孫玉秋，胡維

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

黎雄

(北京師范大學(xué)數(shù)學(xué)學(xué)院，北京 100875)

帶寬自適應(yīng)的Mean-Shift跟蹤算法

孫玉秋，胡維

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

黎雄

(北京師范大學(xué)數(shù)學(xué)學(xué)院，北京 100875)

針對(duì)傳統(tǒng)Mean-Shift目標(biāo)跟蹤算法在進(jìn)行物體跟蹤時(shí)核函數(shù)帶寬不能實(shí)時(shí)更新的問(wèn)題，提出了一種基于比較中心加權(quán)直方圖與邊緣加權(quán)直方圖的巴氏相似度的帶寬自適應(yīng)算法。首先，手動(dòng)選取需要跟蹤的目標(biāo)，計(jì)算目標(biāo)模板的中心加權(quán)直方圖與邊緣加權(quán)直方圖以及二者的巴氏相似度HistDist1；然后，在當(dāng)前幀通過(guò)Mean-Shift迭代找到目標(biāo)的中心，并計(jì)算出候選模板的邊緣加權(quán)直方圖以及目標(biāo)模板中心加權(quán)直方圖與候選模板邊緣加權(quán)直方圖的巴氏相似度HistDist2；最后，在設(shè)定范圍內(nèi)比較巴氏相似度HistDist1與HistDist2的大小，得到目標(biāo)的尺寸變化情況。試驗(yàn)結(jié)果表明，該算法可以適應(yīng)尺寸發(fā)生變化的目標(biāo)跟蹤，實(shí)現(xiàn)了核函數(shù)帶寬的自適應(yīng)。

帶寬自適應(yīng)；目標(biāo)跟蹤；Mean-Shift算法；巴氏相似度；核函數(shù)

Mean-Shift算法由Fukunaga于1975年提出，是一種基于密度梯度的無(wú)參數(shù)估計(jì)方法。1995年，Cheng將其引入計(jì)算機(jī)視覺領(lǐng)域,取得了較好的跟蹤效果[1～3]。盡管Mean-Shift算法的實(shí)時(shí)性好，利于跟蹤，但是當(dāng)目標(biāo)在運(yùn)動(dòng)過(guò)程中發(fā)生尺度變化時(shí)，將得到很差的跟蹤結(jié)果。Mean-Shift算法不僅對(duì)目標(biāo)的尺寸變化敏感，而且缺乏對(duì)模板的實(shí)時(shí)更新，并且對(duì)目標(biāo)的描述僅用顏色特征，容易受背景影響[4，5]。

文獻(xiàn)[1]用仿射變換來(lái)描述目標(biāo)形狀、尺寸的變化，但是運(yùn)算量較大；文獻(xiàn)[3]通過(guò)比較目標(biāo)模板和候選模板的中心加權(quán)直方圖與邊緣加權(quán)直方圖的相似度，實(shí)現(xiàn)跟蹤窗的自動(dòng)縮放。這種方法沒(méi)有對(duì)相似度比較進(jìn)行限制，在實(shí)際中容易造成窗口不斷變小或者變大，甚至進(jìn)入死循環(huán)；文獻(xiàn)[6]分別對(duì)帶寬加減Δh, 然后與h比較，選出其中Bhattacharyya系數(shù)最大的作為新的帶寬h，然而這種猜測(cè)性的比較難以取得好的跟蹤效果，容易造成搜索窗不斷變??；文獻(xiàn)[7]和文獻(xiàn)[8]分別將灰度特征與邊緣特征相結(jié)合，并且文獻(xiàn)[7]應(yīng)用的是模糊方法，但都對(duì)跟蹤環(huán)境的要求較高；文獻(xiàn)[9]結(jié)合SIFT特征和Kalman濾波以及Mean-Shift算法，可以取得好的跟蹤效果，但是在很大程度增加了時(shí)間復(fù)雜度。

