基于多Agent進化計算的圖像目標識別

周亦鵬，胡 娟，杜軍平

（1.北京工商大學計算機與信息工程學院，北京 100048；2.北京政法職業(yè)學院信息技術(shù)系，北京 100024；3.北京郵電大學計算機學院，北京 100876）

基于多Agent進化計算的圖像目標識別

周亦鵬1，胡 娟2，杜軍平3

（1.北京工商大學計算機與信息工程學院，北京 100048；2.北京政法職業(yè)學院信息技術(shù)系，北京 100024；3.北京郵電大學計算機學院，北京 100876）

對圖像的多目標識別問題進行研究，提出一種基于Agent進化計算的目標識別方法。該方法通過Agent和Agent群體的協(xié)同進化完成對樣本圖像集的快速搜索和模板匹配。同時，針對目標遮擋的問題，利用遮擋圓來構(gòu)造模板，實現(xiàn)對遮擋目標的識別。實驗結(jié)果表明，提出的方法實現(xiàn)了平移不變、旋轉(zhuǎn)不變、尺度不變、鏡像不變的識別，而且能夠準確地確定出遮擋區(qū)域的位置和遮擋區(qū)域的大小，同時也大大減小了模板匹配的計算量。

圖像處理；目標識別；Agent；進化計算

0 引言

計算機視覺研究中的一個熱點問題是圖像的目標識別，它的主要任務是通過自動化的方法，在不需要或盡可能少的人工干預情況下，由計算機系統(tǒng)自動識別出圖像中出現(xiàn)的特定目標。圖像目標識別算法大致可以分為基于模板的方法、基于特征的方法和基于三維模型的方法3類［1-3］。其中，基于模板的方法具有較強的抗噪性，對目標的識別具有平移不變性、尺度不變性等特點，但是計算量相對較大。

因此，本文把模板匹配的思想和多Agent進化計算［4-5］結(jié)合起來，在實現(xiàn)目標識別的同時，減少模板匹配的計算量，提高計算效率。

同時，針對遮擋目標識別的問題，考慮到遮擋位置和遮擋區(qū)域大小的隨機性，以及無法預知遮擋區(qū)域的輪廓、紋理等特征，本文提出一種采用遮擋模板的方法來解決遮擋目標識別題，利用Agent構(gòu)造遮擋模板，在待測圖像中同時搜索遮擋目標和遮擋區(qū)域。

1 基于模板匹配的圖像目標識別

基于模板匹配的目標識別方法，其優(yōu)點在于不需要掌握圖像內(nèi)容的知識，只要有實際的目標圖像數(shù)據(jù)即可，而且能夠保持目標的原始信息。

基于模板的方法根據(jù)模板在匹配過程中是否發(fā)生變形可以分為剛性模板和變形模板兩類。剛性模板是指模板一旦構(gòu)造完成就不再發(fā)生變化，模板匹配過程中，只能將模板進行旋轉(zhuǎn)、縮放等形式的變換，這些變換過程中，模板內(nèi)各像素間的相對位置要保持不變且不產(chǎn)生任何形變。而變形模板的形狀則能夠根據(jù)測度函數(shù)發(fā)生變化，目的是使其與目標的形狀更為接近。

雖然變形模板能夠適應不同形狀的目標，但是構(gòu)造變形模板需要大量的先驗知識，因此很多目標識別問題并不適用。而且，多數(shù)變形模板的構(gòu)造僅依賴于目標的輪廓信息，沒有充分利用顏色、紋理等其它特征信息，也影響了識別準確性。剛性模板則幾乎不需要先驗知識，而且能充分地利用目標自身的各種特征，即使是在目標受到部分遮擋的情況下，仍然可以通過未遮擋區(qū)域的特征進行識別。

因此，本文采用剛性模板實現(xiàn)目標匹配，將同一類目標的多個樣本的平均圖像作為模板，從而使同一類型的各個目標均能夠獲得較高的匹配度。具體方法是：從多個樣本圖像中剪切出目標的所在區(qū)域，獲得多個目標圖像，并通過插值獲得統(tǒng)一的尺度，然后將所有目標圖像的灰度值進行標準化。設目標圖像I的灰度矩陣為I［W］［H］（W 為圖像的寬度，H為高度），計算其均值和方差：

