劉韶濤， 姚燦榮

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 福建 廈門 361021)

結(jié)合PSO的改進(jìn)壓縮跟蹤方法

劉韶濤， 姚燦榮

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 福建 廈門 361021)

針對(duì)基于在線檢測(cè)的跟蹤方法中目標(biāo)在多尺度空間中的搜索和匹配問題，結(jié)合粒子群優(yōu)化算法(PSO)和壓縮感知思想，提出一種魯棒的多尺度目標(biāo)跟蹤算法.首先,通過粒子群在多尺度空間中采集樣本;然后,經(jīng)過壓縮感知提取特征;最后,通過粒子的迭代計(jì)算，搜索出當(dāng)前目標(biāo)的最佳匹配位置.實(shí)驗(yàn)結(jié)果表明：提出的算法能較好地適應(yīng)目標(biāo)的多尺度變化，在快速性和魯棒性上具有更好的性能. 關(guān)鍵詞： 目標(biāo)跟蹤; 壓縮感知; 粒子群優(yōu)化; 多尺度

一個(gè)典型的目標(biāo)跟蹤系統(tǒng)包括表觀模型和在當(dāng)前幀定位目標(biāo)新位置的搜索策略[1].由于光照變化、遮擋等問題，導(dǎo)致目標(biāo)的表觀模型時(shí)常發(fā)生變化.因此，一個(gè)自適應(yīng)強(qiáng)的表觀模型表示對(duì)魯棒的目標(biāo)跟蹤十分重要.基于特征實(shí)時(shí)檢測(cè)[2-3]的運(yùn)動(dòng)目標(biāo)跟蹤方法是近年來的一種主流目標(biāo)跟蹤技術(shù)[4-6].在線方法在對(duì)目標(biāo)進(jìn)行分類判別的同時(shí)，也在對(duì)圖像進(jìn)行采樣，用于實(shí)時(shí)更新分類器，使檢測(cè)器具有一定的適應(yīng)能力，不僅在一定程度上解決了檢測(cè)和跟蹤時(shí)的遮擋問題，還能適應(yīng)復(fù)雜場(chǎng)景下的多目標(biāo)跟蹤.然而，其計(jì)算和搜索復(fù)雜度較高，且容易產(chǎn)生漂移.近年來，基于隨機(jī)優(yōu)化技術(shù)的粒子群優(yōu)化算法(PSO)被廣泛應(yīng)用于計(jì)算機(jī)視覺處理[7-9].為了在多尺度空間中快速尋找目標(biāo)，降低計(jì)算代價(jià)，保持跟蹤的實(shí)時(shí)性和重疊率，本文提出一種結(jié)合粒子群優(yōu)化的壓縮跟蹤算法(PSO-CT)，在每一幀的目標(biāo)搜索過程中，利用粒子群優(yōu)化的搜索方法，在多尺度空間中更快速地搜索目標(biāo).

1 壓縮跟蹤算法

壓縮跟蹤(compress tracking)算法是Zhang等[6]基于壓縮感知理論[10]提出的一種高效、快速的基于在線學(xué)習(xí)的實(shí)時(shí)跟蹤方法.壓縮跟蹤算法的流程，如圖1所示.圖1中：分類器更新是通過在當(dāng)前幀跟蹤結(jié)果的鄰域內(nèi)采集正負(fù)樣本，然后進(jìn)行壓縮，訓(xùn)練分類器得到.

圖1 實(shí)時(shí)壓縮跟蹤算法流程Fig.1 Real-time compress tracking algorithm

1.1 隨機(jī)投影

圖2 特征映射Fig.2 Feature projection

