一種基于FPGA指紋識別加速結(jié)構(gòu)的設計與實現(xiàn)

趙錦明　錢磊　吳東

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

[關鍵詞]生物識別；指紋識別；流水；乒乓操作；FPGA

[中圖分類號]TP3 [文獻標識碼]A

1 引言

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

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

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

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

2 基于細節(jié)特征點的指紋識別算法

2.1 指紋識別簡介

指紋識別是指通過比較不同指紋的細節(jié)特征點來進行身份鑒別的過程，其整體流程如圖1所示。包括指紋庫的建立、待比對指紋采集、指紋處理及特征提取、指紋匹配等主要過程。

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

2.2 基于細節(jié)特征點的指紋識別算法原理

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

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

各步驟具體如下：

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

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

2.3 算法分析

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

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

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

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

3.1 設計思想

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

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

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

3.2 算法調(diào)整

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

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

3.3 結(jié)構(gòu)設計

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

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

4.1 模塊劃分

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

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

各模塊的功能說明如下：

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

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

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

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

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

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

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

4.2 優(yōu)化策略

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

4.2.1 資源優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

5.1 實驗平臺

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

5.2 結(jié)果分析

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

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

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

6 結(jié)束語

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

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