指纹识别技术在整个生物特征识别领域占据着重要地位，目前传统的指纹识别系统在指纹匹配准确度上也已经达到了比较理想的效果。然而，随着数据信息的膨胀，在很多应用场合下指纹数据库的规模越来越大，当系统需要处理大容量的指纹数据库时，如果采用传统的一对一的指纹识别模式，则将消耗相当长的时间。这对于实时性要求较强的应用系统而言，显然是不可接受的。为了提高大容量数据库下指纹识别的效率，一种基于指纹检索策略的快速搜索方案被提出，这一方案将有效降低整个指纹识别过程的耗时量。
此外，在嵌入式技术高速发展的今天，市场对于高度集成化、便携化、智能化的嵌入式指纹系统有着强烈的需求。考虑到嵌入式指纹系统需要进行现场指纹采集、指纹查找和验证等过程，则更需要合理的策略来保证系统的实时性和可靠性。因此，设计高效的嵌入式指纹检索算法，并在具有大容量指纹数据库的嵌入式系统下实现指纹的快速检索与匹配，有着重要的研究意义和广泛的商业价值。
1.自动指纹识别系统研究
随着计算机和信息技术的发展，FBI和法国巴黎警察局于上世纪六十年代开始了对自动指纹识别系统AFIS（Automatic Fingerprint Identification System）的研究。自动指纹识别系统（AFIS）最初使用于刑事案件侦破之中，到了九十年代，被广泛用于个人身份的鉴定。
自动指纹识别系统（AFIS）是一个典型的生物特征识别系统，它包括了指纹图像采集模块、图像预处理模块、指纹特征分析与提取模块、指纹对比匹配模块等几个部分。在实际应用中，一个完整的自动指纹识别系统一般可以实现指纹注册和指纹匹配两大功能。在进行指纹注册时，系统首先通过指纹图像采集模块采样得到待注册用户的指纹图像数据；随后将这些数字化的图像信息传入主控制器，并由图像预处模块进行预处理加工；接着由指纹特征分析与提取模块提取出需要的指纹特征，并生成指纹特征模板；最后将特征模板存放到指纹数据库中。在进行指纹匹配时，首先依然是采集待鉴定用户的指纹图像数据；接着同样进行图像预处理和指纹特征提取；然后利用提取到的待测指纹特征与指纹库中的指纹特征模板进行对比；最后给出认证结果以确认身份是否匹配。自动指纹识别系统基本工作流程如图1所示。
图1自动指纹识别系统基本工作流程图
为了应对某些大容量指纹数据库下自动指纹识别系统运行效率低下的问题，目前学术界也提出了相关优化措施，其中以指纹分类策略和指纹检索策略最具代表性。指纹分类技术的不足之处在于人体指纹并非均匀的分布在各个指纹类中，在很大的数据库下并不能很有效的减小对比范围；另外对于模糊指纹，并不能起到准确的分类效果。而指纹检索技术则能较好的避免以上问题，在缩小对比范围的同时，也克服了模糊指纹分类不确定的缺陷。
2.指纹检索算法与程序设计
2.1指纹图像预处理算法
指纹检索的首要环节就是进行指纹图像的预处理工作，其目的是为了去除图像无效区域、降低噪声，从而提高指纹检索的效率。在利用指纹采集器获取到灰度化的原始指纹图像后，首先是进行指纹图像的分割，提取出指纹前景区；然后再通过计算平均像素灰度的方法对图像进行标准化处理，使指纹图像的灰度和对比度调整到一个统一标准的范围内。
预处理的第二环节是图像的滤波增强，本文采用基于方向场和频率场特性的Gabor滤波增强算法对指纹图像进行增强处理。在滤波前首先需要计算指纹图像的脊线方向场图像和频率特性图，对于指纹脊线方向场信息，采用经典的Sobel算子求取像素的梯度值，然后利用求出的像素横向梯度矢量Gx和纵向梯度矢量Gy计算方向角度值；对于指纹频率信息，则通过计算某一区域指纹脊线间平均像素距离而得到。获得以上信息后，再利用Gabor滤波函数对指纹图像做增强处理。
得到增强的指纹图像后，还要对图像进行二值化和细化处理。二值化是使灰度图像变成黑白图像，将图像在灰度层次上从原来的256色降为黑白2色，对指纹图像信息量进行了压缩；细化则是在不改变原有图像像素拓扑连接关系的条件下，保留了纹线的主要信息，使指纹图像的脊线分布变得简单明了，为指纹特征的提取和索引做准备，因此也是图像预处理中非常重要的一步。
2.2指纹特征提取算法
指纹特征提取的主要目的是计算指纹核心点（Core）和细节点（Minutia）的特征信息。在提取指纹核心点时，采用的是Poincare Index算法，该算法的思路是在指纹图像某像素点区域内，按围绕该点的闭合曲线逆时针方向旋转一周，计算方向角度旋转变化量的和，最后以计算结果来寻找核心点。计算过程中如果某像素点的Poincare Index值为π则判定为核心点，然后便提取该点的坐标与方向场信息，记为P（Cx， Cy，θc）。
对于指纹的细节点特征，在本设计中只要求提取指纹脊线端点（Ending）和脊线分叉（Bifurcation）两种细节点。在细化的指纹图像中，这两种细节点的形态如图2和图3所示：
图2 脊线端点
图3 脊线分叉
在提取指纹细节点时，首先为细化图像中的每个像素点P建立一个8邻域像素区，如图4所示。其中P1~P8为像素点P周围的邻近环绕像素点。P1~P8中黑色点的值设为1，白色点的值设为0.
图4 8邻域像素图
根据Crossing Number （CN）理论，在8邻域像素图中按照公式1计算像素点的CN值。例如在图2和图3中，8领域像素区域内中心点的CN值分别为1和3.
最后按上述方法对细化指纹图像中的所有像素点进行CN值计算，当CN值为1时，可判定所检测的P点为脊线端点，当CN值为3时，则可判定P点为脊线分叉点。检测到细节点之后返回该点的坐标（x，y），并根据CN的值返回细节点的类型T，然后再读取该点的方向角θ。因此，在本算法中一个指纹细节点的具体特征最后用M（x， y，θ，T）算子来表征。
2.3 指纹索引与检索算法
在得到一系列的指纹特征后，接下来就是设计指纹综合索引因子。索引因子以多维向量的形式表示，概括了一枚指纹图像的综合特征。指纹检索时通过将待查询指纹的索引因子与数据库中指纹的索引因子相比较，可快速计算得出与目标指纹相似度较高的一批候选指纹，达到有效缩减匹配范围的目的。指纹综合索引因子的设计描述如下：
公式2中Θm×n 代表将指纹图像划分为m×n块以后，由指纹图像每一子块局部脊线方向场组成的角度矩阵；Fm×n代表指纹的局部脊线频率矩阵；D代表以指纹核心点P(Cx,Cy)为中心，固定半径R内所有细节点到核心点距离的平均值；Δ则代表离核心点最近的三个细节点(设M1, M2, M3)的方向角与核心点方向角的差值，记作Δ={ω1, ω2, ω3}(ωi=θi-θc，且-π<ωi<π)。
检索开始时，设待查询指纹的综合索引因子为S{Θm×n，Fm×n，D，Δ}, 指纹数据库中的指纹综合索引因子为S’{Θ’m×n，F’m×n，D’，Δ’}。然后计算以下各项相似度分数：
其中dj=θ[j]-θ’[j], (j=1,2,…,m×n；θ[j]为指纹图像第j块的局部脊线方向角)。
最后根据以上4个相似度值计算S和S’这两枚指
