武言哲，謝吉華,，徐芳

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

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

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

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

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

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

引 言

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

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

1 硬件組成

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

圖1 硬件組成框圖

1.1 主控芯片

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

圖2 處理器功能框圖

1.2 指紋傳感器

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

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

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

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

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

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

功能：申請(qǐng)開(kāi)辟一個(gè)內(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)申請(qǐng)字節(jié)空間。

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

功能：在已申請(qǐng)的內(nèi)存池中，釋放從固定物理地址開(kāi)始的一段固定長(zhǎng)度的字節(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)

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

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

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

3 指紋算法的改進(jìn)

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

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

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

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

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

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

圖4 梯度圖和方向圖

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

3.2 指紋圖像處理算法

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

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

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

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

二值化基本思想是，計(jì)算切向灰度與法向灰度，如果切向灰度大于法向灰度，判斷為黑點(diǎn)，如若相反則判斷為白點(diǎn)。因?yàn)榭紤]到誤差的影響，所以在實(shí)際計(jì)算過(guò)程中采用了對(duì)每一個(gè)像素點(diǎn)添加相應(yīng)加權(quán)值的方法。這樣做降低了由二值化產(chǎn)生的噪聲點(diǎn)所帶來(lái)的誤差。筆者所設(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)

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

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

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

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

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

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

3.3 指紋匹配算法

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

typedefstructtagMinutiae{

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

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

sint32Direction; //方向

sint32Triangle[3]; //特征點(diǎn)為等邊三角形三個(gè)頂點(diǎn)

sint32Type; //類型

}MINUTIA, *MINUTIAPTR;

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

typedefstructtagMatchResult{

sint32Similarity; //相似度

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

sint32TransX; //水平偏移總量

sint32TransY; //垂直偏移總量

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

}MATCHRESULT, *PMATCHRESULT;

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

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

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

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

實(shí)驗(yàn)樣本的選取與測(cè)試方案的設(shè)計(jì)如下：

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

實(shí)驗(yàn)樣本2如下：

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

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

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

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

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

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

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

結(jié) 語(yǔ)

[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] 劉國(guó)柱.基于ARM9的家庭智能安防系統(tǒng)研究[D].濟(jì)南:山東大學(xué),2011.

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

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

武言哲(碩士研究生)，主要研究方向?yàn)橄到y(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)