趙錦明　錢磊　吳東

[摘要]指紋識(shí)別是生物識(shí)別技術(shù)中重要且廣泛使用的一種。當(dāng)前該領(lǐng)域研究的重點(diǎn)在如何更好地采集提取指紋特征以及指紋安全等方面，對(duì)于大規(guī)模指紋識(shí)別的研究較少。隨著電子商務(wù)、公安部門的大規(guī)模使用，需要進(jìn)行比對(duì)的指紋數(shù)據(jù)暴增。針對(duì)這一現(xiàn)狀，論文在基于細(xì)節(jié)特征點(diǎn)的這一類指紋識(shí)別算法基礎(chǔ)上，利用FPGA平臺(tái)對(duì)這類算法進(jìn)行加速，通過(guò)對(duì)算法的分析調(diào)整，在FPGA上設(shè)計(jì)實(shí)現(xiàn)了一種新的加速結(jié)構(gòu)，并采取了相應(yīng)的優(yōu)化策略。通過(guò)加速，單節(jié)點(diǎn)FPGA能達(dá)到每秒100萬(wàn)次指紋比對(duì)，相對(duì)于軟件性能提升了25倍，為后續(xù)新算法的大規(guī)模使用奠定了基礎(chǔ)。

[關(guān)鍵詞]生物識(shí)別；指紋識(shí)別；流水；乒乓操作；FPGA

[中圖分類號(hào)]TP3 [文獻(xiàn)標(biāo)識(shí)碼]A

1 引言

在信息化時(shí)代的今天，信息安全尤其重要，如何鑒別一個(gè)人的身份是其中一個(gè)至關(guān)重要的問題。傳統(tǒng)方式存在易丟失、容易被偽造等問題，利用生物識(shí)別技術(shù)進(jìn)行身份認(rèn)定，不僅安全、準(zhǔn)確，還便于管理，應(yīng)用前景廣闊。指紋具有終身不變性、唯一性和方便性，依靠指紋的生物識(shí)別技術(shù)被廣泛接受與認(rèn)可，相關(guān)應(yīng)用也較為廣泛。

指紋是指人的手指末端正面皮膚上凸凹不平產(chǎn)生的紋線。紋線的起點(diǎn)、終點(diǎn)、結(jié)合點(diǎn)和分叉點(diǎn)，稱為指紋的細(xì)節(jié)特征點(diǎn)（Minutiae）。指紋識(shí)別即指通過(guò)比較不同指紋的細(xì)節(jié)特征點(diǎn)來(lái)進(jìn)行身份鑒別。

目前指紋識(shí)別主要應(yīng)用在手機(jī)解鎖、門禁考勤等方面，需要進(jìn)行的比對(duì)計(jì)算量小，而隨著指紋識(shí)別應(yīng)用領(lǐng)域更加廣泛，如電子商務(wù)、公安部門等，指紋識(shí)別中的數(shù)據(jù)量暴增，識(shí)別過(guò)程中的計(jì)算量極大，采用傳統(tǒng)的方法需要大量時(shí)間，這在許多應(yīng)用場(chǎng)合是達(dá)不到要求的。已有的研究主要針對(duì)指紋識(shí)別采集階段圖像增強(qiáng)和特征提取，如文獻(xiàn)；指紋識(shí)別系統(tǒng)的全過(guò)程自動(dòng)化AFIS（Automated Fingerprint Identification System），如文獻(xiàn)；指紋識(shí)別算法的準(zhǔn)確率，如文獻(xiàn)等；與此同時(shí)，也有部分嘗試對(duì)指紋識(shí)別進(jìn)行加速的研究，文獻(xiàn)，但效果不夠理想。

