劉 鍇,戴平陽,江曉蓮,李翠華

(廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院,福建廈門361005)

基于排序支持向量機(jī)的多特征融合目標(biāo)跟蹤算法

劉 鍇,戴平陽,江曉蓮,李翠華

(廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院,福建廈門361005)

針對(duì)計(jì)算機(jī)視覺領(lǐng)域的目標(biāo)跟蹤問題,提出一種基于排序支持向量機(jī)的多特征融合目標(biāo)跟蹤算法。利用排序支持向量機(jī)學(xué)習(xí)得到排序函數(shù),提取2種不同的圖像特征分別構(gòu)造分類器,使2個(gè)排序支持向量機(jī)并行預(yù)測(cè),分別計(jì)算2個(gè)分類器的錯(cuò)誤率,從而得到分類器權(quán)重完成融合。實(shí)驗(yàn)結(jié)果表明,與目前主流的跟蹤算法相比,該算法的跟蹤結(jié)果更準(zhǔn)確,在復(fù)雜視頻環(huán)境下也能對(duì)目標(biāo)進(jìn)行穩(wěn)定跟蹤,具有較強(qiáng)的魯棒性。

目標(biāo)跟蹤;多特征融合;排序?qū)W習(xí);分類器;排序支持向量機(jī);魯棒性

1 概述

視覺目標(biāo)跟蹤是計(jì)算機(jī)視覺領(lǐng)域內(nèi)一個(gè)重要組成部分,隨著研究的不斷深入,人們提出了許多跟蹤算法［1］,但要實(shí)現(xiàn)不同場(chǎng)景下的目標(biāo)魯棒跟蹤,仍然需要克服許多難點(diǎn),如場(chǎng)景光照變化、背景混淆、目標(biāo)自身形變、目標(biāo)快速運(yùn)動(dòng)、部分遮擋、完全遮擋等［2］。

近年來,基于學(xué)習(xí)的視覺跟蹤方法越來越受到人們的關(guān)注,文獻(xiàn)［3］提出了一種結(jié)合光流法的支持向量機(jī)跟蹤算法,該算法使用離線數(shù)據(jù)訓(xùn)練支持向量機(jī)來進(jìn)行目標(biāo)跟蹤。文獻(xiàn)［4］引入結(jié)構(gòu)化輸出的支持向量機(jī)(Support Vector Machine,SVM)來進(jìn)行目標(biāo)跟蹤,該方法通過使用結(jié)構(gòu)化輸出的支持向量機(jī)直接給出了目標(biāo)跟蹤結(jié)果,而不是采用傳統(tǒng)的基于檢測(cè)的先采用后分類的跟蹤方法來進(jìn)行跟蹤。文獻(xiàn)［5］則將排序支持向量機(jī)引入跟蹤領(lǐng)域,提出了使用排序支持向量機(jī)來進(jìn)行視覺目標(biāo)跟蹤,并進(jìn)一步改進(jìn)為帶有弱監(jiān)督樣本的排序支持向量機(jī)跟蹤算法［6］。

本文提出一種多特征融合的排序支持向量機(jī)跟蹤算法。首先通過排序支持向量機(jī)得到一個(gè)排序函數(shù),然后將多特征融合的思想與排序支持向量機(jī)相結(jié)合,使用不同的特征并行訓(xùn)練支持向量機(jī),并將它們用相應(yīng)的權(quán)重值結(jié)合起來,最終形成一個(gè)自適應(yīng)的在線學(xué)習(xí)多特征融合算法。

2 排序?qū)W習(xí)

排序?qū)W習(xí)是一種監(jiān)督或半監(jiān)督學(xué)習(xí)問題,其目的是利用訓(xùn)練數(shù)據(jù)自動(dòng)構(gòu)建排序模型。訓(xùn)練數(shù)據(jù)由數(shù)據(jù)列表組成,這些數(shù)據(jù)兩兩之間存在偏序關(guān)系。其中的排序是通過給出每項(xiàng)數(shù)據(jù)的分值來實(shí)現(xiàn)。排序?qū)W習(xí)與分類或回歸等傳統(tǒng)的機(jī)器學(xué)習(xí)任務(wù)有所不同。與分類學(xué)習(xí)相比,排序?qū)W習(xí)定義了序的關(guān)系,而與回歸學(xué)習(xí)不同,排序?qū)W習(xí)元素之間有序但沒有度量關(guān)系。

排序?qū)W習(xí)定義為:給定輸入向量集合X={x1, x2,…,xl}及對(duì)應(yīng)標(biāo)簽集合Y={y1,y2,…,yl}。排序?qū)W習(xí)就是從決策函數(shù)集合F={f:X→Y}中尋找最優(yōu)決策函數(shù)f*,使得其能精確預(yù)測(cè)未標(biāo)記數(shù)據(jù)x的標(biāo)簽y。即給定損失函數(shù)g,在最優(yōu)決策函數(shù)f*,有風(fēng)險(xiǎn)函數(shù)R(f)最小。

