錢 超， 王福明

（中北大學(xué)，信息與通信工程學(xué)院，山西太原 030051）

0 引言

指紋識別的效率和好壞很大程度上依賴于指紋圖像的預(yù)處理。一個好的預(yù)處理方法將大大減少偽特征點數(shù),減少對原始采集圖像好壞的依賴。一個優(yōu)秀的生物特征識別系統(tǒng)要求能實時迅速有效地完成其識別過程。所有的生物特征識別系統(tǒng)都包括如下幾個處理過程：采集、比對和匹配。指紋識別處理也一樣，它包括指紋圖像采集、指紋圖像預(yù)處理、特征提取、特征值的比對與匹配等過程。使用指紋識別方式的優(yōu)點在于它的可靠、方便且容易被接受[1]。

預(yù)處理在整個自動指紋識別系統(tǒng)的過程中是很關(guān)鍵的一步，是正確地進行特征提取、匹配等操作的基礎(chǔ)。采集到的指紋圖像由于各種原因的影響，是一幅含多種不同程度噪聲干擾的灰度圖像，指紋脊線可能被斷開、橋接或模糊等，而含有大量噪化的指紋脊線結(jié)構(gòu)會影響著自動指紋識別系統(tǒng)的性能。指紋預(yù)處理是指紋特征提取前的不可缺少的一個重要環(huán)節(jié)，主要用于突出指紋圖像中的紋理、方向信息，消除或者減弱噪聲等無用信息。指紋圖像預(yù)處理通常包括指紋圖像分割、圖像增強、二值化、細化等[2]。

1 指紋圖像二值化

指紋圖像二值化后，其紋線寬度是不均勻的，這是因為原始圖像的質(zhì)量受到壓力大小的影響和圖像采集過程中噪聲的影響而造成的。雖然紋線的寬度并不包含指紋的特征信息，但它的不均勻性會影響指紋特征的提取，并且指紋識別只對紋線的走向感興趣，并不關(guān)心它的粗細，因此為了減小數(shù)據(jù)量，提高識別準確性，應(yīng)對指紋圖像進行細化處理[3]。

指紋圖像細化方法的一種是可以直接從灰度圖像進行，但難以尋找紋線的中心點；另一種則是廣泛使用的，把灰度線條圖像變成二值圖像再進行細化。細化是刪除指紋紋線的邊緣像素，使之只有一個像素寬度。細化時應(yīng)保證紋線的連接性、方向性和特征點不變，還應(yīng)保持紋線的中心基本不變。指紋圖像的細化是接受二值化后的指紋圖像，并為指紋圖像的特征提取和匹配提供圖像。細化方法應(yīng)滿足下列條件：

(1)迭代必須收斂。(收斂性)

(2)不破壞紋線的連接性。(連接性)

(3)不引起紋線的逐步吞食。(拓撲性)

(4)保護指紋的細節(jié)特征。(保持性)

(5)骨架紋線的寬度為一個像素。(細化性)

(6)骨架盡可能接近紋線中心。(中軸性)

(7)算法簡單、速度快。(快速性)

細化從實現(xiàn)的方法上分，可分為兩大類：一類是從外到內(nèi)逐點剝?nèi)ザ祱D像的邊緣點，如Hildth算法；令一類是從內(nèi)到外，找到某一中間點，然后按掃描方向?qū)ふ移?鄰域內(nèi)也為線條紋中間像素的點，逐次取得細化線。第一種方法中間定位性比較好，易于實現(xiàn)，但往往要經(jīng)過若干次迭代運算才能得到細化線，速度較慢：第二種方法能保持較好的連通性，但情況復(fù)雜，中間定位不準。細化算法按細化處理過程可分為串行細化、并行細化和串并行混合細化。串行細化一次只能處理一個像素，下次操作由上次的操作結(jié)果決定。并行細化算法是同時對滿足給定條件的像素進行處理，即一次處理所有像素的一個子集[4]。

按細化后圖像的連通性可將細化算法分為4連通細化、8連通細化和混合連通細化，4連通指的是細化后圖像在水平垂直4個方向上的連通，8連通是細化后圖像在水平垂直4個方向再加上正反45度共8個方向上的連通，混合連通是指細化后圖像既有4連通也有8連通。其他常用于指紋細化的算法還有方向圖中心掃描細化算法、紋線跟蹤細化算法等。

淺閱讀是走向深閱讀過程中的起步階段。在這個階段，閱讀主體可以大致擬出閱讀的提綱或思維導(dǎo)圖，至少在腦中會形成對閱讀內(nèi)容的總體印象，判斷出下一步需要詳讀的部分和略讀的部分。

現(xiàn)有的指紋細化算法存在很多問題，像細化不徹底、紋線吞噬、骨架偏離紋線中心、細化效率低下等。其中紋線細化不徹底特別是紋線分叉點處細化不徹底，影響紋線分叉點的正確提取。紋線的吞噬往往導(dǎo)致提取的紋線端點位置移動較大。

