提取二值化指紋圖像中特征數(shù)據(jù)的算法研究

1、. . . . 目錄1 引言11.1指紋識(shí)別發(fā)展概況11.2指紋識(shí)別技術(shù)概述31.2.1預(yù)處理41.2.2特征提取41.2.3指紋匹配51.2本文主要研究容與結(jié)構(gòu)安排52 特征提取算法介紹72.1指紋的特征數(shù)據(jù)72.1.1總體特征72.1.2局部特征72.2提取算法83 圖段的提取103.1基本定義103.1.1行程103.1.2行程碼103.1.3行程相關(guān)103.1.4圖段113.2圖段提取算法113.2.1提取行程113.2.2提取圖段123.3代碼展示123.3.3提取圖段124 特征提取134.1圖段結(jié)構(gòu)134.2.1圖段屬性134.2.1圖段結(jié)構(gòu)類型134.2提取端點(diǎn)144.2.1算

2、法簡介144.2.2判定規(guī)則144.3消除周邊點(diǎn)155 實(shí)驗(yàn)與結(jié)果165.1實(shí)驗(yàn)環(huán)境165.2實(shí)驗(yàn)結(jié)果165.2.1圖段提取的結(jié)果165.2.2特征提取的結(jié)果185.2.3結(jié)果分析186 總結(jié)2017 / 191 引言人類一直在研究有效的身份鑒別方法。用于身份鑒別的傳統(tǒng)方法有兩種：第一種基于標(biāo)志的身份鑒別，通常是通過判斷是否具有某種特定標(biāo)志來對(duì)身份進(jìn)行鑒別，如，護(hù)照、鑰匙，通行證等。第二種基于知識(shí)的身份鑒別，通常是根據(jù)被鑒別者所具有的某種知識(shí)來對(duì)其進(jìn)行鑒別，如銀行存折的密碼，個(gè)人認(rèn)證數(shù)字或固定問題答案等。這些傳統(tǒng)的身份鑒別方法具有簡便，易于實(shí)現(xiàn)且經(jīng)濟(jì)成本很少的優(yōu)點(diǎn)。但是，隨著科學(xué)技術(shù)和人類社會(huì)

3、的發(fā)展，現(xiàn)代社會(huì)對(duì)于人類自身身份識(shí)別的準(zhǔn)確性、安全性與實(shí)用性提出了更高要求。傳統(tǒng)的身份識(shí)別方法己經(jīng)遠(yuǎn)遠(yuǎn)不能滿足這種要求，于是人類找到了生物識(shí)別這種更為安全可靠、使用方便的新的身份識(shí)別技術(shù)。生物識(shí)別技術(shù)是利用人體生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。生物特征包括生理特征和行為特征，人的生理特征與生俱來，多為先天性的；行為特征則是習(xí)慣使然，多為后天形成。常見的生物特征包括：指紋、掌紋、虹膜、臉像、聲音、筆跡等。這些特征都具有唯一性和穩(wěn)定性的特點(diǎn)，且不易復(fù)制。與傳統(tǒng)的身份鑒別手段相比，基于生物特征的身份認(rèn)證技術(shù)具有以下優(yōu)點(diǎn)1, 2, 3：(1)普遍性：每個(gè)人都擁有該特征；(2)唯一性：沒有哪兩個(gè)人擁有同樣

4、的該特征；(3)永久性：該特征不會(huì)隨時(shí)間而變化；(4)可采集性：該特征能夠被定量地測量出來；(5)易實(shí)現(xiàn)性：容易實(shí)現(xiàn)，資源消耗少，對(duì)工作環(huán)境要求不苛刻； (6)防偽性：即不易偽造或被盜，識(shí)別率高；(7)方便性強(qiáng)：“隨身攜帶”，隨時(shí)隨地可用。目前的生物識(shí)別技術(shù)主要包括指紋、手形、面孔、虹膜、視網(wǎng)膜、聲音、簽名等的認(rèn)證。其中，指紋識(shí)別是利用手指紋線所構(gòu)成的圖像的唯一性和排他性進(jìn)行身份鑒定?；谥讣y的自動(dòng)識(shí)別技術(shù)是最早和最廣泛的被應(yīng)用于實(shí)踐的生物識(shí)別技術(shù)。它是一種相對(duì)準(zhǔn)確率最高，且最易被用戶接受的身份認(rèn)證方案1。1.1指紋識(shí)別發(fā)展概況指紋在全球圍被承認(rèn)中國使用最早，6000年以前就有使用。一千多年前

