哈希編碼和Kalman濾波的目標跟蹤算法*

李 華， 李 莉， 郭育艷

(1. 河南工程學院 計算機學院， 鄭州 451191； 2. 河南財經(jīng)政法大學 科研處， 鄭州 450046)

視頻圖像中運動目標的檢測與跟蹤是計算機視覺領(lǐng)域中的熱點之一，廣泛應用于軍事偵察、精確制導、火力打擊、戰(zhàn)場評估及安防監(jiān)控等領(lǐng)域[1-2].目標跟蹤通過檢測目標在視頻圖像序列中的位置信息來實現(xiàn)對目標的跟蹤，常用的目標跟蹤算法有Mean-shift、模板匹配法、KLT、光流法和CamShift等.其中，Mean-shift目標跟蹤算法[3]計算量不大，在目標區(qū)域已知的情況下可實現(xiàn)實時跟蹤，但當目標運動速度較快時，跟蹤效果較差；基于模板匹配的目標跟蹤算法[4]具有較強的魯棒性，跟蹤效果較好，但計算量大，算法復雜，跟蹤速度較慢；KLT跟蹤算法利用特征點實現(xiàn)目標跟蹤，跟蹤速度較快，但跟蹤效果較差；光流法跟蹤效果一般，計算量較大，速度較慢，不適用于目標跟蹤；CamShift[5]是一種連續(xù)自適應的Mean-shift算法，主要是針對視頻序列，該算法對單目標跟蹤效果較好，但當目標與背景顏色相近時，跟蹤效果較差.

哈希算法[6-7]是圖像檢索領(lǐng)域中一個重要算法，該算法將任意分辨率的圖像數(shù)據(jù)轉(zhuǎn)化為幾百比特的二進制序列，大大減少了圖像檢索的計算量.由于運動目標跟蹤的原理與圖像檢索的原理相似，即在每一幀中搜索與目標最相似的區(qū)域.針對現(xiàn)有的目標跟蹤算法過于復雜、計算量大和遮擋無法跟蹤等問題，將哈希算法改進后應用于目標跟蹤領(lǐng)域，提出了基于哈希編碼和Kalman濾波的目標跟蹤改進算法.首先利用哈希算法對感興趣區(qū)域進行編碼；然后根據(jù)編碼特征進行目標匹配跟蹤；最后借助Kalman濾波算法對運動目標的位置進行預測.實驗表明，本文方法跟蹤效果較好，具有較強的抗干擾能力，提高了跟蹤速率，但無法較好地實現(xiàn)遮擋情況下的目標跟蹤，因此，本文方法的性能有待進一步提高.

1 哈希編碼目標跟蹤算法

鑒于哈希算法的抗碰撞性、魯棒性和Kalman濾波算法的快速性[8]，提出了基于哈希編碼和Kalman濾波的目標跟蹤改進算法，算法實現(xiàn)過程如圖1所示.

圖1 算法實現(xiàn)框圖Fig.1 Implementation block diagram of algorithm

首先輸入視頻序列幀，提取出待測區(qū)域的哈希編碼值，與目標編碼值進行比對，繼而跟蹤匹配；再采用Kalman濾波算法對運動目標位置進行最優(yōu)估計；最后實現(xiàn)目標更新，輸出結(jié)果.

1.1 編碼特征提取

目標特征提取是目標跟蹤過程中的核心部分.采用哈希編碼對圖像信息進行處理，映射為一維數(shù)字摘要.特征相同或相近的二維圖像生成的一維數(shù)字摘要也相同或相近；反之，生成的一維數(shù)字摘要不同或區(qū)別較大[9].哈希編碼生成過程分為以下幾步：

1) 圖像預處理，消除一些無關(guān)信息，如噪聲.

2) 將彩色圖轉(zhuǎn)化為灰度圖，減少計算量.YUV空間中的Y分量代表圖像亮度，U、V代表色度分量，采用Y分量來近似代替灰度圖，RGB空間向YUV空間轉(zhuǎn)換的公式為

(1)

3) 將目標圖像縮小為32×32像素，快速去除圖像高頻信息和細節(jié)，簡化后續(xù)運算.

4) 對處理后的圖像進行DCT變換，其表達式為

(2)

5) 計算上述64個DCT系數(shù)的均值E，即

(3)

6) 生成編碼值.將DCT變換后的系數(shù)f(u，v)與均值E比較，若f(u，v)≥E，記為1；若f(u，v)

(4)

將比較結(jié)果串成長度為64的一維向量，組合次序無要求，但必須保證所有圖像都采用同一個編碼次序，得到一個64 bit編碼數(shù)據(jù)，為該目標的編碼值.

1.2 目標匹配

目標匹配有多種方法，如歐氏距離、漢明距離和范數(shù)等.本文通過計算目標的哈希編碼值與圖像的哈希編碼值之間誤碼的個數(shù)，將誤碼個數(shù)最少的目標作為跟蹤目標.設目標的哈希編碼值為ho，待測區(qū)域的哈希編碼值為ho′，圖像的哈希編碼值為hi，誤碼個數(shù)為Dis(ho，hi)，則有

