指纹识别中的一种细节匹配算法

指纹识别中的一种细节匹配算法

罗希平田捷*

(北京中国科学院自动化研究所人工智能实验室 100080)

摘要:指纹匹配是AFIS中最重要的问题之一。一般用象脊线末端和脊线分支点这样的细节点来表示一个指纹，并通过细节匹配来做指纹匹配。本文提出一种细

节匹配算法，这种算法对Anil Jain等人提出的细节匹配算法进行了修正。我们

采用了一种新的更简单的方法来进行指纹图像的校准，并以一种简单而有效的方

式将脊线信息引入匹配过程中，这样做的好处之一是以较低的计算代价有效地解

决了匹配中参照点对的选取问题。另外，我们采用了大小可变的限界盒来适应指

纹的非线性形变。我们的算法能更好地区分来自不同指纹的图像，并能更加有效

地处理来自同一个指纹的被匹配图像之间的非线性形变。对用活体指纹采集仪采

集的指纹图像集所做的实验显示我们的算法有较快的速度和较高的准确率。

关键词: 指纹识别, 细节匹配, 自动指纹识别系统(AFIS)

1. 背景介绍

自动指纹识别系统（即Automated Fingerprint Identification System，简称AFIS）有着广泛的应用背景。

指纹识别是要决定两幅指纹图像是否来自同一个手指。过去人们对指纹识别做了很多研究。D.K.Isenor等人[2]提出了一种用图匹配来对两幅指纹图像进行匹配的方法。Andrew K.Hrechak等人[3]用结构匹配来做指纹识别。但目前最常用的方法用是FBI提出的细节点坐标模型来做细节匹配。它利用脊末梢与脊线分支点这两种关键点来鉴定指纹。通过将细节点表示为点模式，一个自动指纹认证问题可以转化为一个点模式匹配（细节匹配）问题。一般的点模式匹配问题是模式识别中的一个有名的难题，人们对一般的点模式匹配问题提出过很多的算法，象sanjay Ranade等人[5]的松弛算法，Shih-hsu Chang等人[6]基于二维聚类的快速算法。Anil Jain等人在[4]针对指纹匹配中的点模式匹配问题提出了一种算法，该算法将直角坐标系中的细节点转换到极坐标系中，通过串匹配算法来进行点匹配。

本文的算法参考了Anil Jain等人[4]的算法。但与[4]中的算法有三个主要差别。首先，我们采用了一种更为简单而有效的指纹图像校准方法。其次，与[4]中仅在校准阶段使用脊线信息的做法不同，我们将脊线信息引入了随后的匹配过程中,在本文第三部分我们将讨论这样做的好处。最后，[4]中的方法在匹配过程中使用了一个固定大小的限界盒，而我们的算法采用了一个大小可变的限界盒，从而使算法能更有效地处理被匹配的两幅指纹图像之间的非线性形变，被匹配的两幅指纹图像之间的非线性形变是指纹匹配中最难解决的问题之一。

我们的自动指纹识别系统框图如图1所示，系统由离线部分和在线部分两个部分组成。在系统的离线部分，用指纹采集仪采集指纹，提取出细节点，然后将细节点保存到数据库中，形成指纹模板库。在系统的在线部分，用指纹采集仪采集指纹，提取出细节点，然后将这些细节点与保存在数据库中模板细节点进行匹配，判断输入细节点与模板细节点是否来自同一个手指的指纹。

本文受国家自然科学基金资助，课题号为：69875019

*：本文联系作者,e_mail:tian@https://www.sodocs.net/doc/7c18403313.html,, 电话：82618465

图1、自动指纹识别系统框图

本文第2部分简单介绍从灰度图像提取细节点的过程，这可以看成是细节匹配的预处理。第3部分详细介绍我们的细节匹配算法。第四部分给出实验结果，第五部分做总结和讨论。

图2.预处理的步骤

图3、细节点的对应脊线

2. 预处理

图2给出了一般的指纹匹配的步骤。首先要获取指纹图像。然后，要用增强算法来提高指纹图像的质量，指纹图像的增强是指纹识别中的一个重要也很困难的研究课题，人们提出过很多种指纹图像增强算法[8][9],但由于图像增强不是我们在本文中将要讨论的问题，我们不在此对增强做详细介绍。增强后的指纹图像随后被二值化,并细化成指纹脊线的骨架。从细化后的图像中就能提取出细节点来，但由于噪声的存在和图像质量等方面的原因，脊线骨架中必然存在的脊线断裂和毛刺等现象，还有可能在一小片区域内有很多不成形的短脊线，这些都造成提取出来的细节点中有很多的伪细节点，因而要进行细节点的后处理以尽可能地去掉伪细节点。

经过上述步骤之后就检测出了细节点。对检测出来的每一个细节点，我们记录如下信息：

1) 细节点的x,y坐标

2) 细节点的方向，这个方向定义为该细节点所在的局部脊线的方向。

3) 细节点的类型，即脊线末梢或脊线分支。

4) 细节点对应的脊线(d i,αi)。

细节点对应的脊线用在与该脊线上的采样点来表示，采样的距离约为脊线间的平均距离。脊线分支点对应的脊线是与该细节点的方向最近的那条。脊线末梢对应的脊线则就是该细节点所在的脊线。采样点用该点与对应细节点的距离di和连接该点与对应细节点的直线与对应细节点方向的夹角αi来表示, αi的取值范围是-180到180度。图3给出了细节点对应的脊线及脊线上的采样点的例子。在细节匹配中，对应脊线将被用来对两个平面点集进行校准，而且，校准的参数，也就是两个点集中任意一对脊线间的旋转角度，将被用来作为判断它们所对应的细节点能否看作匹配的细节点的条件。

自动指纹识别系统的应用中，在公安领域的应用一般是针对大规模数据库的，对存储空间的要求比较高，此时在细节点中加入脊线信息会加大系统的存储量，似乎显得不太合适，但硬件的发展正在不断降低对存储空间的要求。在一般的应用如网络安全，指纹门控系统，指纹考勤系统等中，数据库没有大到对存储空间提出严格要求的程度，而脊线信息的加入可以有效的处理指纹图像的校准并会带来后面将会讨论到的其它好处，我们认为是值得的。

3.

细节匹配

正如文[4]中指出的，在极坐标系中进行细节匹配有很多的优点。指纹图像的非线性形变往往呈放射状，在某个区域内的形变比较大，然后非线性地向外扩张，因而，在极坐标中能更好地描述非线性形变。另外，在极坐标系中，我们不需要考虑输入图像与模板图像的参照点之间的平移，因为输入图像与模板图像间的平移是固定的，也就是说另外一对对应点之间的平移与参照点之间的平移是一样的，这样，将另外一对对应点的坐标相对于参照点转换为极坐标时，平移就被抵消掉了。而且，在极坐标系中显然比在直角坐标系中更便于处理两幅图像间的旋转。综合上述原因，我们将在极坐标系中做细节匹配。

即使输入指纹图像与数据库中的模板图像来自同一个手指，两幅图像之间也还是会有象平移，旋转，尺度变化这样的形变。我们在对两幅图像进行匹配之前先要估计它们之间的形变参数，并以此对这两幅图像进行校准。由于两幅指纹图像是用同一个仪器采集的，可以假定它们间的尺度变化参数为1。另外，如前讨论的，在极坐标中可以不考虑两幅图像间的平移。因而需要作出估计的仅有输入图像与模板图像间的旋转参数。

另一方面，按指纹时由于用力的差异等多种原因必然会使两幅指纹图像间存在非线性形变。即使是经过校准，输入图像中的细节点也不可能与模板图像中的对应点完全重合。在加上采集过程中存在噪声等原因，使得两幅图像的对应点之间可能存在一定的偏差。这些都要求细节匹配算法具有一定的弹性，也就是说细节匹配算法应该能在一定程度上容忍由于提取出来的细节点位置不准确或图像的非线性形变造成的对应点位置的差异。Anil Jain 等人[4]通过对[10]中介绍的算法增加一种自适应性来处理弹性匹配问题。[10]中的方法在每一个模板细节点上加了一个限界盒（bounding box ）,限定了与该模板细节点对应的输入细节点可能存在的区域。[4]文中给这种方法增加了一定的自适应性，当在匹配过程中检测到一个不精确的匹配时（对应点的位置有一定差异），在其后的匹配中对模板细节点的限界盒做一定的调整，从而使算法具有一定的处理局部细节点位置差异与非线性形变的能力。本文中我们将采用尺寸可变的限界盒来取代[4]中所用的大小固定的限界盒，使匹配算法对非线性形变更为鲁棒。

