李慶年，胡玉平

(1.南寧學(xué)院 信息工程學(xué)院， 南寧 530200; 2.廣東財經(jīng)大學(xué) 信息學(xué)院， 廣州 510320)

指紋識別是近二十年來的研究熱點[1]，隨著硬件技術(shù)的快速發(fā)展，使用識別技術(shù)的機構(gòu)和公司與日俱增。指紋呈現(xiàn)出多種特征，根據(jù)這些特征可以更好地實現(xiàn)精準(zhǔn)識別。在這些特征中，細節(jié)點是應(yīng)用最廣泛的特征之一。識別算法通常從指紋細節(jié)點中提取一組結(jié)構(gòu)進行計算[2]，在模板指紋數(shù)據(jù)庫中尋找給定的輸入指紋。驗證旨在評估2幅圖像是否對應(yīng)同一指紋。與許多其他圖像匹配出現(xiàn)的問題一樣，由于空間中存在圖像變形、信息缺失等因素，因而驗證具有很高的復(fù)雜性[3]。此外，由于涉及特征之間的多種比較，識別技術(shù)實質(zhì)上比驗證更加復(fù)雜。為了克服識別中存在的困難，學(xué)者們提出了分類和索引等技術(shù)[4-5]。

當(dāng)數(shù)據(jù)庫中的數(shù)據(jù)量較大時，指紋識別問題的復(fù)雜性變得更高，尤其是識別時間，其與匹配數(shù)呈線性增長關(guān)系[6]。龐大的指紋數(shù)據(jù)庫對指紋識別構(gòu)成了挑戰(zhàn)。在過去幾年，科研人員提出了幾種使用大規(guī)模高性能計算體系結(jié)構(gòu)來處理大數(shù)據(jù)問題的框架，這些框架中最流行的是Apache Hadoop[7]和Apache Spark[8]。Apache Hadoop是MapReduce范例的一種開放源碼，它將數(shù)據(jù)構(gòu)造成一組key和value的組合對，將這些組合對分為2個階段進行處理：Map階段和reduce階段。在Map階段，每個映射操作接收一個單線對，并輸出一組它所產(chǎn)生的線對。將所有映射階段的中間線對進行洗牌和排序，以便每個reduce操作都接收相同key。reduce操作的結(jié)果也可表示為一組關(guān)鍵value對，這些關(guān)鍵value對存儲在HDFS中。Apache Spark同樣將HDFS用作底層文件系統(tǒng)，但會將數(shù)據(jù)分組為彈性分布式數(shù)據(jù)集(RDD)。Spark將這些RDD盡可能多地保存在內(nèi)存中，以減少I/O磁盤容量。Spark提供了一組轉(zhuǎn)換(將一種RDD轉(zhuǎn)換為另一種RDD)和操作(將RDD轉(zhuǎn)換為某種結(jié)果)，這些轉(zhuǎn)換和操作可以隨意組合，以創(chuàng)建不同的工作流程。負載平衡戰(zhàn)略[9]、虹膜識別的并行化[10]等方案都是利用這些框架來解決生物特征識別的問題。

基于上述分析，本文在大數(shù)據(jù)框架中處理并行指紋識別問題時，提出了一種基于新型指紋拓撲結(jié)構(gòu)(fingerprint topology structure,FTS)的指紋匹配分解方法。主要創(chuàng)新點如下：

1) 提出了一種基于細節(jié)點的置信度指紋匹配算法，有助于全局范圍的指紋信息提取，從而確保局部相似細節(jié)點的有效匹配。

2) 提出的分解方法在指紋匹配過程中考慮了更好的并行性，允許丟棄局部結(jié)構(gòu)中檢測到的非匹配的子集，從而可有效使用和輸入局部結(jié)構(gòu)的模板信息，增加了識別輸入指紋的靈活性。

3) 將提出的分解方法在Apache Hadoop和Apache Spark框架上實現(xiàn)，通過與現(xiàn)有的MPI系統(tǒng)上的實驗結(jié)果進行比較，驗證了該方法的可靠性。將分解方法應(yīng)用于2種不同的匹配算法(Jiang算法[11]和細節(jié)點圓柱代碼(MCC算法)[12])中，通過實驗驗證了所提出分解方法的通用性。

1 基于細節(jié)點特征的指紋匹配

