王彥芳, 馮 琦, 鄧秀劍

(1.西北工業(yè)大學(xué) 電子信息學(xué)院， 西安 710072；2. 航空電子系統(tǒng)綜合技術(shù)重點(diǎn)實(shí)驗(yàn)室， 上海 200233)

基于幾何差異的目標(biāo)識(shí)別算法

王彥芳1, 馮 琦1, 鄧秀劍2

(1.西北工業(yè)大學(xué) 電子信息學(xué)院， 西安 710072；2. 航空電子系統(tǒng)綜合技術(shù)重點(diǎn)實(shí)驗(yàn)室， 上海 200233)

為降低目標(biāo)識(shí)別算法復(fù)雜性且提高其抗噪能力,提出一種基于幾何特征差異的目標(biāo)識(shí)別算法；將獲取到的目標(biāo)圖片經(jīng)圖像處理后提取輪廓，并以最小周長(zhǎng)多邊形算法構(gòu)造目標(biāo)輪廓的近似多邊形;然后根據(jù)模板庫(kù)標(biāo)準(zhǔn)目標(biāo)做放大或縮小處理后使其面積與模板面積相等；再使用擺放算法使其與模板庫(kù)圖形部分重合；并提出一種改進(jìn)型雙向鏈表算法求多邊形相交部分，通過計(jì)算相交部分面積大小達(dá)到識(shí)別圖像的目的；經(jīng)過仿真實(shí)驗(yàn)驗(yàn)證了此方法簡(jiǎn)單易行，能夠快速識(shí)別目標(biāo)。

目標(biāo)識(shí)別；多邊形擬合；多邊形相交面積；雙向鏈表

0 引言

利用形狀特征來描述物體并加以識(shí)別是復(fù)雜背景下目標(biāo)自動(dòng)識(shí)別技術(shù)的一個(gè)重要研究方向。傳統(tǒng)的識(shí)別方法大都建立在對(duì)目標(biāo)統(tǒng)計(jì)特征提取的基礎(chǔ)之上，而這些統(tǒng)計(jì)特征是經(jīng)過人為的處理變換才能得到，如文獻(xiàn)[1]抽取圖像輪廓，對(duì)曲率進(jìn)行傅里葉變換來得到形狀的特征向量，該方法形狀區(qū)分能力強(qiáng)但是對(duì)噪聲比較敏感;文獻(xiàn)[2]提出一種基于最佳匹配點(diǎn)、利用交比來識(shí)別平面圖形的方法，但是此方法容易因?yàn)閭€(gè)別點(diǎn)匹配位置錯(cuò)誤而導(dǎo)致不能識(shí)別目標(biāo)量；文獻(xiàn)[3]提出一種基于k聚類分析法的目標(biāo)識(shí)別算法，但是該方法精度不高，只能對(duì)具體數(shù)據(jù)進(jìn)行分析而不能增加新的數(shù)據(jù)對(duì)象。

本文直接利用目標(biāo)的幾何形狀這一原始幾何特征，克服了統(tǒng)計(jì)特征識(shí)別目標(biāo)處理復(fù)雜、易受噪聲影響等缺點(diǎn)，通過目標(biāo)多邊形與模板庫(kù)中多邊形交面積大小達(dá)到識(shí)別目標(biāo)的目的。仿真實(shí)驗(yàn)證明，該方法幾何特征明顯，簡(jiǎn)單高效，提高了識(shí)別的實(shí)時(shí)性。

1 圖像預(yù)處理

在進(jìn)行圖像識(shí)別之前需要對(duì)圖像做一些預(yù)處理，目的是對(duì)系統(tǒng)獲取的原圖像基本特征信息進(jìn)行相應(yīng)的、有針對(duì)性的處理，以濾除干擾噪聲，突出下一步圖像識(shí)別中所關(guān)注的邊緣信息。其過程主要包括圖像灰度化、圖像平滑、圖像濾波、圖像增強(qiáng)、圖像邊緣檢測(cè)以及多邊形逼近。

圖像灰度化是將彩色圖像轉(zhuǎn)換成灰度圖像，以提高圖像的處理速度;圖像平滑是壓制和削弱突變和噪聲,一般采用鄰域平均法[4];圖像濾波主要采用中值濾波，可有效消除孤立噪聲點(diǎn)干擾，而且能很好地保留圖像邊緣輪廓，有利于后續(xù)圖像的識(shí)別;圖像增強(qiáng)主要是改善圖像視覺效果，有目的地強(qiáng)調(diào)圖像整體或局部特性;圖像邊緣檢測(cè)的目的是標(biāo)識(shí)數(shù)字圖像中變化明顯的點(diǎn),大幅度減少數(shù)據(jù)量，盡量只保留圖像重要的結(jié)構(gòu)屬性;多邊形逼近的目的是去除邊緣輪廓中小區(qū)域的凹凸不平對(duì)待識(shí)別目標(biāo)形狀的影響,可采用最小周長(zhǎng)多邊形算法[5]得到目標(biāo)輪廓近似多邊形，達(dá)到簡(jiǎn)化識(shí)別目標(biāo)主體輪廓并減少后續(xù)識(shí)別復(fù)雜度的目的。

