基于局部方向場散列的掌紋快速辨識方法

陳 曦, 于 明, 岳 峰

(1. 河北工業大學電子信息工程學院,天津 300401；2.北京科學技術研究院北京市新技術應用研究所,北京 100089;3.河北工業大學人工智能與數據科學學院,天津 300401)

掌紋識別近年來備受研究者關注，并且提出了多種掌紋識別方法，包括基于紋理[1]、基于方向編碼[2]、基于局部描述符[3]、基于深度神經網絡[4-6]等。掌紋識別系統因其在安全性的可靠表現成為出入管控、身份鑒別等應用領域的理想解決方案。

掌紋識別系統通過比較查詢掌紋與存儲模板的相似度來進行身份辨識。研究發現系統識別的準確性和處理速度將會隨著注冊人數的上升而下降[7]。然而很多系統需要面向大規模人群進行身份辨識，因此加速識別過程不僅可以減少系統響應時間，而且可以通過采用更復雜的匹配算法，為提高識別精度提供可能性[8]。現有的快速掌紋識別方法可以大致分為層次匹配法、掌紋分類法和基于樹形結構的識別方法和基于散列的識別方法。

層次匹配方法[9]通常會提取多種簡單特征，然后以分層的方式快速搜索目標。因此，這類方法可以構建多層搜索結構，從而在單個層中排除較少候選目標。分層匹配方法的缺點是在搜索終止之前產生目標丟失的情況。

掌紋分類方法是指將掌紋分成幾個類別，然后將輸入圖像與其對應類中的模板進行匹配[10]。這種方法的缺點是根據初始分類規則，可能會將查詢掌紋和目標模板置于不同的類別中，從而無法成功進行匹配。因此，盡管這兩種策略在加速識別過程方面都取得了不錯的性能，但它們會造成明顯的精度損失。

2009年，Yue等[11]提出了一種基于覆蓋樹的快速掌紋識別方法，隨后通過優化樹結構對其進行了改進[12]。結果表明，該方法可以顯著加快識別過程，而且相對于傳統的蠻力搜索，沒有任何精度損失。但是由于在搜索過程中必須查詢到注冊者的至少一個模板，因此在搜索加速上受到一定限制。

受到模糊數據快速檢索的啟發，Yue等[13]提出了一種基于散列的快速掌紋識別方法主方向模式散列(POP hashing)。POP hashing設計了一種主方向模式(POP)作為散列函數，從而通過減少目標的搜索范圍而加速識別過程。實驗結果表明其在幾乎不損失精度的前提下比蠻力搜索方式快十倍以上。此外，與序數編碼(ordinal code)，魯棒線編碼(RLOC)等方法的對比結果證明，POP Hashing在精度和速度上都優于這些方法。

為此，定義一種新的散列模式，稱為局部方向場模式。并根據其設計了一種新的快速掌紋識別方法局部方向場編碼(LOFP hashing)。在公共數據庫的實驗結果表明，LOFP hashing可以將POP hashing的識別速度顯著提升3～10倍。

1 散列與基于散列的掌紋識別方法

散列是一種旨在對目標數據分塊的技術，它通過散列函數為每個數據標定一個散列值，每個散列值對應若干數據。在搜索特定目標時，通過散列的方式可以將搜索空間從整個數據庫轉化成特定子空間中的數據，這樣可以通過縮小搜索范圍來提高搜索效率。圖1為簡化的數據散列示意圖。

圖1 數據散列過程示例Fig.1 An example of the hashing process

文獻[13-14]證實，基于方向編碼的掌紋識別技術可以通過散列的方式顯著提升搜索效率。由于方法采用了類似的散列框架，因此將簡要介紹文獻[13]中快速掌紋識別方法POP hashing。

在預處理階段，POP hashing首先提取掌紋圖像的D=1 024個方向特征，并將特征所屬的用戶ID依次索引至散列表H。同時，還需要建立一個位移表S和尺度表O(tabO)。位移表S用于記錄編號為1～1 024的特征在散列表H(tabH)的起始位置。尺度表O用于記錄散列表H中每個位置所包含的用戶ID數量。

