Mean Shift跟蹤的背景優(yōu)化及動態(tài)分析

王建華， 王春平， 梁 偉， 王惠萍

(1.白求恩軍醫(yī)學(xué)院計算機教研室，石家莊 050081; 2.軍械工程學(xué)院光學(xué)與電子工程系，石家莊 050003)

0 引言

隨著計算機視覺的快速發(fā)展，目標(biāo)跟蹤已成為視覺領(lǐng)域的一個重要研究方向，廣泛應(yīng)用于視頻監(jiān)控、人工智能、運動分析等領(lǐng)域［1］。其中的一類算法是基于目標(biāo)表達和定位的方法，Mean Shift則屬于這類算法中比較成功的算法之一，它是一種基于最優(yōu)梯度下降的方法，通過迭代來尋找目標(biāo)，從而實現(xiàn)對目標(biāo)的跟蹤。自從1995年被Yizong Cheng［2］引入到計算機視頻，就由于具有計算量小、跟蹤效果好、實時性強等特點，被廣泛應(yīng)用于目標(biāo)跟蹤的各個領(lǐng)域。但傳統(tǒng)的Mean Shift算法存在以下缺點:1)背景像素的參與容易帶來定位偏差;2)缺乏相應(yīng)的動態(tài)分析方法;3)對于目標(biāo)的剛性形變和嚴(yán)重遮擋比較敏感。為了解決這些問題，許多專家和學(xué)者給出過不盡相同的改進方法，例如:文獻［3］將 SIFT(Scale Invariant Feature Transform)與Mean Shift結(jié)合;文獻［4］用聯(lián)合顏色紋理直方圖表示目標(biāo)特征計算目標(biāo)模型;文獻［5］通過自適應(yīng)調(diào)整核函數(shù)寬度實現(xiàn)對大小變化的目標(biāo)跟蹤;文獻［6］利用分塊的方法實現(xiàn)目標(biāo)在遮擋情況下的跟蹤;文獻［7］中將粒子濾波與Mean Shift相結(jié)合的算法。綜合考慮以上算法的優(yōu)缺點，針對Mean Shift算法在目標(biāo)快速運動且目標(biāo)大小變化較大、存在嚴(yán)重遮擋情況下容易丟失目標(biāo)的問題，本文提出兩方面的改進措施:1)將跟蹤窗口內(nèi)的區(qū)域區(qū)分為目標(biāo)和背景兩部分，通過減少背景像素在概率密度函數(shù)(PDF)中的權(quán)重來對背景進行優(yōu)化，以降低背景對目標(biāo)跟蹤的影響，提高定位精度;2)采用分塊的方法對跟蹤狀態(tài)進行動態(tài)分析，根據(jù)目標(biāo)的大小變化，更新跟蹤窗口大小及模板，實時判斷遮擋狀態(tài)，根據(jù)遮擋位置和目標(biāo)實際大小的不同，動態(tài)計算目標(biāo)的位置，當(dāng)存在嚴(yán)重遮擋時，采用最小二乘法進行二維線性預(yù)測，解決目標(biāo)在短時間內(nèi)被完全遮擋的跟蹤問題。對上述改進方法進行實驗，實驗結(jié)果驗證了該方法對于復(fù)雜條件下的目標(biāo)跟蹤的穩(wěn)健性。

1 傳統(tǒng)Mean Shift算法原理

Mean Shift算法［8］是一種基于密度估計的非參數(shù)匹配算法，利用目標(biāo)區(qū)域的顏色概率直方圖分布建立目標(biāo)模型，根據(jù)均值平移向量，在臨近區(qū)域內(nèi)自動搜索匹配度最高的區(qū)域，作為新的目標(biāo)位置，該算法不需要進行窮盡搜索，實時性強，在基于圖像處理的目標(biāo)跟蹤中得到廣泛應(yīng)用。其實現(xiàn)過程如下所述。

