基于超球覆盖仿生模式识别的指纹点名系统

李 丽，殷 业，崔晓静

(上海师范大学信息与机电工程学院，上海200234)

0 引言

仿生模式识别是基于“认识”事物特征的一种识别算法［1］，最先由中科院院士王守觉在2002年提出［2］，在仿生模式识别中，任何事物映射到n维特征空间的投影视为集合Q［3-4］，若某一待识别物体特征在n维特征空间中的投影在Q中，则记为物体匹配成功，否则即为失败．文中基于超球串的仿生模式识别算法，就是根据投影在n维特征空间中的特征值集合Q，作一个超球串即由n个超球组成，使得Q中所有的值均在超球串内［5］．该算法由于只需要找出圆心半径，故算法简单;又利用大小超球串覆盖，覆盖准确，因此该算法速度快、识别率高，适用于多种应用场合的目标特征模式识别．

为了加强学校对学生的课堂管理，很多高校都制定了相应的考勤制度［5-6］．考勤是为了如实记录学生的实际出勤情况，方便教学管理［7］．学校考勤方式，由早前的人工签到、单一键盘输入、接触卡式考勤系统到感应卡式考勤系统［8］，这些考勤系统由于种种自身的弊端，而渐渐地被生物识别考勤所取代．利用指纹的唯一性、难以伪造性的特点，可以研究出各种指纹考勤系统．然而，指纹考勤的速度和准确率仍然是指纹考勤的关键，在学校考勤管理中，代签、冒名签到、一堂课多次签到的情况却时有出现．

本文作者论述了指纹的识别算法，归纳总结了前人的研究成果．现在主流识别算法一般为细节点、滤波器组和小波变换的识别算法．而考虑到细节点算法的特征描述简单、模板占用内存小的特点，故采用细节点识别算法．目前在指纹识别研究领域里面，部分使用了遗传算法指纹细节特征匹配、基于三角形全等的指纹细节特征匹配等方法，上述方法存在着计算量大等缺陷．

基于上述背景，在嵌入式系统上，设计了一种基于超球串覆盖的仿生模式识别的指纹考勤系统，通过对班级的选择，选择签到是继续签到还是重新签到，防止该同学是否一次课堂多次签到，代签到和冒名签到，在保证指纹考勤速度的前提下，提高了识别的准确度．

1 基于超球串的仿生模式识别算法

在基于超球串的仿生模式识别算法中，训练模板时，将样本特征聚类，关键求得超球串的半径和圆心．

(1)在二维空间中，设 XOY 中有 N 个样本点(x1，y1)、(x2，y2)、…、(xn，yn)，超圆串即为 n个圆组成，选取n=3，也就是说，该超圆串由3个圆心、半径均不同的圆(记为圆A，圆B，圆C)组合而成．

第一步，曲线拟合．

将样本点用LSM(Least square method)法进行拟合，采用一次线性拟合L:y=kx+d，其中k、d为待定系数．

其中ei为(xi，yi)到拟合点(xi，kxi+d)的误差．根据最小均方误差准则，有

为使E(k，d)最小，由极值原理可知，此时

解此联立方程组得

第二步，求圆A的圆心．

设直线L上存在一动点P(x0，kx0+d)，过点P作一直线L0，使得L0⊥L．记使直线L可以过集合Q内样本点的两个临界 P 位置为 P1(xup，yup)，P2(xdown，ydown)，令 yup＞ ydown，此时对应的直线为 L1，L2，则圆A圆心坐标

第三步，求圆A的半径．

找出Q中离y=kx+d最大距离的点PM(xdA，ydA)，此时

以A为圆心，为半径画圆，其中

圆A为(x-xA)2+(y-yA)2=R2A．

第四步，求出圆B的圆心(xB，yB)和半径RB．

过PM点作平行于L的直线L3，及L3对称于L的直线L4，L3、L4交于圆A点Pu1(xu1，yu1)、Pu2(xu2，yu2)、Pd1(xd1，yd1)、Pd2(xd2，yd2)，其中点 Pu1即为点 PM，如图 1 所示，连接 Pu1、Pu2的直线 L5交 L 于点Pu(xu，yu)，设:

圆B的圆心坐标为

