改進(jìn)的基于模型匹配的快速目標(biāo)識(shí)別

孫思佳，閆鈞華，儲(chǔ)林臻，杭誼青

（南京航空航天大學(xué) 航天學(xué)院，江蘇 南京 210016）

數(shù)字圖像的高分辨率使得基于圖像的目標(biāo)識(shí)別數(shù)據(jù)量大，為了快速地識(shí)別目標(biāo)，文中對(duì)基于模型匹配的目標(biāo)識(shí)別算法展開深入研究，采用最小周長多邊形[1]近似來簡化目標(biāo)主體輪廓，構(gòu)造目標(biāo)的近似多邊形，以減少算法處理的數(shù)據(jù)量。在獲得目標(biāo)主體輪廓的近似多邊形的基礎(chǔ)上，本文采用具有仿射不變性的特征不變量：多邊形頂點(diǎn)個(gè)數(shù)、最長線段兩側(cè)頂點(diǎn)個(gè)數(shù)、同底三角形面積比[2-3]向量對(duì)待識(shí)別目標(biāo)進(jìn)行描述。采用同樣的方法建立模型匹配數(shù)據(jù)庫，應(yīng)用3個(gè)特征量逐一進(jìn)行分層遍歷搜索匹配，以提高目標(biāo)識(shí)別的實(shí)時(shí)性。造過程如圖1所示。

圖1 構(gòu)造目標(biāo)主體輪廓的近似多邊形Fig.1 Constructing approximate polygon of the main object contour

1 目標(biāo)輪廓最小周長多邊形近似（MPP）

在目標(biāo)識(shí)別中，待識(shí)別目標(biāo)的輪廓會(huì)有許多較小的凹凸不平的小區(qū)域，其影響對(duì)目標(biāo)主體輪廓形狀的識(shí)別，本文采用最小周長多邊形來構(gòu)造目標(biāo)主體輪廓的近似多邊形[4]。構(gòu)

1）過邊緣檢測獲得目標(biāo)的初始輪廓，如圖1（a）所示。2）用一組級(jí)聯(lián)的方形單元來包圍目標(biāo)的初始輪廓，如圖1（b）所示，這組方形元素的集合稱為“細(xì)胞聯(lián)合體”[5]。細(xì)胞聯(lián)合體所包圍的區(qū)域，如圖1（b）陰影區(qū)域所示，該區(qū)域邊界構(gòu)成了一條4連通區(qū)域。3）獲得陰影區(qū)域邊界的黑、白點(diǎn)，如圖1（c）所示。在邊界上按順時(shí)針方向行進(jìn)，在凸角處（內(nèi)角90度）用一個(gè)黑點(diǎn)表示，在凹角處（內(nèi)角270度）用一個(gè)白點(diǎn)表示。黑點(diǎn)位于凸角本身上，白點(diǎn)位于相應(yīng)凹角的對(duì)角位置。4）將已經(jīng)獲得黑、白點(diǎn)的陰影區(qū)域放置于背景網(wǎng)格上，如圖1（d）所示。5）連接所有的黑點(diǎn)構(gòu)建初始多邊形，如圖1（e）所示。6）去掉初始多邊形邊界外的白點(diǎn)，如圖1（f）所示。7）連接圖1（f）中所有的黑點(diǎn)和白點(diǎn)構(gòu)建多邊形，因?yàn)槌跏级噙呅蝺?nèi)部的白點(diǎn)與多邊形的凸性有關(guān)，所以這些白點(diǎn)必須合并到多邊形中，如圖1（g）所示。多邊形的頂點(diǎn)的內(nèi)角范圍如果為（0°，180°），則定義為凸頂點(diǎn)；如果為（180°，360°），則定義為凹頂點(diǎn)；如果為0°，180°，360°，則既不是凸頂點(diǎn)也不是凹頂點(diǎn)，對(duì)這樣的點(diǎn)保留在多邊形中不作處理。多邊形中的黑點(diǎn)一部分是凸頂點(diǎn)，一部分是凹頂點(diǎn)（如圖1（g）中箭頭標(biāo)示的黑點(diǎn)）。去掉黑點(diǎn)中的凹頂點(diǎn)，這樣可以簡化多邊形的形狀。8）連接剩下的所有的點(diǎn)，如圖1（h）所示。在這個(gè)新的多邊形中有可能出現(xiàn)由凸頂點(diǎn)變成凹頂點(diǎn)的黑點(diǎn)，如圖1（h）中箭頭標(biāo)示的黑點(diǎn)。去掉這樣的點(diǎn)，進(jìn)一步簡化多邊形的形狀。重復(fù)這一過程直到不再出現(xiàn)這樣的點(diǎn)，如圖1（i）所示。9）圖1（i）中的多邊形就是MPP，去掉背景網(wǎng)格和陰影區(qū)域，最終獲得目標(biāo)主體輪廓的近似多邊形，如圖1（j）所示。

