指纹特征匹配算法的研究与实现

第２９卷　第１２期　ＶＯ１．２９　ＮＯ．１２　计算机工程与设计　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　２００８年６月　Ｊｕｎｅ　２００８　指纹特征匹配算法的研究与实现　田　慧　（平顶山工学院计算机系，河南平顶山４６７０６４）　摘　要：指纹特征的匹配是实现指纹识别的重要环节，现有的匹配算法大多需要反复的调整每一个点来与图像模版中的点　相对应，这样就加大了匹配算法的计算复杂度，因而无法满足指纹实时识别系统的要求。为此提出了通过快速确定参考、旋　转和平移参数的方法，以实现指纹特征匹配算法的实时要求。实验结果表明，该特征匹配算法在满足实时性要求的前提下，　其性能指标完全符合一般的商业用途。　关键词：指纹识别；特征匹配；特征向量；拒识别率；实时性　中图法分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１０００—７０２４（２００８）１２—３２５８－０３　Ｒｅｓｅａｒｃｈ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｉｆｎｇｅｒｐｒｉｎｔ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　ＴＩＡＮＨｕｉ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｐｉｎｇｄｉｎｇｓｈａｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｐｉｎｇｄｉｎｇｓｈａｎ　４６７０６４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｆｉｎｇｅｒｐｒｉｎｔ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｍａｔｃｈｉｎｇ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｌｉｎｋ　ｔｏ　ｒｅａｌｉｚｅ　ｆｉｎｇｅｒｐｒｉｎｔ　ｉｄｅｎｔｉｆｉｃａｔｉｏｎ，ａｎｄ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｍａｔｃｈｉｎｇ　ａｌ－　ｇｏｒｉｔｈｍ　ｍｏｓｔｌｙ　ｎｅｅｄ　ｔｏ　ｒｅｐｅａｔｅｄｌｙ　ａｄｊｕｓｔ　ｅａｃｈ　ｐｏｉｎｔ　ｔＯ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｔｏ　ｔｈｅ　ｐｏｉｎｔ　ｉｎ　ｉｍａｇｅ　ｔｅｍｐｌａｔｅ，ｔｈｕｓ　ｈｅ　ｔｃｏｍｐｕｔａｔｉｏｎ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｈｅ　ｍａｔｃｈｉｔｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｉｎｃｒｅａｓｅｄ　ｎｄ　ａｔｈｅ　ａｌｇｏｒｉｔｈｍ　Ｃａｎ　ｎｏｔ　ｍｅｅｔ　ｔｈｅ　ｎｅｅｄｓ　ｏｆ　ｒｅａｌ－ｔｉｍｅ　ｉｆｎｇｅｒｐｒｉｎｔ　ｉｄｅｎｔｉｆｉｃａｔｉｏｎ　ｓｙｓｔｅｍ．Ｔｈｅｒｅｆｏｒｅ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆｑｕｉｃｋｌｙ　ｄｅｔｅｒｍｉｎｉｎｇ　ｒｅｆｅｒｅｎｃｅ，ｒｏｔａｔｉｏｎ　ｎｄ　ａｔｒａｎｓｌａｔｉｎｇ　ｐａｒａｍｅｔｅｒｓ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｔｏ　ｒｅａｌｉｚｅ　ｔｈｅ　ｒｅａｌ—ｔｉｍｅ　ｒｅｑｕｉｒｅｍｅｎｔｓ　ｏｆｆｉｎｇｅｒ—　ｐｒｉｎｔ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｎｄｉｃａｔｏｒｓ　ｏｆ　ｔｈｅ　ｆｉｎｇｅｒｐｒｉｎｔ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　ａｒｅ　ｆｕｌｌ　ａｃｃｏｒｄ　ｗｉｈ　ｔｇｅｎｅｒａｌ　ｃｏｍｍｅｒｃｉａｌ　ｐｕｒｐｏｓｅｓ　ｕｎｄｅｒ　ｔｈｅ　ｐｒｅｍｉｓｅ　ｏｆ　ｍｅｅｔｉｎｇ　ｒｅａｌ—ｔｉｍｅ　ｒｅｑｕｉｒｅｍｅｎｔｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｆｉｎｇｅｒｐｒｉｎｔ　ｉｄｅｎｔｉｉｃａｔｉｏｎ；ｃｈａｆｒａｃｔｅｒ　ｍａｔｃｈｉｎｇ；ｅｉｇｅｎｖｅｃｔｏｒ；ＦＲＲ；ｒｅａｌ－ｔｉｍｅ　０引　言　自动指纹识别是２１世纪６０年代兴起的，利用计算机取　人们开始着手研究用计算机来处理指纹，自动指纹识别系统　（ＡＦＩＳ）的研究与应用就由此扩展开来。指纹图像模式识别是　模式识别领域的一项综合性研究，其核心是提炼指纹图像构　代人工来进行指纹识别的一种方法。近年来，随着计算机技　术的飞速发展，低价位指纹采集仪的出现以及可靠算法的实　现，更使得自动指纹识别技术越来越多的进入到人们的生活　成要素的组织形式和秩序。这些要素包括纹线的构成、流向、　中心点、三角点及细节特征点等。由于采集的指纹或现场指　纹受印压的轻重、扭曲、偏转和环境的影响，使指纹图像存在　着相对变形、残缺和噪声，造成信息丢失和假特征的出现。因　而指纹图像模式识别的关键是寻求适应各种图像环境的图像　处理及特征提取方法，寻求相对尺度、平移、旋转、仿射不变的　图像拓扑结构模式和计算机视觉不变量。在这一方法的导引　下，指纹自动识别的基本处理框架通常包含指纹采集、预处　理、特征提取和特征匹配４个部分。　和工作中。指纹识别的一个简单流程如图１所示。　指纹数据库　图１指纹识别的流程　指纹图像模式识别的主要研究内容包括：①指纹图像的　几何、拓扑性质；②指纹图像的增强、消噪声、平滑、二值化、细　指纹的两个重要特征在１９世纪初的科学研究中就已经　化算法；③指纹图像的特征提取方法及特征空间的构成；④指　纹图像的拓扑分类方法；⑤面向实际应用的指纹自动识别　系统等。　需要重点解决的问题为：寻求相对于尺度、平移、旋转、仿　被发现：①两个不同手指的指纹纹脊的样式不同：②指纹纹脊　的样式终生不变。这个研究成果使得指纹在犯罪鉴别中得以　正式应用。　２０世纪６０年代，由于计算机可以有效地处理图形图像，　收稿日期：２００７—１１－２６　Ｅ－ｍ蚰：ｙｗｌｘｚｙ＠１２６．ｃｏｍ　射不变的特征量及特征量的提取方法，指纹图像特征的拓扑　作者简介：田慧（１９７２一）。女，河南平顶山人，硕士，讲师，研究方向为多媒体技术及应用。　・——３２５８－——　维普资讯 http://www.cqvip.com

