基于重疊區(qū)域位置估計(jì)的圖像拼接

秦禹杰 孫先松 李軒

摘要：針對(duì)圖像拼接中特征點(diǎn)提取和匹配耗時(shí)長(zhǎng)的問(wèn)題，提出了一種重疊區(qū)域位置估計(jì)的圖像拼接方法。首先輸入圖像對(duì)并進(jìn)行預(yù)處理，得到二值梯度圖;其次兩幅圖像水平向滑動(dòng)，記錄每次重合的區(qū)域;然后將水平向重合區(qū)域縱向滑動(dòng)，計(jì)算每次重合時(shí)的方差，并取最小值作為水平向重合區(qū)域的相似度;最后在配準(zhǔn)階段只對(duì)相似度值最小的水平向重合區(qū)域進(jìn)行特征點(diǎn)提取和匹配，并利用隨機(jī)抽樣一致（RANSAC） 算法進(jìn)行單應(yīng)性矩陣計(jì)算和魯棒校驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該方法不僅有助于估計(jì)圖像對(duì)的重疊區(qū)域位置，而且匹配對(duì)和特征點(diǎn)的比值提升了0.2～5倍，顯著提高了圖像配準(zhǔn)的效率。

關(guān)鍵詞： 圖像拼接; 重疊區(qū)域位置估計(jì); 圖像配準(zhǔn); 隨機(jī)抽樣一致; 魯棒校驗(yàn)

中圖分類號(hào)：TP391? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）25-0015-05

開(kāi)放科學(xué)（資源服務(wù)） 標(biāo)識(shí)碼（OSID） ：

1 概述

因?yàn)橄鄼C(jī)拍攝視角的局限性，單幅圖像的視野相比于人類雙目視覺(jué)的視野要小，因此在需要獲得大視野圖像時(shí)，就得使用圖像拼接技術(shù)對(duì)兩幅或多幅圖像進(jìn)行拼接。圖像拼接技術(shù)在許多領(lǐng)域有著應(yīng)用，如全景視頻[1]、虛擬現(xiàn)實(shí)[2]和礦物分析[3]等。

圖像拼接技術(shù)主要有兩個(gè)步驟，分別是圖像配準(zhǔn)和圖像融合，其中圖像配準(zhǔn)是關(guān)鍵，直接決定了圖像拼接的效率和質(zhì)量。圖像配準(zhǔn)又由特征提取、特征匹配、單應(yīng)性矩陣計(jì)算和圖像插值與變換組成，其中特征提取和特征匹配最為耗時(shí)，一般來(lái)說(shuō)至少占整個(gè)拼接計(jì)算時(shí)間的60%。特征提取算法用于獲取圖像的特征信息，如Harris[4]、SIFT[5]、SURF[6]等。特征匹配算法的目的是通過(guò)特征描述符距離計(jì)算找到匹配對(duì)，從而確定重疊區(qū)域的位置和圖像變換的參考圖像，但當(dāng)非重疊區(qū)域的無(wú)效特征點(diǎn)較多時(shí)，不僅會(huì)降低圖像配準(zhǔn)的效率，而且會(huì)影響單應(yīng)性矩陣的質(zhì)量，特別是在進(jìn)行大批量圖像拼接的時(shí)候。

為了更有效率地獲得優(yōu)質(zhì)匹配對(duì)，找到重疊區(qū)域，研究人員在圖像配準(zhǔn)方面做了一些工作。針對(duì)特征點(diǎn)提取效率問(wèn)題，Qu等人[7]提出了一種基于二值子圖像像素個(gè)數(shù)和方差相似度的重疊區(qū)域位置估計(jì)算法，使特征點(diǎn)的提取更有針對(duì)性，優(yōu)點(diǎn)在于大量無(wú)序圖像拼接時(shí)能減少較多計(jì)算時(shí)間，但沒(méi)有給出估計(jì)錯(cuò)誤的解決方案和提及準(zhǔn)確率的問(wèn)題。針對(duì)特征點(diǎn)匹配效率問(wèn)題，Qin等人[8]提出了一種基于分割子圖像和壓縮的匹配算法，使用壓縮了高度的10個(gè)子圖像分別進(jìn)行特征點(diǎn)匹配，優(yōu)點(diǎn)在于可以有效利用計(jì)算平臺(tái)的硬件優(yōu)勢(shì)，并獲得更多匹配對(duì)，但子圖像只包含了部分原圖像的特征信息，較容易產(chǎn)生錯(cuò)誤匹配對(duì)，降低了單應(yīng)性矩陣的質(zhì)量。

