指纹识别技术是生物特征识别的重要研究内容，也是目前研究最多、最有应用前景的生物识别系统。指纹识别技术的研究最早从17世纪开始的，并成功应用于刑事侦查。随着现代电子集成制造技术的进步和快速可靠算法的研究，指纹识别技术日趋成熟，其应用也日益普遍，在民用方面已经非常广泛，如指纹门禁系统、指纹考勤系统、银行指纹储蓄系统、驾驶员指纹管理系统、手机指纹识别系统等。通常一个自动指纹识别系统(AFIS)的包括指纹采集、指纹分类、指纹预处理、指纹细节特征提取和指纹匹配等过程(图 1)。指纹匹配是自动指纹识别系统研究的核心内容之一，匹配算法的好坏直接影响识别的性能、速度和效率。指纹匹配算法主要分为基于图形图像^[1]、基于脊结构^[2]和基于特征细节点的匹配算法^[3]。基于特征细节点的匹配算法(点模式匹配算法)具有简单、快捷和鲁棒性等优点，是目前最常用的方法。大部分的点模式匹配算法都是基于纯几何形状的“欧几里得”匹配法，在这个框架下，研究者们提出了很多点模式匹配算法。例如，Ranand和Rosenfeld^[4]提出了利用松弛法进行点匹配，但是松弛匹配算法只能针对部分几何不变量进行处理，如点集间的平移，因此在实际中很难运用推广。Gao^[5]提出了一种基于极坐标变化的点特征进行匹配的算法，该算法根据点集的分布与点位置信息，构建了点的特征属性图，通过极坐标变换得到对数极坐标的特征图，并利用几何不变矩方法对特征图进行描述。Starink^[6]提出了三角匹配的算法，该算法基于三角形相似的匹配方法实现简单，但时间和空间复杂度大，且在判断三角形相似的过程中，大小三角形相似的判断误差范围不好控制，容易造成误匹配。Zheng^[7]在三角形匹配算法的基础上，提出了一种三角形相似向量的算法，主要解决关键问题点模式匹配算法的参考点定位问题。为了减小三角形匹配算法的计算复杂度，Zhao^[8]提出了将指纹图像分成一系列的循环集，利用奇异点的理论降低了计算复杂度。Ghazvini^[9]使用遗传算法和Cao^[10]使用粒子群算法分别研究了三角形匹配算法，但他们都增大了存储要求，且单独进行点模式下匹配很难克服噪声、旋转及变形对指纹识别的干扰。Jain等人^[11]利用聚类方法进行指纹匹配，同样该算法计算量大，时间消耗较多，无法满足识别系统的实时需要。

利用三角形的不变性、稳定性和唯一性特征，提出一种无方向的三角形匹配指纹识别算法，该方法将各个特征点与基准三角形3个顶点的距离组成有序三数组，利用数组的相等对指纹相似度进行判断。较传统的三角形匹配算法，该方法不受指纹图像方向、旋转角度及其位置的影响，算法实现简单。实验结果表明，该方法有效地提高了系统的识别性能和容错能力，对低质量的指纹图像表现出较好的鲁棒性。

假定有两个点模式$\boldsymbol{P}$和$\boldsymbol{Q}$，其中点模式$\boldsymbol{P}$中有从待识别指纹图像中提取的$m$个特征点$\boldsymbol{P}$={$p_1$，$p_2$，…，$p_m$}，点模式$\boldsymbol{Q}$中有从模板指纹图像中提取的$n$个特征点$\boldsymbol{Q}$={$q_1$，$q_2$，…，$q_n$}，$\boldsymbol{P}$、$\boldsymbol{P}$中每点存放的是坐标信息[$x$，$y$]$^{\rm{T}}$。因而点模式$\boldsymbol{P}$和$\boldsymbol{Q}$可分别表示为

$\boldsymbol{P} = \{ {({x_{{p_i}}},{y_{{p_i}}})^{\rm{T}}}|i = 1,2, \cdots ,m\} $

(1)

$\boldsymbol{Q} = \{ {({x_{{q_a}}},{y_{{q_a}}})^{\rm{T}}}|a = 1,2, \cdots ,n\} $

(2)

点模式$\boldsymbol{P}$和$\boldsymbol{Q}$之间的匹配就是找到一个校准函数$G_r$($t_x$，$t_y$，$\theta $)使得两个点集有最大数量点对之间存在稳定的一一对应关系，即$G_r$($p_i$)=$q_a$，由于点的相对位置存在误差，因此一般||$G_r$($p_i$)－$q_a$||≤$\varepsilon $($\varepsilon $为允许变形范围)表示这种对应关系。这种对应关系将待识图像中的一点$\boldsymbol{p}$=[$x_p$，$y_p$]$^{\rm{T}}$映射成另一点$\boldsymbol{q}$=[$x_q$，$y_q$]$^{\rm{T}}$，其映射规则为

