基于改進的FA優(yōu)化二維Otsu圖像分割算法?

吳俊輝，汪烈軍，秦繼偉

(新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆烏魯木齊830046)

0 引言

圖像分割是圖像處理等方向的一個基本研究點，也是一個難點．重要的方法有閾值法、邊界檢測法、區(qū)域法等[1]．其中閾值法因其易于理解、效果較好，快速被學(xué)者們廣泛認可，成為最常用的方法之一．

現(xiàn)有被廣泛使用的閾值法有：類間方差法、最大熵法、交叉熵法、最小誤差法、模糊熵法等[2]．1979年由大津[3]提出的1-Otsu，以其簡單的閾值計算、迅捷的分割速度、較好的提取效果得到廣泛應(yīng)用．然而，圖像中存在噪聲等干擾時，該算法就可能達不到預(yù)期效果，甚至出現(xiàn)誤分、錯分．劉建莊等[4]提出了一種2-Otsu，通過引入鄰域均值來提高算法的抗噪性能，然而計算復(fù)雜度卻呈指數(shù)型增長，妨礙實時性應(yīng)用．對此，吳成茂等[5]提出了一種有效的算法，通過求二元連續(xù)函數(shù)極值使算法速率得到提升．景曉軍等[6]提出了一種實用性較強的算法，利用信噪比和對比度較低圖像的二維直方圖面積計算，實現(xiàn)快速迭代，節(jié)約存儲空間，減少分割時間．汪海洋等[7]提出了一種自適應(yīng)閾值選取算法，通過查表法進行快速計算，從而降低時間開銷．這些算法的研究對象是二維直方圖上所有點，因此依舊存在計算量較高、程序代碼量較多，無法滿足實時性需求的問題．

Yang Xin-She[8,9]于2008年提出基于群體搜索的隨機優(yōu)化算法FA，概念簡單明了、尋優(yōu)精度較高、設(shè)置參數(shù)較少，在諸多鄰域得到應(yīng)用．劉長平等[10]用FA解決NP難題中的一種組合優(yōu)化問題，劉鵬等[11]用FA實現(xiàn)群體動態(tài)自動聚集，使動畫效果更加逼真．

鑒于此，為了保證分割效果、滿足實時性需求、提高運算效率，本文提出FA-2-Otsu．該算法采用FA搜索，結(jié)合自適應(yīng)步長的更新策略，將2-Otsu的類間方差作為目標(biāo)函數(shù)，全面、快速的搜尋最佳閾值，進行圖像分割．通過實驗可得，F(xiàn)A-2-Otsu抗噪性能略強，提取效果良好，運算時間較少，較好的解決了上述問題．

1 二維Otsu算法

設(shè)圖像大小為R×C，灰度級為L，任一位置(r，c)處灰度值為f(r，c)，鄰域平均灰度值為g(r,c)，由f(r,c)的取值范圍為0≤f(r,c)≤L?1，可得g(r,c)的取值范圍為0≤g(r,c)≤L?1[6]．以f(r,c)和g(r,c)構(gòu)建坐標(biāo)系，定義(f(r,c)，g(r,c))所構(gòu)成長度為L-1的正方形區(qū)域為該圖像的二維直方圖[4]．在直方圖中任一點(i,j)處的值為Pij，則f(r,c)=i且g(r,c)=j的出現(xiàn)次數(shù)為K時

其中0≤i,j≤L?1,且

根據(jù)上述定義，任一向量(r,c)可以把直方圖大約分成兩大類：一類為背景X，另一類為目標(biāo)X1，而對于圖像中數(shù)量較少的邊界點和噪聲點，因其Pij值較小、幾乎可以忽略不計，故而一般默認為0．

選取分割閾值為(r,c)，X0、X1類的先驗概率分別為w0，w1則

此時X0、X1兩類各自均值分別為u0，u1則

在前文中假設(shè)數(shù)量較少邊界點和噪聲點的Pij為0，顯然易得w0+w1≈1，則圖像的總體灰度均值uz的表達式為：

定義X0、X1兩類之間的方差為:

設(shè)A=V為X0、X1兩類離散測度矩陣，2-Otsu把A的跡tr(A)作為距離測度函數(shù)，則

其中w0,w1,u0i,u0j,u1i,u1j,uzi,uzj如上所述．設(shè)輸入向量為(r0,c0)時tr(A)最大，則(r0,c0)為2-Otsu分割的最佳閾值．上述傳統(tǒng)2-Otsu采用窮舉法進行搜索，計算復(fù)雜度較高，耗費時間較長，因此本文引入改進的FA對其進行優(yōu)化．

2 螢火蟲算法

2.1 標(biāo)準(zhǔn)螢火蟲算法

FA是對生物界螢火蟲種群的熒光特性假設(shè)、簡化、構(gòu)建而成．螢火蟲的絕對亮度值定義為位置xi=（xi1，xi2，···，xid）（xid維向量）處的待優(yōu)化目標(biāo)函數(shù)值I0．