本文的主要思想是采用圖像處理的方式對(duì)重疊區(qū)域位置進(jìn)行估計(jì)，減少無(wú)效特征點(diǎn)提取和匹配的計(jì)算時(shí)間，從而提高圖像配準(zhǔn)的效率，它的優(yōu)點(diǎn)是可以分塊并行計(jì)算，且實(shí)現(xiàn)起來(lái)較為容易。

2 圖像拼接算法

2.1 本文算法流程

本文的圖像預(yù)處理和估計(jì)限制條件是保障估計(jì)準(zhǔn)確率的關(guān)鍵，圖像預(yù)處理可以為后面的步驟提供有大量特征信息的圖像，估計(jì)限制條件可以有效防止時(shí)間消耗，兩者共同保證了本算法的可靠性，在此基礎(chǔ)上計(jì)算水平和垂直方向滑動(dòng)重合時(shí)的方差，并對(duì)估計(jì)出的重疊區(qū)域提取和匹配特征點(diǎn)。本文的算法流程如圖1所示。

2.2 重疊區(qū)域估計(jì)

（1） 圖像預(yù)處理

輸入兩幅圖像后，首先進(jìn)行灰度化，再進(jìn)行雙邊濾波。相較于高斯濾波，雙邊濾波的優(yōu)勢(shì)在于去除圖像噪聲的同時(shí)能較大程度保留邊緣特征信息。本文模板尺寸取15*15，空間距離權(quán)重模板方差取20，相似性權(quán)重模板方差取50。

相比于單純的灰度二值化，梯度圖更能對(duì)特征進(jìn)行描述，且具有光照不變性，梯度圖提取本文使用sobel算子。

使用自適應(yīng)閾值算法對(duì)其二值化。閾值矩陣計(jì)算，本文選用高斯濾波模板，模板尺寸取15*15，常數(shù)項(xiàng)取-2。對(duì)大于閾值的點(diǎn)設(shè)為255（白色） ，小于則設(shè)為0（黑色） ，即可得到二值梯度圖。

一般來(lái)說(shuō)，得到的梯度圖白色區(qū)域較細(xì)，可以對(duì)二值梯度圖進(jìn)行膨脹處理，本文膨脹核尺寸取5*5。為了縮短計(jì)算時(shí)間，將二值梯度圖的高度壓縮1/2。圖像預(yù)處理效果如圖2所示。

（2） 重疊區(qū)域位置估計(jì)

若事先知曉要進(jìn)行圖像拼接，在拍攝圖像的時(shí)候，通常是以自身為旋轉(zhuǎn)點(diǎn)，每拍攝一張圖像就橫向旋轉(zhuǎn)一定的角度，或者是進(jìn)行橫向平移式的拍攝。基于此，可以針對(duì)性地對(duì)重疊區(qū)域位置進(jìn)行估計(jì)。

圖像分割的份數(shù)取20，垂直滑動(dòng)單向次數(shù)取10，則水平滑動(dòng)總重合次數(shù)為39，垂直滑動(dòng)總重合次數(shù)為21，通過(guò)對(duì)符號(hào)的使用，滑動(dòng)取方差估計(jì)重疊區(qū)域位置算法的步驟如下：

輸入：兩張大小相同的圖像src1和src2。

輸出：src1和src2的估計(jì)重疊區(qū)域子圖像。

