一種改進的Mean-Shift 實時車輛跟蹤算法

張 彤，馬延柯，首照宇

(桂林電子科技大學 a. 機電工程學院;b. 認知無線電與信息處理省部共建教育部重點實驗室，廣西 桂林541004)

在智能車流量統計系統［1］中，對于車輛的精確快速跟蹤是交通參數提取、交通事件處理的一項關鍵技術。車輛的不規律運動影響了跟蹤的效率，近年來，眾多學者對此展開了深入的研究，并提出了一些較好的方法［2－4］，其中Mean－Shift 跟蹤方法自提出以來就備受關注。Mean－Shift 跟蹤算法的目標模型選取核函數空間加權的顏色直方圖，采用Bhattacharrya系數作為相似性度量，通過Mean－Shift 迭代搜尋目標位置。其具有計算負荷小、調節參數少等優點，但是存在無法估計目標的尺度方向，對變速運動目標的跟蹤效果差的問題［5］。于此，在此算法理論的基礎上提出了一些改進。文獻［6－8］通過特征點匹配方法，結合整體與局部模型各自優點，計算連續幀間相關特征點的仿射變換系數得到尺度與方向信息，但是特征點提取、描述與匹配可能影響實時性;文獻［9］通過權重圖法，利用像素點權重的協方差矩陣計算尺度和方向信息，計算量小，效果較好，但易受到光照等因素影響;文獻［10－11］通過尺度法，使用圖像金字塔或全局概率密度搜索提高目標定位能力，這里尺度分別指圖像尺度和帶寬尺度，但缺點是易受相似目標干擾;文獻［12］通過預測法，結合Kalman 濾波或者粒子濾波算法，增加目標搜索能力，但對非線性、非高斯分布的狀態變量的預測有一定局限，對目標運動模型有一定要求?，F有的預測方法有很多，神經網絡法、線性預測法、馬爾科夫鏈預測法等，它們分別具有各自的特點，適用于不同的場合。理論上樣本或者先驗知識的積累決定了這幾種方法的預測精度。然而在工程應用中，這種積累是難以實現的。在傳統均值飄移算法基礎上，通過尋找搜索區域與當前目標所在真實位置區域盡可能的重疊，從而盡快地搜索出當前目標位置。據此，本文提出一種基于時間序列預測法的運動歷史Mean－Shift 跟蹤方法，首先通過運動歷史信息加權圖像來記錄前幾幀的運動目標位置，根據其運動屬性來預測當前幀目標所在位置，然后選定該預測中心位置來進行搜索，從而減少迭代次數，提高智能車流量統計系統的實時性和魯棒性。實驗結果表明，該方法取得了良好的效果。

1 Mean－Shift 跟蹤算法

1.1 Mean-Shift 算法

Mean－Shift 算法的原理是在核密度估計的基礎上，在一組數據的密度分布中采用步長迭代尋找局部極值點，步長具有自適應性。屬于一種無參非監督特征空間分析方法。計算機視覺處理中，通常都是在多維空間中對數來分析處理，在假設d 維歐式空間情況下，其中有n 個樣本xi∈Rd，i=1，2，…，n，x 表示該空間中的一個點，可以得到Rd空間中的點x 的密度概率估計值為

根據核函數公式，若采用H=h2I，對應的Mean－Shift 矢量為

根據經典算法的計算公式，密度梯度的估計相當于核密度估計的梯度，有g(x)=－k'(x)。m(x)通常與概率密度速率最大的方向重疊，經過若干次迭代可以收斂至概率密度的局部極值點。

1.2 Mean-Shift 跟蹤目標模型描述

Mean－Shift 跟蹤算法的基本原理是首先建立目標模型，再采用匹配度函數來衡量目標相似度，通過密度估計方法來解決搜索匹配度的局部極值問題，通過Mean－Shift 迭代來定位其局部最大值。

1.2.1 初始目標模型的建立

