結(jié)合改進遺傳算法與局部閾值法的指紋圖像分割*

王群峰 徐迎暉

（廣東工業(yè)大學自動化學院）

結(jié)合改進遺傳算法與局部閾值法的指紋圖像分割*

王群峰 徐迎暉

（廣東工業(yè)大學自動化學院）

在改進型遺傳算法和局部閾值法的圖像分割技術(shù)基礎(chǔ)上，提出一個相互融合的方法。與融合前的 2種算法相比，改善了由于圖像邊界分割不完全和局部模糊不清造成無法分割的問題。實驗結(jié)果表明：這種融合的方法比單獨使用1種方法分割效果更好。

改進型遺傳算法；局部閾值法；指紋圖像；圖像分割

0 引言

在自動指紋識別系統(tǒng)中，采集指紋后需對指紋圖像進行一系列的預(yù)處理。其中，圖像分割的好壞對后續(xù)處理影響很大。指紋圖像包括前景區(qū)和背景區(qū)。由于背景區(qū)存在大量噪聲，指紋圖像分割就是要將背景區(qū)域從指紋圖像中最大限度地分離出去，這樣既減少偽特征數(shù)量，提高特征提取的準確率，同時節(jié)省處理時間。

指紋圖像分割一般是根據(jù)一種或者多種圖像信息進行分割。采用的方法主要有灰度閾值、方向圖信息、紋線頻率、紋理框架結(jié)構(gòu)和信息熵等。其中，灰度閾值計算比較簡單，且利用閾值進行指紋圖像分割一直是眾多學者研究的熱點，并已提出很多閾值選取方法。如大津展之提出的最大類間方差法[1]，該方法是全閾值分割法，雖然其簡單快捷的性能優(yōu)于其他灰度直方圖法，但大多數(shù)圖像不可能只有一個波谷而使圖像明顯地分為2部分，故單獨使用該方法存在較大缺陷；Kapur等提出最佳熵閾值方法[2]，該方法應(yīng)用信息熵的知識，尋找使指紋圖像信息熵最大的閾值進行分割，其原理比較簡單，但指紋信息的概率密度函數(shù)的計算是個難點；還有早期的基于自動閾值選擇法和均勻化誤差閾值法，都是尋找最佳閾值進行圖像分割。以上幾種方法都是基于單一的全閾值進行指紋圖像分割，應(yīng)用在其他圖像處理時，具有反應(yīng)快、時間短等特點。但指紋識別系統(tǒng)要求指紋圖像分割的精度較高，單一的全閾值分割法無法滿足要求。

在指紋采集過程中，光照、汗液、按壓力度不均等都會對指紋圖像產(chǎn)生很大的影響。若采集到的指紋灰度不均，局部對比度低，閾值法很難達到最佳的分割效果，但利用局部閾值法進行指紋圖像分割，局部對比度低的問題會得到改善。局部閾值法分割主要依賴于子塊圖像的大小和領(lǐng)域像素的局部特性，故對指紋圖像的前景與背景對比度并不敏感。其缺點是當子塊圖像在指紋圖像邊緣時，會出現(xiàn)指紋圖像邊緣分割不完全現(xiàn)象。

選擇圖像分割算法時，需考慮既能減少分割過程時間，又能有效保留指紋信息，優(yōu)化指紋識別系統(tǒng)的處理性能，并且面對不同質(zhì)量的指紋分割具有良好的魯棒性。本文根據(jù)全閾值和局部閾值法的優(yōu)缺點，在對不同指紋圖像分析及分割算法研究的基礎(chǔ)上，提出了基于改進的遺傳算法和局部閾值法融合的指紋圖像分割法。

1 改進的遺傳算法

1.1 傳統(tǒng)遺傳算法

遺傳算法[3]是一種多目標、自適應(yīng)和具有強大搜索能力的處理工具。它具有并行搜索能力，應(yīng)用于圖像分割的最佳閾值求取，可大大縮短尋找最佳閾值的時間。傳統(tǒng)遺傳算法常根據(jù)個體的適應(yīng)度大小采用輪盤賭選擇策略[4]，其基本思想是根據(jù)染色體適應(yīng)度的比例確定個體的被選取概率或生存概率。這樣選擇算子雖然簡單，易于實現(xiàn)，但存在2個問題：1) 局部最優(yōu)解，在進化初期適應(yīng)度很高的個體被選擇的概率很大，進而繁殖出很多后代，這樣種群單一而無法繼續(xù)進化使搜索陷入局部最優(yōu)；2) 收斂性差，進化后期接近最優(yōu)解時，在最優(yōu)解附近來回擺動，收斂速度慢。因此，在遺傳算法的基礎(chǔ)上提出了改進遺傳算法。

