基于壓縮跟蹤和遺傳算法的實時跟蹤方法

呂韻秋， 劉 凱， 費聚鋒， 程 飛

(1.西安電子科技大學(xué) 計算機學(xué)院， 陜西 西安 710071； 2.上海無線電設(shè)備研究所， 上海 200090)

基于壓縮跟蹤和遺傳算法的實時跟蹤方法

呂韻秋1， 劉 凱1， 費聚鋒2， 程 飛1

(1.西安電子科技大學(xué) 計算機學(xué)院， 陜西 西安 710071； 2.上海無線電設(shè)備研究所， 上海 200090)

壓縮跟蹤算法具有簡單、高效、實時的優(yōu)點，但是由于被跟蹤目標(biāo)尺度變化、形態(tài)變化與被遮擋等因素的干擾，跟蹤結(jié)果容易產(chǎn)生誤差。為了減小誤差，在原始壓縮跟蹤算法的基礎(chǔ)上，提出一種基于壓縮跟蹤和遺傳算法的運動目標(biāo)跟蹤方法。首先該方法利用原始壓縮跟蹤算法得到目標(biāo)可能的位置；然后在該位置周圍選定初始搜索區(qū)域；最后，利用遺傳算法找出最優(yōu)項作為該幀的跟蹤結(jié)果。實驗證明，該算法較好地解決了目標(biāo)形態(tài)變化和目標(biāo)被部分被遮擋等問題。

壓縮感知； 遺傳算法； 快速跟蹤； 特征提取

0 引言

目標(biāo)跟蹤是光電成像制導(dǎo)領(lǐng)域的關(guān)鍵技術(shù)之一。導(dǎo)彈飛行過程中，導(dǎo)彈飛行姿態(tài)、與目標(biāo)的距離和目標(biāo)姿態(tài)都會發(fā)生較大變化，導(dǎo)致拍攝到的圖像中目標(biāo)尺寸和形態(tài)發(fā)生變化等問題，引起跟蹤目標(biāo)丟失。

近年來，人們研究出許多算法來解決跟蹤問題。資料[1]提出基于Adaboost的在線特征選擇方法，在線選擇最優(yōu)特征以改善跟蹤結(jié)果。資料[2]提出一種半監(jiān)督boosting方法。它主要考慮如何利用少量的標(biāo)注樣本和未標(biāo)注樣本來進(jìn)行訓(xùn)練和分類。資料[3]提出在線多樣例學(xué)習(xí)跟蹤方法。該算法將利用正、負(fù)樣本包的多樣例學(xué)習(xí)引入在線跟蹤。

資料[4]提出了實時壓縮跟蹤算法并指出該算法優(yōu)于現(xiàn)在大多數(shù)優(yōu)秀的算法。壓縮跟蹤算法給目標(biāo)跟蹤提供了一個新的方向。它簡單、高效且穩(wěn)定，但仍有很多缺點，比如不能解決遮擋和尺寸變化等。

本文引入遺傳算法對跟蹤問題進(jìn)行研究。遺傳算法是一類借鑒自然界進(jìn)化機制的搜索和優(yōu)化技術(shù)。它應(yīng)用廣泛且有很強的魯棒性和全局尋優(yōu)能力。在圖像分割和圖像識別等方面，遺傳算法有著廣泛的應(yīng)用[5]。

1 基本原理

1.1 壓縮跟蹤算法

壓縮跟蹤算法(Compressive Tracking, CT)是一種簡單高效的基于壓縮感知的跟蹤算法， 利用壓縮感知對多尺度圖像特征進(jìn)行降維，然后在降維后的特征上采用簡單的樸素貝葉斯分類器進(jìn)行分類。該方法簡單有效并被越來越多的用于目標(biāo)跟蹤領(lǐng)域中。

壓縮感知理論指出：對于高維圖像空間中的特征x∈m，可使用隨機矩陣R∈n×m將其投影到低維空間上的特征v∈n上，如式(1)所示。

