【文章內(nèi)容簡(jiǎn)介】 算法在具體實(shí)現(xiàn)中可利用同一塊中所有像素有同樣方向的條件，推導(dǎo)出快速算法，防止一些點(diǎn)的重復(fù)掃描，大大縮短處理時(shí)間。 指紋圖像的細(xì)化算法指紋圖像二值化后，紋線仍具有一定的寬度，而指紋識(shí)別只對(duì)紋線的走向感興趣，不關(guān)心它的粗細(xì)。為了進(jìn)一步壓縮數(shù)據(jù)，得到更精確的細(xì)節(jié)特征，提高識(shí)別的準(zhǔn)確性，對(duì)指紋圖像進(jìn)行細(xì)化處理是不可忽略的。所謂細(xì)化，就是從原來(lái)的圖中去掉一些點(diǎn)，但仍要保持原有的形狀。實(shí)際上，是保持原圖的骨架[7]。指紋圖像的細(xì)化是指刪除指紋紋線的邊緣像素，使之只有一個(gè)像素寬度，細(xì)化時(shí)應(yīng)保證紋線的連接性、方向性和特征點(diǎn)不變，還應(yīng)保持紋線的中心基本不變。一種好的細(xì)化方法應(yīng)滿足下列條件：1．迭代必須收斂的。(收斂性)2．不破壞紋線的連接性。(連接性)3．不引起紋線的逐步吞食。(拓?fù)湫?4．保護(hù)指紋的細(xì)節(jié)特征。(保持性)5．骨架紋線的寬度為1個(gè)像素。(細(xì)化性)6．骨架盡可能接近條紋中心線。(中軸性) 7. 算法簡(jiǎn)單、速度快。(快速性)圖39　統(tǒng)一模塊下面介紹一種適合于指紋圖像細(xì)化的算法，這種方法滿足上面的細(xì)化條件，而且可以提出快速算法。這種算法采用模板，如圖39所示，左上角的方窗(即)為消除模板。即，一黑色象素八臨域與消除模板中的一個(gè)相匹配的話，該點(diǎn)被認(rèn)為是可消除的點(diǎn)。消除模板具體如下： （A） （B） （C） （D） （E） （F） （G） （H） 圖310 消除模塊圖（A）~（D） 4個(gè)模板能有效去除邊緣上的突出物，保證了細(xì)化后的指紋骨架處于指紋脊線中心，避免了細(xì)化后的指紋骨架出現(xiàn)毛刺。除消除模板外，還需構(gòu)造保留模板，保持紋線的連通性。 （A） （B） （C） （D） （E） （F） 保持模板內(nèi)容如下圖所示： 圖311 保留模塊具體算法如下：從圖像的左上角元素開(kāi)始進(jìn)行，每個(gè)像素(圖中為)均抽取出如圖39所示的15個(gè)相鄰像素，并且把其中8個(gè)鄰域像素()與圖310中的8個(gè)模板比較，如果和8個(gè)消除模板中的任意一個(gè)都不匹配時(shí)，保留；如果與8個(gè)中的任一個(gè)匹配，則抽取的元素再和上圖中的6個(gè)保留模板進(jìn)行比較，如果與其中任一個(gè)匹配的話，則保留，否則刪去。重復(fù)這個(gè)過(guò)程，直到?jīng)]有一個(gè)像素的值被改變。這種算法的具體實(shí)現(xiàn)可引入查表法，即對(duì)所要處理的像素周?chē)０鍍?nèi)前15個(gè)點(diǎn)預(yù)先進(jìn)行編碼(用雙字節(jié)15個(gè)位來(lái)表示，雙字節(jié)的最低位存放的值，依此類(lèi)推，次最高位存放的值)，把編碼值作為存儲(chǔ)地址，按上述細(xì)化法則，預(yù)先在存儲(chǔ)地址上存入相應(yīng)的細(xì)化值(可用0、1表示，0表示保留，1表示刪去)。細(xì)化時(shí)，移動(dòng)4x4的方窗內(nèi)象素的編碼地址去查找相應(yīng)的細(xì)化值，用細(xì)化值替換當(dāng)前像素值。 特征提取及其后處理 特征點(diǎn)的提取特征提取一般是指提取指紋圖像的局部特征，也就是細(xì)節(jié)點(diǎn)特征。在基于細(xì)節(jié)點(diǎn)的指紋自動(dòng)識(shí)別系統(tǒng)中，特征提取是在細(xì)化后的指紋圖像上進(jìn)行的。特征提取的首要問(wèn)題是確定細(xì)節(jié)點(diǎn)和它的位置，細(xì)節(jié)點(diǎn)的位置和細(xì)節(jié)點(diǎn)間的相對(duì)位置很重要，盡管每個(gè)指紋中包括將近80個(gè)細(xì)節(jié)，只要確定十幾個(gè)細(xì)節(jié)點(diǎn)就己經(jīng)足夠用來(lái)識(shí)別了。探測(cè)細(xì)節(jié)點(diǎn)的算法很簡(jiǎn)單，如圖312所示的3x3模板就可以用來(lái)確定特征的位置。M是待檢測(cè)的點(diǎn)，是它的八鄰域，沿順時(shí)針?lè)较蚺帕?。是?xì)化后圖像在處的灰度。如果M是端點(diǎn)，則它的八鄰域滿足：， （） 如果M是分叉點(diǎn)，則它的八鄰域滿足：， （）這樣我們就可以在細(xì)化后的圖像中找到細(xì)節(jié)點(diǎn)(端點(diǎn)和分叉點(diǎn))，并記錄它們?cè)趫D中的相對(duì)位置。 假特征點(diǎn)的去除這樣得到的特征中存在由指紋質(zhì)量、攝入噪聲等原因造成的很多假特征，如下圖312所示(a)和(b)中產(chǎn)生了假的端點(diǎn)；(c)和(d)中形成了錯(cuò)誤的斷開(kāi)和連接；(e)中顯示的是一個(gè)由不平滑的脊引起的毛刺，出現(xiàn)了假端點(diǎn)和假分叉兩種特征：(f)~(g)是幾種錯(cuò)誤連接的例子，分別稱(chēng)為橋形、三角形、梯形結(jié)構(gòu)。 圖312 假特征針對(duì)上面這些假特征，我們采用了非常簡(jiǎn)單的方法：計(jì)算特征點(diǎn)間的距離，如果距離值小于所給的閥值，則認(rèn)為特征點(diǎn)為假特征點(diǎn)。這種算法實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單：掃描特征點(diǎn)的某一鄰域，如果該鄰域中出現(xiàn)其他特征點(diǎn)的話，將該特征點(diǎn)與出現(xiàn)的特征點(diǎn)同時(shí)去除，如此循環(huán)幾次，當(dāng)沒(méi)有特征點(diǎn)被刪去時(shí)，處理完成。這種方法中鄰域的選取很重要，如果取得比較小，則可能起不到去除假特征點(diǎn)的作用；如果取得比較大的話，則可能將真正的特征點(diǎn)也一并刪去。在具體實(shí)現(xiàn)中，我們?nèi)∑浒霃綖榧箤挼囊话搿?細(xì)節(jié)點(diǎn)信息的提取及記錄對(duì)每一個(gè)細(xì)節(jié)點(diǎn)，我們記錄如下信息：1．細(xì)節(jié)點(diǎn)的x,y坐標(biāo)。2．細(xì)節(jié)點(diǎn)的方向，這個(gè)方向就是該細(xì)節(jié)點(diǎn)所在的塊的塊方向。3．細(xì)節(jié)點(diǎn)的類(lèi)型，即脊線端點(diǎn)或脊線分叉點(diǎn)。4．細(xì)節(jié)點(diǎn)對(duì)應(yīng)的脊線。細(xì)節(jié)點(diǎn)對(duì)應(yīng)的脊線用該脊線上的采樣點(diǎn)來(lái)表示，采樣的距離約為脊線間的平均距離。分叉點(diǎn)對(duì)應(yīng)的脊線是與該細(xì)節(jié)點(diǎn)的方向最近的那條，端點(diǎn)對(duì)應(yīng)的脊線就是該細(xì)節(jié)點(diǎn)所在的脊線。采樣點(diǎn)用該點(diǎn)與對(duì)應(yīng)細(xì)節(jié)點(diǎn)的距離，和連接該點(diǎn)與對(duì)應(yīng)細(xì)節(jié)點(diǎn)的直線與對(duì)應(yīng)細(xì)節(jié)點(diǎn)方向的夾角來(lái)表示，的取值范圍在180到180度之間。下圖給出了細(xì)節(jié)點(diǎn)對(duì)應(yīng)的脊線與脊線上的采樣點(diǎn)的例子。在細(xì)節(jié)匹配中，對(duì)應(yīng)脊線將被用來(lái)對(duì)兩個(gè)平面點(diǎn)集進(jìn)行校準(zhǔn)，而且，校準(zhǔn)的參數(shù)，也就是兩個(gè)點(diǎn)集中任意一對(duì)脊線間的旋轉(zhuǎn)角度，將被用來(lái)作為判斷它們所對(duì)應(yīng)的細(xì)節(jié)點(diǎn)能否看作匹配的細(xì)節(jié)點(diǎn)的條件。 圖313 細(xì)節(jié)點(diǎn)的對(duì)應(yīng)脊線 指紋識(shí)別中細(xì)節(jié)點(diǎn)的匹配細(xì)節(jié)匹配一般在極坐標(biāo)系中進(jìn)行，因?yàn)橹讣y圖像的非線性形變往往呈放射狀，在某個(gè)區(qū)域內(nèi)的形變比較大，然后非線性地向外擴(kuò)張，因而，在極坐標(biāo)中能更好地描述非線性形變；另外，在極坐標(biāo)中不需要考慮輸入圖像與模板圖像的參照點(diǎn)之間的平移，將一對(duì)對(duì)應(yīng)點(diǎn)的坐標(biāo)相對(duì)于參照點(diǎn)轉(zhuǎn)換為極坐標(biāo)時(shí)，平移就被抵消了；還有，在極坐標(biāo)系中顯然比在直角坐標(biāo)系中更便于處理兩幅圖像間的旋轉(zhuǎn)[8]。細(xì)節(jié)點(diǎn)集的校準(zhǔn)：令 （）表示模板圖像中的M個(gè)細(xì)節(jié)點(diǎn)， （）表示輸入圖像中的N個(gè)細(xì)節(jié)點(diǎn)。為了把細(xì)節(jié)點(diǎn)轉(zhuǎn)移到極坐標(biāo)系中去，需要在模板細(xì)節(jié)點(diǎn)集和輸入細(xì)節(jié)點(diǎn)集中各選一個(gè)參照點(diǎn)作為相應(yīng)的極坐標(biāo)系中的原點(diǎn)，并算出其它細(xì)節(jié)點(diǎn)相對(duì)于參照點(diǎn)的極坐標(biāo)。由于事先不知道模板點(diǎn)集與輸入點(diǎn)集的對(duì)應(yīng)關(guān)系，需要考慮所有可能的參照點(diǎn)對(duì)。對(duì)模板點(diǎn)集中的每一點(diǎn)和輸入點(diǎn)集中的每一點(diǎn)，定義為將和當(dāng)作參照點(diǎn)對(duì)時(shí)，從輸入圖像到模板圖像的旋轉(zhuǎn)角度。如果，和可以被當(dāng)作一對(duì)對(duì)應(yīng)點(diǎn)，即它們分別對(duì)應(yīng)的脊線相似性到了一定程度，則將取0度到360度間的一個(gè)值，否則，我們定義取值為400，以表示和不能是一對(duì)對(duì)應(yīng)點(diǎn)。如果和是不同類(lèi)型的細(xì)節(jié)點(diǎn)，也就是說(shuō)它們一個(gè)是端點(diǎn)，一個(gè)是分叉點(diǎn)，則它們不是對(duì)應(yīng)點(diǎn)對(duì)，取值為400。即，表示和對(duì)應(yīng)的脊線相似性到了一定程度。 本章小結(jié) 本章詳細(xì)介紹了指紋識(shí)別過(guò)程的原理及算法的研究，具體算法將在后續(xù)章節(jié)給出。 第4章 指紋識(shí)別算法的MATLAB實(shí)現(xiàn) MATLAB簡(jiǎn)介 MATLAB 的概況 MATLAB是矩陣實(shí)驗(yàn)室（Matrix Laboratory）之意。除具備卓越的數(shù)值計(jì)算能力外，它還提供了專(zhuān)業(yè)水平的符號(hào)計(jì)算、文字處理、可視化建模仿真和實(shí)時(shí)控制等功能。 MATLAB的基本數(shù)據(jù)單位是矩陣，它的指令表達(dá)式與數(shù)學(xué)，工程中常用的形式十分相似，故用MATLAB來(lái)解算問(wèn)題要比用C、FORTRAN等語(yǔ)言完成相同的事情簡(jiǎn)捷得多。當(dāng)前流行的MATLAB包括擁有數(shù)百個(gè)內(nèi)部函數(shù)的主包和三十幾種工具包(Toolbox)。工具包又可以分為功能性工具包和學(xué)科工具包。功能工具包用來(lái)擴(kuò)充MATLAB的符號(hào)計(jì)算、可視化建模仿真、文字處理及實(shí)時(shí)控制等功能。學(xué)科工具包是專(zhuān)業(yè)性比較強(qiáng)的工具包，控制工具包、信號(hào)處理工具包、通信工具包等都屬于此類(lèi)。開(kāi)放性使MATLAB廣受用戶(hù)歡迎。除內(nèi)部函數(shù)外，所有MATLAB主包文件和各種工具包都是可讀可修改的文件，用戶(hù)通過(guò)對(duì)源程序的修改或加入自己編寫(xiě)程序構(gòu)造新的專(zhuān)用工具包。 MATLAB產(chǎn)生的歷史背景 在70 年代中期,Cleve Moler博士和其同事在美國(guó)國(guó)家科學(xué)基金的資助下開(kāi)發(fā)了調(diào)用EISPACK和LINPACK的FORTRAN程序庫(kù)。 EISPACK是特征值求解的FOETRAN 程序庫(kù)，LINPACK是解線性方程的程序庫(kù)。在當(dāng)時(shí)，這兩個(gè)程序庫(kù)代表矩陣運(yùn)算的最高水平。 到70年代后期，身為美國(guó)New Mexico大學(xué)計(jì)算機(jī)系系主任的Cleve Moler在給學(xué)生講授線性代數(shù)課程時(shí)，想教學(xué)生使用EISPACK和LINPACK程序庫(kù)，但他發(fā)現(xiàn)學(xué)生用FORTRAN編寫(xiě)接口程序很費(fèi)時(shí)間，于是他開(kāi)始自己動(dòng)手，利用業(yè)余時(shí)間為學(xué)生編寫(xiě)EISPACK 和LINPACK的接口程序。Cleve Moler給這個(gè)接口程序取名為MATLAB,該名為矩陣(matrix)和實(shí)驗(yàn)室(labotatory)兩個(gè)英文單詞的前三個(gè)字母的組合。在以后的數(shù)年里,MATLAB在多所大學(xué)里作為教學(xué)輔助軟件使用,并作為面向大眾的免費(fèi)軟件廣為流傳。1983年春天,Cleve Moler到Standford 大學(xué)講學(xué),MATLAB深深地吸引了工程師John Little敏銳地覺(jué)察到MATLAB在工程領(lǐng)域的廣闊前景。同年,他和Cleve Moler,Steve Bangert一起，用C語(yǔ)言開(kāi)發(fā)了第二代專(zhuān)業(yè)版。這一代的MATLAB語(yǔ)言同時(shí)具備了數(shù)值計(jì)算和數(shù)據(jù)圖示化的功能。1984年，Cleve Moler和John Little成立了Math Works公司，正式把MATLAB推向市場(chǎng)，并繼續(xù)進(jìn)行MATLAB的研究和開(kāi)發(fā)。 在當(dāng)今30多個(gè)數(shù)學(xué)類(lèi)科技應(yīng)用軟件中，就軟件數(shù)學(xué)處理的原始內(nèi)核而言，可分為兩大類(lèi)。一類(lèi)是數(shù)值計(jì)算型軟件，如 MATLAB,Xmath,Gauss 等，這類(lèi)軟件長(zhǎng)于數(shù)值計(jì)算，對(duì)處理大批數(shù)據(jù)效率高；另一類(lèi)是數(shù)學(xué)分析型軟件，Mathematical,Maple等,這類(lèi)軟件以符號(hào)計(jì)算見(jiàn)長(zhǎng),能給出解析解和任意精確解,其缺點(diǎn)是處理大量數(shù)據(jù)時(shí)效率較低。Math Works 公司順應(yīng)多功能需求之潮流,在其卓越數(shù)值計(jì)算和圖示能力的基礎(chǔ)上,又率先在專(zhuān)業(yè)水平上開(kāi)拓了其符號(hào)計(jì)算、文字處理、可視化建模和實(shí)時(shí)控制能力,開(kāi)發(fā)了適合多學(xué)科,多部門(mén)要求的新一代科技應(yīng)用軟件MATLAB。經(jīng)過(guò)多年的國(guó)際競(jìng)爭(zhēng),MATLAB以經(jīng)占據(jù)了數(shù)值軟件市場(chǎng)的主導(dǎo)地位。在MATLAB進(jìn)入市場(chǎng)前,國(guó)際上的許多軟件包都是直接以 FORTRAN、C 語(yǔ)言等編程語(yǔ)言開(kāi)發(fā)的。這種軟件的缺點(diǎn)是使用面窄,接口簡(jiǎn)陋,程序結(jié)構(gòu)不開(kāi)放以及沒(méi)有標(biāo)準(zhǔn)的基庫(kù),很難適應(yīng)各學(xué)科的最新發(fā)展,因而很難推廣。MATLAB的出現(xiàn),為各國(guó)科學(xué)家開(kāi)發(fā)學(xué)科軟件提供了新的基礎(chǔ)。在 MATLAB 問(wèn)世不久的80年代中期,原先控制領(lǐng)域里的一些軟件包紛紛被淘汰或在MATLAB上重建。 Math Works 公司1993年推出了MATLAB ,（for ）, 版。MATLAB ,其幫助信息采用超文本格式和PDF格式,在 Netscape IE ,Acrobat Reader中可以方便地瀏覽。時(shí)至今日,經(jīng)過(guò) Math Works 公司的不斷完善,MATLAB已經(jīng)發(fā)展成為適合多學(xué)科,多種工作平臺(tái)的功能強(qiáng)大大大型軟件。在國(guó)外,MATLAB已經(jīng)經(jīng)受了多年考驗(yàn)。在歐美等高校,MATLAB已經(jīng)成為線性代數(shù)、自動(dòng)控制理論、數(shù)理統(tǒng)計(jì)、數(shù)字信號(hào)處理、時(shí)間序列分析、動(dòng)態(tài)系統(tǒng)仿真等高級(jí)課程的基本教學(xué)工具；成為攻讀學(xué)位的大學(xué)生、碩士生、博士生必須掌握的基本技能。在設(shè)計(jì)研究單位和工業(yè)部門(mén),MATLAB被廣泛用于科學(xué)研究和解決各種具體問(wèn)題。在國(guó)內(nèi),特別是工程界，MATLAB一定會(huì)盛行起來(lái)?？梢哉f(shuō)，無(wú)論你從事工程方面的哪個(gè)學(xué)科，都能在MATLAB里找到合適的功能。 MATLAB 的語(yǔ)言特點(diǎn) 一種語(yǔ)言之所以能如此迅速地普及，顯示出如此旺盛的生命力，是由于它有著不同于其他語(yǔ)言的特點(diǎn)，正如同F(xiàn)ORTRAN和C等高級(jí)語(yǔ)言使人們擺脫了需要直接對(duì)計(jì)算機(jī)硬件資源進(jìn)行操作一樣，被稱(chēng)作為第四代計(jì)算機(jī)語(yǔ)言的MATLAB，利用其豐富的函數(shù)資源，使編程人員從繁瑣的程序代碼中解放出來(lái)。MATLAB最突出的特點(diǎn)就是簡(jiǎn)潔。MATLAB用更直觀的，符合人們思維習(xí)慣的代碼，代替了C和FORTRAN語(yǔ)言的冗長(zhǎng)代碼。MATLAB給用戶(hù)帶來(lái)的是最直觀、最簡(jiǎn)潔的程序開(kāi)發(fā)環(huán)境。以下簡(jiǎn)單介紹一下 MATLAB 的主要特點(diǎn): 1）、語(yǔ)言簡(jiǎn)潔緊湊，使用方便靈活，庫(kù)函數(shù)極其豐富。MATLAB程序書(shū)寫(xiě)形式自由，利用起豐富的庫(kù)函數(shù)避開(kāi)繁雜的子程序編程任務(wù)，壓縮了一切不必要的編程工作。由于庫(kù)函數(shù)都由本領(lǐng)域的專(zhuān)家編寫(xiě)，用戶(hù)不必?fù)?dān)心函數(shù)的可靠性。可以說(shuō)，用MATLAB進(jìn)行科技開(kāi)發(fā)是站在專(zhuān)家的肩膀上。 具有FORTRAN和C等高級(jí)語(yǔ)言知識(shí)的讀者可能已經(jīng)注意到，如果用FORTRAN或C語(yǔ)言去編寫(xiě)程序，尤其當(dāng)涉及矩陣運(yùn)算和畫(huà)圖時(shí)，編程會(huì)很麻煩。例如，如果用戶(hù)想求解一個(gè)線性代數(shù)方程，就得編寫(xiě)一個(gè)程序塊讀入數(shù)據(jù)，然后再使用一種求解線性方程的算法（例如追趕法）編寫(xiě)一個(gè)程序塊來(lái)求解方程，最后再輸出計(jì)算結(jié)果。在求解過(guò)程中