基于Mean Shift重要性采樣的粒子濾波跟蹤算法

劉 璞，王春平，徐 艷

（軍械工程學(xué)院 電子與光學(xué)工程系，河北 石家莊050003）

0 引 言

粒子濾波因其在非線性、非高斯系統(tǒng)中具有較強(qiáng)的魯棒性［1］，已經(jīng)被應(yīng)用于復(fù)雜情況下的目標(biāo)跟蹤，并且取得了良好的效果。但是粒子濾波算法仍存在一些缺陷，主要表現(xiàn)為兩個(gè)方面［2］：一是在粒子遞推的過程中，部分粒子的權(quán)值趨向于1，其它粒子的權(quán)值趨向于0，形成了粒子的退化現(xiàn)象，使粒子集無法準(zhǔn)確近似系統(tǒng)狀態(tài)的統(tǒng)計(jì)特性；二是為了提高粒子濾波算法的精度，往往采用大樣本量，這樣雖然精度提高了，但是增大了算法的計(jì)算量，影響目標(biāo)跟蹤的實(shí)時(shí)性。

粒子濾波能否取得好的效果很大程度上取決于粒子的傳播方式，即重要性采樣的設(shè)計(jì)，這是粒子濾波領(lǐng)域的一個(gè)研究熱點(diǎn)［3］。結(jié)合上述問題，本文提出了基于MS重要性采樣的粒子濾波跟蹤算法，該算法將MS算法融入到粒子濾波算法中，利用MS的迭代尋優(yōu)過程對(duì)粒子樣本進(jìn)行確定性搜索，使其收斂到局部最優(yōu)點(diǎn)，完成粒子的重要性采樣，同時(shí)能夠增大有效粒子權(quán)重，減少跟蹤過程采用的粒子數(shù)目，降低計(jì)算量，提高跟蹤的實(shí)時(shí)性。

1 Mean Shift算法

Mean Shift算法是一種非參數(shù)核函數(shù)估計(jì)方法［4］，在采樣充分的情況下，核函數(shù)估計(jì)能夠逐漸收斂于服從任意分布的密度函數(shù)，將以每個(gè)采樣點(diǎn)為中心的局部區(qū)域的平均效果作為該采樣點(diǎn)的概率密度估計(jì)值，最終綜合所有采樣點(diǎn)的密度估計(jì)結(jié)果，實(shí)現(xiàn)對(duì)目標(biāo)位置的穩(wěn)定預(yù)測(cè)［5］。

目標(biāo)的顏色特征對(duì)于目標(biāo)的尺度、旋轉(zhuǎn)或者變形具有較好的穩(wěn)定性［6］，因此采用顏色直方圖表達(dá)目標(biāo)特征有助于目標(biāo)的穩(wěn)定跟蹤［7］。本文根據(jù)MS 算法的核函數(shù)概念，利用目標(biāo)顏色分布建立目標(biāo)模型。核函數(shù)采用Epanechikov核函數(shù)

假設(shè)目標(biāo)區(qū)域的中心為x0，目標(biāo)區(qū)域內(nèi)的像素點(diǎn)用｛xi；i＝1，2，…N ｝表示，彩色圖像的每個(gè)顏色通道的特征值為u＝1，2，…M，對(duì)目標(biāo)區(qū)域進(jìn)行建模

式中：δ——Delta函數(shù)，C——常量系數(shù)，滿足

假設(shè)候選區(qū)域的中心為y0，根據(jù)式（2）可以同理得出，候選區(qū)域的目標(biāo)模型為

將候選區(qū)域的顏色分布與參考模板的顏色分布進(jìn)行對(duì)比，利用Bhattacharyya系數(shù)作為度量二者相似性的標(biāo)準(zhǔn)，其函數(shù)表達(dá)式為

在候選區(qū)域進(jìn)行MS確定性搜索時(shí)，使ρ∧（y0）取得最大值的位置即是目標(biāo)的新位置。假設(shè)給定目標(biāo)的起始位置為y0，根據(jù)MS算法的收斂性，進(jìn)行有限次迭代后找到其新位置y1

式中：ωi——采樣點(diǎn)的權(quán)值，g（x）——核函數(shù)，g（x）＝－K′（x），h——核函數(shù)的帶寬。

設(shè)定閾值ε作為判斷迭代是否停止的條件，當(dāng)‖y1－y0‖＜ε時(shí)，表明已經(jīng)找到局部最優(yōu)點(diǎn)，此時(shí)終止MS迭代過程。

2 改進(jìn)的粒子濾波算法設(shè)計(jì)

粒子濾波是一種非參數(shù)化的基于貝葉斯隨機(jī)采樣的濾波方法［8］，適用于非線性系統(tǒng)，其主要思想是利用狀態(tài)空間中一系列隨機(jī)樣本粒子的加權(quán)對(duì)系統(tǒng)狀態(tài)的后驗(yàn)概率密度進(jìn)行近似，得到系統(tǒng)狀態(tài)的估計(jì)值［9］。

假設(shè)系統(tǒng)的狀態(tài)方程和觀測(cè)方程分別為

