基于交通視頻序列的多運動目標跟蹤算法

高韜，劉正光，張軍

(天津大學 電氣與自動化工程學院，天津，300072)

多運動目標跟蹤應用廣泛，特別是在交通視頻監控方面，對其進行了廣泛的研究，提出了許多識別跟蹤算法。然而，這些算法大都只針對某一特定場景，并且由于硬件的限制，這一課題的發展歷史較短，而且其內容涉及到圖像處理、模式識別和人工智能等多個學科，其理論還不夠完善，一些重要的問題尚未解決，行之有效的方法和技術還有待開發。肖敬若等[1]結合擴展卡爾曼濾波法與均值漂移法對運動目標進行跟蹤，該方法可用于背景較復雜的情況，但是，當目標形變較大，并且運動方向改變時，跟蹤往往會失效。Yao等[2]通過光流法識別運動目標后，利用卡爾曼濾波，采用運動區域顏色特征匹配跟蹤方法，對多個目標進行跟蹤，但該方法只適用于背景較簡單、目標較明顯的情況。如果背景過于復雜且目標不明顯，會導致處理速度過慢，影響跟蹤效果。Lei等[3-4]使用混合高斯模型背景建模法檢測運動目標，并通過卡爾曼濾波，利用目標顏色直方圖和形狀模型進行匹配識別，從而對多目標進行跟蹤。但跟蹤匹配參數無法自適應獲得，常會導致累積跟蹤誤差，準確度較低。Okuma等[5-6]提出Boosted粒子濾波與均值漂移相結合的多目標跟蹤算法，可有效地跟蹤人體等非剛體目標，并且具有較好的抗遮擋性。但該算法事先需要大量的樣本訓練，計算復雜度高，并且不適用于目標大小變化劇烈的場景，限制了它的應用。盧曉鵬等[7]也提出一種Mean-shit與粒子濾波結合跟蹤算法，首先應用Mean-shift 算法進行跟蹤，由得到的目標位置計算相似系數，與預先設定好的門限系數比較并采用不同的濾波策略，具有一定的抗遮擋性。但該算法同樣沒有考慮目標大小變化明顯的情況，并且選擇粒子采樣的門限閾值需人工預先設定，不利于實際應用。在多目標數據關聯方面，最直接的方法是最近鄰域(NN)法，即如果1個量測與1個目標軌跡的空間距離最近，則該量測為該目標的當前量測，但在實際應用中采用歐式距離的測度常存在各種缺陷；聯合概率數據關聯濾波(JPDA)算法[8-9]綜合考慮了相交的波門內的所有回波和航跡，在密集回波環境下，跟蹤多個近距離機動目標時仍然有很好的跟蹤性能，但其計算量隨著跟蹤門內回波數目的增長而呈指數增長。在密集回波環境下，由于其計算量和存儲量巨大而難于在實際中應用。多假設數據關聯跟蹤算法(MHT)[10]把多個假設繼續傳遞，讓后續的觀測數據解決這種不確定性，但其主要應用在雷達領域的航跡跟蹤。目前，數據關聯根據先驗知識，如目標的動力學特征，將檢測結果與目標狀態關聯起來，并對跟蹤軌跡進行濾波，而針對視頻監控領域，攝像頭與圖像之間相關性較低，所以，應對被跟蹤目標建模并據此在圖像序列各幀中定位目標。針對現有跟蹤算法的不足，本文作者提出一種結合SIFT特征粒子濾波和Mean-shift算法，采用隊列鏈表結構數據關聯的多目標跟蹤算法，提高了跟蹤的準確性與效率，具有較高的應用價值。

1 運動目標識別

背景減法是目前最常用的一種識別算法，相對于其他算法，能夠提供最完整的運動信息，而且其操作簡單，檢測位置準確且速度快。但該算法的性能完全取決于背景生成的質量。本文作者對運動目標識別采用一種基于Marr小波概率核函數的背景算法(MarrB)，并在 B/RDWT(Binary/redundant discrete wavelet transforms)域[11]提取運動信息從而檢測運動目標。

1.1 靜態背景生成

將初始幀作為背景B，設當前輸入幀為f，分別對其進行金字塔1/2分解，進行2級分解的公式為：

