基于Kalman預測和點模式匹配的多目標跟蹤

摘 要： 針對復雜背景下多運動目標的跟蹤方法不能有效解決遮擋和高速運動等問題，提出一種Kalman預測與點模式匹配相結合的多目標跟蹤方法。利用Kalman濾波預測目標在下一幀圖像中的位置，以此位置為中心確定目標搜索區域，然后以點模式匹配進行搜索區域和目標模板進行匹配，有效地解決目標的旋轉和輕微的遮擋問題。為了提高匹配速度和實時性，在點模式匹配中利用Kalman濾波對目標旋轉角度的預測與修正；同時為了保證跟蹤的魯棒性、連續性及準確性，對目標模板的更新采用置信度二級判決門限。實驗表明該方法具有較好的實時性，并能夠有效地解決遮擋等問題。

關鍵詞： 點模式匹配； 卡爾曼濾波； 置信度； 跟蹤算法； 多目標跟蹤

中圖分類號： TN911?34； TP391.41 文獻標識碼： A 文章編號： 1004?373X（2013）14?0027?04

Multi?object tracking based on Kalman filtering prediction and point matching algorithm

MA Ying?hui1， GAO Lei2， XU Xiao?wen3

（1. Computer Science Department， Suqian College， Suqian 223800， China；

2. Department of Mechanical and Electrical Engineering， Suqian College， Suqian 223800， China；

3. School of Physics Science and Technology， Central South University， Changsha 410083， China）

Abstract： Since the muti?object tracking method can not effectively overcome the target covering and high?speed movement in complex background， a new multi?object tracking algorithm based on point matching algorithm and Kalman filtering prediction is proposed. The possible position of a moving object in the next frame image is predicted by Kalman filtering. The position is regarded as the search center to determine the object seach region. The matching of the object template and the candidate regions is carried out with point matching algorithm to solve the problems of rotation and slight covering of the target. In order to improve the matching speed and real?time performance， the rotation angle of the target is predicted and corrected in the process of point matching by using Kalman filtering. The secondary judgment threshold of confidence is adopted for object template update to ensure the tracking robustness， continuity， stability and accuracy. The experimental results show that this approach has better real?time performance and can solve the covering problem effectively.

Keywords： point matching； Kalman filtering； confidence； tracking algorithm； multi?object tracking

0 引 言

在計算機視覺和模式識別領域，運動目標跟蹤一直是研究的熱點問題，在智能視頻監控、智能交通系統（ITS）、精確制導系統及機器人視覺導航等領域都有廣泛的應用[1]。目標跟蹤是在連續的圖像序列中檢測和識別感興趣的運動目標，從而得到目標的運動軌跡。跟蹤算法的好壞取決于算法的魯棒性、準確性和實時性。目前運動目標跟蹤算法有基于目標檢測的跟蹤算法，如幀間差分跟蹤算法、背景差分跟蹤算法、基于光流場估計的跟蹤算法等；基于目標檢測的跟蹤算法是對整幅圖像的信息進行處理，故跟蹤的穩定性較高，但對整幅圖像進行運算，一般計算量很大，尤其是基于光流場估計的跟蹤算法為達到一定的跟蹤效果，必須有特定硬件的支持，而且實現起來相當復雜。還有的運動跟蹤算法是為了解決跟蹤過程中觀測和模型存在的不確定性，在目標狀態估計中引入統計學模型，將運動目標抽象為具有相關運動信息的質點，如Kalman濾波，擴展卡爾曼濾波和粒子濾波等[2?3]。常用的目標跟蹤算法還有基于模板匹配的算法、基于特征點的相關算法等[4]，這些跟蹤算法計算量小，實現比較簡單，所以得到廣泛應用。

點匹配算法是基于目標特征點的跟蹤方法，能較好地解決目標的旋轉和遮擋的問題[5]；但對于做加速和高速運動的目標，其跟蹤的魯棒性較差，難以實現正確跟蹤。卡爾曼濾波可方便地預測目標的位置，該算法穩定性好，計算量小，但單獨使用Kalman濾波的跟蹤算法準確性較低。綜上考慮，針對Kalman濾波的實時性和點模式匹配能有效解決目標旋轉和遮擋問題，本文提出一種基于Kalman預測和點模式匹配的多目標跟蹤方法。首先介紹點模式匹配算法和Kalman濾波算法，其次給出了兩種算法的結合算法的思想和具體實現過程，最后實驗結果表明本文的算法能夠有效解決遮擋問題，且跟蹤的實時性和穩定性較好。

1 點模式匹配算法

點模式匹配是將同一背景的兩幅圖像中滿足一定幾何變換關系的點匹配成對，從而完成目標的識別和定位[6?8]。

