一種改進(jìn)的Mean-Shift 實(shí)時車輛跟蹤算法

張 彤，馬延柯，首照宇

(桂林電子科技大學(xué) a. 機(jī)電工程學(xué)院;b. 認(rèn)知無線電與信息處理省部共建教育部重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004)

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

1 Mean－Shift 跟蹤算法

1.1 Mean-Shift 算法

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

根據(jù)核函數(shù)公式，若采用H=h2I，對應(yīng)的Mean－Shift 矢量為

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

1.2 Mean-Shift 跟蹤目標(biāo)模型描述

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

1.2.1 初始目標(biāo)模型的建立

在視頻序列中，目標(biāo)特征是通過灰度或顏色分量來進(jìn)行描述的。通過一定方法篩選出要跟蹤的目標(biāo)區(qū)域，該區(qū)域?yàn)橐痪匦?，d0為其中心，h 設(shè)為邊長，把選定目標(biāo)區(qū)域顏色空間均勻分成m 個特征區(qū)間，通過此選定搜索域全部特征值的概率值來表述目標(biāo)模型，通過直方圖估計(jì)法得到的特征值v 的概率核密度qv為

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

1.2.2 當(dāng)前目標(biāo)模型的建立

對于當(dāng)前幀圖像中可能會出現(xiàn)搜索目標(biāo)區(qū)域描述為待選目標(biāo)模型，在當(dāng)前幀目標(biāo)搜索區(qū)域中，第v 個特征概率的表達(dá)式為

式中:y0表示當(dāng)前幀搜索區(qū)域的中心坐標(biāo);Ch是一個歸一化常系數(shù)，且，使得=1，m 表示特征個數(shù)。

1.2.3 特征相似性函數(shù)

用Bhattacharyya 系數(shù)來衡量初始目標(biāo)模型和當(dāng)前目標(biāo)模型的相似程度，如果值越大，表示相似程度越高，也即當(dāng)前目標(biāo)與初始目標(biāo)最相似。

Bhattacharyya 系數(shù)定義為

兩個目標(biāo)模型的相似程度跟ρ(y)函數(shù)值成正比例關(guān)系，相似性函數(shù)最大的當(dāng)前幀區(qū)域就是當(dāng)前目標(biāo)所在區(qū)域。

1.2.4 跟蹤步驟

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

圖1 Mean－Shift 跟蹤步驟

2 運(yùn)動歷史預(yù)測和優(yōu)化的Mean－Shift跟蹤算法

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

2.1 運(yùn)動歷史信息的提取

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

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

運(yùn)動歷史信息圖像更新公式如下

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

圖2 運(yùn)動歷史信息圖

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

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

2.2 優(yōu)化的Mean-Shift 跟蹤算法

2.2.1 預(yù)測原理

運(yùn)動歷史信息加權(quán)圖像記錄了運(yùn)動車輛的位置、運(yùn)動方向、面積、速度等信息。據(jù)此運(yùn)動歷史信息對下一幀運(yùn)動目標(biāo)狀態(tài)進(jìn)行最優(yōu)估計(jì)，預(yù)測具有定位準(zhǔn)確、可靠性高等特點(diǎn)。假設(shè)系統(tǒng)狀態(tài)Xk為一個4×Nk維向量，目標(biāo)預(yù)測方程［16］為

式中:Xk表示依據(jù)k－1 時刻的狀態(tài)對k 時刻狀態(tài)的估計(jì)值;Xk－1為k－1 時刻最優(yōu)狀態(tài)估計(jì)值;Uk為k 時刻的控制量;Φk/k－1為狀態(tài)轉(zhuǎn)移矩陣。

根據(jù)k 時刻的提取值和估計(jì)值，得出k 時刻的最優(yōu)預(yù)測值為

式中:Hk為觀測矩陣。

然后計(jì)算預(yù)測位置最接近的目標(biāo)

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

2.2.2 優(yōu)化后的方法具體步驟:

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

圖3 目標(biāo)搜索流程圖

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

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

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

圖4 第529 幀的變道車輛跟蹤結(jié)果

圖5 第2 027 幀的變道車輛跟蹤結(jié)果

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

圖6 實(shí)驗(yàn)?zāi)繕?biāo)位置圖

圖7 比對了傳統(tǒng)算法與改進(jìn)算法在監(jiān)控區(qū)域內(nèi)的迭代次數(shù)，對一輛車進(jìn)行跟蹤時，傳統(tǒng)算法需要2 ～3 次迭代才能完成一次搜索，而本文改進(jìn)的跟蹤算法為平均1 次，提高了監(jiān)控系統(tǒng)的實(shí)時性。

圖7 傳統(tǒng)算法與本文算法迭代次數(shù)對比圖

4 小結(jié)

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

［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］鄭可飚，黃文清，張佐理，等. 運(yùn)動目標(biāo)跟蹤系統(tǒng)的遮擋問題處理［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(11):2816－2818.

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

［6］康一梅，謝晚冬，胡江，等. 目標(biāo)尺度自適應(yīng)的Mean－Shift 跟蹤算法［J］.兵工學(xué)報(bào)，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，F(xiàn)ENG 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］李弟平，鄒北驥，傅自剛. 快速運(yùn)動目標(biāo)的Mean－Shift 的高速運(yùn)動目標(biāo)跟蹤［J］.小型微型計(jì)算機(jī)系統(tǒng)，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］劉軍學(xué)，屈楨深，任行行，等.基于改進(jìn)運(yùn)動歷史圖像的多運(yùn)動目標(biāo)實(shí)時跟蹤［J］.計(jì)算機(jī)應(yīng)用，2008，28(3):199－200.

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