武言哲，謝吉華,，徐芳

(1.東南大學(xué)，南京 210096；2.無錫市信息安全工程技術(shù)研究中心)

LC698S片上指紋算法的優(yōu)化與應(yīng)用

武言哲1，謝吉華1,2，徐芳2

(1.東南大學(xué)，南京 210096；2.無錫市信息安全工程技術(shù)研究中心)

主要介紹在無MMU支持的硬件環(huán)境中，為了解決程序運行的內(nèi)存碎片的問題，利用自定義的內(nèi)存池(Memory Pool)為指紋程序分配內(nèi)存空間，通過片內(nèi)RAM實現(xiàn)指紋識別功能的方案。本文對經(jīng)典的預(yù)處理算法以及以特征點的拓撲結(jié)構(gòu)作為特征值的識別算法作了進一步的優(yōu)化。除此之外，本文提出分辨率動態(tài)分布算法，這種算法降低了原圖像分辨率，改變了圖像大小，節(jié)省了片內(nèi)RAM空間，加快了圖像處理速度，使得FAR與FRR達到識別要求，同時縮短指紋識別時間。

LC698S；分辨率動態(tài)分布；內(nèi)存池；指紋識別

引 言

在基于點模式的指紋識別過程中，對處理器浮點運算要求較高的是指紋圖像分割和增強，定點運算較多的是二值化與細化。所以如果在沒有專用指紋處理模組的環(huán)境中進行開發(fā)，主控芯片需要具備一定的浮點運算能力。與此同時在軟件上，開發(fā)人員需要提高內(nèi)存空間的利用率，對指紋識別算法作出優(yōu)化。

在不同的應(yīng)用場景中，對嵌入式指紋識別的硬件與軟件的有著不同要求。例如對于指紋鎖與門禁的應(yīng)用場景，算法的設(shè)計要盡可能降低識假率(FAR)，而對于員工考勤機，則盡可能降低拒真率(FRR)。由于本文的應(yīng)用場景是為PKI體系中USB Key的使用者提供私人信息的保密性，所以整個指紋識別算法的改進需要降低識假率。本文選用的處理器LC698S是由華芯研發(fā)的國內(nèi)稅控專用SoC安全芯片，具備一定的浮點運算能力，內(nèi)嵌了外設(shè)模塊，可作外擴功能的開發(fā)。筆者針對這種國產(chǎn)芯片，利用片內(nèi)RAM空間，進行指紋識別功能的開發(fā)。

1 硬件組成

硬件整體架構(gòu)主要包含主控芯片LC698S以及指紋傳感器JP2050,其中，傳感器與芯片的通信采用的是SPI協(xié)議。為了縮短指紋圖像認證時間以及防止指紋特征信息的泄露，筆者完全利用片內(nèi)RAM作為指紋圖像處理與識別運算的空間，另外NAND Flash中存放的是指紋識別源碼與指紋特征信息。整體硬件組成圖如圖1所示。

圖1 硬件組成框圖

1.1 主控芯片

LC698S為SPARC V8架構(gòu)、32位 RISC嵌入式微處理器，內(nèi)嵌32位整型數(shù)處理模塊， 32位和64位的浮點數(shù)處理模塊，具有較強的運算能力。除此之外，內(nèi)嵌了大量的外設(shè)，其中包括64 KB片內(nèi)RAM空間，智能卡控制器與磁卡控制器等。該芯片處理指令速度為160 MIPS，雙精度浮點運算速度為40 MFlops，主頻為166 MHz。處理器功能框圖如圖2所示。

圖2 處理器功能框圖

1.2 指紋傳感器

JP2050S按壓式指紋傳感器是CMOS型指紋傳感器，分辨率為508 dpi，指紋采集區(qū)像素點陣為192×192 pixels，通信協(xié)議為SPI，輸出256級灰度圖像，單像素存儲空間為8位。所以每幅采集圖像大小(實際位圖數(shù)據(jù))為36 KB。

由于主控芯片片內(nèi)內(nèi)存為64 KB，每個圖像大小至少為36 KB，為了減少指紋識別程序在內(nèi)存中所占用的空間，筆者在算法層面對指紋圖像的像素數(shù)量作了進一步的縮減，具體內(nèi)容在軟件解決方案中會有所體現(xiàn)。

2 軟件開發(fā)環(huán)境

開發(fā)工具選擇SPARC交叉開發(fā)工具鏈，主要包括Sparc-elf-gcc、Sparc-elf-ld、Sparc-elf-objdump等，使用主控芯片內(nèi)部的DSU和DCL串行通信模塊進行在線調(diào)試。DCL對外遵循RS232標(biāo)準，在DSU調(diào)試模式下，通過TAP接口動態(tài)監(jiān)視芯片片內(nèi)寄存器與存儲器等。

為了在應(yīng)用程序運行時分配連續(xù)的地址空間，可以將內(nèi)存池的設(shè)計引入到指紋識別程序中，使用已經(jīng)封裝好的接口申請內(nèi)存空間。主要函數(shù)接口如下：

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

