秦 臻 ， 曹劍中

（1.中國科學(xué)院 西安光學(xué)精密機(jī)械研究所，陜西 西安710119；2.中國科學(xué)院研究生院 北京 100039）

目標(biāo)的實(shí)時(shí)跟蹤在計(jì)算機(jī)視覺跟蹤領(lǐng)域有著非常重要的應(yīng)用，近年來在目標(biāo)跟蹤領(lǐng)域提出了很多好的算法，然而很多算法由于計(jì)算復(fù)雜，都未能應(yīng)用到對(duì)實(shí)時(shí)性要求較高的場(chǎng)合。Dorin Comaniciu將Mean shift算法引入到目標(biāo)跟蹤領(lǐng)域[1-2]，極大地減少了跟蹤算法的計(jì)算量。Dorin Comaniciu提出的算法是以彩色直方圖作為特征來實(shí)現(xiàn)目標(biāo)的識(shí)別與定位，而灰度直方圖所包含的圖像信息單一，使得Mean shift算法很難應(yīng)用于灰度圖像，限制了Mean shift算法的適應(yīng)環(huán)境。經(jīng)典的Mean shift算法要求相鄰兩幀間目標(biāo)模板區(qū)域必須重疊，在目標(biāo)較快運(yùn)動(dòng)的情況下容易跟丟目標(biāo)；在目標(biāo)出現(xiàn)尺度變化的復(fù)雜條件下，其跟蹤結(jié)果往往出現(xiàn)偏差，甚至跟蹤失敗。筆者提出了基于空間方向直方圖的Mean shift跟蹤算法，使用空間統(tǒng)計(jì)信息作為匹配信息，結(jié)合卡爾曼濾波預(yù)測(cè)目標(biāo)位置。實(shí)驗(yàn)結(jié)果表明，該算法在目標(biāo)運(yùn)動(dòng)較快，光照變化和尺度縮放等情況下可以對(duì)目標(biāo)準(zhǔn)確的跟蹤，具有良好的魯棒性和效率。

1 Mean shift算法概述

Mean shift算法是一種非參數(shù)概率密度估計(jì)算法[3]，可以通過迭代，快速地收斂于概率密度函數(shù)的局部極大值。算法的跟蹤過程就是不斷尋找概率密度局部最大值的過程，其步驟如下。

1.1 目標(biāo)模型的描述

在首幀圖像中確定被跟蹤的目標(biāo)區(qū)域，可通過手工選擇矩形框的方式來確定目標(biāo)區(qū)域。目標(biāo)模型可以描述為在目標(biāo)區(qū)域上的所有特征值的概率值，用目標(biāo)模型的特征值估計(jì)的概率密度為：

其中，K（x）為核函數(shù)的輪廓函數(shù)；b（xi）是表示像素 xi屬于哪類特征值；h 表示核函數(shù)的帶寬[4]；δ[b（xi）-u]是用于判斷目標(biāo)區(qū)域中的任意像素xi的顏色值是否等于第u個(gè)特征值；C是一個(gè)標(biāo)準(zhǔn)化的常量系數(shù)。

1.2 候選模型的描述

類似式（1），計(jì)算當(dāng)前幀中，搜索窗口的特征值的概率密度為：

1.3 相似性函數(shù)

相似性函數(shù)用于描述目標(biāo)模型和候選模型的相似性度量，可使用Bhattacharyya[5]系數(shù)作為相似性函數(shù)，即

其值在0～1之間。ρΛ（y）的值越大，表示兩個(gè)模型越相似。

1.4 目標(biāo)定位

為使ρΛ（y0）最大，應(yīng)當(dāng)先將當(dāng)前幀的目標(biāo)中心定位為前一幀中目標(biāo)中心的位置y0，在y0鄰域內(nèi)尋找局部最優(yōu)目標(biāo)位置 y1。 定位時(shí)，先在 ρΛ（y0）處對(duì)函數(shù)式（3）進(jìn)行泰勒展開，相似性函數(shù)可近似為：

其中：

令

可以看出，求相似性函數(shù)最大就是要求式（6）最大，通過對(duì)相似性函數(shù)求最大值，即可計(jì)算Mean shift向量y1-y0。如式（7）所示：

