基于８鄰域編碼逐像素跟蹤法的指紋細節特征提取算法

摘要：研究并實現基于8鄰域編碼逐像素跟蹤法的細節特征提取算法。該算法能有效提取細化后指紋圖像中的端點和分叉點，通過回朔跟蹤法，能有效去除圖像中的偽特征點。實驗結果表明該算法較大幅度提高了特征提取的速度，并能夠較準確的濾除偽特征點，縮短了圖像后處理時間，可以滿足實際應用的需要。

關鍵詞：8鄰域；特征提取；指紋

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)31-0932-03

Minutiae Extraction in Fingerprint Images Based on 8 Neighborhoods Region Coding Pursue Pixe

CHEN Yan-ping， ZHAO Lei

(Computer Science and Technology， Hefei University， Hefei 230031， China)

Abstract: Minutiae extraction in fingerprint iImages based on 8 neighborhoods region coding pursue pixel method is studied and realized. It can realize the image after melts carefully for fingerprint in end points and bifurcation point go on effective draw， and through returning slot the fake feature point in image go to wipe off. Test result to show that this method greater improve the speed that drawn， reduction imagery processing time， can satisfy the needs of actual application basically， and can be more exact to strain the fake feature point. The experiment indicated， a suit of arithmetic operational speed that this paper puts forward rapid， can draw feature efficiently， method is simple and effective， and the algorithm is simple， is easy programming realization.

Key words: 8 neighborhoods; minutiae extraction; fingerprint

1 引言

指紋特征值是指紋算法的基礎數據，是指紋算法最重要的數據結構。指紋通過兩類特征來進行驗證：總體特征和局部特征。局部特征是指指紋上的節點的特征，這些具有某種特征的節點稱為特征點。兩枚指紋經常會具有相同的總體特征[3，4]，但它們的局部特征——特征點，卻不可能完全相同。指紋細節特征點主要指的是紋線端點和紋線分叉點。大量的統計結果表明，使用這兩類特征點就足以描述指紋的唯一性。

迄今為止，人們已經對指紋細節特征點提取算法進行了很多的研究工作，常規的細節特征提取算法大多是在經過細化的指紋圖像上進行的，包括細節特征提取、去偽特征點兩個步驟[5]。基于8鄰域編碼逐像素跟蹤法，通過逐像素掃描指紋圖像，從而記錄下提取出的特征點的信息：類型、坐標、方向。該方法簡單，運行速度快，配合去除偽特征點的方法，能夠滿足實際應用的需要。

28鄰域編碼逐像素跟蹤算法原理

逐像素跟蹤就是從指紋圖像的一點出發，沿著行和列地走向，達到行的另一端后再掃描下一行。在對細化二值像素進行掃描時，用8鄰域編碼來表示當前點的類型和8鄰域像素的狀態。細節特征的坐標直接表征該指紋，因此特征提取的好壞直接影響到以后的指紋匹配結果。

對于細化后的圖像，像素點的灰度值可以認為只有兩種情況：0或1，0為背景點灰度，1為前景點灰度。脊線上的點的8鄰域內像素的特征分析如下：

1）端點周圍八個象素只有一個值為1，其余為0，因此端點周圍像素的值順序變化（從0到1，或從1到0）的次數為2；

2）分叉點周圍的像素值順序變化的次數為6；

3）脊線的連續點周圍八個像素有兩個值為1，其余為0，因此連續點周圍像素順序變化次數為4；

圖1顯示了三種特征點的類型的表現形式。根據這些細節特征信息，細化后的指紋圖像就可利用3×3模板來判斷細節特征，如圖2所示：

■

圖1 特征點類型 圖2 像素Ｐ及其8鄰域

其中P1，P2，….，P8是它的8個鄰域點，沿著順時針方向排列。R(1)，R(2)，…，R(8)分別是P1，P2，…，P8的灰度值（0表示背景點灰度，用白點表示；1表示脊線點灰度，用黑點表示）。因此，可以給出如下的數學描述。

定義交叉數Cn(p)為：

■ （1）

當Cn(p)=1，表示P點是斷點（或端點）；當Cn(p)=2，表示P點是連續點；當Cn(p)=3，表示P點是分叉點。