在搜索階段，該方法定義了一種散列函數，稱為主方向模式(POP)，它包含K個不鄰接的主方向特征。主方向特征(POF)是指位于手掌三條主線位置的特征，POF的穩定性高、一致性強[15]。POP hashing通過一組Gabor濾波器對掌紋圖像卷積后，將響應強度前10%的方向特征選為POF。然后，將每個POP在散列表H中進行搜索，當其K個POF檢索到的用戶ID有交集時，稱為一次碰撞。查詢樣本與真實目標的碰撞稱為真碰撞，否則稱為假碰撞。POP hashing采用多碰撞策略，當候選目標的碰撞次數達到C，認為找到了疑似目標，將其與查詢樣本進行全匹配，并通過匹配得分判斷是否成功命中目標。

隨后，Yue等[14]改進了POP Hashing，提出了A-POP hashing算法。A-POP hashing在預處理階段，僅用P=0.5D個響應強度較高的特征建立tabH，不僅減少了全匹配的次數，還可以減少約50%的存儲空間。

綜合速度與識別準確度，POP和A-POP hashing是面向大規模數據庫的掌紋識別算法中最具優勢的方法。

2 方法

由圖1可知，有若干數據共享相同的散列值。同一散列值對應的數據量越多，假碰撞的概率越高，查找的復雜度越高。對于POP hashing，通過POP包含的K個方向特征以及閾值為C的多碰撞策略，可以將散列后的子空間大小，即共享相同散列值的模板數量限制在χ左右，如式(1)所示：

(1)

式(1)中：B為方向編碼的數量，對于POP hashing，B=6；N為數據庫中模板的總數。因此為了進一步降低查找復雜度，可以通過增加B、K或C來實現。然而，K或C的增加會造成識別準確率下降，因此它們的選擇要平衡速度和精度。而且使用二維Gabor濾波器對圖像卷積是一個復雜度較高的運算，因此通過增加濾波器數量來增加B并不可行。使用基于梯度的方向場來進行掌紋方向特征提取和POF篩選。

2.1 掌紋方向特征提取和POF篩選

基于梯度的方向場被廣泛用于方向特征提取。相對于Gabor濾波器組，它可以在有限的時間耗費下得到每個位置連續而非離散的方向表達。基于梯度方向場在圖像坐標(m,n)上的梯度強度δ和方向θ可以根據式(2)、式(3)得到：

(2)

(3)

式中：Gx(i,j)和Gy(i,j)分別為由Sobel濾波器與掌紋圖像卷積得到的水平和垂直方向的梯度響應；W為濾波器的尺寸。由于基于梯度的方法容易受到噪聲的影響，因此通過式(4)，對得到的方向θ進行一致性評估，一致性權重φ是介于0～1的值，φ越高，θ的可靠性越強。

(4)

然后，通過對加權梯度強度κ=δφ進行降序排列來檢測主方向特征POF。圖2為隨機選取兩個手掌的不同樣本，根據排序后κ前10%的方向特征選取的POF。從圖2可以看出，檢測出的POF基本都位于主線相關區域，而且不同樣本間重合度很高。在100個掌的實際測試中，POF的位置重合度達71.2%，重合的POF具有相同方向編碼的比例是92.4%。而在κ排序靠后10%的方向特征重合度為38.6%，重合點具有相同編碼的比例僅為34.8%。因此，根據方法檢測的POF具有很強的一致性。

圖2 兩個手掌不同樣本檢測的POFFig.2 POFs across the samples of two subjects

2.2 特征雙編碼方法

檢測到POF后，需要對它們連續的特征方向θ進行離散化編碼。傳統方向編碼方式有兩個缺點。首先，絕大多數情況下θ會落在兩個離散編碼值之間的區域[16]，也就是說，用單個編碼表示連續方向并不精確。如圖3(a)所示，當θ處于編碼C3和C4之間的區域，無論哪個編碼都無法精確表達θ；當θ處在編碼邊界時，編碼存在不穩定的情況，稱這種情況為邊界漂移(boundary-shifting)。如圖3(b)所示，fα和fβ表示兩個方向特征，它們的連續方向表達分別為θ-ε和θ+ε，其中ε>0且足夠小。若θ處于編碼Cα和Cβ的邊界，它們會被分別編碼為Cα和Cβ。由于二者方向非常接近，因此更合理的方式是將它們編碼為相同的值。

