多層時空切片聯合的快速人體跟蹤算法

楊景景 蘇小紅 馬培軍

(哈爾濱工業大學計算機科學與技術學院 哈爾濱 150001)

1 引言

人體跟蹤一直是目標跟蹤領域中一個具有挑戰性的研究課題。許多計算機應用技術的實現都依賴于準確的人體跟蹤結果，例如行為理解、安全監控和智能交通系統等。目前主要的人體跟蹤方法有基于特征點的跟蹤方法、基于剪影的跟蹤方法和基于區域的跟蹤方法[1]。

基于特征點的跟蹤算法[2]使用多個特征點表示人體目標，通過找到最優的多特征點的關聯關系實現人體跟蹤。這種方法無需建立目標模型，計算相對簡單，但是不能提供準確的目標區域信息，因此不能適于實際人體跟蹤的要求。與之相反，基于剪影的跟蹤算法[3]通過輪廓進化或形狀匹配的方法能夠跟蹤出精確的人體輪廓，但是相應地該類算法需要建立復雜的目標輪廓模型，模型需要大量的初始化和訓練，不能適用于實時的人體跟蹤要求。

基于區域的跟蹤算法是以上兩類算法在區域準確率和計算復雜度上的一個平衡，是目前應用比較廣泛的一類人體跟蹤算法，該類算法一般使用模板和密度外觀模型來表示人體區域。其中比較經典的有均值漂移算法和粒子濾波算法等。均值漂移算法[4]采用取自圓形區域內的加權顏色直方圖表示目標，并通過計算均值漂移偏移量來估計目標下一時刻的位置來實現跟蹤。粒子濾波器算法[5]通過多個加權粒子的形式建立目標概率密度方程，采用非參數化的方法實現目標狀態空間估計，可以解決非線性、非高斯分布問題，具有更廣泛的應用性和魯棒性。此外，多模型粒子濾波算法[6]、粒子概率密度假設濾波器[7]、高斯粒子聯合概率數據關聯濾波算法[8]和準蒙特卡羅濾波算法[9]等也相繼提出以解決復雜環境下的機動多目標跟蹤問題。

基于區域的跟蹤算法仍然在一定程度上依賴于準確的目標外觀模型，并且需要對模型進行初始化和訓練，增加了算法的計算量。針對以上問題，本文提出無目標模型的多區域聯合的人體跟蹤算法，在保證區域跟蹤準確率的前提下降低跟蹤所需的計算量。本文利用時空切片[10]的方法，將人體表示為在不同時空切片圖像中的多個區域(本文稱為切片)的組合，切片無需使用任何預定義的目標模型。首先，在各時空切片圖像中通過最小化一個改進的目標映射代價方程，確立人體切片間的映射關系，實現人體切片的跟蹤。然后，根據人體的不同切片運動和空間一致性，使用聚類算法組合人體的多個切片的跟蹤結果，重構人體輪廓，進而實現整個人體的跟蹤。

2 時空切片方法的引入

假設視頻是一個?(x,y,t)的3維圖像序列，其中(x,y)為圖像維，t為時間維。那么一個水平時空切片圖像就是固定y坐標后連續地從一個視頻中提取相同位置的一行像素點組合得到的一個?(x,y=yk,t)2維圖像。設切片圖像?0源自原始視頻中y=y0的區域，則圖像?0中t=ti行對應的是原始視頻中t=ti幀(實際對應t=ti幀圖像中y=y0的那一行像素)。

如果將人體近似地看成是一個垂直的“條形”剛體目標，則當人體在視頻中運動時，人體在不同時空切片圖像中生成的人體切片不僅具有相同的水平坐標，而且也具有一致的運動模式[11]。圖1顯示的是人體在4個不同水平時空切片圖像中的軌跡對比。

如果將視頻?(x,y,t)中第i幀的第j個人體表示成一個2維函數(x,y)的形式，γ既可代表一片區域也可代表一段輪廓。傳統的人體跟蹤問題實際上就是在圖像序列中連續尋找一個γ人體序列的問題，可表示為

圖1 在y = 160, 150, 140, 130時的水平時空切片圖像

本文引入時空切片方法，將原始的?(x,y,t)圖像序列分割成水平時空切片圖像的集合，即

其中n表示時空切片的切分數目，且yk+1＞yk。相應地，視頻中的每個2維(x,y)人體也被分割成人體切片的集合，形如

其中(x,y=y)表示位于時空切片圖像?(x,y

k=yk,t)中的人體切片；x的取值范圍可以為空，表示該時空切片圖像中沒有對應j人體的人體切片。

