艾 樂(lè)，張志忠

1.中國(guó)人民公安大學(xué) 刑事科學(xué)技術(shù)學(xué)院，北京 100038

2.中國(guó)科學(xué)院 自動(dòng)化研究所 復(fù)雜系統(tǒng)管理與控制國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190

指紋三角區(qū)域特征點(diǎn)融合匹配STSF算法研究*

艾 樂(lè)1+，張志忠2

1.中國(guó)人民公安大學(xué) 刑事科學(xué)技術(shù)學(xué)院，北京 100038

2.中國(guó)科學(xué)院 自動(dòng)化研究所 復(fù)雜系統(tǒng)管理與控制國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190

AI Le,ZHANG Zhizhong.Study of feature fusion matching STSF algorithm for partial delta fingerprint. Journal of Frontiers of Computer Science and Technology,2017,11(6)：950-958.

目前大部分指紋自動(dòng)識(shí)別系統(tǒng)（automatic fingerprint identification systems，AFIS）所采用的特征點(diǎn)匹配算法需以準(zhǔn)確提取特征點(diǎn)為前提，這些算法在面對(duì)存在高度畸變且殘缺不全的現(xiàn)場(chǎng)指紋時(shí)，往往難以準(zhǔn)確識(shí)別指紋圖像。在相似三角形匹配算法的基礎(chǔ)上，研究了SIFT（scale invariant feature transform）特征點(diǎn)與二級(jí)特征點(diǎn)之間的位置關(guān)系，克服了相似三角形之間尺度不一的問(wèn)題。此外，提出了一種基于貝葉斯統(tǒng)計(jì)推斷的相似三角形與SIFT融合算法（similar triangle SIFT feature，STSF）。實(shí)驗(yàn)結(jié)果表明，STSF算法能夠有效提升殘缺指紋匹配的精度和計(jì)算效率。

指紋匹配；特征融合；殘缺指紋

1 引言

指紋由于其人各不同、終身基本不變的性質(zhì)，被廣泛用于法庭科學(xué)領(lǐng)域及商用、民用人身識(shí)別領(lǐng)域。指紋自動(dòng)識(shí)別系統(tǒng)（automatic fingerprint identification systems，AFIS）的應(yīng)用為指紋的儲(chǔ)存、識(shí)別、快速檢索和比對(duì)提供了巨大幫助。AFIS中的核心指紋匹配算法大致可分為基于相關(guān)性、基于特征點(diǎn)位置關(guān)系或無(wú)特征點(diǎn)算法3種。相關(guān)性匹配算法（correlationbased matching）[1-2]即將兩枚指紋圖像疊加并計(jì)算位移和扭轉(zhuǎn)角度?；谔卣鼽c(diǎn)匹配算法是分別提取兩幅指紋圖片中的特征點(diǎn)，從而進(jìn)行特征點(diǎn)查詢(xún)。無(wú)特征點(diǎn)匹配算法（non-minutiae feature based matching）[3-4]使用的是紋線(xiàn)流向、類(lèi)型等非二級(jí)特征。目前大部分AFIS系統(tǒng)采用的是特征點(diǎn)匹配算法，這是由于其更符合指紋學(xué)界對(duì)指紋鑒定所用二級(jí)特征的理解。此類(lèi)算法都需要以準(zhǔn)確提取特征點(diǎn)為前提，面對(duì)現(xiàn)場(chǎng)指紋時(shí)，需要克服以下幾個(gè)問(wèn)題：（1）即使是同一個(gè)手指，每次遺留指紋時(shí)由于受力的方向、大小、作用方式、承痕客體表面情況、附著物等多種條件影響，很難形成完全一樣的兩枚指紋，相同特征點(diǎn)也必然會(huì)存在不同程度的位移、形變等。因此基于特征點(diǎn)的匹配算法需要具備抗畸變能力。（2）現(xiàn)場(chǎng)指紋多為局部指紋，二級(jí)特征點(diǎn)數(shù)量有限，如何僅依靠有限的特征點(diǎn)，在千萬(wàn)級(jí)數(shù)據(jù)庫(kù)中檢索出同源指紋，并使其排序靠前。