在二維圖像中，特征點用坐標表示， 表示模版圖像中特征點的集合，表示待匹配圖像中特征點的集合。其中。點集和進行匹配，就是要確定一個配準函數，使得中的盡可能多的點經過變換后匹配中的子集。配準函數實質上是一個4參數的仿射變換，其中是兩幅圖像的伸縮系數，是偏轉角度，分別是沿軸，軸的位移。

（1）

2 卡爾曼濾波算法

卡爾曼濾波是采用最小方差估計的動態系統的最優化自回歸數據處理算法 [9?12]，通過動態的狀態方程和觀測方程來描述系統，如下所示：

狀態方程：

（2）

觀測方程：

（3）

式中為系統狀態從時刻到時刻的轉移矩陣；為觀測矩陣；稱為系統的作用矩陣；是協方差矩陣；是具有協方差的零均值、白噪聲序列，是零均值白噪聲序列。

Kalman濾波器包含預測和修正兩部分，Kalman濾波算法如下：

預測方程：

（4）

誤差協方差預測方程：

（5）

式中Q為零值白噪聲序列。

Kalman增益系數方程：

（6）

狀態修正方程：

（7）

誤差協方差修正方程：

（8）

預測部分得到的是先驗估計，修正部分得到的是后驗估計，完成每次的預測和修正之后，均由后驗估計值預測下一時刻的先驗估計值，重復執行以上的步驟，完成Kalman濾波的遞歸過程。

3 Kalman濾波與點模式匹配的組合算法

本文結合卡爾曼濾波算法和點模式匹配算法的優缺點，提出一種Kalman預測與點模式匹配相結合的多運動目標跟蹤方法，流程如圖1所示。

圖1 目標跟蹤的流程圖

文章中采用Kalman濾波來預測與修正目標的旋轉角度，同時還采取一種基于置信度二級判決門限的目標穩定跟蹤策略。具體的算法如下所述：

在實際的目標跟蹤中，相鄰的兩幀圖像的時間間隔較短，所以每個目標的運動狀態變化不大，故可假定目標在兩幀圖像的時間間隔內做勻速運動，定義目標的運動狀態為一個四維向量。其中：和表示在時刻目標的軸和軸的坐標；表示目標在方向和方向的運動速度。所以定義二維觀測向量為，表示匹配得到的目標坐標。

定義狀態轉移矩陣為：

（9）

式中表示相鄰的兩幀圖像間的時間間隔。

觀測矩陣為：

（10）

和的協方差矩陣為：

（11）

（12） 第一步：初始化系統對初始幀進行處理，獲得初始模版信息，采用鼠標手工選定初始模板（矩形區域）。得到目標的中心位置，將賦初值為目標的初始位置和速度。一般速度未知，可以設為零，并記錄當前圖像時刻，同時設。

第二步：利用Kalman濾波預測跟蹤目標：

（1）預測。在每幀圖像進行匹配搜索之前，記錄與上一幀圖像的時間間隔，將、狀態轉移矩陣、代入式（4），計算出時刻的目標運動狀態的先驗估計。將式（9）和式（11）一起代入誤差協方差預測方程式（5），對誤差協方差進行預測。

（2）匹配。設定搜索區域為以中的為中心的區域，在該區域內尋找最佳匹配位置，得到。

（3）修正。按式（6）求出Kalman濾波器增益系數。將代入式（7）中，得到由當前實際觀測修正后的狀態向量，同時按式（8）對誤差協方差矩陣進行修正。

第三步：點模式匹配點模式匹配算法流程如下：

輸入：模板圖像點集，待匹配圖像點集，參數、匹配可靠度和門限系數：

步驟1：確定與點集和中的每一個點最臨近的個點，并按臨近的遠近程度組成鏈表。

步驟2：由的分布來確定，利用和由公式求出匹配誤差門限。

步驟3：在模板圖像的點集中任意的選擇的一點，，確定點的個最臨近點是否是匹配點的個最臨近點，如果匹配，所求得的配準函數即為局部配準函數。

步驟4：求配準函數，由于相鄰兩幀圖像的時間間隔很短，一般認為輸入圖像和模板圖像的大小不變，因此參數應始終為1；參數可由來確定，對配準函數來說只有一個參數。由于運動目標的形狀相近和面積不大，故目標自身旋轉角度不會發生突變，因此可以利用Kalman濾波器來預測與修正旋轉角度（步驟同第一步）。然后進一步確定是否為全局配準函數。如果得到了，進行步驟5。如果沒找到，重復步驟3。

步驟5：輸出。

完成上述步驟，可確定目標的像素的坐標位置及兩幀相鄰圖像間的目標的旋轉角度，計算得到目標的置信度。

