基于改進螢火蟲算法的二維Otsu圖像分割法

周晨航, 田力威, 趙宏偉

(1. 沈陽大學 信息工程學院, 遼寧 沈陽　110044;

2. 遼寧省物聯(lián)網信息集成技術工程研究中心, 遼寧 沈陽　110044)

?

基于改進螢火蟲算法的二維Otsu圖像分割法

周晨航1, 田力威2, 趙宏偉2

(1. 沈陽大學 信息工程學院, 遼寧 沈陽110044;

2. 遼寧省物聯(lián)網信息集成技術工程研究中心, 遼寧 沈陽110044)

摘要:對二維最大類間方差(2-D Otsu)算法和螢火蟲算法研究現(xiàn)狀進行了調查研究.為了解決二維Otsu圖像閾值分割方法存在的計算復雜度高、實時性差等缺點,提出了一種將改進的螢火蟲算法與二維Otsu算法結合的圖像分割算法,即通過自適應慣性權重優(yōu)化的螢火蟲算法(IFA)搜尋圖像分割的最佳閾值.實驗結果表明,改進后的算法能夠很好的實現(xiàn)圖像分割的效果,有效地縮短了圖像分割的運行時間,可以運用于圖像分割的實時處理.

關鍵詞:最佳閾值; 二維Otsu; 慣性權重; 螢火蟲算法; 圖像分割

圖像分割是數(shù)字圖像處理技術中的一種重要方法,它簡化了圖像并且改變圖像的表現(xiàn)形式,從而使圖像更容易被理解和分析.圖像分割的精確度對后續(xù)任務的處理會起到直接的影響,因此對其進行研究具有重要的理論價值和實際意義[1-2]. 常用的圖像分割方法有:基于閾值的分割方法[3]、基于區(qū)域的分割方法[4]、基于邊緣的分割方法[5]以及基于特定理論的分割方法等.其中,基于閾值的分割方法簡單、有效、穩(wěn)定,是實際應用過程中常用的一種圖像分割技術.

在閾值分割技術當中,最大類間方差法[6-7](Otsu算法)是最常用的分割方法之一,但是一維Otsu算法沒有考慮到周圍像素點對中心像素點的影響,不能很好地處理圖像中的噪聲,因此,劉建莊[8]等人提出了二維Otsu算法,較一維Otsu算法在圖像分割效果上取得了很大的改善. 但仍存在耗時多、圖像分割精度低、圖像誤分割等問題.范九倫[9]等人在二維Otsu算法的基礎上提出了曲線閾值型Otsu算法, 吳一全[10]等人提出了一種新的二維直方圖區(qū)域斜分方法并進行閾值分割,雖然都改進了二維Otsu算法,但二者都需要在整個二維直方圖上計算每條閾值直線的概率和類間離散矩陣的跡,因此都會影響計算效率.

螢火蟲算法[11]是劍橋學者Xin-She Yang于2008年提出的一種較為新穎的生物進化算法,但是算法本身還是存在一些問題,例如收斂慢,易陷入局部最優(yōu)等.同時很多學者也已經著手研究螢火蟲算法在圖像分割領域的應用.Horng Ming-Huwi[12]等結合螢火蟲算法和最小交叉熵準則對圖像進行多閾值分割,但是改進后的算法仍然存在計算復雜度高的問題.吳鵬[13]等提出了一種螢火蟲算法優(yōu)化最大熵的圖像分割方法,但是該算法只考慮到圖像的灰度概率信息,忽略了灰度值這一重要因素,所以結果都不盡理想.

為了更好地解決二維Otsu算法和螢火蟲算法在圖像分割優(yōu)化中存在的復雜度高、實時性差等問題,本文提出了一種基于螢火蟲算法改進的二維Otsu圖像閾值分割方法.基本思想是將求解二維Otsu的目標函數(shù)問題轉化為用螢火蟲算法求解最優(yōu)解問題,得出圖像的最佳分割閾值,然后分割圖像.實驗結果表明,本文提出的算法分割效果理想、程序運行時間短.

1二維Otsu閾值分割方法