其中 g（x）=-k′（x），這樣目標(biāo)區(qū)域即可由初始位置逐步移動(dòng)到真實(shí)的目標(biāo)位置。 根據(jù)式（4）可知，相似性函數(shù)ρΛ（y0）在處先進(jìn)行泰勒展開，而泰勒展開要求是在鄰域內(nèi)展開，這就限制了起始點(diǎn)y0和y的距離不能太大。

2 基于方向直方圖的跟蹤

2.1 方向直方圖

給定一組灰度圖像I，定義像素的梯度方向角為

式中 ?f/?y和 ?f/?x分別是該像素處沿 y和 x方向的梯度，可以通過梯度算子來獲得。梯度方向角θ的取值范圍為0～2π。為了獲得方向編碼，需要對(duì)方向角進(jìn)行量化。方向角量化的間距為Δθ，于是方向編碼可按式（9）計(jì)算：

如果方向編碼被量化成m個(gè)，則cij的取值為{0，1，2，…，m-1}。 對(duì)于小于閾值T的像素來說，定義其方向編碼為m，由于此區(qū)域很難計(jì)算出穩(wěn)定的梯度方向角，因而閾值T可根據(jù)經(jīng)驗(yàn)來選擇。如果采用的量化方向?yàn)?6個(gè)，方向編碼的間距Δθ取π/8。用Mean shift跟蹤目標(biāo)模型和候選模型時(shí)，在跟蹤區(qū)域用方向編碼來描述目標(biāo)。方向編碼示意圖如圖1所示。

2.2 跟蹤算法流程

1）預(yù)測(cè)跟蹤坐標(biāo) 利用前一幀圖像中目標(biāo)的位置信息來預(yù)測(cè)在當(dāng)前幀中目標(biāo)的位置信息。先驗(yàn)估計(jì)計(jì)算公式[6]如下：

2）獲得當(dāng)前幀的跟蹤坐標(biāo) 以1）預(yù)測(cè)得到的跟蹤坐標(biāo)為起始搜索位置，應(yīng)用基于方向直方圖的Mean shift跟蹤算法，得到當(dāng)前幀目標(biāo)實(shí)際的跟蹤坐標(biāo) Zk（xK，yK）。

3）校正跟蹤坐標(biāo) 根據(jù)2）得到的實(shí)際測(cè)量值Zk，利用后驗(yàn)估計(jì)公式，計(jì)算得到新的后驗(yàn)估計(jì)坐標(biāo)值，返回到1），進(jìn)行下一幀參數(shù)的預(yù)測(cè)。

后驗(yàn)估計(jì)計(jì)算公式[7]如下：

R為觀測(cè)噪聲協(xié)方差矩陣；Kk為卡爾曼增益；H表示狀態(tài)變量xk對(duì)測(cè)量變量Zk的增益矩陣。

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

本文利用灰度圖像序列來驗(yàn)證新算法的跟蹤效果[8-9]。圖2為圖像跟蹤區(qū)域的灰度直方圖和方向統(tǒng)計(jì)直方圖。圖3是汽車圖像序列的跟蹤結(jié)果。

3.1 直方圖的對(duì)比

方向直方圖簡化了目標(biāo)的表述方式，減少了Mean shift匹配時(shí)的bins的個(gè)數(shù)，因而降低了跟蹤過程中的匹配復(fù)雜度，有利于提高跟蹤速度，并且利用了目標(biāo)運(yùn)動(dòng)的方向特性，跟蹤時(shí)對(duì)目標(biāo)方向變化不敏感。

圖1 運(yùn)動(dòng)方向編碼示意圖Fig.1 Coding schemes of movement direction

圖2 汽車運(yùn)動(dòng)區(qū)域直方圖Fig.2 Histogram of motor movement region

3.2 序列圖像跟蹤結(jié)果

圖3 跟蹤汽車圖像序列Fig.3 Image sequence of tracking car

在圖 3 中，圖（a）、（b）、（c）為原算法的跟蹤結(jié)果；圖（d）、（e）、（f）為新算法的跟蹤結(jié)果。原跟蹤算法中，在汽車運(yùn)動(dòng)較快的情況下，跟蹤過程中目標(biāo)存在部分出框的問題；而新算法在目標(biāo)運(yùn)動(dòng)速度過快和目標(biāo)尺度變化的情況下仍然可以穩(wěn)定的跟蹤到目標(biāo)。