通過對一般細化算法存在的問題，進行改進，以減少偽特征的個數(shù)，對細化算法中的消除模板和保留模板進行改進，并模糊了消除模版的概念，擴大了消除模板的范圍[5]。

2 改進的OPTA算法

OPTA算法是一種典型的基于模板的圖像細化算法（如圖1至圖3所示），算法核心是通過應(yīng)用消除和保留這兩套模板來達到對原圖細化的目的。OPTA算法用到的是與其相鄰的10個像素。從圖像的左上角元素開始進行，首先用該像素的8個鄰域與8個細化模板(消除模板)相匹配，若與任何消除模板都不匹配，不做任何改變；若與其中的任一消除模板匹配，則再與保留模板相匹配，若存在與一個保留模板匹配，則不做任何改變，若與任何保留模板都不匹配，則把該像素改為0。該算法按從左上角到右下角的順序進行，處理完一個過程即為一次迭代，“迭代”反復(fù)進行，直到?jīng)]有一個像素的值被改變?yōu)橹?。其中迭代的次?shù)依賴于圖像的大小、紋線的形狀和圖像的質(zhì)量[7]。

圖1 OPTA算法所取的鄰域

圖2 OPTA細化算法的消除模板(×表示任意，可以為0或1)

圖3 OPTA細化算法的保留模板(×表示任意，可以為0或1)

下面給出幾個細化中的定義：

目標點與背景點：目標點指像素值為1的點，背景點指像素值為O的點。

單像素寬：考察紋線上每一點的8鄰點，紋線端點的8鄰點中只有一個目標點，紋線連續(xù)點的8鄰點有兩個目標點，紋線分叉點有3個目標點，且每點8鄰點最多只有3個目標點。符合上述條件即為單像素寬。

邊界點：屬于目標點，且其4鄰點中至少有一個為背景點。

端點：屬于邊界點，且其8鄰點中只有一個屬于目標點。

關(guān)鍵點：刪除該點后會引起紋線的不連通，又叫做斷點。

消除模板：判斷是否符合消除的條件。

保留模板：對符合消除條件的像素，判斷與其相鄰的同一行或同一列是否有非0點，如沒有則直接刪除該點，否則保留該點[9]。

OPTA算法能滿足收斂性、連接性、拓撲性和保持性，能得到較好的細化效果。但該算法得到的細化骨架存在在分叉點處細化不徹底，細化后的紋線不光滑，紋線有較多毛刺且紋線扭曲不在紋線中心的問題。因此不滿足細化的中軸性和細化性。同時，它采用兩個不同大小模板分兩次進行計算，其速度也受到影響。為了解決OPTA算法存在的問題，人們提出了一種改進的OPTA算法，改進后的OPTA算法（見圖4）消除模板仍采用OPTA的消除模板。而在保留模板中，當前中心點的去留除了與消除模板有關(guān)外，還取決于另一個“l(fā)"值周圍點的情況：若該“1"值為中心的3×3鄰域和消除模板相同，則該“1"值應(yīng)該被刪除，否則刪除當前中心點。

圖4 改進的OPTA算法的保留模板

3 改進的OPTA算法的不足及改進

改進后的OPTA算法仍然存在一定的局限性，突出表現(xiàn)在某些紋線方向位置容易產(chǎn)生毛刺。經(jīng)過研究發(fā)現(xiàn)，毛刺的出現(xiàn)對紋線方向十分敏感。紋線方向角在第2像限的時候容易出現(xiàn)毛刺，特別是紋線近似水平和垂直的時候.毛刺的出現(xiàn)尤其明顯。故推測毛刺的產(chǎn)生和模板不完全對稱有關(guān)。對于圖5(a)，可以看到2個小的毛刺，但是細化沒有去掉。對于5(c)中的紋線，細化完成后同樣產(chǎn)生了毛刺。主要原因是由于消除模板中沒有包含這種情況。

圖5 毛刺的細化

分叉處的細化不徹底主要原因是由于消除模板不完善。如圖6（a），第四行第三列的點是個多余的像素點，刪除這個點并不影響紋線的連通線；對于圖6（c），第二行第三列的點是多余的像素點，造成了不完全的細化，但若只是刪除該點，又會造成紋線的中斷，所以應(yīng)對其進行一定程度的細化，即將第二行第三列的點刪除，即置為0，同時將第二行第四列的點置為1，保持了紋線的連通性[10]。

圖6 分叉點處的細化

針對上文中對毛刺的產(chǎn)生和分義處的細化小徹底的原因分析，本文使用了針對性的消除模板和保留模板。針對毛刺的消除模板如圖7。針對未完全細化的情況，引入特定的消除模板，如圖8所示。