5、就有簽字畫押記載，無論是在法庭證詞上，還是在民間契約上，利用指紋作為個(gè)人標(biāo)識(shí)得到法律上的認(rèn)可。同一時(shí)期的古代印度，指紋也被用于人身標(biāo)識(shí)?，F(xiàn)代指紋人身標(biāo)識(shí)技術(shù)起始于十六世紀(jì)晚期。1684年，英國的植物形態(tài)學(xué)者N.Grew對(duì)指紋做出了系統(tǒng)的研究并發(fā)表了一篇論文，文中詳細(xì)分析了指紋的犁溝、脊線、汗腺孔的結(jié)構(gòu)，這篇文章被認(rèn)為是有關(guān)指紋技術(shù)的第一篇科學(xué)文獻(xiàn)。1788年，Mayer對(duì)指紋的構(gòu)造原理和指紋脊線犁溝分布特點(diǎn)做出了詳細(xì)的描述，給出了解剖學(xué)形式的詳細(xì)報(bào)告。1823年，Purkinje提出了最早的指紋分類策略，他將指紋按照紋線中脊的外形分布特點(diǎn)分成九類。H.Fauld在1880年指出指紋的個(gè)人唯一性

6、和終身不變性，這使得指紋在犯罪鑒別中得以正式應(yīng)用 (1808年阿根廷首次應(yīng)用)，與此同時(shí)，Herschel聲稱，他將指紋作為身份驗(yàn)證的依據(jù)已有近20年的歷史了。這些發(fā)現(xiàn)建立了現(xiàn)代指紋身份驗(yàn)證技術(shù)的基礎(chǔ)。十九世紀(jì)末，F(xiàn).Galton對(duì)指紋進(jìn)行了更為深入的研究，并在1888年提出利用細(xì)節(jié)特征點(diǎn)進(jìn)行單個(gè)指紋分類的方法。1899年E.Henry建立了著名的Henry指紋分類系統(tǒng)，提高了指紋驗(yàn)證效率，為指紋用于人身標(biāo)識(shí)起了重要的推動(dòng)作用與更為科學(xué)的鑒別標(biāo)準(zhǔn)。到二十世紀(jì)早期，結(jié)合解剖學(xué)觀點(diǎn)，人們對(duì)指紋的構(gòu)成已經(jīng)有了很好的了解，指紋鑒別被司法部門正式規(guī)定為合法的人身辨識(shí)方法，指紋鑒別己經(jīng)成為司法調(diào)查的一道標(biāo)

7、準(zhǔn)程序，指紋鑒別機(jī)構(gòu)在世界圍開始建立，構(gòu)造出大量的罪犯指紋庫。六十年代，隨著計(jì)算機(jī)的出現(xiàn)，人們開始了對(duì)自動(dòng)指紋鑒別技術(shù)的研究。美國聯(lián)邦調(diào)查局巴黎警部首先開發(fā)了自動(dòng)指紋鑒別系統(tǒng) (AFIS) 大大提高了法律相關(guān)部門的效率。在司法部門取得的成功，也大大推進(jìn)了自動(dòng)指紋鑒別系統(tǒng)向其他民用領(lǐng)域的轉(zhuǎn)化。20世紀(jì)末期以來，指紋識(shí)別技術(shù)被應(yīng)用到許多方面。通過使用指紋驗(yàn)證來取代各個(gè)計(jì)算機(jī)應(yīng)用程序的密碼就是最為典型的實(shí)例?？梢韵胂笕绻?jì)算機(jī)上的所有系統(tǒng)和應(yīng)用程序都可以使用指紋驗(yàn)證的話，人們使用計(jì)算機(jī)就會(huì)非常方便和安全，用戶不再討厭必要的安全性檢查，而開發(fā)商的售后服務(wù)工作也會(huì)減輕許多。IBM公司已經(jīng)開發(fā)成功并廣泛應(yīng)

8、用的Global Sign on軟件通過定義唯一的口令，使用指紋，就可以在公司整個(gè)網(wǎng)絡(luò)上暢行無阻。把指紋識(shí)別技術(shù)同IC卡結(jié)合起來，是目前最有前景的一個(gè)方向之一。該技術(shù)把卡的主人的指紋 (加密后) 存儲(chǔ)在IC卡上，并在IC卡的讀卡機(jī)上加裝指紋識(shí)別系統(tǒng)，當(dāng)讀卡機(jī)閱讀卡上的信息時(shí)，一并讀入持卡者的指紋，通過比對(duì)卡上的指紋與持卡者的指紋，就可以確認(rèn)持卡者是否是卡的真正主人，從而進(jìn)行下一步的交易。在更加嚴(yán)格的場合，還可以進(jìn)一步同后端主機(jī)系統(tǒng)數(shù)據(jù)庫上的指紋作比較。指紋IC卡可以廣泛地運(yùn)用于許多行業(yè)中，例如取代現(xiàn)行的ATM卡、制造防偽證件 (簽證或護(hù)照、公費(fèi)醫(yī)療卡、會(huì)員卡、借書卡等)。目前ATM提款機(jī)加裝指