將圖像I的灰度值標準化到（μ0，σ0）：

最后求所有目標圖像的灰度的平均值，重采樣后就得到模板圖像。

模板匹配過程是將模板在待測圖像上逐點進行平移，依次計算模板與其所覆蓋的區(qū)域之間的相似度，找出匹配度最高的位置，即要尋找的目標。

設模板T的尺寸為TW×TH，待測圖像I的尺寸為W×H（通常TW ＜W，TH ＜H）。待測圖像I被模板T所覆蓋的區(qū)域稱為子圖S（i，j），其中（i，j）為子圖的中心坐標。目標識別過程就是在整幅待測圖像中尋找與模板T最為相似的子圖S（i，j）。但是，如果采用遍歷搜索，將模板與所有子圖進行比較，則搜索過程的計算量將十分巨大，因此必須設計有效的方法來降低搜索空間，提高搜索效率。

2 多Agent進化計算

2.1 多Agent進化計算系統(tǒng)的結(jié)構(gòu)

基于模板匹配的圖像目標識別實質(zhì)上是一個組合優(yōu)化問題，從而能夠以較少的計算量獲得最優(yōu)的解決方案。進化計算是解決此類問題的常用方法［6-8］，但隨著圖像識別難度和復雜度的提高，存在進化緩慢、易于早熟、搜索效率不高等缺點。因此，本文提出一種基于Agent的進化計算方法，利用Agent的智能性、自主性和協(xié)作能力［9-10］，將其與進化計算方法相結(jié)合，以提高目標識別的準確度和計算效率。

基于Agent的進化計算將進化過程中的每個個體作為一個Agent，所有Agent構(gòu)成一個群體。同時，一個群體可以進一步劃分為若干個子群體。所有子群體分為優(yōu)勝子群體和臨時子群體兩類，優(yōu)勝子群體由全局競爭過程中勝出的Agent構(gòu)成，臨時子群體則包括競爭過程中的其它Agent，如圖1所示。

不同于傳統(tǒng)的進化計算方法，本文在Agent進化過程中采用“趨同”和“異化”算子。趨同的作用是在子群體內(nèi)快速搜索局部最優(yōu)解，然后在各個子群體中選出當前的優(yōu)勝子群體。異化操作是通過重構(gòu)子群體，從而在整個解空間中探索全局最優(yōu)的個體。

系統(tǒng)中的Agent通過公告板實現(xiàn)交互與通信，其中局部公告板用于子群體內(nèi)Agent間的通信，全局公告板則用于各子群體間的通信。公告板包含Agent個體或子群體的序號（No.）、動作（Action）和得分（Score）等信息。其中，Agent的動作與具體的領域有關，在目標識別領域，動作可以是Agent在待測圖像中所處的位置及其下一步的搜索方向；得分則是對Agent動作執(zhí)行效果的評價。

此外，系統(tǒng)通過特征提取F-Agent對個體Agent的動作和得分進行分析，從中提取環(huán)境信息，從而指導異化操作的進行。

圖1 多Agent進化計算系統(tǒng)結(jié)構(gòu)Fig.1 Architecture of multi-agent evolution systen

2.2 趨同和異化

Agent進化計算過程中包含趨同和異化兩個重要的操作，其中趨同是局部搜索，異化是全局搜索。

子群體中的各個Agent為成為子群體內(nèi)的優(yōu)勝者而競爭的過程叫做趨同。當一個子群體內(nèi)不再產(chǎn)生新的優(yōu)勝Agent時，則稱該子群體已經(jīng)成熟，此時趨同過程結(jié)束。

