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

基于RANSAC策略優(yōu)化的稀疏矩陣指紋匹配算法

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

0　引言

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

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

為了解決現(xiàn)有指紋匹配算法在匹配速度與準(zhǔn)確率難以統(tǒng)一的問題，本文提出了基于RANSAC策略優(yōu)化的稀疏矩陣的指紋匹配算法。

1　指紋匹配算法研究現(xiàn)狀

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

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

2　稀疏矩陣指紋匹配算法

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

為了找到恰當(dāng)?shù)幕鶎仃囘M(jìn)行分解，本文假設(shè)已知非負(fù)矩陣V找到適合的非負(fù)矩陣因子W與H，確保V≈WH。附加定義U=［uij］=WTW，V=［vij］=HTH然后增加以下3個稀疏性限制條件：

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

（2）最大化W的局部表現(xiàn)能力。如約束1所述，H的稀疏化和W的局部化能力是息息相關(guān)的。這里進(jìn)一步加強(qiáng)了約束1中的最大稀疏化。當(dāng)且僅當(dāng)∑ivij=max時局部表現(xiàn)能力最強(qiáng)；

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

將上述3個約束合并起來，就可以建立如下的目標(biāo)函數(shù)：

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

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

3　基于RANSAC優(yōu)化的指紋匹配算法

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

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

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

（2）通過初始模型求取問題的約束條件，當(dāng)數(shù)據(jù)樣本符合解的約束條件，則稱其為內(nèi)點，否則稱為外點；

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

（4）經(jīng)過N次采樣，選取包含內(nèi)點數(shù)目最多的模型，并使用這些內(nèi)點重新計算模型的參數(shù)，完成計算。

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

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

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

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

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

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

圖1　總體算法流程圖

4　算法結(jié)果及分析

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

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

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

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

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

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

5　結(jié)語

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

［1］劉舒，于瑞華.生物特征識別中的關(guān)鍵技術(shù)與發(fā)展趨勢［J］.中國人民公安大學(xué)學(xué)報：自然科學(xué)版，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］.南京大學(xué)學(xué)報：自然科學(xué)版，2009，45：18-23

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

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

［6］石光明，劉丹華，高大化等.壓縮感知理論及其研究進(jìn)展［J］.電子學(xué)報，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，F(xiàn)errara 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）

江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目（No.PAPD）、2013年江蘇省高等教育教改研究課題（No.2013JSJG155）、

1007-1423（2015）23-0042-04

10.3969/j.issn.1007-1423.2015.23.010

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

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

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

陳思達(dá)（1994-），男，福建福州人，本科，主研究方向為計算機(jī)軟件開發(fā)

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

2015-06-16

2015-08-06

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

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

江蘇省現(xiàn)代教育技術(shù)研究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.