指紋密碼的提取與匹配算法

何丹琪

摘要：指紋是指手指上谷線和脊線所形成的圖形，指紋識(shí)別技術(shù)因?yàn)槠錅?zhǔn)確性、便捷性和易操作性得到了廣泛的運(yùn)用。文章通過綜合運(yùn)用圖像的處理和模式的識(shí)別技術(shù)，對(duì)指紋的圖像文件進(jìn)行預(yù)處理、對(duì)指紋的特征點(diǎn)進(jìn)行提取，并進(jìn)行指紋匹配，進(jìn)而解決相關(guān)問題。

關(guān)鍵詞：二進(jìn)制編碼；指紋分類；指紋識(shí)別與對(duì)比；指紋相似度；指紋密碼 文獻(xiàn)標(biāo)識(shí)碼：A

中圖分類號(hào)：TP242 文章編號(hào)：1009-2374（2016）31-0017-02 DOI：10.13535/j.cnki.11-4406/n.2016.31.009

1 指紋圖像的采集

在實(shí)際生活中，指紋圖像的采集通常需要借助相關(guān)的一起設(shè)備來完成，通過對(duì)指紋的圖像化處理，可以采集相關(guān)數(shù)據(jù)。

2 指紋圖像的預(yù)處理

從大多數(shù)的指紋圖像可以發(fā)現(xiàn)，某些指紋圖像有比較大的噪聲，如某些圖像的脊線出現(xiàn)了斷裂、模糊、橋接等現(xiàn)象，因此為了使后期處理得以簡(jiǎn)化，特征提取的可靠性得以提高，指紋圖像的預(yù)處理十分有必要。圖像的預(yù)處理步驟主要是以下步驟：圖像的分割、圖像的增強(qiáng)、圖像的二值化和細(xì)化等。

（1）圖像分割。將指紋圖像的有效部分（主要是前景部分）切割出來，把含有大量噪聲的背景部分舍棄；（2）圖像增強(qiáng)。將斷裂的指紋連上，粘連的指紋分開，使模糊的指紋清晰；（3）二值化處理。選用合適的限制條件即閾值，對(duì)指紋灰度圖像進(jìn)行二值化處理，使之成為黑白二值的圖像；（4）細(xì)化。在不改變脊線連通性的基礎(chǔ)上，通過腐蝕操作將原有的脊線轉(zhuǎn)換至單像素寬，使指紋圖像數(shù)據(jù)量減少，紋線結(jié)構(gòu)更加

清晰。

具體模型過程如下：

2.1 圖像的分割

這里采用灰度共生矩陣法。這種方法通過計(jì)算指紋圖像中某些指定取向和某些指定距離的兩個(gè)像素點(diǎn)之間的灰度差值的次數(shù)，就可以計(jì)算出指紋圖像在方向、間隔、幅度變化大小和速度的不同信息，這樣可以將指紋圖像的灰度數(shù)據(jù)轉(zhuǎn)變?yōu)橐粭l一條的紋理數(shù)據(jù)。

2.2 圖像增強(qiáng)和二值化

為了將圖像進(jìn)行二值化，首先確定一個(gè)3×3的小塊，需要確定這個(gè)小塊中中心線的灰度值，其計(jì)算公

式為：

（1）

式中：p表示小塊中灰度值大于閾值的概率，閾值取這個(gè)小塊的平均值。通過這個(gè)模型的計(jì)算可以將所有的灰度值轉(zhuǎn)換成只有0和255，增強(qiáng)了圖像的對(duì)比度，使得為下一步指紋細(xì)化操作提供了依據(jù)。

2.3 圖像細(xì)化

指紋圖像的細(xì)化處理是指在指紋圖像進(jìn)行灰度二值化以后，在不影響指紋紋路的連通性的前提下，去除指紋紋線的邊緣的像素點(diǎn)，細(xì)化紋路的像素寬度，直到小于等于一個(gè)像素的寬度。對(duì)于細(xì)化算法主要要滿足以下六個(gè)方面的要求：（1）紋路連通：刪除邊界數(shù)據(jù)時(shí)不能破壞指紋的連通性；（2）不變性：維持指紋的細(xì)節(jié)方面的特征，如叉口等；（3）中軸性：骨架盡量接近指紋紋路的中心線；（4）迭代收斂：進(jìn)行數(shù)據(jù)迭代計(jì)算時(shí)是不發(fā)散的；（5）細(xì)化性：骨架紋線的必須其寬度為1個(gè)像素；（6）拓?fù)涮卣鳎罕ＷC紋路基本結(jié)構(gòu)特性不發(fā)生變化。

