基于細(xì)節(jié)點(diǎn)描述子的指紋檢索算法

湯正剛 沈雷 呂葛梁

摘要：針對(duì)指紋一對(duì)一匹配識(shí)別方法嚴(yán)重影響指紋數(shù)據(jù)庫系統(tǒng)識(shí)別效率的問題，提出一種基于細(xì)節(jié)點(diǎn)描述子的指紋檢索算法，該算法先根據(jù)細(xì)節(jié)點(diǎn)描述子的結(jié)構(gòu)信息進(jìn)行粗匹配篩選，剔除虛假細(xì)節(jié)點(diǎn)產(chǎn)生的影響;然后利用篩選后的細(xì)節(jié)點(diǎn)位置關(guān)系確定最佳參考點(diǎn);最后基于最佳參考點(diǎn)計(jì)算所有指紋圖像相似度，將相似度排在前N?0的指紋返回并作為候選指紋。實(shí)驗(yàn)結(jié)果表明，該算法在時(shí)間和空間上都優(yōu)于傳統(tǒng)指紋檢索算法。

關(guān)鍵詞：指紋分類;指紋檢索;細(xì)節(jié)點(diǎn)描述子;最佳參考點(diǎn)

Fingerprint Indexing Based on Minutiae Descriptor

TANG Zheng?gang，SHEN Lei，LV Ge?liang

（School of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

Abstract：Aiming at the problem that fingerprint one?to?one matching identification method seriously affects the recognition efficiency of fingerprint database system， a fingerprint retrieval algorithm based on minutiae descriptor is proposed. The algorithm first performs rough matching screening based on the structural information of the minutiae descriptors to remove the influence of false minutiae points， and then uses the filtered results of the location of the minutiae point to determine the best reference point. At last the algorithm calculates the similarity of the fingerprint images based on the best reference point， and selects the fingerprints with the similarity ranked in the top N?0 as the candidate fingerprints according to the the best reference point. Experimental results show that the proposed algorithm outperforms the traditional fingerprint indexing algorithm both in time and space.

Key Words：fingerprint classification;fingerprint indexing;minutiae descriptor;optimal reference point

0?引言

近年來，隨著指紋識(shí)別產(chǎn)品[1?2]在人們生活中被廣泛使用，出現(xiàn)了越來越多的大型指紋數(shù)據(jù)庫（如機(jī)場(chǎng)指紋庫、公安指紋庫等），雖然目前指紋匹配算法在時(shí)間和準(zhǔn)確率方面有了很大改善[3?5]，但在大型指紋數(shù)據(jù)庫中進(jìn)行指紋識(shí)別時(shí)，如果仍然采用一對(duì)一匹配，會(huì)嚴(yán)重影響指紋識(shí)別系統(tǒng)效率。為此，引入預(yù)篩選技術(shù)縮小指紋匹配空間，提高指紋識(shí)別效率。預(yù)篩選技術(shù)通?？梢苑譃閮深悾褐讣y分類、指紋檢索[6?8]。

在指紋分類中，指紋數(shù)據(jù)庫被劃分為固定類別[9?11]，將輸入指紋與同一分類的指紋進(jìn)行匹配即可。指紋分類最大缺點(diǎn)是指紋類別有限且分布非常不均，在Galton-Henry分類方案中，右環(huán)型、左環(huán)型和漩渦型3類大約占93%[12]，因此指紋分類并不能有效縮小匹配空間;此外，對(duì)于殘缺和低質(zhì)量指紋圖像，指紋分類無法準(zhǔn)確判斷其類型，導(dǎo)致該類指紋識(shí)別成功率較低。

指紋檢索指首先提取穩(wěn)定的特征向量，通過尋找與其特征向量相似度較高的一批指紋作為候選指紋模版，然后一對(duì)一進(jìn)行精細(xì)匹配。指紋檢索很好地避免了指紋分類中對(duì)于殘缺和低質(zhì)量指紋類別無法判斷的問題，而且該技術(shù)的檢索性能遠(yuǎn)遠(yuǎn)優(yōu)于指紋分類技術(shù)。

