摘  要： 為了提高基于幾何形態的物體跟蹤方法的準確率，詳細分析了基于幾何形態的物體跟蹤方法下目標點的正確性，并根據分析的結果，在對目標物體采樣時選取更容易被跟蹤到的目標點，對于跟蹤的結果，排除由于背景影響產生的無效目標點，從增強有效點和排除無效點這兩方面入手，提出了基于LK光流法的有效點增強跟蹤算法。實驗證明，提出的算法能夠更加有效地跟蹤物體，尤其是當目標快速運動或者發生形變時，能夠有效地減少跟蹤目標的中心錯誤率。

　　關鍵詞： 目標跟蹤；LK光流法；有效點增強

0 引言

　　基于幾何形態的物體跟蹤方法是計算機視覺領域一個被廣泛研究的問題，其中普遍使用的方法是先用矩形或橢圓形的包圍盒初始化需要被跟蹤的物體，給出包圍盒在t時刻的大小及位置，跟蹤器跟蹤物體運動并估計在t+1時刻包圍盒的大小及位置。為了讓跟蹤算法適應被跟蹤物體所在環境的變化和物體本身外觀的改變，視頻跟蹤的方法也越來越復雜，但無論是基于生成模型的跟蹤方法，還是基于辨別模型的跟蹤方法，都會假設被跟蹤的物體在t時刻的狀態是已知的并且是正確的，而對于絕大多數現實世界的視頻來說，這個假設成立的條件非常苛刻，導致跟蹤器跟蹤失敗。

　　LK光流法自從1981年被提出后，就被廣泛應用于計算機視覺的各個方面，如醫學圖像配準[1]、圖像拼接[2]、視頻追蹤[3-4]等領域。對于給定的模板，LK光流法用梯度下降的方法求解圖像中與模板誤差最小的塊。而在視頻跟蹤領域，流傳最廣的就是Lucas-Kanade跟蹤算法[5]以及它的金字塔應用[6]，兩個算法依靠估計被跟蹤塊的平移量來確定物體的運動方向。在此基礎上，Kanade-Lucas-Tomasi跟蹤器[7]又將仿射變換和角點檢測的方法引入了LK光流法之中，進一步增強了追蹤的效果。由于LK光流法需要耗費大量運算重新估計Hessian方程，HAGER G D[4]提出了交換圖像與模板的角色的方法，提高了追蹤的效率。而后，上述文章中所提到的思想又被重新整合，形成了反向組合算法[8]。

　　為了降低失敗率，本文在LK光流法的基礎上分析了導致追蹤失敗的幾個原因，并結合這些原因提出了一種新的跟蹤算法。

1 追蹤點的正確性分析

　　LK光流跟蹤法作為一種基于模板的追蹤算法，首先需要在包圍盒中選取有效的跟蹤點，然后在視頻的每幀之間建立點到點的運動軌跡，最后根據跟蹤到的有效點估計新的包圍盒。這樣的跟蹤方式存在以下問題：首先，對于跟蹤點，每次跟蹤結果不可避免地會產生誤差，由于誤差的累積，便會導致跟蹤窗口的偏移；其次，如果某些目標點所在部分在后續視頻中突然產生形變，被遮擋或者消失，跟蹤器將會丟失目標，導致跟蹤失敗[9-10]。為了降低跟蹤器的失敗率，首先引入了一套判斷機制判斷跟蹤到的點是否有效；其次，由于使用包圍盒初始化追蹤器，目標物體不可避免地會帶入背景信息，影響跟蹤器的跟蹤效果，為了提高正確率，本文從初始化目標點的選取和排除兩方面進行分析并提出了新的增強有效跟蹤點的方法。

　　1.1 被跟蹤點的失效檢測

　　這里主要引入了Forward-Backward錯誤檢測和SSD錯誤檢測兩種檢測被跟蹤點是否失效的方法。

　　SSD錯誤檢測方法是最常用的跟蹤錯誤檢測方法之一。這種檢測方法假設在跟蹤過程中目標點所在環境的變化量在一定范圍內。實現方法如下，在t時刻，用目標跟蹤點周圍的圖像塊R描述目標跟蹤點。跟蹤目標點至t+1時刻，并得到它在t+1時刻的描述R′，SSD錯誤檢測算法的跟蹤誤差則表示為：