同理半径RA的求法，以B为圆心，r为半径，求得覆盖L1、L3、L4和L5所围区域内的样本点大于99%的最小半径r，记为RB，则RB为圆B半径．则圆B为(x-xB)2+(y-yB)2=R2B．

第五步，求圆C的圆心及半径．

参照圆B半径圆心的求法，得到圆C圆心及半径RC，则圆C为(x-xC)2+(y-yC)2=R2C．

使超圆串中，样本覆盖率大于99．9%，图2为基于超球仿生模式识别方法划分两种类型的样本的情况，其中不同圆串内的点代表不同类型的样品．

图1 二维平面内超圆串示意图

图2 二维特征空间

在二维平面中，若(x-xA)2+(y-yA)2≤R2A或(x-xB)2+(y-yB)2≤R2B或(x-xC)2+(y-yC)2≤R2C，则匹配成功［9］．

(2)在三维空间中，求得一个球串，该球串由3个不同圆心不同半径的球组合而成，关键在于分别求得 3 个球的圆心(xA，yA，zA)、(xB，yB，zB)、(xC，yC，zC)及半径 RA、RB、RC．

参照二维空间中的拟合方法，设一直线L:Z=m1x+m2y+m3，E=Σmi=1(zi-m1xi-m2yi-m3)2，令为使E最小，根据极值定理，使