1） 對(duì)src1和src2進(jìn)行預(yù)處理，得到高度壓縮為1/2的二值梯度圖img1和img2;

2） 將img1和img2按src1->width/20列的跨度進(jìn)行水平滑動(dòng)，每次重合的區(qū)域記錄到數(shù)組hOverlap1[i]和hOverlap2[j]（i，j = 0，1，2，…，39）;

3） 取出hOverlap1[i]和hOverlap2[j]（i=j）按src1->height/200行的跨度進(jìn)行垂直滑動(dòng)（即在縱向1/5的區(qū)域內(nèi)滑動(dòng)） ，每次重合的區(qū)域記錄到二維數(shù)組vOverlap1[i][k]和vOverlap2[j][l]（i， j = 0，1，2，…，39; k， l = 0，1，2，…，21）;

4） 計(jì)算|vOverlap1[i][k] - vOverlap2[j][l]|（i=j， k=l）的方差，記錄到二維數(shù)組vStdDev[u][v] （u = 0，1，2，…，39; v = 0，1，2，…，21）;

5） 找出vStdDev[u][v]（u = 0，1，2，…，39）各一維數(shù)組的最小值，記錄到數(shù)組hStdDev[m]（m = 0，1，2，…，39）;

6） 找出hStdDev[m]的最小值Shmin，并獲得其元素序號(hào)idx;

7） 將src1和src2按src1->Width/20列的跨度進(jìn)行水平滑動(dòng)，每次重合的區(qū)域記錄到數(shù)組overlap1[i]和overlap2[j]（i，j = 0，1，2，…，39），并將overlap1[i]和overlap2[j]（i=j=idx）作為估計(jì)重疊區(qū)域;

8） 從數(shù)組hStdDev[m]中刪除最小值Shmin并計(jì)算均值M，然后計(jì)算M-Dhmin，若差值小于閾值t1則不信任估計(jì)重疊區(qū)域并退出算法，若大于閾值t1則進(jìn)行下一步。

9） 若估計(jì)重疊區(qū)域面積占比小于30%，則將估計(jì)重疊區(qū)域調(diào)整為對(duì)應(yīng)的30%面積區(qū)域，然后返回估計(jì)重疊區(qū)域子圖像。

滑動(dòng)示意圖如圖3所示，靠左邊的圖表示右滑和上滑的圖像，靠右邊的圖表示左滑和下滑的圖像，中間交叉部分表示重合的區(qū)域。

為了保證算法的效率，在滑動(dòng)時(shí)只按一定跨度進(jìn)行滑動(dòng)。為了保證方差相似度的質(zhì)量，M和Dhmin的差要大于閾值t1，以及重疊區(qū)域面積占比設(shè)置下限為30%。垂直滑動(dòng)跨度取src1->High/200行，是由0.2*0.5*src1->height/20計(jì)算得來(lái)，0.5是因?yàn)楦叨葔嚎s了1/2，0.2是為了能在縱向1/5的區(qū)域內(nèi)搜索。為了減少計(jì)算量，可以用標(biāo)準(zhǔn)差值代替方差值表示相似度。

2.3 圖像配準(zhǔn)

相比于SIFT（Scale-invariant feature transform），SURF在抗干擾和計(jì)算速度上更有優(yōu)勢(shì)[9]。本文為了兼顧計(jì)算時(shí)間和特征不變性，故采用SURF。為了減少特征點(diǎn)提取的計(jì)算量，本文將圖像分割為20份并行計(jì)算，同樣也是為了配合算法1中的水平滑動(dòng)跨度。圖像對(duì)數(shù)量閾值設(shè)為t2。特征點(diǎn)匹配方面，為了提高匹配對(duì)的質(zhì)量，在構(gòu)建k-d樹(shù)的基礎(chǔ)上進(jìn)行了比率檢驗(yàn)和交叉檢測(cè)[10]，然后使用RANSAC算法[11]得到內(nèi)點(diǎn)。

