簡(jiǎn)介

圖像拼接是將同一場(chǎng)景的多個(gè)重疊圖像拼接成較大的圖像的一種方法，在醫(yī)學(xué)成像、計(jì)算機(jī)視覺(jué)、衛(wèi)星數(shù)據(jù)、軍事目標(biāo)自動(dòng)識(shí)別等領(lǐng)域具有重要意義。圖像拼接的輸出是兩個(gè)輸入圖像的并集。通常用到五個(gè)步驟：

特征提取 Feature Extraction：在所有輸入圖像中檢測(cè)特征點(diǎn)圖像配準(zhǔn) Image Registration：建立了圖像之間的幾何對(duì)應(yīng)關(guān)系，使它們可以在一個(gè)共同的參照系中進(jìn)行變換、比較和分析。大致可以分為以下幾個(gè)類

1、直接使用圖像的像素值的算法,例如,correlation methods

2、在頻域處理的算法,例如,基于快速傅里葉變換(FFT-based)方法;

3、低水平特征的算法low level features,通常用到邊緣和角點(diǎn)，例如，基于特征的方法,

4、高水平特征的算法high-level features,通常用到圖像物體重疊部分，特征關(guān)系，例如，圖論方法（Graph-theoretic methods）

圖像變形 Warping：圖像變形是指將其中一幅圖像的圖像重投影，并將圖像放置在更大的畫(huà)布上。

圖像融合 Blending：圖像融合是通過(guò)改變邊界附近的圖像灰度級(jí)，去除這些縫隙，創(chuàng)建混合圖像，從而在圖像之間實(shí)現(xiàn)平滑過(guò)渡。混合模式(Blend modes)用于將兩層融合到一起。

特征點(diǎn)提取

特征是要匹配的兩個(gè)輸入圖像中的元素，它們是在圖像塊的內(nèi)部。這些圖像塊是圖像中的像素組。對(duì)輸入圖像進(jìn)行Patch匹配。具體解釋如下: 如下圖所示，fig1和fig2給出了一個(gè)很好的patch匹配，因?yàn)閒ig2中有一個(gè)patch看起來(lái)和fig1中的patch非常相似。當(dāng)我們考慮到fig3和fig4時(shí)，這里的patch并不匹配，因?yàn)閒ig4中有很多類似的patch，它們看起來(lái)與fig3中的patch很相似。由于像素強(qiáng)度很相近，所以無(wú)法進(jìn)行精確的特征匹配，

