一種新的基于分塊直方圖的Mean－Shift跟蹤算法

李群山，張 文

（1.電子科技大學(xué)光電信息學(xué)院，四川成都610054;2.內(nèi)江師范學(xué)院工程技術(shù)學(xué)院，四川內(nèi)江 641112）

目標(biāo)跟蹤是計(jì)算機(jī)視覺和圖像處理研究中的一個(gè)重要課題，其廣泛應(yīng)用于智能視頻監(jiān)控、軍事制導(dǎo)、智能機(jī)器人等視覺應(yīng)用領(lǐng)域［1-2］。目標(biāo)的顏色直方圖具有特征穩(wěn)定、抗部分遮擋、計(jì)算方法簡單和計(jì)算量小的特點(diǎn)，基于Mean-Shift的跟蹤一般采用直方圖對目標(biāo)進(jìn)行建模，然后通過相似度度量，最終實(shí)現(xiàn)目標(biāo)的匹配和跟蹤［1］。

均值漂移算法（Mean-Shift）是一種基于密度梯度上升的非參數(shù)方法，通過較少的幾次迭代運(yùn)算就能找到目標(biāo)位置。這種算法計(jì)算量小、計(jì)算速度快，體現(xiàn)出良好的實(shí)時(shí)性和穩(wěn)定性，適用于實(shí)時(shí)視頻的目標(biāo)跟蹤。經(jīng)典的Mean-Shift跟蹤算法用于目標(biāo)建模的顏色直方圖只是包含了顏色特征在目標(biāo)中出現(xiàn)的概率信息，沒有融入目標(biāo)的空間信息［3-7］。梁靜等人利用kalman濾波器和Mean-Shift相結(jié)合的方法跟蹤動(dòng)態(tài)背景下的運(yùn)動(dòng)目標(biāo)，解決了目標(biāo)被部分遮擋的情況［8-11］。

目標(biāo)的顏色通常分布在顏色空間的一個(gè)子空間，傳統(tǒng)的顏色直方圖通常將顏色空間均勻劃分（例如16×16×16或者32×32×32），這樣容易造成大量的空的顏色直方圖區(qū)間，不僅浪費(fèi)內(nèi)存空間，而且還增加了計(jì)算量。針對傳統(tǒng)顏色直方圖空閑率高，本文提出了簡化顏色直方圖的方法，針對傳統(tǒng)顏色直方圖沒有融入空間信息的缺點(diǎn)，提出了一種新的分塊直方圖構(gòu)建方法，這種分塊直方圖構(gòu)建方法簡單，而且保留了顏色直方圖的尺度和旋轉(zhuǎn)變化的不變性。

1 經(jīng)典Mean-Shift算法

1.1 目標(biāo)模型

設(shè){xi}，i=1，2，…，n表示目標(biāo)區(qū)域歸一化的n個(gè)像素集，x0為目標(biāo)區(qū)域的中心像素點(diǎn)。將顏色特征空間劃分成u=1，2，…，m個(gè)子空間，也就是直方圖上的m個(gè)bin。每個(gè)特征u=1，2，…，m在目標(biāo)區(qū)域的概率值為

假設(shè)候選目標(biāo)模型的在t時(shí)刻的中心位置為y;{xi}，i=1，2，…，Nb表示候選目標(biāo)區(qū)域的像素集，則相應(yīng)候選目標(biāo)模型在特征值u=1，2，…，m出現(xiàn)的概率可以表示為

1.2 相似性度量

經(jīng)典的Mean-Shift使用Bhattacharry系數(shù)度量目標(biāo)模型與候選目標(biāo)模型（y）之間的相似性。相似性定義為

跟蹤過程就是不斷獲得與目標(biāo)模型相似性最大的候選模型的過程，即求取式（3）最大值的過程。為求式（3）的最大值，令式（3）在（y0）處進(jìn)行Taylor式展開，并省略一些極小項(xiàng)，得

將式（2）代入式（4）得

要使式（3）最大也就是要使得式（5）最大，而式（5）的第一項(xiàng)為常量，則第二項(xiàng)最大時(shí)式（5）最大。結(jié)合Mean-Shift算法，得迭代公式為

式中，g（x）=－K'（x）。如果使用Epanechniko核函數(shù)，則（7）式進(jìn)一步簡化為