　　SSD=‖R-R′‖（1）

　　SSD值用來衡量兩個圖像塊的相似程度，SSD值越高，表示兩個圖像塊之間越不相似，SSD值高于某個閾值時，則跟蹤錯誤。這種誤差描述方法的缺陷如圖1（a）所示，位于車胎前輪的點②因為被遮擋而在第二張圖中消失，但由于圖片中存在與點②極其相似的點③，跟蹤器跟蹤點②到點③，SSD錯誤檢測方法無法排除被錯誤跟蹤的點③這種點漂移的情況。為了解決這種錯誤跟蹤的情況，引入了Forward-Backward錯誤檢測方法。

　　Forward-Backward錯誤檢測方法是基于正向追蹤與反向追蹤的一致性假設產生的方法，認為被正確追蹤到的點應該獨立于時間軸，即正向追蹤和反向追蹤生成的軌跡差別不大。具體實現方法如圖1（b）所示。用S=（It，It+1，…，It+k）表示一段視頻中的一系列幀，Pt為其中一個被跟蹤點在t時刻的位置，首先，追蹤器追蹤點Pt，經過正向追蹤k步后生成點Pt的軌跡T=（Pt，Pt+1，…，Pt+k）。然后，令t+k=Pt+k，反向追蹤t+k，同樣生成追蹤k步后的軌跡T=（t+k，t+k-1，…，t）。最后，比較兩條軌跡，如果它們相差太遠，則跟蹤錯誤。為了簡化運算，本文使用點Pt與t之間的歐式距離表示兩條軌跡之間的差距，則

　　如果正向跟蹤目標物體的軌跡與反向跟蹤目標物體軌跡之間的差距小于一定的閾值，則認為目標點已被正確地跟蹤到。

　　圖1中，Forward-Backward錯誤檢測方法可以排除正向追蹤軌跡與反向追蹤軌跡差別太大的點。點①在兩張圖中均可見，跟蹤器正向追蹤與反向追蹤的結果一致；點②因為被遮擋而在第二張圖中消失，導致正向追蹤軌跡與反向追蹤軌跡差別較大。

　　1.2 跟蹤點初始化

　　跟蹤器在跟蹤過程中的表現對跟蹤點的初始化方法非常敏感，因此，如何初始化跟蹤點也就顯得至關重要。初始化跟蹤點通常有兩種方法：靜態初始化方法和適應性初始化方法。靜態初始化方法采用第一幀包圍盒中的點初始化跟蹤器，對于目標點的選擇，一種方法是隨機選擇包圍盒中的點作為目標點；另一種方法則是用第一幀中的特征點初始化跟蹤器[5，7]。但問題是，由于靜態模板不足以表達被追蹤物體的所有形態，即使是包圍盒中的特征點，也有可能在后續視頻中被遮擋、消失或者發生形態的改變而導致跟蹤失敗。適應性初始化方法在追蹤過程中逐漸更新目標模型，這種方法的好處是可以適應物體外表、光照或者周圍環境的變化。但是由于每步更新產生的誤差的累積，包圍盒會逐漸發生漂移。

　　為了辨別什么樣的目標點更容易被跟蹤到，本文分別使用LK光流法跟蹤視頻第一幀中所有像素點和第一幀中的特征點，并使用Forward-Backward錯誤檢測方法和SSD錯誤檢測方法排除跟蹤錯誤的點，結果如圖2所示，可以發現：（1）如果目標點周圍沒有任何特征點存在，那么目標點一定不能被追蹤到；（2）并不是所有特征點在追蹤過程中都能被追蹤到；（3）特征點周圍的點比其他目標點更容易被追蹤到。

　　結合上述特點，特征點及其周圍的點被跟蹤到的概率更高，在連續兩幀圖像中，尤其如此。但是，如果每幀都計算特征點，需要耗費大量的運算，從而降低了跟蹤效率。為此，本文提出一種新的目標點選取方法來權衡靜態初始化和適應性初始化方法：（1）首先用包圍盒中的隨機點初始化視頻的第一幀；（2）用LK光流法跟蹤這些目標點，分別計算這些點的SSD誤差和Forward-Backward誤差；（3）保留誤差最低的20%的目標點；（4）在初始化下一幀時，在保留下來的目標點周圍再隨機選取目標點。

