基于BRISK和改進RANSAC算法的圖像拼接

1、基于BRISK和改進RANSAC算法的圖像拼接圖像拼接是圖像處理的一個重要領(lǐng)域，指的是將兩張或多張有重疊像素的圖像經(jīng)過一系列操作組成一張廣角圖像1，目前廣泛應(yīng)用于遙感影像配準、計算機視覺、醫(yī)學(xué)圖像處理、視覺 SLAM 以及嵌入式設(shè)備等領(lǐng)域，如相機在拍攝時由于拍攝空間和相機視角局限性的影響，導(dǎo)致單張圖像獲取信息有限，需要利用圖像拼接的方式獲得包含信息更加豐富圖像。圖像拼接主要分為基于頻域的拼接方法和基于時域的拼接方法兩類?；陬l域的拼接方法是通過傅里葉變換將圖像變換至頻域，然后根據(jù)圖像間的互功率譜求解出平移矢量，最后根據(jù)平移矢量實現(xiàn)圖像拼接2?；跁r域的拼接方法又分為基于灰度拼接和基于圖像特征點

2、拼接兩類方法，基于灰度的理論研究較早但實際應(yīng)用相對較少，主要是通過驗證圖像的灰度相關(guān)性來實現(xiàn)圖像拼接，該方法在解決圖像畸變大、不連續(xù)等問題時存在困難，因此，基于灰度的拼接方法難以獲得較好的拼接結(jié)果3；基于圖像特征點的拼接方法主要通過計算圖像特征點的位置關(guān)系求解出圖像的變換關(guān)系，再根據(jù)變換關(guān)系實現(xiàn)圖像拼接，該方法具有計算速度快、魯棒性強的優(yōu)勢，可以獲得較好的拼接結(jié)果4。目前，圖像拼接主要是基于特征點拼接實現(xiàn)的。常用的特征點提取方法有SIFT （Scale Invariant Feature Transform）5-6、SURF（Speeded Up Robust Features）7-8以及OR

3、B （Oriented FAST and Rotated BRIEF）9-10等方法。SIFT算法是由Lowe等人提出的，文獻11-12將該方法結(jié)合RANSAC13算法應(yīng)用在圖像拼接中，該算法對尺度縮放、旋轉(zhuǎn)、亮度變化保持不變性，對仿射變換、視角變化、噪聲也保持一定程度的穩(wěn)定性，但是因為使用多次的高斯卷積，使得其存在運算量較大，運行時間較長的缺點，尤其是在算力有限的嵌入式設(shè)備上很難滿足實時性。SURF算法是由Bay等人提出的，文獻3，14 將該方法分別結(jié)合PROSAC15算法和RANSAC算法應(yīng)用在圖像拼接中。SURF算法是SIFT算法的一種改進，它使用盒狀濾波器代替高斯卷積，再配合上積分圖像

4、，大幅減小了特征點的提取時間，但其檢測到的特征點比SIFT算法要多，因此其進行特征點匹配時相對耗時，依然存在運行時間較長的缺點，同樣無法較好地在算力有限的嵌入式設(shè)備上滿足實時性。ORB算法是由Rublee等人提出的，文獻4將該方法結(jié)合RANSAC算法應(yīng)用在圖像拼接中。該算法是一種較為簡單的利用二進制特征描述符進行特征點提取的算法，其顯著特點是速度超快，具有旋轉(zhuǎn)不變性，在一定程度上不受噪聲和圖像變換的影響，雖然在算力較低的嵌入式設(shè)備上滿足實時性，但存在不具備尺度不變性且特征點匹配準確率較低的問題。為了解決這些問題，本文提出了一種基于BRISK和改進RANSAC算法的方法來實現(xiàn)圖像拼接。首先，針對