在整個搜索空間內(nèi)，所有子群體也在為成為全局優(yōu)勝者而進行競爭。子群體通過重構(gòu)來不斷地探索新的空間，從而成為新的優(yōu)勝子群體，這個過程叫做異化。異化包含兩種情況：1）若某個臨時子群體的得分高于成熟的優(yōu)勝子群體的得分，則該臨時子群體成為新的優(yōu)勝子群體，并且釋放原優(yōu)勝子群體中的Agent；若某個成熟的臨時子群體的得分低于優(yōu)勝子群體，則釋放該臨時子群體中的Agent。2）被釋放的Agent在整個搜索空間內(nèi)重新進行散布并形成新的臨時群體。

初始情況下，所有的Agent進行全局搜索，然后以其中得分較高的若干個Agent為中心形成多個初始子群體。之后趨同和異化操作在進化過程中反復交替進行。

與傳統(tǒng)進化計算相比，基于Agent的進化計算將群體劃分為子群體，類似于小生境環(huán)境，更易于并行實現(xiàn)。

3 多Agent圖像目標識別

3.1 基于多Agent的圖像目標識別過程

本文采用多Agent進化計算與模板匹配相結(jié)合的方法識別目標，從而減少計算代價，并且通過并行計算來提高識別速度。

首先，每個Agent采用一定大小的窗口從待測圖像上剪切一個子圖像，然后將子圖像與模板圖像進行匹配。為了適應目標尺度大小和旋轉(zhuǎn)角度的變化，Agent需要將窗口內(nèi)的子圖像進行縮放、旋轉(zhuǎn)等處理，然后進行匹配。

因此，每個Agent的窗口W 包括4個參數(shù)：窗口的中心坐標（i，j）、窗口寬度lw和窗口的旋轉(zhuǎn)角度θ。Agent將獲得的窗口子圖像再進行尺度縮放后得到與模板大小相同的待匹配圖像，稱為樣本圖像，記為Si，j，θ，lw（x，y）。

這樣處理的優(yōu)點是：多個Agent群體可以同時搜索多個區(qū)域，與模板圖像進行匹配，既能避免陷入局部最優(yōu)，又能加快處理的速度；通過調(diào)整Agent的窗口參數(shù)，可以對樣本圖像進行平移、旋轉(zhuǎn)、縮放，保持目標識別過程的平移、旋轉(zhuǎn)和縮放不變性。

為了評價樣本圖像和模板之間的匹配度，通過計算模板圖像與樣本圖像色差的累計和來定義評價函數(shù)：

其中，Tuv（x，y）和Suv，i，j，θ，lw（x，y）分別為轉(zhuǎn)換到CIE1976L＊u＊v＊均勻顏色空間上的模板圖像和樣本圖像，TW、TH分別是模板圖像的寬度和高度。u（x，y）、v（x，y）分別為樣本圖像的U＊、V＊值，u（x，y）、v（x，y）分別為模板圖像的U＊、V＊值。

根據(jù)式（4）可以看出，F(xiàn)（i，j，θ，lw）值越小，樣本圖像和模板的匹配度越高。

3.2 遮擋目標的識別

如何識別被遮擋的目標一直是目標識別中最難解決的問題之一。由于遮擋區(qū)域的位置和大小難以預知，同時也無法預先獲得遮擋區(qū)域的輪廓、紋理等輔助信息，因此傳統(tǒng)的模板匹配和特征選擇方法都不能很好地解決這一問題。

本文提出一種采用遮擋模板的遮擋目標識別方法。遮擋模板是將目標的遮擋位置定義為某個圓與模板圖像的相交區(qū)域，然后利用這樣的遮擋模板與樣本圖像進行匹配。通過尋找遮擋圓心、半徑等最優(yōu)的參數(shù)組合來解決目標遮擋問題。使用圓定義遮擋區(qū)域的優(yōu)點為：

1）使用圓和模板的相交區(qū)域來定義遮擋位置，既可以用來描述邊緣遮擋的情況，也可以用來描述孔形遮擋，如圖2所示。此外，如果將遮擋位置定義為圓和模板的相交區(qū)域的補集，則還適用于鏡框遮擋的情況。