如果信號(hào)通過某種變換后是可稀疏表示或者可壓縮的，則可以設(shè)計(jì)一個(gè)與變換基不相關(guān)的測(cè)量矩陣來測(cè)量信號(hào)，得到的測(cè)量值通過求解優(yōu)化問題可實(shí)現(xiàn)信號(hào)的精確或者近似重構(gòu).具體地，對(duì)于高維圖像空間中的數(shù)據(jù)x∈Z，如果x在正交基Ψ上是K-稀疏的，且能找到一個(gè)與Ψ不相關(guān)的觀測(cè)基R，則可以使用隨機(jī)觀測(cè)矩陣R∈Zn×m，將其投影到低維空間y∈Zn上，如圖2 所示.圖2中：n?m.Johnson-Lindenstrauss準(zhǔn)則表明：當(dāng)隨機(jī)測(cè)量矩陣R滿足有限等距性質(zhì)時(shí)，K個(gè)系數(shù)可通過求解最小誤差，從y中高概率地恢復(fù)原始信號(hào)x.

1.2 隨機(jī)測(cè)量矩陣

為了適應(yīng)實(shí)際應(yīng)用的實(shí)時(shí)性需求，采用文獻(xiàn)[6]提出的一個(gè)非常稀疏的隨機(jī)測(cè)量矩陣，具體矩陣元素定義為

(1)

式(1)中:p為隨機(jī)元素ri，j取某個(gè)值的概率.例如，取s=n/4時(shí),測(cè)量矩陣非常稀疏，即n行中每行只需2～4個(gè)非零元素，就能滿足Johnson-Lindenstrauss推論，且只需初始的一次離線計(jì)算就能滿足整個(gè)跟蹤過程的計(jì)算．

假設(shè)s是第t-1跟蹤到的目標(biāo)位置，在以s為中心,r為半徑的范圍內(nèi)，采集測(cè)試樣本集的Haar-like特征：Ti∈Zw×h×l(i=1,2,…,r2)，l為Haar-like的模板數(shù)，則每個(gè)特征的維數(shù)m可能達(dá)到106以上.利用初始產(chǎn)生的隨機(jī)稀疏矩陣,將此高維數(shù)據(jù)投影到低維空間中，形成適合快速計(jì)算的低維特征v.

圖3 圖像特征的多尺度表示Fig.3 Representation of multi-scale feature

1.3 目標(biāo)的Haar-like多尺度表示與尺度不變性

(2)

2 基于PSO改進(jìn)的壓縮跟蹤算法

2.1 粒子群優(yōu)化算法

圖4 粒子更新示意圖Fig.4 Particle update schematic

(3)

(4)

式(3)，(4)中:ω為迭代權(quán)重；φ1，φ2為大于0的常數(shù)，用于平衡個(gè)體最佳和全局最佳；r1,r2∈(0,1)為均勻分布的隨機(jī)數(shù).

2.2 結(jié)合PSO改進(jìn)的壓縮跟蹤

(5)

式(5)中:Σ為高斯矩陣的協(xié)方差.

對(duì)角線元素為速度預(yù)測(cè)，即

(6)

2.3 適應(yīng)值函數(shù)

在當(dāng)前幀，以前一幀為中心，半徑R(足夠大)的圓，或者為邊長(zhǎng)的正方形范圍內(nèi)，按高斯分布隨機(jī)初始化K個(gè)粒子.由于在前一幀中已經(jīng)更新了分類器，因此,用分類器的分類響應(yīng)作為粒子j在第t次迭代時(shí)相應(yīng)的適應(yīng)函數(shù)值,即

(7)

式(7)中:zj,t為粒子xj,t在當(dāng)前位置時(shí)提取的低維特征向量.

根據(jù)每個(gè)粒子的適應(yīng)函數(shù)值f(xj,t)，得到全局最佳g和粒子j的個(gè)體最佳pt,j的更新，即

(8)

(9)

(10)

(11)

(12)

由式(10)～(12)可知：通過適應(yīng)函數(shù)值可以控制個(gè)體和社會(huì)認(rèn)知的變化，使之得到平穩(wěn)控制，而粒子最大速度可利用先驗(yàn)知識(shí)獲取.

2.4 分類器更新

當(dāng)獲取當(dāng)前幀的最大響應(yīng)位置時(shí)，確定目標(biāo)在當(dāng)前幀的位置.為了確定正負(fù)樣本的采樣范圍，通過2個(gè)距離閾值α和β來界定采樣的類別.在Dα= {z|||l(z)-lt||<α}區(qū)域內(nèi)采集正樣本，在區(qū)域Dζ,β={z|ζ<||l(z)-lt||<β}采集負(fù)樣本.其中，α<ζ<β，即靠近當(dāng)前目標(biāo)中心的隨機(jī)采集為正樣本，外圍采集為負(fù)樣本.

