朱安民，陳燕明

深圳大學(xué)計算機與軟件學(xué)院，深圳518060

實時跟蹤技術(shù)在軍事安全、交通監(jiān)管、智能機器人及游戲娛樂產(chǎn)業(yè)等領(lǐng)域有廣泛應(yīng)用. 實時跟蹤包括目標(biāo)檢測和目標(biāo)跟蹤兩部分，其中目標(biāo)的跟蹤部分占實時跟蹤的大多數(shù)時間，因此對跟蹤的實時性起著關(guān)鍵作用.

目前的跟蹤算法主要有點跟蹤［1］、核跟蹤［2］和輪廓跟蹤［3］. 其中，點跟蹤方法是以目標(biāo)的特征點來表征目標(biāo)，從視頻當(dāng)前幀的特征點尋找下一幀的匹配特征點，由此獲得被跟蹤的目標(biāo). 實際上，隨著目標(biāo)的運動和其所處場景的變化，在跟蹤過程中經(jīng)常發(fā)生點的特征發(fā)生劇烈變化或消失而導(dǎo)致跟蹤失敗的情況. 因此，面對光照變化、目標(biāo)形變、部分遮擋、高速運動、尺度縮放、旋轉(zhuǎn)、圖片噪音和模糊等因素，如何選取目標(biāo)的特征點是首要解決的問題. Qiao 等［4］提出利用獲得目標(biāo)的相位奇異點進(jìn)行跟蹤的方法. 當(dāng)被跟蹤的目標(biāo)有明顯紋理時，相位奇異點健壯性佳，且對縮放及旋轉(zhuǎn)不敏感. 但是，噪音干擾也易使其被誤認(rèn)為是奇異點，且在視覺模糊的情況下，奇異點易被丟失. Khan 等［5］通過建立前景特征點集和背景特征點集，由增強的各向異性mean shift 算法跟蹤兩個點集，并建立目標(biāo)模板集合進(jìn)行匹配，從而得到跟蹤軌跡. 該算法雖能較好地處理部分遮擋問題和較大程度的目標(biāo)變形問題，但由于兩個特征點集的計算量較大，運算時間長，對于高速運動目標(biāo)，跟蹤的實時性不足.Sun 等［6］采用Lowe［7］的SIFT 特征作為特征點，并建立點匹配的動態(tài)模型，但因SIFT 特征的計算量較大，且在遇到部分遮擋和變形的情況下會出現(xiàn)點跟蹤失敗，需建立目標(biāo)模板模型彌補失敗情況，進(jìn)行目標(biāo)匹配，增加運行時間，所以同樣對于高速運動目標(biāo)的追蹤效果有待提高. Pan 等［8］采用基于多層隱馬爾可夫模型的粒子濾波跟蹤. 該算法隨著層數(shù)的增加，跟蹤的準(zhǔn)確性明顯增強，但是同時計算復(fù)雜性也提高，運行時間變長.

在實時跟蹤過程中，目標(biāo)所處的運動場景的變化和映射在二維圖像中目標(biāo)的變化，都會使原本用來描述目標(biāo)的特征點消失. 因此，為持續(xù)描述被跟蹤目標(biāo)，需不斷更新描述目標(biāo)的特征點. 即使場景變化或目標(biāo)變化導(dǎo)致特征點消失，仍可通過獲得新的特征點描述目標(biāo)，實現(xiàn)繼續(xù)跟蹤目標(biāo). 為提高跟蹤的魯棒性和實時性，本研究提出特征點動態(tài)選擇模型算法，即采用Lucase-Kanade 光流法［9-10］計算跟蹤特征點，并對特征點集進(jìn)行一致性約束，從而提高特征點的可靠性. 該算法能較好地處理目標(biāo)和場景變化導(dǎo)致的特征點跟蹤丟失問題，動態(tài)選擇一段時間范圍內(nèi)能夠描述目標(biāo)的相對穩(wěn)定的特征點.

1 光流法簡介

