圖像拼接技術
簡介
圖像拼接是将同一場景的多個重疊圖像拼接成較大的圖像的一種方法，在醫學成像、計算機視覺、衛星資料、軍事目标自動識别等領域具有重要意義。圖像拼接的輸出是兩個輸入圖像的并集。所謂圖像拼接就是将兩張有共同拍攝區域的圖像無縫拼接在一起。這種應用可應用于車站的動态檢測、商城的人流檢測、十字路口的交通檢測等，給人以全景圖像，告别目前的監控牆或視訊區域顯示的時代，減輕從業人員“眼”的壓力。
基本思想：圖像拼接并非簡單的将兩張有共同區域的圖像把相同的區域重合起來，由于兩張圖像拍攝的角度與位置不同，雖然有共同的區域，但拍攝時相機的内參與外參均不相同，是以簡單的覆寫拼接是不合理的。是以，對于圖像拼接需要以一張圖像為基準對另外一張圖像進行相應的變換（透視變換），然後将透視變換後的圖像進行簡單的平移後與基準圖像的共同區域進行重合。
說明：
1、圖像預處理是為了增強圖像的特征，預處理可以包含：灰階化、去燥、畸變校正等。
2、特征點提取可用的方法有：sift、surf、fast、Harris等，sift具有旋轉與縮放不變性，surf為sift的加速，檢測效果都不錯，在此先用sift進行實作。
3、單應性矩陣求取時要清楚映射關系，是第一張圖像空間到第二張圖像空間的映射，還是第二張圖像到第一張圖像的映射，這個在變換的時候很重要。
4、判斷左右 （上下）圖像是為了明确拼接關系,建議将左右圖像的判斷放在求取單應性矩陣之前，這樣映射關系不至于颠倒。否則将會出現拼接成的圖像有一半是空的。
通常用到五個步驟：
特征提取 Feature Extraction：在所有輸入圖像中檢測特征點圖像配準 Image Registration：建立了圖像之間的幾何對應關系，使它們可以在一個共同的參照系中進行變換、比較和分析。大緻可以分為以下幾個類
1. 直接使用圖像的像素值的算法,例如,correlation methods
2. 在頻域處理的算法,例如,基于快速傅裡葉變換(FFT-based)方法;
3. 低水準特征的算法low level features,通常用到邊緣和角點，例如，基于特征的方法,
4. 高水準特征的算法high-level features,通常用到圖像物體重疊部分，特征關系，例如，圖論方法（Graph-theoretic methods）
圖像變形 Warping：圖像變形是指将其中一幅圖像的圖像重投影，并将圖像放置在更大的畫布上。
圖像融合 Blending：圖像融合是通過改變邊界附近的圖像灰階級，去除這些縫隙，建立混合圖像，進而在圖像之間實作平滑過渡。混合模式(Blend modes)用于将兩層融合到一起。
特征點提取
特征是要比對的兩個輸入圖像中的元素，它們是在圖像塊的内部。這些圖像塊是圖像中的像素組。對輸入圖像進行Patch比對。具體解釋如下: 如下圖所示，fig1和fig2給出了一個很好的patch比對，因為fig2中有一個patch看起來和fig1中的patch非常相似。當考慮到fig3和fig4時，這裡的patch并不比對，因為fig4中有很多類似的patch，它們看起來與fig3中的patch很相似。由于像素強度很相近，是以無法進行精确的特征比對，
Harris角點檢測算法
Harris算法是一種基于Moravec算法的點特征提取算法。1988年C. Harris 和 M.J Stephens設計了一種圖像局部檢測視窗。通過在不同的方向上移動少量視窗，可以确定強度的平均變化。可以通過觀察小視窗内的強度值很容易地識别角點。在移動視窗時，平坦區域在所有方向上均不會顯示強度的變化。邊緣區域在沿邊緣方向強度不會發生變化。對于角點，則在各個方向上産生顯著強度變化。Harris角點探測器給出了一種檢測平坦區域、邊緣和角點的數學方法。Harris檢測的特征較多，具有旋轉不變性和尺度變異性。
位移下的強度變化:
其中，
是視窗函數，
是移動後的強度，
是單個像素位置的強度。
Harris角點檢測算法如下：
1. 對圖像中的每個像素點（x，y）計算自相關矩陣M（autocorrelation matrix M）:
其中
是
的偏導數。
2. 對圖像中的每個像素點做高斯濾波，獲得新的矩陣M，離散二維零均值高斯函數為
3. 計算每個像素點(x,y)的角點度量，得到
，k 的範圍是
。
4. 選擇局部最大值點。Harris方法認為特征點與局部最大興趣點的像素值對應。
5. 設定門檻值T，檢測角點。如果 R 的局部最大值高于門檻值T，那麼此點為角點。
SIFT角點檢測算法
SIFT算法是尺度不變的特征點檢測算法，可用于識别其他圖像中的相似目标。SIFT的圖像特征表示為關鍵點描述符（key-point-descriptors）。在檢查圖像比對時，将兩組關鍵點描述符作為輸入提供給最近鄰搜尋(Nearest Neighbor Search，NNS)，并生成一個緊密比對的關鍵點描述符（matching key-point-descriptors）。
SIFT的計算分為四個階段:
1. 尺度空間構造（Scale-space construction）
2. 尺度空間極值檢測(Scale-space extrema detection)
3. 關鍵點定位(key-point localization)
4. 方向配置設定(orientation assignment)和關鍵點描述符定義(defining key-point descriptors)
第一階段确定潛在的興趣點。它利用高斯函數的差分(difference of Gaussian function,DOG)搜尋所有尺度和圖像位置。第一階段中發現的所有興趣點的location和scale是确定的。根據關鍵點的穩定性來選擇關鍵點。一個穩定的關鍵點能夠抵抗圖像失真。在方向配置設定環節，SIFT算法計算穩定關鍵點周圍梯度的方向。根據局部圖像梯度方向，為每個關鍵點配置設定一個或多個方向。對于一組輸入幀，SIFT提取特征。圖像比對使用Best Bin First(BBF)算法來估計輸入幀之間的初始比對點。為了去除不屬于重疊區域的不需要的角，使用RANSAC算法。它删除圖像對中的錯誤比對。通過定義幀的大小、長度和寬度來實作幀的重投影。最後進行拼接，得到最終的輸出拼接圖像。在拼接時，檢查場景每幀中的每個像素是否屬于扭曲的第二幀。如果是，則為該像素配置設定來自第一幀的對應像素的值。SIFT算法既具有旋轉不變性，又具有尺度不變性。SIFT非常适合于高分辨率圖像中的目标檢測。它是一種魯棒的圖像比較算法，雖然速度較慢。SIFT算法的運作時間很大，因為比較兩幅圖像需要更多的時間。
FAST 算法
FAST是Trajkovic和Hedley在1998年建立的角點檢測算法。對于FAST，角點的檢測優于邊緣檢測，因為角點有二維強度變化，容易從鄰近點中區分出來。适用于實時圖像處理應用程式。
FAST角點探測器應該滿足以下要求：
1. 檢測到的位置要一緻，對噪聲變化不敏感，對同一場景的多幅圖像不能移動。
2. 準确;檢測到的角點應該盡可能接近正确的位置。
3. 速度;角落探測器應該足夠快。
原理：首先圍繞一個候選角點選擇16個像素點。如果其中有n（n一般為12）個連續的像素都比候選角點加上一個門檻值要高，或者比候選角點減去一個門檻值要低，那麼此點即為角點（如圖4所示）
為了加快FAST算法的速度，通常會使用角點響應函數（ corner response function, CRF)。該函數根據局部鄰域的圖像強度給出角點強度的數值。對圖像進行CRF計算，并将CRF的局部最大值作為角點，采用多網格（multi-grid）技術提高了算法的計算速度，并對檢測到的假角點進行了抑制。FAST是一種精确、快速的算法，具有良好的定位(位置精度)和較高的點可靠性。FAST的角點檢測的算法難點在于最佳門檻值的選擇。
SURF算法
Speed-up Robust Feature(SURF)角點探測器采用三個特征檢測步驟;檢測(Detection)、描述(Description)、比對(Matching)，SURF通過考慮被檢測點的品質，加快了位移的檢測過程。它更注重加快比對步驟。使用Hessian矩陣和低維描述符來顯著提高比對速度。SURF在計算機視覺社群中得到了廣泛的應用。SURF在不變特征定位上十分有效和魯棒
圖像配準
在特征點被檢測出來之後，需要以某種方式将它們關聯起來,可以通過NCC或者SDD（Sum of Squared Difference）方法來确定其對應關系。
歸一化互相關（normalized cross correlation，NCC）
互相關的工作原理是分析第一幅圖像中每個點周圍的像素視窗，并将它們與第二幅圖像中每個點周圍的像素視窗關聯起來。将雙向相關性最大的點作為對應的對。
基于圖像強度值計算在兩個圖像中的每個位移（shifts）的“視窗”之間的相似性
是視窗的平均值圖像
和
分别是兩張圖檔。
是視窗的像素坐标，
是通過NCC系數計算出的位移或偏移。NCC系數的範圍為
。NCC峰值相對應的位移參數表示兩個圖像之間的幾何變換。此方法的優點是計算簡單，但是速度特别慢。此外，此類算法要求源圖像之間必須有顯著的重疊。
互資訊（Mutual Information, MI）
互資訊測量基于兩個圖像之間共享資訊數量的相似性。
兩個圖像
與
之間的MI以熵表示：
分别是
的熵。
表示兩個圖像之間的聯合熵。
g是
可能的灰階值，
是g的機率分布函數
然而，從圖中可以看到，許多點被錯誤地關聯在一起。
計算單應矩陣
單應矩陣估計是圖像拼接的第三步。在單應矩陣估計中，不屬于重疊區域的不需要的角被删除。采用RANSAC算法進行單應。
随機樣本一緻算法RANSAC(random sample consensus)
RANSAC算法從可能含有異常值的觀測資料集中拟合數學模型，是一種魯棒參數估計的疊代方法。該算法是不确定性的，因為它隻在一定的機率下産生一個合理的結果，随着執行更多的疊代，這個機率會增加。RANSAC算法用于在存在大量可用資料外行的情況下以魯棒的方式拟合模型。RANSAC算法在計算機視覺中有許多應用。
RANSAC原理
從資料集中随機選取一組資料并認為是有效資料（内點）來确定待定參數模型，以此模型測試資料集中的所有資料，滿足該模型的資料成為内點，反之為外點（通常為噪聲、錯誤測量或不正确資料的點），疊代執行，直到某一個參數模型得到的内點數最大，則該模型為最優模型。考慮如下假設:
1. 參數可以從N個資料項中估計。
2. 可用的資料項總共是M。
3. 随機選擇的資料項成為好模型的一部分的機率為' data-ratio=0.9473684210526315 data-type=gif data-w=19 src="https://mmbiz.qpic.cn/mmbiz_png/rqpicxXx8cNmRBjhqlOPp4jnugHicZ97nAsEhLvRd1gm9NQQJbQibZiauHJkHX6ibakTWN0Enq3uSJUSbtnlYEqWmrA/640?wx_fmt=gif" _width=19px crossorigin=anonymous class="" data-fail=0 v:shapes="_x0000_i1027"> 。
4. 如果存在一個很好的拟合，那麼算法在沒有找到一個很好的拟合的情況下退出的機率是
RANSAC步驟
1. 随機選取N個資料（3個點對）
2. 估計參數x（計算變換矩陣H）
3. 根于使用者設定的門檻值，找到M中合适該模型向量x的的資料對總數量K（ 計算每個比對點經過變換矩陣後到對應比對點的距離，根據預先設定的門檻值将比對點集合分為内點和外點，如果内點足夠多，則H足夠合理，用所有内點重新估計H）。
4. 如果符合的數量K足夠大，則接受該模型并退出
5. 重複1-4步驟 L次
6. 到這一步退出
K有多大取決于認為屬于合适結構的資料的百分比以及圖像中有多少結構。如果存在多個結構，則在成功拟合後，删除拟合資料并重做RANSAC。
疊代次數L可以用如下公式計算：
優點：可以robust地估計模型參數 缺點：疊代次數無上限，設定的疊代次數會影響算法時間複雜度和精确程度，并且需要預設門檻值
在執行RANSAC之後，隻能在圖像中看到正确的比對，因為RANSAC找到了一個與大多數點相關的單應矩陣，并将不正确的比對作為異常值丢棄
單應矩陣（Homography）
有了兩組相關點，接下來就需要建立兩組點的轉換關系，也就是圖像變換關系。單應性是兩個空間之間的映射，常用于表示同一場景的兩個圖像之間的對應關系，可以比對大部分相關的特征點，并且能實作圖像投影，使一張圖通過投影和另一張圖實作大面積的重合。
設2個圖像的比對點分别是
,
，則必須滿足公式：
且由于兩向量共線，是以其中，H 為8參數的變換矩陣，可知四點确定一個H
令
則有Bh=0，N個點對給出2N個線性限制。
用RANSAC方法估算H：
1. 首先檢測兩邊圖像的角點
2. 在角點之間應用方差歸一化相關，收集相關性足夠高的對，形成一組候選比對。
3. 選擇四個點，計算H
4. 選擇與單應性一緻的配對。如果對于某些門檻值:Dist(Hp、q) <ε，則點對(p, q)被認為與單應性H一緻
5. 重複34步，直到足夠多的點對滿足H
6. 使用所有滿足條件的點對，通過公式重新計算H
圖像變形和融合
最後一步是将所有輸入圖像變形并融合到一個符合的輸出圖像中。基本上，可以簡單地将所有輸入的圖像變形到一個平面上，這個平面名為複合全景平面。
圖像變形步驟
1. 首先計算每個輸入圖像的變形圖像坐标範圍，得到輸出圖像大小，可以很容易地通過映射每個源圖像的四個角并且計算坐标(x,y)的最小值和最大值确定輸出圖像的大小。最後，需要計算指定參考圖像原點相對于輸出全景圖的偏移量的偏移量xoffset和偏移量yoffset。
2. 下一步是使用上面所述的反向變形，将每個輸入圖像的像素映射到參考圖像定義的平面上，分别執行點的正向變形和反向變形。
平滑過渡（transition smoothing）圖像融合方法包括 羽化（feathering）， 金字塔（pyramid）， 梯度（gradient）
圖形融合
最後一步是在重疊區域融合像素顔色，以避免接縫。最簡單的可用形式是使用羽化（feathering），它使用權重平均顔色值融合重疊的像素。通常使用alpha因子，通常稱為alpha通道，它在中心像素處的值為1，在與邊界像素線性遞減後變為0。當輸出拼接圖像中至少有兩幅重疊圖像時，将使用如下的alpha值來計算其中一個像素處的顔色：假設兩個圖像
, 在輸出圖像中重疊；每個像素點（x，y）在圖像
，其中（R,G,B）是像素的顔色值，将在縫合後的輸出圖像中計算(x, y)的像素值：
小結
上述内容對一些常用的算法進行了簡單的概述。Harris角點檢測方法具有魯棒性和旋轉不變性。然而，它是尺度變化的。FAST算法具有旋轉不變性和尺度不變性，且具有較好的執行時間。但是當有噪聲存在時，它的性能很差。SIFT算法具有旋轉不變性和尺度不變性，并且在有噪聲情況下更有效。它具有非常明顯的特征。然而，它受到光照變化的影響。該算法在執行時間和光照不變性方面具有較好的性能。
參考
1. OpenCV探索之路（二十四）圖像拼接和圖像融合技術
人工智能晶片與自動駕駛