1) 全局匹配方法。尋找2個細節(jié)點集的最佳對準(zhǔn)，使用指紋的全部信息實現(xiàn)匹配，該方法雖然提供了較高的清晰度，但是對指紋采集的失真較為敏感。

2) 局部匹配方法。從細節(jié)點集中提取局部結(jié)構(gòu)，并對這些局部結(jié)構(gòu)進行比較，以確定它們的相似性。該方法通常不受平移和旋轉(zhuǎn)的影響，因此對失真不太敏感。

(1)

識別問題即在包含n個指紋T={T1,…,Tn}的模板數(shù)據(jù)庫中查找輸入指紋Ij。大多數(shù)識別系統(tǒng)通過將Ij與每個模板指紋Ti進行比較來完成n個驗證，并返回產(chǎn)生最大分數(shù)的標(biāo)識：

(2)

這種識別系統(tǒng)的識別時間關(guān)于n呈線性增加。因此，當(dāng)n很大時，識別時間往往過長。

2 提出的指紋匹配通用分解方法

本文提出了一種適用于基于細節(jié)點的指紋匹配算法的通用分解方法。它將匹配過程分解為較小的步驟，這些步驟以并行和靈活的方式計算，從而及早發(fā)現(xiàn)不匹配指紋并加快處理速度。

2.1 新型指紋拓撲結(jié)構(gòu)

在傳統(tǒng)的指紋拓撲結(jié)構(gòu)中，通常只提取某一種特征。文獻[15]利用提取出的紋線特征，通過對比紋線達到指紋匹配的目的。文獻[16]利用中心點附近的方向場實現(xiàn)指紋匹配，該算法提取的是鄰域特征。本文中把細節(jié)點特征、脊線特征以及鄰域特征三者結(jié)合起來，實現(xiàn)了一種新型指紋拓撲結(jié)構(gòu)。

在指紋的特征識別中，叉點包含的信息量更大，且不易受到外部條件的干擾?；诖?，本文將脊線跟蹤應(yīng)用到叉點的3個分支中，如圖1所示。o點表示叉點，a、b、c點表示脊線點，順著3個分支可到達a、b、c三點。令叉點和3個脊線點的方向角差分別為α、β、γ，叉點和3個脊線點間的長度分別為oa、ob、oc，并將它們存入到特征向量中。用(x,y)表示叉點的坐標(biāo)，在特征點的類型中，用E表示端點，用F表示叉點，則叉點的特征向量可以表示為{(x,y),F,(α,oa),(β,ob),(γ,oc)}。

圖1 叉點拓撲結(jié)構(gòu)

由于端點僅存在于一條脊線上，它所包含的脊線特征以及鄰域特征較少，所以使用k近鄰算法來提取端點附近的有用特征。在圖2中，根據(jù)k近鄰算法尋找離叉點o距離短、并且處在環(huán)形區(qū)域中的3個脊線點，這3個脊線點就可以作為鄰域特征點。接著，利用脊線追蹤的方式尋找到最終的脊線點a、b、c。整個過程中，組成環(huán)形區(qū)域的2個圓的半徑分別為R1和R2，端點和3個脊線點的方向角差分別為α、β、γ，端點和3個脊線點間的長度分別為oa、ob、oc，并將它們存入到特征向量中。用(x,y)表示端點的坐標(biāo)。在特征點的類型中，用E表示端點，用F表示叉點，則端點的特征向量可以表示為{(x,y),E,(α,oa),(β,ob),(γ,oc)}。

圖2 端點拓撲結(jié)構(gòu)

2.2 提出的基于置信度的匹配算法

假設(shè)p和p′分別是2個細節(jié)點的不同集合，且它們各包含Np和Np′個細節(jié)點，則可以得到Np和Np′個細節(jié)點的拓撲結(jié)構(gòu)以及1個相似度矩陣SLS，該矩陣的元素個數(shù)為Np×Np′。令M={ii′}為p和p′之間的最優(yōu)匹配，則該最優(yōu)匹配可表示為一個尋找最優(yōu)的問題：

(3)

用以下二值優(yōu)化問題的解代替該問題的解：

m0=arg max(msT),m∈{ 0,1}NpNp′

s.t. |1pm*|≤|1p| and |m*1p′|≤|1p′|

(4)