其中：n1和n2都為3，表示高斯濾波核寬；均方差σ為0.5。交通監控攝像頭一般固定在道路標桿上，考慮到車輛干擾對其引起的輕微震動，設偏移矩陣為[v,h]，v和h分別代表垂直和水平抖動參數。設第n-1級的初始偏移矩陣為[vn-1,hn-1]，偏移函數為：

其中：fmax和fmin分別為圖像中像素的最大和最小灰度。為了便于實際運算，采用 Gauss函數的差ψ(t)=形成的DOG(Difference of Gaussian)來近似Marr小波。不斷調整(Δx,Δy)，根據最佳近似度得到最佳偏移距離同時，將作為下一級fn的初始偏移矩陣。通過逐級迭代，最終確定背景圖像的擴展范圍。設偏移修正過后初始背景像素為B(i,j)，當前幀像素為f(i,j)，定義當前幀與背景偏差的Marr核概率分布為：

圖1 背景建模比較Fig.1 Background modeling comparison

其中：控制參數α=0.3；方差γ初值取β=0.01。同時，設背景像素更新權重為：

則迭代更新背景為：

其中：i為迭代次數；N為處理視頻序列幀數。圖 1所示為連續幀差法、混合高斯法和本研究中使用的MarrB算法對交通視頻序列背景建模的結果。從圖 1可知：MarrB算法在去除背景噪聲以及靜態背景生成方面具有更佳的抗干擾魯棒性。

1.2 B/RDWT域運動目標識別

分別對背景和當前幀進行B/RDWT，在離散小波域直接提取運動信息。對于二維數字圖像，可采用二進小波變換的特例：冗余離散小波變換(RDWT)來實現。冗余離散小波變換是除去了下采樣的離散小波變換。由于沒有下采樣，不同尺度的時間抽樣率固定，離散小波變換固有的平移變化在這里被消除，并且冗余離散小波變換后各子帶的大小與輸入信號的大小相同，從而運動信息M(x,y)可根據各子帶差異獲得，具體過程可參考文獻[11-12]。圖2所示為當前幀以及根據運動區域多運動車輛目標識別檢測結果。

圖2 運動車輛檢測Fig.2 Motion vehicles detection

1.3 邊緣陰影剔除

要剔除陰影，首先要判斷圖像中是否有陰影存在，目前，判斷場景中是否有陰影存在的研究較少。毛燕芬等[13-14]將前景像素分為“暗色”和“亮色”，定義“亮色”像素點的平均能量為Eb，陰影程度為Pd，當前景區域的Eb和Pd都超過相應閾值時，判斷存在陰影。但閾值常由經驗判定，并且當背景環境較復雜時，常會誤判。一般地，當場景中光照較強時，陰影很可能存在，因此，本文作者采用直接判斷背景亮度來判斷是否有陰影。當亮度超過類間方差閾值T的像素數目時，判斷為存在陰影，一般T取全部像素數目的1/4。該方法處理速度快、效果好，即使偶爾誤判，由于采用邊緣陰影剔除算法，也不會導致目標丟失。目前，運動目標陰影檢測一般采用基于彩色空間的方法[15-16]。該方法認為陰影區域色彩變化很小，只是背景彩色分量乘以某個系數K(掩膜)，以此進行陰影分割。但是，在某些情況下，目標和陰影在顏色信息上沒有明顯的差別，例如，當交通道路環境中同時存在黑車和陰影時，難于區分黑車與黑色陰影。一般認為，陰影處具有稀少的邊緣細節，而目標內部邊緣細節豐富。本研究中，依靠完整提取的前景信息，首先，對前景模板進行“Canny”算子邊緣提取，然后，對前景區域進行“Sobel”邊緣提取，除去噪聲后的兩者信息的差值即可得到運動目標。圖3所示為該算法各步驟處理結果。

2 結合SI_P與Mean-shift的跟蹤算法

以檢測出來的運動目標信息作為后續幀跟蹤的初始條件，采用一種結合 SIFT特征粒子濾波和 Meanshift的跟蹤算法，提高跟蹤的準確度。

2.1 SI_P算法

SIFT特征點[17]代表了運動目標魯棒性特征，將其與粒子濾波算法[18-19]相結合，形成 SI_P濾波算法。初始粒子的選取以及狀態轉移都以 SIFT特征點為依據。算法具體過程如下。

(1)樣本初始化。在初始幀中通過運動目標識別算法確定目標區域，并計算目標模板的顏色概率分布：

