史駿鵬，吳一全,2

(1.南京航空航天大學 電子信息工程學院，江蘇 南京 211106； 2.南京理工大學 江蘇省社會安全圖像與視頻理解重點實驗室，江蘇 南京 210094)

?

基于混沌蜂群優(yōu)化的指紋匹配算法

史駿鵬1，吳一全1,2

(1.南京航空航天大學 電子信息工程學院，江蘇 南京 211106； 2.南京理工大學 江蘇省社會安全圖像與視頻理解重點實驗室，江蘇 南京 210094)

為了進一步加快指紋匹配算法的運算速度、提高識別效率，提出了一種基于混沌蜂群優(yōu)化和可變界限盒的指紋匹配算法。首先，結合人工蜂群優(yōu)化算法收斂速度快、控制參數(shù)少、能夠避免局部最優(yōu)等優(yōu)點以及混沌策略的類隨機性、高遍歷性等特點，在指紋點匹配中引入混沌蜂群優(yōu)化算法，并設計兼顧了匹配精度和運算時間的適應度函數(shù)；然后利用適應度函數(shù)估計出指紋特征匹配的幾何變換參數(shù)并進行指紋點特征的粗匹配；最后，利用可變界限盒進行精匹配，避免指紋圖像局部形變帶來的影響。大量實驗結果表明，與基于局部特征的指紋匹配算法、基于遺傳算法優(yōu)化的指紋匹配算法相比，本文提出的算法所需運算時間更短，匹配精度更高。

指紋識別；特征點匹配；群智能優(yōu)化；人工蜂群；混沌策略；可變界限盒；適應度函數(shù)；極坐標

指紋作為人體的基本特征之一，具有唯一性、終身不變性的特點，已被廣泛用于個體身份的驗證和識別。指紋圖像的特征匹配作為指紋識別系統(tǒng)的關鍵環(huán)節(jié)之一，直接影響識別的速度和精度。如何保證指紋特征匹配算法的實時性和識別率，一直是國內(nèi)外學者關注的問題之一。

目前主流的指紋匹配算法可以分為整體匹配[1-3]和特征點匹配[4-12]兩大類。其中特征點匹配通過對指紋特征點進行某些幾何變換(平移、旋轉、縮放)，使待匹配的指紋特征點和模板指紋特征點一一對應，從而達到指紋識別的目的。指紋采集過程中無法避免的噪聲和非線性形變干擾，對最終的指紋匹配結果影響很大。文獻[1-3]使用全局特征進行整體匹配，但容易受到指紋脊部結構形變和噪聲帶來的影響。文獻[4]通過獲取相鄰細節(jié)特征點的角度差和距離差，構建特征向量進行局部匹配，提高了指紋匹配的精度，但未考慮到指紋圖像非線性形變所造成的干擾。界限盒準則限定了匹配點之間角度誤差和距離誤差的容許范圍，能夠在一定程度上克服非線性形變的干擾。文獻[5]結合半可變界限盒對指紋特征點進行二次匹配，雖然提高了匹配的精度，但匹配時間波動較大。文獻[6]提出了一種基于細節(jié)點局部配準的指紋匹配算法，以特征點的紋理信息和結構信息為特征，進行全局匹配獲得指紋間的公共區(qū)域；然后將公共區(qū)域內(nèi)的細節(jié)特征點及其鄰近的參照點進行分組；最后根據(jù)界限盒約束條件，在極坐標系下進行指紋的匹配。文獻[7]建立局部特征點的三角模型，利用可變界限盒進行指紋特征點匹配，匹配結果精度較高。此外，許多學者還考慮將指紋特征點和其他特征信息相結合共同用于指紋匹配，也有利于提高匹配的精度。文獻[8]從原本篩選剔除出的非匹配特征點對中提取出被忽視的細節(jié)信息，結合未剔除的匹配特征點，一起用于指紋的匹配。指紋的采集區(qū)域和采集方向不同，往往導致指紋圖像中提取出的特征點相似度很低，影響匹配的結果。針對這一問題，文獻[9]提出了一種具有全局特性的“利手特征”用于指紋圖像匹配，一定程度上提高了匹配精度。文獻[10]利用局部特征點之間的距離、特征點類型等信息構建新的特征向量，用以實現(xiàn)指紋的全局匹配。文獻[11]提出了一種基于脊線特征的指紋模糊匹配算法，建立衡量相似程度的模糊集合，并利用加權平均法綜合評判脊線總體相似度，然后結合特征點相似度最終得出匹配結果。但是上述算法較為復雜，均需要較長的運算時間。