設有一幅灰度級為L的圖像f(x,y),鄰域平滑圖像g(x,y)的灰度級也為L,g(x,y)中像素的灰度值為3×3鄰域內的灰度均值.對于圖像中的任意一個像素就可以由像素灰度值i和鄰域平均灰度值j構成的二維單元來表示.假設,M為圖像的總像素個數(shù),fij為像素的灰度值為i而且鄰域的平均灰度值為j的像素點的個數(shù),那么二維單元(i,j)出現(xiàn)的概率為

(1)

任意給定一個閾值向量(s,t),將二維直方圖分割成如圖1中所示的A,B,C,D四個區(qū)域.其中,區(qū)域B和C表示圖像中的目標類和背景類,區(qū)域A和D則對應與圖像中的邊緣點和噪聲.分別用C1和C0來表示二維直方圖中的目標類和背景類,其出現(xiàn)的概率分別表示為

(2)

(3)

圖1　二維直方圖

目標類C1和背景類C0對應的均值矢量μ1和μ0表示為

(4)

(5)

綜合的灰度均值矢量μt可表示為

(6)

圖像中邊緣點或噪聲的概率在多數(shù)情況下可以忽略.因此:

(7)

類間離散度矩陣表示為

(8)

背景類和目標類的距離測度函數(shù)可以用離散度矩陣的跡來表示:

(9)

當距離測度函數(shù)rtr(S)取得最大值時的閾值向量(s,t)即為最佳閾值.

在圖像分割過程中,閾值的選取是最關鍵的環(huán)節(jié),對于傳統(tǒng)的二維Otsu閾值分割方法來說,在實時處理過程中效果不理想,因此本文引入了螢火蟲算法來改進圖像分割閾值的尋優(yōu)過程.

2螢火蟲算法

2.1基本螢火蟲算法

螢火蟲算法(Firefly Algorithm,FA)作為一種生物進化算法,其原理是利用螢火蟲的發(fā)光特性,在指定區(qū)域內搜索其他個體并向亮度較大的個體靠近,從而實現(xiàn)其位置的尋優(yōu)[14].螢火蟲的個體信息主要是位置、亮度和吸引度,而導致螢火蟲個體之間相互吸引移動的因素是亮度和吸引度.

從數(shù)學角度對螢火蟲算法的描述如下:

螢火蟲的相對熒光亮度I定義為

(10)

式中:I0代表螢火蟲的最大螢光亮度值;γ為光強吸收系數(shù);Rj為螢火蟲i與j之間的空間距離.

螢火蟲的吸引度β定義為

(11)

式中:β0表示螢火蟲的最大吸引度,β0∈[0,1];γ、Rj意義同上.

螢火蟲i在被吸引向螢火蟲j移動的位置更新公式如下:

(12)

Xi(t)、Xj(t)為螢火蟲i和j在第t次迭代時的位置向量;α為步長因子,且α∈[0,1];rand∈U(0,1)為隨機因子.式中,Xi(t)為螢火蟲當前時刻位置對下一時刻位置的影響,它能夠有效地起到平衡全局和局部搜索的作用;β0e-γ Rj(Xj(t)-Xi(t))反映了群體中螢火蟲個體之間由于相互吸引而引起的位置變化;α(rand-1/2)是為了避免螢火蟲算法的搜索結果陷入局部最優(yōu)而設置的隨機步長項.

2.2基于自適應慣性權重優(yōu)化的螢火蟲算法

考慮到在傳統(tǒng)螢火蟲算法迭代后期算法已基本收斂到全局或者局部極值點附近,由式(11)可知,螢火蟲之間的吸引力與相互之間的距離成反比作用,螢火蟲算法的局部搜索能力下降甚至會在極值點附近震蕩.雖然在螢火蟲算法過程當中已經加入了隨機項來防止震蕩現(xiàn)象的發(fā)生,但是可能需要多次迭代之后算法才能擺脫極值點的束縛,因此在迭代次數(shù)有限時可能就無法找到全局最優(yōu)值.為了解決上述問題,本文引入慣性權重來優(yōu)化螢火蟲算法,簡稱IFA算法,優(yōu)化后的螢火蟲算法如下:

(13)

ω即為本文引入的慣性權重(ω∈[0,1]),它決定本次迭代過程中螢火蟲所處的位置受上次迭代結果影響的大小,慣性權重的計算公式如下:

(14)