目前已提出較多指紋檢索算法，如Bhanu[6]和王平等[13]提出了基于三角形結(jié)構(gòu)的指紋特征檢索算法;Liang等[14]提出一種基于細(xì)節(jié)點(diǎn)鄰域結(jié)構(gòu)和低階Delaunay三元組的指紋檢索方法;Iloanus等[15]提出基于細(xì)節(jié)點(diǎn)四元組的指紋檢索法等。在傳統(tǒng)特征檢索中，特征結(jié)構(gòu)中的邊長(zhǎng)容易受到形變影響，且邊長(zhǎng)越長(zhǎng)或越短，形變影響越大;兩細(xì)節(jié)點(diǎn)之間的脊線數(shù)目受到噪聲、紋線斷裂、紋線模糊等質(zhì)量因素的影響。細(xì)節(jié)點(diǎn)信息和特征結(jié)構(gòu)的類型都要通過細(xì)節(jié)點(diǎn)類型求得，但在很多情況下不能確定細(xì)節(jié)點(diǎn)類型。

綜上可知，傳統(tǒng)指紋檢索算法利用指紋細(xì)節(jié)點(diǎn)間的結(jié)構(gòu)信息實(shí)現(xiàn)指紋檢索，該類算法存在一定缺陷。王平和Iloanus的算法構(gòu)建的三角形和四元組數(shù)量較大，不僅需要消耗大量?jī)?nèi)存空間且會(huì)在一定程度上影響指紋檢索效率;Liang的算法構(gòu)建低階Delaunay網(wǎng)的拓?fù)浣Y(jié)構(gòu)是唯一的，容易受到虛假細(xì)節(jié)點(diǎn)影響，如果提取的細(xì)節(jié)點(diǎn)中包含一定量的虛假細(xì)節(jié)點(diǎn)，則會(huì)構(gòu)建許多錯(cuò)誤的結(jié)構(gòu)信息，降低指紋檢索準(zhǔn)確率。本文提出一種基于細(xì)節(jié)點(diǎn)描述子的指紋檢索算法，構(gòu)建的細(xì)節(jié)點(diǎn)描述子相互獨(dú)立，相互之間的影響較小，克服了不同細(xì)節(jié)點(diǎn)間出現(xiàn)虛假結(jié)構(gòu)信息的影響;而且細(xì)節(jié)點(diǎn)描述子已在文獻(xiàn)[16]中用于指紋匹配，并可取得較好的效果，說明細(xì)節(jié)點(diǎn)描述子可以準(zhǔn)確表示指紋特征信息，該特性可保證檢索算法性能。

1?細(xì)節(jié)點(diǎn)描述子構(gòu)建

構(gòu)建的細(xì)節(jié)點(diǎn)描述子具備以下特性：①細(xì)節(jié)點(diǎn)描述子具有穩(wěn)定的結(jié)構(gòu);②細(xì)節(jié)點(diǎn)描述子含有準(zhǔn)確、可靠的輔助信息。

1.1?細(xì)節(jié)點(diǎn)描述子

本文主要利用細(xì)節(jié)點(diǎn)描述子進(jìn)行指紋搜索，不宜構(gòu)造復(fù)雜的結(jié)構(gòu)。因此，根據(jù)文獻(xiàn)[16]中細(xì)節(jié)點(diǎn)描述子的定義，繪制本文構(gòu)建的細(xì)節(jié)點(diǎn)描述子，如圖1所示。

假設(shè)P?0為提取的細(xì)節(jié)點(diǎn)，θ?0為該點(diǎn)的方向場(chǎng)，以P?0為圓心，繪制領(lǐng)域半徑為R的圓，在該圓上均勻地取3個(gè)輔助點(diǎn)，分別為P?1、P?2、P?3;輔助點(diǎn)P?1為細(xì)節(jié)點(diǎn)P?0方向場(chǎng)方向與該圓相交的點(diǎn)，P?1、P?2、P?3之間間隔為120°，其中輔助點(diǎn)P?1、P?2、P?3對(duì)應(yīng)的方向場(chǎng)分別為θ?1、θ?2、θ?3。

如果輔助點(diǎn)位于非指紋區(qū)域，則認(rèn)為該細(xì)節(jié)點(diǎn)是無效細(xì)節(jié)點(diǎn);細(xì)節(jié)點(diǎn)描述子領(lǐng)域半徑R的大小直接影響細(xì)節(jié)點(diǎn)鑒別能力，下文通過實(shí)驗(yàn)給出最佳領(lǐng)域半徑R值。