在視頻序列中，目標特征是通過灰度或顏色分量來進行描述的。通過一定方法篩選出要跟蹤的目標區域，該區域為一矩形，d0為其中心，h 設為邊長，把選定目標區域顏色空間均勻分成m 個特征區間，通過此選定搜索域全部特征值的概率值來表述目標模型，通過直方圖估計法得到的特征值v 的概率核密度qv為

式中:xj表示該選定搜索域中第j 個像素值坐標;k(·2)表示核函數;C 為一個歸一化常量系數;函數b 和δ 的構造是為了分析判斷第j 個像素顏色灰度值是否與對應特征值v 匹配;

1.2.2 當前目標模型的建立

對于當前幀圖像中可能會出現搜索目標區域描述為待選目標模型，在當前幀目標搜索區域中，第v 個特征概率的表達式為

式中:y0表示當前幀搜索區域的中心坐標;Ch是一個歸一化常系數，且，使得=1，m 表示特征個數。

1.2.3 特征相似性函數

用Bhattacharyya 系數來衡量初始目標模型和當前目標模型的相似程度，如果值越大，表示相似程度越高，也即當前目標與初始目標最相似。

Bhattacharyya 系數定義為

兩個目標模型的相似程度跟ρ(y)函數值成正比例關系，相似性函數最大的當前幀區域就是當前目標所在區域。

1.2.4 跟蹤步驟

設置視頻序列，已知初始幀的目標模型{q^v}v=1，2，…，m，并給出t－1 時刻的目標位置d0，對t 幀圖像進行目標搜索過程如圖1 所示。

圖1 Mean－Shift 跟蹤步驟

2 運動歷史預測和優化的Mean－Shift跟蹤算法

傳統的均值飄移跟蹤算法是以前一幀運動目標的所在位置為依據進行搜索，搜索區域與當前目標所在區域部分重合，搜索區域的大小對搜索時間有一定的影響，如果從前一幀的運動目標位置開始搜索，將會通過多次迭代才能收斂于當前幀目標所在位置，從而造成算法計算量大，實時性差。在實際應用中，可以通過一定的方法減少迭代次數，從而減少算法計算量，提高系統實時性，實現對多個目標的實時跟蹤。

2.1 運動歷史信息的提取

運動歷史信息的提取技術在虛擬現實中備受關注，同時在智能監控領域也被廣泛應用［13］。在運動目標的跟蹤中，是對下一幀運動目標位置進行有效預測的關鍵，其基本思路是，提取每幀圖像對應的不同時刻并將連續圖像進行加權疊加，時間序列圖像通過浮點數來表達，這是它的核心理論。通過將當前視頻序列時間戳轉換為浮點矩陣后進行目標運動信息加權圖像更新。隨著時間的推進，當前幀信息加權圖像總是具有最大灰度值(最亮)，而過去幀信息加權在當前運動信息圖像中的影響將會越來越弱(圖像變暗);當過去時間序列與當前時間序列的間隔超過設置閾值時，其影響將被清為零。

系統通過一定的目標檢測算法比如背景差、幀差等提取出運動車輛目標，但是系統只能獲得運動發生的位置，而其他運動歷史信息并未知，然而運動歷史信息加權圖像(motion history－weighted images)能夠描述更多的運動屬性，例如運動的方向［14］等。

運動歷史信息圖像更新公式如下

式中:τ 是當前系統時間，δ 表示運動歷史圖所能表示的時間片段。圖2a 是一段視頻運動序列中的第31 幀圖像;圖2b 是該序列幀圖像中的運動車輛所獲取的經典運動歷史信息加權圖像，可見此信息圖像是一個亮度從黑到白的灰度圖，從暗到明的方向表示運動的方向。

圖2 運動歷史信息圖

提取出一定時間序列的運動歷史加權圖像后，將3×3 的Sobel 算子應用到圖像上［15］，并對其水平、垂直方向求偏導，從而得到特征空間像素點(x，y)上的梯度sx(x，y)、sy(x，y)，據此進一步計算梯度方向Orient(x，y)和幅值M(x，y)分別為

