一種基于ORB 特征匹配和反投影直方圖的目標跟蹤方法

劉泓佚，常天慶，郝 娜，戴文君

(裝甲兵工程學(xué)院，北京 100072)

目前的跟蹤算法，如粒子濾波等，能以一定的精度跟蹤發(fā)生形變的目標。但是這些算法計算量大，計算的復(fù)雜度高，進行長時間跟蹤時跟蹤效果差，經(jīng)常丟失目標。因此本文采用ORB 特征匹配的跟蹤方式，首先在視頻中選取目標區(qū)域，提取這一區(qū)域以及每一幀視頻中圖像的ORB 特征，進行特征點匹配并連接相似的特征點，以此達到跟蹤的目的，并保證一定實時性。

1 ORB 特征的相關(guān)理論

為了更好地描述物體，讓計算機能通過特征點準確快速的發(fā)現(xiàn)和辨識目標，人們提出了很多特征點及描述符。從最初的HARRIS 角點，到SIFT、PCA-SIFT、GOLH、SURF，在2006年提出了FAST 算法，在2010年提出來了BRIEF 算法，2011年Ethan Rublee 等人使用結(jié)合了灰度質(zhì)心法的FAST 特征和加入了方向信息的BRIEF 特征描述符，提出了ORB 算法，即oriented FAST and rotated BRIEF。

1.1 FAST 算法及其改進［1］

在圖像中一個點的周圍圓形區(qū)域中找到足夠多的像素點，這些像素點跟中心像素點的差值都大于一個閾值時，這個中心點就是FAST 特征點，如圖1 所示。ORB 算法中使用FAST-9，即圓形區(qū)域的半徑為9。FAST 特征點的提取速度非常快，因此很受研究人員青睞。但是FAST 特征點不具有旋轉(zhuǎn)不變性，因此ORB 算法采用了一種結(jié)合強度質(zhì)心思想的FAST，即OFAST。

圖1 FAST 特征

OFAST 在FAST 的基礎(chǔ)上通過矩加入了主方向。一個區(qū)域內(nèi)圖像的矩的定義如下

通過矩的定義得到區(qū)域圖像的質(zhì)心

OFAST 特征點的方向定義為待測點與質(zhì)心的夾角

其中atan2 是arctan 的象限感知。

1.2 BRIEF 算法及其改進

BREIF 算法用二進制的方式對圖像區(qū)域進行表達，算法用τ 測試計算二進制描述子［2］。對于一個M ×M 的矩形區(qū)域Q，其τ 測試定義為

其中x 和y 表示形如(u，v)的二維坐標，而q(x)表示x 位置處的灰度值。

Brief 算法即是若干個隨機選出點的τ 測試值組成的二進制bit 串:

BRIEF 算法拋棄了用直方圖描述區(qū)域的方法，而是隨機采點計算二進制描述子，極大的提高了描述子的建立速度，而且生成的二進制描述子也便于計算，便于在硬件上進行處理，這種二進制描述子的匹配效率非常之高，在很多情況下匹配效果超過了SURF。但是Brief 算法不具備旋轉(zhuǎn)不變性，對噪聲也比較敏感，因為τ 測試依靠灰度值，噪聲容易對灰度產(chǎn)生影響，雖然在計算τ 測試前進行濾波處理，但是還是無法完全去除噪聲的影響。

ORB 算法采用了rBRIEF 算法，它引入了方向信息以增加旋轉(zhuǎn)不變性［3］。首先將n 比特的點集寫成矩陣形式

根據(jù)Fast 算法得到的方向角θ 求出其對應(yīng)的旋轉(zhuǎn)矩陣Rθ，構(gòu)建經(jīng)過矯正的Sθ，Sθ=RθS，為原始BRIEF 加入了旋轉(zhuǎn)不變性，新的描述點集為

1.3 特征提取的步驟

對于一個31 ×31 的圖像，將所有的5 ×5 方塊用oFAST算法檢測關(guān)鍵點的位置以及關(guān)鍵點的角點方向。對每個子窗口檢測到的二進制描述串求平均值，并根據(jù)均值與0.5 的偏差大小進行排序，將這些子窗口的二進制描述串存入到一個容器T 中，進行貪婪搜索算法［3］。

1)移出容器T 中的頂層的第一項，放入到一個結(jié)果容器R 中。

2)然后用容器T 的下一項與容器R 中所有的二進制描述串進行比較，如果它們之間的相關(guān)性大于一個閾值。則不必用這個含有冗余信息的描述串，否則將其添加到結(jié)果容器R。

