基于中心点的自适应匹配算法

1、基于中心点的自适应匹配算法吴爱燕1吴爱燕（1980-），河北衡水人，汉族，硕士研究生。通讯地址：河北科技大学（中）研究生院2002级1班，联系电话E-mail: way_yijun，魏世泽2，王伟3（1,3 河北科技大学信息工程学院，河北石家庄 050051；2 河北科技大学现教中心，河北石家庄 050051）摘 要：随着指纹识别技术的广泛应用，人们对指纹匹配速度和精度的要求越来越高。为了满足用户的需求，研究人员提出了许多优秀的匹配算法，其中点匹配算法是目前研究较广泛的一种算法。由于指纹录入时产生旋转、平移和非线性形变，一般在进行精确的匹配之前先将指纹进行校正。切线校

2、正算法简单，有利于解决指纹录入时产生的旋转和平移，提高匹配速度。在点匹配算法中，利用特征点的方向信息和坐标信息进行匹配，同时采用自适应阀值法，对指纹录入时产生的非线性形变具有较好的鲁棒性，可以提高识别率。关键词：指纹识别; 匹配; 校正; 切线; 中心点; 三角点1. 引 言人的指纹具有唯一性和终身不变的稳定性。因此，一直以来指纹被公认是可靠的物证和身份鉴定的可靠依据。指纹匹配是自动指纹识别系统（AFIS）的核心研究内容之一，它在指纹特征提取之后，是自动指纹识别的最后一步，也是非常关键的一步。指纹匹配要解决的问题是对从两幅给定指纹图像中提取的特征信息进行匹配，判断两枚指纹是否来自同一个手指。由

3、于一些客观因素的存在，如：指纹录入时的随机性、磨损严重或受到不可恢复的意外伤害、特征提取算法的不完善等，使得指纹的匹配技术在提高识别率和识别速度上存在着一定的难度。Isenor等1提出了一种用图匹配来对两枚指纹图像进行匹配的算法。Hrechak等2提出了结构匹配算法。此外，还有Jain等3的串匹配算法，Mital D P等4提出的基于细节点的匹配算法。但目前最常用的方法是用FBI提出的采用指纹细节点模型做细节匹配。它利用指纹脊线的端点和分歧点（如图1所示）来鉴定指纹。本文在借鉴前人研究经验的基础上，提出了一种新的校正算法和点匹配算法，在一定程度上增强了指纹识别系统抵抗噪声和非线性形变的能力，提

4、高了指纹的识别速度和准确率。图1 脊线的端点和分歧点 2. 基于中心点的自适应匹配算法在实验中，首先，将输入的指纹图像分割成w*w大小的子块（实验中取w=16）；其次，求取每块指纹图像的方向信息，方向信息的计算采用文献3提出的公式法，其中采用soble算子计算梯度，采用5*5低通滤波平滑块的方向信息；然后，利用方向场图像的Poincare 索引来检测指纹图像中的特征点（包括中心点和三角点），其中对图像中的每个像素都用一个数字化的闭曲线计算Poincare索引，实验中设计了一条13个像素点的闭曲线；最后，根据中心点和三角点的信息给指纹分类，待识指纹首先根据类型、中心点和三角点的信息进行粗略匹配，

5、然后进行校正，最后进行精确匹配。预处理、特征提取和多级索引不是本文讨论的内容，因此不做详细介绍。在指纹细节匹配中,如何选择可靠的基准点对一直是个难题,如果将所有可能的点对分别当作基准点对来计算又存在计算量太大的问题。在文献5提出了一种限界盒的匹配算法，该算法在选取基准点对时引入了脊线信息，大大减少了可能的基准点对的数目。缩小了计算量，提高了匹配速度；同时在匹配时引入限界盒思想，提高了匹配精度，具体算法详见文献5。本文在借鉴其经验的基础上，提出了一种基于中心点的自适应匹配算法。我们的算法分为两步：首先用切线校正算法将指纹的坐标信息转换到极坐标系下，然后再进行匹配。在六类指纹中混合形指纹十分罕见，