3.1 细节点集的校准

令

=)(,...,)111(,,,,θθp M p M p M p p p P y x y x T T 表示模板图像中的M 个细节点，

=)(,...,)111(,,,,θθQ N Q N Q N Q Q Q Q y x y x T T 表示输入图像中的N 个细节点，

为了把细节点转换到极坐标系中去，我们要在模板细节点集和输入细节点集中各选一个参照点作为相应的极坐标系中的原点，并算出其它细节点相对与参照点的极坐标。由于我们事先并不知道模板点集与输入点集的对应关系，我们将考虑所有可能的参照点对。

图4、输入脊线与模板脊线的校准

对模板点集中的每一点P i (1≤i ≤M)和输入点集中的每一点Q j (1≤j ≤N)，定义rotate[i][j] 为将P i 和Q j 当作参照点对时，从输入图像到模板图像的旋转角度。如果P i 与Q j 可以被当成一对对应点，即它们分别对应的脊线相似性到一定程度，则rotate[i][j]将取0度360度间的一个值，否则我们定义rotate[i][j]取值为400以表示P i 与Q j 不能不是一对对应点。如果P I 和Q j 是不同类型的细节点，也就是说它们一个是脊线末梢，一个是脊线分支，则它们(P i 与Q j )不是对应点对，rotate[i][j]取值为400。注意，rotate[i][j]<400表示P i 与Q j 对应的脊线相似性到了一定程度。

如果P I 和Q j 是相同类型的细节点，也就是说它们都是脊线末梢或都是脊线分支，如果记录的对应脊线中的点个数不同，设置则它们(P i 与Q j )是不是对应点对及rotate[i][j]的取值将由如下算法决定。

用R 表示细节点P i 对应的脊线，r 表示细节点Q i 对应的脊线。匹配r 与R ，用下式来计算这两条脊线间的差异：

∑∑==?=?=L i i i L i i i r R L

ang Diff d r d R L dist Diff 00)()(1_)()(1_αα (1) 其中L 是记录的脊线中的点个数，R(d i )和r(d i )分别表示从脊线R 与r 上的点i 到对应的细节点的距离，R(αi )和r(αi )分别表示连接脊线R 与r 上的点i 与对应的细节点的直线同对应细节点的方向的夹角。见图4。

如果这两条脊线的差异Diff_dist 和Diff_ang 分别小于某个阈值T d 和T α，也就是说这两条脊线的形状在一定程度上相似，那么P i 和Q j 能被当作对应细节点对，rotate[i][j]为:

ir_in dir_temp-d j i rotate =]][[ (

)2 其中dir_temp 和dir_in 分别是P i 和Q j 的方向。

如果Diff_dist 大于T d 或Diff_ang 大于T α也就是说两条脊线彼此不相似，那么细节点P I 与Q j 不能被当作对应细节点对，我们将rotate[i][j]的值设为400。

要在极坐标系中将输入图像与模板图像校准，只需将输入细节点与模板细节点都分别相对于参照点P i 和Q j 转换到极坐标系中，然后在所有输入细节点的极角上加一个角度rotate[i][j]。也就是说，将输入细节点与模板细节点都分别相对于参照点P i 和Q j 用下式转换到极坐标系中

()()

? ??+= ???θθθr i i r i i i i x x y y y y x x e r r i r i tan 122 ( )3其中(x i , y i , θi )T 是待转换细节点的坐标，(x r , y r , θr )T 是参照细节点的坐标， (r i ,

e i , θi )T 是细节点在极坐标中的表示(r I 表示极半径，e I 表示极角，θI 表示细节点相对于参照细节点的方向)。然后，我们对每一个输入细节点的e

i 加一个角度rotate[i][j]。图5给出了一个校准的例子。

图 5 一个校准的例子 (a)细化后的模板图像。(b) 细化后的输入图像。(c)将

输入图像旋转一个由(a)和 (b)中的参照细节点决定的角度. (d).输入图像与模板图像的校准结果，其中参照细节点互相重叠。

3.2 校准后的细节匹配

我们的细节匹配算法步骤如下:

1) 对每一个i(1≤i ≤M)和每一个j(1≤j ≤N)，如果rotate[i][j]=400，即细节点P I 与Q j 不能被当作对应细节点对,则重复此步并选择另一对P i 和Q j ，否则转向步骤2)。如果所有的细节点对都已考虑过了，则转向步骤5)。

2) 将P I 和Q j 当作参照细节点，用3.1节中的方法将输入点集和模板点集中的细节点都转换成极坐标。

3) 将极坐标中的模板细节点和输入细节点按极角递增方向排序，并连接成串，表示如下；

=)(,...,)111(,,,,θθp M p M p M p p p e r e r P T T s i )4(

=)(,...,)111(,,,,θθQ N Q N Q N Q Q Q e r e r Q T T s j )5( 其中(r *P , e *P , θ*P )和(r *Q , e *Q , θ*Q )表示对应的极半径，极角和相对于参照

点的细节点方向。

4) 用后面将要介绍的方法匹配串P i s 和Q j s ，找出匹配分数，记录为m_score[i][j]。然

后转回步骤1).

5) 找出m_score[i][j]中的最大值，把它当做输入细节点集与模板细节点集的匹配分数。如果匹配分数高于一个预先设定的阈值，则认为输入图像与模板图像来自同一个指纹，否则认为它们来自不同指纹。

图6、限界盒 图7、（a ）固定大小的限界盒。(b)可

变大小的限界盒

在介绍匹配串P i s 和Q j s 的方法之前，我们先介绍一下限界盒及其大小。

如图6所示，一个限界盒是放在模板细节点上的一个盒子.这个盒子的一对边的极角为常数，另一对边的极半径为常数。用 angle_size 表示极半径为常数的那对边的极角差异:

angle_size=angle_high-angle_low .

同样，用radius_size 极角为常数的那对边的极半径的差异:

radius_size=radius_high-radius_low .

限界盒的大小用angle_size 和radius_size 来表示。

[4]文中使用了一个固定大小的限界盒，即在所有的模板细节点处angle_size 和radius_size 取同样的值。我们将使用可变大小的限界盒，即 angle_size 和radius_siz e 的值将随着细节点的极半径大小而改变。如果模板细节点的极半径比较大，它的限界盒将有一个较大的radius_size 和较小的angle_size 。固定大小与可变大小限界盒的差异可从图7中看出来。用下式来计算极半径为r 的模板细节点的radius_size 和angle_size 。

arg r_ if arg _arg _ if r_ l r_ if __ ><<<=e

r_l size e l r e r_l size r r_small size r_smal size small r size radius ( )6α

r size r =_ ( )7 arg a_ if arg _arg _ if _ l a_ if __ ><<<=e

a_l size e l a e a_l size a a_small size a a_smal size small a size angle )8(r size a 2_β

= (

)9 其中r_small, r_large, a_small, a_large 分别是radius_size 和angle_size 的上界和下界,它们的值是预先设定的。α和β是预先给定的常数。

我们使用可变大小的限界盒而不是固定大小的限界盒是为了使算法对非线性形变更为鲁棒。非线性形变一般在一个特定的区域内较大，然后非线性地向外扩张。当细节点的极半径较小时，小的形变就可以造成大的极角的改变，而极半径的改变较小。所以在这种情况下限界盒的angle_size 应该比较大而radius_size 则应该较小。另一方面，当细节点的极半径较大时，极角的较小改变就会造成细节点位置的较大变动，而极半径的形变可以看成是该细节点与参照细节点间的所有区域的形变的累加。所以在这种情况下限界盒的angle_size 应该比较小而radius_size 则应该较大。我们在由100个指纹组成的小数据库上的实验表明用可变大小的限界盒可以使匹配率提高至少3个百分点。

用input_point[L]表示输入串Q j s 的第L 个点，template_point[k]表示模板串P i s 的

第k 个点。用angle_size[k]和radius_size[k]表示模板串中第k 个细节点的限界盒大小。angle_high[k], angle_low[k], radius_high[k], radius_low[k]表示模板串中第k 个细节点的限界盒的四边的值，它们的初值如下：

angle_high[k]=angle_size[k]/2

angle_low[k]= -angle_size[k]/2

radius_high[k]=radius_size[k]/2

radius_low[k]= - radius_size[k]/2

匹配P i s 和Q j s

的算法描述如下：

1) 用(6),(7),(8)和(9)式决定每一个模板细节点的限界盒的大小，获得angle_high[k], angle_low[k], radius_high[k], radius_low[k]对每一个k(1≤k ≤M)的值。置m_score[i][j]=0.

