一種基于稀疏表達(dá)和光流的目標(biāo)跟蹤方法

牛一捷

(大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028)*

0 引言

隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，計(jì)算機(jī)視覺研究領(lǐng)域受到了越來越多研究者的關(guān)注.目標(biāo)跟蹤是其中備受關(guān)注的前沿方向，在人機(jī)交互、安全監(jiān)控、虛擬現(xiàn)實(shí)、醫(yī)學(xué)、體育等方面都有廣泛應(yīng)用.雖然已經(jīng)取得了一些進(jìn)展，但到目前為止還沒有一個(gè)通用算法適用于所有問題.這是因?yàn)槟繕?biāo)跟蹤問題受到多種因素影響，如:內(nèi)在因素包括目標(biāo)物體位置、形狀和尺度的變化等;外在因素包括光照變化，攝像機(jī)運(yùn)動(dòng)及視角轉(zhuǎn)換，遮擋、復(fù)雜背景等.

傳統(tǒng)的經(jīng)典目標(biāo)跟蹤方法有:光流法［1］、meanshift、kalman、粒子濾波.這些算法的準(zhǔn)確率較低，表現(xiàn)為跟蹤目標(biāo)易發(fā)生漂移并很快中斷跟蹤任務(wù).近年來，隨著模式識別技術(shù)的發(fā)展，研究人員開始將跟蹤問題看成目標(biāo)檢測、目標(biāo)識別等模式識別問題，提出了很多算法，其中最具有代表性的有:Online Adaboost［2］，BeSemiT［3］，TLD［4］等.這類方法在實(shí)際應(yīng)用中跟蹤的準(zhǔn)確率較高，但是需要提前學(xué)習(xí)并且在新的一幀到來時(shí)需要進(jìn)行大量的識別操作，對于對實(shí)時(shí)性要求比較高的跟蹤問題來說是一個(gè)瓶頸問題.

本文鑒于上面兩類算法的優(yōu)缺點(diǎn)，提出一種光流算法和稀疏表達(dá)技術(shù)相結(jié)合的新算法(SROF).不僅能夠較好的避免發(fā)生漂移和跟蹤任務(wù)突然中斷問題，而且算法的準(zhǔn)確性也得到了很大的提高.

1 傳統(tǒng)光流算法

光流的概念是Gibson在1950年首先提出來的.后來將光流法應(yīng)用于跟蹤問題，即利用圖像像素點(diǎn)在時(shí)間域上的變化以及相鄰幀之間的相關(guān)性來進(jìn)而推斷出跟蹤目標(biāo)在新一幀速度及方向的方法.根據(jù)選取像素點(diǎn)的數(shù)量，分為稠密光流和稀疏光流.稠密光流是圖像中的每個(gè)像素點(diǎn)均參與運(yùn)算，計(jì)算開銷較大.稀疏光流僅由一組選定的像素點(diǎn)參與運(yùn)算，因此在實(shí)際應(yīng)用中較多地使用稀疏光流法.目前應(yīng)用廣泛的是 Bruce D.Lucas和Takeo Kanade在1981年提出的 Lucas-Kanade(LK)算法［1］，本文也基于這個(gè)算法.本算法基于三點(diǎn)假設(shè).

(1)亮度恒定，像素在幀間運(yùn)動(dòng)時(shí)，像素值保持不變:

(2)圖像的變化相對于時(shí)間的變化微小，對圖像約束方程使用泰勒公式展開，可以得到:

這個(gè)方程中，Ix，Iy是二維圖像的偏導(dǎo)數(shù)，It是圖像隨時(shí)間的導(dǎo)數(shù)，u和v是所要求的速度在x，y方向分量，但目前對于單個(gè)像素，無解，于是有了第三個(gè)假設(shè).

2 稀疏表達(dá)技術(shù)

稀疏表達(dá)技術(shù)是用比香農(nóng)定律更低的采樣率來表示和壓縮信號.Mei，X.and H.Ling等將其引入到視頻目標(biāo)跟蹤這一領(lǐng)域中［9-11］.

