一種用于多目標跟蹤的特征關聯方法

摘 要:在基于圖像序列的多目標跟蹤問題中，傳統目標鏈算法利用目標的運動特征和面積特征對其進行關聯，取得了較好的效果，但在如新目標進入視場，舊目標離開視場，多個目標靠近、融合，單目標發生分裂等復雜跟蹤情況中，以上特征存在一定的失效情況。為此，提出一種計算目標形狀相似度的方法，在傳統目標鏈算法的基礎上引入描述目標形狀的新特征，構造了一個計算目標形狀相似度的函數，可以解決形狀不同的目標在靠近或交叉通過等復雜情況下的準確關聯問題。實驗表明，在對剛體目標的跟蹤中得到了更可靠的目標關聯效果。

關鍵詞:圖像序列; 目標關聯; 特征匹配; 形狀特征

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3545-03

doi:10.3969/j.issn.1001-3695.2009.09.099

Track multiple objects with feature-correlation algorithms

NIE Xuan1， CHEN Huai-min2

(1.College of Software Microelectronics， Northwestern Polytechnical University， Xi’an 710072， China; 2. National Laboratory of UAV Special Technology， Northwestern Polytechnical University， Xi’an 710065， China)

Abstract:This paper proposed a method to compute objective contour feature. Conventional objective chain algorithms correlated the motion with area characteristics of the objectives to reach the goals. Nevertheless， they might not be efficient under certain circumstances of complicated tracking. This paper incorporated the contour characteristic of the objective into conventional methods and thus constructed a function to estimate the similarity of the objective. Experiments were conducted to show that more reliable results are obtained when rigid objects are tracked.

Key words:image sequence; objective correlation; feature matching; geometric feature

在基于圖像序列的目標跟蹤中，所觀測目標出現在與其相似的目標群中的概率經常大于其獨自出現的概率，故多目標的跟蹤具有很強的實用性，它在交通監控、軍事偵察和監視、飛機導航以及天文觀察等領域都有著重要的實用價值[1，2]。同時，多目標的跟蹤也是一個相當具有挑戰性的課題，因為多目標存在的場景中，圖像中各運動目標區域在時、空域變化特性不同，使得觀測場景內運動狀態呈多樣性變化，如新目標進入視場，舊目標離開視場，多個目標靠近、融合，單目標發生分裂等[3]。

在多目標跟蹤中，特征關聯是一類重要的方法，其主要解決各目標在不同幀之間彼此關聯的問題，即運動目標之間的對應關系通過目標的特征匹配來建立。常用的匹配特征有目標的位置、大小以及顏色等。對于這類算法的研究很多，一般都基于目標和背景之間存在明顯區分的假設，其關聯效果取決于對目標特征的選擇。圖1給出了特征關聯在多目標跟蹤中的作用。

在特征關聯算法中，為從多幅圖像尋找對應于同一目標的匹配，通常采用最近鄰法或全鄰域法。其使用的匹配函數通常利用每個目標質心位置信息，即考慮待跟蹤目標與下一幀各目標質心間的歐氏距離，距離最小的兩個目標認為是同一個目標。該方法較少考慮目標自身的特征屬性，易出現跟蹤錯誤。也有學者提出在目標檢測與提取基礎上，同時利用目標質心位置與目標所占圖像區域面積作為特征進行匹配的方法[4]，盡管較單獨利用目標質心位置有一定的改進，但仍無法處理同類目標交叉通過的情況。為此，本文提出一種基于特征關聯新方法，可較好地處理復雜情況下目標關聯的問題。

1 基于目標鏈的特征跟蹤算法

在對圖像中的目標進行檢測和提取后，可建立每個目標的目標鏈，以確定同一目標在相鄰幀圖像中的聯系。具體方法為:a)在跟蹤開始時，為檢測到的每個目標相應建立一個特征向量并作為一個節點記錄在一個鏈表中，該鏈表被稱為目標鏈，同時設置一個計數器來記錄目標數目;b)利用目標鏈進行目標匹配，具體地，計算當前幀中每個目標的特征參數向量，與上一幀的各個目標鏈節點進行匹配，以確定目標間的關聯，并用同一目標的新特征向量更新目標鏈中相應的特征向量節點;c)如果已被記錄的特征向量不被任何目標匹配，則判斷該目標離開場景，此時刪除其特征向量節點，并對目標計數減1;d)如果有的目標匹配不到已記錄的特征向量，則判斷有新目標出現，此時建立新的特征向量節點，且對目標計數加1。這樣，對每一個目標，其在被跟蹤過程中始終與一個代表它的特征向量相關聯。用于辨識每個目標的特征向量由目標鏈的一個節點記錄，目標鏈節點的不斷更新反映出了目標運動狀況的改變，而節點的插入和刪除表示新目標的出現和已有目標的離開。

