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

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

基于多示例學習的目標跟蹤算法

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

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

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

目標跟蹤；多示例學習；弱分類器

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

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

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

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

1 算法描述

1.1 基于多示例學習的目標跟蹤

算法1(基于多示例學習的跟蹤)

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

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

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

步驟2 使用最新的MIL分類器，計算

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

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

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

1.2 在線MIL分類器

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

Φ={h1,h2,…,hM}

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

其中

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

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

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

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

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

在MIL中，記訓練集為

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

其中

Xi={Xi1,Xi2,…,xim}

代表第i個包，xij代表第i個包中的第j個示例，yi代表第i個包的標記(0代表負包，1代表正包)。包標記定義為

其中yij代表第i個包中的第j個示例的標記，在訓練階段示例標記是未知的。

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

但在求包標記時會用到示例標記P{yi|xij}，因此需要對示例標記建模，即

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

算法2(在線MIL分類器)

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

輸出分類器

步驟2 依次遍歷M個弱分類器，用它和強分類器的組合，估計每個示例xij為正示例的概率

估計每個包Xi為正包的概率

計算每個包的信息熵

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

hk(xij)=hm*(xij)。

把該弱分類器添加到強分類器中，即

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

1.3 弱分類器

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

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

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

2 實驗結果與分析

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

2.1 跟蹤結果對比

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

圖1 David Indoor跟蹤效果

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

圖2 David Indoor誤差曲線

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

表1 David Indoor誤差比較

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

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

圖3 Girl跟蹤效果

圖4 Girl誤差曲線

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

表2 Girl誤差比較

2.2 處理時間對比

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

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

3 結 語

提出一種基于多示例學習框架的跟蹤算法。該算法利用類Haar特征構建若干弱分類器，然后級聯(lián)為多示例學習強分類器，進行基于檢測的跟蹤，并在跟蹤的過程中，實時更新多示例學習強分類器，以適應運動目標外觀變化。實驗表明，該算法具有較好的魯棒性和實時性，對于運動目標外觀有顯著變化的情況具有較好的跟蹤效果。

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

[2] 靳鵬飛. 基于自適應模板相關跟蹤算法的研究[J]. 西安郵電學院學報, 2007, 12(1): 44-47.

[3] 李晶, 范九倫, 張雁冰. 基于卡爾曼濾波的人臉跟蹤算法[J]. 西安郵電學院學報, 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.

[責任編輯:王輝]

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

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

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

10.13682/j.issn.2095-6533.2014.02.007

TP391

A

2095-6533(2014)02-0043-05