其中：I為粒子區域的像素的個數；δ為Kronecker余子函數；參數a為粒子區域的規模大小；h代表顏色直方圖；xi為第i個像素點的位置；函數f為歸一化因子；k為Epanechnikov核函數的輪廓函數。結合目標區域和當前幀 SIFT特征點建立初始狀態樣本集合

(2)由替代選擇法[20]根據樣本權值從樣本集St-1中抽取N個樣本。計算樣本集合歸一化累積權值，產生[0, 1]區間上的均勻分布的隨機數r。在樣本中搜索使得權值的最小k，并使

(3)設樣本空間通過運動模型

其中：A為狀態轉移矩陣；R為擾動矩陣；r為隨機高斯矩陣。A和R分別為：

其中：σ=3, 0.35α= 。同時，將t時刻由SIFT匹配的特征點賦予St，得到Ssift,t。

(4)計算候選樣本分布和目標模板的Bhattacharyya系數

重新計算Ssift,t中每個樣本的權值：

圖3 陰影剔除后的目標提取Fig.3 Targets segmentation after removing shadow

(5)由樣本的加權平均估計t時刻運動目標的中心位置：

圖 4所示為結合 SIFT特征點的粒子濾波跟蹤結果。

2.2 Mean-shift運動目標邊界提取

Mean-shift[21]是一種基于外部特征的跟蹤算法，能夠對機動目標進行實時跟蹤。對于目標實時跟蹤，設由 SI_P濾波得到的目標中心初始位置為y?0，計算分布概率，然

后計算權值{wi}，其中：

為顏色概率分布函數；i=1, …,nh。令g為加權核函數，則目標中心新位置為：

則

通過自適應改變Marr小波核寬尺度，較好地解決了上述問題。

3 多目標數據關聯

對于交通視頻監控序列，車輛的行駛情況與數據結構的隊列鏈表類似，先駛進某一道路場景的車輛一般也先離開道路(違章超車情況較少，并且不影響跟蹤準確性)。因此，對于多運動車輛的跟蹤數據關聯采用隊列鏈表處理法(如圖 5所示)，鏈表中每一個元素代表運動車輛，元素為結構體，包含車輛的中心位置、四周邊界點位置、行駛方向、內部顏色概率分布以及最佳Bhattacharyya匹配系數等重要信息。

(1)新目標的進入。在空間上，新目標只可能在視頻圖像幀的邊界區域出現。若在圖像的邊界區域檢測到1個觀測值，中心為y, 則計算其和所有現存目標的距離D；若該距離遠大于目標在相鄰幀中可能運動的距離，則說明該觀測為1個新目標，在隊列鏈表中插入相應新元素值。否則，計算其顏色概率分布pu(y)，判斷其與現存運動目標{ω1,ω2, …,ωn}的Bhattacharyya相關系數ρ，即若ρ小于現存目標的Bhattacharyya系數，則判斷為新目標；否則，選取差值最大的為最佳匹配目標的狀態變化，并更新鏈表對應元素內部結構值。

圖4 SIFT特征點粒子濾波跟蹤Fig.4 Particle filtering tracking based on SIFT matching

圖5 隊列鏈表數據關聯Fig.5 Data association of queue technique

(2)舊目標的消失。舊目標的消失也只可能出現在圖像的邊界區域。假設上一幀圖像中的目標ωi接近邊界，即將在下一幀圖像消失，則用如下方法對消失目標進行判定：讀取新一幀圖像，計算目標ωj與新一幀中各目標{ω1,ω2, …,ωm}的 Bhattacharyya相關度，若與任何目標都不相關，則目標ωj消失。

該方法的優點在于運算復雜度低及利于交通監控。在實際監控中，更關心對違章車輛的監控，如跨道行駛、逆行和闖紅燈等車輛，對這些車輛可根據目標的中心值以及行駛方向快速判斷。對于無違章行為的目標可以提前從隊列鏈表中刪除，不進行處理，從而提高跟蹤系統的性能并降低對硬件的需求，利于現場應用。

4 實驗結果

圖 6所示為傳統粒子濾波跟蹤與 SI_P(SIFT-particle)濾波跟蹤性能，十字代表粒子狀態，黑線為濾波得到的運動軌跡。從圖6可以看出：在SI_P算法中，每幀中的粒子一直保持在目標區域內，而在傳統粒子濾波算法中，由于目標面積改變，軌跡誤差較大，從而偏移運動物體導致跟蹤失效。