有人為此提出了特征點(diǎn)組匹配算法[5]，用于說(shuō)明特征點(diǎn)的幾何位置關(guān)系，其缺點(diǎn)是需要預(yù)估指紋變形程度。在此基礎(chǔ)上，有學(xué)者提出了相似三角形方法（similar vector triangle matching algorithm）[6]，不必依賴(lài)指紋中心點(diǎn)及三角點(diǎn)，且具有一定的抗位移和形變的能力，但仍需準(zhǔn)確提取特征點(diǎn)和相當(dāng)多的特征點(diǎn)數(shù)目。Bazen等人[7]提出了一種優(yōu)先于整體定位的方法，將某一特征點(diǎn)及其鄰近的兩個(gè)特征點(diǎn)形成一個(gè)組合關(guān)系，以此為基準(zhǔn)在檔案指紋中尋找相似的組合結(jié)構(gòu)。雖然特征組中可能存在偽特征，但統(tǒng)計(jì)所有特征點(diǎn)集后計(jì)算最小方差，即可消除誤差得到最優(yōu)結(jié)果，基于特征點(diǎn)組的定位方法還可用于變形指紋，消除系統(tǒng)算法中的誤識(shí)率（false acceptance rate）。隨后又有人提出了完全獨(dú)立于整體特征定位的局部特征點(diǎn)定位方法，所利用的均為局部特征點(diǎn)組合關(guān)系[8-9]。Abraham等人[10]提出了一種形狀及方向混合描述符（hybrid shape and orientation descriptor），可以有效過(guò)濾可疑特征組，同時(shí)利用紋線(xiàn)方向提高匹配得分。此種方法尤其適用于缺少中心點(diǎn)或三角點(diǎn)的殘缺指紋。

SIFT（scale invariant feature transform）特征點(diǎn)作為通用圖像匹配算法的基礎(chǔ)，反映了圖像的局部灰度結(jié)構(gòu)，具有很好的尺度、平移和旋轉(zhuǎn)不變性，即使在指紋圖片存在放大或縮小、扭曲、位移時(shí)，也可保持穩(wěn)定，且SIFT特征點(diǎn)數(shù)目眾多，因此可用于殘缺指紋的特征點(diǎn)提取工作。但SIFT特征也存在缺點(diǎn)：易受指紋圖片背景影響，難以處理指紋圖像的畸變問(wèn)題，會(huì)形成偽特征，錯(cuò)誤率也隨之提高。因此有人提出將幾種特征點(diǎn)提取方法綜合運(yùn)用以減低錯(cuò)誤率，提高匹配度的方法。如Malathi等人[11]提出將提取的汗孔特征和SIFT特征匹配得分進(jìn)行加權(quán)，可以大大提升殘缺指紋比對(duì)的準(zhǔn)確率，但是當(dāng)圖像尺寸降低時(shí)，匹配精度降低。

三角特征模式匹配作為特征點(diǎn)匹配的主流算法，具有不錯(cuò)的抗畸變能力[12]，但對(duì)于殘缺指紋，能利用的特征點(diǎn)數(shù)目較少，往往匹配上具有相似比例但大小不同的三角特征，如圖1所示。另一方面，SIFT特征點(diǎn)具有旋轉(zhuǎn)、平移和尺度不變性，且數(shù)目眾多，但會(huì)出現(xiàn)計(jì)算復(fù)雜度高，偽特征點(diǎn)多等問(wèn)題，直接進(jìn)行SIFT特征點(diǎn)匹配錯(cuò)誤率高。因此本文旨在將二者結(jié)合起來(lái)，設(shè)計(jì)更好的匹配算法。犯罪現(xiàn)場(chǎng)能夠提取到的多是犯罪分子抓取、握取物品遺留的手指?jìng)?cè)面指紋，其中三角區(qū)域二級(jí)特征點(diǎn)出現(xiàn)頻率較高，三角點(diǎn)易辨識(shí)。因此本文針對(duì)指紋三角區(qū)域開(kāi)展研究，提升特征點(diǎn)匹配的準(zhǔn)確性，減少AFIS檢索時(shí)間，提高工作效率。

Fig.1 Matching vector triangle of two different fingerprints with different scales圖1 兩枚異源指紋匹配的尺度不一三角特征

2 算法與模型

2.1 相似三角形匹配算法

假設(shè)現(xiàn)場(chǎng)指紋上二級(jí)特征點(diǎn)數(shù)量為P={P1,P2,…,Pn}，檔案指紋上二級(jí)特征點(diǎn)數(shù)量為Q={Q1,Q2,…,Qn}，每個(gè)特征點(diǎn)都有對(duì)應(yīng)的橫縱坐標(biāo)、方向x、y、θ。設(shè)Pi和Qi分別表示來(lái)自現(xiàn)場(chǎng)指紋和檔案指紋上的某一點(diǎn)。對(duì)每一個(gè)由任意3個(gè)P點(diǎn)組成的三角形，依據(jù)以下條件尋找檔案指紋中的相似三角形。

