一種新的指紋圖像模板細化方法

摘 要：OPTA方法是一個經典的指紋圖像細化方法，針對OPTA的不足提出的改進OPTA方法能夠得到完全細化的指紋圖像，細化后圖像紋線扭曲小。但是這兩種模板細化方法均存在細化后圖像容易產生毛刺的不足，究其原因是由于模板細化方向粗糙造成的。為此提出了16方向的細化模板，該模板以22.5°為角度單位對圖像進行更細致的細化處理，得到的細化圖像光滑幾乎無毛刺，取得了更為理想的細化效果。

關鍵詞：指紋圖像； 指紋細化； 模板； 16方向

中圖分類號：TP39141 文獻標志碼：A

文章編號：10013695(2008)09286302

New template thinning method for fingerprint image

HE Jing， FAN Jiulun

(Dept. of Information Control， Xi’an Institute of Posts Telecommunications， Xi’an 710061， China)

Abstract:OPTA method is a classical thinning method for fingerprint image. Improved OPTA method， which was proposed to overcome the insufficiency of OPTA method， could obtain a complete thinning result， and could eliminate the distortion of the skeleton. But the above two template thinning methods had the deficiency of being easy to get burrs after thinning for the cause of thinning direction of the templates was not detail. In order to deal with this problem， this paper proposed a set of 16direction thinning templates. New method uses 22.5 degrees as an angle unit to process image meticulously. The results show that thinned image is smooth and almost not has any burrs， more ideal thinning effect is obtained.

Key words：fingerprint image; fingerprint thinning; template; 16direction

生物特征識別技術以其惟一性和可靠性的特點成為近年來信息安全技術研究的熱點問題。臉像、指紋、虹膜等第一代生物特征受到了廣泛重視，指紋識別由于其易采集的特點已被應用于日常工作的很多領域。

自動指紋識別系統主要包括以下幾個部分：獲得指紋圖像、濾除噪聲、對圖像進行二值化處理、細化處理、提取指紋的特征以及特征匹配等。其中對圖像進行細化又稱骨架化，是指紋圖像預處理的關鍵步驟。細化圖像時要對圖像進行反復的掃描操作，耗時較長。因此，研究如何快速有效地對指紋圖像進行細化是非常重要的。

研究人員已經提出了很多種指紋圖像的細化方法，典型的有OPTA細化方法^[1]、Hall細化方法^[2]、Rosedfeld細化方法^[3]、ZR細化方法^[4]、Zhang和Suen方法^[5]以及改進的OPTA方法^[6]等。這些算法各有所長。其中ZR方法、Zhang和Suen方法都是采用邏輯算術的方法進行刪除判斷，細化后都能得到較平滑的骨架線；但是ZR方法會引起紋線的吞噬，而Zhang和Suen方法對斜線變形較大，有時甚至將斜線收縮為一點。OPTA方法是目前最常用的細化方法之一，它采用了8個3×3的刪除模板和兩個1×4和4×1的保留模板對指紋圖像抽取鄰域進行比對，是一種典型的模板算法，細化后無紋線吞噬現象，但是在指紋圖像的右上部和右中部會產生很多毛刺。鑒于此提出改進OPTA方法^[6]在一定程度上減少了毛刺問題，但并沒有完全解決此問題。為此本文提出了一種新的細化模板算法，能夠對圖像完全細化，細化后幾乎無毛刺，是一個具有應用價值的細化方法。

1 典型的細化模板算法

1.1 OPTA細化方法

OPTA算法是一種典型的模板細化方法^[1]。對于一幅二值化的指紋圖像，設其背景點的像素值為0，前景點的像素值為1。OPTA算法是從圖像的左上角開始，對每一個前景點元素(模板中的P5)抽取出如圖1所示的模板鄰域，并將該鄰域與給定的刪除模板(圖3)相比較。如果該鄰域的像素值與八個刪除模板中的任一個相匹配則準備刪除該點，否則保留該點。為了保持連通性，抽取元素的鄰域再與圖2的兩個保留模板進行比較。如果抽取鄰域的第二行與模板圖2(a)的第二行匹配，或抽取鄰域的第二列與模板圖2(b)中的第二列匹配，則P5點保留，否則P5才真正刪去(對該點的像素值置0)。其中模板中的“1”代表該點的像素值為1，“0”代表該點的像素值為0，“×”代表該點的像素值既可以為1也可以為0。該算法是從圖像的左上角開始到右下角結束作為一次循環，反復進行迭代，直到沒有像素值改變為止。

用OPTA算法對指紋圖像進行細化可以達到較好的細化效果，但是細化后的圖像細化不完全，存在細化后的指紋脊線不光滑、有毛刺、紋線扭曲等問題。

1.2 改進的OPTA細化方法

鑒于OPTA方法存在的不足而提出的改進OPTA算法^[6]，對OPTA方法中的刪除模板進行了一定的改進，可以有效去除紋線邊緣上的突出物。該算法的具體步驟與OPTA方法相同，都是抽取當前像素點的鄰域與刪除模板和保留模板進行比對，來決定像素點的刪除與否。所不同的是該算法采用統一的4×4模板，其抽取鄰域以及刪除模板、保留模板如圖4~6所示。

