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

歐陽颯颯，冀小平

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

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

歐陽颯颯，冀小平

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

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

Mean Shift;灰色馬爾可夫預(yù)測模型;幾何特征;目標(biāo)跟蹤

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

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

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

1 Mean Shift算法

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

u個(gè)直方圖，該函數(shù)值為1，否則為0。

令候選模型的中心坐標(biāo)為y，則可以描述為

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

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

2 灰色馬爾可夫預(yù)測模型

灰色系統(tǒng)預(yù)測的概念是由鄧聚龍教授首先在國內(nèi)提出，之后灰色系統(tǒng)理論的研究得到了迅速發(fā)展。灰色預(yù)測方法的優(yōu)點(diǎn)在于對缺少基礎(chǔ)資料的預(yù)測能夠得到較好的預(yù)測效果，與別的預(yù)測方法相比較而言它用到的樣本數(shù)據(jù)較小，而預(yù)測的精度相對較高。馬爾可夫概率矩陣是對隨機(jī)過程每個(gè)時(shí)刻狀態(tài)的描述，它是根據(jù)狀態(tài)之間的轉(zhuǎn)移概率來預(yù)測系統(tǒng)的發(fā)展，把在不相同狀態(tài)范圍的內(nèi)在波動規(guī)律展現(xiàn)出來，使隨機(jī)作用造成的波動得以修正。灰色馬爾可夫預(yù)測模型就是將兩者的優(yōu)勢相結(jié)合進(jìn)行預(yù)測。

2.1 建立 GM（1，1）模型

假設(shè)有原始序列為

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

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

式中:a為發(fā)展系數(shù);b為灰作用量，是待估參數(shù)。

把式（7）轉(zhuǎn)化為矩陣方程

GM（1，1）模型的離散響應(yīng)方程為

2.2 建立轉(zhuǎn)移概率矩陣

由狀態(tài)i經(jīng)k步轉(zhuǎn)到狀態(tài)j的頻率也可以用式（14）來表示，將狀態(tài)轉(zhuǎn)移概率依次排序，可得到矩陣

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

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

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

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

圖1 本文算法流程圖

4 實(shí)驗(yàn)結(jié)果與分析

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

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

5 結(jié)論

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

:

［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］鄧聚龍.灰色系統(tǒng)理論教程［M］.武漢:華中理工大學(xué)出版社，1992.

［6］葉有時(shí)，唐林波，趙保軍，等.基于SOPC的深空目標(biāo)實(shí)時(shí)跟蹤系統(tǒng)［J］.系統(tǒng)工程與電子技術(shù)，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

責(zé)任編輯:時(shí) 雯

2012－07－23