$\begin{array}{l} \boldsymbol{q} = {G_r}\left( p \right) \Rightarrow \left[ {\begin{array}{*{20}{c}} {{x_q}}\\ {{y_q}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{t_x}}\\ {{t_y}} \end{array}} \right] + \\ \left[ {\begin{array}{*{20}{c}} {{\rm{cos}}\theta }&{ - {\rm{sin}}\theta }\\ {{\rm{sin}}\theta }&{{\rm{cos}}\theta } \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_p}}\\ {{y_p}} \end{array}} \right] \end{array}$

(3)

式中，$t_x$、$t_y$分别是$x$方向和$y$方向的平移量，$\theta $是旋转角度。

定理1^[12] 假定($p_i$，$p_j$)和($q_a$，$q_b$)是点模式$\boldsymbol{P}$和$\boldsymbol{Q}$中的两对点，如果$p_i$≠$p_j$且$q_a$≠$q_b$，则存在唯一的映射$G_r$，使得$q_a$=$G_r$($p_i$)，$q_b$=$G_r$($p_j$)，其中$r$∈($t_x$，$t_y$，$\theta $)，$\theta $=${\theta _{\mathop {{q_a}{q_b}}\limits^ \to }} - {\theta _{\mathop {{p_i}{p_j}}\limits^ \to }}$，且

${t_x} = {x_{{q_a}}} - {x_{{p_i}}}{\rm{cos}}\theta + {y_{{p_j}}}{\rm{sin}}\theta $

(4)

${t_{y}} = {y_{{q_b}}} - {x_{{p_i}}}{\rm{sin}}\theta + {y_{{p_j}}}cos\theta $

(5)

定理1从理论上保证了校准函数$G_r$($t_x$，$t_y$，$\theta $)的存在性和唯一性。这种映射是一种全局的、刚性的变换，只是一种坐标系的调整，变换后同一副图像中各点之间的位置关系并没有任何改变，因此校准函数$G_r$($t_x$，$t_y$，$\theta $)可以修正为$G_r$(0，0，$\theta $)。由于旋转角度的存在，导致在基准点对的确定和匹配点对匹配的计算过程都需要构造矢量，需要大量的迭代运算和迭代时间，特别是如果指纹特征在提出过程中引入的位置和角度的偏差较大时，会导致识别不成功的情况出现，无法满足自动指纹识别系统的实时需要。本文构造了一种无方向的三角形匹配算法，提出了一种新的校准函数，该函数完全不依赖于旋转角度，故称为“无方向^[13]”的匹配算法。下面首先介绍两个定理，为基准三角形的确定以及构造校准函数奠定理论基础。

定理2  3条边可以唯一地确定一个三角形。

证明：由三角形的稳定性原理易证。

定理3 平面上任意一点都可以通过这个点到平面上任意一个确定的三角形的顶点的距离组成的有序三数组唯一确定。

证明：平面上任意一点与一个确定的三角形的位置关系有3种，即位于三角形之外、三角形的边界和三角形内部。

1) 假设平面上任意一点$P$位于△$ABC$之外。设点$P$到△$ABC$ 3个顶点$A$、$B$、$C$的距离分别为$a$、$b$、$c$。以$B$点为圆心、$b$为半径作圆；以$C$点为圆心、$c$为半径作圆，两个圆的交点分别记为$P$和$Q$。再以$A$点为圆心、$a$为半径作圆，那么3个圆必相交于$P$点，如图 2所示。下面用反证法证明3个圆必不相交于$Q$点。假设3个圆必相交于$P$和$Q$点，即$Q$与$Q$′重合，连接$PQ$和$PQ$′，在圆$C$中有$PQ$⊥$BC$，在圆$A$中有$PQ$′⊥$AC$，又由于$PQ$和$PQ$′重合，那么有$BC$//$AC$，这与$BC$、$AC$为△$ABC$的两条边矛盾，因此，假设不成立，即$Q$与$Q$′不重合，那么这3个圆必定唯一地相交于点$P$，因此，$P$点可以由$a$、$b$、$c$唯一确定，记为$P$($a$，$b$，$c$)。

2) 假设平面上任意一点$P$位于△$ABC$的边界上，不妨假设$P$点在边$BC$上，如图 3所示。假设点$P$到△$ABC$ 3个顶点$A$、$B$、$C$的距离分别为$a$、$b$、$c$。以$B$点为圆心、$b$为半径作圆；以$C$点为圆心、$c$为半径作圆，两个圆相切于交点$P$，再以$A$点为圆心、$a$为半径作圆，那么3个圆必唯一地相交于点$P$，因此，$P$点可以由$a$、$b$、$c$唯一确定，记为$P$($a$，$b$，$c$)。