同時，在CPU為1.4 GHz，內存為512 M，軟件為 VC++6.0的環境下，選取 15幀圖像(分辨率為768×576)，對兩者的運行時間進行對比，結果如圖7所示，添加SIFT特征點提取過程后，SI_P平均運行時間只比粒子濾波算法的平均運行時間多 0.15 s，完全在監控系統時延容許范圍內。

對于交通視頻序列的多目標跟蹤，雖然遮擋車輛目標的分離是一個很難的問題，但是在交通監控的實際應用中，對于在遮擋情況比較嚴重時(比如交通路口的堵車)，往往更關心的是堵車隊列的長度，對于單獨車輛的分割沒有很高的要求；只有在車流比較順暢時才更關心單獨車輛的檢測與跟蹤，而在這種情況下，車輛之間往往都有一定的間距，遮擋的情況比較少，即使有也比較簡單。圖8所示為高速上車輛路監控結果。在實際監控應用中，當車輛目標過于細小時監控也無意義，行人和遠處車輛可作為噪聲去除，而主要關注近景車輛。作為比較，將本文跟蹤系統與目前使用較廣泛的 MoG-Kalman多目標跟蹤系統[3-4]進行對比，測試序列選為市區車流量較大時的監控錄像片斷。圖9和圖10所示為2種跟蹤系統的測試結果。從圖9和圖10可以看出，由于背景建模以及運動識別的準確性，本文作者提出的跟蹤系統能有效地除去行人、晃動的樹葉及光照的變化等背景噪聲的影響(為清晰起見，去掉了粒子顯示)，同時跟蹤窗口尺度隨目標大小自適應改變，并且對車輛的相互遮擋也具有一定的魯棒性；而MoG-Kalman多目標跟蹤系統由于背景差的缺陷，識別結果具有較大誤差，往往只含有噪聲信息，跟蹤窗口也無法自適應改變尺度。對于該序列，設識別誤差測度e為：

圖6 傳統粒子濾波與SI_P濾波跟蹤Fig.6 Traditional particle filtering and SI_P filtering tracking

圖7 運行時間對比Fig.7 Runtime comparison

圖8 高速路跟蹤結果Fig.8 Multiple targets tracking on freeway

圖9 本文跟蹤系統在市區道路上的多目標跟蹤結果Fig.9 Multiple targets tracking on urban road by system provides by authors

圖10 MoG-Kalman跟蹤系統在市區道路上的多目標跟蹤結果Fig.10 Multiple targets tracking on urban road by system of MoG-Kalman

其中：r為算法識別跟蹤的全部像素數目；f為前景像素數目。選取0～230幀作為對比對象，識別誤差結果如圖11所示。

圖11 誤差測度比較Fig.11 Error comparison

5 結論

(1)提出了一種基于交通視頻序列的多目標跟蹤算法。該算法通過Marr小波概率核函數生成靜態背景，提高了背景生成的有效性，并結合當前幀在B/RDWT域進行多運動目標識別，同時采用邊緣陰影剔除算法去除陰影的干擾。

(2)運動跟蹤采用新型的SI_P粒子濾波算法，并結合均值漂移法獲得運動目標的準確跟蹤窗口，并自適應改變尺度。采用隊列鏈表法記錄多運動目標之間的數據關聯，在提高識別準確率的同時降低了運算的復雜度。實際道路測試結果表明：該算法對于多運動目標識別跟蹤具有優越的性能，可應用于智能交通監控、跟蹤等。

[1] 肖敬若, 張艷寧, 胡伏原, 等. 一種魯棒的多目標自動跟蹤算法[J]. 信號處理, 2007, 23(3): 437-440.XIAO Jing-ruo, ZHANG Yan-ning, HU Fu-yuan, et al. A robust automatic multi-target tracking algorithm in complex environments[J]. Signal Processing, 2007, 23(3): 437-440.

[2] Yao F H, Sekmen A, Malkani M J. Multiple moving target detection, tracking, and recognition from a moving observer[C]//Proceedings of the IEEE International Conference on Information and Automation. New York: IEEE, 2008:978-983.

[3] LEI Bang-jun, XU Li-qun. Real-time out-door video surveillance with robust foreground extraction and object tracking via multi-state transition management[J]. Pattern Recognition Letters, 2006, 27(15): 1816-1825.