1.2?指紋方向場(chǎng)計(jì)算

細(xì)節(jié)點(diǎn)描述子使用的輔助信息是細(xì)節(jié)點(diǎn)周圍的方向場(chǎng)信息，因此，指紋方向場(chǎng)的準(zhǔn)確性會(huì)直接影響細(xì)節(jié)點(diǎn)描述子的效果。通常使用梯度算子計(jì)算指紋方向場(chǎng)[17?19]，具體如下：

（1）將指紋圖像分成W*W的固定小塊。

（2）采用Sobel算子計(jì)算每小塊內(nèi)每個(gè)像素點(diǎn)梯度??x（i，j）、?y（i，j）?。

（3）根據(jù)梯度值計(jì)算塊方向，公式如下：

文獻(xiàn)[17]-[19]提出的算法是在固定分塊尺寸后計(jì)算指紋方向場(chǎng)，雖然對(duì)紋線清晰的指紋圖像能夠取得較好的效果，但對(duì)質(zhì)量較差的指紋圖像則存在明顯不足。而本文檢測(cè)對(duì)象是分辨率更高的方向場(chǎng)——點(diǎn)方向場(chǎng)，求每一點(diǎn)的方向場(chǎng)所需時(shí)間比塊方向場(chǎng)更多。為了加速計(jì)算，本文在其基礎(chǔ)上設(shè)計(jì)滑動(dòng)窗口（見圖2）技術(shù)，同時(shí)使用圖像的高斯金字塔分解[20]技術(shù)縮小指紋尺度，獲得更加準(zhǔn)確的指紋方向場(chǎng)。

2?指紋檢索算法

本文提出的基于細(xì)節(jié)點(diǎn)描述子的指紋檢索算法，利用細(xì)節(jié)點(diǎn)描述子對(duì)所有細(xì)節(jié)點(diǎn)進(jìn)行粗匹配，然后根據(jù)粗匹配點(diǎn)間的位置信息尋找最佳參考點(diǎn)，最后基于最佳參考點(diǎn)計(jì)算兩指紋相似度。算法具體包括：?①從指紋圖中提取每個(gè)細(xì)節(jié)點(diǎn)特征信息為（x，y，T，θ?0，θ?1，θ?2，θ?3），其中x、y、T、θ?0分別表示細(xì)節(jié)點(diǎn)的橫坐標(biāo)、縱坐標(biāo)、類型（端點(diǎn)、分叉點(diǎn)）及方向場(chǎng);②θ?1、θ?2、θ?3為圖1中細(xì)節(jié)點(diǎn)描述子中對(duì)應(yīng)三點(diǎn)的方向場(chǎng)。輸入兩幅指紋A和B，A是待識(shí)別指紋，提取的細(xì)節(jié)點(diǎn)為集合A={a?1，a?2，…，a?N}，B為指紋庫中的任意指紋，提取的細(xì)節(jié)點(diǎn)為集合B={b?1，b?2，…，b?M}。

2.1?粗糙匹配點(diǎn)集獲取

利用細(xì)節(jié)點(diǎn)描述子局部方向場(chǎng)信息，獲取指紋A和B粗糙匹配點(diǎn)集。具體過程如下：

（1）選取指紋圖像?A中任意一個(gè)細(xì)節(jié)點(diǎn)a?n，遍歷指紋圖像B中所有細(xì)節(jié)點(diǎn)，若指紋圖像B中存在細(xì)節(jié)點(diǎn)b?m，兩個(gè)細(xì)節(jié)點(diǎn)a?n、b?m?滿足類型相同、且位置平移在（±Δ?x?0?，±Δ?y?0）范圍內(nèi)的條件，則進(jìn)入（3）;若遍歷指紋圖像B中所有細(xì)節(jié)點(diǎn)后不存在與細(xì)節(jié)點(diǎn)a?n對(duì)應(yīng)的細(xì)節(jié)點(diǎn)b?m，則放棄指紋圖像A的細(xì)節(jié)點(diǎn)a?n。