1)在初始幀中，利用手動或自動檢測算法檢測到目標(biāo)所在區(qū)域，利用顏色概率直方圖分布建立初始目標(biāo)模型。設(shè)目標(biāo)中心為y0，像素位置為，其中n為目標(biāo)所包含的像素點的個數(shù)，該目標(biāo)區(qū)域的像素灰度級范圍為［0，H－1］。則可得到目標(biāo)區(qū)域的統(tǒng)計直方圖分布模型為

2)在當(dāng)前幀的y0點位置，像素位置為{xi}，i=1，…，nh，統(tǒng)計候選目標(biāo)的直方圖分布

3)用Bhattacharyya系數(shù)計算候選目標(biāo)與初始目標(biāo)模型的相似度。

4)計算跟蹤窗內(nèi)像素的權(quán)重。

5)根據(jù)均值平移向量，搜索新的目標(biāo)位置。

同時計算Bhattacharyya系數(shù)為

6)比較Bhattacharyya系數(shù)，更新候選目標(biāo)位置，如果，則

7)判斷是否達到最優(yōu)，如果‖y1－y0‖＜ξ，停止迭代;否則置y0=y1跳轉(zhuǎn)到第2)步。

2 背景優(yōu)化

從Mean Shift算法中，可以看出跟蹤窗內(nèi)所有像素(目標(biāo)和背景)均參與直方圖分布的統(tǒng)計對目標(biāo)進行建模，當(dāng)跟蹤窗內(nèi)包括的背景像素比較少時，Mean Shift算法能穩(wěn)定跟蹤目標(biāo)，但當(dāng)跟蹤窗內(nèi)的背景像素比較多或背景變化比較明顯時，就會產(chǎn)生定位偏差，甚至丟失目標(biāo)。因此，減少或消除背景像素的影響對于提高目標(biāo)跟蹤的定位精度是非常必要的。

本文將跟蹤窗內(nèi)的目標(biāo)和背景分為兩部分，通過減少背景像素在概率密度函數(shù)中的權(quán)重來對背景進行優(yōu)化，以降低背景對目標(biāo)跟蹤的影響，提高定位精度。設(shè)跟蹤窗內(nèi)像素xi灰度為h的像素的權(quán)重為λh，則

類似地，將目標(biāo)模型進行如上改進。

采用最大類間法對跟蹤窗口內(nèi)的像素進行閾值分割，以將目標(biāo)和背景區(qū)分開來，對于目標(biāo)或背景內(nèi)出現(xiàn)的空洞，采用數(shù)學(xué)形態(tài)學(xué)的方法予以消除。這里需要指出的是，為了保證建立目標(biāo)模型數(shù)據(jù)的原始性，避免引入二次誤差，該二值圖像僅用來判斷參與建立模型的像素是否屬于目標(biāo)，建立目標(biāo)模型時用到的圖像數(shù)據(jù)仍然是跟蹤窗口內(nèi)的原始圖像數(shù)據(jù)。

3 跟蹤狀態(tài)的動態(tài)分析

由于Mean Shift算法以候選目標(biāo)和目標(biāo)模型的模板相似度最大化為判斷準(zhǔn)則，所以模板對于跟蹤的穩(wěn)定性起著至關(guān)重要的作用。但在實際圖像跟蹤中，一成不變的目標(biāo)是非常少見的，大多數(shù)情況下，都會由于目標(biāo)運動狀態(tài)、背景變化或其他物體遮擋等因素的影響，目標(biāo)在圖像中的運動形態(tài)會發(fā)生很大變化，因此為了提高該算法的跟蹤魯棒性和穩(wěn)定性，需要對跟蹤狀態(tài)進行實時分析，根據(jù)跟蹤狀態(tài)的不同，及時調(diào)整跟蹤策略，以滿足復(fù)雜情況下運動目標(biāo)跟蹤的需要。

本文采用的動態(tài)分析方法基于分塊的思想［9］，動態(tài)計算每個子塊相對于目標(biāo)中心位置的位置偏差，根據(jù)目標(biāo)與模板的相似性系數(shù)，判斷是否有遮擋發(fā)生，如果存在遮擋，則根據(jù)遮擋的位置，自動根據(jù)其他子塊相對于目標(biāo)中心的位置偏差對目標(biāo)位置進行定位。子塊數(shù)量選擇的基本原則是:數(shù)量過多影響算法的實時性，數(shù)量過少抗遮擋能力差。為了提高抗干擾能力，又要保證算法的實時性，這里以中心對稱的方式將目標(biāo)模板分為4塊，圖1為分割示意圖。