根據(jù)正負(fù)樣本，分類器的參數(shù)更新為

(13)

(14)

當(dāng)目標(biāo)在場(chǎng)景中因轉(zhuǎn)向、形變、遮擋及鏡頭晃動(dòng)等因素發(fā)生劇烈變化時(shí)，可能導(dǎo)致粒子在給定范圍內(nèi)的適應(yīng)值無法小于閾值，搜索終止于局部最優(yōu).結(jié)合文獻(xiàn)[12]的方法，采用選擇更新和re-search策略.當(dāng)目標(biāo)發(fā)生遮擋時(shí)，分類器的響應(yīng)值顯著減小，為了不被遮擋物完全取代，設(shè)定一個(gè)分類閾值TC；當(dāng)分類相應(yīng)低于閾值時(shí)，分類器停止更新；當(dāng)在給定的局部范圍內(nèi)無法搜索到目標(biāo)時(shí)，則跳出局部搜索范圍，增加粒子數(shù)量，將PSO搜索范圍擴(kuò)大至全局搜索.

PSO-CT算法有以下5個(gè)步驟.

步驟1 初始化粒子群參數(shù)、分類器和目標(biāo)特征.

步驟2 對(duì)于每一幀，有如下5點(diǎn)：

1) 計(jì)算Frame(t)的積分圖；

2) 如果第t-1幀的分類響應(yīng)P>TC，則對(duì)于每個(gè)目標(biāo)，根據(jù)上一幀得到的目標(biāo)位置，在以上一幀的目標(biāo)為中心，d為邊長(zhǎng)的正方形內(nèi)隨機(jī)產(chǎn)生K個(gè)粒子，并初始化個(gè)體最佳pj和全局最佳g；否則，在全局范圍內(nèi)，將尺度參數(shù)w，h范圍擴(kuò)大，隨機(jī)產(chǎn)生4K個(gè)粒子，并初始化4K個(gè)例子的個(gè)體最佳pj和全局最佳g；

3) 計(jì)算每個(gè)粒子的Haar-like特征，計(jì)算粒子的分類得分，得到各自的適應(yīng)值f(x(j,t))；

4) 比較f(x(j,t))及pj和g，更新個(gè)體最佳pj和全局最佳g,修改粒子的位置和速度；

5) 如果f(g) 滿足搜索結(jié)束條件，則得到這一幀的目標(biāo)位置:Loc=g；否則，跳轉(zhuǎn)至全局搜索2).

步驟3 在跟蹤到的當(dāng)前幀目標(biāo)周圍Xζ,β={x|ζ<||It+1(x)-It(x*)||<β}，采集正、負(fù)樣本.

步驟4 利用上面的積分圖，計(jì)算正樣本和負(fù)樣本的Haar-like特征值，壓縮特征.

步驟5 通過正樣本和負(fù)樣本更新分類器，進(jìn)行下一幀處理.

3 結(jié)果與分析

3.1 粒子數(shù)的確定

為了驗(yàn)證算法的有效性，在CPU主頻為3GHz，內(nèi)存為8GB的PC實(shí)驗(yàn)環(huán)境下，采用幾個(gè)標(biāo)準(zhǔn)視頻集[13]，將文中算法與粒子濾波(PF)、基于檢測(cè)學(xué)習(xí)跟蹤算法(TLD)、壓縮跟蹤算法(CT)進(jìn)行比較.

(a) 中心平均定位誤差 (b) 幀平均處理時(shí)間圖5 粒子數(shù)與平均定位誤差和幀平均處理時(shí)間Fig.5 Particle number， CLE and PT

為了更好確定實(shí)驗(yàn)中粒子個(gè)數(shù)，針對(duì)粒子數(shù)與算法性能的關(guān)系進(jìn)行多次重復(fù)實(shí)驗(yàn)，結(jié)果如圖5所示.