　　1.3 基于運動域的錯誤點檢測

　　LK光流法使用跟蹤到的有效點估計下一幀的目標包圍盒，為了包圍所有的有效點，在估計的包圍盒中會逐漸帶入背景信息。使用LK光流跟蹤法跟蹤目標物體，并使用Forward-Backward錯誤檢測方法和SSD錯誤檢測方法排除被錯誤跟蹤的點，其中連續兩幀的檢測結果如圖3所示。圖3（a）中的點為t時刻在目標跟蹤物中選取的被跟蹤的點，圖3（b）為使用LK光流法跟蹤目標點至t+1時刻并且使用Forward-Backward錯誤檢測方法和SSD錯誤檢測方法后保留下來的目標點，部分目標點位于被跟蹤的物體上，而部分則在背景環境中，對于目標點的跟蹤，這些保留下來的目標點都是可靠的，但對于目標物體的跟蹤，位于背景環境中的點則會讓跟蹤窗口逐漸產生漂移。但是在大部分情況下，被跟蹤物體上目標點的運動方向與背景環境中目標點的運動方向并不一致，圖3（c）記錄了所有可靠的目標點從t時刻到t+1時刻的運動方向，圖3（d）為對運動方向統計的結果，高度較高的方塊統計位于跟蹤物體上的目標點的運動方向，高度較矮的方塊統計位于背景環境中的目標點的運動方向，可以發現，目標物體的運動方向與背景的運動方向發生了明顯的分離。

　　利用這個特性，可以降低背景環境的點對跟蹤結果的影響，具體方法如圖4所示。

　　首先，對于所有可以被追蹤的目標點m，計算其運動方向向量m。

　　然后，對運動方向向量進行分類。筆者認為，如果存在目標物體的運動方向和背景的運動方向發生分離，那么將所有運動方向向量投射到單位圓后，運動方向向量會呈現出明顯的區域化特征，如果對所有單位化后的運動方向向量按照逆時針0~360°方向進行編號，其中某些相鄰運動方向向量之間的夾角會明顯大于其他的相鄰運動方向向量之間的夾角。基于這個假設，需要先對運動方向單位化：

　　而后對單位化后的運動方向向量按照逆時針方向進行編號，對于兩個編號相鄰的運動方向，計算它們之間的夾角：

　　逆時針方向上編號最大的運動方向向量計算夾角時，m+1為編號為（1）的方向向量。而后，設置一個閾值t，如果cos?茲m≤t，則保留這時夾角的編號m。

　　如圖5所示，由于余弦函數在0~2π的范圍內并不是單調遞減函數，因此需要排除余弦值大于t，但是角度卻大于預設值的運動方向向量夾角。這里通過判斷運動方向向量所在象限進行排除，如果相鄰運動方向向量夾角的余弦值大于t，對于m+1和m，通過其坐標，確定所在的象限m+1和m，如果兩個象限不連續，則同樣記錄下夾角的編號。然后，從記錄下來的編號處分開，將運動方向分為Nm類。

　　最后，在分類的基礎上確定主運動方向，統計每類中運動方向向量的數量：

　　如果其中一類中運動方向向量的數量明顯大于其他類，則確定這類為目標物體的運動方向，保留擁有這類運動方向向量的目標點。

　　2 基于LK光流法的有效點增強方法

　　前面分析了目標點的正確性，結合上述分析，提出了魯棒性更強并且效果更好的基于LK光流法的有效點增強跟蹤方法。除視頻第一幀外，追蹤器接收相鄰兩幀圖片It和It+1以及在t-1時刻到t時刻追蹤到的所有目標點Pt，輸出從t時刻到t+1時刻追蹤到的所有目標點Pt+1，再根據Pt+1估計t-1時刻包圍盒的位置。算法流程如圖6所示。

　　（1）隨機初始化第一幀的包圍盒。

　　（2）追蹤目標點，其中，依靠LK光流追蹤器生成從時刻到t+1時刻目標點的運動軌跡。

　　（3）按照式（1）和式（2）對追蹤到的目標點進行SSD錯誤檢測和FB錯誤檢測。