表1 Mean shift和改進(jìn)算法的對(duì)比Tab.1 Contrast between Mean shift and improved algorithm

圖4 兩組算法跟蹤效率對(duì)比Fig.4 Tracking performance comparison of two groups algorithm

表1和圖4是Mean shift算法和新算法的跟蹤效率對(duì)比分析。圖（a）是兩組算法迭代次數(shù)對(duì)比。圖（b）是兩組算法跟蹤耗時(shí)對(duì)比。

可以看出，由于卡爾曼濾波算法的計(jì)算量很小，卡爾曼濾波器平穩(wěn)運(yùn)行后，新的算法能夠減少每幀內(nèi)Mean shift的迭代次數(shù)，而且每幀的計(jì)算時(shí)間相對(duì)減少，表明新算法有效地提高了跟蹤的效率。

4 結(jié) 論

本文提出了一種基于空間方向直方圖的Mean shift跟蹤新算法。該算法利用卡爾曼濾波器預(yù)測(cè)當(dāng)前幀目標(biāo)的可能位置，利用空間直方圖來描述目標(biāo)，能夠在一定復(fù)雜條件下對(duì)目標(biāo)進(jìn)行準(zhǔn)確、有效、實(shí)時(shí)的跟蹤。實(shí)驗(yàn)結(jié)果表明，該算法可以較好的適應(yīng)光線變化，目標(biāo)尺度縮放或色彩質(zhì)量很差等圖像序列中的目標(biāo)跟蹤，改善了傳統(tǒng)基于色彩方向直方圖的局限性，提高了跟蹤算法的效率。

[1]Comaniciu D， Ramesh V， Meer P.Kernel-based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

[2]ComaniciuD，RameshV，MeerP.Real-timetrackingofnon-rigid objects using Mean shift[C]//Proc IEEE Coference on Computer Vision and Pattern Recognition，2000：142-149.

[3]CHENG Yi-zong.Mean shift， mode seeking， and clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17（8）：790-799.

[4]Comaniciu D，Ramesh V，Meer P.The variable bandwith Mean shift and data-driven scale selection[J].Eighth IEEE International Conference on Computer Vision，2001：438-445.[5]PENG Ning-song， YANG Jie， LIU Zhi.Mean shift blob tracking with kernel histogram filtrering and hypothesis testing[J].Pattern Recognition Letters， 2005，26（5）：605-614.

[6]田綱，胡瑞敏，王中元.一種基于運(yùn)動(dòng)矢量分析的Mean shift目標(biāo)跟蹤算法[J].中國圖象圖形學(xué)報(bào).2010，15（1）：85-90.TIAN Gang， HU Rui-min， WANG Zhong-yuan.A Mean shift target tracking algorithm based on motion vector analysis[J].Journal of Image and Graphics， 2010，15（1）：85-90.

[7]詹建平，黃席樾，沈志熙，等.基于均值漂移和卡爾曼濾波的目標(biāo)跟蹤方法[J].重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)，2010，24（3）：76-80.ZHAN Jian-ping， HUANG Xi-yue， SHEN Zhi-xi， et al.Target tracking based on Mean-shift and kalman filter[J].JournalofChongqing University ofTechnology：Natural Science， 2010， 24（3）：76-80.

[8]王寶榮，楊華，王一程，等.基于卡爾曼濾波與均值漂移算法的目標(biāo)跟蹤[J].激光與紅外，2009， 39（11）：1233-1236.WANG Bao-rong， YANG Hua， WANG Yi-cheng，et al.Targettrackingalgorithm based on Kalman filterand meanshift[J].Laser and Infrared， 2009， 39（11）：1233-1236.

[9]劉惟錦，章毓晉.基于Kalman濾波和邊緣直方圖的實(shí)時(shí)目標(biāo)跟蹤[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2008 ，48（7）：1104-1107.LIU Wei-jin，ZHANG Shu-jin.Edge-color-histogram and Kalman filter-based real-time object tracking[J].Journal of Tsinghua University：Science and Technology， 2008 ，48（7）：1104-1107.