Mean-Shift算法的計(jì)算步驟:首先初始化y0，可令y0為最初的目標(biāo)中心;然后用式（6）計(jì)算wi，并利用式（7）計(jì)算獲得下一次迭代的位置;令y0=y1，進(jìn)行下一次迭代運(yùn)算，如此不斷地迭代計(jì)算式（6），（7），直到‖yi+1－yi‖ ＜ε，或達(dá)到最大迭代次數(shù)。最終由式（7）得到的位置就是目標(biāo)的準(zhǔn)確位置。

2 改進(jìn)的Mean-Shift算法

2.1 目標(biāo)顏色直方圖的簡化

在建立目標(biāo)顏色直方圖之前通常需要將顏色空間進(jìn)行量化，目前一般采用均勻量化顏色空間的方法，這樣可以減少計(jì)算量。但是目標(biāo)顏色通常緊湊分布在顏色空間的一部分子空間中，因而會(huì)造成大量空的顏色直方圖區(qū)間，或者取值極小的顏色直方圖區(qū)間。這樣不僅會(huì)浪費(fèi)大量的內(nèi)存空間，而且增加計(jì)算量。例如:圖1是經(jīng)常遇到的人臉跟蹤目標(biāo)，其顏色直方圖在16×16×16均勻量化的RGB顏色空間中，空的直方圖區(qū)間達(dá)到3 878個(gè)，空閑率達(dá)3 878/4 096=94.7%。若為這些空的直方圖區(qū)間分配內(nèi)存空間，按存儲類型為雙精度浮點(diǎn)型（8 byte）計(jì)算將是31 024 byte。若是在32×32×32量化空間，則空區(qū)間為32 550，空閑率達(dá)=32 550/32 768=99.3%，浪費(fèi)的內(nèi)存空間將是260 400 byte。圖2（圖2～圖11彩色圖見網(wǎng)址:http://blog.sina.com.cn/s/blog_b9be7b8501017gyc.html）色彩如此豐富，其在16×16×16均勻量化的RGB顏色空間中空的直方圖區(qū)間也達(dá)3 400個(gè)，空閑率為3 400/4 096=83%。而且在跟蹤過程中計(jì)算Bhattacharry系數(shù)時(shí)，為其還要付出一定的計(jì)算代價(jià)。

針對顏色直方圖空閑率非常高的情況，本文提出簡化顏色直方圖的方法，得到?jīng)]有空閑區(qū)間的直方圖;同時(shí)為了應(yīng)對在計(jì)算候選目標(biāo)顏色直方圖時(shí)會(huì)出現(xiàn)不同于初始跟蹤目標(biāo)顏色特征的像素的情況，在簡化的顏色直方圖后增加一個(gè)區(qū)間用于累積非初始跟蹤目標(biāo)顏色特征的像素。其計(jì)算步驟如下:

1）按照傳統(tǒng)方法統(tǒng)計(jì)得到顏色直方圖，并去除空直方圖區(qū)間。

2）保存剩下的顏色直方圖區(qū)間對應(yīng)的顏色特征值。

3）在經(jīng)過上面處理后的直方后增加一個(gè)區(qū)間，用于累積候選目標(biāo)中出現(xiàn)的非初始目標(biāo)顏色特征的像素。在初始目標(biāo)的直方圖中該區(qū)間的值為0，在候選目標(biāo)的直方圖中該區(qū)間的值為所有不屬于初始目標(biāo)顏色特征的像素總和歸一化后的值。

2.2 空間顏色直方圖的建立

假設(shè)某目標(biāo)Q的大小為N（即總像素點(diǎn)），f（x，y）是該目標(biāo)中的一點(diǎn)，f（x，y）表示目標(biāo)在該點(diǎn)的顏色值，（x，y）表示該點(diǎn)的坐標(biāo)，則其質(zhì)心為

該目標(biāo)中離該質(zhì)心（x0，y0）最大的距離為

圖3 圖像空間劃分示意圖

最后，根據(jù)前面顏色空間量化結(jié)果得到的m個(gè)顏色子特征空間，分別計(jì)算每個(gè)圓環(huán)區(qū)域內(nèi)的傳統(tǒng)顏色直方圖，得到最終的分塊顏色直方圖。其中第v個(gè)子空間的第u個(gè)顏色特征值為