本文在此背景下，針對(duì)如何快速進(jìn)行較大規(guī)模指紋比對(duì)這一問題，對(duì)常用的基于特征點(diǎn)的一類指紋識(shí)別算法進(jìn)行了分析，基于FPGA平臺(tái)，針對(duì)識(shí)別過(guò)程中計(jì)算量最密集的部分進(jìn)行重構(gòu)及算法調(diào)整，設(shè)計(jì)并實(shí)現(xiàn)了一種FPGA平臺(tái)上的加速結(jié)構(gòu)。并采用了一些方法進(jìn)行資源優(yōu)化和性能提升。加速效果明顯，采用該加速結(jié)構(gòu)FPGA單節(jié)點(diǎn)對(duì)原算法有25倍的加速效果。達(dá)到了每秒100萬(wàn)次指紋比對(duì)的性能：如果同時(shí)采用多節(jié)點(diǎn)FPGA并行，能達(dá)到更高的性能，能夠初步滿足大規(guī)模指紋識(shí)別的需要，并為后續(xù)同類型新算法的大規(guī)模應(yīng)用奠定了很好的基礎(chǔ)。

2 基于細(xì)節(jié)特征點(diǎn)的指紋識(shí)別算法

2.1 指紋識(shí)別簡(jiǎn)介

指紋識(shí)別是指通過(guò)比較不同指紋的細(xì)節(jié)特征點(diǎn)來(lái)進(jìn)行身份鑒別的過(guò)程，其整體流程如圖1所示。包括指紋庫(kù)的建立、待比對(duì)指紋采集、指紋處理及特征提取、指紋匹配等主要過(guò)程。

指紋識(shí)別算法主要用在指紋匹配階段，用于將新采集的指紋與數(shù)據(jù)庫(kù)中的指紋逐一進(jìn)行比對(duì)?；诩?xì)節(jié)特征點(diǎn)的指紋識(shí)別算法是一類典型的指紋識(shí)別算法，即指通過(guò)比較計(jì)算不同指紋的細(xì)節(jié)特征點(diǎn)的相似程度而進(jìn)行身份鑒別的方法。

2.2 基于細(xì)節(jié)特征點(diǎn)的指紋識(shí)別算法原理

基于細(xì)節(jié)特征點(diǎn)的算法是一類典型且使用較多的指紋識(shí)別算法，該算法中指紋匹配部分比對(duì)的流程如圖2所示。

將采集到的待匹配指紋EXP的細(xì)節(jié)特征點(diǎn)與數(shù)據(jù)庫(kù)中某個(gè)指紋DEMO的細(xì)節(jié)特征點(diǎn)數(shù)據(jù)作為輸入：先將EXP指紋特征點(diǎn)兩兩組合展開為特征向量，如圖3所示：并對(duì)展開的EXP指紋特征向量按照向量角排序存儲(chǔ)：然后將DEMO指紋根據(jù)其特征點(diǎn)兩兩展開生成特征向量，同時(shí)與已生成的EXP特征向量構(gòu)建特征向量對(duì)：再根據(jù)特征向量對(duì)計(jì)算出參數(shù)對(duì)EXP指紋進(jìn)行旋轉(zhuǎn)、平移操作，并刪除相似度較低的向量對(duì)；最后根據(jù)剩余的相似度較高特征向量對(duì)，計(jì)算出它們的全局相似度，并根據(jù)相似度判斷它們是否匹配。

各步驟具體如下：

EXP指紋展開是指根據(jù)EXP指紋的細(xì)節(jié)特征點(diǎn)數(shù)據(jù)，將特征點(diǎn)兩兩組合生成特征向量，如圖3所示，A1、A2是EXP指紋的兩個(gè)細(xì)節(jié)特征點(diǎn)：

EXP指紋特征向量排序是指根據(jù)前面生成的特征向量，按照其角度A1方向角和特征向量長(zhǎng)度對(duì)其進(jìn)行排序；DEMO指紋展開并構(gòu)建特征向量對(duì)是根據(jù)DEMO指紋特征點(diǎn)兩兩組合構(gòu)建特征向量，并同時(shí)根據(jù)已生成的有序EXP指紋特征向量初步查找可能相似的特征向量，構(gòu)造成特征向量對(duì)；EXP指紋旋轉(zhuǎn)、平移并刪減特征向量對(duì)是將EXP指紋按照比較結(jié)果進(jìn)行旋轉(zhuǎn)平移，并將處理后相似度較低的特征向量對(duì)刪除；計(jì)算全局相似度是指根據(jù)最后剩下的特征向量對(duì)，計(jì)算兩個(gè)指紋的全局相似程度：最后根據(jù)全局相似度判斷輸入的兩個(gè)指紋是否匹配，即完成了一次指紋比對(duì)：再取出指紋庫(kù)中另一DEMO指紋重復(fù)上述過(guò)程。

