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

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

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

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

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

為了更好地描述物體，讓計(jì)算機(jī)能通過特征點(diǎn)準(zhǔn)確快速的發(fā)現(xiàn)和辨識目標(biāo)，人們提出了很多特征點(diǎn)及描述符。從最初的HARRIS 角點(diǎn)，到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 算法及其改進(jìn)［1］

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

圖1 FAST 特征

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

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

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

其中atan2 是arctan 的象限感知。

1.2 BRIEF 算法及其改進(jìn)

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

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

Brief 算法即是若干個(gè)隨機(jī)選出點(diǎn)的τ 測試值組成的二進(jìn)制bit 串:

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

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

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

1.3 特征提取的步驟

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

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

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

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

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

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

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

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

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

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

2.2 ORB 特征的匹配方案

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

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

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

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

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

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

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

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

2.3 仿真與對比

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

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

圖5 暴力匹配ORB 特征所用的時(shí)間

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

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

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

3.1 輔助跟蹤策略

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

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

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

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

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

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

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

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

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

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

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

圖13 TLD 跟蹤算法效果圖

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

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

圖14 tld 跟蹤算法效果圖

圖15 CT 跟蹤算法效果圖

圖16 CT 跟蹤算法效果圖

5 結(jié)論

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

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

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

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

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

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

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

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