基于目標檢測和圖割的多目標跟蹤算法

姜明新，王洪玉，邱天爽

（1.大連理工大學 電子信息與電氣工程學部，遼寧 大連 116024；2.大連民族學院 信息與通信工程學院，遼寧 大連 116600）

0 引 言

多目標跟蹤是計算機視覺領域的一個熱點研究問題，是運動目標行為理解的前提和基礎，在機器人導航、視頻理解、智能監控等領域都有著廣泛的應用［1－3］.多目標跟蹤的實現存在很多難點，比如在擁擠的環境里，目標的進入和離開，目標之間的嚴重遮擋等.

近些年來，國內外許多學者關注基于視頻的多目標跟蹤問題，所提出的算法包括點跟蹤、核跟蹤和輪廓跟蹤三大類.

點跟蹤也稱為基于檢測的跟蹤，利用有效的技術將運動目標檢測出來，然后再進行跟蹤.跟蹤部分的實現可以分為確定性方法和概率方法.確定性方法是利用目標和觀測之間某種特征的距離來實現跟蹤，特征通常選用位置、顏色、形狀等.由于目標檢測獲得的觀測常常含有噪聲，概率方法考慮了這些不確定性因素，所以得到了更為普遍的應用，比如卡爾曼濾波［4］、粒子濾波［5］等技術.點跟蹤能夠處理新目標的進入和原有目標的離開，但檢測的質量直接影響跟蹤的結果，只能用矩形框、橢圓等來描述跟蹤的結果，無法準確地描述出目標的輪廓.

核跟蹤也稱為基于分布的跟蹤，跟蹤之前手動選擇參考目標，利用當前幀和參考幀的一些特征分布來實現跟蹤.較為常見的方法有KLT特征點跟蹤算法［6］和 Comaniciu等提出的meanshift跟蹤算法［7］.核跟蹤計算量小，具有較好的實時性，但無法處理目標的進入和離開，當多目標之間發生遮擋時跟蹤的失敗率較高.

輪廓跟蹤也稱為基于動態分割的跟蹤，這種方法能夠在連續的每一幀中分割多個目標，并且可以描述出每個目標的詳細輪廓.利用圖割理論［8］實現輪廓跟蹤是一種比較有效的方法，這種方法求解全局最小時不需要先獲得局部最小和全局模型的先驗知識，優化過程收斂快，計算代價低，而且能夠處理多個目標相互融合／分離（fusion／split）的拓撲變化.輪廓跟蹤的缺點是無法處理新目標的進入和原目標的離開.

通過以上對不同跟蹤方法的分析，本文提出一種基于運動目標檢測和圖割理論的多目標跟蹤算法.首先采用碼本模型進行背景建模，檢測出運動目標；然后，利用圖割理論構建網絡圖，建立能量方程；最后，利用最大流－最小割算法實現能量方程的最小化，進而實現對多目標的跟蹤.

1 運動目標檢測

碼本模型是由Kim 等［9］提出的，該算法抗干擾能力強，能夠有效地克服陰影和空洞的問題，計算復雜度小，適合做實時檢測.利用文獻［9］獲得碼本后，檢測前景似然信息的過程如下：

假設目標檢測過程中新輸入像素為xi＝（R，G，B），其對應的碼本為M.減背景操作BGS（xi）可以大致分為三步：

步驟1 計算當前像素的亮度I＝R＋G＋B，定義布爾變量match＝0，并給閾值變量ε賦值.

步驟2 根據以下兩個條件從碼本M中找出與當前像素相匹配的碼字Cm，如果能夠找到碼字Cm，則match＝1，否則，match＝0.

為了判斷前景和背景，運動目標檢測中亮度變化有一個范圍，對于每個碼字，其范圍為［Ilow，Ihi］.亮度函數的定義為

步驟3 判斷前景運動目標像素：

2 基于目標檢測和圖割的多目標跟蹤算法

圖割是圖論中一種關于網絡流的算法［10－11］，是一種基于圖論的組合優化技術，用來最小化計算機視覺中的能量函數問題.由于網絡圖相比于向量、表、堆棧等數據結構，具有表示直觀、能夠處理非線性問題等優點，因此，在計算機視覺領域中被廣泛應用.

在多目標跟蹤的領域里，可以將監控視頻圖像映射成一個網絡圖，建立一個關于目標像素標號的能量函數，通過最大流－最小割算法實現能量函數最小化，求出對應的最小割，從而給不同的像素賦予不同的標簽，實現多目標跟蹤的目的.由于圖割算法是在全局最優的框架下進行分割，可以保證能量函數的解收斂到全局最小.