v=Rx

(1)

式中：n?m。

理想情況下，矩陣R可以大致保持原始信號之間的距離。如果隨機矩陣R滿足Johnson-Lindenstrauss引理且x是可壓縮的，則可以以較高的概率從向量v中以最小誤差重建x，v幾乎保留了x的全部信息。

壓縮跟蹤算法使用了一個非常稀疏的矩陣作為隨機測量矩陣R。這個矩陣不但滿足Johnson-Lindenstrauss引理，并且可以實時的運行。該矩陣的項定義如下：

(2)

式中：p為rij取某值的概率。當(dāng)上式中的s取2或3時，矩陣R滿足Johnson-Lindenstrauss推論，當(dāng)rij=0的概率越大時，計算量就越小。文獻(xiàn)[7]中s=m/4。壓縮跟蹤算法將每個樣本用一組多尺度矩形濾波器進(jìn)行卷積，將其表示為一個列向量，將這些列向量連接得到高維空間中圖像特征。接著，算法用隨機矩陣將這些特征投影到低維空間中。該壓縮特征可直接使用廣義Haar-like特征進(jìn)行計算，即隨機選擇的任意位置、任意大小的若干矩形塊像素的加權(quán)組合。圖1為特征提取方法的示意圖，該圖描述了怎樣將高維特征壓縮為低維特征。矩陣R中，黑、灰、白三種顏色分別表示正樣本、負(fù)樣本和零項；箭頭表示R中每行的非零項乘特征x的對應(yīng)項等價于在輸入圖像的固定位置用矩形濾波器進(jìn)行卷積。

圖1 特征提取方法示意圖

對于每個樣本z∈m，它的低維表示是v=(v1,…,vn)Τ∈n，其中m?n。壓縮跟蹤算法假設(shè)v中的所有元素都是獨立分布?？梢酝ㄟ^貝葉斯分類器進(jìn)行建模，假設(shè)先驗分布p(y=0)=p(y=1),y∈{0,1}。見公式(3)，其中H(v)的值越大，樣本為正樣本的概率越大。

(3)

(4)

(5)

(6)

1.2 遺傳算法

遺傳算法(Genetic Algorithm, GA)是一種基于自然選擇和遺傳理論的優(yōu)化算法。它的過程與自然界生物進(jìn)化過程相似。首先選擇一個初始化種群，接著對種群進(jìn)行選擇、交叉和變異操作，經(jīng)過若干代進(jìn)化后，得到全局最優(yōu)解。

遺傳算法基本步驟描述如下：

a) 隨機生成一個初始種群；

b) 遵照適應(yīng)度越高，選擇概率越大的原則，從種群中選擇兩個個體作為父方和母方；

c) 抽取父母雙方的染色體進(jìn)行交叉，產(chǎn)生子代并對子代染色體進(jìn)行變異；

d) 重復(fù)b)、c)步驟，直到產(chǎn)生新種群。

遺傳算法的應(yīng)用過程通常包含五個基本元素：

a) 參數(shù)編碼，通過對表現(xiàn)型進(jìn)行編碼產(chǎn)生基因型；

b) 初始種群的設(shè)置，初始種群可隨機產(chǎn)生，也可以根據(jù)一些限制生成；

c) 適應(yīng)度函數(shù)的設(shè)置，適應(yīng)度函數(shù)是選擇操作的唯一依據(jù)，作用是評估種群中的個體，適應(yīng)度越高，個體被選擇的概率越大；

d) 遺傳操作的設(shè)計，這些操作模擬了自然界生物進(jìn)化，適者生存的過程；

e) 控制參數(shù)的設(shè)置，比如種群尺度、交叉概率、變異概率、進(jìn)化代數(shù)。

2 基于壓縮跟蹤和遺傳算法的實時跟蹤方法

2.1 特征提取和適應(yīng)度函數(shù)