8鄰域紋線點數定義為：

■ （2）

編碼與補碼的定義：

跟蹤過程每前進一步，就是從當前點P的8鄰域點中選擇一點作為下一個待跟蹤點。前進的方向有8種可能，定義DC=K作為點P到點PK的主向編碼，定義DC作為點P到點PK的主向編碼的補碼，即點PK到點P的方向編碼，DC和DC的關系可以表示為：

■ （3）

構成偽特征結構的特征點之間的距離一般小于紋線間的平均距離

當我們以每一個特征點為起點，對端點做一個方向的紋線跟蹤或者對分叉點做3個方向的紋線跟蹤，最大跟蹤步長設為λ，λ為紋線間的平均距離，可以根據指紋采集系統而定，這里取λ=6。在每一個紋線方向跟蹤的過程中，當遇到了端點或者分叉點以及跟蹤步長達到閾值λ的時候，此方向的跟蹤就可停止，把紋線跟蹤結果保存起來。

將端點和分叉點作為細化二值圖像的特征點，為了使特征點與圖像中所含虛假特征點有所區分，需要提取特征點的一些相關屬性：

1）細節特征點的坐標：特征點位于細化二值圖像中的坐標。以圖像的左上角的起始點作為坐標參照系的原點，以向右的方向為X軸的正方向，以向下的方向為Y軸的正方向；

2）細節特征點的類型：1-端點，2-分叉點；

3）細節特征點的方向：對于分叉點，可以提取它的三條紋線的方向作為結構屬性。我們定義紋線的方向為紋線跟蹤最后一點指向特征點的方向。則分叉點的第i(i=1，2，3)條紋線的方向Di即為紋線跟蹤最后一點tpi指向該分叉點P的方向，即：

■ （4）

對于分叉點，取與其它兩條紋線角度最大的紋線方向作為特征點的方向。

對于端點，特征點的方向就是其所在的紋線的方向；

3 特征提取過程

通過對細化二值指紋圖像分析發現，某紋線點的S鄰域灰度值的組合最簡單的組合有三種情況：

1）端點：滿足Cn（P）=1，Sn（P）=1時，1個中心點的8鄰域中只有一個黑點，像這樣的端點鄰域組合共有8種組合。紋線跟蹤到了端點時，除了上一個被跟蹤點以及中心點外，再無其它點可以作為下一個跟蹤點，所以紋線跟蹤到端點就停止跟蹤；

2）分叉點：滿足Cn(P)=3，Sn(p)=3時，1個中心點的8鄰域共有3個相互間隔的黑點，且它們互不相連。分叉點的8鄰域組合共有12種，像素跟蹤到了分叉點也要停止跟蹤；

根據以上二種情況推出8鄰域編碼像素跟蹤提取特征算法：

1）定義變量：交叉數c和點數s，交叉數和點數是判斷特征點類型的依據。

2）定義四個二維數組：tlx[][]，tx[][]，ty[][]，tfx[];其中數組的第一維用來記錄特征點的編號，數組的第二維分別記錄特征點的類型，x坐標，y坐標和方向。

3）定義數組l[8]用來記錄當前掃描的像素的8鄰域的值。

4）首先從起始像素開始跟蹤掃描，提取出當前像素點的值，并用數組l[]記錄其8鄰域的值，計算其8鄰域中的交叉數及黑點數，通過交叉數和點數判定該點是否為端點或交叉點，若是特征點則判斷其方向(方向的判定方法見上一節8鄰域編碼逐像素跟蹤法的相關概念)，四個二維數組分別記錄該點的編號、類型、坐標和方向。調用畫點函數在當前點用紅色標識。

5）若圖像未掃描完畢則繼續掃描下一像素點，返回(4)執行，若圖像掃描完畢則結束。

4 濾除偽特征點

對整個圖像搜索完畢后得到的這些特征并非都是真實的分叉點和端點，由于指紋質量、細化、特征提取過程引入的噪聲造成了很多偽特征點，特別是圖像邊緣有很多圖像分割產生的邊界偽端點。細化圖中的噪聲一般可分為以下5類[4]：

1）毛刺：由二值圖中的紋線不平滑引起的、從毛刺的端點開始跟蹤，一般7個點內遇上分叉點；

