一種基于RANSAC的柱面圖像配準算法

摘要:提出了一種基于RANSAC的柱面圖像配準算法。算法首先采用NCC算法對檢測出來的Harris角點進行粗匹配，然后采用兩次改進的RANSAC算法刪除誤配，提高正確匹配角點的數量，最后對仿射變換模型參數進行Levenberg-Marquardt非線性優化以進一步降低圖像的配準誤差。實驗結果表明:通過一次改進RANSAC去錯配后角點有效匹配率達到約99.2%，通過二次改進RANSAC去錯配后角點有效匹配率達到約99.6%，與現有算法相比，在同等條件下獲得了更高的匹配有效率。

關鍵詞:圖像處理; 特征提取; 圖像配準; RANSAC; NCC

中圖分類號:TP391文獻標識碼:A

A RANSAC-Based Cylindrical Image Registration Algorithm

LIU Xiangbin1，2， ZOU Beiji1

(1. School of Information Science and Engineering， Central South University， Changsha， Hunan 410083， China; 2. Institute of Image Recognition Computer Vision， Hunan Normal University， Changsha， Hunan 410081， China)

Abstract: A RANSAC-based cylindrical image registration algorithm is presented. First， the algorithm makes a coarse matching for the detected Harris corner points using the NCC algorithm. Then， it reduces the 1 matched pairs by two pass of improved RANSAC algorithm to increase the number of right matched pairs. At last， it optimizes the affine transformation model parameters using Levenberg-Marquardt algorithm to lower the registration error further. Experiment shows that the right matched ratio of Harris corner reaches 99.2% after one time of improved RANSAC， and reaches 99.6% after two times of improved RANSAC. Compared with present methods， it has achieved higher right matched ratio under the same conditions.

Key words: image processing; feature extraction; image registration; RANdom SAmple Consensus; Normalized Cross Correlation

在全景圖的生成過程中，最關鍵的就是圖像的拼接技術，而拼接技術的核心是圖像的配準技術[1]。圖像配準是立體視覺、運動分析、數據融合等實用技術的基礎，在導航、地圖與地形配準、自然資源分析、天氣預報、環境監測、生理病變研究等許多領域都有重要的應用價值，因而得到廣泛的研究[2-3]。

常用的圖像配準方法一般可以分為基于灰度的圖像配準方法和基于特征的圖像配準方法兩種。由于基于灰度的圖像配準方法對光照、對比度和拍攝角度等敏感，而基于特征的圖像配準方法能夠很好地解決這些問題，因此，目前普遍采用的是基于特征的圖像配準方法[4]。

RANSAC算法[5]是基于特征的圖像配準算法中的典型算法，其優點是可靠、穩定、精度高，對圖像噪聲和特征點提取不準確有強健的承受能力，魯棒性強，并且具有較好的剔出誤匹配點的能力，經常被使用在圖像特征匹配中。但RANSAC算法通常只適用于平面圖像的配準，而不適合于柱面圖像的配準[6]。為此，本文對其進行改進，提出了一種將NCC角點匹配算法[7]與改進的RANSAC算法相結合的圖像配準算法，應用于柱面圖像的配準。該算法在提取待配準圖像的Harris角點的基礎上，首先采用NCC算法對檢測出來的角點進行粗匹配，然后采用兩次改進的RANSAC算法刪除誤配，提高正確匹配角點的數量，最后對仿射變換模型參數進行Levenberg–Marquardt(LM)非線性優化[8]以進一步降低圖像的配準誤差，從而獲得了良好的配準效果。

1 本文算法

1.1NCC角點匹配

角點匹配是點特征圖像配準中的關鍵步驟。所謂角點匹配是指在獲得兩幅圖像的所有角點之后，找出兩幅圖像角點之間的對應關系。角點的匹配通常采用不相似測度SSD(sum of square differences)[9]和相似測度NCC來匹配。本文采用相似性測度NCC算法來進行角點的粗匹配。

設W1和W2是分別以圖像1中的角點p1和圖像2中的角點p2為中心的兩個大小相同的窗口，u1和u2為相關窗口內像素灰度的均值，(xi，yi)的取值范圍為窗口大小，則定義基于NCC的兩幅圖像間的相似測度如式(1)所示。

(1)

NCC匹配方法去除了低頻背景亮度信息的干擾。進行角點匹配時，首先對于圖像1中的任一角點，尋找在圖像2中和它相關性最大的角點;然后對于圖像2中的任一角點，尋找在圖像1中和它相關性最大的角點，當雙向搜尋到的最大相關性的角點彼此對應且相關性大于某一閾值時，即認為找到了一對候選匹配角點。