式中：ft（）、ht（）——狀態(tài)轉(zhuǎn)移函數(shù)、量測(cè)函數(shù)，wt、vt——系統(tǒng)噪聲、觀測(cè)噪聲。

t時(shí)刻觀測(cè)量的集合用Dt表示

為減弱粒子退化現(xiàn)象和降低算法計(jì)算量，將MS算法嵌入到PF的重要性采樣中，利用MS算法對(duì)粒子的收斂作用，使得MS重要性采樣后的粒子更加接近目標(biāo)的真實(shí)狀態(tài)分布，這樣既能夠減弱粒子的退化又一定程度上減少對(duì)粒子的需求量，降低算法計(jì)算量。

算法的具體設(shè)計(jì)如下：

（1）初始化目標(biāo)區(qū)域。在第一幀圖像中用鼠標(biāo)畫取目標(biāo)區(qū)域，根據(jù)顏色分布建立目標(biāo)參考模型，在選取的先驗(yàn)概率分布函數(shù)P（xt－1）中抽取N 個(gè)粒子，i＝0，1，2…，N，令每個(gè)粒子的權(quán)重為N－1。

（2）對(duì)每個(gè)粒子利用UKF（無跡卡爾曼濾波）算法［10］得到和，其建議分布函數(shù)為

（5）估計(jì)目標(biāo)位置。輸出估計(jì)值P（xt｜Dt）

（7）令t＝t＋1，重復(fù)步驟（2）～（6）。

綜合以上步驟，本文算法流程如圖1所示。

3 仿真實(shí)驗(yàn)與分析

實(shí)驗(yàn)用的PC機(jī)配置為奔騰雙核，主頻2.5GHz，內(nèi)存2.0GB；軟件工具為Windows XP 操作系統(tǒng)，MATLAB R2011運(yùn)行環(huán)境。

圖1 本文算法流程

首先對(duì)傳統(tǒng)粒子濾波算法和本文算法進(jìn)行粒子模擬跟蹤仿真，如圖2所示，其中圖2（a）是模擬的目標(biāo)位置真值，圖2（b）是傳統(tǒng)粒子濾波算法的跟蹤結(jié)果，圖2（c）是本文算法的跟蹤結(jié)果。將圖2（b）和圖2（c）進(jìn)行比較可以看出，傳統(tǒng)算法由于少數(shù)粒子占據(jù)了大部分權(quán)重，重采樣后粒子的多樣性減少，粒子退化嚴(yán)重，導(dǎo)致不能準(zhǔn)確估計(jì)目標(biāo)位置，跟蹤效果較差；本文算法由于在重采樣之前進(jìn)行了MS重要性采樣，對(duì)目標(biāo)位置進(jìn)行確定性搜索，保證了粒子狀態(tài)估計(jì)的準(zhǔn)確性，跟蹤效果較好且與圖2（a）的真值相近。

選取路面行駛汽車的視頻序列（720 576，25 幀／s）和直升機(jī)模型空中飛行的視頻序列（600 460，25 幀／s），都采用傳統(tǒng)粒子濾波算法和本文提出的濾波算法分別進(jìn)行跟蹤測(cè)試。

圖3是背景保持不變的汽車行駛序列跟蹤結(jié)果，由上至下分別是第10、48、85幀圖像。圖3（a）是傳統(tǒng)粒子濾波算法的跟蹤結(jié)果，傳統(tǒng)算法在跟蹤過程中對(duì)目標(biāo)位置的估計(jì)稍有偏差，不過序列中目標(biāo)顏色與背景對(duì)比度較大且背景保持不變，一定程度上降低了粒子退化的速度，使候選模型和目標(biāo)參考模型仍然比較接近，有一定的跟蹤效果。圖3（b）是本文算法的跟蹤結(jié)果，算法中加入了MS重要性采樣，對(duì)粒子的確定性搜索使粒子樣本更加接近目標(biāo)的真實(shí)狀態(tài)，由第85 幀圖像可以看出，其跟蹤效果優(yōu)于傳統(tǒng)算法。

圖2 傳統(tǒng)粒子濾波和本文算法跟蹤仿真對(duì)比結(jié)果

圖4是背景由簡(jiǎn)單變復(fù)雜的直升機(jī)飛行序列的跟蹤結(jié)果，由上至下分別是第30、79、105幀圖像。圖4（a）是傳統(tǒng)粒子濾波算法的跟蹤結(jié)果，傳統(tǒng)算法由于在粒子遞推過程中大部分權(quán)重集中在少數(shù)粒子，重采樣后粒子多樣性減少，出現(xiàn)粒子退化現(xiàn)象，尤其當(dāng)背景變復(fù)雜且與目標(biāo)顏色相近時(shí)，粒子樣本的估計(jì)狀態(tài)與目標(biāo)真實(shí)狀態(tài)差別較大，導(dǎo)致跟蹤效果較差，特別是在第107幀圖像中，目標(biāo)已經(jīng)基本丟失。圖4（b）是本文算法的跟蹤結(jié)果，由于對(duì)建議分布中抽取的粒子進(jìn)行了MS重要性采樣，使大部分粒子收斂到局部最大值，粒子樣本的估計(jì)狀態(tài)接近于目標(biāo)的真實(shí)狀態(tài)，雖然背景變得復(fù)雜且目標(biāo)顏色與背景近似，但是對(duì)跟蹤效果的影響較小，到第107幀圖像時(shí)，仍然能夠準(zhǔn)確跟蹤目標(biāo)。