式中:k為螢火蟲更新位置的次數(shù);f(Xi(k))為第i個螢火蟲第k次更新位置時對應的目標函數(shù)值;f(Xbest(k))為第k次更新位置時最優(yōu)螢火蟲所對應的目標函數(shù)值,λ(k)的值反映出了慣性權重變化的平滑度,當其值變化較大時說明平滑度較差,反之亦然.由式(14)可知λ(k)的值會隨著目標函數(shù)值的變化而改變,從而避免了權重的盲目選擇,使得螢火蟲算法的搜索方向更加合理.

為了平滑權重的變化,采用下式計算權重.

(15)

當算法的搜索結果接近極值點,λ(k)的變化速度明顯減小,由式(15)可知ω(k)的值也越小,從而增強了算法的局部搜索能力,防止算法陷入極值點震蕩的問題.反之,當算法搜索結果偏離極值點時,λ(k)變化加快,ω(k)越大,能夠更快的收斂到極值點.

優(yōu)化后的螢火蟲算法(IFA)在保持螢火蟲算法特性的基礎上又加快了算法收斂速度,提高了算法精度,因此本文引入了IFA算法對二維Otsu閾值分割方法進行優(yōu)化和求解.

3基于IFA算法的二維Otsu圖像閾值分割方法

3.1IFA算法和二維Otsu圖像閾值分割方法的結合

提出了一種基于IFA算法的二維Otsu圖像閾值分割方法,通過引入改進的螢火蟲算法對二維Otsu算法進行改進,將二維Otsu閾值分割方法的閾值(s,t)的選取問題轉化為螢火蟲算法對二維Otsu算法的距離測度函數(shù)式(9)的尋優(yōu)問題.

(16)

為全局最優(yōu)值.

將二維Otsu算法的距離測度函數(shù)rt r(S)設為螢火蟲算法的目標函數(shù),當rt r(S)取最大時的閾值(s,t),即為所求的圖像最佳分割閾值.在對螢火蟲算法進行計算之前設定如下三個前提條件:①螢火蟲不分雌雄,發(fā)光弱者被發(fā)光強者吸引而移動.②每個螢火蟲的吸引度β和發(fā)光強度I成正比.③距離測度函數(shù)rt r(S)的值對應于螢火蟲的熒光亮度I.

3.2基于IFA算法的閾值流程圖和尋優(yōu)步驟

基于IFA算法的二維Otsu圖像閾值分割方法流程圖如圖2所示.

圖2　基于IFA算法的二維Otsu圖像閾值分割方法流程圖

具體步驟如下:

(1) 在搜索范圍內隨機放置螢火蟲的個數(shù)m,設定每個螢火蟲的最大吸引度為β0,傳播介質的光強吸收系數(shù)為γ,隨機步長因子的大小為α,最大迭代次數(shù)為T,隨機初始化各螢火蟲的位置.

(2) 計算螢火蟲的熒光亮度.運用二維Otsu算法的距離測度函數(shù)rt r(S)計算目標函數(shù)值,并作為相應個體的最大螢光亮度值I0結合到改進的螢火蟲算法中.

(3) 更新螢火蟲i的位置.螢火蟲i在被熒光亮度更高的螢火蟲j吸引后的位置更新變化公式如式(12)所示.

(4) 通過距離測度函數(shù)rt r(S)計算位置更新后的螢火蟲亮度值I0,并對熒光亮度最強的個體進行局部范圍搜索,當目標值得到改善時則更新最優(yōu)解,否則維持原來的最優(yōu)解.

(5) 當達到最大迭代次數(shù)T時,記錄此時的最優(yōu)解Hbest,否則,重復步驟(3)～步驟(5)進入下一次搜索.最優(yōu)解所對應的閾值(s,t)即為全局最優(yōu)的圖像分割閾值.

4實驗結果及分析

本文采用了MATLAB 7.12.0(R2011a)編程環(huán)境,在硬件配置為Pentium(R) Dual-Core CPU 3.00 GHz,2 G內存的計算機上完成了仿真.

實驗1測試IFA算法尋優(yōu)性能.采用如下兩個函數(shù),全部取二維.

函數(shù)F1的全局極小值在0附近,fmin=0,初始范圍(-4,4),n=2;函數(shù)F2的全局極小值在1附近,fmin=0,初始范圍(-2.048,2.048),n=2.設FA和IFA的種群規(guī)模為80,迭代次數(shù)為50,光強系數(shù)γ=1,初始吸引度β0=1,隨機移動步長因子α=0.2.IFA中的權重系數(shù)動態(tài)獲取.

