杜 港，侯凌燕，佟 強，楊大利

（北京信息科技大學 計算機學院，北京 100101）

1 引 言

圖像拼接是圖像處理的一個重要領域，指的是將兩張或多張有重疊像素的圖像經(jīng)過一系列操作組成一張廣角圖像［1］，目前廣泛應用于遙感影像配準、計算機視覺、醫(yī)學圖像處理、視覺SLAM 以及嵌入式設備等領域，如相機在拍攝時由于拍攝空間和相機視角局限性的影響，導致單張圖像獲取信息有限，需要利用圖像拼接的方式獲得包含信息更加豐富圖像。圖像拼接主要分為基于頻域的拼接方法和基于時域的拼接方法兩類?；陬l域的拼接方法是通過傅里葉變換將圖像變換至頻域，然后根據(jù)圖像間的互功率譜求解出平移矢量，最后根據(jù)平移矢量實現(xiàn)圖像拼接［2］?；跁r域的拼接方法又分為基于灰度拼接和基于圖像特征點拼接兩類方法，基于灰度的理論研究較早但實際應用相對較少，主要是通過驗證圖像的灰度相關(guān)性來實現(xiàn)圖像拼接，該方法在解決圖像畸變大、不連續(xù)等問題時存在困難，因此，基于灰度的拼接方法難以獲得較好的拼接結(jié)果［3］；基于圖像特征點的拼接方法主要通過計算圖像特征點的位置關(guān)系求解出圖像的變換關(guān)系，再根據(jù)變換關(guān)系實現(xiàn)圖像拼接，該方法具有計算速度快、魯棒性強的優(yōu)勢，可以獲得較好的拼接結(jié)果［4］。目前，圖像拼接主要是基于特征點拼接實現(xiàn)的。

常用的特征點提取方法有SIFT（Scale In?variant Feature Transform）［5-6］、SURF（Speeded Up Robust Features）［7-8］以 及ORB（Oriented FAST and Rotated BRIEF）［9-10］等方法。SIFT 算法是由Lowe 等人提出的，文獻［11-12］將該方法結(jié)合RANSAC［13］算法應用在圖像拼接中，該算法對尺度縮放、旋轉(zhuǎn)、亮度變化保持不變性，對仿射變換、視角變化、噪聲也保持一定程度的穩(wěn)定性，但是因為使用多次的高斯卷積，使得其存在運算量較大，運行時間較長的缺點，尤其是在算力有限的嵌入式設備上很難滿足實時性。SURF 算法是由Bay 等人提出的，文獻［3，14］將該方法分別結(jié) 合PROSAC［15］算 法 和RANSAC 算 法 應 用 在圖像拼接中。SURF 算法是SIFT 算法的一種改進，它使用盒狀濾波器代替高斯卷積，再配合上積分圖像，大幅減小了特征點的提取時間，但其檢測到的特征點比SIFT 算法要多，因此其進行特征點匹配時相對耗時，依然存在運行時間較長的缺點，同樣無法較好地在算力有限的嵌入式設備上滿足實時性。ORB 算法是由Rublee 等人提出的，文獻［4］將該方法結(jié)合RANSAC 算法應用在圖像拼接中。該算法是一種較為簡單的利用二進制特征描述符進行特征點提取的算法，其顯著特點是速度超快，具有旋轉(zhuǎn)不變性，在一定程度上不受噪聲和圖像變換的影響，雖然在算力較低的嵌入式設備上滿足實時性，但存在不具備尺度不變性且特征點匹配準確率較低的問題。

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

2 實驗原理

圖像拼接的原理為找到兩幅圖像中相對應的位置，然后經(jīng)過對待拼接圖像的投影變換，將兩幅圖像置于同一圖像坐標系中，從而完成圖像拼接。本文中尋找對應位置使用到BRISK 算法；投影變換關(guān)系需使用單應性矩陣表示。

2.1 特征檢測算法BRISK

BRISK 算法是由Stefan 等人提出的，該方法和SURF 算法、SIFT 算法一樣，具有尺度不變性和旋轉(zhuǎn)不變性，但運行速度優(yōu)于SURF 算法、SIFT 算法。該方法在運行速度上的優(yōu)勢，主要歸結(jié)于采用基于FAST 方法進行特征點檢測和使用類似于BRIEF 方法的二值位字符串描述符。

BRISK 方法構(gòu)建了由n個組層和n個組間層組成的尺度空間金字塔（n值一般為4），這樣保證了BRISK 方法的尺度不變性。若用t表示圖像的尺度，則各層的尺度公式可由式（1）表示：