式中：M表示匹配關(guān)系；m表示M相對應(yīng)的1×NpNp′的行向量；s表示SLS相對應(yīng)的1×NpNp′的行向量；m0表示最優(yōu)解，它是一個二值向量。m可以表示成一個矩陣形式m*，m*的大小為Np×Np′，m*(i,i,)=1即表示細節(jié)點i和i′相互匹配，而m*(i,i,)=0則表示這2個細節(jié)點不匹配；向量1p表示一個值全為1的、大小為1×Np的行向量，向量1p′則表示一個值全為1的，大小為1×Np的列向量。在約束條件中，p和p′集合中的細節(jié)點互相匹配，|1p|表示1p的l1范數(shù)。

在傳統(tǒng)的指紋識別方法中，細節(jié)點的局部相似度能在局部區(qū)域內(nèi)衡量相似程度，而在全局范圍上，局部相似的細節(jié)點很有可能不能相互匹配。因此，本文提出了置信度的概念，它描述了一組細節(jié)點對在該全局范圍內(nèi)與候選點之間的匹配可能性。對于p和p′兩個細節(jié)點的集合來說，置信度矩陣CGC包含Np×Np′個元素，關(guān)聯(lián)矩陣用TM來表示，其中TM(i,i′)=CGC(i,i′)×SSL(i,i′)，則匹配問題可以轉(zhuǎn)化為

(5)

可以使用下列二值優(yōu)化問題的解代替該問題的解：

(6)

其中：t表示與矩陣TM相對應(yīng)的行向量，其大小為1×NpNp′；M表示匹配關(guān)系；m表示M相對應(yīng)的1×NpNp′的行向量；m0表示最優(yōu)解，它是一個二值向量。指示向量m可以表示成一個矩陣形式m*，m*的大小為Np×Np′。m*(i,i,)=1表示細節(jié)點i和i′相互匹配，而m*(i,i,)=0則表示這2個細節(jié)點不匹配。向量1p表示一個值全為1的、大小為1×Np的行向量，向量1p′表示一個值全為1的、大小為1×Np的列向量。在約束條件中，p和p′集合中的細節(jié)點互相匹配，|1p|表示1p的l1范數(shù)。

2.3 匹分解法

(7)

基于部分分數(shù)的概念，定義了2個聚合這些分數(shù)的函數(shù)，用來以并行且靈活的方式計算最終匹配分數(shù)qij。

1) 函數(shù)Qp將1組kp部分分數(shù)與單個新的部分分數(shù)聚合，如方程式(8)所示。需要注意的是，kp為正在聚合的部分分數(shù)的數(shù)量，它與2個指紋中任何一個局部結(jié)構(gòu)的數(shù)量均無關(guān)。因此，函數(shù)Qp的輸出是由2個指紋中得到的局部結(jié)構(gòu)的kp子集中計算出來的部分分數(shù)。

(8)

2) 在單局部分數(shù)上應(yīng)用方程式(9)中定義的函數(shù)Qf，單局部分數(shù)包含所有Ti和Ij局部結(jié)構(gòu)之間的相似性聚合信息，并計算出最終匹配分數(shù)qij。

(9)

當(dāng)保持函數(shù)Qf固定時，這2個函數(shù)允許以非常靈活的方式聚合部分分數(shù)，從而使匹配算法具有細粒度并行化以形成最終匹配分數(shù)。

3 匹配方法的并行化

3.1 將匹配方法嵌入到MapReduce

上文定義的分解法可以表示為MapReduce范式中的問題。假設(shè)模板數(shù)據(jù)庫由所有nT模板指紋的局部結(jié)構(gòu)組成。本文提取將要識別的nI輸入指紋的局部結(jié)構(gòu)(通常nI?nT)，假設(shè)在MapReduce匹配過程啟動之前，先將這些本地結(jié)構(gòu)存儲在分布式文件系統(tǒng)中。

映射 (k1,v1)→ 列表 ({k2,v2},?j∈{1,…,ni})

(10)

映射為每個輸入生成nI個輸出記錄，因此將2個指紋的標(biāo)識符作為key，將所產(chǎn)生的部分分數(shù)發(fā)送到reduce函數(shù)。每個reduce函數(shù)合并給定的模板對以及輸入指紋以生成最終匹配分數(shù)，如方程(11)所示。將這些分數(shù)寫入分布式文件系統(tǒng)。

(11)