為了滿足指紋識別實時性的要求，人們開始考慮基于群體智能的優(yōu)化算法，并應用到指紋匹配中。遺傳算法、粒子群優(yōu)化算法等能對搜索策略實時調(diào)整，避免了繁瑣冗余的遍歷性匹配，有效地提升了指紋特征匹配的搜索效率。文獻[13]和[14]利用遺傳算法對指紋匹配算法進行優(yōu)化，匹配效率得到一定的提升。文獻[15]在指紋匹配中采用三角描述符作為初始種群，提高了遺傳算法的收斂速度。粒子群算法與遺傳算法類似，但不涉及遺傳算法的交叉和變異，而是粒子在解空間中搜索最優(yōu)位置，易于實現(xiàn)。文獻[16]提出了一種基于Tent映射混沌粒子群的快速指紋特征匹配算法，在Tent映射和混沌粒子群優(yōu)化的基礎上快速尋找適合的參考點并進行精確匹配。然而粒子群算法的優(yōu)化性能會隨著問題維數(shù)的增加而不斷下降，與之相比，人工蜂群(artificial bee colony, ABC)算法控制參數(shù)較少，全局尋優(yōu)能力較強，能解決較為復雜的優(yōu)化問題，可望應用于指紋匹配中[17-20]。

本文提出了一種基于混沌蜂群優(yōu)化和可變界限盒的分層指紋匹配算法。首先，利用蜂群優(yōu)化算法收斂快、可避免局部最優(yōu)、控制參數(shù)少等優(yōu)點以及混沌策略的類隨機性、高遍歷性等特點，將混沌蜂群優(yōu)化算法引入指紋圖像的點模式匹配中，搜索兩幅指紋圖像之間可能存在的平移、旋轉等幾何變換參數(shù)；其中，混沌蜂群優(yōu)化的適應度函數(shù)將兼顧匹配精度和運行時間的；然后利用可變界限盒柔性匹配進行精匹配，避免指紋圖像局部形變和噪聲的干擾。在實驗結果與分析部分，將本文算法與基于局部特征的指紋匹配算法[10]、基于遺傳算法優(yōu)化的指紋匹配算法[14]進行了對比實驗。

1 基于混沌蜂群優(yōu)化的點匹配算法

指紋圖像在采集過程中，由于指紋本身的旋轉、平移以及形變等問題，導致采集到的指紋特征點和數(shù)據(jù)庫中的模板特征點存在差異。假設集合P是采集的待匹配指紋圖像特征點集，特征點的個數(shù)為M；集合Q是預先存儲在數(shù)據(jù)庫中的模板指紋圖像特征點集，特征點的個數(shù)為N。這兩個點集分別表示為

1.1 指紋細節(jié)特征匹配

假設指紋特征點集P和Q為匹配的指紋圖像，則可以通過一定的平移、旋轉、縮放等幾何處理，將特征點集P近似變換成特征點集Q。通過搜索這些幾何變換參數(shù)，使一組特征點經(jīng)幾何變換后與另一組特征點盡可能多的對應，達成一定的閾值條件，即可判斷這兩組指紋圖像是匹配的。特征點集的變換包括平移、旋轉和尺度變換，由于采集得到的指紋圖像大小基本一致，因此尺度變換往往可以忽略，只需通過平移旋轉矩陣HRT對特征點進行變換：

1.2 人工蜂群優(yōu)化及混沌策略

