基于網格運動統計算法和最佳縫合線的密集重復結構圖像快速拼接方法

牟 琦，唐 洋，李占利，李洪安

(1.西安科技大學 計算機科學與技術學院，西安 710054； 2.西安科技大學 機械工程學院，西安 710054)

0 引言

圖像拼接是指將相鄰的且具有一定重疊區域的兩幅或多幅圖像合成為一幅大視場圖像的技術。近年來，圖像拼接技術逐漸成為計算機視覺、地質勘探、信息隱藏以及虛擬現實等領域的研究熱點[1-4]。

在合成得到的全景圖中，如果同一物體出現部分重疊而導致的模糊、重影現象，稱為鬼影。圖像拼接通常包含圖像預處理、特征匹配和圖像融合3個步驟。匹配點的數量和質量會直接影響變換矩陣的精度，當正確匹配點數量過少時，會導致圖像配準階段出現配準鬼影，圖像融合階段出現合成鬼影[5-6]。

目前常用的圖像拼接方法是采用經典的尺度不變特征變換(Scale-Invariant Feature Transform, SIFT)算法[7]、加速穩健特征(Speeded Up Robust Features, SURF)算法[8]及其改進算法[9]提取特征點后，通過隨機抽象一致算法(RANdom SAmple Consensus, RANSAC)算法[10]完成特征匹配，最后采用漸入漸出法進行圖像融合[11-13]。SIFT算法對于圖像旋轉、縮放以及尺度變換具有很強的魯棒性，可以得到理想的拼接效果，但是在特征提取和特征向量描述上計算量大，需要消耗大量時間。SURF算法在保持SIFT算法優良性能的同時，有效地提高了計算速度。為了快速得到更豐富的特征點，Patel等[14]采用SURF算法進行特征提取，通過積分圖像加快計算，但當帶拼接圖片之間存在較大視差時，特征魯棒性較低。 Rublee等[15]提出了ORB(Oriented FAST (Features from Accelerated Segment Test) and Rotated BRIEF (Binary Robust Independent Elementary Features))算法，計算量更小，可以快速地提取大量特征點，Wang等[16]采用ORB算法提取圖像特征，對于紋理豐富的圖像，拼接效果好且速度快;但是對于密集重復結構的圖像，ORB提取的特征點魯棒性較低，需要進一步的過濾和精匹配。另外，一部分研究者在圖像預處理階段首先確定重疊區域，以減少SIFT算法對無效區域進行匹配的耗時，提高算法運行速度[11,13]。文獻[11]利用圖像能量的歸一化互相關系數快速分割出匹配圖像與待匹配圖像間的相似區域，僅在重疊區域中使用SIFT算法搜索特征點，提高了圖像匹配的速度。

在視頻監控、建筑、農業等領域中，存在大量具有密集重復結構的圖像。對這類圖像進行拼接時，采用SIFT、SURF等算法提取特征點時，會存在大量非常近似的特征點，從而出現很多誤匹配點；如果采用RANSAC算法剔除誤匹配點，則僅會留下少量的匹配點，且質量不高，導致出現配準鬼影。采用漸入漸出算法對圖像進行融合時，對變換模型的精度依賴很大，較多的誤匹配點會導致拼接結果出現合成鬼影，因此，對于存在密集重復結構的圖像拼接，在圖像匹配階段，應盡可能剔除誤匹配點，實現特征點間的精確匹配，消除配準鬼影；在圖像融合階段，應盡可能消除變換模型精度對拼接效果的影響，消除合成鬼影。

