視頻序列中目標(biāo)的檢測與跟蹤

蔡睿妍，田 全

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

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

1 目標(biāo)檢測

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

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

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

顏色扭曲度為

u2可以由式(5)求解

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

不同處理階段目標(biāo)檢測的結(jié)果如圖1所示?？梢钥吹?，在經(jīng)過上述處理，得到了完整的目標(biāo)。

圖1 目標(biāo)檢測

2 目標(biāo)跟蹤

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

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

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

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

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

圖2 KD-Tree算法原理圖

算法流程如下：

1)定義目標(biāo)質(zhì)心點(diǎn)坐標(biāo)存儲結(jié)構(gòu)體，即

其中ID為每個目標(biāo)對應(yīng)的序號，x和y分別為每個目標(biāo)質(zhì)心坐標(biāo)的橫、縱坐標(biāo)值。

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

圖3 目標(biāo)檢測與跟蹤流程

3)將第i+1幀的每個目標(biāo)的橫縱坐標(biāo)按照Blob2D32f結(jié)構(gòu)體形式進(jìn)行存儲，ID號不填充，然后存放在當(dāng)前幀數(shù)組ArrayN中。

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

5)定義D_max。

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

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

8)遍歷結(jié)束后，ArrayL數(shù)組中余下的Blobi即為上一幀存在但當(dāng)前幀消失的目標(biāo)，將其刪除。

9)將當(dāng)前幀數(shù)組ArrayN中的元素更新到ArrayN數(shù)組中。

10)循環(huán)執(zhí)行步驟3)～9)過程，直到程序結(jié)束。

隨著視頻幀數(shù)據(jù)的不斷采集，循環(huán)進(jìn)行上述過程，即實(shí)現(xiàn)了目標(biāo)的檢測與跟蹤。流程圖如圖3所示。

3 目標(biāo)跟蹤實(shí)驗(yàn)

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

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

圖4 目標(biāo)跟蹤結(jié)果

4 結(jié)論

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

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

［2］潘翔鶴，趙曙光，柳宗浦，等.一種基于梯度圖像幀間差分和背景差分的運(yùn)動目標(biāo)檢測新方法［J］.光電子技術(shù)，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樹的最近點(diǎn)搜索算法［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，36(7)：73-76.