9、紋識(shí)別功能在美國已經(jīng)開始使用。持卡人可以取消密碼 (避免老人和孩子記憶密碼的困難) 或者仍舊保留密碼，在操作上按指紋與密碼的時(shí)間差不多。近年來，自動(dòng)發(fā)送信息的互聯(lián)網(wǎng)絡(luò)，帶給人們的方便與利益，正在快速增長之中，但也因此產(chǎn)生了很多的問題，尤其在信息安全方面。無論是團(tuán)體或者個(gè)人的信息，都害怕在四通八達(dá)的網(wǎng)絡(luò)上傳送而發(fā)生有損權(quán)益或隱私的事情。由于指紋特征數(shù)據(jù)可以通過電子或其他傳輸方法在計(jì)算機(jī)網(wǎng)絡(luò)上進(jìn)行傳輸和驗(yàn)證，通過指紋識(shí)別技術(shù)，限定只有指定的人才能訪問相關(guān)信息，可以極提高網(wǎng)上信息的安全性，這樣，包括網(wǎng)上銀行、網(wǎng)上貿(mào)易、電子商務(wù)的一系列網(wǎng)絡(luò)商業(yè)行為，就有了安全性保障。SFNB (Security Fi

10、rst Network Bank安全第一網(wǎng)絡(luò)銀行) 就是通過互聯(lián)網(wǎng)絡(luò)來進(jìn)行資金劃算的，他們目前正在實(shí)施以指紋識(shí)別技術(shù)為基礎(chǔ)的保障安全性的項(xiàng)目，以增強(qiáng)交易的安全性。在醫(yī)院里，指紋識(shí)別技術(shù)可以驗(yàn)證病人身份，例如輸血管理。指紋識(shí)別技術(shù)也有助于證實(shí)尋求公共救援、醫(yī)療與其他政府福利或者保險(xiǎn)金的人的身份確認(rèn)。在這些應(yīng)用中，指紋識(shí)別系統(tǒng)將會(huì)取代或者補(bǔ)充許多大量使用照片和ID的系統(tǒng)。總之，隨著低價(jià)格高性能單片機(jī)和DSP的廣泛使用，以與廉價(jià)的取像設(shè)備、指紋鑒別算法的開發(fā)與研究，指紋鑒別技術(shù)具有更廣闊的發(fā)展前景，也將大量被應(yīng)用于人們的生產(chǎn)生活中1, 2。1.2指紋識(shí)別技術(shù)概述指紋識(shí)別技術(shù)簡稱FIS(Fingerp

11、rint Identification Technology)。前面已經(jīng)講到，早期的指紋識(shí)別技術(shù)僅限于人工或半自動(dòng)化的查找和匹配。到20世紀(jì)60年代，計(jì)算機(jī)技術(shù)的發(fā)展推動(dòng)了指紋自動(dòng)識(shí)別技術(shù)。目前指紋識(shí)別方法分為兩大類4：一是以手指毛細(xì)孔的位置，二是以手指表皮上的凸紋和凹紋所形成的紋路為識(shí)別的基準(zhǔn)。利用毛細(xì)孔來做識(shí)別，最主要的困難是必須以雷射光來掃描毛細(xì)孔的位置，設(shè)備不易取得，然而毛細(xì)孔的位置是永遠(yuǎn)固定不變的，而且毛細(xì)孔的位置不容易受外力而破壞，判斷成功率較高。凸凹紋線所形成的紋絡(luò)，可經(jīng)由油墨的按壓在紙上，或經(jīng)由掃描器掃描進(jìn)電腦后取得影像檔案，藉此來做判斷，所以取得非常容易，可是此種方法取得的指

12、紋，因?yàn)榻?jīng)過多次失真，使比對(duì)的錯(cuò)誤率提高。本文討論的提取特征數(shù)據(jù)的算法是基于第二類。因?yàn)檫@種方法取得的圖像多次失真，所以對(duì)計(jì)算機(jī)的自動(dòng)指紋識(shí)別技術(shù)要求比較高。而基于計(jì)算機(jī)的自動(dòng)指紋識(shí)別技術(shù)主要涉與三個(gè)步驟：圖像預(yù)處理、特征提取、特征匹配。1.2.1預(yù)處理在指紋自動(dòng)識(shí)別過程中，由于按下力、皮膚表面性質(zhì)的差異等各種原因的影響，都將導(dǎo)致得到的指紋圖像質(zhì)量欠佳，這些圖像給指紋特征點(diǎn)的正確提取與匹配造成了相當(dāng)大的困難。對(duì)指紋圖像進(jìn)行預(yù)處理，可以去除指紋圖像的各種噪聲和無效指紋區(qū)域，同時(shí)增強(qiáng)有效的指紋區(qū)域，這對(duì)于系統(tǒng)后面的處理是非常重要的，可以保證系統(tǒng)對(duì)于輸入圖像的魯棒性，降低指紋識(shí)別系統(tǒng)的錯(cuò)誤接受率 (

13、FAP：False Acceptance Probability) 和提高正確接受率(AAP：Authentic Acceptance Probability)5。預(yù)處理是指紋自動(dòng)識(shí)別系統(tǒng)中非常重要的一步，它的好壞直接影響著指紋識(shí)別的效果。預(yù)處理一般包括圖像增強(qiáng)、圖像的二值化、濾波等步驟4。預(yù)處理后將得到一幅相對(duì)連續(xù)、平滑的二值化指紋圖像。1.2.2特征提取特征提取一般分為兩個(gè)階段：提取特征點(diǎn)和特征點(diǎn)后處理。指紋圖像由大量的紋線構(gòu)成，紋線走向所形成的紋路可以用人眼直接觀察，它被稱作指紋的總體特征。指紋紋路并不是連續(xù)、平滑的，它經(jīng)常出現(xiàn)中斷或分叉，這些斷點(diǎn)和分叉點(diǎn)就是指紋的局部特征，稱為“細(xì)節(jié)點(diǎn)

