【文章內(nèi)容簡(jiǎn)介】 系統(tǒng)采用 Sobel 梯度算子計(jì)算象素點(diǎn)在 x 和 y 方向上的梯度 Gx 和 Gy 。對(duì)所有非背靜區(qū)域的象素計(jì)算梯度，并保存在數(shù)組 Gx (i,j) 和 Gy (i,j) 里。 x? (i,j) = ),(),(22222vuGvuG yiiujjvx? ??????????? , (35) y? (i,j) = )),(),(( 222222 vuGvuGyiiujjvx ?? ??????????? , (36) )),( ),((ta n21),( 1 ji jiji xy??? ?? (37) 并不在開(kāi)始就計(jì)算出所有點(diǎn)或塊的方向估計(jì)，只有當(dāng)后續(xù)處理需要計(jì)算某個(gè)象素的方向信息時(shí)，才根據(jù)公式予以計(jì)算，從而省去了很多不必要的計(jì)算量。 特征抽取 指紋灰度圖象經(jīng)過(guò)增強(qiáng)處理，對(duì)于細(xì)化后的圖象，經(jīng)過(guò)一定的光滑處理后，進(jìn)一步去噪（如去除孤立點(diǎn)、毛刺、跨接短橋、小環(huán)等）后，就可以初步提取指紋細(xì)節(jié)點(diǎn)。假定 P為被檢測(cè)的黑點(diǎn)， N 為 P 的 8鄰域中黑像素的個(gè)數(shù)。如果N=1，則 P是末梢點(diǎn)；如果 N=3,則 P是分支點(diǎn)。由于干擾、噪聲的影響，提取出的細(xì)節(jié)點(diǎn)中包含相當(dāng)多的偽細(xì)節(jié)點(diǎn)，一般采用統(tǒng)計(jì)和結(jié)構(gòu)信息相結(jié)合的方法刪除 偽細(xì)節(jié)點(diǎn)。 信息的新穎算法，這里用到的算法是對(duì)上述算法的改進(jìn)，算法的基本思想是沿紋線方向自適應(yīng)地追蹤指紋脊線，在追蹤的過(guò)程中，局部增強(qiáng)指紋圖象，最后江南大學(xué)畢業(yè)設(shè)計(jì)論文 —— 基于指紋識(shí)別技術(shù)的學(xué)生身份認(rèn)證系統(tǒng) 第 12 頁(yè) 共 51 頁(yè) 得到一幅細(xì)化后的指紋脊線骨架圖和附加在其上的細(xì)節(jié)點(diǎn)信息。由于該算法只在占全圖比例很少的點(diǎn)上估算方向并濾波處理，計(jì)算量相對(duì)較少，所以在時(shí)間上明顯優(yōu)于傳統(tǒng)的方法。 ? 基于脊線跟蹤的細(xì)節(jié)提取算法 從數(shù)學(xué)上看，可以將指紋圖象視為一個(gè)定義在二維平面上的一個(gè)曲面，沿脊線方向，灰度、變換相對(duì)平緩， 沿垂直于脊線的法線方向，灰度呈現(xiàn)波峰波谷交替出現(xiàn)的分布，而在接近背景區(qū)域或脊線末梢處，沿脊線方向的灰度發(fā)生顯著變化。本算法的思想正是建立在上述假設(shè)的基礎(chǔ)上。 圖 33 脊線跟蹤算法示意圖 圖 34 細(xì)節(jié)點(diǎn)的判定 算法步驟 在處理階段得到了計(jì)算出方差并從大到小排序的圖象塊序列。選擇塊方差最大的塊中灰度值最大的點(diǎn)，以該點(diǎn) (it ,jt ) 為起始點(diǎn)執(zhí)行脊線跟蹤算法。主要步驟如下 ： 1． 首先，計(jì)算出該點(diǎn) (it ,jt ) 的方向估計(jì)值 ? ，得到以 (it ,jt ) 為中心的方向與 ? 正交的（即法線方向Φ）長(zhǎng)度為 2? +1 的點(diǎn)集Ω((i,j) ,Φ ,? ) 。 ? 是一個(gè)與脊線寬度相關(guān)的常數(shù)，通常取 35。 2． 然后對(duì)點(diǎn)集Ω做局部濾波增強(qiáng)處理。 (a)對(duì)Ω上每個(gè)點(diǎn) (Xi ,Yi ),i= 0..2? 得到點(diǎn)集Ω i =Ω ((Xi ,Yi ) ,θ ,h) ，計(jì)算Ω i 上的灰度均值，賦給 (Xi ,Yi ) ，得到一個(gè)相對(duì)光滑的點(diǎn)集Ω 39。 ；（通常取 h=1） (b)使用一個(gè)高斯低通濾波器 G與Ω 39。 做卷積運(yùn)算。 Ω 39。 39。 =Ω 39。 ? G (38) G(j) = r?21exp???????? ???????2rj (39) 3． 下一步是定位Ω上的最可能是脊線骨架上的點(diǎn)，以灰度值為依據(jù)找到江南大學(xué)畢業(yè)設(shè)計(jì)論文 —— 基于指紋識(shí)別技術(shù)的學(xué)生身份認(rèn)證系統(tǒng) 第 13 頁(yè) 共 51 頁(yè) 局部最大處（ Xmax ,Ymax ）和最小處（ Xmin ,Ymin ），認(rèn)為最大處是與脊線骨架接近的脊線點(diǎn)，也是 要找的點(diǎn)，最小處是離脊線邊緣最近的非脊線點(diǎn)，并計(jì)算兩處的灰度落差 d，以作為下一步自適應(yīng)跟蹤的判據(jù)。 4． 計(jì)算出（ Xmax ,Ymax ）處的方向估計(jì)值θ，已一定的步長(zhǎng) u，沿θ方向探測(cè)點(diǎn) (Xi ,Yi ) ,i = 0..n 直至 (X 1?n ,Y 1?n ) 落在背景區(qū)域或者與（ Xmax ,Ymax ）的灰度值之差大于某個(gè)與 d 相關(guān)的值。得到延伸的距離 step = n? u 。 u 一般取 1 或 2。 5． 對(duì) (Xn ,Yn ,step) 檢查終止條件，如果滿足終止條件，則結(jié)束了沿一個(gè)方向的脊線跟蹤，回到初始點(diǎn)，沿反方向繼續(xù)跟蹤，當(dāng)另一個(gè)方向的探測(cè)也結(jié)束后，得到了一條脊線，對(duì)脊線上的所有點(diǎn) (x,y) ，修改s[x,y]=m(m0,為脊線的序號(hào) ) 。定位到下一個(gè)起始點(diǎn)，回到步驟 1。從下一個(gè)塊中尋找灰度最值點(diǎn)，如果該點(diǎn)未被訪問(wèn)過(guò)，則以該點(diǎn)作為新的出發(fā)點(diǎn)。 6． 如果不滿足終止條件，則令（ X,Y） =( Xn ,Yn ) 為新的起始點(diǎn)，回到步驟 1。 終止條件和細(xì)節(jié)點(diǎn)的判定如下： i. sm(x,y) = +? 。 表示已經(jīng)接觸到了背景區(qū)域； ii. sm(x,y) = l m。 表示已經(jīng)接觸到了一條 已經(jīng)標(biāo)記過(guò)的脊線，探測(cè)到了分支點(diǎn)與脊線 l和 m相關(guān)聯(lián)； iii. step=0 或者小于某個(gè)很小的正整數(shù)；表示已經(jīng)探測(cè)到脊線 m 的一個(gè)方向的末梢點(diǎn)。 偽碼描述： int FollowRidge() { int m = 0。 //變量 M記錄已找到 foreach Block B { x,y = B 中最值點(diǎn) { if (sm(x,y) == 0) { θ = (x,y) 處的方向估計(jì)； Ω = GetSection(x,y,θ ,α )。 //得到領(lǐng) 域點(diǎn)集 Filter(Ω )。 //局部濾波增強(qiáng) 江南大學(xué)畢業(yè)設(shè)計(jì)論文 —— 基于指紋識(shí)別技術(shù)的學(xué)生身份認(rèn)證系統(tǒng) 第 14 頁(yè) 共 51 頁(yè) x,y,xd = GetLocalMax(Ω )。 //定位局部最大值 If (sm(x,y) == 0) { m++。 TrackRidge(x,y,d,m0。 //以 (x,y)為起點(diǎn)跟蹤 } } } } return m。 } void TracRidge(x,y,d,m) //以 (x,y)為起始 點(diǎn)執(zhí)行跟蹤算法 { θ = 處的方向估計(jì)； Trace(x,y,θ ,d,m)//沿當(dāng)前方向跟蹤 If (θ 0) θ =θ π 。 Elseθ =θ + π 。//得到反方向 Trace(x,y,θ ,d,m)。//沿反方向跟蹤 S[x,y] = m。 } int Trace(Xstart, Ystart, θ start,dstart) //沿θ start方向跟蹤 { end = false。 k = 0 。//變量 k記錄跟蹤步數(shù) xcurr = xstart 。 ycurr = ystart 。 θ curr = θ start 。 dcur =dstart 。 While(!end) { x[k] = xcurr。 。 y[k] = ycurr。 θ [k] =θ curr。 (xnext, ynext, θ next,step)= GetNextPoint(xcurr, ycurr, θ curr ,σ )。 //定位下一點(diǎn) Ω = GetSection(xnext, ynext, θ next, σ )。 //得到新的領(lǐng)域點(diǎn)集 Filter(Ω )。//局部濾波增強(qiáng) 處理 Xmax, Ymax, θ max,dmax = GetLocalMax(Ω ) //找到新的最值點(diǎn) end = check(x,y,step)。 江南大學(xué)畢業(yè)設(shè)計(jì)論文 —— 基于指紋識(shí)別技術(shù)的學(xué)生身份認(rèn)證系統(tǒng) 第 15 頁(yè) 共 51 頁(yè) //終止條件判斷 k++。 xcurr = xmax 。 ycurr = ymax 。 θ curr = θ max 。 dcur =dmax 。 } for ( I = 0 。 I k1 。 I ++) { Line((x[i],y[i],x[i+1],y[i+1]))。 Foreach point(x,y) on the line S[x,y] = m 。//更新 s[x,y] } return k。 } 當(dāng)算法終止時(shí)，通過(guò)記錄在中的數(shù)據(jù)，得到了一幅寬度為 1的脊線圖，并且在執(zhí)行脊線跟蹤的過(guò)程中得到了指紋細(xì)節(jié)點(diǎn)的位置，類型和相關(guān)的脊線信息。 下面的圖像是處理結(jié)果： 原圖 過(guò)程 結(jié)果 江南大學(xué)畢業(yè)設(shè)計(jì)論文 —— 基于指紋識(shí)別技術(shù)的學(xué)生身份認(rèn)證系統(tǒng) 第 16 頁(yè) 共 51 頁(yè) 比對(duì)算法 指紋比對(duì)需要解決的問(wèn)題是：給定二維平面中的兩個(gè)點(diǎn)集 P 與 Q，其中的點(diǎn)包含有位置信息與方向信息。假定二者之間存在某種全局的旋轉(zhuǎn)與平移變換，同時(shí)有噪聲與局部變形存在。比對(duì)的目標(biāo)是 找到 P 與 Q 中的共同點(diǎn)，并求出點(diǎn)與點(diǎn)的對(duì)應(yīng)關(guān)系。 指紋細(xì)節(jié)比對(duì)有樹(shù)狀結(jié)構(gòu)搜索的方法，近鄰關(guān)系的結(jié)構(gòu)化方法，無(wú)監(jiān)督神經(jīng)網(wǎng)絡(luò)的方法等。指紋細(xì)節(jié)比對(duì)的很多思想來(lái)自于一般點(diǎn)匹配問(wèn)題，本系統(tǒng)中采用的是遺傳算法求解指紋特征點(diǎn)匹配問(wèn)題。 指紋比對(duì)分為兩個(gè)步驟：首先利用遺傳算法搜索所有可能將兩幅指紋特征點(diǎn)集對(duì)齊的參數(shù)，然后再確定點(diǎn)的位置匹配關(guān)系。以下從遺傳算法的每一個(gè)環(huán)節(jié)詳細(xì)介紹對(duì)齊參數(shù)搜索算法。 搜索空間： 考慮到指紋點(diǎn)匹配的具體情況，兩幅指紋之間可能有平移、旋轉(zhuǎn)及局部變形存在，算法在處理時(shí)，將變形所帶來(lái)的誤差作為噪聲 處理，而遺傳算法搜索兩幅指紋在 x 方向的平移， y方向的平移及圍繞原點(diǎn)的旋轉(zhuǎn)角度。 適度函數(shù)： 假定某一個(gè)對(duì)應(yīng)的參數(shù)為 dx， dy，θ。將特征點(diǎn)集 P 做參數(shù)為θ的旋轉(zhuǎn)與平移變換，得到點(diǎn)集 P39。 。假如此參數(shù)恰是 P 與 Q 之間的變換參數(shù)，則對(duì)特征點(diǎn)集 Q中的每一點(diǎn)（除去 Q 中新增的點(diǎn)），在 P39。 中相應(yīng)位置上都應(yīng)有一個(gè)點(diǎn)與之對(duì)應(yīng)，并且這兩個(gè)點(diǎn)的特征方向也一致。據(jù)此，目標(biāo)函數(shù)如下設(shè)計(jì)：對(duì)點(diǎn)集 Q中每一點(diǎn) qi ，尋找 P39。 中與之相近的點(diǎn) pj ，假如 pj 與 qi 之間的距離為 ? d，特征方向之差為 ?? ，當(dāng)二者都在某一誤差范圍內(nèi)時(shí)，定義 pj 對(duì) qi 的支持度為 s(qi , pj )=1/(1+? d)+K/(1+ ?? )，式中 K為比例系數(shù)，用于調(diào)整距離與角度影響搜索方向的比重。考慮到可能有若干個(gè) pj 與 qi 相近，而 qi 只能與一個(gè)點(diǎn)對(duì)應(yīng)，于是取 qi 的匹 配度為 m(qi )=jmax(s(qi , pj )) 。值得注意的是，這種近似有可能得 江南大學(xué)畢業(yè)設(shè)計(jì)論文 —— 基于指紋識(shí)別技術(shù)的學(xué)生身份認(rèn)證系統(tǒng) 第 17 頁(yè) 共 51 頁(yè) P中有兩個(gè)相近的點(diǎn)對(duì)應(yīng)到 Q中同一個(gè)點(diǎn)。對(duì)應(yīng)點(diǎn)搜索算法步驟將會(huì)檢測(cè)出這一問(wèn)題并加以解決。取 Q 中所有點(diǎn)匹配適度之和作為控制遺傳算法的適度函數(shù)。 編碼方案： 本方法中，有 3 個(gè)參數(shù)同時(shí)需要優(yōu)化。遺傳算法的個(gè)體編碼采用多參數(shù)編碼。每一個(gè)體由 3 段 0/1 編碼組成。第一段是 dx 的編碼，第二段是 dy 的編碼，第三段則表示θ?？紤]到通常指紋匹配的可能參數(shù)范圍，設(shè)置每段代碼為 8位。對(duì)于參數(shù) dx 與 dy，碼值減去 127 得到參數(shù)值，故它們的搜索范圍均為 [127， 128]，精確到 1 象素。對(duì)于參數(shù)θ，碼值減去 127 后除以 4 得到參數(shù)值，故它的搜索范圍為 [， 32]，精確到 。為了克服普通二進(jìn)編碼的 Hamming 懸崖缺陷，每一段參數(shù)采用 Gray 編碼。 遺傳操作： ? 遺傳種群的產(chǎn)生：分別隨機(jī)生成 dx， dy，θ，將它們轉(zhuǎn)換成 Gray 碼后串接在一起。種群大小取 50。 ? 選擇策略：采用期 望值方法。首先依據(jù)個(gè)體 x被選擇的期望值 nPs (x,t)（ n為需要選出的個(gè)體總數(shù)）的整數(shù)部分安排個(gè)體被選中的次數(shù)。期望值的小數(shù)部分重新由輪盤(pán)賭方法選擇。 Ps (x,t)=f(x,t)/?x txf ),(為每一個(gè)體被選擇的概率，式中 f(x,t)為個(gè)體 x在第 t代的適度值。 ? 交叉策略：采用修正的單點(diǎn)交叉策略。首先根據(jù)預(yù)先設(shè)定的交叉概率決定用于交叉的個(gè)體。每?jī)蓚€(gè)參與交叉的個(gè)體隨機(jī)選定一個(gè)交叉位置，兩個(gè)個(gè)體在該交叉點(diǎn)后的結(jié)構(gòu)進(jìn)行互換，并且生成兩個(gè)新個(gè)體。在修正中，所得的兩個(gè)新個(gè)體只有在適度值高于父輩時(shí)沒(méi)，才替換父輩進(jìn)入種群。這是由于在指紋點(diǎn)匹配問(wèn)題中，有非常多的參數(shù) dx， dy，θ組合將導(dǎo)致兩幅特征點(diǎn)集沒(méi)有特征點(diǎn)對(duì)應(yīng)。普通的后代直接替換父輩的交叉策略有較大可能破壞當(dāng)前的搜索結(jié)果，而使種群重新回到一個(gè)較差的水平。實(shí)驗(yàn)結(jié)果表明：修正的交叉策略在收斂速度、最優(yōu)解的適度值等方面優(yōu)于普通的交叉策略。 ? 變異策略：引入兩種變異操作： 1) 需要變異的個(gè)體以一定的概率