基于最小生成树相似测度的耳廓匹配

　　摘   要: 将树匹配引入身份识别，将每只耳廓表示为一棵最小生成树，通过两棵树的相似测度衡量两只耳廓的相似度，以完成耳廓匹配。首先从耳廓点云数据中选取一定数量的关键点;然后分别对两只耳廓的关键点集采用Kruskal算法生成最小生成树，计算两只耳廓匹配产生的3个相似度测量值;最后经过置信加权求和，求出两只耳廓之间的整体相似度，进而完成耳廓匹配。

　　关键词: 耳廓匹配；树匹配；相似测度

　　随着科学技术的不断发展，基于身份证和密码的传统身份鉴别技术暴露出越来越多的缺陷，已经不能满足人们对快速、便捷、有效的身份识别技术的需求，在此情况下，基于生物特征的身份识别技术应运而生。生物特征识别是利用人类特有的生理或行为特征进行个人身份识别的技术[1]，它提供了一种高稳定性、可靠性的身份鉴别途径。而耳廓凭借其特殊的生理位置和结构特征，已经成为生物特征识别领域的后起之秀。与指纹识别、人脸识别、虹膜识别等方法相比，耳廓识别不受化妆和表情变化的影响，具有更高的唯一性、稳定性和健壮性。耳廓识别在公共安全、信息安全等领域具有潜在的应用前景。

　　根据输入数据的不同，可以将耳廓特征识别方法分为基于二维图像的识别和基于三维点云的识别，相比较而言，三维耳廓数据将提供更多的细节信息，能够在不同的光照和姿态变化条件下取得较好的识别效果。最初，基于三维耳廓点云的耳廓识别算法大多采用ICP算法，参考文献[2]用经典的ICP算法配准三维图形，参考文献[3]用耳廓/外耳廓表示法进行人耳曲面匹配，但基于ICP算法的识别算法复杂度很高。参考文献[4]基于直方图的形状描述匹配骨架图；参考文献[5]基于图的直方图及路径相似性进行图匹配；参考文献[6]通过测量图的相似性来匹配两张脸；参考文献[7]基于二分图来匹配三维耳廓形状特征。

　　1 算法基础

　　针对两只待匹配耳廓，首先选取分布在三维空间中的若干关键点并提取附属在关键点上的特征向量，以此来建立特征描述。

　　1.1 提取关键点及特征

　　在三维耳廓模型上随机选取一点vi，以vi为球心、r为半径做球， 记球内所有点构成的矩阵为Ri， 其均值向量为m、协方差矩阵为C。对C进行主成分分析得到特征向量和特征值矩阵。将Ri中所有点分别投影到较大的两个特征值对应的特征向量上，记两个方向上投影的最大值和最小值之差分别为dx和dy，若d=|dx-dy|大于指定阈值，则选vi为关键点，记作kvi。重复该过程，直到获得指定的关键点数目，记该耳廓的关键点集合为KV。大量实验数据表明,当关键点数目n=200时，实验效果最佳。

　　对于任意关键点kvi，本文基于参考文献[8]方法对其邻域内的全部点进行曲面拟合。首先在参数区域上沿u方向和v方向分别进行均匀采样，得到均匀分布的nu×nv个采样点，记其深度集合{Zuv}组成的局部形状特征为LSFi，则定义在关键点集KV上的局部形状特征集合为{LSFi}。为保证特征的计算效率及精度，本文对局部形状特征进行必要的压缩，采用参考文献[6]的方法将kvi上的nu×nv维局部形状特征LSFi压缩为11维，同时保证压缩后的精度保持在97.3%。

　　1.2 两耳廓关键点集间的映射

　　针对模型耳廓p，考察数据库中的测试耳廓g，根据两耳廓上各关键点的局部形状特征计算两个特征的相似度，从而找到特征之间的对应关系。特征之间的相似度由两个特征之间的均方根距离RMS来计算：

　　其中，pi和gi分别表示模型耳廓和测试耳廓第i对关键点上特征向量的分量。RMS距离值最小的一对特征建立对应关系。

　　2 MST的相似测度

　　对于已经确定了对应关系的两只待匹配耳廓，将已匹配关键点分别投影到2D平面上，对其进行Delaunay三角剖分后，再把剖分结果投影回三维空间，得到一张三维网格图。然后对剖分图进行MST计算，不同耳廓和同一耳廓的不同扫描数据树的结构如图1所示。

　　图1中每一列为同一耳廓的不同扫描数据，每一行为不同的耳廓数据，节点为关键点，线条为MST。通过比较可知，不同的耳廓上树的结构存在明显的差异；同一耳廓的树的结构大致相同，具有很高的重复率。

　　2.1 衡量两耳廓的三个相似测度

