改进的基于模型匹配的快速目标识别

孙思佳，闫钧华，储林臻，杭谊青

（南京航空航天大学 航天学院，江苏 南京 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.