任兩只螢火蟲i、j，定義螢火蟲i對j的相對亮度為：

式中I0為螢火蟲的絕對亮度值；γ為光吸收系數(shù)，可設(shè)為一個常數(shù)；rij為螢火蟲i、j之間的距離，用以下公式計算：

相對亮度越大吸引力越大，則可定義螢火蟲i對j吸引力βij(rij)為

式中β0為光源處的吸引力，可設(shè)為一個常數(shù)；γ、rij的意義同上．

綜上所述，假設(shè)由于被吸引螢火蟲j向i移動，則其位置更新公式如下：

上式中，t為算法的迭代次數(shù)；Xi(t)為螢火蟲i的空間位置；Xj(t)為螢火蟲j的空間位置；βij(rij)為螢火蟲i對j的吸引力；α為常數(shù)，取值范圍為0≤α≤1；εj為隨機數(shù)向量．

2.2 基于改進的FA優(yōu)化的二維Otsu算法

標(biāo)準(zhǔn)FA中步長因子α的值是不變的，在搜尋最優(yōu)解的過程中存在易陷入局部最小值和收斂速率較慢的問題．因此，本文引入步長調(diào)整函數(shù)改進原有固定步長因子，快速、高效的搜尋到全局最優(yōu)值．步長調(diào)整函數(shù)需滿足如下條件：算法搜尋初始步長較大，以便于擴大尋優(yōu)區(qū)域，獲得全局最佳值；算法搜尋中后期步長較小，以避免算法出現(xiàn)振蕩等發(fā)散問題．

本文采用由指數(shù)與反比例復(fù)合而成步長調(diào)整函數(shù)，其公式如下：

式中α為步長因子；α0為常數(shù)，表示步長因子的初始值；k為常數(shù)且0＜k＜1，k的大小影響α的變化速率，可根據(jù)需要選取合適的值；t為迭代次數(shù)，取值范圍為0＜t＜MG．

本文提出一種FA-2-Otsu，使2-Otsu中搜尋最佳閾值等價于FA中尋找最大亮度值．其中FA的目標(biāo)函數(shù)即為2-Otsu的距離測度函數(shù)，因此尋找距離測度函數(shù)取最大值的位置也就是搜尋FA中具有最大亮度螢火蟲的位置，此位置也就是最佳分割閾值．FA-2-Otsu的偽代碼如下：

讀入待分割的圖像，定義目標(biāo)函數(shù)f(x)；

設(shè)定設(shè)定最大迭代次數(shù)MG；

設(shè)定算法的參數(shù)α0，β0，γ，N，k；

初始化N只螢火蟲的位置xi（i=1,2,...,N）；

由螢火蟲的位置xi及目標(biāo)函數(shù)計算每個螢火蟲的絕對亮度I0；

while(t

根據(jù)找到的最優(yōu)解進行圖像分割．

算法流程如圖1.

圖1 算法流程圖

3 實驗結(jié)果與分析

本文采用MATLAB(R2016b）編程環(huán)境，在硬件配置Intel(R)Core(TM)i3-4150 CPU@3.50GHz，8G內(nèi)存的計算機上完成了實驗仿真．實驗的參數(shù)設(shè)置如下：螢火蟲的數(shù)量N=20、算法最大迭代次數(shù)MG=30、初始步長因子α0=0.5，k=0.0001、最大吸引力β0=0.2、光吸收系數(shù)γ=1；添加強度為0.1的高斯和椒鹽噪聲．分別對Lena和boat的源圖像及加噪圖像用1-Otsu、2-Otsu和FA-2-Otsu進行分割，實驗結(jié)果如圖2、圖3、圖4、圖5所示．

圖2 Lena圖的源圖像分割結(jié)果

圖3 boat圖的源圖像分割結(jié)果

圖4 Lena圖加噪聲的分割結(jié)果

圖5 boat圖加噪聲的分割結(jié)果

3.1 主觀分析

對圖2、圖3、圖4、圖5從主觀上看有如下結(jié)論：

（1）對Lena圖來說，F(xiàn)A-2-Otsu比1-Otsu和2-Otsu在嘴巴、臉部特征及帽子等處有更多的細節(jié)和更加清晰的分割效果．

（2）對boat圖來說，這是一幅低對比度的圖像，F(xiàn)A-2-Otsu分割結(jié)果的背景較為干凈，2-Otsu比1-Otsu分割效果好．

（3）對Lena和boat圖加噪圖像來說，1-Otsu效果最差，噪聲點特別多，這是因為其抗噪聲性能最低；2-Otsu的效果較好，去除噪聲點最多；FA-2-Otsu在去除噪聲方面比1-Otsu好但不如2-Otsu，然而其在分割細節(jié)方面保留較好．

3.2 客觀分析

客觀評價選取香農(nóng)熵、區(qū)域?qū)Ρ榷纫约八惴ㄟ\行時間三個指標(biāo)作為評價標(biāo)準(zhǔn)．

3.2.1 香農(nóng)熵

香農(nóng)熵H的計算公式如下：

式中P0、P1分別為分割結(jié)果中0、1的概率，香農(nóng)熵的值與分割效果成正比[12]，具體結(jié)果如表1所示．由表1可得3種算法香農(nóng)熵的客觀數(shù)值相差不大．

表1 香農(nóng)熵的對比

3.2.2 區(qū)域?qū)Ρ榷?/h4>