針對特征點的精確匹配問題，鄒承明等[17]通過構造泰森多邊形來將重疊區域劃分為4行4列的子區域來篩選出正確特征點，但構造泰森多邊形算法比較耗時，且對于密集重復結構的圖像不適用。Lin等[18]提出的RepMatch算法可以較好地解決重復結構問題，通過首先確定匹配點的核心集，然后采用暴力(Brute Force, BF)[19]算法和對極幾何約束來擴展核心集，以此來剔除重復結構中的誤匹配點，算法精度高且魯棒性好，但算法較為復雜，耗時較長。Bian等[20]提出一種基于網格運動統計的GMS算法，通過引入運動平滑性約束，在粗匹配特征點相鄰的區域中，利用統計的方式構造劃分指標來將大量的粗匹配點快速轉換成大量高質量的正確匹配點，同時使用網格結構來加速這一過程，剔除誤匹配點精度高且耗時短。

為了避免由于變換模型精度不高而產生的合成鬼影，一個有效的解決辦法是求解最佳縫合線。Duplaquet等[21]提出了一個尋找最佳縫合線的準則，利用動態規劃的思想找到最佳縫合線，方賢勇等[22]通過對圖像的分析和實驗，對文獻[21]的最佳縫合線的求解準則的結構強度差異表達式進行了修改從而更容易求得最佳縫合線。

綜上所述，目前的圖像拼接方法，在對具有密集重復結構圖像進行拼接時，不能夠很好地消除配準鬼影和合成鬼影。針對具有密集重復結構的圖像拼接問題，本文在以上研究的基礎上提出了一種快速、高精度的圖像拼接方法。該方法首先計算兩幅圖像間的重疊區域，并在重疊區域提取大量粗匹配點；然后，采用GMS算法進行精匹配，并采用RANSAC估計變換模型；最后，采用動態規劃思想求解最佳縫合線。實驗結果表明，采用本文方法對具有密集重復結構的圖像進行拼接時，在速度和拼接效果上都明顯優于傳統的SIFT和SURF算法，以及結合區域分塊的SIFT算法[11]和SURF算法。其中結合區域分塊的SURF方法，是采用文獻[11]中提出的區域分塊算法對傳統的SURF算法進行了預處理。

1 本文方法

本文將網格運動統計(Grid-based Motion Statistics, GMS)算法和最佳縫合線算法相結合，提出了一種密集重復結構的圖像拼接方法，其流程如圖1所示。

圖1 本文方法流程Fig. 1 Flow chart of the proposed method

對具有密集重復結構的圖像提取特征時，會存在大量近似的特征點，導致在特征匹配時出現大量的誤匹配點。一般采用RANSAC算法來剔除誤匹配，但RANSAC算法的原理是使用盡可能少的點來估計模型參數，然后盡可能地擴大得到的模型參數的影響范圍。對于具有密集重復結構的圖像，由于單個特征點的相似性，采用RANSAC算法剔除誤匹配點容易出現誤判，僅會留下少量的匹配點，且正確率不高，從而導致配準鬼影的出現。

GMS算法[20]根據當前匹配點周圍的統計信息，可以更準確地剔除誤匹配點；但是GMS算法的匹配精度與粗匹配點數量成正比，因此需要更多的粗匹配點。與SIFT、SURF算法相比，ORB算法能夠在更短的時間內獲得更多的特征點供匹配和過濾，因此本文方法采用ORB算法提取圖像特征點。

由于視差和密集重復結構的存在，經過GMS算法剔除誤匹配點，完成精匹配后，所估計的變換模型仍然會存在一定的誤差，導致變換模型精度不夠高。若采用常用的漸入漸出法進行圖像融合，在不精確的匹配點位置處會出現物體的不完全重合，導致明顯的合成鬼影，而最佳縫合線算法將重疊區域分割成兩部分，兩邊各取一幅圖像的內容，合理的分割線可以有效地避免合成鬼影的產生，因此，本文方法采用最佳縫合線算法進行圖像融合。

由于GMS算法采用網格結構來加速，且僅在重疊區域提取特征點，因此本文方法的效率也優于傳統算法。

1.1 圖像配準

1.1.1 特征提取與粗匹配

