基于兩步位操作匹配的實時目標識別跟蹤算法*

曹 建，謝曉方，付霖宇，梁 捷

(海軍航空工程學院，山東煙臺 264001)

0 引言

目標識別在圖像分析和計算機視領域起著重要作用，是近年來研究的熱點之一。按照實現(xiàn)方法可以分為兩大類:分類識別和匹配識別。分類識別方法一般需要構造有效的特征向量和充分利用相關領域的知識，而在許多實際應用中，很難得到有關特征概率和類別概率的先驗知識，或者得到的數(shù)據(jù)不足。在這種情況下，可使用模型直接匹配未知物體，并選擇最佳匹配為最終分類結果。但實際成像系統(tǒng)中，場景圖像與照明、攝像機參數(shù)、攝像機位置等因素有關，因此，要從圖像中對目標進行匹配識別，特別是從復雜背景多物體的圖像中識別特定目標，必須考慮很多復雜因素包括:場景的不變性，場景的復雜度;特征占用內(nèi)存空間大小;圖像遮擋等。

采用局部特征的目標匹配可以從整體匹配的形式轉變?yōu)榫植科ヅ涞男问剑瑥亩鵀檎趽跄繕说淖R別和不同姿態(tài)的同一目標的識別開辟了一條有效的途徑[1]。近幾年，經(jīng)過國內(nèi)外學者的努力，已經(jīng)有大量速度較快且具有魯棒性的相關算法，包括尺度不變性特征轉換(SIFT)[2]，加速魯棒特征(SURF)[3]，定向快速旋轉 Brief特征(ORB)[4]，以及由 Strfan等人提出的二值化魯棒尺度不變特征(BRISK)[5]等。其中，BRISK特征算子是一種新的具有尺度不變性和旋轉不變性的角點檢測和描述算法，與其他的特征檢測與描述算法(SIFT，SURF等)相比，運算速度以及內(nèi)存占用量有了明顯改善。

但在特定的場合，如便攜電子設備(手機、平板電腦等)或是軍用設備(如自尋的電視制導系統(tǒng))上，計算能力有限且硬件平臺內(nèi)存容量較小，特別是在實時應用場合，連續(xù)視頻圖像中目標識別跟蹤對算法處理速度提出了更高要求。

為此，文中提出了一種通過兩步位操作模板匹配(two step bits operation matching，TSBOM)的目標識別跟蹤算法。該算法基于改進的BRISK算法，對原算法中的特征描述符建立方法及匹配算法進行了改進:提出了采樣點對選擇策略和幅值－旋轉兩級描述符建立方法;在特征點匹配階段，提出兩步位操作特征匹配算法，并通過部分匹配及檢測漢明重量閾值的方式進一步加快算法執(zhí)行速度。

1 BRISK算法

與其他具有旋轉、尺度等魯棒性的局部特征檢測算法相同，BRISK算法使用尺度空間關鍵點檢測以及主方向矯正等技術，實現(xiàn)各種不變性。整個算法流程包括角點特征提取、尺度空間關鍵點檢測以及描述子建立3個階段。

1.1 角點特征提取

在角點特征提取階段，采用由Mair等人提出的AGAST角點探測算法來提取角點特征。其核心思想是檢測候選特征點為圓心的Breaenham圓周上的像素值。如果候選點周圍領域內(nèi)有足夠多的采樣點與該候選點的灰度值差別夠大(足夠“亮”或足夠“暗”)，則認為該候選點為一個特征點[8]。

為了克服FAST對噪聲敏感，不具備旋轉不變性以及不具備尺度不變性等各種缺點。BRISK先采用不同尺度高斯平滑，通過使用FAST值(FAST Score)作為度量局部最大性的指標，將點灰度測試轉變?yōu)榫植繀^(qū)域最值比較，有效去除噪聲干擾。為了具有尺度不變性，在尺度空間對關鍵點進行檢測。

1.2 尺度空間關鍵點檢測

與其他具有尺度不變性的特征算法相同，BRISK也是從構建尺度空間金字塔開始的。先構建尺度空間金字塔(n層(octave)以及n－1個中間層(inter-octave)構成，中間層位于相層兩階之間);然后，將具有相同閾值T的FAST算子應用于每一層以及中間層，檢測出潛在的感興趣區(qū)域，最后，對這些潛在區(qū)域中的點在尺度空間進行非極大值抑制。并對極大值進行亞像素和連續(xù)尺度校正。