3)重復(fù)1)、2)步驟，直到結(jié)果容器R 中有256 個二進制字符串。如果完成一次循環(huán)后容器中二進制字符串仍低于256 個，則提高相關(guān)性閾值，重新進行貪婪搜索，直到搜索到256 個二進制描述字符串。

2 ORB 特征的優(yōu)勢及特征匹配方案

2.1 ORB 特征的優(yōu)勢［4］

SURF、SIFT 和ORB 同樣為性能優(yōu)良的特征檢測和描述方法。SIFT 和SURF 都使用了高斯金字塔，以及Hessian 變換，檢測得到的特征有尺度和旋轉(zhuǎn)不變性，而ORB 沒有考慮尺度不變性，避免了耗時的高斯卷積，因此ORB 特征的檢測和描述耗時最短。當(dāng)目標圖像像素大小為352 ×169 時的特征點提取結(jié)果及時間如圖2 所示，提取SURF、SIFT 和ORB特征分別耗時27 ms、134 ms、20 ms。

當(dāng)目標圖像像素大小為1 280 ×720 時的特征點提取結(jié)果及時間如圖3 所示，提取SURF、SIFT 和ORB 特征分別耗時264 ms、1 459 ms、54 ms。

圖2 從左到右為SURF、SIFT、ORB 特征點檢測和描述的結(jié)果

圖3 從左到右為SURF、SIFT、ORB 特征點檢測和描述的結(jié)果

2.2 ORB 特征的匹配方案

實現(xiàn)基于ORB 特征匹配的目標跟蹤任務(wù)時，首先需要選定目標區(qū)域，分別計算目標區(qū)域和整個場景圖像的ORB特征，然后分別對其進行描述，而后在每幀圖像中將目標和場景的特征描述符進行匹配，標記出匹配點，達到跟蹤的目的。匹配的質(zhì)量影響跟蹤的效果，因此匹配方式的選取很重要。最簡單的匹配方式是暴力匹配。本文使用局部敏感哈希(LSH)算法。

暴力匹配是預(yù)先存儲目標圖像的特征，用每一個已知特征逐個的匹配待測圖像中所有的特征，這種方法雖然計算量較大，但如果是對簡單數(shù)據(jù)集進行匹配，計算時間較短。

LSH 方法的主要思想是將在特大數(shù)據(jù)集中找相鄰元素的問題簡化為新空間的哈希桶內(nèi)找相鄰元素的問題。具體的做法如下［5-6］:

1)對于一個向量，通過將歐式空間轉(zhuǎn)換到漢明空間，得到其n 維的二值向量。

2)找到m 個符合一定條件的哈希函數(shù)，每一個函數(shù)都隨機抽取二值向量中的k 位作為輸入，并將輸出結(jié)果(哈希值)保存。

3)計算樣本庫中所有向量分別經(jīng)過m 個哈希函數(shù)作用的結(jié)果，將經(jīng)過相同哈希函數(shù)作用且哈希值大致相同的不同向量放在新的位置(哈希桶)。

4)對待測向量進行匹配時，通過m 個哈希函數(shù)作用，根據(jù)哈希值，只需將對應(yīng)的多個哈希桶中的元素取出進行比較。避免匹配與其相鄰概率小的向量，從而提高了匹配效率。

局部敏感哈希算法中哈希桶的數(shù)量、隨機抽取二進制向量的位數(shù)等會影響匹配效果，設(shè)置哈希桶個數(shù)為6，抽取的二進制向量位數(shù)為12。

2.3 仿真與對比

提取鼠標選中的目標區(qū)域，計算此區(qū)域與視頻幀圖像的ORB 特征，并進行匹配。選取了在野外錄制的車輛視頻進行跟蹤，分別采用暴力匹配和SLH 匹配，如圖4 和圖6 所示，圖5 和7 分別顯示了匹配的時間。

圖4 暴力匹配ORB 特征的效果圖

圖5 暴力匹配ORB 特征所用的時間

圖6 局部敏感哈希法匹配ORB 特征

圖7 局部敏感哈希法匹配ORB 特征的時間

3 基于反直方圖投影的輔助跟蹤策略

3.1 輔助跟蹤策略

ORB、SURF 以及SIFT 描述符都是在灰度圖像的基礎(chǔ)上計算特征點，而后進行描述的，沒有利用顏色信息，因此我提出一種基于反投影直方圖的輔助跟蹤策略，利用所選區(qū)域的顏色直方圖對整個待處理圖像進行相關(guān)性的重構(gòu)。

