基于特征聚類的大視差圖像拼接算法 *

許光宇，丁 健

(安徽理工大學計算機科學與工程學院，安徽 淮南 232001)

1 引言

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

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

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

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

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

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

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

2 子平面確定及配準

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

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

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

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

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

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

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

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

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

(1)用離散點構(gòu)建Delaunay三角網(wǎng)[11]，記錄每個三角形及其對應的3個頂點并進行編號。

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

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

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

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

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

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

2.2 改進的AGNES層次聚類

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

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

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

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

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

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

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

傳統(tǒng)AGNES層次聚類算法在每次合并完一個類后，必須重新計算合并后類之間的距離矩陣。在面對大量數(shù)據(jù)時，這種計算方式會產(chǎn)生龐大的計算量。假設對N個對象進行聚類，計算得到的距離矩陣大小為N2，合并完一個類之后，剩余類數(shù)為N-1，重新計算類間距離，得到的距離矩陣大小為(N-1)2，不斷重復以上步驟，直到達到目標聚類數(shù)目為止。完成聚類的時間復雜度為O(N2)，并且每一次類合并后需要計算的距離矩陣都會占用N2階存儲空間，這無疑會降低拼接算法的魯棒性。若能使初始對象合并后不需再次計算距離矩陣，而是充分利用初始距離矩陣的數(shù)據(jù)進行類間合并，則可以大幅度縮短運算時間?；谝陨纤枷耄疚膶GNES層次聚類算法做出如下改進：

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

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

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

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

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

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

2.3 子平面配準

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

(1)

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

(2)

(3)

因而得到式(4)：

ah=0

(4)

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

s.t. ‖h‖=1

(5)

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

(6)

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

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

3.1 拼接流程

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

Figure 4 Stitching process圖4 拼接流程

3.2 分組策略

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

(7)

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

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

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

3.3 圖像融合

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

(8)

4 實驗結(jié)果及分析

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

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

4.1 拼接效果對比

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

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

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

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

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

Table 1 RMSE on different datasets

4.2 算法時間復雜度分析

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

Table 2 Algorithm runtime comparison on different datasets

5 結(jié)束語

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