假設t時刻圖像中的像素p用特征向量zt（p）來描述：

式中：zct（p）表示像素點的顏色信息，是一個YUV顏色空間的三維向量；zmt（p）表示像素點的運動信息，是一個二維的光流向量.

如果在t時刻有kt個目標被跟蹤，其中第i個目標用Oit表示，在視頻圖像中，目標可以看作是多個像素組成的模板.針對目標i來說，視頻圖像中的像素點不屬于該目標，則看作背景，用包含運動信息和顏色信息的概率分布來表示像素點屬于目標還是背景.

t時刻屬于目標i的像素點的概率分布用lit來表示，對應的特征向量為由于運動信息和顏色信息是相互獨立的，lit可以分解為lit，c（對 應的特 征向量 為（對應的特征向量為屬于目標i的像素點的概率分布lit的數學表達式為

同理，t時刻屬于背景的像素點的概率分布qit（對應的特征向量為可以表示為

目標跟蹤的任務是根據t－1時刻的目標利用圖割算法得到t時刻的目標Oit.

如果t時刻共有mt個觀測，第j個觀測用Mjt表示，Mjt也可以看作是一些像素組成的集合.假設t時刻屬于觀測j的像素點的概率分布用ρjt來表示，則ρjt的數學表達式為

假設由t－1時刻的目標Oit－1預測的t時刻的目標為P，用dit－1表示t－1時刻目標i中所有像素點光流向量的均值，即：

中的每一個像素利用平均光流向量可以預測得到t時刻的目標為：

利用t－1時刻的預測、t時刻得到的新的觀測值和目標像素的概率分布建立能量方程，通過最大流－最小割算法進行能量函數最小化，實現對多目標的跟蹤.基于圖割理論的多目標跟蹤算法流程圖如圖1所示.

圖1 基于圖割理論的多目標跟蹤算法流程圖Fig.1 Flowchart of the multi－target tracking algorithm based on graph cuts

2.1 構建網絡圖

假設t時刻的無向網絡圖為Gt＝〈Vt，Et〉，其中Vt為t時刻的點集，Et為t時刻的邊集.點集Vt由兩個子集組成：第一個子集是N個像素的集合P，第二個子集是觀測子集.每一個觀測Mjt對應一個節點njt，稱這些節點為觀測節點，因此，點集Vt＝P∪｛njt，j＝1，2，…，mt｝，邊集Et也可以分解 為想要將目標i從視頻圖像中分割出來，就意味著給圖中的每個像素p賦予標簽值fip，t，由于針對每一個目標構建一個無向網絡圖，fip，t對于一個像素點來說不是背景就是目標.想要將觀測和目標建立起聯系，就意味著給每一個觀測節點njt賦予二值標簽fij，t.t時刻，所有的節點標簽值組成一個標簽值集合Lit.

多目標跟蹤算法的無向網絡圖如圖2所示.圖2（a）表示t－1時刻能量最小化的結果，其中白色節點的標簽值為目標，黑色節點的標簽值為背景.箭頭表示目標的光流向量.圖2（b）是t時刻關于目標i的網絡圖，圖中有兩個觀測節點n1t和n2t，用粗線圈上的像素點分別屬于這兩個觀測.虛線框住的像素點是根據上一時刻目標像素點的光流向量得到的本幀的預測值

2.2 建立能量方程

t時刻，針對目標i建立能量方程，能量方程由一元數據項和二元平滑項組成：

其中數據項為

圖2 多目標跟蹤算法的無向網絡圖Fig.2 The undirected graph of the multi－target tracking algorithm

式（12）中，利用t－1時刻的跟蹤結果得到的t時刻的預測區域的似然函數l1的表達式為

其中“ob”表示像素的標簽值為目標，“bg”表示像素的標簽值為背景.

式（12）中，d2（j，fp，t）似然函數的數學表達式為

為了估計t－1時刻的目標跟蹤結果i和t時刻的.觀測j之間的相似度，利用式（14）計算t－1時刻目標i的概率分布lit－1和t時刻觀測j的概率分布ρjt之間的距離.本文采用Kullback－Lerbler距離，簡稱KL距離

式（12）中的常數α是控制觀測對數據項的影響程度的，本文中，令α等于觀測Mjt的像素數目.

式（11）中的平滑項B｛p，q｝，t的設計基于相鄰像素｛p，q｝的顏色梯度信息，具體表達式為

其中σT＝4〈（Zct（p）－Zct（q））2〉，式中的〈·〉表示目標區域的均值.

能量方程式（11）建立后，利用α擴展法進行最小化，求得像素的標簽值，可得

則t時刻的目標i為

3 實驗結果及分析