结构识别与匹配方法。其中特征匹配是识别系统的关键环节。　对应边长分别相等并且三对对应顶点间的方向角相等，则称　两个矢量三角形全等。　引理１　指纹图像上一有向点Ｐ＝（‰；ｙｏ　，Ｔｏ，　以任意给定点　ｏ（ａｏ，￣ｏ）为中心旋转　角度后，经Ｘ轴方向的平移　和Ｙ轴方向的　平移　后得有向点０　，　则　匹配算法的好坏直接影响识别的性能、速度和效率。　ｌ指纹特征匹配算法的改进　１．１指纹特征匹配算法的理论分析　指纹识别，即根据指纹的特征描述来判断两幅指纹图像　是否来自同一人的同一手指。　指纹的特征描述方法有很多种类，但无论哪一种特征描　］；ｏ－０．ｏ　０＋　引理２一个标准系下矢量三角形的３个顶点　ｔ　点　，　，以　任意一点为中心旋转０角后，再做相同的平移后得到的３个顶　，构成的新矢量三角形与原矢量三角形全等。反之，　若两个矢量三角形全等，则其中的任何一个都可以通过另一　述方法都必须考虑到从一幅指纹原始图像到特征描述方式的　转化和基于这种描述方式下的模式匹配过程中所存在的问题，　同一手指的不同指纹图像的采集通常是在不同条件下进行的。　比如：观察点不同，传感器不同，或者是相同的传感器（指纹采　集器）但是在不同时间获得的，这样两幅图像将有不同程度的　平移、旋转和缩放差异，而这种差异在特征提取和模式匹配过　程中是未知的。由于采集时噪声和其它影响的存在，无论特　征点的描述方法和提取方法如何，特征点的相对位置都会发　生变化。指纹匹配的大部分算法是“欧几里德”匹配法。这些　算法一定程度上允许特征点的缺失，而且它们中的一些算　法可以允许特征点位置在一定的弹性范围内存在偏差，但　偏差不能太大。而算法是反复地调整每一个点，它与模板　图像中的点相对应，直到满足某个条件为止。尽管人们对　算法进行了许多改进，以降低匹配的复杂度。但这些算法　因其固有的反复操作特性使得运算时间很长，不适用于指　纹实时识别系统。　１．２指纹特征匹配算法的改进思路　鉴于上述原因，本文提出了一种基于曲线结构和三角法　来确定参考点的点模式匹配算法，其基本思想是通过对指纹　图像中的特殊特征点——图像中心部孤立端点所连纹线进行　跟踪采样，取得纹线上两个固定点，再利用矢量三角形法，快　速确定参考点和旋转、平移参数，从而避免了在一般的点模式　匹配算法中，因选取参考点进行的逐点反复搜索而消耗大量　时间的弊病。　同时，该算法是根据多点来确定变换参数，而不是通常意　义上的一点，在一定程度上可以消除在特征提取过程中所引　入的位置、角度的偏差，得到更为准确的变换参数。　２匹配算法　２．１定义及弓Ｉ理　定义１　图像　的特征点的全体为Ｐ　牡，…　，则　的特征点　序列空间Ｐ记为：Ｐ＝　ｔ　，・・・　）。　定义２对图像　，如存在Ｐ，则对Ｖｐ　有　∈　１≤ｆ≤　），　Ｐ　＝（　；Ｙｐ，．　，　为　特征点信息。其中　．　为Ｐ　的坐标，　为特征　点的类型，０为局部主导方向。　定义３指纹图像中有向点是具有位置和方向的点，有向　点Ｐ用Ｐ（ｘ，ｙ，　表示，其中ｘ，ｙ，０分别代表Ｘ轴、Ｙ轴坐标和Ｐ点的局　部主导方向，一　≤Ｏ＜￣ｚｒ。　定义４若直角坐标系下的不在同一直线上的３个有向　点按顺时针次序排列，称这３个点按标准方向系排列，所构成　三角形为标准系下矢量三角形。　定义５如果两个同为标准系下的矢量三角形满足：三对　个经旋转和平移得到。　２．２匹配算法　２．２．１　建立特征向量　初次匹配就是利用相邻点间的结构关系建立局部特征向　量进行初步匹配，这一步可以比较准确地找到两个指纹点集　间的最佳匹配参考点。　首先进行指纹图像特征的提取得到所有特征点。每一个　特征点记录了３方面信息：点的位置　）：点的类型　分支点，　末梢点）：该点所在脊线的方向角度ｑＣ［－７ｒ，Ｔｒ］。　对每个特征点，以该点为中心建立一个用于匹配的局部　邻域特征向量。取与该中心点０距离大于刖拘最近３个点　）作为其邻域特征点，距离小于等于的点则不取这３个　邻域点和该中心点一起用来构造局部特征向量。接逆时针把　Ｐｔ　连接起来组成一个三角形。把点０，Ｐｔ　的类型（末梢　点或分支点）分别记为Ｓｏ　Ｓ　Ｓ　Ｓ把ｐ　与０、Ｐ　与０、Ｐ，与０的距离　分别记为Ｄｔ、Ｄ　和Ｄ，；把ｐｔ与Ｐ　、Ｐｔ与　、ｐ　与Ｐ，的距离分别记为　、　和　。按照Ｐ　、Ｐ　、Ｐ，与０点的距离。从小到大排列局部　特征向量。如果Ｄｔ（Ｄ　（Ｄ，，则局部特征向量排列为　（瓦，　，　，　’Ｄ　’Ｄ　’Ｄ　，　，　，　）。　２．２．２特征匹配算法　首先在待识别指纹的中心部位寻找孤立端点，并求取特　征附加；对所取的点与特征附加所构成的矢量三角形与模板　中的带特征附加特征点所构成的矢量三角形进行比较，判断　其是否全等，若不等，继续取下一个进行比较，直到全部找完；　若全等，计算两个矢量三角形的旋转和平移参数；按求得的参　数对待识指纹的所有特征点进行变换；然后求变换后特征空　间的匹配特征点数目。并计算与特征点比例，若在一定范围　内，即可判定匹配成功，否则判定为失败，其算法流程如图　２所示。　矢量三角形的全等判断，在算法实现中并非严格要求全　等，考虑到指纹采集时的弹性摄动，应允许存在一定范围的误　差，误差大小的设计按系统要求的情况，经过实验可得到选择　构成矢量三角形的３个点是中心部位孤立端点及特征附加，　原因是孤立端点仅带一条纹线。跟踪便利，中心部位纹线通　常曲率较大，矢量三角形全等容易判断。量三角形的旋转平　移参数通过下列方法计算：　取两个矢量三角形△　，和△　ＢｚＢ，的重心　（　，　）和　Ｇｎ（Ｘｎ，　），令平移量　＝　＋Ｚ—　一　一　）／３＝　一‰　・——３２５９・——　维普资讯 http://www.cqvip.com ＦＲＲ＝　３．２实验结果　采用了Ｍａｔｌａｂ　６．５对算法进行了实验。对指纹识别竞赛　ＦＶＣ２０００提供的指纹数据库ＤＢＩ、ＤＢ２、ＤＢ３、ＤＢ４中的Ｓｅｔ　Ｂ　库中的指纹图像进行了匹配测试。分别对于ＤＢ１、ＤＢ２、ＤＢ３、　ＤＢ４中的每一个指纹图像与同一手指的其它采样图像进行匹　图２特征匹配的流程　＝（　．｝　一　一　一　）／３＝　一曲　ｎ一一　（　＋　＋　）　３　式中：　—一　和Ａ　的方向角。　为简化可使用如下公式进行计算　：　±堡±　＝　二　二　，一　３　从参数的计算可以看出实际这是一种均值方法，它可以　减少用任意顶点对计算参数所带来的偶然误差和映射变换中　的误差传播。　２．２．３算法的性能分析　本方法可以有效地控制偶然误差，经改进还可以有效地　克服指纹按捺过程中弹性形变的影响。在实现中高效率地寻　找全等矢量三角形是关键问题，以往的算法中都是在全体特　征点中寻求全等矢量三角形。　假设两枚指纹的特征点数分别为ｍ和ｎ，则需进行Ｃ－ｘＣ：　次的判断，而每次又都可能对应所有特征点的旋转和平移，以　每枚指纹中大约５０个特征点来计算，时间消耗极大。而利用　孤立端点加曲线跟踪的方法不但使可能的参考点减到５个左　右，而且免去了另外两点的组合判断。理论上缩短时间达Ｃ　×　Ｃ　倍。　３实验结果　３，１性能评价参数　自动指纹识别系统的性能评价参数有：识别速度、正确率　（ｃａ）、误识率（ＦＡＲ）、拒识别率（ＥＲＲ）。　其计算公式分别为　ＣＲ＝ｌ一（，　＋职Ｒ）　ＦＡＲ－　・——３２６０・——　配运算。　实验结果如表１所示。　表１实验结果　指纹库　匹配次数　ＦＡＲ　ＦＲＲ　ＣＲ　ＤＢ１　７９ｘ８０　０　１．１７　９８．８３　ＤＢ２　７９ｘ８０　０　１．１６　９８．８４　ＤＢ３　７９ｘ８０　０　１．１６　９８．８４　ＤＢ４　７９ｘ８０　０　１．１８　９８．８２　４结束语　本文提出的指纹特征匹配算法，可以有效地控制偶然　误差，克服指纹按捺过程中弹性形变的影响，同时能高效率　地寻找全等矢量三角形，与现有的算法相比，能满足实时性　的要求。实验结果表明，该算法性能指标完全符合一般的　商业用途。　自动指纹识别系统的研究和开发已成为国内外学术界和　商界的热点。相对于其它生物特征鉴定技术，例如语音识别　及虹膜识别，指纹识别具有许多独到的优点，更重要的是它具　有很高的实用性和可行性，已经被认为是一种理想的身份认　证技术，有着十分广泛的应用前景。　参考文献：　【１】　Ａｍｅｎｇｎａｌ　Ｊ　Ｃ，Ｊｕａｎ　Ａ，Ｐｅｒｅｚ　Ｊ　Ｃ，ｅｔ　ａ１．Ｒｅａｌ—ｔｉｍｅ　ｍｉｎｕｔｉａｅ　ｅｘｔｒａｃ．　ｔｉｏｎ　ｉｎ　ｉｆｎｇｅｒｐｒｉｎｔ　ｉｍａｇｅｓ［Ｃ］．Ｐｒｏｃ　ｏｆ　ｔｈｅ　６ｔｈ　ｎＩｔ　Ｃｏｎｆ　ｏｎ　Ｉｍａｇｅ　ｐｒｏｃｅｅｄｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ（ＩＰＡ９７），２００３．　【２】　李建华，马小妹，郭成安．基于方向图的动态阙值指纹图像二值　化方法【Ｊ］．大连理工大学学报，２００２，４２（５）：６２６．６２８．　【３】　Ｊａｉｎ　Ａ，Ｈｏｎｇ　Ｌ，Ｂｏｌｌｅ　Ｒ．Ｏｎ—ｌｉｎｅ　ｉｆｎｇｅｒｐｒｉｎｔ　ｖｅｒｉｉｆｃａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎｆｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００２，ｌ　９（４）：　３０２．３１３．　【４】Ｊａｉｎ　Ａ，Ｌｉｎ　Ｈｏｎｇ，Ｂｏｌｌｅ　Ｒ．Ｏｎ—ｌｉｎｅ　ｆｉｎｇｅｒｐｒｉｎｔ　ｖｅｒｉｉｆｃａｔｉｏｎ［Ｊ］．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉ－　ｇｅｎｃｅ，２００３，１９（４）：３０２—３　ｌ４．　［５】　罗希平，田捷．自动指纹识别中的图像增强和细节匹配算法［Ｊ］．　软件学报，２００２，１３（５）：９４６．９５６．　［６】　张洪光，刘雪梅．指纹识别中的一种局部向量匹配算法［Ｊ］．计算　机工程，２００２，２８（４）：１０６．１０８．　［７】　简兵，庄镇泉，李军．一种新颖的指纹细节提取算法［Ｃ】．第六届　国际青年计算机工作者会议暨第二届生物特征识别研讨会，　２００ｌ：７．１３．　【８］　苏彦华．Ｖｉｓｕａｌ　Ｃ＋＋数字图像识别技术典型案例【Ｍ］．ｊ匕京：人民　邮电出版社，２００４：１７７．１９５．