基于RANSAC策略優化的稀疏矩陣指紋匹配算法

曹中琰，施琳琳，盧恩雪，陳思達，李全彬（江蘇省先進激光材料與器件重點實驗室，江蘇師范大學物理與電子工程學院，徐州　221116）

基于RANSAC策略優化的稀疏矩陣指紋匹配算法

曹中琰，施琳琳，盧恩雪，陳思達，李全彬
（江蘇省先進激光材料與器件重點實驗室，江蘇師范大學物理與電子工程學院，徐州221116）

0　引言

指紋識別技術是生物識別技術中最重要﹑應用最廣泛的技術，具有易采集性、唯一性的突出特點。例如很多大型企事業單位已經用指紋考勤代替了傳統的IC卡、磁卡等考勤方式，從而有效地提升了單位的管理效率，從根本上避免了代打考勤的現象。

指紋匹配算法是自動指紋識別系統的重要研究內容，準確且快速地提高指紋匹配算法是研究的一大熱點。但是指紋數字圖像識別技術仍面臨著很多問題，如識別速度慢，識別成本較高，系統昂貴，系統魯棒性差，識別錯誤率較高等問題，特別是采集指紋的過程中，諸如局部形變、光照條件變化、部分遮擋等因素常常導致同一指紋在不同的圖像中具有較大的差異，這些都是指紋圖像匹配所需要解決的難點［1］。

為了解決現有指紋匹配算法在匹配速度與準確率難以統一的問題，本文提出了基于RANSAC策略優化的稀疏矩陣的指紋匹配算法。

1　指紋匹配算法研究現狀

目前，常用的指紋匹配算法主要分為三種：基于點模式的匹配方法，基于全局結構特征的匹配方法，基于融合特征的匹配方法。其中，以點模式匹配方法研究最多，應用最為廣泛。Ranade和Rosenfeld利用松弛法進行特征點匹配［2］。Ratha等提出一種基于點模式的匹配，用一般的Hough變換來恢復兩幅指印間的位置變換。Jiang等使用定義在局部結構特征間的相似度衡量方法以此來比對兩個模式，而后得到兩個細節點序列間的匹配分數。Wahab等提出一種利用細節點組來定義局部結構特征的方法。王偉希等提出了一種由指紋參考點和參考方向構成極坐標系，用極坐標表示指紋特征信息的新的點模式匹配算法［3］。曹國等通過一系列實驗得出一種快速指紋混合匹配方法。首先我們應該定位指紋的中心點及其方向，然后提取指紋的圖像特征并建立指紋細節點匹配模板，最終應用多級匹配的方法實現了指紋識別［4］。

除了點模式匹配法以外，在全局結構特征匹配方法上，Chen和Sherlock都分別對指紋的拓撲結構進行了研究，基于這些信息進行匹配，得以改善指紋圖像的噪聲、旋轉和變形對識別的干擾。Tan和Bhanu提出作用于遺傳算法的指紋匹配方法，利用了指紋的整體結構信息來尋找不同指紋間的最優變換。在融合匹配算法上，如Prabhakar等人提出基于決策層的融合算法，融合四種匹配算法，在一定程度上提高匹配準確率［5］。

2　稀疏矩陣指紋匹配算法

如果一個矩陣的非零元素相當少，遠遠小于其零元素的數量，而且該矩陣中的非零元素雜亂無章的分布在整個矩陣中，那么該矩陣就是稀疏矩陣。得益于稀疏矩陣計算速度快、存儲容量較小的優點，采用稀疏矩陣可以改善指紋匹配速度。也即通過矩陣分解，取得加強指紋局部化特征的效果。

為了找到恰當的基對矩陣進行分解，本文假設已知非負矩陣V找到適合的非負矩陣因子W與H，確保V≈WH。附加定義U=［uij］=WTW，V=［vij］=HTH然后增加以下3個稀疏性限制條件：

（1）使H最大稀疏化。H必須包括盡可能多的零元素，使W的列向量更富于表現局部特征的能力；

（2）最大化W的局部表現能力。如約束1所述，H的稀疏化和W的局部化能力是息息相關的。這里進一步加強了約束1中的最大稀疏化。當且僅當∑ivij=max時局部表現能力最強；

（3）最大化W的正交性。加約束條件∑i≠juij=min，和約束1比較后，改為∑?i，juij=min。

將上述3個約束合并起來，就可以建立如下的目標函數：