（1）將三角形3條邊按長(zhǎng)短由低到高排列(Lp1,Lp2,Lp3)(Lq1,Lq2,Lq3)，根據(jù)邊長(zhǎng)，調(diào)整3個(gè)節(jié)點(diǎn)的順序(Ap,Bp,Cp)(Aq,Bq,Cq)。

（2）計(jì)算3條邊的形變程度：

（3）計(jì)算角度差：

設(shè)T1為邊長(zhǎng)形變的閾值，T2為角度形變的閾值，若滿(mǎn)足 ||K1-K2

旋轉(zhuǎn)角度為：

每個(gè)特征點(diǎn)的橫縱坐標(biāo)即可進(jìn)行霍夫變換：

計(jì)算得到匹配后的特征點(diǎn)坐標(biāo)x′、y′、θ′，當(dāng)歐式距離小于某一閾值時(shí)，認(rèn)為兩個(gè)特征點(diǎn)匹配。根據(jù)兩幅圖像匹配的特征點(diǎn)個(gè)數(shù)計(jì)算得分，在實(shí)驗(yàn)中采用了常見(jiàn)的但實(shí)驗(yàn)效果不如直接采用特征點(diǎn)個(gè)數(shù)作為匹配得分，這是因?yàn)闅埲敝讣y特征點(diǎn)數(shù)目較少，匹配點(diǎn)個(gè)數(shù)能夠更好反應(yīng)二者的匹配程度。

上述方法雖然能夠很好地解決特征點(diǎn)三角形形狀相似的問(wèn)題，但是難以解決相似三角形尺度不一的問(wèn)題。由于指紋圖像的畸變問(wèn)題，如果設(shè)置一個(gè)比較緊的形變閾值，會(huì)丟失很多正確的匹配三角形對(duì)，同時(shí)設(shè)置比較大的形變閾值會(huì)浪費(fèi)大量的計(jì)算資源。

文獻(xiàn)[13]提出的歐氏距離矩陣分析（Euclidean distance matrix analysis，EDMA）方法認(rèn)為，從兩個(gè)不同的圖形中尋找地標(biāo)點(diǎn)需要借助相對(duì)的位置關(guān)系，能夠有效地克服旋轉(zhuǎn)、尺度等問(wèn)題。大量的指紋圖像檢索方法[14]也都依據(jù)特征點(diǎn)位置關(guān)系進(jìn)行建模，達(dá)到快速精準(zhǔn)匹配的目的，然而殘缺指紋匹配中難以尋找大量的二級(jí)特征點(diǎn)，因此本文希望通過(guò)SIFT特征點(diǎn)與二級(jí)特征點(diǎn)之間的位置關(guān)系進(jìn)行建模，解決匹配三角形對(duì)中出現(xiàn)的大量的尺度不一的情形。計(jì)算二級(jí)特征點(diǎn)三角形內(nèi)SIFT數(shù)目Nij，計(jì)算方法可由簡(jiǎn)單的射線(xiàn)法完成，如圖2所示。如果二級(jí)特征點(diǎn)三角形內(nèi)的SIFT數(shù)目相差較多，則可直接過(guò)濾三角形對(duì)。實(shí)驗(yàn)結(jié)果表明，不僅在精度上還是在時(shí)間效率上算法性能都有所提升。

Fig.2 Ray methods for calculating the number of SIFT圖2 射線(xiàn)法SIFT數(shù)目計(jì)算方法

2.2 SIFT特征點(diǎn)匹配算法

SIFT算法一般采用128維的統(tǒng)計(jì)直方圖作為描述符。指紋圖像由于脊線(xiàn)縱橫，灰度邊緣信息豐富，特征點(diǎn)數(shù)目往往有上千個(gè)，兩幅指紋圖像的SIFT特征點(diǎn)的匹配，需要耗費(fèi)大量時(shí)間，剔除錯(cuò)誤匹配點(diǎn)時(shí)間消耗也會(huì)大大增加，對(duì)于大規(guī)模指紋匹配算法并不適用。但是殘缺指紋由于受采集場(chǎng)景的條件限制，獲取的特征點(diǎn)數(shù)目有限，SIFT算子需要更強(qiáng)的魯棒性，才能滿(mǎn)足匹配需求。另一方面，殘缺指紋圖像所需的紋理特征都是基于脊線(xiàn)走勢(shì)、變化的微小細(xì)節(jié)特征，因此只選取尺度和極值在適當(dāng)范圍內(nèi)的SIFT算子作為有效特征點(diǎn)。本文基于歐式度量進(jìn)行相似性匹配，運(yùn)用樹(shù)結(jié)構(gòu)進(jìn)行搜索匹配，使用Ransac算法對(duì)SIFT特征點(diǎn)進(jìn)行篩選，剔除不匹配特征點(diǎn)。SIFT特征點(diǎn)匹配得分按照下列方法計(jì)算：