這樣，人體跟蹤就由尋找γ人體序列變成尋找人體切片集合的序列，即

其中人體切片序列

在對應的時空切片圖像?(x,y=yk,t)中使用本文提出的目標映射算法實現。

3 人體切片的檢測與跟蹤

在時空切片圖像中，人體切片是一個區別于背景的，分布在某一x區間內的多個像素點的集合。人體切片在圖像中所占的區域一般較小，但是又與純粹的點目標不同，它還包含一定的形狀、顏色和紋理等信息。因此針對這一特點，對時空切片圖像?(x,y=y,t)中的第i行的第j個人體切片γi，本

kj文使用下式來描述人體切片：

3.1 人體切片檢測

如果將時空切片圖像看成是一個在時間域上的“行”序列，那么參照視頻幀圖像序列中的前景和背景定義，“行”就相當于序列中的“幀圖像”，而人體切片就相當于“幀圖像”中的前景目標。因此，本文使用如下所示的混合高斯背景模型對時空切片圖像中的“行”進行建模，進而檢測人體切片。

其中wj為第j個高斯成分的權重系數；η(xN;θj)表示第j個成分的正態分布。對不同y取值的時空切片圖像，算法都需要訓練一個高斯背景模型。

值得注意的是，由于時空切片圖像中的“行”僅包含有限的顏色信息，為了提高檢測準確率和獲得更豐富的顏色信息，本文在高斯背景建模及顏色直方圖提取時，在當前行的相鄰m行鄰域內進行特征提取(實驗中m=5)。

3.2 人體切片跟蹤

人體切片的跟蹤實際上就是建立多個切片目標之間的一對一映射的問題。本文通過最小化目標映射代價方程來確立多個切片目標之間的映射關系。為了提高映射準確率，在現有的幾何約束代價方程的基礎上，本文提出新的顏色直方圖相似性約束，并使用以下兩種約束的組合來計算目標映射代價。

(1)最近一致的幾何約束[12]。本約束假設目標始終沿著一條最近一致的路徑運動。也就是說，如果幀間的時間間隔足夠小，那么可以認為人體切片在下一時刻將始終停留在離前一時刻最近的位置上，而且它們的運動方向和速度都不會發生大的變化。

其中，m和l分別是第(k-1)行和第(k+1)行中的人體切片個數；1≤p≤m, 1≤r≤l。

(2)顏色直方圖相似性約束。不同于純粹的點目標，人體切片還包含一定的顏色信息。因此，為了進一步提高映射準確率，本文在前一約束基礎上增加一種新的顏色直方圖相似性約束，對目標進行顏色直方圖相似性判斷。其中直方圖相似性使用巴氏距離定義。

其中m,l,p和r的定義同式(9)；u表示顏色直方圖的灰度級分量，h表示直方圖的灰度級。

由以上兩個約束方程組合計算得到最終的目標映射代價函數φ如下：

其中λ和β分別是以上兩種約束的權重系數，且λ+β= 1 。實驗發現，幾何約束對映射準確率的影響要大于顏色直方圖相似性約束，因此λ＞β；并且β取值過大或過小時，映射準確率都較低。實際上，λ取0.6～0.7,β取0.3～0.4時，準確率比較理想。本文中，λ=0.6。使用非遞歸的貪心搜索算法最小化∑φ求得其中可能的一個最優解。

4 人體切片的聚類與重構

基于人體切片運動與空間一致性，建立人體切片到候選人體目標的隸屬關系，將人體切片集合劃分為多個人體類，然后在此基礎上重構相應的人體區域信息，實現人體切片到完整人體的組合跟蹤。

4.1 人體切片聚類

圖 2顯示的是包含兩個運動人體的人體切片LTR分布圖。其中不同的坐標點代表不同的人體切片。圖中的坐標點自然聚集為兩個區域，每個區域代表一個人體。其中同一人體內的坐標點，分布集中，具有較小的類內距離；而不同人體間的坐標點，距離較遠，具有較大的類間距離。由于聚類使用的是與尺度無關的切片中心x坐標及運動參數等信息，算法具有處理一定尺度變化范圍內的不同人體聚類的能力。而在實際視頻監控環境中，由場景遠近帶來的人體尺度變化是有限的，因此本文算法能夠滿足實際監控環境的跟蹤需要。本文使用層次聚類方法在LTR3維空間中進行人體切片聚類，并使用歐氏距離表示切片間的距離度量。由于未知聚類數目，根據層次聚類的類間距離來判定聚類終止條件。

4.2 人體輪廓重構

步驟 1 對集合內的所有人體切片，按各切片y坐標的升序對進行排序；

5 實驗結果和分析

