楊　帆

(中國(guó)船舶重工集團(tuán)公司第七二三研究所　揚(yáng)州　225001)

?

一種改進(jìn)的基于核跟蹤的運(yùn)動(dòng)物體跟蹤算法

楊帆

(中國(guó)船舶重工集團(tuán)公司第七二三研究所揚(yáng)州225001)

針對(duì)核跟蹤中均值漂移算法候選目標(biāo)模型起始檢索窗口選擇的不足,將卡爾曼濾波預(yù)測(cè)的窗口和三幀差法提取的窗口通過加權(quán)的方式,產(chǎn)生一個(gè)新的檢測(cè)窗口作為均值漂移算法的檢索窗口,同時(shí)對(duì)核函數(shù)帶寬和目標(biāo)模型進(jìn)行更新。實(shí)驗(yàn)表明經(jīng)過優(yōu)化的算法,對(duì)運(yùn)動(dòng)物體跟蹤的效果有了明顯的提升,算法的魯棒性也得到了增強(qiáng)。

運(yùn)動(dòng)物體跟蹤; 均值漂移; 幀差法

Class NumberTP301

1　引言

運(yùn)動(dòng)物體檢測(cè)與跟蹤作為計(jì)算機(jī)視覺方面的關(guān)鍵性基礎(chǔ)問題,它的主要研究方向是從圖像一系列視頻幀中提取出運(yùn)動(dòng)變化區(qū)域的方法。在軍事作戰(zhàn)、智能交通、人機(jī)交互、多媒體娛樂、機(jī)器人導(dǎo)航、虛擬現(xiàn)實(shí)、醫(yī)學(xué)圖像等領(lǐng)域應(yīng)用十分廣泛[1]。運(yùn)動(dòng)物體跟蹤一般處于運(yùn)動(dòng)物體檢測(cè)和運(yùn)動(dòng)物體的后期行為分析的中間步驟,運(yùn)動(dòng)物體跟蹤本質(zhì)是運(yùn)動(dòng)目標(biāo)的坐標(biāo)位置的變化,為后期行為分析提供位置數(shù)據(jù)。運(yùn)動(dòng)物體的跟蹤是將視頻幀中我們關(guān)注的物體進(jìn)行信息關(guān)聯(lián),通過關(guān)聯(lián)的方法,把原本分散的不同幀中的相對(duì)獨(dú)立的運(yùn)動(dòng)物體,提取它的相關(guān)性,記錄這個(gè)運(yùn)動(dòng)物體的軌跡信息。

2　幾種常見的跟蹤算法

目前常用的跟蹤方法一般可以分為三類:點(diǎn)跟蹤、核跟蹤和輪廓跟蹤法。

· 點(diǎn)跟蹤法[2]:用點(diǎn)與點(diǎn)之間的相關(guān)性來描述運(yùn)動(dòng)物體的關(guān)聯(lián)系。當(dāng)然視頻中的運(yùn)動(dòng)物體用點(diǎn)刻畫,用點(diǎn)跟蹤法,缺陷是會(huì)丟失物體本身的信息。所以,點(diǎn)跟蹤法適用于微小物體的跟蹤,該算法同時(shí)具有計(jì)算量小、方法簡(jiǎn)單的優(yōu)點(diǎn),缺點(diǎn)是不能準(zhǔn)確地跟蹤物體。

· 核跟蹤法[3]:核跟蹤法是計(jì)算原始物體所占的區(qū)域在相鄰兩視頻幀之間的運(yùn)動(dòng)。核指的是運(yùn)動(dòng)目標(biāo)的外觀或形狀。運(yùn)動(dòng)物體被看成一個(gè)橢圓區(qū)域或矩形區(qū)域。最簡(jiǎn)單的一種核跟蹤方法是模版匹配,可以通過運(yùn)動(dòng)區(qū)域內(nèi)兩者的相似度比較,最終確定最匹配的區(qū)域。均值漂移(Mean Shift)算法是一種典型的核跟蹤方法,避免了毫無目的的隨意匹配,向著概率密度函數(shù)增大的方向匹配,因此該方法可以通過較少的迭代次數(shù)快速找到與目標(biāo)最相似的位置。

