基于AHP的跟蹤算法性能評(píng)價(jià)研究*

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

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

0 引言

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

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

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

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

1.1 跟蹤準(zhǔn)確度

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

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

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

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

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

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

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

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

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

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

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

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

2 算法性能的綜合計(jì)算

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

圖1 跟蹤算法性能評(píng)價(jià)內(nèi)容

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

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

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

根據(jù)AHP法，首先需要構(gòu)造權(quán)重判斷矩陣，以區(qū)分各個(gè)指標(biāo)的權(quán)重。在構(gòu)造判斷矩陣時(shí)，要根據(jù)實(shí)際情況選擇合適的標(biāo)度法，由決策者直接通過(guò)對(duì)指標(biāo)兩兩比較得到，常見(jiàn)的標(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)度法等級(jí)量化表

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

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

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

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

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

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

第二步，計(jì)算Mi的n次方根:

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

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

2.3 一致性檢驗(yàn)

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

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

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

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

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

表3 RI的取值表

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

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

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

2.5 計(jì)算綜合評(píng)價(jià)分?jǐn)?shù)

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

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

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

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

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

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

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

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

圖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為由各個(gè)實(shí)驗(yàn)得到的數(shù)據(jù)根據(jù)本章提出的評(píng)價(jià)方法計(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ù)計(jì)算得到的指標(biāo)分?jǐn)?shù)

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

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

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

4 小結(jié)

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

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

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

[3]李鵬飛，陳朝武，李曉峰.智能視頻算法評(píng)估綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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ì)算機(jī)研究與發(fā)展，2010，47(9):1663－1671.

[7]王相海，方玲玲，叢志環(huán)，等.卡爾曼粒子濾波的視頻車(chē)輛跟蹤算法研究[J].中國(guó)圖象圖形學(xué)報(bào)，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的主動(dòng)目標(biāo)跟蹤[J].模式識(shí)別與人工智能，2010，23(5):646－652.

[10]艾斯卡爾·艾木都拉，王保柱.恒虛警率PDAF的弱點(diǎn)狀目標(biāo)跟蹤技術(shù)性能分析[J].計(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]張杰，唐宏，蘇凱，等，效能評(píng)估方法研究[M].北京:國(guó)防工業(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é)報(bào)，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.