2.3 算法分析

該算法主要是基于遍歷的思想，整體上待匹配指紋與指紋庫(kù)中的指紋遍歷地進(jìn)行一一比較：在一對(duì)指紋比較過(guò)程中，通過(guò)細(xì)節(jié)特征點(diǎn)兩兩組合產(chǎn)生特征向量，然后在兩個(gè)指紋的特征向量之間遍歷地計(jì)算相似程度。整體過(guò)程計(jì)算量比較大，而且大多數(shù)都是重復(fù)的運(yùn)算過(guò)程，軟件平臺(tái)上需要消耗大量的處理器資源，但硬件平臺(tái)卻很適合處理這一類問題。

目前該類算法在軟件平臺(tái)上的實(shí)現(xiàn)性能受處理器資源和頻率限制，只能達(dá)到約每秒數(shù)萬(wàn)次指紋比對(duì)，遠(yuǎn)遠(yuǎn)無(wú)法達(dá)到大規(guī)模使用的要求。本文針對(duì)這一現(xiàn)狀，嘗試基于FPGA平臺(tái)對(duì)這類算法進(jìn)行加速。

3 基于FPGA的加速結(jié)構(gòu)設(shè)計(jì)

FPGA平臺(tái)具有許多軟件平臺(tái)無(wú)法比擬的優(yōu)勢(shì)，如較低的功耗、豐富的資源、天生的并行性等，因而采用FPGA平臺(tái)進(jìn)行加速設(shè)計(jì)是合適的。為了達(dá)到研究目標(biāo)，根據(jù)FPGA平臺(tái)的特點(diǎn)，對(duì)原算法進(jìn)行適當(dāng)調(diào)整，并設(shè)計(jì)一種相應(yīng)的加速結(jié)構(gòu)。

3.1 設(shè)計(jì)思想

通過(guò)對(duì)軟件算法的流程和原理研究發(fā)現(xiàn)，該算法中涉及到較大的計(jì)算量，特別是其中DEMO指紋展開并構(gòu)建特征向量對(duì)部分，不僅需要根據(jù)DEMO指紋細(xì)節(jié)特征點(diǎn)構(gòu)建特征向量，同時(shí)還要從上一步已經(jīng)生成的特征向量中查找相似度較高的特征向量構(gòu)造向量對(duì)，并計(jì)算相似度。這一過(guò)程是計(jì)算量最大、計(jì)算最密集的部分，也是整個(gè)算法中的瓶頸部分。因此為了對(duì)該類算法進(jìn)行加速，首先考慮的就是對(duì)這一部分進(jìn)行調(diào)整與加速。

根據(jù)直觀的想法，兩個(gè)指紋相似度越高，它們之間匹配的特征向量對(duì)數(shù)目也就越多。在這一想法的基礎(chǔ)上，本文對(duì)樣本指紋數(shù)據(jù)庫(kù)進(jìn)行了統(tǒng)計(jì)分析，結(jié)果如圖4所示。

從圖4可以看出，隨著閾值的增大，滿足匹配閾值的指紋比率急劇降低，而正確率降低較慢，所以設(shè)定一個(gè)閾值對(duì)指紋庫(kù)進(jìn)行預(yù)過(guò)濾是可行的，本文也就是基于這一思想進(jìn)行了加速結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)。

3.2 算法調(diào)整

