学位论文 > 优秀研究生学位论文题录展示

超大规模指纹库的索引结构和检索方法

作　者: 袁宝玺
导　师: 蔡安妮
学　校: 北京邮电大学
专　业: 通信与信息系统
关键词: 自动指纹识别系统指纹检索自动指纹质量评价索引器检索器
分类号: TP391.41
类　型: 博士论文
年　份: 2013年
下　载: 24次
引　用: 0次
阅　读: 论文下载

内容摘要

指纹是目前生物特征识别领域中应用最为广泛的生物特征。由于指纹具有唯一性和不变性等优良特性,并且随着近几十年来自动指纹识别技术的研究日渐成熟,使得自动指纹识别系统(Automated Fingerprint Identification System, AFIS)在身份鉴别领域得到了广泛的应用,AFIS已经遍及公安、边防、出入境检查、银行、保险、医疗卫生及网络接入等许多场合。随着自动指纹识别技术应用领域的不断扩大,指纹数据库的规模也在不断扩大。目前AFIS面临的一个巨大难题就是超大规模指纹图像库的检索问题。所谓超大规模,是指库容量达到千万枚指纹以上超大规模指纹库检索算法要解决的问题属于海量信息的检索问题,而海量信息检索是一个典型的NP问题。得到检索问题的解通常比验证一个给定的解要花费多得多的时间。由于穷举法无法解决海量信息的检索问题,所以目前研究最多的是启发式搜索算法,这类算法在搜索过程中加入了与问题有关的启发性信息,用以指导搜索向着一个比较小的范围内进行,目的是加速整个搜索过程,从而减少搜索时间。指纹图像检索算法的基本思想是：首先提取可靠的检索特征作为启发性信息,然后依据检索特征的特点构造出高效的索引(Indexing)结构,最后依据相似性检索规则进行检索(Retrieval),得到候选指纹序列。所以,如何提取指纹图像中的可靠特征,以及如何针对不同的特征研究针对性的索引结构和检索方法,是构建超大规模指纹检索系统必须要考虑的问题。同时,检索特征的信息量是和指纹图像的质量密切相关的,低质量指纹图像在AFIS中的识别准确性会显著降低,在大规模指纹库中检索的准确率和效率也会明显降低,因此,研究指纹质量评价方法及其在指纹检索系统中的应用方法也是必须要研究的重要问题。本文针对上述问题进行了大量的研究,提出了一些有效的解决方案。本文的研究工作主要集中在如下几个方面：(a)自动指纹质量评价方法研究在指纹检索系统中,指纹质量评价可以用于针对不同质量的探查指纹使用不同的检索算法,也可以用于根据探查指纹图像质量的高低设定浮动检索阈值。由于指纹质量评价是一个各种因素综合作用的复杂过程,所以一般使用将各种全局特征、局部特征进行综合评价的多特征融合的方法。指纹质量评价首先要解决的是评价特征的选择问题,但是,相关文献中仅仅是完全依靠经验进行特征的选择,没有提出选择特征的依据。本文使用视觉注意机制原理作为依据对指纹质量评价特征进行归类,然后综合考虑AFIS系统的整体效率和特征的可靠性,对指纹质量评价特征进行了筛选,最终得到了5个质量评价特征,其中,提出了基于极坐标中心敏感特性的细节点评价方法评价细节点可靠性,提出了基于Otsu算法的灰度对比度评价方法作为灰度对比度评价特征。实验证明,本文选取的5个特征在BP神经网络分类器、SVM分类器和本文提出的基于多特征非线性融合的指纹质量评价方法中都获得了很高的主客观评价一致性。相关文献提出的基于机器学习的质量分类方法的不足主要表现为分类质量等级太少,基于加权的质量评价方法的不足主要表现为无法较好地逼近各个质量评价特征到指纹质量评价结果之间的非线性映射关系。本文通过引入指纹质量主观评价和影响力判断矩阵分析两个主观实验,提出了基于多特征非线性融合(Multi Parameters Non-linear Integrated, MPNLI)的指纹质量评价方法,该方法最终得到的是非线性融合的质量评价公式,可以有效逼近各个特征对指纹质量评价分数的非线性贡献。同时,由于基于MPNLI的指纹质量评价方法能够得到比BP神经网络方法和SVM方法更多的质量等级,使得使用基于MPNLI的指纹质量评价方法设定的检索阈值会更加精细,从而能够有效提高整个系统的检索效率。(b)指纹检索算法研究在当前的指纹检索算法中,由于仅仅将索引模块和检索模块视为查找过程的一个简单步骤,很大程度上忽视了对检索策略的考量。在本文中,将构建索引的功能模块命名为索引器,检索功能模块命名为检索器。在系统中明确定义索引器和检索器的好处是,可以对这两部分涉及的技术分别进行深入研究。基于细节点多元组的指纹检索算法是当前一种比较可靠高效的指纹检索算法,但是,该算法面临着多元组辨识能力与数量的矛盾。本文提出了基于MTOSMM的指纹检索方法,该方法通过三元组的匹配信息获取四元组以上结构的匹配数目,有效解决了多边形辨识能力与数量的矛盾。对于索引器的构建问题,本文从三角形特征的匹配方法、特征参数的量化、特征量化产生的匹配错误分析及解决、三角形一边多次匹配结构、多元组的精选方法、量化区间中点标志、索引结构的建立等多个方面进行了分析研究,最终提出了基于三角形一边多次匹配的多元组精选方法和两层索引结构。实验结果表明,本文构建的索引器能够大大提高检索器的检索速度。与索引器的研究被忽视一样,由于仅仅将检索视为一个简单的查找索引的步骤,检索策略的考量也没有受到当前已有的指纹检索方法的重视。对于检索器的构造问题,主要需要关注两个方面：相似性准则的构造和检索阈值的设定问题。本章提出了基于三角形一边多次匹配的相似性评价准则,该准则采用多种拓扑结构的匹配数量的加权和构造打分公式,其中权值通过中点标志权值法获得。针对检索策略问题,本文认为,基于阈值法的检索策略要优于相关文献中常用的基于Top N方法的检索策略,原因是基于阈值法的检索策略可以使得检索和一对一精细比对同步进行,而且可以省去检索分数排序环节；而基于Top N方法的检索策略必须得等到检索完指纹库中所有的库指纹,并将它们按检索分数从大到小排序完之后才能进入一对一精细比对阶段。基于阂值法的检索策略需要解决的关键问题是浮动阈值的设定方法,为此本文提出了基于质量等级的阈值预测方法,该方法可以将指纹质量评价对指纹检索结果具有的预测功能应用到指纹检索系统中。(c)低质量指纹的检索算法研究犯罪嫌疑人在犯罪现场遗留的指纹被称为现场指纹,由于现场指纹是手指在无意中留下的,可能会存在压力不均匀、面积小、区域偏、背景复杂等情况,采集到的现场指纹图像常常存在形变大、噪声大等特点,所以低质量现场指纹的检索问题显得尤为困难。据我们所知,到目前为止尚没有专门针对低质量现场指纹的检索方法公开发表。由于现场指纹图像的质量一般会很差,所以,本文提出的基于MTOSMM的指纹检索方法对于低质量指纹的检索效果还有待改进,因此本文提出了基于现场三角形多播(Latent Triplet Multicast, LTM)的指纹检索方法用于提升低质量指纹的检索效果。现场指纹的检索效果很差和其图像本身的细节点数量很少有很大的关系,所以要想提高低质量指纹的检索效果,必须要想办法有效利用现场指纹中仅有的有效信息。本文提出的基于LTM的指纹检索方法能够通过三角形多播的方法来增加现场指纹可用的三角形数量,同时还能够减少特征量化引起的匹配错误,从而提高低质量现场指纹的检索效率。(d)超大规模指纹检索系统的构建本文提出了基于MPNLI的指纹质量评价方法、基于MTOSMM的指纹检索方法和基于LTM的指纹检索方法,如何将这些方法组合构造超大规模指纹检索系统,使得几种算法都能充分发挥自身的优点,也是一个必须要研究的问题。基于MTOSMM的指纹检索方法以细节点三角形检索为基础,具有速度快、精度较高的优点,但在处理质量很差的现场指纹图像时效果并不是很好。所以基于MTOSMM的指纹检索方法可用于质量较高的探查指纹图像的检索。基于LTM的指纹检索方法是在基于MTOSMM的指纹检索方法的基础上派生出的专门针对质量很差的现场指纹图像的一种指纹检索方法,对于质量很差的现场指纹的检索具有很大的改进作用。所以基于LTM的指纹检索方法可用于低质量的探查指纹图像的检索。指纹质量评价方法在本文构造的超大规模指纹检索系统中主要完成两个功能：算法的选择功能和检索阈值的设置功能。算法选择功能通过基于BP神经网络的指纹分类方法实现。由于基于MTOSMM的指纹检索方法和基于LTM的指纹检索方法分别适合于高质量和低质量的探查指纹的检索,所以需要一个两类分类器,能够将探查指纹归类到高质量类别或者低质量类别中。然后在检索阶段,高质量的探查指纹使用基于MTOSMM的指纹检索方法,低质量的探查指纹使用基于LTM的指纹检索方法。由于基于BP神经网络的指纹分类方法在进行两类分类时的分类准确率高于基于MPNLI的质量评价方法,所以本文此处可以选择基于BP神经网络的指纹分类方法完成算法选择功能。无论是基于MTOSMM的指纹检索方法还是基于LTM的指纹检索方法,都需要通过基于质量等级的检索阈值预测方法来预测检索阈值,基于MPNLI的指纹质量评价方法可以使得基于质量等级的检索阈值预测方法能够预测到多等级的浮动阈值,能够有效提高整个系统的筛选率。综上所述,本文通过指纹质量评价算法、指纹检索算法和超大规模指纹库的检索系统构造方法等多个方面对超大规模指纹库的检索问题进行了研究,取得了一定的研究成果。