3) 假设平面上任意一点$P$位于△$ABC$的内部。假设点$P$到△$ABC$ 3个顶点$A$、$B$、$C$的距离分别为$a$、$b$、$c$。以$B$点为圆心、$b$为半径作圆；以$C$点为圆心、$c$为半径作圆，两个圆的交点记为$P$和$Q$。再以$A$点为圆心、$a$为半径作圆，那么3个圆必唯一地相交于$P$点，如图 4所示。因此，$P$点可以由$a$、$b$、$c$唯一确定，记为$P$($a$，$b$，$c$)。

综上所述，定理成立。证毕。

本文提出的无方向性的点匹配算法主要有两个重要环节：基准三角形的确定和无方向点的匹配。

假设对于待识点集$\boldsymbol{P}$中一点$p_1$，在$\boldsymbol{Q}$中找到与之匹配的点$q_1$形成了一对肯定匹配的点对(参考点)，分别在待识指纹图像中和模板指纹图像中寻找两个距离它们最近的特征点$p_2$、$p_3$和$q_2$、$q_3$构成特征点子集。这样，分别在待识指纹图像和模板指纹图像中形成了两个三角形△$p$₁$p$₂$p$₃和△$q$₁$q$₂$q$₃如图 5所示。

由定理2知，3条边可以唯一地确定一个三角形，因此，可以根据3个特征点之间的距离(三角形的3条边长)以及它们的相互位置关系，判断这两个由3组特征点构成的三角形的相似程度。

具体判断方法如下：

1) 计算顶点$p_1$和$q_1$对应的边长|$p_2$ $p_3$|和|$q$₂$q$₃|，对于给定的一个阈值$\varepsilon $，如果|$p$₂$p$₃|－ |$q$₂$q$₃ |＞$\varepsilon $，则△$p$₁$p$₂$p$₃和△$q$₁$q$₂$q$₃不可能全等，判断结束，否则转步骤2)；

2) 分别计算$p_1$到$p_2$、$p_3$和$q_1$到$q_2$、$q_3$的距离|$p$₁$p$₂|、|$p$₁$p$₃ |和$q$₁$q$₂|、|$q$₁$q$₃ |。对于给定的一个阈值$\varepsilon $，如果|$p$₁$p$₂|－ |$q$₁$q$₂| ≤$\varepsilon $且|$p$₁$p$₃|－ |$q$₁$q$₃|≤$\varepsilon $，或者|$q$₁$q$₂|－ |$q$₁$q$₃| ≤$\varepsilon $且| |$p$₁$p$₃| － |$q$₁$q$₂| ≤$\varepsilon $，则△$p$₁$p$₂$p$₃和△$q$₁$q$₂$q$₃近似全等。

由定理3知，平面上任意一点都可以通过这个点到平面上任意一个确定的三角形的顶点的距离组成的有序三数组唯一确定，因此，可以设计无方向匹配点算法如下：

假设对于待识点集$\boldsymbol{P}$中一点$p_1$，在$\boldsymbol{Q}$中找到与之匹配的点$q_1$形成了一对参考点。

1) 以$p_1$为顶点与点集$\boldsymbol{P}$中的其他点$p$_$i$($i$≠1)构造三角形，以$q_1$为顶点与点集$\boldsymbol{Q}$中其他点$q$_$j$($j$≠1)构造三角形；

2) 按照3.1节的方法逐一判断，分别在点集$\boldsymbol{P}$和点集$\boldsymbol{Q}$中确定基准三角形，记为△$p$₁$p$₂$p$₃和△$q$₁$q$₂q₃；

3) 计算$\boldsymbol{P}$中$p$_$i$($i$≠1)到△$p$₁$p$₂$p$₃ 3个顶点的距离，分别记为$h$_{$p_i$ $p$1}，$h$_{$p_i$ $p$2}，$h$_{$p_i$ $p$3}，构成有序数组($h$_{$p_i$ $p$1}，$h$_{$p_i$ $p$2}，$h$_{$p_i$ $p$3})；

4) 计算$\boldsymbol{Q}$中$q$_$j$($j$≠1)到△$q$₁$q$₂$q$₃ 3个顶点的距离，分别记为$h$_{$q_j$ $q$1}，$h$_{$q_j$ $q$2}，$h$_{$q_j$ q3}，构成有序数组($h$_{$q_j$ $q$1}，$h$_{$q_j$ q2}，$h$_{$q_j$ q3})；