在上述步驟中，我們采用了一種模板的消去保留法，對(duì)圖像逐點(diǎn)保留或刪除，通過增加保留模板和消去模板，提高細(xì)化的速度與精度。該算法是一種串行細(xì)化算法，采用統(tǒng)一的模板，先構(gòu)建了8個(gè)消除模板和6個(gè)保留模板，實(shí)現(xiàn)細(xì)化處理。

2.4 圖像可能特征點(diǎn)的提取

指紋細(xì)節(jié)特征點(diǎn)（Minutiae）主要指的是紋線端點(diǎn)（Ridge Ending）和紋線分叉點(diǎn)（Bifurcation）。紋線端點(diǎn)就是指指紋紋路突然中斷的位置，紋路分叉點(diǎn)指的是紋路一分為二的位置。根據(jù)資料顯示的統(tǒng)計(jì)結(jié)果表明，采用這兩種特征點(diǎn)可以確定指紋的唯一性。因此我們只提取端點(diǎn)和分叉點(diǎn)，并進(jìn)行去偽處理。

具體算法如下：

（2）

2.5 圖像偽特征點(diǎn)的去除

經(jīng)過以上二值化和細(xì)化步驟的指紋圖像中，還存在以下五類噪聲：（1）紋線間斷。上個(gè)模型中的指紋特征點(diǎn)提取算法測(cè)得到兩個(gè)指紋紋路端點(diǎn)，并定義其為偽特征點(diǎn)。這種偽特征點(diǎn)的兩點(diǎn)間距非常小，而且沿局部紋線方向的兩點(diǎn)之間的區(qū)域無紋線；（2）紋線叉連。在紋線叉連的位置，上個(gè)模型中的指紋特征點(diǎn)提取算法會(huì)提取到兩個(gè)指紋的分叉點(diǎn)，但都屬于偽特征點(diǎn)；（3）短橫線。如果指紋不潔凈，有污漬，采集到的指紋圖像易產(chǎn)生很多的由隨機(jī)噪聲引起的短橫線。在短橫線位置，可能提取到兩個(gè)紋線端點(diǎn)，也屬于偽特征。這種偽特征點(diǎn)的特點(diǎn)是兩點(diǎn)之間距離很小，兩點(diǎn)之間由一條指紋紋路相連；（4）較小的孔狀結(jié)構(gòu)；（5）毛刺。

3 指紋密碼存儲(chǔ)模型

在采集完指紋特征點(diǎn)之后，我們需要將特征點(diǎn)信息存儲(chǔ)，以便下步對(duì)比匹配時(shí)使用。對(duì)細(xì)化后的圖像以像素為單位，采用上述特征點(diǎn)提取算法遍歷整個(gè)圖像，記錄特征點(diǎn)的位置信息。對(duì)于分叉點(diǎn)，記錄為0，坐標(biāo)為（x，y）；端點(diǎn)記錄為1，坐標(biāo)為（x，y）。對(duì)于坐標(biāo)（x，y），需要16bite來存儲(chǔ)，對(duì)于0/1，需要1bite。遍歷整個(gè)圖像后，就可以將端點(diǎn)和分叉點(diǎn)信息存儲(chǔ)。

一般來說指紋識(shí)別所給的圖像分辨率是400*600，將其分割后160*120，但是圖像的DPI只有72，根據(jù)我國(guó)《居民身份證采集器通用技術(shù)要求》，寬為12.75mm，長(zhǎng)為17.93mm，圖像DPI為500。DPI是指單位英寸上所包含的像素點(diǎn)，那么題目所給的圖像單位面積上所包含的像素點(diǎn)總數(shù)是72 72 5184點(diǎn)/平方英寸，而更具標(biāo)準(zhǔn)所要求應(yīng)該具有的像素點(diǎn)總數(shù)是500 500 250000點(diǎn)/平方英寸，標(biāo)準(zhǔn)單位面積上所具有的像素點(diǎn)總數(shù)是題目所給圖像的48.23倍。這樣一來，對(duì)題目所給的圖像進(jìn)行分割和細(xì)化等工作時(shí)，效果并不是很樂觀，為了體現(xiàn)算法的有效性，我們還選取了FVC2004指紋庫中的一些指紋進(jìn)行細(xì)化處理，用來和題目所給的圖像進(jìn)行對(duì)比。

4 指紋密碼對(duì)比模型

經(jīng)過前面的指紋圖像預(yù)處理和特征點(diǎn)提取環(huán)節(jié)，獲得的細(xì)節(jié)特征信息就是指紋圖像的特征點(diǎn)集合，通過對(duì)特征集合之間的信息相似性進(jìn)行比對(duì)，就能夠判斷出對(duì)應(yīng)的指紋圖像是否來自同一個(gè)手指。