通過以上圖像預(yù)處理，就得到了待識(shí)別目標(biāo)的輪廓多邊形。

2 輪廓多邊形的相關(guān)處理

2.1 相似性變換

實(shí)際中獲取的輪廓多邊形通常與模板庫(kù)中的多邊形大小不同，與其對(duì)應(yīng)的標(biāo)準(zhǔn)圖形輪廓多邊形有相似的關(guān)系，所以在比較之前要對(duì)輪廓多邊形做放大或縮小處理，使其面積與模板庫(kù)中所進(jìn)行比較的多邊形面積一致，假設(shè)圖1中多邊形A表示獲取的輪廓多邊形，多邊形B表示模板庫(kù)中多邊形，要將多邊形A放大至與B面積相等，其具體步驟如下：

步驟 1：計(jì)算多邊形A與多邊形B的面積SA、SB。多邊形A,B的相似比為k(B/A)。

步驟 2：從平面上任取一點(diǎn)O，連接該點(diǎn)與多邊形A的各頂點(diǎn)，計(jì)算每條連線長(zhǎng)度li(i=1,2,3,4,5),將其按遠(yuǎn)離O的方向延長(zhǎng)(當(dāng)k<1時(shí)在O與頂點(diǎn)連線上取點(diǎn))使得Li=k*li，得到點(diǎn)B1、B2、B3、B4。

步驟 3：連接點(diǎn)B1、B2、B3、B4即得到放大(或縮小)后的多邊形。

圖1 多邊形相似變換過程

2.2 多邊形重疊方式選擇

將進(jìn)行放大或縮小后的輪廓多邊形與模板庫(kù)中的多邊形一一重合以計(jì)算其相交面積。多邊形重合方式有無數(shù)種，在識(shí)別時(shí)需要從中選擇最合適的重合方式。顯然當(dāng)兩個(gè)多邊形面積相等時(shí)，相交面積越大，兩個(gè)多邊形相同的可能性越大。本節(jié)算法采用一種基于重心距離限定[6]的多邊形擺放方式。算法流程如下。

輸入：經(jīng)過相似多邊形處理后的多邊形A的頂點(diǎn)坐標(biāo)Ai(i=1,2,…,n)，模板庫(kù)多邊形B的頂點(diǎn)坐標(biāo)Bj(j=1,2,…,k)(n、k表示多邊形的頂點(diǎn)個(gè)數(shù))。

輸出：調(diào)整擺放位置后的多邊形。

步驟 1：計(jì)算多邊形A的重心OA以及多邊形B的重心坐標(biāo)OB。

步驟 2：對(duì)多邊形A,B做如下處理：

多邊形A做旋轉(zhuǎn)平移處理得到Ai,j,使得A第j條邊與B的第i條邊重疊且中點(diǎn)重合；

計(jì)算這種擺放方式下的重心距離di,j;

設(shè)置重心閾值d*；

If(di,j

從幾何知識(shí)可以知道，當(dāng)i=p,j=q時(shí)，若相交面積達(dá)到最大值，dp,q將相應(yīng)地較小。相反，若dr,s比較大，那么相交面積將較小,如圖2。

圖2 多邊形擺放方式選擇

用集合Г表示多邊形各種合適的擺放方式的集合，Г=[(i,j)|(i,j)∈(1,…,n)×(1,…,k),di,j≤d*]，即可以利用d*從空間{1,…,n}×{1,…,k}中選取Г恰當(dāng)?shù)淖蛹?，后續(xù)計(jì)算中只需計(jì)算集合Г內(nèi)各情況的相交面積，這樣只需計(jì)算少量情況下的相交面積就可以找出所要識(shí)別的目標(biāo)，大大減少了計(jì)算復(fù)雜度，提高了處理的實(shí)時(shí)性。

3 多邊形交集求取

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，而雙向鏈表主要特點(diǎn)是它的每個(gè)數(shù)據(jù)節(jié)點(diǎn)都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表任意一個(gè)節(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)和后繼節(jié)點(diǎn)。利用此結(jié)構(gòu)可以確定每一點(diǎn)和相鄰兩點(diǎn)間的關(guān)系，便于實(shí)現(xiàn)交點(diǎn)的快速插入。本節(jié)對(duì)文獻(xiàn)[7]中的算法進(jìn)行改進(jìn)，使算法適用于所有相交多邊形。

