姜明新,王洪玉,邱天爽
(1.大連理工大學(xué) 電子信息與電氣工程學(xué)部,遼寧 大連 116024;2.大連民族學(xué)院 信息與通信工程學(xué)院,遼寧 大連 116600)
多目標(biāo)跟蹤是計(jì)算機(jī)視覺領(lǐng)域的一個(gè)熱點(diǎn)研究問題,是運(yùn)動(dòng)目標(biāo)行為理解的前提和基礎(chǔ),在機(jī)器人導(dǎo)航、視頻理解、智能監(jiān)控等領(lǐng)域都有著廣泛的應(yīng)用[1-3].多目標(biāo)跟蹤的實(shí)現(xiàn)存在很多難點(diǎn),比如在擁擠的環(huán)境里,目標(biāo)的進(jìn)入和離開,目標(biāo)之間的嚴(yán)重遮擋等.
近些年來,國(guó)內(nèi)外許多學(xué)者關(guān)注基于視頻的多目標(biāo)跟蹤問題,所提出的算法包括點(diǎn)跟蹤、核跟蹤和輪廓跟蹤三大類.
點(diǎn)跟蹤也稱為基于檢測(cè)的跟蹤,利用有效的技術(shù)將運(yùn)動(dòng)目標(biāo)檢測(cè)出來,然后再進(jìn)行跟蹤.跟蹤部分的實(shí)現(xiàn)可以分為確定性方法和概率方法.確定性方法是利用目標(biāo)和觀測(cè)之間某種特征的距離來實(shí)現(xiàn)跟蹤,特征通常選用位置、顏色、形狀等.由于目標(biāo)檢測(cè)獲得的觀測(cè)常常含有噪聲,概率方法考慮了這些不確定性因素,所以得到了更為普遍的應(yīng)用,比如卡爾曼濾波[4]、粒子濾波[5]等技術(shù).點(diǎn)跟蹤能夠處理新目標(biāo)的進(jìn)入和原有目標(biāo)的離開,但檢測(cè)的質(zhì)量直接影響跟蹤的結(jié)果,只能用矩形框、橢圓等來描述跟蹤的結(jié)果,無法準(zhǔn)確地描述出目標(biāo)的輪廓.
核跟蹤也稱為基于分布的跟蹤,跟蹤之前手動(dòng)選擇參考目標(biāo),利用當(dāng)前幀和參考幀的一些特征分布來實(shí)現(xiàn)跟蹤.較為常見的方法有KLT特征點(diǎn)跟蹤算法[6]和 Comaniciu等提出的meanshift跟蹤算法[7].核跟蹤計(jì)算量小,具有較好的實(shí)時(shí)性,但無法處理目標(biāo)的進(jìn)入和離開,當(dāng)多目標(biāo)之間發(fā)生遮擋時(shí)跟蹤的失敗率較高.
輪廓跟蹤也稱為基于動(dòng)態(tài)分割的跟蹤,這種方法能夠在連續(xù)的每一幀中分割多個(gè)目標(biāo),并且可以描述出每個(gè)目標(biāo)的詳細(xì)輪廓.利用圖割理論[8]實(shí)現(xiàn)輪廓跟蹤是一種比較有效的方法,這種方法求解全局最小時(shí)不需要先獲得局部最小和全局模型的先驗(yàn)知識(shí),優(yōu)化過程收斂快,計(jì)算代價(jià)低,而且能夠處理多個(gè)目標(biāo)相互融合/分離(fusion/split)的拓?fù)渥兓?輪廓跟蹤的缺點(diǎn)是無法處理新目標(biāo)的進(jìn)入和原目標(biāo)的離開.
通過以上對(duì)不同跟蹤方法的分析,本文提出一種基于運(yùn)動(dòng)目標(biāo)檢測(cè)和圖割理論的多目標(biāo)跟蹤算法.首先采用碼本模型進(jìn)行背景建模,檢測(cè)出運(yùn)動(dòng)目標(biāo);然后,利用圖割理論構(gòu)建網(wǎng)絡(luò)圖,建立能量方程;最后,利用最大流-最小割算法實(shí)現(xiàn)能量方程的最小化,進(jìn)而實(shí)現(xiàn)對(duì)多目標(biāo)的跟蹤.
碼本模型是由Kim 等[9]提出的,該算法抗干擾能力強(qiáng),能夠有效地克服陰影和空洞的問題,計(jì)算復(fù)雜度小,適合做實(shí)時(shí)檢測(cè).利用文獻(xiàn)[9]獲得碼本后,檢測(cè)前景似然信息的過程如下:
假設(shè)目標(biāo)檢測(cè)過程中新輸入像素為xi=(R,G,B),其對(duì)應(yīng)的碼本為M.減背景操作BGS(xi)可以大致分為三步:
步驟1 計(jì)算當(dāng)前像素的亮度I=R+G+B,定義布爾變量match=0,并給閾值變量ε賦值.
步驟2 根據(jù)以下兩個(gè)條件從碼本M中找出與當(dāng)前像素相匹配的碼字Cm,如果能夠找到碼字Cm,則match=1,否則,match=0.
為了判斷前景和背景,運(yùn)動(dòng)目標(biāo)檢測(cè)中亮度變化有一個(gè)范圍,對(duì)于每個(gè)碼字,其范圍為[Ilow,Ihi].亮度函數(shù)的定義為
步驟3 判斷前景運(yùn)動(dòng)目標(biāo)像素:
圖割是圖論中一種關(guān)于網(wǎng)絡(luò)流的算法[10-11],是一種基于圖論的組合優(yōu)化技術(shù),用來最小化計(jì)算機(jī)視覺中的能量函數(shù)問題.由于網(wǎng)絡(luò)圖相比于向量、表、堆棧等數(shù)據(jù)結(jié)構(gòu),具有表示直觀、能夠處理非線性問題等優(yōu)點(diǎn),因此,在計(jì)算機(jī)視覺領(lǐng)域中被廣泛應(yīng)用.
在多目標(biāo)跟蹤的領(lǐng)域里,可以將監(jiān)控視頻圖像映射成一個(gè)網(wǎng)絡(luò)圖,建立一個(gè)關(guān)于目標(biāo)像素標(biāo)號(hào)的能量函數(shù),通過最大流-最小割算法實(shí)現(xiàn)能量函數(shù)最小化,求出對(duì)應(yīng)的最小割,從而給不同的像素賦予不同的標(biāo)簽,實(shí)現(xiàn)多目標(biāo)跟蹤的目的.由于圖割算法是在全局最優(yōu)的框架下進(jìn)行分割,可以保證能量函數(shù)的解收斂到全局最小.
假設(shè)t時(shí)刻圖像中的像素p用特征向量zt(p)來描述:
式中:zct(p)表示像素點(diǎn)的顏色信息,是一個(gè)YUV顏色空間的三維向量;zmt(p)表示像素點(diǎn)的運(yùn)動(dòng)信息,是一個(gè)二維的光流向量.
如果在t時(shí)刻有kt個(gè)目標(biāo)被跟蹤,其中第i個(gè)目標(biāo)用Oit表示,在視頻圖像中,目標(biāo)可以看作是多個(gè)像素組成的模板.針對(duì)目標(biāo)i來說,視頻圖像中的像素點(diǎn)不屬于該目標(biāo),則看作背景,用包含運(yùn)動(dòng)信息和顏色信息的概率分布來表示像素點(diǎn)屬于目標(biāo)還是背景.
t時(shí)刻屬于目標(biāo)i的像素點(diǎn)的概率分布用lit來表示,對(duì)應(yīng)的特征向量為由于運(yùn)動(dòng)信息和顏色信息是相互獨(dú)立的,lit可以分解為lit,c(對(duì) 應(yīng)的特 征向量 為(對(duì)應(yīng)的特征向量為屬于目標(biāo)i的像素點(diǎn)的概率分布lit的數(shù)學(xué)表達(dá)式為
同理,t時(shí)刻屬于背景的像素點(diǎn)的概率分布qit(對(duì)應(yīng)的特征向量為可以表示為
目標(biāo)跟蹤的任務(wù)是根據(jù)t-1時(shí)刻的目標(biāo)利用圖割算法得到t時(shí)刻的目標(biāo)Oit.
如果t時(shí)刻共有mt個(gè)觀測(cè),第j個(gè)觀測(cè)用Mjt表示,Mjt也可以看作是一些像素組成的集合.假設(shè)t時(shí)刻屬于觀測(cè)j的像素點(diǎn)的概率分布用ρjt來表示,則ρjt的數(shù)學(xué)表達(dá)式為
假設(shè)由t-1時(shí)刻的目標(biāo)Oit-1預(yù)測(cè)的t時(shí)刻的目標(biāo)為P,用dit-1表示t-1時(shí)刻目標(biāo)i中所有像素點(diǎn)光流向量的均值,即:
中的每一個(gè)像素利用平均光流向量可以預(yù)測(cè)得到t時(shí)刻的目標(biāo)為:
利用t-1時(shí)刻的預(yù)測(cè)、t時(shí)刻得到的新的觀測(cè)值和目標(biāo)像素的概率分布建立能量方程,通過最大流-最小割算法進(jìn)行能量函數(shù)最小化,實(shí)現(xiàn)對(duì)多目標(biāo)的跟蹤.基于圖割理論的多目標(biāo)跟蹤算法流程圖如圖1所示.
圖1 基于圖割理論的多目標(biāo)跟蹤算法流程圖Fig.1 Flowchart of the multi-target tracking algorithm based on graph cuts
假設(shè)t時(shí)刻的無向網(wǎng)絡(luò)圖為Gt=〈Vt,Et〉,其中Vt為t時(shí)刻的點(diǎn)集,Et為t時(shí)刻的邊集.點(diǎn)集Vt由兩個(gè)子集組成:第一個(gè)子集是N個(gè)像素的集合P,第二個(gè)子集是觀測(cè)子集.每一個(gè)觀測(cè)Mjt對(duì)應(yīng)一個(gè)節(jié)點(diǎn)njt,稱這些節(jié)點(diǎn)為觀測(cè)節(jié)點(diǎn),因此,點(diǎn)集Vt=P∪{njt,j=1,2,…,mt},邊集Et也可以分解 為想要將目標(biāo)i從視頻圖像中分割出來,就意味著給圖中的每個(gè)像素p賦予標(biāo)簽值fip,t,由于針對(duì)每一個(gè)目標(biāo)構(gòu)建一個(gè)無向網(wǎng)絡(luò)圖,fip,t對(duì)于一個(gè)像素點(diǎn)來說不是背景就是目標(biāo).想要將觀測(cè)和目標(biāo)建立起聯(lián)系,就意味著給每一個(gè)觀測(cè)節(jié)點(diǎn)njt賦予二值標(biāo)簽fij,t.t時(shí)刻,所有的節(jié)點(diǎn)標(biāo)簽值組成一個(gè)標(biāo)簽值集合Lit.
多目標(biāo)跟蹤算法的無向網(wǎng)絡(luò)圖如圖2所示.圖2(a)表示t-1時(shí)刻能量最小化的結(jié)果,其中白色節(jié)點(diǎn)的標(biāo)簽值為目標(biāo),黑色節(jié)點(diǎn)的標(biāo)簽值為背景.箭頭表示目標(biāo)的光流向量.圖2(b)是t時(shí)刻關(guān)于目標(biāo)i的網(wǎng)絡(luò)圖,圖中有兩個(gè)觀測(cè)節(jié)點(diǎn)n1t和n2t,用粗線圈上的像素點(diǎn)分別屬于這兩個(gè)觀測(cè).虛線框住的像素點(diǎn)是根據(jù)上一時(shí)刻目標(biāo)像素點(diǎn)的光流向量得到的本幀的預(yù)測(cè)值
t時(shí)刻,針對(duì)目標(biāo)i建立能量方程,能量方程由一元數(shù)據(jù)項(xiàng)和二元平滑項(xiàng)組成:
其中數(shù)據(jù)項(xiàng)為
圖2 多目標(biāo)跟蹤算法的無向網(wǎng)絡(luò)圖Fig.2 The undirected graph of the multi-target tracking algorithm
式(12)中,利用t-1時(shí)刻的跟蹤結(jié)果得到的t時(shí)刻的預(yù)測(cè)區(qū)域的似然函數(shù)l1的表達(dá)式為
其中“ob”表示像素的標(biāo)簽值為目標(biāo),“bg”表示像素的標(biāo)簽值為背景.
式(12)中,d2(j,fp,t)似然函數(shù)的數(shù)學(xué)表達(dá)式為
為了估計(jì)t-1時(shí)刻的目標(biāo)跟蹤結(jié)果i和t時(shí)刻的.觀測(cè)j之間的相似度,利用式(14)計(jì)算t-1時(shí)刻目標(biāo)i的概率分布lit-1和t時(shí)刻觀測(cè)j的概率分布ρjt之間的距離.本文采用Kullback-Lerbler距離,簡(jiǎn)稱KL距離
式(12)中的常數(shù)α是控制觀測(cè)對(duì)數(shù)據(jù)項(xiàng)的影響程度的,本文中,令α等于觀測(cè)Mjt的像素?cái)?shù)目.
式(11)中的平滑項(xiàng)B{p,q},t的設(shè)計(jì)基于相鄰像素{p,q}的顏色梯度信息,具體表達(dá)式為
其中σT=4〈(Zct(p)-Zct(q))2〉,式中的〈·〉表示目標(biāo)區(qū)域的均值.
能量方程式(11)建立后,利用α擴(kuò)展法進(jìn)行最小化,求得像素的標(biāo)簽值,可得
則t時(shí)刻的目標(biāo)i為
選用多組實(shí)驗(yàn)視頻進(jìn)行測(cè)試,驗(yàn)證本文提出的基于目標(biāo)檢測(cè)和圖割的多目標(biāo)跟蹤算法的魯棒性,限于篇幅,本文只列出部分實(shí)驗(yàn)結(jié)果.利用Windows 7操作系統(tǒng)來實(shí)現(xiàn)多目標(biāo)跟蹤算法,采用Visual Studio 2010結(jié)合OpenCV 2.2作為軟件平臺(tái),計(jì)算機(jī)配置為Pentium(R)Dual-Core CPU 2.0GHz.
首先,需要利用運(yùn)動(dòng)目標(biāo)檢測(cè)算法來獲得觀測(cè)值,實(shí)驗(yàn)結(jié)果如圖3所示.圖3(a)和(c)表示監(jiān)控視頻中任意兩幀原始視頻圖像,圖3(b)和(d)是利用碼本模型獲得的觀測(cè)值.
從圖3(d)的結(jié)果可以看出,當(dāng)視頻中左側(cè)的兩個(gè)目標(biāo)之間發(fā)生遮擋時(shí),通過運(yùn)動(dòng)目標(biāo)檢測(cè)得到的觀測(cè)是兩個(gè)目標(biāo)共同組成的前景.所以,需要考慮預(yù)測(cè)信息和上一幀目標(biāo)的概率分布,結(jié)合新得到的觀測(cè),來共同構(gòu)建能量方程和網(wǎng)絡(luò)圖.利用圖割理論進(jìn)行多目標(biāo)跟蹤的實(shí)驗(yàn)結(jié)果如圖4所示.
圖3 利用碼本模型獲得的觀測(cè)值Fig.3 The result of the observation obtained using codebook model
在這組實(shí)驗(yàn)視頻中,多個(gè)目標(biāo)之間發(fā)生了相互遮擋,圖4(a)和(b)中目標(biāo)1和目標(biāo)3發(fā)生了遮擋,圖4(c)和(d)中目標(biāo)1和目標(biāo)4發(fā)生了遮擋,實(shí)驗(yàn)視頻中的目標(biāo)4是新進(jìn)入的目標(biāo).
圖4 多目標(biāo)跟蹤算法的實(shí)驗(yàn)結(jié)果Fig.4 The experimental result of the multi-target tracking algorithm
為了更直觀地表示給每個(gè)像素賦予標(biāo)簽值的效果,將屬于同一個(gè)目標(biāo)的像素點(diǎn)賦予了同一種顏色,然后,再用矩形框表示跟蹤結(jié)果.從實(shí)驗(yàn)結(jié)果可以看出,提出的多目標(biāo)跟蹤算法,對(duì)多目標(biāo)之間的遮擋和多目標(biāo)的數(shù)目變化具有較強(qiáng)的魯棒性.
為了驗(yàn)證本文提出算法在跟蹤準(zhǔn)確率方面的優(yōu)勢(shì),針對(duì)上述實(shí)驗(yàn)視頻進(jìn)行了跟蹤準(zhǔn)確率數(shù)據(jù)統(tǒng)計(jì),并且與粒子濾波算法進(jìn)行了對(duì)比,實(shí)驗(yàn)對(duì)比數(shù)據(jù)如表1所示.
表1 跟蹤準(zhǔn)確率對(duì)比Tab.1 The comparison of tracking accuracy
本文在分析各種跟蹤方法的基礎(chǔ)上,結(jié)合點(diǎn)跟蹤和輪廓跟蹤的優(yōu)勢(shì),提出了一種基于運(yùn)動(dòng)目標(biāo)檢測(cè)和圖割理論的多目標(biāo)跟蹤算法,將多目標(biāo)跟蹤問題轉(zhuǎn)化為能量最小化問題,給像素賦予標(biāo)簽,根據(jù)圖割理論建立能量方程,構(gòu)造網(wǎng)絡(luò)圖,利用最大流-最小割算法實(shí)現(xiàn)能量方程的最小化,進(jìn)而完成對(duì)多目標(biāo)的跟蹤.實(shí)驗(yàn)結(jié)果表明,該算法對(duì)多目標(biāo)的數(shù)目變化和遮擋具有較強(qiáng)的魯棒性.
[1] 姜明新,王洪玉,劉曉凱.基于多相機(jī)的多目標(biāo)跟蹤算法[J].自動(dòng)化學(xué)報(bào),2012,38(4):497-506.JIANG Ming-xin,WANG Hong-yu,LIU Xiao-kai.A multi-target tracking algorithm based on multiple cameras[J].Acta Automatica Sinica,2012,38(4):497-506.(in Chinese)
[2] Yilmaz A,Javed O,Shah M.Object tracking:A survey[J].ACM Computing Surveys,2006,38(4):229-240.
[3] 姜明新,王洪玉.基于多層定位的多目標(biāo)跟蹤算法[J].大連理工大學(xué)學(xué)報(bào),2012,52(5):767-771.JIANG Ming-xin,WANG Hong-yu.Tracking algorithm of multi-object based on localizing at multiple planes[J].Journal of Dalian University of Technology,2012,52(5):767-771.(in Chinese)
[4] HAN Zhen-jun,JIAO Jian-bin,ZHANG Baochang,etal.Visual object tracking via samplebased adaptive sparse representation [J].Pattern Recognition,2011,44(9):2170-2183.
[5] Mei X,Ling H.Robust visual tracking and vehicle classification via sparse representation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(11):2259-2272.
[6] Shi J,Tomasi C.Good features to track [C]//Proceedings of the 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE,1994.
[7] Comaniciu D,Ramesh V,Meer P.Kernel-based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(5):564-577.
[8] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(11):1222-1239.
[9] Kim K,Chalidabhongse T H,Harwood D,etal.Real-time foreground-background segmentation using codebook model [J].Real-Time Imaging,2005,11(3):172-185.
[10] Ford L R,F(xiàn)ulkerson D R.Flows in Networks[M].New Jersey:Princeton University Press,1962.
[11] Boykov Y,Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1124-1137.