為了使用FPGA平臺(tái)對(duì)整個(gè)算法進(jìn)行加速，本文對(duì)原算法的結(jié)構(gòu)進(jìn)行了適當(dāng)調(diào)整，算法整體采用預(yù)過(guò)濾之后精確比對(duì)的思想進(jìn)行加速。通過(guò)預(yù)過(guò)濾剔除指紋庫(kù)中大部分不符合的指紋，經(jīng)過(guò)分析發(fā)現(xiàn)在特定閾值下能剔除99%的指紋庫(kù)指紋，再對(duì)余下可能性較大的小部分指紋進(jìn)行精確比對(duì)，從而達(dá)到整體加速的效果；其中預(yù)過(guò)濾加速部分在FPGA上進(jìn)行，也是整個(gè)加速結(jié)構(gòu)的核心部分。

基于上述思想，為了便于硬件的加速結(jié)構(gòu)實(shí)現(xiàn)，本文適當(dāng)調(diào)整原算法結(jié)構(gòu)：將DEMO指紋展開并構(gòu)建特征向量對(duì)這一過(guò)程剝離開來(lái)，先產(chǎn)生DEMO指紋特征向量，再和待匹配的EXP指紋特征向量進(jìn)行逐一組合匹配計(jì)算。這樣調(diào)整的好處在：一方面可以將計(jì)算過(guò)程分成多個(gè)模塊，便于計(jì)算量的平衡；另一方面多模塊的結(jié)構(gòu)便于硬件環(huán)境下流水，從而加速整個(gè)計(jì)算過(guò)程。

3.3 結(jié)構(gòu)設(shè)計(jì)

在上述設(shè)計(jì)思想的指導(dǎo)下，本文調(diào)整算法結(jié)構(gòu)后初步設(shè)計(jì)的結(jié)構(gòu)如圖5所示。

4 加速結(jié)構(gòu)實(shí)現(xiàn)

4.1 模塊劃分

根據(jù)粗篩的想法，將原算法DEMO指紋展開并構(gòu)建特征向量對(duì)部分拆分為：demo_gen、pair_expand、pair_expand_all、pair_cal這四個(gè)子模塊，結(jié)構(gòu)如圖5所示。

拆分為多個(gè)子模塊一方面是為了均衡計(jì)算量，避免某個(gè)部分計(jì)算量過(guò)大，成為加速設(shè)計(jì)的瓶頸：另一方面是為了在FPGA中形成流水線，從而提高在FPGA中運(yùn)行的性能

各模塊的功能說(shuō)明如下：

demo_gen：將DEMO指紋特征點(diǎn)集中的特征點(diǎn)兩兩組合生成正向和反向的DEMO指紋特征向量（對(duì)應(yīng)生成的DEMO特征向量A1方向角的兩種情況），并將生成的DEMO特征向量相關(guān)數(shù)據(jù)（A1方向角，A2方向角，長(zhǎng)度Len）傳到下一模塊。

pair_expand：根據(jù)demo_gen模塊傳人的DEMO指紋特征向量數(shù)據(jù)。按照A1方向角允許誤差展開查找待匹配的EXP指紋特征向量，在EXP指紋特征向量角度地址映射表（A1_addr_map）中查找ID范圍（A1_addr_map中的角度映射值，對(duì)應(yīng)EXP指紋特征向量緩存表linebyA1中EXP特征向量位置），并將DEMO特征向量與待匹配的EXP特征向量ID范圍數(shù)據(jù)傳人下一模塊。

pair_expand_all：根據(jù)pair_expand模塊傳入的ID范圍展開待匹配的EXP特征向量，生成DEMO特征向量與具體的EXP特征向量對(duì)數(shù)據(jù)，并傳到下一模塊。

pair_cal：計(jì)算pair_expand_all模塊傳人的所有特征向量對(duì)數(shù)據(jù)是否匹配，并統(tǒng)計(jì)兩個(gè)指紋點(diǎn)集間局部相似度累加和，輸出結(jié)果供粗篩過(guò)濾使用。

同時(shí)，在整個(gè)結(jié)構(gòu)中增加到兩個(gè)比較重要的數(shù)據(jù)結(jié)構(gòu)。