（2）繼續(xù)從指紋圖像A中選取下一個(gè)細(xì)節(jié)點(diǎn)，重復(fù)（1），直至遍歷完指紋圖像A中所有細(xì)節(jié)點(diǎn)。

（3）計(jì)算細(xì)節(jié)點(diǎn)描述子中兩點(diǎn)之間的相對(duì)角度差Δ?θ?k?。

式中k為細(xì)節(jié)點(diǎn)描述子中相對(duì)角度差對(duì)應(yīng)編號(hào)，其范圍為1≤k≤6。

兩細(xì)節(jié)點(diǎn)描述子間第k角度偏差記為G（k）：

式中，Δ?θa?n?k為細(xì)節(jié)點(diǎn)a?n?的相對(duì)角度差，Δ?θb?m?k為細(xì)節(jié)點(diǎn)b?m的相對(duì)角度差。

（4）判斷兩指紋細(xì)節(jié)點(diǎn)是否匹配：①如果式（5）中任意G（k）大于閾值T?1，說明兩細(xì)節(jié)點(diǎn)不匹配，回到（1），否則進(jìn)入下一步;②兩細(xì)節(jié)點(diǎn)描述子相似度S計(jì)算公式為S=1-16T?1∑6k=1G（k）;③若S大于閾值T?2，則記錄相似度Si;④ 重復(fù)（1）、（2），直到剩下點(diǎn)都完成匹配（存在指紋A中一個(gè)點(diǎn)與指紋B中多個(gè)點(diǎn)相似度大于T?2）;⑤選取每組Si中最大S作為匹配點(diǎn)，記錄匹配成功的點(diǎn)集Q，匹配對(duì)數(shù)為L(zhǎng)?，每對(duì)匹配點(diǎn)之間的指紋匹配點(diǎn)類型為（Δ?x?i?，Δ?y?i?，Δ?θ?i?）。

2.2?指紋圖像相似度計(jì)算

利用細(xì)節(jié)點(diǎn)間全局位置關(guān)系，確定最佳參考點(diǎn)對(duì)，然后計(jì)算基于最佳參考點(diǎn)的指紋圖像相似度。

（1）確定最佳參考點(diǎn)對(duì)。分析第一步中的粗匹配點(diǎn)集，從中尋找最佳匹配點(diǎn)。原理如下：如果兩幅指紋圖來自同一手指，則每對(duì)匹配點(diǎn)（Δ?x?i?，Δ?y?i?，Δ?θ?i?）位置變換相等，允許在一定范圍之內(nèi)變動(dòng)（Δ?x?i?±Δ?l?0?，Δ?y?i?±Δ?l?1?，Δ?θ?i?±Δ?l?2?）;但如果偏差較大，則說明對(duì)應(yīng)的匹配點(diǎn)是虛假匹配點(diǎn)。具體過程如下：

計(jì)算集合?Q?（Δ?x?，Δ?y?，Δ?θ?）與每對(duì)匹配點(diǎn)（Δ?x?i?，Δ?y?i?，Δ?θ?i）（i=1，2，…，L）的偏差d?i：

取d?i中小于閾值T?3個(gè)數(shù)最大值C?m對(duì)應(yīng)的匹配點(diǎn)為最佳匹配點(diǎn)，即a?i和b?i?為最佳匹配點(diǎn)，其位置偏差為（Δ?x?ij?，Δ?y?ij?，Δ?θ?ij?）。

（2）基于最佳參考點(diǎn)計(jì)算指紋圖像相似度。

式（7）中D（i）是最佳匹配點(diǎn)下偏差d?i集合，C?m為在最佳參考點(diǎn)下細(xì)節(jié)點(diǎn)匹配點(diǎn)數(shù)，R為匹配點(diǎn)中端點(diǎn)的個(gè)數(shù)，L為細(xì)節(jié)點(diǎn)描述子匹配點(diǎn)數(shù)，N和M分別為指紋A和指紋B的細(xì)節(jié)點(diǎn)數(shù)。

2.3?指紋檢索結(jié)果

輸入指紋A與指紋庫中所有指紋，重復(fù)粗糙點(diǎn)集獲取和指紋圖像相似度計(jì)算，得到所有指紋相似度集合Score，再從Score中選出排在前N?0個(gè)的指紋作為候選指紋。