　　（4）按照1.3節提出的方法分離背景與目標物體，進一步去除在背景中的目標點。

　　（5）在剩下的點中保留20%誤差最小的目標點，并根據它們重新估計包圍盒。對于包圍盒的估計，首先假設物體可以表示為方形的圖像塊，找到目標點中最小行數rmin、最大行數rmax、最小的列數cmin、最大列數cmax，并設置一個范圍值，則新的包圍盒可表示為[cmin，rmin，cmax，rmax+]。

　　（6）在以保留下來的目標點為中心，R為半徑的區域內重新選擇追蹤目標點，并在下一次追蹤中重復步驟（2）到步驟（6），直到整個視頻完結。

3 實驗結果與分析

　　本節分別在三個數據集上實驗了基于LK光流法的有效點增強跟蹤算法，并與中值跟蹤算法進行對比，采用中心錯誤率來衡量試驗結果的準確性，實驗結果圖7所示。首先，對于快速運動、正常運動或者在運動過程中產生了形變的目標，中值跟蹤算法和基于LK光流法的有效點跟蹤算法的中心錯誤率在總體上均呈現出逐步上升的趨勢，這是由于每步更新均會產生誤差，誤差逐步地累積導致中心錯誤率逐步上升，但是無論在哪種情況下，基于LK光流法的有效點增強跟蹤算法的中心錯誤率總是低于中值跟蹤的中心錯誤率。

　　但是，當目標物體為快速運動狀態或者當目標物體發生形變時，本文提出的方法的中心錯誤率會明顯低于中值跟蹤算法，這是因為在這兩種狀態下目標物體的包圍盒中更加容易帶入背景信息，這些背景信息則導致目標中心誤差越來越大，而本文的方法減少了背景信息的影響，所以中心錯誤率會維持在能夠接受的范圍內。

4 結論

　　本文詳細分析了在基于幾何形態的物體跟蹤中被追蹤的目標點的正確性，并根據分析的結果，提出了基于LK光流法的有效點增強跟蹤算法，經過優化后的算法能夠更加有效地跟蹤物體，尤其是當目標快速運動或者發生形變時，采用本文方法能有效地將中心錯誤率控制在一定的可以接受的范圍之內。但是由于增加了對跟蹤到的點的處理步驟，產生了額外的計算，因此效率方面稍稍低于原來的方法。以后的工作會著重提高效率，改進有效點的選取策略，并且將之運用在更多的數據集上進行測試，同時利用測試結果進一步改進策略。

　　參考文獻

　　[1] CHRISTENSEN G E， JOHNSON H J. Image consistent registration[J]. IEEE Transactions on Medical Imaging， 2004，20（7）：568-582.

　　[2] SHUM H Y， SZELISKI R. Construction of panoramic image mosaics with global and local alignment[J]. International Journal of Computer Vision， 2000，16（1）：63-84.

　　[3] BLACK M， JEPSON A. Eigen-tracking： robust matching and tracking of articulated objects using a view-based representation[J]. International Journal of Computer Vision， 1998，36（2）：101-130.

　　[4] HAGER G D， BELHUMEUR P N. Efficient region tracking with parametric models of geometry and illumination[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1998，20（10）：1025-1039.

　　[5] LUCAS B D， KANADE T. An iterative image registration technique with an application to stereo vision[J]. International Joint Conference on Artificial Intelligence， 1981（81）：674-679.

　　[6] BOUGUETJ Y. Pyramidal implementation of the lucas kanade feature tracker description of the algorithm[M]. Technical Report， Intel Microprocessor Research Labs， 2000.

　　[7] SHI J， TOMASI C. Good features to track[C]. Conference on Computer Vision and Pattern Recognition， 1994：593-600.

　　[8] BAKER S， MATTHEWS I. Lucas-kanade 20 years on： a unifying framework[J]. International Journal of Computer Vision， 2006，56（3）：221-255.

　　[9] ROSTEN E， DRUMMOND T. Machine learning for high-speed corner detection[C]. ECCV 2006， 2006，3951：430-443.

　　[10] MCCANE B， NOVINS K. On benchmarking optical flow[J]. Computer Vision and Image Understanding， 2003，84（1）：126-143.