李 娜， 李大湘， 劉衛(wèi)華， 劉 穎

(1. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121；2. 長(zhǎng)安大學(xué) 信息工程學(xué)院, 陜西 西安 710064；3. 陜西省法庭科學(xué)電子信息實(shí)驗(yàn)研究中心 圖像處理實(shí)驗(yàn)室， 陜西 西安 710121)

基于多示例學(xué)習(xí)的目標(biāo)跟蹤算法

李 娜1,2,3， 李大湘1,3， 劉衛(wèi)華1,3， 劉 穎1,3

(1. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121；2. 長(zhǎng)安大學(xué) 信息工程學(xué)院, 陜西 西安 710064；3. 陜西省法庭科學(xué)電子信息實(shí)驗(yàn)研究中心 圖像處理實(shí)驗(yàn)室， 陜西 西安 710121)

為提高運(yùn)動(dòng)目標(biāo)跟蹤算法的魯棒性，提出一種基于多示例學(xué)習(xí)(MIL)框架的跟蹤算法。該算法利用類Haar特征構(gòu)建若干弱分類器，然后級(jí)聯(lián)為多示例學(xué)習(xí)強(qiáng)分類器，根據(jù)目標(biāo)在視頻前一幀中的位置，依據(jù)最大熵原理，在當(dāng)前幀中找出目標(biāo)可能出現(xiàn)的范圍，并利用該強(qiáng)分類器確定其最有可能出現(xiàn)的位置，作為跟蹤結(jié)果，并且將該位置不同鄰域內(nèi)的圖像分別作為正包和負(fù)包去更新多示例學(xué)習(xí)強(qiáng)分類器。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)于運(yùn)動(dòng)目標(biāo)外觀有顯著變化的情況具有較好的魯棒性和實(shí)時(shí)性。

目標(biāo)跟蹤；多示例學(xué)習(xí)；弱分類器

目標(biāo)跟蹤是計(jì)算機(jī)視覺研究的熱點(diǎn)，在視頻監(jiān)控、視頻檢索、交通監(jiān)控等領(lǐng)域都有廣泛應(yīng)用，但現(xiàn)有的部分算法往往不能有效解決照明變化、外觀變化、形狀變化和遮擋對(duì)目標(biāo)跟蹤的影響[1-3]，因此，目標(biāo)跟蹤領(lǐng)域的新思想新算法仍然層出不窮。

文[4]提出了多示例學(xué)習(xí)(Multiple instance Learning, MIL)的概念。在MIL問題中，訓(xùn)練樣本以包作為單位，包有確定標(biāo)記，而包內(nèi)示例標(biāo)記則不確定。如果包被標(biāo)記為負(fù)，則表明包中所有示例都為負(fù)示例，如果包被標(biāo)記為正，則表明包中至少有一個(gè)正示例。

針對(duì)目標(biāo)跟蹤問題，將視頻當(dāng)前幀中的圖像塊與圖像塊的集合分別看作示例和包。將包含目標(biāo)的圖像集合標(biāo)記為正包，否則標(biāo)記為負(fù)包。利用正包和負(fù)包來訓(xùn)練分類器，并以此對(duì)下一幀圖像中的目標(biāo)位置進(jìn)行預(yù)測(cè)和判斷。文[5]將多示例學(xué)習(xí)用于目標(biāo)檢測(cè)中，提高了檢測(cè)精度。文[6-8]研究了基于檢測(cè)的跟蹤方法，將多示例學(xué)習(xí)算法用于目標(biāo)跟蹤中，建立了魯棒的目標(biāo)外觀模型。多示例學(xué)習(xí)問題中，示例選擇的好壞直接影響到分類的結(jié)果，文[9]對(duì)多示例學(xué)習(xí)問題中如何選擇示例進(jìn)行了探討。

本文擬在MIL框架下，提出一種基于多示例學(xué)習(xí)框架的跟蹤算法。該算法利用類Haar特征構(gòu)建若干弱分類器，然后級(jí)聯(lián)為多示例學(xué)習(xí)強(qiáng)分類器。根據(jù)目標(biāo)在視頻前一幀中的位置，依據(jù)最大熵原理，在當(dāng)前幀中找出目標(biāo)可能出現(xiàn)的范圍，由此確定其最有可能出現(xiàn)的位置，作為跟蹤結(jié)果，并且將該位置不同鄰域內(nèi)的圖像集合分別作為正包和負(fù)包去更新強(qiáng)分類器。

1 算法描述

1.1 基于多示例學(xué)習(xí)的目標(biāo)跟蹤

算法1(基于多示例學(xué)習(xí)的跟蹤)

