引言

指纹识别技术在整个生物特征识别领域占据着重要地位，目前传统的指纹识别系统在指纹匹配准确度上也已经达到了比较理想的效果。然而，随着数据信息的膨胀，在很多应用场合下指纹数据库的规模越来越大，当系统需要处理大容量的指纹数据库时，如果采用传统的一对一的指纹识别模式，则将消耗相当长的时间。这对于实时性要求较强的应用系统而言，显然是不可接受的。为了提高大容量数据库下指纹识别的效率，一种基于指纹检索策略的快速搜索方案被提出，这一方案将有效降低整个指纹识别过程的耗时量［1］。

此外，在嵌入式技术高速发展的今天，市场对于高度集成化、便携化、智能化的嵌入式指纹系统有着强烈的需求。考虑到嵌入式指纹系统需要进行现场指纹采集、指纹查找和验证等过程，则更需要合理的策略来保证系统的实时性和可靠性。因此，设计高效的嵌入式指纹检索算法，并在具有大容量指纹数据库的嵌入式系统下实现指纹的快速检索与匹配，有着重要的研究意义和广泛的商业价值。

1 自动指纹识别系统研究

在进行指纹匹配时，首先采集待鉴定用户的指纹图像数据；接着同样进行图像预处理和指纹特征提取；然后利用提取到的待测指纹特征与指纹库中的指纹特征模板进行对比；最后给出认证结果以确认身份是否匹配。自动指纹识别系统基本工作流程如图1所示。

图1 自动指纹识别系统基本工作流程图

为了应对某些大容量指纹数据库下自动指纹识别系统运行效率较低的问题，目前学术界也提出了相关优化措施，其中以指纹分类策略和指纹检索策略最具代表性。指纹分类技术的不足之处在于人体指纹并非均匀地分布在各个指纹类中，在很大的数据库下并不能很有效地减小对比范围；另外对于模糊指纹，并不能达到准确的分类效果。而指纹检索技术则能较好地避免以上问题，在缩小对比范围的同时，也避免了模糊指纹分类不确定的缺陷。

2 指纹检索算法与程序设计

2.1指纹图像预处理算法

指纹检索的首要环节就是进行指纹图像的预处理工作，是为了去除图像无效区域、降低噪声，从而提高指纹检索的效率。在利用指纹采集器获取到灰度化的原始指纹图像后，首先进行指纹图像的分割，提取出指纹前景区；然后再通过计算平均像素灰度的方法对图像进行标准化处理，使指纹图像的灰度和对比度调整到一个统一标准的范围内。

预处理的第二环节是图像的滤波增强，采用基于方向场和频率场特性的Gabor滤波增强算法［4］对指纹图像进行增强处理。在滤波前首先需要计算指纹图像的脊线方向场图像和频率特性图，对于指纹脊线方向场信息，采用经典的Sobel算子［5］求取像素的梯度值，然后利用求出的像素横向梯度矢量Gx和纵向梯度矢量Gy计算方向角度值。对于指纹频率信息，则通过计算某一区域指纹脊线间平均像素距离而得到。获得以上信息后，再利用Gabor滤波函数对指纹图像做增强处理。

得到增强的指纹图像后，还要对图像进行二值化和细化处理。二值化是使灰度图像变成黑白图像，将图像在灰度层次上从原来的256色降为黑白2色，对指纹图像信息量进行了压缩；细化则是在不改变原有图像像素拓扑连接关系的条件下，保留了纹线的主要信息，使指纹图像的脊线分布变得简单明了，为指纹特征的提取和索引做准备，因此也是图像预处理中非常重要的一步。

2.2 指纹特征提取算法

指纹特征提取的主要目的是计算指纹核心点(Core)和细节点(Minutia)的特征信息。在提取指纹核心点时，采用的是Poincare Index算法［6］，该算法的思路是在指纹图像某像素点区域内，按围绕该点的闭合曲线逆时针方向旋转一周，计算方向角度旋转变化量的和，最后以计算结果来寻找核心点。计算过程中如果某像素点的Poincare Index值为π，则判定为核心点，然后便提取该点的坐标与方向场信息，记为P(Cx, Cy, θc)。

对于指纹的细节点特征，在本设计中只要求提取指纹脊线端点(Ending)和脊线分叉(Bifurcation)两种细节点。在细化的指纹图像中，这两种细节点的形态如图2和图3所示。

图2 脊线端点图3脊线分叉

图4 8邻域像素图

在提取指纹细节点时，首先为细化图像中的每个像素点P建立一个8邻域像素区，如图4所示。其中，P1~P8为像素点P周围的邻近环绕像素点，P1~P8中黑色点的值设为1，白色点的值设为0。

根据Crossing Number (CN)理论［7］，在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 指纹索引与检索算法

在得到一系列的指纹特征后，接下来就是设计指纹综合索引因子。索引因子以多维向量的形式表示，概括了一枚指纹图像的综合特征［78］。指纹检索时通过将待查询指纹的索引因子与数据库中指纹的索引因子相比较，可快速计算得出与目标指纹相似度较高的一批候选指纹，达到有效缩减匹配范围的目的。指纹综合索引因子的设计描述如下：

其中，Θ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′这两枚指纹的总体相似分数T。

式(7)中,μ表示各部分相似度值的权重因子。根据实际测试，在保证检索效果最佳时，μ的各项经验值分别取：μ1=0.28，μ2=0.16，μ3=0.30，μ4=0.26。检索算法按照索引因子比对法,则将待查询指纹与数据库中的所有指纹进行检索对比，在遍历完整个指纹数据库以后，得到了一系列的相似度分数。最后根据设定的阈值分数，选出分数最高的一部分指纹，从而减小指纹对比识别的范围。