3?實(shí)驗(yàn)與結(jié)果分析

為了得到實(shí)驗(yàn)圖像數(shù)據(jù)庫，采集1 000組指紋圖像建立指紋圖像庫，每組6幅圖像樣本，一共6 000幅樣本圖像，其中約有20%的指紋圖指紋質(zhì)量偏差。為了驗(yàn)證算法性能，從每組人工選取3幅圖像，共3 000幅作為指紋數(shù)據(jù)庫Ⅰ，剩下的3 000幅圖像作為指紋數(shù)據(jù)庫Ⅱ。

本文采用穿透率（Penetration Rate）及命中率[13]（Hit Rate）指標(biāo)衡量檢索算法性能。假設(shè)指紋庫有?d組指紋，其中I?m是和測(cè)試指紋I匹配的庫指紋，I?m和I的檢測(cè)分?jǐn)?shù)為S?m，即S?m為測(cè)試指紋I命中時(shí)的檢索分?jǐn)?shù)，設(shè)S?m在所有分?jǐn)?shù)中排名為m，可得測(cè)試指紋I的穿透率為：

計(jì)算某一穿透率P的命中率為：

式中，M為測(cè)試指紋數(shù)量，n?p表示所有穿透率小于P的測(cè)試指紋數(shù)量。

圖3是本文算法和王平、Liang、Iloanus的算法檢索特征數(shù)量與細(xì)節(jié)點(diǎn)數(shù)量的曲線對(duì)比。從中看出本文構(gòu)建檢索特征的數(shù)量最少，在一定程度上減少了檢索時(shí)間，而且每個(gè)檢索特征相互獨(dú)立，該屬性可保證檢索算法性能。

圖4是穿透率分別在5%、10%、15%時(shí)領(lǐng)域半徑R與命中率的性能曲線。從圖4可知，領(lǐng)域半徑R在17～24內(nèi)命中率性能提升幅度較大，同時(shí)結(jié)合在其它穿透率時(shí)的性能提升情況可以看出，本文算法細(xì)節(jié)點(diǎn)描述子的最佳領(lǐng)域R選取為19時(shí)，細(xì)節(jié)點(diǎn)描述子的鑒別能力最強(qiáng)。

分別在指紋數(shù)據(jù)庫Ⅰ和指紋數(shù)據(jù)庫Ⅱ中，將王平、Liang、Iloanus和本文算法進(jìn)行指紋檢索實(shí)驗(yàn)，得到命中率和穿透率的算法曲線（見圖5、圖6）。圖中結(jié)果表明本文算法在兩個(gè)數(shù)據(jù)庫中都展示了更好的性能，在相同搜索能力下所需搜索空間最小。表1是在命中率為95%和100%時(shí)，4個(gè)算法在指紋庫Ⅰ、Ⅱ穿透率的比較，本文算法在兩個(gè)指紋庫中相差0.2%～0.3%，在4個(gè)算法中的變化最小?？芍疚奶岢龌诩?xì)節(jié)點(diǎn)描述子的指紋檢索算法性能相比于傳統(tǒng)的指紋檢索算法，有效提高了指紋檢索能力，而且算法性能最穩(wěn)定。

為了驗(yàn)證本文算法運(yùn)行時(shí)間的可行性，將本文算法和王平、Liang、Iloanus的算法在不同規(guī)模指紋數(shù)據(jù)庫中進(jìn)行時(shí)間、效率仿真，同時(shí)加入文獻(xiàn)[8]的匹配算法進(jìn)行仿真，統(tǒng)計(jì)在相同數(shù)量的指紋庫中匹配一枚指紋的平均時(shí)間，如圖7所示。在指紋庫中進(jìn)行指紋檢索時(shí)，4種檢索算法所需時(shí)間分別為97.3ms、120ms、158ms、213ms，而文獻(xiàn)[8]的匹配算法需1 269ms，進(jìn)一步證明本文指紋檢索算法消耗時(shí)間較少，可以實(shí)現(xiàn)快速檢索指紋。

4?結(jié)語