2.3 STSF融合算法

SIFT特征點(diǎn)反應(yīng)了指紋圖像的脊線(xiàn)紋理區(qū)別，而二級(jí)特征點(diǎn)相似三角形匹配算法與指紋專(zhuān)家鑒定方法類(lèi)似，依照二級(jí)特征點(diǎn)之間的幾何位置關(guān)系確定指紋圖像關(guān)系。從兩種匹配方式中提取互補(bǔ)信息，能夠有效提升殘缺指紋的匹配準(zhǔn)確性。本文運(yùn)用貝葉斯統(tǒng)計(jì)的方法來(lái)獲取二者的互補(bǔ)信息[15]。

設(shè)指紋圖像i與指紋圖像j的兩種匹配得分為scoreSIFT、scoretriangle，則指紋圖像i與指紋圖像j在當(dāng)前的匹配分?jǐn)?shù)下，匹配的概率為：

其中，G表示指紋圖像i與指紋圖像j真正匹配；I表示指紋圖像i與指紋圖像j不匹配。該后驗(yàn)概率表明在不同特征空間下的得分置信度。因此最終的得分為：

weight為權(quán)重函數(shù)，定義為：

直觀來(lái)說(shuō)，p(G|score)越高，當(dāng)前得分下真正匹配的概率越高，當(dāng)前特征空間的得分權(quán)重應(yīng)該提高；反之p(G|score)越低，則說(shuō)明二者并不是真正的匹配，當(dāng)前特征空間的得分權(quán)重應(yīng)該降低。

p(G|score)的概率估計(jì)有多種方式，可以在模型中加入先驗(yàn)知識(shí)，但為了便于分析，取p(G)=p(I)。本文采用基于統(tǒng)計(jì)直方圖的經(jīng)驗(yàn)估計(jì)，定義為：

其中，NG(score)為訓(xùn)練集中當(dāng)前得分下直方圖箱寬區(qū)間內(nèi)正確匹配的個(gè)數(shù)；NI(score)為訓(xùn)練集當(dāng)前得分下直方圖箱寬區(qū)間內(nèi)錯(cuò)誤匹配的個(gè)數(shù)。

3 數(shù)據(jù)集選取及評(píng)價(jià)指標(biāo)

為了驗(yàn)證特征點(diǎn)融合匹配算法的有效性，本文選取公開(kāi)數(shù)據(jù)集FVC2002指紋庫(kù)進(jìn)行實(shí)驗(yàn)驗(yàn)證。不僅如此，本文還模擬殘缺指紋的遺留環(huán)境，選取特定三角區(qū)域指紋作為待匹配圖像進(jìn)行指紋圖像匹配。

3.1 數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

本文算法在Matlab 2015b進(jìn)行實(shí)驗(yàn)，操作系統(tǒng)為Ubuntu 14.04,模型運(yùn)行環(huán)境為Intel Xeon E5-2630@ 2.30 GHz，32 GB內(nèi)存。選取的數(shù)據(jù)集來(lái)自FVC指紋競(jìng)賽，它提供來(lái)自不同的傳感器采集的4個(gè)指紋數(shù)據(jù)庫(kù)，該數(shù)據(jù)集可用于科學(xué)指紋實(shí)驗(yàn)的匹配、檢索等。本文對(duì)小規(guī)模數(shù)據(jù)集FVC2002指紋庫(kù)DB_1、DB_2進(jìn)行了測(cè)試，它包含10枚不同手指的8次不同采樣。

本文不僅在公開(kāi)數(shù)據(jù)集上進(jìn)行測(cè)試，還為了模擬真實(shí)犯罪情景，尤其是針對(duì)案發(fā)現(xiàn)場(chǎng)遺留的犯罪指紋進(jìn)行測(cè)試。本文仿照實(shí)際案件中遺留三角區(qū)域指紋形成力度與角度，采用油墨捺印的方法采集，運(yùn)用三星SCX-4100傳感器進(jìn)行掃描保存，生成300dpi指紋圖像數(shù)據(jù)，如圖3所示。真實(shí)數(shù)據(jù)在采集過(guò)程中，選取的格式一致，但大小不一。為了增強(qiáng)指紋圖像的對(duì)比度，并且使算法具有普適性，對(duì)指紋庫(kù)中的指紋圖像只進(jìn)行直方圖均衡化處理，并未做其他處理。