本文采用 CAVIAR視頻對算法進行測試，其中，CAVIAR視頻分辨率384×288，幀率25 fps，分別采自架設在監控區域正面和拐角的兩個攝像頭。實驗中，視頻取64個時空切片圖像[13]。

5.1軌跡誤差以及魯棒性分析

圖3(a)和圖3(b)是兩個視頻的人體跟蹤軌跡與真實軌跡的對比，其中加號軌跡代表真實軌跡，點狀軌跡代表算法估計軌跡。圖 3(a)對應的視頻Video1僅包含一個人體目標，而圖3(b)對應的視頻Video2則包含多個人體目標。圖3(c), 3(d)分別顯示的是圖 3(a)和圖 3(b)兩段視頻的軌跡誤差曲線(以像素為單位)。從圖中可以看出，在某些幀，由于復雜背景干擾造成的切片丟失及檢測誤差，導致估計區域大于或小于真實區域，進而區域中心點坐標出現偏差，軌跡誤差增大。但總體來說，其軌跡誤差依然保持在較低的水平上，平均軌跡誤差分別為2.389像素和5.27像素。值得注意的是，圖3(c)中的軌跡誤差遞增現象是由 Video1人體目標面向鏡頭行走造成尺寸遞增而引起的，算法本身沒有跟蹤迭代或者累加的過程。

由于復雜背景干擾而引起人體的部分切片丟失，使算法在某些幀內跟蹤到的只是人體的部分區域，在結果上表現為跟蹤的人體的中心點發生微小變化，導致跟蹤的軌跡是一條圍繞著真實軌跡上下擾動的曲線，平均每幀的軌跡誤差變化并不明顯，從而使其相對于其他跟蹤算法而言對環境干擾具有更強的魯棒性。

圖2 包含兩個行人的視頻中人體切片LTR分布示意圖

圖3 Video1和Video2人體跟蹤軌跡及軌跡誤差

圖4 不同切片丟失情況下的人體區域跟蹤結果

圖4顯示的是不同切片丟失情況下的人體區域跟蹤結果。從圖4結果可以看出，本文的跟蹤算法對環境干擾引起的人體切片丟失具有一定的魯棒性。具體地講，如圖4(b)，位于人體內部的軀干切片的丟失不會對人體區域的大小和位置產生任何影響，因而不會影響軌跡誤差。而腿部切片和頭部切片對生成最終的人體區域的影響相對較大。其中，當某幀中的切片丟失數量較少(如圖 4(c)所示)時對軌跡誤差的影響在誤差范圍內可以忽略不計，當某幀中的切片數量丟失較多(如圖 4(d)所示)時，會對當前幀的軌跡誤差產生一定的影響，但由于每一幀檢測的切片數量是變化的，切片丟失的情況僅在個別幀中出現，因此個別幀中切片的丟失對平均每幀軌跡誤差影響不大。

5.2 與其他方法的對比

為了驗證本文提出的跟蹤算法的有效性，與現有的其他目標跟蹤方法如 MS[4], MSPF[14],CCMSPF[15]和MSFG[16]進行了對比。

表1顯示的是CAVIAR數據庫中4個視頻的平均軌跡誤差、運行時間、查準率和查全率[1]的對比結果，其中查準率和查全率用于驗證估計區域的準確性。從表1都可以看出，本文跟蹤算法的平均軌跡誤差均低于CCMPF, MS, MSFG和MSPF算法；在平均運行時間上，本文跟蹤算法與CCMSPF, MS和MSFG算法接近，遠優于MSPF算法；查全率明顯優于其他算法，查準率與其他算法接近，其中平均查準率為 93.33%，而平均查全率為 60.62%。平均查全率較低的原因是：本文算法提取的是人體輪廓，而真實值給定的是人體邊界盒矩形區域。如圖5所示，輪廓剪影區域為本文跟蹤結果，而矩形框區域為真實結果。本文的人體輪廓能更精確地描述目標形狀，這也是論文的一個優勢，但是該輪廓始終位于邊界盒的內部，自然造成查全率較低，而查準率則會較高。而其他算法由于采用位于目標內部的橢圓模型來表示目標區域，造成查全率也普遍較低。

6 結束語

