基于ORB特征點的多目標匹配

高建哲，呂文閣

0 引言

圖像匹配是機器視覺中一種常用的圖像處理和圖像分析技術。廣泛應用于軍事和民用生活領域，例如目標跟蹤、車輛監測、衛星導航、機器人控制以及工業檢測等。其主要方法有基于灰度值的匹配，基于輪廓邊緣的匹配以及基于特征點的匹配，這些年來基于特征點的圖像匹配方法已經成為國內外研究的熱點。其中David G.Lowe提出了SIFT算法[1]，Herbert Bay等人提出了SURF算法[2]，不同的圖像匹配算法在檢測關鍵點和提取描述向量時采用不同的方法，構造出的局部特征描述子就會具有不同的魯棒性，針對SIFT和SURF速度上的劣勢，ERublee等人在2011年提出來一種快速局部特征檢測算子ORB（oriented FAST and rotated BRIEF），該算子兼顧了SIFT和SURF的準確性和魯棒性，同時又有較快的速度[3]。

在目標識別中，有時圖像中存在待識別目標的多個相同或相似的副本，此時，不能夠直接地使用特征點匹配算法，而是需要先分離多目標，然后對單一目標做出估計。因為在求解模板到目標的仿射變換參數時，其他的目標特征點會被認為是誤匹配點，所以如何的分離這些特征點成為解決基于特征點的多目標匹配的關鍵。

對此，國內外的學者有著不同的研究，Lowe D等人利用Hough變換通過對特征點的可能的姿態進行投票分析，根據投票的峰值進行特征點的分類，但是計算繁瑣比較費時[4]。呂冀等人通過為所有的匹配點建立統一的超定線性方程組并對其簡化得到增廣矩陣，然后對增廣矩陣進行線性變換，從中提取多目標穩定的特征點，進而分離多目標特征點，但是魯棒性有所欠缺[5]。朱迪等人通過對模板中心點在目標圖像的估計，利用K-means進行中心點分類，進而分離多個目標，對于不確定目標個數的檢測具有一定的局限性[6]。

因此，本文提出了一種基于ORB特征點和采用基于特征點密度峰值的聚類分析方法［7］進行模板中心的自適應判斷，可以避免目標個數不確定時所帶來的的問題，同時實驗也驗證了算法的快速性，穩定性，具有一定的應用的價值。

1 ORB特征點匹配

1.1 ORB特征點檢測

ORB算子采用了FAST特征點和BRIEF描述子并加以改進。因為FAST特征點和BRIEF描述子均具有良好的魯棒性，所以ORB算子也具有良好的魯棒性。FAST特征點本身不具備旋轉不變性，在ORB的方案中，為了解決這個問題，ORB定義了鄰域矩如式(1)，通過矩計算來獲取特征點的鄰域的灰度強度質心，以特征點中心到灰度強度質心的方向作為FAST主方向。

其中，其中（x，y）是相對FAST特征點的位置，r為圓形鄰域半徑，一般取3或4，（x，y）∈ [-r，r]，I表示（x，y）坐標上圖片的灰度值，mpq稱為特征點（p+q）階矩(p，q=0，1，2，…)。至此得到了FAST角點圓形鄰域的強度中心點，其計算公式如下(2):

設特征點的中心為O，構造從特征點中心到灰度質心C的向量OC，作為特征點的方向，即FAST特征點的方向。因此，該角點的主方向角θ為式(3)：

這樣FAST改進成了Oriented-Fast。ORB在特征描述方面，采用BRIEF描述子，BRIEF是一種快速的二進制特征描述算子，BRIEF描述子通過在圖像上某點p的鄰域內的隨機選取n個點對，對于每一個點對可以形成一個二值測試τ來提取，其定義如式(4)。

其中，I（p，x）為p的鄰域內x點處的像素灰度值，I（p，y）為p的鄰域內y點處的像素灰度值，n一般取值為256，于是BRIEF特征描述子定義為如下式(5)。因此，BRIEF描述子本質上就是由這n個測試得到的n個字符組成的一個位字符串。

然而BREIF特征描述子在發生旋轉時無法保持穩定，因此，將角點的主方向作為描述子的主方向，從而取得對旋轉變化的魯棒性。原理如下：設(xi,yi)為任意的參與二值測試的點對，則所有的點對可以定義一個2×n的矩陣如下式(6)：

于是利用特征點的主方向為θ的旋轉矩陣Rθ就可以構造S的有向的形式Sθ=RθS。其中Rθ定義如下式(7)，θ為逆時針方向。因此得到了steered BRIEF為式(8)：

