樊 祥，方義強(qiáng)，2，程正東，朱 斌，施 展，2

(1解放軍電子工程學(xué)院，合肥 230037;2脈沖功率激光技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，合肥 230037)

0 引言

對目標(biāo)的檢測跟蹤算法在近幾年得到了很大的發(fā)展。為了能夠?qū)λ惴ㄓ幸粋€合適、客觀的評價，更好的把握算法改進(jìn)和研究的方向，促進(jìn)對算法的優(yōu)化，需要一個科學(xué)的算法性能評價方法。對于檢測算法的性能評價研究得比較多，很多文獻(xiàn)都對這方面做了比較深入的討論研究[1];而現(xiàn)行文獻(xiàn)資料對于目標(biāo)跟蹤算法的評價方法研究較少，只分別從一些側(cè)面對跟蹤算法進(jìn)行過初步的研究。文獻(xiàn)[2]采用了有效跟蹤評價和有效跟蹤精度評價的方法對跟蹤算法進(jìn)行評價;綜述文獻(xiàn)[3]提到了目前國際上在智能視頻算法中通過精確度、完整性來進(jìn)行跟蹤算法的性能評價;文獻(xiàn)[4－6]用算法具有低的跟蹤誤差來說明算法性能優(yōu)越性的問題;文獻(xiàn)[7]用算法的跟蹤有效性和精度來說明算法性能;文獻(xiàn)[8－9]通過算法的實(shí)時性來說明算法的優(yōu)越性。但是這些文獻(xiàn)都沒有系統(tǒng)的對跟蹤算法的性能進(jìn)行評價，主要表現(xiàn)在兩個方面:一是采用的性能指標(biāo)不夠全面;二是沒有對各性能指標(biāo)進(jìn)行綜合。

因此文中主要針對跟蹤算法的評價方法不夠健全的問題，利用層次分析法(AHP)提出了一種評價跟蹤算法的方法，AHP法為運(yùn)籌學(xué)中進(jìn)行系統(tǒng)效能評價的一種方法，文中是第一次用AHP法來進(jìn)行跟蹤算法的性能評價。

1 主要性能指標(biāo)的分析

要對跟蹤算法進(jìn)行評價，首先需選取合適的指標(biāo)作為評價的依據(jù)。通過對相關(guān)文獻(xiàn)和算法的研究，一個完整的跟蹤算法主要涉及到的指標(biāo)有跟蹤準(zhǔn)確度、算法的實(shí)時性和算法的硬件實(shí)現(xiàn)等，因此文中主要從算法的這幾個方面來考慮跟蹤算法的性能評價問題。

1.1 跟蹤準(zhǔn)確度

跟蹤準(zhǔn)確度是最直觀的反映算法性能的一個方面。文獻(xiàn)[10]提出了一個跟蹤率的概念，跟蹤率定義為，α=n/N，其中n為持續(xù)跟蹤上的圖像幀數(shù)，N為跟蹤圖像的總幀數(shù)。該方法可以在一定程度上表征算法對目標(biāo)的跟蹤準(zhǔn)確度，但該方法只是從是否跟蹤上目標(biāo)來說明跟蹤的準(zhǔn)確度問題，是一個比較粗糙的方法，不能精確的描述一個算法的跟蹤準(zhǔn)確度，尤其是對于對紅外小目標(biāo)的跟蹤描述。而多數(shù)文獻(xiàn)用目標(biāo)的算法預(yù)測位置與實(shí)際位置的差，即跟蹤誤差來說明跟蹤的準(zhǔn)確度問題[3－4，7]，該方法精確的描述了每幀圖像的誤差，但同時該方法不對跟丟的情況進(jìn)行判斷，使得跟蹤誤差在遇到目標(biāo)跟丟的情況下失去了意義。因此文中將兩者結(jié)合起來描述跟蹤的準(zhǔn)確度。

由于存在目標(biāo)跟丟的情況，因此需要對跟蹤誤差做進(jìn)一步的定義。假設(shè)對于某個算法，算法得到的有效預(yù)測坐標(biāo)與實(shí)際坐標(biāo)的平均跟蹤誤差為E(μ)，其定義如下:

式中:xti、yti是真實(shí)目標(biāo)的坐標(biāo)值;xci、yci是算法跟蹤有效的目標(biāo)坐標(biāo)值。這里計算平均跟蹤誤差時，只計算了算法對目標(biāo)有效跟蹤部分的坐標(biāo)值，而沒有考慮跟丟時誤差的計算，顯然這樣不夠合理。因此在討論誤差時，文中提出采用E(μ)/S11=E(μ)·N/n來衡量算法的跟蹤誤差。

1.2 跟蹤算法的實(shí)時性

對目標(biāo)的自動檢測跟蹤對實(shí)時性的要求很高，在算法評價時必須要考慮其實(shí)時性的問題?，F(xiàn)行的很多算法結(jié)構(gòu)比較復(fù)雜，時間開銷很大，雖然這些算法在一些特定的場合在某些方面可以取得相對較好的效果，但是這樣的算法實(shí)時性差，仍然沒有實(shí)際應(yīng)用的價值。因此，在考慮跟蹤算法的性能評價時，必須要把實(shí)時性考慮在內(nèi)。

設(shè)v為算法處理速度，單位為fps(幀 /s)，文中算法的處理速度用計算機(jī)仿真得到。算法的處理速度應(yīng)該有一個合適的值，這與有些文獻(xiàn)上認(rèn)為的處理速度越快越好的觀點(diǎn)是不一樣的。因?yàn)樗惴ㄊ紫葢?yīng)該滿足實(shí)時性的要求，但是當(dāng)算法達(dá)到的速度過快時，已經(jīng)遠(yuǎn)超出了實(shí)時性的要求，超出的部分對于算法性能的提高沒有影響或影響不大，而且很多情況下處理速度的加快是以犧牲其它方面的性能為代價的。因此文中在考慮實(shí)時性的時候提出處理速度上限和下限的概念，分別用vH和vL表示，用一個分段函數(shù)來表述處理速度對算法性能的影響，表達(dá)形式如下:

當(dāng)v＜vL時，認(rèn)為算法過慢，為無效算法;當(dāng)vL≤v≤vH時，算法性能隨著速度的增加線性提高;當(dāng)v＞vH時，認(rèn)為算法處理速度已超過了需求的處理速度。

1.3 算法的硬件可實(shí)現(xiàn)性

好的算法同時也應(yīng)該適合于硬件的實(shí)現(xiàn)[11]，而很多算法在設(shè)計時沒有考慮到其硬件實(shí)現(xiàn)的問題，沒有考慮算法所需要的硬件資源情況以及現(xiàn)階段的可實(shí)現(xiàn)性問題，使得這些算法只能停留在研究層面。因此，文中提出把算法的硬件可實(shí)現(xiàn)性也作為評價算法的一個重要的依據(jù)。

對于一個算法，其越容易通過硬件來實(shí)現(xiàn)，對硬件資源的需求越少，則認(rèn)為該算法的可實(shí)現(xiàn)性越好。與前兩者不同的是，算法硬件的可實(shí)現(xiàn)性為定性指標(biāo)，因此文中采用5個等級來量化算法的可實(shí)現(xiàn)性，用δ表示，δ的值越大說明其硬件可實(shí)現(xiàn)性越好，其取值情況如表1所示[12]。

表1 δ的取值與等級的對應(yīng)關(guān)系

其中，硬件可實(shí)現(xiàn)性的權(quán)值可以通過算法實(shí)現(xiàn)對硬件資源的需求、硬件開發(fā)難易程度等方面來綜合衡量，通過評價者的經(jīng)驗(yàn)或相關(guān)專家討論來確定。也可以把硬件可實(shí)現(xiàn)性分成更詳細(xì)的下級指標(biāo)參數(shù)，由評價者或者組織各領(lǐng)域?qū)＜疫M(jìn)行打分確定，文中對此不做更深入的研究。

2 算法性能的綜合計算

通過前面的論述可知，對于小目標(biāo)跟蹤算法評價的內(nèi)容如圖1所示。

圖1 跟蹤算法性能評價內(nèi)容

在確定各個指標(biāo)后，需要按照實(shí)際的需求情況，對各個指標(biāo)進(jìn)行加權(quán)綜合，形成對跟蹤算法性能評價的綜合指標(biāo)。常用的可用于指標(biāo)加權(quán)的方法有AHP法、模糊綜合評價法等，而從跟蹤算法評價的內(nèi)容可以看到評價指標(biāo)體系具有明顯的層次性，而且涉及的指標(biāo)參數(shù)較少，因此文中采用 AHP法來計算綜合指標(biāo)。