中心加權(quán)直方圖可以有效的減少目標(biāo)邊緣背景的影響，可以準(zhǔn)確獲得目標(biāo)中心。邊緣加權(quán)直方圖突出目標(biāo)邊緣的像素分布，通過(guò)比較目標(biāo)的邊緣加權(quán)直方圖的相似度，可以有效的反映出目標(biāo)的尺寸變化。就目標(biāo)尺寸的變化問(wèn)題，筆者提出了一種有效的更新核函數(shù)帶寬算法。首先選取待跟蹤的目標(biāo)，用帶寬h計(jì)算模板目標(biāo)的中心加權(quán)直方圖quc和邊緣加權(quán)直方圖qub，用巴氏相似度計(jì)算二者的相似系數(shù)HistDist1，并用帶寬h進(jìn)行Mean-Shift迭代，得到新的目標(biāo)中心y；然后用帶寬h和中心y，計(jì)算候選目標(biāo)的邊緣加權(quán)直方圖pub，并與模板目標(biāo)的中心加權(quán)直方圖quc進(jìn)行巴氏相似度計(jì)算，得到相似度系數(shù)HistDist2；最后比較kiHistDist1與HistDist2的大小，確定增大或縮小搜索窗，并以新的搜索窗對(duì)下一幀進(jìn)行目標(biāo)定位與跟蹤。

1 Mean-Shift算法

在Mean-Shift算法跟蹤過(guò)程中，通過(guò)比較核函數(shù)加權(quán)下的目標(biāo)模板與候選模板的顏色直方圖，使搜索窗沿梯度增大方向移動(dòng)，得到新的目標(biāo)位置。

1.1 目標(biāo)模型

通過(guò)人工選取需要跟蹤的目標(biāo)作為跟蹤模板，以目標(biāo)的顏色分布作為目標(biāo)特征，得到目標(biāo)的顏色概率直方圖，第u個(gè)特征值的概率為:

(1)

1.2 候選模型

類似的，在第N*幀中，計(jì)算出在上一幀的搜索窗內(nèi)的像素的分布直方圖，第u個(gè)特征值的概率為：

(2)

1.3 核函數(shù)

為減小目標(biāo)周圍背景像素的影響，實(shí)現(xiàn)對(duì)目標(biāo)中心的強(qiáng)調(diào)，使用式(3)表示的凸函數(shù)作為核函數(shù)進(jìn)行中心加權(quán)：

(3)

同樣，為展示目標(biāo)在移動(dòng)時(shí)邊緣像素發(fā)生的變化，使用式(4)表示的凹函數(shù)作為核函數(shù)對(duì)目標(biāo)進(jìn)行邊緣加權(quán):

(4)

核函數(shù)示意圖如圖1所示。

圖1 核函數(shù)示意圖

1.4 巴氏相似度(Bhattacharyya系數(shù))

巴氏相似度由統(tǒng)計(jì)學(xué)家Bhattacharyya提出，是一種用來(lái)計(jì)算2個(gè)離散或連續(xù)概率分布的相似性的方法，是向量相似度匹配中最常用的算法。直方圖qu與pu的相似度計(jì)算公式如下：

(5)

根據(jù)巴氏相似度計(jì)算模板目標(biāo)中心加權(quán)直方圖與邊緣加權(quán)直方圖的相似度HistDist1, 同理計(jì)算模板目標(biāo)中心加權(quán)直方圖與候選目標(biāo)邊緣加權(quán)直方圖的相似度HistDist2。

1.5 Mean-Shift目標(biāo)跟蹤

在算法實(shí)現(xiàn)過(guò)程中，分別用式(1)和式(2)表示模板目標(biāo)和候選目標(biāo)，用Bhattacharyya系數(shù)ρ表示他們之間的匹配程度：

(6)

在初始幀，手動(dòng)選取需要跟蹤的目標(biāo)，得到目標(biāo)初始中心位置y0，在之后的每一幀，用式(7)進(jìn)行迭代得到目標(biāo)新的中心，實(shí)現(xiàn)目標(biāo)的跟蹤：

(7)

然而，在實(shí)際應(yīng)用中，目標(biāo)的尺寸通常是變化的，如果不實(shí)時(shí)更新跟蹤窗帶寬，將會(huì)跟丟目標(biāo)。

2 基于巴氏相似度的核帶寬更新

通過(guò)計(jì)算目標(biāo)模板自身的中心加權(quán)直方圖與邊緣加權(quán)直方圖的巴氏相似度以及目標(biāo)模板的中心加權(quán)直方圖和候選模板的邊緣加權(quán)直方圖的巴氏相似度，并且在設(shè)定范圍內(nèi)比較這2個(gè)相似度的大小，從而實(shí)現(xiàn)核函數(shù)帶寬的實(shí)時(shí)更新。

2.1 邊緣加權(quán)與中心加權(quán)