?ho′∈hi，Dis(ho，ho′)

(5)

哈希編碼值ho′對應的圖像區(qū)域為搜索到當前的目標區(qū)域.

1.3 目標校正

搜索視頻圖像目標難免存在誤差，隨著搜索視頻幀數(shù)的增加，誤差也逐漸增多[10].為了避免誤差的引入，本文采用反饋方式對目標位置進行校正.

設上一幀視頻圖像為ft-1(x，y)，目標位置為(xt-1，yt-1)，采用Kalman濾波算法在當前幀中搜索目標位置，得到新位置(x′t，y′t).再以新位置為起點在上一幀中用Kalman濾波算法反搜索目標，得到上一幀中目標位置(x′t-1，y′t-1).若(x′t-1，y′t-1)≠(xt-1，yt-1)，則對當前幀中搜索到的目標位置(x′t，y′t)進行校正，即

(6)

式中，(xt，yt)為當前幀中搜索到的目標位置(x′t，y′t)校正后的最終位置.

2 Kalman加速策略

視頻圖像處理的關(guān)鍵問題是實時性問題.在整張圖像上搜索目標非常耗時，縮小搜索范圍，可大大提升搜索效率.利用Kalman濾波算法對運動目標下一幀可能出現(xiàn)的位置進行預測，再將預測位置作為搜索的起點，對其周圍圖像進行搜索，從而縮小搜索范圍[11].當目標被部分短暫遮擋時，將Kalman預測的位置看作真實位置來完成對目標的穩(wěn)定跟蹤.

Kalman濾波算法包含兩個子模型：狀態(tài)模型和預測模型[12].狀態(tài)模型可用一個線性隨機微分方程描述，即

X(k)=AX(k-1)+BU(k)+W(k)

(7)

系統(tǒng)的測量值為

Z(k)=HX(k)+V(k)

(8)

式中：X(k)為k時刻系統(tǒng)狀態(tài)向量；U(k)為k時刻驅(qū)動輸入向量；A為狀態(tài)轉(zhuǎn)移矩陣；B為系統(tǒng)控制輸入矩陣；Z(k)為k時刻測量結(jié)果矢量；H為狀態(tài)向量與觀測向量之間的聯(lián)系矩陣；W(k)和V(k)分別為過程與測量的噪聲，服從高斯分布.

狀態(tài)向量預測方程為

X(k|k-1)=AX(k-1|k-1)+BU(k)

(9)

式中：X(k|k-1)為利用上一時刻狀態(tài)預測當前狀態(tài)的結(jié)果；X(k-1|k-1)為上一時刻狀態(tài)的最優(yōu)結(jié)果.

X(k|k-1)的協(xié)方差P預測方程為

P(k|k-1)=AP(k-1|k-1)A′+Q

(10)

式中：P(k|k-1)為X(k|k-1)對應的協(xié)方差；P(k-1|k-1)為X(k-1|k-1)對應的協(xié)方差；A′為A的轉(zhuǎn)置矩陣；Q為系統(tǒng)過程的協(xié)方差.結(jié)合預測值與觀測值，對X(k|k-1)進行最優(yōu)化估計，即

X(k|k)=X(k-1|k-1)+kg(k)·

(Z(k)-HP(k|k-1))

(11)

式中，kg為卡爾曼增益，其表達式為

(12)

式中，R為觀測噪聲協(xié)方差.當前狀態(tài)協(xié)方差P(k|k)的預測方程為

P(k|k)=(I-kg(k)H)P(k|k-1)

(13)

式中，I為單位矩陣.對于單模型測量值I=1，當系統(tǒng)進入k+1狀態(tài)時，P(k|k)即為P(k-1|k-1).

在每一幀搜索目標時，以預測值X(k|k-1)作為起始點，在其周圍進行目標搜索.相鄰兩幀圖像時間間隔非常短，如果目標做勻速運動，那么狀態(tài)轉(zhuǎn)移矩陣A與系統(tǒng)控制輸入矩陣B為

其中，Δt為時間間隔，狀態(tài)向量與觀測向量之間的聯(lián)系矩陣為

3 實驗結(jié)果與分析

3.1 實驗對比

為了驗證本文算法的有效性，在MATLAB2012b環(huán)境下運行，對視頻背景靜止且較為單一的專用測試視頻“Sample.avi”(總幀數(shù)為80幀)分別采用經(jīng)典均值偏移(Mean-shift，MS)算法和本文提出的改進算法進行對比.Mean-shift算法對“Sample.avi”視頻中的第1幀、第9幀、第16幀和第23幀的跟蹤結(jié)果如圖2所示.

圖2 Mean-shift算法視頻跟蹤結(jié)果Fig.2 Results of video tracking with Mean-shift algorithm

