基于超球覆蓋仿生模式識別的指紋點名系統(tǒng)

李 麗，殷 業(yè)，崔曉靜

(上海師范大學(xué)信息與機電工程學(xué)院，上海200234)

0 引言

仿生模式識別是基于“認(rèn)識”事物特征的一種識別算法［1］，最先由中科院院士王守覺在2002年提出［2］，在仿生模式識別中，任何事物映射到n維特征空間的投影視為集合Q［3-4］，若某一待識別物體特征在n維特征空間中的投影在Q中，則記為物體匹配成功，否則即為失敗．文中基于超球串的仿生模式識別算法，就是根據(jù)投影在n維特征空間中的特征值集合Q，作一個超球串即由n個超球組成，使得Q中所有的值均在超球串內(nèi)［5］．該算法由于只需要找出圓心半徑，故算法簡單;又利用大小超球串覆蓋，覆蓋準(zhǔn)確，因此該算法速度快、識別率高，適用于多種應(yīng)用場合的目標(biāo)特征模式識別．

為了加強學(xué)校對學(xué)生的課堂管理，很多高校都制定了相應(yīng)的考勤制度［5-6］．考勤是為了如實記錄學(xué)生的實際出勤情況，方便教學(xué)管理［7］．學(xué)校考勤方式，由早前的人工簽到、單一鍵盤輸入、接觸卡式考勤系統(tǒng)到感應(yīng)卡式考勤系統(tǒng)［8］，這些考勤系統(tǒng)由于種種自身的弊端，而漸漸地被生物識別考勤所取代．利用指紋的唯一性、難以偽造性的特點，可以研究出各種指紋考勤系統(tǒng)．然而，指紋考勤的速度和準(zhǔn)確率仍然是指紋考勤的關(guān)鍵，在學(xué)?？记诠芾碇校?、冒名簽到、一堂課多次簽到的情況卻時有出現(xiàn)．

本文作者論述了指紋的識別算法，歸納總結(jié)了前人的研究成果．現(xiàn)在主流識別算法一般為細(xì)節(jié)點、濾波器組和小波變換的識別算法．而考慮到細(xì)節(jié)點算法的特征描述簡單、模板占用內(nèi)存小的特點，故采用細(xì)節(jié)點識別算法．目前在指紋識別研究領(lǐng)域里面，部分使用了遺傳算法指紋細(xì)節(jié)特征匹配、基于三角形全等的指紋細(xì)節(jié)特征匹配等方法，上述方法存在著計算量大等缺陷．

基于上述背景，在嵌入式系統(tǒng)上，設(shè)計了一種基于超球串覆蓋的仿生模式識別的指紋考勤系統(tǒng)，通過對班級的選擇，選擇簽到是繼續(xù)簽到還是重新簽到，防止該同學(xué)是否一次課堂多次簽到，代簽到和冒名簽到，在保證指紋考勤速度的前提下，提高了識別的準(zhǔn)確度．

1 基于超球串的仿生模式識別算法

在基于超球串的仿生模式識別算法中，訓(xùn)練模板時，將樣本特征聚類，關(guān)鍵求得超球串的半徑和圓心．

(1)在二維空間中，設(shè) XOY 中有 N 個樣本點(x1，y1)、(x2，y2)、…、(xn，yn)，超圓串即為 n個圓組成，選取n=3，也就是說，該超圓串由3個圓心、半徑均不同的圓(記為圓A，圓B，圓C)組合而成．

第一步，曲線擬合．

將樣本點用LSM(Least square method)法進(jìn)行擬合，采用一次線性擬合L:y=kx+d，其中k、d為待定系數(shù)．

其中ei為(xi，yi)到擬合點(xi，kxi+d)的誤差．根據(jù)最小均方誤差準(zhǔn)則，有

為使E(k，d)最小，由極值原理可知，此時

解此聯(lián)立方程組得

第二步，求圓A的圓心．

設(shè)直線L上存在一動點P(x0，kx0+d)，過點P作一直線L0，使得L0⊥L．記使直線L可以過集合Q內(nèi)樣本點的兩個臨界 P 位置為 P1(xup，yup)，P2(xdown，ydown)，令 yup＞ ydown，此時對應(yīng)的直線為 L1，L2，則圓A圓心坐標(biāo)

第三步，求圓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)，設(shè):

圓B的圓心坐標(biāo)為

同理半徑RA的求法，以B為圓心，r為半徑，求得覆蓋L1、L3、L4和L5所圍區(qū)域內(nèi)的樣本點大于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為基于超球仿生模式識別方法劃分兩種類型的樣本的情況，其中不同圓串內(nèi)的點代表不同類型的樣品．

圖1 二維平面內(nèi)超圓串示意圖

圖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個不同圓心不同半徑的球組合而成，關(guān)鍵在于分別求得 3 個球的圓心(xA，yA，zA)、(xB，yB，zB)、(xC，yC，zC)及半徑 RA、RB、RC．

參照二維空間中的擬合方法，設(shè)一直線L:Z=m1x+m2y+m3，E=Σmi=1(zi-m1xi-m2yi-m3)2，令為使E最小，根據(jù)極值定理，使