14、”或“特征點(diǎn)”。兩枚指紋經(jīng)常會(huì)具有一樣的總體特征，但它們的局部特征細(xì)節(jié)點(diǎn)，卻不可能完全一樣，就是這些細(xì)節(jié)點(diǎn)提供了指紋唯一性的確認(rèn)信息。一般的指紋識(shí)別系統(tǒng)都是基于細(xì)節(jié)點(diǎn)的識(shí)別系統(tǒng)。目前最常用的細(xì)節(jié)特征是美國聯(lián)邦調(diào)查局 (FBI) 提出的特征點(diǎn)坐標(biāo)模型，它利用端點(diǎn) (Ending) 與分叉點(diǎn) (Bifurcating) 兩種特征來鑒定指紋4, 6。盡管已有很多指紋圖像增強(qiáng)算法，但是對(duì)于質(zhì)量較差的指紋圖像很難完全彌補(bǔ)其中的缺陷。常見的指紋缺陷有紋線斷裂、紋線粘連、紋線中出現(xiàn)孔洞等。這些缺陷會(huì)使細(xì)節(jié)點(diǎn)自動(dòng)提取算法得到很多虛假細(xì)節(jié)點(diǎn)。因此，特征提取是整個(gè)識(shí)別系統(tǒng)的關(guān)鍵。1.2.3指紋匹配指紋匹配一般分為

15、兩類7：驗(yàn)證(verification)和辨識(shí)(identification)。認(rèn)證是一對(duì)一的匹配，它首先把某人的指紋特征與個(gè)人信息以某種形式存儲(chǔ)起來，需要認(rèn)證時(shí)將當(dāng)前的請(qǐng)求指紋與之前的存儲(chǔ)指紋進(jìn)行匹配，判斷兩枚指紋是否來自同一個(gè)手指。識(shí)別是一對(duì)多的匹配，和認(rèn)證系統(tǒng)類似，這種系統(tǒng)要事先把許多人的指紋特征與個(gè)人信息存入數(shù)據(jù)庫，識(shí)別時(shí)將當(dāng)前請(qǐng)求指紋與數(shù)據(jù)庫中的多個(gè)指紋分別進(jìn)行一對(duì)一的匹配，判斷是否有和當(dāng)前指紋符合的信息。顯然，識(shí)別完成的就是多次認(rèn)證，認(rèn)證系統(tǒng)可以說是識(shí)別系統(tǒng)的一個(gè)特例，它就是一對(duì)多的識(shí)別系統(tǒng)。因此，無論哪種類型的匹配，都是新輸入指紋的特征與原來存儲(chǔ)指紋的特征進(jìn)行比對(duì)的過程。匹配算法

16、的核心思想是：通過某些坐標(biāo)變換(如平移、旋轉(zhuǎn)、伸縮變換)，消除由于采集時(shí)指紋位移、旋轉(zhuǎn)和畸變對(duì)特征點(diǎn)位置造成的影響；然后對(duì)比坐標(biāo)變換后指紋特征點(diǎn)的相關(guān)信息(位置、類型、角度等)。1.2本文主要研究容與結(jié)構(gòu)安排目前，盡管指紋識(shí)別技術(shù)己有很多的商業(yè)產(chǎn)品，但識(shí)別準(zhǔn)確率還是不能滿足某些特定的應(yīng)用；且許多已有的算法因商業(yè)利益而未能公開；同時(shí)，對(duì)于每個(gè)細(xì)節(jié)點(diǎn)需要記錄其類型、位置坐標(biāo)和所在紋線方向，在非理想采集條件下，指紋圖像不能保證都很清晰，其中可能出現(xiàn)對(duì)比度不均勻、紋線斷裂、紋線粘連等缺陷，造成紋線模糊或失真，這是使指紋特征可靠提取非常困難的主要原因。因此，開發(fā)更多理想的自動(dòng)指紋識(shí)別系統(tǒng)在目前仍然是一個(gè)