圖3 汽車序列跟蹤過程

圖4 直升機(jī)序列跟蹤過程

4 結(jié)束語

本文針對(duì)粒子濾波目標(biāo)跟蹤中粒子退化的問題，將MS算法融入到粒子濾波算法中，提出了基于MS重要性采樣的粒子濾波目標(biāo)跟蹤算法。該算法利用目標(biāo)顏色分布建立目標(biāo)參考模型，在MS的迭代尋優(yōu)過程中，對(duì)粒子樣本進(jìn)行確定性搜索，使其收斂到目標(biāo)候選模型的局部最優(yōu)點(diǎn)，以更加準(zhǔn)確地估計(jì)目標(biāo)狀態(tài)，實(shí)現(xiàn)對(duì)目標(biāo)模型的重要性采樣，有效解決了粒子退化問題。同時(shí)粒子估計(jì)準(zhǔn)確性的提高，也減少了算法對(duì)粒子的需求量，增強(qiáng)了目標(biāo)跟蹤的實(shí)時(shí)性。實(shí)驗(yàn)結(jié)果表明，該算法的跟蹤性能優(yōu)于傳統(tǒng)的粒子濾波算法，特別在背景較復(fù)雜且與目標(biāo)顏色相近的情況下，跟蹤優(yōu)勢(shì)更加明顯。

［1］LIU Yiming，ZHOU Shangbo.Video tracking algorithm of particle filtering based on multi－feature fusion ［J］.Computer Engineering，2010，36 （22）：228－230 （in Chinese）. ［劉一鳴，周尚波.基于多特征融合的粒子濾波視頻跟蹤算法 ［J］.計(jì)算機(jī)工程，2010，36 （22）：228－230.］

［2］HAN Hua.The research on intelligent multiple video targets tracking based on improved particle filter ［D］.Shanghai：PhD Thesis of DongHua University，2011：25－26 （in Chinese）.［韓華.基于改進(jìn)粒子濾波算法的多目標(biāo)智能視頻跟蹤研究 ［D］.上海：東華大學(xué)博士學(xué)位論文，2011：25－26.］

［3］GAO Jianpo，WEI Zhihui，MENG Yingjun，et al.Improved CONDENSATION face tracking algorithm based on mean－shift drift［J］.Opto－Electronic Engineering，2009，36 （2）：137－142 （in Chinese）.［高建坡，韋志輝，孟迎軍，等.基于均值移動(dòng)確定性漂移的改進(jìn)CONDENSATION 人臉跟蹤 ［J］.光電工程，2009，36 （2）：137－142.］

［4］Ning Jifeng，Zhang Lei.Scale and orientation adaptive mean shift tracking［J］.IET Computer Vision，2012，6 （1）：52－61.

［5］GONG Yisong，GUI Qingming，LI Baoli，et al.Design of particle filtering algorithm based on mean shift and its application in navigation data processing ［J］.Journal of Surveying and Mapping，2011，40 （Suppl.）：120－125 （in Chinese）.［宮軼松，歸慶明，李寶利，等.基于均值漂移的粒子濾波算法設(shè)計(jì)及其在導(dǎo)航數(shù)據(jù)處理中的應(yīng)用 ［J］.測(cè)繪學(xué)報(bào)，2011，40 （增刊）：120－125.］

［6］ZHENG Yufeng，MA Xiurong，ZHAO Xiaolin，et al.Mean shift target tracking algorithm based on color and edge features［J］.Journal of Optoelectronics· Laser，2011，22 （8）：1231－1235 （in Chinese）.［鄭玉鳳，馬秀榮，趙曉琳，等.基于顏色和邊緣特征的均值遷移目標(biāo)跟蹤算法 ［J］.光電子·激光，2011，22 （8）：1231－1235.］

［7］Leichter I，Lindenbaum M，Rivlin E.Mean Shift tracking with multiple reference color histograms［J］.Computer Vision and Image Understanding，2010，114 （3）：400－408.

［8］Vasileios Maroulas，Panos Stinis.Improved particle filters for multi－target tracking ［J］.Journal of Computational Physics，2012，23 （1）：602－611.

［9］GUO Xiaosong，LI Yipeng，GUO Junbin.Research on particle filtering algorithm and its applications［J］.Computer Engineering and Design，2009，30 （9）：2264－2266 （in Chinese）.［郭曉松，李奕芃，郭君斌.粒子濾波算法及其應(yīng)用研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （9）：2264－2266.］

［10］Wu Chunlin，Han Chongzhao.Quadrature Kalman particle filter［J］.System Engineering and Electronics，2010，21（2）：175－179.