GACT算法在計算適應(yīng)度函數(shù)時采用了灰度直方圖特征[6]，其優(yōu)點是對目標(biāo)的形變和旋轉(zhuǎn)敏感并且計算簡單。該特征為稠密特征，方便對模板和候選圖像進(jìn)行匹配。

假設(shè)圖像灰度級為L(0～L-1)，L通常取256。為了提高計算速度和實時性，將灰度級映射為m級。因此，圖像的灰度直方圖特征可表示為p={p1,p2,…,pm}。

(7)

式中：b(xi)為xi的灰度值映射函數(shù)。

假設(shè)模板樣本的特征為p={p1,p2,…,pm}，候選樣本的特征為q(r)={q1,q2,…,qm}，其中r代表候選樣本序號。使用歐式距離來計算模板樣本和候選樣本之間的相似度[8]，定義為

(8)

適應(yīng)度函數(shù)定義為

(9)

于是問題轉(zhuǎn)化為求式(9)最大值問題。當(dāng)式(9)的值越大時，候選樣本和模板樣本越相似。

但是，由于上述求特征的操作用到了映射變換，當(dāng)灰度值跨度不大時，在一些測試集上有較大的概率發(fā)生兩幅完全不相同的圖像樣本的特征相似性較大，為了避免這些情況的發(fā)生，GACT算法對這種求特征的方法進(jìn)行了改進(jìn)。

將模板樣本和候選樣本分成4個部分r1,r2,r3,r4，兩者對應(yīng)部分的相似度記做d(r1),d(r2),d(r3),d(r4)，選取四者的最大值作為最終的相似度。圖2為計算適應(yīng)度函數(shù)過程的示意圖，如圖所示，箭頭代表兩個矩形的匹配過程，黑色邊框表示將樣本分割為四個部分。

圖2 計算適應(yīng)度函數(shù)過程示意圖

適應(yīng)度函數(shù)定義為相似度的倒數(shù)：

(10)

2.2 編碼方法和遺傳操作

使用壓縮跟蹤算法得到跟蹤目標(biāo)在下一幀中的預(yù)測位置(xp,yp)。以該點為中心點，取寬度為w，高度為h的矩形作為初始搜索區(qū)域，w,h的值由人工設(shè)定，通常w,h的值越大，算法精度越高，速度越慢。GACT算法采用浮點數(shù)編碼。下面介紹浮點數(shù)編碼的遺傳操作方法。

(1) 選擇操作

采用輪盤賭算法使得種群快速集聚[7]。由于每個個體之間適應(yīng)度的差異很小，輪盤賭算法能夠避免產(chǎn)生超級個體，從而避免算法“早熟”當(dāng)相似度之間的差異不大時，該方法產(chǎn)生優(yōu)異個體的速度會較慢。

為了解決這個問題，本文對該算法進(jìn)行了改進(jìn)：設(shè)置兩個閾值k,l(k

(2) 交叉操作

文獻(xiàn)[8]提出一種類似于二進(jìn)制編碼一致交叉的方法，見式(11)。

(11)

式中：α,β是(0,r),r≤1中服從正態(tài)分布的隨機數(shù)。L,R分別為參數(shù)的左、右邊界。當(dāng)r很小時，α,β在原始值附近的小范圍內(nèi)變化，當(dāng)r很大時，結(jié)果跟原始數(shù)據(jù)相差越大。

(3) 變異操作

變異操作定義如下：

(12)

式中：N(c,σ)代表均值為c，標(biāo)準(zhǔn)差為σ的正態(tài)分布。

但是式(12)的變異操作需要產(chǎn)生正態(tài)分布的隨機數(shù)且需要做邊界處理，實現(xiàn)較為復(fù)雜。大量仿真實驗表明，采用式(13)所示的變異操作實現(xiàn)簡便，效果同樣很好[9]。

(13)

式中：“0”，“1”代表變異的兩個方向；γ為(0,1)區(qū)間上的隨機數(shù)；k∈(0,1]為一個系數(shù)；r(2)隨機產(chǎn)生整數(shù)0或1。

2.3 算法流程

圖3為算法流程：

a) 輸入第t幀圖像，第(t-1)幀跟蹤位置lt-1；