全文目录

摘要  4-9
ABSTRACT  9-15
目录  15-18
第一章概述  18-34
  1.1 研究背景  18-20
  1.2 自动指纹识别系统  20-23
    1.2.1 指纹图像的采集  20
    1.2.2 AFIS的建库过程  20-22
    1.2.3 AFIS的工作模式  22-23
  1.3 超大规模指纹库中常用的加速技术  23-24
  1.4 指纹检索与辨识问题的研究现状  24-27
    1.4.1 穷举法  24
    1.4.2 指纹分类  24-26
    1.4.3 指纹索引  26-27
  1.5 指纹检索系统及关键技术问题  27-30
    1.5.1 指纹检索系统的搜索引擎  27
    1.5.2 指纹检索系统的关键技术问题  27-30
  1.6 测试算法常用的公开指纹库  30-31
    1.6.1 FVC系列  30
    1.6.2 NIST系列  30-31
  1.7 本文的主要研究内容与创新点  31-33
    1.7.1 指纹图像质量评价方法  31-32
    1.7.2 指纹检索方法  32
    1.7.3 索引器的构建  32-33
    1.7.4 检索器的构建  33
  1.8 本文组织与结构  33-34
第二章指纹图像质量评价方法研究  34-71
  2.1 引言  34
  2.2 指纹图像质量的评价方法  34-35
  2.3 自动指纹图像质量评价技术的研究现状  35-37
    2.3.1 当前的指纹图像质量评价方法  35-36
    2.3.2 指纹图像质量评价算法性能的衡量  36-37
  2.4 指纹图像质量评价的特征选择  37-47
    2.4.1 基于视觉注意机制的特征归类  37-39
    2.4.2 指纹图像的完整性  39-40
    2.4.3 指纹图像的灰度对比度  40-41
    2.4.4 指纹图像的纹理特征  41-43
    2.4.5 指纹图像细节点的可靠性  43-46
    2.4.6 质量评价特征向量的生成  46-47
  2.5 基于非线性融合的指纹质量评价方法  47-55
    2.5.1 一般图像的质量评价方法  47-50
    2.5.2 当前指纹图像质量评价算法的不足  50-51
    2.5.3 基于非线性融合的指纹图像质量评价算法  51-55
  2.6 实验  55-69
    2.6.1 数据集  55
    2.6.2 主观实验结果  55-56
    2.6.3 所提出的质量评价特征的性能  56-58
    2.6.4 基于MPNLI的指纹图像质量评价模型的训练  58-66
    2.6.5 基于MPNLI的指纹图像质量评价方法的性能  66-67
    2.6.6 各种多特征融合方法的性能比较  67-69
  2.7 结论  69-71