若要進(jìn)一步壓縮指紋密碼的存儲(chǔ)空間，則可以對(duì)指紋密碼的對(duì)比模型進(jìn)行改進(jìn)，不用存儲(chǔ)全部的特征點(diǎn)，可以存儲(chǔ)特定的特征點(diǎn)，比如隔一個(gè)特征點(diǎn)就存儲(chǔ)一個(gè)，這樣就可以降低特征點(diǎn)存儲(chǔ)數(shù)目，使得所需要的存儲(chǔ)字節(jié)降低。但是這要求對(duì)比模型也要做一定的改進(jìn)。對(duì)于唯一性的確定，通過生物學(xué)上的分析，一個(gè)人的指紋是唯一的，那么如果在確保能夠準(zhǔn)確提取多個(gè)特征點(diǎn)，那么一個(gè)人的指紋將是唯一的。但是由于算法在細(xì)化和分割過程中有許多的偽特征點(diǎn)，那么就有一定的可能使得兩枚指紋的指紋密碼是類似的，在做對(duì)比時(shí)可能會(huì)判定為同一枚指紋。

5 模型的優(yōu)缺點(diǎn)

模型對(duì)圖像分辨率的要求很高，在題目所給的指紋上表現(xiàn)并不是很好，因?yàn)轭}目所給的圖像分辨率很低。在FVC2004的一枚指紋上可見模型的表現(xiàn)還是很好的。模型沒有進(jìn)行低質(zhì)量指紋圖的測(cè)試，但是通過理論分析，模型在對(duì)指紋圖像噪聲的處理上還有待提高。由于不能使用別人已有的指紋識(shí)別算法，加上我們小組成員對(duì)圖像噪音處理不是很了解，導(dǎo)致我們?cè)谠肼曁幚矸矫嬗泻艽蟮娜秉c(diǎn)，后續(xù)可以對(duì)模型的噪聲處理進(jìn)行加強(qiáng)，想必能得到一個(gè)很好的指紋識(shí)別算法。

模型在噪音處理方面可以做進(jìn)一步的改進(jìn)，還可以通過對(duì)算法的優(yōu)化降低編程計(jì)算的時(shí)間復(fù)雜度，使得模型更加高效。

6 結(jié)語

本模型的數(shù)學(xué)背景不是很復(fù)雜，有利于編程實(shí)現(xiàn)，并且模型將指紋密碼采用緊湊的二進(jìn)制數(shù)字來存儲(chǔ)，這樣能夠提高存儲(chǔ)所需的內(nèi)存空間，降低存儲(chǔ)的使用，對(duì)目前大量的指紋數(shù)據(jù)來說，這是很經(jīng)濟(jì)的，也是很實(shí)

用的。

參考文獻(xiàn)

[1] 郭進(jìn)，文安邦，嚴(yán)冬春，史忠林.復(fù)合指紋識(shí)別技術(shù) 定量示蹤流域泥沙來源[J].農(nóng)業(yè)工程學(xué)報(bào)，2014， （2）.

[2] 祝恩.低質(zhì)量指紋圖像的特征提取與識(shí)別技術(shù)的研究 [D].國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[3] 王瑋.自動(dòng)指紋識(shí)別系統(tǒng)關(guān)鍵技術(shù)研究[D].重慶大 學(xué)，2007.

[4] 張圓圓.指紋識(shí)別技術(shù)相關(guān)算法的研究[D].北京郵電 大學(xué)，2012.

[5] 張潔.殘缺指紋識(shí)別中若干關(guān)鍵技術(shù)的研究[D].北京 郵電大學(xué)，2013.

[6] 田捷，陳新建，張陽陽，楊鑫，何余良，李亮，謝 衛(wèi)華，鄭志鵬.指紋識(shí)別技術(shù)的新進(jìn)展[J].自然科學(xué) 進(jìn)展，2006，（4）.

[7] 時(shí)鵬，田捷，蘇琪，楊鑫.基于奇異點(diǎn)鄰近結(jié)構(gòu)的快 速指紋識(shí)別[J].軟件學(xué)報(bào)，2008，（12）.

[8] 戴平陽.指紋識(shí)別技術(shù)研究進(jìn)展[J].廈門大學(xué)學(xué)報(bào) （自然科學(xué)版），2002，（6）.

[9] 王俊珺.指紋識(shí)別算法優(yōu)化與應(yīng)用研究[D].華東師范 大學(xué)，2009.