【正文】 續(xù)的、平滑筆直的，而是經(jīng)常出現(xiàn)中斷、分叉或打折。 13 第二章 指紋識別算法 本章首先 介紹了傳統(tǒng)的基于細(xì)節(jié)點的指紋識別算法，以及基于結(jié)構(gòu)的指紋識別算法的基本原理，接著 介紹 本文 指紋識別的核心算法 —— 指紋特征提取與匹配算法，不僅對常規(guī)的點匹配的方法和本文的算法進(jìn)行介紹，并且對它們的性能進(jìn)行了比較；而第二部分則介紹了指紋奇異點提取算法的思想和實現(xiàn)的具體步驟。用 比來表達(dá)這個數(shù)。 此外拒登率 (Error Registration Rate， ERR)和識別速度也會影響到使用的方便性。 但成本很高，而且還處于實驗室階段。它通過感應(yīng)壓在設(shè)備上的脊和遠(yuǎn)離設(shè)備的谷溫度的不同就可以獲得指紋圖像。 6英寸的盒子里，在不久的將來更小的設(shè)備可能只有3179。 自動指 紋識別技術(shù)是一項綜合性的高新技術(shù)，是一個學(xué)科交叉性很強(qiáng)的 7 研究領(lǐng)域。 （ 2） 指紋分類技術(shù)有待突破。驗證其實是回答了這樣一個問題 :“他是他自稱的這個人嗎 ？ ”這是應(yīng)用系統(tǒng)中使用得較多的方法。 在產(chǎn)品應(yīng)用方面，歐美 國家已經(jīng)開始使用指紋識別 ATM，并在南美廣泛使用。 現(xiàn)代指紋識別起源于 16 世紀(jì)后期， 1684 年英國人 發(fā)表了指紋研究的第 一 篇論文，闡述了指紋的脊線、谷線、毛孔的結(jié)構(gòu)， 1809 年 開 始用指紋代替印章，邁出了指紋識別歷史上重要的一步， Henry Fauld 于 3 1880 年在美國 《 Nature》雜志 上 發(fā)表論文，指出指紋具有唯一性、不變形，并利用現(xiàn)場指紋來鑒定罪犯，從此揭開了現(xiàn)代指紋識別的序幕。而視網(wǎng)膜則難于采樣，也無標(biāo)準(zhǔn)的視網(wǎng)膜樣本庫可供系統(tǒng)軟件開發(fā)使用，這就導(dǎo)致了視網(wǎng)膜識別系統(tǒng)難以開發(fā)，可行性較低的問題 。 生物特征識別 (Biometrics)技術(shù)是指通過計算機(jī)利用人體所固有的生理特征或行為特征來進(jìn)行個人身份鑒別。另一方面，由于數(shù)字信號處理器 (DSP)的迅猛發(fā)展，已經(jīng)可以滿足圖像處理中的運(yùn)算量要求。s character. The algorithm39。從概率學(xué)的角度來講，在兩枚指紋 中 只要有 1213個特征點相吻合，即 可 被認(rèn)為是同 一 指紋。 曲禮》斷定 :“中國第一個提到用指紋鑒別個人的是唐代的作家賈公彥。各種相應(yīng)的產(chǎn)品也 己投放市場多年。多年來各個公司及其研究機(jī)構(gòu)產(chǎn)生 了眾多的指紋數(shù)字化算法，而所用的指紋識別算法最終都?xì)w結(jié)為在指紋圖像上提取和比對指紋特征。主要表現(xiàn)在： （ a） 對被采指紋的適應(yīng)性用戶 ID 指紋庫 用戶指紋 提取指紋特征 特征匹配 匹配結(jié)果 用戶指紋 提取指紋特征 逐一匹配 指紋庫 用戶 ID 6 差。 今后指紋識別技術(shù)研究發(fā)展的方向： （ a） 非接觸式真皮層指紋采集。潛在指印是手指在臺板上按完后留下的，這種潛在指印降低了指紋圖像的質(zhì)量。這是最常見的半導(dǎo)體指紋傳感器，它通過電子度量來捕捉指紋。 半導(dǎo)體傳感器 的缺點在于 ，其價格與硅晶片的面積相關(guān)，晶片面積越大，芯片價格越高。 這幾種方法各有優(yōu)缺點。指紋識別系統(tǒng)的工作速度主要由采集時間、圖像處理時間、比對時間和平均識別速度幾項指標(biāo)構(gòu)成。 本文所做工作及論文結(jié)構(gòu) 指紋識別技術(shù)作為一種新興的身份驗證技術(shù)，具有廣闊的應(yīng)用空間。核心點對于 SecureTouch 的指紋識別算法很重要，但沒有核心點的指紋它仍然能夠處理。 分叉點（ Bifurcation） —— 一條紋路在此分開成為兩條或更多的紋路。 Gabor 變換用于紋理分析主要是它具有可調(diào)節(jié)的方向和中心頻率，以及最優(yōu)化的空間和頻率分辨率。 但基于特征點的匹配算法還存在許多缺點。隨著理論研究的不斷深入和應(yīng)用領(lǐng)域的不斷擴(kuò)展，小波分析越來越顯示出它 的獨特魅力。 （ a）均勻分解 （ b）金字塔分解 （ c）小波分解 圖 28 三種子帶分解方式 小波變換應(yīng)用指紋圖像的特性 （ 1）小波變換系數(shù)的統(tǒng)計特性 圖像的離散小波變換通常運(yùn)用高通濾波器 L對圖像進(jìn)行水平和垂直方向的濾波，在小波頻域內(nèi)，低通子帶的系數(shù)稱為尺度系數(shù)，而其他子帶的系數(shù)則稱為小波系數(shù)。 (Γ (1/β )/ Γ (2/β )) (26) 在實際求解過程中，式（ 24）的解可以通過插值和對應(yīng)查表的方法來得到。α 1,β 1)。前一種方法只能提取出有限的幾個方向（比如 4， 8或 16），這種方法的弊病是存在量化誤碼率差，而用梯度算子來尋找連續(xù)方向的方法，可抑制量化誤差，因而本文采用的是這種方法。經(jīng)實驗驗證，使用 Sobel算子已經(jīng)可以滿足實際要求； （ 3）計算以 (i,j)為中心的每一塊的方向，如下： 26 2222( , ) 2 ( , ) ( , ) )WWijy x yWWu i v ji j u v u v???? ? ? ?? ? ??? （ 213） 22 2222( , ) ( , ) ( , ) )WWijx x yWWu i v ji j u v u v???? ? ? ?? ? ? ??? （ 214） ( , )1( , ) a r c ta n ( )2 ( , )yxijij ij?? ?? （ 215） 這里θ (i,j)是局部脊線方向的最小平方估計。( , )1( , ) a r c ta n ( )2 ( , )yxijij ij?? ?? （ 220） 這樣我們就得到了指紋圖像的方向場。 （ 1）區(qū)域方向會聚性測度 指紋的奇異點是指紋中各種方向的會聚點，雖然在某一個徑向上的方向 29 場比較接近，但不同徑向上的方向場就相差甚遠(yuǎn)。由此，我們提出用如下定義的方向會聚性測度函數(shù)來衡量方向會聚的程度： 這里 (i,j)是當(dāng)前考察的奇異點， D(i,j)為 (i,j)所在的方向子塊，令 βi (i=1,2...8)為 D(i,j)在其領(lǐng)域中沿 8 個主方向的發(fā)散角（如圖 213），在領(lǐng)域內(nèi)沿每一發(fā)散角徑向長度為 L，這里 L 值選為 3。這里作一簡單敘述，設(shè) O是方向場子，在給定點 (i,j)索引如下計算： 01( , ) ( )2 wkP o in a ca re i j k???? (221) ( ) ( ) / 2( ) ( ) ( ) / 2()d k d kk d k d kdk? ? ?? ? ? ??????? ? ? ? ????? 其 它 (222) 其中 ( ) ( ( ( 1 ) ) , ( ( 1 ) ) ) ( ( ) , ( ) )x y x yd k O i M O D i M O D O i j? ? ? ? ? ? ?? ? ? ? (223) 由 Poincare 值判斷，為 0176。 w 窗的傅立葉頻率的主方向。梯度的計算公式如下： arctan( )yx?? ?? (210) tan yx?? ?? (211) 指紋紋線方向與梯度方向的關(guān)系為 ：α＝θ π /2 (212) 25 其中 ， ,xy??分別是 x 方向和 y 方向上指紋灰度值的變化值。 如 果 DDth，兩個指紋不是同源指紋；否則，是同源指紋。 （ 3）基于廣義高斯概密度的相似度量方法 上述可知，若給定了廣義高斯概率模型，子帶小波系數(shù)的直方圖可以用α 和 β 來描述。因此，任一子帶的小波系數(shù)的均值都等于或近似等于 0。這是因為小波變換具有空間 —— 頻率的局部性、方向性、多分辨率性和帶寬在對數(shù)頻率軸上等寬的優(yōu)點，并與視覺特性接近，所以不僅可以利用統(tǒng)計特性，還可以利用視覺特性來提高編碼效率，并且用金字塔算法還可以實現(xiàn)圖像的正交、無冗余分解。而在預(yù)處理過程中，由于算法本 身所需的空間較大，加上很多中間結(jié)果需要保存，所以預(yù)處理過程所需空間很大。 基于結(jié)構(gòu)的指紋識別算法處理流程圖如圖 23所示 。 孤立點（ Dot or Island） —— 一條特別短的紋路，以至于成為一點。三角點提供了指紋紋路的計數(shù)跟蹤的開始之處。本文 的指紋傳感器模塊就 采用 DSP 來實現(xiàn)指紋識別。 F A R FR R E E R 圖 13 FAR 和 FRR 關(guān)系曲線圖 ROC 曲線 由于計算機(jī)處理指紋時，只是涉及了指紋的一些有限的信息，而且比對算法并不是精確匹配，其結(jié)果也不能保證 100%準(zhǔn)確。但是其有步驟繁多，抗干擾能力差，對指紋圖像質(zhì)量依賴性強(qiáng)，提取特征點可靠性差等缺點。小的接觸面積使每次捕捉的指紋圖像重疊區(qū)域變小，這樣導(dǎo)致輸入指紋與模板指紋間缺乏足夠的對應(yīng) 細(xì)節(jié)點，傳統(tǒng)的基于細(xì)節(jié)點的算法的性能就會下降。傳感器陣列的每一點是一個金屬電極，充當(dāng)電容器的一極，按在傳感面上的手指頭的對應(yīng)點則作為另一極，傳感面形成兩極之間的介電層。另外臺板上的涂層 (膜 )和 CCD 陣列隨著時間的推移會有損耗，精確度會降低 。通過非接觸方式采集指紋，則可以有效解決指紋錄入時的變形問題。畢竟清晰的指紋圖像是正確實現(xiàn)自動指紋識別的前提和保障。 自動指紋識別技術(shù)系統(tǒng)〔 AFIS〕 可以分為兩類，即驗證 （ 如圖 21） 和辨識 （ 如圖 22） 。從事指紋識別的研究機(jī)構(gòu)有 ： 北京大學(xué)信息中心，清華大學(xué)自動化系，北京郵電 人 學(xué)，中科院，長春光機(jī)所等。其實，賈公彥只不過是根據(jù)我國長期應(yīng)用指、掌紋的實踐經(jīng)驗對“質(zhì)劑”和“下千書”作了進(jìn)一步解釋而己 ，中國正式應(yīng)用指紋遠(yuǎn)早于此。 每個人的指紋是相當(dāng)固定的，很難發(fā)生變化。 small data memory needed by the algorithm (need to save 6 data, 24 byte. Be close to the capacity of `ID+password39。它是模式識別領(lǐng)域中使用最早，也是應(yīng)用最廣的生物鑒定技術(shù)。這些都給管理者和使用者帶來很大不方便。 便于獲取指紋樣 本 ，易于開發(fā)識別系統(tǒng)，實用性強(qiáng)。在唐代指、掌印己應(yīng)用于文書契約 上， 而至少到了宋代，手印己正式作為刑事訴訟的物證了。 單就指紋識別算法而言，國內(nèi)外的研究水平處于同步狀態(tài)。指紋 以一定的壓縮格式存貯，并與其姓名或其標(biāo)識 （ ID， PIN） 聯(lián)系起來。另外，指頭表面是一 個三維曲面，而獲取的指紋圖像卻是一個二維平面，這種從立體向平面的轉(zhuǎn)化也會造成指紋的變形。各種生物識別技術(shù)都具有自身的特點和優(yōu)勢?，F(xiàn)在傳感器可以裝在 6179。其表面的頂層是具有彈性的壓感介質(zhì)材料，它們依照指紋的外表地形（凹凸）轉(zhuǎn)化為相應(yīng)的電子信號，并進(jìn)一步產(chǎn)生具有灰度級的指紋圖像。但由于超聲波錄入設(shè)備的耐久性還難以估計，因此實際中應(yīng)用得較少。 性能評價 指紋算法中引入了兩個重要的數(shù)字指標(biāo)來描述該系統(tǒng)的精確度。我們可以根據(jù)不同的用途來調(diào)整這兩個值。第 三 章介紹了本設(shè)計所使用的硬件開發(fā)工具以及在 AVR 開發(fā)系統(tǒng)中實現(xiàn)指紋 系統(tǒng) 程序 設(shè)計 的過程。 模式區(qū) 核心點 三角點 紋數(shù) 圖 22 指紋總體特征 局部特征 局部特征是指指紋上的節(jié)點的特征，這些具有某種特征的節(jié)點稱為特征點。 指紋的特征提取與匹配算法 指紋其實是比較復(fù)雜的。 圖 23 基于結(jié)構(gòu)的指紋識別算法流程圖 基于特征點的特征提取與匹配算法 目前國內(nèi)外指紋識別的技術(shù)基本上都是采用基于細(xì)節(jié)特征點的指紋識別技術(shù)。因此限制了指紋技術(shù)的應(yīng)用。二維小波變換分為可分離和不可分離兩種方式。而小波系數(shù)在零仁附近高度集中，單為零的系數(shù)高達(dá) 77%，較好地去除了相關(guān)性，減小了熵 圖 29 指紋圖像 21 值。 , ) ) l o g ( 1 / ) ( 1 / )D p p?? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ?? ? ???????? ? ? ? (27) 從（ 27）式中，可以看出， KLD 距離函數(shù)含量有四個變量，兩個尺度參數(shù) α 1 和 α 2 及兩個形狀參數(shù) β 1 和 β 2。相當(dāng)于點匹配方法中一個特征點的存儲容量，從而極大減小存儲容量，使得指紋識別技術(shù)的廣泛應(yīng)用成為可能。 中值法就是將點方向圖分塊以后，將其中的所有方向用排序算法排序后，選出其中位于中間位置的方向，以此作為塊方向圖的方向。 （ 4）由于噪聲、斷裂的脊線和谷線的存在，估計的脊線方向 θ (i,j)可能不是總正確。 時，該點是核點； 具體算法主要步驟描述如下： 28 （ 1）將指紋圖像分為 5179。 （ 2） 指紋灰度方差 在指紋的前、背景的交界處以及前景模糊區(qū)，方向不規(guī)則，易產(chǎn)生偽奇異點。 時， (i,j)是核點；這樣得到相鄰的幾個候選奇異點。這里該平滑操作是基于塊水平而基于象素水平進(jìn)行的。 w 的方塊，對于本文中的指紋圖象， w選為 5； （ 2） 計算每一點 (i,j)的梯度 ( , ) ( , )xyi j