· 輪廓跟蹤法[4]:該方法就是在連續(xù)圖像中通過物體模型找到物體的運(yùn)動(dòng)區(qū)域。對(duì)于非剛性的運(yùn)動(dòng)物體,如手、頭、人體等,物體的輪廓不能用簡(jiǎn)單的幾何形狀來描述。顏色直方圖、物體邊緣、物體輪廓是很好地表達(dá)物體的方法。目前人頭檢測(cè)是比較典型的輪廓跟蹤方法。

3　Mean Shift算法

均值漂移算法(Mean Shift)是一種穩(wěn)定的方法,它尋找局部極值的是在一組數(shù)據(jù)的概率密度分布中。1995年Cheng對(duì)此算法進(jìn)行優(yōu)化,并運(yùn)用到圖像處理的領(lǐng)域。此算法還被應(yīng)用到圖像平滑、圖像分割、目標(biāo)物體跟蹤等方面[5]。

均值漂移算法的一般流程如下[6]:

1) 計(jì)算目標(biāo)模型

Mean Shift算法用到彩色直方圖來描述團(tuán)塊的統(tǒng)計(jì)特征。用團(tuán)塊對(duì)物體的位置及大小的描述。假如直方圖的維數(shù)為m,運(yùn)動(dòng)目標(biāo)中的像素位置為{xi,xi=(xi,yi)}i=1,2,…,n,n為區(qū)域內(nèi)目標(biāo)像素點(diǎn)的總個(gè)數(shù),目標(biāo)的中心為x0,半徑為h=(hx,hy),團(tuán)塊中每個(gè)像素點(diǎn)的像素值與彩色直方圖存在一一映射關(guān)系,假設(shè)函數(shù)b:R2→{1,…,m}。目標(biāo)模型的特征值u的概率密度為

K表示核函數(shù)的輪廓函數(shù),h表示核函數(shù)的窗寬,σ表示克羅內(nèi)克函數(shù)。

之后每幀中,運(yùn)動(dòng)目標(biāo)可能存在的區(qū)域稱為候選區(qū)域。假如{xi,xi=(xi,yi)}i=1,2,…,nh是當(dāng)前視頻幀中候選目標(biāo)中的像素的位置,y是候選目標(biāo)的中心位置,因此候選目標(biāo)中顏色u∈{1,…,m}的概率密度函數(shù)為

3) 計(jì)算目標(biāo)模型和候選模型它們之間的Bhattacharyya系數(shù)。

Bhattacharyya(巴氏系數(shù))表示:

其中,g(x)=-k′(x)。

4　基于Mean Shift跟蹤算法的改進(jìn)

從Mean Shift跟蹤算法可以看出該算法在跟蹤中的優(yōu)勢(shì):算法的計(jì)算量小。如果目標(biāo)區(qū)域已經(jīng)知到,本算法就可以達(dá)到實(shí)時(shí)跟蹤的效果,效率高。

同時(shí),Mean Shift算法也有著以下一些不足:

1) 跟蹤過程中因?yàn)榇翱趯挾鹊拇笮?huì)不變,也沒有對(duì)目標(biāo)模型進(jìn)行更新,如果目標(biāo)尺度產(chǎn)生了變化時(shí),跟蹤就不會(huì)成功。

2) 缺乏必要的模板更新。所以Mean Shift算法需要迭代多次以尋找更優(yōu)的候選模型,這樣就增加了檢索時(shí)間。通常工程應(yīng)用中都會(huì)為了實(shí)時(shí)性的考慮,如果限制了迭代的次數(shù),這種做法對(duì)尋找最優(yōu)的候選目標(biāo)位置是不利的。

3) 直方圖特征在目標(biāo)顏色特征描述方面略不足,所以目標(biāo)模型和候選模型在做相似性度量時(shí),就不可能做到完全相似。

針對(duì)以上提出的Mean Shift算法的不足,本文引入三幀差法和Kalman濾波器改進(jìn)Mean Shift算法。

三幀差分算法認(rèn)為是相鄰兩幀差分算法的一種改進(jìn),它的做法是選取連續(xù)三幀圖像,然后進(jìn)行差分運(yùn)算,這樣可以消除背景影響,這樣可以提取精確的目標(biāo)輪廓信息。這樣就得到目標(biāo)的準(zhǔn)確位置。同時(shí)卡爾曼濾波可以根據(jù)前一幀的運(yùn)動(dòng)目標(biāo)位置來預(yù)測(cè)的當(dāng)前幀中的位置,因此可以先用三幀差法提取所有的運(yùn)動(dòng)物體輪廓,再利用Kalman濾波從提取出來的輪廓中選擇一個(gè)合適的輪廓,最后再應(yīng)用Mean Shift進(jìn)行其跟蹤。具體優(yōu)化如下:

