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

王群峰 徐迎暉

（廣東工業大學自動化學院）

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

王群峰 徐迎暉

（廣東工業大學自動化學院）

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

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

0 引言

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

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

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

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

1 改進的遺傳算法

1.1 傳統遺傳算法

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

1.2 改進遺傳算法

1.2.1 改進選擇算子

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

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

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

1.2.2 交叉和變異概率的改進

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

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

2 遺傳算法在指紋圖像分割中應用

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

圖1 遺傳算法在圖像分割中應用流程[3]

2.1 編碼和解碼

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

2.2 初始化種群及種群規模

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

2.3 適應度函數的確定

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

2.4 生殖參數選定

3 局部閾值分割算法

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

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

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

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

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

4 兩種算法結合

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

圖3 結合兩種算法的處理流程

5 實驗結果分析

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

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

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

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

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

[5] 曹道友,程家興.基于改進的選擇算子和交叉算子的遺傳算法[J].計算機技術與發展,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年生，碩士研究生，主要研究領域：圖像處理、模式識別。E-mail: 190554341@qq.com

廣東省工業高新技術領域科技計劃項目 (2013B010401028）

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