視頻序列中目標的檢測與跟蹤

蔡睿妍，田 全

(大連大學信息工程學院，遼寧大連116622)

目標的檢測與跟蹤涉及到人工智能、機器視覺、生物醫學、自動控制等多個學科，近年來，隨著計算機技術的發展，得到了廣泛的研究與應用［1］。目前比較流行的目標檢測算法包括幀間運動估計和背景差分的方法，幀間運動估的方法是利用圖像序列中相鄰幀圖像之間的差來提取圖像的運動區域的。該方法實現簡單，但只能檢測相對運動的目標，并且檢測出目標的位置不夠精確。背景差分法首先定義視頻圖像的特定幀為背景，然后將當前幀和背景進行差分比較，如果同位置的像素特征、像素區域特征或其他特征的差別大于選定的閾值，則當前幀中該位置的像素區域就判定為前景目標區域，反之則為背景。該方法容易受到光線亮度變化的影響［2］。基于上述原因，本文提出了一種基于時間序列的編碼建模算法，該算法能夠解決像素劇烈變化的問題，可以提高復雜背景下目標檢測的穩健性。目標的跟蹤是通過算法獲得目標在特定時間段上的運動軌跡，包括目標的產生、運動和銷毀三個過程。由于算法中涉及到幀間目標空間位置的測量，在傳統的跟蹤算法中，當目標數目增加的時候，算法的時間復雜度呈指數形式增加。本文在分析上述問題基礎上，將KD-Tree方法［3］引入目標跟蹤算法之中，降低了算法的時間復雜度，同時降低了算法對目標數目的敏感程度，實現了高精度、高效率的目標檢測與跟蹤。

1 目標檢測

很多場景都包含復雜的運動目標，諸如搖曳在風中的樹、轉動的風扇、擺動的窗簾等。通常這種場景中還有光線的變化。解決這個問題最好的方法是采用基于時間序列的編碼建模算法，對每個像素或者一組像素建立時間序列模型，在每個像素點進行抽樣，根據顏色扭曲尺度和亮度邊界聚類獲得編碼本的集合，并不是所有像素點擁有相同數量的編碼本數量。通過編碼本表示的聚類子不需要對應單個高斯分布或者其他參數的分布，因此該編碼方式是以像素為基礎的。

歸一化顏色算子是用來處理全局和局部亮度變化的方法，該技術在圖像的暗色區域效果不理想，因為顏色比率的不確定性與亮度相關，所以灰度級低的像素點相對與灰度級高的像素點不確定性更高。這些不確定性使灰度級低的區域變得不穩定，在可能聚集在低灰度級的區域造成無檢測［4］。本文通過建立顏色模型來估計顏色的亮度和扭曲，該模型依賴于編碼元素主軸界定在亮度值高低邊界的背景像素值。對于輸入像素點pixi=(B，G，R)和編碼本 ci，定義 Vi=(Bi，Gi，Ri) ，可得

由式(1)和式(2)可得

顏色扭曲度為

u2可以由式(5)求解

此外，統計地分配亮度變化的最大和最小值，將其賦給一個編碼本，在特定的范圍內限制陰影水平和焦點水平，能夠有效地適應亮度的變化。為了去除圖像中引入的噪聲，首先對目標檢測完成的圖像進行3×3的中值濾波，然后進行形態學處理，使待檢測的目標形成一個完整的連通域，并在一定程度上消除中值濾波無法消除的噪聲，最終得到比較理想的目標圖像。

不同處理階段目標檢測的結果如圖1所示。可以看到，在經過上述處理，得到了完整的目標。

圖1 目標檢測

2 目標跟蹤

目標跟蹤是建立在目標檢測的基礎上的，即確定實時視頻幀中檢測到的目標的運動軌跡，這種軌跡的建立可以通過目標特征的匹配來實現，通常采用的特征信息有目標的位置、尺度、形狀以及顏色等。本文采用目標的位置(即每個目標的質心坐標)建立運動模型，實現目標軌跡的精確匹配。

將每幀圖像檢測出的多個目標同上一幀圖像檢測出的目標進行比較并分類，主要有3種情況：1)當前目標是由上一幀中某個目標運動得到的(運動速度大于或等于0);2)當前目標在上一幀中沒有出現，是新增加的目標;3)某些目標在上一幀中出現過，但在當前幀消失了。

在跟蹤用攝像機完整標定的情況下，視場中的目標的運動速度會保持在某個區間之內，即可以通過實驗的方法確定某一類別目標的最大運動速度，因為攝像系統的幀率是一定的，所以可以確定目標在兩幀之間的時間間隔內的最大位移，定義為D_max，以此作為閾值條件。然后把上一幀的所有目標的質心坐標放在一個數組中，作為一個待遍歷的集合Vec。將當前幀的每一個目標的質心坐標在集合Vec中尋找出與之幾何距離最近的對應目標A，然后計算該距離d與D_max的關系：1)如果d≤D_max，當前幀的目標是從上一幀的目標A運動得到的;2)如果d＞D_max，當前幀的目標是新增加的目標;3)如果在上一幀的目標中存在沒有和當前幀目標相對應的，則說明沒有對應的這些目標在當前幀中消失了。