2 基于目標位置與面積特征的匹配算法

為敘述方便，定義一組經連續采樣得到的圖像序列F={f1，f2，…，fn}，對其中每幀圖像統一到相同的二維直角坐標系中，將第k幀圖像fk中的m個目標分別記為R={r1，r2，…，rm}。

由于跟蹤系統的攝像機一般具有較高的采樣頻率，序列中相鄰兩幀的時間相隔Δt比較小，根據目標運動的連續性，其位置和速度等運動狀態不可能在這樣短的時間內發生較大變化。由于目標運動中的能量集中于其質心，該質心位置變化具有連續性，可采用最近鄰法或全鄰域法利用位置相似性特征進行目標關聯。具體地，考察當前某目標與下一幀中每個待匹配目標之間質心的歐氏距離，則距離最小時認為是同一個目標。

當單獨考慮目標質心距離的特征信息時，定義ri的位置特征值為(xik，yik)，它表示在fk內ri質心的坐標;同時，(xjk+1，yjk+1)表示fk+1中rj的質心坐標。兩個待匹配目標間的絕對距離為

D(i，j)=(xik-xjk+1)2+(yik-yjk+1)2(1)

將式(1)定義的距離作歸一化處理，得到以下的運動位置相對相似度函數:

s(D(i，j))=D(i，j)/∑i(D(i，j))(2)

其中:∑i(D)表示屬于fk的某目標ri與fk+1中所有目標的位置距離之和。

式(2)表達了目標間的運動相似性，即s(D(i，j))越小，其運動越相似。同理，還可以考慮對目標其他運動特征的利用，若增加目標運動的速度、加速度狀況，則建立的匹配函數會更有效，但相應的計算復雜度也會提高。如果不同目標之間的運動速度差異較大，應考慮將其速度、加速度等作為判斷目標運動狀態是否相似的特征。

同理，相鄰兩幀中同一個目標的面積也不可能發生較大變化，故可以利用最近鄰法建立如式(3)所示的面積的相對相似度函數:

s(A(i，j))=|ΔA(i，j)|/∑i(|ΔA(i，j)|)(3)

其中:ΔA(i，j)=A(i)-A(j)，表示任意兩目標ri與rj的面積絕對差異;∑i(|ΔA|)表示屬于fk的某目標ri與fk+1中所有目標的面積絕對差異之和。

利用目標的運動特征和面積特征可在一定程度實現有效的目標關聯，但實際中往往存在著多個面積差異較小的目標發生運動交叉的情況，此時以上特征可能會失效。本文提出一種在以上算法的基礎上引入計算目標形狀相似度的方法，通過比較目標在形狀上的差異使該問題得到解決。

3 目標形狀相似度的計算

對于剛體目標，因其運動的連續性，它在相鄰的兩幀圖像中的輪廓形狀將基本維持不變?；谏鲜鲈颍疚奶岢鲆环N計算目標形狀相似度的方法，在跟蹤剛體目標時，可將其與目標的運動特征和面積特征結合起來進行目標關聯。

為敘述方便，定義F(i，j)為目標ri與rj之間的形狀相似度判定函數，用于表示該兩個目標的輪廓形狀接近程度。本文認為，將目標的輪廓曲線用一個多邊形近似表征后，可進一步計算F(i，j)。

