帶寬自適應的Mean-Shift跟蹤算法

孫玉秋，胡維

(長江大學信息與數學學院，湖北 荊州 434023)

黎雄

(北京師范大學數學學院，北京 100875)

帶寬自適應的Mean-Shift跟蹤算法

孫玉秋，胡維

(長江大學信息與數學學院，湖北 荊州 434023)

黎雄

(北京師范大學數學學院，北京 100875)

針對傳統Mean-Shift目標跟蹤算法在進行物體跟蹤時核函數帶寬不能實時更新的問題，提出了一種基于比較中心加權直方圖與邊緣加權直方圖的巴氏相似度的帶寬自適應算法。首先，手動選取需要跟蹤的目標，計算目標模板的中心加權直方圖與邊緣加權直方圖以及二者的巴氏相似度HistDist1；然后，在當前幀通過Mean-Shift迭代找到目標的中心，并計算出候選模板的邊緣加權直方圖以及目標模板中心加權直方圖與候選模板邊緣加權直方圖的巴氏相似度HistDist2；最后，在設定范圍內比較巴氏相似度HistDist1與HistDist2的大小，得到目標的尺寸變化情況。試驗結果表明，該算法可以適應尺寸發生變化的目標跟蹤，實現了核函數帶寬的自適應。

帶寬自適應；目標跟蹤；Mean-Shift算法；巴氏相似度；核函數

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

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

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

1 Mean-Shift算法

在Mean-Shift算法跟蹤過程中，通過比較核函數加權下的目標模板與候選模板的顏色直方圖，使搜索窗沿梯度增大方向移動，得到新的目標位置。

1.1 目標模型

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

(1)

1.2 候選模型

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

(2)

1.3 核函數

為減小目標周圍背景像素的影響，實現對目標中心的強調，使用式(3)表示的凸函數作為核函數進行中心加權：

(3)

同樣，為展示目標在移動時邊緣像素發生的變化，使用式(4)表示的凹函數作為核函數對目標進行邊緣加權:

(4)

核函數示意圖如圖1所示。

圖1 核函數示意圖

1.4 巴氏相似度(Bhattacharyya系數)

巴氏相似度由統計學家Bhattacharyya提出，是一種用來計算2個離散或連續概率分布的相似性的方法，是向量相似度匹配中最常用的算法。直方圖qu與pu的相似度計算公式如下：

(5)

根據巴氏相似度計算模板目標中心加權直方圖與邊緣加權直方圖的相似度HistDist1, 同理計算模板目標中心加權直方圖與候選目標邊緣加權直方圖的相似度HistDist2。

1.5 Mean-Shift目標跟蹤

在算法實現過程中，分別用式(1)和式(2)表示模板目標和候選目標，用Bhattacharyya系數ρ表示他們之間的匹配程度：

(6)

在初始幀，手動選取需要跟蹤的目標，得到目標初始中心位置y0，在之后的每一幀，用式(7)進行迭代得到目標新的中心，實現目標的跟蹤：

(7)

然而，在實際應用中，目標的尺寸通常是變化的，如果不實時更新跟蹤窗帶寬，將會跟丟目標。

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

通過計算目標模板自身的中心加權直方圖與邊緣加權直方圖的巴氏相似度以及目標模板的中心加權直方圖和候選模板的邊緣加權直方圖的巴氏相似度，并且在設定范圍內比較這2個相似度的大小，從而實現核函數帶寬的實時更新。

2.1 邊緣加權與中心加權

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

表1 相似度大小變化情況

注：Hi即為文中的HistDisti。

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

2.2 帶寬自適應算法實現

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

圖2 中心加權直方圖與邊緣加權直方圖

當目標尺寸發生大小變化時，搜索窗應當保持同等大小的變化。如果kHistDist1

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

2) 在當前幀，用帶寬h進行Mean-Shift迭代，得到新的目標中心y；

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

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

5) 用新的帶寬h和新的目標中心y對下一幀進行目標定位與跟蹤。

圖3 帶寬自適應目標跟蹤算法流程圖

3 試驗結果分析

對實時車輛的跟蹤結果如圖4所示，其中紅色方框為搜索框，藍色線條為跟蹤軌跡；最左側一列為目標尺寸變小的情況，車輛由近至遠逐漸變小；右側為目標尺寸變大的情況，車輛由遠到近尺寸逐漸變大。由圖4可以看出，對于這2種情況，筆者提出的算法都能夠實時準確的檢測并標出目標所在位置，實現了搜索窗的大小隨著目標尺寸變化而自動變化。因此，相比于傳統Mean-Shift跟蹤算法在跟蹤過程中搜索窗大小不變的情況，該算法可以自動適應跟蹤目標的尺寸變化，并且能夠實現核函數帶寬的實時更新，有更好的跟蹤效果。

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

4 結語

傳統Mean-Shift跟蹤算法以直方圖作為目標特征，并且缺乏模板更新，帶寬大小不變。筆者提出的算法基于傳統的Mean-Shift跟蹤算法，改進了傳統算法帶寬不變的缺點，實現了跟蹤的帶寬自適應。在試驗過程中發現，在更新帶寬的過程中，同時對搜索窗的長和寬進行同比例縮放，當目標的長寬比例發生變化時，可能跟丟目標；對于速度過快的目標，傳統的目標跟蹤算法搜索窗中心的更新跟不上目標的移動。后期對這個方向的進一步研究將會有重大意義。

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

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

[3]陳昌濤, 朱勤, 周圣毅, 等. 核函數帶寬自適應的Mean-Shift跟蹤算法[J].計算機應用, 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]朱志玲, 阮秋琦. 結合尺度不變特征變換和Kalman濾波的MeanShift視頻運動目標跟蹤[J].計算機應用, 2013, 33(11): 3179～3243.

[編輯] 洪云飛

2016-11-05

國家自然科學基金項目(11571041)；湖北省自然科學基金資助項目(2013CFA053)。

孫玉秋(1968-)，女，博士，教授，博士生導師，現主要從事數字圖像處理、模式識別與目標檢測方面的教學與研究工作,yqsun@yangtzeu.edu.cn。

TP391

A

1673-1409(2017)01-0005-07

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