基于排序支持向量機的多特征融合目標跟蹤算法

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

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

基于排序支持向量機的多特征融合目標跟蹤算法

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

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

針對計算機視覺領域的目標跟蹤問題,提出一種基于排序支持向量機的多特征融合目標跟蹤算法。利用排序支持向量機學習得到排序函數,提取2種不同的圖像特征分別構造分類器,使2個排序支持向量機并行預測,分別計算2個分類器的錯誤率,從而得到分類器權重完成融合。實驗結果表明,與目前主流的跟蹤算法相比,該算法的跟蹤結果更準確,在復雜視頻環境下也能對目標進行穩定跟蹤,具有較強的魯棒性。

目標跟蹤;多特征融合;排序學習;分類器;排序支持向量機;魯棒性

1 概述

視覺目標跟蹤是計算機視覺領域內一個重要組成部分,隨著研究的不斷深入,人們提出了許多跟蹤算法［1］,但要實現不同場景下的目標魯棒跟蹤,仍然需要克服許多難點,如場景光照變化、背景混淆、目標自身形變、目標快速運動、部分遮擋、完全遮擋等［2］。

近年來,基于學習的視覺跟蹤方法越來越受到人們的關注,文獻［3］提出了一種結合光流法的支持向量機跟蹤算法,該算法使用離線數據訓練支持向量機來進行目標跟蹤。文獻［4］引入結構化輸出的支持向量機(Support Vector Machine,SVM)來進行目標跟蹤,該方法通過使用結構化輸出的支持向量機直接給出了目標跟蹤結果,而不是采用傳統的基于檢測的先采用后分類的跟蹤方法來進行跟蹤。文獻［5］則將排序支持向量機引入跟蹤領域,提出了使用排序支持向量機來進行視覺目標跟蹤,并進一步改進為帶有弱監督樣本的排序支持向量機跟蹤算法［6］。

本文提出一種多特征融合的排序支持向量機跟蹤算法。首先通過排序支持向量機得到一個排序函數,然后將多特征融合的思想與排序支持向量機相結合,使用不同的特征并行訓練支持向量機,并將它們用相應的權重值結合起來,最終形成一個自適應的在線學習多特征融合算法。

2 排序學習

排序學習是一種監督或半監督學習問題,其目的是利用訓練數據自動構建排序模型。訓練數據由數據列表組成,這些數據兩兩之間存在偏序關系。其中的排序是通過給出每項數據的分值來實現。排序學習與分類或回歸等傳統的機器學習任務有所不同。與分類學習相比,排序學習定義了序的關系,而與回歸學習不同,排序學習元素之間有序但沒有度量關系。

排序學習定義為:給定輸入向量集合X={x1, x2,…,xl}及對應標簽集合Y={y1,y2,…,yl}。排序學習就是從決策函數集合F={f:X→Y}中尋找最優決策函數f*,使得其能精確預測未標記數據x的標簽y。即給定損失函數g,在最優決策函數f*,有風險函數R(f)最小。

3 排序支持向量機

排序支持向量機 (Ranking Support Vector Machine,RSVM)是解決排序學習問題的一類典型算法［7］。排序支持向量機的核心思想是把對目標數據樣本的排序問題,轉換為基于有序對數據樣本的二值分類問題,并利用支持向量機求解。

假設f是如下線性函數滿足:

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

由式(4)可得,xi和xj之間的優先關系xi?xj轉換為xi-xj表示。對于任意給定樣本對,都可以將它們之間的有序關系轉換為新的向量和新的標簽,從而由已知訓練集S,可以構成包含已標記樣本的新數據集S′,由式(5)給出:

從而將排序學習問題轉化為標準的二分類問題。構造RSVM可得:

令w*為式(6)的最優權重向量,則RSVM排序函數為:

4 多特征融合

4.1 特征表示

圖像的信息提取及表示,是影響跟蹤算法性能的關鍵因素。其中,圖像特征的選擇尤為關鍵。圖像特征大致分為顏色和灰度統計特征、紋理和邊緣特征、代數特征、變換系數特征或濾波器系數特征。在跟蹤過程中,每個實例根據其特征表示成為一個特征向量。本文用到的描述圖像區域實例的特征包括Haar類特征和HOG特征2類。其中Haar類特征由2個～6個隨機生成的矩形框和對應權重決定,每個圖像區域隨機采樣200個Haar類特征來表示,而HOG特征則將每個圖像區域表示成為一個3 780維特征向量。