2) 做如下循环：

While 1≤k ≤M do

While 1≤L ≤N and e L P < angle_high[k] do

if template_point[k] and input_point[L] satisfy condition1, then

m_score[i][j]= m_score[i][j]+1;

调整限界盒;

end if

Increase L;

End while

Increase k;

End while

上述过程中, condition1定义为:

<

otherwise 400]][[ if 1false l k rotate [k]angle_high e k]angle_low[h[k]radius_hig )

-([k]radius_low true condition r r Q k p l εθ )10(

?<+?==? otherwise 180081360) mod )360(( if a a a e e e Q k P

L ( )11

?<+?==? otherwise 180081360) mod )360(( if a a a Q k P

L θθθ )12( condition1是将template_point[k]和input_point[L]看作对应点对的条件。其含义是，要将任意两个细节点template_point[k]和input_point[L] 看作对应点对的条件，input_point[L]应该在template_point[k]的限界盒的内部，这两个细节点的方向差异应小于ε(我们设置ε=30),rotate[k][l]应小于400，即P k 和Q l 对应的脊线不相似. 将体现在rotate[i][j]中的脊线信息引入到匹配过程中来的作用主要体现在两个方面。一个方面是在指纹细节匹配中，如何选择可靠的参照点对一直是一个难题，而如果将所有可能的点对分别当作参照点对来计算又将带来计算量太大的问题。我们的算法中通过引入脊线信息，在参照点对的选取中，细节点P i 与Q j 能被当作参照点对，则必须rotate[i][j]<400，即P i 与Q j 对应的脊线有一定程度的相似性,这样做大大减少了可能的参照点对的数目，使得我们的算法既保证了计算的速度，又有效地解决了参照细节点对的选取问题。另一个方面是引入脊线信息能有效地防止两幅来自不同指纹的图像被错误地匹配为来自同一个指纹的，同时，它对来自同一幅指纹的图像的匹配的影响很小。这是因为如果两幅图像来自同一个指纹，则它们的对应点所对应的脊线往往也是相似的，而如果两幅图像来自不同指纹，则很可能点对P k 和Q l 满足作为对应点对的所有其它条件但rotate[k][l]=400，即它们对应的脊线不相似。将rotate[i][j]引入匹配过程的效果的

一个例子见图8。图8(a)和(b)给出了来自不同指纹的两幅图像的细化后图像。图8(c)给出了匹配过程中不使用rotate[i][j]的匹配结果，15对细节点被认为是对应点。图8(d) 给出了匹配过程中使用rotate[i][j]的匹配结果，仅6对细节点被认为是对应点。

调整限界盒的做法如下：

对每一个模板细节点template_point[m]，其中 m>k且e m Q- e k Q <120执行以下操作:

angle_high[m]= angle_high [m]+λ(r L p-r k Q)

angle_low[m]= angle_low[m]+ λ(r L p-r k Q)

radius_high[m]=radius_high[m]+λΔe

radius_low[m]=radius_high[m]+ λΔe

其中Δe由(11)定义.λ是一个预先给定的值，设置为0.5。一旦检测到一对对应点，我们将对那些还没有拿来匹配，又在从template_point[k]开始的一个扇形区域内的模板点的限界盒位置进行调整。

Fig.8.在匹配过程中引入rotate[i][j]的效果的例子

4 实验结果

我们用来测试本文介绍的算法的指纹数据库包含1000从100个不同手指采集的1000幅指纹图像，每个手指采集了10幅图像。图像的大小是300×300,图像是用VERIDICOM公司生产的指纹采集仪采集的。采集图像时没有限制手指的位置和方向。

指纹库中的每一幅图像都与库中所有其它的图像做匹配，总共做999000 (999×1000) 次匹配。如果两幅图像的匹配分数比一个阈值高，就称它们是匹配得好的，即认为它们来自同一个手指。

在指纹认证中，定义来自同一个手指的10幅图像为一个模板，我们的指纹库中总共有100个模板。每一幅图像都与它自己所在的模板（包含其它9幅图像）和其它99个模板进行匹配。如果一幅图像能与一个模板中的三幅或更多图像匹配得好，就说它与该模板匹配得好，即认为它与该模板中的图像来自同一个手指。如果一幅图像不能与包含它自己的模板匹配得好，就认为该图像被拒识了。如果一幅图像与包含它自己的模板匹配得好，就产生了一个正确识别。如果一幅图像与来自不同手指的模板匹配得好，就产生了一个错误识别。

定义reject_num为被拒识的图像数目,correct_num为正确识别的次数，false_num 为错误识别的次数，识别率与拒识率用下式计算：

%100___×+=

num

false num correct num correct 识别率 )14(%1001000

_×=num reject 拒识率 )15( 表I 给出了我们的指纹认证实验结果，列出了在一定识别率下的拒识率。表I 还给出了用VERIDICOM 公司随指纹采集仪自带的算法实验的结果。从表I 可以看出我们的算法比VERIDICOM 公司随指纹采集仪自带的算法效果要好。另外，我们的实验是在PII350微机上完成的，每一次匹配的时间平均为0.018秒，用VERIDICOM 公司随指纹采集仪自带的算法每一次匹配的时间平均为0.012秒，速度上相差不大。这显示了我们算法的实用性。[4]文中报告的结果为在SPARC 20工作站上每一次匹配的时间平均为2.55秒。

在指纹识别中,每幅图像k(k=1, 2, …, 1000)与指纹库中的其它999幅图像匹配，记录下与k 匹配分数最高的前n(n=1, 2, …, 10)幅图像.如果在前n(n=1, 2, …, 10)幅图像中至少有一幅正确的图像（与图像k 来自同一个手指的图像），就将match_num[n] 增加1。match_num[n] 定义为正确的前n 名匹配的总数。前n 名匹配的匹配率计算如下：

%1001000

][_×=n num match 匹配率 )16( 表II 给出了我们实验中的匹配率。

基于三个原因我们没有用我们的算法与[4]文中的算法做比较。一是我们用的实验数据库与[4]文所用的不同，我们无法得到他们用的数据库。二是我们没有他们的识别系统，如果我们自己编程序实现他们的算法，再拿来与我们的算法做比较，对他们来说是不公平的，因为可能有很多技术细节是论文中涉及不到的。三是[4]文中没有给出计算识别率，拒识率和匹配率的公式，但显然他们所用的公式与(14)，（15），(16)是不同的。因为如果用（14）式来计算识别率，对[4]文中实验用的仅包含180幅图像的指纹库,他们所报告的99.996%的识别率是不可能有的数字。同样，如果用(16)来计算匹配率，99.94%这样的数字是不可能的。

表 I: The verification rate and Reject rate

The method of this paper The method of VERIDICOM Corp.

Verification rate Reject rate Verification rate Reject rate

100% 15.60% 100% 17.10% 99.883% 14.10% 99.648% 15.00% 99.770% 13.20% 99.421% 14.10% 99.211% 11.90% 98.761% 12.30% 98.456% 10.70% 97.019% 12.10%

Table II. Top 10 matching rate

Number of best matches Matching rate

1 98.3%

2 98.9%

3 99.1%

4 99.1%

5 99.1%

6 99.2%

7 99.3%

8 99.4%

9 99.4%

10 99.4%

5 总结与讨论

本文介绍了一种处理指纹识别中的细节匹配问题的算法。这种算法改进了[4]文中提出的利用极坐标中的点模式匹配来做细节匹配的算法。我们用了一种更简单也更有效的方法来做指纹图像的校准。另外，我们在匹配的过程中引入了脊线信息并使用了一个大小可变

的限界盒，这使得我们的算法具有更强的分辨来自不同指纹的图像的能力，并能更鲁棒地处理指纹图像的非线性形变。

在实验过程中，我们发现主要有三类情况我们的算法不能有效的处理。第一种情况是图像质量很差时，经常会检测到很多伪细节点而丢掉很多真细节点。在这种情况下，匹配结果严重依赖于图像增强算法和细节提取算法的鲁棒性，在细节匹配中则难有大的作为。第二种情况是当来自同一个手指的两幅图像的共同区域很小时。在我们的指纹库中就有好几例这样的情况，一幅图像与来自同一个手指的其它9幅图像的共同区域都较小。在实际应用中，这种问题可以简单地通过重新采集指纹图像来克服。第三种情况是当来自同一个手指的两幅图像的共同区域间的非线性形变太大时。实际上，在使算法能忍受大的非线性形变与使算法具有较强的区分来自不同手指的图像的能力之间有一个折中，算法能忍受非线性形变的能力越强，它对来自不同手指的图像的区分能力就越差，这也是识别率与拒识率之间的折中。我们认为要更好地处理这个问题，使算法具有更强的忍受非线性形变的能力，同时又不影响对来自不同手指的图像的区分能力，就需要在匹配的过程中引入更多的脊线信息。而用什么样的方式才能在匹配过程中简单而有效地引入更多的脊线信息是需要进一步研究的问题。

参考文献

[1] C.H.Liu, J.H.Liu, J.W.Osterberg and J.D.Nicol, Fingerprint comparison. I: Similarity of

fingerprints. Journal of Forensic Science. 27. 290-304(1982)

[2] D.K.Isenor and S.G.Zaky, Fingerprint Identification using graph matching, Pattern

Recognition, Vol.19, No.2, pp.113-122,1986

[3] A ndrew.K.Hrechak and James A.Mchugh, Automated fingerprint recognition using structural

matching. Pattern Recognition, Vol.23, No.8, pp.893-904,1990

[4] A nil Jain, Lin Hong and Ruud Bolle, On-Line Fingerprint Verification, IEEE Trans on

Pattern Analysis and Machine Intelligence, vol.19, No.4. pp302-313, 1997

[5] S anjay Ranade and Azriel Rosenfeld, Point Pattern Matching by Relaxation, Pattern

Recognition, Vol.12, pp.269-275, 1980

[6] S hih-hsu Chang, Fang-Hsuan Cheng, Wen-hsing Hsu and Guo-zua Wu, Fast algorithm for point

pattern matching: invariant to translations, rotations and scale changes. Pattern Recognition, Vol.29, pp.311-316,1997

[7] Q inghan Xiao and H. Raafat, Fingerprint Image Postprocessing: A Combined Statistical and

Structural Approach, Pattern Recognition,Vol 24, No.10, pp.985-992,1991.

[8] L in Hong, Yifei Wan, and Anil Jain, Fingerprint image enhancement: algorithm and

performance evaluation, IEEE Trans On Pattern Analysis and Machine Intelligence, Vol.20, No.8, pp.777-789, 1998

[9] D.C.Huang, Enhancement and feature purification of fingerprint images, Pattern

Recognition, Vol.26, No.11, pp.1661-1671, 1993

[10] N.Ratha, S.Chen, and A.K.Jain, Adaptive flow orientation based feature extraction in

fingerprint images, Pattern Recognition, Vol.28, No.11, pp1657-1672, 1995

A Minutia Matching algorithm in Fingerprint Verification

LUO XIPING, TIAN JIE

AILAB, Institute of Automation, The Chinese Academy of Sciences, Beijing,100080

(e_mail: tian@https://www.sodocs.net/doc/7c18403313.html,)

Abstract: Fingerprint matching is one of the most important problems in AFIS. In general, we use minutiae such as ridge endings and ridge bifurcation to represent a fingerprint and do fingerprint matching through minutiae matching. In this paper, we proposed a minutia matching algorithm which modified Jain et al.'s algorithm. In our algorithm, a simpler alignment method is used. We introduced ridge information into the minutiae matching process in a simple but effective way and solved the problem of reference point pair selection with low computational cost. In addition, we used changeable sized bounding box to make our algorithm more robust to nonlinear deformation between fingerprint images. Experiments done on a set of fingerprint images captured with an inkless scanner shows that our algorithm is fast and has high accuracy.

Index terms : fingerprint, minutia matching, AFIS

Suprema指纹识别算法介绍

Suprema指纹识别算法介绍 产品名称：Suprema指纹识别算法介绍 产品型号：OTA750采用的指纹算法 产品分类：Suprema指纹识别算法介绍 详细介绍： OTA750彩屏指纹考勤机的指纹算法采用了世界上最可信赖的Suprema指纹识别算法，产品的稳定性、指纹的安全可靠性得到了有力的保障。 Suprema指纹识别算法介绍 Suprema拥有世界一流的指纹识别技术。Suprema解决方案的特点在于对算法拥有极强的理论背景。Suprema的指纹识别算法在世界上最值得信赖的世界指纹识别大赛 (International Fingerprint Verification Competition, (FVC2004) 上摘取冠军桂冠，在light category表现出最小的出错率，被认为是世界上最可信赖的指纹解决方案，再加上其优越的技术力量可确保客户产品及应用软件的 最佳稳定性和信赖度。 Suprema指纹识别算法比起其竞争对手拥有如下特点及优势： 最高的信赖性.指纹识别中算法可以说是左右其性能的最核心的要素。 在世界指纹识别大赛(FVC2004)中夺得了第一，被认定为世界最好的 指纹识别算法。再加上其优越的技术力量可确保客户产品及应用软 件的最佳稳定性和信赖度。 广泛适用性 卓越的支持 Suprema指纹识别算法在世界指纹识别大赛中所获得成绩 评论 FVC是世界上最大的指纹识别技术评论，也是国际性指纹识别算法大赛,隔年举行并由意大利和美国第三方组织。在最近的两届FVC2004和FVC2006，SUPREMA 指纹识别算法摘取了世界范围的最高桂冠。 成果 在FVC2004和FVC2006，Suprema的指纹识别算法在众多参赛者中脱颖而出分别在Light级别和开放级别中获取了冠军。在FVC2006，Suprema在开放级别中以7枚金牌荣获了桂冠。在FVC2004，Suprema在Light级别中以最小误差率荣获了冠军。Suprema是唯一一家赢得两项级别（开放和Light）冠军的公司，即

指纹识别系统

指纹识别系统 1.1 指纹识别系统原理 指纹识别系统的组成原理。如图1-1所示。图中的学习模块负责采集用户指纹数据，对指纹图像进行预处理，提取这些指纹的特征，作为将来的比对模板存人数据库。而识别模块则负责采集和处理指纹图像，在提取特征后与数据库中的指纹模板进行比对，然后判断是否匹配．得出结论。整个系统的核心就是图像处理、特征提取以及指纹比对。 图1-1 1.2 指纹采集与指纹图像处理方法 目前，主要的指纹采集方法有两种：一种是光学采集器；另一种是用半导体传感器。光学采集器采集指纹是通过把手指沾上油墨后按在白纸上，然后用摄像机把图像转换为电信号。光学采集受外界干扰小、采集精度较高，但是数据量较大，因此处理时问较长。而对于半导体传感器来说，手指的温度、湿度对其测量结果有影响，但是数据量不大，处理比较方便。随着半导体技术的发展，半导体传感器的成本低、体积小、方便集成等优点逐步体现，它已逐步代替光学采集器。指纹鉴定过程的第一个阶段是指纹图像的采集阶段，也就是指纹模板的录A阶段。为了初步确定图像预处理方法，我们必须首先了解指纹传感器获得的图像的尺寸和质量。根据不同的指纹传感器，我们设计不同的方案进行图像采集，并将从各个图中提出特征点储存到数据库中，来产生“活模板”，为后面的指纹鉴定做准备。 指纹图像处理是整个指纹识别过程的核心。常见的指纹图像处理包括滤波增强、二值化、细化、提取特征点四个步骤。在采集指纹图像的过程中，由于采集环境，皮肤表面的性质，采集设备的差异等各种因素的影响，采集的图像会不同程度的受到各种噪声的干扰，从而影响了采集图像的质量。所以实际的指纹图像首先通过一个滤波增强来改善图像的质量，恢复

从数字图像处理技术角度谈谈对指纹识别的认识

从数字图像处理技术角度谈谈对指纹识别的认识 4.1 指纹图像表示 从指纹传感器输出的是指纹原始图像，其数据量比较大。这对整个指纹识别系统的处理和存储都是个不小的负担。在远程采集系统中，对通信带宽会造成较大负荷。因此需要对指纹图像进行压缩存储。指纹图像压缩一般经过图像变换、量化和编码等过程。解压需经过解码、量化解码和反变换等过程。 压缩后的指纹图像需确保指纹特征信息的不丢失不损坏。理论上来讲采用无损压缩算法是最理想的。但经过实践证明，对于分辨率不是很高的指纹图像来说，采用无损压缩的压缩比很低。通常情况下采用JEPG、WSQ和EZW三种压缩算法。 4.2 指纹图像处理 4.2.1 指纹图像增强 刚获得的图象有很多噪音。这主要由于平时的工作和环境引起的。指纹还有一些其他的细微的有用信息，我们要尽可能的使用。指纹图像增强的目的主要是为了减少噪音，增强嵴峪对比度，使得图像更加清晰真实，便于后续指纹特征值提取的准确性. 指纹图像增强常用的是平滑和锐化处理。 （1）平滑处理 平滑处理是为了让整个图像取得均匀一致的明暗效果。平滑处理的过程是选取整个图像的象素与其周围灰阶差的均方值作为阈值来处理的。这种做法实现的是一种简单的低通滤波器。 实验表明：一般的自然图像相邻像素的灰度相关性约为0.9。因此在图像受到白噪声干扰时，以像素的邻域平均值代替中心像素，是一个去除噪声的好办法。算法是：。其中f(x,y)表示被噪声污染的原始图像，大小为N*N，g(n,m)是平滑后的图像，S是处理点(x,y)邻域中点的坐标（不包括（x,y）点）的集合，而M是集合S内坐标点的总数。例如，以(x,y)点为中心，取单位距离构成的邻域，其中点的坐标集合为：s={(x,y+1),(x,y-1),(x+1,y),(x-1,y)}。

基于特征的图像匹配算法毕业设计论文(含源代码)

诚信声明 本人声明： 我所呈交的本科毕业设计论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果由本人承担。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：2010 年05 月20日

毕业设计（论文）任务书 设计（论文）题目： 学院：专业：班级： 学生指导教师（含职称）：专业负责人： 1．设计（论文）的主要任务及目标 (1) 了解图象匹配技术的发展和应用情况，尤其是基于特征的图象匹配技术的发展和应用。 (2) 学习并掌握图像匹配方法，按要求完成算法 2．设计（论文）的基本要求和内容 （1）查阅相关中、英文文献，完成5000汉字的与设计内容有关的英文资料的翻译。（2）查阅15篇以上参考文献，其中至少5篇为外文文献，对目前国内外图象匹配技术的发展和应用进行全面综述。 （3）学习图象匹配算法，尤其是基于特征的图象匹配算法。 （4）实现并分析至少两种基于特征的图象匹配算法，并分析算法性能。 3．主要参考文献 [1]谭磊, 张桦, 薛彦斌．一种基于特征点的图像匹配算法[J]．天津理工大学报，2006， 22(6)，66-69． [2]甘进，王晓丹，权文．基于特征点的快速匹配算法[J]．电光与控制，2009，16(2)， 65-66． [3]王军，张明柱．图像匹配算法的研究进展[J]．大气与环境光学学报，2007，2(1)， 12-15．

指纹识别门禁系统的设计与实现

目录 摘要 .............................................................. I II ABSTRACT ........................................................... I V 第一章绪论 ........................................................ １ 1.1 论文的背景及意义............................................ １ 1.2 识别技术简介................................................ ２ 1.2.1 指纹特点 .............................................. ２ 1.2.2 指纹特征 .............................................. ２ 1.2.3 指纹应用系统简介...................................... ２ 1.2.4 指纹取像技术及其特点.................................. ３第二章指纹门禁系统的总体设计 ...................................... ５ 2.1 系统功能.................................................... ５ 2.2 系统性能指标................................................ ５ 2.3 系统硬件结构................................................ ６ 2.4 系统软件结构................................................ ７第三章指纹门禁系统的硬件设计 ...................................... ９ 3.1 SPCE061A单片机介绍 ......................................... ９ 3.1.1 SPCE061A单片机的主要性能.............................. ９ 3.1.2 指纹识别模块OM-20的管脚说明及性能指标................ ９ 3.1.3 SPCE061A单片机与指纹识别模块OM－20的接口电路设计... １０ 3.2 SPCE061A单片机与液晶显示模块SPLC501的接口............... １１第四章指纹门禁系统的软件设计 .................................... １３ 4.1 指纹处理模块.............................................. １３ 4.1.1 指纹识别模块OM-20通讯协议.......................... １３ 4.1.2 登记指纹模板程序设计................................ １３ 4.1.3 删除指纹模板程序设计................................ １４ 4.1.4 清空指纹模板程序设计................................ １４ 4.2 系统主程序设计............................................ １５ 4.3 指纹开门程序设计.......................................... １５

(完整版)第二章指纹识别的原理和方法

第二章指纹识别的原理和方法 指纹识别的采集及其参数[15] 指纹具有惟一性（随身携带、难以复制、人人不同、指指相异）。根据指纹学理论，将两人指纹分别匹配上12个特征时的相同几率仅为1/1050。指纹还具有终身基本不变的相对稳定性。指纹在胎儿六个月时已完全形成，随着年龄的增长，尽管人的指纹在外形大小、纹线粗细上会有变化，局部纹线之间也可能出现新细线特征，但从总体上看，同一手指的指纹纹线类型、细节特征的总体布局等无明显变化。指纹的这些特点为身份鉴定提供了客观依据。 指纹识别过程可以分为4个步骤：采集指纹图像、提取特征、保存数据和比对。通过指纹读取设备读取到人体指纹的图像,取到指纹图像之后，要对原始图像进行初步的处理，使之更清晰。指纹辨识软件建立指纹的数字表示特征数据，软件从指纹上找到被称为“节点”（minutiae）的特征点，这些数据(通常称为模板)，保存为1K大小的记录。最后，通过计算机模糊比较的方法，把两个指纹的模板进行比较，计算出它们的相似程度，最终得到两个指纹的匹配结果。 2.2.1指纹图像的采集[16][17][18] 指纹采集模式主要分为“离线式”和“在线式”两种。所谓“离线式”就是指在指纹采集时，利用某些中间介质（如油墨和纸张）来获取指纹图像，在通过一定的技术手段将图像数字化输入计算机，它属于非实时采集。目前“离线式”采集方式在大多数场合已经消失。所谓“在线式”是通过与计算机联机的先进指纹传感器的专用指纹采集设备，将真实的人体指纹直接变成数字图像数据，实时传输给计算机。 基于指纹传感器的“在线式”实时采集设备以其操作简单、实时性强、采集效率高、图像质量好等优点，广泛应用于自动指纹识别领域。 指纹传感器是采集指纹的装置,是一切自动指纹识别系统的必备设备,从原理上,目前见到的指纹传感器分下面3类： (1)光学录入

图像匹配搜索算法

本文基于相关性分析来实现图像匹配 第一步：读取图像。 分别读取以下两幅相似的图片，显示效果如下： 第二步：选择一副图像的子区域。用户可以通过鼠标选择需要截取的图像部分，用于匹配。随机选取图片的一块区域，如下图：

第三步：使用相关性分析两幅图像 采用协方差的方式计算相关系数，分析图片的相似性。 1．协方差与相关系数的概念 对于二维随机变量(,)X Y ，除了关心它的各个分量的数学期望和方差外，还需要知道这两个分量之间的相互关系，这种关系无法从各个分量的期望和方差来说明，这就需要引进描述这两个分量之间相互关系的数字特征——协方差及相关系数。 若X Y 与相互独立,则()( )0 Y E X EX Y EY σ--???? =≠;若()()0E X EX Y EY --≠????,则表 示X 与Y 不独立,X 与Y 之间存在着一定的关系 设 (,)X Y 是二维随机变量， 则称()()E X EX Y EY --????为X 与Y 的协方差（Covariance ），记为 ()cov ,X Y 或XY σ，即 ()()()cov ,XY X Y E X EX Y EY σ==--???? 若 0X σ≠ 且0Y σ=≠，则称 XY XY X Y σρσσ== 为X 与Y 的相关系数（Correlation Coefficient ）。()c o v ,X Y 是 有量纲的量，而XY ρ则是无量纲的量．协方差常用下列公式计算

()() =-? cov,X Y E XY EX EY 2．用全搜索和协方差计算截取图片与另外一幅图片的各点的相似度。c=normxcorr2(sub_I1(:,:,1),I2(:,:,1)); 第四步：找到整幅图像的偏移。 [max_c,imax]=max(abs(c(:))); [ypeak,xpeak]=ind2sub(size(c),imax(1)); [m,n]=size(sub_I1); xbegin=xpeak-n+1; ybegin=ypeak-m+1; xend=xpeak; yend=ypeak; 从原图像提取匹配到的图像 extracted_I1=I2(ybegin:yend,xbegin:xend,:); 第五步：显示匹配结果。 相关性匹配图： 找出峰值即最相似区域的中心

基于FPGA的指纹识别系统设计

基于FPGA的指纹识别系统设计 第一章绪论 1.1 设计背景 生物识别技术是利用人的胜物特征进行身份认证的技术, 人的指纹就是生物特征之一。此外, 生物特征还包括虹膜、视网膜、声音和脸部热谱图等。指纹识别是生物识别技术中最为成熟的, 其唯一性、稳定性, 一直都被视为身份鉴别的可靠手段之一。 由于最早的指纹识别技术仅仅依靠人工对比，工作效率低下、比对正确率低、对比对人员的要求高，从而使得指纹识别技术无法得到广泛应用。但随着计算机的出现及其运算速度的迅速提高,使指纹对比鉴定的应用发生了革命性的变化。使用计算机管理指纹数据库,极大提高了指纹对比的速度,同时由于计算机比对算法的不断改进提高,使指纹比对误识率已降到了10 - 6 以下,不仅可以满足刑侦方面的需要,而且迅速进入了更多的应用领域。 随着光学技术和光学仪器加工工艺的进步,各种采集指纹图案进行身份认证的系统和设备中需要配备的高清晰、无畸变光学采集仪也达到了很高水平,确保可以生成高质量的指纹图像。计算机运算速度的提高和计算机小型化的进展,使采用微机甚至单片机也可以进行指纹对比运算成为可能。现代电子集成制造技术使得我们可以生产出相当小的指纹图像读取设备和指纹识别模块。其成本下降得也很快,大大加快了指纹识别技术的推广速度。 同时人们对消费类产品的要求越来越趋向于小型化，并且对可携带设备的安全性要求也与日俱增。传统的PC、MCU、或者DSP的处理平台移动性比较差，体积比较大，无法满足人们日益增长的需求。所以，设计一套体积比较小、速度更快的嵌入式指纹识别系统是非常有意义的。 而本设计正是为了这一目的，选用具有高集成度、低功耗、短开发周期的FPGA来完成此项设计，以实现系统的ASIC为研究背景，具有很强的现实意义和广阔的市场空间。 本系统采用xilinx公司Spartan 3E系列FPGA作为核心控制器件，这款器件采

指纹识别算法基本概述

指纹识别算法基本概述 指纹识别算法，是指在指纹识别过程中，对采集的指纹图像预处理，数据特征提取，特征匹配，指纹识别等一系列解决问题的清晰指令。本文通过对指纹图像预处理、指纹图像特征提取和指纹匹配三方面对指纹识别算法进行整体概述。 一、指纹图像预处理：在指纹识别过程中，刚获取的指纹图像会受到噪声、汗渍以及毛刺等因素影响，使得图像画面不清晰，预处理的目的是改善输入指纹图像的质量，以提高特征提取的准确性。指纹图像预处理在整个指纹识别系统中的地位就好比地基对于整栋房子的作用，预处理图像的好坏将会影响到后面特征提取、指纹匹配的过程，这是在指纹识别过程中要处理好的第一步。指纹图像预处理一般分为四步：图像分割、图像滤波、二值化和细化。 1.图像分割。主要是指获取的原始指纹图像与背景区域之间有混合，需要从两者之间隔离出来，这就需要根据灰度的大小对图像进行初步处理，然后进行归一化及分割处理，消除背景区域。 2.图像滤波。这是指纹图像预处理过程中最核心的一步，主要是通过对受噪音影响的指纹图像去噪，同时对图像进行修复和整理，增强脊线谷线结构对比度，进一步获取更加清晰的图像。 3.二值化。经过图像滤波后，纹线部分得到增强，但脊的强度不完全相同，这种情况主要是表现在灰度值的差异。图像的二值化是指将灰度图像（灰度有255阶）转化为只包含黑、白两个灰度的二值图像，即0和1两个值。这样使脊的灰度值趋于一致，对图像信息进行压缩，节约了存储空间，有利于指纹特征提取和匹配。 4.细化。是指对指纹二值化后指纹的走向、粗细等特征进行图像的细化，使指纹纹线更加平滑。 二、指纹图像特征提取：指纹图像特征提取的算法有很多种，主要有基于灰度图像的细节特征提取、基于曲线的特征提取、基于奇异点的特征提取、基于脊线频率的特征提取等。对指纹图像的特征点进行提取，能有效地减少伪特征点，提取准确的特征点，提高匹配速度和指纹识别性能，降低识别系统的误识率和拒真率。 三、指纹匹配：指纹特征匹配主要是基于细节特征值的匹配，通过对输入指纹细节特征值与存储的指纹细节特征值相比较，实现指纹识别，两者相比较时需要设立一个临界值，匹配时大于这个阈值，则指纹匹配；当匹配时小于阈值，则指纹不匹配。特征匹配是识别系统的关键环节，匹配算法的好坏直接影响识别的性能、速度和效率。 在指纹识别算法中，从指纹输入到匹配需要进行指纹图像预处理、特征提取、指纹匹配三个步骤，这是指纹识别算法所要经历的基本过程，其中每个过程中每个细节的处理还是有很多的，这就不一一详细说明，本文只是大概描述指纹识别算法的基本步骤。 在国内指纹识别算法中，拥有自身指纹识别算法的企业少之甚少，而广州微正智能科技有限公司，拥有自主知识产权的微正指纹识别算法MZFinger5.0，算法优越，匹配精准，安全稳定，在当今市场上拥有很强的竞争力。 指纹识别算法随着科技的进步，在历史的长河中总是在不断地优化发展，性

指纹识别的原理和方法

指纹识别的原理和方法 一、概述 指纹识别的背景知识 我们手掌及其手指、脚、脚趾内侧表面的皮肤凸凹不平产生的纹路会形成各种各样的图案。这些纹路的存在增加了皮肤表面的摩擦力，使得我们能够用手来抓起重物。人们也注意到，包括指纹在内的这些皮肤的纹路在图案、断点和交叉点上各不相同，也就是说，是唯一的。依靠这种唯一性，我们就可以把一个人同他的指纹对应起来，通过对他的指纹和预先保存的指纹进行比较，就可以验证他的真实身份。这种依靠人体的身体特征来进行身份验证的技术称为生物识别技术，指纹识别是生物识别技术的一种。 目前，从实用的角度看，指纹识别技术是优于其他生物识别技术的身份鉴别方法。这是因为指纹各不相同、终生基本不变的特点已经得到公认。 最早的指纹识别系统应用与警方的犯罪嫌疑人的侦破，已经有30多年的历史，这为指纹身份识别的研究和实践打下了良好的技术基础。特别是现在的指纹识别系统已达到操作方便、准确可靠、价格适中的阶段，正快速的应用于民用市场。 指纹识别系统通过特殊的光电转换设备和计算机图像处理技术，对活体指纹进行采集、分析和比对，可以迅速、准确地鉴别出个人身份。 系统一般主要包括对指纹图像采集、指纹图像处理、特征提取、特征值的比对与匹配等过程。现代电子集成制造技术使得指纹图像读取和处理设备小型化，同时飞速发展的个人计算机运算速度提供了在微机甚至单片机上可以进行指纹比对运算的可能，而优秀的指纹处理和比对算法保证了识别结果的准确性。 指纹自动识别技术正在从科幻小说和好莱坞电影中走入我们实际生活中，就在今天，您不必随身携带那一串钥匙，只需手指一按，门就会打开；也不必记住那烦人的密码，利用指纹就可以提款、计算机登录等等。 指纹识别技术主要涉及四个功能：读取指纹图像、提取特征、保存数据和比对。 在一开始，通过指纹读取设备读取到人体指纹的图像，取到指纹图像之后，要对原始图像进行初步的处理，使之更清晰。 接下来，指纹辨识软件建立指纹的数字表示——特征数据，一种单方向的转换，可以从指纹转换成特征数据但不能从特征数据转换成为指纹，而两枚不同的指纹不会产生相同的特征数据。软件从指纹上找到被称为―节点‖（minutiae）的数据点，也就是那些指纹纹路的分叉、终止或打圈处的坐标位置，这些点同时具有七种以上的唯一性特征。因为通常手指上平均具有70个节点，所以这种方法会产生大约490个数据。 有的算法把节点和方向信息组合产生了更多的数据，这些方向信息表明了各个节点之间的关系，也有的算法还处理整幅指纹图像。总之，这些数据，通常称为模板，保存为1K大小的记录。无论它们是怎样组成的，至今仍然没一流种模板的标准，也没一流种公布的抽象算法，而是各个厂商自行其是。 最后，通过计算机模糊比较的方法，把两个指纹的模板进行比较，计算出它们的相似程度，最终得到两个指纹的匹配结果。 指纹识别的原理和方法 二. 取得指纹图象 1.取象设备原理 取像设备分成两类：光学、硅晶体传感器和其他。

算法学习：图论之二分图的最优匹配(KM算法)

二分图的最优匹配（KM算法） KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。 基本原理 该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }

【算法】指纹识别算法基本原理介绍

【算法】指纹识别算法基本原理介绍 在有的国家，指纹属于个人隐私，不能象人工处理那样直接处理指纹图像，所以许多生物识别技术并不直接存储指纹的图像。多年来在各个公司及其研究机构产生了许多不同的数字化算法。指纹识别算法虽然各不相同但是这些算法最终都归结为在指纹图像上找到并比对指纹的特征。我们定义了指纹的两类特征来进行指纹的验证：总体特征和局部特征。 A 总体特征：总体特征是指那些用肉眼就可以直接观察到的特征，包括： 1. 纹形 其他的指纹图案都基于这三种基本图案。仅仅依靠纹形来分辨指纹是远远不够的，这只是一个粗略的分类，通过更详细的分类使得在大数据库中搜寻指纹更为方便快捷。 2. 模式区 模式区是指指纹上包括了总体特征的区域，即从模式区就能够分辨出指纹是属于那一种类型的。有的指纹识别算法只使用模式区的数据。 SecureTouch的指纹识别算法使用了所取得的完整指纹而不仅仅是模式区进行分析和识别。 3. 核心点 核心点位于指纹纹路的渐进中心，它在读取指纹和比对指纹时作为参考点。许多算法是基于核心点的，既只能处理和识别具有核心点的指纹。核心点对于SecureTouch的指纹识别算法很重要，但没有核心点的指纹它仍然能够处理。 4. 三角点

三角点位于从核心点开始的第一个分叉点或者断点、或者两条纹路会聚处、孤立点、折转处，或者指向这些奇异点。三角点提供了指纹纹路的计数跟踪的开始之处。 5. 纹数 指模式区内指纹纹路的数量。在计算指纹的纹数时，一般先在连接核心点和三角点，这条连线与指纹纹路相交的数量即可认为是指纹的纹数。 B 局部特征 局部特征是指指纹上的节点的特征，这些具有某种特征的节点称为特征点。两枚指纹经常会具有相同的总体特征，但它们的局部特征--特征点，却不可能完全相同。指纹纹路并不是连续的、平滑笔直的，而是经常出现中断、分叉或打折。这些断点、分叉点和转折点就称为“特征点”。就是这些特征点提供了指纹唯一性的确认信息。指纹上的节点有四种不同特性： 1.特征点的分类：有以下几种类型，最典型的是终结点和分叉点。 终结点 一条纹路在此终结。 分叉点 一条纹路在此分开成为两条或更多的纹路。 分歧点 两条平行的纹路在此分开 孤立点 一条特别短的纹路，以至于成为一点。 环点 一条纹路分开成为两条之后，立即有合并成为一条，这样形成的一个小环称为环点。 短纹 一端较短但不至于成为一点的纹路。

指纹图像预处理及特征提取算法的研究与实现

2012年1月 内蒙古科技与经济 Januar y 2012　第1期总第251期 Inner M o ngo lia Science T echnolo gy &Economy N o .1T o tal N o .251 指纹图像预处理及特征提取算法的研究与实现 X 张松宇1,杨文斌2 (1.内蒙古机电职业技术学院;2.内蒙古灵奕信息技术有限责任公司,内蒙古呼和浩特　010070) 摘　要:提出了一套完整的基于方向特性的指纹预处理算法,包括前景/背景分割、方向滤波、二值化、细化4部分。特征提取采用8邻域方法提取纹线中的两种细节特征——端点和分叉点。实验结果表明,指纹图像经过预处理算法后提取出了纹线,并且很好地保留了纹线的关键信息,对特征提取奠定了良好的基础。指纹图像经过特征提取后,准确有效地定位了两类特征点。 关键词:指纹;预处理;特征提取 中图分类号:T P391.41 文献标识码:A 文章编号:1007—6921(2012)01—0083—02 自动指纹识别技术大多是依靠指纹的细节特征提取实现指纹的匹配的。准确地提取细节特征是自动指纹识别系统获得高识别率的前提和基础。指纹的细节特征主要指脊线端点和分叉点。在实践中,由于手指本身的因素和采集条件的限制,采集到的指纹图像会不同程度地受到各种噪声的干扰。这种干扰最终会影响系统的识别率。因此,在提取指纹特征前必须对输入的指纹图进行预处理。预处理的目的是:去除原图像中的噪声,把它变成一幅清晰的二值点线细化图,以便于提取正确的细节特征。笔者提出了一套较完善的指纹预处理算法,包括图像分割、方向滤波增强、二值化、细化等步骤,并准确有效地提取出了指纹的细节特征点。1　预处理算法 1.1　规格化和图像分割 规格化的主要目的在于消除指纹采集过程中由于传感器自身的噪声以及因为手指压力不同而造成的灰度差异,将不同的指纹图像的对比度和灰度调整到一个固定的级别上。图像分割是把指纹前景区与背景区分开。前景区域中指纹脊和谷的灰度差是比较大的,因而其灰度统计特性中局部灰度方差是很大的,而对于图像背景区域,这一值是很小的。基于这一特性,我们可以利用图像的局部方差对指纹图像进行分割。规格化与图像分割后的指纹图像见图1。 1.2　方向图滤波 方向图是指纹图像的一种变换表示方式,即用纹线的方向来表示该纹线。方向图有点方向图和块方向图两种,点方向图表示指纹图像中每一像素点脊线的方向,而块方向图则表示指纹图像中每一块 脊线的大致方向。 图1　原始图像的规格化与分割 方向滤波器是一系列与像素点方向有关的滤波器模板,使用时根据方向特性,从中选择一个对应的滤波器进行滤波。笔者使用的方向滤波器有8个滤波器模板组成,滤波时,指纹图中每一点的灰度值由其周围48个点的灰度值及相应的模板系数共同决定(即灰度值与相应的模板系数相乘并把结果相加,然后赋给中心像素点,作为其灰度值)。方向滤波增强后的指纹图像见图2 。 图2　方向滤波后指纹图像 1.3　二值化和细化 二值化的目的是把灰度指纹图像变成0和1的二值图像。笔者采用局部自适应阈值法中的动态阈值法对图像二值化,它可以根据局部灰度值的变化情况调整阈值大小,实验证明该方法效果较好。 二值化后的图像脊线仍具有一定的宽度,为了提高获取特征点精度,需要把脊线细化成为一个像 ? 83?X 收稿日期:2011-11-28

指纹识别中的一种细节匹配算法

指纹识别中的一种细节匹配算法 罗希平田捷* (北京中国科学院自动化研究所人工智能实验室 100080) 摘要:指纹匹配是AFIS中最重要的问题之一。一般用象脊线末端和脊线分支点这样的细节点来表示一个指纹，并通过细节匹配来做指纹匹配。本文提出一种细 节匹配算法，这种算法对Anil Jain等人提出的细节匹配算法进行了修正。我们 采用了一种新的更简单的方法来进行指纹图像的校准，并以一种简单而有效的方 式将脊线信息引入匹配过程中，这样做的好处之一是以较低的计算代价有效地解 决了匹配中参照点对的选取问题。另外，我们采用了大小可变的限界盒来适应指 纹的非线性形变。我们的算法能更好地区分来自不同指纹的图像，并能更加有效 地处理来自同一个指纹的被匹配图像之间的非线性形变。对用活体指纹采集仪采 集的指纹图像集所做的实验显示我们的算法有较快的速度和较高的准确率。 关键词: 指纹识别, 细节匹配, 自动指纹识别系统(AFIS) 1. 背景介绍 自动指纹识别系统（即Automated Fingerprint Identification System，简称AFIS）有着广泛的应用背景。 指纹识别是要决定两幅指纹图像是否来自同一个手指。过去人们对指纹识别做了很多研究。D.K.Isenor等人[2]提出了一种用图匹配来对两幅指纹图像进行匹配的方法。Andrew K.Hrechak等人[3]用结构匹配来做指纹识别。但目前最常用的方法用是FBI提出的细节点坐标模型来做细节匹配。它利用脊末梢与脊线分支点这两种关键点来鉴定指纹。通过将细节点表示为点模式，一个自动指纹认证问题可以转化为一个点模式匹配（细节匹配）问题。一般的点模式匹配问题是模式识别中的一个有名的难题，人们对一般的点模式匹配问题提出过很多的算法，象sanjay Ranade等人[5]的松弛算法，Shih-hsu Chang等人[6]基于二维聚类的快速算法。Anil Jain等人在[4]针对指纹匹配中的点模式匹配问题提出了一种算法，该算法将直角坐标系中的细节点转换到极坐标系中，通过串匹配算法来进行点匹配。 本文的算法参考了Anil Jain等人[4]的算法。但与[4]中的算法有三个主要差别。首先，我们采用了一种更为简单而有效的指纹图像校准方法。其次，与[4]中仅在校准阶段使用脊线信息的做法不同，我们将脊线信息引入了随后的匹配过程中,在本文第三部分我们将讨论这样做的好处。最后，[4]中的方法在匹配过程中使用了一个固定大小的限界盒，而我们的算法采用了一个大小可变的限界盒，从而使算法能更有效地处理被匹配的两幅指纹图像之间的非线性形变，被匹配的两幅指纹图像之间的非线性形变是指纹匹配中最难解决的问题之一。 我们的自动指纹识别系统框图如图1所示，系统由离线部分和在线部分两个部分组成。在系统的离线部分，用指纹采集仪采集指纹，提取出细节点，然后将细节点保存到数据库中，形成指纹模板库。在系统的在线部分，用指纹采集仪采集指纹，提取出细节点，然后将这些细节点与保存在数据库中模板细节点进行匹配，判断输入细节点与模板细节点是否来自同一个手指的指纹。 本文受国家自然科学基金资助，课题号为：69875019 *：本文联系作者,e_mail:tian@https://www.sodocs.net/doc/7c18403313.html,, 电话：82618465

图像匹配的主要方法分析

图像匹配的主要方法分析 在我国的图像处理中，有很多的关键技术正在不断的发展和创新之中。这些相关技术的发展在很大程度上推动了我国图像处理事业的发展。作为图像处理过程中的关键技术，图像匹配技术正在受到越来越多的关注。文章针对图像匹配的主要方法进行详细的论述，希望通过文章的阐述和分析能够为我国的图像匹配技术的发展和创新贡献微薄力量，同时也为我国图像处理技术的发展贡献力量。 标签：图像处理；图像匹配；特征匹配；方法 在我国的图像处理技术中，图像的匹配技术不仅仅是其中的重要组成部分，同时还是很多图像技术的发展创新的技术基础。例如图像技术中的立体视觉技术；图像技术中的运动分析技术以及图像技术中的数据融合技术等。通过上述内容可以看出，在我国的图像技术中，图像匹配技术具有非常广泛的应用。随着我国的相关技术不断的创新和发展，对于图像匹配技术的要求也是越来越高。这样就要求我国的图像匹配技术有更深层次的研究和发展。我国现阶段的研究主要是针对图像匹配过程中的匹配算法进行研究，希望借助研究能够更加有效的提升在实际的工作应用中的图像质量，同时也能够在很大程度上提升图像处理的图像分别率。文章的主要陈述点是通过图像匹配技术的具体方法进行优点和缺点的分析，通过分析优点和缺点来论述我国图像处理技术中的图像匹配技术的发展方向以及改进措施。近些年出现了很多的图像匹配方法，针对现阶段的新方法以及新的研究思路我们在实际的应用过程中要有一个非常清醒的选择。文章针对这一问题主要有三个内容的阐述。第一个是图像匹配技术的算法融合；第二个是图像匹配技术中的局部特征算法；最后一个是图像匹配技术中的模型匹配具体算法。 1 现阶段在世界范围内较为经典的图像匹配技术的算法 关于现阶段在世界范围内的较为经典的图像匹配技术的算法的阐述，文章主要从两个方面进行分析。第一个方面是ABS图像匹配算法。第二个方面是归一化相互关图像匹配算法。下面进行详细的论述和分析。 （1）算法一：ABS图像匹配算法。ABS图像匹配算法最主要的原理就是要使用模板的图像以及相应的匹配图像的搜索用窗口之间的转换差别来显示两者之间的关联性。图像匹配的大小在数值上等同于模板图像的窗口滑动顺序。窗口的每一次滑动都会引起模板图像的匹配计算。现阶段ABS的算法主要有三个，如下： 在选择上述三种计算方法的过程中要根据实际情况社情相应的阀值，否则会出现很高的失误率。上述的三种算法使用范围较狭窄。只使用与等待匹配的图像在模板影像的计算。 （2）算法二：归一化相互关图像匹配算法。归一化相互关的图像匹配算法在现阶段是较为经典的算法。通常专业的称法为NC算法。此计算方法主要是采

指纹识别系统(文献综述)

指纹识别方法的综述 摘要 : 对在指纹的预处理和特征提取、指纹分类、指纹的匹配过程中的方向图、滤波器、神经网络等关 键性原理和技术做了详细的说明, 并对在各个过程中用到的方法做了进一步的比较, 讨论了各种方法的优越性。 0引言 自动指纹识别是上世纪六十年代兴起的,利用计算机取代人工来进行指纹识别的一种方法。 近年 来, 随着计算机技术的飞速发展,低价位指纹采集仪的出现以及高可靠算法的实现,更使得自动指纹识 别技术越来越多地进入到人们的生活和工作中, 自动指纹识别系统的研究和开发正在成为国 内外学术 界和商业界的热点。相对于其他生物特征鉴别技术例如语音识别及虹膜识别, 指纹识别具有许多独到 的优点 ,更重要的是它具有很高的实用性和可行性,已经被认为是一种理想的身份认证技术 有着十分 广泛的应用前景, 是将来生物特征识别技术的主流。 , 1指纹取像 图1 是一个自动指纹识别系统 AFIS(Automated Fingerprint Identification System)的简单流程。 指纹取像→ 图像预处理 → 特征提取 → 指纹识别 ↓↑ 数据库管理———— 将一个人的指纹采集下来输入计算机进行处理是指纹自动识别的首要步骤。指纹图像的获取主要利用设备取像,方便实用 , 比较适合 AFIS 。利用设备取像的主要方法又利用光学设备、晶 体传感器和超声波来进行。光学取像设备是根据光的全反射原理来设计的。晶体传感器取像是根据谷线和脊线皮肤与传感器之间距离不同而产生的电容不同来设计的。超声波设备取像也是采用光波来取像,但由于超声波波长较短,抗干扰能力较强,所以成像的质量非常好。 2图像的预处理与特征提取 无论采取哪种方法提取指纹 ,总会给指纹图像带来各种噪声。预处理的目的就是去除图像中的 噪 音,把它变成一幅清晰的点线图 ,以便于提取正确的指纹特征。预处理是指纹自动识别过程的第 一步 , 它的好坏直接影响着指纹识别的效果。常用的预处理与特征提取( Image Preprocessing and Feature Ex2 t raction) 方法的主要步骤包括方向图计算、图像滤波、二值化、细化、提取特征和后处理。 当然这些步骤 可以根据系统和应用的具体情况再进行适当变化。文献[ 1 ] 提出了基于脊线跟踪的方法能够

图的匹配——匈牙利算法与KM算法

图的匹配 一、什么是图的匹配 1.图的定义 无向图：无向图G 是指非空有限集合V G ，和V G 中某些元素的无序对的集合E G ，构成的二元组(V G ，E G )。V G 称为G 的顶点集，其中的元素称为G 的顶点。E G 称为G 的边集，其中的元素称为G 的边。在不混淆的情况下，有时记V ＝V G ，E ＝E G 。如果V ＝{v 1,…,v n }，那么E 中的元素e 与V 中某两个元素构成的无序对(v i ，v j )相对应，记e ＝v i v j ，或e ＝v j v i 。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。 二分图：设G 是一个图。如果存在V G 的一个划分X ，Y ，使得G 的任何一条边的一个端点在X 中，另一个端点在Y 中，则称G 为二分图，记作G ＝(X ，Y ，E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻，则称G 为完全二分图。 2.匹配的相关概念 设G ＝(V ，E)是一个图，E M ?，如果M 不含环且任意两边都不相邻，则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。 对于图G ＝(V ，E)，在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m e e w M w )()(，并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果 对一切，e ∈E ，w(e)=1,则G 的最大权匹配就是G 的最大匹配。 设M 是图G=(V ,E)的一个匹配，v i ∈V 。若v i 与M 中的边相关联，则称v i 是M 饱和点，否则称v i 为M 非饱和点。 如果G 中每个顶点都是M 饱和点，则称M 为G 的完美匹配。 设M 是G 的一个匹配，P 是G 的一条链。如果P 的边交替地一条是M 中的边，一条不是M 中的边，则称P 为M 交错链。类似地，我们可以定义G 的交错圈。易知，G 的交错圈一定是偶圈。 一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。 两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2＝（S 1∩S 2）\（S 1∪S 2） 容易看出，设M 是G 的匹配，P 是G 中的M 增广链、则M ⊕P 也是G 的匹配，而且1+=⊕M P M 。 图表 1 “异或”操作 可以证明，G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。