AHP法是美國匹茲堡大學(xué)運(yùn)籌學(xué)專家T.L.Saaty于20世紀(jì)70年代提出的一種系統(tǒng)分析方法。1982年天津大學(xué)許樹柏等將該方法引入我國，研究內(nèi)容主要集中在判斷矩陣、比例標(biāo)度、一致性問題、可信度上。AHP法是一種實(shí)用的多準(zhǔn)則決策方法，該方法以其定性與定量相結(jié)合處理各種決策因素的特點(diǎn)，以及系統(tǒng)、靈活、簡潔的優(yōu)點(diǎn)，在我國得到了廣泛的應(yīng)用[12]。

2.1 構(gòu)造權(quán)重判斷矩陣

根據(jù)AHP法，首先需要構(gòu)造權(quán)重判斷矩陣，以區(qū)分各個指標(biāo)的權(quán)重。在構(gòu)造判斷矩陣時，要根據(jù)實(shí)際情況選擇合適的標(biāo)度法，由決策者直接通過對指標(biāo)兩兩比較得到，常見的標(biāo)度法有1～9標(biāo)度法，9/9～9/1分?jǐn)?shù)標(biāo)度法、90/9～99/9指數(shù)標(biāo)度法等。如表2為應(yīng)用比較多的 1 ～ 9 標(biāo)度法[12－13]。

表2 1～9標(biāo)度法等級量化表

如對于第一層指標(biāo)，假設(shè)其判斷矩陣為A，則其形式如下:

式中，aij表示指標(biāo)ai相對于指標(biāo)aj的相對權(quán)重，指標(biāo)a1、a2、a3分別對應(yīng)于跟蹤準(zhǔn)確度、實(shí)時性和硬件可實(shí)現(xiàn)性。

2.2 指標(biāo)權(quán)重計算

根據(jù)AHP法，得到判斷矩陣后，對指標(biāo)權(quán)重的計算分3個步驟，以第一層指標(biāo)為例。

第一步，計算判斷矩陣A的每一行元素的乘積:

式中n為判斷矩陣A的維數(shù)。

第二步，計算Mi的n次方根:

第三步，對ˉωi進(jìn)行歸一化處理:

這樣就得到了所需求的權(quán)向量 ω =[ω1，ω2，ω3]，ω1、ω2、ω3分別為跟蹤準(zhǔn)確度、實(shí)時性和硬件可實(shí)現(xiàn)性。

2.3 一致性檢驗(yàn)

對于判斷矩陣，由于人的主觀度量可能存在一定的偏差，因此為了提高權(quán)重評價的可靠性，最后需要對判斷矩陣做一致性檢驗(yàn)。

判斷矩陣的最大特征值λmax為:

式中，[Aω]i為Aω向量中的第i個元素。

一致性檢驗(yàn)的公式為:

其中:CI為一致性指標(biāo)，CR為一致性比例，RI為修正因子。通常情況下，當(dāng)CR ＜0.1時，認(rèn)為該判斷矩陣滿足一致性要求，對于維數(shù)小于3的不需要進(jìn)行判斷。RI的取值和維數(shù)相關(guān)，其取值和維數(shù)的對應(yīng)關(guān)系如表 3 所示[12]。

表3 RI的取值表

2.4 指標(biāo)的規(guī)范化

對上述的用于評價的各種指標(biāo)，其量綱不同，各指標(biāo)值的量級也不一樣，很可能造成評價的不合理性，因此在進(jìn)行綜合評價前，有必要把各指標(biāo)值轉(zhuǎn)換為可以綜合處理的量化值，一般都規(guī)范到[0，1]的范圍內(nèi)。