圖3 傳統編碼方式存在的缺陷Fig.3 Disadvantages of single-orientation encoding method

根據式(1)，為了降低目標搜索的復雜度，選取了相對于POP hashing更大的編碼數量B=18。隨著B的增長，每個離散編碼可以表達的方向更為精確，因此圖3(a)中的影響會降低。但是由于編碼邊界更為密集，因此圖3(b)中邊界漂移的情況會愈發頻繁地出現。因此，提出一種稱為方向場編碼(OFC)的雙編碼方式，除了根據傳統方式將θ編碼為主導碼Cd，還將其最近鄰的碼域所屬的碼值編為輔助碼Ca。即α=(Cd,Ca)，定義如式(5)所示：

(5)

根據這種方式，一副掌紋圖像的所有P個POF被雙編碼為β={ap}，p=1,2,…,P。對于任意兩個編碼Cα和Cβ，它們之間的距離被定義為γ，如式(6)所示。

γ(Cα,Cβ)=min(Cα-Cβ,B-Cα-Cβ)

(6)

(7)

(8)

進一步，將每個編碼表達為9層18位的比特碼形式，如表1所示。那么式(5)中的兩個編碼可以改寫為式(9)的形式。

表1 OFC的9層18位比特碼Table 1 9-layer,18 bits representation of OFC

(9)

式(9)中：bl為第l層的18位比特碼，而式(6)可以被重新表達為Hamming距離γ：

(10)

式(10)中：?表示邏輯異或操作，這樣不僅可以方便編碼在計算機當中存儲，還能使編碼距離的計算非常便捷[17-19]。

最終，兩個OFC編碼的匹配得分通過非線性距離度量方式計算。

(11)

2.3 局部方向場模式與LOFP Hashing

2.3.1 局部方向場模式

為了解決查詢樣本與模板沒有精確配準的問題，搜索階段在查詢碰撞時需要在對查詢目標進行位置平移，這個過程會帶來不可忽視的計算壓力。以POP hashing為例，它需要在水平和豎直方向上進行[-2,+2]的移動，因此樣本與模板之間需要嘗試25種配準方式。如果能夠在不損失精度的情況下減少這些嘗試，搜索的復雜度將至多減少96%。

圖4 LOFP示意圖Fig.4 An example of LOFP

(12)

2.3.2 LOFP Hashing

在預處理階段，提出一種基于窗口碼圖CM構建散列表H的方法，具體方法如算法1所示。用這種結構，可以方便地記錄每個POF的雙編碼以及在圖像坐標系下坐標到LOFP區域索引號?的轉換。其中算法1第3行中坐標(x,y)到區域索引號的映射方法如式(13)所示。

算法1 窗口碼圖的構建

輸入：POF數量P；OFC編碼OC={ap}，p=1,2,…,P；POF坐標POS

輸出：窗口碼圖CM

CM=NULL//初始化

fori=1 toPdo

?=Get_Wnd_Idx(POS(i)) //坐標映射

Ccode=αi//獲取OFC雙編碼

CM[?][Ccode(0)]=TRUE //主導碼位置

CM[?][Ccode(1)]=TRUE //輔助碼位置

end for

(13)

在搜索階段，對于一個LOFP的二元表達{P=·,V=*}，檢索目標身份信息，即第1節中所述的碰撞檢測方式如下：首先，根據位移表O[·][*]找到記錄對應散列值子空間的起始位置。然后，根據尺度表S[·][*]找到H中記錄的子空間大小。最后，根據子空間起始位置與大小返回所有模板的身份信息。如圖5所示。

圖5 散列表搜索示意圖Fig.5 Searching the hash tables