1.2變換估計與配準誤差

在拍攝360°全景圖序列圖像時，相機的運動包括平移和旋轉，在相機傾斜程度不大以及焦距足夠大的時候，基于仿射變換的方法可獲得較好的匹配結果。仿射變換模型可以看作是透視變換模型的一種近似，它可處理的相機運動包括相機的平移、鏡頭的拉伸和繞光軸的旋轉。在全景圖序列圖像中，相鄰兩幅圖像之間的關系可以用如式(2)所示的仿射變換關系表示。

(2)

其中，

(3)

經NCC角點粗匹配后形成了圖像1和圖像2之間的一組映射點集，接下來就是從這一組映射點集中估算仿射變換矩陣H的6個參數。

對給定圖像1和圖像2及n組候選初始匹配點:，根據仿射變換關系式(2)可知，每一對匹配點可得到兩個方程，代入3對不共線的匹配點，可得到6個方程，從而可求解得到變換矩陣H。但在實際的計算過程中，由于噪聲、角點定位誤差、模型誤差、角點錯配等因素的存在，往往需要代入8對以上匹配點坐標，然后利用最小二乘法求解。

平均幾何配準誤差是衡量配準算法精度的一個重要指標，其誤差如式(4)所示。

(4)

其中，dist表示兩點之間的距離。

1.3RANSAC算法

NCC角點匹配屬于粗匹配，其中含有不少的錯配，如果直接采用其匹配結果進行配準，則會帶來較大的配準誤差。

RANSAC是一個采用迭代法來估計參數的數學模型，具有可靠、穩定、精度高、魯棒性強等優點，是基于特征的圖像配準算法中的典型算法，具有較好的剔除誤匹配點的能力，經常被應用在圖像的特征匹配中[6]。例如，對于存在個別嚴重偏差的離散點序列，如果采用最小二乘法進行直線擬合，其擬合的結果將會產生嚴重的誤差，而采用RANSAC算法則會得到一條理想的直線。這樣存在嚴重偏差的點在RANSAC算法中被稱為外點。RANSAC算法首先隨機選取兩個特征點，構造一條直線，根據事先確定的容許誤差來計算這條直線可以包含多少個點，這條直線包含的點被稱為內點，然后根據這些內點重新計算出一條新的直線，如此重復下去，直到內點的數量不再變化為止，從而得到RANSAC算法的擬合結果，因此算法的精度得到了顯著的提高。

1.4本文算法描述

但RANSAC算法通常只適用于平面圖像的配準，而不適合柱面圖像的配準，為此，本文對其進行改進，發揮其優點，使其應用于柱面圖像的配準。

由式(1)可知，如果兩幅圖像之間的某一初始匹配(x，x’)的相似測度值小于某一閾值T則可認為它們之間不匹配，可將其去除，這正是RANSAC算法中剔除外點的思想。可用式(5)表示。

(5)

其中，

(6)

稱為基礎矩陣。基礎矩陣可采用仿射變換矩陣H的方法來獲得，代入9對不共線的匹配點，得到9個方程，但在實際計算中，由于噪聲、角點定位誤差、模型誤差、角點錯配等因素，往往需要代入10對以上匹配點坐標，然后利用最小二乘法求解。

改進的RANSAC算法可描述如下:

(1)將當前最佳估計內點數目Ni設置為0;

(2)對圖像按寬度和高度最小值的1/4分割為一系列的子塊，然后在所有子塊中隨機抽取3個子塊，并在每個子塊中隨機抽取一個點作為初始點，兩幅圖像的初始點集組成初始匹配點對，根據選取出的初始匹配對利用最小二乘法計算出變換矩陣H1;

(3)對所有初始匹配(x，x’)，統計 小于給定容許誤差t1的匹配點數目，作為當前內點數，并利用最小二乘法計算基礎矩陣F;

(4)將當前內點數目與Ni進行比較，如果大于Ni則將基礎矩陣F作為當前最佳估計并更新Ni，同時動態估測剩余所需迭代次數S(S正比于1/log(p)，其中p為Ni占初始匹配點數目的比例)。如果當前迭代次數達到S，則保留F并進行下一步;否則循環執行(2)~(4)。

(5)根據F和圖像1中所有角點的位置信息，估算這些角點在圖像2中的位置區域，并在這個區域內(一般取3×3的窗口)重新進行角點匹配。由于此時的錯誤匹配角點對很少，變換矩陣H已經接近實際真實值，故可以更精確、有效地指導角點匹配，所以會產生更多的有效匹配角點。