2 構(gòu)造特征不變量——同底三角形面積比

在獲得目標(biāo)主體輪廓的近似多邊形的基礎(chǔ)上，文中采用具有仿射不變性的同底三角形面積比作為多邊形的特征不變量。同底三角形面積比的仿射不變性證明如下。

圖2（a）所示空間平面四邊形經(jīng)過仿射變換轉(zhuǎn)換為圖2（b）。

圖2 平行四邊形的仿射變換Fig.2 Affine transformation of parallelogram

仿射變換公式：

圖2（a）四邊形ABCD中有4個(gè)三角形：ΔABC、ΔACD、ΔABD、ΔBCD，其面積分別記為SΔABC、SΔACD、SΔABD、SΔBCD。圖2（b）四邊形abcd中有4個(gè)三角形：Δabc、Δacd、Δabd、Δbcd，其面積分別記為SΔabc、SΔacd、SΔabd、SΔbcd。

由公式（1）所示的仿射變換T={[A]b}可知Δabc和ΔABC面積關(guān)系：

其他3組對(duì)應(yīng)三角形（Δacd和ΔACD、Δabd和ΔABD、Δbcd和ΔBCD）也滿足式（2）。

由此可得底邊同為AC的同底三角形△ACD和△ABC的面積比值如下：

SΔACD/SΔABC=det{[A]}SΔaαl/det{A}SΔabc=SΔaod/SΔabc（3）

由式（3）可知仿射變化前后同底三角形ΔACD和ΔABC的面積比值相等，也可類推出圖2（a）平行四邊形ABCD和2（b）平行四邊形abcd中其他對(duì)應(yīng)同底三角形面積比值相等。由此可得圖2中仿射前后兩個(gè)四邊形的同底三角形的面積比值是相等的，具有仿射不變性。

3 基于模型匹配的目標(biāo)識(shí)別算法

3.1 建立模型匹配數(shù)據(jù)庫

通過CAD建立目標(biāo)模型，構(gòu)造模型的全方位姿態(tài)圖，對(duì)姿態(tài)圖進(jìn)行預(yù)處理與邊緣檢測獲得目標(biāo)的初始輪廓，采用最小周長多邊形構(gòu)造目標(biāo)主體輪廓的近似多邊形，進(jìn)行特征提取獲得多邊形的特征不變量：多邊形頂點(diǎn)個(gè)數(shù)（Cntm）、最長線段兩側(cè)頂點(diǎn)個(gè)數(shù)（Cntm1、Cntm2）、同底三角形面積比向量（Dml、Dm2）。

3.2 目標(biāo)識(shí)別算法流程

算法詳細(xì)實(shí)現(xiàn)步驟為：1）建立模型匹配數(shù)據(jù)庫。2）獲得待識(shí)別目標(biāo)的多邊形的特征不變量。3）利用待識(shí)別目標(biāo)的多邊形頂點(diǎn)個(gè)數(shù)（Cntm）特征量在模型匹配數(shù)據(jù)庫中進(jìn)行搜索匹配，獲得符合匹配的第1層數(shù)據(jù)子庫。4）利用待識(shí)別目標(biāo)的最長線段兩側(cè)頂點(diǎn)個(gè)數(shù)（Cntm1、Cntm2）特征量在第1層數(shù)據(jù)子庫中進(jìn)行搜索匹配，獲得符合匹配的第2層數(shù)據(jù)子庫。5）利用待識(shí)別目標(biāo)的同底三角形面積比向量（Dml、Dm2）特征量在第2層數(shù)據(jù)子庫中進(jìn)行搜索匹配。如果待識(shí)別目標(biāo)與模型之間的特征量的歐氏距離小于閾值（e），則符合匹配完成目標(biāo)識(shí)別。如果大于閾值，則不符合匹配未完成目標(biāo)識(shí)別。目標(biāo)識(shí)別算法流程如圖3所示。歐氏距離可表達(dá)如下：

圖3 目標(biāo)識(shí)別算法流程圖Fig.3 Flowchart of object recognition algorithm

其中，模型庫中模型的同底三角形面積比向量為（Dml、Dm2），待識(shí)別目標(biāo)的同底三角形面積比向量為（Db1，Db2）。在搜索匹配過程中需要注意一個(gè)特殊情況：待識(shí)別目標(biāo)的最長線段兩側(cè)頂點(diǎn)個(gè)數(shù)相等即cntm1=cntm2。此時(shí)，歐氏距離為：

