基于 ORB 與 K-means 聚類的圖像匹配算法

邢藝馨， 田愛奎， 張立曄， 常春紅， 郝本利

(山東理工大學 計算機科學與技術學院, 山東 淄博 255000)

0 引 言

目前，計算機視覺領域技術的快速發展，使得雙目立體視覺在工業機器人、生物醫學、虛擬現實以及軍事等領域應用前景廣泛，其圖像匹配精度和速度一直備受關注。對此，經典算法的提出更是推動了該領域的發展。David G.Lowe 提出的SIFT(Scale Invariant Feature Transform，初度不變特征變換)算法所提取的特征點穩定性高，同時具有尺度不變性和旋轉不變性的特點，可獲取更多信息量，但同時有存在匹配時間較長的缺點[1]。隨后，作為SIFT算法的優化算法——SURF(Speed Up Robust Feature)被提出，其利用了快速的Hessian矩陣檢測關鍵點，缺點是魯棒性降低[2]。2011年，Rublee[3]等對上述二種算法進行研究改進，提出了經典的ORB(Oriented FAST and Rotated BRIEF)算法，該算法的優點是匹配速度快，同時對噪聲敏感的缺點也相當明顯，匹配精度也因此降低。傳統的ORB算法沒有充分解決尺度不變性的問題，針對此問題，戴雪梅[4]等結合SURF算法的尺度不變的特征，對ORB算法進行了改進，得到一種全新的SURF-ORB(簡稱SURB)算法，其保留了ORB算法的速度優勢，又有效地避免了ORB算法不具備尺度不變性的缺陷，提高了算法運行效率。2020年，文永革[5]等提出了結合SIFT算法與K-means聚類算法的圖像匹配優化算法，提升了圖像特征的算法效率，并且實現了在同等距離比率下，圖像特征匹配精度的提升。文獻[6]提出了一種大規模的對象檢測系統，用戶可通過選擇查詢圖像的區域來提供查詢對象。并且大型語料庫中檢索包含相同對象的圖像的排序列表在系統中返回，會出現忽略圖像的語義部分的情況。文獻[7]中，通過對局部空間進行網格結構均分的方式得到視覺詞匯表，缺點與文獻[6]相似，問題仍未得到解決。文獻[8]提出，通過比較各興趣點局部澤尼克矩的歐氏距離，來提取最優匹配點后，以興趣點的空間離散度計算圖像匹配性。文獻[9] 對K-means聚類算法進行改進研究，在基于主成分分析的K-means初始聚類中心優化算法的基礎上，提出一種全新的基于潛在穩定性的K-means最佳聚類數確定方法，解決了聚類分析的初始聚類中心的選擇和聚類K值的問題。文獻[10]中，孫士寶等人在分析了孤立點和噪聲數據對 K-means 算法影響的基礎上，提出了一種基于加權的K-means 算法。文獻[11]中提出了基于半監督 K-均值聚類對 K 值進行全局尋優算法，解決了K-means 算法隨機選擇初始聚類中心的不足。

綜上所述，本文算法目的是對ORB算法進行改進。考慮到K-means算法具有優化迭代的特點，雙目視覺對尺度不變性要求較低，采用傳統ORB算法與K-means聚類算法相結合，通過亞像素插值法提升特征點坐標精確度。經多次圖像匹配實驗結果對比，驗證了本文算法對不同分辨率圖像的匹配精度有較穩定的提升，同時性能也優于傳統的圖像匹配算法。

1 ORB算法

作為高效的圖像匹配算法，ORB算法在特征匹配和抑制圖像噪聲兩方面性能都可代替SIFT算法，其算法的速度優勢更適用于實時系統中。在傳統ORB 特征檢測算法中，首先建立特征點的特征描述向量，依據FAST子檢測圖像上符合條件的特征點，并根據灰度質心法計算主方向；其次，根據Rotated BRIEF(Binary Robust Independent Elementary Features，二元魯棒獨立基本特征)描述算法，生成特征點的特征向量；最后，通過計算模板圖像特征向量和待搜索圖像特征向量的漢明距離(Hamming Distance)，來確定各個特征向量的相似度。

1.1 關鍵點檢測——FAST算法

判斷一個像素點是否為關鍵點，檢測方法是判斷該點灰度值與周圍鄰域內大部分的像素點進行對比，若相差過大則該像素可能是角點(特征點)。為判斷特征點是否角點，先假定該特征點為點P，通過以點P為中心，半徑為3個像素作圓，并使該圓過16個像素點。判斷在圓周上的16個像素點中，是否最少有連續的n個像素點滿足都比Ip+t大，或都比Ip-t小的情況。如果實際數據滿足公式(1)，則可以確定P是一個特征點，否則P不是特征點。

(1)

式中，Ip表示點P的灰度值；t表示閾值；I(x)表示圓周上任意像素點的灰度值；I(p)表示圓心的灰度值；εd表示給定的灰度差值(閾值)。若N值超過設定的閾值(一般取值為周圍圓圈點的3/4)，則認為P點是一個特征點。

1.2 特征點匹配——BRIEF算子

得到特征點后，需要對這些特征點的屬性進行描述。屬性的輸出稱為該特征點的描述子(Feature DescritorS)。ORB算法使用BRIEF算子進行一個特征點描述子的計算。BRIEF特征提取思路是：在關鍵點附近以一定模式隨機選取適量點對，將這些點對的灰度值大小進行比較，結果組合起來成為二進制串，此二進制串作為角點的描述子。算法操作流程如下：