具體地，由于目標輪廓是一條封閉曲線，從幾何意義上，它可以看做某個多邊形在頂點數趨向無窮時的近似逼近。一般地，也可利用頂點密集的多邊形來近似表示該曲線。例如對于圖2(a)(b)中的兩個目標，可得到(c)(d)的輪廓效果。因此，理論上可通過對多邊形的相似性分析來判斷目標形狀的接近程度。為了簡化運算，可在待匹配的相鄰兩幀圖像中，將光柵化表示的目標輪廓曲線上的點各自進行等比例間隔的重采樣，連接重采樣后得到的相鄰點便產生了一個表征目標輪廓形狀的多邊形。由于采樣比例間隔相同，所產生的兩個多邊形的頂點數目相同，且它們為同構多邊形，如圖2(e)(f)所示。重采樣后，多邊形頂角的銳利程度反映了目標輪廓的變化程度，頂角越銳利，其表征目標形狀特征的能力越強;反之，若頂角較鈍，其表征目標形狀特征的能力較弱。當某頂點接近時，該頂點原來連接的兩條線段可用一條線段進行替換。為了突出輪廓特征，本文采取刪除較平直頂點、保留較銳利頂點的策略，以削弱較平直頂點對輪廓形狀相似判定的干擾。具體地，按照頂點的銳利度排序，并按照設定的頂點保留數目將其中較平直的頂點刪去，得到簡化后的多邊形，如圖2(g)(h)所示。

再查找各多邊形的最大拐點(即頂角內角最小的點)，沿著順時針方向將各個頂角順次對應起來，并建立它們形狀的絕對相似度函數F(i，j)，如式(4)所示:

F(i，j)=∑Mm=1|θk，im-θk+1， jm|(4)

其中:θk，im和θk+1， jm的含義為:對于任意目標ri和rj，表示它們各自輪廓的m邊形的對應內角。式(4)表明兩個同構多邊形對應內角的角度越接近，它們就越相似。

最后進行歸一化處理，修改后的形狀相對相似度函數如式(5)所示，它代表了兩目標在目標群中的形狀相對接近程度。

s(F(i，j))=F(i，j)/∑i(F)(5)

其中:∑i(F)為屬于fk的某目標ri與fk+1中所有目標的絕對相似度之和。s(F(i，j))間接給出了對應目標的形狀相似度。

4 特征匹配

在式(2)(3)(5)中，s(D)代表了目標位置之間的接近程度，s(A)說明目標面積的差別程度，而s(F)表征了目標間形狀的相似程度。當應用中存在多個同類目標時，利用目標質心位置的變化信息能夠有效關聯各目標，而依據目標的面積和形狀就能夠將異類目標區分出來。因此在一般情況下，綜合采用以上三種特征起到了很好的目標辨識作用?？紤]到在不同的應用場合，三種特征對判別的影響程度不同，本文給出的目標辨識特征向量為[γs(D)，ξs(A)，λs(F)]。其中，γ、ξ、λ是三個特征的影響因子，其取值由具體應用來確定。由此得到表示目標ri與rj的絕對相似度函數如下:

Δ(i，j)=(γs(D))2+(ξs(A))2+(λs(F))2(6)

最后作歸一化處理，并將目標相似函數修正為ΔR(i，j)=1-Δ(i，j)/∑i(Δ(i，j))。其中:∑i(Δ(i，j))為屬于fk的某目標ri與fk+1中所有目標的絕對相似度之和。ΔR(i，j)代表了兩個目標總的相對相似程度，該值越大，說明兩目標的關聯性越大。顯然，max ΔR(i，j)表示ri與rj是同一目標的可能性最大。利用這種方法，可設定相似度的閾值TΔ來判斷目標的消失。如果在fk+1中，某目標與fk的所有目標匹配的結果均小于TΔ，說明在fk+1中該目標消失;如果比TΔ大，則相似函數取得最大值時的目標為原目標的后續。這種關系由式(7)給出:

same(i，j)=1max ΔR(i，j)≥TΔ0max ΔR

為了在較小區域中進行目標關聯，可根據每個目標的運動狀況，引入卡爾曼濾波來預測目標出現區域， 從而減少運算量，并使跟蹤穩定性增強，即由目標ri的運動狀態得到在fk+1中對它的搜索區域，并僅在搜索區域中進行目標相似性判斷。

5 目標關聯

在相鄰幀圖像中進行目標關聯是多目標跟蹤重點解決的課題，需要考慮目標與目標的對應，以及是否有新目標進入或者舊目標離開場景等問題。