17、有實(shí)用價(jià)值和有一定難度的研究任務(wù)。本文參閱了大量指紋識(shí)別方面的文獻(xiàn)資料，針對(duì)指紋識(shí)別技術(shù)中的一個(gè)重要環(huán)節(jié)：特征提取進(jìn)行了深入研究，對(duì)以往的算法進(jìn)行了大量改進(jìn)和完善。具體工作如下：(1) 特征提取采用了種基于圖段分析提取細(xì)節(jié)點(diǎn)的方法，這種方法將整個(gè)匹配過程分為三個(gè)階段：第一階段稱為圖段提取，第二階段稱為細(xì)節(jié)點(diǎn)提取。該方法使相差很大的指紋與早淘汰，減少了拒絕時(shí)間。(2) 在圖段提取階段，提取指紋圖像中的局部連通區(qū)域?yàn)閳D段。具體來說指紋圖像中的一個(gè)黑色圖段表示一個(gè)沒有分支、粗細(xì)均勻的線條狀結(jié)構(gòu)的局部紋線段。(3) 在細(xì)節(jié)點(diǎn)提取階段，先分析圖段的結(jié)構(gòu)類型。根據(jù)圖段的結(jié)構(gòu)類型、是否存在相關(guān)圖段與其與相關(guān)

18、圖段的相對(duì)位置關(guān)系，提取指紋的細(xì)節(jié)點(diǎn)。(4) 將所有算法在 Microsoft Visual Studio 2005 上編程實(shí)現(xiàn)，并通過大量的實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證。實(shí)驗(yàn)結(jié)果表明本文采用的特征算法取得了較好的效果。2 特征提取算法介紹2.1指紋的特征數(shù)據(jù)指紋之間的區(qū)別，即特征，目前分為總體特征和局部特征4, 6, 8。2.1.1總體特征總體特征是指那些用肉眼直接就可以觀察到的特征8：(1) 模式區(qū) (Pattern Area)模式區(qū)是指指紋上包括了總體特征的區(qū)域，即從模式區(qū)就能夠分辨出指紋是屬于那一種類型的。有的指紋識(shí)別算法只使用模式區(qū)的數(shù)據(jù)。SecureTouch 的指紋識(shí)別算法使用了所取得的完

19、整指紋而不僅僅是模式區(qū)進(jìn)行分析和識(shí)別。(2) 核心點(diǎn) (Core Point)核心點(diǎn)位于指紋紋路的漸進(jìn)中心，它在讀取指紋和比對(duì)指紋時(shí)作為參考點(diǎn)。許多算法是基于核心點(diǎn)的，既只能處理和識(shí)別具有核心點(diǎn)的指紋。核心點(diǎn)對(duì)于SecureTouch 的指紋識(shí)別算法很重要，但沒有核心點(diǎn)的指紋它仍然能夠處理。三角點(diǎn)位于從核心點(diǎn)開始的第一個(gè)分叉點(diǎn)或者斷點(diǎn)、或者兩條紋路會(huì)聚處、孤立點(diǎn)、折轉(zhuǎn)處，或者指向這些奇異點(diǎn)。三角點(diǎn)提供了指紋紋路的計(jì)數(shù)跟蹤的開始之處。(3) 紋數(shù) (Ridge Count)指模式區(qū)指紋紋路的數(shù)量。在計(jì)算指紋的紋數(shù)時(shí)，一般先在連接核心點(diǎn)和三角點(diǎn)，這條連線與指紋紋路相交的數(shù)量即可認(rèn)為是指紋的紋數(shù)。2

20、.1.2局部特征局部特征是指指紋上的節(jié)點(diǎn)的特征，這些具有某種特征的節(jié)點(diǎn)稱為特征點(diǎn)。兩枚指紋經(jīng)常會(huì)具有一樣的總體特征，但它們的局部特征特征點(diǎn)，卻不可能完全一樣8。(1) 端點(diǎn) (Ending)：一條紋路在此終結(jié)。(2) 分叉點(diǎn) (Bifurcation)：一條紋路在此分開成為兩條或更多的紋路。(3) 分歧點(diǎn) (Ridge Divergence)：兩條平行的紋路在此分開。(4) 孤立點(diǎn) (Dot or Island)：一條特別短的紋路，以至于成為一點(diǎn)。(5) 環(huán)點(diǎn) (Enclosure)：一條紋路分開成為兩條之后，立即有合并成為一條，這樣形成的一個(gè)小環(huán)稱為環(huán)點(diǎn)。(6) 短紋 (Short Ridg

21、e)：一端較短但不至于成為一點(diǎn)的紋。2.2提取算法目前最常用的指紋特征屬于局部特征，它是由美國聯(lián)邦調(diào)查局 (FBI) 提出的利用端點(diǎn) (Ending) 與分叉點(diǎn) (Bifurcating) 兩種特征來鑒定指紋4, 6。如圖11所示。圖11 端點(diǎn)和分叉點(diǎn)對(duì)于這種指紋特征，眾多專家學(xué)者提出了很多細(xì)節(jié)點(diǎn)提取算法，其中最常用的是基于細(xì)化圖像的方法913。此類方法首先得到細(xì)化指紋圖像，然后通過鄰域分析得到細(xì)化紋線的端點(diǎn)和分叉點(diǎn)。Xiao等人9綜合利用細(xì)節(jié)點(diǎn)的統(tǒng)計(jì)特性和結(jié)構(gòu)特性進(jìn)行細(xì)節(jié)點(diǎn)后處理；Hung10通過將細(xì)化紋線與其上的細(xì)節(jié)點(diǎn)表示成圖的形式，利用圖論的知識(shí)來清除虛假細(xì)節(jié)點(diǎn)；Ratha等人11根據(jù)細(xì)