詳細的碰撞檢測方法由算法2給出，變量Cs用于統計查詢掌紋的LOFP中，在H的窗口碼圖CM有對應記錄的數量，如果等于K，表示發生一次碰撞(算法2中的第13行)，然后將相應的用戶ID插入到待檢隊列Cd，并更新碰撞計數器c(算法2中的第21行)。當a中某個元素超過碰撞閾值C，認為找到候選目標，將輸出對應模板ID，進行全匹配。

算法2 碰撞檢測

輸出：碰撞計數器a

a=0 //初始化

Cd=NULL //初始化待檢隊列

Cs=NULL

fork=1 toKdo //逐個檢測

forz=1 toZkdo //逐個檢測

of=O[?k][Ccode] //起始位置

size=S[?k][Ccode] //子空間的大小

forsz=1 tosizedo //檢測窗口碼圖CM

IfCM[?k][Ccode]=TRUE //CM有對應值

ID=H[of+sz]

Cs[ID]=Cs[ID]+1

IfCs[ID]=K

Insert(Cd,ID) //插入隊列

end if

end if

end forsz

end forz

end fork

forl=1 to Length(Cd)

c[Cd(l)]=c[Cd(l)]+1 //更新計數器

end forl

在方法上，LOFP hashing采用了與POP hashing相似的框架。所提出的方法與其主要區別在于以下三點。

(1)基于梯度的方向場能夠以較少計算代價提取特征的連續方向表達θ，利用式(3)、式(4)得到的一致性加權梯度強度可以提取到穩定的POF。

(2)根據式(1),選取的較大的編碼范圍B使方向特征更具有區分度。OFC雙編碼方式不僅可以消除邊界漂移和提高編碼對連續方向θ的表達準確性，同時可以根據式(10)、式(11)，以很小的存儲和運算代價得到編碼間的相似度得分。

(3)窗口化的特征表達方式LOFP可以去除檢測碰撞時的位置平移過程，至多減少96%的碰撞檢測次數。

3 實驗結果與分析

3.1 測試數據庫

使用三個大型公開數據庫，簡介如下。

(1)香港理工大學大型掌紋數據庫(DB1)[20]：包含9 667個手掌，共93 638張圖像。數據庫中，約86%的受試者是學生，約12%是工人，約1%是老人，1%是其他人。

(2)中國科學院掌紋數據庫(DB2-R)[21]：包含5 237張從600個掌獲取的圖像。每只手掌大約8張圖片，所有的樣本都在同一周期采集。在數據采集過程中，沒有限制手掌姿態和位置，也沒有構成半封閉環境。因此圖像質量比DB1中要差。

(3)十萬人模擬數據庫(DB2-S)[22]：包含了100 000個模擬生成的模板，每個模板是一個1 024維隨機生成的方向特征向量。

實驗中，將第二個數據庫DB2-R和第三個數據庫DB2-S合并為一個超大型數據庫DB2。數據庫選取的依據有兩點。首先，3個數據庫的選擇與設置和相關文獻中一致，可以公平地比較方法性能。其次，3個均為國際公開大型數據庫，有利用模擬大規模人群辨識過程。

3.2 結果評估標準

實驗從識別準確度和速度兩個方面評估方法性能。準確度方面，采用生物識別領域三個通用的評估指標：錯誤拒絕率(FRR)、錯誤接受率(FAR)和真實接受率(GAR)。FRR表示查詢樣本未被成功識別的比例，FAR表示查詢樣本被識別為錯誤身份信息的比例，GAR表示查詢樣本被成功識別的比例。速度方面，以方法相對于蠻力搜索的速度提升比例，即加速比為標準。蠻力搜索是生物識別系統中最廣泛的一種匹配方式，它將查詢目標與模板逐一匹配，直至找到滿足相似度閾值的目標。

實驗平臺為一臺PC機，配置為Intel i7-8700 320 GHz CPU，8 GB RAM，僅使用CPU單核單線程。軟件環境是Windows 10 Home Basic(64位)和 Visual Studio 2010。測試程序由C++語言編寫。