1) 候選模型初始位置選擇

首先利用三幀差法把當(dāng)前幀中所有運(yùn)動(dòng)物體的輪廓提取出來,接著用Kalman濾波器預(yù)測(cè)在當(dāng)前幀的目標(biāo)模型的輪廓P。然后輪廓P中心一一和三幀差法中提取的物體輪廓中心相匹配,去除最相近的那個(gè)輪廓作為候選模型輪廓Q,新的輪廓L需:

L=aP+bQ

因?yàn)長(zhǎng)是加權(quán)得來的,a、b是加權(quán)系數(shù),輪廓L中心作為起始的檢索位置,同時(shí)作為Mean Shift的檢索窗口。

2) 優(yōu)化Mean Shift算法,實(shí)現(xiàn)自動(dòng)跟蹤

傳統(tǒng)的均值漂移算法都是需手動(dòng)選取目標(biāo)模型。三幀差法提取的運(yùn)動(dòng)物體之后,可以對(duì)其進(jìn)行一定的篩選,作為均值漂移算法的目標(biāo)模型,這樣均值漂移算法可以自動(dòng)選取目標(biāo)模型,自動(dòng)跟蹤的功能也就實(shí)現(xiàn)了。

3) 自動(dòng)更新核函數(shù)帶寬

當(dāng)均值漂移算法選出候選模型后,對(duì)于團(tuán)塊來說,核函數(shù)帶寬就是團(tuán)塊的高和寬的一半,把候選模型的區(qū)域的寬和高的一半當(dāng)成核函數(shù)帶寬,這樣就自動(dòng)更新成功核函數(shù)的帶寬。

5　實(shí)驗(yàn)結(jié)果及分析

進(jìn)行實(shí)驗(yàn)之前,先介紹一些試驗(yàn)參數(shù)。系統(tǒng)的狀態(tài)向量表示:xk=(x,y,w,h,dx,dy,dw,dh)T,觀察向量表示:zk=(x,y,w,h)T,狀態(tài)傳遞矩陣表示:

測(cè)量矩陣表示:

系統(tǒng)噪聲的協(xié)方差矩陣是8×8對(duì)角陣,其主對(duì)角線元素為0.00001,測(cè)量噪聲的協(xié)方差矩陣是4×4對(duì)角陣,主對(duì)角線元素0.1,后驗(yàn)估計(jì)的協(xié)方差是8×8單位矩陣,系統(tǒng)控制矩陣先設(shè)為0矩陣。Mean Shift算法用的是HSV空間的H-S二維直方圖提取物體特征,特征相似性度量使用的是巴氏距離,

5.1實(shí)驗(yàn)說明

首先根據(jù)圖1可以看出:從視頻中提取的圖片分別是第190幀、第194幀、第198幀。藍(lán)色矩形框:三幀差法提取的輪廓,綠色矩形框:卡爾曼濾波預(yù)測(cè)的輪廓,紅色矩形框:跟蹤結(jié)果的最終輪廓(四種不同的算法得出的最優(yōu)輪廓)。

(第一行圖片)第一種方法:將Mean Shift尋找的最優(yōu)輪廓作為下一次Mean Shift算法搜索輪廓。

(第二行圖片)第二種方法:將卡爾曼濾波預(yù)測(cè)的輪廓作為下一次Mean Shift算法搜索輪廓。

(第三行圖片)第三種方法:將三幀差法提取的輪廓作為下一次Mean Shift算法搜索輪廓。

(第四行圖片)第四種方法:本文提出的算法提取的輪廓(三幀差法提取輪廓與卡爾曼濾波預(yù)測(cè)輪廓加權(quán))作為下一次Mean Shift算法搜索輪廓。

圖1　不同窗口算法比較

5.2實(shí)驗(yàn)分析

通過上述對(duì)比可以發(fā)現(xiàn):

第一種方法(將Mean Shift尋找的最優(yōu)輪廓作為下一次Mean Shift算法搜索輪廓)自適應(yīng)效果比較差,當(dāng)運(yùn)動(dòng)目標(biāo)運(yùn)動(dòng)一段時(shí)間后,提取框已經(jīng)偏離運(yùn)動(dòng)目標(biāo)的位置。

