LC698S片上指纹算法的优化与应用

武言哲，谢吉华,，徐芳

(1.东南大学，南京 210096；2.无锡市信息安全工程技术研究中心)

LC698S片上指纹算法的优化与应用

武言哲1，谢吉华1,2，徐芳2

(1.东南大学，南京 210096；2.无锡市信息安全工程技术研究中心)

主要介绍在无MMU支持的硬件环境中，为了解决程序运行的内存碎片的问题，利用自定义的内存池(Memory Pool)为指纹程序分配内存空间，通过片内RAM实现指纹识别功能的方案。本文对经典的预处理算法以及以特征点的拓扑结构作为特征值的识别算法作了进一步的优化。除此之外，本文提出分辨率动态分布算法，这种算法降低了原图像分辨率，改变了图像大小，节省了片内RAM空间，加快了图像处理速度，使得FAR与FRR达到识别要求，同时缩短指纹识别时间。

LC698S；分辨率动态分布；内存池；指纹识别

引 言

在基于点模式的指纹识别过程中，对处理器浮点运算要求较高的是指纹图像分割和增强，定点运算较多的是二值化与细化。所以如果在没有专用指纹处理模组的环境中进行开发，主控芯片需要具备一定的浮点运算能力。与此同时在软件上，开发人员需要提高内存空间的利用率，对指纹识别算法作出优化。

在不同的应用场景中，对嵌入式指纹识别的硬件与软件的有着不同要求。例如对于指纹锁与门禁的应用场景，算法的设计要尽可能降低识假率(FAR)，而对于员工考勤机，则尽可能降低拒真率(FRR)。由于本文的应用场景是为PKI体系中USB Key的使用者提供私人信息的保密性，所以整个指纹识别算法的改进需要降低识假率。本文选用的处理器LC698S是由华芯研发的国内税控专用SoC安全芯片，具备一定的浮点运算能力，内嵌了外设模块，可作外扩功能的开发。笔者针对这种国产芯片，利用片内RAM空间，进行指纹识别功能的开发。

1 硬件组成

硬件整体架构主要包含主控芯片LC698S以及指纹传感器JP2050,其中，传感器与芯片的通信采用的是SPI协议。为了缩短指纹图像认证时间以及防止指纹特征信息的泄露，笔者完全利用片内RAM作为指纹图像处理与识别运算的空间，另外NAND Flash中存放的是指纹识别源码与指纹特征信息。整体硬件组成图如图1所示。

图1 硬件组成框图

1.1 主控芯片

LC698S为SPARC V8架构、32位 RISC嵌入式微处理器，内嵌32位整型数处理模块， 32位和64位的浮点数处理模块，具有较强的运算能力。除此之外，内嵌了大量的外设，其中包括64 KB片内RAM空间，智能卡控制器与磁卡控制器等。该芯片处理指令速度为160 MIPS，双精度浮点运算速度为40 MFlops，主频为166 MHz。处理器功能框图如图2所示。

图2 处理器功能框图

1.2 指纹传感器

JP2050S按压式指纹传感器是CMOS型指纹传感器，分辨率为508 dpi，指纹采集区像素点阵为192×192 pixels，通信协议为SPI，输出256级灰度图像，单像素存储空间为8位。所以每幅采集图像大小(实际位图数据)为36 KB。

由于主控芯片片内内存为64 KB，每个图像大小至少为36 KB，为了减少指纹识别程序在内存中所占用的空间，笔者在算法层面对指纹图像的像素数量作了进一步的缩减，具体内容在软件解决方案中会有所体现。

2 软件开发环境

开发工具选择SPARC交叉开发工具链，主要包括Sparc-elf-gcc、Sparc-elf-ld、Sparc-elf-objdump等，使用主控芯片内部的DSU和DCL串行通信模块进行在线调试。DCL对外遵循RS232标准，在DSU调试模式下，通过TAP接口动态监视芯片片内寄存器与存储器等。

为了在应用程序运行时分配连续的地址空间，可以将内存池的设计引入到指纹识别程序中，使用已经封装好的接口申请内存空间。主要函数接口如下：

① mpool_t *mpool_open(const unsigned int flags, const unsigned int page_size, void *start_addr, int *error_p)

功能：申请开辟一个内存池。

② int mpool_close(mpool_t *mp_p)

功能：释放已经分配的内存池。

③ void *mpool_alloc(mpool_t *mp_p, const unsigned long byte_size, int *error_p)

功能：在内存池内申请字节空间。

④ int mpool_free(mpool_t *mp_p, void *addr, const unsigned long size)

功能：在已申请的内存池中，释放从固定物理地址开始的一段固定长度的字节空间。

⑤ int mpool_stats(const mpool_t *mp_p, unsigned int *page_size_p, unsigned long *num_alloced_p, unsigned long *user_alloced_p, unsigned long *max_alloced_p, unsigned long *tot_alloced_p)

功能：返回一个已申请内存池的统计信息。