光流是運動物體在觀察成像平面上的像素運動的瞬時速度. 光流法則是利用圖像序列中像素在時域上的變化及相鄰幀之間的相關(guān)性找到上一幀跟當(dāng)前幀之間的對應(yīng)關(guān)系，從而計算出相鄰幀之間物體的運動信息的一種方法. 本研究采用Lucase-Kanade光流法計算像素的運動變化.

光流法有3 個前提假設(shè):①相鄰幀之間的亮度I 恒定;②相鄰幀之間物體的運動較小;③保持空間一致性，即同一區(qū)域的像素具有相同運動［11］.

由假設(shè)①和假設(shè)②可得出光流約束方程為

經(jīng)一階泰勒級數(shù)展開可得

若由③假設(shè)一個局部范圍內(nèi)(u，v)相同，則

式(3)可記為Aμ = b.

圖1 為光流法點跟蹤示意圖，根據(jù)光流法計算像素點P 在下一幀的對應(yīng)點. 根據(jù)假設(shè)②，設(shè)點P為圓心，以r 為半徑的圓是P 點的可能移動范圍.在圓內(nèi)搜索亮度值相同的點，如左圖IP= Ia= Ib，根據(jù)假設(shè)③，若以P 點為中心3 ×3 的像素區(qū)域和分別以a 點和b 點為中心3 ×3 的像素區(qū)域亮度值一一對應(yīng)相等，則點a 和點b 為P 點在下一幀的可能對應(yīng)點. 比較點a 和點b 的μ 值，以μ 值最小的點作為P 點在下一幀的對應(yīng)點.

圖1 光流法點的跟蹤示意圖Fig.1 Point tracking diagram of optical flow method

2 運動目標(biāo)的跟蹤算法

運動目標(biāo)跟蹤算法模型如圖2，虛線框中的動態(tài)選擇模型包括目標(biāo)模型(ⅰ)、隨機采樣模型(ⅱ)及一致性約束條件(ⅲ). 其中，目標(biāo)模型為描述目標(biāo)的特征點的集合，這些特征點決定了跟蹤的目標(biāo)所在的區(qū)域;隨機采樣模型為目標(biāo)區(qū)域隨機采樣獲得的點，這些點將作為候選的描述目標(biāo)的特征點;一致性約束為運動目標(biāo)區(qū)域內(nèi)各點所具有的空間相關(guān)性，運動中目標(biāo)區(qū)域的點具有速度和方向上的一致性，如線性運動的各點具有等速同向規(guī)律，旋轉(zhuǎn)運動的各點具有等速異向規(guī)律等. 因此，可通過一致性約束來判斷在場景變化或目標(biāo)變化中不一致的特征點.

圖2 運動目標(biāo)跟蹤算法模型Fig.2 Algorithm model of moving target tracking

本研究利用動態(tài)選擇模型進(jìn)行目標(biāo)跟蹤. 首先，模塊ⅰ計算當(dāng)前幀特征點在下一幀的對應(yīng)點，模塊ⅲ在當(dāng)前幀目標(biāo)區(qū)域隨機采樣特征點并計算其在下一幀的對應(yīng)點;然后，模塊ⅱ對模塊ⅰ獲得的對應(yīng)點進(jìn)行一致性約束評估，獲得一致性約束條件;其次，模塊ⅰ和ⅲ中符合一致性約束條件的對應(yīng)點選為特征點;最后，將模塊ⅲ中的特征點加入到模塊ⅰ中.

2.1 動態(tài)選擇模型

在相鄰兩幀之間，若目標(biāo)區(qū)域的某點的特征具有唯一性，則說明該點穩(wěn)定性好，可作為描述目標(biāo)的特征點. 目標(biāo)模型主要用于選擇目標(biāo)的特征點以保持特征的穩(wěn)定性. 假設(shè)初始化目標(biāo)方框，目標(biāo)模型在目標(biāo)方框內(nèi)初始一組特征點集N，N(t)為隨時間t 變化的特征點數(shù). 利用中值法［14］預(yù)測下一幀目標(biāo)方框區(qū)域.