為了給圖像對(duì)提供更好的特征匹配，采用角點(diǎn)匹配，進(jìn)行定量測(cè)量。角點(diǎn)是很好的匹配特性。在視點(diǎn)變化時(shí)，角點(diǎn)特征是穩(wěn)定的。此外，角點(diǎn)的鄰域具有強(qiáng)度突變。利用角點(diǎn)檢測(cè)算法對(duì)圖像進(jìn)行角點(diǎn)檢測(cè)。角點(diǎn)檢測(cè)算法有Harris角點(diǎn)檢測(cè)算法、SIFT特征點(diǎn)檢測(cè)算法((Scale Invariant Feature Transform),FAST算法角點(diǎn)檢測(cè)算法，SURF特征點(diǎn)檢測(cè)算法(Speeded-up robust feature)

Harris角點(diǎn)檢測(cè)算法

Harris算法是一種基于Moravec算法的點(diǎn)特征提取算法。1988年C. Harris 和 M.J Stephens設(shè)計(jì)了一種圖像局部檢測(cè)窗口。通過(guò)在不同的方向上移動(dòng)少量窗口，可以確定強(qiáng)度的平均變化。我們可以通過(guò)觀察小窗口內(nèi)的強(qiáng)度值很容易地識(shí)別角點(diǎn)。

在移動(dòng)窗口時(shí)，平坦區(qū)域在所有方向上均不會(huì)顯示強(qiáng)度的變化。邊緣區(qū)域在沿邊緣方向強(qiáng)度不會(huì)發(fā)生變化。對(duì)于角點(diǎn)，則在各個(gè)方向上產(chǎn)生顯著強(qiáng)度變化。

Harris角點(diǎn)探測(cè)器給出了一種檢測(cè)平坦區(qū)域、邊緣和角點(diǎn)的數(shù)學(xué)方法。Harris檢測(cè)的特征較多，具有旋轉(zhuǎn)不變性和尺度變異性。位移下的強(qiáng)度變化:其中，是窗口函數(shù)，是移動(dòng)后的強(qiáng)度，是單個(gè)像素位置的強(qiáng)度。

Harris角點(diǎn)檢測(cè)算法如下：

1、對(duì)圖像中的每個(gè)像素點(diǎn)計(jì)算自相關(guān)矩陣（autocorrelation matrix M）:?

其中是的偏導(dǎo)數(shù)

2、對(duì)圖像中的每個(gè)像素點(diǎn)做高斯濾波，獲得新的矩陣，離散二維零均值高斯函數(shù)為

3、計(jì)算每個(gè)像素點(diǎn)(x,y)的角點(diǎn)度量，得到，?的范圍是。

4、選擇局部最大值點(diǎn)。Harris方法認(rèn)為特征點(diǎn)與局部最大興趣點(diǎn)的像素值對(duì)應(yīng)。

5、設(shè)置閾值T，檢測(cè)角點(diǎn)。如果?的局部最大值高于閾值，那么此點(diǎn)為角點(diǎn)。

SIFT角點(diǎn)檢測(cè)算法

SIFT算法是尺度不變的特征點(diǎn)檢測(cè)算法，可用于識(shí)別其他圖像中的相似目標(biāo)。SIFT的圖像特征表示為關(guān)鍵點(diǎn)描述符（key-point-descriptors）。在檢查圖像匹配時(shí)，將兩組關(guān)鍵點(diǎn)描述符作為輸入提供給最近鄰搜索(Nearest Neighbor Search，NNS)，并生成一個(gè)緊密匹配的關(guān)鍵點(diǎn)描述符（matching key-point-descriptors）。

SIFT的計(jì)算分為四個(gè)階段:

1、尺度空間構(gòu)造（Scale-space construction）

2、尺度空間極值檢測(cè)(Scale-space extrema detection)

3、關(guān)鍵點(diǎn)定位(key-point localization)

4、方向分配(orientation assignment)和關(guān)鍵點(diǎn)描述符定義(defining key-point descriptors)

第一階段確定潛在的興趣點(diǎn)。它利用高斯函數(shù)的差分(difference of Gaussian function,DOG)搜索所有尺度和圖像位置。第一階段中發(fā)現(xiàn)的所有興趣點(diǎn)的location和scale是確定的。根據(jù)關(guān)鍵點(diǎn)的穩(wěn)定性來(lái)選擇關(guān)鍵點(diǎn)。一個(gè)穩(wěn)定的關(guān)鍵點(diǎn)能夠抵抗圖像失真。

在方向分配環(huán)節(jié)，SIFT算法計(jì)算穩(wěn)定關(guān)鍵點(diǎn)周圍梯度的方向。根據(jù)局部圖像梯度方向，為每個(gè)關(guān)鍵點(diǎn)分配一個(gè)或多個(gè)方向。對(duì)于一組輸入幀，SIFT提取特征。圖像匹配使用Best Bin First(BBF)算法來(lái)估計(jì)輸入幀之間的初始匹配點(diǎn)。為了去除不屬于重疊區(qū)域的不需要的角，使用RANSAC算法。它刪除圖像對(duì)中的錯(cuò)誤匹配。通過(guò)定義幀的大小、長(zhǎng)度和寬度來(lái)實(shí)現(xiàn)幀的重投影。最后進(jìn)行拼接，得到最終的輸出拼接圖像。

在拼接時(shí)，檢查場(chǎng)景每幀中的每個(gè)像素是否屬于扭曲的第二幀。如果是，則為該像素分配來(lái)自第一幀的對(duì)應(yīng)像素的值。SIFT算法既具有旋轉(zhuǎn)不變性，又具有尺度不變性。SIFT非常適合于高分辨率圖像中的目標(biāo)檢測(cè)。它是一種魯棒的圖像比較算法，雖然速度較慢。SIFT算法的運(yùn)行時(shí)間很大，因?yàn)楸容^兩幅圖像需要更多的時(shí)間。

FAST 算法