輸入第t-1幀中目標(biāo)所在位置坐標(biāo)、視頻第t幀;輸出第t幀中目標(biāo)所在位置坐標(biāo)，更新后的MIL分類器。

步驟1 從第t幀中找到圖像集合

其中，s為搜索半徑，l(x)為圖像塊x的位置，用目標(biāo)中心點(diǎn)坐標(biāo)(x,y)表示,Xs中的任意圖像塊與t-1幀中目標(biāo)位置的距離小于s。計(jì)算該圖像集合中每個(gè)圖像塊x的特征向量。

步驟2 使用最新的MIL分類器，計(jì)算

即找出Xs中出現(xiàn)目標(biāo)概率最大的圖像塊，并將它作為第t幀中目標(biāo)所在位置。

將Xγ作為正包，Xγ,β作為負(fù)包，對(duì)MIL分類器進(jìn)行更新。其中γ和β分別是正包、負(fù)包的選擇半徑。

在該跟蹤算法中，最重要的就是如何得到MIL分類器以及如何對(duì)其進(jìn)行更新。

1.2 在線MIL分類器

在線MIL分類器是由K個(gè)弱分類器級(jí)聯(lián)而成的。目的是要從M個(gè)弱分類器

Φ={h1,h2,…,hM}

中依次選出K個(gè)弱分類器，使其滿足

其中

(1-pi)(1-yi) log (1-pi)],

分別是包的信息熵函數(shù)和從Φ中選出的k-1個(gè)弱分類器構(gòu)成的強(qiáng)分類器。

文[7]中L取值為包的對(duì)數(shù)似然函數(shù)

(1-yi) log (1-pi)]。

考慮到最大熵原理是從符合條件的分布中選擇熵最大的分布作為最優(yōu)秀的分布，符合應(yīng)用背景，故可選擇信息熵作為目標(biāo)函數(shù)，通過求它的最大值，從而確定出最合適的弱分類器,因此，求在線MIL分類器的問題就轉(zhuǎn)化為如何求包的概率pi以及如何得到弱分類器hj(j=1,2,…,M)。

在MIL中，記訓(xùn)練集為

{(X1,y1),(X2,y2),…,(Xn,yn)},

其中

Xi={Xi1,Xi2,…,xim}

代表第i個(gè)包，xij代表第i個(gè)包中的第j個(gè)示例，yi代表第i個(gè)包的標(biāo)記(0代表負(fù)包，1代表正包)。包標(biāo)記定義為

其中yij代表第i個(gè)包中的第j個(gè)示例的標(biāo)記，在訓(xùn)練階段示例標(biāo)記是未知的。

根據(jù)文[5]，采用Noisy-OR(NOR)模型對(duì)包概率建模，即

但在求包標(biāo)記時(shí)會(huì)用到示例標(biāo)記P{yi|xij}，因此需要對(duì)示例標(biāo)記建模，即

其中H(xij)是上文提到的由K個(gè)弱分類器級(jí)聯(lián)的強(qiáng)分類器，其生成方法描述如下。

算法2(在線MIL分類器)

Xi={xi1,xi2,…,xim},yi∈{0,1};

輸出分類器

步驟2 依次遍歷M個(gè)弱分類器，用它和強(qiáng)分類器的組合，估計(jì)每個(gè)示例xij為正示例的概率

估計(jì)每個(gè)包Xi為正包的概率

計(jì)算每個(gè)包的信息熵

步驟3 從M個(gè)信息熵Lm中，選出使得Lm取得最大值的弱分類器，即

hk(xij)=hm*(xij)。

把該弱分類器添加到強(qiáng)分類器中，即

H(xij)=H(xij)+hk(xij)。若k=K，停止計(jì)算；否則令k=k+1，跳至步驟2。

1.3 弱分類器

求在線MIL分類器的問題可轉(zhuǎn)換為求弱分類器的問題。更新MIL分類器時(shí)，弱分類器也在更新。假設(shè)正包中的類Haar特征服從正態(tài)分布，即

負(fù)包中的類Haar特征服從正態(tài)分布，即

假設(shè)P{y=1}=P{y=0}，利用Bayes公式可計(jì)算求得弱分類器hk(x)，即

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