22、節(jié)點(diǎn)空間關(guān)系清除虛假細(xì)節(jié)點(diǎn)；Farina等人12通過分析真假細(xì)節(jié)點(diǎn)周圍紋線的拓?fù)浣Y(jié)構(gòu)，給出了清除虛假細(xì)節(jié)點(diǎn)和驗(yàn)證真實(shí)細(xì)節(jié)點(diǎn)可靠性的方法；Bian等人13的方法不僅利用了細(xì)節(jié)點(diǎn)周圍細(xì)化紋線的統(tǒng)計(jì)和結(jié)構(gòu)特性，而且利用了二值圖像上對(duì)應(yīng)紋線的寬度信息。上述基于細(xì)化圖像的細(xì)節(jié)點(diǎn)提取方法主要有以下缺點(diǎn)：細(xì)化處理比較耗時(shí)；若圖像增強(qiáng)和二值化效果不好，會(huì)產(chǎn)生大量虛假細(xì)節(jié)點(diǎn)；細(xì)節(jié)點(diǎn)后處理操作非常耗時(shí)。因此，本文采用的是一種圖段分析提取細(xì)節(jié)點(diǎn)的方法6。該方法首先通過行程編碼匹配得到二值指紋圖像中的圖段，每個(gè)圖段表示一個(gè)不包含分支的紋線段。然后根據(jù)圖段的結(jié)構(gòu)形式和圖段之間的連接關(guān)系判定指紋紋線端點(diǎn)的位置。利用指紋谷

23、線端點(diǎn)與紋線分叉點(diǎn)的對(duì)應(yīng)關(guān)系，通過提取谷線上的端點(diǎn)得到紋線的分叉點(diǎn)。由于在端點(diǎn)判定之前清除了噪聲圖段，使該方法對(duì)紋線邊緣毛刺和紋線中的小孔等結(jié)構(gòu)形式具有較好的魯棒性，不會(huì)像基于細(xì)化圖像方法那樣產(chǎn)生大量虛假細(xì)節(jié)點(diǎn)。從而提高指紋匹配的精度。3 圖段的提取目前的自動(dòng)指紋識(shí)別系統(tǒng)，普遍使用基于細(xì)節(jié)點(diǎn)的點(diǎn)模式匹配算法，一般情況下若兩幅圖像能成功匹配10個(gè)特征點(diǎn)對(duì)便可確認(rèn)為同一枚指紋。因此，特征點(diǎn)是識(shí)別的依據(jù)。本文采用的方法提取特征點(diǎn)要先提取圖段。3.1基本定義在提取之前，首先明確幾個(gè)基本概念的定義，這些概念在后面的討論中經(jīng)常用到。3.1.1行程在圖像的某一行水平掃描線上，由多個(gè)連續(xù)的、具有一樣灰度值的像

24、素點(diǎn)所組成的像素點(diǎn)集合稱為一個(gè)行程6。對(duì)于二值圖像有兩種行程：黑色行程和白色行程。例如圖31中共有6個(gè)黑色行程。圖31 行程與其相關(guān)關(guān)系3.1.2行程碼由一個(gè)行程的起始和結(jié)束點(diǎn)水平坐標(biāo)構(gòu)成的二元組稱為行程碼，用(S，E)表示，其中S表示行程的起始坐標(biāo)，E代表行程的終止坐標(biāo)6。3.1.3行程相關(guān)設(shè) (S1，E1) 和 (S2，E2) 為分屬相鄰兩個(gè)掃描行中的兩個(gè)行程，如果S2 > E1或E2 < S1，則稱這兩個(gè)行程不相關(guān)，反之稱這兩個(gè)行程相關(guān)6。而判定行程相關(guān)與否的過程被稱為行程匹配。雖然一幅二值圖像中的黑白像素排列初看起來顯得雜亂無章，但仔細(xì)觀察可以發(fā)現(xiàn)。相鄰兩個(gè)掃描行中的行程之

25、間只存在以下兩種相關(guān)關(guān)系：(1) 某一行中的一個(gè)行程與另一行中的惟一一個(gè)行程相關(guān)，稱之為一對(duì)一相關(guān)6。如圖31中的行程b和行程c為一對(duì)一相關(guān)，行程f和行程a，行程e和行程a也是一對(duì)一相關(guān)。(2) 某一行中的一個(gè)行程與另一行的多個(gè)行程同時(shí)相關(guān)，則稱為一對(duì)多相關(guān)6。例如圖31中的行程a同時(shí)與行程b，d相關(guān)，行程a和行程f，e之間也是一對(duì)多相關(guān)。3.1.4圖段由一系列互為一對(duì)一相關(guān)的行程所組成的集合稱為圖段6。如圖31中的行程c和b構(gòu)成一個(gè)圖段。圖32所示的圖案由m，n和k三個(gè)圖段構(gòu)成。圖段的重要幾何參數(shù)是圖段包絡(luò)矩形的寬度W和高度H，圖32中圖段k的包絡(luò)矩形如虛線所示：圖32 圖段3.2圖段提取算