功能：申請開辟一個內(nèi)存池。

② int mpool_close(mpool_t *mp_p)

功能：釋放已經(jīng)分配的內(nèi)存池。

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

功能：在內(nèi)存池內(nèi)申請字節(jié)空間。

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

功能：在已申請的內(nèi)存池中，釋放從固定物理地址開始的一段固定長度的字節(jié)空間。

⑤ 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)

功能：返回一個已申請內(nèi)存池的統(tǒng)計信息。

筆者在μClinux系統(tǒng)上進行了內(nèi)存池源碼測試，起始地址為0x577d fa4a。本次測試的內(nèi)存池，主要目的是測試各個庫函數(shù)的功能。需要指出的是指紋識別功能的開發(fā)并不是基于μClinux操作系統(tǒng)而進行的，而是利用Sparc開發(fā)工具鏈，直接在芯片內(nèi)部進行。本次工作僅是測試內(nèi)存池功能函數(shù)，其目的是在Sparc開發(fā)環(huán)境中，為內(nèi)存池的成功應(yīng)用做準備。測試結(jié)果如圖3所示。

圖3 內(nèi)存池參數(shù)分配圖

3 指紋算法的改進

經(jīng)典松弛匹配算法是由Sanjay、Ranade與Rosenfeld等人設(shè)計與實現(xiàn)的，經(jīng)典Hough變換方法是由Stockman等人提出的，基于二維聚類的快速算法是由Shih-hsu、Chang 等人設(shè)計與實現(xiàn)的，三角匹配算法由Zsolt Miklos 等人提出。除此之外，還有工程師，如Xudong Jiang等人將指紋特征點的全局與局部拓撲結(jié)構(gòu)進行歸類，分步分段進行指紋匹配工作。

為了在提高識別速度的同時，減少圖像占用內(nèi)存的空間，筆者對指紋原圖像像素點的分布進行了動態(tài)規(guī)劃，使得原本為508 dpi圖像分辨率的分布是依據(jù)指紋圖像梯度場的分布而重新規(guī)劃的，整體上降低了指紋圖像像素數(shù)量，從而減少圖像大小，減少了識別程序所占用內(nèi)存空間，加快了處理圖像的速度。

3.1 分辨率動態(tài)分布算法

分辨率的動態(tài)分布要依據(jù)指紋紋線的疏密程度來劃分，衡量指紋紋線疏密程度的物理量為指紋紋線的梯度場。

具體梯度場的獲取是根據(jù)對每個像素灰度的大小f(x,y)求(x,y)的偏導(dǎo)數(shù)，然后取模值|T|可求得。由于后期方向濾波過程需要圖像方向場，這里圖像方向場也一并計算出來。方向場以右手定理垂直于梯度方向為基準，然后對參數(shù)θ的值進行正交分解。方向場的獲取利用Sobel算子去求(x,y)的偏導(dǎo)數(shù)，并將方向場的每一點像素與周圍像素聯(lián)系起來。Sobel算子表示如下：

梯度圖與方向圖的處理效果如圖4所示。

圖4 梯度圖和方向圖

對于指紋紋線比較緊密的區(qū)域，相應(yīng)的梯度圖像的灰度值偏高，視覺上所呈現(xiàn)出的結(jié)果是偏白色。所以在像素點采集步長上要偏小。反之，對于紋線較為稀疏的區(qū)域，相應(yīng)的梯度圖像灰度值偏低，視覺上所呈現(xiàn)出的結(jié)果是偏黑色。因為白色區(qū)域是保留指紋特征點信息較多的區(qū)域，所以進行分辨率劃分時，分辨率要高，像素取點的步長要短。反之，因為黑色區(qū)域保留的指紋特征點信息較少，分辨率要低，所以像素取點的步長要較長。根據(jù)梯度場圖像灰度值的分布，可以人為地給出像素采集步長。

3.2 指紋圖像處理算法

此部分主要論述的是對經(jīng)過分辨率重新分布的指紋圖像進行預(yù)處理的過程。

圖像分割算法就是利用合理梯度的模作為閾值，以此來分割前景與背景區(qū)，增強算法采用的是方向濾波方法，以及在脊線方向上采用空域濾波使得脊線變得連續(xù)，彌補脊線斷裂的不足。在法向上采用頻域濾波，將脊線之間的噪聲點去除，這樣做有利于后期的二值化處理。具體的空域濾波，筆者選擇的是平滑濾波法，頻域濾波采用的是非線性高通濾波。所謂平滑濾波就是將8鄰域平均像素值作為中心像素點的像素值。為了充分利用指紋脊線相間的特點，需要對脊線進行振蕩加強，法向濾波采用Gabor函數(shù)[6]。筆者將切向與法向運算進行了簡化，以減少主控芯片的運算時間與運算量，切法方向模板表示如下：

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

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

二值化基本思想是，計算切向灰度與法向灰度，如果切向灰度大于法向灰度，判斷為黑點，如若相反則判斷為白點。因為考慮到誤差的影響，所以在實際計算過程中采用了對每一個像素點添加相應(yīng)加權(quán)值的方法。這樣做降低了由二值化產(chǎn)生的噪聲點所帶來的誤差。筆者所設(shè)置加權(quán)值參數(shù)如下：