2）不論遮擋區(qū)域與目標區(qū)域的相交線為直線還是曲線都可以用圓形遮擋進行描述，圓半徑較大時，相交線可以近似為直線，圓半徑較小時相交線是弧線。

由于遮擋圓的位置和大小不確定，因此在模板匹配過程中需要增加圓心的橫、縱坐標（a，b）和圓半徑（r）3個參數(shù)來確定遮擋模板。這樣，在整個目標識別過程中共有7維參數(shù)來確定受到遮擋的窗口，包括遮擋圓的3維參數(shù)（圓心的橫縱坐標

和圓半徑）和樣本圖像窗口的4維參數(shù)（窗口中心橫縱坐標、窗口的寬度和旋轉(zhuǎn)角）。因此，目標識別過程需要使用多Agent系統(tǒng)在樣本圖像集中進行搜索，獲得這7維參數(shù)的最優(yōu)解，從而達到目標識別的目的。

圖2 使用圓遮擋住模板Fig.2 Template covered by circularity

4 實驗結(jié)果

4.1 一般目標的實驗結(jié)果

采用圖3所示的剛性模板來識別圖4中的多個目標，每個目標分別用字母A-G進行標記。

根據(jù)多Agent進化系統(tǒng)優(yōu)化的結(jié)果，將最優(yōu)的個體（即找到的目標）用方框標示出來。

圖4的7個目標中，識別出A-F共6個目標。可以看出，目標A、B與目標D之間的旋轉(zhuǎn)角度具有很大的差別，這說明了算法具有很好旋轉(zhuǎn)不變性。由于水流和光照的影響，每個目標上具有不同的水紋，而且目標B與其它幾個目標還具有較大的顏色差異，這些目標均能被正確識別，說明算法具有彩色恒定性。但是，由于目標G的一部分被目標E所遮擋，因此沒有識別出來。

圖4中，若采用遍歷法進行識別，則搜索計算量達33 751萬次，而本文方法識別出6個目標共進化79代，評價個體1.59萬次，可見使用多Agent進化計算方法極大減小了計算量。

圖3 模板圖像Fig.3 Template Image

4.2 遮擋目標的實驗結(jié)果

針對前一實驗中目標G因遮擋而未能識別的問題，采用3.2節(jié)提出的遮擋目標識別方法進行實驗，待測圖像的識別結(jié)果如圖5所示，同時得到的遮擋位置如圖6所示。

圖4 待測圖像和識別結(jié)果Fig.4 Test image and recognition result

圖5 遮擋目標的實驗結(jié)果Fig.5 Recognition result of covered object

圖6 目標E和G的差圖像及遮擋圓位置Fig.6 Diffevence images of object E and G and their covered circularity

從實驗中看出，樣本圖像中的目標E在窗口剪切的過程中并沒有完整保留，而目標G也有相當一部分被E所遮擋。從圖5的識別結(jié)果可以看出，使用本文提出的遮擋目標識別方案，兩個目標均能準確地找到，并識別出目標的遮擋位置。

5 結(jié)論

本文提出一種改進的圖像目標識別算法，將基于模板匹配的目標識別方法和性能優(yōu)異的Agent進化計算結(jié)合起來。同時，采用遮擋圓來構(gòu)造遮擋模板，解決了遮擋目標的識別問題。實驗結(jié)果表明，本文算法不但能夠在目標識別過程中保持平移不變性、旋轉(zhuǎn)不變性和尺度不變性，而且能夠有效識別被遮擋的目標并定位遮擋區(qū)域。同時，模板匹配的計算量也大大地減少。

［1］田娟，鄭郁正.模板匹配技術(shù)在圖像識別中的應用［J］.傳感器與微系統(tǒng)，2008，27（1）：112-114，117.

Tian Juan，ZhengYuzheng.Application of template matching technique in image recognition［J］.Transducer and Microsystem Technologies，2008，27（1）：112-114，117.

［2］Roy Kaushik，Bhattacharya Prabir.Iris recognition using genetic algorithms and asymmetricalSVMs［J］.Machine Graphics and Vision，2010，19（1）：33-62.