圖5中：n1為粒子數(shù)；t為幀處理時(shí)間.由圖5可知：如要實(shí)現(xiàn)實(shí)時(shí)跟蹤，必須合理控制粒子數(shù)量.其中，中心定位誤差(CLE)的計(jì)算為

(15)

式(15)中：(xt,yt)和(xr,yr)分別表示當(dāng)前跟蹤定位結(jié)果與人工定位標(biāo)準(zhǔn)位置.

圖6 粒子平均迭代次數(shù)Fig.6 Average iteration times of particle

3.2 PSO-CT的跟蹤性能分析

將粒子數(shù)設(shè)置為30，將收斂閾值Th=0.01,Tc=0.6，迭代參數(shù)ω=0.5，初始φ1=0.5，φ2=0.5，最大迭代次數(shù)設(shè)為100.設(shè)4維搜索空間半徑為40.在測(cè)試粒子搜索目標(biāo)過程中，計(jì)算復(fù)雜度的實(shí)驗(yàn)結(jié)果，如圖6所示.PSO-CT平均每個(gè)粒子的迭代次數(shù)(n2)為42.4 次·幀-1，總迭代次數(shù)為30×42.4，相當(dāng)于只需1 272次搜索和比對(duì)，就能在每一幀圖像中發(fā)現(xiàn)目標(biāo).文獻(xiàn)[6]采用改進(jìn)全搜索的coarse-to-fine策略需要3 496次.在幾組復(fù)雜場(chǎng)景下的跟蹤結(jié)果，如圖7,8所示，其幀率如表1所示.圖8中：n3為幀數(shù)；e為跟蹤誤差.

(a) David第160幀 (b) David第182幀 (c) David第292幀

(c) Car第88幀 (d) Car第252幀 (e) Car第621幀

(f) Carcase第67幀 (g) Carcase第115幀 (h) Carcase第849幀圖7 復(fù)雜環(huán)境下幾種跟蹤算法結(jié)果Fig.7 Tracking result of some algorithm in complex scenes

(a) Motocross (b) Mountainbike (c) Coke圖8 幾種算法的跟蹤誤差Fig.8 Tracking error of some algorithms

由圖8可知：Motocross中目標(biāo)因?yàn)榉D(zhuǎn)產(chǎn)生平穩(wěn)形變,此時(shí)，TLD算法、PF算法和PSO-CT算法表現(xiàn)出良好效果;Mountainbike中場(chǎng)景從平穩(wěn)跨越到劇烈抖動(dòng)，此時(shí)，原始PSO-CT算法在平穩(wěn)環(huán)境誤差較小，而面對(duì)突變，最終也能快速校正偏差;Coke場(chǎng)景中，中間經(jīng)歷幾次遮擋和高度變化，當(dāng)鏡頭或者景深發(fā)生明顯變化時(shí)，多尺度的PSO-CT的尺度適應(yīng)性能優(yōu)勢(shì)明顯.

表1 幾種跟蹤算法的平均幀率Tab.1 Average frame processing rate of some tracking algorithms

綜上可知，在變化比較快的復(fù)雜場(chǎng)景下，CT和PSO-CT表現(xiàn)相對(duì)穩(wěn)定，且PSO-CT能適應(yīng)突然、快速的目標(biāo)位置變化.當(dāng)鏡頭或者景深發(fā)生明顯變化時(shí)，多尺度的PSO-CT在尺度變化的自適應(yīng)方面體現(xiàn)出良好的跟蹤效果.在時(shí)間效率上，如表1所示.由于采用特征壓縮方法，將特征用低維的向量表示，CT算法和PSO-CT算法在速度上具有優(yōu)勢(shì)，體現(xiàn)出良好的快速性和實(shí)時(shí)性.

4 結(jié)束語