此外，在中間組合階段聚合部分分數(shù)集，從而最小化mapper和reducer之間的網(wǎng)絡(luò)和磁盤流量。在MapReduce中，組合器可以在記錄上應(yīng)用多次或一次不用，這意味著它必須是可結(jié)合的、可交換的。基于集合的定義，提出的分解自然地符合這些要求：

(12)

圖3(a)給出了本文方法在MapReduce中的流程。圖3(b) 給出了每個映射的工作流程，其中局部匹配在映射中執(zhí)行。

圖3 MapReduce框架中執(zhí)行過程的流程

3.2 將匹配方法嵌入到Spark

提出的分解方法不僅適用于MapReduce，還可用于Apache Spark中設(shè)計高效識別框架，如算法1所述。

算法1 對Spark分解的適應(yīng)性的偽代碼輸入RDD廣播輸入的RDD模板RDD模板RDD.GroupByKey()當(dāng)lTIK∈TemplateRDD時,執(zhí)行 當(dāng)lTj∈InputRDD時,執(zhí)行 ps=p({lTik},LIj) psRDD.insert({i, j},ps) 結(jié)束結(jié)束FinalpsRDD=psRDD.reduceByKey(Qp)ScoresRDD=FinalpsRDD.mapValues(Qf)

4 2種經(jīng)典的匹配算法

4.1 細節(jié)點圓柱碼匹配算法

細節(jié)點圓柱碼(minutia cylinder-code，MCC)[12]匹配算法使用有圓柱狀支撐的局部結(jié)構(gòu)。圓柱體包含關(guān)于細節(jié)鄰域的信息，將圓柱體編碼成一個大小為NsNsNd的實數(shù)向量。局部匹配由計算每對圓柱(1個Ti和1個Ij)之間的相似性組成，從而獲得矩陣Γ，其中γ是相似函數(shù)：

(13)

Cappelli等提出了4種計算全局分數(shù)的合并技術(shù)，本文主要研究局部松弛相似度排序(LSSR)。

(14)

(15)

通過平均具有np個最高效率的松弛相似性計算全局分數(shù)。

4.2 Jiang匹配算法

Jiang匹配算法[11]使用基于每個細節(jié)點的Nn個最近領(lǐng)域的局部結(jié)構(gòu)，每個局部結(jié)構(gòu)均可描述為實數(shù)向量，所有局部結(jié)構(gòu)對之間的相似性矩陣都遵循方程(13)的形式。全局匹配包括對局部結(jié)構(gòu)的最佳匹配對進行整理，并根據(jù)這種配對對齊所有其他細節(jié)點。從每一個細節(jié)點中得到一個旋轉(zhuǎn)平移不變向量Fgk。然后，對每一對對齊的細節(jié)點計算匹配確定性級別ml(r,s)：

(16)

最終匹配分數(shù)計算如下：

(17)

5 實驗和分析

通過實驗驗證提出的匹配算法和分解方法性能，并將Jiang匹配算法、MCC匹配算法應(yīng)用于提出的分解框架中進行實驗。實驗中，提出的基于置信度的匹配算法分別在Apache Hadoop和Apache Spark中實現(xiàn)，Jiang匹配算法、MCC匹配算法在MPI中的實現(xiàn)結(jié)果均參考文獻[16]的實驗結(jié)果。

5.1 測試結(jié)果

通過SFinGe軟件[17]生成了具有400 000個模板指紋的數(shù)據(jù)庫。通過采用模板指紋的5 000個附加印模，以及數(shù)據(jù)庫中不匹配的額外5 000個指紋，建立了10 000個輸入指紋集。圖4為部分指紋圖像示例。SFinGe數(shù)據(jù)庫的統(tǒng)計數(shù)據(jù)如表2所示。

圖4 SFinGe數(shù)據(jù)庫部分指紋圖像示例

參數(shù)模板輸入模板指紋數(shù)(nT和nI)400 00010 000局部結(jié)構(gòu)平均數(shù)(m)55.4750.14字節(jié)數(shù)Jiang3.27E+092.42E+07MCC6.38E+107.9E+08

盡管在3種比較框架(MPI、Hadoop和Spark)中使用了相同的算法，但由于浮點運算誤差，所得結(jié)果的精度各不同。對于3種比較框架，表3給出了獲得SFinGe數(shù)據(jù)庫的TPR(真陽性率)。從表3可以看出，3種框架下的值非常相似，只有略微的差異。Jiang匹配算法和MCC匹配算法在MPI框架下的實驗數(shù)據(jù)參考文獻[16]的實驗結(jié)果，通過對比可以看出，提出的分解框架具有良好的可靠性。