5) 如果($h$_{$p_i$ $p$1}，$h$_{$p_i$ $p$2}，$h$_{$p_i$ $p$3})=($h$_{$q_j$ $q$1}，$h$_{$q_j$ $q$2}，$h$_{$q_j$ $q$3})，即$h$_{$p_i$ $p$1}=$h$_{$q_j$ $q$1}，$h$_{$p_i$ $p$2}=$h$_{$q_j$ $q$2}，$h$_{$p_i$ $p$3}=$h$_{$q_j$ $q$3}，则$p_i$与$q_j$匹配，否则$p_i$与$q_j$不匹配。

本文算法在CPU为Inter(R) Xeon(R) CPU E3-1245 V2@3.40 GHz，内存为16.0 GB，操作系统为Windows 7的PC机上进行测试；测试软件为Microsoft Visual C++ 6.0。

采用国际标准测试库FVC2004^[14]DB1和DB2进行测试，其中由110只不同的手指，每个手指采集8个样本，共包含了880幅指纹图像256个灰度级，并以TIF格式保存在指纹数据库中，DB1和DB2指纹库的具体性能指标见表 1。

1) 错误拒绝率(FRR)。发生错误拒绝的比对次数占总统计比对次数的比例，用百分比表示，也叫误拒率、拒真率(FNMR)。

2) 错误接受率(FAR)。发生错误接受的比对次数占总统计比对次数的比例，用百分比表示，也叫误识率、授假率(FMR)。

3) 相等错误率(EER)。在某给定的匹配相似度下，FAR与FRR相等时的错误率。

4) FMR100。误识率为1 %时的拒识率。

5) FMR1000。误识率为0.1 %时的拒识率。

6) ZeroFMR。误识率为0时的拒识率。

7) ROC(receiver operating curve)曲线。ROC曲线以FMR为横坐标、以FNMR为纵坐标得到的曲线，又称接受者操作特性曲线。

按照本文提出的无方向匹配算法步骤，首先提取出模板指纹和待识指纹的特征点信息，然后求取两幅指纹图像的基准三角形，最后给出实际的匹配结果。其中一对指纹的匹配过程如图 6—图 9所示。

为了测试本文算法的综合性能，将本文算法与国际优秀商用SDK算法—VeriFinger 6.1 SDK和BioCore SDK，以及中国科学院自动化研究所的Fingerpass和MD算法^[15]分别在指纹数据库DB1和DB2中进行了几组不同的对比实验。为了方便，将本文算法记作OFI，实验结果见表 2、表 3和图 10—图 12。

EER和ROC曲线都是衡量算法综合性能的指标，从表 2和表 3中可以看出，无论是在DB1还是DB2指纹库中，OFI算法的EER最小，说明较其他几种算法而言，OFI算法的综合性能最优。同样，从图 10和图 11中也可以得到同样结果，无论是在DB1还是DB2指纹库中，OFI算法的ROC曲线都低于VeriFinger 6.1 SDK和BioCore SDK算法相应地ROC曲线，而ROC曲线越低表示性能越好。因此，OFI算法具有较高的匹配精度和较好的鲁棒性。通过比较几种算法的平均比对时间，容易看出OFI算法的平均比对时间花费最少，这是因为本文提出的无方向算法不受平移、旋转角度的影响，极大地减少了算法的计算量，从而减少了比对时间。

图 12给出了几种算法随着旋转角度的变化，得到的实验统计结果。OFI算法在不同旋转角度下都有较为稳定的匹配结果，VF 6.1 SDK算法在不同旋转角度下也有不错的匹配效果，而BioCore SDK、Fingerpass、和MD算法则对旋转较为敏感，只有在小角度旋转时有较好的匹配效果，而在大角度旋转时匹配效果不理想。这是因为本文提出的无方向匹配算法不依赖于旋转角度，对旋转是不敏感的，因此具有较好的匹配效果。

匹配算法是指纹识别技术研究中的热点和难点，通过对现有方法分析和归纳，提出了无方向的点模式匹配算法。该算法利用平面中任意点与一个确定的三角形之间的位置结构稳定性，将各个特征点与基准三角形三个顶点的距离组成有序三数组，利用数组的相等对指纹相似度进行判断，从而实现指纹的准确匹配。与传统三角形匹配算法相比，该方法不受指纹图像方向及其位置的影响，算法实现简单，识别精度高且速度快，是一种全局模式的匹配方法。实验结果表明，该方法对于不同类型指纹数据库中不同质量的指纹图像均表现出较好的普适性和鲁棒性，能够更好地解决当待识别的指纹图像与原始指纹图像发生位移、旋转、形变等难匹配问题。残缺指纹的匹配问题是指纹识别技术中的难点，也是指纹识别技术在刑事侦查和司法鉴定领域中最直接的应用，下一步工作将深入研究无方向的点模式匹配算法在残缺指纹匹配中的若干问题。