1.2 改進遺傳算法

1.2.1 改進選擇算子

本文選擇算子的改進采用了逐次減少最大值的選擇法。為使種群具有多樣性將輪盤賭選擇改為直接選取最優(yōu)多個個體的方法。其基本思想是選擇計算個體適應(yīng)度后，進行排序后再選擇，同時若選定某個個體后，下次再計算適應(yīng)度時相應(yīng)地減少該個體比例的大小。重復(fù)此操作，直至產(chǎn)生種群大小為M ，這樣既保證種群的多樣性，又減小早熟的可能性。具體過程如下：

1) 選擇計算比例選擇算子，計算比例公式

這種選擇算子只與個體適應(yīng)度的次序有關(guān)，與適應(yīng)度大小沒有直接的聯(lián)系。顯然這種方法不僅能夠保證最優(yōu)個體被選中，而且選擇后的種群不會單一。

1.2.2 交叉和變異概率的改進

從式(2)、式(3)可以看出，當待交叉?zhèn)€體或待變異個體適應(yīng)度值等于最大適應(yīng)度值時，交叉和變異概率為零，這種狀況將導致局部解不發(fā)生變化或在附近來回擺動，此時優(yōu)良個體卻不一定是全局最優(yōu)的，這樣就出現(xiàn)了局部最優(yōu)解現(xiàn)象。

為防止交叉和變異概率出現(xiàn)為零現(xiàn)象，可使用式(4)、式(5)改進自適應(yīng)交叉和變異概率。動態(tài)確定交叉和變異概率，既可避免進化過程不收斂，又可以防止優(yōu)良的基因因為變異而被淘汰。改進后的遺傳算法，種群優(yōu)良個體可以從局部最優(yōu)解中擺脫出來，進而獲得全局最優(yōu)解。

2 遺傳算法在指紋圖像分割中應(yīng)用

在指紋圖像分割中，種群的個體是圖像的灰度值。運用遺傳算法解決指紋圖像分割問題時必須進行4個重要的步驟：1) 把指紋圖像灰度值編解碼成染色體；2) 調(diào)整初始種群規(guī)模及繁殖代數(shù)；3) 設(shè)計目標適應(yīng)度函數(shù)；4) 生殖參數(shù)的調(diào)整與確定。遺傳算法在圖像處理中應(yīng)用流程如圖1所示[3]。

圖1 遺傳算法在圖像分割中應(yīng)用流程[3]

2.1 編碼和解碼

因為指紋圖像的灰度值范圍為0～255，所以使用8位的二進制碼將各個染色體編碼，這樣每個染色體代表一個分割閾值，即00000000～11111111之間任何數(shù)值都代表一種可能的閾值。當進化趨向它們之間的任何值時，二進制所對應(yīng)值是最佳閾值。

2.2 初始化種群及種群規(guī)模

初始群體的規(guī)模會影響遺傳算法的執(zhí)行效率。種群規(guī)模太小時，意味著搜索空間小，搜索效率差，最大可能會早熟陷入局部最優(yōu)解；種群規(guī)模太大時，計算復(fù)雜性增加。本文設(shè)定每代種群的個數(shù)為25，最大繁殖代數(shù)為200，初始解是采用隨機函數(shù)產(chǎn)生25個0～255之間的隨機數(shù)。

2.3 適應(yīng)度函數(shù)的確定

利用適應(yīng)度函數(shù)評估解的優(yōu)劣，通常在編寫適應(yīng)度函數(shù)過程中，所得函數(shù)值越大，說明圖像的前景和背景的差別就越大，分割效果越好。本文采用 Otsu法提出的適應(yīng)度函數(shù)?，進行指紋圖像分割閾值的選取。

2.4 生殖參數(shù)選定

3 局部閾值分割算法

