許光宇，丁 健

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

1 引言

圖像拼接技術(shù)是計(jì)算機(jī)視覺、圖像處理領(lǐng)域的一個(gè)重要研究分支。其原理是在同一場(chǎng)景下，以不同視角獲得兩幅或者多幅存在重疊區(qū)域的圖像，對(duì)其進(jìn)行配準(zhǔn)、投影和融合，進(jìn)而得到一幅視野更大、分辨率更高的圖像。

隨著智能手機(jī)、數(shù)碼相機(jī)等手持式圖像采集設(shè)備的普及，圖像獲取和后期圖像處理的需求與日俱增，相應(yīng)的各種拼接軟件和應(yīng)用也層出不窮，例如AutoStitch[1]、微軟的圖像合成編輯器ICE (Image Composite Editor)和Photoshop的Photomerge等。這些軟件要求輸入圖像必須滿足2個(gè)基本條件才能取得準(zhǔn)確的拼接結(jié)果，即：

(1)要求圖像的重疊區(qū)域要近似在一個(gè)平面上；

(2)多次拍攝時(shí)相機(jī)的光心位置需要盡量重合。

如果不滿足條件(1)，即圖像中存在多個(gè)子平面，則一個(gè)全局單應(yīng)性矩陣就無法實(shí)現(xiàn)多個(gè)子平面的精確配準(zhǔn)，拼接后的圖像會(huì)出現(xiàn)明顯的重影和錯(cuò)位。如果不滿足條件(2)，則會(huì)因?yàn)橄鄼C(jī)光心發(fā)生偏移導(dǎo)致拍攝結(jié)果產(chǎn)生視差，影響拼接結(jié)果。針對(duì)上述問題可以從硬件和算法2個(gè)方面改善?；谟布纳剖菑膯栴}的根源出發(fā)，使相機(jī)光心重合，一般方法是采用廣角鏡頭或者普通鏡頭加球面透鏡以獲得更大的視角，從根本上解決視差問題，但是成本較高。從算法角度改善的方案受用相對(duì)更廣泛，普通相機(jī)多次拍攝就可以得到類似廣角的效果，近年來國(guó)內(nèi)外研究人員做了大量的相關(guān)工作。

Gao等[2]提出了基于雙平面假設(shè)的圖像拼接算法，把實(shí)際場(chǎng)景近似劃分為背景和前景2個(gè)平面，分別計(jì)算2個(gè)單應(yīng)性矩陣進(jìn)行投影變換，得到了不錯(cuò)的拼接效果。但是，該算法需要滿足的分割條件較為嚴(yán)格，不適用于大多數(shù)實(shí)際場(chǎng)景。Zaragoza等[3]提出了盡可能投影配準(zhǔn)方法APAP(As-Projective- As-Possible)，率先使用網(wǎng)格優(yōu)化模型，把圖像劃分成密集網(wǎng)格，利用移動(dòng)直線線性變換法moving DLT(Direct Linear Transform)求解每個(gè)網(wǎng)格單元的單應(yīng)性矩陣，使用局部單應(yīng)性對(duì)齊圖像。Zhang等[4]結(jié)合縫合線搜索算法，運(yùn)用局部區(qū)域?qū)R模型評(píng)估拼接質(zhì)量，以獲得最佳的配準(zhǔn)效果，提高了大視差場(chǎng)景下的拼接性能。Chang等[5]提出了保持形狀的半投影變換方法SPHP(Shape Preserving Half Projective)，從重疊區(qū)域的投影變換逐漸過渡到非重疊區(qū)域的相似變換，可以有效解決非重疊區(qū)域的投影失真問題。Lin等[6]提出了自適應(yīng)的盡可能自然投影方法AANAP(Adaptive As Natural As Possible)，自適應(yīng)確定圖像間最小旋轉(zhuǎn)角度，結(jié)合投影變換、相似變換和仿射變換處理圖像拼接過程中的投影失真，大幅度提升了視覺觀感。Chen等[7]在 APAP預(yù)配準(zhǔn)后，添加局部相似項(xiàng)和全局相似項(xiàng)作為網(wǎng)格約束，在處理多圖拼接時(shí)可以有效地保護(hù)圖像內(nèi)的幾何結(jié)構(gòu)。