1.3 BRISK描述子建立

受BRIEF算法的啟發(fā)，BRISK也使用了由Calondor等人提出的二進制串[7]來描述每個特征點，其優(yōu)點是采用漢明距離來計算匹配程度，即將特征先按位異或(XOR)，然后統(tǒng)計結果中1的個數(shù)，若其較小，表明匹配程度較高。正如文獻[7]證明的一樣，這種算法在運算速度上比一般的歐式距離算法有明顯優(yōu)勢。與BRIEF，ORB等算法不同，BRISK不是利用隨機點對，而是使用幾個同心Bresenham圓上均勻分布的采樣點(共計60個)，兩兩遍歷構成采樣點對。由歐式距離意義下的長距離采樣點對估計特征點方向，旋轉采樣區(qū)域，重采樣，然后利用短距離采樣點對生成二進制描述子。

1.4 BRISK 算法缺點

BRISK算法的三階段中，描述子建立過程涉及到點對選擇，主方向矯正等，所需時間較多，相比較其他兩個過程，尚有改進余地。通過分析，運算量集中在兩方面，一是描述子生成時，由于在待測特征點周圍使用了較多的采樣點(60個)，造成采樣點對數(shù)量較多，相關性較大，降低描述子的判別性;二是為了滿足旋轉不變性，需確定主方向并旋轉，花費了大量的運算時間。

通過降低采樣點數(shù)，優(yōu)化點對選購策略是減少點對數(shù)量，降低相關性，提高算法速度及判別性的有效方法;另外，圍繞文中研究的視頻序列圖像，由于幀間特征點在視點空間上變化較小，使特征點集旋轉角度有限，實現(xiàn)旋轉不變性的計算是不必要或是精度要求較低的。Calonder在其文獻[7]中也指出，角度方向的檢測過程還會減低后續(xù)的識別率。

2 基于改進BRISK算法的目標識別

在實際視頻圖像應用背景下，文中提出了改進的BRISK算法，包括點對選取策略，雙二進制串描述符以及兩步位操作模板匹配等內(nèi)容。最后，利用該算法匹配目標特征數(shù)據(jù)庫實現(xiàn)目標跟蹤識別。

2.1 特征描述子建立

2.1.1 點對選擇策略

文獻[8]中FREAK算法模擬人眼功能，利用不同標準差高斯函數(shù)構建平滑重疊區(qū)域，中間密集，四周稀疏，模擬人眼視網(wǎng)膜細胞的分布，減少采樣點數(shù)量，進而減少用于建立特征描述子的點對數(shù)量。由BRISK的60個采樣點(59×30=1770對)變成 43個采樣點(43×21=903對)。在提高速度的同時，內(nèi)存占用量也大大降低。文中也采用“視網(wǎng)膜”采樣區(qū)定義的43個采樣點，如圖1。

對于點對選擇策略，BRISK將所有屬于短距離采樣點對均進行了計算，進而生成二進制串，所使用的點對具有較高相關性。在ORB算法中，離線計算測試數(shù)據(jù)，利用小相關性(均值0.5)的方法得到點對選擇策略。根據(jù)這一方法，對測試圖像中的采樣點，首先構建二維矩陣，矩陣每一行為某點遍歷其他所有采樣點形成的二進制描述子;然后考慮該矩陣的每一列，只有其均值在0.5附近，表明該列的0，1分布數(shù)量較為相同，該采樣點對相關性低。按照以上方法，選擇了排序后的前128個點對。

2.1.2 雙二進制串描述子

雙二進制串描述子指的是特征點幅度和角度二進制描述子。在尺度空間關鍵點檢測后，得到關鍵點坐標，然后利用 FREAK使用的高斯函數(shù)，平滑采樣區(qū)，再選擇上述離線確定出的128個點對，不經(jīng)過主模式確定及旋轉，直接按照式(1)生成128維二進制描述子，其中，I (Pi，σi)，I (Pj，σj)為高斯平滑后的采樣點灰度值，A128為128個點對構成集合。由于該描述子反映的是特征角點周圍采樣區(qū)域的灰度情況，稱它為特征點幅度二進制描述子。

圖1 FREAK采樣區(qū)域

