基于方向直方圖的Mean shift目標跟蹤新算法

秦 臻 ， 曹劍中

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

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

1 Mean shift算法概述

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

1.1 目標模型的描述

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

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

1.2 候選模型的描述

類似式（1），計算當前幀中，搜索窗口的特征值的概率密度為：

1.3 相似性函數(shù)

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

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

1.4 目標定位

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

其中：

令

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

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

2 基于方向直方圖的跟蹤

2.1 方向直方圖

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

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

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

2.2 跟蹤算法流程

1）預測跟蹤坐標 利用前一幀圖像中目標的位置信息來預測在當前幀中目標的位置信息。先驗估計計算公式[6]如下：

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

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

后驗估計計算公式[7]如下：

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

3 實驗結(jié)果與分析

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

3.1 直方圖的對比

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

圖1 運動方向編碼示意圖Fig.1 Coding schemes of movement direction

圖2 汽車運動區(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é)果。原跟蹤算法中，在汽車運動較快的情況下，跟蹤過程中目標存在部分出框的問題；而新算法在目標運動速度過快和目標尺度變化的情況下仍然可以穩(wěn)定的跟蹤到目標。

表1 Mean shift和改進算法的對比Tab.1 Contrast between Mean shift and improved algorithm

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

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

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

4 結(jié) 論

本文提出了一種基于空間方向直方圖的Mean shift跟蹤新算法。該算法利用卡爾曼濾波器預測當前幀目標的可能位置，利用空間直方圖來描述目標，能夠在一定復雜條件下對目標進行準確、有效、實時的跟蹤。實驗結(jié)果表明，該算法可以較好的適應(yīng)光線變化，目標尺度縮放或色彩質(zhì)量很差等圖像序列中的目標跟蹤，改善了傳統(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]田綱，胡瑞敏，王中元.一種基于運動矢量分析的Mean shift目標跟蹤算法[J].中國圖象圖形學報.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]詹建平，黃席樾，沈志熙，等.基于均值漂移和卡爾曼濾波的目標跟蹤方法[J].重慶理工大學學報：自然科學，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]王寶榮，楊華，王一程，等.基于卡爾曼濾波與均值漂移算法的目標跟蹤[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濾波和邊緣直方圖的實時目標跟蹤[J].清華大學學報：自然科學版，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.