算法基本思想是將兩多邊形頂點(diǎn)按逆時(shí)針方向分別依次放入雙向鏈表中，從一個(gè)是入點(diǎn)[8]的交點(diǎn)處逆向行進(jìn)，當(dāng)碰到交點(diǎn)時(shí)，對(duì)交點(diǎn)類型進(jìn)行判斷以確定是沿原鏈表繼續(xù)向前還是轉(zhuǎn)至另一多邊形鏈表，如此依次判斷直至回到初始入點(diǎn)，即得到多邊形的一個(gè)交。再?gòu)氖Ｓ辔幢闅v交點(diǎn)選取一個(gè)入點(diǎn)重復(fù)上述操作，直至所有交點(diǎn)都被遍歷。對(duì)于多邊形邊重合的情況，只考慮相交部分兩端點(diǎn)為相交點(diǎn)。以圖3圖形為例說明該算法，具體步驟如下：

輸入：兩多邊形A、B逆時(shí)針頂點(diǎn)序列{A1,A2,A3,A1}，{B1,B2,…，B8，B1}。

輸出：兩多邊形的相交部分逆時(shí)針方向坐標(biāo)。

步驟 1:A1,A2,A3,A1→A鏈表；

B1,B2,B3,B4B5,B6,B7,B8,B1→B鏈表。

步驟 2:交點(diǎn)插入鏈表具體步驟如下：

定義交點(diǎn)個(gè)數(shù)CountI,并賦值為0；

for(i=1;i<4;i++)

for(j=1;j<9;j++)

{If(多邊形A的第i條邊與B的第j條邊相交)

判斷交點(diǎn)個(gè)數(shù)賦值給CountI；

If(CountI==1)

{求出交點(diǎn)I坐標(biāo)；

將I插入到A鏈表第i個(gè)點(diǎn)與第i+1個(gè)點(diǎn)之間；

將I插入到B鏈表第j個(gè)點(diǎn)與第j+1個(gè)點(diǎn)之間；}

Else if(CountI>1) {求出交線的兩端點(diǎn)I1、I2，其中I1靠近第i個(gè)頂點(diǎn);

將I1、I2插入到A鏈表第i個(gè)點(diǎn)與第i+1個(gè)點(diǎn)之間；

將I1、I2插入到B鏈表第j個(gè)點(diǎn)與第j+1個(gè)點(diǎn)之間；}

}

最后得到A鏈表：A1,I10,I6,I5,I1,A2,I2(B2),I3(B3)，I4,I7(B6),A3(I8)(B7),I9,A1;B鏈表：B1,I1,I2(B2),I3(B3),B4,I4,I5,B5,I6,B6(I7),B7(I8),B8,I9,I10,B1

步驟 3：選取由A逆時(shí)針進(jìn)入B的入點(diǎn)(如選擇I1)對(duì)兩鏈表進(jìn)行遍尋求兩多邊形交集過程如下：

從I1開始，沿A鏈表行進(jìn)；

執(zhí)行如下判斷：

If(遍歷到入點(diǎn)交點(diǎn))

{If(交點(diǎn)是原多邊形頂點(diǎn))

{If(交點(diǎn)也是另一多邊形頂點(diǎn))

{沿原多邊形鏈表繼續(xù)行進(jìn)至下一交點(diǎn)即重疊線段末端；

If(逆時(shí)針走向時(shí)交點(diǎn)相對(duì)于另一多邊形為入點(diǎn))

沿原多邊形鏈表繼續(xù)遍歷；

Else 轉(zhuǎn)至沿另一多邊形鏈表遍歷；}

Else 轉(zhuǎn)至沿另一多邊形鏈表遍歷；}

Else沿原多邊形鏈表繼續(xù)行進(jìn)；}

Else 繼續(xù)遍歷尋找入點(diǎn)交點(diǎn)；

步驟 4：檢測(cè)是否所有交點(diǎn)均已被遍歷，若否，則從未遍歷的交點(diǎn)中選取一入點(diǎn)，按以上步驟繼續(xù)遍歷，直至所有交點(diǎn)均被遍歷，輸出相交多邊形，算法結(jié)束。如圖3，I6是由多邊形B進(jìn)入多邊形A的入點(diǎn)，故從I6開始先沿B鏈表遍歷，到達(dá)I7，I7、B6、A3三點(diǎn)合一，判斷知兩多邊形存在邊部分重合，沿鏈表B繼續(xù)行進(jìn)，至I8，I8是由多邊形B到A的出點(diǎn)，故轉(zhuǎn)入A鏈表，沿A遍歷，按上述步驟直至起始入點(diǎn)I6，得到點(diǎn)I6,B6(I7),A3(I8)(B7),I9,I10,I6，依次連接得到另一相交多邊形，輸出相交多邊形，算法結(jié)束。