中值法預(yù)測目標(biāo)方框的計算過程如下:假設(shè)當(dāng)前幀的特征點集為B = {b1，b2，…，bn}，對應(yīng)的前一幀的特征點集為A = {a1，a2，…，an}，則:①計算各特征點坐標(biāo)的水平偏移量為{dx1，dx2，…，dxn}，垂直偏移量為{dy1，dy2，…，dyn}，分別取數(shù)列{dx1，dx2，…，dxn}和{dy1，dy2，…，dyn}的中值可得目標(biāo)方框的位移. ②計算A 中各點兩兩之間的歐式距離{da1，da2，…，dan}和B 中各點兩兩之間的歐式距離{db1，db2，…，dbm}，然后取數(shù)列{db1/da1，db2/da2，…，dbm/dam}的中值可得目標(biāo)方框的縮放比例. 經(jīng)上述兩次中值法可預(yù)測下一幀的目標(biāo)方框.

圖3 是一個人影很明顯的行人實例(predestrian2)，其特征點數(shù)量N(t)隨時間t 的變化明顯衰減:第1 幀初始化100 個特征點，剛開始在第2 幀保持100 個特征點，到第6 幀時許多不穩(wěn)定點被丟失，在第36 幀發(fā)生遮擋后特征點數(shù)剩13 個，至第64 幀特征點數(shù)只剩6 個，最后隨著目標(biāo)的運動變化特征點全部丟失，跟蹤失敗.

圖3 實例(pedestrian2)特征點的衰減情況Fig.3 The attenuation of feature points in the pedestrian2 video sequence

圖4 給出了5 個跟蹤實例［13］的特征點數(shù)N(t)隨時間t 的變化情況. 由圖4 可見，在時間范圍Δt內(nèi)，N(t)值變化很小. 此時的特征點可描述運動目標(biāo)的特征. 我們稱在Δt 時間內(nèi)的特征點集具有穩(wěn)定性. 但當(dāng)t ＞Δt 時，N(t)值逐步減少，此時特征點集作為描述運動目標(biāo)特征的可靠性降低，易致跟蹤失敗.

圖4 5 個特征點集實例隨時間衰減情況Fig.4 The attenuation of feature points in 5 video sequences

為解決特征點集衰減問題，本研究增加了隨機采樣模型. 首先在目標(biāo)區(qū)域內(nèi)隨機選擇100 個像素點，這些像素點與目標(biāo)模型特征點不重復(fù)，根據(jù)光流法可計算這100 個像素點在下一幀的對應(yīng)點，并把這些對應(yīng)點作為隨機采樣模型獲取的目標(biāo)特征點. 當(dāng)目標(biāo)特征點數(shù)量N(t)值逐步減少至臨界值時，從隨機特征點集中選取新的特征點放入模型，并增大N(t)值以保持特征點集的穩(wěn)定性. 圖5 顯示了單獨的目標(biāo)模型和本研究提出的聯(lián)合了隨機采樣模型的目標(biāo)模型，在目標(biāo)跟蹤中特征點集的變化情況. 從第28 幀開始，在只采用單獨的目標(biāo)模型的情況下，運動目標(biāo)遇到部分遮擋，特征點數(shù)量急劇下降，第40 幀以后部分遮擋的情況消失，而采用本研究提出的聯(lián)合了隨機采用模型的目標(biāo)模型后，由于不斷獲得新的特征點，繼續(xù)保持跟蹤目標(biāo)的穩(wěn)定性.

圖6 給出一個室內(nèi)明暗變化環(huán)境下跟蹤行人時特征點集變化的對比實例. 其中，上2 組為單個目標(biāo)模型特征點;下2 組為目標(biāo)模型聯(lián)合隨機采樣模型的特征點. 通過采樣添加新的特征點，目標(biāo)模型特征點的分布將逐步趨于臉部的輪廓、眼睛、鼻子和嘴巴等邊緣，呈現(xiàn)與目標(biāo)特征相關(guān)的規(guī)律，此時模型動態(tài)選擇的特征點趨于更穩(wěn)定.

2.2 特征點的一致性約束