針對(duì)原始?jí)嚎s跟蹤存在的不足，結(jié)合粒子群優(yōu)化算法的優(yōu)化多維空間搜索，實(shí)現(xiàn)復(fù)雜場(chǎng)景下多尺度目標(biāo)跟蹤.實(shí)驗(yàn)表明，提出的PSO-CT跟蹤方法在實(shí)時(shí)性和穩(wěn)定性上具有一定優(yōu)勢(shì).該算法對(duì)運(yùn)動(dòng)目標(biāo)發(fā)生部分遮擋和形變時(shí)仍然有較好的魯棒性，然而，當(dāng)多個(gè)目標(biāo)之間產(chǎn)生聚合與分離時(shí)，跟蹤還達(dá)不到最理想的結(jié)果，這將是下一步工作需要考慮和突破的地方.

[1] 龔聲蓉,劉純平,季怡.復(fù)雜場(chǎng)景下圖像與視頻分析[M].北京:人民郵電出版社,2013:8-9.

[2] KALAL Z,MIKOLAJCZYK K,MATAS J.Tracking-learning-detection[J].Pattern Analysis and Machine Intelligence,2012,34(7):1409-1422.

[3] STALDER S,GRABNER H,GOOL L V.Cascaded confidence filtering for improved tracking-by-detection[M].Berlin:Springer,2010:369-382.

[4] GRABNER H,GRABNER M,BISCHOF H.Real-time tracking via on-line boosting[C]∥British Machine Vision Conference.Edinburgh：[s.n.]，2006:6.

[5] FELZENSZWALB P,MCALLESTER D,RAMANAN D.A discriminatively trained, multiscale, deformable part model[C]∥IEEE Conference on Computer Vision and Pattern Recognition.Anchorage:IEEE Press,2008:1-8.

[6] ZHANG Kaihua,ZHANG Lei,YANG M H.Real-time compressivetracking[C]∥Europeanence on Computer Vision.Berlin:Springer,2012:864-877.

[7] SAINI S,AWANG R D R,ZAKARIA M N B,etal.A review on particle swarm optimization algorithm and its variants to human motion tracking[J].Mathematical Problems in Engineering,2014(2014):1-16.

[8] ZHANG Xiaoqin, HU Weiming, MAYBANK S,etal. Sequential particle swarm optimization for visual tracking[C]∥IEEE Conference on Computer Vision and Pattern Recognition.Anchorage:IEEE Press,2008:921-928.

[9] FLEISCHMANN P,AUSTVOLL I,KWOLEK B.Particle swarm optimization with soft search space partitioning for video-based markerless pose tracking[J].Lecture Notes in Computer Science,2012,7517:479-490.

[10] BARANIUK R.Compressive sensing[J].IEEE signal processing magazine,2007,24(4):118-121.

[11] THIDA M,ENG H,MONEKOSSO D N,etal.A particle swarm optimisation algorithm with interactive swarms for tracking multiple targets[J].Applied Soft Computing,2013,13(6):3106-3117.

[12] TAWAB A M A,ABDELHALIM M B,HABIB S.Efficient multi-feature PSO for fast gray level object-tracking[J].Applied Soft Computing,2014,14(1):317-337.

[13] WU Yi,LIM J,YANG M H.Online object tracking: A benchmark[C]∥IEEE Conference on Computer vision and pattern recognition.Portland:IEEE Press,2013:2411-2418.

(責(zé)任編輯： 錢筠 英文審校： 吳逢鐵)

Improved Compress Tracking Algorithm Based on PSO

LIU Shaotao， YAO Canrong

(College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China)

For the searching and matching problem in multi-scale space of online detecting tracking method, a robust multi-scale tracking algorithm was proposed based on particle swarm optimization (PSO) and compress sensing. Firstly, feature was sampled with particles in multi-scale space. Then feature was extracted by compress sensing. Finally, targets would be searched quickly and robustly after calculate the best fitness and position of all the particle. The experimental results demonstrate that the proposed algorithm can adapt target in multi-scale change and has a better performance in robustness and rapidity. Keywords： visual tracking; compress sensing; particle swarm optimization; multi-scale

10.11830/ISSN.1000-5013.201701024

2015-06-02

劉韶濤(1969-)，男，副教授，主要從事軟件體系結(jié)構(gòu)的研究.E-mail:shaotaol@hqu.edu.cn.

國(guó)務(wù)院僑辦科研基金資助項(xiàng)目(09QZR02)

TP 391.3

A

1000-5013(2017)01-0121-06