（1） 單應(yīng)矩陣與內(nèi)點(diǎn)計(jì)算

利用齊次坐標(biāo)進(jìn)行變換，匹配點(diǎn)對(duì)有如下變換關(guān)系：

[h1h2h3h4h5h6h7h8h9uv1=u'v'1] （1）

等式左邊的大矩陣是單應(yīng)矩陣H，其自由度為8，即4個(gè)匹配點(diǎn)對(duì)就可以計(jì)算出h1～h8的數(shù)值，h9取1即可。將單應(yīng)矩陣以向量形式h轉(zhuǎn)換為齊次線性最小二乘問(wèn)題Ah=0后，應(yīng)用最小二乘法求解。

RANSAC算法的核心思想是每次抽取s個(gè)匹配對(duì)，抽多少次才能保證有一次不是外點(diǎn)的概率為q。基于此，對(duì)數(shù)變換后可得如下關(guān)系式：

[N=log1-qlog1-1-εs] （2）

式中，N表示迭代抽取的次數(shù)，s表示每次抽取的匹配點(diǎn)對(duì)個(gè)數(shù)，ε表示匹配點(diǎn)對(duì)總量與外點(diǎn)對(duì)的比例。本文中s取4，因?yàn)橹辽傩枰?個(gè)匹配點(diǎn)對(duì)才能計(jì)算出單應(yīng)矩陣。q需要事先確定，q越大，則抽取的匹配點(diǎn)對(duì)為內(nèi)點(diǎn)的可能性就越大。ε由單應(yīng)矩陣的重映射誤差得到，重映射誤差d的計(jì)算式如下：

[dp'，Hp=||p'-Hp||]

[=u'-h1u+h2v+h3h7u+h8v+h92+v'-h4u+h5v+h6h7u+h8v+h92]

（3）

每次選取4個(gè)匹配對(duì)后，計(jì)算單應(yīng)矩陣H，再利用H對(duì)所有的匹配對(duì)進(jìn)行重映射誤差計(jì)算。[e=i=0nd2i]，設(shè)置閾值η，若e小于該值，則認(rèn)為該對(duì)匹配點(diǎn)是內(nèi)點(diǎn)。得到ε后，帶入式（2），更新最大迭代次數(shù)N，直到滿足迭代次數(shù)或已得到最大的內(nèi)點(diǎn)數(shù)量時(shí)，則退出迭代。

（2） 魯棒校驗(yàn)

通過(guò)貝葉斯公式，計(jì)算后驗(yàn)概率（一對(duì)匹配點(diǎn)是內(nèi)點(diǎn)的情況下圖像有重疊區(qū)域的概率） 。設(shè)置閾值pmin，若后驗(yàn)概率大于pmin，則認(rèn)為輸入的兩幅圖像是有重疊區(qū)域的[12]。基于此，本文使用如下的置信度計(jì)算公式對(duì)估計(jì)重疊區(qū)域進(jìn)行評(píng)估：

[c=ni8.0+0.3nf] （4）

式中，ni表示內(nèi)點(diǎn)匹配對(duì)的數(shù)量，nf表示總匹配對(duì)數(shù)量。設(shè)置閾值ηc，若置信度大于ηc，則認(rèn)為重疊區(qū)域估計(jì)成功。

3? 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法的有效性和準(zhǔn)確率，對(duì)20對(duì)圖片進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)圖片組如圖4所示，圖像的尺寸均為1000*1000。實(shí)驗(yàn)程序的運(yùn)行環(huán)境為i5-6300HQ（四核） 、Windows10和Visual Studio 2015，程序?qū)崿F(xiàn)方式為C++語(yǔ)言和Opencv3.3.0。

3.1 估計(jì)方法有效性驗(yàn)證

（1） 估計(jì)成功圖像對(duì)實(shí)驗(yàn)結(jié)果與分析