表4所示為3種框架下3種匹配算法的平均識別時間。從表4可以看出，相比其他2種匹配算法，本文的基于置信度的匹配算法在這幾種框架中的識別時間方面有很大的優(yōu)勢?？傮w而言，幾種匹配算法嵌入提出的分解框架后，均獲得了較好的識別性能。提出的分解方法能以靈活的方式識別輸入指紋，從而有效地使用輸入局部結(jié)構(gòu)的模板信息。安全丟棄部分分數(shù)增強了匹配過程的可靠性，由于允許對非匹配指紋或非相似指紋部件進行早期檢測，從而減少了計算量。

表3 獲得SFinGe數(shù)據(jù)庫的TPR(FPR為0%)

表4 SFinGe數(shù)據(jù)庫上的平均識別時間 s

表5所示為3種匹配算法嵌入提出的分解框架后在Hadoop中實施時的統(tǒng)計數(shù)據(jù)。從表5可以看出，組合階段得到了較好的優(yōu)化，這是因為傳遞給reducer的部分分數(shù)非常低，從而導(dǎo)致在洗牌階段需要較少的網(wǎng)絡(luò)流量。大部分計算時間用在映射階段，該階段計算所有局部相似點。

表5 使用Hadoop執(zhí)行的統(tǒng)計數(shù)據(jù)

表6所示為Spark中每步的平均時間。需要注意的是，各階段是同時執(zhí)行的，因此總的時間遠低于各個階段的時間總和。首先，在整個計算節(jié)點上實施數(shù)據(jù)庫加載，這樣就可以在考慮加載數(shù)據(jù)大小的情況下，從分布式文件系統(tǒng)中快速完成加載。對于每個指紋，輸入指紋的傳播要花費更多的時間。計算匹配結(jié)果和將結(jié)果寫入HDFS消耗了大量時間，且它們所消耗的時間基本相同。

表6 Spark中每步的平均時間 s

綜合表3～6的測試結(jié)果顯示，3種匹配算法的識別性能均良好，各個步驟的統(tǒng)計數(shù)據(jù)和所用時間均在可接受范圍內(nèi)。由此可見，提出的分解方法具有良好的可靠性。

5.2 提出的分解框架的通用性分析

本文中所提出分解方法的關(guān)鍵是考慮可擴展識別系統(tǒng)，使用SFinGe數(shù)據(jù)庫中多個尺度的子集，利用Hadoop和Spark評估可擴展性。在每種情況下，將輸入指紋的數(shù)目設(shè)置為模板數(shù)的10%，其中一半是冒充身份，最大數(shù)量可達10 000。因此，最大的數(shù)據(jù)庫計算為4×109個匹配。

圖5所示為Hadoop、Spark框架下3種匹配算法的吞吐量與模板指紋數(shù)量之間的關(guān)系。從圖5可以看出，雖然Spark的吞吐量高于Hadoop，但當(dāng)模板數(shù)量增加時，這2個框架呈現(xiàn)出了相同的特性：對于大型數(shù)據(jù)庫，隨著計算時間與通信時間呈比例增加，吞吐量也不斷增加。通過分析在大數(shù)據(jù)框架中的測試結(jié)果可知，提出的分解框架可以較好地適用于3種不同的匹配算法，提出的分解方法具有良好的通用性。

圖5 2種大數(shù)據(jù)框架下3種匹配算法的吞吐量

6 結(jié)束語

本文中提出了一種面向細節(jié)點指紋匹配的通用分解方法，并將其在Apache Hadoop和Apache Spark 2種大數(shù)據(jù)計算框架中進行實現(xiàn)，驗證了該方法的可靠性。將所提出分解方法應(yīng)用于3種匹配算法進行實驗，驗證了分解方法的通用性。綜合可知，先提取出細節(jié)點特征，然后將匹配分數(shù)的計算分解為較低級別的步驟有助于提高匹配過程的靈活性。

在下一步研究中，考慮將提出的分解框架部署于其他的大數(shù)據(jù)或并行計算環(huán)境實現(xiàn)，例如MPI。此外，還可將分解方法應(yīng)用于其他的指紋匹配算法，進一步提升該方法的可靠性和通用性。