Fig.3 Partial fingerprints simulating real case圖3 仿照現(xiàn)場(chǎng)條件制作的殘缺指紋

3.2 特征提取

由于殘缺指紋圖像的質(zhì)量普遍不高，而二級(jí)特征點(diǎn)提取的準(zhǔn)確性又關(guān)乎匹配算法的性能，本文采用二級(jí)特征點(diǎn)提取算法[10]，主要步驟包括：圖像增強(qiáng)，制作模板，尋找特征點(diǎn)，剔除錯(cuò)誤匹配。提取結(jié)果如圖4所示。本文還測(cè)試了算法[16]，但是與前者相比，提取速度有所提升，但精確度不高。

Fig.4 Schematic diagram of minutiae extraction圖4 特征點(diǎn)提取效果示意圖

SIFT特征點(diǎn)運(yùn)用公開(kāi)的VLFeat庫(kù)[17]進(jìn)行提取，在提取之前只進(jìn)行了直方圖均衡化處理。由于殘缺指紋圖像的紋理特征是基于脊線(xiàn)走勢(shì)、變化的細(xì)節(jié)特征，并且為了減少計(jì)算量，文獻(xiàn)[18]指出了尺度參數(shù)大于3.5的SIFT特征點(diǎn)對(duì)匹配精度并沒(méi)有提升作用，故本文只選取尺度參數(shù)小于3.5的SIFT特征點(diǎn)。此外，為了保證不同指紋圖像提取到的SIFT數(shù)目相近，同時(shí)保留顯著的SIFT特征點(diǎn)，因此設(shè)置峰值閾值去除低對(duì)比度特征點(diǎn)。峰值閾值在FVC2002數(shù)據(jù)庫(kù)取0.03[18]。該閾值對(duì)最后的匹配精度影響較小，但是能加快匹配的速度。特征提取時(shí)間如表1所示。

Tabel 1 Comparison of features extraction time表1 特征提取時(shí)間比較 s

3.3 評(píng)價(jià)指標(biāo)

本文旨在幫助現(xiàn)有指紋自動(dòng)識(shí)別系統(tǒng)提升匹配精度，輔助公安部門(mén)從大規(guī)模指紋庫(kù)中識(shí)別出罪犯指紋，提升匹配得分的置信度，因此本文選取的評(píng)價(jià)指標(biāo)與FVC競(jìng)賽中的匹配算法標(biāo)準(zhǔn)指標(biāo)略有不同。在FVC數(shù)據(jù)庫(kù)中，不僅給出了平均拒識(shí)率（false rejection rate，F(xiàn)RR）、誤識(shí)率（false accept rate，F(xiàn)AR）。還將每一幅圖像作為查詢(xún)，定義評(píng)價(jià)指標(biāo)為：

其中，NC為排序前8幅圖像中正確匹配的個(gè)數(shù)，該指標(biāo)可以驗(yàn)證真正匹配的指紋是否出現(xiàn)在候選指紋列表前列。在真實(shí)三角圖像數(shù)據(jù)中，由于每一幅圖像只有一幅圖像匹配，故類(lèi)似地選取rank10-error作為評(píng)價(jià)指標(biāo)。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 FVC2002數(shù)據(jù)集

本文首先在FVC2002的DB_1、DB_2數(shù)據(jù)集上進(jìn)行了測(cè)試，表2給出了基于相似三角形的匹配算法和基于SIFT匹配算法的查詢(xún)結(jié)果。為了衡量模型的性能，本文給出的算法參數(shù)都經(jīng)過(guò)柵欄搜索。由表2可以看出，相似三角形算法與SIFT匹配算法性能相近，而本文提出的改進(jìn)三角形算法提升了算法[10]的性能，但提升效果有限。這說(shuō)明指紋圖像在采集過(guò)程中的旋轉(zhuǎn)、平移和畸變，使得匹配算法并不能很好地區(qū)分出真正匹配的指紋。但如圖5所示，基于SIFT特征點(diǎn)與基于相似三角形的匹配算法的搜索排序結(jié)果并不相同，即便基于相似三角形的算法效果弱于基于SIFT特征點(diǎn)的算法，但基于SIFT特征點(diǎn)算法匹配靠前的是紋理特征相近的圖片，而基于相似三角形算法匹配的圖片是二級(jí)特征點(diǎn)類(lèi)似的圖像，這意味著如果能從不同特征空間提取互補(bǔ)信息，能夠有效提升殘缺指紋的匹配準(zhǔn)確性。