本文提出了一種基于細(xì)節(jié)點(diǎn)描述子的指紋檢索算法，利用細(xì)節(jié)點(diǎn)描述子對(duì)指紋細(xì)節(jié)點(diǎn)進(jìn)行粗匹配，降低了虛假細(xì)節(jié)點(diǎn)在檢索過程中的影響;同時(shí)通過指紋局部和全局信息相結(jié)合的方法，從粗匹配點(diǎn)中確定最佳參考點(diǎn)，根據(jù)最佳參考點(diǎn)計(jì)算指紋相似度，使指紋檢索達(dá)到很好的效果。

參考文獻(xiàn)：

[1]?倪增超，王婧.自動(dòng)指紋識(shí)別技術(shù)的發(fā)展及應(yīng)用[J].科技創(chuàng)新與應(yīng)用，2015（32）：40.

[2]?李慶艷，張文安.淺析指紋識(shí)別在移動(dòng)支付的應(yīng)用前景[J].廣東通信技術(shù)，2015，35（8）：2?6.

[3]?GHADDAB M H， JOUINI K，KORBAA O， Fast and accurate fingerprint matching using expanded delaunay triangulation[C].?IEEE/ACS 14th International Conference on Computer Systems and Applications， 2017：751?758.

[4]?GUTIRREZ P D， LASTRA M， HERRERA F， et al. A high performance fingerprint matching system for large databases based on GPU[J]. IEEE Transactions on Information Forensics and Security， 2014，9（1）：62?71.

[5]?PAULINO A A， FENG J， JAIN A K. Latent fingerprint matching using descriptor?based hough transform[J]. IEEE Transactions on Information Forensics and Security， 2013，8（1）：31?45.

[6]?CAPPELLI R. Fast and accurate fingerprint indexing based on ridge orientation and frequency[J]. IEEE Transactions on Systems， Man?and Cybernetics：Part B （Cybernetics），2011，41（6）：1511?1521.

[7]?趙琪.自動(dòng)指紋識(shí)別中若干關(guān)鍵技術(shù)的研究[D].長(zhǎng)沙：中南大學(xué)，2009.

[8]?BHANU B， TAN X J. Fingerprint indexing based on novel features of minutiae triplets[J].IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25（5）：616?622.

[9]?聶桂軍，孟慶杰，朱琳，等.基于方向圖跟蹤和對(duì)稱軸的自動(dòng)指紋分類算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：70?73.

[10]?楊小冬，寧新寶，詹小四，等.基于紋線跟蹤的指紋分類方法[J].計(jì)算機(jī)工程，2005（7）：170?173.

[11]?楊利敏，楊杰，李鋼.基于指紋分類的模式匹配[J].電子學(xué)報(bào)，2003（7）：1030?1034.

[12]?MALTONI D，MAIO D ， JAIN A K， et al. Handbook of fingerprint recognition[M]. New York：Springer?Verlag Press，2009.

[13]?王平.指紋圖像的檢索與匹配算法研究[D].大連：大連理工大學(xué)，2004.

[14]?LIANG X， BISHNU A， ASANO T. A robust fingerprint indexing scheme using minutia neighborhood structure and low?order delaunay triangles[J]. IEEE Transactions on Information Forensics and Security， 2007，2（4）：721?733.

[15]?ILOANUSI O， GYAOUROVA A， ROSS A.Indexing fingerprints using minutiae quadruplets[C]. CVPR 2011 WORKSHOPS，2011：127?133.

[16]?陳暉，殷建平，祝恩，等.一種基于細(xì)節(jié)點(diǎn)局部描述子的指紋圖像匹配方法[J].計(jì)算機(jī)工程與科學(xué)，2010，32（1）：87?91.

[17]?劉靈麗，李麗娟.指紋圖像預(yù)處理和特征提取[J].計(jì)算機(jī)工程，2006，32（16）：190?192.

[18]?周曄華.指紋圖像預(yù)處理算法研究[D].南京：南京理工大學(xué)，2008.

[19]?王瑋，李見為，張騰.指紋圖像的預(yù)處理算法[J].計(jì)算機(jī)應(yīng)用，2004（5）：72?75.

[20]?GONZALES R C， WOODS R E. 數(shù)字圖像處理[M].第三版.阮秋琦，阮宇智，譯.北京：電子工業(yè)出版社，2011.