基于ORB和改進RANSAC算法的圖像拼接技術

佘建國，徐仁桐，陳 寧

(1.江蘇科技大學機械工程學院，江蘇鎮江212003)

(2.江蘇科技大學能源與動力工程學院，江蘇鎮江212003)

照片拼接是將同一個場景的若干照片進行配準，找到重疊區域，進行重疊區域對齊、變換、融合，組成一幅視野寬廣的場景圖片［1］.照片拼接技術已廣泛應用于海事、軍事、遙感、視頻監控等領域.

ORB算法是Roblee E等人在2011年的ICCV(IEEE international conference on computer vision)提出的一種匹配算法，其運算速度與SIFT相比，SURF算法有了很大的提升.ORB 是一種局部不變特征描述子，對照片圖像的平移、旋轉、縮放等矩陣變換具有不變性.該算法思想是在圖像金字塔上利用改進的FAST進行角點特征檢測，并確定主方向，使特征點有一定的尺度不變性［2］;然后用改進的BRIEF描述特征，使描述符有一定的旋轉不變性.

使用ORB進行粗匹配后，針對某些不正確的匹配，文中設計了一種改進的RANSAC算法，對誤匹配進行剔除.

1 ORB算法實現粗匹配

1.1 ORB 特征檢測

該文采用 oFAST(oriented FAST)算子進行ORB特征檢測.oFAST特點是給FAST算子檢測到的角點添加方向信息.它首先采用Harris算法檢測角點.FAST檢測的角點定義［3］是:若某像素點與其周圍鄰域內足夠多的像素點處于不同的區域，則該像素點可能為角點.如圖1所示，從圖片中選取一個像素點P，并設其像素值為XP;將該像素點與周圍的16個像素點進行比較，若這個以P點為圓心，16個像素點組成的圓上有N個連續像素點，其像素值要么都比XP+T(T為選取的閾值)大，要么比XP-T小，那么它就是一個角點，N一般取9或者12.

圖1 FAST角點檢測Fig.1 FAST corner detection

然后，FAST角點主方向運用 Intensity Centroid［4］來運算.FAST角點主方向通過圖像團塊的灰度矩來確定，定義如式(1)所示，其中，q決定了灰度矩的階數，I(x，y)為點(x，y)處的灰度值.

灰度矩心設為C=(Cx，Cy)，其中因此，角點區域的主方向為:

利用角點主方向，就可提取BRIEF描述子.為了提高算法的旋轉不變性，需要確保x，y在鄰域半徑為 r的圓形區域內，即 x，y ∈［-r，r］.

1.2 ORB 特征描述

文中采用rBRIEF(rotated BRIEF)算法來進行ORB特征描述.原理是從oFAST算法檢測出的所有角點中找到效果良好的點對，用來描述圖像特征.一般角點大小為31×31［5］，在 ORB 算法中用ORB::CommonParams(1.2，1，31)體現，二進制測試對的每個區域窗口大小為5×5.將角點測試對進行灰度差異二值化的公式如式(3)，其中x，y表示角點的位置.

選擇n個角點位置(x，y)，對其進行特征運算，如式(4).

n可以取128，256等數值，數值不同會影響運行速度、識別率、存儲率.ORB本身不具備旋轉不變性［6］，解決辦法是將角點主方向作為BRIEF的主方向.設有n對位置坐標(xi，yi)，構造2×n矩陣:

對2×n矩陣進行旋轉變換，變換矩陣采用角點主方向θ的旋轉矩陣，使得M矩陣變成有向形式，如式(5)所示.

所以得出rBRIEF描述子結果為:

1.3 ORB粗匹配編程

VS2010是微軟推出的集成開發環境，數字圖像處理是其主要功能之一，但單純使用VS2010處理圖像難度很大.OpenCV擁有許多圖像處理函數［7］，若將其和VS2010結合，便會降低工作難度，減少工作量.因此，文中的ORB編程采用OpenCV嵌入到VS2010實現.

文中首先安裝OpenCV2.3.1版本，選擇屬性＞高級系統設置＞環境變量＞新建，新建一個用戶變量，將安裝的OpenCV的lib路徑作為其變量值.然后在VS2010下新建一個項目，右擊選擇屬性＞配置屬性＞VC++目錄，引入OpenCV的包含目錄和庫目錄.接著在Debug和Release的附加依賴項中引入opencv_calib3d231d.lib，opencv_highgui231d.lib 等庫文件.配置成功后，編程時要在程序的開頭包含OpenCV 的頭文件，如 cv.h，highgui.h 等.文中實現ORB算法檢測的C++關鍵代碼如下:

ORB orb;

/*引入OpenCV庫中的ORB特征類*/

vector＜KeyPoint＞ Pts1，Pts2;/* 創建對象類型為Keypoint類的兩個容器以存儲特征點*/

Mat describer1，describer2;

/*定義存放特征向量的兩個矩陣*/

orb(image1，Mat()，Pts1，describer1);orb(image2，Mat()，Pts2，describer2);

BruteForceMatcher＜HammingLUT＞ matcher;/*定義一個BurteForceMatcher對象*/

vector＜DMatch＞ matches;

matcher.match(describer1， describer2， matches);/*對特征向量進行匹配*/

采用一對540×380像素的圖像進行粗匹配，運行結果如圖2，其中a)，b)為特征點檢測，c)為特征點粗配準.發現有一些誤匹配存在，需用RANSAC去除誤匹配.

圖2 ORB算法粗匹配Fig.2 Coarse matching with ORB algorithm

2RANSAC算法改進

RANSAC算法是一種經典的消除誤匹配的方法，具有匹配精度高、可靠度高，魯棒性強［8］等優點.RANSAC算法需要用到單應矩陣H(Homography Matrix)［9］，它描述了兩幅圖像點坐標之間的變換關系，即Ai′=HAi，可以進行圖像之間的平移、旋轉和縮放［10］.H 變換如式(7)所示，其中(x，y)，(x′，y′)表示待匹配特征點坐標.

用RANSAC算法剔除誤匹配的關鍵是求出單應矩陣H，在VS2010中對H的編程代碼如下:

CvMat*H;/*定義單應矩陣H*/

H=ransac_xform(feature1，n1，FEATURE_FWD_MATCH， lsq_homog，4，0.01，homog_xfer_err，3.0，＆inliers，＆n_inliers);/* 定義H的各項參數，其中inliers表示提純后的內點對數，n-inliers表示最終匹配點對個數*/

經典RANSAC算法［11］采用迭代法來估計H矩陣的 8 個參數(a0，a1，a2，…，a7)，基本過程如下:

步驟1:將兩幅圖像進行粗匹配，獲得N個待匹配點對的集合，并進行坐標歸一化.即Ai′?Ai，其中 i=1，2，…，N.

步驟2:從N個待匹配點對中隨機選取4個點對，解出矩陣H的8個參數.

步驟3:計算其余(N-4)個特征點經過矩陣H變換得到的特征點與其他待匹配特征點之間的歐氏距離 d，d= ‖HA-A′‖.若 d ＜ t(t為閾值［12］)，則該待匹配特征點為內點，反之為外點.

步驟4:重復步驟2～3 k次，計下每一次的內點數量，其中k為迭代次數.

步驟5:選擇內點數最多的集合作為最終內點集合［13］，與此相對應的H變換中的8個參數作為參數估計最優值.

實際發現，粗匹配檢測出的特征點對有一些偏差很大，如圖2 a)左部特征點對應于圖2 b)右部特征點，顯然不匹配，但經典RANSAC算法步驟還是把這些點帶入計算，使得算法速度慢、工作效率低，尤其在兩幅圖片特征點數量多的時候愈發明顯.于是文中對RANSAC算法進行一些改進，先采用空間一致性法［14］，在算法過程中剔除明顯的錯誤匹配點，以縮小抽樣點總量，減少迭代次數.

空間一致性理論可以用圖3具體說明.相似的結構容易導致錯誤的匹配，圖3中檢測兩扇不同但相似的窗子，得出了12對彩色特征點，并用不同色彩表示不同值的特征點.如果考慮一下鄰域的彩點情況，如圖中考慮8點的鄰域(紅圓圈出)，可以發現雖然8和8*特征相同，但鄰域內6和6*、9和9*、12和12*等特征不同，結果可以判定8和8*不匹配，這就是空間一致性理論的基本思想.

圖3 不同窗戶的相似特征點Fig.3 Similar feature points between different windows