Tabel 2 Result of four kinds of algorithms on FVC2002表2 FVC2002數(shù)據(jù)庫(kù)中4種算法結(jié)果比較

Fig.5 Relation graph of rank and accuracy on FVC2002 DB_2圖5 FVC2002 DB_2數(shù)據(jù)庫(kù)排序位置和準(zhǔn)確率關(guān)系圖

基于此，本文提出了STSF融合算法，在該次試驗(yàn)中，分別選取FVC2002的DB_2、DB_1互相作為訓(xùn)練集和測(cè)試集。FVC2002 DB_2數(shù)據(jù)集與DB_1類(lèi)似，除在圖像分辨率上略有不同之外，與DB_1基本類(lèi)似，因此選取其作為訓(xùn)練集。實(shí)驗(yàn)結(jié)果表明，STSF算法在兩個(gè)數(shù)據(jù)集上提升了接近5%的性能。

為了進(jìn)一步對(duì)比不同指紋匹配得分與算法排序的關(guān)系，如圖5、圖6所示，本文給出了基于相似三角形、改進(jìn)相似三角形、SIFT特征點(diǎn)以及STSF算法排序位置與匹配個(gè)數(shù)的關(guān)系。從圖中可以看出，STSF算法明顯好于其他算法，并且隨著排序數(shù)目的增加，STSF算法仍然明顯優(yōu)于其他算法，說(shuō)明STSF融合算法能夠有效判別不同特征空間得分的置信度，進(jìn)而提升得分函數(shù)的效能。

Fig.6 Relation graph of rank and accuracy on FVC2002 DB_1圖6 FVC2002 DB_1數(shù)據(jù)庫(kù)排序位置和準(zhǔn)確率關(guān)系圖

此外，給出了兩個(gè)數(shù)據(jù)庫(kù)上算法的FAR率和FRR率結(jié)果，如圖7、圖8、圖9所示。實(shí)驗(yàn)表明，STSF能有效降低FAR率和FRR率。圖10為不同特征下指紋查詢(xún)結(jié)果。

Fig.7 FAR-FRR result of similar triangle algorithm on DB_1圖7 DB_1中相似三角形算法的FAR-FRR圖

4.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)結(jié)果

Fig.8 FAR-FRR result of SIFT algorithm on DB_1圖8 DB_1中SIFT算法的FAR-FRR圖

Fig.9 FAR-FRR result of STSF algorithm on DB_1圖9 DB_1中STSF算法的FAR-FRR圖

為了進(jìn)一步說(shuō)明本文算法在殘缺指紋匹配上的有效性，選取真實(shí)采集的三角指紋數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。殘缺三角指紋共有66個(gè)，將殘缺指紋與完整指紋進(jìn)行匹配，其中完整指紋包含51個(gè)正確匹配圖像和49個(gè)錯(cuò)誤匹配圖像。與FVC2002數(shù)據(jù)集相比，采集的三角指紋畸變程度更高，圖像清晰度更低。為了對(duì)比STSF算法的有效性，首先對(duì)比了全部66個(gè)查詢(xún)圖像的實(shí)驗(yàn)結(jié)果，由于測(cè)試數(shù)據(jù)有限，只選取了排序前10中出現(xiàn)的排序結(jié)果，實(shí)驗(yàn)結(jié)果如表3所示。由表3中可以看出，基于SIFT特征點(diǎn)匹配的算法和基于相似三角形的算法性能大幅降低。還對(duì)比了當(dāng)前點(diǎn)匹配效果最好的算法HSOD（hybrid shape and orientation descriptor）[10]，其算法的性能大大優(yōu)于SIFT算法和基于改進(jìn)的相似三角形算法，然而計(jì)算復(fù)雜度過(guò)高，每?jī)煞讣y圖像平均匹配時(shí)間達(dá)到40 s，是本文改進(jìn)相似三角形算法的80倍，是SIFT匹配算法的285倍，不能滿(mǎn)足實(shí)際需求。

在進(jìn)行權(quán)重估計(jì)時(shí)采用了非參數(shù)統(tǒng)計(jì)方法——parzen窗估計(jì)算法。其算法復(fù)雜度主要由兩部分組成，包括O(M)和O(n2)，其中M為匹配次數(shù)，n為直方圖箱寬。在FVC2002數(shù)據(jù)和真實(shí)數(shù)據(jù)中，n2>>M，因此算法復(fù)雜度為O(n2)。