稀疏表達(dá)的核心理論可以理解為在一組過完備基A∈Rd×n(使用n維傳感器經(jīng)d次觀測得到的某個(gè)信號的觀測值)下，重構(gòu)某個(gè)信號y.稀疏表達(dá)要求對信號y∈Rd的重構(gòu)系數(shù)向量x∈Rn盡可能地稀疏，轉(zhuǎn)化為如下最小化問題:

但上述I0－范數(shù)最小化問題是NP-hard問題，計(jì)算率極低.Tao等人在式(5)基礎(chǔ)上證明了:在滿足約束等距性(restricted isometry property，RIP)條件下，如下的I1－范數(shù)最小化問題是式(5)的I0－范數(shù)最小化問題的最緊表示［10］:

這是一個(gè)凸優(yōu)化問題，其求解效率要比式(5)高得多.再引入觀測噪聲，上述最優(yōu)化問題可以松弛化表示為:

對于上述最優(yōu)化問題，有許多方法能夠有效地求解，包括貪婪算法、L1最小化、LASSO，本文利用LASSO算法.

3 仿射變換區(qū)域的生成

4 SROF算法

SROF算法的基本思路是:將目標(biāo)跟蹤任務(wù)分為兩階段:粗略定位和精確定位.第一階段粗略定位，主體思想為光流算法.第二階段精確定位，主體思想為模式識別思想.具體的算法流程如下:

(1)初始化

(a)在視頻的第一幀中初始化跟蹤目標(biāo)，并提取正負(fù)樣本;

(b)用顏色特征表示正負(fù)樣本，利用稀疏表達(dá)技術(shù)提取原始目標(biāo)關(guān)鍵特征.

(2)實(shí)時(shí)追蹤

for T=2，3，… ，t(t為視頻序列總幀數(shù))

①粗略定位:

(a)聯(lián)合 Harris和FAST算法檢測出的特征點(diǎn)和等間距像素點(diǎn)組成光流算法像素點(diǎn)集O.

(b)采用后向跟蹤－形心配準(zhǔn)的方法，為跟蹤目標(biāo)在新一幀中計(jì)算粗略定位區(qū)域.

②準(zhǔn)確定位:

(a)對粗略定位區(qū)域根據(jù)仿射變換法建立一組目標(biāo)候選區(qū)域.

(b)用顏色特征表示每個(gè)候選區(qū)域，利用稀疏表達(dá)技術(shù)計(jì)算每個(gè)候選區(qū)域與初始目標(biāo)的正負(fù)樣本的相似度比率，最終確定目標(biāo)的準(zhǔn)確位置.

該算法關(guān)鍵技術(shù)分析:

(1)光流算法特征點(diǎn)選定

在稀疏光流算法中像素點(diǎn)的選取很重要，通常的算法是選取跟蹤目標(biāo)區(qū)域內(nèi)的等間隔像素點(diǎn)集.這樣選取的像素點(diǎn)不能代表跟蹤目標(biāo)的特點(diǎn).本文在等間隔選取像素點(diǎn)的基礎(chǔ)上添加上角點(diǎn).角點(diǎn)是圖像亮度發(fā)生劇烈變化或圖像邊緣曲線上曲率最大值的點(diǎn).常用的角點(diǎn)檢測方法有:Moravec、Harris［5］，SUSAN，F(xiàn)AST［6］，SIFT 等.

本文選擇經(jīng)典的Harris和FAST來共同完成光流特征點(diǎn)的選定.FAST角點(diǎn)檢測算法是目前為止速度最快的角點(diǎn)選取算法.FAST算法原理:檢測候選特征點(diǎn)周圍一圈的像素值，如果候選點(diǎn)周圍領(lǐng)域內(nèi)有足夠多的像素點(diǎn)與該候選點(diǎn)的灰度值差別夠大，則認(rèn)為該候選點(diǎn)為一個(gè)特征點(diǎn).Harris角點(diǎn)檢測算法是 Moravec角點(diǎn)檢測算子的擴(kuò)展.它的基本原理:當(dāng)一個(gè)窗口在圖像上移動(dòng)，在平滑區(qū)域，窗口在各個(gè)方向上沒有變化.窗口在邊緣的方向上沒有變化.但在角點(diǎn)處，窗口在各個(gè)方向上具有變化.Harris角點(diǎn)檢測正是利用了這個(gè)直觀的物理現(xiàn)象，通過窗口在各個(gè)方向上的變化程度，決定是否為角點(diǎn).

