【正文】 最后，感謝評(píng)審委員會(huì)的各位專家能夠在百忙之中審閱我的論文，感謝學(xué)校、學(xué)院對(duì)本次答辯的支持。同時(shí)，感謝我的父母和親人，謝謝他們對(duì)我多年的關(guān)懷和支持。感謝老師讓我生活和學(xué)習(xí)上得到成長(zhǎng)，使我能更好地適應(yīng) 將來的工作生活。在蔡老師的精心指導(dǎo)和嚴(yán)格要求下，我完成了畢業(yè)論文。 （ 2）本文的算法雖然進(jìn)行了仿真驗(yàn)證，但算法移植到 FPGA 上還有許多工作需要做，還需進(jìn)一步努力。針對(duì)仿真測(cè)試的結(jié)果分析，存在一些繼續(xù)改進(jìn)的地方。 （ 2）最后，本文應(yīng)用 Matlab 對(duì)以上算法進(jìn)行仿真測(cè)試，驗(yàn)證了本文指紋識(shí)別算法的可行性以及其優(yōu)劣勢(shì)，達(dá)到 檢驗(yàn)算法的目的。 濾除了偽特征點(diǎn)以后，不但使匹配的速度大大提高，而且指紋識(shí)別性能提升，使識(shí)別系統(tǒng)的誤拒率和誤識(shí)率的下降，因此在進(jìn)行指紋匹配之前，盡可能將偽特征點(diǎn)去除，保留真特征點(diǎn)。 （ 1）指紋特征提取是指紋自動(dòng)識(shí)別的核心技術(shù)之一，采用模板匹配法，提取指紋的細(xì)節(jié)特征即端點(diǎn)和分叉點(diǎn)。全局結(jié)構(gòu)特征用于指紋分類，減少指紋匹配時(shí)間；端點(diǎn)和分叉點(diǎn)成為最常用的局部結(jié)構(gòu)特征，也稱為細(xì)節(jié)特征，用這兩類 特征點(diǎn)描述指紋的唯一性。圖中為了分辨分叉點(diǎn)和端點(diǎn)，特將分叉點(diǎn)用藍(lán)色叉號(hào)表 第 22頁(yè) 22 示，將端點(diǎn)用紅色圓圈表示 。一般按經(jīng)驗(yàn)取值，本文取采集頭采集的指紋的脊線周期大約 10 個(gè)像素，試驗(yàn)表明此時(shí) DD D3 和 D4 的值取 6 時(shí)，偽特征點(diǎn)剔除的效果比較 好。 （ 4）環(huán)的刪除 通過脊線跟蹤，若在一個(gè)分叉點(diǎn) i 的 D4 范圍內(nèi)存在另外一個(gè)分叉點(diǎn) j，且特征點(diǎn)之間的連線 的方向與脊線的方向近似相等，即 ),( ji?? 近似等于 0，則這兩個(gè)分叉點(diǎn)為環(huán)形成的兩個(gè)偽特征點(diǎn)，將它們從特征點(diǎn)集中刪除。 （ 3）橋的刪除 通過脊線跟蹤，若在一個(gè)分叉點(diǎn) i 的 D3 范圍內(nèi)存在另外一個(gè)分叉點(diǎn) j，且 ),( ji?? 近似等于 2/? ，則這兩個(gè)特征點(diǎn)為橋形成的偽特征點(diǎn)，需要將它們從特征點(diǎn)集中刪除。 （ 1）斷點(diǎn)、短線的刪除 通過脊線跟蹤，若在一個(gè)端點(diǎn) i 的 D1 范圍內(nèi)存在另外一個(gè)端點(diǎn) j，且方向近似相同，則端點(diǎn) i 和端點(diǎn) j 為一對(duì)斷點(diǎn)，將它們從特征點(diǎn)集中刪除 [24]。跟蹤時(shí)，考察以iP 為中心的 33子塊，通過將 8 領(lǐng)域中脊線像素點(diǎn)與己跟蹤的像 素點(diǎn)進(jìn)行對(duì)比，搜尋尚未考察的脊線上的像素點(diǎn) (圖 3— 4 中 深色部分 ) 1?iP ，并保存 iP 到已跟蹤點(diǎn)集中，再以 1?iP 代替 iP 作為下一個(gè)跟蹤的像素點(diǎn)，以此類推實(shí)現(xiàn)脊線跟蹤。 首先從指紋脊線的端點(diǎn)出發(fā)，沿脊線不斷推進(jìn)，并對(duì)已經(jīng)跟蹤過的脊線上像素點(diǎn)進(jìn)行標(biāo)記，并保存下來。根據(jù)上節(jié)分析的偽特征點(diǎn)的特征，本文將根據(jù)偽特征點(diǎn)的這些性質(zhì)提出一套偽特征點(diǎn)剔除的算法。 （ 4）查找所有位于邊界子塊中的邊緣特征點(diǎn)，并從特征點(diǎn)集中進(jìn)行剔除。 （ 2）通過計(jì)算各個(gè)子塊中像素點(diǎn)之和，檢測(cè)該子塊中是否含有脊線，并對(duì)含有脊線的子塊進(jìn)行標(biāo)記，方便下面的進(jìn)一步操作。 分析邊緣部分特征點(diǎn)的特點(diǎn)發(fā)現(xiàn)，這部分特征點(diǎn)不一定就是位于指紋圖像的邊緣。本文特在去偽特征點(diǎn)前對(duì)這類 第 20頁(yè) 20 特征點(diǎn)進(jìn)行剔除。它們又不屬于上節(jié)分析的那幾類偽特征點(diǎn)，但 它們并不是指紋的固有特征，所以需要進(jìn)行剔除。這些特征點(diǎn)是由于在指紋采集時(shí)，指紋接觸采集頭的邊界，脊線的起始點(diǎn)。其特點(diǎn)是一般這兩個(gè)偽特征點(diǎn)的距離非常小，而且這兩個(gè)偽特征點(diǎn)間的連線與所在的脊線方向近似相同。主要是由于隨機(jī)噪聲影響產(chǎn)生的。其特點(diǎn)是這兩個(gè)分叉點(diǎn)的距離一般近似等于平均脊線間距，而且兩個(gè)偽分叉點(diǎn)間的連線近似垂直于其局部鄰域的脊線方向。 （ 4）假橋現(xiàn)象，當(dāng)手指過潮濕或者臟時(shí)，采集的指紋圖像容易出現(xiàn)多脊線假橋 (有時(shí)也叫橋 )的現(xiàn)象，即本來不相連的兩條脊線連在了一起。另外手指褶皺、傷疤也容易產(chǎn)生斷點(diǎn)現(xiàn)象。短線的特點(diǎn)就是會(huì)產(chǎn)生兩個(gè)偽端點(diǎn)，該兩個(gè)端點(diǎn)相距很近，位于同一脊線上。這類偽特征點(diǎn)的特點(diǎn)是它們往往成對(duì)出現(xiàn)，而且偽端點(diǎn)和偽分叉點(diǎn)的距離非常近，一般小于細(xì)化前的脊線寬度的一半。 （ 1） 毛刺現(xiàn)象，毛刺的出現(xiàn)有多方面的原因，比如受隨機(jī)噪聲的影響而形成的，還有部分是受圖像增強(qiáng)和細(xì)化處理產(chǎn)生的。大量偽特征點(diǎn)的存在將導(dǎo)致匹配效率降低，成功匹配率降低，嚴(yán)重影響指紋識(shí)別系統(tǒng)的指標(biāo)，因此在匹配前必須對(duì)偽特征點(diǎn)進(jìn)行剔除。 從上文細(xì)化后的指 紋圖像上不難發(fā)現(xiàn)，由于細(xì)化后的指紋圖像出現(xiàn)了毛刺、粘連、斷點(diǎn)等現(xiàn)象。由于圖像質(zhì)量和噪聲的干擾，經(jīng)過預(yù)處理后的細(xì)化圖像上存在大量的偽特征點(diǎn)，所以特征提取后可能產(chǎn)生多達(dá)一、兩萬個(gè)細(xì)節(jié)特征點(diǎn)，其中包含了大量的偽特征點(diǎn)，這些偽特征點(diǎn)的存在，不但使匹配的速度大大降低，還使指紋識(shí)別性能急劇下降，造成識(shí)別系統(tǒng)的誤拒率和誤識(shí)率的上升，因此在進(jìn)行指紋匹配之前，盡可能將偽特征點(diǎn)去除，同時(shí)保留真特征點(diǎn)。所以考慮到指紋識(shí)別系統(tǒng)的魯棒性，以及特征點(diǎn)提取算法的可靠性本文采用第二種算法。但是由于模板匹配法采用的是遍歷原則，即對(duì)所有像素都進(jìn)行特征點(diǎn)判定，所以不會(huì)出現(xiàn)第一種算法那樣的特征點(diǎn)丟失的問題。另外，該算法脊線跟蹤的步長(zhǎng)不好確定，即使采用自適應(yīng)步長(zhǎng)也只是稍微降低丟失特征點(diǎn)的情況，沒有從根本上改觀，加上是利用灰度分布直方圖來確定特征點(diǎn) 的，因此特征點(diǎn)的位置信息并不十分精確，有可能與實(shí)際的位置出現(xiàn)偏差，尤其是在圖像模糊的情況下，更是相差甚遠(yuǎn)。這兩點(diǎn)是該算法的最大優(yōu)點(diǎn)。 算法比較 以上即是常用的兩種特征點(diǎn)提取算法，通過比較不難發(fā)現(xiàn)：基于灰度直接提取算法原理比較簡(jiǎn)單，簡(jiǎn)化了圖像增強(qiáng)、二值化步驟，直接求取脊線并得到特征點(diǎn)。如下式 3— 3。端點(diǎn)的角度取從端點(diǎn)為起點(diǎn)的端線的角度，分叉點(diǎn)的角度取相對(duì)最小分支線的角度。 （ 2） 對(duì) 脊線中間連續(xù)點(diǎn)，因?yàn)榘肃徲蛑挥袃蓚€(gè)點(diǎn)灰度值為 1，除去上一個(gè)被跟蹤的點(diǎn)，剩下的一點(diǎn)即為下一個(gè)待跟蹤點(diǎn)。 （ 3） 若 P 點(diǎn)為脊線上的點(diǎn)，且 )(PCn =6， )(PSn =3，則可判定像素點(diǎn) P 為分叉點(diǎn)，如圖 3— 3 中點(diǎn) B 點(diǎn)。通過分析可以發(fā)現(xiàn))(PCn 和 )(PSn 數(shù)值僅存在以下三種情況 ： （ 1） 若 P 點(diǎn)為脊線上的點(diǎn)，且 )(PCn =2， )(PSn =l，則可判定像素點(diǎn) P 為端點(diǎn)，如圖 3— 3 中 E 點(diǎn) 。 ?? ? ?? 8 1 1)( i iin PPPC (其中 PP 19? ) (3— 1) ??? 81)( i in PPS (3— 2) 通過分析可知，細(xì)化后的指紋圖像的鄰域 狀態(tài)如圖 3— 3 所示。 P9 為 P 的鄰域， )(PCn為這 8 個(gè)鄰域像素的相鄰像素的灰度值 (此時(shí)己二值化，所以灰度值只可 能為 0 或 l)從 0變?yōu)?1，或者從 1 變?yōu)?0 的次數(shù) 。圖中 P 為待測(cè)像素點(diǎn)， Pl、 P2這種方法省去了復(fù)雜的 指紋圖像預(yù)處理過程，但是特征提取的算法卻十分復(fù)雜，而且由于噪聲等因素影響，提取的特征信息 (位置、方向等 )也不夠準(zhǔn)確。若跟蹤到的脊線與先前己經(jīng)跟蹤過的脊線相交，停止跟蹤，求取兩條脊線交點(diǎn)位置，此處即特征點(diǎn)分叉點(diǎn)。 （ 3） 從新的出發(fā)點(diǎn)出發(fā)，沿指紋圖像的方向圖的方向前進(jìn)一定步長(zhǎng) (算法最開始是按 固定步長(zhǎng)進(jìn)行跟蹤的，后來發(fā)展到自適應(yīng)步長(zhǎng)跟蹤 )，繼續(xù)在發(fā)現(xiàn)方向求取灰度分布的最大值和最小值，仍然以最大值處的像素點(diǎn)作為新的出發(fā)點(diǎn)。 具體算法如下 [19]： （ 1） 計(jì)算指紋圖像的方向圖，一般以塊方向作為指紋的方向。 （ 3） 標(biāo)記模塊，用來給跟蹤過的紋線作記號(hào)，以免重復(fù)跟蹤，陷入死循環(huán)。 該算法主要由幾個(gè)緊密聯(lián)系的模塊組成： （ 1） 跟蹤步進(jìn)模塊，主要負(fù)責(zé)預(yù)測(cè)下一步跟蹤方向和步長(zhǎng)，用來沿紋線前進(jìn)一步。 直接灰度圖像法 直接灰度圖像指紋特征提取 [1718]的原理是使用模式識(shí)別的方法跟蹤灰度圖上的紋線走向。 最常用的特征點(diǎn)提取算法有兩類 ：一是從灰度圖像直接提取特征點(diǎn)；二是對(duì)預(yù)處理細(xì)化后的圖像進(jìn)行提取特征點(diǎn)。他們采用了一種二級(jí)算法，用自適應(yīng)“編輯”方法將指紋圖像二值化，再?gòu)亩祷蟮闹讣y圖像中提取特征點(diǎn)。迄今為止，人們已經(jīng)對(duì)指紋細(xì)節(jié)特征提取算法進(jìn)行了很多的研究工 第 15頁(yè) 作。英國(guó)司法界認(rèn)為有 12 個(gè)細(xì)節(jié)點(diǎn)匹配，就可以認(rèn)為兩幅指紋相同，美國(guó) FBI 認(rèn)為 8 個(gè)細(xì)節(jié)點(diǎn)匹配就足夠了 [1516]。因此為了能普遍的表征指紋圖像，一般選用端點(diǎn)和分叉點(diǎn)作為指紋圖像特征點(diǎn)。從表中可以發(fā)現(xiàn)，端點(diǎn)和分叉點(diǎn)占特征點(diǎn) 91%，而交叉形、橋形以 及環(huán)形三類總共只占 9%左右 [14]。特征匹配就是利用這些信息進(jìn)行的。 局部特征 局部特征是指指紋拓?fù)鋱D中的幾種有效的特征，比如指紋紋路是不是連續(xù)的，方向 第 14頁(yè) 是不是一致，具體到細(xì)節(jié)特征就表現(xiàn)為斷點(diǎn)、分叉點(diǎn)、交叉點(diǎn)、橋、環(huán)等等，這些通常稱為特征點(diǎn)。 （ 5）脊線數(shù)，指的是模式區(qū)內(nèi)指紋 脊線的數(shù)量。 （ 3）核心點(diǎn) (core)，是指指紋脊線的漸進(jìn)中心點(diǎn)。拱型沒有中心點(diǎn)和三角點(diǎn)，帳型和箕型有一個(gè)中心點(diǎn)和三角點(diǎn)，雙箕型有兩個(gè)中心點(diǎn) [13]。目前最常見的表示指紋圖像的全局特征是按照指紋的脊線總體結(jié)構(gòu)來確立的，具體包括指紋的紋形、模式區(qū)、核心點(diǎn) (core)、三角點(diǎn) (delta)和脊線數(shù)五個(gè)特征。目前流行的自動(dòng)指紋識(shí)別系統(tǒng)大多采用基于細(xì)節(jié)點(diǎn)的表達(dá)方式，故在進(jìn)行指紋的細(xì)化及細(xì)化處理之后要進(jìn)行指紋的特征提取，以方便最后的指紋匹配。 第 13頁(yè) 3 指紋圖像特征的提取 指紋圖像的最終匹配還要依賴指紋的特征點(diǎn)來進(jìn)行。 OPTA 算法能滿足收斂性、連接性、拓?fù)湫院捅３中裕瑢?duì)指紋圖像的細(xì)化能達(dá)到較好的效果。串行細(xì)化算法即單連通細(xì)化 (OPTA)算法 [11]通過構(gòu)造一組指紋細(xì)化模板，對(duì)于脊線上的每個(gè)像素點(diǎn)取其一定范圍的鄰域，如果該鄰域與模板符合就保留該當(dāng)前點(diǎn)，不符合則刪除。逐層剝離法按照細(xì)化順序又主要分為兩類：串行細(xì)化和并行細(xì)化。逐層剝離法是反復(fù)將圖像邊緣層的點(diǎn)剝?nèi)ィ敝恋玫街行墓羌?，其特點(diǎn)是簡(jiǎn)單、實(shí)用、容易理解，所以較為常用，但該方法依賴于像素的執(zhí)行順序，因而容易受毛刺或孔洞噪聲的影響，且一般需要多次迭代，速度較慢。細(xì)化算法的迭代必須收斂且不能破壞紋線的連接性，不能引起紋線的逐步吞食，還要盡可能的保護(hù)指紋的細(xì)節(jié)特征，細(xì) 化的骨架也要盡可能接近紋線中心線，要求算法簡(jiǎn)單、高效。細(xì)化是圖象分析、信息壓縮、特征提取、模式識(shí)別常用的基本技術(shù)。 細(xì)化 二值化后的指紋脊線平均寬度為 6— 8 個(gè)像素，由于按捺的輕重不勻使指紋脊線的粗細(xì)不能恒定，難于據(jù)此直接抽取指紋的特征集。 局部自適應(yīng)閥值法 [910]，它是針對(duì)固定閥值法的缺陷提出的，該算法將指紋圖像劃分為大小合適的子塊，對(duì)每一個(gè)子塊進(jìn) 行求取閥值，然后進(jìn)行分塊二值化。由于指紋圖像在采集時(shí)的環(huán)境（光線、壓力、濕度等），整幅指紋圖像的明暗分布并不是均勻的，往往存在某一部分局部過暗（即灰度值偏?。?，而另外一部分局部過亮（偏大）。 固定閥值法 [8]就是整幅指紋圖像采用一個(gè)固定 的閥值，對(duì)于灰度值大于這個(gè)閥值的像素點(diǎn)的灰度值置為 1，小于等于這個(gè)閥值的像素點(diǎn)其灰度值置為 0。由于指紋圖像的方向特征、細(xì)節(jié)點(diǎn)位置等特征的提取以及匹配都跟像素點(diǎn)灰度值的多少?zèng)]關(guān)系，只跟指紋圖像的脊線的形狀、走 向有關(guān)系，因此二值化處理不會(huì)丟失指紋圖像的特征信息，另外二值化還可以方便圖像信息的存儲(chǔ)，節(jié)約存儲(chǔ)空間，并且方便了后續(xù)的計(jì)算處理。該方法不需要計(jì)算原始指紋圖像的方向和頻率，因此簡(jiǎn)單易行，計(jì)算量較小，但是在噪聲的影響下會(huì)對(duì)圖像造成較 大的破壞，其合理性還有待進(jìn)一步研究。Willis 和 Myers 提出了一種快速的頻域增強(qiáng)算法。 Kamei 和 Mizoguchi 在頻域?qū)D像作方向?yàn)V波時(shí)進(jìn)一步考慮了指紋的局部頻率信息，并使用貪婪算法以能量最小化的方式對(duì)濾波圖像進(jìn)行融合。該方法利用了圖像的全局信息，對(duì)低質(zhì)量指紋圖像也能取得較好的增強(qiáng)效果，但是僅以常數(shù)作為指紋的脊線頻率，沒有考慮頻率的空間變化性，對(duì)指紋的紋線結(jié)構(gòu)和細(xì)節(jié)特征具有一定的破壞性。 Sherlock 等提出了基于頻域的方向?yàn)V波算法。 頻域?yàn)V波法通過直接改善圖像的頻譜來實(shí)現(xiàn)圖像增強(qiáng)。該方法較好地結(jié)合了指紋的方向信息和頻率信息，對(duì)指紋圖像的增強(qiáng)效果比較顯著。 Hong 等提出采用具有方向和頻率選擇性的二維 Gabor 濾波器來增強(qiáng)指紋圖像。但是，該方法沒有使用指紋的頻率信息，主要依據(jù)經(jīng)驗(yàn)來確定濾波器模板，對(duì)低質(zhì)量指紋圖像的處理效果較差，具有一定的局限性 [5]。 O’Gorman 和 Nickerson 較早提出采用方向?yàn)V波器進(jìn)行指紋圖像增強(qiáng)。 從目前的研究情況和各種算法的綜合比較來看，空域?yàn)V波和頻域?yàn)V波仍