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

史駿鵬，吳一全,2

(1.南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 211106； 2.南京理工大學(xué) 江蘇省社會(huì)安全圖像與視頻理解重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210094)

?

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

史駿鵬1，吳一全1,2

(1.南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 211106； 2.南京理工大學(xué) 江蘇省社會(huì)安全圖像與視頻理解重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210094)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 適應(yīng)度函數(shù)

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

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

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

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

2)精匹配。首先將特征點(diǎn)集P和Q轉(zhuǎn)換到極坐標(biāo)系下，轉(zhuǎn)換公式為

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

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

圖1 可變界限盒

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

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

如果兩個(gè)指紋特征點(diǎn)滿足一定的匹配準(zhǔn)則，則可以確定該特征點(diǎn)對(duì)滿足匹配要求，匹配準(zhǔn)則為

式中Tη為設(shè)定的極坐標(biāo)方向差閾值。

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[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]. 吉林大學(xué)學(xué)報(bào): 工學(xué)版, 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]曹國(guó), 孫權(quán)森, 毛志紅, 等. 一種新的形變指紋匹配方法[J]. 中國(guó)圖象圖形學(xué)報(bào), 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]袁東鋒, 杜恒, 秦小鐵. 基于三角形局部特征點(diǎn)模型指紋匹配算法[J]. 重慶師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]朱寧, 施榮華, 吳科樺. 一種新的點(diǎn)模式指紋匹配方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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)學(xué)報(bào), 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]漆遠(yuǎn), 田捷, 鄧翔. 基于遺傳算法的指紋圖匹配算法及應(yīng)用[J]. 軟件學(xué)報(bào), 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]. 信號(hào)處理, 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)學(xué)報(bào), 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)化的二維非對(duì)稱Tsallis交叉熵圖像閾值選取[J]. 智能系統(tǒng)學(xué)報(bào), 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年生，碩士研究生，主要研究方向?yàn)閳D像處理與視頻通信。發(fā)表學(xué)術(shù)論文3篇。

吳一全，男，1963年生，博士，教授，博士生導(dǎo)師，主要研究方向?yàn)閳D像處理與分析、目標(biāo)檢測(cè)與識(shí)別、智能信息處理。發(fā)表學(xué)術(shù)論文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.

國(guó)家自然科學(xué)基金項(xiàng)目(61573183)；江蘇省社會(huì)安全圖像與視頻理解重點(diǎn)實(shí)驗(yàn)室(南京理工大學(xué))開(kāi)放基金項(xiàng)目(JSKL201302)；江蘇省高校優(yōu)勢(shì)學(xué)科建設(shè)工程項(xiàng)目(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)學(xué)報(bào)， 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.