第三章基于细节点多元组的指纹检索方法  71-106
  3.1 引言  71-72
  3.2 指纹检索算法的研究现状  72-73
    3.2.1 检索特征的提取  72
    3.2.2 索引结构的构造  72-73
    3.2.3 检索方法  73
  3.3 指纹检索算法的评价指标  73-74
  3.4 基于三角形一边多次匹配的搜索引擎  74-75
  3.5 检索特征的选取  75-78
  3.6 索引器的构造  78-90
    3.6.1 三角形特征的匹配方法  78
    3.6.2 特征参数的量化  78-80
    3.6.3 特征组量化产生的匹配错误  80-81
    3.6.4 量化引起匹配错误的原因  81-82
    3.6.5 量化引起的匹配错误的解决途径  82-83
    3.6.6 三角形一边多次匹配结构  83-84
    3.6.7 基于MTOSMM的多元组精选方法  84-87
    3.6.8 中点标志  87-88
    3.6.9 两层索引结构的建立  88-90
    3.6.10 离线建库阶段的流程  90
  3.7 检索器的构造  90-95
    3.7.1 相似性评价准则  90-92
    3.7.2 检索策略  92-93
    3.7.3 基于质量等级的检索闽值预测方法  93-95
  3.8 实验  95-105
    3.8.1 与近期算法的性能比较  95-103
    3.8.2 在NIST SD27指纹库上的检索性能  103-105
  3.9 结论  105-106