DT=Min{Max（|Dm1-Db1|，|Dm2-Db2|），Max（|Dm1-Db2|，|Dm2-Db1|）} （5）

4 實(shí)驗(yàn)結(jié)果

待識(shí)別目標(biāo)如圖4所示，圖4（c）是采用最小周長多邊形構(gòu)造的待識(shí)別目標(biāo)的近似多邊形，應(yīng)用CPDA[6]角點(diǎn)提取法（Chord-to-Point Distance Accumulation）提取出近似多邊形的關(guān)鍵角點(diǎn)，即為多邊形的頂點(diǎn)，如圖中的小正方形所示。

圖4 待識(shí)別目標(biāo)Fig.4 The object to be recognized

文中建立了幾種不同類型交通工具的模型匹配數(shù)據(jù)庫，分別為兩輪車、四輪汽車、飛機(jī)、坦克這4個(gè)大類，每種類型的模型中還有幾種不同的小類。從每種大類中抽取兩種小類（由于坦克的特殊性只抽取了一種小類），再從每種小類中抽取兩個(gè)姿態(tài)（側(cè)面20度和側(cè)面60度）。對(duì)待識(shí)別目標(biāo)進(jìn)行目標(biāo)識(shí)別實(shí)驗(yàn)，如圖5所示。文中基于模型匹配的目標(biāo)識(shí)別算法進(jìn)行特征量比對(duì)如表1所示。

圖5 模型庫Fig.5 Template database

表1 特征量比對(duì)表Tab.1 Comparison table of features

實(shí)驗(yàn)結(jié)果為：在閾值e＝0.5時(shí)，待識(shí)別目標(biāo)與飛機(jī)類中的戰(zhàn)斗機(jī)側(cè)面20度的姿態(tài)匹配，因此待識(shí)別目標(biāo)被識(shí)別為戰(zhàn)斗機(jī)，實(shí)驗(yàn)數(shù)據(jù)如表1所示。識(shí)別時(shí)間都為十秒的量級(jí)，而現(xiàn)在許多成熟的識(shí)別算法時(shí)間都在分鐘級(jí)，實(shí)驗(yàn)表明本文目標(biāo)識(shí)別算法速度較快；本算法對(duì)各目標(biāo)姿態(tài)的特征多邊形頂點(diǎn)個(gè)數(shù)不同的情況，仍有較高的識(shí)別率；且本算法采用近似多邊形過濾掉了不能表征目標(biāo)主要形狀的偽角點(diǎn)和細(xì)節(jié)輪廓，增加了目標(biāo)識(shí)別的穩(wěn)定性。

5 結(jié)束語

文中建立了模型匹配數(shù)據(jù)庫，采用了最小周長多邊形構(gòu)造目標(biāo)主體輪廓的近似多邊形，提取了多邊形頂點(diǎn)個(gè)數(shù)、最長線段兩側(cè)頂點(diǎn)個(gè)數(shù)、同底三角形面積比向量特征不變量對(duì)待識(shí)別目標(biāo)進(jìn)行模型匹配。實(shí)驗(yàn)表明，基于模型匹配的目標(biāo)識(shí)別算法能夠快速的識(shí)別目標(biāo)，提高了目標(biāo)識(shí)別的實(shí)時(shí)性，同時(shí)能夠判定目標(biāo)所處的姿態(tài)狀況。本算法適用于目標(biāo)背景簡單，對(duì)于背景復(fù)雜的情況，需要改進(jìn)算法提高識(shí)別魯棒性。

[1]Gonzalez R C，Woods R E，Eddins S L.Digital image processing using MATLAB[M].阮秋琦等譯.北京：電子工業(yè)出版社，2005.

[2]趙軍.基于飛機(jī)模型的飛機(jī)識(shí)別方法研究[D].西安：西北工業(yè)大學(xué)機(jī)電學(xué)院，2004.

[3]趙軍.基于同底三角形面積比的飛機(jī)外形識(shí)別方法研究[J].蘭州交通大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，24（3）：94－97..ZHAO Jun.Recognizing Aircraft based on triangle area ratio of the same hemline[J].Journal of Lanzhou Jiaotong University：Natrual sciences，2005，24（3）：94－97.

[4]Kushner T，Wu A Y，Rosenfeld A.Image processing on MPP[J].Pattern Recogni-tion，1982，15（3）：121－130.

[5]Kim C E，Skalansky J.Digital and c-ellular convexity[J].Pattern Recognition，1982，15（5）：359－367.

[6]Awrangje M，Lu G.Robust image corner detection based on the chord-to-point distance accumulation technique[J].IEEE Trans Multimedia，2008，10（6）：1059－1072.