對其梯度圖進行運動分割，先計算每個分割區域的運動方向，再計算選擇區域內的整個運動方向，并且返回［0，360］之間的角度值。對每一幀圖像進行處理時，對其梯度方向進行計算，無論是全局的還是局部的都需要對該區域運動歷史信息圖像進行標準化處理，并且對其權值進行規則化，以使運動歷史圖像中最近的時間序列運動信息具有最大影響值。計算公式為

2.2 優化的Mean-Shift 跟蹤算法

2.2.1 預測原理

運動歷史信息加權圖像記錄了運動車輛的位置、運動方向、面積、速度等信息。據此運動歷史信息對下一幀運動目標狀態進行最優估計，預測具有定位準確、可靠性高等特點。假設系統狀態Xk為一個4×Nk維向量，目標預測方程［16］為

式中:Xk表示依據k－1 時刻的狀態對k 時刻狀態的估計值;Xk－1為k－1 時刻最優狀態估計值;Uk為k 時刻的控制量;Φk/k－1為狀態轉移矩陣。

根據k 時刻的提取值和估計值，得出k 時刻的最優預測值為

式中:Hk為觀測矩陣。

然后計算預測位置最接近的目標

計算目標j 的匹配度L(i，j')，根據匹配度函數，對檢測目標進行匹配。預先設定一閾值T，通常取為0.006 ～0.060。

2.2.2 優化后的方法具體步驟:

對于一個視頻序列，已知初始幀的目標模型{q^v}v=1，2，…，m，并給出t－1 時刻的目標位置d0，對t 幀圖像進行目標搜索流程圖如圖3 所示。

圖3 目標搜索流程圖

3 實驗結果分析

為了驗證本文算法的有效性，對兩組方向速度改變(變道)車輛進行了實驗，并與Mean－Shift 方法進行了比較。

車輛方向速度改變(變道)情況的跟蹤結果如圖4 所示，圖4a 為第529 幀變道前車輛位置圖，方框標記的白色車輛處在左二車道，準備變道;圖4b 為對應的運動歷史信息加權圖像，依據此圖像記錄的車輛運動屬性進行估計下一幀運動位置;圖4c 為采用本文方法實驗的目標車輛變道后跟蹤結果，變道后的白色車輛處在右二車道;圖4d 為傳統Mean－Shift 方法對目標車輛的跟蹤結果。圖5a 為第2 027 幀目標車輛位置圖，方框標記的灰色車輛處在右一車道，準備變道;圖5b 為對應的運動歷史信息加權圖像;圖5c 為采用本文方法對目標車輛的跟蹤結果;圖5d 為傳統方法對目標車輛的實驗結果，右二車道方框標記的灰色車輛為圖5a 中變道的車輛。從圖中結果可以看出，本文方法能在車輛運動屬性發生變化情況下準確跟蹤，效果明顯比傳統方法好。

圖4 第529 幀的變道車輛跟蹤結果

圖5 第2 027 幀的變道車輛跟蹤結果

圖6 中針對右二車道進行分析，圖6a 表示運動目標所在原始位置，圖6b 表示當前幀要檢測運動目標位置，根據運動歷史屬性信息，在搜索之前預測出當前幀運動目標可能在矩形框附近，然后在矩形框附近搜索，預測下一幀車輛目標位置，如果利用傳統的均值飄移算法，開始搜索位置定位在原始圖像中矩形框，一般情況下要通過5 次左右的迭代才能收斂于當前幀中的矩形框位置，而且系統很難實現短時間內同時對多個目標進行準確跟蹤，與傳統方法相比，本文算法迭代次數減少，收斂速度加快，提高了系統的實時性。

圖6 實驗目標位置圖

圖7 比對了傳統算法與改進算法在監控區域內的迭代次數，對一輛車進行跟蹤時，傳統算法需要2 ～3 次迭代才能完成一次搜索，而本文改進的跟蹤算法為平均1 次，提高了監控系統的實時性。

圖7 傳統算法與本文算法迭代次數對比圖

4 小結

本文針對傳統Mean－Shift 算法存在無法有效地估計車輛目標方向、變速運動車輛目標的缺陷進行改進，在Mean－Shift迭代搜索的基礎上增加了預測功能，提出了改進算法。在本實驗中，通過記錄的運動歷史屬性信息來構建數學模型，并對下一幀位置進行預測，包括方向、速度等，從而避免因車輛的變道、提速等不規律運動行為而引起的錯跟、丟跟。實驗表明，該預測算法能為Mean－Shift 提供幀間相似密度低的區域目標的鎖定能力，以及對視頻幀的高效處理能力，減輕處理器的負擔。下一步還將對多個樣本進行訓練，并通過算法學習來進一步提高車輛跟蹤算法的自適應性和高效性。實現對復雜視頻、復雜場景的有效分析。

［1］WANG Guolin，XIAO Deyun，GU J. Review on vehicle detection based on video for traffic surveillance［C］//Proc. IEEE International Conference on Automation and Logistics. Piscataway，USA:IEEE Press，2008:2961－2966.

［2］SUBUDHI B N，NANDA P K，GHOSH A. A change information based fast algorithm for video object detection and tracking［J］.IEEE Trans. Circuits and Systems for Video Technology，2011，21(7):993－1004.

［3］JAZAYERI A，CAI Hongyuan，JIANG Yuzheng. Vehicle detection and tracking in car video based on motion model［J］.IEEE Trans.Intelligent Transportation Systems，2011，12(2):583－595.

［4］鄭可飚，黃文清，張佐理，等. 運動目標跟蹤系統的遮擋問題處理［J］.計算機工程與設計，2009，30(11):2816－2818.

［5］顧幸方，茅耀斌，李秋潔.基于Mean－Shift 的視覺目標跟蹤算法綜述［J］.計算機科學，2012，39(12):16－17.

［6］康一梅，謝晚冬，胡江，等. 目標尺度自適應的Mean－Shift 跟蹤算法［J］.兵工學報，2011，32(2):210－216.

［7］ZHAO Chuan，KNIGHT A，REID I. Target tracking using meanshift and affine structure［C］//Proc. 2008 International Conference on Pattern Recognition.［S.l.］:IEEE Press，2008:1－5.

［8］CHEN Aihua，ZHU Ming，WANG Yanhua，et al. Mean－Shift tracking combining SIFT［C］//Proc. International Conference on Signal Processing.［S.l.］:IEEE Press，2008:1532－1535.

［9］NING Jifeng，ZHANG Lei，ZHANG D，et al. Scale and orientation adaptive Mean Shift tracking［J］.IET Computer Vision，2012，6(1):52－61.

［10］LI Shuxiao，CHANG Hongxing，ZHU Chengfei. Adaptive pyramid mean shift for global real－time visual tracking［J］.Image and Vision Computing，2010，28(3):424－437.

［11］LI Liangfu，FENG Zuren，CHEN Weidong，et al. A coarse－to－fine kernel matching approach for mean－shift based visual tracking［J］.Opto－Electronics Review，2009，17(1):65－71.

［12］李弟平，鄒北驥，傅自剛. 快速運動目標的Mean－Shift 的高速運動目標跟蹤［J］.小型微型計算機系統，2011，32(8):1665－1668.

［13］DAVIS J W. Hierarchical motion history images for recognizing human motion［EB/OL］.［2014－12－20］.http://wenku.baidu.com/view/fd02140df12d2af90342e605.html.

［14］BRADSKI G R，DAVIS J W. Motion segmentation and pose recognition with motion history gradients［J］.Machine Vision and Applications，2002(13):174－184.

［15］劉軍學，屈楨深，任行行，等.基于改進運動歷史圖像的多運動目標實時跟蹤［J］.計算機應用，2008，28(3):199－200.

［16］胡學剛，劉忠振. 基于高斯模型和卡爾曼預測的檢測和跟蹤［J］.計算機工程與設計，2013，34(1):247－248.