一致性約束作為動態(tài)選擇模型的一部分，有必要對其進(jìn)一步說明:實時跟蹤的目標(biāo)運動形式可能是剛體運動、局部非剛體運動、高速運動、變速運動或兼有各種情況的體操運動［12］. 因此，分析目標(biāo)的運動速度和運動方向有利于實現(xiàn)跟蹤的魯棒性，特別是當(dāng)目標(biāo)出現(xiàn)部分遮擋或者高速運動的情況時.

圖5 實例car 特征點數(shù)量變化比較Fig.5 Comparison of feature points in car video sequence

圖6 暗場景臉部跟蹤中特征點的穩(wěn)定性對比Fig.6 The stability of the feature points in low light

對同一個運動目標(biāo)，假設(shè)視頻跟蹤的相鄰兩幀之間的時間是連續(xù)的，即目標(biāo)的運動變化很小，則運動具有空間一致性，目標(biāo)各特征點間具有位移和方向的一致性. 如圖7 的變速情況，為運動目標(biāo)分別沿x 軸和y 軸的位移. 從圖7 可見，實例car 的運動變化較小，實例motocross 的運動變化劇烈. 由空間一致性可知，運動目標(biāo)的速度即幀間的位移大小也具有一致性. 具體步驟為:①由歐式距離計算下一幀目標(biāo)模型點的位移大小并統(tǒng)計概率;②分析概率分布的特征得出位移大小的臨界值;③根據(jù)空間一致性約束篩選下一幀目標(biāo)模型中的特征點和隨機采樣的新特征點.

圖7 x 軸與y 軸方向上兩個目標(biāo)的運動軌跡Fig.7 The trajectory of two objects in the x-axis and y-axis

如圖8，模型特征點集位移大小的概率分析為:設(shè)目標(biāo)模型特征點數(shù)量為n，{x1，x2，…，xn}為各特征點的位移統(tǒng)計量，統(tǒng)計位移概率P(xk)，(0 ≤xk＜+ ∞，k = 1，2，…，n)，則概率分布函數(shù)為

其中，E = 3 為位移偏差;p(xi)為最大概率值. 當(dāng)F(x)≥0.5 時，xi為模型特征點的位移臨界值.

圖8 柱形特征點位移的概率分析Fig.8 Probability analysis in displacement of feature points

圖9 為視頻car，目標(biāo)小汽車經(jīng)過遮擋物的情況. 當(dāng)遮擋物與目標(biāo)運動產(chǎn)生相對運動時，即產(chǎn)生運動方向的不一致性. 本研究采用運動方向的一致性約束，能及時剔除目標(biāo)模型中偏離穩(wěn)定性的特征點，并約束新添加的采樣特征點. 其算法步驟與位移一致性類似:①計算下一幀的目標(biāo)模型各個特征點相對于當(dāng)前幀的目標(biāo)模型特征點所在的方向(正東、東南、正南、西南、正西、西北、正北和東北)，然后統(tǒng)計這8 個方向上各方向的概率;②分析概率分布的特征得出下一幀的運動方向;③根據(jù)方向一致性約束篩選下一幀目標(biāo)模型中的特征點和隨機采用的新特征點.

圖9 實例(car)特征點方向分析Fig.9 Direction analysis in feature points of car video sequence

模型特征點運動方向的概率分析如下:設(shè)目標(biāo)模型特征點數(shù)量為n，{y1，y2，…，yn}為各特征點的方向統(tǒng)計量，統(tǒng)計方向概率P(yk)，(yk= 1，2，…，8，k = 1，2，…，n)，則概率分布函數(shù)為

其中，E = 1 為方向偏差;p(yi)為最大概率值. 當(dāng)F(y)≥0.5 時，yi為模型特征點的運動方向，目標(biāo)做線性運動;否則，目標(biāo)做非線性運動.

一致性約束能使描述目標(biāo)的特征點隨目標(biāo)的改變而變化，從而保持目標(biāo)模型的穩(wěn)定性.

3 實驗結(jié)果及分析