由此，ORB具有了旋轉不變性的特點。

1.2 特征點匹配

由上節得到的特征點描述子的形式為二進制碼串的形式，因此采用Hamming距離進行匹配，匹配點的hamming距離與非匹配點的hamming距離有較大的差異。匹配的相似度越高則hamming距離越小，因此，通過設定閾值的方式篩選正確的匹配點。如圖1是特征點匹配示意圖。

圖1 ORB特征點匹配對

2 特征點分離

2.1 匹配點在目標圖像上的中心估計

模板圖的特征點集為T，目標圖像的特征點集為S，（t，s）為模板圖和目標圖的一個匹配點對，其中t∈T，s∈S。記錄模板特征點相對于模板中心的位置，模板中心c可以選取模板圖像的幾何中心點。模板特征點到模板中心的相對向量記為式(9)：

其中，p（c）為模板中心的位置坐標， p(ti)為某一個模板特征點的位置坐標。對于匹配正確的點對(ti,si)，則可以通過t，s的位置坐標以及特征點方向來近似的估計S的中心點cs

式中θ=θs-θt。θs為目標圖像特征點的角度，θt為對應模板圖像特征點的角度方向。每個具有匹配對目標圖像的特征點對都會產生一個估計中心點。效果如圖2所示，圖2（a）為模板及其中心，圖2（b）為目標圖及其估計的中心點。

圖2 估計中心點

2.2 中心點聚類分析

理論上，同一個目標副本所有特征點估計的中心點的坐標應該為同一個點，實際中，由于圖像采集以及設備誤差，因此中心點為距離靠的很近的點群，這些點位于實際中心點的某一鄰域內。本文采用機器學習中的基于快速查找密度峰值的聚類算法來分離這些特征點。

式中dc為截止距離。對于dc的選取參考文獻[8]。dij=dist（pi，pj）表示數據點pi，pj之間的某種距離，本文選取歐式距離。當 ρi為最大時， δi=max( )dij。

該算法認為聚類中心同時擁有以下兩個特點：

（1）本身的密度足夠大，即周圍的點的密度均不超過它自己；

（2）和另外的聚類中心的距離相對來說更大。

圖3 中心的點的分類

2.3 分類匹配

由于每一個中心點對應一個特征點，因此分類后的中心點等同于分類后的特征點，分別采用改進的隨機一致抽樣方法進行匹配篩選，獲取模板到目標副本的變換矩陣，分離結果如圖4所示。

圖4 分離結果圖

2.4 總體流程

從模板和待檢測圖像分別提取ORB特征點，采用Hamming距離進行初步的篩選匹配點對，然后利用模板圖像特征點和模板中心形成的向量進行搜索圖中心點的估計，接著采用基于密度峰的聚類方法進行搜索圖的特征點的分類，同時可以去除一部分誤匹配點，然后對分類后的點集分別采用隨機一致抽樣方法進行變換矩陣的求解，獲取轉換關系，得到模板在待檢測圖的位置以及旋轉角度等信息。總體流程圖如圖5所示。

圖5 總體流程圖

3 實驗結果

本實驗程序是在opencv2.4.9和VS2013的基礎上編寫而成的，實驗分為三部分，分別驗證目標副本的個數能否自適應判斷，該算法的魯棒性，以及運行速度。

3.1 目標個數的自適應判斷

如圖6所示，左上圖為模板圖像，剩下的分別為目標為1，2，3，4，5個的情況，該算法均能夠很好地判斷出來目標的個數。

3.2 魯棒性檢測

魯棒性檢測主要是檢測算法在遮擋，光照不均等，外部環境有差異的情況下的工作的穩定性，如圖7所示，該算法在有待檢測目標物體有重疊的情況下依然可以識別判斷目標個數。

3.3 速度檢測

本實驗的硬件測試平臺為Inter Core i5雙核處理器，主頻2.5 GHz，運行內存4 GB，本次實驗選取十組圖片（640×480）進行處理，分別與采用SIFT特征點以及SURF特征點的模板匹配定位進行比較。本文的處理算法速度平均為213.66 ms，是SIFT的3.2倍，是SURF的5.9倍。結果如表1所示。

圖6 不同數目樣本判斷結果圖

圖7 在有遮擋重疊的情況下檢測結果

表1 算法運行時間

4 結束語

針對特征點匹配的目標副本自適應個數匹配的問題，本文提出了一種基于ORB特征點和密度峰聚類的自適應判斷目標副本個數的多目標匹配方法，運行速度較快，并且對于遮擋、重疊等具有一定的魯棒性，在理論和應用上都具備一定的價值。