式中:a（xi）表示該像素距離質(zhì)心的量化空間距離;δ［a（xi）－v］是Kronecker delta函數(shù)，當(dāng)該像素屬于第v個(gè)空間圓環(huán)時(shí)，函數(shù)值為1，否則為0。其他參數(shù)與傳統(tǒng)顏色直方圖相同。于是，目標(biāo)模型可表示為:q={quv}，u=1，2，…，m;v=1，2，…，w 。這樣得到的分塊顏色直方圖具有以往分塊直方圖不具有的尺度、旋轉(zhuǎn)不變性。

2.3 新分塊直方圖與傳統(tǒng)顏色直方圖的比較

為了驗(yàn)證新分塊直方圖的優(yōu)點(diǎn)，下面對兩個(gè)顏色分布相似物體的傳統(tǒng)顏色直方圖與新顏色空間直方圖進(jìn)行比較，來驗(yàn)證新分塊直方圖具有更好地區(qū)分顏色分布相似目標(biāo)的優(yōu)點(diǎn)。圖4、圖5表示顏色分布相似的兩個(gè)目標(biāo);圖6、圖7分別是圖4、圖5的傳統(tǒng)顏色直方圖;圖8、圖9分別是圖4、圖5的分塊顏色直方圖。為了顯示方便，以下的顏色直方圖在HSV顏色空間統(tǒng)計(jì)得到，歸一化系數(shù)為直方圖中區(qū)間值的最大值，分塊顏色直方圖的圓環(huán)數(shù)僅為3個(gè)。

利用Bhattacharry系數(shù)度量圖6與圖7之間的相似程度為0.98，而圖8與圖9之間的相似程度僅為0.80?？梢钥闯鲂骂伾狈綀D有更好地區(qū)分顏色分布相似目標(biāo)的能力。為了加大區(qū)分度可增加分塊的圓環(huán)數(shù)。

2.4 改進(jìn)后的Mean-Shift算法

根據(jù)分塊直方圖的計(jì)算方法不同，改進(jìn)后的Mean-Shift算法的Bhattacharry系數(shù)計(jì)算式為

將式（11）代入式（12）整理得

Meanshift算法的其他計(jì)算公式不變。

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

本文的所有實(shí)驗(yàn)在VS2008環(huán)境下及利用OpenCV完成，主機(jī)主頻1.9 GHz，內(nèi)存1 Gbyte。在RGB顏色空間計(jì)算顏色直方圖，顏色空間量化為16×16×16的子空間，目標(biāo)的初始化手動(dòng)完成，真值的標(biāo)注也由手動(dòng)完成。為了適應(yīng)尺度的變化，進(jìn)行增量正負(fù)10%的核窗寬調(diào)整。

3.1 實(shí)驗(yàn)一

實(shí)驗(yàn)視頻在辦公室環(huán)境拍攝，為了構(gòu)造顏色分布相似的目標(biāo)，實(shí)驗(yàn)中利用魔方作為跟蹤對象。視頻圖像大小為640×480。實(shí)驗(yàn)視頻拍攝的是魔方的變速運(yùn)動(dòng)及尺度變化的情形。實(shí)驗(yàn)結(jié)果如圖10所示。跟蹤目標(biāo)在X，Y坐標(biāo)軸上的誤差統(tǒng)計(jì)結(jié)果如圖11所示。實(shí)驗(yàn)畫面中的紅色框?yàn)楦倪M(jìn)后算法跟蹤結(jié)果，白色框?yàn)榻?jīng)典Mean-Shift算法跟蹤結(jié)果。

分析圖10和圖11可看出改進(jìn)后的Mean-Shift算法比經(jīng)典算法跟蹤目標(biāo)更加準(zhǔn)確，主要原因是分塊直方圖中融入了空間信息，使其描述目標(biāo)的能力比傳統(tǒng)顏色直方圖更準(zhǔn)確。

3.2 實(shí)驗(yàn)二

實(shí)驗(yàn)所用視頻拍攝的是兩個(gè)顏色分布相似魔方存在遮擋的情形。其中一個(gè)魔方靜止，另一個(gè)魔方運(yùn)動(dòng)。圖12的跟蹤試驗(yàn)中，跟蹤的目標(biāo)為運(yùn)動(dòng)的魔方，運(yùn)動(dòng)魔方逐漸運(yùn)動(dòng)到靜止魔方背后被遮擋的情形。圖13的跟蹤實(shí)驗(yàn)中，跟蹤目標(biāo)是靜止魔方，在實(shí)驗(yàn)中逐漸被運(yùn)動(dòng)魔方遮擋的情形。實(shí)驗(yàn)畫面中的紅色框?yàn)楦倪M(jìn)Mean-Shift算法跟蹤結(jié)果，白色框?yàn)榻?jīng)典Mean-Shift算法跟蹤結(jié)果。