選用多組實驗視頻進行測試，驗證本文提出的基于目標檢測和圖割的多目標跟蹤算法的魯棒性，限于篇幅，本文只列出部分實驗結果.利用Windows 7操作系統來實現多目標跟蹤算法，采用Visual Studio 2010結合OpenCV 2.2作為軟件平臺，計算機配置為Pentium（R）Dual－Core CPU 2.0GHz.

首先，需要利用運動目標檢測算法來獲得觀測值，實驗結果如圖3所示.圖3（a）和（c）表示監控視頻中任意兩幀原始視頻圖像，圖3（b）和（d）是利用碼本模型獲得的觀測值.

從圖3（d）的結果可以看出，當視頻中左側的兩個目標之間發生遮擋時，通過運動目標檢測得到的觀測是兩個目標共同組成的前景.所以，需要考慮預測信息和上一幀目標的概率分布，結合新得到的觀測，來共同構建能量方程和網絡圖.利用圖割理論進行多目標跟蹤的實驗結果如圖4所示.

圖3 利用碼本模型獲得的觀測值Fig.3 The result of the observation obtained using codebook model

在這組實驗視頻中，多個目標之間發生了相互遮擋，圖4（a）和（b）中目標1和目標3發生了遮擋，圖4（c）和（d）中目標1和目標4發生了遮擋，實驗視頻中的目標4是新進入的目標.

圖4 多目標跟蹤算法的實驗結果Fig.4 The experimental result of the multi－target tracking algorithm

為了更直觀地表示給每個像素賦予標簽值的效果，將屬于同一個目標的像素點賦予了同一種顏色，然后，再用矩形框表示跟蹤結果.從實驗結果可以看出，提出的多目標跟蹤算法，對多目標之間的遮擋和多目標的數目變化具有較強的魯棒性.

為了驗證本文提出算法在跟蹤準確率方面的優勢，針對上述實驗視頻進行了跟蹤準確率數據統計，并且與粒子濾波算法進行了對比，實驗對比數據如表1所示.

表1 跟蹤準確率對比Tab.1 The comparison of tracking accuracy

4 結 語

本文在分析各種跟蹤方法的基礎上，結合點跟蹤和輪廓跟蹤的優勢，提出了一種基于運動目標檢測和圖割理論的多目標跟蹤算法，將多目標跟蹤問題轉化為能量最小化問題，給像素賦予標簽，根據圖割理論建立能量方程，構造網絡圖，利用最大流－最小割算法實現能量方程的最小化，進而完成對多目標的跟蹤.實驗結果表明，該算法對多目標的數目變化和遮擋具有較強的魯棒性.

［1］ 姜明新，王洪玉，劉曉凱.基于多相機的多目標跟蹤算法［J］.自動化學報，2012，38（4）：497－506.JIANG Ming－xin，WANG Hong－yu，LIU Xiao－kai.A multi－target tracking algorithm based on multiple cameras［J］.Acta Automatica Sinica，2012，38（4）：497－506.（in Chinese）

［2］ Yilmaz A，Javed O，Shah M.Object tracking：A survey［J］.ACM Computing Surveys，2006，38（4）：229－240.

［3］ 姜明新，王洪玉.基于多層定位的多目標跟蹤算法［J］.大連理工大學學報，2012，52（5）：767－771.JIANG Ming－xin，WANG Hong－yu.Tracking algorithm of multi－object based on localizing at multiple planes［J］.Journal of Dalian University of Technology，2012，52（5）：767－771.（in Chinese）

［4］ HAN Zhen－jun，JIAO Jian－bin，ZHANG Baochang，etal.Visual object tracking via samplebased adaptive sparse representation ［J］.Pattern Recognition，2011，44（9）：2170－2183.

［5］ Mei X，Ling H.Robust visual tracking and vehicle classification via sparse representation ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（11）：2259－2272.

［6］ Shi J，Tomasi C.Good features to track ［C］／／Proceedings of the 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos：IEEE，1994.

［7］ Comaniciu D，Ramesh V，Meer P.Kernel－based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564－577.

［8］ Boykov Y，Veksler O，Zabih R.Fast approximate energy minimization via graph cuts ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（11）：1222－1239.

［9］ Kim K，Chalidabhongse T H，Harwood D，etal.Real－time foreground－background segmentation using codebook model ［J］.Real－Time Imaging，2005，11（3）：172－185.

［10］ Ford L R，Fulkerson D R.Flows in Networks［M］.New Jersey：Princeton University Press，1962.

［11］ Boykov Y，Kolmogorov V.An experimental comparison of min－cut／max－flow algorithms for energy minimization in vision ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（9）：1124－1137.