函數(shù)的收斂曲線圖如圖3、圖4所示.

從圖3、圖4中可看出,兩種算法在優(yōu)化初期,種群分布均表現(xiàn)出了明顯的隨機特性;迭代后期兩種算法均能收斂至極值點,尋優(yōu)成功,但改進后的自適應慣性權重螢火蟲算法(IFA)優(yōu)化函數(shù)時收斂速度更快,具有更好的有效性和快速性.

實驗2使用傳統(tǒng)的二維Otsu方法和IFA算法改進后的二維Otsu方法對預處理后的圖像進行分割比較.實驗參數(shù):光強系數(shù)γ=1,初始吸引度β0=1,步長因子α=0.5,螢火蟲個數(shù)m=50,最大迭代次數(shù)T=50.仿真結果如圖5～圖7.

圖3　優(yōu)化函數(shù)F1的收斂曲線圖

圖4　優(yōu)化函數(shù)F2的收斂曲線圖

圖5　迎客松原始圖及分割結果

實驗結果圖像依次分別為原始圖片,傳統(tǒng)的二維Otsu方法分割結果 ,改進后的二維Otsu方法分割結果,圖像的二維直方圖.

傳統(tǒng)的二維Otsu方法和改進后的二維Otsu方法的運行時間和分割閾值比較如表1所示.

不同參數(shù)設置對分割結果和速度的影響的實驗,針對Rice圖,對比的參數(shù)變動,其他參數(shù)按照實驗默認值.

圖6　Lenna原始圖及分割結果

圖7　Rice原始圖及分割結果

表1　傳統(tǒng)的二維Otsu方法和改進后的二維Otsu方法的運行時間及分割閾值對比

表2　種群規(guī)模對算法性能的影響

表3　步長因子α、光強度系數(shù)γ對算法性能的影響

從表2、表3可見, 實驗參數(shù)對結果有一定的影響,綜合各種因素, 本文選取的實驗參數(shù)較優(yōu). 從圖5～圖7可以看出, 基于IFA改進后的二維Otsu方法的分割結果與傳統(tǒng)的二維Otsu方法的分割結果差別不大, 且都能較好地選取閾值, 使目標與背景分割準確, 有效地減少圖像誤分割區(qū)域. 同時, 從表1可以看出,改進后的算法能夠有效地縮短圖像分割的運行時間,很好地改善傳統(tǒng)二維Otsu方法的不足.

5總結

本文提出的基于IFA改進的二維Otsu圖像閾值分割方法,在繼承螢火蟲算法的參數(shù)設置少,操作簡單,穩(wěn)定性好,尋優(yōu)效果好等優(yōu)點的基礎上優(yōu)化了螢火蟲算法,然后對二維Otsu算法進行了改進.實驗證明,基于IFA改進后的二維Otsu算法在保證分割效果的基礎上改善了算法運算速度,具有很好的應用前景.

參考文獻:

[1] SEZGIN M, SANKUR B. Survey over image threshold techniques and quantitative performance evaluation[J]. Journal of Electronic Imaging, 2004,13(1):146-168.

[2] 韓思奇,王蕾. 圖像分割的閾值法綜述[J]. 系統(tǒng)工程與電子技術, 2002,24(6):91-94,102.

(HAN S Q, WANG L. A Survey of thresholding methods for image segmentation[J]. Systems Engineering and Electronics, 2002, 24(6):91-94,102.)

[3] 劉雅坤,于雙元,羅四維. 基于最小最大割算法的閾值分割算法[J]. 計算機科學, 2014,41(1):95-99.

(LIU Y K, YU S Y, LUO S W. Threshold image segmentation based on min-max cut algorithm[J]. Computer Science, 2014,41(1):95-99.)

[4] 方晶晶,李振波,姜宇. 人體膚色區(qū)域的自適應模型分割方法[J]. 計算機輔助設計與圖形學學報, 2013,25(2):229-234.

(FANG J J, LI Z B, JIANG Y. Human skin color region segmentation based on adaptive model[J]. Journal of Computer-Aided Design & Computer Graphics, 2013,25(2):229-234.)

[5] 向方,王宏福. 圖像邊緣分割算法的優(yōu)化研究與仿真[J]. 計算機仿真, 2011,28(8):280-283.