跟蹤率S11=α=n/N和硬件可實(shí)現(xiàn)性S3=δ的值已經(jīng)在[0，1]內(nèi)，且為無量綱的量，滿足規(guī)范要求;跟蹤實(shí)時性S2，通過S2=η/vH來規(guī)范;跟蹤誤差S12屬于成本型指標(biāo)，即誤差越小，跟蹤效果越好，根據(jù)成本型指標(biāo)的線性變換方法[12]，首先得到最小誤差Emin(μ)，然后通過線性變換把跟蹤誤差的值限定在[0，1]的范圍內(nèi)，而理論上的最小誤差值為零，因此Emin(μ)必須為一個非零值，對于小于該值的誤差按照Emin(μ)處理。

2.5 計算綜合評價分?jǐn)?shù)

在獲得各指標(biāo)的權(quán)重后，通過與對應(yīng)評價值的乘積就可以得到最后的綜合評價分?jǐn)?shù)。對于不同的跟蹤算法，得分最高者性能好。計算算子為:

S1、S2、S3分別為跟蹤準(zhǔn)確度、實(shí)時性和硬件可實(shí)現(xiàn)性的評價分?jǐn)?shù)。其中跟蹤準(zhǔn)確度的分?jǐn)?shù)S1同樣可以通過AHP法由跟蹤率和跟蹤誤差獲得，即 S1=[ω11，ω12][S11，S12]T。

通過前面的討論可以得到基于AHP的小目標(biāo)跟蹤算法的評價流程如圖2所示。

圖2 基于AHP的小目標(biāo)跟蹤算法的評價流程圖

3 實(shí)驗(yàn)驗(yàn)證

求得權(quán)向量分別為[ω11，ω12]= [0.75，0.25];[ω1，ω2，ω3]= [0.57，0.29，0.14]。對于 A2，其一致為了驗(yàn)證文中方法的合理性以及對一些參數(shù)的確定和優(yōu)化，文中采用流行的幾種跟蹤算法進(jìn)行了實(shí)驗(yàn)，并通過上述評價方法來進(jìn)行跟蹤算法的性能評價，得到各個算法的綜合評價分?jǐn)?shù)。

在實(shí)驗(yàn)之前，文中通過綜合考慮構(gòu)造了判斷矩陣，用于實(shí)驗(yàn)后的性能討論，由于該評價系統(tǒng)中涉及的指標(biāo)參數(shù)少，容易進(jìn)行兩兩比較判斷，因此文中采用了1～9標(biāo)度法來構(gòu)造權(quán)重判斷矩陣。對于跟蹤率和跟蹤誤差采用的判斷矩陣為A1，對于跟蹤準(zhǔn)確度、實(shí)時性和硬件可實(shí)現(xiàn)性的判斷矩陣為A2，則其取值如下:性比例RI=0，符合一致性要求。

由于文中采用的跟蹤算法是針對紅外小目標(biāo)的跟蹤的，認(rèn)為當(dāng)跟蹤誤差超過3個像素時就認(rèn)為目標(biāo)開始丟失，并且取Emin(μ)取0.2(個像素);算法處理速度的上限設(shè)為 50fps，下限設(shè)為1fps。文中實(shí)驗(yàn)總共包含3組圖像序列和4種不同的算法。圖3為參與實(shí)驗(yàn)的3組圖像序列，其中小目標(biāo)用白色矩形框標(biāo)識。

圖3 參與實(shí)驗(yàn)的3組圖像序列

表4～表6為分別采用粒子濾波算法[14]、均值位移算法[15]、自適應(yīng)閾值分割算法[16]和基于數(shù)學(xué)形態(tài)學(xué)的小目標(biāo)跟蹤算法進(jìn)行實(shí)驗(yàn)得到的數(shù)據(jù);表7～表9為由各個實(shí)驗(yàn)得到的數(shù)據(jù)根據(jù)本章提出的評價方法計算得到的指標(biāo)分?jǐn)?shù)。

表4 采用圖像序列1實(shí)驗(yàn)后得到的數(shù)據(jù)

表5 采用圖像序列2實(shí)驗(yàn)后得到的數(shù)據(jù)

表6 采用圖像序列3實(shí)驗(yàn)后得到的數(shù)據(jù)

表7 采用圖像序列1實(shí)驗(yàn)數(shù)據(jù)計算得到的指標(biāo)分?jǐn)?shù)

表8 采用圖像序列2實(shí)驗(yàn)數(shù)據(jù)計算得到的指標(biāo)分?jǐn)?shù)

表9 采用圖像序列3實(shí)驗(yàn)數(shù)據(jù)計算得到的指標(biāo)分?jǐn)?shù)