切向加權(quán)值：Hw[7]=(2,2,3,4,3,2,2)

法向加權(quán)值：Vw[7]=(1,1,1,1,1,1,1)

細化算法采用的是查表法，基本思想是判斷黑點的圖像邊緣特征，即周圍的8點必定表現(xiàn)一定的色彩順序。周圍的色彩順序共有256種，一一進行枚舉不現(xiàn)實，筆者參考了許多文獻總結(jié)出一張細化表，用一個字節(jié)來表示一種色彩順序。

端點與分叉點的提取算法采用經(jīng)典的8鄰域提取算法[7]，以Pk作為灰度值，具體數(shù)學(xué)表達式為

中心點的提取需要采用Poincare公式。為了便于計算機編程,同樣用方格法進行奇異點的提取，本文采用5×5與3×3方格法。在5×5方格內(nèi)，以(i,j)為中心，選取封閉曲線D1、D2、…、D12，方向為逆時針。該閉合曲線的Poincare值為：

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

3×3方格計算與5×5方格計算類似，在此不贅述。當(dāng)5×5方格與3×3方格計算的Poincare值相同時，候選點可以作為奇異點，以作為配準中心點。圖5為指紋預(yù)處理各個階段的效果圖。

圖5 指紋處理效果圖(從左至右依次為分割圖、二值化圖、細化和特征點提取圖)

3.3 指紋匹配算法

配準的原理是首先依據(jù)每個特征點周圍場的分布，尋找配準點作為兩幅圖像的參考點，然后計算出每個特征點之間的拓撲關(guān)系，為了便于在片外Flash空間存儲指紋特征信息，需要將拓撲關(guān)系進行壓縮編碼[8]。下面是指紋特征點拓撲結(jié)構(gòu)源碼：

typedefstructtagMinutiae{

sint32x; //橫坐標(biāo)

sint32y; //縱坐標(biāo)

sint32Direction; //方向

sint32Triangle[3]; //特征點為等邊三角形三個頂點

sint32Type; //類型

}MINUTIA, *MINUTIAPTR;

相似度結(jié)構(gòu)源碼如下:

typedefstructtagMatchResult{

sint32Similarity; //相似度

sint32Rotation; //旋轉(zhuǎn)偏移總量

sint32TransX; //水平偏移總量

sint32TransY; //垂直偏移總量

sint32MMCount(); //匹配特征點數(shù)

}MATCHRESULT, *PMATCHRESULT;

圖6所示的流程圖展現(xiàn)的是最終配準與匹配的過程。

圖6 指紋特征匹配模塊算法流程

4 算法實現(xiàn)與性能分析

此部分主要論述的是閾值的選定以及性能參數(shù)FAR和FRR的確定，測試用例選擇的是國際指紋識別大賽的指紋庫FVC2008。

實驗樣本的選取與測試方案的設(shè)計如下：

根據(jù)實驗樣本1，可計算出FRR，具體計算方法為FRR=失敗匹配次數(shù)/總的匹配次數(shù)。

實驗樣本2如下：

根據(jù)實驗樣本2，可計算出FAR，具體計算方法為FAR=成功匹配次數(shù)/總的匹配次數(shù)。

本文設(shè)定了MatchScore=1，2，…，12，總共12級閾值，在每級閾值下對實驗樣本1和實驗樣本2進行匹配實驗，實驗結(jié)果如圖7所示。

圖7 FAR和FRR測試結(jié)果圖

可以看出，閾值分數(shù)對于拒真率和識假率的影響是成反比的，在閾值分數(shù)為8的時候，兩項指標(biāo)均處于較低的水平，因此8為目標(biāo)取值。

最終筆者將指紋算法移植到片外Flash中，利用SPARC開發(fā)工具鏈對指紋傳感器所抓取的指紋位圖圖像文件進行讀取并在片內(nèi)進行了識別處理。為了便于優(yōu)化功能，在控制臺打印了指紋識別各個過程所占用CPU的時間。LC698S性能參數(shù)為160MIPs/40MFlops(doubleprecision)@166MHz。最終運行結(jié)果如圖8所示。

圖8 最終運行結(jié)果

從圖中可以清晰地看出，整個識別過程耗時低于300ms。本文對經(jīng)典指紋識別算法的改造，應(yīng)用到搭載LC698S芯片上的是成功可行的。

結(jié) 語

[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的家庭智能安防系統(tǒng)研究[D].濟南:山東大學(xué),2011.

[7] 張圓圓.指紋識別技術(shù)相關(guān)算法的研究[D].北京:北京郵電大學(xué),2012.

[8] 李汝才.基于ARM9的嵌入式指紋識別系統(tǒng)[D].哈爾濱:哈爾濱工程大學(xué),2013.

武言哲(碩士研究生)，主要研究方向為系統(tǒng)芯片與嵌入式系統(tǒng)應(yīng)用。

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)