為了便于討論，將目標區域分成三種，分別為進入區、跟蹤區和離開區[5]。進入區表示目標剛剛進入場景;跟蹤區表示目標進入完全跟蹤狀態;離開區表示目標已經脫離跟蹤。算法關鍵在于如何對相鄰幀中同一運動目標建立正確的對應關系，避免產生誤配。在目標分割與提取的基礎上，可根據保存的目標鏈來確定ri的后續rj;然后用rj的特征值來刷新其對應的目標鏈節點，提供給后續跟蹤使用，同時保留目標的運動軌跡，并借助卡爾曼濾波來預測其運動位移。由于目標鏈記錄了目標的自身特征和運動特征，隨時提供對目標的辨識依據，將作為目標關聯條件的式(7)與以下判斷策略相結合，可得到有效的目標關聯方法:

a)將開始跟蹤時的第一幀圖像中出現的目標全部作為新目標。如果目標質心位置的坐標P(x，y)

b)接收后續圖像fk，對當前第i個目標ri(1≤i≤n，n為被跟蹤目標數)，如果其處于跟蹤區，則運用卡爾曼濾波進行跟蹤，反之則否。對于前一種情況，計算ri與fk+1內所有目標間的相似度函數，并根據式(7)進行如下判斷:

(a)如果same(i，j)=1，說明目標rj為目標ri的后續，用rj的特征值更新ri的目標鏈節點，并對該目標rj作更新標記。

(b)如果same(i，j)=0，說明目標ri在fk+1中沒有后續。這時可能出現目標暫時靜止、消失或者離開跟蹤區三種情況?？筛鶕i的質心坐標作如下判斷:若Pi(x，y)Pout(x，y)，認為該目標離開跟蹤區，應停止該目標對應的卡爾曼模型，同時刪除其目標鏈節點。

(c)在對所有被跟蹤目標進行匹配后，檢查fk上所有目標是否被標記，如果全部目標都被做了標記，則說明對屬于fk的所有目標找到了關聯關系;如果有目標未被標記，那么應判斷其質心坐標是否滿足Pin(x，y)≤P(x，y)

(d)遞歸處理fk+1，重復(a)~(c)，直至圖像序列處理結束。

6 實驗結果及評價

圖3給出一組測試圖像。其中，(a)(b)分別為第k、k+1幀原始圖像，圖中有兩個目標分別向右、向左運動。對于(a)中向右運動的目標，表1給出了本文提出的算法與采用目標運動特征和面積特征的算法[6]分別計算的相似度結果比較。

表1中，f1o1為第k幀中向右運動的目標;f1o2為第k幀中向左運動的目標;f2o1為第k+1幀中向右運動的目標;f2o2為第k+1幀中向左運動的目標。取γ=ξ=λ=1。

從表1可以看到，本文計算得到的前后幀圖像中兩個向右運動的目標之間的相似度為0.659，大于文獻[6]算得的0.601;而f1o1與f2o2之間的相似度為0.341，小于文獻[6]算得的0.399，即本文得出相同目標間的相似度較高，不同目標間相似度較低。顯然，本文結果的可靠性較高。

7 結束語

針對傳統算法所采用的運動特征和面積特征存在的特異性小、容易造成誤關聯的缺陷，提出了一種計算目標形狀相似度的方法，并通過將目標形狀特征與文獻[6]使用的運動特征和面積特征相結合，獲得了更可靠的目標關聯效果。

參考文獻:

[1]MAGEE D R. Tracking multiple vehicles using foreground， background and motion models [J]. Image and Vision Computing， 2004，22(2): 143-155.

[2]HARITAOGLU I， HARWOOD D， DAVIS L. W4: real-time surveillance of people and their activities [J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2000，22(8): 809-830.

[3]BAR-SHALOM Y. Tracking methods in a multitarget environment [J]. IEEE Trans on Automatic Control， 1978，23(4): 618-626.

[4]COLLINS R， LIPTON A， KANADE T， et al. A system for video surveillance and monitoring， CMU-RI-TR-00-12 [R]. Pittsburgh: Carnegie Mellon University， 2000.

[5]張嫣.運動圖像序列中多目標跟蹤的研究與實現[J].計算機應用研究，2002， 19(1):74-76.

[6]付曉薇，方康玲，邱奕敏，等.一種基于特征代價函數的多目標跟蹤算法[J].武漢科技大學學報，2004， 27(4):416-418.