求出m1、m2、m3，则该直线的法向量为L=(m1，m2，-1)，滑动该法平面，记使直线L可以过集合Q内样本点的两个临界 P 位置为 P1(xup，yup，zup)和 P2(xdown，ydown，zdown)，令 zup＞ zdown，则圆 A 圆心坐标为(xB，，半径方法如(1)中第三步;

则圆 A 为 ΦA(x，y，z)= (x-xA)2+(y-yA)2+(z-zA)2=R2A，参照(1)中第四步;

圆 B 为 ΦB(x，y，z)= (x-xB)2+(y-yB)2+(z-zB)2=R2B，参照(1)中第五步;

圆 C 为 ΦC(x，y，z)= (x-xB)2+(y-yB)2+(z-zB)2=R2C．

图3为三维空间内，基于超球仿生模式识别方法划分两种类型的样本的情况，其中不同圆串内的点代表不同类型的样品．则在三维空间中若 ΦA(x，y，z)≤R2A或 ΦB(x，y，z)≤R2B或 ΦC(x，y，z)≤R2C，则匹配成功．

图3 三维特征空间划分

(3)在n维空间中，求得超球串，该超球串由3个不同圆心半径的超球组成，观察分析式(1)和(2)，可写出n维超椭球的方程:

圆 A 为 ΦA(x1，x2，…，xn)=(x1-x1A)2+(x2-x2A)2+… +(xn-xnA)2=R2A;

圆 B 为 ΦB(x1，x2，…，xn)=(x1-x1B)2+(x2-x2B)2+… +(xn-xnB)2=R2B;

圆 C 为 ΦC(x1，x2，…，xn)=(x1-x1C)2+(x2-x2C)2+… +(xn-xnC)2=R2C．

则在 n 维空间中若 ΦA(x1，x2，…，xn)≤R2A或 ΦB(x1，x2，…，xn)≤R2B或 ΦC(x1，x2，…，xn)≤R2C，则匹配成功．

2 算法的系统软硬件实现

2.1 系统软件实现

指纹识别的过程分为训练部分和识别部分，图4即为训练部分，图5为识别部分．

图4 训练部分

图5 识别部分

在训练过程中，采集N个模板指纹后，进行图像预处理，对每个样本均提取n个特征参数，然后将n维空间中的N各样本点聚类，在n维空间中求出超球串的圆心和半径，从而得到判别公式．

在识别过程中，采集待识别指纹后，进行图像预处理，对待识别指纹图像提取n个特征参数，然后这些特征参数与模板参数进行比较，判断待识别特征参数是否满足模板判别公式，若满足任一判别公式，则匹配成功，即与该模板指纹为同一指纹，若不满足，则匹配失败．

将两枚指纹打开进行对比，如图6所示，点击“Match”进行匹配对比，算法对比结论为“Same Fingerprint!”，此时两枚指纹匹配．利用C++编写指纹识别的界面，如图7所示，通过指纹采集仪采集到指纹，与模板库中的指纹进行1∶N对比，得到匹配结果．

图6 两指纹对比界面

图7 指纹识别界面

2.2 系统硬件实现

根据功能要求，本设计在STM32系统实验板上连接OLED液晶显示模块和指纹传感器，构建指纹识别的硬件平台［10］，其系统结构［11］如图8 所示．

图8 指纹点名系统物理结构图

工作流程为:STM32在系统上电以后，各模块进行初始化，根据自身需求，待进入系统后，通过按键选择相应的功能，指纹识别结果用OLED显示，主控制器采用 JTAG接口连接J-link仿真器进行系统程序的仿真和调试．

在STM32上实现的指纹点名器如图9所示，系统各部分如图10(a)，10(b)，10(c)，10(d)，10(e)所示

图9 硬件实物图

图10 指纹点名系统平面图

3 实验结果及分析

为了验证算法的准确率CR、拒识率FRR、误识率FAR和识别速度，采集周围200枚指纹作为指纹库，每个指纹采集3次，随机选取50枚指纹共进行49×50=2450次匹配测试．

从表1可以看出，提出的仿生模式识别算法与参考文献［5，12，13］中所用的指纹识别算法相比，FAR及FRR更低，CR更高．

表1 指纹识别算法比对

实验使用频率为72 MHZ的STM32F103ZET6主建的平台上进行测试实指纹平均识别时间为1．5 s，完全可满足实时嵌入式系统的要求．

4 结论

本文作者给出了基于超球串覆盖的仿生模式识别算法的理论和具体实现步骤，并将算法应用于指纹图像匹配，在STM32嵌入式硬件系统上实现了算法．通过实验，表明该算法在用于指纹图像匹配时准确率更高、匹配速度更快．新算法概念清晰，具体实现方便，能有效提高运算速度和识别率，可推广应用于类似的其他应用领域．同时在嵌入式系统中实现了许多指纹识别、匹配和管理的新功能，有效地避免了课堂点名中的一些传统弊端，为未来课堂教学电子化管理提供了必要的手段．

［1］WANG SJ，CHEN X．Biomimetic(topological)pattern recognition-a new model of pattern recognition theory and its application:Neural Networks 2003 Proceedings of the International Joint Conference on［C］．Portland:IEEE，2003．

［2］JUN-YING Z，JUN-YING G，YI-KUI Z．A novel partially occluded face recognition method based on biomimetic pattern recognition:Wavelet Analysis and Pattern Recognition(ICWAPR)2012 International Conference on［C］．Xian:IEEE，2012．

［3］CAO W M，FENG H．Multispectral Image Recognition Research Based on Biomimetic Pattern Recognition:Electronic Commerce and Security 2009 ISECS ′09 Second International Symposium on［C］．Nanchang:IEEE，2009．

［4］CHEN J W．The key algorithm of automatic fingerprint identification system［D］．Shanxi:North University，2006．

［5］ZHANG M G．The design and implementation of fingerprint attendance management system based on VC［D］．Jilin:Jilin University，2013．

［6］CAI C W，FAN H J，LIU B Y．The design and application of access control system based on fingerprint recognition technology［J］．TV technology，2012，36(03):128-130．

［7］XU Y，YIN Y，WANG P．The study of speech recognition based on biomimetic pattern recognition［J］．Shanghai Mechanical and Electrical Engineering，2007，10(02):127-130．

［8］ZHANG T．The design and implementation of fingerprint attendance system for university classroom［D］．Chongqing，Chongqing University，2011．

［9］YANG L，The design of fingerprint identification system based on STM32［D］．Zhejiang:Hangzhou Electronic Science and Technology University，2012．

［10］BARRENECHA M，ALTUNA J，SAN-MIGUEL M．A Low-Cost FPGA-based Embedded Fingerprint Verification and Matching System［J］．Intelligent Solutions in Embedded Systems，2009，38:247-250．

［11］WANG Y P，LI Q，ZHANG L．Design of embedded fingerprint identification system based on DSP:Anti-Counterfeiting Security and Identification(ASID)2011 IEEE International Conference on［C］．Xiamen:IEEE，2011．

［12］WU G X．Research on several key algorithm of automatic fingerprint identification［D］．Changsha:Central South University，2007．

［13］GUO X X．Research on Key Technology of Automatic Fingerprint Identification System［D］．Changsha:Central South University，2009．