第四章低质量现场指纹的检索方法研究  106-121
  4.1 引言  106
  4.2 低质量指纹检索存在的问题  106-110
  4.3 现场指纹三角形多播  110-116
  4.4 基于现场指纹三角形多播的指纹检索方法  116-117
  4.5 实验  117-120
  4.6 结论  120-121
第五章超大规模指纹库检索系统的索引结构和检索方法  121-132
  5.1 引言  121
  5.2 模块功能分析  121-122
    5.2.1 指纹检索模块的功能  121
    5.2.2 指纹图像质量评价模块的功能  121-122
  5.3 系统设计  122-128
    5.3.1 索引器的构建  122-123
    5.3.2 基于BP神经网络的两类分类器的训练  123-124
    5.3.3 基于图像质量等级的浮动检索阈值集合的建立  124-126
    5.3.4 基于探查指纹质量的检索模块  126
    5.3.5 指纹检索系统检索效果的评价标准  126-128
  5.4 实验  128-131
    5.4.1 数据集  128
    5.4.2 在训练集中预测检索阈值  128-130
    5.4.3 整个指纹检索系统的性能  130-131
  5.5 总结  131-132
第六章总结与展望  132-135
  6.1 本文工作总结  132-133
    6.1.1 指纹质量评价方法研究  132
    6.1.2 基于细节点多元组的指纹检索方法研究  132-133
    6.1.3 低质量现场指纹的检索方法研究  133
    6.1.4 超大规模指纹库检索系统的索引结构和检索方法  133
  6.2 展望  133-135
参考文献  135-141
致谢  141-142
攻读学位期间发表的学术论文目录  142

超大规模指纹库的索引结构和检索方法

内容摘要

全文目录

相似论文