實(shí)驗(yàn)在Visual Studio 2008環(huán)境下，結(jié)合OpenCV 2.2和Intel IPP 6.1，在Pentium Dual-Core 2.93GHz CPU和2G內(nèi)存的電腦上進(jìn)行。為了驗(yàn)證新算法的有效性，將其與Online AdaBoost[10]和MIL跟蹤方法[7]，在兩個(gè)公開數(shù)據(jù)集David Indoor和Girl[11]上進(jìn)行了測(cè)試對(duì)比。Online AdaBoost方法中比較了正包搜索半徑γ=1(記為OAB1)和γ=4(記為OAB4)兩種情況。MIL和新方法中，設(shè)置正包搜索半徑γ=4，負(fù)包中包含65個(gè)圖像塊，特征池中總的特征總數(shù)M=250，待選取的特征數(shù)為K=50構(gòu)成強(qiáng)分類器，弱分類器的更新速率α=0.85。

2.1 跟蹤結(jié)果對(duì)比

David Indoor數(shù)據(jù)集的跟蹤效果如圖1所示，當(dāng)光照條件和目標(biāo)外觀發(fā)生變化(眼鏡摘掉、面部旋轉(zhuǎn))時(shí)，OAB1和OAB4方法隨著時(shí)間的推移，跟蹤效果越來越差，最后嚴(yán)重偏離了運(yùn)動(dòng)目標(biāo)。MIL方法具有較好的跟蹤效果，但從總體上看，新算法的跟蹤結(jié)果最接近目標(biāo)真實(shí)位置。

圖1 David Indoor跟蹤效果

通過計(jì)算不同方法的跟蹤結(jié)果與目標(biāo)真實(shí)位置的距離，得到了不同跟蹤方法的誤差曲線，如圖2所示。在剛開始的10幀內(nèi)，四種方法的跟蹤效果差別不大，但是隨著時(shí)間的推移，在第150幀至224幀之間以及第370幀至最后一幀，OAB1和OAB4的誤差急劇增大，跟蹤結(jié)果偏離真實(shí)目標(biāo)較遠(yuǎn)，跟蹤失敗。而MIL和新算法的誤差曲線較平穩(wěn)，但從總體上看，新算法的平均誤差更小。

圖2 David Indoor誤差曲線

四種方法跟蹤結(jié)果的誤差最大值、誤差均值以及誤差標(biāo)準(zhǔn)差如表1所示，新算法產(chǎn)生的誤差的最大值、均值和標(biāo)準(zhǔn)差在四種方法中均為最小，表現(xiàn)出較好的穩(wěn)定性和魯棒性，對(duì)于光照條件和目標(biāo)外觀發(fā)生變化的情況，仍能得到較好的跟蹤效果。

表1 David Indoor誤差比較

Girl數(shù)據(jù)集的跟蹤效果如圖3所示。目標(biāo)的外觀發(fā)生了顯著變化，有正面臉、側(cè)面臉、背面以及其他目標(biāo)的干擾，跟蹤難度比David Indoor數(shù)據(jù)集增大。從跟蹤效果來看，MIL和新算法的跟蹤效果要優(yōu)于OAB1和OAB4。

圖4為采用不同跟蹤方法得到的誤差曲線，可以看出，四種方法的跟蹤效果都比David Indoor數(shù)據(jù)集的跟蹤效果差，這是由于Girl數(shù)據(jù)集中運(yùn)動(dòng)場(chǎng)景更為復(fù)雜所致。OAB1和OAB4的跟蹤誤差隨著時(shí)間在逐步增加，在450幀之前，MIL和新算法的誤差曲線較為平穩(wěn)，性能相差不大。但在450幀至最后一幀之間，MIL的誤差急劇增大，這是由于運(yùn)動(dòng)目標(biāo)被部分遮擋所致，而新算法誤差呈現(xiàn)出平穩(wěn)變化的趨勢(shì)。

圖3 Girl跟蹤效果

圖4 Girl誤差曲線

四種方法跟蹤結(jié)果的誤差最大值、誤差均值以及誤差標(biāo)準(zhǔn)差如表2所示。新算法產(chǎn)生的誤差的最大值和標(biāo)準(zhǔn)差在四種方法中最小，而誤差均值略高于MIL?？傮w來看，新算法表現(xiàn)出較好的穩(wěn)定性和魯棒性，對(duì)于目標(biāo)外觀發(fā)生顯著變化的情況，仍能得到較好的跟蹤效果。

表2 Girl誤差比較

2.2 處理時(shí)間對(duì)比

在David Indoor和Girl數(shù)據(jù)集上，對(duì)比OAB1、OAB4、MIL和新算法的平均處理時(shí)間，如表3所示。兩個(gè)數(shù)據(jù)集中每幀圖像大小均為320 pixel×240 pixel，OAB1算法在David Indoor和Girl數(shù)據(jù)集上的平均處理時(shí)間為161 ms/幀和153 ms/幀。OAB4的算法復(fù)雜度較OAB1稍高，平均處理時(shí)間分別為175 ms/幀和166 ms/幀。MIL和新算法的時(shí)間復(fù)雜度相同，平均處理時(shí)間分別為238 ms/幀和222 ms/幀。可見，新算法取得較好的跟蹤效果是以犧牲時(shí)間為代價(jià)的。

