第４７卷第５期 ２ ０ ０ ７年９月 大连理工大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ ＶＯＩ．４７，Ｎｏ．５ Ｓｅｐｔ．２ ０ ０ ７ 文章编号：１０００—８６０８（２００７）０５－０６８３－０６ 采用方向场配准和图匹配的指纹匹配算法 魏鸿磊 ｚ， 欧宗瑛 ， 张建新 （１．大连理工大学机械工程学院，辽宁大连 １１６０２４￣ ２．大连水产学院机械工程学院，辽宁大连 １１６０２３） 摘要：提出一种新的指纹匹配算法．在配准阶段，引入局部方向场匹配，并结合局部细节点 拓扑结构匹配以进行指纹对齐；在对齐后的匹配中，首先在两个指纹的细节点集之间进行弹 性匹配，得到一个由匹配的细节点对组成的相似集，然后以相似集中的细节点做顶点，以各顶 点之间的连线为边，为输入指纹和模板指纹组成对应的拓扑图进行图匹配；还引入了全局方 向场匹配，并与细节点集匹配进行融合，以提高算法的精度．采用ＦＶＣ２００２公布的指纹库进 行对比实验，结果证明了算法的有效性． 关键词：指纹识别；自动指纹识别系统；细节匹配；图匹配 中图分类号：ＴＰ３９１ 文献标识码：Ａ ０ 引 言 量并评价两个指纹的相似程度．由于各种不利因 由于指纹的稳定性、惟一性和易采集性，指纹 素的影响，确定真实匹配细节点的数量很困难，常 识别成为应用最广泛的人体生物特征身份鉴别技 用方法是基于限界盒的弹性匹配［６￣１ ，不要求两 术［１］．目前最常用的指纹匹配方法是通过提取指 个细节点完全重合，只要一个细节点处于另一个 纹脊线的末梢点和分又点（统称为“细节点”），将 细节点周围预设的“限界盒”内即认为匹配．该算 指纹之间的匹配转化为细节点集之间的点模式匹 法的限界盒尺寸设定很困难：采用较小限界盒会 配，以基于局部细节匹配的算法［２ 和基于预配 引起错误拒绝率的较大上升，而采用较大的限界 准的全局细节匹配算法［６叫０］最为常见． 盒会引起错误接受率的较大上升．罗希平等［７］根 据细节点离配准基准点的远近程度采用不同大小 基于局部细节匹配的算法根据两指纹对应细 节点拓扑结构的相似性评价两指纹的相似程度． 的限界盒；Ｊｉａｎｇ等［９ 在两个细节点匹配时还参考 该算法对非线性变形较为鲁棒，但是局部结构一 了细节点周围的局部结构匹配结果，这两种方法 般以较少的细节点构成，混入少量的伪细节点或 提高了算法精度，但并没有改变算法的局限性． 丢失少量真细节点就会严重影响匹配的结果 ］． 指纹是一个纹理图像，其方向场稳定、规律， 基于预配准的全局细节匹配算法首先配准两 蕴含了纹线的轨迹、曲率等重要信息，受变形噪声 个细节点集，然后进行细节点匹配，具有较高的识 等因素的影响较小．本文引入局部方向场匹配， 别精度［１］．常见的指纹配准算法有基于脊线配准 并结合局部细节点拓扑结构匹配进行配准；在配 的算法 卅 和基于局部拓扑结构配准的算 准后的匹配中，进行初匹配和图匹配两次匹配，并 法 。。．采用脊线配准为取得较好的效果需要提 融合两次匹配的结果；为充分利用指纹图像的宏 取较长的脊线，而在指纹质量较差时这一点经常 观纹理信息以提高匹配精度，还进行全局方向场 无法得到保证．采用局部结构配准时，在指纹质 匹配并与全局细节点匹配结果进行融合． 量较差和指纹重合区域较小时，会造成局部拓扑 １ 匹配特征 相似性的严重下降，从而造成配准效果的严重下 降．在指纹配准后，需要统计匹配的细节点的数 对每个指纹记录如下信息用于指纹匹配： 收稿日期：２００５—１０—１９； 修回日期：２００７—０６—１３． 作者简介：魏鸿磊 （１９７３一），男，博士；欧宗瑛（１９３６一），男，教授，博士生导师 大连理工大学学报 第４７卷 （１）细节点特征集 Ｍ一｛ ：（ｚ ，Ｙ ， ） Ｉ≥ｉ≥１） 其中（ｚ ，Ｙ ，Ｏｍ）ｉ为细节点的位置坐标和方向． （２）指纹方向块特征集 Ｄ一｛Ｄ ：（ｚｄ，Ｙｄ， ） Ｄ Ｉ≥ｉ≥１） 其中Ｄ 为指纹有效区域分成的大小为１６×１６的 块，以方向块的中心点坐标（ｚ ，Ｙ ）和纹理方向 表示． ２ 细节点集的匹配 待匹配的模板指纹的细节点集Ｐ和输入指纹 的细节点集Ｑ分别表示如下： Ｐ＝｛Ｐ 一（ ，Ｙｐ， ） ；ＩＰ Ｉ≥ ≥１） Ｑ一｛Ｑ。一（ｚ ，Ｙ ， ） ；ＩＱ Ｉ≥ ≥１） 首先需要将两个细节点集Ｐ和Ｑ配准，然后 才能进行匹配． ２．１ 细节点集的配准 细节点集配准的关键是挑选出两细节点集的 配准基准点．为此，对每个模板指纹的细节点Ｐ 和每个输入指纹的细节点Ｑ ，首先将其局部方向 场进行匹配，如果匹配分值大于预设的阈值，再进 步对其局部细节点拓扑结构进行匹配，并且根 据两次匹配的结果决定它们是否可作为配准基准 点．采用局部方向场预配准的优点在于指纹的方 向场相对于指纹变形和噪声有较强的鲁棒性，且 同源指纹之间相同区域的方向场很相似，因此采 用局部方向场匹配可以较好地评价两指纹局部区 域的相似性；缺点在于有些异源指纹也有很相似 的方向场，因此单独采用局部方向场配准不够可 靠．本文将局部方向场匹配和局部细节点拓扑结 构匹配相结合，以综合两种方法的优点，改善配准 的效果． ２．１．１ 局部方向场的建立 首先以模板指纹和 输入指纹的每个细节点所在的方向块为中心，将 其周围ｋ行ｋ列方向块的方向与中心细节点方向 之间的相对角度口一ｄ （ ， ）按从下到上、从左到 右的顺序存入ｋ×ｋ的数组ＦＶｉ－］［ｊ－］中，组成该细 节点的局部方向场．ｄ （￡ ，ｔｚ）为两个角度的差 值，按下式计算［９３： ｆ￡ｌ一￡２；一兀＜￡１一￡２＜兀 ｄ （￡ｌ，ｔｚ）一．《２７（＋ｔ１一ｔ２；ｔｌ—ｔ２＜一７（ （１） 【２７（一ｔｌ＋ｔ２；ｔｌ—ｔ２＞７（ 图１是一个７×７大小的局部方向场的组成 示例． ●客 ～ ●， Ｐ ● ● ● ．‘ ● ● ● ● ● ● ◆一细节点方向 一块方向 图１ 局部方向场示意图 Ｆｉｇ．１ Ｌｏｃａｌ ｏｒｉｅｎｔａｔｉｏｎ ｆｉｅｌｄ ２．１．２ 局部方向场的匹配 为计算一个模板指 纹的局部方向场和一个输入指纹的局部方向场之 间的相似度，需要确定两个局部方向场之间方向 块的对应关系，一般做法是首先根据中心细节点 之间的位移和角度关系对齐两个局部方向场，然 后对输入指纹局部方向场的每个方向块，都搜索 出模板指纹局部方向场中距离最近的方向块作为 对应块．这种方法需要做循环比较，计算量较大， 本文提出如下方法： 如果 和 分别为输入指纹和模板指纹的 局部方向场中心细节点的方向角，（ｚ。，Ｙ。）为输入 指纹方向场的中心块坐标，（ｚ ，Ｙ ）为输入指纹方 向场中方向块Ｆ户１＝ ］［力的坐标，则如下确定模板 指纹方向场中与其对应的方向块： ｍ—ｋ／２＋［ｄ￣ｃｏｓ ＋ｄｙｓｉｎ￣］／１６ … ｋ／２＋［ ｓｉｎ 一ｄ ＣＯＳ￣］／１６ … 上式实际上是将输入指纹方向场旋转到与模 板指纹方向场对应的位置，从而确定对应块．其 中 一ｚ —ｚｏ，ｄｙ—Ｙ —Ｙｏ， ＝ 一 ． 对 和 取整，则模板指纹方向场中 Ｆ ］［，２］就是Ｆ ］［力的对应块． 两个对应块的匹配分值如下计算： 一 ；ｓ＞ｏ㈤ ｌ０； ≤０ 其中Ｄ。是预设定的方向角最大许可差值． 两个局部方向场如果有 个对应块，则总体 匹配分值为所有对应块匹配分值的平均值： ㈤ ２．１．３ 配准参照点集的构成 对局部方向场匹 配分值高于某预设阈值的细节点对，采用文献［９］ 中介绍的方法进行局部细节点拓扑结构匹配，并 第５期 魏鸿磊等：采用方向场配准和图匹配的指纹匹配算法 ６８５ 将局部方向场匹配结果和局部细节点拓扑结构匹 配结果按下式融合： Ｓ＝ 。＋（１一 ） （５） 式中：５。为局部方向场匹配分值； 为局部细节 点拓扑结构匹配分值； 为预设的权值． 选取融合后的匹配分值大于预设阈值的细节 点对构成候选参照点对集合，记为Ａ＝（（Ａｆ， ），…，（ 晏， 凳））． ２．２ 配准后细节点集的匹配 本文配准后细节点集的匹配过程如图２所 示：第一阶段匹配出两个细节点集的初步的对应 关系，组成两个细节点集的相似子集；第二阶段分 别以两个相似子集中的细节点为顶点，并将所有 顶点之间以直线互连建立两个完全图并进行图匹 配；最后综合两阶段的匹配结果得出细节点集的 匹配分值． 图２ 图匹配示意图 Ｆｉｇ．２ Ｍａｔｃｈｉｎｇ ｏｆ ｔｈｅ ｇｒａｐｈｓ 本文图匹配是两图之间对应边的匹配．由细 节点相连而成的图体现了一个指纹中的细节点之 间相互的位置和角度关系．同源指纹匹配得到的 相似子集的相似程度较高，图匹配分值也较高，而 异源指纹虽然可能有较多的伪匹配对进入相似子 集，但是由相似子集建立的图的相似程度一般较 低，匹配分值也较低．进入相似集中的伪匹配对 越多，图的相似性就越差．同源指纹匹配时重叠 区域的细节点一般是一一对应的，虽然采用较宽 松的匹配条件，进入相似集的伪匹配对数目也较 少，因此对图相似性的影响较小；异源指纹之间， 由于所有的匹配对都是伪匹配对，采用宽松的匹 配条件，造成进入相似集的伪匹配对更多，引起图 相似性的严重下降．图２是两个较相似的异源指 纹的匹配（分别为ＦＶＣ２Ｏ０２的ＤＢ１指纹库Ａ集中 的２号指纹局部和７６号指纹局部），虽然初匹配 取得了较好的结果，但是组成的两图有明显的差 异，而实际上图的匹配分值也较低． 本文细节点的匹配实际上经过初匹配和图匹 配两次匹配，如果细节点对是来自同源指纹的真 匹配对，则两次匹配都取得较高分值的可能性较 大，否则较小，因此采用两次匹配的分值乘积作为 匹配分值能更有效地评价两细节点的相似性． 细节点集Ｐ和Ｑ匹配过程的描述如下： （１）按先后顺序选择一对参照点对（ ， ）， 以其为原点，按文献［９］方法将两个细节点集转 换到极坐标系下，表示为 Ｐ一｛Ｐ 一（ｒｐ， ｐ，Ｏｐ）ｉ；ｌＰ Ｉ≥ｉ≥１｝ Ｑ＝｛Ｑ ＝（ｒｑ， ， ） Ｑ ｌ≥ｉ≥１｝ 逐一比较输入细节点和模板细节点，若两细节点 满足式（６）条件，则认为初匹配成功： ， ｌ Ｉ．｛ＩＪＩ Ｓｒ ［ｒ丽ｐ－丽ｒｑ Ｉ ｌ≤１ ｄ￣（ｅｐ，ｅｑ）≤１．． Ｉ ：下（６）｛ＩＬ ： —— ．．ｔＪ０ ＿一 ≤一１ 并按下式计算匹配分值： Ｓ一３一 一 一 （７） 式中 Ｄ 和Ｄ 分别是预设定长度系数、极角和 方向角最大许可误差，本文取（ ，Ｄ ，Ｄ ）＝（０．３， ７ｃ／６，７ｃ／６），实验证明这个匹配条件是很宽松的， 基本避免了由于采集时的非线性变形引起的同源 指纹对应细节点之间的位置偏离而造成的失配现 象． 令所有匹配的细节点对组成相似集，其中，如 果有重复匹配的细节点则取匹配分值最大的一 对．相似集记为Ｂ＝（（Ｂｆ，Ｂ ），…，（Ｂ晏，Ｂ２））， 对应的初匹配分值矩阵记为Ｓ＝（ Ｓ。… 大连理工大学学报 第４７卷 Ｓ ）．其中（Ｂ ，Ｂ ）为匹配的第ｉ对输入细节点和 模板细节点标识，而 是它们的匹配分值． （２）以细节点为顶点，根据相似集建立两个 分别以输入细节点和模板细节点为顶点的完全 图，然后根据式（８）在两图对应边之间进行匹配， 可以得到一个相似度矩阵，由此可以评价两图的 相似性，进而可以评价两细节点集的相似性． Ｉｄｐ—ｄｑＩ－ ｄ≯（ ，ａｑ） ｄ≯（ ， ） 一。 Ａｍａｘ（ｄｐ，ｄｑ）Ｄ Ｄ口 （８） 式中： 、Ｄ分别为预定义的长度系数和角度限定 值；其他各值的意义如图３所示．如果以式（８）计 算出的匹配分值小于零则取为零． 图３ 对应边匹配示意图 Ｆｉｇ．３ Ｍａｔｃｈｉｎｇ ｏｆ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｅｄｇｅｓ 如果相似集中有Ｋ对细节点，则可构成有Ｋ 个顶点的两个图进行匹配，可以得到如下Ｋ×Ｋ 大小的分值矩阵： Ｃｌ１ Ｃ１２ Ｃ１ｘ Ｃ２１ Ｃ２２ Ｃ Ｃ＝＝ （９） ； ： ： Ｃｘ１ Ｃｘ２ ＣＫＫ 其中Ｃ 是由第ｉ和第 个顶点连成的边的匹配分 值，Ｃｕ＝Ｃ Ｃｉ 一０． 令每个细节点的匹配分值为以该细节点为端 点的边的匹配分值的均值，则由图匹配得到的细 节点匹配分值矩阵为 ∑Ｃ ＾ １ Ｇ＝ ∑Ｃ ＾ １ （１Ｏ） ∑Ｃ ＾ １ （３）在初匹配阶段得到１×Ｋ的分值矩阵ｓ， 在图匹配阶段得到Ｋ×１的分值矩阵Ｇ，采用两 矩阵的乘积的行列式值作为两次匹配得到的总分 值： Ｓ 一ＩＳＧ Ｉ（ＩＩ） 逐一以每对参照点配准两个细节点集并匹 配，以最大的一个匹配分值作为细节点匹配的相 似度． ３ 全局方向场匹配 当细节点集匹配取得最高分值时，进行全局 方向场匹配．如果两个指纹是同源指纹，则两个 指纹在细节点集匹配和全局方向场匹配时一般都 能够取得较高的匹配分值，反之则较少可能，因此 采用两种算法的匹配结果进行融合，有利于提高 同源指纹的匹配分值并降低异源指纹的匹配分 值，从而提高匹配精度． 全局方向场匹配方法过程如下：首先根据细 节点匹配获得最高分值时得到的配准参数对齐两 个全局方向场，然后搜索对应方向块，如果有模板 方向块Ｂ 和输入方向块Ｂ 的距离小于一个预设 阈值 ，则（Ｂ ，Ｂ ）为对应块，记录两个块的标 识，并以式（３）计算两个块的匹配分值，最终以式 （４）计算两个全局方向场的匹配分值． ４ 两个指纹匹配分值的计算 在取得最大的细节点集匹配分值和方向场匹 配分值后，按下式计算两指纹最终匹配分值： Ｓ＝ （ｏ．５＋Ｓｕ·５ 十。） （１２）ｌｚ） 其中Ｋ和￡分别为两个指纹重合区域的细节点 数． ５ 指纹库测试实验 按ＦＶＣ２０００［１妇的测试标准，采用ＦＶＣ２００２ 公布的４个指纹库的Ａ集进行实验，每个库的Ａ 集包含１００×８张指纹图像．每个样本与相同手 指的其余样本未能匹配上的比率称为错误拒绝率 ＦＮＭＲ．本文ＦＮＭＲ实际测试总数为（（８× ７）／２）×１００＝２ ８００次．每个手指的第一个样本 与其他手指的第一个样本匹配成功的比率称为错 误接受率ＦＭＲ，本文ＦＭＲ实际测试的总数为 （（１００×９９）／２）＝４ ９５０次．ＥＥＲ、ＦＭＲ１００和 ＦＭＲＩＯ００分别是当ＦＮＭＲ＝ＦＭＲ、ＦＭＲ： ０．０１和ＦＭＲ＝０．００１时的ＦＮＭＲ值；匹配时间 是同一集中所有匹配的平均时间，不包括预处理 及特征提取时间．ＲＯＣ曲线是采用对数坐标的 ＦＭＲ与ＦＮＭＲ关系曲线．文献［９］的算法是较 第５期 魏鸿磊等：采用方向场配准和图匹配的指纹匹配算法 为常用的典型算法，将该算法与本文算法进行对 照实验．两个算法采用相同的图像预处理及细节 点提取平台，所有实验均在ＰＩＩＩ７５０ＭＨｚ的微机 上进行，实验结果如表１～４和图５～８所示． 表１ 两种算法在ＤＢ１Ａ上的测试结果 Ｔａｂ．１ Ｒｅｓｕｌｔｓ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ１Ａ 表２ 两种算法在ＤＢ２Ａ上的测试结果 Ｔａｂ．２ Ｒｅｓｕｌｔｓ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ２Ａ 表３ 两种算法在ＤＢ３Ａ上的测试结果 Ｔａｂ．３ Ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ３Ａ 表４ 两种算法在ＤＢ４Ａ上的测试结果 Ｔａｂ—Ｒｅｓｕｌｔｓ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ４Ａ 经分析，文献［９］算法在ＤＢ１和ＤＢ２两个库 上指纹匹配失败的主要原因是非线性变形较大， 从表１和表２、图４和图５可知，本文算法在这两个 库上的精度有了较大幅度的提高，表明本文算法 较文献［９］算法对非线性变形的处理效果具有明 显优势；由于ＤＢ３和ＤＢ４两个库的指纹质量较 差，文献［９］算法在这两个库上产生匹配错误的 主要原因是有些指纹特征点的提取错误较多，从 表３和表４、图６和图７可知，本文算法在这两个库 上的精度也有了一定程度的提高，但较在前两个 库上的幅度小，这说明本文算法在处理特征提取 错误方面相对较弱，需要进一步的提高．从表１ ４可知，本文算法的计算时间有一定程度的增 加，但在实际应用中，平均增加０．Ｏｌ～０．０３ Ｓ的 匹配时间影响并不大． 图４ ＤＢ１ Ａ上两种算法的ＲＯＣ曲线比较 Ｆｉｇ．４ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ１Ａ Ｆ Ｒ 图５ ＤＢ２Ａ上两种算法的ＲＯＣ曲线比较 Ｆｉｇ．５ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ２Ａ 图６ ＤＢ３Ａ上两种算法的ＲＯＣ曲线比较 Ｆｉｇ．６ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ３Ａ 图７ ＤＢ４Ａ上两种算法的ＲＯＣ曲线比较 Ｆｉｇ—Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＤＢ４Ａ ６ 结 语 本文提出了一种基于预配准的指纹匹配算 法，在配准阶段提出融合局部方向场和局部细节 ６８８ 大连理工大学学报 第４７卷 点拓扑结构进行配准，在配准后的匹配阶段提出 ｓｔｒｕｃｔｕｒａｌ ｓｉｍｉｌａｒｉｔｙ［Ｃ］∥Ｆｉｆｔｈ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ．Ｐａｌｍ：Ｓｐｒｉｎｇｓ， ２０００：２９－３４ 种细节点集的图匹配算法，并在最后的匹配结 果中融合了全局细节点匹配与全局方向场匹配结 果．按ＦＶＣ２０００的测试标准［１¨，采用ＦＶＣ２００２ ［６］ＪＡＩＮ Ａ Ｋ，ＨＯＮＧ Ｌ，ＢＯＬＬＥ Ｒ．Ｏｎ—ｌｉｎｅ 公布的４个指纹库进行对比实验表明，本文算法 有效地提高了匹配精度，而匹配时间的增加程度 对实际应用的影响不大． ｆｉｎｇｅｒｐｒｉｎｔ ｖｅｒｉｆｉｃａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌ ａｎｄ Ｍａｃｈ Ｉｎｔｅｌｌ，１９９７，１９（４）：３０２－３１３ ［７］罗希平，田 捷．自动指纹识别中的图像增强与细节 匹配［Ｊ］．软件学报，２００２，１３（５）：９４６—９５６ ［８］郭 浩，欧宗瑛，何４５（１）：６４—６７ （ＧＵＯ Ｈａｏ，ＯＵ Ｚｏｎｇ—ｙｉｎｇ，ＨＥ Ｙａｎｇ．Ａ ｎｅｗ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｍｉｎｕｔｉａｅ ｏｆ 参考文献： ［１］ＭＡＬＯＮＩ Ｄ，ＭＡＩＯ Ｄ，ＪＡＩＮ Ａ Ｋ，ｅｔ ａ１．Ｈａｎｄｂｏｏｋ 洋．一个新的基于细节特征的 指纹匹配方法［Ｊ］．大连理工大学学报，２００５， ｏｆ Ｆｉｎｇｅｒｐｒｉｎｔ Ｒｅｃｏｇｎｉｔｉｏｎ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００３：３－１ ２ ［２］ＲＡＴＨＡ Ｎ Ｋ，ＫＡＲＵ Ｋ，ＣＨＥＮ Ｓｈａｏ—ｙｕｎ，ｅｔ ａ１．Ａ ｒｅａｌ—ｔｉｍｅ ｍａｔｃｈｉｎｇ ｓｙｓｔｅｍ ｆｏｒ ｌａｒｇｅ ｆｉｎｇｅｒｐｒｉｎｔ ｆｉｎｇｅｒｐｒｉｎｔｓ［Ｊ］．Ｊ Ｄａｌｉａｎ Ｕｎｉｖ Ｔｅｃｈｎｏｌ，２００５， ４５（１）：６４—６７） ｄａｔａｂａｓｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌ ａｎｄ Ｍａｃｈ Ｉｎｔｅｌｌ，１９９６，１８（８）：７９９—８１３ ［９］ＪＩＡＮＧ Ｘ，ＹＡＵ Ｗ Ｙ． Ｆｉｎｇｅｒｐｒｉｎｔ ｍｉｎｕｔｉａｅ ｍａｔｃｈｉｎｇ ｂａｓｅｄ ｏｎ ｔｈｅ ｌｏｃａｌ ａｎｄ ｇｌｏｂａｌ ｓｔｒｕｃｔｕｒｅｓ ［３］ＣＨＥＮ Ｘ Ｊ，ＴＩＡＮ Ｊｉｅ，ＹＡＮＧ Ｘ．Ａ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｔｏｐｏｌｏｇｉｃ ｓｔｒｕｃｔｕｒｅ［Ｃ］∥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｍａｇｅ Ａｎａｌｙｓｉｓ ａｎｄ ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｂａｒｃｅｌｏｎａ： ［ｓ ｎ］，２０００：１０３８—１０４１ Ｒｅｃｏｇｎｉｔｉｏｎ．Ｐｏｒｔｕｇａｌ：ｓ ｎ］，２００４：３６０—３６７ ［４］ｚｓ Ｍ，ＫＯＶＡＣＳ Ｖ．Ａ ｆｉｎｇｅｒｐｒｉｎｔ ｖｅｒｉｆｉｃａｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｔｒｉａｎｇｕｌａｒ ｍａｔｃｈｉｎｇ ａｎｄ ｄｙｎａｍｉｃ ［１Ｏ］田 捷，何余良，陈宏，等．一种基于相似度聚类 方法的指纹识别算法［Ｊ］．中国科学：Ｅ辑，２００５， ３５（２）：１８６—１９９ ｔｉｍｅ ｗａｒｐｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌ ａｎｄ Ｍａｃｈ Ｉｎｔｅｌｌ，２０００，２２（１１）：１２６６—１２７６ ［１１］ＭＡＩＯ Ｄ，ＭＡＬＴＯＮＩ Ｄ，ＣＡＰＰＥＬＬＩ Ｒ，ｅｔ ａ１． ＦＶＣ２０００：ｆｉｎｇｅｒｐｒｉｎｔ ｖｅｒｉｆｉｃａｔｉｏｎ ｃｏｍｐｅｔｉｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌ ａｎｄ Ｍａｃｈ Ｉｎｔｅｌｌ， ［５］ＲＡＴＨＡ Ｎ Ｋ，ＢＯＬＬＥ Ｒ Ｍ，ＰＡＮＤＩＴ Ｖ Ｄ，ｅｔ ａ１． Ｒｏｂｕｓｔ ｆｉｎｇｅｒｐｒｉｎｔ ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｕｓｉｎｇ ｌｏｃａｌ ２００２，２４（３）：４０２—４１２ Ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｏｒｉｅｎｔａｔｉｏｎ ｆｉｅｌｄｓ ａｌｉｇｎｍｅｎｔ ａｎｄ ｇｒａｐｈ ｍａｔｃｈｉｎｇ ＷＥＩ Ｈｏｎｇ—ｌｅｉ ·。，ＯＵ Ｚｏｎｇ—ｙｉｎｇ ，ＺＨＡＮＧ ｄｉａｎ—ｘｉｎ （１．Ｓｃｈｏｏｌ ｏｆ Ｍｅｃｈ．Ｅｎｇ．，Ｄａｌｉａｎ Ｕｎｉｖ．ｏｆ Ｔｅｃｈｎｏ１．，Ｄａｌｉａｎ １１６０２４，Ｃｈｉｎａ； ２．Ｓｃｈｏｏｌ ｏｆ Ｍｅｃｈ．Ｅｎｇ．，Ｄａｌｉａｎ Ｆｉｓｈｅｒｉｅｓ Ｕｎｉｖ．，Ｄａｌｉａｎ １１６０２３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｎｏｖｅｌ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｗａｓ ｄｅｖｅｌｏｐｅｄ．Ｉｎ ｔｈｅ ａｌｉｇｎｍｅｎｔ ｓｔａｇｅ，ａ ｈｙｂｒｉｄ ａｌｉｇｎｍｅｎｔ ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ ｕｓｅｄ ｌｏｃａｌ ｏｒｉｅｎｔａｔｉｏｎ ｆｉｅｌｄ ａｎｄ ｌｏｃａｌ ｍｉｎｕｔｉａｅ ｔｏｐｏｌｏｇｉｃ ｓｔｒｕｃｔｕｒｅ ｔｏ ａｃｈｉｅｖｅ ｔｈｅ ａｌｉｇｎｍｅｎｔ ｏｆ ｔｗｏ ｆｉｎｇｅｒｐｒｉｎｔｓ．Ｉｎ ｔｈｅ ａｌｉｇｎｅｄ ｍｉｎｕｔｉａ ｍａｔｃｈｉｎｇ ｓｔａｇｅ，ａ ｍｉｎｉｍｕｍ ｓｅｔ ｏｆ ｍａｔｃｈｅｄ ｍｉｎｕｔｉａ ｐａｉｒｓ ｗａｓ ａｃｈｉｅｖｅｄ ｂｙ ｍａｔｃｈｉｎｇ ｔｗｏ ｍｉｎｕｔｉａ ｓｅｔ ｂｙ ｔｈｅ ｅｌａｓｔｉｃ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ，ｗｉｔｈ ｔｈｅ ｍｉｎｕｔｉａｅ ｉｎ ｔｈｅ ｍａｔｃｈｅｄ ｐａｉｒｓ ｓｅｔ ａｓ ｎｏｄｅ ａｎｄ ｓｔｒａｉｇｈｔ ｌｉｎｅｓ ｃｏｎｎｅｃｔｉｎｇ ｔｗｏ ｍｉｎｕｔｉａｅ ａｓ ｔｈｅ ｅｄｇｅｓ，ｔｗｏ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｇｒａｐｈｓ ｆｏｒ ｉｎｐｕｔ ｆｉｎｇｅｒｐｒｉｎｔ ａｎｄ ｔｅｍｐｌａｔｅ ｆｉｎｇｅｒｐｒｉｎｔ ｗｅｒｅ ｃｏｎｓｔｒｕｃｔｅｄ，ａｎｄ ａ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｅｓｅｎｔｅｄ ｔｏ ｍａｔｃｈ ｔｈｅ ｔｗｏ ｇｒａｐｈｓ．Ｔｈｅ ｍａｔｃｈｉｎｇ ｍｅｔｈｏｄ ｕｓｉｎｇ ｇｌｏｂａｌ ｏｒｉｅｎｔａｔｉｏｎ ｆｉｅｌｄ ｗａｓ ａｌｓｏ ｉｎｔｒｏｄｕｃｅｄ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｔｗｏ ｆｉｎｇｅｒｐｒｉｎｔｓ ｍａｔｃｈｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔｓ ｏｎ ｆｏｕｒ ｄａｔａｂａｓｅｓ ｏｆ ＦＶＣ２００２ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｆｉｎｇｅｒｐｒｉｎｔ ｍａｔｃｈｉｎｇ ｔｅｃｈｎｉｑｕｅ ｉｓ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ：ｆｉｎｇｅｒｐｒｉｎｔ ｒｅｃｏｇｎｉｔｉｏｎ；ａｕｔｏｍａｔｉｃ ｆｉｎｇｅｒｐｒｉｎｔ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｓｙｓｔｅｍｓ（ＡＦＩＳ）；ｍｉｎｕｔｉａ ｍａｔｃｈｉｎｇ；ｇｒａｐｈ ｍａｔｃｈｉｎｇ