區(qū)域?qū)Ρ榷菴的計算公式如下

式中f0為背景像素個數(shù)、f1為目標(biāo)像素個數(shù)．區(qū)域?qū)Ρ榷鹊闹蹬c分割質(zhì)量亦成正比[13]．具體結(jié)果如表2所示．由表2可得3種算法區(qū)域?qū)Ρ榷鹊臄?shù)值幾乎相同，然而當(dāng)Lena圖加噪聲時，F(xiàn)A-2-Otsu和2-Otsu區(qū)域?qū)Ρ榷鹊闹递^1-Otsu高出很多，原因是1-Otsu的抗噪聲性能在三種算法中較差．

表2 區(qū)域?qū)Ρ榷鹊膶Ρ?/p>

3.2.3 算法運行時間

算法運行時間T的大小關(guān)系到實時性問題，是一種重要的客觀標(biāo)準(zhǔn)．同一算法，在同等條件下，運行時間不是固定的而是有波動的，因此本文在相同硬件配置條件下，對同一個算法運行100次，取其100次運行的總時間作為一個客觀評價標(biāo)準(zhǔn)．具體結(jié)果如表3所示，F(xiàn)A-2-Otsu與1-Otsu的運行時間明顯小于2-Otsu的運行時間，且FA-2-Otsu與1-Otsu的運行時間較為接近，100次運行的總時間相差不到10秒．

表3 算法的運算時間的對比

主觀評價結(jié)論與上述三種客觀評價標(biāo)準(zhǔn)所得結(jié)果基本一致，由此可得本文算法分割效果較好，分割時間較少，在大多數(shù)情況下優(yōu)于另外兩種算法．

4 結(jié)論

本文提出一種FA-2-Otsu，相對于Otsu通過窮舉法獲得最佳分割閾值，該算法僅需要在螢火蟲移動時經(jīng)過的那部分像素點中搜尋最大亮度值，能夠較快的獲得最優(yōu)解．實驗結(jié)果表明，1-Otsu分割時間短但是抗噪性能太弱、2-Otsu抗噪性能強但計算復(fù)雜度過高，所提算法保證圖像分割質(zhì)量的前提下，抗噪性能較強、分割效率較高、分割時間較少，且為其他領(lǐng)域?qū)で笞顑?yōu)解提供一種新的思路，是一種綜合性能較好的算法．

參考文獻：

[1]姜楓,顧慶,郝慧珍,等.基于內(nèi)容的圖像分割方法綜述[J].軟件學(xué)報,2017,28(1):160-183.

[2]吳一全,孟天亮,吳詩婳.圖像閾值分割方法研究進展20年(1994—2014)[J].數(shù)據(jù)采集與處理,2015,30(1):1-23.

[3]Otsu N.A Threshold Selection Method from Gray-Level Histograms[J].IEEE Transactions on Systems Man&Cybernetics,2007,9(1):62-66.

[4]劉健莊,栗文青.灰度圖象的二維Otsu自動閾值分割法[J].Acta Automatica Sinica,1993,19(1):101-105.

[5]吳成茂,田小平,譚鐵牛.二維Otsu閾值法的快速迭代算法[J].模式識別與人工智能,2008,21(6):746-757.

[6]景曉軍,蔡安妮,孫景鰲.一種基于二維最大類間方差的圖像分割算法[J].通信學(xué)報,2001,22(4):71-76.

[7]汪海洋,潘德爐,夏德深.二維Otsu自適應(yīng)閾值選取算法的快速實現(xiàn)[J].Acta Automatica Sinica,2007,33(9):968-971.

[8]Yang X S.Firef l y Algorithm,Stochastic Test Functions and Design Optimisation[J].International Journal of Bio-Inspired Computation,2010,2(2):78-84(7).

[9]Aungkulanon P,Chaiead N,Luangpaiboon P.Simulated Manufacturing Process Improvement via Particle Swarm Optimisation and Firef l y Algorithms[J/OL].Lecture Notes in Engineering&Computer Science,2011,2189(1).

[10]劉長平,葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法[J].計算機應(yīng)用研究,2011,28(9):3295-3297.

[11]劉鵬,劉弘,鄭向偉,等.基于改進螢火蟲算法的動態(tài)自動聚集路徑規(guī)劃方法[J].計算機應(yīng)用研究,2011,28(11):4146-4149.

[12]劉書琴,毋立芳,宮玉,等.圖像質(zhì)量評價綜述[J].中國科技論文,2011,06(7):501-506.

[13]張松,汪烈軍,祁彥慶.一種基于PCNN和改進的OTSU的圖像分割算法[J].中國科技論文,2016(2):236-240.