26、法3.2.1提取行程逐行掃描圖像，如果當(dāng)前像素為前景點(diǎn)，則進(jìn)行以下操作：(1) 如果當(dāng)前像素為該行的第一個(gè)像素或者它的前一像素為背景點(diǎn)，則開始新的行程；(2) 如果當(dāng)前像素為該行的最后一個(gè)像素或者它的后一像素為背景點(diǎn)，則該行程結(jié)束，并且把行程的圖段編號(hào)初始化為，以便后面使用；(3) 把像素的行程編號(hào)和行程對(duì)應(yīng)起來。3.2.2提取圖段對(duì)每個(gè)行程依次進(jìn)行以下操作，直到最后一個(gè)行程：(1) 如果當(dāng)前行程的圖段編號(hào)為初始化的，就表示當(dāng)前行程已經(jīng)有了歸屬圖段，則操作下一個(gè)行程；(2) 初始化新圖段，即把當(dāng)前行程放入該圖段的起始行程和結(jié)束行程；(3) 如果當(dāng)該圖段的結(jié)束行程在圖像的最后一行，則進(jìn)行步驟 (

27、9)；(4) 掃描該圖段的結(jié)束行程的下一行，求出當(dāng)前行程的下相關(guān)行程數(shù)，如不為1，則進(jìn)行步驟 (9)；(5) 求該圖段的結(jié)束行程下相關(guān)行程數(shù)的上相關(guān)行程數(shù)，如不為1，則進(jìn)行步驟 (9)；(6) 如兩個(gè)行程的長度相差太大(本文取的3倍)，則進(jìn)行步驟 (9)；(7) 把該圖段的結(jié)束行程的下相關(guān)行程放入該圖段的結(jié)束行程；(8) 繼續(xù)步驟(3)。(9) 求出單個(gè)圖段和更新圖段集合的一些屬性 (在3.2.1圖段屬性中會(huì)具體描述)，以便以后使用；(10) 操作下一個(gè)行程。3.3代碼展示3.3.3提取圖段4 特征提取因?yàn)楸疚牟捎玫姆椒ㄔ谇蠓植纥c(diǎn)的時(shí)候是利用指紋白色谷線端點(diǎn)與黑色紋線分叉點(diǎn)對(duì)應(yīng)的關(guān)系，通過提取

28、白色谷線上的端點(diǎn)得到黑色紋線的分叉點(diǎn)。所以這里就只描述黑色紋線端點(diǎn)的求法。4.1圖段結(jié)構(gòu)圖段的結(jié)構(gòu)會(huì)影響對(duì)細(xì)節(jié)點(diǎn)的判斷。4.2.1圖段屬性而對(duì)圖段結(jié)構(gòu)進(jìn)行分析需要以下幾個(gè)屬性：(在圖段提取可以中一并求出)(1) 單個(gè)圖段的屬性。包括圖段的矩形的寬度H和高度W，以與構(gòu)成圖段的行程的平均長度L。(2) 圖段集合的屬性。包括圖段的最大寬度RWmax和最小寬度RWmin。其中，為了增強(qiáng)算法的適用性，對(duì)不同的指紋圖像，RWmax和RWmin應(yīng)取不同的值。本文取的是所有H>1.5W的圖段中最大的L值為RWmax，最小的L值為RWmin。4.2.1圖段結(jié)構(gòu)類型(1) 噪聲圖段：如果W<RWmax

29、且H<RWmax，或者L<(1/2)RWmin，則圖段為噪聲圖段。它代表圖段的尺寸不合理。(2) 垂直方向圖段：如果H W，則圖段為垂直方向圖段。它代表圖段的方向在45°至135°之間。如圖31 (a) 所示。(3) 水平方向圖段：如果H < W，則圖段為水平方向圖段。它代表圖段的方向在-45°至45°之間。如圖31 (b) 所示。(4) 扁長型圖段：如果HRWmax且L>RWmax，則圖段為扁長型圖段。它代表圖段處于水平狀態(tài)。(5) 弧頂、弧底圖段：弧頂圖段指呈現(xiàn)上三角形的圖段，弧底圖段指呈現(xiàn)下三角形的圖段。如圖31 (c) 和