圖1 分塊示意圖Fig.1 Fragments of object region

其中，Δyave-b，Δyave-a分別為跟蹤窗口調(diào)整前后位置偏差平均值。當(dāng)有遮擋情況發(fā)生時，不更新目標(biāo)模板及跟蹤窗口，待目標(biāo)脫離遮擋后，再進行更新操作。

4 算法流程

為了提高Mean Shift算法的跟蹤精度和抗遮擋能力，將背景優(yōu)化方法和跟蹤狀態(tài)的動態(tài)分析方法統(tǒng)一到一個跟蹤框架結(jié)構(gòu)中，具體算法流程如下所述。

1)初始化跟蹤目標(biāo)(本文采用手動的方法選定目標(biāo))，將目標(biāo)模板按圖1所示進行分塊。對模板進行閾值分割，區(qū)分目標(biāo)和背景，根據(jù)式(7)針對原始圖像數(shù)據(jù)統(tǒng)計目標(biāo)模型的直方圖分布。

2)讀取新一幀圖像，確定模板的坐標(biāo)位置。

①對跟蹤窗口內(nèi)的像素進行閾值分割，以區(qū)分目標(biāo)和背景;

②利用式(8)統(tǒng)計候選目標(biāo)的直方圖分布;

③利用傳統(tǒng)Mean Shift算法的3)～7)步計算目標(biāo)位置，并記錄最終的目標(biāo)相似度ρ;

④ 若 ρ≥ρth(ρth為預(yù)先設(shè)定的遮擋閾值)，說明目標(biāo)沒有被遮擋，記錄目標(biāo)的位置信息并根據(jù)跟蹤窗口及分塊的基本方法，計算每個子塊相對于目標(biāo)坐標(biāo)的位置偏差，讀取下一幀圖像，返回步驟①;若ρ＜ρth，執(zhí)行步驟⑤;

5 實驗結(jié)果及分析

本實驗采取的圖像序列是在室外獲取的人由遠及近且存在遮擋的視頻。圖2給出了跟蹤效果圖。

圖2 跟蹤實例Fig.2 Example of tracking

圖中，黑色矩形是傳統(tǒng)Mean Shift算法的跟蹤結(jié)果;白色矩形區(qū)域是經(jīng)過背景優(yōu)化和動態(tài)分析后的目標(biāo)跟蹤結(jié)果。其中，第1幀中黑色矩形區(qū)域為手動的方法選取的目標(biāo)位置;在第88幀中，我們發(fā)現(xiàn)用傳統(tǒng)的Mean Shift算法雖然能跟上目標(biāo)，但由于它沒有根據(jù)目標(biāo)的大小變化及時更新核窗的大小，使得跟蹤位置出現(xiàn)偏差，而改進算法加入了背景優(yōu)化及動態(tài)分析策略，算法自動根據(jù)目標(biāo)大小變化調(diào)整跟蹤窗口，目標(biāo)跟蹤定位較為準(zhǔn)確;在第167幀中，目標(biāo)被部分遮擋，傳統(tǒng)的Mean Shift算法出現(xiàn)了很大的位置偏差，而改進算法判斷遮擋情況，自動根據(jù)第1、2子塊信息進行整個目標(biāo)位置的判定，結(jié)果較好;在第269幀到第345幀中，目標(biāo)經(jīng)歷了一個完全遮擋過程，傳統(tǒng)的Mean Shift算法陷入了局部最小值，而改進算法此時所有的子塊的均小于設(shè)定的閾值，采用二維線性預(yù)測方法進行預(yù)測，當(dāng)目標(biāo)脫離遮擋時，更新目標(biāo)模板，重新跟蹤。

將算法跟蹤結(jié)果與手動提取的結(jié)果采用計算定位偏差的方法進行比較，結(jié)果如表1所示。定位偏差Ei為