由圖2可知，Mean-shift算法以目標顏色直方圖作為特征，采用窗口固定方法對“Sample.avi”視頻進行跟蹤，跟蹤效果較差，易丟失目標.第16幀跟蹤目標已嚴重跟偏；第23幀已完全丟失目標.Mean-shift算法耗時11 s，跟蹤效果較差.采用本文方法對“Sample.avi”視頻的第1幀、第26幀、第45幀和第80幀進行跟蹤，結(jié)果如圖3所示.

圖3 本文方法視頻跟蹤結(jié)果(1)Fig.3 Results of video tracking with as-proposed method (1)

通過實驗分析，采用本文方法在“Sample.avi”視頻跟蹤全程中，并無出現(xiàn)跟蹤目標偏離的情況，跟蹤效果較好.在相同實驗環(huán)境下，耗時7 s，速度優(yōu)于經(jīng)典Mean-shift算法.

對比實驗結(jié)果表明，本文提出的基于哈希編碼與Kalman濾波的目標跟蹤改進算法在背景單一的情況下跟蹤效果較好，在視頻第80幀(最后一幀)時仍能有效跟蹤，而Mean-shift算法在第16幀時已嚴重跟偏，跟蹤效果較差.

為進一步驗證本文方法的優(yōu)越性，分別采用Mean-shift算法和本文方法對“Sample.avi”視頻的定位偏差進行分析.偏差大小使用位置分量的和方根誤差(root sum square error，RSSE)來描述，即

(14)

式中：xi、yj分別為目標x、y方向上位置估計值；xp、yp分別為目標x、y方向上位置真實值.

若目標的位置估計值與位置真實值相同，則對應時刻的和方根誤差RSSE為0；反之，則越大.采用Mean-shift算法和本文方法對“Sample.avi”視頻進行定位偏差分析，結(jié)果如圖4所示.

圖4 定位偏差Fig.4 Location deviation

Mean-shift算法從第16幀開始，位置分量的和方根誤差(RSSE)呈上升趨勢，跟蹤效果較差；本文方法的誤差曲線呈細微波動狀態(tài)，跟蹤效果較好.

3.2 復雜環(huán)境目標跟蹤

由于跟蹤效果受拍攝環(huán)境、目標位置、目標大小等因素影響較大，所以實驗采取主觀評判的標準，不進行偏差分析.采用本文方法對拍攝的一個騎摩托車小視頻“Motorcycle.avi”進行跟蹤，該視頻總幀數(shù)為17幀，視頻圖像大小為640×480像素，跟蹤時間共1.5 s，跟蹤目標為摩托車駕駛員.采用本文方法對“Motorcycle.avi”視頻第1幀、第8幀、第13幀和第17幀進行跟蹤，結(jié)果如圖5所示.

圖5中，“Motorcycle.avi”整個視頻背景復雜，跟蹤目標處于快速運動中，選取的任意四幀跟蹤結(jié)果表明對于快速運動的目標，本文方法跟蹤效果較好，并能準確計算出目標在每一幀中的位置.

采用本文方法對小視頻“Target with Cover.avi”的第1幀、第25幀、第70幀和第84幀進行跟蹤實驗，跟蹤目標為行人，視頻總幀數(shù)為84幀，視頻圖像大小為640×480像素，跟蹤時間共7 s，得到的實驗結(jié)果如圖6所示.

圖5 本文方法視頻跟蹤結(jié)果(2)Fig.5 Results of video tracking with as-proposed method (2)

圖6 本文方法視頻跟蹤結(jié)果(3)Fig.6 Results of video tracking with as-proposed method (3)

從圖6a中可以看出，本文方法在無遮擋時跟蹤效果較好；當目標漸漸被遮擋時，仍能有效地跟蹤，如圖6b所示；當目標慢慢地抽離被遮擋的部分時，該方法仍能較好跟蹤，如圖6c所示；跟蹤一直持續(xù)到視頻的最后一幀(第84幀)，如圖6d所示.該實驗表明，本文方法在目標遮擋后仍能有效跟蹤，且跟蹤效果較好.

4 結(jié) 論

針對經(jīng)典的Mean-shift目標跟蹤算法計算量大，計算復雜，不利于硬件實現(xiàn)等問題，提出了基于哈希編碼和Kalman濾波的目標跟蹤改進算法.該方法利用哈希函數(shù)的抗碰撞性和摘要性提取目標的哈希特征值并進行編碼，跟蹤匹配，借助Kalman濾波算法對運動目標位置預測，縮小目標搜索范圍，加快目標跟蹤速度，實現(xiàn)將二維圖像轉(zhuǎn)變?yōu)橐痪S數(shù)字摘要，大大減少了匹配運算量.在MATLAB2012b，圖像大小640×480像素的環(huán)境下，跟蹤速率可達12幀/s.通過分析不同的視頻，實驗結(jié)果表明，基于哈希編碼與Kalman濾波的目標跟蹤改進算法有效地提高了目標跟蹤速度，并在背景復雜、目標快速運動、完全遮擋等情況下仍能穩(wěn)定跟蹤，針對以前很多遮擋后無法進行繼續(xù)跟蹤的算法進行了很好的補充.