表3 各算法在相應(yīng)數(shù)據(jù)集上的平均處理時(shí)間/ms

3 結(jié) 語

提出一種基于多示例學(xué)習(xí)框架的跟蹤算法。該算法利用類Haar特征構(gòu)建若干弱分類器，然后級(jí)聯(lián)為多示例學(xué)習(xí)強(qiáng)分類器，進(jìn)行基于檢測(cè)的跟蹤，并在跟蹤的過程中，實(shí)時(shí)更新多示例學(xué)習(xí)強(qiáng)分類器，以適應(yīng)運(yùn)動(dòng)目標(biāo)外觀變化。實(shí)驗(yàn)表明，該算法具有較好的魯棒性和實(shí)時(shí)性，對(duì)于運(yùn)動(dòng)目標(biāo)外觀有顯著變化的情況具有較好的跟蹤效果。

[1] Yilmaz A, Javed O, Shah M. Object Tracking: A Survey[J]. ACM Computing Surveys, 2006, 38(4): 1-45.

[2] 靳鵬飛. 基于自適應(yīng)模板相關(guān)跟蹤算法的研究[J]. 西安郵電學(xué)院學(xué)報(bào), 2007, 12(1): 44-47.

[3] 李晶, 范九倫, 張雁冰. 基于卡爾曼濾波的人臉跟蹤算法[J]. 西安郵電學(xué)院學(xué)報(bào), 2010, 15(3): 101-104.

[4] Dietterich T G, Lathrop R H, Lozano-Perez T. Solving the multiple-instance problem with axis-parallel rectangles[J]. Artificial Intelligence, 1997, 39(1/2): 31-71.

[5] Viola P, Platt J, Zhang Cha. Multiple instance boosting for object detection[J]. Neural Information Processing Systems, 2007,18(1): 1417-1426.

[6] Babenko B, Dolla P, Tu Zhuowen, et al. Simultaneous Learning and Alignment: Multi-Instance and Multi-Pose Learning[C]//Workshop on Faces in Real-Life Images: Detection, Alignment, and Recognition. France Marseille: IEEE ECCV, 2008: 1-14.

[7] Babenko B, Yang M, Belongie S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8) :1619-1632.

[8] Zhang Kaihua, Song Huihui. Real-time visual tracking via online weighted multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 46(1): 397-411.

[9] Fu Zhouyu, Robles-Kelly A. MILIS: Multiple Instance Learning with Instance Selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5): 958-977.

[10] Grabner H, Grabner M, Bischof H. Real-Time Tracking via On-line Boosting[C]//Proceedings of the British Machine Vision Conference. UK Edinburgh: BMVC,2006: 47-56.

[11] Babenko B. Tracking with online multiple instance learning[EB/OL].(2011-02-03)[2013-11-20].http://vision.ucsd.edu/～bbabenko/project_miltrack.shtml.

[責(zé)任編輯:王輝]

Object tracking algorithms with multiple instance learning

LI Na1,2,3， LI Daxiang1,3， LIU Weihua1,3， LIU Ying1,3

(1.School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.School of Information Engineering, Chang’an University, Xi’an 710064, China；3.Lab of Image Processing, Shaanxi Crime Scene Investigation Unit, Xi’an 710121, China)

In this paper, an object tracking algorithm with multiple instance learning is proposed. This algorithm uses Haar-like features to build many weak classifiers, and combines some of them into an additive strong classifier. According to the position of the object in the former frame, the position of the object in the current frame is ascertained with the strong classifier. Different image patches are cropped as positive and negative bags to update the online strong classifier in its neighborhood. The experimental results show that this algorithm has good robustness and real-time performance when the appearance of object undergoes some significant changes.

object tracking, multiple instance learning, weak classifier

2013-12-03

陜西省自然科學(xué)基金資助項(xiàng)目(2013JM8031)；西安郵電大學(xué)中青年教師基金資助項(xiàng)目(ZL2013-04，ZL2012-01)

李娜(1981-)，女，講師，從事目標(biāo)跟蹤和行為分析研究。E-mail：lina114@xupt.edu.cn 李大湘(1974-)，男，副教授，從事多示例學(xué)習(xí)和圖像檢索研究。E-mail: 35108809@qq.com

10.13682/j.issn.2095-6533.2014.02.007

TP391

A

2095-6533(2014)02-0043-05