本文采用多層時空切片方法，將傳統的XYT3維空間上的人體跟蹤問題轉化為多個XT2維空間中的人體切片聯合跟蹤問題。使用多個人體切片的聯合來表示人體目標，無需初始化和訓練人體目標模型。實驗結果表明，本文算法在軌跡誤差上優于傳統跟蹤算法，滿足實時性視頻處理要求，并且對于由于環境干擾引起的人體區域丟失具有一定的魯棒性?，F階段本文僅使用運動和顏色特征進行跟蹤，并且特征提取也是在當前幀的切片較小鄰域內進行，信息量不夠豐富，不能處理較大尺度變化場景下的人體跟蹤。為了進一步提高跟蹤準確率和魯棒性、解決尺度變化問題，在下一步的研究工作中考慮結合連續多幀的切片區域，在其基礎上提取更豐富的顏色、梯度或紋理特征用于跟蹤。

圖5 部分人體跟蹤結果(輪廓剪影為本文估計區域，矩形框為真實區域)

表1 Video1-Video4實驗對比結果

[1]Yilmaz A, Javed O, and Shah M. Object tracking: a survey[J].ACM Computing Surveys, 2006, 38(4): 13-58.

[2]Vidal R and Ma Y. A unified algebraic approach to 2-d and 3-d motion segmentation[C]. European Conference on Computer Vision, Prague, Czech, 2004: 1-15.

[3]Yilmaz A, Li X, and Shah M. Contour based object tracking with occlusion handling in video acquired using mobile cameras[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(11): 1531-1536.

[4]Comaniciu D, Ramesh V, and Meer P. Kernel-based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-575.

[5]Isard M and MacCormick J. BraMBLe: a Bayesian multipleblob tracker[C]. IEEE International Conference on Computer Vision, Vancouver, Canada, 2001, 2: 34-41.

[6]鑒福升, 徐躍民, 陰澤杰. 多模型粒子濾波跟蹤算法研究[J].電子與信息學報, 2010, 32(6): 1271-1276.

Jian Fu-sheng, Xu Yue-min, and Yin Ze-jie. Research of multiple model particle filter tracking algorithms[J].Journal of Electronics&Information Technology, 2010, 32(6):1271-1276.

[7]連峰, 韓崇昭, 劉偉峰, 等. 基于 SMC-PHDF 的部分可分辨的群目標跟蹤算法[J]. 自動化學報, 2010, 36(5): 731-741.

Lian Feng, Han Chong-zhao, Liu Wei-feng,et al.. Tracking partly resolvable group targets using SMC-PHDF[J].Acta Automatica Sinica, 2010, 36(5): 731-741.

[8]張俊根, 姬紅兵, 蔡紹曉. 基于高斯粒子JPDA濾波的多目標跟蹤算法[J]. 電子與信息學報, 2010, 32(11): 2686-2690.

Zhang Jun-gen, Ji Hong-bing, and Cai Shao-xiao. Gaussian particle JPDA filter based multi-target tracking[J].Journal of Electronics&Information Technology, 2010, 32(11):2686-2690.

[9]趙玲玲, 馬培軍, 蘇小紅. 一種快速準蒙特卡羅粒子濾波算法[J]. 自動化學報, 2010, 36(9): 1351-1356.

Zhao Ling-ling, Ma Pei-jun, and Su Xiao-hong. A fast quasi-Monte Carlo-based particle filter algorithm[J].ActaAutomatica Sinica, 2010, 36(9): 1351-1356.

[10]Adelson E H and Bergen J R. Spatiotemporal energy models for the perception of motion[J].Journal of the Optical Society of America A, 1985, 2(2): 284-299.

[11]楊景景, 蘇小紅, 馬培軍. 基于時空切片軌跡分析的復雜人體運動跟蹤[J]. 信號處理, 2012, 28(2): 246-256.

Yang Jing-jing, Su Xiao-hong, and Ma Pei-jun. Complex human motion tracking based on spatio-temporal slice trajectory analysis[J].Signal Processing, 2012, 28(2):246-256.

[12]Shafique K and Shah M. A non-iterative greedy algorithm for multi-frame point correspondence[C]. IEEE International Conference on Computer Vision, Nice, France, 2003: 110-115.

[13]Yang J, Su X, and Ma P. Fast pedestrian detection using slice- based motion analysis[C]. International Conference on Pervasive Computing, Signal Processing and Applications,Harbin, China, 2010: 74-77.

[14]Zhang B, Tian W, and Jin Z. Joint tracking algorithm using particle filter and mean shift with target model updating[J].ChineseOptics Letters, 2006, 4(10): 569-572.

[15]Silva D D, Cesar R M, Vieira M B,et al.. Tracking and matching connected components from 3D video[C]. Brazilian Symposium on Computer Graphics and Image Processing,Nstal, Brazil, 2005: 257-264.

[16]Li L, Huang W, Gu I Y H,et al.. Statistical modeling of complex backgrounds for foreground object detection[J].IEEE Transactions on Image Process, 2004, 13(11):1459-1472.