2）短線：由二值圖中的孤立黑塊引的，其特點是從一個端點跟蹤一個較短的距離時會通上另一個端點；

3）島嶼：由二值圖中紋線模糊或紋線中有空洞引起的，其特點是兩個分叉點距離很近、且方向一般相同；

4）假小橋：按壓時由于用力不均，使得相鄰兩紋線連接起來，其特點是假小橋和相鄰兩紋線近乎垂直。

從下列分析圖五種偽特征，可以看出如果直接用特征提取算法進行處理，則提取出的偽特征點一般距離只有幾個像素，如毛刺，從毛刺產生的分叉點和端點距離一般不超過7個像素（經驗閾值）且有連接兩個偽特征點的脊線；短線產生兩個偽端點，存在一條連接兩個端點的脊線；假小橋造成的結果與島嶼類似，但兩個偽特征點之間只有一條脊線連接且與分叉點方向近乎垂直。

根據上述分析得到的偽特征點，我們可以使用下面的方法對偽特征點進行去除：

1）邊界點：目前的特征提取算法將在圖像邊緣也提取出特征點，但圖像邊緣提取出的特征點（主要是端點）大部分都是由于背景分割而產生的，因此需要對圖像邊緣的特征點進行去除。只要將圖像前景塊與背景塊相鄰部分一定閾值的特征點去掉即可；

2）毛刺和短線：毛刺產生分叉點和端點，短線產生兩個端點。因此實際算法只要查找距離在一定閾值內的特征點，并從其中一個端點出發，如果在一定閾值內使用逐像素跟蹤法可以到達另一個端點則認為其為偽特征點，兩個特征點同時去除；

3）島嶼和假小橋：島嶼和假小橋都是產生兩個分叉點。本文的判斷條件為：兩個分叉點之間距離小于一定閾值，且存在一條連接兩個分叉點的脊線則認為其為偽特征點，同時去除。

5 實驗結果分析

在Windows XP下，通過VC++開發工具構建了可視化操作平臺[1-2]，使用8位灰度圖像進行仿真，該圖像為單像素圖像，且圖像中的每個像素只有兩個值(0或255)，在算法設計中0表示圖像中的黑點，255為白點[6]。紅色的點表示通過該算法提取的特征點，由圖4，圖5可看出，圖中的偽特征點基本被有效去除。

■

圖4提取所有特征點 圖5去除偽特征點后

6 結束語

在基于自動指紋識別技術中，最常用的方法是基于指紋細節特征點匹配識別，其中特征點提取是一個至關重要的環節。快速而有效的提取出指紋圖像的特征點，可以提高整個指紋匹配系統的有效性與可靠性。

本文研究了基于8鄰域編碼逐像素跟蹤法的細節特征提取算法。通過對細化脊線進行回朔的跟蹤來判斷偽特征點，并對偽特征點予以去除，用8鄰域編碼來表示當前點的類型和8鄰域像素的狀態，然后通過跟蹤8鄰域的方法來判斷所需要跟蹤的下一點。跟蹤結果用來判別偽特征點，最后達到偽特征濾除的目的。通過試驗證明此方法較大幅度提高了特征提取的速度，縮短圖像處理后時間，基本可以滿足實際應用的需要，保證能夠準確的濾除偽特征點。

參考文獻：

[1] Gonzalez R C， Woods R E.數字圖像處理[M].2版.阮秋琦，譯.北京：電子工業出版社，2002.

[2] Sonka M， Hlavac V，Boyle R.數字圖像處理、分析和機器視覺[M].2版.艾海舟，譯.北京：北京郵電出版社，2002.

[3] 馮國進，顧國華，張保民.指紋圖像預處理與特征提取[J].計算機應用研究，2004，21(5):183-185.

[4] 尹義龍，寧新寶，張曉梅.改進的指紋細節特征提取算法[J].中國圖象圖形學報A，2002，7(12):1302-1306.

[5] Maio D.Direct Gray-Scale Minutiae Detection in Fingerprints[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1997，(19)1:27-40.

[6] 郭晶瑩，吳晴，商慶瑞.基于Matlab實現的指紋圖像細節特征提取[J].計算機仿真，2007，24(01):192-195.