本文首先采用文獻[11]方法對圖像進行區域分塊，確定重疊區域；然后使用ORB算法分別提取兩幅圖像重疊區域中的特征點，得到大量的粗匹配點，采用漢明距離度量距離，并使用BF算法完成特征點的粗匹配。ORB算法采用具有方向的加速分割測試特征(oriented Features from Accelerated Segment Test, oFAST)算法提取圖像中的角點特征，采用具有旋轉不變性的二值魯棒獨立基礎特征(rotated Binary Robust Independent Elementary Features, rBRIEF)算法特征點描述子進行特征描述。

1.1.2 特征精匹配

GMS算法剔除誤匹配點基于一個假設：圖像中的像素點具有運動平滑性，因此，處于正確匹配點附近的特征點也是一一對應的[20]。也就是說，在兩幅圖像中，正確匹配點周圍也會存在許多正確匹配的點，而誤匹配點周圍不會有很多匹配點。

GMS算法的主要思想如下：首先將圖片進行網格化，對于任意網格中的匹配點xi，令Si為xi所在網格的匹配點數量，則Si服從二項分布，如式(1)所示。

(1)

其中：K表示xi的周圍的網格數；n表示xi的所在網格中的特征點數量；pt表示xi匹配正確的概率；pf表示xi匹配錯誤的概率；T表示xi匹配正確；F表示xi匹配錯誤。

Si的分布如圖2所示，從圖2中可以看出,誤匹配和正確匹配的Si分布是不同的，即正確匹配點一般要比誤匹配點多，通過設定閾值，使用Si的均值和方差就可以劃分誤匹配點和正確匹配點。為了表示方便，將Si的均值和方差結合成一個劃分指標P，對粗匹配后的特征點使用劃分指標P來剔除誤匹配點。P的計算式如式(2)所示。

(2)

圖2 Si的分布Fig. 2 Distribution of Si

為了提高算法的精度，可以將該問題轉化為一個優化問題，即最大化劃分指標P。由式(2)可得出式(3)，它表示了P正比于網格數K和網格內的特征數量n。

(3)

使用式(4)即可以判定當前網格區域是否匹配正確：

(4)

其中:Sij表示網格區域{ik,jk}和其8鄰域網格區域的匹配點總數目，示意圖如圖3所示;τi是閾值;α是一個常數因子，通常選擇α=6;Ni是K(K=9)個匹配網格區域的總特征數。

圖3 網格匹配區域{i, j}示意圖Fig. 3 Schematic diagram of grid matching region {i, j}

1.2 估計變換模型

在圖像配準后，采用RANSAC算法估計變換模型，得到兩幅圖像之間的變換關系。RANSAC算法采用迭代的方式進行數據擬合，能夠從包含異常數據的一組數據集中估計出數學模型，如圖4所示。

對于兩幅圖像f1(x,y) 和f2(x,y)，兩幅圖像上的對應匹配點(xi,yi) 和(xi′,yi′)應滿足式(5)，因此，只要已知變換矩陣H，就能將兩幅圖像變換到同一個坐標系中。

(5)

其中:h11、h12、h21、h22表示旋轉和尺度變化量;h13表示水平位移量;h23表示垂直位移量;h31和h32表示水平和垂直方向的形變量。

圖4 RANSAC算法示意圖Fig. 4 Schematic diagram of RANSAC algorithm

經過精匹配后，仍然會存在一定數量的誤匹配點，RANSAC算法可以在存在誤匹配點的情況下，估計出兩幅圖像的變換矩陣。

1.3 圖像融合

本文采用最佳縫合線算法[22]進行圖像拼接。將滿足下列兩個條件的縫合線定義為最佳縫合線：

1)顏色強度上，兩幅圖像的顏色差異最小；

2)結構強度上，縫合線上的像素點在兩幅原始圖像上的結構最相似。

結構強度差值是通過修改梯度計算Sobel算子[22]實現的，修改后的Sobel算子如下:

由變換矩陣H將兩幅圖像變換到同一坐標系后，求取兩幅圖像的重疊區域的差值圖像，然后運用動態規劃的思想，以差值圖像第一行像素為起點，建立多條縫合線，并從中尋找顏色強度和結構強度最小的一條縫合線，作為最佳縫合線，其過程如圖5所示。

圖5 最佳縫合線搜索過程Fig. 5 Searching process of optimal seam

算法時間復雜度為計算結構強度和顏色強度的復雜度O(M*N)和尋找強度最小縫合線的復雜度O(M*N)，忽略常數項后，最終時間復雜度為O(M*N)，M表示重疊區域的高度，N表示重疊區域的寬度。

2 實驗與結果分析

2.1 運行環境

本文算法實驗環境如下：Intel core i7- 7700/3.60 GHz CPU，8 GB內存，64位Windows 10操作系統，編程語言為C++，在Microsoft Visual Studio Community 2017中運行。

2.2 評價指標

本文分別采用主觀評價準則和客觀評價指標對對實驗結果進行綜合評價。主觀評價準則要求圖像中看不出拼接痕跡，且過渡自然、拼接處沒有鬼影出現。客觀評價指標采用了運行時間和匹配正確率(Correct Matching Rate, CMR)，CMR值越大，匹配性能越好。

2.3 特征精匹配對比實驗

為了驗證本文方法對于密集重復結構圖像特征精匹配的有效性，分別采用SIFT+RANSAC算法、SURF+RANSAC算法和本文方法對兩組龍貓圖片進行剔除誤匹配點對比實驗。實驗采用的兩組龍貓圖片來自于網絡，龍貓的姿態和所處的背景均發生了變化，且龍貓身上的紋理和背景環境中均存在大量密集重復結構。實驗結果如圖6和表1所示。為避免提取的特征點較少導致兩幅圖像不能匹配，3種算法都通過參數設置盡可能提取更多的特征點，其中：SIFT算法和本文方法分別設置提取10 000個特征點，SURF算法設置較低的閾值，以期望提取更多的特征點。

圖6 不同方法剔除誤匹配點結果對比Fig. 6 Result comparison of different methods for rejecting false matching points

從圖6中可以看出，SIFT算法和SURF算法提取的粗匹配點對較少，經過RANSAC算法再次篩選后，僅能找到少量的正確匹配點；而使用本文算法可以得到更多正確的匹配點。表1是剔除誤匹配點的客觀評價對比，由表1可以看出，本文方法不僅可以獲取更多的匹配點，且匹配正確率更高，耗時更短。

表1 不同方法剔除誤匹配點客觀指標對比Tab. 1 Objective indicator comparison of different methods for rejecting false matching points

2.4 圖像拼接對比實驗

圖像拼接對比實驗的圖片由作者從西安科技大學圖書館和實驗樓采集而來。圖書館和實驗樓的外觀均存在密集重復結構，使用相機以較大視差分別拍攝兩張圖像，并保證相鄰兩幀間有一定程度的重合，如圖7所示。圖像分辨率為1 440像素×1 080像素。

本文方法在預處理階段，首先采用文獻[11]的區域分塊算法確定了重疊區域，然后僅對重疊區域進行特征提取和匹配。為了保證實驗效果的可參考性，對比實驗中對SURF算法和ORB算法也都采用區域分塊的方法進行了預處理。為了便于描述，將文獻[11]中的方法(區域分塊+SIFT+RANSAC+漸入漸出算法)簡稱為AB-SIFT算法，將結合區域分塊的SURF+RANSAC+漸入漸出算法簡稱為AB-SURF算法，將結合區域分塊的ORB+GMS+漸入漸出算法簡稱為AB-ORB算法。

圖7 大視角重復結構圖像(拼接前)Fig. 7 Large angle repetitive structure images (before stitching)

