嵌入式PPC平台指纹识别算法优化及实现_图文

1、微 处 理 机M I CROPROCESS ORS嵌入式 PPC 平台指纹识别算法优化及实现 朱礼波 , 付宇卓 , 谢 憬(上海交通大学 , 上海 200240 摘 要 :在现有指纹识别算法的基础上 , 根据嵌入式的特点 , 通过软件算法的加速以及系统硬 件的配置优化来实现板级的指纹识别系统 。通过交叉编译器把二进制代码转化为适合于 power 2 pc405core 类型的数据 , 采用 S DK 工具 Xilinx XUP V irtex -II Pr o Devel opment Syste m 开发板协同仿 真 。 在软件算法加速优化的基础上速度得到了很大的提高 。关键词 :指纹识别

2、 ; PPC 处理器 ; 嵌入式 ; 软件加速中图分类号 :TP391 文献标识码 :A 文章编号 :1002-2279(2009 05-0082-04The I m p l em en ta ti o n and A rithm e ti c I m p r o en o f F r ti ngu ish o n the P PC P l a tfo r m i n SZ -bo,(School U , Shanghai 200240, China the p arithmetic, according t o the characteristic of e mbed the syste m

3、 of finger p i p le mented . B inary code is converted by cr oss -comp iler t o the kind of data fitful f or pc405core . U sing the t ool of S DK -Xilinx XUP V irtec -II Pr o Devel opment Syste m devel opment board does HW /S W co si m ulati on . The s peedup of s oft w are arith metic and the confi

4、gurati on of hard ware i m p r ove the perf or mance of finger p rint distinguish .Key words:Finger p rint; PPC; Embed; Soft w are s peed -up1 引 言近年来 , 越来越多的个人 、 消费者 、 公司和政府 机关都认为现有的基于智能卡 、 身份证号码和密码 的身份识别系统很繁琐而且并不十分可靠 。 生物识 别技术为此提供了一个安全可靠的解决方案 。 其中 指纹识别技术是目前最为成熟的 、 应用也最为广泛 的生物识别技术 。 每个人的包括指纹在内的皮肤纹 路

5、在图案 、 断点和交叉点上各不相同 , 也就是说 , 这 些指纹特征是唯一的 , 并且终生不变 。依靠这种唯 一性和稳定性 , 就可以把采集到的指纹同预存的指 纹对应起来 , 通过对采集的指纹和预先保存的指纹 进行比较 , 就可以验证出被检查人的真实身份 。虽 然基于 DSP 或者 ARM 的指纹识别论证系统已经在 考勤 、 门禁等领域实现商品化 , 但这样的嵌入式系统 很难实现小型化集成化 , 更无法 S OC, 所以本文采用 基于 Xilinx FPG A 来实现指纹识别论证系统 , 利用 FPG A 高集成度 , 低功耗 , 短开发周期等优点 , 具有 很强的现实意义和广阔的市场空间 。

6、 2 指纹识别技术原理以及算法介绍指纹识别技术的原理与其他生物识别技术的原 理类似 。 它是利用人体的指纹特征对个体身份进行 区分和鉴定 。 指纹识别的关键在于识别指纹的总体 特征和局部特征 。指纹识别技术主要涉及四个功能 :读取指纹图 像 、 提取特征 、 保存数据和比对 。在一开始 , 通过指 纹读取设备读取到人体指纹图像并对其进行初步的 处理 , 使之更加清晰 。 接下来 , 指纹辨识软件建立指 纹的数字表示 特征数据 , 一种单方向的转换 , 可 以从指纹转换成为特征数据 , 但不能从特征数据转 换成指纹 , 通常称其为模版 。最后通过计算机模糊 比较的方法 , 将两个指纹的模版进行比

7、较 , 计算出它 们的相似程度 , 最终得到两个指纹的匹配结果 , 具体 的流程如图 1所示 。指纹识别算法主要包括如下几个步骤 :指纹图 像导入与格式转换 、 图像软化操作 、 计算指纹图像脊 线的方向 、 计算指纹脊线的频率 、 获取图像的有效区作者简介 :朱礼波 (1984- , 男 , 江苏省响水县人 , 硕士研究生 , 主研方向 :计算机系统结构。 收稿日期 :2008-08-26第 5期 2009年 10月 No . 5 Oct . , 2009 朱礼波等 :嵌入式 PPC 平台指纹识别算法优化及实现域 、 指纹图像增强 、 图像二值化 、 细化指纹图像 、 从细 化图像中提取细节

8、点并储存到集合中 、 在图像中画 出细节点 、 判断指纹是否匹配 。 如图 2所示。 图 1指纹识别步骤 图 2 指纹识别算法3 系统搭建与算法优化系统的搭建与算法优化主要包括硬件平台搭 建 、 软件算法介绍 、 算法裁减及加速算法 、 以及算法 实现优化这四部分 。 3. 1 硬件平台搭建系统采用 Xilinx X UP V irtex -II Pr o Devel opment Syste m 开发板搭建。 采用内嵌的 po wper pc405core 和相关的必要外部设备。 包括 UART, DDRA M 片内数 据与指令 BRA M, 快速 P LB 总线 , 慢速 OP B 总线。

9、 UART 的作用在于与外界通信 , 负责把比特流文件下载到 FPG A 开发板上 ; DDRA M 负责存储程序 ; 片内 的数据与指令 BRAM 起到 CACHE 的功能 , 所以把 常需要用到的数据与指令放到数据与指令 BRAM , 可以加快程序的运行 ; 快速总线 P LB 连接快速设 备 ; 慢速总线 OP B 则连接外围的慢速设备 , 这样可 以降低功耗 , 使接口简单化 。 系统结构如图 3所示 。 3. 2 算法介绍如图 2所示 , 指纹识别算法各步骤主要的作用 如下 :步骤一 主要实现指纹图像的导入 , 格式转换 , 大小处理 ;步骤二 主要实现图像软化操作 , 对导入图像进

10、行第一次处理 , 柔化象素值 , 减少部分噪声;图 3 硬件结构图;, 有 , 运行速度慢 , 有效区小 , 速度快 ;步骤六 指纹图像增强算法 , 该增强算法针对指 纹图像设计 , 它标记了指纹图像中没有使用的区域 , 而其它的区域 , 在增强后 , 脊线可以被清晰的分离出 来 (使用一个阈值 。该算法生成了一个脊线方向 图 , 一个掩码图 ;步骤七 图像二值化 , 将图像数据通过阈值转化 为 0x00和 0xFF 的集合 ;步骤八 细化指纹图像 , 使用“ H it and M iss ” 结 构元素 。 图像必须是二值化过的 (只包含 0x00或 0xFF , 该算法的缺点是产生很多伪造

11、的线条 (伪特 征 , 必须由另外的算法来消除 , 后处理非常必要 ; 步骤九 从细化图像中提取细节点 , 并储存到集 合中 ;步骤十 在图像中画出细节点 , 不改变背景 ; 步骤十一 判断指纹是否匹配 3. 3 算法裁减及加速算法算法裁减方面包括 :去除步骤四中的低通以及 步骤六的图像增强 , 该增强算法针对指纹图像设计 , 它标记了指纹图像中没有使用的区域 , 而其它的区 域 , 在增强后 , 利用分析并设置阈值 , 脊线可以被清 晰的分离出来 。 首先建立步骤评估体系 , 主要包括 运行时间以及对细节点数目的影响程度 。 由于最终 指纹匹配与否是通过对比细节点来实现的 , 因此裁 减的依

12、据为去掉那些占据较长的运行时间并且没有 对最终提取到的细节点数目有明显影响的步骤 。 另外由于步骤三获取指纹图像脊线的方向 , 含 有大量的循环 、 浮点 、 三角运算 ; 步骤四计算指纹脊38 5期 微 处 理 机 线的频率 , 含有大量的循环 、 数组 、 浮点 、 三角运算 ,是影响系统动作速度的主要方面 。 所以在算法裁减 的基础上 , 通过对主要步骤中的核心程序进行理解 , 采取算法加速来提高系统运行速度 。加速算法包括 :浮点定点化 , 数学函数重新编 写 。 由于浮点运算在硬件实现上有相当大的难度 , 不仅占用的系统资源较多 , 而且硬件运行的速度也 较慢 , 无法满足运行时间上

13、的要求 , 所以需要浮点定 点化 。浮点定点化的主要思想是以可以忍受的精度损 失来点定化以进行运算 ; 这其中的关键就是由程序 员来确定一个数的小数点处于 16位中的哪一位 。 这就是数的定标 。数的定标有 Q 表示法 , 不同的 Q 所表示的数不仅范围不同 , 而且精度也不相同 。 Q 越大 , 数值范围越小 , 但精度越高 ; 相反 , Q 越小 , 数 值范围越大 , 但精度就越低。 , Q0-32768到 +1, 为 -1到 0. 。 在 本系统中 , , 最终使用 Q8精度 , 精确到 1/256=0. 00390625。 例如 :浮点数 (x 转换为定点数 (x p :x q =(

14、int x ×2Q定点数 (x q 转换为浮点数 (x :x =(float x q ×2-Q设 x =0. 5001, y =3. 1, 则浮点运算结果为 :z =x +y =0. 5001+3. 1=3. 6001Qx =8, Qy =8, Qz =8则定点加法为 :x =128; y =794; z =922因为 z 的 Q 值为 9, 所以定点值 z =922即为浮 点值 z =(floa t 922/256=3. 6015625。由于嵌入式中调用数学函数的能力不强 , 所以 在调用数学函数如 sin ( , cos ( 的地方用自己写的 sinx ( , cosx

15、 ( 来替代 。最后系统运行的速度得到 很大的提高 , 提高了五倍以上 , 二分钟可以出来结 果 。 3. 4 算法实现优化系统的软硬件协同调试主要使用 Xilinx XPS 和 S DK 工具完成 。软硬协调主要注意的问题是 link scri p t 的设置 。 这是很重要的一步 , 包括设置程序存 储位置 , stack, heap 大小和所放位置 。 Stack 主要负 责函数调用 , 而 heap 负责函数中动态申请内存 。考 虑速度的缘故 , 在本系统中使用了如下二种方案 :方案一 程序存放在 BRAM 中 , 经过精简优化后的程序大小不到 100k, 可以放入 128K 的 BR

16、AM , 由于 BRAM 访问速度比 DDR 的访问速度要快很多 , 并且在运行中会多次调用该程序 , 因此将程序存放 在 BRAM 中可以提高速度 。方案二 程序 、 stack 、 heap 全都放在 DDR 中 , 这 样的话 , 保证程序能够正常运行 , 但是速度比较慢 , 在不进行算法修改 , 硬件加速的情况下 , 这种方法比 较可行 。4 系统调试与结果分析4. 1 系统调试经过分析各个步骤的时间消耗 , 选择从数据读 图 , 先 要 从 外 部 , 和 S DRAM 交 换 。由 于 CP U 访 问 片 外 S DRAM 的速度比较慢 , 这一过程将占用大量的 CP U 时间

17、。 为了提高识别速度 , 本系统考虑采用 DMA 方式加速这一过程 。在系统中加入一个 DMA 控制 器和一块片内的 BRAM , 通过 CP U 控制 DMA 直接 把外部 S DRAM 中的图像数据读取到片内 BRAM 中 , 然后对此数据流进行处理 。由于 DMA 操作几 乎不消耗 CP U 时间 , 而 CP U 访问 BRAM 的时间消 耗明显小于 CP U 访问片外 S DRAM 的时间消耗 , 这 一策略将有效提高识别速度 。在 CP U 对 指 纹 图 像 预 处 理 的 各 个 步 骤 中 , Gabor 滤 波是图象增强部分的核心 , 也是图象增强部 分乃至整个指纹图像预处

18、理过程中运算量最大 、 消 耗 CP U 时间最多的一步 , 因此考虑将 Gabor 滤波器 硬件化以降低 CP U 时间开销 。 4. 2 实验与结果分析打开 E DK 工具 , xp s 8. 2i, 加载 test 文件夹中的 syste m. x mp 工程 , 下载 bitstrea m 到 V irtex -II Pr o 开发板 , 在 cons ole window 有相应的提示 , 并在终端 中看到输出 , 打开 S DK, 并根据 verify 文件夹中的指 纹检测程序建立工程 , 对 L inker Scri p t 进行配置 , 运 行 debug, 并 在 X ML

19、cons ole 框中 输 入 dow -data 0x0aaa0000out128. txt, 点击 resu me 键 , 并注意终端 中的输出结果 , 如图 4所示 。多次运行 , 对比如图 5所示 , 给出具体分析内容 与结论 。目前 , 市场上主流的指纹对比速度为 1. 5S/枚 左右 。 如深圳千里马出品的指纹考勤门禁机 , 中科 48 2009年 朱礼波等 :嵌入式 PPC 平台指纹识别算法优化及实现院的嵌入式指纹自动识别模块 。通过对比可以发 现 , 经过软件算法级加速以及具体实现的加速 , 指纹 检测速度已经达到了与市场上同一数量级。 图4 最终板上运行结果 图 5 运行结果

20、对比5 结 束 语上述比较详细 、 系统地阐述了如何在嵌入式中 实现指纹识别系统 。 从算法的分析 、 硬件平台搭建 、 算法级优化到算法优化实现 。 软件方面通过浮点定 点化 、 去除多余步骤 、 数学函数重新编写来加快程序 运行的速度 ; 硬件中数据读取方面采用加入 DMA 模块 , 而在数据处理方面可以考虑采用一个流水线 型 16×16位乘法器 , 一个 32×8位乘法器和一个流 水线型 32位除法器 , 以提高系统工作效率 。 指纹识 别系统的应用非常广泛 , 几乎所有对安全性有要求 的场合都可以用到 , 具有广阔的应用前景 。参考文献 :1 He, J ie I

21、EEE, L iang L i,and . Analysis of Lo 2rehensive f Finger p rintMatc 2I ons on system s, man, and cyber 2B:cybernetics, 2007, 37(5 :1204-1211. 2 戴平阳 . 指纹识别技术研究进展 D.厦门 :厦门大学 ,2002. 3 卢朝阳 , 张岗山 , 刘琳 . 指纹识别系统性能评价方法D.西安 :西安电子科技大学 , 2002. 4 罗希平 , 田捷 . 自动指纹识别中的图像增强和细节匹配算法 J .软件学报 , 2002, 13(5 :946-956. 5 刘

22、旭 , 田捷 . 自动指纹识别算法在嵌入式系统上的实现 J .计算机工程与应用 , 2002, 38(21 :120-122.(上接第 81页 10 Dom ingos P . Pr os pects and challenges f or multi -rela 2ti onal data m ining J .AC M SI GK DD Exp l orati ons Ne wsletter archive vol . 5, Issue 1. Ne w York:AC M Press, 2003:80-83.11 Z HU M iao -liang, Q I U Yu . A Survey

23、 of Mobile AgentSYS TE M J .Journal of Computer Research and Devel opment, 2001, 38(1 :15-25.12 H B l ockeel, L De Raedt . T op -down inducti on of firstorder l ogical decisi on trees J .A rtificial I ntelligence, 1998, 101(1-2 :285-297.13 L De Raedt, H B l ockeel, L Dehas pe,W Van Laer . ThreeCompa

24、ni ons f or Data M ining in First O rder LogicJ .I n 4, 2001. :105-139.14 S Kra mer . Structural regressi on treesC .I n Pr oceedingsof the Thirteenth Nati onal Conference on A rtificial I ntel 2ligence, pages 812-819. M I T Press, Ca mbridge, MA, 1996.15 S Kramer, G W id mer . I nducing Classificat

25、i on andRegressi on Trees in First O rder Logic J .I n 4, 2001:140-159.16 J Quinlan . C4. 5:Pr ogram s f or M achine Learning M.Morgan Kauf mann, San Francisco, CA, 1993.17 张伟 , 杨炳儒 , 宋威 . 多关系数据挖掘研究综述 J .计算机工程与应用 , 2006.18 J Knobbe, A Siebes, Van derW allen, D. M. G . Multi -relati onal decisi on tr

26、ee inducti on C .I n Pr oceedings ofthe 3rdEur opean Conference on Princi p les and Practiceof Knowledge D iscovery in Databases, PK DD 99, 1999.19 Fayyad U M , Irani K B. On the handling of continuous -valued attributes in decisi on tree generati onJ .Machine Learning, vol . 8, 1992.20 Quinlan J R. I m p r oved U se of Continuous A ttributes inC4. 5J .Journal of A rtificial I ntelligence Research, vol .