事實(shí)上，模板目標(biāo)自身中心加權(quán)直方圖與自身邊緣加權(quán)直方圖的相似度，多數(shù)情況大于模板目標(biāo)中心加權(quán)直方圖與候選目標(biāo)邊緣加權(quán)直方圖的相似度。見表1。其中，HistDist1為目標(biāo)模板的中心加權(quán)直方圖與自身的邊緣加權(quán)直方圖的相似度；HistDist2為目標(biāo)模板的中心加權(quán)直方圖與下一幀的邊緣加權(quán)直方圖的相似度；HistDist3為目標(biāo)的中心加權(quán)直方圖與下一幀的搜索窗縮小的邊緣加權(quán)直方圖的相似度；HistDist4為目標(biāo)的中心加權(quán)直方圖與下一幀的搜索窗變大的邊緣加權(quán)直方圖的相似度。

表1 相似度大小變化情況

注：Hi即為文中的HistDisti。

比較表1的H1和H2可以看出，目標(biāo)模板的中心加權(quán)直方圖與自身的邊緣加權(quán)直方圖之間的相似度，幾乎遠(yuǎn)大于目標(biāo)模板的中心加權(quán)直方圖與下一幀的邊緣加權(quán)直方圖的相似度。比較H3和H4可以看出，當(dāng)搜索窗縮小時(shí)，相比于HistDist2(即搜索窗大小不變時(shí))，相似度變??；當(dāng)搜索窗變大時(shí)，相似度變大。根據(jù)這一變化規(guī)律可以確定目標(biāo)的縮放情況。

2.2 帶寬自適應(yīng)算法實(shí)現(xiàn)

由于在多數(shù)情況下，HistDist1 一定大于HistDist2，因此，在比較兩者大小關(guān)系時(shí)，需要加上一個(gè)比例系數(shù)k，即，如果kHistDist1HistDist2(0

圖2 中心加權(quán)直方圖與邊緣加權(quán)直方圖

當(dāng)目標(biāo)尺寸發(fā)生大小變化時(shí)，搜索窗應(yīng)當(dāng)保持同等大小的變化。如果kHistDist1

1) 讀取視頻文件，選取待跟蹤的目標(biāo)，用帶寬h計(jì)算模板目標(biāo)的中心加權(quán)直方圖quc和邊緣加權(quán)直方圖qub，用巴氏相似度計(jì)算二者的相似系數(shù)HistDist1；

2) 在當(dāng)前幀，用帶寬h進(jìn)行Mean-Shift迭代，得到新的目標(biāo)中心y；

3) 用帶寬h和中心y，計(jì)算候選目標(biāo)的邊緣加權(quán)直方圖pub，并與模板目標(biāo)的中心加權(quán)直方圖quc進(jìn)行巴氏相似度計(jì)算，得到相似度系數(shù)HistDist2；

4) 比較kiHistDist1與HistDist2的大小，如果k1HistDist1

5) 用新的帶寬h和新的目標(biāo)中心y對(duì)下一幀進(jìn)行目標(biāo)定位與跟蹤。

圖3 帶寬自適應(yīng)目標(biāo)跟蹤算法流程圖

3 試驗(yàn)結(jié)果分析

對(duì)實(shí)時(shí)車輛的跟蹤結(jié)果如圖4所示，其中紅色方框?yàn)樗阉骺颍{(lán)色線條為跟蹤軌跡；最左側(cè)一列為目標(biāo)尺寸變小的情況，車輛由近至遠(yuǎn)逐漸變??；右側(cè)為目標(biāo)尺寸變大的情況，車輛由遠(yuǎn)到近尺寸逐漸變大。由圖4可以看出，對(duì)于這2種情況，筆者提出的算法都能夠?qū)崟r(shí)準(zhǔn)確的檢測(cè)并標(biāo)出目標(biāo)所在位置，實(shí)現(xiàn)了搜索窗的大小隨著目標(biāo)尺寸變化而自動(dòng)變化。因此，相比于傳統(tǒng)Mean-Shift跟蹤算法在跟蹤過(guò)程中搜索窗大小不變的情況，該算法可以自動(dòng)適應(yīng)跟蹤目標(biāo)的尺寸變化，并且能夠?qū)崿F(xiàn)核函數(shù)帶寬的實(shí)時(shí)更新，有更好的跟蹤效果。