圖像拼接實驗結果如圖8～9所示，其中子圖(c)中的折線部分為本文方法找到的最佳縫合線。

從圖8～9可以看出，AB-SIFT和AB-SURF的拼接結果圖中均出現了明顯的鬼影,例如圖8中的安全警示樁和圖9中的墻壁，這是因為所提取出的正確匹配點較少，導致變換模型精度不夠。由于ORB算法可以得到更多的粗匹配點，使得變換模型能計算得較為精確，因此AB-ORB的拼接效果要優于AB-SIFT和AB-SURF算法;但是由于變換模型不夠精確，圖8和圖9所示AB-ORB算法的拼接結果中墻壁部分仍然出現了鬼影，主要原因是漸入漸出算法過于依賴變換模型的精確，由于墻壁上紋理稀疏且結構重復，即使經過GMS算法處理后，變換模型的精度還是不夠高，導致出現了合成鬼影，而本文算法有效地避免配準鬼影和合成鬼影的產生，在墻壁和安全警示樁處均未出現鬼影，達到了理想的拼接效果。

圖8 圖書館拼接結果Fig. 8 Stitching results of library

圖9 實驗樓拼接結果Fig. 9 Stitching results of laboratory

為了驗證區域分塊對拼接速度和質量的影響，圖像匹配的客觀指標對比實驗中除了以上算法外，增加了經典SIFT算法和SURF算法的結果，如表2～3所示。從表2～3可以看出，采用區域分塊并確定重疊區域的方法，在提高匹配精度的同時，也明顯提高了拼接速度。對于具有重復結構的圖7(a)，由于其紋理信息較為豐富，因此SIFT、AB-SIFT、SURF和AB-SURF算法提取的初始匹配點數目較多，所以耗時較長；對于圖7(b)，由于紋理特征較少，SIFT、AB-SIFT、SURF和AB-SURF算法剔除的初始匹配點數目較少，雖然耗時變短了，但是經過篩選之后留下的正確匹配點更少了，導致拼接結果不理想。從表2～3中還可以看出，本文方法在兩幅圖像中都能提取較多的特征點，且CMR指標均最高，運行時間比采用漸入漸出融合算法的AB-ORB算法略長，盡管漸入漸出算法和最佳縫合線算法的時間復雜度都是O(M*N)，但是對所計算出的結構值進行排序求最小值的時間復雜度也是O(M*N)，所以比漸入漸出融合算法的耗時要長，但是本文方法拼接效果是最好的，因此，綜合運行時間、匹配精度和拼接效果三方面，本文方法更具有優越性，平均拼接速度分別是傳統SIFT和SURF算法的7.4倍和3.2倍，是結合區域分塊的SIFT算法的4.1倍，是結合區域分塊的SURF算法的1.4倍。

表2 剔除誤匹配點效率對比Tab. 2 Efficiency comparison of rejecting false matching points

表3 剔除誤匹配點時間對比 單位：ms Tab. 3 Time comparison of rejecting false matching points unit:ms

3 結語

對于具有密集重復結構的圖像拼接，使用SIFT、SURF及其改進算法提取特征點時，會存在大量的誤匹配點，經RANSAC算法剔除誤匹配點后，保留下的匹配點數量很少，且精度不高，導致變換模型估計不精確，出現拼接鬼影和合成鬼影。針對此問題，本文提出了一種基于GMS和最佳縫合線的快速圖像拼接方法。GMS能夠更精確地剔除誤匹配點，保留更多的正確匹配點，為圖像拼接提供更高精度的變換模型，且速度更快；最佳縫合線法能夠在變換模型精度有所欠缺的情況下，有效抑制合成鬼影。實驗結果表明，對于具有密集重復結構的圖像，本文方法能夠獲得更佳的拼接效果，且運行時間更短。如何更進一步地提升圖像拼接算法的性能，并最終實現實時拼接，是接下來的研究方向。