基于灰色馬爾可夫模型的均值偏移算法

歐陽颯颯，冀小平

（太原理工大學信息工程學院，山西太原 030024）

基于灰色馬爾可夫模型的均值偏移算法

歐陽颯颯，冀小平

（太原理工大學信息工程學院，山西太原 030024）

針對Mean Shift算法中存在的不足，提出了結合均值偏移和灰色馬爾可夫預測模型的目標跟蹤算法。該方法利用灰色馬爾可夫模型預測目標在當前時刻的中心位置，以此點作為均值偏移算法進行目標搜索的起始位置。同時，提取目標的幾何特征，根據目標的面積來改善跟蹤窗口的大小，利用“目標模型”和“候選模型”之間目標特征的變化產生模型更新策略。經實驗得，該方法能實時穩健地進行跟蹤。

Mean Shift;灰色馬爾可夫預測模型;幾何特征;目標跟蹤

【本文獻信息】歐陽颯颯，冀小平.基于灰色馬爾可夫模型的均值偏移算法［J］.電視技術，2013，37（3）.

Comaniciu等［1］提出的基于Mean Shift的跟蹤算法取得了很大成功，并且吸引了越來越多學者的研究興趣。Mean Shift算法是一種非參數密度估算法，它具有良好的實時性，且對形變、目標遮掩的穩健性良好，易于與其他算法集成，廣泛地應用于目標跟蹤中。但該算法也存在一定的缺陷，為了解決傳統均值偏移算法不能自適應改變核函數帶寬的缺陷，Collins等將Lindeberg尺度的空間理論和Mean Shift算法相結合［2］，并在某種程度上改善了此缺陷;Li Jinping等提出了采用Level Set描述目標輪廓方法與Mean Shift算法組合進行跟蹤，使得在光線變化、目標顏色發生改變時取得好的效果［3］，改善了相似顏色干擾問題;為了解決遮擋情況下均值偏移算法的跟蹤缺陷，許多學者采用了目標預測結合Mean Shift的跟蹤方法，Maggio E等提出了采用粒子濾波結合Mean Shift算法的跟蹤［4］，取得了好的跟蹤效果，但計算量大。

本文在灰色GM（1，1）模型的基礎上引入馬爾可夫鏈預測理論，建立運動目標的灰色馬爾可夫GM（1，1）預測模型，利用少量的數據來預測目標的運動軌跡，并以當前時刻的目標預測位置作為Mean Shift算法進行迭代搜索的起始位置;利用提取的幾何特征表示相似度函數來自適應性地更新搜索窗口，以此減少迭代次數，最后根據模型更新策略來更新目標模擬。

1 Mean Shift算法

Mean Shift算法是一個自適應地尋找概率密度局部最大值的迭代方法。在目標跟蹤中，采用歸一化的加權顏色直方圖來描述目標模型。假定跟蹤目標的中心位于x0，xi是d維Euclidean空間Rd中的一組點，用向量表示xi（i=1，2，…，n），使用帶寬為h的核函數K（x）作為多變量核密度估計，則目標模型可以表示為

u個直方圖，該函數值為1，否則為0。

令候選模型的中心坐標為y，則可以描述為

pu與qu（y）的相似性用Bhattacharyya系數^ρ（y）來度量，即

從式（3）可以看出，兩個模型越相似，則^ρ（y）的值越大，為使其值最大，令yk表示目標的初始位置，將^ρ（y）在該點進行一階泰勒展開求導為零，可以得到Mean Shift向量

2 灰色馬爾可夫預測模型

灰色系統預測的概念是由鄧聚龍教授首先在國內提出，之后灰色系統理論的研究得到了迅速發展?；疑A測方法的優點在于對缺少基礎資料的預測能夠得到較好的預測效果，與別的預測方法相比較而言它用到的樣本數據較小，而預測的精度相對較高。馬爾可夫概率矩陣是對隨機過程每個時刻狀態的描述，它是根據狀態之間的轉移概率來預測系統的發展，把在不相同狀態范圍的內在波動規律展現出來，使隨機作用造成的波動得以修正。灰色馬爾可夫預測模型就是將兩者的優勢相結合進行預測。

2.1 建立 GM（1，1）模型

假設有原始序列為

將該序列x（0）進行一次累加生成處理，得到x（1）（記作1－AGO）

建立GM（1，1）灰微分方程

式中:a為發展系數;b為灰作用量，是待估參數。

把式（7）轉化為矩陣方程

GM（1，1）模型的離散響應方程為

2.2 建立轉移概率矩陣

由狀態i經k步轉到狀態j的頻率也可以用式（14）來表示，將狀態轉移概率依次排序，可得到矩陣

從以上分析可知，灰色GM（1，1）模型用來預測目標軌跡變化的總趨勢，對其軌跡狀態的修正則是通過馬爾可夫轉移概率矩陣來完成的，最終精確地預測出目標的位置，為均值偏移算法提供搜索初始位置，避免了由于遮擋造成的目標丟失。

3 Mean Shift算法和灰色馬爾可夫模型的結合

