一種基于粒子群優(yōu)化的Snake模型的指紋分割方法

汪慶

（合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，安徽 合肥 230009）

1 引言

指紋作為一個重要的人體生物特征已被廣泛用于社會個人信息安全保護(hù)等領(lǐng)域，對指紋圖像準(zhǔn)確的分割，獲取真實有效的指紋區(qū)域，能夠減少特征提取的處理時間、提高指紋識別的正確率，對于提高整個指紋系統(tǒng)的效率具有重要意義。

目前，許多學(xué)者對指紋圖像分割方法進(jìn)行了研究，通常采用指紋圖像塊特征進(jìn)行分割，已經(jīng)取得了不少成果，但各種算法往往也存在各自的不足之處。Snake模型①Kass M,Witkin A,Terzopoulous D.Snakes:Active Contour Models，International Journal of Computer Vision,1988,1(4):321-331.是由Kass等于1987年提出的一種基于能量最小化的輪廓檢測算法，該模型是以一組相對靠近圖像目標(biāo)的點作為初始輪廓，通過能量函數(shù)極小化，使得輪廓產(chǎn)生彈性形變，將輪廓形狀鎖定在目標(biāo)特征附近，達(dá)到分割的目的。

本文在對指紋圖像分割處理過程中，針對傳統(tǒng)Snake模型存在的一些不足，提出了一種改進(jìn)的Snake模型指紋分割方法。該方法解決了Snake模型初始輪廓點的自動確定問題，并通過粒子群優(yōu)化算法（PSO）改進(jìn)了指紋凹陷區(qū)域無法捕獲問題。

2 傳統(tǒng)Snake模型

傳統(tǒng)Snake模型首先根據(jù)經(jīng)驗將初始輪廓手工分布于靠近目標(biāo)圖像邊緣，然后根據(jù)圖像的連續(xù)性、平滑性和外力的共同作用定義一個能量函數(shù)，該能量使得邊緣向能量函數(shù)減少的區(qū)域移動，當(dāng)能量函數(shù)趨于穩(wěn)定時，形成最終的輪廓曲線。該模型的能量函數(shù)為：

其中，S 表示弧長，Eint（v）為內(nèi)部能量，防止曲線拉伸或者彎曲，α（s），β（s）分別為一階導(dǎo)數(shù)和二階導(dǎo)數(shù)的加權(quán)系數(shù)，其中一階導(dǎo)數(shù)項是曲線的斜率，用于控制曲線的連續(xù)性，二階導(dǎo)數(shù)項是曲線的曲率，用于控制曲線輪廓的彈性程度。Eext（v）為外部能量，用于引導(dǎo)曲線向圖像輪廓的邊緣移動為梯度算子，Gσ·I（x,y）表示圖像與特征密度為σ的Gaussan平滑濾波器卷積。

但是，傳統(tǒng)Snake模型也存在不足①李培華，張?zhí)镂模骸吨鲃虞喞€模型（蛇模型）綜述》，《軟件學(xué)報》2000年第6期，第751-757頁。：1.初始輪廓點位置需要相對地接近目標(biāo)，否則可能無法獲得正確的目標(biāo)圖像。這需要通過一定的方法盡可能將初始輪廓點放在目標(biāo)圖像附近。2.凹陷區(qū)域不能夠捕獲。不少學(xué)者對該模型進(jìn)行了研究，并取得了一定的成果。李濤等人②李濤，于明，蘭娜：《一種自動初始化輪廓的改進(jìn)蛇模型算法》，《河北工業(yè)大學(xué)學(xué)報》2006年第1期，第58-61頁。提出了一種利用重心發(fā)出射線來獲取初始輪廓點的方法。XU等人③Xu C,Prince J L.Snakes,Shapes,and Gradient Vector Flow，IEEE Transaction on Image Processing,1998,7(3)pp.359-369.提出了一種能夠檢測出凹陷區(qū)域的GVF Snake模型，該模型利用擴(kuò)散方程獲得圖像域梯度向量場作為新的外力。

針對Snake模型的這兩個缺點，本文做出了一些改進(jìn)：1.利用基于凸包算法的方法自動獲取模型初始輪廓；2.對改進(jìn)了的Snake模型，利用PSO算法解決指紋圖像凹陷區(qū)域不能收斂的問題。

3 改進(jìn)的Snake模型方法

3.1 初始輪廓確定

通常對Snake模型初始輪廓的確定是采用手工獲取，但是手工的方法無法實現(xiàn)圖像分割的自動處理。針對指紋圖像的特殊性，本文提出了一種基于凸包算法的初始輪廓獲取方法，該方法無需人工干預(yù)，能夠自動獲取初始化輪廓。初始點個數(shù)由初始點間隔step控制。

獲取初始輪廓算法如下：

Step1：利用canny算子獲取指紋紋路的邊界；

Step2：對Step1中獲取的邊界進(jìn)行凸包計算，獲取一組能使最小多邊形包含所有的點集；

Step3：對Step2中獲取的凸包點集進(jìn)行排序并均勻間隔取點，得到最終的初始輪廓。

3.2 Snake模型改進(jìn)

3.2.1 PSO算法

PSO算法④倪慶劍，邢漢承，張志政等：《粒子群優(yōu)化算法研究進(jìn)展》，《模式識別與人工智能》2007年第3期，第349-357頁。模擬鳥群飛行覓食的行為，通過鳥群中個體之間的協(xié)作使群體達(dá)到最優(yōu)，是一種群智能算法?；镜腜SO算法流程如下：

Step1：初始化粒子群位置xi和初始速度vi；

Step2：對每個粒子計算適應(yīng)度函數(shù)值ffit；