在面對(duì)大視差問題時(shí)，無論是將圖像分成背景和前景雙平面，還是把圖像分成數(shù)個(gè)大小相同的單元，處理的關(guān)鍵都是把圖像按照某種方式進(jìn)行分割，分別進(jìn)行單應(yīng)性計(jì)算。基于此分割思想，本文提出了一種基于特征聚類的局部配準(zhǔn)算法，用以拼接大視差圖像。該算法利用特征點(diǎn)集構(gòu)建泰森多邊形，之后運(yùn)用改進(jìn)的AGNES(AGlomerative NESting)算法進(jìn)行層次聚類，結(jié)合拼接誤差分析聚類結(jié)果，確定圖像中子平面數(shù)目及位置，最后計(jì)算局部單應(yīng)性矩陣進(jìn)行投影變換，實(shí)現(xiàn)圖像的高精度拼接。

2 子平面確定及配準(zhǔn)

從日常拍攝得到的圖像中提取到的特征點(diǎn)會(huì)分布在圖像的各個(gè)區(qū)域，在有些區(qū)域特征點(diǎn)分布較為密集，并且分布較為密集的區(qū)域之間經(jīng)常存在明顯的邊界。產(chǎn)生這種現(xiàn)象的原因是圖像存在多個(gè)可以按照特征點(diǎn)分布劃分的子平面。

圖1展示了實(shí)際場(chǎng)景圖像中可能會(huì)出現(xiàn)的子平面分布情況?？梢钥吹?，在待拼接圖像重疊區(qū)域，對(duì)應(yīng)數(shù)字標(biāo)注的橢圓形內(nèi)部特征點(diǎn)分布較為集中，并且正好對(duì)應(yīng)圖像中的景物實(shí)體。例如圖1a的樓房橫梁、正門、樹木、馬路以及人行道等，圖1b的扶手、近處樓房、汽車、遠(yuǎn)處樓房以及地面等，這些景物實(shí)體正是本文定義的圖像子平面。

Figure 1 Sub plane distribution圖1 子平面分布情況

可以推斷，確定圖像子平面的關(guān)鍵就是讓分布密集的特征點(diǎn)聚類成簇，得到多個(gè)可以代表圖像實(shí)體景物的子區(qū)域。而在對(duì)應(yīng)子平面上進(jìn)行局部投影可以有效提高配準(zhǔn)精度，改善拼接效果。

本文以特征點(diǎn)分布為依據(jù)在目標(biāo)圖像重疊區(qū)域構(gòu)造泰森多邊形，然后使用改進(jìn)的AGNES層次聚類算法對(duì)特征點(diǎn)聚類,合并對(duì)應(yīng)組內(nèi)泰森多邊形，從而確定子平面在圖像中的位置。

2.1 泰森多邊形構(gòu)建

泰森多邊形也稱為Voronoi圖或者Dirichlet圖，是一種解決空間分析問題的常用工具[8 - 10]，多運(yùn)用于分析地理實(shí)體在區(qū)域中產(chǎn)生的影響。

如圖2所示，泰森多邊形構(gòu)建的主要步驟如下所示：

Figure 2 Voronoi diagram construction 圖2 Voronoi 圖構(gòu)建

(1)用離散點(diǎn)構(gòu)建Delaunay三角網(wǎng)[11]，記錄每個(gè)三角形及其對(duì)應(yīng)的3個(gè)頂點(diǎn)并進(jìn)行編號(hào)。

(2)計(jì)算每個(gè)三角形的外接圓圓心并記錄。

(3)遍歷三角形鏈表，尋找與當(dāng)前三角形3邊共邊的3個(gè)相鄰三角形。如果找到，則連接相應(yīng)的外接圓圓心，并存入Voronoi邊鏈表中；如果找不到，則求出最外邊的中垂線存入Voronoi邊鏈表。

(4)遍歷結(jié)束，根據(jù)找到的Voronoi邊畫出Voronoi圖。