圖3 改進(jìn)型雙向鏈表求交集

4 實(shí)例仿真

為了驗(yàn)證上文所提算法的可行性，在VC++6.0平臺(tái)上對(duì)不同目標(biāo)進(jìn)行了大量識(shí)別仿真實(shí)驗(yàn)。圖4為其中部分仿真輪廓匹配圖，表列出了圖目標(biāo)輪廓匹配時(shí)的相交邊、重心距離以及相交面積。其中項(xiàng)目1重合邊、2重合邊表示多邊形1與多邊形2相重合的邊在各多邊形中所處的位置。從圖表中可以看到，重心距離與相交面積的關(guān)系基本符合重心距離越小相交面積越大，從而證明了擺放算法的可行性；對(duì)于真正匹配的圖像在擺放方式正確情況下其相交面積遠(yuǎn)遠(yuǎn)大于其他匹配圖形相交面積，如圖表中(b4)面積遠(yuǎn)大于其他匹配圖形面積，則(b4)對(duì)應(yīng)模板庫(kù)中的目標(biāo)就是所要尋找的目標(biāo)。從仿真可以看出，此算法能夠正確識(shí)別目標(biāo)。

5 結(jié)束語

本文所提算法對(duì)飛機(jī)、艦船甚至手勢(shì)等目標(biāo)都可以進(jìn)行識(shí)別，在識(shí)別過程中利用雙向鏈表每一節(jié)點(diǎn)處都可方便訪問前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)的結(jié)構(gòu)特點(diǎn)存儲(chǔ)目標(biāo)輪廓多邊形與模板庫(kù)目標(biāo)多邊形交集頂點(diǎn)，從而得到交集多邊形，最終通過交集面積的比較來確定所要識(shí)別的目標(biāo)。整個(gè)過程簡(jiǎn)便易操作，并且克服了統(tǒng)計(jì)特征識(shí)別的不利影響。

圖4 目標(biāo)輪廓匹配圖

[1] Elghazal A, Basir O, Belkasim S. A novel curvature-based shape Fourier descriptor[A].15thIEEE international Conference on Image Processing[C].2008:953-956.

[2] 周秀芝，劉 方，王潤(rùn)生. 利用局部不變特征識(shí)別復(fù)雜平面多邊形[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003,15(7)：858-862.

[3] 國(guó)新毅. 高速自動(dòng)化灌裝線上視覺檢驗(yàn)系統(tǒng)研究[D].濟(jì)南：山東大學(xué)，2009.

[4] 滕召榮，蔣天發(fā). 鄰域平均法對(duì)矢量圖平滑處理[J].現(xiàn)代電子技術(shù)，2009(14)：75-77.

[5] 何東健.數(shù)字圖像處理[M].西安:西安電子科技大學(xué)出版社，2003.

[6] Kashyap R L，Oommen B J.A Geometrical Approach to Polygonal Dissimilarity and Shape Matching [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1982, 4 (6)：649-654.

[7] 宋立明，閆浩文，王邦松,等.兩個(gè)簡(jiǎn)單多邊形求交的算法[J]. 測(cè)繪與空間地理信息，2011,34(6)：258-260.

[8] 何 研.2-D不規(guī)則多邊形演化布局求解的干涉量計(jì)算研究[D].湘潭：湘潭大學(xué)，2011.

A New Target Recognition Algorithm Based on Geometric Difference

Wang Yanfang1, Feng Qi1, Deng Xiujian2

(1.School of Electronic Information，Northwestern Polytechnic University，Xi’an 710072，China;2.Science and Technology on Avionics Integration Laboratory，Shanghai 200233，China)

In order to reduce the complexity of the target recognition and improve their noise immunity, a geometric-difference based recognition method is presented. First, exact contour of target picture after image processing, and construct approximate polygon outline of target image using a minimum perimeter polygon method. Then zoom in the two polygons according to standard targets in template library to get the same area. And make target contour parts overlap with standard contour using the placement algorithm. After that, we introduced a new algorithm called modified two-way chain table algorithm to get intersection area, and recognized the target according to intersecting area. The simulation experiments show that this method is simple and can quickly identify the target.

target recognition; polygon fitting; polygon intersecting area; doubly linked list

2015-08-18；

2015-10-26。

航空科學(xué)基金資助項(xiàng)目(20145553028)；西北工業(yè)大學(xué)研究生創(chuàng)意創(chuàng)新種子基金(22016126)。

王彥芳(1991-)，女，山東濟(jì)寧人，碩士研究生，主要從事航空火力控制及目標(biāo)識(shí)別方向的研究。

1671-4598(2016)07-0156-03

10.16526/j.cnki.11-4762/tp.2016.07.041

TP301 文獻(xiàn)標(biāo)識(shí)碼：A