限于篇幅，表1比較了估計(jì)成功的5對(duì)不同估計(jì)重疊區(qū)域面積圖像對(duì)在SIFT算法、SURF算法和本文算法特征點(diǎn)和匹配對(duì)個(gè)數(shù)的結(jié)果，表2為表1的計(jì)算時(shí)間比較。實(shí)驗(yàn)結(jié)果表明，在估計(jì)成功的情況下，隨著重疊區(qū)域面積的占比降低，本文算法大大減少了特征點(diǎn)的提取數(shù)量以及計(jì)算時(shí)間，提升了匹配對(duì)占比，且沒(méi)有降低圖像配準(zhǔn)的準(zhǔn)確性。

以估計(jì)成功的實(shí)驗(yàn)圖7、2和14為例，本方法位置估計(jì)的匹配和拼接結(jié)果如下圖5所示，半透明區(qū)域?yàn)楣烙?jì)的非重疊區(qū)域。

（2） 估計(jì)失敗圖像對(duì)實(shí)驗(yàn)結(jié)果與分析

表3比較了本方法重疊區(qū)域位置估計(jì)失敗的3對(duì)圖像在整幅圖和本文算法計(jì)算時(shí)的特征點(diǎn)和匹配對(duì)數(shù)量。對(duì)整幅圖的計(jì)算也采用了并行計(jì)算方式。可以看出，第一次得到的匹配對(duì)數(shù)量都很低，原因是完全沒(méi)有相似區(qū)域或者相似區(qū)域面積較小。表4是表3的計(jì)算時(shí)間對(duì)比，可以看出，因?yàn)槎嗔艘淮螌?duì)部分無(wú)效特征點(diǎn)的匹配，所以總的計(jì)算時(shí)間反而有所增加。

分析估計(jì)失敗的原因，序號(hào)4圖像對(duì)的畫面內(nèi)容是天空和草地，邊緣特征信息較少，序號(hào)12圖像對(duì)的畫面內(nèi)容是一座高樓，存在較明顯的旋轉(zhuǎn)關(guān)系，序號(hào)17圖像對(duì)的畫面內(nèi)容是樹(shù)林，邊緣特征信息太多且沒(méi)有區(qū)域性，即本方法在不存在旋轉(zhuǎn)和透視關(guān)系、邊緣特征信息較為豐富且具有左右區(qū)域差別的情況下具有較好的估計(jì)準(zhǔn)確性。

圖6對(duì)比了20對(duì)圖像分別在使用窮舉匹配法、Lowe的方法和本方法時(shí)的圖像拼接計(jì)算時(shí)間，可以看出，在估計(jì)重疊區(qū)域失敗的情況下，雖然會(huì)增加額外的計(jì)算時(shí)間，但從整體來(lái)看，本方法還是能減少大批量圖像拼接的計(jì)算時(shí)間。

3.2 估計(jì)方法比較

作為同樣采用圖像處理方式對(duì)重疊區(qū)域進(jìn)行估計(jì)，以此提高圖像配準(zhǔn)效率的方法，且無(wú)其他相同性質(zhì)的估計(jì)算法情況下，本文估計(jì)方法將只與文獻(xiàn)[7]的估計(jì)方法進(jìn)行對(duì)比。據(jù)文獻(xiàn)[7]所述，將圖像預(yù)處理中的中值濾波核尺寸和自適應(yīng)濾波核尺寸設(shè)置為21，其他未提及參數(shù)則與本方法的設(shè)置相同。實(shí)驗(yàn)樣本用上述20對(duì)圖像，對(duì)比估計(jì)都成功、文獻(xiàn)[7]方法失敗但本方法成功和文獻(xiàn)[7]方法成功但本方法失敗三種情況的結(jié)果，以此驗(yàn)證不同估計(jì)方法的差異性、準(zhǔn)確性和有效性。估計(jì)成功的標(biāo)準(zhǔn)是，估計(jì)的重疊區(qū)域面積占比和實(shí)際的偏差不能太大，且拼接效果較好，實(shí)際占比由人工根據(jù)圖像對(duì)標(biāo)定。

