大數據環境下利用新型FTS的并行細節點指紋匹配通用分解方法

李慶年，胡玉平

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

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

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

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

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

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

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

1 基于細節點特征的指紋匹配

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

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

(1)

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

(2)

這種識別系統的識別時間關于n呈線性增加。因此，當n很大時，識別時間往往過長。

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

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

2.1 新型指紋拓撲結構

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

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

圖1 叉點拓撲結構

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

圖2 端點拓撲結構

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

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

(3)

用以下二值優化問題的解代替該問題的解：

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

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

(4)

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

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

(5)

可以使用下列二值優化問題的解代替該問題的解：

(6)

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

2.3 匹分解法

(7)

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

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

(8)

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

(9)

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

3 匹配方法的并行化

3.1 將匹配方法嵌入到MapReduce

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

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

(10)

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

(11)

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

(12)

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

圖3 MapReduce框架中執行過程的流程

3.2 將匹配方法嵌入到Spark

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

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

4 2種經典的匹配算法

4.1 細節點圓柱碼匹配算法

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

(13)

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

(14)

(15)

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

4.2 Jiang匹配算法

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

(16)

最終匹配分數計算如下：

(17)

5 實驗和分析

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

5.1 測試結果

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

圖4 SFinGe數據庫部分指紋圖像示例

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

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

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

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

表4 SFinGe數據庫上的平均識別時間 s

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

表5 使用Hadoop執行的統計數據

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

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

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

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

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

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

圖5 2種大數據框架下3種匹配算法的吞吐量

6 結束語

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

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