EXP指紋特征向量緩存表（linebyA1）：存儲(chǔ)了一個(gè)EXP指紋的所有特征向量數(shù)據(jù)。并且按照A1方向角從小到大的順序排列，建立這樣一個(gè)表是為了根據(jù)A1方向角的值快速的查找到EXP指紋對(duì)應(yīng)的特征向量數(shù)據(jù)，節(jié)省查找時(shí)間，其中一條特征向量的數(shù)據(jù)結(jié)構(gòu)如表1所示。

EXP指紋特征向量角度地址映射表（A1_addr_map）：是根據(jù)表linebyA1中A1方向角從小到大統(tǒng)計(jì)的特征向量數(shù)目的累加和，其映射了方向角為A1的特征向量數(shù)據(jù)在linebyA1表中的起止地址，配合linebyA1表快速的定位所有方向角為A1的特征向量：A1_addr_map表的序號(hào)對(duì)應(yīng)方向角A1，每個(gè)數(shù)據(jù)表示該角度特征向量的數(shù)目。

4.2 優(yōu)化策略

進(jìn)行上述算法調(diào)整和結(jié)構(gòu)實(shí)現(xiàn)后，經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)加速效果并不明顯。為了提高加速的效果。除采用一些主要的優(yōu)化策略：計(jì)算過(guò)程多模塊化、模塊內(nèi)循環(huán)流水及模塊之間流水并行、采用新的數(shù)據(jù)結(jié)構(gòu)緩存避免重復(fù)計(jì)算等，還針對(duì)資源和結(jié)構(gòu)方面進(jìn)行了特定的優(yōu)化。

4.2.1 資源優(yōu)化

為了在單節(jié)點(diǎn)FPGA中盡可能多的放入并行加速流水線，對(duì)單條流水線中各個(gè)模塊的資源占用情況進(jìn)行分析發(fā)現(xiàn)：demo_gen模塊的LUT資源使用（約7%）是決定放入條數(shù)的瓶頸。

經(jīng)過(guò)深入研究算法發(fā)現(xiàn)：算法中采用簡(jiǎn)單平方和之后開平方的方式計(jì)算兩個(gè)特征點(diǎn)之間的距離。該運(yùn)算需要占用大量計(jì)算資源，是資源瓶頸。為了緩解這一情況，文中采用兩點(diǎn)距離近似計(jì)算方法，即采用移位運(yùn)算來(lái)近似求解兩點(diǎn)間的距離，且算法的精確度在能夠接受的范圍內(nèi)，從而在使用很少資源的同時(shí)達(dá)到較高的精確度。

原算法和近似算法的資源占用情況如圖6所示，F(xiàn)F（Flip-Flop）使用是原來(lái)的14.8%，LUT（Look-Up-Table）的使用是原來(lái)的26.3%，極大的優(yōu)化了資源的使用，使得原來(lái)單節(jié)點(diǎn)放入加速流水結(jié)構(gòu)從14條增加到20條。

4.2.2 結(jié)構(gòu)優(yōu)化

經(jīng)過(guò)資源優(yōu)化之后，整體性能有了很大提高，為了進(jìn)一步提高整體性能，觀察并統(tǒng)計(jì)各個(gè)模塊的時(shí)延情況如圖7所示，另一方面在資源優(yōu)化后，LUT的使用下降，而第一個(gè)模塊demo_gen部分的DSP資源的使用成為了瓶頸，約占全部資源的4%。

觀察各模塊的時(shí)延圖，可以發(fā)現(xiàn)第一個(gè)模塊demo_gen的運(yùn)行時(shí)延不到最大時(shí)延模塊pair_expand_all的一半，但其DSP資源的占用最多，也是影響FPGA中放人流水線數(shù)目的瓶頸。

基于上述情況，本文考慮采用雙尾端的結(jié)構(gòu)，即在一個(gè)demo_gen模塊后面連接相同的兩條尾巴。如圖8所示。并且通過(guò)“乒乓”操作的方式使得demo gen模塊的有效運(yùn)行時(shí)間更長(zhǎng)，從圖7時(shí)延上來(lái)看這一設(shè)計(jì)是可行的。