3 排序支持向量機(jī)

排序支持向量機(jī) (Ranking Support Vector Machine,RSVM)是解決排序?qū)W習(xí)問題的一類典型算法［7］。排序支持向量機(jī)的核心思想是把對(duì)目標(biāo)數(shù)據(jù)樣本的排序問題,轉(zhuǎn)換為基于有序?qū)?shù)據(jù)樣本的二值分類問題,并利用支持向量機(jī)求解。

假設(shè)f是如下線性函數(shù)滿足:

其中,w表示權(quán)重向量;＜·,· ＞表示內(nèi)積。將式(3)代入式(2)得:

由式(4)可得,xi和xj之間的優(yōu)先關(guān)系xi?xj轉(zhuǎn)換為xi-xj表示。對(duì)于任意給定樣本對(duì),都可以將它們之間的有序關(guān)系轉(zhuǎn)換為新的向量和新的標(biāo)簽,從而由已知訓(xùn)練集S,可以構(gòu)成包含已標(biāo)記樣本的新數(shù)據(jù)集S′,由式(5)給出:

從而將排序?qū)W習(xí)問題轉(zhuǎn)化為標(biāo)準(zhǔn)的二分類問題。構(gòu)造RSVM可得:

令w*為式(6)的最優(yōu)權(quán)重向量,則RSVM排序函數(shù)為:

4 多特征融合

4.1 特征表示

圖像的信息提取及表示,是影響跟蹤算法性能的關(guān)鍵因素。其中,圖像特征的選擇尤為關(guān)鍵。圖像特征大致分為顏色和灰度統(tǒng)計(jì)特征、紋理和邊緣特征、代數(shù)特征、變換系數(shù)特征或?yàn)V波器系數(shù)特征。在跟蹤過程中,每個(gè)實(shí)例根據(jù)其特征表示成為一個(gè)特征向量。本文用到的描述圖像區(qū)域?qū)嵗奶卣靼℉aar類特征和HOG特征2類。其中Haar類特征由2個(gè)～6個(gè)隨機(jī)生成的矩形框和對(duì)應(yīng)權(quán)重決定,每個(gè)圖像區(qū)域隨機(jī)采樣200個(gè)Haar類特征來表示,而HOG特征則將每個(gè)圖像區(qū)域表示成為一個(gè)3 780維特征向量。

4.2 融合過程

單獨(dú)使用某個(gè)特征往往難以全面描述各種場(chǎng)景中的目標(biāo)信息。過去的研究常常將不同的特征簡(jiǎn)單地結(jié)合成為一個(gè)新的特征,然而由于各個(gè)特征對(duì)圖像的描述準(zhǔn)確度不同,簡(jiǎn)單結(jié)合的特征將不能靈活地根據(jù)實(shí)際情況調(diào)整不同特征之間的權(quán)重關(guān)系,從而影響到訓(xùn)練的分類器性能。

分別訓(xùn)練基于HOG和Haar 2個(gè)不同特征表示的分類器,然后根據(jù)其對(duì)應(yīng)錯(cuò)誤率分別計(jì)算相應(yīng)的權(quán)重,從而有效地調(diào)整2種特征的影響因子。在t時(shí)刻某個(gè)特征無法很好描述目標(biāo),從而導(dǎo)致跟蹤性能下降時(shí),該特征對(duì)應(yīng)分類器的權(quán)重值會(huì)因其錯(cuò)誤率的升高而降低,這將使得能有效描述目標(biāo)特征的跟蹤器在跟蹤過程中起主導(dǎo)作用,從而實(shí)現(xiàn)基于多特征融合的魯棒目標(biāo)跟蹤。

在訓(xùn)練過程中,給定訓(xùn)練集合C,其中有已標(biāo)記樣本數(shù)N,分別訓(xùn)練基于HOG及Haar特征的分類器。由每個(gè)分類器的分類結(jié)果可以得到M個(gè)分類錯(cuò)誤樣本,從而計(jì)算得到該分類器錯(cuò)誤率:

那么該分類器權(quán)重可以表示為:

5 訓(xùn)練集的構(gòu)成

從連續(xù)k幀圖像中采集訓(xùn)練樣本并學(xué)習(xí)得到排序支持向量機(jī)。假定目標(biāo)周圍的圖像塊分值要高于遠(yuǎn)離目標(biāo)區(qū)域的圖像塊分值。若在t幀目標(biāo)的位置為,那么,可以分別構(gòu)建和2個(gè)訓(xùn)練樣本集,如式(10)和式(11)所示:

6 多特征融合的排序SVM跟蹤算法

根據(jù)Ranking SVM構(gòu)造排序函數(shù):

那么,圖像對(duì)的排序問題就轉(zhuǎn)換為二值分類問題,其RSVM定義如下:

式(14)的對(duì)偶問題由式(15)給出:

那么,圖像排序問題就等價(jià)于一個(gè)二次優(yōu)化問題。求解式(15)得到最優(yōu)解α*,由式(16)可以計(jì)算得到最優(yōu)權(quán)重向量w*:

那么,排序函數(shù)F由式(17)給出:

式(17)表明,F(xi)越大,對(duì)應(yīng)的xi排名越高。因此,最終融合的分類器C的分值由式(18)計(jì)算得到:

蘇軾“以詩為詞”的詞學(xué)理論是建立在“詩詞同源”基礎(chǔ)之上的，“清詩絕俗，甚典而麗。搜研物情，刮發(fā)幽翳，微詞宛轉(zhuǎn)，蓋詩之裔”［3］。詞為詩之苗裔，蘇軾重點(diǎn)強(qiáng)調(diào)的是詞如詩的主觀抒情性、個(gè)性化的色彩，用以淡化詞之媚俗，展現(xiàn)文人士大夫剛健清雅的精神境界，這就打破了詞為艷科的藩籬，擺脫了音律對(duì)詞的束縛，從而改革詞風(fēng)，擴(kuò)大詞境，促進(jìn)詞之雅化，提高詞之品格。古往今來的論者，對(duì)“以詩為詞”的褒揚(yáng)者，其在自己所處時(shí)代的歷史境遇內(nèi)，皆是以詩詞的相通之處——詩詞均出自于《詩》、《騷》、古樂府，都能吟詠性情，皆可作為察政觀俗的工具，詞可寓詩人的句法［4］50為基點(diǎn)，進(jìn)而對(duì)蘇軾“以詩為詞”理論的進(jìn)行發(fā)揚(yáng)。

其中,wHaar和wHOG由式(8)和式(9)計(jì)算得到。

在t時(shí)刻,給定搜索區(qū)域和分類器C,由式(18)計(jì)算搜索區(qū)域內(nèi)候選圖像塊的最終分值Ft(x),從而得到目標(biāo)位置。

多特征融合的排序支持向量機(jī)目標(biāo)跟蹤算法的具體描述如下:

算法 多特征融合的排序支持向量機(jī)目標(biāo)跟蹤算法

輸入 圖像序列{I1,I2,…,IT},原始幀目標(biāo)位置

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

本文算法在vs2010上由c++編寫實(shí)現(xiàn)。測(cè)試用的視頻序列為經(jīng)典公開測(cè)試序列。在所有測(cè)試序列實(shí)驗(yàn)中,參數(shù)設(shè)置對(duì)所有視頻序列都是固定的。實(shí)驗(yàn)參數(shù)具體為 r=2,α=5,β=30,s=30,其中式(10)采樣得到45個(gè)樣本構(gòu)成,式(11)采樣后隨機(jī)選取100個(gè)樣本構(gòu)成。

在Davidindoor序列中,目標(biāo)在室內(nèi)走動(dòng)過程中有光照變化、尺度變化、自身形變等干擾。

在Davidoutdoor序列中,目標(biāo)從左往右運(yùn)動(dòng)再返回,期間目標(biāo)外觀因變向而改變,且發(fā)生多次嚴(yán)重遮擋。

在Girl視頻序列中,跟蹤難點(diǎn)主要是目標(biāo)在跟蹤過程中會(huì)出現(xiàn)較明顯的尺度變化、旋轉(zhuǎn)、遮擋、自身形變、相似物體干擾,是較難的測(cè)試序列。

在Jumping序列中,跟蹤難點(diǎn)則是目標(biāo)快速運(yùn)動(dòng)及因此而造成的目標(biāo)模糊。

本文算法在經(jīng)典測(cè)試序列上跟蹤結(jié)果如圖1所示,表 1 是本文算法與 Frag［8］,L1［9］,MIL［10］, PCA［11］,PN［12］,VTD［13］等主流跟蹤算法在測(cè)試序列上相應(yīng)的中心誤差對(duì)比。實(shí)驗(yàn)結(jié)果表明,本文算法在經(jīng)典的測(cè)試序列上明顯優(yōu)于上述對(duì)比算法,能夠?qū)崿F(xiàn)準(zhǔn)確魯棒的目標(biāo)跟蹤。

圖1 經(jīng)典序列跟蹤結(jié)果