6、可以直接用其中心点和三角点的个数进行匹配，弓形指纹没有中心点，因此不适用该基于中心点的校正、匹配算法，但弓形指纹也较罕见，因此对匹配的速度和精度影响甚微。对于弓形指纹匹配算法，本文在最后阐述。对于其他的四类指纹（尖拱形、左旋形、右旋形、涡形）的匹配方案如下所述。2.1极坐标系下基于中心点的切线校正算法首先，建立极坐标系。1) 取指纹的中心点作为坐标极点；2) 定义与中心点方向（涡形指纹任取其中一个中心点即可）垂直的方向作为中心点的切线方向，该垂线为中心点的切线。将该切线作为极轴，切线方向即极轴的正方向。如下图所示：图2 切线图然后，运用公式(1)进行坐标转换。=+ (1)其中，为直角坐标系下指

7、纹中心点的坐标，为直角坐标系下指纹特征点的坐标，为校正后的指纹特征点坐标，为指纹中心点的切线与直角坐标系下X轴的夹角（夹角小于）。无论指纹在录入时发生怎样的旋转和平移，相对一幅指纹图而言，以中心点为基准点的相对坐标是不变的，因此采用该校正坐标系对指纹图像进行校正，有效的解决了指纹录入时的旋转和平移问题。对指纹录入时发生的非线性形变，本文在匹配算法中采用了自适应阀值法进行了有效地解决。2.2 基于中心点的自适应匹配算法指纹的局部特征有很多种，例如：脊线的端点、分歧点、孤立点、小桥、小棒、小孔、毛刺等。各种特征出现的概率并不相等，许多特征是罕见的，其中端点出现的概率最高，其次是分歧点。一般的指纹识

8、别技术选取这两种特征点足以描述指纹的一般性，因此本文选取端点和分歧点，参见图1。指纹图像经过校正后，进入最后精确匹配阶段。本文设计了一种新的细节匹配算法，以坐标极点（即中心点core）作为基准点，将其周围最近的36个特征点与其连接，构成36个特征矢量。在算法中取五个参数，表示一幅指纹图像检测到的端点的个数，表示检测到的分歧点的个数，表示一个特征点到坐标极点的欧氏距离，表示一个特征矢量与极轴的夹角（夹角小于），表示一个端点的方向角或一个分歧点在两脊线上的方向角之差。根据公式(2)，(3)进行初步匹配，如果待识指纹和模板指纹同类特征点的个数相差超过允许限度值，则视为其不匹配。 (2) (3)模板指

9、纹特征序列表示如下：；待识指纹特征序列表示如下：，特征序列中的特征值按升序存放。其中，。模板指纹的某一特征点与待识指纹的某一同类特征点的相似度用f_score表示，模板指纹的特征序列与待识指纹的特征序列的匹配度用w_score表示。在公式(2)和(3)同时成立的前提下，判断，如果超过了某一临界值，则视两枚指纹匹配，否则为不匹配。由于非线性形变一般在一个特定的区域内较大,然后非线性地向外扩张。当特征点的极径（即特征矢量）较大时，极角较小的改变就会造成特征点位置较大的变动；相对而言，当特征点的极径较小时,小的形变就可以造成大的极角（即夹角或方向角差）的改变,而特征点位置的改变较小。参见图3所示A变

10、换到A，与B变换到B改变的角度是相同的，但A的位移变换要大于B的位移变换；而C点变换到C，与A变换到A位移的变换是相同的，但C变换的角度要大于A。相对大的位移变化可能会造成极径相对较大的变化，因此，我们在借鉴文献5限界盒的思想上，设计了自适应阀值，用如下公式计算临界值。 其中图3 位移与角度变换关系图当特征矢量低于某一值时，限界值可视为常量，不再随着特征矢量的变化而变化即。对于弓形指纹，由于这类指纹没有中心点core，因此，我们采用文献5提出的寻找基准点对方案，对每一对满足5的基准点对首先进行切线校正；然后进行匹配，校正和匹配方案均如前所述；最后选择各基准点对的最大值，如果超过了某一临界值，则