Fig.10 Fingerprint search results on different features圖10 不同特征下指紋查詢(xún)結(jié)果圖

Table 3 Results of three algorithms on real database表3 真實(shí)數(shù)據(jù)集中3種算法結(jié)果比較

為了進(jìn)一步說(shuō)明STSF算法的有效性，將真實(shí)采集的數(shù)據(jù)平分形成訓(xùn)練集和測(cè)試集。

不需要訓(xùn)練集的算法直接在測(cè)試集上進(jìn)行算法性能評(píng)估。STSF算法只有一個(gè)參數(shù)，即直方圖參數(shù)估計(jì)的箱體寬度，參數(shù)與算法性能的關(guān)系如圖11所示。STSF算法能顯著提升改進(jìn)相似三角形和SIFT匹配特征點(diǎn)的匹配準(zhǔn)確度，即便在改進(jìn)相似三角形和SIFT特征點(diǎn)匹配算法性能相對(duì)較差的情況下，STSF算法也能顯著提升匹配算法的性能，達(dá)到了與HSOD算法相差不多的結(jié)果。此外，還將STSF算法運(yùn)用在HSOD和SIFT匹配算法上，即便在SIFT算法匹配性能十分差的情況下，貝葉斯判別算法也能提升算法的有效性，說(shuō)明本文提出的STSF算法具有一定的魯棒性。

Fig.11 Partial fingerprint searching result and histogram bin size圖11 真實(shí)殘缺指紋查詢(xún)結(jié)果與直方圖箱寬結(jié)果圖

5 結(jié)束語(yǔ)

針對(duì)殘缺指紋的匹配識(shí)別問(wèn)題，由于指紋圖像受采集環(huán)境影響，圖像模糊，全局特征信息不足。因此，本文試圖利用紋理信息和二級(jí)特征點(diǎn)信息進(jìn)行匹配融合。由于不同特征空間的得分函數(shù)尺度不一，利用貝葉斯推斷的方法能有效估計(jì)不同特征空間相似度的置信度，并依據(jù)此置信度進(jìn)行特征融合。最后，選取數(shù)據(jù)集FVC2002和真實(shí)采集數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，提取相應(yīng)的SIFT紋理特征和二級(jí)特征點(diǎn)作為匹配特征，試圖從不同特征空間尋找真實(shí)匹配圖像。實(shí)驗(yàn)結(jié)果表明：（1）紋理特征點(diǎn)空間和二級(jí)特征點(diǎn)空間反映了指紋圖像的不同側(cè)面，如果能提取二者的互補(bǔ)信息，能有效提升算法性能。（2）運(yùn)用概率估計(jì)的方法能夠有效判別當(dāng)前特征空間得分的置信度，依據(jù)此置信度進(jìn)行貝葉斯融合能夠有效提升匹配算法的性能。

[1]Paulino A A,Feng Jianjiang,Jain A K.Latent fingerprint matching using descriptor-based Hough transform[J].IEEE Transactions on Information Forensics and Security,2013,8 (1):31-45.

[2]Fu Xiang,Feng Jufu.Minutia tensor matrix:a new strategy for fingerprint matching[J].PloS One,2015,10(3):e0118910.

[3]Singh V,Elamvazuthi I.Fingerprint matching algorithm for poor quality Images[J].The Journal of Engineering,2015,1. doi:10.1049/joe.2014.0247.

[4]Nanni L,Lumini A.Descriptors for image-based fingerprint matchers[J].Expert Systems with Applications,2009,36 (10):12414-12422.