圖8中，a-d是對應(yīng)于第一種未完全細化的情況的消除模板，e-h是對應(yīng)于第二種未完全細化情況的消除模板。a-d模板中的中心點為應(yīng)該刪除的點，e-h中荻色背景的點是進行了變換，即將模板中有灰色背景的對應(yīng)位置中的0變換成1，而l變換成0。選樣，第二種未完全細化的情況就得到了有效的解決。

圖7 針對毛刺的消除模板

圖8 針對未完成細化的消除模板

圖9 修正后的消除模扳(一)

以在OPTA提出的消除模板為基礎(chǔ)，在基礎(chǔ)上添加上述12個消除模板；以文獻[6]提出的保留模板為基礎(chǔ).在消除模板的基礎(chǔ)上修正保留模板。修正后的結(jié)果如圖9～圖11所示。

圖10 修正后的消除摸板㈡

圖11 修正后的消除模板(三)

把消除模板分為3類：類一：如圖 9中(a)-(h)，類二：如圖10中(i)-(p)，類三：如圖11中(q)-(t)。(i)-(p)是屬于可直接刪除的，不需要進行保留模板匹配，因為(m)-(p)是OPTA原消除模板的特例，這類模板應(yīng)先于OPTA原消除模板進行匹配，以免重復(fù)計算。細化從圖像的左上角開始進行，對于每一像素取其8個鄰域的像素，與類二的消除模板匹配，若存在一個模板與其匹配，則刪除該點(即修改為0)。否則與類一、類三匹配，若不存在模板與其匹配，則停止：若存在一個模板與其匹配，記匹配的消除模板為m，并取該像素的i5鄰域的像素，與保留模板相匹配，如不存在任何保留模板匹配時，若m為類一，則刪除該點，否則，對相對應(yīng)的模板的對應(yīng)位置進行變換。

4 實驗結(jié)果及分析

在采用OPTA算法對指紋圖像進行細化操作所得的細化結(jié)果中產(chǎn)生的毛刺很多，在三叉點處細化不全，在處理后的結(jié)果圖中可以看到有些指紋的紋線發(fā)生了斷裂的情況，出現(xiàn)了一些相互不連接的斷線。破壞了指紋本身的連接性和拓撲性。改進的OPTA細化算法與OPTA算法相比在細化整體效果上有了明顯提高，尤其是對細化過程中產(chǎn)生的毛刺和細化不徹底的處理得到了很好的效果，紋線連接性好。在計算速度方面，OPTA算法采用兩個大小不同的模板進行兩次計算，計算速度慢，改進的OPTA算法克服了OPTA的這個缺點。經(jīng)過以上的分析可知，本文中采用MATLAB7.0進行實驗,指紋庫采集分辨率為500 dpi,指紋采集設(shè)備為PIS2004光學(xué)指紋采集儀,圖像尺寸大小為640×480，實驗僅作同源樣本間的交叉比對。這表明指紋頻率能量能準確反映樣改進的OPTA細化算法是合理可行的，并且能得到較好的細化結(jié)果，滿足細化處理的要求。實驗結(jié)果如圖12所示。

圖12 實驗結(jié)果

[1]陳茂林,戚飛虎.基于最優(yōu)梯度估計及小波變換的指紋圖像處理技術(shù)[J].上海交通大學(xué)學(xué)報,2001,35(2):181-183.

[2]Ling Hong,Wang Yfei,Anil K Jain.Fingerprint image enhancement：algorithm and performance evaluation[J].IEEE Transactions on PaRem Analysis and MachineIntelligence,1 998,20(8):777-789.

[3]柯渝.指紋識別系統(tǒng)中的預(yù)處理與后處理研究[D].廈門:廈門大學(xué),2004.

[4 ]Jie Zhou,Jinwei Gu.A model—based method for the computation of fingerprints’orientation field[J].IEEE Transactions On Image Processing,2004,13(6):821-835.

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

[5]王業(yè)琳,寧新寶,尹義龍.指紋圖像細化算法的研究[J].南京大學(xué)報,2003(7):468-475.

[6]唐海勇,唐世鋼,邵巖.線條紋圖像的細化[J].哈爾濱理工大學(xué)學(xué)報,2002(4):50-53.

[7]Jie Zhou,David Zhang,C.Y Wu.Orientation analysis for rotated human facedetection[J].Image Vision Compute,2002(20):257-264.

[8]馮星奎,李林艷,顏祖泉.一種新的指紋圖像細化算法[J].中國圖象圖形學(xué)報,1999(10):835-838.

[9]趙偉.指紋圖像的預(yù)處理和細化算法的研究[D].重慶:重慶大學(xué)數(shù)理學(xué)院,2007.

[10]閏俊紅.指紋圖像預(yù)處理研究[D].呼和浩特:內(nèi)蒙古工業(yè)大學(xué),2006.