從計算結(jié)果可以看到，對于圖像序列1和圖像序列2，由于目標(biāo)所在的位置背景比較簡單，信噪比較高，因此除均值位移算法跟蹤效果相對較差外，其它的算法都能實(shí)現(xiàn)較好的跟蹤。而對于圖像序列3，由于背景復(fù)雜，信噪比低，只有數(shù)學(xué)形態(tài)學(xué)算法實(shí)現(xiàn)了對小目標(biāo)較好的跟蹤，表現(xiàn)出來優(yōu)良的跟蹤能力。

4 小結(jié)

通過實(shí)驗(yàn)的計算結(jié)果可以看到，采用文中提出的評價方法通過把跟蹤算法的各指標(biāo)進(jìn)行綜合，實(shí)現(xiàn)對跟蹤算法的性能評價。評價的計算方法靈活、合理，對跟蹤算法的評價問題，尤其是對于單憑一項(xiàng)指標(biāo)無法做出判斷的算法的評價，具有較好的參考意義。

[1]高陳強(qiáng)，張?zhí)祢U，李強(qiáng)，等.幾種典型紅外弱小目標(biāo)檢測算法的性能評估[J].重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2010，22(3):386 －391.

[2]周進(jìn)，吳欽章.弱小目標(biāo)跟蹤算法性能評估的研究[J].光電工程，2007，34(1):19－22.

[3]李鵬飛，陳朝武，李曉峰.智能視頻算法評估綜述[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2010，22(2):352－360.

[4]Andrew Cilia. Object tracking using cluster of elastically linked feature trackers[J]. Journal of Electronic Imaging 2008，17(2):023019－1－023019－11.

[5]Ruiming Liu，Erqi Liu，Jie Yang，et al. Automatically detect and track infrared small targets with kernel Fukunaga-Koontz transform and Kalman prediction[J]. APPLIED OPTICS，2007 46(31):7780－7791.

[6]袁廣林，薛模根，韓裕生，等.基于自適應(yīng)多特征融合的mean shift目標(biāo)跟蹤[J].計算機(jī)研究與發(fā)展，2010，47(9):1663－1671.

[7]王相海，方玲玲，叢志環(huán)，等.卡爾曼粒子濾波的視頻車輛跟蹤算法研究[J].中國圖象圖形學(xué)報，2010，15(11):1615－1622.

[8]Cui-yun Li，Hong-bing Ji. Marginalized particle filter based track-before-detect algorithm for small dim infrared target[C]//IEEE.AICI 2009:321－325.

[9]劉獻(xiàn)如，蔡自興，唐王進(jìn).基于SAD與UKF-Mean Shift的主動目標(biāo)跟蹤[J].模式識別與人工智能，2010，23(5):646－652.

[10]艾斯卡爾·艾木都拉，王保柱.恒虛警率PDAF的弱點(diǎn)狀目標(biāo)跟蹤技術(shù)性能分析[J].計算機(jī)工程與應(yīng)用，2009，45(3):168－171.

[11]HU Tao-tao，F(xiàn)AN Xiang，Zhang Yujin，et al. Infrared small target tracking based on SOPC[C]//SPIE. Parallel Processing for Imaging Applications，2011，Vol. 7872:78720U－1－78720U －9.

[12]張杰，唐宏，蘇凱，等，效能評估方法研究[M].北京:國防工業(yè)出版社，2009.

[13]Lyle M，Dawley，Lenore A Marentette，Long A M.Developing a decision model for joint improvised explosive device defeat organization(JIEDDO)proposal selection，ADA 484369[R]. Department of The Air Force Air University，2008.

[14]任彪，樊祥，馬東輝.基于多特征融合與粒子濾波的紅外弱小目標(biāo)跟蹤方法[J].彈箭與制導(dǎo)學(xué)報，2009，29(5):304－307.

[15]Dorin Comaniciu，Visvanathan Ramesh. Mean shift and optical prediction for efficient object tracking[C]//IEEE International Conference on Image Processing，2000:70－73.

[16]薛豐廷，彭鼎祥.紅外跟蹤系統(tǒng)中的自適應(yīng)閾值分割[J].激光與紅外，2008，38(4):386 －388.