【正文】 Relaxation[J].Pattem Recogition,1993,12(2):269275 [20]A． Hrechak and J． Mchugh． Automated fingerprint recognition using structural matching[J]． Patern Recognition,1990,23(8):893— 904 指紋識(shí)別中若干關(guān)鍵問(wèn)題研究 22 致 謝 經(jīng)過(guò)半年的材料準(zhǔn)備、開(kāi)題、論文寫(xiě)作及修改，我的畢業(yè)論文終于定稿。 本文由于時(shí)間上的限制，在實(shí)現(xiàn)細(xì)化和匹配的基礎(chǔ)上沒(méi)有能夠?qū)?xì)化和匹配算法進(jìn)行更深入的改進(jìn)研究，是一個(gè)缺憾。 （ 4）在上述的特征點(diǎn)的部分選用了點(diǎn)模匹配，以特征點(diǎn)滿(mǎn)足相對(duì)距離的個(gè)數(shù)和相對(duì)值為依據(jù)判斷是否匹配。選用了一種比較精確的 模板細(xì)化，得到了指紋細(xì)化后比較清晰的圖像。分割前還對(duì)圖像進(jìn)行低頻歸一化處理。本文針對(duì)指紋圖像的特性，將均值方差法、模板細(xì)化、點(diǎn)模匹配應(yīng)用于指紋識(shí)別技術(shù)，以改善指紋識(shí)別算法的性能。方法二對(duì)圖像的預(yù)處理要求不高，方法簡(jiǎn)單，但計(jì)算復(fù)雜，適合一對(duì)多的檢索性匹配。相似度的計(jì)算，方法一以滿(mǎn)足特征點(diǎn)的相對(duì)距離差距不大的點(diǎn)的個(gè)數(shù)為相似依據(jù)；方法二以卷積值的大小來(lái)判斷圖像的相似性，并計(jì)算圖像的相似距離。兩種方法都以浙江理工大學(xué)信息電子學(xué)院本科畢業(yè)論文 (設(shè)計(jì) ) 19 中心點(diǎn)為基準(zhǔn)點(diǎn)。 FFT 卷積的方法能從多幅數(shù)據(jù)庫(kù)的指紋圖片中挑選出與當(dāng)前輸入圖片最相近的指紋，即使它的圖像有所殘缺，也不大會(huì)影響它的判斷和距離的計(jì)算。如果可行，則此匹配法能找到最相近的圖片代號(hào)并顯示出它們的距離。這種方法簡(jiǎn)單明了，缺點(diǎn)在于計(jì)算量比較大，需要較久的計(jì)算時(shí)間。 本論文還參考了一種匹配方式，它先讀取所有的數(shù)據(jù)庫(kù)，庫(kù)的大小 可自己選擇。匹配與否用 success 值返回。最后判斷可積點(diǎn)的個(gè)數(shù)和相對(duì)值。這種方法將原特征點(diǎn)的相對(duì)距離進(jìn)行修改，使得各個(gè)特征點(diǎn)之間的相對(duì)距離產(chǎn)生差異。 浙江理工大學(xué)信息電子學(xué)院本科畢業(yè)論文 (設(shè)計(jì) ) 17 本論文匹配方法介紹 針對(duì)上述中提及的問(wèn) 題，本論文采用了兩種匹配方式，第一種為主流的點(diǎn)模匹配法，第二種則是較簡(jiǎn)單的 FFT 卷積判斷法。參考點(diǎn)在指紋圖像的識(shí)別中是也至關(guān)重要的。 (4)最終得到的是兩幅指紋的相似度，怎么確定相似度的計(jì)算方式。 (3)由于指紋存在變形位移，任何一對(duì)匹配點(diǎn)之間都不是絕對(duì)相等，而是存在一定的差距。當(dāng)然，他所帶來(lái)的難題有： (1)如何快速找到基準(zhǔn)點(diǎn)把兩幅指紋對(duì)齊。從模板指紋和輸入指紋中選取一個(gè)節(jié)點(diǎn)作為參考節(jié)點(diǎn)對(duì)，在進(jìn)行節(jié)點(diǎn)匹配時(shí)先利用基準(zhǔn)點(diǎn)將指紋對(duì)齊，然后再評(píng)估其它節(jié)點(diǎn)的匹配程度。點(diǎn)模式匹配是著名的數(shù)學(xué)難題。對(duì)于基于細(xì)節(jié)點(diǎn)的匹配思路大體分兩種：基于直角坐標(biāo)系 的特征識(shí)別和基于極坐標(biāo)系的特征識(shí)別 [19]。通過(guò)將細(xì)節(jié)點(diǎn)表示為點(diǎn)模式，一個(gè)指紋識(shí)別問(wèn)題可以轉(zhuǎn)化為一個(gè)點(diǎn)模式匹配問(wèn)題。目前最為常用的方法是 FBI 提出的細(xì)節(jié)點(diǎn)坐標(biāo)模型來(lái)做細(xì)節(jié)匹配。 指紋圖像匹配方面， 主要有基于圖像，脊線(xiàn)結(jié)構(gòu)和特征點(diǎn)的方法。 指紋識(shí)別中若干關(guān)鍵問(wèn)題研究 16 第 5章 指紋圖像的匹配 指紋圖像匹配方法 指紋匹配要解決的是對(duì)兩幅給定指紋圖像的特征模式進(jìn)行比對(duì)，判斷這兩幅圖像是否 來(lái)自同一個(gè)人的同一手指。對(duì)于特征點(diǎn)和偽特征點(diǎn)的判斷方法還有很多，端點(diǎn)判斷和分叉點(diǎn)判斷屬于比較多的特征點(diǎn)判斷，偽特征點(diǎn)也還有別的種類(lèi)，短線(xiàn)之類(lèi)也屬于處理后出現(xiàn)的偽特征，本仿真中沒(méi)有對(duì)此作出處理。 圖 a 指紋 1 判斷點(diǎn) 圖 b 指紋 2 判斷點(diǎn) 圖 41 通過(guò) 判斷后得到的特征點(diǎn)分布圖 這個(gè)特征點(diǎn)分布結(jié)果圖包含了特征點(diǎn)和偽特征點(diǎn)。小橋處理方式類(lèi)同斷點(diǎn)和毛刺。小橋的判斷條件為 :10 范圍內(nèi)特征值為 1， 6 的上半范圍或下半范圍特征值仍為 1。毛刺的處理方式也類(lèi)同斷點(diǎn)。第四類(lèi)為毛刺，毛刺的判斷類(lèi)似于短點(diǎn)。此時(shí)在更小 12 的上半范圍或下半范圍，特征仍為 2 則浙江理工大學(xué)信息電子學(xué)院本科畢業(yè)論文 (設(shè)計(jì) ) 15 認(rèn)為為斷點(diǎn)。第二類(lèi)：對(duì)于直線(xiàn) 12 點(diǎn)的和不超過(guò) 1 的點(diǎn)也被視為偽特征點(diǎn)，處理方式類(lèi)同。第一類(lèi)：超出一定邊界，仿真中用了 17。處理方式類(lèi)同上面。 （ 2）分叉點(diǎn)的判斷條件為：周?chē)?8 鄰域兩兩相鄰當(dāng)且僅當(dāng)存在 6 個(gè)不同值。其中（ 1）端點(diǎn)的判斷條件為：周?chē)?8 鄰域兩兩相鄰當(dāng)且僅當(dāng)存在 2 個(gè)不同值。第 3 足則專(zhuān)門(mén)記錄偽特征最終可以除去。對(duì)整個(gè)圖像進(jìn)行特征提取后得到的特征點(diǎn)并非全部都是真實(shí)的分叉點(diǎn)和端點(diǎn)，由于指紋質(zhì)量，細(xì)化、特征提取過(guò)程引入的噪聲造成了很多偽特征點(diǎn)，特別是圖像邊 緣有很多圖像分割產(chǎn)生的邊界偽端點(diǎn)。 在提取指紋圖像的細(xì)節(jié)特征中，由于圖像質(zhì)量和噪聲的干擾，存在 大量的偽特征點(diǎn)，實(shí)驗(yàn)表明一幅質(zhì)量較差的圖像在經(jīng)過(guò)預(yù)處理，細(xì)節(jié)特征提取后可能產(chǎn)生多達(dá)一、兩萬(wàn)個(gè)細(xì)節(jié)特征點(diǎn)，其中包含了大量的偽特征點(diǎn)，這些偽特征點(diǎn)的存在，不但使匹配的速度大大降低，還使指紋識(shí)別性能急劇下降，造成識(shí)別系統(tǒng)的拒真率和誤識(shí)率的上升，因此在進(jìn)行指紋匹配之前，應(yīng)對(duì)細(xì)節(jié)特征進(jìn)行驗(yàn)證，盡可能將偽特征點(diǎn)去除，同時(shí)保留真特征點(diǎn)。 指紋特征提取和去偽特征 目前在細(xì)化二值圖像中提取細(xì)節(jié)特征多是用 8 鄰域法，該方法比較簡(jiǎn)單，在得到可靠的細(xì)化二值圖像后，只需要一個(gè) 3 3 的模板便可將端點(diǎn)和分叉點(diǎn)提取出來(lái)。最后確定出特征點(diǎn)的類(lèi)型、位置、方向。 目前已定義的特征類(lèi)型己達(dá) 150 多種，但是這些擴(kuò)展的特征往往不易提取相互區(qū)分，并且它們都可以由端點(diǎn)和分叉點(diǎn)的組合進(jìn)行描述，這使得端點(diǎn)和分叉點(diǎn)成為最常用的結(jié)構(gòu)特征，也稱(chēng)為細(xì)節(jié)特征，它被認(rèn)為是最穩(wěn)定、最容易檢查的，而且占全部特征點(diǎn)的 80％以上。指紋由脊線(xiàn)和谷線(xiàn)交替構(gòu)成，在大多數(shù)地方紋線(xiàn)連續(xù)且相互平行，而某些局部不連續(xù)的地方構(gòu)成了細(xì)節(jié)點(diǎn)。 為了比較兩個(gè)指紋是否相同，需要從指紋圖像中提取出能表示指紋唯一性的特征。 (2)基于直接灰度的特征提取方法：這種方法直接從灰度圖像出發(fā)，通過(guò)分析圖像的紋理屬性和拓?fù)浣Y(jié)構(gòu)提取特征點(diǎn)。 (4)魯棒性：要求這種特征對(duì)噪聲的存在與指紋形變不敏感。 (2)可測(cè)試性：適用于指紋匹配算法，便于在匹配算法中應(yīng)用。對(duì)于自動(dòng)指紋識(shí)別技術(shù)而言，選擇一種合適的、能表達(dá)指紋唯一性的特征量是非常關(guān)鍵的。 浙江理工大學(xué)信息電子學(xué)院本科畢業(yè)論文 (設(shè)計(jì) ) 13 第 4章 指紋圖像的特征提取 指紋特征提 取概述 特征提取就是對(duì)細(xì)化后的指紋圖像提取表示其特征的信息的操作。 當(dāng)然，此次仿真的細(xì)化還有待改進(jìn)。 細(xì)化將黑白二值圖像細(xì)化成了單個(gè)像素帶寬的指紋圖像，由于模板的選擇不同，上圖中的細(xì)化圖像一定程度上存在毛刺、分叉、斷點(diǎn)等不理想的情況。細(xì)算中的模板在一個(gè)函數(shù)中實(shí)現(xiàn)，細(xì)化結(jié)果如下圖所示。 （ 4）循環(huán)進(jìn)行上述過(guò)程，到所有點(diǎn)值不改變?yōu)橹梗疃噙M(jìn)行 20 次細(xì)化。對(duì)于滿(mǎn)足后六種情況的模板賦值為 3，別的情況點(diǎn)值不做改變。 本論文中采用了方法步驟如下： （ 1）建立 3 維數(shù)組 ，第一組數(shù)據(jù)為預(yù)處理后的圖像信息，定義每一個(gè)像素點(diǎn)它周?chē)c(diǎn)像素參數(shù)。模板分為保留模板和消除模板，消除模板就是根據(jù)條件判定這點(diǎn)去除作為背景的模板；保留模板則是根據(jù)條件判定這點(diǎn)保留作為前景的模板。 制約細(xì)化的直觀表現(xiàn)在計(jì)算速度、毛刺和斷點(diǎn)上。性能上這些算法各有所長(zhǎng)。由于并行細(xì)化算法具有快速而準(zhǔn)確的特性，因此他一直是人們研究的熱點(diǎn)，并且相應(yīng)的提出了許多并行細(xì)化算法，如 OPTA 細(xì)化算法 [15]， R． W． Hall 細(xì)化算法， Rosenfeld 細(xì)化算法， Zhang amp。在串行細(xì)化算法中，當(dāng) 前迭代的結(jié)果不僅取決于前一次的迭代迭代圖像，而且與當(dāng)前處理情況有關(guān)；而在并行方式中，當(dāng)前迭代僅僅是由前一次的迭代情況決定，串行細(xì)化算法的處理結(jié)果依賴(lài)于對(duì)像素處理的先后順序，因而像素點(diǎn)的消除或保留不可預(yù)測(cè)。 (7)快速性：算法簡(jiǎn)單，速度快。 (5)細(xì)化性：骨架紋線(xiàn)的寬度為 1 個(gè)像素，即單像素寬。 (3)拓?fù)湫裕翰灰鸺y線(xiàn)的逐步吞食，保持原圖像的基本結(jié)構(gòu)特性。一種好的細(xì)化算法應(yīng)該滿(mǎn)足下列條件 [14]： (1)收斂性：迭代必須是收斂的。 細(xì)化處理是指在指紋圖像二值化以后，在不影響紋線(xiàn)連通性的基礎(chǔ)上，刪除紋線(xiàn)的邊緣像素，直到紋線(xiàn)為單像素 寬為止。獲取一個(gè)圖像骨架的過(guò)程通常稱(chēng)為對(duì)圖像“細(xì)化”的過(guò)程。細(xì)化可以便我們得到絞線(xiàn)的單像素的骨架。這種修改是為了使圖像連續(xù)圓滑。此時(shí)背景為白，紋線(xiàn)為黑。再根據(jù)前面判斷的是否為背景即 Icc 值的來(lái)修正 Icc 值：灰度值為 128且 Icc 為 1 時(shí)（非背景指紋紋線(xiàn)時(shí)）， Icc 值為 0，像素值置為 0。所以最好選用局部閾值法作為二值化算法。一般的圖像處理中的二值化算法主要是計(jì)算整幅圖像的灰度平均值，然后將該值作為門(mén)限，高于該門(mén)限的像素點(diǎn)就置 1，反之置 0。根據(jù)是否將圖像分塊處理，又分全局閾值算法和局部閾值算法兩種，全局閾值算法是將整幅圖像以一個(gè)閾值處理，而局部閾值算法則把原圖分成若 干個(gè)子圖，在每個(gè)子圖中確定閩值，在進(jìn)行二值化，由于指紋圖像在不同區(qū)域的亮度和對(duì)比度是有差別的，因而全局閾值算法不適用。這樣不僅可以壓縮原指紋圖像的數(shù)據(jù)量，而且也方便后面的細(xì)節(jié)特征的提取。由于指紋圖像脊、谷相間，因此指紋圖像的處理常是將指紋圖像二值化。該方法快捷，損壞程度低，缺點(diǎn)是計(jì)算有一定的復(fù)雜度，要通過(guò) 2 次方差均值來(lái)處理。 (a) 指紋原始圖像 (b) 歸一化處理圖像 (c) 分割后圖像 圖 21 指紋 1 的處理結(jié)果 圖 a 指紋原始圖像 圖 b 歸一化處理圖像 圖 c 分割后圖像 圖 22 指紋 2 的處理結(jié)果 從圖中可以看到用方差均值法分割既適用于比較圓滑的指紋，又適用紋線(xiàn)變化很大的指紋圖像。 仿真中歸一化的參數(shù) 0AVE 取了 150， 0VAR 取了 100，分割的區(qū)域大小 M 取了 10。 仿真結(jié)果和結(jié)論 本實(shí)驗(yàn)基于 的 Pc 機(jī)， Window 7 操作系統(tǒng)， 的仿真軟件環(huán)境下。指紋圖像的歸一化公式如式 ()所示，當(dāng)大于平均值時(shí)為加。 在使用方差均值法之前還要使用歸一法將圖變?yōu)榈皖l圖。 設(shè)指紋圖像 I的大小為 H L， I(i,j)為像素點(diǎn) (i,j)的灰度， AVE和 VAR分別為原指紋圖像的均值和方差， AVE和 VAR可以通過(guò)公式 ()和 ()計(jì)算得到。具體步驟分以下三步： (1)將低頻圖分成 M M 大小的無(wú)重疊方塊，方塊的大小以一谷一脊為宜。在這部分將重點(diǎn)介紹均值法差法的計(jì)算方法和在仿真中的運(yùn)用?；谌值闹讣y識(shí)別仍處于實(shí)驗(yàn)室探索階段 ,應(yīng)用領(lǐng)域中尚不廣泛。 基于全局的圖像分割則是根據(jù)情況特別是某些特殊場(chǎng)合的利用，如殘缺指紋。這種方法最大的優(yōu)點(diǎn)是易實(shí)現(xiàn)，很 好體現(xiàn)出紋理，但缺點(diǎn)是對(duì)于變化太快的部分出錯(cuò)。 LinHong 等人開(kāi)發(fā)的基于最小均方估計(jì)算法，即公式法。圖像均值就是對(duì)每一個(gè)單位塊的灰度值取均值，方差則反映該塊中各點(diǎn)與均值的偏差性，方向 [10]這可以很好的反映紋理的變化趨勢(shì)。 代表塊特征的指紋圖像分割目前研究趨勢(shì)為多種塊基本特征如灰度均值、塊灰度方差 [9]、塊方向圖等綜合運(yùn)用和重新定義塊特征。此原理在匹配中也可以運(yùn)用。它是圖像分割中最基本的方法。但是小波變換的明顯缺點(diǎn)是它計(jì)算復(fù)雜，計(jì)算效果也指紋識(shí)別中若干關(guān)鍵問(wèn)題研究 6 取決于函數(shù)的選擇。 小波變換的特點(diǎn)是 壓縮比高，壓縮速度快，壓縮后能保持信號(hào)與圖象的特征不變，且在傳遞中可以抗干擾。對(duì)于任意函數(shù) ? ? ? ?RL2?tf 的連續(xù)小波變換 [7]：公式（ 1）為變換公式，公式（ 2）為重構(gòu)公式。小波變換和傅里葉變換的出發(fā)點(diǎn)都是將信號(hào)表示成基函數(shù)的線(xiàn)性組合。因此根據(jù)以上的的灰度值領(lǐng)域關(guān)系，紋線(xiàn)的扭曲程度，指紋圖像分割大致分為三類(lèi)：基于像素的圖像分割，基于塊特征的圖像分割以及基于全局的圖像分割。特征集合則是幾種的結(jié)合。指紋分割的最基本的依據(jù)是圖像某些特征和特征集合。 第六章：總結(jié)本文所取得的一些研究成果，并對(duì)課題發(fā)展進(jìn)行了展望。 第四章：主要介紹了指紋圖像細(xì)化后的特征提取，需要哪些特征，去除哪些偽特征，以方便和正確地進(jìn)行匹配工作。 第二章：為后續(xù)的研究工作奠定基礎(chǔ)，本章介紹了均值方差的基礎(chǔ)知識(shí)和基本理論以及仿真中具體的分割運(yùn)用算法。其中分割部分采用了方差均值的方法，細(xì)化選取了一種偽特征較少的模板，匹配時(shí)以分叉點(diǎn)和端點(diǎn)信息進(jìn)行匹配。實(shí)際應(yīng)用要求最好自動(dòng)指紋識(shí)別系統(tǒng)能對(duì)識(shí)別任務(wù)實(shí)時(shí)做出響應(yīng)，而讓指紋匹配算法同時(shí)達(dá)到高速度和高準(zhǔn)確率也是一個(gè)難題。要想設(shè)計(jì)一個(gè)對(duì)較多真正特征點(diǎn)缺失、較多偽特征點(diǎn)出現(xiàn)和較大形變均不敏感的指紋匹配算法，也是一件十分困難 的事。對(duì)于質(zhì)量很差的圖像，如果不經(jīng)過(guò)特殊的增強(qiáng)處理，是很難正確地進(jìn)行特征提取的。就現(xiàn)有文獻(xiàn)和產(chǎn)品來(lái)看，對(duì)低質(zhì)量的指紋圖像的處理效果還遠(yuǎn)不能令人滿(mǎn)意。指紋識(shí)別系統(tǒng)主要包括 4 部分：指 紋圖像采集，指紋圖像預(yù)處理，指紋特征提取和指紋特征匹配[5]。因此，指紋識(shí)別技術(shù)的應(yīng)用范圍極廣。 ④指紋與主體的不可分離性：即指紋不存在丟失、遺忘、被竊取的可能。正是這些無(wú)窮無(wú)盡的細(xì)節(jié)特征組合構(gòu)成了指紋的唯一性．事實(shí)上，甚至包括雙胞胎，世界上