人工蜂群優(yōu)化算法由3個部分組成，即引領蜂、觀察蜂和偵查蜂(也稱雇傭蜂、跟隨蜂和偵查蜂)，其具體過程為：1)每只引領蜂都對應一個確定的食物源，并在其鄰域隨機搜索一個新的食物源，然后將食物源的信息進行反饋，送到觀察蜂處；2)比較反饋回的食物源收益度大小后，觀察蜂會選取一個食物源作為目標并在其附近重復進行搜索，不斷尋找更優(yōu)的食物源；3)當觀察蜂在搜索某個食物源時，若收益度基本不再發(fā)生變化，便放棄該食物源，轉化為偵查蜂重新開始搜索。不斷循環(huán)迭代這一過程直到搜索到最佳的食物源位置。需要注意的是，在迭代過程中, 蜂群對于食物源位置的搜索需要遵循一定的規(guī)則：引領蜂和食物源是一一對應的關系，其數(shù)目必須和食物源數(shù)目保持一致；觀察蜂的數(shù)目也需要和引領蜂的數(shù)目一一對應。

為了更好地避免蜂群陷入局部極值，在蜂群優(yōu)化算法中引入具有類隨機性和遍歷性等特點的混沌策略，對偵查蜂進行初始化，循環(huán)迭代跳出局部最優(yōu)解位置，最終遍歷搜尋出全局最優(yōu)解位置。混沌序列的公式為

式中：βk表示序列中的參數(shù)，βk+1表示下一個序列的參數(shù)。

1.3 適應度函數(shù)

指紋特征點受到很多因素的制約，除了指紋圖像采集時的噪聲干擾和非線性形變，指紋圖像的去噪、增強、細化等預處理也會對最終參與匹配的指紋特征點造成影響。即使是同一手指的兩幅指紋圖像，也不一定能獲得位置、方向及數(shù)目高度一致的兩組特征點集。因此設計一個合適的匹配適應度函數(shù)是很有必要的，它在諸多干擾下依舊能較為準確地判斷出指紋的匹配關系。

為了提升指紋匹配過程中的匹配速度和精度，本文算法引入了分層匹配的思想，將匹配過程分為粗匹配和精匹配2個部分。粗匹配通過全局仿射變換確定大致相符的匹配點對；精匹配則將匹配點對變換到極坐標系下，并根據(jù)可變限界盒準則設計匹配適應度函數(shù)，對其進行比較。

1)粗匹配。假定變換因子分別為Δx、Δy和Δθ，利用式(2)的平移旋轉變換矩陣將指紋特征點集P變換成特征點集T；計算T和Q中所有特征點的歐氏距離和特征點類型差，并將結果放在集合J中：

式中：aik為指紋特征點間的歐氏距離；δik為特征點類型是否一致的判斷指標。若δik為0，則兩個特征點類型一致；若不為0，則兩個特征點類型不一致，肯定不匹配。

2)精匹配。首先將特征點集P和Q轉換到極坐標系下，轉換公式為

相較于其他指紋匹配算法，本文算法無需預先計算出指紋中心點作為極坐標原點，而是挑選粗匹配特征點作為極坐標的原點。分別對P和Q進行極坐標變換，并根據(jù)極角遞增的方向進行排序，獲得新的特征點集，表示為

為了消除局部形變的影響，在此引入可變界限盒。界限盒限定了匹配點之間角度和距離誤差的容許范圍，而可變界限盒更具彈性。如圖1所示，可變界限盒的形狀大小根據(jù)特征點的極徑和極角動態(tài)可變，當匹配點距離原點越近，則界限盒的角度越大，半徑越小；反之，當匹配點距離原點越遠，則界限盒的角度越小，半徑越大。

圖1 可變界限盒

可以利用式(8)和式(9)獲得可變的極徑閾值Tr和極角閾值Te：

式中：r為匹配特征點的極徑，rsmall、rlarge和esmall、elarge分別是極徑閾值和極角閾值的最大值和最小值。υ和ε是預先設定的常數(shù)。

如果兩個指紋特征點滿足一定的匹配準則，則可以確定該特征點對滿足匹配要求，匹配準則為

式中Tη為設定的極坐標方向差閾值。

記錄滿足條件的精匹配特征點對數(shù)目ns，并利用式(11)計算相似度ssim：