對兩幅圖進行空間一致性檢查，需要設圖像為Gi，定義尺寸不變特征函數:式中:(xj，yj)為特征點中心坐標;σj為尺度;dj為描述子.對于每一個特征 fj，定義其鄰域集合NGi(fi)，其包含以(xj，yj)為圓心，rσj為半徑的圓的特征點，并且尺度大小在(sminσj，smaxσj)范圍.NGi(fi)集合表示如式(9)所示，式(9)中的∧表示取小運算.

設有一圖像對(G1，G2)，通過各自的特征點描述子可以進行點匹配，形成匹配點集C:

然后定義一個匹配點集c=(f1j，f2k)∈C的鄰域集N(c):

那么就說明匹配點集是符合空間一致性的，其中臨界值θ∈［0，1］.這樣，就可以從匹配點集C剔除錯誤點，形成新點集Cnew，顯然Cnew?C.

改進RANSAC算法采用上述空間一致性檢測原理，其步驟如下:

步驟1:通過ORB算法檢測出粗匹配點，點集為C.

步驟2:采用空間一致性檢查點集C，得出新點集Cnew.新點集的數目

步驟3:采用經典RANSAC對N個匹配點進行迭代計算.設 k=0，εnew=m/N，I*=0，其中 k為迭代次數，m為Cnew中的隨機匹配點，εnew為Cnew局內點所占的比例.當η=(1-εmnew)k≥ η0時，計算圖像變換模型φ，算出局內點的數目I，若I＞I*，則I*=I，εnew=I*/N，存儲 φ，直到 η ＜ η0為止.

3 改進RANSAC實驗

為了驗證改進算法的實際效果，采用2組圖片進行匹配性試驗，并且統計運算結果.首先，運用改進RANSAC對圖2a)，b)進行提純，精匹配效果如圖4 a)，拼接結果如圖4 b)所示.

圖4 540×380像素圖片匹配Fig.4 Matching of 540 ×380 pixels′images

同樣，再用改進RANSAC算法對一組300×400像素圖片進行檢測.粗匹配和精匹配效果如圖5a)，b)所示，拼接的效果如圖5 c)所示.

圖5 300×400像素圖片匹配Fig.5 Matching of 300 ×400 pixels′images

運用ORB和經典RANSAC對同樣的圖片進行匹配試驗，效果如圖6a)，b)所示.為了統計提純時間，采用cvGetTickCount()、cvGetTickFrequency()函數的組合實現，其獲取時間的代碼片段如下:

int64 bt，et;∥定義整型變量計算時間

bt=cvGetTickCount();∥開始時間

……;∥寫入需要監測時間的RANSAC代碼

∥片段

et=cvGetTickCount();∥結束時間printf(“提純時間=%f Seconds ”，(et-bt)/

(double)cvGetTickFrequency()/1000000.0);

∥輸出時間

圖6 ORB+RANSAC對兩組圖片提純的效果Fig.6 ORB+RANSAC purifying effect on the two groups of images

采用matches.size()函數得出ORB粗匹配點對數，通過inliers++自增運算獲得提純后inliers內點對數.考慮到系統環境的變化性，對兩組圖片分別調試10次，算出平均內點對數、提純時間等參數.對實驗結果進行統計，結果如表1所示.由表可見，改進RANSAC算法的剔誤率和經典RANSAC相當，提純速度有所提高;該改進算法在兩幅圖片角度、亮度等差異較大的情況下提純速度提升較明顯.

表1 算法比較Table 1 Comparison of algorithms

4 結論

文中對ORB算法進行了研究，采用oFAST算子和rBRIEF描述子實現了圖像粗匹配.在結合前人研究的基礎上，將空間一致性理論運用在RANSAC算法中，對其進行了改進.采用兩組圖像進行了實驗，對該改進算法和經典RANSAC算法進行比較，算出了精匹配的內點對數、提純時間、剔誤率等評估參數.

實驗表明，改進RANSAC算法在保證匹配精度的條件下，提高了提純速度.而且ORB原本的運算速度就很快，據文獻［15-16］描述，其速度是SIFT的100倍，是 SURF的10倍.那么，ORB和改進RANSAC的結合，在進行圖像快速拼接，尤其在視頻幀圖像的快速拼接時，運用此算法可以達到良好的實時性，保證了實時拼接的流暢性.這對于圖像或者視頻實時拼接技術研究者有一定的借鑒作用.

References)

［1］ 傅軍棟，姚孝明.實景圖像拼接及其漫游控制技術［M］.成都:西南交通大學出版社，2011:1-20.