(XIANG F, WANG H F. The optimization of image edge segmentation algorithm research and simulation[J]. Computer Simulation, 2011,28(8):280-283.)

[6] OTSU N. A threshold selection method from gray-level histograms[J]. IEEE Transactions on Systems, Man, and Cybernetic, 1979,9(1):62-66.

[7] 范立南,胡向麗,孫申申. 基于OTSU算法和帶通濾波器的毛玻璃型肺結節(jié)檢測[J]. 沈陽大學學報(自然科學版), 2012,24(6):43-46.

(FAN L N, HU X L, SUN S S. Detection of ground glass opacity nodule based on Otsu algorithm and band-pass filter[J]. Journal of Shenyang University (Natural Science), 2012,24(6):43-46.)

[8] 劉健莊,栗文青. 灰度圖像的二維Otsu自動閾值分割方法[J]. 自動化學報, 1993,19(1):101-105.

(LIU J Z, LI W Q. The automatic threshold of gray-level pictures via two-dimensional Otsu method[J]. Acta Automatica Sinica, 1993,19(1):101-105.)

[9] 范九倫,趙鳳. 灰度圖像的二維Otsu曲線閾值分割法[J]. 電子學報, 2007,35(4):751-755.

(FAN J L, ZHAO F. Two-dimensional Otsu’s curve thresholding segmentation method for gray-level images[J]. Acta Electronica Sinica, 2007,35(4):751-755.)

[10] 吳一全,潘喆,吳文怡. 二維直方圖區(qū)域斜分閾值分割及快速遞推算法[J]. 通信學報, 2008,29(4):77-83,89.

(WU Y Q, PAN Z, WU W Y. Image thresholding based on two-dimensional histogram oblique segmentation and its fast recurring algorithm[J]. Journal on Communications, 2008,29(4):77-83,89.)

[11] COELHO L, MARIANI V C. Improved firefly algorithm approach applied to chiller loading for energy conservation[J]. Energy and Buildings, 2013,59(2):273-278.

[12] HORNG M H, LIOU R J. Multilevel minimum cross entropy threshold selection based on the firefly algorithm[J]. Expert Systems with Applications, 2011,38(12):14805-14811.

[13] 吳鵬. 螢火蟲算法優(yōu)化最大熵的圖像分割方法[J]. 計算機工程與應用, 2014(12):115-119.

(WU P. Image segmentation method based on firefly algorithm and maximum entropy method[J]. Computer Engineering and Applications, 2014(12):115-119.)

[14] YANG X S. Firefly algorithm for multimodal optimization[C]∥Stochastic Algorithms: Foundations and Applications, SAGA 2009, Lecture Notes in Computer Sciences, 2009,5792:169-178.

【責任編輯: 李艷】

Image Thresholding Segmentation with 2-D Otsu Based on Improved Firefly Algorithm

ZhouChenhang1,TianLiwei2,ZhaoHongwei2

(1. College of Information Engineering, Shenyang University, Shenyang 110044, China; 2. Liaoning Information Integration Technology Engineering Research Center of Internet of Things, Shenyang 110044, China)

Abstract:The research status of 2-D Otsu algorithm and the firefly algorithm is investigated. In order to solve the problems in 2-D image thresholding segmentation such as high computation cost, bad real time capability, etc, a novel image segmentation algorithm is proposed, that combing improved firefly algorithm with 2-D Otsu. The algorithm takes advantage of firefly algorithm that optimized by adaptive inertia weight (IFA)to search the optimal threshold of image segmentation. Experimental results show that the improved algorithm can achieve good segmentation performance, which may not only shorten the run time, but also be applied to the real-time processing of image segmentation.

Key words:optimal threshold; 2-D Otsu; inertia weight; firefly algorithm; image segmentation

中圖分類號:TP 391.4

文獻標志碼:A

文章編號:2095-5456(2016)01-0045-06

作者簡介:周晨航(1990-),男,安徽黃山人,沈陽大學碩士研究生; 田力威(1973-),男,遼寧沈陽人,沈陽大學教授,博士后研究人員.

基金項目:科學技術部國際科技合作與交流專項基金資助項目(2011DFA91810-5); 遼寧省自然科學基金資助項目(2013020011); 教育部新世紀優(yōu)秀人才支持計劃資助項目(NCET-12-1012).

收稿日期:2015-06-26