笔者在μClinux系统上进行了内存池源码测试，起始地址为0x577d fa4a。本次测试的内存池，主要目的是测试各个库函数的功能。需要指出的是指纹识别功能的开发并不是基于μClinux操作系统而进行的，而是利用Sparc开发工具链，直接在芯片内部进行。本次工作仅是测试内存池功能函数，其目的是在Sparc开发环境中，为内存池的成功应用做准备。测试结果如图3所示。

图3 内存池参数分配图

3 指纹算法的改进

经典松弛匹配算法是由Sanjay、Ranade与Rosenfeld等人设计与实现的，经典Hough变换方法是由Stockman等人提出的，基于二维聚类的快速算法是由Shih-hsu、Chang 等人设计与实现的，三角匹配算法由Zsolt Miklos 等人提出。除此之外，还有工程师，如Xudong Jiang等人将指纹特征点的全局与局部拓扑结构进行归类，分步分段进行指纹匹配工作。

为了在提高识别速度的同时，减少图像占用内存的空间，笔者对指纹原图像像素点的分布进行了动态规划，使得原本为508 dpi图像分辨率的分布是依据指纹图像梯度场的分布而重新规划的，整体上降低了指纹图像像素数量，从而减少图像大小，减少了识别程序所占用内存空间，加快了处理图像的速度。

3.1 分辨率动态分布算法

分辨率的动态分布要依据指纹纹线的疏密程度来划分，衡量指纹纹线疏密程度的物理量为指纹纹线的梯度场。

具体梯度场的获取是根据对每个像素灰度的大小f(x,y)求(x,y)的偏导数，然后取模值|T|可求得。由于后期方向滤波过程需要图像方向场，这里图像方向场也一并计算出来。方向场以右手定理垂直于梯度方向为基准，然后对参数θ的值进行正交分解。方向场的获取利用Sobel算子去求(x,y)的偏导数，并将方向场的每一点像素与周围像素联系起来。Sobel算子表示如下：

梯度图与方向图的处理效果如图4所示。

图4 梯度图和方向图

对于指纹纹线比较紧密的区域，相应的梯度图像的灰度值偏高，视觉上所呈现出的结果是偏白色。所以在像素点采集步长上要偏小。反之，对于纹线较为稀疏的区域，相应的梯度图像灰度值偏低，视觉上所呈现出的结果是偏黑色。因为白色区域是保留指纹特征点信息较多的区域，所以进行分辨率划分时，分辨率要高，像素取点的步长要短。反之，因为黑色区域保留的指纹特征点信息较少，分辨率要低，所以像素取点的步长要较长。根据梯度场图像灰度值的分布，可以人为地给出像素采集步长。

3.2 指纹图像处理算法

此部分主要论述的是对经过分辨率重新分布的指纹图像进行预处理的过程。

图像分割算法就是利用合理梯度的模作为阈值，以此来分割前景与背景区，增强算法采用的是方向滤波方法，以及在脊线方向上采用空域滤波使得脊线变得连续，弥补脊线断裂的不足。在法向上采用频域滤波，将脊线之间的噪声点去除，这样做有利于后期的二值化处理。具体的空域滤波，笔者选择的是平滑滤波法，频域滤波采用的是非线性高通滤波。所谓平滑滤波就是将8邻域平均像素值作为中心像素点的像素值。为了充分利用指纹脊线相间的特点，需要对脊线进行振荡加强，法向滤波采用Gabor函数[6]。笔者将切向与法向运算进行了简化，以减少主控芯片的运算时间与运算量，切法方向模板表示如下：

切向模板：Hw=1/7(1,1,1,1,1,1,1)

法向模板：Vw=1/7(-3,-1,3,9,3,-1,-3)

二值化基本思想是，计算切向灰度与法向灰度，如果切向灰度大于法向灰度，判断为黑点，如若相反则判断为白点。因为考虑到误差的影响，所以在实际计算过程中采用了对每一个像素点添加相应加权值的方法。这样做降低了由二值化产生的噪声点所带来的误差。笔者所设置加权值参数如下：

切向加权值：Hw[7]=(2,2,3,4,3,2,2)

法向加权值：Vw[7]=(1,1,1,1,1,1,1)

细化算法采用的是查表法，基本思想是判断黑点的图像边缘特征，即周围的8点必定表现一定的色彩顺序。周围的色彩顺序共有256种，一一进行枚举不现实，笔者参考了许多文献总结出一张细化表，用一个字节来表示一种色彩顺序。

端点与分叉点的提取算法采用经典的8邻域提取算法[7]，以Pk作为灰度值，具体数学表达式为

中心点的提取需要采用Poincare公式。为了便于计算机编程,同样用方格法进行奇异点的提取，本文采用5×5与3×3方格法。在5×5方格内，以(i,j)为中心，选取封闭曲线D1、D2、…、D12，方向为逆时针。该闭合曲线的Poincare值为：

Poincare(i,j)=∑121|D1-D(i+1)mod12|

