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