2.4 软件程序设计

软件程序是整个指纹检索算法的映射与实现，它将算法的各个理论环节转化为实际的函数，并封装成可以在嵌入式系统下执行的功能模块。本文中嵌入式指纹检索程序实现用户指纹注册和指纹检索匹配两大功能，涵盖了指纹采集程序、指纹图像预处理程序、指纹特征提取程序、指纹索引与检索程序、指纹匹配程序等部分，其执行流程如图5所示。软件进入到执行状态后，首先按照用户指令参数进行模式判断，选择进入到指纹注册或者指纹检索状态。当选择指纹注册入库时，软件会先进行指纹图像采集，然后对图像进行预处理，接着提取出指纹的细节特征并建立指纹索引因子，最后将指纹特征模板和对应的索引因子入库保存。而当需要进行指纹检索时，系统同样会先进行指纹采集、图像预处理、特征提取和索引因子建立，然后利用索引因子进行指纹库检索，找出与查询指纹最相似的一批待匹配指纹，最后利用匹配程序对这部分指纹逐一对比，给出匹配结果。

图5 嵌入式指纹检索软件执行流程图

3 嵌入式应用平台设计

为了使所设计的指纹检索算法得到实现和验证，根据嵌入式指纹检索系统的要求，还需要设计嵌入式应用平台。该平台的设计主要分为硬件系统和软件环境两部分。

3.1 嵌入式硬件系统设计

本文所设计的用于指纹检索算法实现与验证的嵌入式硬件平台，以东南大学自主研发的高性能微处理器SEP6200为核心控制单元［9］。SEP6200是一颗32位的高性能应用处理器，主频达到800 MHz，有着高效的运算和控制能力，能够较好地执行指纹检索程序。主控制器配合DDR、NAND Flash、LCD、USB指纹采集器等外围设备，搭建成了完整的嵌入式指纹检索硬件平台，图6是嵌入式指纹检索系统的硬件框架结构图。

系统中主控制器SEP6200用于控制指纹采样和进行任务调度；DDR模块用来临时存储指纹图像数据和执行软件程序；NAND Flash用以存放算法软件代码和指纹数据库；LCD显示屏在执行算法时用于提供良好的GUI用户界面；USB指纹采集器则是用来采集原始指纹图像，并将图像数据经USB接口传送至核心控制单元。

图6 嵌入式指纹检索系统硬件平台架构图

3.2 嵌入式软件系统配置

嵌入式软件系统主要涉及到操作系统和设备驱动配置两个方面。

3.2.1 嵌入式Linux操作系统

本设计采用Linux2.6内核操作系统作为嵌入式底层软件基础平台。Linux操作系统作为一个开源软件系统，有着良好的可配置、可裁剪特性，同时其开发周期短、成本低、安全性高，非常适用于嵌入式系统上指纹检索应用软件的开发和测试。

3.2.2 驱动程序配置

为了使操作系统能够控制USB指纹采集器和LCD等外设工作，必须为Linux内核配置相关的设备驱动程序。对于USB指纹采集器，本设计采用V4L2驱动框架对图像数据进行控制管理，V4L2是Linux下开发视频设备驱动的一套新框架，该框架为驱动程序定义了一系列对应的回调函数，同时为应用程序定义了一套标准的API 调用，便于用户在应用层通过URB获得指纹图像数据。此外，对于LCD液晶显示屏也需要提供相应的驱动支持，LCD通常由微处理器的LCDC(LCD Controller，LCD控制器)进行控制。

4 系统测试与分析

在系统设计完成之后，对系统的性能和效率等指标做了相应的测试。实验中采用了两个指纹数据库进行系统验证，分别是国际标准指纹测试库FVC2000DB3和本系统采集自建的指纹数据库库OWNDB。FVC2000DB3包含800张指纹图像，OWNDB包含500张指纹图像，两库中的图像都以8位灰度的BMP格式保存，图7和图8分别为两个指纹数据库的示例图像。

指纹检索算法的性能采用检索穿透率(Penetration Rate, PR)和检索错误率 (Error Rate, ER)衡量。检索穿透率(PR)定义为检索得出的待匹配指纹数量占整个数据库的比重，该比重可以由算法程序员自行设定；检索错误率(ER)则定义为在某一穿透率的限制下，在待匹配指纹中未检测到目标指纹的概率，即检索失败率。在实验中利用所述的两个指纹数据库对系统进行测试，得到一系列的实验数据，将这些实验数据进行曲线拟合，绘制出如图9所示的曲线图。

图7 FVC2000DB3指纹图图8OWNDB指纹图

图9 指纹检索系统的性能实验数据

从实验数据图可知，在FVC2000DB3数据库上，当检索穿透率为10%时，系统检索错误率在6%左右。而在OWNDB数据库上，当穿透率为10%时，系统错误率则可降低至4.6%以内，充分验证了本设计的可靠性。此外作为嵌入式系统，软件程序的执行效率也是一项重要指标。在实验中，当系统进行1:800检索时总耗时为1.63 s；当进行1:500检索时总耗时为0.99 s。总体来看，系统的实时性也达到了比较良好的指标。

结语

指纹检索算法是一种应用于大容量指纹数据库的快速指纹搜索方案。本文在对传统自动指纹识别系统研究的基础上，设计了基于多维向量指纹索引因子的快速指纹检索算法，同时利用国产SOC芯片SEP6200，搭建了嵌入式应用平台，并最终将所设计的算法以应用程序的形式在嵌入式目标平台上进行映射与实现。系统经过实验测试与分析，得到了良好的性能指标，进一步论证了本设计的可行性。