基于遺傳算法的指紋圖匹配算法及應用研究

史晶

摘 要：針對目前在公安和身份確認等領域得到廣泛應用的自動指紋識別，在簡單介紹其分類和指紋匹配要求的基礎上，結合指紋匹配基本原理與現有方法，提出一種以遺傳算法為基礎的新型匹配算法。目前，在高層次匹配當中引入這一方法，能以指紋細節點具有的特征為依據完成初匹配，取得了顯著成效，可將其作為日后研究和發展重點。

關鍵詞：自動指紋識別; 指紋圖匹配; 遺傳算法

中圖分類號：TP18? ? ? ? ? ? 文獻標識碼：A? ? ? ?文章編號：1006-3315（2019）9-200-001

由于自動指紋識別具有靈活、方便和精準等優勢，所以在身份確認等領域逐漸得到廣泛應用。而其能否發揮應有效果，有賴于指紋圖匹配，即需要借助高水平匹配算法來保證指紋匹配精度。

1.基本概述

自動指紋識別具有廣闊的應用與發展前景，不僅能用于公安領域，還能在計算機領域得到應用，比如作為確認用戶身份的手段和對網絡資源進行訪問的口令等。除此之外，它還能以嵌入式系統形式在銀行系統中使用，如用于信用卡身份確認等。

就目前來看，這項技術主要包含下列兩方面：其一，指紋分類;其二，指紋細節匹配。以指紋特征為依據，可將指紋分成以下五種：第一，尖拱類指紋;第二，拱類指紋;第三，左環類指紋;第四，右環類指紋;第五，漩渦類指紋。對指紋進行分類的目的在于便于指紋庫建立與管理，為后續指紋匹配創造良好條件。雖然很多人員針對指紋分類方面的問題做出大量研究，但從自動指紋識別角度講，怎樣縮小誤識率依然是難點所在[1]。

指紋的匹配主要用于判斷指紋是否屬于目標，它需要將指紋具有的特征作為基礎，這些特征包括：脊末梢;分岔點;符合特征;未定義。現在最常用特征為細節點對應的坐標模型，即利用分岔點和脊末梢來完成指紋的鑒定。為解決指紋匹配方面的問題，需要提出一種新型算法，比如根據指紋圖包含的結構信息予以初匹配，再以此為基礎，借助遺傳或補償算法進行與指紋圖之間的匹配。這一算法能有效抵抗非線性變形和噪聲，對指紋圖像沒有太高要求，所以能識別不完全的指紋。

2.指紋匹配

現有文獻中對指紋匹配提出很多算法，其中大部分是以點匹配算法為基礎的。對于點匹配算法，它是指采用某種變換措施對兩個點進行匹配[2]。

比如Ranade等提出的松弛算法，這一方法定義兩個點集，針對一組匹配，為點集定義相對變換。以該變換條件下其它點實際匹配程度為依據，對相對變換可靠度進行計算。若有一個變換能使點集科學匹配，如果這一變換和前一變換相近，則說明變換有較大可靠度，但其它變換較小。對可靠度進行重復計算的過程中，其它變換具有的可靠度會對正處于計算過程的可靠度造成加權影響。完成迭代后，能使匹配達到科學的變換，其可靠度將較大，其它變小。這一方法由于需要對可靠度進行反復計算，故速度相對較慢。

又比如Stockman提出以Hough為基礎的方式，將點模式通過匹配轉化為檢測Hough當中的峰值。該方法的缺點為：如果細節點的數量較少，則難以在空間內積累證據完成可靠匹配。除此之外，這一方法的計算量還很大。雖然有人從能量達到最小這一角度入手對點匹配問題進行描述，同時引入模擬退火方式，但是這一方法的實際計算量也很大。

在此之后，Rand等提出了更加細致的能對指紋特征進行分析的模型[3]。這一模型對10種指紋具有的特征進行了區分。以此為基礎，可通過格柵的疊加來完成特征識別。S-Sobajic等提出三種能對指紋進行匹配的方法，其中一種為借助光學儀器對指紋圖進行相關性計算，這一方法具有很快的速度，但成本較高，且不容易攜帶;另一種方法為PCA法，從圖像識別角度講也就是KL變換，這一方法的指紋識別成效相對較少，其主要原因為指紋圖具有的特征屬于松散定義，同時存在很多偽特征。此外還有一種方法為神經網絡算法，這一方法十分簡單，但在計算時需要付出很大的代價。

對算法而言，其本質在于改進后的算法，它能在利用現有結構信息的前提下，借助補償算法對偏移累積進行抵消，所以可以有效抵抗變形及噪聲。采用初匹配算法可以加快匹配速度。

3.以遺傳算法為基礎的匹配算法

對兩幅指紋圖進行匹配，能解決形變、旋轉與平穩方面的問題，將關鍵點對應的點集作為指紋匹配輸入，這兩個點集分別從輸入與標準指紋圖進行提取，然后共同存儲于模板庫當中[4]。

這兩個點集能對關鍵點坐標和方向進行記錄，若指紋圖能完全匹配，可對輸入指紋圖實施變換，以此獲得模板對應的指紋圖。基于此，其中一個點集能通過變換成為另一個點集。部分點會由于噪音而發生偏移，或被添加與刪除。如此一來，匹配指紋圖即變為找出變換，促使點集良好匹配。因無法知曉指紋圖是否屬于同一手指，故試圖找到能使更多點實現匹配的具體變換。若兩個點不僅之間的距離很近，并且方向還保持一致，則可認定這兩個點是相互匹配的。但需要注意，任何一個點集都可能存在不能采用變換的方式達到匹配的點。因指紋圖的大小基本相同，所以在實際的變換過程中沒有考慮伸縮因子，相應的，在匹配算法當中也沒有考慮伸縮因子。

4.結束語

綜上所述，對自動指紋識別及其應用而言，指紋圖匹配具有重要作用和意義，為滿足更復雜情況下指紋識別要求，需要不斷創新指紋圖匹配方式。通過綜合考慮，提出一種以遺傳算法為基礎的匹配算法，以此避免偏移的產生及其累積，并有效加快匹配的速度。

參考文獻：

[1]魏志平，謝進，席濤，曹書磊.雙穩態俘能器的控制及控制器功耗優化[J]傳感器與微系統，2019，38（04）：33-36

[2]趙婧，包偉華.基于分步遺傳算法的壓力變送器排產優化[J]應用技術學報，2019（01）：165-171

[3]蔣洋，張星臣，周曉曄.考慮支線運輸服務的多式聯運網絡優化[J]沈陽工業大學學報（社會科學版），2015（10）：25-26

[4]黃正鵬，王力，張仕學，余廷忠，張起榮.基于傳統遺傳和數據壓縮算法的冗余光纖數據存儲優化[J]激光雜志，2019，40（03）：135-139