本研究的實驗數(shù)據(jù)均出自文獻(xiàn)［13］，包括多種不同情況的實例視頻，并按15 幀/秒的速率轉(zhuǎn)化為320 ×240 的灰度圖像序列處理. 本研究提出的動態(tài)選擇模型跟蹤算法通過學(xué)習(xí)特征點的穩(wěn)定性進(jìn)行運動目標(biāo)的實時跟蹤. 本實驗中，首先用隨機采樣模型初始化目標(biāo)模型. 在第1 幀中隨機采樣，選取目標(biāo)區(qū)域中的100 個像素，利用Lucase-Kanade 光流法得到第2 幀的對應(yīng)點，再根據(jù)一致性約束條件獲得符合要求的對應(yīng)點作為特征點(位移的臨界值范圍采用E = ±3)，此時這些特征點作為目標(biāo)的特征描述用來初始化目標(biāo)模型. 然后隨機采樣模型繼續(xù)采樣100 個像素，并行計算隨機采樣點和目標(biāo)模型特征點在下一幀的對應(yīng)點. 從目標(biāo)模型特征點在下一幀的對應(yīng)點中得到一致性約束條件，通過這些一致性約束條件剔除目標(biāo)模型在下一幀中不穩(wěn)定的特征點，同時用此一致性約束條件篩選隨機采樣點在下一幀中的對應(yīng)點. 當(dāng)目標(biāo)模型中穩(wěn)定的特征點的數(shù)量減少時，篩選過的隨機采樣點作為目標(biāo)特征點加入目標(biāo)模型，維持目標(biāo)模型特征點的數(shù)量在一個峰值上. 如圖10，實例motocross 跟蹤過程有效特征點數(shù)N 最大達(dá)92，這也是本實驗初始設(shè)置采樣點為100 的原因. 另外，如實例motocross 和pedestrian2，N 最小為8，當(dāng)N ＜8 時，特征點不足以描述目標(biāo)，因此目標(biāo)跟蹤失敗.

圖10 目標(biāo)模型特征點數(shù)峰值分析Fig.10 Peak analysis in object model

采用本研究提出的算法(model)和具有代表性的3 種算法［14］，包括FB (forward-backward)、NCC (normalized cross correlation)、FB + NCC 分別進(jìn)行跟蹤實驗，并進(jìn)行對比，結(jié)果如表1. 其中，7個實例分別為①低速行駛穿過部分遮擋物的汽車(car);②室內(nèi)亮度變化的行人(david);③劇烈晃動的跳繩運動(jumping)，④身體有遮擋的并行路人(predestrian1);⑤人影很明顯的行人(predestrian2);⑥背景和衣色紋理相似的行人(predestrian3);⑦高速運動中的越野摩托(motocross).

表1 FB，NCC，F(xiàn)B+NCC 算法與本研究算法在有效跟蹤上的幀數(shù)對比Table 1 Comparison with approaches (FB，NCC，F(xiàn)B+NCC)in terms of the numbers of correctly tracked frames

由表1 可見，在大部分低速運動的實例(car、david 和pedestrian2)中，幾種算法都能獲得較多的連續(xù)跟蹤，對部分遮擋情況都有很好的適應(yīng)性，但當(dāng)遮擋面積占目標(biāo)比例變大時，如實例car 中，F(xiàn)B+NCC 算法最早跟蹤失敗. 其次，如實例motocross這種高速變速運動，F(xiàn)B、NCC 和FB +NCC 等算法因無法快速適應(yīng)變化的特征點，導(dǎo)致跟蹤失敗. 本研究提出的模型算法能較好地適應(yīng)該情況，獲得良好的跟蹤效果. 最后，圖11 給出本算法在時間效率上的情況，圖中可知本算法的平均耗時優(yōu)于FB+NCC 算法，有較高的實時性.

圖11 本算法和FB+NCC 算法目標(biāo)跟蹤效率比較Fig.11 Comparison with FB+NCC on the time efficiency

結(jié) 語