在圖12實(shí)驗(yàn)中，在運(yùn)動(dòng)魔方被靜止魔方遮擋后再從靜止魔方后面運(yùn)動(dòng)出來時(shí)，白色框（經(jīng)典Mean-Shift算法跟蹤結(jié)果）跟蹤丟失，停留在靜止魔方上;而紅色框（改進(jìn)Mean-Shift算法跟蹤結(jié)果）卻能正確地進(jìn)行跟蹤。

圖12 運(yùn)動(dòng)目標(biāo)被遮擋跟蹤實(shí)驗(yàn)

圖13 靜止目標(biāo)被遮擋跟蹤實(shí)驗(yàn)

在圖13實(shí)驗(yàn)中，運(yùn)動(dòng)魔方逐漸從靜止魔方前面經(jīng)過，并完全遮擋了后面靜止的魔方，隨著運(yùn)動(dòng)的進(jìn)行，當(dāng)被遮擋的靜止魔方逐漸顯現(xiàn)出來時(shí)，白色框（經(jīng)典Mean-Shift算法跟蹤結(jié)果）跟蹤丟失，跟蹤到顏色相似的運(yùn)動(dòng)魔方上;而紅色框（改進(jìn)Mean-Shift算法跟蹤結(jié)果）卻能停留在了靜止魔方上，表示跟蹤正確。

4 結(jié)語

本文針對顏色直方圖空閑率高造成的內(nèi)存空間的浪費(fèi)問題提出了一種簡化顏色直方圖的計(jì)算方法，并提出了一種新的分塊顏色直方圖的構(gòu)造方法。實(shí)驗(yàn)結(jié)果表明基于新的分塊直方圖的Mean-Shift跟蹤算法比經(jīng)典的Mean-Shift算法具有更好的跟蹤穩(wěn)定性，在跟蹤顏色分布相似的目標(biāo)方面，特別是在相似目標(biāo)出現(xiàn)大部分遮擋情況下仍能穩(wěn)定地跟蹤目標(biāo)，與經(jīng)典Mean-Shift算法相比具有更穩(wěn)定的效果。

：

［1］宋新，沈振康，王平，等.Mean-Shift在目標(biāo)跟蹤中的應(yīng)用［J］.系統(tǒng)工程與電子技術(shù)，2007，29（9）:1405-1409.

［2］李培華.一種改進(jìn)的Mean-Shift跟蹤算法［J］.自動(dòng)化學(xué)報(bào)，2007，33（4）:347-354.

［3］FUKUNAGA K，HOSTETLER L.Estimation of the gradient of a density function and its applications in pattern recognition［J］.IEEE Trans.Information Theory，1975，21（1）:32-40.

［4］CHENG Yizong.Mean shift，mode seeking，and clustering［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，1995，17（8）:790-799.

［5］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2002，24（5）:603-619.

［6］COMANICIU D，RAMESH V，MEER P.Kernel-based object tracking［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2003，25（5）:564-577.

［7］COMANICIU D，RAMESH V，MEET P.Real-time tracking of non-rigid objects using mean shift［C］//Proc.IEEE Conference on Computer Vision and Pattern Recogniton，2000.［S.l.］:IEEE Press，2000:142-149.

［8］YILMAZ A，SHAFIQUE K，SHAH M.Target tracking in airborne forward looking infrared imagery［J］.Image and Vision Computing，2003（21）:623-635.

［9］BIRCHFIELD S T，RANGARAJAN S.Spatiograms versus histograms for region-based tracking［C］//Proc.Computer Vision and Pattern Recognition，2005.［S.l.］:IEEE Press，2005:1158-1163.

［10］袁光林，薛模根，謝愷，等.多顏色直方圖自適應(yīng)組合mean shift跟蹤［J］.中國圖象圖形學(xué)報(bào)，2011，16（10）:1832-1840.

［11］梁靜，支琤，周軍.基于mean shift的抗遮擋運(yùn)動(dòng)目標(biāo)跟蹤算法［J］.電視技術(shù)，2008，32（12）:82-85.