摘  要： 為了提高基于幾何形態(tài)的物體跟蹤方法的準(zhǔn)確率，詳細(xì)分析了基于幾何形態(tài)的物體跟蹤方法下目標(biāo)點(diǎn)的正確性,，并根據(jù)分析的結(jié)果,，在對(duì)目標(biāo)物體采樣時(shí)選取更容易被跟蹤到的目標(biāo)點(diǎn)，對(duì)于跟蹤的結(jié)果,，排除由于背景影響產(chǎn)生的無效目標(biāo)點(diǎn),，從增強(qiáng)有效點(diǎn)和排除無效點(diǎn)這兩方面入手，提出了基于LK光流法的有效點(diǎn)增強(qiáng)跟蹤算法,。實(shí)驗(yàn)證明,，提出的算法能夠更加有效地跟蹤物體，尤其是當(dāng)目標(biāo)快速運(yùn)動(dòng)或者發(fā)生形變時(shí),，能夠有效地減少跟蹤目標(biāo)的中心錯(cuò)誤率,。

　　關(guān)鍵詞： 目標(biāo)跟蹤；LK光流法,；有效點(diǎn)增強(qiáng)

0 引言

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

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

　　為了降低失敗率，本文在LK光流法的基礎(chǔ)上分析了導(dǎo)致追蹤失敗的幾個(gè)原因,，并結(jié)合這些原因提出了一種新的跟蹤算法,。

1 追蹤點(diǎn)的正確性分析

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

　　1.1 被跟蹤點(diǎn)的失效檢測

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

　　SSD錯(cuò)誤檢測方法是最常用的跟蹤錯(cuò)誤檢測方法之一,。這種檢測方法假設(shè)在跟蹤過程中目標(biāo)點(diǎn)所在環(huán)境的變化量在一定范圍內(nèi),。實(shí)現(xiàn)方法如下，在t時(shí)刻,，用目標(biāo)跟蹤點(diǎn)周圍的圖像塊R描述目標(biāo)跟蹤點(diǎn),。跟蹤目標(biāo)點(diǎn)至t+1時(shí)刻，并得到它在t+1時(shí)刻的描述R′,，SSD錯(cuò)誤檢測算法的跟蹤誤差則表示為：

　　SSD=‖R-R′‖（1）

　　SSD值用來衡量兩個(gè)圖像塊的相似程度,，SSD值越高，表示兩個(gè)圖像塊之間越不相似,，SSD值高于某個(gè)閾值時(shí)，則跟蹤錯(cuò)誤,。這種誤差描述方法的缺陷如圖1（a）所示,，位于車胎前輪的點(diǎn)②因?yàn)楸徽趽醵诘诙垐D中消失，但由于圖片中存在與點(diǎn)②極其相似的點(diǎn)③,，跟蹤器跟蹤點(diǎn)②到點(diǎn)③,，SSD錯(cuò)誤檢測方法無法排除被錯(cuò)誤跟蹤的點(diǎn)③這種點(diǎn)漂移的情況。為了解決這種錯(cuò)誤跟蹤的情況,，引入了Forward-Backward錯(cuò)誤檢測方法,。

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

　　如果正向跟蹤目標(biāo)物體的軌跡與反向跟蹤目標(biāo)物體軌跡之間的差距小于一定的閾值，則認(rèn)為目標(biāo)點(diǎn)已被正確地跟蹤到,。

　　圖1中,，F(xiàn)orward-Backward錯(cuò)誤檢測方法可以排除正向追蹤軌跡與反向追蹤軌跡差別太大的點(diǎn)。點(diǎn)①在兩張圖中均可見,，跟蹤器正向追蹤與反向追蹤的結(jié)果一致,；點(diǎn)②因?yàn)楸徽趽醵诘诙垐D中消失，導(dǎo)致正向追蹤軌跡與反向追蹤軌跡差別較大,。

　　1.2 跟蹤點(diǎn)初始化

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

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

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

　　1.3 基于運(yùn)動(dòng)域的錯(cuò)誤點(diǎn)檢測

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

　　利用這個(gè)特性,，可以降低背景環(huán)境的點(diǎn)對(duì)跟蹤結(jié)果的影響，具體方法如圖4所示,。

　　首先,，對(duì)于所有可以被追蹤的目標(biāo)點(diǎn)m，計(jì)算其運(yùn)動(dòng)方向向量m,。

　　然后,，對(duì)運(yùn)動(dòng)方向向量進(jìn)行分類。筆者認(rèn)為,，如果存在目標(biāo)物體的運(yùn)動(dòng)方向和背景的運(yùn)動(dòng)方向發(fā)生分離,，那么將所有運(yùn)動(dòng)方向向量投射到單位圓后，運(yùn)動(dòng)方向向量會(huì)呈現(xiàn)出明顯的區(qū)域化特征,，如果對(duì)所有單位化后的運(yùn)動(dòng)方向向量按照逆時(shí)針0~360°方向進(jìn)行編號(hào),，其中某些相鄰運(yùn)動(dòng)方向向量之間的夾角會(huì)明顯大于其他的相鄰運(yùn)動(dòng)方向向量之間的夾角?；谶@個(gè)假設(shè),，需要先對(duì)運(yùn)動(dòng)方向單位化：

　　而后對(duì)單位化后的運(yùn)動(dòng)方向向量按照逆時(shí)針方向進(jìn)行編號(hào)，對(duì)于兩個(gè)編號(hào)相鄰的運(yùn)動(dòng)方向,，計(jì)算它們之間的夾角：