(2)粗略定位

傳統(tǒng)光流法的前提假設(shè)條件過多不適于實(shí)際的目標(biāo)跟蹤算法.具體的表現(xiàn)就是跟蹤的準(zhǔn)確性不高，在跟蹤目標(biāo)的過程中很快就會(huì)出現(xiàn)目標(biāo)丟失的現(xiàn)象，而且無法重新找回跟蹤目標(biāo)，整個(gè)跟蹤過程失敗.因此，為了提高算法的準(zhǔn)確性，采用后向跟蹤－形心配準(zhǔn)的方法［7］.具體算法:用(1)中產(chǎn)生的聯(lián)合特征點(diǎn)集O應(yīng)用到光流算法，之后得到在下一幀中對應(yīng)的一組像素點(diǎn)集M.采用相同的光流方法，前后兩幀對調(diào)，在上一幀中找到點(diǎn)集M對應(yīng)的點(diǎn)集Q.計(jì)算O點(diǎn)集和Q點(diǎn)集對應(yīng)點(diǎn)的歐式距離，把距離大于點(diǎn)集M，Q中所有對應(yīng)兩點(diǎn)之間平均距離的點(diǎn)舍棄.利用剩余點(diǎn)前后幀之間的位置偏移來計(jì)算跟蹤目標(biāo)的所在位置.

(3)原始跟蹤目標(biāo)關(guān)鍵特征提取

第一階段已經(jīng)得到了跟蹤目標(biāo)的粗略位置，接下來要應(yīng)用模式識別的思想，對跟蹤目標(biāo)進(jìn)行精確定位.首先要根據(jù)原始跟蹤目標(biāo)選取正負(fù)樣本.為了考慮到跟蹤目標(biāo)可能的變化，對初始跟蹤目標(biāo)區(qū)域(圖1(a)中間方框)，根據(jù)3中仿射變換方法建立正樣本Np.選取跟蹤目標(biāo)區(qū)域外圍有部分重疊的部分(圖1(b)沿著大方框邊緣，移動(dòng)紅色方框一圈，且紅色方框和中間的目標(biāo)方框相同大小)建立負(fù)樣本.正負(fù)樣本Nn記錄了初始跟蹤目標(biāo)特征.負(fù)樣本記錄了背景特征.

圖1 正負(fù)樣本選取示意圖

正負(fù)樣本都用顏色直方圖表示.顏色特征是一種全局特征，即以整個(gè)圖像為單位提取的特征，如:顏色、紋理等.本文使用顏色直方圖，它是不同色彩在整幅圖像中所占的比例.對于RGB圖像在每個(gè)通道上，共有256個(gè)取值，那么一副圖像就共有256×3個(gè)取值.一個(gè)樣本表示為一個(gè)列向量，列向量為768×1.但是這些取值中存在大量的冗余信息，這些冗余信息會(huì)干擾到目標(biāo)的正確識別.通?？梢圆捎媒稻S的方法進(jìn)行處理，如PCA或稀疏表達(dá).本文采用稀疏表達(dá)方法來提取關(guān)鍵特征維.

根據(jù)2的理論分析，將稀疏表示問題可描述為如下LASSO最小化問題:

(4)精確定位