［3］Zhang Changjiang，Lu Juan.Satellite cloud image enhancement by genetic algorithm with fuzzy technique［C］//2009In-ternational Conference on New Trends in Information and Service Science，NISS2009.Beijing，2009：1090-1095.

［4］姜楠，張春森.遺傳算法在圖像模板匹配中的應用［J］.紅外與激光工程，2008，37（4）：324-327.

Jiang Nan，Zhang Chunsen.Application of genetic algorithm in image matching［J］.Infrared and Laser Engineering，2008，37（4）：324-327.

［5］劉其成，鄭緯民.多Agent并行遺傳算法在地震勘探屬性優(yōu)化中的應用［J］.計算機科學，2010，37（4）：234-237.

Liu Qicheng，Zheng Weimin.Seismic exploration attribute optimization based on multi-agent parallel genetic algorithm［J］.Computer Science，2010，37（4）：234-237.

［6］梁軍，程顯毅.基于混合蟻群遺傳算法的Agent聯(lián)盟求解［J］.計算機科學，2009，36（4）：227-231.

Liang Jun，Cheng Xianyi.Solving method of agent coalition problem based on hybrid ant colony and genetic algorithm［J］.Computer Science，2009，36（4）：227-231.

［7］Ugur A，Korukoglu S，Caliskan A，et al.Genetic algorithm based solution for TSP on a sphere［J］.Mathematical and Computational Applications，2009，14（3）：219-228.

［8］馬永杰，馬義德，蔣兆遠，等.一種快速遺傳算法及其收斂性［J］.系統(tǒng)工程與電子技術(shù)，2009，31（3）：714-718.

Ma Yongjie，Ma Yide，Jiang Zhaoyuan，et al.Fast genetic algorithm and its convergence［J］.Systems Engineering and Electronics，2009，31（3）：714-718.

［9］彭軍，劉亞，吳敏，等.基于狀態(tài)預測的多智能體動態(tài)協(xié)作算法［J］.系統(tǒng)仿真學報，2008，20（20）：5511-5515.

Peng Jun，Liu Ya，Wu Min，et al.Dynamic cooperation algorithm in multi-agent system based on state prediction［J］.Journal of System Simulation，2008，20（20）：5511-5515.

［10］張秋花，薛惠鋒，吳介軍，等.多智能體系統(tǒng)MAS及其應用［J］.計算機仿真，2007，24（6）：133-137.

Zhang Qiuhua，Xue Huifeng，Wu Jiejun，et al.Theory and application of the multi-agent system［J］.Computer Simulation，2007，24（6）：133-137.

Image Object Recognition Based on Multi-Agent Evolutionary Computation

ZHOU Yi-peng1，HU Juan2，DU Jun-ping3
（1.School of Computer Science and Information Engineering，Beijing Technology and Business University，Beijing 100048，China；2.Department of Information Technology，Beijing College of Politics and Law，Beijing 100024，China 3.School of Computer Science，Beijing University of Posts and Telecommunications Beijing，100876，China）

Image objects recognition is studied.A new object recognition method based on Agent evolutionary computation is proposed.In this method，the processes of searching object on sample image set and template matching are all achieved by cooperation of Agent groups.Moreover，to solve the problem of occluded object recognition，a new method using occluding circle to construct template is proposed too.The experimental results show that the proposed method has the features of translation invariance，rotation invariance，scale invariance and mirror invariance，at the same time，the occluded area can be located.Furthermore，the computation amount of template matching is greatly reduced.

image processing；object recognition；Agent；evolutionary computation

TP391.9

A

1672-3813（2013）03-0055-06

2012-12-04

國家重點基礎研究發(fā)展計劃（973計劃）（2012CB821206）；國家自然科學基金（91024001，61070142）；北京市自然科學基金（4111002）

周亦鵬（1976-），男，山西太原人，博士，講師，主要研究方向為智能系統(tǒng)。

（責任編輯 耿金花）