FAST是Trajkovic和Hedley在1998年創(chuàng)建的角點(diǎn)檢測(cè)算法。對(duì)于FAST，角點(diǎn)的檢測(cè)優(yōu)于邊緣檢測(cè)，因?yàn)榻屈c(diǎn)有二維強(qiáng)度變化，容易從鄰近點(diǎn)中區(qū)分出來(lái)。適用于實(shí)時(shí)圖像處理應(yīng)用程序。

FAST角點(diǎn)探測(cè)器應(yīng)該滿足以下要求：

1、檢測(cè)到的位置要一致，對(duì)噪聲變化不敏感，對(duì)同一場(chǎng)景的多幅圖像不能移動(dòng)。

2、準(zhǔn)確;檢測(cè)到的角點(diǎn)應(yīng)該盡可能接近正確的位置。

3、速度;角落探測(cè)器應(yīng)該足夠快。

原理：首先圍繞一個(gè)候選角點(diǎn)選擇16個(gè)像素點(diǎn)。如果其中有n（n一般為12）個(gè)連續(xù)的像素都比候選角點(diǎn)加上一個(gè)閾值要高，或者比候選角點(diǎn)減去一個(gè)閾值要低，那么此點(diǎn)即為角點(diǎn)（如圖4所示）

為了加快FAST算法的速度，通常會(huì)使用角點(diǎn)響應(yīng)函數(shù)（ corner response function, CRF)。該函數(shù)根據(jù)局部鄰域的圖像強(qiáng)度給出角點(diǎn)強(qiáng)度的數(shù)值。對(duì)圖像進(jìn)行CRF計(jì)算，并將CRF的局部最大值作為角點(diǎn)，采用多網(wǎng)格（multi-grid）技術(shù)提高了算法的計(jì)算速度，并對(duì)檢測(cè)到的假角點(diǎn)進(jìn)行了抑制。FAST是一種精確、快速的算法，具有良好的定位(位置精度)和較高的點(diǎn)可靠性。FAST的角點(diǎn)檢測(cè)的算法難點(diǎn)在于最佳閾值的選擇。

SURF算法

Speed-up Robust Feature(SURF)角點(diǎn)探測(cè)器采用三個(gè)特征檢測(cè)步驟;檢測(cè)(Detection)、描述(Description)、匹配(Matching)，SURF通過(guò)考慮被檢測(cè)點(diǎn)的質(zhì)量，加快了位移的檢測(cè)過(guò)程。它更注重加快匹配步驟。使用Hessian矩陣和低維描述符來(lái)顯著提高匹配速度。SURF在計(jì)算機(jī)視覺(jué)社區(qū)中得到了廣泛的應(yīng)用。SURF在不變特征定位上十分有效和魯棒

圖像配準(zhǔn)

在特征點(diǎn)被檢測(cè)出來(lái)之后，我們需要以某種方式將它們關(guān)聯(lián)起來(lái),可以通過(guò)NCC或者SDD（Sum of Squared Difference）方法來(lái)確定其對(duì)應(yīng)關(guān)系。

歸一化互相關(guān)（normalized cross correlation，NCC）

互相關(guān)的工作原理是分析第一幅圖像中每個(gè)點(diǎn)周圍的像素窗口，并將它們與第二幅圖像中每個(gè)點(diǎn)周圍的像素窗口關(guān)聯(lián)起來(lái)。將雙向相關(guān)性最大的點(diǎn)作為對(duì)應(yīng)的對(duì)。

基于圖像強(qiáng)度值計(jì)算在兩個(gè)圖像中的每個(gè)位移（shifts）的“窗口”之間的相似性

其中，是窗口的平均值圖像和分別是兩張圖片。 是窗口的像素坐標(biāo)，是通過(guò)NCC系數(shù)計(jì)算出的位移或偏移。NCC系數(shù)的范圍為。NCC峰值相對(duì)應(yīng)的位移參數(shù)表示兩個(gè)圖像之間的幾何變換。此方法的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單，但是速度特別慢。此外，此類算法要求源圖像之間必須有顯著的重疊。

互信息（Mutual Information, MI）

互信息測(cè)量基于兩個(gè)圖像之間共享信息數(shù)量的相似性。

兩個(gè)圖像與之間的MI以熵表示：

其中， 和分別是和的熵。表示兩個(gè)圖像之間的聯(lián)合熵。

是可能的灰度值，是的概率分布函數(shù)

