Mean Shift跟蹤的背景優化及動態分析

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

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

0 引言

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

1 傳統Mean Shift算法原理

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

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

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

3)用Bhattacharyya系數計算候選目標與初始目標模型的相似度。

4)計算跟蹤窗內像素的權重。

5)根據均值平移向量，搜索新的目標位置。

同時計算Bhattacharyya系數為

6)比較Bhattacharyya系數，更新候選目標位置，如果，則

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

2 背景優化

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

本文將跟蹤窗內的目標和背景分為兩部分，通過減少背景像素在概率密度函數中的權重來對背景進行優化，以降低背景對目標跟蹤的影響，提高定位精度。設跟蹤窗內像素xi灰度為h的像素的權重為λh，則

類似地，將目標模型進行如上改進。

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

3 跟蹤狀態的動態分析

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

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

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

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

4 算法流程

為了提高Mean Shift算法的跟蹤精度和抗遮擋能力，將背景優化方法和跟蹤狀態的動態分析方法統一到一個跟蹤框架結構中，具體算法流程如下所述。

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

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

①對跟蹤窗口內的像素進行閾值分割，以區分目標和背景;

②利用式(8)統計候選目標的直方圖分布;

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

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

5 實驗結果及分析

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

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

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

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

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

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

6 結束語

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

［1］ 劉鋼，劉明，匡海鵬，等.多目標跟蹤方法綜述［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目標跟蹤核函數寬度的自適應調整［J］.計算機工程與應用，2010，46(17):243-245.

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

［7］ 張旭，李志國.基于粒子濾波和均值平移的目標跟蹤［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］ 王春平，王建華，朱元昌.遮擋情況下運動目標的航跡預測方法研究［J］.火力與指揮控制，2005，30(s):107-108.