本文提出了一种指纹识别的特征点匹配算法，该算法是在Xiping Luo的算法的基础上经过改进而得到的。该算法首先通过指纹的中心点来确定指纹匹配时的参考点，指纹的中心方向为初始方向，在此基础上将所有的特征点用极坐标表示，对指纹模板特征点和输入指纹特征点实行归一化。其次，在匹配过程中，采用了一个可变限制框，以适应指纹的非线性变化。此外，本算法采用只对有效区内的指纹特征点进行比对来提高指纹识别的鲁棒性，对指纹中心偏移的输入图象有较好的识别效果。通过对指纹库中的指纹图像做实验，结果表明该算法速度快，精度高，更适用于实时指纹识别系统。
引言
每个人的指纹都是惟一的识别代码，终生享有，使用成本为零，安全系数极高，并且突破传统束缚，无需携带磁卡、IC卡、TM卡、射频卡等识别载体，更无需记忆密码，所以指纹在生物识别和鉴定系统中有着非常广泛的应用。指纹识别的核心问题之一是指纹匹配，它用来确定两个指纹是否来自同一手指。为找到一种速度快、性能好的指纹匹配算法，许多人对此进行了研究。目前指纹匹配方法可以分为两类。一类是基于图形的匹配方法，另一类是采用人工神经网络的方法。Xiping Luo的算法是一种基于图形的匹配方法，其实质是基于几何量的统计来实现的，大量的统计需要较长的时间，因此匹配速度往往较慢。本算法在Xiping Luo的算法的基础上进行了一些改进。
指纹最重要的特征之一是它的局部纹线特征，从某种程度来讲，这一特征决定了一个指纹的惟一性(或者叫个性化)。在局部纹线特征中，纹线端点(Rigde ending)和纹线分叉点(Ridge bifurcation)是两个最重要的特征，称为特征点，如指纹的另一个重要特征是指纹的中心点。它代表指纹的中心位置。本文中的匹配算法研究了指纹的中心点快速定位的方法，并利用中心点来确定参考点，从而节省了寻找参考点所用的时间。
特征点匹配
如果两个指纹来自相同的手指，它们的对应特征点的位置应该相近，并且对应特征点的局部特征也应该相近。
如果采用指纹的最大相似点作为参考点，相似度的计算要用大量的时间，因此本文把指纹的中心点作为参考点。指纹的中心点的定位方法很多，常用的有Poincare索引法、点方向一致性度量法和方向均值差异法等3种中心定位算法，还有在此基础上改进的一些方法。为了简化运算复杂度，指纹的中心点采用指纹上各个凸形纹线中曲率最大处的点。模板指纹的中心点记为，输人指纹的中心点记为，其中x和y是坐标值, 代表中心点的位置，t是中心点的类型（1代表左环型，2代表右环型，3代表旋涡型，4代表拱型）。
一个特征点可以记为P(x,y,d,t)，其中x和y是坐标值，代表特征点的位置，d是特征点的方向(取值从0～360) ,t是特征点的类型(1代表纹线端点，2代表纹线分叉点)。对一个模板指纹图像，具有M个点的特征点系列可以表示为:
对一个输入的指纹图像，具有N个点的特征点系列可以表示为:
特征点匹配是在极坐标系中进行的，因为指纹图像的非线性形变往往呈放射状，在某个区域内的形变比较大，然后非线性地向外扩张，因而，在极坐标中能更好地描述非线性形变；另外，在极坐标中不需要考虑输入图像与模板图像的参照点之间的平移，将一对对应点的坐标相对于参照点转换为极坐标时，平移就被抵消了，还有，在极坐标系中显然比在直角坐标系中更便于处理两幅图像间的旋转。
确定了参考点之后，可以将模板特征点系列和输入特征点系列中的每个特征点的坐标转化为极坐标。指纹的中心定为极坐标的中心，指纹的中心方向定为极坐标的初始零方向。对一个特征点P和Q，用下面的公式将其转化为极坐标。
在极坐标中的特征点记为，其中是极径，是极角，是极坐标系下特征点的方向，是特征点的类型，是模板指纹图像或输人指纹图像的中心方向。
即使输入指纹图像与数据库中的模板图像来自同一个手指，两幅图像之间也还是会有像平移、旋转、尺度变化这样的形变。我们在对两幅图像进行匹配之前先要估计它们之间的形变参数，并以此对这两幅图像进行校准。
另外，按指纹时由于用力的差异等多种原因必然会使两幅指纹图像间存在非线性形变。即使是经过校准，输入图像中的细节点也不可能与模板图像中的对应点完全重合。再加上采集过程中存在噪声等原因，使得两幅图像的对应点之间可能存在一定的偏差。这些都要求细节点匹配算法具有一定的弹性，也就是说细节匹配算法应该能在一定程度上容忍由于提取出来的细节点位置不准确或图像的非线性形变造成的对应点位置的差异。为解决这个问题，本文的匹配算法引入了尺寸可变的限制框，使匹配算法有更强的鲁棒性。
如图2所示，一个限制框是包围模板细节点上的一个框，这个框的一对边的极角为常数，另一对边的极半径为常数。用angle_size表示极半径为常数的那对边的极角差异：
angle_size=angle_high-angle_low
用adius_size表示极角为常数的那对边的极半径差异:
radius_ size = radius_high - radius_low
限制框的大小用angle_size和radius_ size来表示。
本文的方法中，angle_size和radius_ size的值将随细节点的极半径大小而改变，使用可变大小的限制框是为了使算法对非线性形变更为鲁棒。当细节点的极半径较小时，小的形变就可以造成大的极角的改变，而极半径的改变较小。所以这种情况下，限制框的angle_size应该比较大，而radius_ size比较小。而当细节点的极半径较大时，极角的较小改变就会造成细节点位置的较大变动，而极半径的形变可以看成是该细节点与参照细节点间的所有区域的形变的叠加。所以在这种情况下，限制框的angle _ size应该比较小，而radius_ size则较大。可用下式来计算极半径为的模板细节点的angle_size和radius_ size：
其中分别是radius _ size和angle _ size的上界和下界，它们的值是预先设定的。是预先给定的常数。
匹配步骤及实验结果
根据以上讨论，本算法包括以下几个匹配步骤：
(1)确定有效特征点区域内的特征点数目，以判断是否进行匹配。
(2)将模板图像和输入图像的特征点系列中的每个特征点的坐标转化为极坐标。对应各自的中心点，利用公式(3)进行转换。
(3)按极角递增的顺序，排列模板特征点系列和输入特征点系列。
(4)根据输入特征点系列中的每个特征点寻找模板特征点系列中的特征点进行匹配。按极角递增的顺序逐一对输入图象和模板图像的特征点进行匹配。如果输入图像中有一个特征点位于限制框内，并且特征点的类型相同，特征点的方向与模板特征点的方向之差在事先设定的阈值范围内，则认为这两个特征点匹配，并将Ture [i ] [ j]增加1，否则Total[i][j]增加1。
(5)计算匹配分数的大小，并将它作为模板指纹和输入指纹的匹配分数，如果这个匹配分数大于阈值，则认为输入的指纹与模板指纹来自同一手指。
实验采用的指纹数据库DB3_B中包含80幅指纹图像。对它们分别进行随机的旋转和移位，分别生成10幅指纹图象。图像的大小是512 X 512像素, 500dpi分辨率。首先，对于每一个数据库中的指纹，我们把它作为输入指纹，把它同生成的指纹进行匹配。其次，对于每一个数据库中的指纹，我们把它作为输入指纹，把它同指纹数据库DB1_B中的指纹进行匹配。通过适当地设定前面所讨论的参数，我们得到了拒识率FRR是0.2%和误识率FAR是0.001的实验结果。实验是在Pentium4,2.0GHz CPU上进行的，操作系统是Windows Professional。
引言
每个人的指纹都是惟一的识别代码，终生享有，使用成本为零，安全系数极高，并且突破传统束缚，无需携带磁卡、IC卡、TM卡、射频卡等识别载体，更无需记忆密码，所以指纹在生物识别和鉴定系统中有着非常广泛的应用。指纹识别的核心问题之一是指纹匹配，它用来确定两个指纹是否来自同一手指。为找到一种速度快、性能好的指纹匹配算法，许多人对此进行了研究。目前指纹匹配方法可以分为两类。一类是基于图形的匹配方法，另一类是采用人工神经网络的方法。Xiping Luo的算法是一种基于图形的匹配方法，其实质是基于几何量的统计来实现的，大量的统计需要较长的时间，因此匹配速度往往较慢。本算法在Xiping Luo的算法的基础上进行了一些改进。
指纹最重要的特征之一是它的局部纹线特征，从某种程度来讲，这一特征决定了一个指纹的惟一性(或者叫个性化)。在局部纹线特征中，纹线端点(Rigde ending)和纹线分叉点(Ridge bifurcation)是两个最重要的特征，称为特征点，如指纹的另一个重要特征是指纹的中心点。它代表指纹的中心位置。本文中的匹配算法研究了指纹的中心点快速定位的方法，并利用中心点来确定参考点，从而节省了寻找参考点所用的时间。
特征点匹配
如果两个指纹来自相同的手指，它们的对应特征点的位置应该相近，并且对应特征点的局部特征也应该相近。
如果采用指纹的最大相似点作为参考点，相似度的计算要用大量的时间，因此本文把指纹的中心点作为参考点。指纹的中心点的定位方法很多，常用的有Poincare索引法、点方向一致性度量法和方向均值差异法等3种中心定位算法，还有在此基础上改进的一些方法。为了简化运算复杂度，指纹的中心点采用指纹上各个凸形纹线中曲率最大处的点。模板指纹的中心点记为，输人指纹的中心点记为，其中x和y是坐标值, 代表中心点的位置，t是中心点的类型（1代表左环型，2代表右环型，3代表旋涡型，4代表拱型）。
一个特征点可以记为P(x,y,d,t)，其中x和y是坐标值，代表特征点的位置，d是特征点的方向(取值从0～360) ,t是特征点的类型(1代表纹线端点，2代表纹线分叉点)。对一个模板指纹图像，具有M个点的特征点系列可以表示为:
对一个输入的指纹图像，具有N个点的特征点系列可以表示为:
特征点匹配是在极坐标系中进行的，因为指纹图像的非线性形变往往呈放射状，在某个区域内的形变比较大，然后非线性地向外扩张，因而，在极坐标中能更好地描述非线性形变；另外，在极坐标中不需要考虑输入图像与模板图像的参照点之间的平移，将一对对应点的坐标相对于参照点转换为极坐标时，平移就被抵消了，还有，在极坐标系中显然比在直角坐标系中更便于处理两幅图像间的旋转。
确定了参考点之后，可以将模板特征点系列和输入特征点系列中的每个特征点的坐标转化为极坐标。指纹的中心定为极坐标的中心，指纹的中心方向定为极坐标的初始零方向。对一个特征点P和Q，用下面的公式将其转化为极坐标。
在极坐标中的特征点记为，其中是极径，是极角，是极坐标系下特征点的方向，是特征点的类型，是模板指纹图像或输人指纹图像的中心方向。
即使输入指纹图像与数据库中的模板图像来自同一个手指，两幅图像之间也还是会有像平移、旋转、尺度变化这样的形变。我们在对两幅图像进行匹配之前先要估计它们之间的形变参数，并以此对这两幅图像进行校准。
另外，按指纹时由于用力的差异等多种原因必然会使两幅指纹图像间存在非线性形变。即使是经过校准，输入图像中的细节点也不可能与模板图像中的对应点完全重合。再加上采集过程中存在噪声等原因，使得两幅图像的对应点之间可能存在一定的偏差。这些都要求细节点匹配算法具有一定的弹性，也就是说细节匹配算法应该能在一定程度上容忍由于提取出来的细节点位置不准确或图像的非线性形变造成的对应点位置的差异。为解决这个问题，本文的匹配算法引入了尺寸可变的限制框，使匹配算法有更强的鲁棒性。
如图2所示，一个限制框是包围模板细节点上的一个框，这个框的一对边的极角为常数，另一对边的极半径为常数。用angle_size表示极半径为常数的那对边的极角差异：
angle_size=angle_high-angle_low
用adius_size表示极角为常数的那对边的极半径差异:
radius_ size = radius_high - radius_low
限制框的大小用angle_size和radius_ size来表示。
本文的方法中，angle_size和radius_ size的值将随细节点的极半径大小而改变，使用可变大小的限制框是为了使算法对非线性形变更为鲁棒。当细节点的极半径较小时，小的形变就可以造成大的极角的改变，而极半径的改变较小。所以这种情况下，限制框的angle_size应该比较大，而radius_ size比较小。而当细节点的极半径较大时，极角的较小改变就会造成细节点位置的较大变动，而极半径的形变可以看成是该细节点与参照细节点间的所有区域的形变的叠加。所以在这种情况下，限制框的angle _ size应该比较小，而radius_ size则较大。可用下式来计算极半径为的模板细节点的angle_size和radius_ size：
其中分别是radius _ size和angle _ size的上界和下界，它们的值是预先设定的。是预先给定的常数。
匹配步骤及实验结果
根据以上讨论，本算法包括以下几个匹配步骤：
(1)确定有效特征点区域内的特征点数目，以判断是否进行匹配。
(2)将模板图像和输入图像的特征点系列中的每个特征点的坐标转化为极坐标。对应各自的中心点，利用公式(3)进行转换。
(3)按极角递增的顺序，排列模板特征点系列和输入特征点系列。
(4)根据输入特征点系列中的每个特征点寻找模板特征点系列中的特征点进行匹配。按极角递增的顺序逐一对输入图象和模板图像的特征点进行匹配。如果输入图像中有一个特征点位于限制框内，并且特征点的类型相同，特征点的方向与模板特征点的方向之差在事先设定的阈值范围内，则认为这两个特征点匹配，并将Ture [i ] [ j]增加1，否则Total[i][j]增加1。
(5)计算匹配分数的大小，并将它作为模板指纹和输入指纹的匹配分数，如果这个匹配分数大于阈值，则认为输入的指纹与模板指纹来自同一手指。
实验采用的指纹数据库DB3_B中包含80幅指纹图像。对它们分别进行随机的旋转和移位，分别生成10幅指纹图象。图像的大小是512 X 512像素, 500dpi分辨率。首先，对于每一个数据库中的指纹，我们把它作为输入指纹，把它同生成的指纹进行匹配。其次，对于每一个数据库中的指纹，我们把它作为输入指纹，把它同指纹数据库DB1_B中的指纹进行匹配。通过适当地设定前面所讨论的参数，我们得到了拒识率FRR是0.2%和误识率FAR是0.001的实验结果。实验是在Pentium4,2.0GHz CPU上进行的，操作系统是Windows Professional。