泰森多邊形具有如下性質(zhì)：(1)每個(gè)多邊形內(nèi)只有一個(gè)離散點(diǎn)；(2)每個(gè)多邊形區(qū)域內(nèi)的點(diǎn)到相應(yīng)離散點(diǎn)的距離最近；(3)多邊形邊界上的點(diǎn)到相鄰2個(gè)多邊形內(nèi)離散點(diǎn)的距離相等。

根據(jù)泰森多邊形的性質(zhì)可知：在圖像重疊區(qū)域上利用特征點(diǎn)構(gòu)建泰森多邊形，則每個(gè)特征點(diǎn)都可以代表該特征點(diǎn)所在泰森多邊形的區(qū)域特征。

本文利用KNN(K-Nearest Neighbor)算法[12]和RANSAC(RANdom SAmple Consensus)算法[13]確定特征點(diǎn)匹配對(duì)，之后在目標(biāo)圖像上定義重疊區(qū)域。以匹配特征點(diǎn)的橫、縱坐標(biāo)的最小值(xmin,ymin)和最大值(xmax,ymax)初步確定一個(gè)矩形區(qū)域的左右界和上下界，為了使處在矩形區(qū)域邊緣上的特征點(diǎn)也能正常構(gòu)建泰森多邊形，以此矩形區(qū)域向外擴(kuò)展10個(gè)像素((xmin-10,ymin-10)和(xmax+10,ymax+10))確定新的邊界，此矩形區(qū)域?yàn)楸疚亩x的重疊區(qū)域。在重疊區(qū)域上利用匹配特征點(diǎn)可構(gòu)建泰森多邊形。

2.2 改進(jìn)的AGNES層次聚類

泰森多邊形的構(gòu)建把重疊區(qū)域按照特征點(diǎn)數(shù)劃分成相應(yīng)數(shù)量的圖像塊，如果直接以每塊區(qū)域分別計(jì)算單應(yīng)性矩陣進(jìn)行投影，計(jì)算量十分大，不符合實(shí)際要求。并且因?yàn)閳D像子平面的存在，如果在特征點(diǎn)密集區(qū)域多次投影，可能會(huì)導(dǎo)致子平面內(nèi)圖像喪失整體性而發(fā)生扭曲失真。因此，本文對(duì)特征點(diǎn)進(jìn)行AGNES層次聚類，聚類的目的是把分布密集的特征點(diǎn)劃分到一個(gè)子平面上進(jìn)行投影，從而提高局部區(qū)域的配準(zhǔn)精度。

AGNES層次聚類算法最初把每個(gè)數(shù)據(jù)對(duì)象看作單獨(dú)的一個(gè)類，每一步合并距離最近的類，自下而上地構(gòu)建一棵嵌套層次聚類樹。相比于K-means聚類算法[14]，層次聚類的優(yōu)點(diǎn)[15-18]在于無需預(yù)先確定聚類數(shù)目，并且只需一次聚類就可以直觀地展現(xiàn)類的層次關(guān)系，有利于后續(xù)確定最優(yōu)分組數(shù)目。

任意類之間的距離度量方法有4種：最小距離法、最大距離法、平均值距離法和平均距離法。本文主要討論采用平均距離法進(jìn)行層次聚類，距離計(jì)算方法統(tǒng)一采用歐氏距離，聚類過程如下所示：

(1)把每個(gè)對(duì)象劃分為單獨(dú)的一類，計(jì)算每個(gè)類之間的距離，得到初始距離矩陣；

(2)將距離最近的2個(gè)類合并；

(3)重新計(jì)算每個(gè)類之間的距離，計(jì)算方式為用類內(nèi)所有數(shù)據(jù)點(diǎn)間的距離的平均值代表類間距離；

(4)重復(fù)步驟(2)和步驟(3)，合并所有類，直到聚類數(shù)目達(dá)到目標(biāo)數(shù)為止。