筆者提出的算法通過(guò)結(jié)合目標(biāo)的中心加權(quán)直方圖與邊緣加權(quán)直方圖，并且對(duì)目標(biāo)模板與候選模板的比較進(jìn)行系數(shù)限制，可以很好的滿足并且適應(yīng)目標(biāo)尺寸發(fā)生的變化。相比于文獻(xiàn)[1]的仿射變換，該算法計(jì)算量更少，更能適應(yīng)實(shí)時(shí)跟蹤的要求。相比于文獻(xiàn)[3]直接比較中心加權(quán)直方圖與邊緣加權(quán)直方圖，文獻(xiàn)[6]猜測(cè)性的選取核函數(shù)帶寬，該算法有效解決了核函數(shù)帶寬在一些情況下只能變小以至于搜索窗不斷縮小的問(wèn)題；相比于文獻(xiàn)[7]和[8]，算法對(duì)環(huán)境的要求降低；相比于文獻(xiàn)[9]，算法在時(shí)間復(fù)雜度上更有優(yōu)勢(shì)。

4 結(jié)語(yǔ)

傳統(tǒng)Mean-Shift跟蹤算法以直方圖作為目標(biāo)特征，并且缺乏模板更新，帶寬大小不變。筆者提出的算法基于傳統(tǒng)的Mean-Shift跟蹤算法，改進(jìn)了傳統(tǒng)算法帶寬不變的缺點(diǎn)，實(shí)現(xiàn)了跟蹤的帶寬自適應(yīng)。在試驗(yàn)過(guò)程中發(fā)現(xiàn)，在更新帶寬的過(guò)程中，同時(shí)對(duì)搜索窗的長(zhǎng)和寬進(jìn)行同比例縮放，當(dāng)目標(biāo)的長(zhǎng)寬比例發(fā)生變化時(shí)，可能跟丟目標(biāo)；對(duì)于速度過(guò)快的目標(biāo)，傳統(tǒng)的目標(biāo)跟蹤算法搜索窗中心的更新跟不上目標(biāo)的移動(dòng)。后期對(duì)這個(gè)方向的進(jìn)一步研究將會(huì)有重大意義。

[1]朱勝利，朱善安. 核函數(shù)帶寬自適應(yīng)的Mean-Shift目標(biāo)跟蹤算法[J].光電工程, 2006, 33(8): 0011～0016.

[2]ChengY.Meanshift,modeseeking,andclustering[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1995, 17(8): 790～799.

[3]陳昌濤, 朱勤, 周圣毅, 等. 核函數(shù)帶寬自適應(yīng)的Mean-Shift跟蹤算法[J].計(jì)算機(jī)應(yīng)用, 2009, 29(6): 1680～1682.

[4]ZhangHuanqing,GeHongwei,YangJinlong.AdaptiveGaussianmixtureprobabilityhypothesisdensityfortrackingmultipletargets[J].Optik, 2016, 127: 3918～3924.

[5]YanZouguo,LiangWeiguo,LvHaidong.ATargetTrackingAlgorithmBasedonImprovedCamshiftandUKF[J].SoftwareEngineeringandApplications, 2014, 7: 1065～1073.

[6]ComaniciuD,RameshV,MeerP.Kernel-BasedObjectTracking[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2003, 25(5): 665～676.

[7]XiaoGang,YunXiao,WuJianMin.Amulti-cuemean-shifttargettrackingapproachbasedonfuzzifiedregiondynamicimagefusion[J].ScienceChina, 2012, 3(55): 577～589.

[8]ZhengHaichao,MaoXia,ChenLijiang,etal.Adaptiveedge-basedmeanshiftfordrasticchangegraytargettracking[J].Optik, 2015, 126: 3859～3867.

[9]朱志玲, 阮秋琦. 結(jié)合尺度不變特征變換和Kalman濾波的MeanShift視頻運(yùn)動(dòng)目標(biāo)跟蹤[J].計(jì)算機(jī)應(yīng)用, 2013, 33(11): 3179～3243.

[編輯] 洪云飛

2016-11-05

國(guó)家自然科學(xué)基金項(xiàng)目(11571041)；湖北省自然科學(xué)基金資助項(xiàng)目(2013CFA053)。

孫玉秋(1968-)，女，博士，教授，博士生導(dǎo)師，現(xiàn)主要從事數(shù)字圖像處理、模式識(shí)別與目標(biāo)檢測(cè)方面的教學(xué)與研究工作,yqsun@yangtzeu.edu.cn。

TP391

A

1673-1409(2017)01-0005-07

[引著格式]孫玉秋，胡維，黎雄.帶寬自適應(yīng)的Mean-Shift跟蹤算法[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)，2017,14(1)：5～11.