5、特征點的檢測速度問題，本文使用BRISK（Binary Robust Invariant Scalable Keypoints）16算法進行特征點檢測。然后，為了在特征點精匹配中得到更多的特征點匹配對數(shù)，本文提出了一種基于RANSAC算法的改進算法：（1）先隨機地從粗匹配點對中選擇4個點對計算單應(yīng)性矩陣H，再根據(jù)單應(yīng)性矩陣H計算統(tǒng)計出內(nèi)點數(shù)，再根據(jù)內(nèi)點擬合出新的單應(yīng)性矩陣，以此循環(huán)，直至內(nèi)點的個數(shù)不再增加為循環(huán)的結(jié)束，將此操作執(zhí)行多次，內(nèi)點數(shù)最大所對應(yīng)的單應(yīng)性矩陣為最終結(jié)果；（2）對RANSAC的內(nèi)點將歐氏距離判斷改成面積判斷。實驗結(jié)果證明，本文提出的方法可以縮短特征點檢測的運行時間且得到更多

6、的內(nèi)點數(shù)，從而提高準確度。2 實驗原理圖像拼接的原理為找到兩幅圖像中相對應(yīng)的位置，然后經(jīng)過對待拼接圖像的投影變換，將兩幅圖像置于同一圖像坐標系中，從而完成圖像拼接。本文中尋找對應(yīng)位置使用到BRISK算法；投影變換關(guān)系需使用單應(yīng)性矩陣表示。2.1特征檢測算法BRISKBRISK算法是由Stefan等人提出的，該方法和SURF算法、SIFT算法一樣，具有尺度不變性和旋轉(zhuǎn)不變性，但運行速度優(yōu)于SURF算法、SIFT算法。該方法在運行速度上的優(yōu)勢，主要歸結(jié)于采用基于FAST方法進行特征點檢測和使用類似于BRIEF方法的二值位字符串描述符。BRISK方法構(gòu)建了由n 個組層和 n 個組間層組成的尺度空間金

7、字塔（n值一般為4），這樣保證了BRISK方法的尺度不變性。若用t表示圖像的尺度，則各層的尺度公式可由式（1）表示：t(ci)=2i,t(di)=2i1.5（1）式中：ci 表示第i個組層，di 為第i個組間層，i = 0，1，n-1。BRISK方法先使用FAST9-1617方法和FAST5-818方法進行特征點提取，然后對特征點的得分值在相鄰的兩個尺度空間上進行非極大值抑制，其中得分值為角點響應(yīng)值。最后，再使用最小二乘法結(jié)合得分值擬合得到特征點的亞像素坐標以及對應(yīng)的尺度。BRISK方法的特征點描述符創(chuàng)建是以特征點為中心，圍繞特征點有4個同心圓，每個同心圓的圓周上分布著數(shù)量不同的采樣像素，從內(nèi)

8、而外分別為10，14，15，20，加上特征點一共是60個采樣點，將這60個采樣點兩兩進行組合，可得到1 770個組合。所對應(yīng)的數(shù)學(xué)表示形式見式（2）：A=(Pi,Pj)R2R2iN,ji,N=60（2）式中，R2代表二元組，Pi、Pj為60個采樣點中的一個。在BRISK中，根據(jù)采樣點間的距離長短，從A中取出集合S和L。S和L的定義見式（3）：S=(Pi,Pj)Adi,js,L=(Pi,Pj)Adi,jL,di,j=pipj=(xixj)2+(yiyj)2（3）式中，Pi的坐標為(xi,yi)，Pj的坐標為(xj,yj)，S=9.75t，L=13.67t，t表示尺度。集合L用于構(gòu)建特征點的角度屬