Step1以關鍵點P為圓心且以d為半徑做圓O。

Step2在圓O內某一模式選取N個點對(實際應用中可取到512)。

Step3定義操作T

式中：IA表示點A的灰度。

Step4分別對已選取的點對進行T操作，將得到的結果進行整合。

BRIEF使用二進制編碼的方法，在特征點周圍的一定區域內提取描述子。因提取的描述子簡單，所以相較于SIFT、SURF算法存儲空間更小，因使用漢明距離進行對比，匹配速度也比SIFT算法更快。

2 K-means聚類算法

K-means聚類分析算法有簡捷易懂、適應性強、高效聚類的優點，是目前普遍運用的一種聚類分析算法。根據已知關鍵點特征向量間的歐氏距離，運用 K-means 聚類分析算法對這些特征向量進行聚類，選取與其余向量差別最小的特征向量作為初始質心的方式，可以優化ORB特征點，簡化計算維度。K-means聚類算法是通過迭代方式求解，具體算法流程如下：

Step1將已知數據分為K組，再隨機地選取K個對象來作為初始質心(聚類中心)。

Step2計算每個對象與各個已知聚類中心之間的歐氏距離，再把這個對象歸類給距離最近的聚類。

Step3分配給聚類中心的對象和聚類中心就組成了一個聚類。每次新分配一個樣本，根據現聚類中存在的對象，再次計算出聚類的新質心。

以上過程將持續循環，直到滿足某個終止條件后結束。若直到沒有對象或最小數目對象被重新分配給了不同的聚類，導致聚類中心再次發生變化，實現誤差平方和局部最小的條件后，迭代求解的聚類分析算法將不再重復。

K-means聚類算法中，初始聚類中心的選取與聚類數目K的確定，是兩個不容忽視的問題。初始聚類中心的選取可采用基于主成分分析(Principal Components Analysis，PCA)的方式；聚類數K的問題，可通過基于潛在穩定性的K-means最佳聚類數確定方法進行確定。

ORB算法識別到關鍵點的坐標信息及描述子后，通過對關鍵點keypoint的坐標進行聚類，在K-means算法中的K值取值為2，即得到優化后的算法。

3 實驗結果分析

為驗證本研究算法的有效性，首先對雙目圖像公開數據集進行大量實驗后，再采用CCD相機拍攝實驗室圖像進行測試。實驗的CPU型號為i7-9600K，采用Python語言實現本研究中的相關算法，進行圖像匹配。通過將本文提出的算法與傳統ORB算法、SIFT算法的匹配效果進行對比，驗證本算法的可行性。通過K-means聚類算法改進后的算法相較于傳統ORB算法剔除誤匹配效果較為明顯，同時具有時間優越性。

通過兩種算法對雙目圖片匹配結果可以看出，ORB與K-means算法結合后的算法性能，得到了一定程度的提升，即本文提出的算法在對雙目圖像進行特征點進行匹配時，圖片中特征點匹配準確度有明顯提高，OpenCV中的ORB算法具有一定程度的尺度不變性。通過圖1與圖2對公開雙目圖片數據集進行圖像匹配的實驗結果對比可見，在公開數據集上進行本文算法實驗性能良好；圖3是使用CCD相機拍攝圖進行圖像匹配，由圖可見，采用K-means聚類算法匹配結果，剔除了傳統ORB算法匹配結果中的誤匹配。通過兩種算法的匹配圖對比可知，結合了K-means算法的ORB算法正確率得到了明顯提高。

(a) SIFT算法匹配結果

(b) ORB算法與改進后算法的匹配結果

(a) SIFT算法匹配結果

(b) ORB算法與改進后算法的匹配結果

(a) SIFT算法匹配結果

(b) 拍攝的雙目圖片算法對比結果

圖像匹配算法的耗時和匹配識別個數的對比結果見表1、表2。

表1 圖像匹配算法耗時對比

表2 圖像匹配算法識別個數對比

由表1中可以看出，SIFT算法的運行時間相比傳統ORB算法長，ORB算法的實時性優勢遠超SIFT算法。本文算法在傳統ORB算法上疊加了K-means聚類算法，雖然本文算法比傳統ORB算法耗時長，但運行速度遠遠小于SIFT匹配算法，速度方面達到預期效果。

表2為3種算法圖像匹配識別的特征對數目的對比。通過對表格數據分析可知，本文算法消除了傳統ORB算法中一些匹配錯誤的點，從而提高了匹配正確率。

ORB算法與K-means算法的結合，在運行時長和匹配正確率上都有很好的表現，具有魯棒性。結合后的算法雖然增加了一些時間開銷，但整體上對算法的實時性驗證并無明顯影響。

4 結束語

本文提出利用ORB算法進行雙目圖像匹配，使用K-means聚類的圖像匹配算法，具有魯棒性強的優點，耗時相比于ORB算法有一定增加，但實時性相較于SIFT算法仍有明顯優勢。由于ORB算法不具有尺度不變性，在對具有尺度變換較大的圖片處理時，本文算法則需要改進。因實驗為雙目測距環境，雙目匹配對尺度不變形要求較低，而對實時性要求較高，故采用改進的ORB算法在OpenCV中的尺度變換特征下進行匹配，可以達到預期效果。