BRISK 方 法 先 使 用FAST9-16［17］方 法 和FAST5-8［18］方法進行特征點提取，然后對特征點的得分值在相鄰的兩個尺度空間上進行非極大值抑制，其中得分值為角點響應值。最后，再使用最小二乘法結(jié)合得分值擬合得到特征點的亞像素坐標以及對應的尺度。

BRISK 方法的特征點描述符創(chuàng)建是以特征點為中心，圍繞特征點有4 個同心圓，每個同心圓的圓周上分布著數(shù)量不同的采樣像素，從內(nèi)而外分別為10，14，15，20，加上特征點一共是60 個采樣點，將這60 個采樣點兩兩進行組合，可得到1 770 個組合。所對應的數(shù)學表示形式見式（2）：

A={(Pi，Pj)∈R2×R2∣i≤N，j

（2）式中，R2代表二元組，Pi、Pj為60 個采樣點中的一個。在BRISK 中，根據(jù)采樣點間的距離長短，從A中取出集合S和L。S和L的定義見式（3）：

2.2 單應性矩陣的求解

在單應性矩陣H中，h9是尺度，且恒為1，故共有8 個未知數(shù)。由上述式（8）～（13）知，一對映射點對可推導出兩個等式，則至少需要4 對點就可以解出單應性矩陣H。換言之，要將一副圖像投影變換為另一幅圖像，至少需要知道投影變換前后4 對點的映射關(guān)系。

在計算單應性矩陣H時，如果已知的映射點對只有4 對時，可通過上述公式直接求解出H的值；但當對應點超過4 對時，可使用最小二乘法，使得反向投影錯誤率的值最小，來擬合求解單應性矩陣H，反向投影錯誤率的求解過程見式（14）：

式中：h1……h(huán)9為對應的單應性矩陣H的9 個值，x'i、y'i為變換后的特征點坐標值，x'i為橫坐標，y'i為縱坐標。xi、yi為變換前的特征點坐標值，xi為橫坐標，yi為縱坐標。

2.3 加權(quán)融合

由于輸入的兩幅圖像存在亮度等方面的差異，在完成圖像拼接后，新生成的圖像會存在明顯的拼接痕跡，影響視覺直觀效果，需要采用加權(quán)平滑算法來實現(xiàn)兩幅圖像間的融合過渡。融合方法見公式（15）：

3 基于RANSAC 算法的改進

3.1 傳統(tǒng)的RANSAC 算法

RANSAC 算法的主要作用是剔除掉特征點錯誤匹配對，算法所對應的流程圖如圖1（a）所示。其主要步驟為：

圖1 改進前后的RANSAC 算法Fig. 1 RANSAC algorithm before and after improvement

（1）從粗匹配結(jié)果中，隨機的選取4 對非線性特征點匹配對組成集合M；

（2）使用集合M計算出單應性矩陣H；

（3）使用H對粗匹配結(jié)果中的所有匹配對進行驗證，統(tǒng)計內(nèi)點個數(shù)（內(nèi)點為小于預設閾值的匹配對）；

（4）若當前內(nèi)點數(shù)大于當前最優(yōu)單應性矩陣的內(nèi)點數(shù)，則對當前最優(yōu)單應性矩陣進行更新，反之，不更新；

（5）根據(jù)當前最優(yōu)單應性矩陣的內(nèi)點數(shù)更新迭代總次數(shù)，若當前迭代次數(shù)小于總迭代次數(shù)，返回執(zhí)行步驟（1），反之，則當前最優(yōu)單應性矩陣為最終結(jié)果。

3.2 改進的RANSAC 算法

根據(jù)上述的RANSAC 算法可知，在粗匹配的結(jié)果中匹配到的內(nèi)點數(shù)越多，則認為當前模型越好，所以可以通過循環(huán)增大集合M，使其可以擬合更多的匹配點對，從而使得最終結(jié)果可以計算到更多的匹配對，故將算法做以下改進，算法所對應的流程圖如圖1（b）所示。

（1）從粗匹配結(jié)果中，隨機的選取4 對非線性特征點匹配對組成集合M；

（2）使用集合M計算出單應性矩陣H；

（3）使用H對粗匹配結(jié)果中的所有匹配對進行驗證，將內(nèi)點加入到集合M中；

（4）若集合M的點對數(shù)增加，則返回步驟（2）繼續(xù)執(zhí)行；若集合M保持不變，則執(zhí)行步驟（5）；

（5）若集合M的點對數(shù)大于當前最優(yōu)單應性矩陣的點對數(shù)，則對當前最優(yōu)單應性矩陣進行更新，反之，不更新；

（6）根據(jù)當前最優(yōu)單應性矩陣的內(nèi)點數(shù)更新迭代總次數(shù)，若當前迭代次數(shù)小于總迭代次數(shù)，返回執(zhí)行步驟（1），反之，則當前最優(yōu)單應性矩陣為最終結(jié)果。

3.3 RANSAC 算法中閾值的選擇

在RANSAC 算法中，判斷一個匹配對是否為內(nèi)點（正確匹配對）的依據(jù)是：像素點（X，Y）經(jīng)過單應性矩陣H投影變換得到的值與實際值的差應小于等于閾值。

當閾值取到足夠大，接近無窮，那么此時任意選擇的4 個初值所求出來的結(jié)果都將使匹配對滿足情況，均被置成內(nèi)點，無法達到將錯誤匹配對剔除的目的，從而導致最終拼接效果不佳。

當閾值取到足夠小，甚至是等于0 時，則此時將會使絕大部分匹配對都不滿足情況，滿足情況的匹配對將會變得寥寥無幾，并且將大部分正確匹配對剔除，使得最終內(nèi)點結(jié)果占實際正確匹配對的比例太低，得到的內(nèi)點將無法代表整體正確匹配對，使得結(jié)果的偶然性增大，導致拼接效果不佳。

當閾值取到合適值時，此時錯誤匹配對將會被剔除，正確匹配對被置成內(nèi)點保留，且內(nèi)點結(jié)果占實際正確匹配對的比例較高，可用得到的內(nèi)點代表整體正確匹配對，使得最終效果更佳。

為了提高單應性矩陣的準確度，必須選擇合適的閾值。由于在特征點檢測BRISK 算法中得到的特征點的像數(shù)值是近似值而非精確值，所以此時就必須允許誤差的存在。雖然得到的像數(shù)值是近似值，但由BRISK 算法可知，該近似值與精確值的差距在一個像素之內(nèi)，故將閾值設置為1，且需將原內(nèi)點判定方法由歐式距離改為面積判斷，即將式（16）：

4 實驗方案與分析

實驗在Python3.7 和Opencv3.4.5 下完成，硬件環(huán)境為：Windows10操作系統(tǒng)，主頻2.20 GHz的Core i7-8750H 處理器、內(nèi)存為8 GB 的筆記本電腦。本文共設計了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 組，內(nèi)容包括人物、樓宇、道路、自然風景等。

4.2 實驗流程

首先讀入一組圖像，對圖像使用BRISK 算法進行特征點提取，對得到的特征點使用KNNmatch 進行初始匹配，由于粗匹配的結(jié)果中依然含有錯誤匹配對，無法直接使用最小二乘法來計算單應性矩陣H，因此還需將匹配結(jié)果通過RANSAC 算法進行錯誤匹配對剔除，再將精匹配結(jié)果使用最小二乘法求得單應性矩陣H，最后根據(jù)求得的矩陣H對圖像進行轉(zhuǎn)換拼接融合。流程圖如圖2 所示。

圖2 實驗流程Fig. 2 Experimental process

4.3 匹配精度評價指標

4.3.1 特征點的正確匹配對的數(shù)量

使用RANSAC 算法進行特征點錯誤匹配對剔除時，不僅會剔除掉錯誤的匹配對，同時也會將部分正確的匹配對進行剔除，尤其是在閾值要求嚴格的情況下，更容易將正確的匹配對進行誤剔除。即在計算單應性矩陣H時，使用到的正確匹配對是整體的一部分，這一部分正確匹配對的數(shù)量越大，越可以代表整體正確匹配對，所以相對保留的正確匹配對越多越好。所以在閾值要求嚴格的情況下，特征點的正確匹配對數(shù)量越多，得到的單應性矩陣H越準確。

4.3.2 平均反向投影錯誤率

平均反向投影錯誤率可用來評估算法的匹配精度。平均反向投影錯誤率的計算式見式（18）：

4.4 實驗結(jié)果分析

4.4.1 實驗一

該實驗的設計目的為驗證BRISK 算法相對于SURF 算 法、SIFT 算 法 以 及ORB 算 法 的 優(yōu)勢。實驗結(jié)果如圖3、圖4 所示。

圖3 各算法提取特征點的時間對比Fig. 3 Time comparison of feature points extracted by each algorithm

圖4 各算法的特征點匹配準確率Fig. 4 Matching accuracy of each keypoint detection al?gorithm

圖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 算法的匹配準確率最低，尤其在第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 實驗二

該實驗的設計目的為驗證本文改進的RANSAC 算法相對于傳統(tǒng)RANSAC 算法以及PROSAC 算法的優(yōu)勢，實驗結(jié)果如圖5 和表1所示。

圖5 特征點的正確匹配對數(shù)目的比較結(jié)果Fig. 5 Comparison of the number of correct matching pairs of keypoints

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

表1 是經(jīng)過剔除錯誤匹配對算法后計算得到單應性矩陣H，再利用其求得平均反向投影錯誤率的結(jié)果，傳統(tǒng)的RANSAC 算法、改進的RANSAC算法、PROSAC 算法分別為經(jīng)過對應算法求得的平均反向投影錯誤率。從表1 中數(shù)據(jù)可以發(fā)現(xiàn)，在每一組中，改進后的RANSAC 算法得到的平均反向投影錯誤率小于傳統(tǒng)的RANSAC 算法，同時也小于PROSAC 算法的結(jié)果。由實驗數(shù)據(jù)可知：相對于傳統(tǒng)的RANSAN 算法，本文改進的RANSAC 算法在平均反向投影錯誤率減少了約10%。

表1 平均反向投影錯誤率的比較結(jié)果Tab.1 Comparison of the average back-projection error rate

如圖5、表1 所示，改進的RANSAC 算法的在特征點的正確匹配對數(shù)目和平均反向投影錯誤率上都具有優(yōu)越性。以圖像組數(shù)1 為例，其對應的圖像處理過程如圖6 所示。

由圖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é)果過渡較為自然，無明顯接縫。