　　已经确定了两只待匹配耳廓关键点之间的对应关系，将树节点之间的平均测地距离作为点误差:

　　其中,(xpi,ypi,zpi)和(xgi,ygi,zgi)分别表示两棵树中第i个节点的坐标值，mp表示已匹配树节点数量。

　　搜索两棵最小生成树，分别记录每条边的边长及组成边的节点，形成边表。比较两张边表，计算两棵树对应边之间的误差:

　　其中，εpi和εgi分别表示两棵树中第i条对应边的边长，me表示边的数量。

　　在构造MST之前已经计算出耳廓上各关键点的特征，用对应特征之间的RMS距离作为特征误差计算:

　　2.2 整体相似测度

　　以上描述了两只耳廓匹配得到的3个相似测度Pd、Ed、Fd,将模型耳廓与测试库中所有耳廓进行匹配就会得到3组相似测度，用min-max准则将3个向量规范化到0~1之间后，模型耳廓和测试耳廓之间的整体相似度可以用置信加权和来表示：

　　S=Kp×Pd+Ke×Ed+Kf×Fd  (5)

　　其中，Kp、Ke、Kf分别表示3个相似测度的置信度[6]。最后得到的S向量包含N个元素，分别表示模型耳廓与测试库中N个耳廓的匹配结果，即两者的整体相似度。取S值最小的测试耳廓作为最终判断的依据。

　　3 实验结果及分析

　　本文实验数据为利用VIVID910三维激光扫描仪自主采集的三维耳廓数据，其中每只耳廓获得2~6个扫描数据不等。本文自行实现了参考文献[2]和参考文献[7]所述算法，并在同样的数据集进行了匹配实验。相关实验结果比较分析如下。

　　3.1 匹配精度

　　当对两只耳廓进行匹配时，RMS距离最小的一对特征之间将建立对应关系,相应的关键点对为匹配点对，若一对已匹配关键点对在空间内的距离值在给定的阈值范围内，就说明匹配正确，正确匹配点对数与图节点总数量的比值为匹配精度。随着图节点数量的增加，对已有数据库中所有耳廓的不同扫描数据进行匹配实验，本文算法与参考文献[2]、参考文献[7]算法的平均匹配精度如图2所示。显然，本文算法的匹配精度最高且逐渐趋于稳定。

　　3.2 时间复杂度

　　本文令关键点数目从100逐渐增加至200，并对耳廓数据库中所有个体的不同扫描数据进行匹配实验，参考文献[2]、参考文献[7]与本文算法平均匹配一对耳廓所用时间对比情况如图3所示。显然，随着图节点数的不断增加，3种算法的匹配时间都有不同程度的增加，其中参考文献[2]算法所用时间变化尤为剧烈，而本文算法所用时间最少且变化不大。可见，本文算法的时间复杂度更低、匹配效率更高。

　　本文采用基于最小生成树相似测度的耳廓匹配方法，把树匹配问题应用于解决耳廓识别问题，获得了较好的实验效果，显然，本文选取耳廓上一定数量的关键点进行匹配,避免了原数据中近10万节点反复迭代计算的过程，计算复杂度大大降低，匹配精度高。耳廓具有丰富的特征结构，仅仅考虑局部特征会造成不同的凸起之间、凹陷之间产生错误匹配，下一步考虑将局部匹配与全局匹配相结合，进一步提高匹配的精度。

　　参考文献

　　[1] 王晓云.基于代数方法的人耳识别研究[D].沈阳:沈阳工业大学,2011.

　　[2] BESL P, NEIL B. A method for registration of 3D shapes[J].IEEE Transactions on Pattern AnalysisMachinInteligence,1992,14(2):239-256.

　　[3] Chen Hui, BHANU B. Human ear recognition in 3D[J].IEEE Transaction on Pattern Analysis and Machine Intelli-gence,2007,29(4):718-737.

　　[4] Tang Jin,Jiang Bo,Luo Bin.Shape description and skeleton-graph matching algorithm based on histogram[J]. Journal ofSouth China University of Technology,2010,38(7):27-32.

　　[5] Tang Jin, Jiang Bo, Luo Bin. Graph matching based on graph histogram and path similarity[J].Journal of Computer-Aided Design and Computer Graphics, 2011,23(9):1481-1489.

　　[6] BENNAMOUN M, OWENS R A. Keypoint detection and local feature matching for textured 3D face recognition[J]. International Journal of Computer Vision,2008,79(1):1-12.

　　[7] Sun Xiaopeng, Wang Xingyue, Wang Guan. 3D ear shapefeature optimal matching using bipartite graph[J]. Frontier and Future Development of Information Technology in Med-icine and Education,2013:3133-3138.

　　[8] D’ERICO J. Surface fitting using gridfit[EB/OL].MATLABCentral File Exchange Select,2006.