上述生成的特征點二進制描述子，由于較遠距離采樣點對數(shù)量無法確定，導致其中含有的特征點角度信息不明顯，如果據(jù)此進行特征點匹配，有可能造成角度信息匱乏使誤配較高。為此，采樣區(qū)高斯平滑后，在關鍵點周圍64個采樣點中，選取距離較遠的點，同關鍵點組成點對，比較灰度，生成特征點角度二進制描述子。這里，以順時針方向，按照距離中心位置，從遠至近，從關鍵點正上方開始，順時針依次提取18個采樣點。圖2中提取點位于不同半徑Bresenham黑色圓點，高斯平滑區(qū)域用不同顏色表示。采樣點加上關鍵點共19點，形成點對規(guī)模為19×9=171，使用點對提取策略，離線找到相關性較小的128對點，按照式(2)生成128位二進制角度信息數(shù)據(jù)，其中I (P0，σ)0為關鍵點(圖3中心點)平滑后的灰度值。

圖2 計算角度二進制描述子所用的采樣區(qū)域

2.2 特征匹配算法

2.2.1 兩步位操作特征匹配算法(TSBOM)

通過上面建立的雙二進制串描述子，設待匹配兩個特征點 ( Pa，Pb)的特征點幅度和角度二進制描述子分別為:

兩步位操作特征匹配算法(two step bits operation matching，TSBOM)，是指按照時間先后的旋轉角度匹配位操作與特征幅值匹配位操作。其核心是在尺寸變換基礎上，考慮到采樣點均勻分布在同心Bresenham圓上，通過按位循環(huán)位移角度二進制描述子來模擬角度旋轉。具體來說，對于角度描述子，理論上共需移位128次，每循環(huán)移位后，計算兩個特征點角度漢明距離，找到最匹配位移操作數(shù)(即旋轉角度信息)M，然后移動幅度描述子M次，再完成兩個特征點幅值匹配工作。如式(5)、式(6)所示，其中函數(shù)Fi()表示對二進制串循環(huán)左移i次，?為按位“異或”操作。

對實際的視頻圖像，選擇相機運動較為明顯的視頻圖像(20幀 /s)，通過提取并匹配不同幀目標特征，分析特征點角度變化最大值，來確定在視頻應用條件下，角度描述子需要移位的最大次數(shù)Mmax，進而降低運算量，提高運算速度。為了具有代表性，提取100幀進行處理分析。通過實驗發(fā)現(xiàn):在幀與幀間，特征點角度基本不變，只有幀數(shù)相差較大(60幀左右)時，特征點變化角度范圍約為(－30°～30°)。將結果擴大，得到Mmax?3。

2.2.2 TSBOM 優(yōu)化方法

1)漢明重量閾值。通過循環(huán)移位指令模擬角度旋轉，待匹配的描述子構成首尾相連環(huán)形結構。2個特征點如為匹配點，但不論如何按位“移位”(旋轉)，不考慮噪聲干擾，在一定誤差情況下，二者雙二進制串描述子中1的個數(shù)相近，否則可以判定不為匹配點。漢明重量是字符串中非零的元素個數(shù)，對于二進制字符串，是指其中1的個數(shù)。設FHWeight()為字符串漢明重量函數(shù)，差異度函數(shù)為的定義按照式(7))，若此值大于閾值范圍(文中為 ＞7或 ＜－7)，判定兩特征點不為匹配點。

2)部分描述子匹配。TSBOM算法含有多位二進制運算，能否只比較256位中的部分來剔除大量待匹配點，進而降低位操作總次數(shù)，提高算法運算效率。其實，按照提取策略，提取順序靠前的點對，相關性最小，最具有辨別力，其對應雙二進制串描述子的前幾位。為此，對每個待匹配特征點，預處理幅值128位的前幾位，可以剔除大量的待匹配點，達到加速目的。大多數(shù)CPU，一個指令周期就能完成16位的二進制操作。由此，選擇幅值描述子的前16位，作為“預先”匹配描述子。

2.3 目標特征數(shù)據(jù)庫建立與目標識別

對于遠距離或近似平面的目標，其透視變形可以通過仿射變換來近似。按照文獻[9]提出的方法，使用仿射矩陣，將目標模板圖像通過仿射變換，生成尺度、旋轉、視角均改變下的目標樣本集。并將該樣本集分為固定尺寸和方向范圍的子集，使用改進的BRISK算法提取每個子集中的角點特征，利用統(tǒng)計學原理，選取該子集中出現(xiàn)概率最高的前n個點作為穩(wěn)定特征，建立目標特征數(shù)據(jù)庫。

