维普资讯 http://www.cqvip.com ２００８年第６期 计算机系统应用 基于结构特征信息的指纹匹配算法研究 Ｒｅｓｅａｒｃｈ ｏｎ Ｔｈｅ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ ｏｆ Ｆｉｎｇｅｒｐｒｉｎｔ Ｂａｓｅｄ ｏｎ Ｓｔｒｕｃｔｕ ｒａ Ｉ Ｆｅａｔｕ ｒｅ Ｉ ｎｆｏｒｍａｔｉｏｎ 张小海 王 宪 （江南大学通信与控制工程学院江苏无锡２１４１２２） 摘要：为了克服通常的指纹识别算法都不支持指纹的旋转和偏移的问题，本文提出了一种基于结构特征信息 的匹配算法。该算法利用结构特征信息中的邻点方向、脊线数、特征方向差和特征类型等特征信息建立 特征矩阵，用两特征点所提取的局部结构信息进行测试来判断该两点是否匹配。计算机仿真实验结果 表明，该算法对旋转、偏移、扭曲和压缩等具有很好的鲁棒性，而且算法复杂度小、处理效果好、运算速 度快。 关键词：指纹匹配旋转偏移扭曲 １ 引言 构关系以及特征信息如图１所示。其中，图１（ａ】描 指纹特征匹配是自动指纹识别系统中的最后一 绘出细化后指纹的一个局部区域几个特征点间的 步，也是最为关键的一步，在特征提取之后。指纹匹配 相互关系，从图上可以看出，特征点间的位置关系、 是用来判决两幅指定的指纹图像是否来源于同一个手 穿越的脊线数以及特征点类型不随平移和旋转而 指，利用提取的两幅指纹特征信息进行相关匹配运算。 变化；图１（ｂ）规定了端点和分歧点两类特征点的 目前指纹匹配常用脊线端点和脊线分歧点实现。特征 方向表示ｉ图１（ｃ）表示出了几个相邻的特征点的位 提取就是提取一副指纹图像中这两种特征点的类型、 置关系以及角度关系，其中每个箭头方向表示每个 位置和方向等信息。 特征点的特征方向，从图上亦可看出，特征点间的 目前，自动指纹匹配方法主要包括基于节点匹配 位置关系以及角度关系不随偏移和旋转而变化。 的方法和基于图像匹配的方法…。基于图像的匹配方 本文提出的匹配算法就是利用跨越的脊线数、角度 法由于受到采集的图像质量的影响较大，因此，基于节 关系和特征点类型等结构特征来比对的，没有采用 点匹配的方法较常用。基于节点的匹配算法中最常用 距离关系，距离易受到扭曲和压缩的影响。这些结 的为基于中心点的特征匹配 ，根据中心点信息确定 构特征对指纹图像的扭曲、压缩、旋转和平移鲁棒， 基准点对、计算相对平移和旋转参数、待识指纹图像姿 因此，本算法具有很好的鲁棒性，对扭曲严重、压缩 势矫正、统计最终匹配结果。由于中心点难以确定且 所确定的中心点坐标往往存在一定误差，图像经过平 较大、中心点很难提取的指纹都有很好的效果。 ， 移和旋转，进行姿势矫正，会引入一定的噪声。因此， 这类方法比较繁琐，效果一般。 基于结构的指纹匹配 不受旋转和平移的影响，无 需确定中心点。利用特征点和周边特征点的结构关系和 特征信息进行局部小区域的匹配，得到该特征点的匹配分 数，遍历所有的特征点，最终得到两幅图像的匹配分数。 ２ 数学建模 （ａ）特征点间的位置关系（ｂ）特征点的特征方向规定 对于一个特征点及其周边的若干特征点的结 Ｒｅ￣．－ｅｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ研究开发７１ 维普资讯 http://www.cqvip.com 计算机系统应用 （Ｃ）几个特征点间的角度关系 图１ 特征点结构及特征信息 ３指纹匹配 ３．１特征信息 本特征匹配需要穿越的脊线数和角度关系等特征 信息。计算穿越脊线的方法有很多种：数值微分法、中 点画线法、Ｂｒｅｓｅｎｈａｍ算法等等；但是数值微分法需要 采用浮点运算，累计误差将使得所计算的像素位置偏 离实际直线段。由于像素网格坐标的取整运算和浮点． 运算速度均很慢，算法效率低，因而实际中很少使用。 中点画线算法和Ｂｒｅｓｅｎｈａｍ算法＿４ 克服了数值微分 法的缺点，是最有效的方法。本文运用Ｂｒｅｓｅｎｈａｍ算 法计算穿越脊线个数，具体方法参照文献［４］，该方法 快速准确，便于硬件实现，具有很好的实用性。 规定逆时针方向为脊线和特征点的正方向。本文 所用的脊线方向是局部小块的脊线方向。首先将指纹 图像分成适当的块（本文取的块大小为１３ １３）；然后 采用Ｌｉｎ ｈｏｎｇ等人在文献［５］中的方向求取算法得到 块方向。各特征点的方向与其所在的块方向有关，参 照图１（Ｃ），若与块方向一致，则其方向即为块方向，否 则其方向为块方向加上竹（计算块方向时，块方向被约 束在［Ｏ，竹］）。参考图１，邻域特征点与中间点的特征 方向差为邻域的特征点方向减去中间点的方向，并把 这个方向差约束在［０，２竹］范围内。 ３．２匹配特征 ３．２．１建立特征矩阵 本文采用７邻域特征点结构。对任意特征点，按 照Ｅｕｃｌｉｄｅａｎ ｄｉｓｔａｎｃｅ距离选取与其最近的７个点共同 构成该特征点的特征结构。对所有的其他特征点按照 ７２ 研究开发Ｒｅ８ｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ２００８年第６期 公式（１）计算到该特征点的Ｅｕｃｌｉｄｅａｎ ｄｉ￣ａｎｃｅ距离，然 后进行由ｉｊｘ￣ｔｊ大排序，选取前７个特征点，这些点即为 要找的７邻域特征点。其中（’Ｃ ，Ｙ ）表示该特征点的 坐标，（ｘ ，Ｙ ）表示相邻的第ｍ个特征点的坐标，ｆｍ 表示最近的第ｍ个特征点到这个特征点的Ｅｕｃｌｉｄｅａｎ ｄｉｓｔａｎｃｅ距离。 ， 一√（ 一 ） ＋（ 一ｙ，，） （１） 找到这７个相邻的特征点后，参考图１（ａ），按照 公式（２）计算这７个特征点与中间点的两点间的方向， 其中对于’Ｃ ＝’Ｃ ，若Ｙ ＞Ｙ ，则０ ＝丌／２，否则０ ＝ １．５竹，再参考图１（ｃ），以中间特征点的特征方向为水 平正方向，将０ 规约到［Ｏ，２］，称这些方向为邻点方 向。然后按照这些由ｉＪ＼￣ｉｊ大的邻点方向对这７个点进 行排序建立特征矩阵，方向小的在最前，大的排最后， 其中对于方向一样的多个特征点按照距离由小到大排 序。这样，一个７邻域的特征点列便可有序排列开来。 ０，ｒ， ａｒｃｔａｎ（警等） （２） 每个邻域特征点含有四个特征信息，包括自身特 征类型Ｔｍ、与中间点所成的邻点方向０ｍ、到中间点所 穿越的脊线数Ｎ 和与中间特征点的特征方向差Ｑ 。 这样一个特征点列并可建立起来 ｉＬ．＝｛｛ ，０，，Ｎｊ，ＱＩ）＇．．．｛ ，０ ，Ｎ７， ｝｝，其中．Ｌｎ表示类型为ｉ 的第ｎ个特征点的７邻域特征点列，＿＿１表示端点类 型，Ｉ＿２表示分歧点类型。所有的特征点列共同构成 了特征矩阵。 ３．２．２配特征点列 对两幅指纹图像计算出两个特征矩阵后，任选两 个特征矩阵中的类型相同的特征点列进行测试是否匹 配。每个特征点列包括７组按序排列的特征信息，进 行按序检测。具体方法如下： （１）在待识匹配点列中搜寻与模板匹配点列中０ 相差小于（１）的邻域点对进行匹配测试，这里取（１）＝竹／ １２，表示只对两个点列中０ 相差小于１５度的点对进 行匹配测试； （２）若这两个点对的类型Ｔ一样，所穿越的脊线 数相等，且与中间特征点的特征方向差之差小于‘ｐ（这 里取‘ｐ＝￣－Ｉ１８，表示与中间特征点的特征方向差之差 小于１Ｏ度），则这两个点对匹配： （３）对剩下的待识组特征信息按照（１）和（２） 维普资讯 http://www.cqvip.com
２００８年第６期 处理： 计算机系统应用 可执行的程序后，对该指纹库做了１００００次自动匹配 实验。结果，正确匹配次数为９８１５次，拒识１４８次，误 识３７次，识别准确率为９８．１５％，拒识率为１．４８％，误 （４）统计两个特征点列中所匹配的点对数，若匹 配点对数大干Ｋ（这里取Ｋ＝４，表示两组特征点列中 至少有５组特征信息匹配，即这两个特征点的７个相 邻的特征点中至少有５组点对匹配），则这两个特征点 匹配。 识率为０．３７％，每一次匹配平均用时０．２５７０ｓ。实验 结果反映了该算法有较高的识别率和较强的抗噪性。 本文提出了一种基于指纹局部若干特征点的结构 特征信息的匹配算法，无需提取指纹的中心点，不需要 ３．２．３匹配判决 遍历所有的特征点列，对两个特征矩阵进行匹配 进行待识指纹的旋转和平移，该算法利用特征点及其 计算，按照公式（３）最终得到两幅指纹的匹配分数。 其中ｎ表示两幅指纹的匹配点对数，Ｎ。表示模板指纹 的特征点数，Ｎ 表示待识指纹的特征点数。 ． ｃ（）ｒＰ：————— 三＿——一 ，。、 ｎｆｉｎ（Ｎ， ） Ｉ ＪＪ 匹配判决取决于匹配分数ｓｃｏｒｅ和匹配点数ｎ，如 果ｓｃｏｒｅ大于 且ｎ大于ｐ（这里取 ＝０．６，Ｂ：８；表 示匹配的两个特征点集中成功匹配的点对数至少占 ６０％且能成功匹配的点对数大干８），则这两幅指纹匹 酉己，否贝０不匹酉己。 注意，由于自动指纹识别算法中存在两个相对立 的指标：拒识率ＦＲＲ和误识率ＦＡＲ。因此，这里提供了 五个参数‘１）、 Ｋ、ＯＬ和Ｂ来根据不同的应用环境去调 节ＦＲＲ和ＦＡＲ。例如，当‘１）越小，或者‘ｐ越小，或者Ｋ 越大，或者ＯＬ越大，或者Ｂ越大时，则ＦＲＲ越大而ＦＡＲ 越小，反之则ＦＲＲ越小而ＦＡＲ越大。 ４实验结果与结论 在ＡＭＤ２５００＋，１．４０ＧＨｚ，５１２Ｍ内存的台式计算 机上，用ＭＡＴＬＡＢ语言实现上述算法，并进行仿真实 验。本文描述的算法使用公开数据集ＦＶＣ２００２ＤＢ指 纹数据库作为测试对象，每个库中分别有十组指纹图 像，每组为同一指纹的不同采集图像，共３２０幅指纹图 像。数据库比较齐全，各种类型的指纹都有，这些指纹 大多质量较差，且有些指纹噪声严重、扭曲较大及旋转 较大。 在Ｍａｔｌａｂ仿真环境下，取‘１）＝，ｒ＇ｒ／１２、‘ｐ＝，ｒｒ／１８、Ｋ＝ ４、 ＝０．６和１３＝８，邻点个数为７，将上述算法编写成 邻域特征点所成的邻点方向、穿越脊线数、特征方向差 以及特征类型等结构特征信息进行匹配测试，利用同 类型的两个特征点的局部结构特征信息匹配测试来判 断模板与待识指纹中的这对特征点是否匹配。其中， 特征点及其邻域特征点所成的邻点方向和穿越脊线数 能很好地反映两个特征点间的位置关系，且不受旋转、 平移、扭曲和压缩的影响：特征方向差能够反映出该特 征点与邻域点所在区域的脊线方向信息。由于所利用 的特征信息对旋转、平移、压缩和扭曲鲁棒，因此，该算 法不仅可以较强地克服由于指纹图像的旋转、平移、扭 曲和压缩对指纹识别造成的影响，而且由于利用了局 部邻域特征点结构信息，数据量小，识别速度快，可靠 性强。 参考文献 １马康玉，刘超，刘跃峰．基于图像匹配的指纹识别． 计算机工程，２００３，２９（１８）：１１７—１１８． ２王业琳，宁新宝，尹义龙．一种新的指纹匹配算法． 中国图象图形学报，２００３，８（２）：２０３—２０８． ３苑玮琦，李宏伟．基于指纹结构特征信息匹配的算 法．光电工程，２ｏｏ６，３３（７）：１０１—１０４． ４孙家广．计算机图形学．北京：清华大学出版 社．１９９８． ５ Ｌｉｎ Ｈｏｎｇ，Ｙｉｆｅｉ Ｗａｎ，Ａｎｉｌ Ｊａｉｎ．ｆｉｎｇｅｒｐｒｉｎ ｉｍａｇｅ ｅｎ— ｈａｎｃｅｍｅｎｔ：ａｌｇｏｒｉｔｈｍ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｅｖａｌｕａｔｉｏｎ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎ． ｔｅｌｌｉｇｅｎｃｅ．１９９８，２０（８）：７７７—７８９． Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ研究开发７３