傳統(tǒng)AGNES層次聚類算法在每次合并完一個(gè)類后，必須重新計(jì)算合并后類之間的距離矩陣。在面對(duì)大量數(shù)據(jù)時(shí)，這種計(jì)算方式會(huì)產(chǎn)生龐大的計(jì)算量。假設(shè)對(duì)N個(gè)對(duì)象進(jìn)行聚類，計(jì)算得到的距離矩陣大小為N2，合并完一個(gè)類之后，剩余類數(shù)為N-1，重新計(jì)算類間距離，得到的距離矩陣大小為(N-1)2，不斷重復(fù)以上步驟，直到達(dá)到目標(biāo)聚類數(shù)目為止。完成聚類的時(shí)間復(fù)雜度為O(N2)，并且每一次類合并后需要計(jì)算的距離矩陣都會(huì)占用N2階存儲(chǔ)空間，這無疑會(huì)降低拼接算法的魯棒性。若能使初始對(duì)象合并后不需再次計(jì)算距離矩陣，而是充分利用初始距離矩陣的數(shù)據(jù)進(jìn)行類間合并，則可以大幅度縮短運(yùn)算時(shí)間。基于以上思想，本文對(duì)AGNES層次聚類算法做出如下改進(jìn)：

(1)計(jì)算出數(shù)據(jù)集合中任意對(duì)象之間的距離d(i,j)，并存儲(chǔ)在一個(gè)一維數(shù)組d中。

(2)對(duì)一維數(shù)組d按照距離值從小到大進(jìn)行排序。

(3)對(duì)d中當(dāng)前元素進(jìn)行判定，首先判斷其對(duì)應(yīng)的2個(gè)對(duì)象是否在同一個(gè)類中，如果不是，就將這2個(gè)對(duì)象合并為一個(gè)類；如果其中一個(gè)對(duì)象已歸屬于某一類，則將另一個(gè)也合并到該類中；如果它們都有各自的類，則合并它們所在類為一個(gè)類。

(4)取d中下一個(gè)元素，重復(fù)步驟(3)，直至處理完數(shù)組d中所有的數(shù)據(jù)。

本文以特征點(diǎn)為數(shù)據(jù)對(duì)象，按照上述聚類算法合并特征點(diǎn)，自下而上建立特征點(diǎn)的層次聚類樹。圖3給出了部分特征點(diǎn)的分組情況。聚類完成后，結(jié)合各種分組方式下的拼接誤差，確定分組數(shù)。具體分組策略在3.2節(jié)給出。

Figure 3 Hierarchical clustering tree圖3 層次聚類樹

2.3 子平面配準(zhǔn)

聚類算法使圖像特征點(diǎn)被劃分到多個(gè)子平面中，這些特征點(diǎn)可以用于計(jì)算每個(gè)子平面對(duì)應(yīng)的單應(yīng)性矩陣H。假設(shè)圖像子平面內(nèi)的匹配特征點(diǎn)對(duì)(xi,yi)和(x′i,y′i)間滿足3×3的矩陣變換關(guān)系(x′i,y′i)=H(xi,yi)，如式(1)所示：

(1)

對(duì)式(1)展開得到2個(gè)線性方程,如式(2)所示：

(2)

(3)

因而得到式(4)：

ah=0

(4)

假設(shè)子平面特征點(diǎn)對(duì)數(shù)量為n，通過最小二乘法求解h，如式(5)所示：

s.t. ‖h‖=1

(5)

式(5)是一個(gè)超定方程組的近似解，在約束‖h‖=1下最小化范數(shù)‖Ah‖，其中的組合矩陣A滿足式(6)：

(6)

為了避免圖像在重疊區(qū)域和非重疊區(qū)域交界處出現(xiàn)錯(cuò)位和裂縫，本文把重疊區(qū)域的子平面求得的單應(yīng)性矩陣H就近分配到相鄰的非重疊區(qū)域，使圖像整體過渡更加自然。

3 拼接算法與實(shí)現(xiàn)

3.1 拼接流程

圖像整體拼接流程如圖4所示?？紤]到對(duì)配準(zhǔn)精度和特征點(diǎn)數(shù)量的要求，本文采用SIFT(Scale-Invariant Feature Transform)算法[19]提取圖像特征點(diǎn)。與SURF(Speeded Up Robust Features)[20]等特征提取算法相比，SIFT具有縮放、旋轉(zhuǎn)、平移不變性以及特征點(diǎn)豐富等優(yōu)點(diǎn)。從目標(biāo)圖像上提取特征點(diǎn)之后，利用KNN算法粗匹配特征點(diǎn)，再使用RANSAC算法精確篩選出內(nèi)點(diǎn)一致集。之后規(guī)劃出重疊區(qū)域，利用匹配特征點(diǎn)構(gòu)建泰森多邊形。再通過改進(jìn)的AGNES層次聚類對(duì)特征點(diǎn)進(jìn)行分組，合并對(duì)應(yīng)組內(nèi)泰森多邊形，得到圖像重疊區(qū)域子平面。計(jì)算每個(gè)重疊區(qū)域子平面的局部單應(yīng)性矩陣，并拓展到非重疊區(qū)域，得到最終拼接結(jié)果。