然而，從圖中我們可以看到，許多點(diǎn)被錯(cuò)誤地關(guān)聯(lián)在一起。

計(jì)算單應(yīng)矩陣

單應(yīng)矩陣估計(jì)是圖像拼接的第三步。在單應(yīng)矩陣估計(jì)中，不屬于重疊區(qū)域的不需要的角被刪除。采用RANSAC算法進(jìn)行單應(yīng)。

隨機(jī)樣本一致算法RANSAC(random sample consensus)

RANSAC算法從可能含有異常值的觀測(cè)數(shù)據(jù)集中擬合數(shù)學(xué)模型，是一種魯棒參數(shù)估計(jì)的迭代方法。該算法是不確定性的，因?yàn)樗辉谝欢ǖ母怕氏庐a(chǎn)生一個(gè)合理的結(jié)果，隨著執(zhí)行更多的迭代，這個(gè)概率會(huì)增加。RANSAC算法用于在存在大量可用數(shù)據(jù)外行的情況下以魯棒的方式擬合模型。RANSAC算法在計(jì)算機(jī)視覺(jué)中有許多應(yīng)用。

RANSAC原理

從數(shù)據(jù)集中隨機(jī)選取一組數(shù)據(jù)并認(rèn)為是有效數(shù)據(jù)（內(nèi)點(diǎn)）來(lái)確定待定參數(shù)模型，以此模型測(cè)試數(shù)據(jù)集中的所有數(shù)據(jù)，滿足該模型的數(shù)據(jù)成為內(nèi)點(diǎn)，反之為外點(diǎn)（通常為噪聲、錯(cuò)誤測(cè)量或不正確數(shù)據(jù)的點(diǎn)），迭代執(zhí)行，直到某一個(gè)參數(shù)模型得到的內(nèi)點(diǎn)數(shù)最大，則該模型為最優(yōu)模型?？紤]如下假設(shè):

1、參數(shù)可以從N個(gè)數(shù)據(jù)項(xiàng)中估計(jì)。

2、可用的數(shù)據(jù)項(xiàng)總共是M。

3、隨機(jī)選擇的數(shù)據(jù)項(xiàng)成為好模型的一部分的概率為。

4、如果存在一個(gè)很好的擬合，那么算法在沒(méi)有找到一個(gè)很好的擬合的情況下退出的概率是。

RANSAC步驟

1、隨機(jī)選取N個(gè)數(shù)據(jù)（3個(gè)點(diǎn)對(duì)）

2、估計(jì)參數(shù)x（計(jì)算變換矩陣H）

3、根于使用者設(shè)定的閾值，找到M中合適該模型向量x的的數(shù)據(jù)對(duì)總數(shù)量K（ 計(jì)算每個(gè)匹配點(diǎn)經(jīng)過(guò)變換矩陣后到對(duì)應(yīng)匹配點(diǎn)的距離，根據(jù)預(yù)先設(shè)定的閾值將匹配點(diǎn)集合分為內(nèi)點(diǎn)和外點(diǎn)，如果內(nèi)點(diǎn)足夠多，則H足夠合理，用所有內(nèi)點(diǎn)重新估計(jì)H）。

4、如果符合的數(shù)量K足夠大，則接受該模型并退出

5、重復(fù)1-4步驟 L次

6、到這一步退出

K有多大取決于我們認(rèn)為屬于合適結(jié)構(gòu)的數(shù)據(jù)的百分比以及圖像中有多少結(jié)構(gòu)。如果存在多個(gè)結(jié)構(gòu)，則在成功擬合后，刪除擬合數(shù)據(jù)并重做RANSAC。

迭代次數(shù)L可以用如下公式計(jì)算：

優(yōu)點(diǎn)：可以robust地估計(jì)模型參數(shù)缺點(diǎn)：迭代次數(shù)無(wú)上限，設(shè)置的迭代次數(shù)會(huì)影響算法時(shí)間復(fù)雜度和精確程度，并且需要預(yù)設(shè)閾值

在執(zhí)行RANSAC之后，我們只能在圖像中看到正確的匹配，因?yàn)镽ANSAC找到了一個(gè)與大多數(shù)點(diǎn)相關(guān)的單應(yīng)矩陣，并將不正確的匹配作為異常值丟棄

單應(yīng)矩陣（Homography）