30、圖31 (d) 所示。圖31 圖段結(jié)構(gòu)類型因?yàn)榛№敗⒒〉讏D段必然同時(shí)是水平方向或扁長型圖段，所以本文把弧頂、弧底圖段的判斷放在端點(diǎn)的提取里，有需要的時(shí)候才進(jìn)行判斷。4.2提取端點(diǎn)4.2.1算法簡介(1) 在正式提取端點(diǎn)之前先分析圖段的結(jié)構(gòu)，把噪聲圖段去除；(2) 依次掃描圖段上、下相關(guān)圖段數(shù)，也就是圖段起始行程的上相關(guān)行程數(shù)和結(jié)束行程下相關(guān)行程數(shù) (可以參照2.2.2提取圖段)，只要上、下相關(guān)行程所在的圖段不是噪聲圖段；(3) 再按照一定的規(guī)則提取端點(diǎn)。4.2.2判定規(guī)則(1) 如果當(dāng)前圖段為扁長型圖段，無上相關(guān)圖段或上相關(guān)圖段在當(dāng)前圖段的左側(cè)，且無下相關(guān)圖段或下相關(guān)圖段在當(dāng)前圖段的左側(cè)，則當(dāng)

31、前圖段的右側(cè)為端點(diǎn)；(2) 如果當(dāng)前圖段為扁長型圖段，無上相關(guān)圖段或上相關(guān)圖段在當(dāng)前圖段的右側(cè)，且無下相關(guān)圖段或下相關(guān)圖段在當(dāng)前圖段的右側(cè)，則當(dāng)前圖段的左側(cè)為端點(diǎn)；(3) 如果當(dāng)前圖段為水平方向圖段，無上相關(guān)圖段，且無下相關(guān)圖段或不是弧頂圖段，則當(dāng)前圖段的上端為端點(diǎn)；(4) 如果當(dāng)前圖段為水平方向圖段，無下相關(guān)圖段，且無上相關(guān)圖段或不是弧頂圖段，則當(dāng)前圖段的下端為端點(diǎn)；(5) 如果當(dāng)前圖段為垂直方向圖段，無上相關(guān)圖段，則當(dāng)前圖段的上端為端點(diǎn)；(6) 如果當(dāng)前圖段為垂直方向圖段，無下相關(guān)圖段，則當(dāng)前圖段的下端為端點(diǎn)；(7) 對(duì)于扁長和水平方向圖段上的端點(diǎn)，其位置坐標(biāo)取整個(gè)圖段中最左或最右端的像素

32、點(diǎn)的坐標(biāo)；(8) 對(duì)于垂直方向圖段上的端點(diǎn)，則取該圖段第一個(gè)或的最后一個(gè)行程中點(diǎn)為端點(diǎn)的位置坐標(biāo)。4.3消除周邊點(diǎn)由于采集的區(qū)域有限，則會(huì)產(chǎn)生接近圖像邊緣的紋線端點(diǎn)，稱為周邊點(diǎn)。要去除周邊點(diǎn)，首先用直線試探求得的經(jīng)過當(dāng)前圖段最長的射線，這條射線的方向就是端點(diǎn)的方向。然后向求出的端點(diǎn)的方向反方向引出一條射線，如果這條射線在到達(dá)圖像邊緣之前沒有經(jīng)過任何圖段，就可以認(rèn)為當(dāng)前端點(diǎn)是采集區(qū)域有限而生成的周邊點(diǎn)。5 實(shí)驗(yàn)與結(jié)果5.1實(shí)驗(yàn)環(huán)境本文的所有算法均在 Microsoft Visual Studio 2005 用C語言編程實(shí)現(xiàn)。本實(shí)驗(yàn)采用的指紋圖像是已經(jīng)進(jìn)行采集和預(yù)處理的。采集是基于Secugen公

33、司的FDU光學(xué)指紋采集儀進(jìn)行指紋采集；預(yù)處理首先采用Gabor濾波的方法進(jìn)行指紋圖像增強(qiáng)，然后用Otsu法進(jìn)行圖像二值化，再用3×3中值濾波器進(jìn)行邊緣平滑和去除孤立噪聲點(diǎn)。5.2實(shí)驗(yàn)結(jié)果如圖51所示。這是一幅經(jīng)過增強(qiáng)、二值化等預(yù)處理的圖，下文所述的實(shí)驗(yàn)結(jié)果都是在這圖上進(jìn)行處理的。圖51預(yù)處理后的指紋圖像5.2.1圖段提取的結(jié)果因?yàn)楸疚乃玫乃惴ㄊ抢弥讣y谷線端點(diǎn)與紋線分叉點(diǎn)的對(duì)應(yīng)關(guān)系，通過提取谷線上的端點(diǎn)得到紋線的分叉點(diǎn)。所以，圖段提取的結(jié)果不僅有黑色的紋線圖段，還有白色的谷線圖段。(1) 其中，黑色紋線圖段如圖52所示。圖52 黑色紋線圖段(2) 而實(shí)驗(yàn)中提取白色谷線圖段，是將圖像中的黑白兩色反轉(zhuǎn)后再和黑色紋線圖段一樣提取的。黑白反轉(zhuǎn)和白色谷線圖段分別如圖52 (左) 和圖52 (右)所示。圖52 反轉(zhuǎn)圖 (左) 和白色谷線圖段 (右)5.