［2］ 張云生，鄒崢嶸.基于改進ORB算法的遙感圖像自動配準方法［J］.國土資源遙感，2013，25(3):20-24.Zhang Yunsheng，Zou Zhengrong.Automatic registration method for remote sensing images based on improved ORB algorithm ［J］.Remote Sensing for Land ＆ Resources，2013，25(3):20-24.(in Chinese)

［3］ 李小紅，謝成明，賈易臻，等.基于ORB特征的快速目標檢測算法［J］.電子測量與儀器學報，2013，27(5):455-460.Li Xiaohong，Xie Chengming，Jia Yizhen，et al.Rapid moving object detection algorithm based on ORB features［J］.Journal of Electronic Measurement and Instrument，2013，27(5):455-460.(in Chinese)

［4］ Rosin P L.Measuring corner properties［J］.Computer Vision and Image Understanding，1999，73(2):291-307.

［5］ 黃征宇.用于ATM機遮擋人臉檢測的模糊級聯分類器和ORB算法的研究［D］.長沙:中南大學，2013.

［6］ 侯毅，周石琳，雷琳，等.基于ORB的快速完全仿射不變圖像匹配［J］.計算機工程與科學，2014，36(2):303-310.Hou Yi，Zhou Shilin，Lei Lin，et al.Fast fully affine invariant image matching based on ORB［J］.Computer Engineering ＆ Science，2014，36(2):303-310.(in Chinese)

［7］ 王小力.基于OpenCV和VC++的目標提取技術［J］.硅谷，2010(15):164-165.Wang Xiaoli.Target extraction technology based on OpenCV and VC++［J］.Silicon Valley，2010(15):164-165.(in Chinese)

［8］ 田文，王宏遠，徐帆，等.RANSAC算法的自適應Tc，d預檢驗［J］.中國圖象圖形學報，2009，14(5):973-977.Tian Wen，Wang Hongyuan，Xu Fan，et al.Enhanced RANSAC with adaptive Tc，dpre-verification ［J］.Journal of Image and Graphics，2009，14(5):973-977.(in Chinese)

［9］ 宋衛艷.RANSAC算法及其在遙感圖像處理中的應用［D］.河北保定:華北電力大學，2011.

［10］ 孫強，葉玉堂，宋昀岑，等.基于優化RANSAC算法的二次元快速穩定配準［J］.計算機工程與設計，2012，33(6):2373-2377.Sun Qiang，Ye Yutang，Song Yuncen，et al.Fast and stable method based on optimized RANSAC algorithm for two-dimensional image［J］.China Computer Federation Magazine，2012，33(6):2373-2377.(in Chinese)

［11］ 介軍，李智杰，姚鵬.改進的RANSAC匹配點提純算法［J］.西安建筑科技大學學報:自然科學版，2013，45(6):896-901.Jie Jun，Li Zhijie，Yao Peng.Improved RANSAC algorithm of matched points purifying ［J］.Journal of Xi′an University of Architecture＆Technology:Natural Science Edition，2013，45(6):896-901.(in Chinese)

［12］ 馬麗濤，楊丹，張小洪，等.一種新的基于條件數的圖像配準算法［J］.中國圖象圖形學報，2008，13(2):278-283.Ma Litao，Yang Dan，Zhang Xiaohong，et al.A new method for image registration based on condition number［J］.Journal of Image and Graphics，2008，13(2):278-283.(in Chinese)

［13］ 黃有群，付裕，馬廣.基于RANSAC算法的柱面全景圖拼接方法［J］.沈陽工業大學學報，2008，30(4):461-465.Huang Youqun，Fu Yu，Ma Guang.Cylindrical panoramic image stitching method based on RANSAC algorithm［J］.Journal of Shenyang University of Technology，2008，30(4):461-465.(in Chinese)

［14］ Sattler T，Leibe B，Kobbelt L.SCRAMSAC:improving RANSAC′s efficiency with a spatial consistency filter［C］∥Proceedings of the IEEE International Conference on Computer Vision.Piscataway:IEEE，2009:2090-2097.

［15］ 謝成明.基于ORB特征的目標檢測與跟蹤的研究［D］.合肥:合肥工業大學，2013.

［16］ Rublee E，Rabaud V，Konolige K，et al.ORB:an efficient alternative to SIFT or SURF［C］∥Proceedings of the IEEE International Conference on Computer Vision.Piscataway:IEEE，2011:2564-2571.