改進的基于模型匹配的快速目標識別

孫思佳，閆鈞華，儲林臻，杭誼青

（南京航空航天大學 航天學院，江蘇 南京 210016）

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

圖1 構造目標主體輪廓的近似多邊形Fig.1 Constructing approximate polygon of the main object contour

1 目標輪廓最小周長多邊形近似（MPP）

在目標識別中，待識別目標的輪廓會有許多較小的凹凸不平的小區域，其影響對目標主體輪廓形狀的識別，本文采用最小周長多邊形來構造目標主體輪廓的近似多邊形[4]。構

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

2 構造特征不變量——同底三角形面積比

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

圖2（a）所示空間平面四邊形經過仿射變換轉換為圖2（b）。

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

仿射變換公式：

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

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

其他3組對應三角形（Δ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中其他對應同底三角形面積比值相等。由此可得圖2中仿射前后兩個四邊形的同底三角形的面積比值是相等的，具有仿射不變性。

3 基于模型匹配的目標識別算法

3.1 建立模型匹配數據庫

通過CAD建立目標模型，構造模型的全方位姿態圖，對姿態圖進行預處理與邊緣檢測獲得目標的初始輪廓，采用最小周長多邊形構造目標主體輪廓的近似多邊形，進行特征提取獲得多邊形的特征不變量：多邊形頂點個數（Cntm）、最長線段兩側頂點個數（Cntm1、Cntm2）、同底三角形面積比向量（Dml、Dm2）。

3.2 目標識別算法流程

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

圖3 目標識別算法流程圖Fig.3 Flowchart of object recognition algorithm

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

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

4 實驗結果

待識別目標如圖4所示，圖4（c）是采用最小周長多邊形構造的待識別目標的近似多邊形，應用CPDA[6]角點提取法（Chord-to-Point Distance Accumulation）提取出近似多邊形的關鍵角點，即為多邊形的頂點，如圖中的小正方形所示。

圖4 待識別目標Fig.4 The object to be recognized

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

圖5 模型庫Fig.5 Template database

表1 特征量比對表Tab.1 Comparison table of features

實驗結果為：在閾值e＝0.5時，待識別目標與飛機類中的戰斗機側面20度的姿態匹配，因此待識別目標被識別為戰斗機，實驗數據如表1所示。識別時間都為十秒的量級，而現在許多成熟的識別算法時間都在分鐘級，實驗表明本文目標識別算法速度較快；本算法對各目標姿態的特征多邊形頂點個數不同的情況，仍有較高的識別率；且本算法采用近似多邊形過濾掉了不能表征目標主要形狀的偽角點和細節輪廓，增加了目標識別的穩定性。

5 結束語

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

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

[2]趙軍.基于飛機模型的飛機識別方法研究[D].西安：西北工業大學機電學院，2004.

[3]趙軍.基于同底三角形面積比的飛機外形識別方法研究[J].蘭州交通大學學報：自然科學版，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.