(6)設置一個更低的閾值t2，再次執行一遍RANSAC算法，得到最終的基礎矩陣F，根據匹配角點的位置，利用最小二乘法求出變換矩陣H2。

(7)為了更進一步降低配準誤差提高配準精度，采用優化誤差函數式(4)進行Levenberg – Marquardt非線性優化，優化進行的初始值為第二次RANSAC算法得到的H2。因為此時LM優化是在較好的初始條件下進行的，所以可以在較短的時間內完成，并且不會陷入局部極小值的問題。

2 實驗結果與分析

本文對所提算法予以實現并分別對室內、建筑物外景、自然風光等幾種場合下的圖像進行了配準實驗。下面以如圖1所示湖面圖像的配準為例予以分析。

本文首先采用改進的Harris角點檢測算法獲得角點。圖1(a)和(b)為兩幅圖像的Harris角點檢測圖，NCC匹配后角點對數為657對，其中正確配對492對，角點匹配的有效率約為74.9%，如圖1(c)所示。一次RANSAC去錯配(t1=0.001)將角點的匹配對數降為509對，其中正確配對505對，角點匹配的有效率達到99.2%，如圖1(d)所示，二次RANSAC去錯配(t2=0.0002)后，角點的匹配對數變成507對，正確配對505對，匹配有效率達到99.6%，如圖1(e)所示。與文獻[6]算法相比，同等條件下，文獻[6]算法的角點匹配對數為536對，正確配對517對，匹配有效率為96.5%。本文算法獲得了更高的匹配有效率，圖1(f)為本文算法最終得到的圖像1中匹配角點的情況，圖1(g)為最終的圖像配準效果圖。

從實驗結果可以看出，本文提出的圖像配準算法的角點匹配有效率遠遠高于NCC算法的角點匹配有效率，也高于同類算法，圖像配準效果良好，說明了算法的有效性和實用性。

3 結論

本文利用RANSAC算法在參數估計方面的優點，并針對RANSAC算法適用于平面圖像的配準而不適用于柱面圖像的配準的不足，對其進行改進，提出了一種基于RANSAC算法的圖像配準算法，應用于柱面圖像的配準。實驗表明，算法獲得了良好的配準效果。

參考文獻

[1]趙輝，陳輝，于泓.一種改進的全景圖自動拼接算法[J].中國圖象圖形學報， 2007，12(2):336-342.

ZHAO Hui，CHEN Hui，YU Hong. An improved fully -automatic image mosaic algorithm [J]. Journal of Image and Graphics，2007，12(2):336-342. (In Chinese)

[2]彭文，童若鋒，錢歸平，等.使用特征點與灰度值的醫學圖像局部配準方法[J].中國圖象圖形學報，2008，13(5): 944-950.

PENG Wen， TONG Ruo-feng， QIAN Gui-ping， et al. Local registration of medical images using feature point and intensity information [J]. Journal of Image and Graphics， 2008，13(5):944-950. (In Chinese)

[3]鄭世友， 周曄. 無有效重疊區域的SAR圖像拼接方法[J].中國圖象圖形學報，2009，14(10):2054-2060.

ZHENG Shi-you， ZHOU Ye. A novel mosaic method for SAR image sequences with deficiency of overlap portion [J].Journal of Image and Graphics，2009，14(10):2054-2060. (In Chinese)

[4]王偉，陸佩忠. 數字圖像拼接技術[J] .小型微型計算機系統，2006，27(7):1347-1352.

WANG Wei， LU Pei-zhong. An overview of digital image mosaic [J]. MINI-MICRO systems， 2006，27(7):1347-1352. (In Chinese)

[5]ZHANG Zheng-you， DERICHE R. A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry [J]. Artificial Intelligence， 1995，78:87-119.

[6]黃有群，付裕，馬廣焜. 基于RANSAC算法的柱面全景圖拼接方法[J]. 沈陽工業大學學報， 2008，30(4):461-465.

HUANG You-qun， FU Yu， MA Guang-kun. Cylindrical panoramic image stitching method based on RANSAC algorithm [J]. Journal of Shenyang University of Technology， 2008， ，30(4):461-465. (In Chinese)

[7]FISCHLER M， BOLLES R. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. ACM， Graphics and Image Processing，1981，24(6):381-395

[8]MARQUARDT D. An algorithm for least squares estimation of nonlinear parameters[J]. J Soc Ind Appl Math， 1963: 431-441.

[9]SCHARSTEIN D， SZELISKI R. A taxonomy and evaluation of dense two frame stero correspondence algorithms [J]. Int J Computer Vision， 2002， 47(1-3):7-42.