Figure 4 Stitching process圖4 拼接流程

3.2 分組策略

本文采用均方根誤差RMSE作為衡量子平面拼接質(zhì)量的標(biāo)準(zhǔn)，其定義如式(7)所示：

(7)

其中,特征點(diǎn)匹配對(duì)(xi,yi)和(x′i,y′i)間的投影關(guān)系用f表示。

不同的數(shù)據(jù)集上[2,3,21]分組數(shù)K和RMSE的關(guān)系如圖5所示。理論上RMSE具有收斂性，即隨著分組數(shù)K的增大，拼接效果越好。然而實(shí)際上隨著分組數(shù)增大，計(jì)算量會(huì)大大增加，并且在平面連續(xù)區(qū)域分塊過多可能會(huì)在細(xì)節(jié)區(qū)域出現(xiàn)局部的扭曲和斷裂，影響視覺效果，這一點(diǎn)是無法從RMSE值上得到體現(xiàn)的。經(jīng)過多次實(shí)驗(yàn)，分組數(shù)K的取值在7～13時(shí)RMSE趨于收斂，為本文算法的合適取值。

Figure 5 Curve of RMSE-K value 圖5 RMSE-K值曲線

3.3 圖像融合

為了更真實(shí)地展示重疊區(qū)域的配準(zhǔn)效果，本文采用簡(jiǎn)單加權(quán)融合法融合圖像，假設(shè)I1(x,y)和I2(x,y)分別表示參考圖像和目標(biāo)圖像，則融合后的圖像I(x,y)表示為：

(8)

4 實(shí)驗(yàn)結(jié)果及分析

本節(jié)在數(shù)據(jù)集railtracks和temple上進(jìn)行拼接效果對(duì)比實(shí)驗(yàn)，以檢驗(yàn)本文所提算法的有效性，對(duì)比算法包括AutoStitch和Photomerge這2款商業(yè)軟件，以及APAP算法和傳統(tǒng)Baseline算法。

實(shí)驗(yàn)可調(diào)參數(shù)包括SIFT算法中的RANSAC 閾值β、迭代次數(shù)M,APAP算法的歸一化參數(shù)γ和帶寬ξ。在所有數(shù)據(jù)集上統(tǒng)一設(shè)定為：β=0.15,M=500,ξ=0.01,σ=12。

4.1 拼接效果對(duì)比

圖6和圖7展示了各種算法對(duì)railtracks和temple數(shù)據(jù)集的拼接效果圖，圖中右側(cè)2列為左側(cè)拼接圖放大的細(xì)節(jié)區(qū)域，左側(cè)的矩形框內(nèi)為正確配準(zhǔn)區(qū)域，橢圓形框內(nèi)為錯(cuò)誤配準(zhǔn)區(qū)域?？梢钥吹?，對(duì)于大視差圖像的拼接，2款商業(yè)軟件在細(xì)節(jié)紋理處均出現(xiàn)了不同程度的錯(cuò)誤配準(zhǔn)，如圖6a和圖6b的鐵軌處和圖7a和圖7b的地磚處。Baseline作為常見的圖像拼接方法，采用一個(gè)全局單應(yīng)性矩陣對(duì)目標(biāo)圖像進(jìn)行投影變換，無法做到精確配準(zhǔn)。APAP算法作為目前處理視差圖像最有效的算法之一，在2個(gè)數(shù)據(jù)集上均表現(xiàn)良好，但是在某些細(xì)節(jié)區(qū)域也出現(xiàn)了誤配準(zhǔn)和輕微的扭曲現(xiàn)象，如圖7d圓形框內(nèi)所示；而本文算法在2種數(shù)據(jù)集上都實(shí)現(xiàn)了高精度的圖像拼接，并未出現(xiàn)誤配準(zhǔn)的情況。