由于粗匹配點的數(shù)目有很多，為了兼顧運行時間和匹配效率，從中選取歐氏距離最小的3對粗匹配點作為極坐標變換的原點，重復進行精匹配，并不斷更新數(shù)值最大的ssim。

2 算法實現(xiàn)步驟

3)在每個引領蜂的鄰域部分隨機搜索一個新的食物源，并按照步驟2)的方式得到一個新的收益度；同時與之前的收益度進行比較，選擇較優(yōu)的食物源位置。

4)觀察蜂根據(jù)食物源的優(yōu)劣，在一個引領蜂的鄰域部分隨機搜索一個新的食物源。利用步驟2)的方式，得到一個新的收益度，同時與之前的收益度進行比較，選擇較優(yōu)的食物源位置，并將引領蜂移動到該處。

5)如果在經(jīng)過3次循環(huán)后，某些引領蜂所對應的食物源的收益度仍沒有發(fā)生改善，則將混沌序列代替?zhèn)刹榉暹M行食物源位置的重置搜索，以跳出局部極值。

6)在一次循環(huán)結束后，記錄本次循環(huán)的最優(yōu)解，并且循環(huán)次數(shù)加1。

7)若循環(huán)次數(shù)達到最大值20后，停止迭代，選擇當前最優(yōu)解作為幾何變換參數(shù)，并獲得最后的匹配相似度；否則，轉到步驟3繼續(xù)進行搜索。

3 實驗結果與分析

為了進行比較和分析，同時給出了基于局部特征的指紋匹配算法、基于遺傳優(yōu)化的指紋匹配算法以及本文算法的fFRR值、fFAR值及匹配時間，列于表1。所有算法的運行環(huán)境為Intel(R) Core(TM) 2 Duo CPU 2.5GHz/4GB內(nèi)存、MATLAB2013。

從表1的實驗結果可以看出，本文基于混沌蜂群優(yōu)化和可變界限盒的分層指紋匹配算法匹配精度高、運行速度快，足以滿足實時性的要求。與文獻[10]算法相比，本文算法利用群體智能算法進行幾何變換參數(shù)的搜索，避免了大量無意義的重復性匹配，挑選出較為優(yōu)秀的特征點對參與匹配，并且采用相似度最高的3組粗匹配點對作為精匹配極坐標的原點，匹配精度更高；與文獻[14]算法相比，本文的混沌蜂群優(yōu)化算法避免了遺傳算法的選擇、交叉和變異等復雜操作，運算速度提高了約20%；同時，采用分層匹配的方式，除了進一步提高匹配的精度外，還利用了可變界限盒的自適應性，有效地避免了外界的非線性形變對匹配特征點的影響。

表1 指紋細節(jié)特征匹配的FRR值、FAR值及匹配時間

Table 1 FRR、FAR and matching time of fingerprint minutiae matching

匹配算法指紋圖庫fFRR/%fFAR/%匹配時間/ms文獻[10]算法DB15.661.3563DB25.171.4868DB35.851.6766DB45.741.5864文獻[14]算法DB13.980.2885DB23.050.6689DB35.250.8986DB44.971.2084本文算法DB13.500.0452DB22.610.2356DB34.560.5053DB43.920.4252

4 結束語

本文利用混沌蜂群算法優(yōu)化指紋細節(jié)特征匹配，將混沌引入蜂群優(yōu)化算法中，使人工蜂群優(yōu)化算法收斂快、避免局部最優(yōu)、控制參數(shù)少等優(yōu)點和混沌策略的類隨機性、高遍歷性的特點有機結合起來，用于幾何變換參數(shù)的搜索；并依據(jù)分層匹配的思想設計匹配適應度函數(shù)，引入可變界限盒柔性匹配，克服了指紋圖像非線性形變的影響。此外，本文算法無需預先找出指紋中心點位置，而是用匹配相似度最高的3對匹配點對作為精匹配的極坐標原點，迭代得出最高的匹配相似度，因此只需較少的特征點就能進行較為準確的匹配，降低了指紋特征提取的難度，易于實現(xiàn)。實驗結果表明，本文算法不僅運算速度快，滿足實時處理的要求，而且匹配精度更高，能更好地用于個人身份的識別。