表1 經(jīng)典序列中心誤差對(duì)比像素

8 結(jié)束語

本文在跟蹤領(lǐng)域引入排序支持向量機(jī),將樣本間的排序問題轉(zhuǎn)化成有序?qū)Φ姆诸悊栴},提高了分類的準(zhǔn)確度。通過構(gòu)造2個(gè)不同圖像特征的分類器,克服了單特征難于全面描述目標(biāo)外觀的缺點(diǎn),并且由它們各自的分類錯(cuò)誤率來調(diào)整其相應(yīng)權(quán)重,可以使融合后的分類器自適應(yīng)地描述目標(biāo)外觀的變化,達(dá)到穩(wěn)定魯棒的跟蹤效果。下一步工作是將本文算法與CUDA編程相結(jié)合,提高特征提取和訓(xùn)練排序支持向量機(jī)的速度。

［1］ 侯志強(qiáng),韓崇昭.視覺跟蹤技術(shù)綜述［J］.自動(dòng)化學(xué)報(bào), 2006,32(4):603-617.

［2］ 盧曉鵬.視頻序列中目標(biāo)跟蹤技術(shù)研究［D］.北京:中國科學(xué)院研究生院,2007.

［3］ Avidan S.Support Vector Tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(8): 1064-1072.

［4］ Hare S,Saffari A,Torr P H S.Struck:Structured Output Tracking with Kernels［C］//Proceedings of CVPR'11.Barcelona,Spain:IEEE Press,2011:263-270.

［5］ Bai Yancheng,Tang Ming.Robust Visual Tracking via Ranking SVM［C］//Proceedings of ICIP'11.Brussels, Belgium:IEEE Press,2011:517-520.

［6］ Bai Yancheng,Tang Ming.Robust Tracking via Weakly Supervised Ranking SVM［C］//Proceedings of CVPR'12.Rhode Island,USA:IEEE Press,2012:1854-1861.

［7］ Yu H,Kim Y,Hwang S.RV-SVM:An Efficient Method for Learning Ranking SVM［C］//Proceedings of PAKDD'09.Berlin,Germany:Springer-Verlag,2009:426-438.

［8］ Adam A,Rivlin E,Shimshoni I.Robust Fragments-based Tracking Using the Integral Histogram ［C］// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.New York, USA:IEEE Computer Society,2006:798-805.

［9］ 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.

［10］ Babenko B,Yang M H,Belongie S.Robust Object Tracking with Online Multiple Instance Learning［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1619-1632.

［11］ 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.

［12］ Kalal Z,Mikolajczyk K,Matas J.Tracking-learningdetection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(7):1409-1422.

［13］ Kwon J,Lee K M.Visual Tracking Decomposition［C］// Proceedings of CVPR'10.San Francisco,USA:IEEE Press,2010:1269-1276.

編輯 金胡考

Object Tracking Algorithm Based on Ranking Support Vector Machine Fused with Multiple Features

LIU Kai,DAI Pingyang,JIANG Xiaolian,LI Cuihua
(School of Information Science and Technology,Xiamen University,Xiamen 361005,China)

For the object tracking problems in computer vision,this paper proposes a tracking algorithm based on Ranking Support Vector Machine(RSVM)fused with multiple features.Firstly,RSVM is used to get rank function.Secondly,the RSVMs combined with the two different image features are learnt respectively,then the two RSVMs predict parallel.Finally,the two RSVMs are fused with the weights which are calculated by the error rates of two classifiers,then it constructs a more adaptive RSVM framework fused with multiple features.This algorithm fuses image features effectively,and gets accurate predictions using RSVM.Experimental results demonstrate that it outperforms several stateof-the-arts algorithms.

object tracking;multiple features fusion;rank learning;classifier;Ranking Support Vector Machine (RSVM);robustness

1000-3428(2014)11-0042-04

A

TP18

10.3969/j.issn.1000-3428.2014.11.008

國家部委基金資助項(xiàng)目;高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20110121110020)。

劉 鍇(1989-),男,碩士研究生,主研方向:計(jì)算機(jī)視覺;戴平陽,博士研究生;江曉蓮,碩士研究生;李翠華,教授、博士。

2013-11-13

2014-01-10E-mail:LKnight.xmu@gmail.com

中文引用格式:劉 鍇,戴平陽,江曉蓮,等.基于排序支持向量機(jī)的多特征融合目標(biāo)跟蹤算法［J］.計(jì)算機(jī)工程, 2014,40(11):42-45.

英文引用格式:Liu Kai,Dai Pingyang,Jiang Xiaolian,et al.Object Tracking Algorithm Based on Ranking Support Vector Machine Fused with Multiple Features［J］.Computer Engineering,2014,40(11):42-45.