3×3方格计算与5×5方格计算类似，在此不赘述。当5×5方格与3×3方格计算的Poincare值相同时，候选点可以作为奇异点，以作为配准中心点。图5为指纹预处理各个阶段的效果图。

图5 指纹处理效果图(从左至右依次为分割图、二值化图、细化和特征点提取图)

3.3 指纹匹配算法

配准的原理是首先依据每个特征点周围场的分布，寻找配准点作为两幅图像的参考点，然后计算出每个特征点之间的拓扑关系，为了便于在片外Flash空间存储指纹特征信息，需要将拓扑关系进行压缩编码[8]。下面是指纹特征点拓扑结构源码：

typedefstructtagMinutiae{

sint32x; //横坐标

sint32y; //纵坐标

sint32Direction; //方向

sint32Triangle[3]; //特征点为等边三角形三个顶点

sint32Type; //类型

}MINUTIA, *MINUTIAPTR;

相似度结构源码如下:

typedefstructtagMatchResult{

sint32Similarity; //相似度

sint32Rotation; //旋转偏移总量

sint32TransX; //水平偏移总量

sint32TransY; //垂直偏移总量

sint32MMCount(); //匹配特征点数

}MATCHRESULT, *PMATCHRESULT;

图6所示的流程图展现的是最终配准与匹配的过程。

图6 指纹特征匹配模块算法流程

4 算法实现与性能分析

此部分主要论述的是阈值的选定以及性能参数FAR和FRR的确定，测试用例选择的是国际指纹识别大赛的指纹库FVC2008。

实验样本的选取与测试方案的设计如下：

根据实验样本1，可计算出FRR，具体计算方法为FRR=失败匹配次数/总的匹配次数。

实验样本2如下：

根据实验样本2，可计算出FAR，具体计算方法为FAR=成功匹配次数/总的匹配次数。

本文设定了MatchScore=1，2，…，12，总共12级阈值，在每级阈值下对实验样本1和实验样本2进行匹配实验，实验结果如图7所示。

图7 FAR和FRR测试结果图

可以看出，阈值分数对于拒真率和识假率的影响是成反比的，在阈值分数为8的时候，两项指标均处于较低的水平，因此8为目标取值。

最终笔者将指纹算法移植到片外Flash中，利用SPARC开发工具链对指纹传感器所抓取的指纹位图图像文件进行读取并在片内进行了识别处理。为了便于优化功能，在控制台打印了指纹识别各个过程所占用CPU的时间。LC698S性能参数为160MIPs/40MFlops(doubleprecision)@166MHz。最终运行结果如图8所示。

图8 最终运行结果

从图中可以清晰地看出，整个识别过程耗时低于300ms。本文对经典指纹识别算法的改造，应用到搭载LC698S芯片上的是成功可行的。

结 语

[1] Chang C H,Cheng F H,Hsu W H,et al.Fast algorithm for point pattern matching: invariant to translations,rotations and scale changes [J].Pattern recognition,1997,30(2):311-320.

[2] Kovács-Vajna Z M.A fingerprint verification system based on triangular matching and dynamic time warping[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2000,22(11):1266-1276.

[3] Jiang X,Yau W.Fingerprint minutiae matching based on the local and global structures[C]//Proceedings.15th International Conference on. IEEE,2000.

[4] Jain A,Lin H,Bolle R.On-line fingerprint verification[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,1997,19(4):302-314.

[5] A. Jain S,Prabhakar L,Hong S,et al.Finger Code:a filterbank for fingerprint representation and matching [C]//IEEE Computer Society Conference on. IEEE,1999.

[6] 刘国柱.基于ARM9的家庭智能安防系统研究[D].济南:山东大学,2011.

[7] 张圆圆.指纹识别技术相关算法的研究[D].北京:北京邮电大学,2012.

[8] 李汝才.基于ARM9的嵌入式指纹识别系统[D].哈尔滨:哈尔滨工程大学,2013.

武言哲(硕士研究生)，主要研究方向为系统芯片与嵌入式系统应用。

Optimization and Realization of On-chip Fingerprint Algorithm Based on LC698S

Wu Yanzhe1,Xie Jihua1,2,Xu Fang2

(1.Southeast University,Nanjing 210096,China;2.Wuxi Research Center for Information Security Engineering)

In order to solve the program memory fragmentation problem in the hardware environment without MMU support,the function of fingerprint identification scheme is achieved through using the custom memory pool for fingerprint application allocated memory space.In the paper,the classical preprocessing algorithm and the feature point topology as the recognition algorithm are optimized.Besides,a dynamic allocate against resolution algorithm is proposed,which reduces the original image resolution,changes the image size,saves the on-chip RAM space,speeds up the image processing speed,makes the FAR and FRR achieve the recognition requirements,and shortens the fingerprint identification time.

LC698S;dynamic distribution resolution;memory pool;fingerprint verification

TP312

A

士然

2016-12-12)