其中:(xo，yo)為手動的方法提取的目標(biāo)中心位置;(xi，yi)為算法跟蹤的中心位置結(jié)果，單位為像素;i為幀數(shù)序列。從表中可以看出，改進的算法具有更高的跟蹤精度。

表1 定位偏差比較Table 1 Comparasion of location errors

6 結(jié)束語

傳統(tǒng)的Mean Shift算法由于算法簡潔、實時性強，被廣泛應(yīng)用于視頻目標(biāo)跟蹤領(lǐng)域，但該算法中，參與目標(biāo)定位時，在包括目標(biāo)的同時不可避免地會引入背景像素，因此背景像素?zé)o疑會給定位結(jié)果帶來偏差;此外，由于傳統(tǒng)的Mean Shift算法沒有相應(yīng)的動態(tài)分析方法，使得目標(biāo)在發(fā)生遮擋時，算法容易陷入局部最小值，造成跟蹤失敗。本文針對傳統(tǒng)Mean Shift算法的上述缺陷，提出了兩方面的改進措施:1)對跟蹤窗口內(nèi)的背景像素進行優(yōu)化，采取閾值分割、數(shù)學(xué)形態(tài)學(xué)等方法區(qū)分目標(biāo)和背景，對目標(biāo)和背景采取不同的權(quán)值進行建模;2)以基于分塊思想的動態(tài)分析方法，實時判斷是否存在遮擋，當(dāng)有部分遮擋時，利用其余未遮擋的子塊根據(jù)各自的位置偏差進行目標(biāo)定位，當(dāng)目標(biāo)被完全遮擋時，利于二維線性預(yù)測的方法對目標(biāo)進行預(yù)測，防止目標(biāo)的丟失。整個跟蹤過程中根據(jù)子塊的位置偏差不斷更新跟蹤窗口的大小，間隔固定幀數(shù)或目標(biāo)脫離遮擋時更新模板。實驗表明，將背景優(yōu)化和動態(tài)分析方法附加在傳統(tǒng)的Mean Shift算法中，有效改善了Mean Shift跟蹤算法的不足，對于復(fù)雜條件下的運動目標(biāo)跟蹤具有很好的魯棒性。

［1］ 劉鋼，劉明，匡海鵬，等.多目標(biāo)跟蹤方法綜述［J］.電光與控制，2004，11(3):26-29.

［2］ CHENG Yizong.Mean Shift，mode seeking，and clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17(8):790-799.

［3］ ZHOU Huiyu，YUAN Yuan，SHI Chunmei.Object tracking using SIFT features and mean shift［J］.Computer Vision and Image Understanding，2009，113(3):345-352.

［4］ NING Jifeng，ZHANG Lei，ZHANG D.Robust object tracking using joint color-texture histogram［J］.International Journal of Pattern Recognition ＆ Artificial Intelligence，2009，23(7):1245-1263.

［5］ 付勇，何明一，劉超.Mean Shift目標(biāo)跟蹤核函數(shù)寬度的自適應(yīng)調(diào)整［J］.計算機工程與應(yīng)用，2010，46(17):243-245.

［6］ 顏佳，吳敏淵，陳淑珍，等.應(yīng)用Mean Shift和分塊的抗遮擋跟蹤［J］.光學(xué)精密工程，2010，18(6):1413-1418.

［7］ 張旭，李志國.基于粒子濾波和均值平移的目標(biāo)跟蹤［J］.激光與紅外，2008，38(8):834-836.

［8］ COMANICIU D，RAMESH V，MEER P.Real-time tracking of non-rigid objects using Mean Shift［C］//IEEE Conference on Computer Vision and Pattern Recognition，2000:142-149.

［9］ ADAM A，RIVLIN E，SHIMSHON L.Robust fragments-based tracking using the integral histogram［C］//Computer Vision and Pattern Recognition，IEEE Computer Society Conference，2006:798-805.

［10］ 王春平，王建華，朱元昌.遮擋情況下運動目標(biāo)的航跡預(yù)測方法研究［J］.火力與指揮控制，2005，30(s):107-108.