在視頻序列的識別跟蹤階段，使用兩步位操作特征匹配算法(TSBOM)，直至視頻圖像最后一幀。其整體流程為:

①提取視頻序列圖像下一幀，在目標待檢測區(qū)域，采用改進BRISK提取特征點集，并生成雙二進制串描述子集;

②遍歷模板數(shù)據(jù)庫中穩(wěn)定特征點，并與幅值描述子集進行前16位描述子匹配，通過“異或”位操作生成匹配結果，若大于閾值(此處為4)，剔除待匹配陪集的不匹配點;

③根據(jù)模板數(shù)據(jù)庫中穩(wěn)定特征點角度描述子和幅值描述子漢明權重值，在閾值(此處為20)條件下，進一步剔除不匹配點;

3 實驗結果及分析

實驗程序使用最新公布的OPenCV 2.4及Visual Studio 2010開發(fā)平臺，硬件平臺為 Intel Pentium E5300，2G RAM PC。實驗的視頻圖像來自于圖像測試數(shù)據(jù)庫，尺寸大小為320×240。通過人工方式，將其中第一幀中部黑色車輛作為目標模板圖，仿射變換得到目標樣本集。按照2.3節(jié)中提出的方法建立了目標特征數(shù)據(jù)庫，調(diào)整AGAST檢測閾值，使每個子集中穩(wěn)定特征點數(shù)量保持在100左右。最終識別跟蹤結果如圖3～圖6所示。由于采用局部特征進行匹配，在目標不完整及有干擾的情況下，均能較好識別目標，而處理速度穩(wěn)定在80fps左右(BRISK算法50fps左右)。目標特征數(shù)據(jù)庫中穩(wěn)定特征角點數(shù)目為30個，占用內(nèi)存容量約900KB。

圖3 目標模板

圖4 多目標車輛識別

圖5 部分遮擋下目標跟蹤

圖6 不完整目標識別跟蹤

4 結論

文中提出了一種基于兩步位操作匹配實現(xiàn)的目標匹配識別算法。該算法基于改進的BRISK算法，對特征描述符建立方法及匹配算法進行了改進:提出了采樣點對選擇策略和幅值－旋轉兩級描述符建立方法;在此基礎上，通過兩步位操作特征匹配算法實現(xiàn)特征點匹配。針對視頻序列中目標圖像，使用仿射變換建立目標特征數(shù)據(jù)庫并進行目標識別。實驗結果表明，文中算法具有更快的運算速度以及更低的存儲空間，更加滿足嵌入式實時系統(tǒng)要求。

[1]孫浩，王程，王潤生.局部不變特征綜述[J].中國圖象圖形學報，2011，16(1):141 －151.

[2]Mikolajczyk schmid.Scale ＆ affine invariant interest point detectors[J]. International Journal of Computer Vision，2004，60(1):63－86.

[3]H Bay，T Tuytelaars，L Van Gool. SURF:Speeded up robust features[C]//Proceedings of the Ninth European Conference on Computer Vision(ECCV)，2006.

[4]Ethan Rublee，Vincent Rabaud，Kurt Konolige，et al. ORB:An efficient alternative to SIFT or SURF[C]//Proceedings of the IEEE International Conference on Computer Vision(ICCV)，2011.

[5]Stefan Leutenegger，Margarita Chli，Roland Siegwart. BRISK:Binary Robust Invariant Scalable Keypoints[C]//Proceedings of the IEEE International Conference on Computer Vision(ICCV)，2011.

[6]E Rosten，T Drummond. Machine learning for high speed corner detection[C]//Proceedings of the European Conference on Computer Vision(ECCV)，2006.

[7]M Calonder，V Lepetit，C Strecha，et al. BRIEF:Binary Robust Independent Elementary Features[C]//Proceedings of the European Conference on Computer Vision(ECCV)，2010.

[8]A Alahi，R Ortiz，P Vandergheynst. FREAK:Fast Retina Keypoint[C]//IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，2012.

[9]孫抗，汪渤，鄭智輝.基于局部亮度直方圖特征的實時目標識別與跟蹤[J].系統(tǒng)工程與電子技術，2011，33(9):1928－1931.