9、性。設(shè)(Pi,Pj)L，則這兩個采樣像素的局部梯度x,y可由式（4）表示：x=(xixj)(I(pi,i)I(pj,j)d2i,jy=(yiyj)(I(pi,i)I(pj,j)d2i,j（4）式中：Pi的坐標為(xi,yi)，Pj的坐標為(xj,yj)，I(pi,i)為采樣像素Pi高斯平滑后的灰度值，I(pj,j)為采樣像素Pj高斯平滑后的灰度值，i、j為高斯平滑時使用的標準差。令gx=1lLx,gy=1lLy,（5）則特征點的角度可由式（6）表示：=arctan(gygx)（6）集合S用于構(gòu)建特征點的描述符，BRISK算法的描述符是基于二值位字符串形成的，字符串的每一位b見式（7）：b=1,

10、0,I(pj,j)I(pi,i)其他（7）式中，pj和pi為經(jīng)過旋轉(zhuǎn)以后的采樣模板中集合S中的一對采樣點，這樣保證了旋轉(zhuǎn)不變性。2.2單應(yīng)性矩陣的求解單應(yīng)性矩陣H 為一個33的矩陣19。設(shè)H=h1h4h7h2h5h8h3h6h9（8）則有xbybwb=h1h4h7h2h5h8h3h6h9xayawa（9）xbwb=h1xa+h2ya+h3wah7xa+h8ya+h9wa=h1xawa+h2yawa+h3h7xawa+h8yawa+h9（10）ybwb=h4xa+h5ya+h6wah7xa+h8ya+h9wa=h4xawa+h5yawa+h6h7xawa+h8yawa+h9（11）令ua=xaw

11、a,va=yawa,ub=xbwb,vb=ybwb（12）則b=h1ua+h2va+h3h7ua+h8va+h9vb=h4ua+h5va+h6h7ua+h8va+h9（13）在單應(yīng)性矩陣H中，h9 是尺度，且恒為1，故共有8個未知數(shù)。由上述式（8）（13）知，一對映射點對可推導(dǎo)出兩個等式，則至少需要4對點就可以解出單應(yīng)性矩陣H。換言之，要將一副圖像投影變換為另一幅圖像，至少需要知道投影變換前后4對點的映射關(guān)系。在計算單應(yīng)性矩陣H時，如果已知的映射點對只有4對時，可通過上述公式直接求解出H的值；但當對應(yīng)點超過4對時，可使用最小二乘法，使得反向投影錯誤率的值最小，來擬合求解單應(yīng)性矩陣H，反向投影錯

12、誤率的求解過程見式（14）：f=i(xih1xi+h2yi+h3h7xi+h8yi+h9)2+(yih4xi+h5yi+h6h7xi+h8yi+h9)2（14）式中：h1h9為對應(yīng)的單應(yīng)性矩陣H的9個值，xi、yi為變換后的特征點坐標值，xi為橫坐標，yi為縱坐標。xi、yi為變換前的特征點坐標值，xi為橫坐標，yi為縱坐標。2.3加權(quán)融合由于輸入的兩幅圖像存在亮度等方面的差異，在完成圖像拼接后，新生成的圖像會存在明顯的拼接痕跡，影響視覺直觀效果，需要采用加權(quán)平滑算法來實現(xiàn)兩幅圖像間的融合過渡。融合方法見公式（15）：f(x,y)=f1(x,y),d1f1(x,y)+d2f2(x,y),f2(

13、x,y),(x,y)R1(x,y)R2(x,y)R3（15）式中：R1、R3表示兩幅圖像的非重合區(qū)域，R2為兩幅圖像的重合區(qū)域，f1(x,y)、f2(x,y)為兩幅圖像(x,y)處的灰度值，d1、d2為加權(quán)系數(shù)且d1+d2=1。3 基于RANSAC算法的改進3.1傳統(tǒng)的RANSAC算法RANSAC算法的主要作用是剔除掉特征點錯誤匹配對，算法所對應(yīng)的流程圖如圖1（a）所示。其主要步驟為：圖1改進前后的RANSAC算法Fig. 1RANSAC algorithm before and after improvement（1）從粗匹配結(jié)果中，隨機的選取4對非線性特征點匹配對組成集合M；（2）使用集合

14、M計算出單應(yīng)性矩陣H；（3）使用H對粗匹配結(jié)果中的所有匹配對進行驗證，統(tǒng)計內(nèi)點個數(shù)（內(nèi)點為小于預(yù)設(shè)閾值的匹配對）；（4）若當前內(nèi)點數(shù)大于當前最優(yōu)單應(yīng)性矩陣的內(nèi)點數(shù)，則對當前最優(yōu)單應(yīng)性矩陣進行更新，反之，不更新；（5）根據(jù)當前最優(yōu)單應(yīng)性矩陣的內(nèi)點數(shù)更新迭代總次數(shù)，若當前迭代次數(shù)小于總迭代次數(shù)，返回執(zhí)行步驟（1），反之，則當前最優(yōu)單應(yīng)性矩陣為最終結(jié)果。3.2改進的RANSAC算法根據(jù)上述的RANSAC算法可知，在粗匹配的結(jié)果中匹配到的內(nèi)點數(shù)越多，則認為當前模型越好，所以可以通過循環(huán)增大集合M，使其可以擬合更多的匹配點對，從而使得最終結(jié)果可以計算到更多的匹配對，故將算法做以下改進， 算法所對應(yīng)的流程

15、圖如圖1（b）所示。（1）從粗匹配結(jié)果中，隨機的選取4對非線性特征點匹配對組成集合M；（2）使用集合M計算出單應(yīng)性矩陣H；（3）使用H對粗匹配結(jié)果中的所有匹配對進行驗證，將內(nèi)點加入到集合M中；（4）若集合M的點對數(shù)增加，則返回步驟（2）繼續(xù)執(zhí)行；若集合M保持不變，則執(zhí)行步驟（5）；（5）若集合M的點對數(shù)大于當前最優(yōu)單應(yīng)性矩陣的點對數(shù)，則對當前最優(yōu)單應(yīng)性矩陣進行更新，反之，不更新；（6）根據(jù)當前最優(yōu)單應(yīng)性矩陣的內(nèi)點數(shù)更新迭代總次數(shù)，若當前迭代次數(shù)小于總迭代次數(shù)，返回執(zhí)行步驟（1），反之，則當前最優(yōu)單應(yīng)性矩陣為最終結(jié)果。3.3RANSAC算法中閾值的選擇在RANSAC算法中，判斷一個匹配對是否為內(nèi)

16、點（正確匹配對）的依據(jù)是：像素點（X，Y）經(jīng)過單應(yīng)性矩陣H投影變換得到的值與實際值的差應(yīng)小于等于閾值。當閾值取到足夠大，接近無窮，那么此時任意選擇的4個初值所求出來的結(jié)果都將使匹配對滿足情況，均被置成內(nèi)點，無法達到將錯誤匹配對剔除的目的，從而導(dǎo)致最終拼接效果不佳。當閾值取到足夠小，甚至是等于0時，則此時將會使絕大部分匹配對都不滿足情況，滿足情況的匹配對將會變得寥寥無幾，并且將大部分正確匹配對剔除，使得最終內(nèi)點結(jié)果占實際正確匹配對的比例太低，得到的內(nèi)點將無法代表整體正確匹配對，使得結(jié)果的偶然性增大，導(dǎo)致拼接效果不佳。當閾值取到合適值時，此時錯誤匹配對將會被剔除，正確匹配對被置成內(nèi)點保留，且內(nèi)點結(jié)

17、果占實際正確匹配對的比例較高，可用得到的內(nèi)點代表整體正確匹配對，使得最終效果更佳。為了提高單應(yīng)性矩陣的準確度，必須選擇合適的閾值。由于在特征點檢測BRISK算法中得到的特征點的像數(shù)值是近似值而非精確值，所以此時就必須允許誤差的存在。雖然得到的像數(shù)值是近似值，但由BRISK算法可知，該近似值與精確值的差距在一個像素之內(nèi)，故將閾值設(shè)置為1，且需將原內(nèi)點判定方法由歐式距離改為面積判斷，即將式（16）：d2x+d2y=1（16）改成式（17）：|dx|=1|dy|=1（17）其中：dx 為實際值與計算值的橫坐標差，dy 為實際值與計算值的縱坐標差。4 實驗方案與分析實驗在Python3.7 和 Ope

18、ncv3.4.5 下完成，硬件環(huán)境為：Windows10操作系統(tǒng)，主頻 2.20 GHz 的 Core i7-8750H 處理器、 內(nèi)存為 8 GB 的筆記本電腦。本文共設(shè)計了3組實驗：實驗一用于驗證BRISK算法相對于SURF算法、SIFT算法以及ORB算法在特征點檢測時間以及特征點匹配準確率上的優(yōu)勢；實驗二用于驗證本文改進的RANSAC算法相對于傳統(tǒng)RANSAC算法以及PROSAC算法在特征點匹配對和平均反向投影誤差上的優(yōu)勢；實驗三用于驗證本文所使用的算法相對于其他常用算法的整體執(zhí)行時間優(yōu)勢。4.1實驗數(shù)據(jù)本文的實驗數(shù)據(jù)來源包括兩部分：自主拍攝和網(wǎng)上收集。實驗數(shù)據(jù)共有18幅圖像，分為9組，

19、內(nèi)容包括人物、樓宇、道路、自然風景等。4.2實驗流程首先讀入一組圖像，對圖像使用BRISK算法進行特征點提取，對得到的特征點使用KNNmatch進行初始匹配，由于粗匹配的結(jié)果中依然含有錯誤匹配對，無法直接使用最小二乘法來計算單應(yīng)性矩陣H，因此還需將匹配結(jié)果通過RANSAC算法進行錯誤匹配對剔除，再將精匹配結(jié)果使用最小二乘法求得單應(yīng)性矩陣H，最后根據(jù)求得的矩陣H對圖像 進行轉(zhuǎn)換拼接融合。流程圖如圖2所示。圖2實驗流程Fig. 2Experimental process4.3匹配精度評價指標4.3.1特征點的正確匹配對的數(shù)量使用RANSAC算法進行特征點錯誤匹配對剔除時，不僅會剔除掉錯誤的匹配對，

20、同時也會將部分正確的匹配對進行剔除，尤其是在閾值要求嚴格的情況下，更容易將正確的匹配對進行誤剔除。即在計算單應(yīng)性矩陣H時，使用到的正確匹配對是整體的一部分，這一部分正確匹配對的數(shù)量越大，越可以代表整體正確匹配對，所以相對保留的正確匹配對越多越好。所以在閾值要求嚴格的情況下，特征點的正確匹配對數(shù)量越多，得到的單應(yīng)性矩陣H越準確。4.3.2平均反向投影錯誤率平均反向投影錯誤率可用來評估算法的匹配精度。平均反向投影錯誤率的計算式見式（18）：K=1ni(xih1xi+h2yi+h3h7xi+h8yi+h9)2+(yih4xi+h5yi+h6h7xi+h8yi+h9)2（18）式中：K為平均反向投影錯

21、誤率，n為精匹配的正確匹配對的總數(shù)，h1h9為對應(yīng)的單應(yīng)性矩陣H的9個值，xi、yi為變換后的特征點坐標值。xi、yi為變換前的特征點坐標值。顯然，平均反向投影錯誤率越小，單應(yīng)性矩陣H的結(jié)果越精確。4.4實驗結(jié)果分析4.4.1實驗一該實驗的設(shè)計目的為驗證BRISK算法相對于SURF算法、SIFT算法以及ORB算法的優(yōu)勢。實驗結(jié)果如圖3、圖4所示。圖3各算法提取特征點的時間對比Fig. 3Time comparison of feature points extracted by each algorithm圖4各算法的特征點匹配準確率Fig. 4Matching accuracy of eac

22、h keypoint detection algorithm圖3的折線圖是由BRISK算法、SURF算法、SIFT算法以及ORB算法對圖像進行特征點檢測所需時間的比較，各種算法的運行時間為10次執(zhí)行時間取平均值為結(jié)果。由圖3的各種特征點檢測算法的時間對比結(jié)果可以發(fā)現(xiàn)，ORB算法的執(zhí)行時間最少，BRISK算法的執(zhí)行時間低于SURF算法、SIFT算法，為次優(yōu)結(jié)果。圖4的柱狀圖是由BRISK算法、SURF算法、SIFT算法以及ORB算法對圖像進行特征點匹配后，得到的特征點匹配準確率，其中特征點匹配準確率為經(jīng)過RANSAC算法得到的匹配對個數(shù)除以粗匹配對個數(shù)。由圖4可知，在當前閾值下，ORB算法的匹配

23、準確率最低，尤其在第2、8組數(shù)據(jù)上，匹配準確率僅有0.02；BRISK算法的匹配準確率在各組數(shù)據(jù)上均優(yōu)于SURF算法、ORB算法，在第3、4、7組數(shù)據(jù)上優(yōu)于SIFT算法。由圖3、圖4可知，雖然BRISK算法的執(zhí)行時間稍弱于ORB算法，但其在匹配準確率上有著更為優(yōu)秀的結(jié)果。BRISK算法在執(zhí)行時間和匹配準確率上均優(yōu)于SURF算法。與SIFT算法相比，BRISK算法雖然只有3組數(shù)據(jù)在匹配準確率上占優(yōu)勢，但是在執(zhí)行時間上各組數(shù)據(jù)均優(yōu)于SIFT算法，總體上可認為BRISK算法優(yōu)于SIFT算法。綜上，在當前閾值下，BRISK算法相對于SURF算法、SIFT算法以及ORB算法具有明顯的優(yōu)勢。4.4.2實驗

24、二該實驗的設(shè)計目的為驗證本文改進的RANSAC算法相對于傳統(tǒng)RANSAC算法以及PROSAC算法的優(yōu)勢，實驗結(jié)果如圖5和表1所示。圖5特征點的正確匹配對數(shù)目的比較結(jié)果Fig. 5Comparison of the number of correct matching pairs of keypoints表1平均反向投影錯誤率的比較結(jié)果Tab.1Comparison of the average back-projection error rate組數(shù)傳統(tǒng)的RANSAC算法改進后的RANSAC算法PROSAC算法10.6040.5270.56620.4760.4280.45830.5300.49

25、30.51140.3330.3330.33350.4910.4590.49360.5530.5100.62570.5840.5361.02380.5340.5260.56590.7250.5900.940圖5柱狀圖是經(jīng)過剔除錯誤匹配對算法后保留的特征點最終匹配對數(shù)。粗匹配為經(jīng)過KNNmatch匹配算法得到的匹配結(jié)果，傳統(tǒng)的RANSAC算法、改進的RANSAC算法、PROSAC算法分別為將粗匹配結(jié)果經(jīng)過對應(yīng)的算法得到的最終正確匹配對個數(shù)。從圖5中數(shù)據(jù)可以發(fā)現(xiàn)，在每一組中，都剔除掉了大量的錯誤匹配對，但改進后的RANSAC算法所保留的正確匹配對的個數(shù)大于傳統(tǒng)的RANSAC算法的結(jié)果，也大于PROS

26、AC算法的結(jié)果。表1是經(jīng)過剔除錯誤匹配對算法后計算得到單應(yīng)性矩陣H，再利用其求得平均反向投影錯誤率的結(jié)果，傳統(tǒng)的RANSAC算法、改進的RANSAC算法、PROSAC算法分別為經(jīng)過對應(yīng)算法求得的平均反向投影錯誤率。從表1中數(shù)據(jù)可以發(fā)現(xiàn)，在每一組中，改進后的RANSAC算法得到的平均反向投影錯誤率小于傳統(tǒng)的RANSAC算法，同時也小于PROSAC算法的結(jié)果。由實驗數(shù)據(jù)可知：相對于傳統(tǒng)的RANSAN算法，本文改進的RANSAC算法在平均反向投影錯誤率減少了約10%。如圖5、表1所示，改進的RANSAC算法的在特征點的正確匹配對數(shù)目和平均反向投影錯誤率上都具有優(yōu)越性。以圖像組數(shù)1為例，其對應(yīng)的圖像處

27、理過程如圖6所示。圖6圖像拼接比較Fig. 6Image mosaicing comparison由圖6（d）可以發(fā)現(xiàn)，經(jīng)過特征點粗匹配后，匹配結(jié)果中存在部分錯誤匹配對；圖6（e）、（f）、（g）分別為粗匹配結(jié)果使用改進后的RANSAC算法、傳統(tǒng)的RANSAC算法以及PROSAC算法進行剔除后的結(jié)果，括號內(nèi)的數(shù)值為匹配對個數(shù)?？梢园l(fā)現(xiàn)，改進后的RANSAC算法得到的結(jié)果均為正確匹配對，且數(shù)量上優(yōu)于傳統(tǒng)的RANSAC算法和PROSAC算法；由圖6（c）可知，最終得到的拼接結(jié)果過渡較為自然，無明顯接縫。4.4.3實驗三為了驗證本文算法在時間方面的有效性，本實驗將本文所用方法與較為常用的SIFT+RANSAC方法、SIFT+PROSAC方法、SURF+RANSAC方法、SURF+PROSAC方法進行圖像拼接的整體時間比較，整體時間主要包括特征點檢測時間、特征點粗匹配時間、精匹配時間以及圖像投影變換時間。實驗結(jié)果如表2所示，其中各拼接方法執(zhí)行時間為10次執(zhí)行時間取平均值的結(jié)果。表2各拼接方法執(zhí)行時間比較Tab.2Compariso