一般直方圖反投影的結(jié)果是一幅像素值在0 ～255 之間變化的灰度圖［7］。亮度越高的地方代表這個區(qū)域與所選區(qū)域的相關(guān)度高，否則說明相關(guān)度低。為了利用這種灰度圖像，進行了下述操作。首先通過設(shè)置閾值，將灰度圖像2 值化，得到離散的黑白圖像，然后用大像素的膨脹單元對黑白圖像進行膨脹，盡可能使白色區(qū)域包含目標所在區(qū)域，并且去除白色區(qū)域中的噪點，最后用膨脹后的圖像與原圖像作與運算，得到了優(yōu)化后的原始圖像。對單個圖像空間進行反投影、閾值分割、膨脹等上述操作，耗時約30 ms。對3 個空間進行上述操作并將結(jié)果疊加，耗時約60 ms。上述過程如圖8所示。

圖8 H 空間反投影直方圖輔助跟蹤的過程

3.2 ORB 特征點跟蹤與反投影直方圖相結(jié)合

在選取目標后首先對原始圖像進行優(yōu)化，而后提取目標區(qū)域以及優(yōu)化后圖像的ORB 特征進行匹配。下面對比了在反直方圖的輔助下，暴力匹配和LSH 匹配的跟蹤效果，如圖9 和圖11 所示，在每幀圖像上應(yīng)用上述兩種方法消耗的時間分別如圖10 和圖12 所示。

圖9 RGB 空間反投影輔助SLH 匹配ORB 特征的跟蹤方法效果圖

圖10 反投影輔助LSH 匹配方法消耗的時間

圖11 RGB 空間反投影輔助暴力匹配ORB 特征的跟蹤方法效果圖

圖12 反投影輔助暴力匹配方法消耗的時間

4 跟蹤結(jié)果的比較

TLD 和CT 算法是目前熱門的兩種優(yōu)秀跟蹤算法。TLD算法分為3 個模塊，分別是跟蹤、檢測和學(xué)習(xí)。其中跟蹤器是Lucas 光流跟蹤器，它是基于兩幀差分的光流估計方法。檢測模塊采用隨機森林算法，它作為一種分類器，相比于其他算法有很大優(yōu)勢，它能處理維度很高(特征量很大)的數(shù)據(jù)，而且不需要對特征進行優(yōu)化。學(xué)習(xí)模塊采用PN 學(xué)習(xí)，用來對檢測器產(chǎn)生的錯誤進行識別。上文中的視頻用TLD 算法跟蹤，處理每幀圖像消耗約73 ms，但是隨著跟蹤時間的增加，當(dāng)目標逐漸縮小時，跟蹤失敗，如圖13 和14 所示。

圖13 TLD 跟蹤算法效果圖

CT 算法是基于檢測和學(xué)學(xué)習(xí)的算法，用稀疏矩陣對特征降維，用樸素貝葉斯分類器進行訓(xùn)練和分類，能對模板進行在線更新。待測視頻采用CT 算法跟蹤每幀耗時約40 ms，跟蹤效果如圖15 和圖16 所示。當(dāng)目標變小時跟蹤失敗。

而本文采用的方法在初始跟蹤時有較好的效果，當(dāng)目標變小時雖然特征的匹配線減少，但是目標始終顯現(xiàn)。除此之外，圖像的邊緣產(chǎn)生了很多檢測點，對結(jié)果產(chǎn)生了一定的干擾;設(shè)置的匹配門限不夠合適，當(dāng)目標大小變化時，匹配效果變差，這都是算法有待提高的地方。

圖14 tld 跟蹤算法效果圖

圖15 CT 跟蹤算法效果圖

圖16 CT 跟蹤算法效果圖

5 結(jié)論

本文提出的反投影直方圖輔助跟蹤策略結(jié)合ORB 特征匹配的跟蹤方法，既利用了顏色信息，又利用了灰度圖中目標的特征，跟蹤1 副1 080 ×720 的視頻序列，每幀只需約200 ms。

［1］章杰.基于ORB 特征和粒子濾波的目標跟蹤算法的研究［D］.長春:吉林大學(xué)，2014.

［2］孟凡清.基于背景差分法與ORB 算法的運動目標檢測與跟蹤算法研究［D］.北京:北京印刷學(xué)院，2014.

［3］劉銘.基于ORB 算法的雙目視覺測量與跟蹤研究［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2014.

［4］謝成明.基于ORB 特征的目標檢測與跟蹤的研究［D］.合肥:合肥工業(yè)大學(xué)，2013.

［5］史世澤.局部敏感哈希算法算法的研究［D］.西安:西安電子科技大學(xué)，2013.

［6］劉英帆. 基于局部敏感哈希的近似最近鄰查詢研究［D］.西安:西安電子科技大學(xué)，2014.

［7］Robert Laganière.Opencv2 計算計視覺編程手冊［M］.北京:科學(xué)出版社，2013.