[5]Cappelli R,Ferrara M,Maltoni D.Fingerprint indexing based on minutia cylinder-code[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(5):1051-1057.

[6]Zheng Jiande,Gao Yuan,Zhang Mingzhi.Fingerprint matching algorithm based on similar vector triangle[C]//Proceedings of the 2nd International Congress on Image and Signal Processing,Tianjin,China,Oct 17-19,2009.Piscataway,USA:IEEE,2009:1-6.

[7]Bazen A M,Gerez S H.Fingerprint matching by thin-plate spline modelling of elastic deformations[J].Pattern Recognition,2003,36(8):1859-1867.

[8]Kisel A,Kochetkov A,Kranauskas J.Fingerprint minutiae matching without global alignment using local structures[J]. Informatica,2008,19(1):31-44.

[9]Abraham J,Champod C,Lennard C,et al.Spatial analysis of corresponding fingerprint features from match and close non-match populations[J].Forensic Science International, 2013,230(1/3):87-98.

[10]Abraham J,Kwan P,Gao Junbin.Fingerprint matching using a hybrid shape and orientation descriptor[M]//Yang Jucheng. State of the Art in Biometrics.Rijeka,Croatia:Intech, 2011:25-56.

[11]Malathi S,Meena C.Improved partial fingerprint matching based on score level fusion using pore and SIFT features [C]//Proceedings of the 2011 International Conference on Process Automation,Control and Computing,Coimbatore, India,Jul 20-22,2011.Piscataway,USA:IEEE,2011:695-698.

[12]Bhanu B,Tan Xuejun.Fingerprint indexing based on novel features of minutiae triplets[J].IEEE Transactions on PatternAnalysis and Machine Intelligence,2003,25(5):616-622.

[13]Lele S,Richtsmeier J T.Euclidean distance matrix analysis: a coordinate-free approach for comparing biological shapes using landmark data[J].American Journal of Physical Anthropology,1991,86(3):415-427.

[14]Jayaraman U,Gupta A K,Gupta P.An efficient minutiae based geometric hashing for fingerprint database[J].Neurocomputing,2014,137(5):115-126.

[15]Choi H,Nagar A,Jain A K.On the evidential value of fingerprints[C]//Proceedings of the 2011 International Joint Conference on Biometrics,Washington,Oct 11-13,2011.Piscataway,USA:IEEE,2011:575-582.

[16]Jain A,Hong Lin,Bolle R.On-line fingerprint verification[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(4):302-314.

[17]Vedaldi A,Fulkerson B.VLFeat:an open and portable library of computer vision algorithms[C]//Proceedings of the 18th International Conference on Multimedia,Firenze,Italy,Oct 25-29,2010.New York:ACM,2010:1469-1472.

[18]Shuai Xin,Zhang Chao,Hao Pengwei.Fingerprint indexing based on composite set of reduced SIFT features[C]//Proceedings of the 19th International Conference on Pattern Recognition,Tampa,USA,Dec 8-11,2008.Piscataway,USA: IEEE,2008:2877-2880.

艾樂(lè)（1990—），女，北京人，2013年于湖北中醫(yī)藥大學(xué)獲得碩士學(xué)位，現(xiàn)為中國(guó)人民公安大學(xué)博士研究生，主要研究領(lǐng)域?yàn)樾淌驴茖W(xué)技術(shù)痕跡檢驗(yàn)。

ZHANG Zhizhong was born in 1991.He is a Ph.D.candidate at Institute of Automation,Chinese Academy of Sciences.His research interests include pattern recognition,computer vision and machine learning.

張志忠（1991—），男，杭州人，中國(guó)科學(xué)院自動(dòng)化研究所博士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，計(jì)算機(jī)視覺(jué)，機(jī)器學(xué)習(xí)。

Study of Feature Fusion Matching STSFAlgorithm for Partial Delta Fingerprint*

AI Le1+,ZHANG Zhizhong2
1.Institute of Criminal Science and Technology,People?s Public Security University of China,Beijing 100038,China
2.State Key Laboratory of Management and Control for Complex Systems,Institute of Automation,Chinese Academy of Sciences,Beijing 100190,China
+Corresponding author:E-mail:zhuanmentianshu@163.com

Most of the fingerprint matching algorithms used in automatic fingerprint identification systems(AFIS) are based on the accurate extraction of minutiae.However,when these methods are used to deal with highly distorted, rotational,and usually partial fingerprints collected from crime screen,their performance drops significantly.On the basis of similar triangle matching algorithm,this paper conquers scale problem by finding the positional relationship between SIFT(scale invariant feature transform)feature and second level feature.In addition,this paper also proposes a Bayesian statistical inference method to fuse the two kinds of algorithms,which is named as similar triangle SIFT feature(STSF)algorithm.The experimental results show that STSF algorithm effectively increases the precision and efficiency of partial fingerprints matching.

fingerprint matching;feature fusion;partial fingerprint

born in 1990.She

the M.S.degree from Hubei University of Chinese Medicine in 2013.Now she is a Ph.D.candidate at People?s Public Security University of China.Her research interest is impression evidence examination in forensic science.

A

TP392

*The Fundamental Research Funds for People?s Public Security University of China under Grant No.2016JKF01102(中國(guó)人民公安大學(xué)基本科研業(yè)務(wù)費(fèi)項(xiàng)目).

Received 2016-11,Accepted 2017-03.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-04-01,http://kns.cnki.net/kcms/detail/11.5602.TP.20170401.1035.002.html