對粗略定位區(qū)域利用3中的仿射變換技術(shù)建立一組候選區(qū)域，由于候選區(qū)域越多算法準(zhǔn)確率越高，但算法效率將受到影響.本文的策略是當(dāng)上一幀置信度比較小時(shí)，本次仿射候選區(qū)域成倍增加，以便獲得更好的跟蹤區(qū)域，提高算法準(zhǔn)確率.再次利用稀疏表達(dá)方法，完成精確定位.對于每一個(gè)候選區(qū)域同樣用768維的顏色直方圖表示，所有候選區(qū)域組成矩陣P.用(3)得到的x，對P進(jìn)行簡化，y=Px.接著對(3)中A矩陣簡化，即A=Ax.將簡化后的y，A代入式(9).利用 LASSO計(jì)算新的，此處的表示每個(gè)候選樣本可以由A中正負(fù)樣本中的哪些關(guān)鍵樣本表示.

最后根據(jù)x'，計(jì)算每個(gè)候選樣本的關(guān)鍵樣本表示中正負(fù)樣本所在比例來最終確定哪個(gè)候選樣本為最終跟蹤目標(biāo).具體計(jì)算公式為式(10)～(12)這里的Ap，An分別表示A中對應(yīng)正負(fù)樣本子集，x'p，x'n，分別表示對應(yīng)正負(fù)樣本子集的那部分元素子集.recP，recN表示計(jì)算每一個(gè)候選區(qū)域如果只用正樣本和負(fù)樣本表示的誤差，最后用式(12)計(jì)算出每個(gè)候選樣本和正負(fù)樣本之間的誤差比率，選取值最大的那個(gè)候選區(qū)域?yàn)樽罱K跟蹤目標(biāo)區(qū)域，r的經(jīng)驗(yàn)值取0.4.

5 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)環(huán)境為:CPU:Intel(R)Core(TM)i3-2350M 2.30GHz，內(nèi)存:2GB，顯存 512MB，操作系統(tǒng)為win7，仿真軟件為Matlab(R2012b).

使用faceocc2數(shù)據(jù)集，這個(gè)數(shù)據(jù)集中包含了嚴(yán)重遮擋、目標(biāo)物體位置、形狀和尺度的變化等在實(shí)際目標(biāo)跟蹤過程中常遇到的難題.數(shù)據(jù)集中圖像大小為320×240，共819幀.

為了比較，在faceocc2數(shù)據(jù)集上除了運(yùn)行本文算法SROF外，還運(yùn)行了三個(gè)目前最具代表性的算法:BoostT、BeSemiT和TLD.

測試參數(shù)的選定:算法初始化時(shí)，選取正樣本Np為50個(gè)，負(fù)樣本Nn為200個(gè).精確定位中，仿射候選樣本的選定，本文選定置信度大于0.9，選取100個(gè)候選區(qū)域，0.9～0.8之間，選定 200個(gè)候選區(qū)域，其他選定300個(gè)候選區(qū)域.式(9)用于生成原始跟蹤目標(biāo)關(guān)鍵特征時(shí)，λ=0.001.式(9)用于精確定位時(shí)，λ=0.01.本文具體數(shù)值的選定皆是經(jīng)驗(yàn)值.

圖2是BoosterT、BeSemiT、SROF四個(gè)算法的跟蹤結(jié)果對比圖.圖3是中心位置誤差對比圖，通過計(jì)算每一幀手工標(biāo)定的實(shí)際目標(biāo)中心點(diǎn)坐標(biāo)和四個(gè)算法在每一幀的跟蹤結(jié)果中心點(diǎn)坐標(biāo)之間的歐式距離得到該圖.

圖2 跟蹤結(jié)果對比圖

根據(jù)圖2，對實(shí)驗(yàn)結(jié)果分析如下:

當(dāng)目標(biāo)發(fā)生部分遮擋時(shí)，如165幀，當(dāng)目標(biāo)位置發(fā)生變化時(shí)，如399幀，除了BeSemiT發(fā)生了嚴(yán)重偏移，其余三個(gè)算法都定位出目標(biāo).當(dāng)目標(biāo)的形狀和尺度的變化時(shí)，如588幀，BeSemiT和TLD都跟丟，BoostT的跟蹤結(jié)果都發(fā)生了嚴(yán)重偏移，當(dāng)跟蹤目標(biāo)被完全遮擋時(shí)，如709幀，BeSemiT和TLD都跟丟，BoostT發(fā)生了嚴(yán)重偏移.本文算法在整個(gè)跟蹤過程中都能較準(zhǔn)確的跟蹤目標(biāo)，尤是當(dāng)目標(biāo)完全遮擋的情下還能較為準(zhǔn)確的標(biāo)定目標(biāo)位置，如709幀，但是對于復(fù)雜運(yùn)動(dòng)，如429幀，當(dāng)目標(biāo)連續(xù)出現(xiàn)偏移之后又發(fā)生遮擋的情況，本文的算法也出現(xiàn)了偏移，需要進(jìn)行改進(jìn)，另外，在429幀，只有BoostT取得了較好的跟蹤效果.根據(jù)圖3，可以發(fā)現(xiàn)本文SROF算法在整個(gè)跟蹤過程中穩(wěn)定地保持著較高的準(zhǔn)確性.

圖3 中心位置誤差對比圖

6 結(jié)論

本文實(shí)現(xiàn)了一個(gè)新的目標(biāo)跟蹤算法.在整個(gè)算法框架上，本文將傳統(tǒng)光流跟蹤算法和模式識別思想相結(jié)合，采用兩階段跟蹤目標(biāo)定位的思路，最終確定出準(zhǔn)確的目標(biāo)跟蹤區(qū)域.在目標(biāo)區(qū)域的表示上，本文用到了全局顏色特征和局部角點(diǎn)特征，從不同角度描述目標(biāo)，提高了算法的準(zhǔn)確率.最重要的是將近年來較為流行的稀疏表達(dá)技術(shù)應(yīng)用到了算法中，不僅用以清除目標(biāo)表示的冗余信息，而且用于最終在一組候選樣本中識別出最為準(zhǔn)確的目標(biāo)跟蹤區(qū)域.雖然經(jīng)實(shí)驗(yàn)證明本算法和目前較為流行的算法性能相當(dāng)，甚至在有些情況下優(yōu)于這些算法.但本文在一些環(huán)境條件下，準(zhǔn)確率較低，還需要針對這些情況，提高算法的適應(yīng)性和準(zhǔn)確性.

［1］Lucas B D，Kanade T.An iterative image registration technique with an application to stereo vision［C］//IJCAI，1981，81:674-679.

［2］Grabner H，Bischof H.On-line boosting and vision［C］//Computer Vision and Pattern Recognition，2006 IEEE Computer Society Conference on IEEE，2006，1:260-267.

［3］Stalder S，Grabner H，Van Gool L.Beyond semi-supervised tracking:Tracking should be as simple as detection，but not simpler than recognition［C］//Computer Vision Workshops(ICCV Workshops)，2009 IEEE 12th International Conference on IEEE，2009:1409-1416.

［4］Kalal Z，Mikolajczyk K，Matas J.Forward-backward error:Automatic detection of tracking failures［C］//Pattern Recognition(ICPR)，2010 20th International Conference on IEEE，2010:2756-2759.

［5］Harris C，Stephens M.A combined corner and edge detector［C］//Alvey vision conference，1988，15:50.

［6］Rosten E，Drummond T.Machine learning for highspeed corner detection［C］//Computer Vision– ECCV 2006.Springer Berlin Heidelberg，2006:430-443.

［7］彭寧嵩.Mean—shift可視跟蹤中的穩(wěn)健性研究［D］.上海:上海交通大學(xué)，2005.

［8］Ross D A，Lim J，Lin R S，et al.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77(1-3):125-141.

［9］Mei X，Ling H.Robust visual tracking using minimization［C］//Computer Vision，2009 IEEE 12th International Conference on IEEE，2009:1436-1443.

［10］Candès E J，Romberg J，Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information［J］.Information Theory，IEEE Transactions on，2006，52(2):489-509.

［11］Zhong W，Lu H，Yang M H.Robust object tracking via sparsity-based collaborative model［C］//Computer Vision and Pattern Recognition(CVPR)，2012 IEEE Conference on IEEE，2012:1838-1845.