通過(guò)這樣的方式，將一條流水線中demo gen模塊的資源占用平攤到兩條流水線，僅占到2%左右，而單條流水線的性能基本沒有影響，從而能夠在同一FPGA中等效放入30多條流水線，極大的提高了加速結(jié)構(gòu)的吞吐率。

4.3 整體結(jié)構(gòu)

經(jīng)過(guò)資源優(yōu)化和整體結(jié)構(gòu)優(yōu)化調(diào)整后，加速結(jié)構(gòu)單條流水線整體如圖8所示。

5 實(shí)驗(yàn)及結(jié)果分析

為了測(cè)試設(shè)計(jì)的整體效果，本文在FPGA平臺(tái)上對(duì)這一加速結(jié)構(gòu)進(jìn)行了實(shí)現(xiàn)。并同時(shí)在軟件平臺(tái)上對(duì)原算法進(jìn)行了相應(yīng)的比較測(cè)試。

5.1 實(shí)驗(yàn)平臺(tái)

本文選擇了常見的軟硬件平臺(tái)進(jìn)行實(shí)驗(yàn)測(cè)試。軟件平臺(tái)：采用的X86服務(wù)器是Intel XeonE5620，主頻2.4GHz，內(nèi)存40GB；硬件平臺(tái)：采用的是Xilinx的FPGA（zynq-7030fbg484），包含的主要資源分別是LUT（78600）、FF（157200）、DSP（400）。

5.2 結(jié)果分析

在所選擇的軟硬件平臺(tái)上，本文針對(duì)不同的指紋數(shù)據(jù)進(jìn)行了多次測(cè)試，實(shí)驗(yàn)結(jié)果如圖9所示。

通過(guò)圖9實(shí)驗(yàn)結(jié)果可以看出。本文所實(shí)現(xiàn)的加速結(jié)構(gòu)加速效果非常明顯：軟件平臺(tái)上的平均匹配速度約為每秒4萬(wàn)次，本文在單節(jié)點(diǎn)FPGA平臺(tái)上實(shí)現(xiàn)的加速結(jié)構(gòu)平均匹配速度約為每秒100萬(wàn)次。達(dá)到了25倍的加速效果。

另一方面，本文采用FPGA平臺(tái)是可擴(kuò)展的。通過(guò)使用多個(gè)FPGA節(jié)點(diǎn)并行的處理，整體計(jì)算速度還可以進(jìn)一步提升。目前本文已在16個(gè)節(jié)點(diǎn)的FPGA上進(jìn)行了實(shí)現(xiàn)，整體性能達(dá)到每秒千萬(wàn)次比對(duì)，能夠初步滿足大規(guī)模范圍的指紋匹配應(yīng)用。

6 結(jié)束語(yǔ)

本文主要針對(duì)基于細(xì)節(jié)特征點(diǎn)的這一類指紋識(shí)別算法在大規(guī)模指紋數(shù)據(jù)應(yīng)用下的加速問題，提出并設(shè)計(jì)實(shí)現(xiàn)了一種加速結(jié)構(gòu)。通過(guò)本文的加速，指紋匹配性能有了極大的提升，單節(jié)點(diǎn)FPGA能達(dá)到25倍的加速效果。16個(gè)節(jié)點(diǎn)并行條件下甚至能到每秒千萬(wàn)次比對(duì)，能夠初步滿足大規(guī)模指紋匹配的應(yīng)用場(chǎng)景，達(dá)到了本文的主要目標(biāo)，也為后續(xù)新指紋匹配算法的大規(guī)模應(yīng)用奠定了基礎(chǔ)。

但由于本文主要針對(duì)基于細(xì)節(jié)特征點(diǎn)這一類指紋識(shí)別算法，對(duì)其他指紋識(shí)別算法的加速效果沒有這么明顯。這是本文目前的主要問題，也是下一步需要深入研究的地方。