蔡睿妍，田 全

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

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

1 目標(biāo)檢測(cè)

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

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

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

顏色扭曲度為

u2可以由式(5)求解

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

不同處理階段目標(biāo)檢測(cè)的結(jié)果如圖1所示。可以看到，在經(jīng)過(guò)上述處理，得到了完整的目標(biāo)。

圖1 目標(biāo)檢測(cè)

2 目標(biāo)跟蹤

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

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

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

針對(duì)上述3種情況，本文采用KD-Tree算法［5］實(shí)現(xiàn)目標(biāo)跟蹤。KD-Tree算法是一種由二叉搜索樹(shù)推廣而來(lái)的用于多維檢索的樹(shù)的結(jié)構(gòu)形式(K即為空間的維數(shù)，此處定義K=2)。與二叉搜索樹(shù)不同的是，它的每個(gè)結(jié)點(diǎn)表示k維空間的一個(gè)點(diǎn)，并且每一層都根據(jù)該層的分辨器對(duì)相應(yīng)對(duì)象做出分枝決策。頂層結(jié)點(diǎn)按由分辨器決定的一個(gè)維度進(jìn)行劃分，第二層則按照該層的分辨器決定的另一個(gè)維度進(jìn)行劃分，以此類推在余下各維之間不斷地劃分。直至一個(gè)結(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個(gè)部分，然后在左右2個(gè)子樹(shù)中以B點(diǎn)和C點(diǎn)的x維度將左右2個(gè)子樹(shù)分為2個(gè)部分，以此類推，在B點(diǎn)、C點(diǎn)各自的子樹(shù)當(dāng)中，以D點(diǎn)、E點(diǎn)的y維度對(duì)其子樹(shù)劃分，遍歷集合當(dāng)中的每一個(gè)點(diǎn)，就可以得到1個(gè)完整的KD-Tree。目標(biāo)軌跡建立的過(guò)程就是在KD-Tree中搜索最近點(diǎn)的過(guò)程，采用KDTree進(jìn)行最近點(diǎn)搜索可以提高系統(tǒng)的工作效率。

圖2 KD-Tree算法原理圖

算法流程如下：

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

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

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

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

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

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

5)定義D_max。

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

7)如果d＞D_max，則該Blobi為新當(dāng)前幀新增加的目標(biāo)，將其賦予一個(gè)新的ID;如果d≤D_max，則該Blobi為由上一幀的目標(biāo)運(yùn)動(dòng)得到的，將其ID更新為ArrayL數(shù)組中與其距離最短的目標(biāo)的ID，并將其對(duì)應(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)過(guò)程，直到程序結(jié)束。

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

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

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

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

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

4 結(jié)論

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

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

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