其中，α，β是大于零的常數，最小化算法可以消除它們。通過迭代計算可以得到目標函數的結果。由迭代規則可知，F（X，WH）為非增序列函數，滿足收斂到局部最小點這一要求，其收斂性可以證明。非負矩陣分解的方法在處理數據時，并不假設矩陣V具有稀疏性，但是得到的分解結果具有稀疏性，然后利用分解結果稀疏的特點進行存儲。本方法多用于進行矩陣數據的預處理［6］。

稀疏矩陣匹配算法更加注重指紋圖像的局部特征，由于局部范圍內指紋形變的可控性，因此可以很好地解決指紋圖像的形變問題。但同樣由于僅對局部特征進行匹配，容易造成總體誤匹配率升高。

3　基于RANSAC優化的指紋匹配算法

為了提高匹配準確率，本文通過RANSAC策略進一步優化稀疏矩陣算法。在運用稀疏矩陣匹配算法進行初匹配的基礎上，通過RANSAC策略進一步剔除誤匹配特征點，從而提高整體算法準確率。

RANSAC策略依據一組含有異常數據的樣本數據集，計算得出有效數據的數學模型參數，最終得出有效樣本數據的算法，在1981年由Fishchler和Bolles第一次提出［7］。RANSAC算法的基本思路如下：

（1）從已有樣本集P中選定最小需求的數據樣本，并使用最小數據樣本求出初始模型；

（2）通過初始模型求取問題的約束條件，當數據樣本符合解的約束條件，則稱其為內點，否則稱為外點；

（3）如果內點的數目大于等于設定的閾值，則用內點數重新估計模型參數并結束本輪運算；如果內點的數目小于設定的閾值，則重新在數據集中選取數據樣本，重復上述的步驟；

（4）經過N次采樣，選取包含內點數目最多的模型，并使用這些內點重新計算模型的參數，完成計算。

在通過稀疏矩陣指紋匹配算法進行初匹配之后，減少了總體匹配所需要的特征點。RANSAC算法具有良好的魯棒性，能夠穩定地提取正確的匹配點對，消除誤匹配點對。

本文RANSAC匹配算法的具體步驟如下：

（1）將初匹配得到的匹配點對作為初始數據集，要將初匹配中的誤匹配點對去除。

（2）對輸入指紋特征點集進行平移、旋轉、尺度變換，將初匹配得到的匹配點對用直線連接起來，并計算線段與水平方向的夾角α（i），以及匹配點對方向的夾角β（i），分別對α（i）和β（i）進行統計，將最大的統計值設定為αM和βM的標準值，將α（i）和β（i）分別與αM和βM進行比較，如果誤差在±3°范圍內，則判定連線平行，這兩對匹配點劃分為內點，否則為外點；

（3）如果得到的匹配點對數目大于設定的閾值（本文采用初始匹配點數目的85%作為閾值），則保留本次計算結果。結束計算，使用內點重新估計指紋的變換參數；否則，重復上面步驟；

（4）經過N次采樣，得到N個內點集，從中選取內點數目最多的一次采樣，使用最小二乘法對內點集進行估計，并代入變換公式，求出變換參數，然后再進行一次整體匹配過程，得出最后的匹配點數。當匹配點數大于設定的閾值，判定兩個指紋匹配，否則斷定不匹配。具體算法流程圖如圖1所示：

圖1　總體算法流程圖

4　算法結果及分析

評價算法準確率的主要指標為誤識率（FAR）和拒識率（FFR）。EER代表誤識率和拒識率相等時的值，EER越小，代表指紋匹配算法的準確性越高。

其中error-num表示不該匹配但匹配的次數，reject-num表示該匹配卻沒有匹配的次數，snum表示匹配的總次數。

利用FVC2004指紋數據庫對本文算法進行測試，整個指紋數據庫中共計100枚指紋圖像［9］。算法1為文獻［5］所用的指紋匹配算法，算法2為未用RANSAC策略進行優化的稀疏矩陣匹配算法，算法3為本文所用算法。表1為從數據庫中提取10枚指紋圖像進行測試時，三種算法的表現能力。表2為本文所用算法和未進行優化的稀疏矩陣匹配算法在進行不同數量指紋圖像匹配時，在準確率和匹配速度方面進行的比較。

表1　本文算法和其他算法效果比較

表2　本文算法和其他算法的實驗測試結果比較

