【文章內(nèi)容簡介】 ；并行細(xì)化算法則每次同時對所有的像素或它的一個子集進(jìn)行處理。串行細(xì)化算法即單連通細(xì)化(OPTA)算法[11]通過構(gòu)造一組指紋細(xì)化模板，對于脊線上的每個像素點(diǎn)取其一定范圍的鄰域，如果該鄰域與模板符合就保留該當(dāng)前點(diǎn)，不符合則刪除。通常，為了得到更加準(zhǔn)確的骨架，往往采用兩組模板，一組被稱為刪除模板，用于決定當(dāng)前點(diǎn)是否刪除，若不符合刪除模板，則保留；若符合刪除模板，則還要與另一組被稱為保留模板的模板比較，若符合保留模板，則保留；若不符合保留模板，則最終刪除。OPTA 算法能滿足收斂性、連接性、拓?fù)湫院捅３中?，對指紋圖像的細(xì)化能達(dá)到較好的效果。本章簡要闡述了指紋預(yù)處理階段中的圖像歸一化、濾波增強(qiáng)、二值化以及細(xì)化等步驟，并對各個步驟的常用的算法的研究狀況和優(yōu)缺點(diǎn)做了簡要介紹。3 指紋圖像特征的提取指紋圖像的最終匹配還要依賴指紋的特征點(diǎn)來進(jìn)行。采集到的指紋圖像在經(jīng)過歸一化，增強(qiáng)，二值化和細(xì)化之后基本保留了原始指紋的紋理特征。目前流行的自動指紋識別系統(tǒng)大多采用基于細(xì)節(jié)點(diǎn)的表達(dá)方式，故在進(jìn)行指紋的細(xì)化及細(xì)化處理之后要進(jìn)行指紋的特征提取，以方便最后的指紋匹配。全局特征[12]是指可以直接觀察到的宏觀特征，必須通過圖像整體獲得。目前最常見的表示指紋圖像的全局特征是按照指紋的脊線總體結(jié)構(gòu)來確立的，具體包括指紋的紋形、模式區(qū)、核心點(diǎn)(core)、三角點(diǎn)(delta)和脊線數(shù)五個特征。（1）紋形，是指指紋脊線整體走向，主要有三大類：拱型（arch）、帳型(tended arch)、左箕型(left loop)、右箕型(right loop)、斗型(whorl)、雙箕型(double whorl)。拱型沒有中心點(diǎn)和三角點(diǎn)，帳型和箕型有一個中心點(diǎn)和三角點(diǎn)，雙箕型有兩個中心點(diǎn)[13]。（2）模式區(qū)，是指包含了指紋圖像的大部分總體特征的區(qū)域，通過這個區(qū)域也能夠分辨出指紋是屬于哪個類型的。（3）核心點(diǎn)(core)，是指指紋脊線的漸進(jìn)中心點(diǎn)。（4）三角點(diǎn)(delta)，一般是指從中心點(diǎn)開始的第一個分叉點(diǎn)、斷點(diǎn)、孤立點(diǎn)等等，常與核心點(diǎn)一起稱為奇異點(diǎn)。（5）脊線數(shù)，指的是模式區(qū)內(nèi)指紋脊線的數(shù)量。全局特征一般用在大規(guī)模指紋庫中，實(shí)現(xiàn)快速分類，也可以用在特征匹配中的粗匹配階段。局部特征是指指紋拓?fù)鋱D中的幾種有效的特征，比如指紋紋路是不是連續(xù)的，方向是不是一致，具體到細(xì)節(jié)特征就表現(xiàn)為斷點(diǎn)、分叉點(diǎn)、交叉點(diǎn)、橋、環(huán)等等，這些通常稱為特征點(diǎn)。這些特征點(diǎn)之間，特征點(diǎn)與周圍脊線之間等等都包含了豐富的信息，比如特征點(diǎn)的類型、方向、位置等等。特征匹配就是利用這些信息進(jìn)行的。據(jù)統(tǒng)計(jì)，這幾類特征點(diǎn)占特征點(diǎn)的比率如3—1所示。從表中可以發(fā)現(xiàn)，端點(diǎn)和分叉點(diǎn)占特征點(diǎn)91%，而交叉形、橋形以及環(huán)形三類總共只占9%左右[14]。這一方面說明了幾乎所有的指紋都有端點(diǎn)和分叉點(diǎn)，而且數(shù)量豐富；另一方面也反映了不是所有的指紋都有橋形、環(huán)形等特征點(diǎn)，而且即使有數(shù)量也比較少。因此為了能普遍的表征指紋圖像，一般選用端點(diǎn)和分叉點(diǎn)作為指紋圖像特征點(diǎn)。圖3—1特征點(diǎn)類型及所占比例一幅質(zhì)量比較好的指紋圖像，一般有40—100個特征點(diǎn)，但真正匹配時，由于受指紋采集時外界影響比較大，不可能實(shí)現(xiàn)100%匹配。英國司法界認(rèn)為有12個細(xì)節(jié)點(diǎn)匹配，就可以認(rèn)為兩幅指紋相同，美國FBI認(rèn)為8個細(xì)節(jié)點(diǎn)匹配就足夠了[1516]。指紋特征提取是指紋自動識別的核心技術(shù)之一，它一般分為兩個階段：提取特征點(diǎn)和偽特征點(diǎn)的剔除。迄今為止，人們已經(jīng)對指紋細(xì)節(jié)特征提取算法進(jìn)行了很多的研究工作。最早提出特征點(diǎn)提取算法的是美國聯(lián)邦調(diào)查局(FBI)的自動指紋識別技術(shù)研究人員。他們采用了一種二級算法，用自適應(yīng)“編輯”方法將指紋圖像二值化，再從二值化后的指紋圖像中提取特征點(diǎn)。該算法的提出在指紋識別領(lǐng)域具有開拓性的意義，并且該算法在相當(dāng)一段時間內(nèi)被廣泛地用作細(xì)節(jié)特征點(diǎn)的標(biāo)準(zhǔn)算法，獲得了廣泛的應(yīng)用。最常用的特征點(diǎn)提取算法有兩類：一是從灰度圖像直接提取特征點(diǎn)；二是對預(yù)處理細(xì)化后的圖像進(jìn)行提取特征點(diǎn)。下面將對這兩種特征點(diǎn)提取算法進(jìn)行介紹比較，并確立本文將要采用的特征點(diǎn)提取算法。直接灰度圖像指紋特征提取[1718]的原理是使用模式識別的方法跟蹤灰度圖上的紋線走向。正常區(qū)域指紋的紋線應(yīng)該是連續(xù)的，當(dāng)出現(xiàn)斷裂終止分開時，則停下來根據(jù)規(guī)則進(jìn)行特征點(diǎn)判定。該算法主要由幾個緊密聯(lián)系的模塊組成：（1）跟蹤步進(jìn)模塊，主要負(fù)責(zé)預(yù)測下一步跟蹤方向和步長，用來沿紋線前進(jìn)一步。（2）中心點(diǎn)確定模塊，負(fù)責(zé)確定紋線的脊部中心點(diǎn)，使跟蹤方向不斷調(diào)整，始終沿紋線的中心前進(jìn)。（3）標(biāo)記模塊，用來給跟蹤過的紋線作記號，以免重復(fù)跟蹤，陷入死循環(huán)。（4）特征判定模塊，負(fù)責(zé)當(dāng)跟蹤到達(dá)紋線流向異常區(qū)域時，判定是否為特征點(diǎn)及特征點(diǎn)類型。具體算法如下[19]：（1）計(jì)算指紋圖像的方向圖，一般以塊方向作為指紋的方向。（2）從初始點(diǎn)出發(fā)，根據(jù)指紋圖像的方向信息，在該處的法線方向上，半個指紋周期內(nèi)，求取灰度分布的最大值和最小值，并以該最大值處的像素點(diǎn)作為新的出發(fā)點(diǎn)。（3）從新的出發(fā)點(diǎn)出發(fā)，沿指紋圖像的方向圖的方向前進(jìn)一定步長(算法最開始是按固定步長進(jìn)行跟蹤的，后來發(fā)展到自適應(yīng)步長跟蹤)，繼續(xù)在發(fā)現(xiàn)方向求取灰度分布的最大值和最小值，仍然以最大值處的像素點(diǎn)作為新的出發(fā)點(diǎn)。（4）不斷重復(fù)步驟3，實(shí)現(xiàn)脊線跟蹤，直到求取的灰度分布的最大值出現(xiàn)明顯的變小，與最小值差不多，甚至相等時，停止跟蹤，說明己經(jīng)到脊線的末端，此處即為特征點(diǎn)端點(diǎn)處。若跟蹤到的脊線與先前己經(jīng)跟蹤過的脊線相交，停止跟蹤，求取兩條脊線交點(diǎn)位置，此處即特征點(diǎn)分叉點(diǎn)。直接從灰度圖像中提取特征的算法一般是對灰度指紋紋線進(jìn)行跟蹤，根據(jù)跟蹤結(jié)果尋找特征的位置和判斷特征的類型。這種方法省去了復(fù)雜的指紋圖像預(yù)處理過程，但是特征提取的算法卻十分復(fù)雜，而且由于噪聲等因素影響，提取的特征信息(位置、方向等)也不夠準(zhǔn)確?；诩?xì)化圖像的模板匹配法[2021]，是先將指紋圖像經(jīng)過圖像歸一化、增強(qiáng)、二值化和細(xì)化等一系列的預(yù)處理得到細(xì)化的指紋圖像，再通過構(gòu)建像素的33鄰域(如圖3—2所示)提取指紋圖像的特征點(diǎn)。圖中P為待測像素點(diǎn)，Pl、P2P9為P的鄰域，為這8個鄰域像素的相鄰像素的灰度值(此時己二值化，所以灰度值只可能為0或l)從0變?yōu)?，或者從1變?yōu)?的次數(shù)。為8鄰域像素中為1的像素的個數(shù)，具體按式(3—1)、(3—2)計(jì)算。 (其中) (3—1) (3—2)通過分析可知，細(xì)化后的指紋圖像的鄰域狀態(tài)如圖3—3所示。對于脊線上的像素，可根據(jù)其鄰域的和數(shù)值判定此時P像素點(diǎn)的狀態(tài)。通過分析可以發(fā)現(xiàn)和數(shù)值僅存在以下三種情況：（1）若P點(diǎn)為脊線上的點(diǎn)，且=2， =l，則可判定像素點(diǎn)P為端點(diǎn)，如圖3—3中E點(diǎn)。（2）若P點(diǎn)為脊線上的點(diǎn)，且=4， =3或者4，則可判定像素點(diǎn)P為脊線上的連續(xù)點(diǎn)，即不是特征點(diǎn)，如圖3—3中的C1點(diǎn)、C2點(diǎn)、C3點(diǎn)、C4點(diǎn)。（3）若P點(diǎn)為脊線上的點(diǎn)，且=6， =3，則可判定像素點(diǎn)P為分叉點(diǎn)，如圖3—3中點(diǎn)B點(diǎn)。P1P2P3P8PP4P7P6P5圖3—2鄰域示意圖EC1C2BC3C4圖3—3細(xì)化后的指紋圖像具體算法如下：（1）從端點(diǎn)出發(fā)，端點(diǎn)的八鄰域只有一個點(diǎn)的灰度值為1，該點(diǎn)就是脊線跟蹤的下一點(diǎn)。（2）對脊線中間連續(xù)點(diǎn)，因?yàn)榘肃徲蛑挥袃蓚€點(diǎn)灰度值為1，除去上一個被跟蹤的點(diǎn)，剩下的一點(diǎn)即為下一個待跟蹤點(diǎn)。（3）設(shè)集合Ω={xi,yi,zi,gi}，根據(jù)及的值判斷被跟蹤點(diǎn)的類型，并記錄下端點(diǎn)或分叉點(diǎn)的橫坐標(biāo)xi，縱坐標(biāo)yi，及特征點(diǎn)的類型zi，gi是特征點(diǎn)的角度跟蹤結(jié)束條件。端點(diǎn)的角度取從端點(diǎn)為起點(diǎn)的端線的角度，分叉點(diǎn)的角度取相對最小分支線的角度。端線及分支線的角度求法為：即從一個特征的位置出發(fā)坐標(biāo)為(xi,yi)搜索到步長為7是最后一點(diǎn)坐標(biāo)為(x,y)。如下式3—3。gi=arctg(yyi)/(xxi) (3—3)對指紋圖像中的所有像素進(jìn)行處理，分別記錄下所有檢測到的端點(diǎn)和分叉點(diǎn)，即完成了特征提取的第一步──特征的提取。以上即是常用的兩種特征點(diǎn)提取算法，通過比較不難發(fā)現(xiàn)：基于灰度直接提取算法原理比較簡單，簡化了圖像增強(qiáng)、二值化步驟，直接求取脊線并得到特征點(diǎn)。并且由于步驟的簡化一定程度上降低了偽特征點(diǎn)出現(xiàn)的概率。這兩點(diǎn)是該算法的最大優(yōu)點(diǎn)。但是該算法對圖像的質(zhì)量要求比較高，僅適合圖像質(zhì)量非常好，脊線清晰的指紋圖像，對于較模糊的指紋圖像則無能為力。另外，該算法脊線跟蹤的步長不好確定，即使采用自適應(yīng)步長也只是稍微降低丟失特征點(diǎn)的情況，沒有從根本上改觀，加上是利用灰度分布直方圖來確定特征點(diǎn)的，因此特征點(diǎn)的位置信息并不十分精確，有可能與實(shí)際的位置出現(xiàn)偏差，尤其是在圖像模糊的情況下，更是相差甚遠(yuǎn)?；诩?xì)化圖像的模板匹配法，算法稍微復(fù)雜一下，跟前一算法相比，多了圖像增強(qiáng)和二值化。但是由于模板匹配法采用的是遍歷原則，即對所有像素都進(jìn)行特征點(diǎn)判定，所以不會出現(xiàn)第一種算法那樣的特征點(diǎn)丟失的問題。另外由于在預(yù)處理階段增加了圖像增強(qiáng)和二值化，所以在算法的魯棒性方面比第一種算法更好。所以考慮到指紋識別系統(tǒng)的魯棒性，以及特征點(diǎn)提取算法的可靠性本文采用第二種算法。提取指紋圖像的細(xì)節(jié)特征，是在細(xì)化圖像進(jìn)行的。由于圖像質(zhì)量和噪聲的干擾，經(jīng)過預(yù)處理后的細(xì)化圖像上存在大量的偽特征點(diǎn)，所以特征提取后可能產(chǎn)生多達(dá)一、兩萬個細(xì)節(jié)特征點(diǎn)，其中包含了大量的偽特征點(diǎn)，這些偽特征點(diǎn)的存在，不但使匹配的速度大大降低，還使指紋識別性能急劇下降，造成識別系統(tǒng)的誤拒率和誤識率的上升，因此在進(jìn)行指紋匹配之前，盡可能將偽特征點(diǎn)去除，同時保留真特征點(diǎn)。在特征提取算法提取的特征點(diǎn)集中存在了一定數(shù)量的偽特征點(diǎn)，這是不可避免的，必須想辦法剔去偽特征點(diǎn)，才能確保特征匹配能夠準(zhǔn)確的進(jìn)行。從上文細(xì)化后的指紋圖像上不難發(fā)現(xiàn)，由于細(xì)化后的指紋圖像出現(xiàn)了毛刺、粘連、斷點(diǎn)等現(xiàn)象。出現(xiàn)這樣的情況的原因有多種，一方面原始圖像本來就存在模糊區(qū)域和粘連區(qū)域，另一方面在指紋圖像的預(yù)處理過程中，雖然多次進(jìn)行了濾波處理，但是噪音依然存在，并且有相當(dāng)一部分帶入到細(xì)化后的指紋圖像中，通過特征點(diǎn)的提取轉(zhuǎn)化為偽特征點(diǎn)。大量偽特征點(diǎn)的存在將導(dǎo)致匹配效率降低，成功匹配率降低，嚴(yán)重影響指紋識別系統(tǒng)的指標(biāo)，因此在匹配前必須對偽特征點(diǎn)進(jìn)行剔除。下面分析一下毛刺、短線、斷線、假橋以及環(huán)這幾種主要的噪聲的特點(diǎn)，以及因它們而產(chǎn)生的偽特征點(diǎn)的特性[22]，方便針對它們各自的特點(diǎn)設(shè)計(jì)剔除算法。（1）毛刺現(xiàn)象，毛刺的出現(xiàn)有多方面的原因，比如受隨機(jī)噪聲的影響而形成的，還有部分是受圖像增強(qiáng)和細(xì)化處理產(chǎn)生的。一個毛刺經(jīng)過提取特征點(diǎn)后會產(chǎn)生一個偽端點(diǎn)和一個偽分叉點(diǎn)。這類偽特征點(diǎn)的特點(diǎn)是它們往往成對出現(xiàn)，而且偽端點(diǎn)和偽分叉點(diǎn)的距離非常近，一般小于細(xì)化前的脊線寬度的一半。（2）短線現(xiàn)象，一般在指紋采集時手指比較臟或者采集頭上有灰塵等容易出現(xiàn)比較多的短線。短線的特點(diǎn)就是會產(chǎn)生兩個偽端點(diǎn)，該兩個端點(diǎn)相距很近，位于同一脊線上。（3）斷點(diǎn)現(xiàn)象，指紋采集時如果手指比較干燥，那么采集到的指紋圖像有可能出現(xiàn)不少斷點(diǎn)。另外手指褶皺、傷疤也容易產(chǎn)生斷點(diǎn)現(xiàn)象。斷點(diǎn)會產(chǎn)生兩個偽端點(diǎn)，而且這兩個偽端點(diǎn)也相距非常近，但是與短線不同的是這兩個偽端點(diǎn)是分布在兩條脊線上，沿脊線方向兩個偽端點(diǎn)之間沒有脊線。（4）假橋現(xiàn)象，當(dāng)手指過潮濕或者臟時，采集的指紋圖像容易出現(xiàn)多脊線假橋(有時也叫橋)的現(xiàn)象，即本來不相連的兩條脊線連在了一起。一般在假橋出現(xiàn)的地方提取的特征點(diǎn)為一對偽分叉點(diǎn)。其特點(diǎn)是這兩個分叉點(diǎn)的距離一般近似等于平均脊線間距，而且兩個偽分叉點(diǎn)間的連線近似垂直于其局部鄰域的脊線方向。（5）環(huán)現(xiàn)象，通常也叫孔。主要是由于隨機(jī)噪聲影響產(chǎn)生的。在出現(xiàn)環(huán)的地方提取特征點(diǎn)一般出現(xiàn)兩個到三個偽分叉點(diǎn)。其特點(diǎn)是一般這兩個偽特征點(diǎn)的距離非常小，而且這兩個偽特征點(diǎn)間的連線與所在的脊線方向近似相同。從上文提取的特征點(diǎn)，不難發(fā)現(xiàn)，位于指紋四周邊緣存在數(shù)量眾多的特征點(diǎn)(包括真特征點(diǎn)和偽特征點(diǎn))。這些特征點(diǎn)是由于在指紋采集時，指紋接觸采集頭的邊界，脊線的起始點(diǎn)。這些起始點(diǎn)雖然也是屬于端點(diǎn)，但是由于它們其實(shí)是不存在的，只是因?yàn)椴杉佑|面積的原因才產(chǎn)生的。它們又不屬于上節(jié)分析的那幾類偽特征點(diǎn)，但它們并不是指紋的固有特征，所以需要進(jìn)行剔除。目前一般的指紋識別方面的文章都忽略了這部分邊緣特征點(diǎn)，沒有在匹配前進(jìn)行剔除，這增加了后續(xù)匹配的特征點(diǎn)數(shù)量，影響了匹配效果。本文特在去偽特征點(diǎn)前對這類特征點(diǎn)進(jìn)行剔除。這樣的處理算法難度并沒有增加多少，但是卻對提高了后續(xù)的匹配效率具有重大意義。分析邊緣部分特征點(diǎn)的特點(diǎn)發(fā)現(xiàn)，這部分特征點(diǎn)不一定就是位于指紋圖像的邊緣。但可以肯定的是這部分是脊線和邊緣空白的交界處，而邊緣特征點(diǎn)就位于邊界的一定范圍內(nèi)，因此本文利用這一特點(diǎn)設(shè)計(jì)了剔除邊緣特征點(diǎn)的算法：（1）將細(xì)化后的指紋圖像進(jìn)行劃分2020的子塊。（2）通過計(jì)算各個子塊中像素點(diǎn)之和，檢測該子塊中是否含有脊線，并對含有脊線的子塊進(jìn)行標(biāo)記，方便下面的進(jìn)一步操作。（3）對上一步已標(biāo)記的子塊的8個鄰子塊進(jìn)行檢測，檢測是否含有脊線，只要8個鄰子塊中有一個沒有含有脊線，說明該中心子塊為邊界子塊。（4）查找所有位于邊界子塊中的邊緣特征點(diǎn)，并從特征點(diǎn)集中進(jìn)行剔除。處理完指紋邊緣的特征點(diǎn)后，下面需要對指紋內(nèi)的偽特征點(diǎn)進(jìn)行剔除。根據(jù)上節(jié)分析的偽特征點(diǎn)的特征，本文將根據(jù)偽特征點(diǎn)的這些性質(zhì)提出一套偽特征點(diǎn)剔除的算法。由于在剔除偽特征點(diǎn)的算法中會用到脊線跟蹤，這里先詳細(xì)介紹一下如何實(shí)現(xiàn)脊線跟蹤。首先從指紋脊線的端點(diǎn)出發(fā)，沿脊線不斷推進(jìn)，并對已經(jīng)跟蹤過的脊線上像素點(diǎn)進(jìn)行標(biāo)記，并保存下來。如圖3—4所示，假設(shè)圖中為上次己跟蹤過的脊線上的像素