針對上述3種情況，本文采用KD-Tree算法［5］實現目標跟蹤。KD-Tree算法是一種由二叉搜索樹推廣而來的用于多維檢索的樹的結構形式(K即為空間的維數，此處定義K=2)。與二叉搜索樹不同的是，它的每個結點表示k維空間的一個點，并且每一層都根據該層的分辨器對相應對象做出分枝決策。頂層結點按由分辨器決定的一個維度進行劃分，第二層則按照該層的分辨器決定的另一個維度進行劃分，以此類推在余下各維之間不斷地劃分。直至一個結點中的點數少于給定的最大點數時，結束劃分。

如圖2 所示，在二維空間內存在點A，B，C，D，E，首先以A點的y維度為起始點，將點集分為2個部分，然后在左右2個子樹中以B點和C點的x維度將左右2個子樹分為2個部分，以此類推，在B點、C點各自的子樹當中，以D點、E點的y維度對其子樹劃分，遍歷集合當中的每一個點，就可以得到1個完整的KD-Tree。目標軌跡建立的過程就是在KD-Tree中搜索最近點的過程，采用KDTree進行最近點搜索可以提高系統的工作效率。

圖2 KD-Tree算法原理圖

算法流程如下：

1)定義目標質心點坐標存儲結構體，即

其中ID為每個目標對應的序號，x和y分別為每個目標質心坐標的橫、縱坐標值。

2)將第i幀的每個目標(定義為Blobi，其中i=1，2，3，…，N)的橫縱坐標按照Blob2D32f結構體形式進行存儲，ID號從0開始順次排列，然后存放在起始幀數組ArrayL中。

圖3 目標檢測與跟蹤流程

3)將第i+1幀的每個目標的橫縱坐標按照Blob2D32f結構體形式進行存儲，ID號不填充，然后存放在當前幀數組ArrayN中。

4)對起始幀數組ArrayL建立KD-Tree。

5)定義D_max。

6)遍歷當前幀數組ArrayN中的每個Blobi，搜索其在KD-Tree中最短距離元素，定義最短距離為d。

7)如果d＞D_max，則該Blobi為新當前幀新增加的目標，將其賦予一個新的ID;如果d≤D_max，則該Blobi為由上一幀的目標運動得到的，將其ID更新為ArrayL數組中與其距離最短的目標的ID，并將其對應元素在ArrayL數組中刪除。

8)遍歷結束后，ArrayL數組中余下的Blobi即為上一幀存在但當前幀消失的目標，將其刪除。

9)將當前幀數組ArrayN中的元素更新到ArrayN數組中。

10)循環執行步驟3)～9)過程，直到程序結束。

隨著視頻幀數據的不斷采集，循環進行上述過程，即實現了目標的檢測與跟蹤。流程圖如圖3所示。

3 目標跟蹤實驗

采用三軸云臺固定攝像機進行實驗，視頻圖像分辨力為640×480，背景模型建立過程累積了35幀圖像，在普通PC上目標檢測與跟蹤的速度可以達到25 f/s(幀/秒)。

圖4分別為第4，6，26，150幀時目標跟蹤的情況，可以看到，目標被完整地檢測出來，在目標物像素尺寸相對整個視頻幀圖像的比例較大的時候，沒有出現單一目標被誤檢測成多個目標的現象，且目標的運動能夠被較好地跟蹤。

圖4 目標跟蹤結果

4 結論

本文討論了幾種目標檢測中背景建模的方法，并重點說明了背景差分的建模方法，對差分后的圖像進行濾波和形態學處理之后，可以得到較完整的目標輪廓，并且通過KD-Tree算法對目標進行跟蹤，大幅度提高了跟蹤效率。

［1］蔡榮太，吳元昊，王明佳，等.視頻目標跟蹤算法綜述［J］.電視技術，2010，34(12)：125-127.

［2］潘翔鶴，趙曙光，柳宗浦，等.一種基于梯度圖像幀間差分和背景差分的運動目標檢測新方法［J］.光電子技術，2009，29(1)：34-36.

［3］SPROULL R F.Refinements to nearest-neighbor searching in K-dimensional trees［J］.Algorithmica，1991，6(4)：579-589.

［4］KIM K，CHALIDABHONGSE T H，HARWOOD D，et al.Real-time foreground-background segmentation using codebook model［J］.Real-Time Image，2005，11(3)：172-185.

［5］劉宇，熊有倫.基于有界k-d樹的最近點搜索算法［J］.華中科技大學學報：自然科學版，2008，36(7)：73-76.