Step3：根據(jù)適應(yīng)度函數(shù)更新選出局部最優(yōu)值pbesti和全局最優(yōu)值gbesti；

Step4：由公式(2)更新粒子速度和公式(3)更新下一代粒子的速度和位置；

Step5：若滿足達(dá)到閾值跳轉(zhuǎn)或迭代次數(shù)最大值，跳轉(zhuǎn)step 6，否則跳轉(zhuǎn)step2；

Step6：算法結(jié)束，輸出結(jié)果。

粒子速度更新：

其中，ω 為慣性因子，c1，c2為學(xué)習(xí)因子，rand（）是0和1之間服從均勻分布的隨機(jī)數(shù)。

3.2.2 適應(yīng)度函數(shù)選取

對于PSO算法中的適應(yīng)度函數(shù)的選取，本文使用了優(yōu)化后的Snake模型：

為了進(jìn)行仿真實驗，需要將曲線S描述成一組控制點，能量最小化過程就是通過這組控制點迭代完成的。為了計算控制點pi（x,y）周圍的能量，將Snake模型積分形式離散化為差分形式：

//內(nèi)部能量控制輪廓的連續(xù)性和彈性

//外部能量控制曲線向指紋圖像邊緣移動

此外，外力方面添加一個面積力使得曲線更加接近區(qū)域真實指紋區(qū)域：

//搜索到凹陷區(qū)域位置時，Sarea越小，能量越趨于極小化。

最終的適應(yīng)度函數(shù)表達(dá)形式為：

3.2.3 基于粒子群優(yōu)化的Snake模型的分割算法

傳統(tǒng)Snake模型應(yīng)對指紋圖像進(jìn)行分割時，對含有凹陷區(qū)域的指紋不能很好地收斂。PSO算法是一種進(jìn)化學(xué)習(xí)算法。通過Snake模型能量構(gòu)造出的改進(jìn)的含有面積因素的適應(yīng)度函數(shù)ffit對粒子進(jìn)行約束，經(jīng)過不斷地迭代更新每個粒子的速度和位置，獲得粒子的全局最優(yōu)值，得到優(yōu)化的控制點。經(jīng)過對每個初始輪廓點進(jìn)行優(yōu)化后的PSO算法，獲得優(yōu)化后的極值輪廓點，最終完成對含有凹陷區(qū)域的指紋圖準(zhǔn)確分割。

算法流程：

Step1：初始化粒子群算法參數(shù)：慣性因子ω，加速因子c1、c2，最大迭代次數(shù)MaxIter，群體數(shù)目PopSize；

Step2：設(shè)定粒子搜索范圍邊界，防止溢出；

Step3：初始化粒子初始位置pi和初始速度vi；

Step4：根據(jù)公式（8）計算粒子適應(yīng)度值 ffit；

Step5：記錄粒子的局部最優(yōu)位置pbesti，記錄最佳適應(yīng)度值ffitbest；

Step6：根據(jù)粒子的pbesti，更新全局最優(yōu)位置gbesti；

Step7：更新粒子速度 vi、更新粒子位置 gbesti、更新粒子適應(yīng)度ffit；

Step8：若滿足迭代次數(shù)最大值，轉(zhuǎn)入Step9，否則跳轉(zhuǎn)Step 7；

Step9：若所有初始輪廓點運算完畢，轉(zhuǎn)入Step10，否則跳轉(zhuǎn)Step1；

Step10：獲得全部輪廓點的最優(yōu)值，完成指紋分割。

本文PSO算法參數(shù)選取：慣性因子ω＝0.8，加速因子c1=c2=2，最大迭代次數(shù)MaxIter=50，群體數(shù)目 PopSize＝20。

4 實驗結(jié)果分析

本文的實驗環(huán)境為：T2400 1.83GHz CPU 2G內(nèi)存；XP操作系統(tǒng)；使用Matlab7.0實現(xiàn)。

通過對指紋圖像進(jìn)行仿真實驗后，從圖1和圖2可以看出實驗對比結(jié)果。在每組圖中：（a）表示原始指紋圖像；（b）表示使用凸包算法后獲取的指紋輪廓線；（c）表示均勻化后初始輪廓點的分布；（d）表示傳統(tǒng)Snake模型方法分割的結(jié)果；（e）表示使用PSO優(yōu)化的Snake模型分割的結(jié)果。本文將Snake模型能量的參數(shù)賦值為： 圖 1：α＝0.05，β＝0.05，γ＝30，δ＝0.05，step=5；圖 2： α＝0.05，β＝0.05，γ＝50，δ＝0.05，step=10。

圖2 仿真實驗2對比結(jié)果圖

圖1-d和圖2-d是傳統(tǒng)Snake模型方法分割的結(jié)果，該算法不能準(zhǔn)確收斂于凹陷指紋邊界區(qū)域；圖1-e和圖2-e是使用PSO優(yōu)化后的Snake算法運行結(jié)果。從實驗結(jié)果可以看出，優(yōu)化后的Snake算法能夠準(zhǔn)確地收斂到指紋的凹陷邊界處，從而實現(xiàn)了對目標(biāo)的準(zhǔn)確分割。

結(jié)束語

本文針對傳統(tǒng)Snake模型在指紋圖像初始輪廓點的自動確定和凹陷區(qū)域的準(zhǔn)確收斂這兩個問題做出了一定的改進(jìn)。首先通過凸包算法解決了初始輪廓點自動提取問題，然后利用具有全局優(yōu)化能力的PSO算法改進(jìn)了凹陷區(qū)域收斂性。實驗結(jié)果表明，該算法能夠自動提取指紋圖像的初始輪廓，并且能夠準(zhǔn)確地收斂到指紋凹陷區(qū)域，完成指紋圖像的準(zhǔn)確分割。