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

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

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

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

0　引言

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

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

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

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

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

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

2　稀疏矩陣指紋匹配算法

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

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

（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時(shí)局部表現(xiàn)能力最強(qiáng)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1　總體算法流程圖

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

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

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

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

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

表2　本文算法和其他算法的實(shí)驗(yàn)測(cè)試結(jié)果比較

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

5　結(jié)語(yǔ)

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

［1］劉舒，于瑞華.生物特征識(shí)別中的關(guān)鍵技術(shù)與發(fā)展趨勢(shì)［J］.中國(guó)人民公安大學(xué)學(xué)報(bào)：自然科學(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］王偉希，袁杰，臧炅.基于局部特征的點(diǎn)模式指紋匹配算法［J］.南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，45：18-23

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

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

［6］石光明，劉丹華，高大化等.壓縮感知理論及其研究進(jìn)展［J］.電子學(xué)報(bào)，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)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目（No.PAPD）、2013年江蘇省高等教育教改研究課題（No.2013JSJG155）、

1007-1423（2015）23-0042-04

10.3969/j.issn.1007-1423.2015.23.010

曹中琰（1995-），男，江蘇徐州人，本科，研究方向?yàn)槿斯ぶ悄?/p>

施琳琳（1993-），女，江蘇海門(mén)人，本科，研究方向?yàn)橹悄苄畔⑻幚?/p>

盧恩雪（1994-），女，浙江臺(tái)州人，本科，研究方向?yàn)閿?shù)字信號(hào)處理

陳思達(dá)（1994-），男，福建福州人，本科，主研究方向?yàn)橛?jì)算機(jī)軟件開(kāi)發(fā)

李全彬（1977-），男，山東臨沂人，教師，博士，研究方向?yàn)槿斯ぶ悄?/p>

2015-06-16

2015-08-06

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

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

江蘇省現(xiàn)代教育技術(shù)研究2013重點(diǎn)課題（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.