跟蹤的過程中，會產生一系列的時間序列{yi}，i=1，2，…，表示迭代的次數，這種時間序列有平穩收斂（呈遞增和遞減兩種形式分布）和波動收斂（呈交替狀分布）兩種形式。針對這兩種形式，可以采用灰色馬爾可夫模型進行目標中心位置的預測。在Mean Shift搜索之前先進行目標在下一幀中位置的初步預測，并用預測中心位置作為目標搜索的起始位置，之后再進行迭代搜索，不僅可以提高搜索準確性，還能夠減少迭代搜索次數?；疑R爾可夫模型采用“新陳代謝”更新策略，保證用于預測的數據是最新的，一般用當前幀的前4幀數據作為基本數據，既保證了預測的準確性，也減少計算量。

如圖1所示，提取的顏色特征用于傳統的Mean Shift算法進行迭代計算，找出最匹配的目標位置，具體過程見本文第2節;利用文獻［6］中的迭代投影算法來近視計算目標的面積，通過前后兩幀面積的差值來判斷是否更新跟蹤窗口的大小;再設置一個閥值，根據相鄰兩幀的目標面積的比值是否小于閥值來判斷是否更新目標模型，避免了目標模型過更新。

圖1 本文算法流程圖

4 實驗結果與分析

本文實驗使用的硬件平臺為2.53 GHz的CPU、2 Gbyte內存，在Windows7操作系統下的計算機，軟件平臺為MATLAB 2010a編程環境。測試視頻選取一段橄欖球的運動視頻序列，視頻圖像大小為352×288，共88幀。根據反復的實驗，選取模板更新閾值為0.2。在整個視頻序列中，橄欖球的運動都是隨機波動的，前42幀被跟蹤的橄欖球從大到小，再從小到大，其大小一直在不斷變化;后40多幀發生遮擋情況。

圖2為傳統的均值偏移算法跟蹤的仿真圖，當球的大小不斷變化時，跟蹤窗口不能自適應地調整大小，當球快速運動時，目標窗口的中心位置嚴重偏移，在42幀發生遮擋時，跟蹤失敗，跟蹤窗口停留在第42幀時的位置。本文算法的仿真圖如圖3所示，根據灰色馬爾可夫模型和均值偏移算法相結合，在球快速運動時能準確地確定目標的中心位置，再根據提取目標的幾何特征的變化來改善跟蹤窗口的大小，能很好地進行實施跟蹤，效果也比傳統的均值偏移算法要好;在發生遮擋時，以灰色馬爾可夫GM（1，1）的預測值為中心來開窗，避免丟失跟蹤目標。從兩個仿真圖來看，本文提出的算法要優于傳統的均值偏移算法，可以取得良好的實時性和穩健性。

5 結論

當在運動目標跟蹤的過程中，發生遮擋、多種運動方式存在的情況下，本文提出通過灰色GM（1，1）模型對目標的運動軌跡進行總趨勢預測，再用馬爾可夫概率轉移矩陣來對軌跡進行修正，這樣能準確預測出目標在每一幀中的中心位置，并比一般的預測方法計算量小、精度高;再結合Mean Shift算法進行匹配跟蹤，最終確定目標。其中通過提取的幾何特征的變化來更新跟蹤窗口和目標模型，這樣可以適應目標的尺度變化和避免了目標模型的過更新。實驗表明，該方法能夠對目標進行實時有效的跟蹤。

:

［1］COMANICIU D，RAMESH V，MEER P.Real－time tracking of non－rigid objects using mean Shift［C］//Proc.IEEE Conference on Computer Vision and Pattern Recognition 2000.［S.l.］:IEEE Press，2000:142－149.

［2］COLLINS R T.Mean Shift blob tracking through scale space［C］//Proc.IEEE Conference on Computer Vision and Pattern Recognition 2003.［S.l.］:IEEE Press，2003:234－240.

［3］LI J P，LI Q J.Real－time tracking by combining level set and Mean Shift［J］.Journal of Information ＆ Computational Science，2008，5（2）:829－836.

［4］MAGGIO E，CAVALLARO A.Hybrid particle filter and mean shift tracker with adaptive transition model［C］//Proc.ICASSP 2005.［S.l.］:IEEE Press，2005:221－224.

［5］鄧聚龍.灰色系統理論教程［M］.武漢:華中理工大學出版社，1992.

［6］葉有時，唐林波，趙保軍，等.基于SOPC的深空目標實時跟蹤系統［J］.系統工程與電子技術，2009，31（12）:3002－3006.

Grey Markov Model－based Mean Shift Algorithm

OUYANG Sasa，JI Xiaoping

（Collge of Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China）

According to the existing shortcomings of Mean Shift algorithm，a combination of Mean Shift and the grey Markov forecasting model of the target tracking algorithm is presented.The method utilizes the gray Markov model to predict the center of the target at the present time，and this point is used for a starting position of the tracking window in the Mean Shift algorithm.Meanwhile，a geometric characteristics of the target is extracted.And then，the size of the tracking window is resized on the basis of the target area.The target characteristics’change between the target model and the candidate model is used to produce the model update strategy.By means of experiments，the method is validated to have a good real－time and robustness.

Mean Shift;Grey Markov forecasting model;geometric characteristics;target tracking

TP911.73;TP391.4

A

責任編輯:時 雯

2012－07－23