從表1可知，本文所使用算法與算法1相比，無論是匹配速度還是匹配精度上都有一定提高。從表2中可以看出，本文所提出的算法在匹配準確率方面有較好表現，同時并未影響算法匹配速度。

5　結語

本文所采用的基于策略優化的稀疏矩陣指紋匹配算法，在不影響匹配速度的情況下，有效提高了系統的匹配準確率。本文為了保證匹配速度，并沒有設置很高的閾值，基于RANSAC算法對于迭代次數的要求，在設置更高閾值的情況下，準確率將會有進一步提高。

［1］劉舒，于瑞華.生物特征識別中的關鍵技術與發展趨勢［J］.中國人民公安大學學報：自然科學版，2006，47（1）：63-65.

［2］Fischler，M.A.，Bolles，R.C.Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography.Communications of the ACM，1981，24（6）：381-395.

［3］王偉希，袁杰，臧炅.基于局部特征的點模式指紋匹配算法［J］.南京大學學報：自然科學版，2009，45：18-23

［4］曹國，毛志紅，梅園.快速的多級指紋混合匹配方法［J］.模式識別與人工智能，2009，22：787-793

［5］于明，皮海龍，王巖.基于k近鄰法和脊線追蹤的指紋匹配算法［J］.吉林大學學報：工學版，2014，44：1806-1810

［6］石光明，劉丹華，高大化等.壓縮感知理論及其研究進展［J］.電子學報，2009，37：1070-1081

［7］Wan，Dingrui，Zhou，Jie.Fingerprint recognition using model-based density map.IEEE Transactions on Image Processing，2006

［8］Cappelli R，Ferrara M，Maltoni D.Fingerprint Verification Competition at IJCB 2011.Biometrics［C］.2011 International Joint Conference on Digital Object Identifier，2011，11（10）：1-6

［9］Jain A K，Prabhakar S，Hong L，et al.Filterbank-based fingerprint matching.IEEE Transactions on Image Processing，2000

Fingerprint Matching；Sparse Matrix；Random Sample Consensus Strategy

Sparse Matrix Fingerprint Matching Algorithm Based on the Strategy Optimization of RANSAC Algorithm

CAO Zhong-yan，SHI Lin-lin，LU En-xue，CHEN Si-da，LI Quan-bin

（Jiangsu Key Laboratory of Advanced Laser Materials and Devices，School of Physics and Electronic Engineering，Jiangsu Normal University，Xuzhou 221116）

江蘇高校優勢學科建設工程資助項目（No.PAPD）、2013年江蘇省高等教育教改研究課題（No.2013JSJG155）、

1007-1423（2015）23-0042-04

10.3969/j.issn.1007-1423.2015.23.010

曹中琰（1995-），男，江蘇徐州人，本科，研究方向為人工智能

施琳琳（1993-），女，江蘇海門人，本科，研究方向為智能信息處理

盧恩雪（1994-），女，浙江臺州人，本科，研究方向為數字信號處理

陳思達（1994-），男，福建福州人，本科，主研究方向為計算機軟件開發

李全彬（1977-），男，山東臨沂人，教師，博士，研究方向為人工智能

2015-06-16

2015-08-06

基于改進點模式指紋匹配算法在匹配速度與匹配準確率上的不足，提出一種新的指紋匹配算法。稀疏矩陣具有計算速度快、儲存容量小的優點，本文將稀疏矩陣應用到指紋匹配算法中，通過稀疏矩陣進行指紋圖像初匹配，并進一步通過RANSAC算法進行總體二次匹配，在提高算法速度的基礎上，維持匹配的準確率。實驗證明，該算法匹配速度快、誤識率低、準確性高，是一種有效實用的匹配算法。

指紋匹配；稀疏矩陣；RANSAC策略

江蘇省現代教育技術研究2013重點課題（No.2013-R-24729）

Aiming at the deficiency of the matching speed and accuracy of the fingerprint matching algorithm based on point pattern，proposes a new fingerprint matching algorithm by discussing the existing algorithms.According to the sparse matrix computing speed and storage capacity of small features，the sparse matrix is applied to the fingerprint matching algorithm to handle initial fingerprint image matching in this paper.And through the RANSAC algorithm for the second time overall matching，to maintain a higher algorithm speed，at the same time，to ensure the accuracy of the matching.The experimental results show that the algorithm has good matching speed，low error rate，high accuracy，and has good performance in all aspects，and it is expected to be a practical and effective matching algorithm.