第四步： 首先對第一幀圖像得到的信息進行點模式匹配計算出目標置信度。通過置信度與門限TargetGate進行比較，來判斷Kalman跟蹤正確與否。如果所得目標置信度小于門限TargetGate時，表示沒有找到目標或目標短暫跟丟，則進入Kalman預測跟蹤狀態，擴大跟蹤門進行下一幀的搜索跟蹤，如果重新跟蹤目標，則系統再次進入自動跟蹤狀態，跟蹤門轉為正常狀態。如果連續數幀還未跟蹤上目標，則超出了目標丟失時間，此時跟蹤結束。當大于門限TargetGate時表示Kalman跟蹤正確，對目標的位置信息進行更新，當置信度大于門限RealGate時，首先對目標特征參數和目標模板進行更新處理，然后讀入下一幀圖像。當置信度大于門限RealGate，不對目標的特征參數和模板信息進行更新，直接進入目標預測跟蹤，目標位置信息由預測的位置點坐標來代替。因此一幀跟蹤結束，進行目標模板更新，讀入下一幀圖像反復進行該過程。

4 實驗結果與分析

為了驗證新算法的效果，使用爆炸復雜環境下的碎片的圖像序列進行了實驗。圖2為單目標的跟蹤結果，粉紅色框為目標跟蹤框，在第51幀，當目標灰度值與背景布灰度值比較接近是，仍可以正確識別和跟蹤目標。在第79幀，運動目標被標桿遮擋時，也能無誤的跟蹤目標，而沒有跟丟目標。因此該算法不論在遮擋前后還是在遮擋中均能準確的跟蹤目標。

圖2 單目標的跟蹤結果

圖3為多目標跟蹤結果，目標1的跟蹤框為紅色，目標2的跟蹤框為黃色，目標3的跟蹤框為普蘭色。第1幀和第30幀中目標1和目標3的距離很近，形狀基本相同，仍能搜索到目標，正常跟蹤，目標1與目標2、3的距離較遠能正確跟蹤；在第79幀中三個目標比較分散，雖然目標2被標桿遮擋，但三個目標的跟蹤效果相當于對三個單目標在復雜背景下的分別跟蹤。

圖3 多目標跟蹤結果

5 結 語

給出了Kalman濾波和點模式匹配的實現的基本框架，針對兩者的優缺點，提出兼具穩定性和實時性的跟蹤算法，該算法有效解決目標的遮擋問題。仿真結果表明，本文的算法通過點模式匹配的算法得出的置信度對卡爾曼跟蹤的效果進行判斷，從而調整跟蹤門的大小，保證跟蹤的穩定性，從而實現運動目標在背景遮擋下還是目標遮擋下均能準確跟蹤。

參考文獻

[1] WELCH G， BISHOP G. An introduction to the Kalman filter [R]. Chapel Hill， Carolina： University of North Carolina， 1997.

[2] 虞旦，韋巍，張遠輝.一種基于卡爾曼預測的動態目標跟蹤算法研究[J].光電工程，2009，36（1）：52?56.

[3] 李晶，范九倫.一種基于卡爾曼濾波的運動物體跟蹤算法[J].計算機應用研究，2010（8）：3162?3164.

[4] 譚磊，張樺，薛彥斌.一種基于特征點的圖像匹配算法[J].天津理工大學學報，2006（6）：66?69.

[5] 歐陽寧，游錦海，莫建文，等.遮擋情況下的多目標跟蹤算法[J].計算機應用研究，2010（5）：1984?1986.

[6] YIN Peng?Yeng. Particle swarm optimi?zation for point pattern matching [J]. Vis. Commun. Image R， 2006， 17： 143?162.

[7]YANG Shu?ying， GE Wei?min， ZHANG Cheng. Tracking unknown moving targets on omnidirectional vision [J]. Vision Research， 2009， 49： 362?367.

[8] ADAM A， RIVLIN E， SHIMSHONI I. Robust fragments?based tracking using the integral histogram [C]// Processings of the IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]： IEEE， 2006： 798?805.

[9] 趙樹杰，趙建勛.信號檢測與估計理論[M].北京：清華大學出版社，2008.

[10] 譚樹人，林高鵬，張茂軍.基于卡爾曼濾波的折反射全向圖像目標跟蹤.[J].電子學報，2011（2）：464?470.

[11] COMANICIU D， RAMESH V， MEER P. Real?time tracking of nonrigid objects using mean shift [C]// Proceedings of the IEEE Conf. on Computer Vision and Pattern Recogition （CVPR）. [S.l.]： IEEE， 2000： 142?149.

[12] IKOMA N， YAMAGUCHI R， KAWANO H. Tracking of multiple moving objects in dynamic image of omni?directional camera using PHD filter [J]. Journa of Advanced Computational Intelligence and Intelligent Informatics， 2008， 12（1）： 167?180.