d) 將lt-1作為模板樣本，并從種群中選擇兩個個體l1,l2，交叉l1,l2得到子代，對子代進(jìn)行變異；

e) 重復(fù)遺傳操作(步驟c)直到產(chǎn)生新的種群；

f) 重復(fù)步驟c)、d)選擇有最優(yōu)適應(yīng)度的樣本lt作為跟蹤結(jié)果；

g) 輸出跟蹤位置lt和最優(yōu)適應(yīng)度。

圖3 GACT的算法流程圖

3 實驗與分析

3.1 實驗結(jié)果

本文在benchmark數(shù)據(jù)集上對算法進(jìn)行測試[10]。用兩種指標(biāo)分別對所提算法和原始壓縮跟蹤算法的效果進(jìn)行評估。

第一種是成功率，定義為

(14)

式中：ROIT為跟蹤邊界框；ROIG為實際邊界框。如果該幀中s大于0.5，跟蹤成功。

圖4為成功率曲線圖，表示了算法在不同重疊率值上的成功率。

圖4 成功率曲線圖

第二種是跟蹤邊界框與人工標(biāo)定的實際邊界框之間的中心誤差。

圖5為mountainBike視頻序列的中心誤差圖，表示了算法在每幀中的中心誤差。

圖5 算法在mountainBike序列中的中心誤差圖

圖6為準(zhǔn)確率曲線圖，表示了算法在各種位置誤差值上的中心誤差。由這兩個標(biāo)準(zhǔn)的結(jié)果所示，GACT算法明顯優(yōu)于原始CT算法。由于灰

圖6 準(zhǔn)確率曲線圖

度直方圖特征計算簡單且遺傳算法避免了全局搜索，該算法能夠?qū)崟r的運行。

圖7為mountainBike視頻序列中的跟蹤情況示意圖，該圖分別畫出了第1，56，111，166，221幀的跟蹤結(jié)果，其中虛線框為GACT算法的跟蹤結(jié)果，實線框為CT算法的跟蹤結(jié)果，該圖表示了兩種算法的跟蹤效果。實驗證明，本文提出的GACT算法主要能夠解決以下問題。

(1) 尺度和形態(tài)變化

對于freeman1和carScale，singer2等視頻序列，目標(biāo)發(fā)生了尺度變化，對于girl，freeman1，mountainBike等序列，目標(biāo)的形態(tài)發(fā)生變化，但是GACT算法相比CT算法能夠較好的跟蹤了目標(biāo)。

(2) 遮擋

Faceocc1和tiger1中目標(biāo)被遮擋，GACT算法仍穩(wěn)定地跟蹤了目標(biāo)。

(3) 運動模糊和背景干擾

對于deer和football等序列，CT算法丟失了目標(biāo)，而GACT算法仍能穩(wěn)定跟蹤。

圖7 mountainBike序列中的跟蹤情況示意圖

3.2 算法不足與改進(jìn)

GACT算法不能解決下列問題：

a) 光照變化：CT算法不能很好的解決光照變化問題，而GACT算法亦無法解決，原因是灰度直方圖特征對于光照不敏感；

b) 長時間完全遮擋：由于使用的模板樣本來源于上一幀，當(dāng)該幀中的目標(biāo)被完全遮擋時，很難發(fā)現(xiàn)它。

針對這些問題，可使用SIFT(Scale-invariant Feature Transform)特征代替灰度直方圖特征去匹配模板和候選樣本[11]。SIFT特征可很好的解決目標(biāo)旋轉(zhuǎn)、光照變化，尺度變化等問題。但是若使用該特征，算法的實時性是否能保證有待進(jìn)一步實驗。

4 結(jié)束語