第二種方法(將卡爾曼濾波預(yù)測(cè)的輪廓作為下一次Mean Shift算法搜索輪廓)算法提取運(yùn)動(dòng)目標(biāo)的輪廓與運(yùn)動(dòng)目標(biāo)實(shí)際輪廓出現(xiàn)較大的偏差。

第三種方法(將三幀差法提取的輪廓作為下一次Mean Shift算法搜索輪廓)自適應(yīng)的效果不錯(cuò),由于三幀差法有閾值的干擾,所以此方法也會(huì)受到影響。

第四種方法:本文提出的算法。自適應(yīng)能力高于第一種。很明顯最后的結(jié)果也很穩(wěn)定。

通過以上分析可得:本文提出的算法(三幀差法提取輪廓與卡爾曼濾波預(yù)測(cè)輪廓加權(quán)作為下一次Mean Shift算法搜索輪廓)相比其它的算法,跟蹤的輪廓更完整,提取框更符合運(yùn)動(dòng)目標(biāo)在視頻中的實(shí)際位置。穩(wěn)定性也更高了。

6　結(jié)語

本文分析比較了幾種常見的跟蹤算法,并重點(diǎn)描述了基于均值漂移(Mean Shift)的跟蹤算法,分析了均值漂移算法(Mean Shift)的不足,用卡爾曼濾波和三幀差法對(duì)Mean Shift進(jìn)行改進(jìn)。最后的實(shí)驗(yàn)通過和其他三種算法對(duì)比證明,本文提出的算法在穩(wěn)定性、魯棒性等方面優(yōu)于其他算法。

[1] N. Dalal, B. Triggs. Histograms of oriented gradients for human detection[C]//Proceeding of Conference on Computer Vision and Pattern Recognition.Los Alamitos: IEEE Computer Society Press,2005,1:886-893.

[2] D. G. Lowe. Object recognition from local scale-invariant features[C]//International Conference on Computer Vision,1999,21(2):1150-1157.

[3] T. J. Broida, R. Chellappa. Estimation of Object Motion Parameters from Noisy Images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1986,PAMI-8(1):90-99.

[4] D. Comaniciu, V. Ramesh, P. Meer. Real-Time Tracking of Non-Rigid Objects using Mean Shift[C]//Proceedings IEEE Conference on Computer Vision and Pattern Recognition,2000,2:142-149.

[5] Y. Cheng. Mean Shift, Mode Seeking,and Clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(8):790-799.

[6] 常發(fā)亮,劉雪,王華杰.基于均值漂移與卡爾曼濾波的目標(biāo)跟蹤算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(12):50-52.

CHANG Faliang, LIU Xue, WANG Huajie. A Moving Object Tracking Algorithm Based on Mean Shift and Kalman filter[J]. Computer Engineering and Applications,2007,43(12):50-52.

[7] 朱勝利,朱善安.基于卡爾曼濾波器組的Mean Shift模版更新算法[J].中國(guó)圖象圖像學(xué)報(bào),2007,12(3):460-465.

ZHU Shengli, ZHU Shanan. An improved Mean Shift Algorithm Based on Kalman filter group[J]. Chinese Journal of Image Image,2007,12(3):460-465.

[8] Marr D. Vision: a computational investigation into the human representation and Processing of visual information[C]//W. H. Freemanand Co.,1982.

[9] Bar-Shalom Y, Fortmarm T. Traeking and Data Association[M]. Aeademie Press,1988.

[10] D. Comaniciu, V. Ramesh, P. Meer. Real-Time Tracking of Non-Rigid Objects using Mean Shift[C]//Proceedings IEEE Conference on Computer Vision and Pattern Recognition,2000,2:142-149.

An Improved Moving Object Tracking Method Based on Mean-shift Algorithm

YANG Fan

(No. 723 Research Institute of CSIC, Yangzhou225001)

Aiming at the deficiency of the initial retrieval window in the candidate target model of mean-shift algorithm, a new detection window is produced as the retrieval window of mean-shift algorithm by weighting the window of kalman filter and extracted window of three image difference methods. At the same time, the bandwidth of kernel function and the arget model are updated. Experiments show that the optimization algorithm has been significantly improved after the detection of moving object, the robustness of the algorithm has been enhanced.

moving object tracking, mean shift, frame difference method

2016年2月14日,

2016年3月19日

楊帆,男,工程師,研究方向:計(jì)算機(jī)應(yīng)用。

TP301

10.3969/j.issn.1672-9722.2016.08.015