2 新的細化方法

OPTA方法和改進的OPTA方法均存在一些不足，分析其原因，發現細化模板不完善是細化后產生毛刺的主要原因。OPTA方法和改進的OPTA方法的刪除模板只考慮了從東、南、西、北、東南、東北、西南、西北8個方向刪除像素點，而實際上用這樣的刪除模板是比較粗糙的，會使每次細化掃描都忽略好多應該刪除的像素點，細化后的圖像出現毛刺，且細化迭代次數多。

本文提出的算法以22.5°為單位建立16方向的刪除模板和保留模板，即取上述8 個方向中任意兩個相鄰方向的角平分線方向，如東與東北方向夾角的角平分線方向（如圖7所示1方向）。抽取的當前像素點的鄰域如圖8。其中P5是當前像素點，抽取P1~P25這個5×5模板與刪除模板(圖9)相比對，若與任一個刪除模板相匹配則準備刪除該像素點；否則保留該像素點。再將該鄰域中的斜體部分與保留模板(圖10)相比對，若與其中之一相匹配則保留該點，否則真正刪去該點。該算法也是從圖像的左上角開始到右下角結束作為一次循環；反復進行迭代，直到沒有像素值改變為止。

分析圖9和10兩組模板，刪除模板中圖9(a1)旋轉得到了(a5)(a9)(a13)三個模板，(a2)旋轉得到了(a6)(a10)(a14)三個模板，(a3)旋轉得到了(a7)(a11)(a15)三個模板，(a4)旋轉得到了(a8)(a12)(a16)三個模板，以上這16個模板處理圖7對應的單數方向；(a17)旋轉得到了(a18)(a19)(a20)三個模板，這四個模板處理圖7中對應的北、西、南、東四個方向；(a21)旋轉得到了(a22)(a23)(a24)三個模板，處理圖7中的東北、西北、西南、東南四個方向。保留模板中圖10(b1)~(b4)分別旋轉90°得到(b5)(b6)(b7)(b8)。這意味著將相同的模板應用于不同的角度，其好處一方面使細化更加準確，另一方面在不增加處理時間的同時減少了迭代次數。

3 實驗結果

筆者在256 MB內存的計算機上用MATLAB語言編程實現了該算法，實驗選取了FVC2000指紋庫中的指紋圖像。實驗結果如圖11~14。

由圖12可見，OPTA方法得到的細化圖像細化不完全，毛刺較多，紋線扭曲大；由圖13可見，改進的OPTA方法得到的細化圖像雖細化完全，但毛刺較多；由圖14可見，本文提出的新方法得到的指紋圖像光滑幾乎無毛刺。另外，由表1可見，本文提出的方法在獲得更好的細化結果時并沒有以犧牲處理時間為代價，對于同一幅指紋圖像，其處理時間介于OPTA與改進的OPTA方法之間。OPTA方法因為其模板較小，細化僅從8個方向進行，處理耗時最短，但是這種方法得到的細化結果（圖12）并不令人滿意，紋線扭曲大，毛刺多，這就給指紋識別的下一步處理中提取特征點帶來了很大的麻煩。在改進的OPTA方法基礎上，調整了刪除模板和保留模板，在一定程度上減少了毛刺，但是這種方法是在迭代次數相近的情況下，以增加處理時間為代價。而本文提出的新方法，細化效果有了明顯的改善，處理時間卻介于OPTA與改進的OPTA方法之間。另外，本文方法的迭代次數明顯減少，表明通過較少的迭代就能比較準確地到達紋線中軸，這也是本文方法取得較好細化效果的一個原因。

4 結束語

本文提出的16方向模板細化算法從更精細的角度出發處理指紋圖像，得到的細化圖像光滑幾乎無毛刺、無紋線扭曲和吞噬現象，細化效果比經典的OPTA方法和改進的OPTA方法更好。綜合細化效果、處理時間和迭代次數來看，本文提出的算法是一種具有實用價值的細化方法。

表1 三種模板細化方法實驗結果比較

模板細化方法處理耗時/s迭代次數

OPTA方法12.792 77610

改進的OPTA方法31.653 00511

本文方法28.426 5516

參考文獻：

［1］CHIN R T， WAN H K， STOVER D L，et al. A onepass thinning algorithm and its parallel implementation[J]. Computer Image Processing，1987，40(1):3040. 

[2]HALL R W. Optimally small operator supports for fully parallel thinning algorithms[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1993，15(8):828833.

[3]PAVLIDIS T. Algorithms for graphics and image processing[M].Washington DC: Rockville， Computer Science Press，1982.

[4]GUO Zicheng， RICHARD W H. Parallel thinning with twosubiteration algorithms[J].Communications of ACM， 1989，32(3):359373.

[5]ZHANG T Y， SUEN C Y.A fast thinning algorithm for thinning digital patterns[J].Communications of ACM，1984，27(3):236239.

[6]馮星奎，李林艷，顏祖泉. 一種新的指紋圖像細化算法[J]. 中國圖象圖形學報，1999，4(10):835838