實驗參數由網格法得到，即通過限制每個參數的取值范圍，執行多個循環尋找最佳組合。它們分別是：LOFP包含的編碼數量K=3、碰撞閾值C=4、編碼數量B=18、窗口大小Sn=2。為了公平地進行對比實驗，相似度閾值T=0.35與POP 和 A-POP hashing相同。

3.3 識別準確度實驗與分析

在DB1中，模板和測試樣本的數量分別為9 667和83 971。蠻力搜索的GAR為99.27%。在不同參數K和C下實驗結果如圖6(a)所示。由圖6(a)可以看出，當K=2、C≤10和K=3、C≤6時，方法的GAR與蠻力搜索幾乎相同。實驗將DB2的模板和樣本的量分別為100 600和4 637。在DB2中，蠻力搜索的GAR為95.99%，方法的GAR如圖6(b)所示，其走勢與DB1中的結果類似。

圖6 LOFP hashing在DB1和DB2中的GARFig.6 GARs of the proposed method on DB1 and DB2

3.4 識別速度實驗與分析

圖7給出了不同數據庫中LOFP Hashing相對于蠻力搜索方加速比的實驗結果。從圖7可以看到，曲線的走勢可以近似看作具有極大值的拋物線。結合圖6可知，在最初階段隨著C的增加，滿足碰撞閾值的次數會減少，造成全匹配次數減少，加速比迅速上升，同時準確度開始下降。達到加速比頂點后，若C持續增加，雖然全匹配次數仍在減少，但是需要更多的LOFP參與碰撞檢測，因此加速比開始下降。加速比頂點隨著K的增加而越早地出現。

圖7 LOFP hashing在DB1和DB2相對于蠻力搜索的加速比Fig.7 Speedups of the proposed method on DB1 and DB2

在搜索階段，查詢掌紋會與大小為N的模板集進行M次全匹配，直到找到目標或返回“不匹配”。M與N的比例在生物識別領域被稱為滲透率[19]。滲透率越低表示算法減少全匹配次數的性能越強。圖8給出了不同參數下滲透率的比較。蠻力搜索的平均滲透率約為50%，與蠻力搜索相比，DB1上LOFP hashing可以將滲透率減少189.25倍，而在DB2中結果達到了337.18倍。

圖8 LOFP hashing在DB1和DB2中的滲透率Fig.8 Penetration rates of on DB1 and DB2

3.5 對比實驗與分析

作為已知最先進的快速掌紋識別方法，文獻[13]已經提供了POP hashing與其他快速識別方法以及一些知名掌紋識別方法的對比。文獻[14]中的A-POP方法是POP hashing的一種加速版本。因此，將二者作為標尺衡量所提方法的性能,所有的對比方法使用的軟、硬件平臺一致。

根據表2，在DB1上所提出的方法對于POP hashing的加速比是3.28倍，精度損失可以忽略不計，并將A-POP hashing的速度提升約50%，且精度更高。這主要是因為方法在去除了位置平移操作后，在兩個數據庫中將嘗試碰撞的數量分別減少了約32%和49%，而選取更大的B=18和雙編碼方式使編碼不僅可區分度更高，而且更精確。假碰撞的次數分別減少了約24%和21%。

表2 在DB1上識別效果對比Table 2 Identification results on DB1

表3 在DB2上識別效果對比Table 3 Identification results on DB2

4 結論

提出了旨在面向大規模人群快速身份辨識的掌紋識別方法LOFP hashing。通過減少假碰撞的發生頻率、加速目標搜索進程以及提高方向特征的穩定性和精確度三個方面對識別性能進行提升。提供了真實掌紋數據庫和模擬數據庫上辨識結果，并給出了理論上有進一步提升空間的合理的分析和解釋。綜合識別精度和速度的考慮，所提方法可以認為比當前最具優勢的POP hashing及其加速版本A-POP hashing更適用于大規模人群身份辨識。隨著深度學習理論與應用的快速發展，未來的研究重點將著重放在基于深度學習的快速掌紋識別方法研究。