提出了一種基于壓縮跟蹤和遺傳算法的跟蹤算法。壓縮跟蹤簡單且具有很好的實時性和魯棒性。所提出的算法利用遺傳算法對壓縮跟蹤結(jié)果進(jìn)行優(yōu)化。采用灰度直方圖特征計算樣本和模板之間的相似度。該相似度作為遺傳算法的適應(yīng)度函數(shù)。跟蹤結(jié)果由遺傳算法得到。實驗證明，在許多易發(fā)生漂移的跟蹤序列上，GACT算法能夠穩(wěn)定地跟蹤且擁有較好的準(zhǔn)確性、魯棒性和跟蹤效率。

[1] R. T. Collins, Y. X. Liu, M. Leordeanu. Online Selection of Discriminative Tracking Features[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2005: 1631-1643.

[2] H. Grabner, C. Leistner, H. Bischof. Semi Supervised Online Boosting for Robust Tracking[J]. Lecture Notes in Computer Science, 2008: 234-247.

[3] B. Banenko, M. H. Yang, S. Belongie. Robust Object Tracking with Online Multiple Instance Learning[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2011: 1619-1632.

[4] Kaihua Zhang, Lei Zhang, Ming-Hsuan Yang. Real-time Compressive Tracking[J]. Proc. International ECCV 2002 Workshop on Biometric Authentication, 2012,(6): 103-111.

[5] Klaus J. Kirchberg, Oliver Jesorsky, Robert W. Frischholz. Genetic Model Optimization for Hausdorff Distance-based Face Localization[J]. ECCV, 2002: 866-879.

[6] Timo Ahonen, Abdenour Hadid, Matti Pietikainen. Face Recognition with Local Binary Patterns[J]. Computer Vision-ECCV, 2004: 469-481.

[7] Kai Song Goh, Andrew Lim, Brian Rodrigues. Sexual Selection for Genetic Algorithms[J]. Artificial Intelligence Review, 2003,(4): 123-152.

[8] Gunilla Borgefors. Distance Transformations in Arbitrary Dimensions[J]. Computer Vision, Graphics, and Image Processing, 1984,(9): 321-345.

[9] Tong Zhang, Hua Zhang, Zi-cai Wang. Float Encoding Genetic Algorithm and its Application[J]. Journal of Harbin Institute of Technology, 2000,(8): 59-61.

[10] Yi Wu, Jongwoo Lim, Ming-Hsuan Yang. Online Object Tracking: A Benchmark[J]. IEEE Conference on Computer Vision and Pattern Recognition, 2013: 2411-2418.

[11] David G. Lowe. Object Recognition from Local Scale-invariant Features[J]. International Conference on Computer Vision, Corfu, Greece, 1999,(9): 1150-1157.

Real-time Tracking Method Based on Compressive Tracking and Genetic Algorithm

LYUYun-qiu1,LIUKai1,FEIJu-Feng2,CHENGFei1

(1.School of Computer Science and Technology, Xidian University, Xian Shaanxi 710071,China; 2.Shanghai Radio Equipment Research Institute, Shanghai 200090, China)

Compressive Tracking is simple, efficient and real-time. However, errors of the tracking result would be produced because of pose variation of tracking object or occlusion. In order to reduce errors, a tracking method of moving object based on compressive tracking and genetic algorithm is proposed in this paper to optimize the result of original compressive tracking. First, a possible position of target is predicted by original compressive tracking. Second, a search region of target is generated around the possible position. Third, genetic algorithm is used to get the optimal value as tracking result. Experiment shows that the proposed algorithm can solve some problems such as pose variation and partial occlusion.

compressive tracking; genetic algorithm; fast tracking; feature extraction

1671-0576(2016)04-0034-06

TN957.52

A

2016-09-20

國家自然科學(xué)基金, 編號: 91538101，61571345，61550110247；上海航天科技創(chuàng)新基金,編號:SAST2015072。

呂韻秋(1994-)，女，碩士；劉 凱(1978-)，男，教授，主要從事圖像處理技術(shù)研究。