求出m1、m2、m3，則該直線的法向量為L=(m1，m2，-1)，滑動該法平面，記使直線L可以過集合Q內(nèi)樣本點的兩個臨界 P 位置為 P1(xup，yup，zup)和 P2(xdown，ydown，zdown)，令 zup＞ zdown，則圓 A 圓心坐標(biāo)為(xB，，半徑方法如(1)中第三步;

則圓 A 為 ΦA(chǔ)(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為三維空間內(nèi)，基于超球仿生模式識別方法劃分兩種類型的樣本的情況，其中不同圓串內(nèi)的點代表不同類型的樣品．則在三維空間中若 ΦA(chǔ)(x，y，z)≤R2A或 ΦB(x，y，z)≤R2B或 ΦC(x，y，z)≤R2C，則匹配成功．

圖3 三維特征空間劃分

(3)在n維空間中，求得超球串，該超球串由3個不同圓心半徑的超球組成，觀察分析式(1)和(2)，可寫出n維超橢球的方程:

圓 A 為 ΦA(chǔ)(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(chǔ)(x1，x2，…，xn)≤R2A或 ΦB(x1，x2，…，xn)≤R2B或 ΦC(x1，x2，…，xn)≤R2C，則匹配成功．

2 算法的系統(tǒng)軟硬件實現(xiàn)

2.1 系統(tǒng)軟件實現(xiàn)

指紋識別的過程分為訓(xùn)練部分和識別部分，圖4即為訓(xùn)練部分，圖5為識別部分．

圖4 訓(xùn)練部分

圖5 識別部分

在訓(xùn)練過程中，采集N個模板指紋后，進(jìn)行圖像預(yù)處理，對每個樣本均提取n個特征參數(shù)，然后將n維空間中的N各樣本點聚類，在n維空間中求出超球串的圓心和半徑，從而得到判別公式．

在識別過程中，采集待識別指紋后，進(jìn)行圖像預(yù)處理，對待識別指紋圖像提取n個特征參數(shù)，然后這些特征參數(shù)與模板參數(shù)進(jìn)行比較，判斷待識別特征參數(shù)是否滿足模板判別公式，若滿足任一判別公式，則匹配成功，即與該模板指紋為同一指紋，若不滿足，則匹配失?。?/p>

將兩枚指紋打開進(jìn)行對比，如圖6所示，點擊“Match”進(jìn)行匹配對比，算法對比結(jié)論為“Same Fingerprint!”，此時兩枚指紋匹配．利用C++編寫指紋識別的界面，如圖7所示，通過指紋采集儀采集到指紋，與模板庫中的指紋進(jìn)行1∶N對比，得到匹配結(jié)果．

圖6 兩指紋對比界面

圖7 指紋識別界面

2.2 系統(tǒng)硬件實現(xiàn)

根據(jù)功能要求，本設(shè)計在STM32系統(tǒng)實驗板上連接OLED液晶顯示模塊和指紋傳感器，構(gòu)建指紋識別的硬件平臺［10］，其系統(tǒng)結(jié)構(gòu)［11］如圖8 所示．

圖8 指紋點名系統(tǒng)物理結(jié)構(gòu)圖

工作流程為:STM32在系統(tǒng)上電以后，各模塊進(jìn)行初始化，根據(jù)自身需求，待進(jìn)入系統(tǒng)后，通過按鍵選擇相應(yīng)的功能，指紋識別結(jié)果用OLED顯示，主控制器采用 JTAG接口連接J-link仿真器進(jìn)行系統(tǒng)程序的仿真和調(diào)試．

在STM32上實現(xiàn)的指紋點名器如圖9所示，系統(tǒng)各部分如圖10(a)，10(b)，10(c)，10(d)，10(e)所示

圖9 硬件實物圖

圖10 指紋點名系統(tǒng)平面圖

3 實驗結(jié)果及分析

為了驗證算法的準(zhǔn)確率CR、拒識率FRR、誤識率FAR和識別速度，采集周圍200枚指紋作為指紋庫，每個指紋采集3次，隨機選取50枚指紋共進(jìn)行49×50=2450次匹配測試．

從表1可以看出，提出的仿生模式識別算法與參考文獻(xiàn)［5，12，13］中所用的指紋識別算法相比，F(xiàn)AR及FRR更低，CR更高．

表1 指紋識別算法比對

實驗使用頻率為72 MHZ的STM32F103ZET6主建的平臺上進(jìn)行測試實指紋平均識別時間為1．5 s，完全可滿足實時嵌入式系統(tǒng)的要求．

4 結(jié)論

本文作者給出了基于超球串覆蓋的仿生模式識別算法的理論和具體實現(xiàn)步驟，并將算法應(yīng)用于指紋圖像匹配，在STM32嵌入式硬件系統(tǒng)上實現(xiàn)了算法．通過實驗，表明該算法在用于指紋圖像匹配時準(zhǔn)確率更高、匹配速度更快．新算法概念清晰，具體實現(xiàn)方便，能有效提高運算速度和識別率，可推廣應(yīng)用于類似的其他應(yīng)用領(lǐng)域．同時在嵌入式系統(tǒng)中實現(xiàn)了許多指紋識別、匹配和管理的新功能，有效地避免了課堂點名中的一些傳統(tǒng)弊端，為未來課堂教學(xué)電子化管理提供了必要的手段．

［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，F(xiàn)ENG 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，F(xiàn)AN 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．