哈希編碼和Kalman濾波的目標(biāo)跟蹤算法*

李 華， 李 莉， 郭育艷

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

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

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

1 哈希編碼目標(biāo)跟蹤算法

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

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

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

1.1 編碼特征提取

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

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

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

(1)

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

4) 對(duì)處理后的圖像進(jìn)行DCT變換，其表達(dá)式為

(2)

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

(3)

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

(4)

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

1.2 目標(biāo)匹配

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

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

(5)

哈希編碼值ho′對(duì)應(yīng)的圖像區(qū)域?yàn)樗阉鞯疆?dāng)前的目標(biāo)區(qū)域.

1.3 目標(biāo)校正

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

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

(6)

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

2 Kalman加速策略

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

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

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

(7)

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

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

(8)

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

狀態(tài)向量預(yù)測(cè)方程為

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

(9)

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

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

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

(10)

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

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

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

(11)

式中，kg為卡爾曼增益，其表達(dá)式為

(12)

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

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

(13)

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

在每一幀搜索目標(biāo)時(shí)，以預(yù)測(cè)值X(k|k-1)作為起始點(diǎn)，在其周?chē)M(jìn)行目標(biāo)搜索.相鄰兩幀圖像時(shí)間間隔非常短，如果目標(biāo)做勻速運(yùn)動(dòng)，那么狀態(tài)轉(zhuǎn)移矩陣A與系統(tǒng)控制輸入矩陣B為

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)對(duì)比

為了驗(yàn)證本文算法的有效性，在MATLAB2012b環(huán)境下運(yùn)行，對(duì)視頻背景靜止且較為單一的專(zhuān)用測(cè)試視頻“Sample.avi”(總幀數(shù)為80幀)分別采用經(jīng)典均值偏移(Mean-shift，MS)算法和本文提出的改進(jìn)算法進(jìn)行對(duì)比.Mean-shift算法對(duì)“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算法以目標(biāo)顏色直方圖作為特征，采用窗口固定方法對(duì)“Sample.avi”視頻進(jìn)行跟蹤，跟蹤效果較差，易丟失目標(biāo).第16幀跟蹤目標(biāo)已嚴(yán)重跟偏；第23幀已完全丟失目標(biāo).Mean-shift算法耗時(shí)11 s，跟蹤效果較差.采用本文方法對(duì)“Sample.avi”視頻的第1幀、第26幀、第45幀和第80幀進(jìn)行跟蹤，結(jié)果如圖3所示.

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

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

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

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

(14)

式中：xi、yj分別為目標(biāo)x、y方向上位置估計(jì)值；xp、yp分別為目標(biāo)x、y方向上位置真實(shí)值.

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

圖4 定位偏差Fig.4 Location deviation

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

3.2 復(fù)雜環(huán)境目標(biāo)跟蹤

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

圖5中，“Motorcycle.avi”整個(gè)視頻背景復(fù)雜，跟蹤目標(biāo)處于快速運(yùn)動(dòng)中，選取的任意四幀跟蹤結(jié)果表明對(duì)于快速運(yùn)動(dòng)的目標(biāo)，本文方法跟蹤效果較好，并能準(zhǔn)確計(jì)算出目標(biāo)在每一幀中的位置.

采用本文方法對(duì)小視頻“Target with Cover.avi”的第1幀、第25幀、第70幀和第84幀進(jìn)行跟蹤實(shí)驗(yàn)，跟蹤目標(biāo)為行人，視頻總幀數(shù)為84幀，視頻圖像大小為640×480像素，跟蹤時(shí)間共7 s，得到的實(shí)驗(yàn)結(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中可以看出，本文方法在無(wú)遮擋時(shí)跟蹤效果較好；當(dāng)目標(biāo)漸漸被遮擋時(shí)，仍能有效地跟蹤，如圖6b所示；當(dāng)目標(biāo)慢慢地抽離被遮擋的部分時(shí)，該方法仍能較好跟蹤，如圖6c所示；跟蹤一直持續(xù)到視頻的最后一幀(第84幀)，如圖6d所示.該實(shí)驗(yàn)表明，本文方法在目標(biāo)遮擋后仍能有效跟蹤，且跟蹤效果較好.

4 結(jié) 論

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