為能實時平穩(wěn)跟蹤動態(tài)目標(biāo)，提出一種基于光流法的目標(biāo)跟蹤算法. 該算法通過實時學(xué)習(xí)目標(biāo)的特征點，而這些特征點在一定時間范圍內(nèi)具有穩(wěn)定描述目標(biāo)特征的特性，即在面臨光照變化、目標(biāo)形變、部分遮擋、變速運動、尺度縮放、旋轉(zhuǎn)、圖片噪音和模糊等因素的情況下仍能有效表達(dá)目標(biāo)特征，從而找出具備一致性約束的特征點進(jìn)行跟蹤并獲得目標(biāo)的運動軌跡. 較之現(xiàn)有流行目標(biāo)跟蹤算法，該算法具有目標(biāo)跟蹤的穩(wěn)定性，即不易跟丟目標(biāo)，同時該算法耗時相對較少，實時性較高. 不過，和其他算法類似，該算法在實時跟蹤的目標(biāo)消失或完全遮擋情況下，需重新檢測目標(biāo)，才能繼續(xù)跟蹤. 下一步，我們將結(jié)合目標(biāo)檢測的算法，處理目標(biāo)消失和完全遮擋后繼續(xù)跟蹤的情況.

/ References:

［1］HuuGiao Nguyen，F(xiàn)ablet R，Ehrhold A，et al. Keypoint-based analysis of sonar images:application to seabed recognition ［J］. IEEE Transactions on Geoscience and Remote Sensing，2012，50(4):1171-1184.

［2］Ren C X，Dai D Q，Yan H. Coupled kernel embedding for low-resolution face image recognition ［J］. IEEE Transactions on Image Processing，2012，21(8):3770-3783.

［3］Yilmaz A，Javed O，Shah M. Object tracking:a survey［J］. ACM Computer Surveys，2006，38(4):1-45.

［4］Qiao Y，Wang W，Minematsu N，et al. A theory of phase singularities for image representation and its applications to object tracking and image matching ［J］. IEEE Transactions on Image Processing，2009，18(10):2153-2166.

［5］Khan Z H，Gu I Y H. Joint feature correspondences and appearance similarity for robust visual object tracking［J］. IEEE Transactions on Information Forensics and Security，2010，5(3):591-606.

［6］Sun L，Liu G Z. Visual object tracking based on combination of local description and global representation ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2011，21(4):408-420.

［7］Lowe D G. Distinctive image features from scale-invariant key points ［J］. International Journal Computer Vision，2004，60(2):91-110.

［8］Pan P，Schonfeld D. Video tracking based on sequential particle filtering on graphs ［J］. IEEE Transactions on Image Processing，2011，20(6):1641-1651.

［9］Fernando W S P，Udawatta L，Pathirana P N. Identification of moving obstacles with Pyramidal Lucas Kanade optical flow and k means clustering ［C］// Proceedings of 3rd International Conference on Information and Automation for Sustainability. Melbourne (Australia): IEEE Press，2007:111-117.

［10］Siong L Y，Mokri S S，Hussain A，et al. Motion detection using Lucas Kanade algorithm and application enhancement ［C］// International Conference on Electrical Engineering and Informatics. Bangi (Malaysia):IEEE Press，2009，2:537-542.

［11］Pyda B，Brindha R. A novel high speed L-K based optical flow computation ［C］// International Conference on Communication and Computational Intelligence.Erode(India):IEEE Press，2010，2:104-108.

［12］Kovashka A，Grauman K. Learning a hierarchy of discriminative space-time neighborhood features for human action recognition ［C］// Conference on Computer Vision and Pattern Recognition. San Francisco (USA):IEEE Press，2010，2:2046-2053.

［13］Yu Q，Dinh T，Medioni G. Online tracking and reacquisition using co-trained generative and discriminative trackers ［J］. Lecture Notes in Computer Science，2008:678-691.

［14］ Kalal Z，Mikolajczyk K，Matas J. Forward-backward error:automatic detection of tracking failures ［C］// The 20th International Conference on Pattern Recognition.Istanbul (Turkey ): Springers Press，2010:2756-2759.