　　逆時(shí)針方向上編號(hào)最大的運(yùn)動(dòng)方向向量計(jì)算夾角時(shí),，m+1為編號(hào)為（1）的方向向量。而后,，設(shè)置一個(gè)閾值t,，如果cos?茲m≤t，則保留這時(shí)夾角的編號(hào)m,。

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

　　最后，在分類的基礎(chǔ)上確定主運(yùn)動(dòng)方向,，統(tǒng)計(jì)每類中運(yùn)動(dòng)方向向量的數(shù)量：

　　如果其中一類中運(yùn)動(dòng)方向向量的數(shù)量明顯大于其他類,，則確定這類為目標(biāo)物體的運(yùn)動(dòng)方向，保留擁有這類運(yùn)動(dòng)方向向量的目標(biāo)點(diǎn),。

　　2 基于LK光流法的有效點(diǎn)增強(qiáng)方法

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

　?。?）隨機(jī)初始化第一幀的包圍盒,。

　　（2）追蹤目標(biāo)點(diǎn),，其中,，依靠LK光流追蹤器生成從時(shí)刻到t+1時(shí)刻目標(biāo)點(diǎn)的運(yùn)動(dòng)軌跡。

　?。?）按照式（1）和式（2）對(duì)追蹤到的目標(biāo)點(diǎn)進(jìn)行SSD錯(cuò)誤檢測和FB錯(cuò)誤檢測,。

　　（4）按照1.3節(jié)提出的方法分離背景與目標(biāo)物體,，進(jìn)一步去除在背景中的目標(biāo)點(diǎn),。

　?。?）在剩下的點(diǎn)中保留20%誤差最小的目標(biāo)點(diǎn),，并根據(jù)它們重新估計(jì)包圍盒。對(duì)于包圍盒的估計(jì),，首先假設(shè)物體可以表示為方形的圖像塊,，找到目標(biāo)點(diǎn)中最小行數(shù)rmin、最大行數(shù)rmax,、最小的列數(shù)cmin,、最大列數(shù)cmax，并設(shè)置一個(gè)范圍值,，則新的包圍盒可表示為[cmin,，rmin，cmax,，rmax+],。

　?。?）在以保留下來的目標(biāo)點(diǎn)為中心，R為半徑的區(qū)域內(nèi)重新選擇追蹤目標(biāo)點(diǎn),，并在下一次追蹤中重復(fù)步驟（2）到步驟（6）,，直到整個(gè)視頻完結(jié)。

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

　　本節(jié)分別在三個(gè)數(shù)據(jù)集上實(shí)驗(yàn)了基于LK光流法的有效點(diǎn)增強(qiáng)跟蹤算法,，并與中值跟蹤算法進(jìn)行對(duì)比,，采用中心錯(cuò)誤率來衡量試驗(yàn)結(jié)果的準(zhǔn)確性，實(shí)驗(yàn)結(jié)果圖7所示,。首先,，對(duì)于快速運(yùn)動(dòng)、正常運(yùn)動(dòng)或者在運(yùn)動(dòng)過程中產(chǎn)生了形變的目標(biāo),，中值跟蹤算法和基于LK光流法的有效點(diǎn)跟蹤算法的中心錯(cuò)誤率在總體上均呈現(xiàn)出逐步上升的趨勢,，這是由于每步更新均會(huì)產(chǎn)生誤差，誤差逐步地累積導(dǎo)致中心錯(cuò)誤率逐步上升,，但是無論在哪種情況下,，基于LK光流法的有效點(diǎn)增強(qiáng)跟蹤算法的中心錯(cuò)誤率總是低于中值跟蹤的中心錯(cuò)誤率。

　　但是,，當(dāng)目標(biāo)物體為快速運(yùn)動(dòng)狀態(tài)或者當(dāng)目標(biāo)物體發(fā)生形變時(shí),，本文提出的方法的中心錯(cuò)誤率會(huì)明顯低于中值跟蹤算法，這是因?yàn)樵谶@兩種狀態(tài)下目標(biāo)物體的包圍盒中更加容易帶入背景信息,，這些背景信息則導(dǎo)致目標(biāo)中心誤差越來越大,，而本文的方法減少了背景信息的影響，所以中心錯(cuò)誤率會(huì)維持在能夠接受的范圍內(nèi),。

4 結(jié)論

　　本文詳細(xì)分析了在基于幾何形態(tài)的物體跟蹤中被追蹤的目標(biāo)點(diǎn)的正確性,，并根據(jù)分析的結(jié)果，提出了基于LK光流法的有效點(diǎn)增強(qiáng)跟蹤算法,，經(jīng)過優(yōu)化后的算法能夠更加有效地跟蹤物體,，尤其是當(dāng)目標(biāo)快速運(yùn)動(dòng)或者發(fā)生形變時(shí)，采用本文方法能有效地將中心錯(cuò)誤率控制在一定的可以接受的范圍之內(nèi),。但是由于增加了對(duì)跟蹤到的點(diǎn)的處理步驟,，產(chǎn)生了額外的計(jì)算，因此效率方面稍稍低于原來的方法,。以后的工作會(huì)著重提高效率,，改進(jìn)有效點(diǎn)的選取策略，并且將之運(yùn)用在更多的數(shù)據(jù)集上進(jìn)行測試,，同時(shí)利用測試結(jié)果進(jìn)一步改進(jìn)策略,。

　　參考文獻(xiàn)

　　[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.