4.2 融合過程

單獨使用某個特征往往難以全面描述各種場景中的目標信息。過去的研究常常將不同的特征簡單地結合成為一個新的特征,然而由于各個特征對圖像的描述準確度不同,簡單結合的特征將不能靈活地根據實際情況調整不同特征之間的權重關系,從而影響到訓練的分類器性能。

分別訓練基于HOG和Haar 2個不同特征表示的分類器,然后根據其對應錯誤率分別計算相應的權重,從而有效地調整2種特征的影響因子。在t時刻某個特征無法很好描述目標,從而導致跟蹤性能下降時,該特征對應分類器的權重值會因其錯誤率的升高而降低,這將使得能有效描述目標特征的跟蹤器在跟蹤過程中起主導作用,從而實現基于多特征融合的魯棒目標跟蹤。

在訓練過程中,給定訓練集合C,其中有已標記樣本數N,分別訓練基于HOG及Haar特征的分類器。由每個分類器的分類結果可以得到M個分類錯誤樣本,從而計算得到該分類器錯誤率:

那么該分類器權重可以表示為:

5 訓練集的構成

從連續k幀圖像中采集訓練樣本并學習得到排序支持向量機。假定目標周圍的圖像塊分值要高于遠離目標區域的圖像塊分值。若在t幀目標的位置為,那么,可以分別構建和2個訓練樣本集,如式(10)和式(11)所示:

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

根據Ranking SVM構造排序函數:

那么,圖像對的排序問題就轉換為二值分類問題,其RSVM定義如下:

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

那么,圖像排序問題就等價于一個二次優化問題。求解式(15)得到最優解α*,由式(16)可以計算得到最優權重向量w*:

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

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

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

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

在t時刻,給定搜索區域和分類器C,由式(18)計算搜索區域內候選圖像塊的最終分值Ft(x),從而得到目標位置。

多特征融合的排序支持向量機目標跟蹤算法的具體描述如下:

算法 多特征融合的排序支持向量機目標跟蹤算法

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

7 實驗結果與分析

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

在Davidindoor序列中,目標在室內走動過程中有光照變化、尺度變化、自身形變等干擾。

在Davidoutdoor序列中,目標從左往右運動再返回,期間目標外觀因變向而改變,且發生多次嚴重遮擋。

在Girl視頻序列中,跟蹤難點主要是目標在跟蹤過程中會出現較明顯的尺度變化、旋轉、遮擋、自身形變、相似物體干擾,是較難的測試序列。

在Jumping序列中,跟蹤難點則是目標快速運動及因此而造成的目標模糊。

本文算法在經典測試序列上跟蹤結果如圖1所示,表 1 是本文算法與 Frag［8］,L1［9］,MIL［10］, PCA［11］,PN［12］,VTD［13］等主流跟蹤算法在測試序列上相應的中心誤差對比。實驗結果表明,本文算法在經典的測試序列上明顯優于上述對比算法,能夠實現準確魯棒的目標跟蹤。

圖1 經典序列跟蹤結果

表1 經典序列中心誤差對比像素

8 結束語

本文在跟蹤領域引入排序支持向量機,將樣本間的排序問題轉化成有序對的分類問題,提高了分類的準確度。通過構造2個不同圖像特征的分類器,克服了單特征難于全面描述目標外觀的缺點,并且由它們各自的分類錯誤率來調整其相應權重,可以使融合后的分類器自適應地描述目標外觀的變化,達到穩定魯棒的跟蹤效果。下一步工作是將本文算法與CUDA編程相結合,提高特征提取和訓練排序支持向量機的速度。

［1］ 侯志強,韓崇昭.視覺跟蹤技術綜述［J］.自動化學報, 2006,32(4):603-617.

［2］ 盧曉鵬.視頻序列中目標跟蹤技術研究［D］.北京:中國科學院研究生院,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

國家部委基金資助項目;高等學校博士學科點專項科研基金資助項目(20110121110020)。

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

2013-11-13

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

中文引用格式:劉 鍇,戴平陽,江曉蓮,等.基于排序支持向量機的多特征融合目標跟蹤算法［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.