11、视为匹配，否则视为不匹配。3. 实验结果我们首先在FVC2000公布的指纹库DB1上，按照FVC2000的测试标准6，对本文的算法和传统确定基准点对算法作了实验，并进行了比较，实验结果见表1。所有的实验均在PIII1000MHZ微机及RedHat Linux平台下实现。测试标准EER(%)、EER*(%)、ZeroFMR(%)、ZeroFNMR(%)详见文献6，在此不再赘述。实验时间用检索时间来衡量两个算法，检索时间包括自特征提取后的一级匹配时间、二级匹配时间、最后精确匹配时间、及指纹图像的输出时间。表1 在FVC2000数据库DB1上的测试结果AlgorithmEER(%)EER*(%)Ze

12、roFMR(%)ZeroFNMR(%)确定基准点对算法3693691925100本文算法3713711903100两种算法的ROC曲线比较如图4所示。图4 在FVC2000的DB1上两算法的ROC比较确定基准点对算法的平均检索时间为0.46183s，本文算法的平均检索时间为0.32215s。4. 结论在传统的校正算法中，待识指纹需与模板指纹一一比对寻找基准点对，本文提出的极坐标系下基于中心点的切线校正算法在一定程度上避免了这一繁琐步骤，并有效地解决了旋转和平移问题。在基于中心点的自适应匹配算法中，我们采用欧氏距离和方向角双重确定特征点的位置，特征点的方向角（或方向差角）与特征矢量和极轴的夹角双

13、重确定了特征点所在脊线的局部方向信息，以及特征点所在脊线与中心点所在脊线的局部方向关系；自适应阀值法的引入，有效地解决了非线性形变问题；特征点集采用升序存储结构，有助于减小算法的复杂度。因此，该匹配算法用于三级检索机制有利于提高检索的速度和准确率。但该方法对中心点检测要求较高。不过，目前指纹匹配算法一般都需要先定位中心点和三角点，再进行分类，若中心点检测不准确，匹配的第一步指纹类型的判断就会出错。现有指纹匹配算法证明目前中心点的检测算法可以满足指纹分类、匹配的要求。实验证明，在中心点检测较准确的前提下，该算法对比于其他算法确实进一步提高了指纹的检索速度和准确率。参考文献：1 Isenor D

14、K,Zaky S G. Fingerprint identification using graph matching.Pattern Rcognition,1986,19(2):pp.113-122.2 Hrechak A K,Mchugh J A.Automated fingerprint recognition using structural matching. Pattern Rcognition, 1990, 23(8): pp.893-904.3 Jain A,Hong L,Bolle R.On_line fingerprint verification. IEEE Trans

15、on Pattern Analysis and Machine Intelligence, 1997,19(4):pp.302-313.4 Mital D P,Khwang E.An Automated Matching Technique for Fingerprint Identification. First International Conference on knowledge-based Intelligen Electronic Systems,1997，05：pp. 21-23.5 pp. 946-956。6 .Autoadjust Matching Arithmetic B

16、ased on Core pointWU Aiyan1, WEI Shize2, WANG Wei3(1,3 Computer Science and Project Institute, Hebei Science and Technology University, Shijiazhuang, Hebei Province 050051, China;2 Modern Education Center, Hebei Science and Technology University, Shijiazhuang, Hebei Province 050051, China)Abstract:

17、With the wide use of the fingerprint recognition, people bring forward higher request to fingerprint matching rate and accuracy gradually. Researchers have put forward much excellent matching arithmetic to satisfy user need. Now, the minutiae matching arithmetic is researched widely. When a fingerpr

18、int is taken, it usually has rotation, translation and transformation, so a fingerprint commonly is first adjusted before matching. The tangent adjusting arithmetic is simple, and it makes for solving the problems of fingerprint rotation and translation, and successfully improves matching rate. The minutiae matching arithmetic that uses