[1]ITO K, NAKAJIMA H, KOBAYASHI K, et al. A fingerprint matching algorithm using phase-only correlation[J]. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2004, E87-A(3): 682-691.

[2]HE Yuliang, TIAN Jie, LI Liang, et al. Fingerprint matching based on global comprehensive similarity[J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 28(6): 850-862.

[3]LUMINI A, NANNI L. Two-class fingerprint matcher[J]. Pattern recognition, 2006, 39(4): 714-716.

[4]JIANG Xudong, YAU W Y. Fingerprint minutiae matching based on the local and global structures[C]//Proceedings of the 15th International Conference on Pattern Recognition. Barcelona, Spain, 2000, 2: 1038-1041.

[5]于明, 皮海龍, 王巖, 等. 基于k近鄰法和脊線追蹤的指紋匹配算法[J]. 吉林大學學報: 工學版, 2014, 44(6): 1806-1810. YU Ming, PI Hailong, WANG Yan, et al. Fingerprint matching algorithm based on k-nearest neighbor and ridge line tracking methods[J]. Journal of Jilin university: engineering and technology edition, 2014, 44(6): 1806-1810.

[6]曹國, 孫權森, 毛志紅, 等. 一種新的形變指紋匹配方法[J]. 中國圖象圖形學報, 2010, 15(4): 645-649. CAO Guo, SUN Quansen, MAO Zhihong, et al. A new algorithm for distorted fingerprint matching[J]. Journal of image and graphics, 2010, 15(4): 645-649.

[7]袁東鋒, 杜恒, 秦小鐵. 基于三角形局部特征點模型指紋匹配算法[J]. 重慶師范大學學報: 自然科學版, 2013, 30(2): 69-73. YUAN Dongfeng, DU Heng, QIN Xiaotie. Fingerprint matching algorithm based on local triangular feature point model[J]. Journal of Chongqing normal university: nature science, 2013, 30(2): 69-73.

[8]ZHANG Qing, YIN Yilong, YANG Gongping. Unmatched minutiae: useful information to boost fingerprint recognition[J]. Neurocomputing, 2016, 171: 1401-1413.

[9]CAO Kai, YANG Xin, CHEN Xinjian, et al. Minutia handedness: a novel global feature for minutiae-based fingerprint matching[J]. Pattern recognition letters, 2012, 33(10): 1411-1421.

[10]朱寧, 施榮華, 吳科樺. 一種新的點模式指紋匹配方法[J]. 計算機工程與應用, 2006, 42(5): 74-76. ZHU Ning, SHI Ronghua, WU Kehua. A new fingerprint matching method of minutiae[J]. Computer engineering and applications, 2006, 42(5): 74-76.

[11]魏鴻磊, 張文孝, 華順剛. 一種采用脊線特征的指紋模糊匹配方法[J]. 智能系統(tǒng)學報, 2012, 7(3): 235-240. WEI Honglei, ZHANG Wenxiao, HUA Shungang. A fuzzy fingerprint matching method based on ridge features[J]. CAAI transactions on intelligent systems, 2012,7(3):235-240.

[12]LIU Feng, ZHANG D. 3D fingerprint reconstruction system using feature correspondences and prior estimated finger model[J]. Pattern recognition, 2014, 47(1): 178-193.

[13]漆遠, 田捷, 鄧翔. 基于遺傳算法的指紋圖匹配算法及應用[J]. 軟件學報, 2000, 11(4): 488-493. QI Yuan, TIAN Jie, DENG Xiang. Genetic algorithm based fingerprint matching algorithm and its application in automated fingerprint recognition system[J]. Journal of software, 2000, 11(4): 488-493.

[14]SHENG W, HOWELLS G, FAIRHUST M C, et al. Consensus fingerprint matching with genetically optimised approach[J]. Pattern recognition, 2009, 42(7): 1399-1407.

[15]GHAZVINI M, SUFIKARIMI H, MOHAMMADI K. Fingerprint matching using genetic algorithm and triangle descriptors[C]//Proceedings of the 19th Iranian Conference on Electrical Engineering. Tehran, Iran, 2011: 1-6.

[16]吳一全, 張金礦. 基于Tent映射混沌粒子群的快速指紋特征匹配[J]. 信號處理, 2011, 27(2): 168-173. WU Yiquan, ZHANG Jinkuang. Fast fingerprint minutiae matching based on Tent map chaotic particle swarm optimization[J]. Sigal processing, 2011, 27(2): 168-173.

[17]KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied soft computing, 2008, 8(1): 687-697.

[18]KARABOGA D, OZTURK C. A novel clustering approach: Artificial bee colony (ABC) algorithm[J]. Applied soft computing, 2011, 11(1): 652-657.

[19]秦全德, 程適, 李麗, 等. 人工蜂群算法研究綜述[J]. 智能系統(tǒng)學報, 2014, 9(2): 127-135. QIN Quande, CHENG Shi, LI Li, et al. Artificial bee colony algorithm: a survey[J]. CAAI transactions on intelligent systems, 2014, 9(2): 127-135.

[20]吳一全, 王凱, 曹鵬祥. 蜂群優(yōu)化的二維非對稱Tsallis交叉熵圖像閾值選取[J]. 智能系統(tǒng)學報, 2015, 10(1): 103-112. WU Yiquan, WANG Kai, CAO Pengxiang. Two-dimensional asymmetric tsallis cross entropy image threshold selection using bee colony optimization[J]. CAAI transactions on intelligent systems, 2015, 10(1): 103-112.

史駿鵬,男，1990年生，碩士研究生，主要研究方向為圖像處理與視頻通信。發(fā)表學術論文3篇。

吳一全，男，1963年生，博士，教授，博士生導師，主要研究方向為圖像處理與分析、目標檢測與識別、智能信息處理。發(fā)表學術論文250余篇。

A fingerprint minutiae matching algorithm based on chaotic bee colony optimization

SHI Junpeng1, WU Yiquan1,2

(1. College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China; 2. Jiangsu Key Laboratory of Image and Video Understanding for Social Safety, Nanjing University of Science and Technology, Nanjing 210094, China)

In order to further improve the operational speed and the recognition efficiency of fingerprint matching algorithms, a fingerprint matching algorithm based on chaotic bee colony activity and a variable boundary box was proposed. Firstly, by combining the advantages of artificial bee colony optimization including fast convergence times, fewer control parameters, and the lack of local optima, with the features of a chaos strategy including its random-like property and ergodicity, the chaotic bee colony activity was introduced into point pattern matching for fingerprint images. A corresponding fitness function incorporating both matching accuracy and operational time was then designed. The corresponding fitness function was then used to estimate the geometric transformation parameters for fingerprint rough matching. Finally, a variable boundary box can be used for fine matching, because it avoids any influences relating to local deformation of the fingerprint images. A large number of experimental results show that, compared with two alternative fingerprint matching algorithms (based on local features and genetic algorithm optimization, respectively) the proposed algorithm has a shorter operational time and has higher matching accuracy.

fingerprint recognition; minutiae matching; swarm intelligence optimization; artificial bee colony; chaos strategy; variable boundary box; fitness function; polar coordinates

2016-01-28.

日期：2016-07-18.

國家自然科學基金項目(61573183)；江蘇省社會安全圖像與視頻理解重點實驗室(南京理工大學)開放基金項目(JSKL201302)；江蘇省高校優(yōu)勢學科建設工程項目(2012).

吳一全.E-mail:nuaaimage@163.com.

TP391.4

A

1673-4785(2016)05-0613-06

10.11992/tis.201601038

http://www.cnki.net/kcms/detail/23.1538.TP.20160718.1522.008.html

史駿鵬，吳一全.基于混沌蜂群優(yōu)化的指紋匹配算法[J]. 智能系統(tǒng)學報， 2016, 11(5): 613-618.

英文引用格式：SHI Junpeng, WU Yiquan. A fingerprint minutiae matching algorithm based on chaotic bee colony optimization[J]. CAAI transactions on intelligent systems, 2016,11(5): 613-618.