圖7對(duì)比了兩種估計(jì)方法的誤差，由實(shí)際占比減去估計(jì)占比得到，0處橫線表示實(shí)際占比。可以看出，本文方法的準(zhǔn)確性較好。

圖8對(duì)比了兩種方法的匹配對(duì)和特征點(diǎn)數(shù)量比值總和，能直觀體現(xiàn)出兩種估計(jì)法的有效性，且本文估計(jì)方法較好。

表5比較了文獻(xiàn)[7]和本文的估計(jì)方法計(jì)算時(shí)間。因?yàn)楸痉椒ㄏ噍^于文獻(xiàn)[7]方法更適合并行計(jì)算，所以本方法計(jì)算時(shí)間較少。

4 結(jié)束語(yǔ)

本文針對(duì)圖像拼接中特征點(diǎn)提取和匹配耗時(shí)長(zhǎng)的問(wèn)題，提出了重疊區(qū)域位置估計(jì)算法，該算法是基于含有邊緣特征信息的二值預(yù)處理圖像，在水平和垂直方向滑動(dòng)計(jì)算方差，先估計(jì)圖像對(duì)重疊區(qū)域的位置，然后只對(duì)估計(jì)區(qū)域進(jìn)行特征點(diǎn)提取和匹配，從而提高圖像配準(zhǔn)的效率。另外，利用條件限制和魯棒校驗(yàn)配合估計(jì)算法，從而提高整體圖像拼接的有效性。

實(shí)驗(yàn)結(jié)果表明，在大批量圖像拼接時(shí)，本文提出的算法能有效提高圖像配準(zhǔn)的效率，但目前該算法對(duì)左右區(qū)域邊緣特征差異不明顯、存在透視關(guān)系和垂直方向偏移大的圖像對(duì)表現(xiàn)不良，故下一步將進(jìn)一步優(yōu)化提出的算法，以應(yīng)對(duì)多種拍攝情況的圖像對(duì)。

參考文獻(xiàn)：

[1] Liu Q X，Su X Y，Zhang L，et al.Panoramic video stitching of dual cameras based on spatio-temporal seam optimization[J].Multimedia Tools and Applications，2020，79（5）：3107-3124.

[2] 任靖娟，王玖煒，曹莉.VR全景視頻制作軟件目標(biāo)可視化三維虛擬仿真[J].計(jì)算機(jī)仿真，2020，37（9）：299-302，311.

[3] Ro S H，Kim S H.An image stitching algorithm for the mineralogical analysis[J].Minerals Engineering，2021，169：106968.

[4] Harris C G ， Stephens M J . A combined corner and edge detector[C]// Alvey vision conference. 1988.

[5] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[6] Bay H ， Tuytelaars T ， Gool L V . SURF： Speeded up robust features[J]. Proceedings of the 9th European conference on Computer Vision - Volume Part I， 2006.

[7] Qu Z，Li J，Bao K H，et al.An unordered image stitching method based on binary tree and estimated overlapping area[J].IEEE Transactions on Image Processing，2020，29：6734-6744.

[8] Qin Y ， Li J ， Jiang P ， et al. Image stitching by feature positioning and seam elimination[J]. Multimedia Tools and Applications， 2021（3）：1-13.

[9] 趙春江.圖像局部特征檢測(cè)和描述基于OpenCV源碼分析的算法與實(shí)現(xiàn)[M].北京：人民郵電出版社，2018：78 -88.

[10] Vincent E ， Laganire R . Matching feature points in stereo pairs： A comparative study of some matching strategies[J]. Machine Graphics and Vision， 2001， 10（3）：237-259.

[11] Choi J ， Medioni G . StaRSaC： Stable random sample consensus for parameter estimation. CVPR[C]// DBLP. DBLP， 2009.

[12] 趙毅力，夏炎.無(wú)序圖像自動(dòng)匹配與識(shí)別[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（12）：262-264，310.

【通聯(lián)編輯：光文玲】