圖6 圖像拼接比較Fig. 6 Image mosaicing comparison

4.4.3 實驗三

為了驗證本文算法在時間方面的有效性，本實驗將本文所用方法與較為常用的SIFT+RANSAC 方法、SIFT+PROSAC 方法、SURF+RANSAC 方 法、SURF+PROSAC 方 法 進 行 圖像拼接的整體時間比較，整體時間主要包括特征點檢測時間、特征點粗匹配時間、精匹配時間以及圖像投影變換時間。實驗結(jié)果如表2 所示，其中各拼接方法執(zhí)行時間為10 次執(zhí)行時間取平均值的結(jié)果。

從表2 中數(shù)據(jù)可以發(fā)現(xiàn)，本文的圖像拼接方法的執(zhí)行時間優(yōu)于SIFT+RANSAC 方法、SIFT+PROSAC 方法、SURF+RANSAC 方法、SURF+PROSAC 方法。本文的圖像拼接方法的時間占比約為上述方法的50%，尤其是在第3 組和7 組數(shù)據(jù)上，執(zhí)行時間僅為其他算法的1/3，體現(xiàn)了本文方法的優(yōu)越性。

表2 各拼接方法執(zhí)行時間比較Tab.2 Comparison of execution time of each algorithm（ms）

5 結(jié) 論

針對圖像拼接的特征點檢測時間優(yōu)化和最終匹配對優(yōu)化問題，本文提出了一種圖像拼接方法。該方法先使用BRISK 算法進行特征點檢測，有效縮短了特征點檢測的運算時間；然后改進了RANSAC 錯誤匹配對剔除方法，使得在相同的條件下，可以得到的內(nèi)點數(shù)大于原RANSAC 算法，從而提高圖像拼接的準確度。實驗結(jié)果表明，BRISK 算法相對于SURF算法、SIFT 算法以及ORB 算法在特征點檢測時間以及特征點匹配準確率上具有優(yōu)勢；本文改進的RANSAC 算法使得內(nèi)點個數(shù)增加，平均反向投影錯誤率相對于原算法減小了10%左右；本文提出的拼接方法的執(zhí)行耗時約為常用的SIFT+RANSAC 方 法、SIFT+PROSAC 方 法、SURF+RANSAC 方法、SURF+PROSAC 方法的50%。本文提出的方法能夠?qū)崟r、準確地進行圖像拼接。

本文提出的算法主要針對于兩幅圖像的拼接，對于多幅圖像拼接問題還需要更多深入的研究，如多幅圖像拼接的圖像曝光補償?shù)葐栴}。