有了兩組相關(guān)點(diǎn)，接下來(lái)就需要建立兩組點(diǎn)的轉(zhuǎn)換關(guān)系，也就是圖像變換關(guān)系。單應(yīng)性是兩個(gè)空間之間的映射，常用于表示同一場(chǎng)景的兩個(gè)圖像之間的對(duì)應(yīng)關(guān)系，可以匹配大部分相關(guān)的特征點(diǎn)，并且能實(shí)現(xiàn)圖像投影，使一張圖通過(guò)投影和另一張圖實(shí)現(xiàn)大面積的重合。

設(shè)2個(gè)圖像的匹配點(diǎn)分別是,，則必須滿足公式：

且由于兩向量共線，所以其中， 為8參數(shù)的變換矩陣，可知四點(diǎn)確定一個(gè)H

令

則有N個(gè)點(diǎn)對(duì)給出2N個(gè)線性約束。

用RANSAC方法估算H：

1、首先檢測(cè)兩邊圖像的角點(diǎn)

2、在角點(diǎn)之間應(yīng)用方差歸一化相關(guān)，收集相關(guān)性足夠高的對(duì)，形成一組候選匹配。

3、選擇四個(gè)點(diǎn)，計(jì)算H

4、選擇與單應(yīng)性一致的配對(duì)。如果對(duì)于某些閾值:Dist(Hp、q) <ε，則點(diǎn)對(duì)(p, q)被認(rèn)為與單應(yīng)性H一致

5、重復(fù)34步，直到足夠多的點(diǎn)對(duì)滿足H

6、使用所有滿足條件的點(diǎn)對(duì)，通過(guò)公式重新計(jì)算H

圖像變形和融合

最后一步是將所有輸入圖像變形并融合到一個(gè)符合的輸出圖像中?；旧希覀兛梢院?jiǎn)單地將所有輸入的圖像變形到一個(gè)平面上，這個(gè)平面名為復(fù)合全景平面。

圖像變形步驟

首先計(jì)算每個(gè)輸入圖像的變形圖像坐標(biāo)范圍，得到輸出圖像大小，可以很容易地通過(guò)映射每個(gè)源圖像的四個(gè)角并且計(jì)算坐標(biāo)(x,y)的最小值和最大值確定輸出圖像的大小。最后，需要計(jì)算指定參考圖像原點(diǎn)相對(duì)于輸出全景圖的偏移量的偏移量xoffset和偏移量yoffset。

下一步是使用上面所述的反向變形，將每個(gè)輸入圖像的像素映射到參考圖像定義的平面上，分別執(zhí)行點(diǎn)的正向變形和反向變形。

平滑過(guò)渡（transition smoothing）圖像融合方法包括 羽化（feathering）， 金字塔（pyramid）， 梯度（gradient）

圖形融合

最后一步是在重疊區(qū)域融合像素顏色，以避免接縫。最簡(jiǎn)單的可用形式是使用羽化（feathering），它使用加權(quán)平均顏色值融合重疊的像素。我們通常使用alpha因子，通常稱為alpha通道，它在中心像素處的值為1，在與邊界像素線性遞減后變?yōu)?。當(dāng)輸出拼接圖像中至少有兩幅重疊圖像時(shí)，我們將使用如下的alpha值來(lái)計(jì)算其中一個(gè)像素處的顏色：假設(shè)兩個(gè)圖像 ,在輸出圖像中重疊；每個(gè)像素點(diǎn)在圖像，其中（R,G,B）是像素的顏色值，我們將在縫合后的輸出圖像中計(jì)算(x, y)的像素值：

小結(jié)

上述內(nèi)容對(duì)一些常用的算法進(jìn)行了簡(jiǎn)單的概述。Harris角點(diǎn)檢測(cè)方法具有魯棒性和旋轉(zhuǎn)不變性。然而，它是尺度變化的。FAST算法具有旋轉(zhuǎn)不變性和尺度不變性，且具有較好的執(zhí)行時(shí)間。但是當(dāng)有噪聲存在時(shí)，它的性能很差。SIFT算法具有旋轉(zhuǎn)不變性和尺度不變性，并且在有噪聲情況下更有效。它具有非常明顯的特征。然而，它受到光照變化的影響。該算法在執(zhí)行時(shí)間和光照不變性方面具有較好的性能。

審核編輯：劉清