Figure 6 Comparison of the stitching effect of different algorithms on railtracks dataset圖6 railtracks數(shù)據(jù)集上不同算法拼接效果對(duì)比

Figure 7 Comparison of the stitching effect of different algorithms on temple dataset圖7 temple數(shù)據(jù)集上不同算法拼接效果對(duì)比

無論是AutoStitch和Photomerge這2款商業(yè)軟件還是傳統(tǒng)Baseline算法，其思想都是基于全局單應(yīng)性矩陣進(jìn)行投影變換的，沒有考慮到多子平面和相機(jī)光心可能不重合的情況，因此在處理視差圖像時(shí)就有可能產(chǎn)生明顯的偽影和錯(cuò)位。APAP算法采用的網(wǎng)格優(yōu)化模型中，圖像會(huì)隨著網(wǎng)格變換發(fā)生變換，由于網(wǎng)格變換的不連續(xù)性，當(dāng)物體跨越多個(gè)網(wǎng)格時(shí)，其幾何結(jié)構(gòu)就可能會(huì)遭到破壞。而本文算法是基于子平面進(jìn)行局部投影，既解決了全局投影精度不高的問題，還能夠使圖像中大部分實(shí)體完整地劃分到同一個(gè)子平面內(nèi)，保證了在實(shí)體幾何結(jié)構(gòu)上投影的連續(xù)性。

本節(jié)還采用均方根誤差RMSE定量分析了各種算法的拼接效果。表1統(tǒng)計(jì)了Baseline算法、APAP算法和本文算法在不同數(shù)據(jù)集上的拼接誤差RMSE值，所有的測(cè)試結(jié)果均是重復(fù)20次實(shí)驗(yàn)得到的平均值。由于AutoStitch和Photomerge無法計(jì)算RMSE值，所以暫不統(tǒng)計(jì)。從結(jié)果來看，本文算法和APAP算法的RMSE值接近，配準(zhǔn)精度都高于常用的Baseline算法。

Table 1 RMSE on different datasets

4.2 算法時(shí)間復(fù)雜度分析

不同算法在各種數(shù)據(jù)集上的耗時(shí)比較結(jié)果如表2所示?？梢钥吹?Baseline算法犧牲拼接精度換取了較快的拼接速度，不適用于大視差圖像拼接。在大部分?jǐn)?shù)據(jù)集上，本文算法的耗時(shí)要低于拼接效果相近的APAP算法，但是面對(duì)存在大量特征點(diǎn)的數(shù)據(jù)集如railtracks時(shí)耗時(shí)增加明顯，主要原因是構(gòu)建泰森多邊形這一步驟的耗時(shí)會(huì)隨著特征點(diǎn)數(shù)量的增多而顯著增加，這也是本文算法的不足之處。在以后的工作中可以加入對(duì)Voronoi圖生成算法的改進(jìn),以提升整體效率。

Table 2 Algorithm runtime comparison on different datasets

5 結(jié)束語

本文提出一種基于特征聚類的圖像拼接算法，以解決大視差圖像的誤配準(zhǔn)問題。首先在重疊區(qū)域以特征點(diǎn)分布為依據(jù)構(gòu)建泰森多邊形，用特征點(diǎn)代表該泰森多邊形內(nèi)區(qū)域特征；然后利用改進(jìn)的AGNES層次聚類算法對(duì)特征點(diǎn)聚類，結(jié)合拼接誤差決定分組策略，合并組內(nèi)對(duì)應(yīng)泰森多邊形構(gòu)成區(qū)域子平面；最后分別計(jì)算每個(gè)子平面的單應(yīng)性矩陣進(jìn)行局部投影，同時(shí)按照就近原則分配非重疊區(qū)域的單應(yīng)性矩陣，實(shí)現(xiàn)全圖配準(zhǔn)，得到高精度的拼接圖像。實(shí)驗(yàn)結(jié)果表明，本文所提算法可視化拼接效果優(yōu)于APAP算法，能夠?qū)崿F(xiàn)大視差圖像的高精度配準(zhǔn)，具有一定的實(shí)用價(jià)值和理論意義。