[4] Rowe D, Reid I, Gonzàlez J, et al. Unconstrained multiple-people tracking[C]//Proceedings of the 28th DAGM Symposium. Berlin: Springer, 2006: 505-514.

[5] Okuma K, Taleghani A, Freitas N, Little J, Lowe D. A boosted particle filter: multitarget detection and tracking[C]//Proceedingsof the 8th European Conference on Computer Vision. Berlin:Springer, 2004, 1: 28-39.

[6] CAI Yi-zheng, Freitas N, Little J. Robust visual tracking for multiple targets[C]//Proceedings of the 9th European Conference on Computer Vision. Berlin: Springer, 2006, 4: 107-118.

[7] 盧曉鵬, 殷學民, 鄒謀炎. 一種基于顏色分布的混合視頻跟蹤方法[J]. 電子與信息學報, 2008, 30(2): 259-262.LU Xiao-peng, YIN Xue-min, ZOU Mou-yan. A hybrid algorithm of object tracking based on color distribution[J].Journal of Electronics & Information Technology, 2008, 30(2):259-262.

[8] 巴宏欣, 趙宗貴, 楊飛, 等. 多傳感器多目標跟蹤的 JPDA算法[J]. 系統仿真學報, 2004,16(7): 1563-1566.BA Hong-xin, ZHAO Zong-gui, YANG fei, et al. JPDA in multisensor multitarget tracking[J].Journal of System Simulation, 2004, 16(7): 1563-1566.

[9] 楊春玲, 余英林, 劉國歲. 多目標跟蹤中的數據關聯算法[J].系統工程與電子技術, 2000, 22(3): 11-15.YANG Chun-ling, YU Ying-lin, LIU Guo-sui. Data association algorithm in multi-target tracking[J]. Systems Engineering and Electronics, 2000, 22(3): 11-15.

[10] Cox I J, Hingorani S L. An efficient implementation of reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(2): 138-150.

[11] GAO Tao, LIU Zheng-guang, ZHANG Jun. Redundant discrete wavelet transforms based moving object recognition and tracking[J]. Journal of Systems Engineering and Electronics,2009, 20(5): 1115-1123.

[12] GAO Tao, LIU Zheng-guang, ZHANG Jun. BDWT based moving object recognition and mexico wavelet kernel mean shift tracking[J]. Journal of System Simulation, 2008, 20(19):5236-5239.

[13] 毛燕芬. 交通視頻監控中的目標檢測與跟蹤[D]. 上海: 上海交通大學圖書館, 2005.MAO Yan-fen. Object detection and tracking in traffic video surveillance[D]. Shanghai: Library, Shanghai Jiao Tong University, 2005.

[14] XIAO Mei, HAN Chong-zhao, ZHANG Lei. Moving shadow detection and removal for traffic sequences[J]. International Journal of Automation and Computing, 2007, 4(1): 38-46.

[15] 潘翔. 基于彩色信息和邊緣特征的運動陰影檢測[J]. 浙江大學學報: 工學版, 2004, 38(4): 389-391.PAN Xiang. Moving shadow detection based on color information and edge features[J]. Journal of Zhejiang University:Engineering Science, 2004, 38(4): 389-391.

[16] 王萍, 王波. 基于小波系數及光學特征的車輛陰影檢測[J].天津大學學報, 2008, 41(2): 199-203.WANG Ping, WANG Bo. Vehicle shadow detection based on wavelet coefficients and photometric features[J]. Journal of Tianjin University, 2008, 41(2): 199-203.

[17] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[18] Nummiaro K. An adaptive color-based particle filter[J]. Image and Vision Computing, 2003, 21(1): 99-110.

[19] Arulampalam M S, Maskell S, Gordon N, Clapp T. A tutorial on particle filters for on-line nonlinear/non-gaussian bayesian tracking[J]. IEEE Transactions on Signal Processing, 2002, 50(2):174-188.

[20] Reckleitis I. A particle filter tutorial for mobile robot localization[C]//Proceedings of the IEEE International Conference on Robotics and Automation. New York: IEEE, 2003,42: 1-36.

[21] 宋新, 沈振康, 王平, 等. Mean shift在目標跟蹤中的應用[J].系統工程與電子技術, 2007, 29(9): 1405-1409.SONG Xin, SHEN Zhen-kang, WANG Ping, et al. Application of mean shift method in target tracking[J]. Systems Engineering and Electronics, 2007, 29(9): 1405-1409.