由于指紋掃描儀所處環(huán)境等原因，采集的指紋圖像會存在噪聲，例如明暗不均、區(qū)域?qū)Ρ榷炔淮蟮?。指紋原圖如圖2(a)所示。若只用一個固定的全局閾值對整幅圖像進行分割，即使閾值選取得非常合理，也不能兼顧圖像的各種情況。改進前遺傳算法處理的圖像如圖2(b)所示。本文通過改進型遺傳算法進行圖像分割，指紋圖像的邊界清晰，但是在原圖像中亮度較暗的區(qū)域，出現(xiàn)嚴重的模糊現(xiàn)象。改進型遺傳算法處理的圖像如圖2(c)所示。

基于上述現(xiàn)象，提出一種局部閾值分割算法對指紋圖像進行分割，具體步驟如下：

2) 計算每個子塊內(nèi)像素的梯度值。利用 Sobel算子計算出水平梯度和垂直梯度，并且求出梯度的幅值。如式(8)～式(10)所示。

5) 分割處理后，再用3×3鄰域平滑濾波器對所得指紋圖像進行平滑處理。

該分割法抗噪能力強，計算簡單，易于實現(xiàn)，但也有缺點。若子圖像在目標區(qū)域或背景區(qū)域，可以根據(jù)統(tǒng)計結(jié)果對其進行分割，效果良好；若子圖像恰好在邊界時，使用該方法將產(chǎn)生失真，此時局部閾值法可能會失效；若背景區(qū)域和前景區(qū)域灰度變化不明顯時，使用這種方法邊緣部分存在很大的噪聲。局部閾值法處理后的圖像如圖2(d)所示。

4 兩種算法結(jié)合

圖2 指紋原圖和4種算法處理后的圖像

圖3 結(jié)合兩種算法的處理流程

5 實驗結(jié)果分析

用Matlab R2010b編程實現(xiàn)本文算法。由圖2(b)和圖2(c)的仿真結(jié)果可看出，雖然后者效果較好，但不明顯，且出現(xiàn)粘連現(xiàn)象。其原因可能是原指紋圖像前景與背景對比度低。由圖2(c)和圖2(d)的仿真結(jié)果可知，利用局部閾值法可改善粘連現(xiàn)象，但引入了邊緣分割不完全現(xiàn)象。其原因是指紋圖像分塊時，部分小塊落在背景區(qū)。由圖2(c)～圖2(e)對比可知：結(jié)合改進型遺傳算法和局部閾值法的指紋圖像分割效果比單獨使用其中一種方法的效果要好。

[1] 李賢陽,黃嬋.一種結(jié)合改進Otsu法和改進遺傳算法的圖像分割方法[J].實驗室研究與探索,2012,31(12):57-61.

[2] 宋家慧.基于遺傳算法的最大熵閾值的圖像分割[J].電子工程師,2005,31(2):60-63.

[3] 雷英杰,張善文. Matlab遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學出版社,2004.10.

[4] 楊平,鄭金華.遺傳選擇算子的比較與研究[J].計算機工程與應(yīng)用,2007,43(15):59-62.

[5] 曹道友,程家興.基于改進的選擇算子和交叉算子的遺傳算法[J].計算機技術(shù)與發(fā)展,2010,20(2):44-47.

Segmentation of Fingerprint Images Using Improved Genetic Algorithm and Local Threshold Method

Wang Qunfeng Xu Yinghui
(Dept. of Automation, Guangdong University of Technology)

This paper puts forward an improved adaptive genetic algorithm, and then combined with the advantages of the improved genetic algorithm and local threshold value method of image segmentation technology, a fusion method is proposed. Compared with the two algorithms, the problems of boundary segmentation of incomplete and ambiguous are improved. The experimental results show that the method can obtain better segmentation than a single method of them.

Improved Genetic Algorithm; Local Threshold; Fingerprint Image; Image Segmentation

王群峰，男，1987年生，碩士研究生，主要研究領(lǐng)域：圖像處理、模式識別。E-mail: 190554341@qq.com

廣東省工業(yè)高新技術(shù)領(lǐng)域科技計劃項目 (2013B010401028）

徐迎暉，男，1977年生，博士，副教授，碩士研究生導師，主要研究領(lǐng)域：信息隱藏與保密通信、語音與圖像信息處理、電路/嵌入式/DSP系統(tǒng)應(yīng)用等。