一種基于種子優(yōu)化算法的圖像分割方法

張然 陳權(quán) 牛青松 韓永蓮 鄧西金

摘 要：基于智能計算的圖像分割技術(shù)是數(shù)字圖像處理研究的重要前沿內(nèi)容?；诮陙沓霈F(xiàn)的仿生群體智能算法種子優(yōu)化算法，設(shè)計構(gòu)建了一種自適應(yīng)種子優(yōu)化算法，并與多閾值圖像分割方法相結(jié)合解決圖像分割問題。最后選用數(shù)字圖像處理領(lǐng)域常用的測試圖像開展了算法實驗，并且與粒子群算法進(jìn)行實驗對比與分析，結(jié)果表明基于自適應(yīng)種子優(yōu)化算法的閾值分割法具有更好的圖像分割性能，能夠有效的開展數(shù)字圖像分割，具有較好的應(yīng)用研究價值。

關(guān)鍵詞： 圖像分割； 種子優(yōu)化算法； 群體智能； 數(shù)字圖像處理； 粒子群算法

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2019）06-0193-05

An Image Segmentation Method Based On Bean Optimization Algorithm

ZHANG Ran1，CHEN Quan1 ，NIU Qing-song2，HAN Yong-lian2 ， DENG Xi-jin2

（1. Army Artillery Air Defense Academy， Hefei 230031， China； 2. Qinghai Institute of science and technology information， Xining 810018， China）

Abstract：Image segmentation based on intelligent computing is an important frontier in digital image processing. Based on the bean optimization algorithm of bionic swarm intelligence algorithm in recent years， an adaptive bean optimization algorithm is designed and constructed， which is combined with multi-threshold image segmentation method to solve the problem of image segmentation. Finally， the algorithm experiments are carried out with the commonly used test images in the field of digital image processing. Experimental comparison and analysis are also carried out with particle swarm optimization algorithm. The results show that the threshold segmentation method based on adaptive seed optimization algorithm has better image segmentation performance and can effectively carry out digital image segmentation. Experiments show that this algorithm has good application research value.

Key words：image segmentation； bean optimization algorithm； swarm intelligence； digital image processing； particle swarm optimization algorithm

現(xiàn)實生活遇到許多重要問題都會涉及到選取一個最好的目標(biāo)，或者為達(dá)到這個最理想的目標(biāo)而對參數(shù)等進(jìn)行選取，這些都可以歸納到優(yōu)化問題中。用于解決優(yōu)化問題的算法稱為優(yōu)化算法，其本質(zhì)就是通過某種策略獲得問題的最優(yōu)解[1]。智能優(yōu)化算法是其中理論最豐富、應(yīng)用最廣泛的策略，該類型算法是受自然現(xiàn)象啟發(fā)而設(shè)計出來的，屬于概率迭代算法的一種。由于該類算法具有自組織性、啟發(fā)式搜索、強(qiáng)魯棒性以及實現(xiàn)簡單等特點(diǎn)，得到眾多研究學(xué)者的關(guān)注，已經(jīng)被廣泛地應(yīng)用于函數(shù)優(yōu)化[2]、調(diào)度[3]、參數(shù)估計[4]、多機(jī)器人系統(tǒng)[5]及特征選擇[6]各個領(lǐng)域中。

圖像計算復(fù)雜度問題是目前圖像處理領(lǐng)域中一個十分受關(guān)注的問題，盡管目前對圖像處理是在灰度級上運(yùn)算而不是在像素級上進(jìn)行操作，相較于傳統(tǒng)的方法已經(jīng)大幅度地減少了計算量，但即便如此，算法的復(fù)雜度仍然比較高，難以滿足要求。大量的研究表明圖像處理問題在一定程度上都是可以轉(zhuǎn)化為最優(yōu)化的求解問題，例如圖像分割這類問題實質(zhì)上就是對最優(yōu)分割點(diǎn)的選取的優(yōu)化問題。而利用智能算法求解這類最優(yōu)化問題，不僅大大提高計算效率而且能夠得到十分準(zhǔn)確的解。智能算法與圖像分割融合一般體現(xiàn)在兩個地方：特征空間聚類和最優(yōu)閾值選取。特征空間聚類的思想就是在圖像分割時充分發(fā)揮智能算法的優(yōu)勢，在盡快獲得最優(yōu)聚類的同時又避免陷入局部最優(yōu)。而最優(yōu)閾值選取即是利用智能算法去計算并找到目標(biāo)函數(shù)的最優(yōu)值，進(jìn)而確定圖像分割的最佳閾值[7]。

基于智能算法的圖像分割的例子有：基于遺傳算法的圖像分割[8]；基于局部蟻群算法的圖像分割[9]；基于CRF與模擬退火算法的圖像分割[10]；基于粒子群算法的圖像分割[11]；基于魚群算法優(yōu)化normalized cut的彩色圖像分割[12]；基于改進(jìn)蜂群算法優(yōu)化的圖像分割[13]等等。通過引入一些人為的知識導(dǎo)向和人工智能的方法，將智能算法與圖像分割相結(jié)合，可以糾正某些分割中的錯誤或者提高求解的效率。種子優(yōu)化算法是近年來出現(xiàn)的一類新的仿生群體智能算法，算法本質(zhì)是對植物種子傳播過程及后代分布演化的建模，其仿生原理清晰，算法實現(xiàn)簡便。經(jīng)過長期研究發(fā)現(xiàn)，該算法在全局優(yōu)化問題求解中，算法的收斂速度以及全局尋優(yōu)都具有很好的性能。對于基于閾值法的圖像分割實質(zhì)上也是全局優(yōu)化的問題，所以基于自適應(yīng)種子優(yōu)化算法實現(xiàn)圖像分割具有可行性和重要研究意義。

2 種子優(yōu)化算法原理

自然界中，植物繁殖后代需要通過某種途徑傳播自己的種子，其傳播的方式多種多樣，例如動物傳播、水傳播、風(fēng)傳播和散射傳播等等。其中散射傳播在豆科植物中比較常見，當(dāng)豆子的種子成熟后，經(jīng)過太陽長時間的暴曬，種皮會發(fā)生爆裂，隨后種子就會被隨機(jī)彈射到父類植物的附近，落在土壤上的種子會發(fā)芽生長，最終長成新的植株。在眾多植株當(dāng)中，有的植株長得比較茁壯，就會生出比較多的種子，這表明這株植株所在的土地很肥沃；有的植株長得會比較纖弱甚至有的地方?jīng)]有植株生長，表明這一塊土地肥力比較差或不適合植株生長。經(jīng)過很多代的演化之后，在肥沃的土地會生長出很多的后代植株，而在貧瘠的土地會生長出很少的植株。種子優(yōu)化算法就是受這種自然現(xiàn)象的啟發(fā)，土地代表算法所需優(yōu)化的目標(biāo)問題，土地的肥沃程度就是目標(biāo)函數(shù)的適應(yīng)度值，某塊土地的適應(yīng)度差，就說明這塊土地較貧瘠；某塊土地的適應(yīng)度越優(yōu)，就代表該土地越肥沃，目標(biāo)問題的最優(yōu)解就是一片土地中最肥沃的一塊。一群種子隨機(jī)地播撒到一塊土地上，如果種子掉落到較肥沃的土地，那么這個種子長大成植株的概率并且繁衍出更多后代植株的機(jī)會就會很大，否則，這個種子就有很大的可能存活不了或生成的植株比較纖弱。長此以往，經(jīng)過數(shù)代的迭代演化，最終只有在最肥沃的土地上會長出一株或多株植物，進(jìn)而發(fā)現(xiàn)問題的最優(yōu)解。

在算法中，用n維向量[X={x1，x2，x3，...，xn}]表示一個種子的位置，所有種子的總數(shù)為sum，對所有的種子隨機(jī)初始化位置向量并計算適應(yīng)度值，對比不同種子之間的適應(yīng)度值的大小，得到適應(yīng)度值較優(yōu)的幾個并將其定義為父種個體，以父種為中心按照某種策略生成后代種子群體，生成后代種子個體的數(shù)量由每個父種適應(yīng)度值的大小決定的。父種自身的適應(yīng)度值越優(yōu)秀，表示父種所在的土地越肥沃，生成后代個體的數(shù)量就會越多；否則，生成后代個體的數(shù)量就越少。同時，為了使得生成的后代種群較為分散，父種與父種之間應(yīng)滿足一定的距離限制。

當(dāng)所有父種的后代種子生成完畢后，再次根據(jù)待求的目標(biāo)函數(shù)計算所有種子的適應(yīng)度值，接著比較不同種子間的適應(yīng)度值，得到適應(yīng)度最大的種子個體并將其作為一號父種，然后選擇剩下的種子中適應(yīng)度最大的種子，計算其與一號父種間的距離是否大于父種間設(shè)定的距離閾值（本文采用的是歐式距離計算），這樣做的目的是來保證父種及后代群體在空間上分布更加合理，可以有效防止算法陷入局部最優(yōu)，提高算法的全局尋優(yōu)能力。父種選擇流程圖如圖2所示：

與此同時，為了擴(kuò)大生成后代種子的范圍，提高算法的全局尋優(yōu)性能，在生成后代種子的時候，隨機(jī)選取一小部分的種子并隨機(jī)設(shè)置其位置。

依據(jù)父種的播撒方程，即種群的分布演化模型，每個父種生成自己的后代種子，然后在新的后代種子中按照父種選擇機(jī)制選取新的父種。循環(huán)迭代，后代種子不斷尋優(yōu)，直至得到所需的優(yōu)化結(jié)果或者達(dá)到設(shè)定的迭代次數(shù)。算法流程圖如圖3所示：

目前該算法已經(jīng)成功構(gòu)建了基于分段函數(shù)的種子優(yōu)化算法[14]、基于正態(tài)分布的種子優(yōu)化算法[15]、基于負(fù)二項分布的種群分布演化模型、種子優(yōu)化算法的Markov鏈模型[16]和基于混沌的種子優(yōu)化算法[17]，并在路徑優(yōu)化[18]、恢復(fù)重建選址[19]等領(lǐng)域開展了應(yīng)用研究，得到了國內(nèi)外研究學(xué)者的認(rèn)可。

3 基于自適應(yīng)種子優(yōu)化算法的多閾值法圖像分割

針對圖像分割的特點(diǎn)和需求，為了進(jìn)一步提高種子優(yōu)化算法求解問題的準(zhǔn)確度和速度，并且增強(qiáng)全局的搜索性能，提出一種自適應(yīng)種子優(yōu)化算法。在迭代的過程中，對種子優(yōu)化算法的父種間距離閾值和父種個體進(jìn)行自適應(yīng)變化，然后將圖像分割的問題看作是種子群體尋找最優(yōu)解的一種優(yōu)化問題，通過基于父種選擇機(jī)制的種群分布演化，直至搜索到最優(yōu)解的位置，即待求解的最佳閾值。

3.1 算法設(shè)計

根據(jù)閾值法圖像分割的思想和實現(xiàn)過程，最佳閾值的求解是此算法的核心點(diǎn)。本文采用最大熵法來計算求解閾值，以此來構(gòu)建待求解的目標(biāo)函數(shù)，當(dāng)選取的閾值個數(shù)較多時，也就是多閾值情況下，假設(shè)選取的閾值個數(shù)為m，由前面內(nèi)容的分析，據(jù)此構(gòu)建的目標(biāo)函數(shù)為：

該算法的執(zhí)行步驟如下：

Step 1. 首先初始化種子群體。選取的種子個數(shù)為popsize，隨機(jī)初始化種子的初始位置，設(shè)定所有種子的維數(shù)為dim，這里的維數(shù)根據(jù)具體的問題會有所不同，父種個數(shù)為n，父種間距離閾值threshold，最大迭代次數(shù)maxgen。

Step 2. 根據(jù)最大熵算法的適應(yīng)度函數(shù)，計算每一個種子的適應(yīng)度值，即熵值。

Step 3. 進(jìn)行迭代尋優(yōu)

1）父種選擇

對比不同種子間的適應(yīng)度值大小，得到本代的種子中適應(yīng)度最優(yōu)的種子，然后將其作為一號父種，繼續(xù)選擇剩下種子中適應(yīng)度最優(yōu)的種子，判斷其與本代已有父種的近似度（本文采用歐氏距離衡量近似度），若大于給定閾值，則選其作為二號父種，以此類推，直至父種的個數(shù)達(dá)到所需要的個數(shù)。

2）根據(jù)設(shè)定的種群分布演化模型，本文采取的是正態(tài)分布模型與負(fù)二項分布模型結(jié)合的方式產(chǎn)生種群，圍繞不同父種以此模型作為播撒方程生成后代的種子群體，父種不同，相應(yīng)的生成后代種群的規(guī)模和范圍也是不同的。

Step 4. 對算法執(zhí)行的當(dāng)前狀態(tài)或者最終結(jié)果的終止條件進(jìn)行判斷。如果滿足，算法立即終止；否則，執(zhí)行Step 2。

Step 5. 輸出結(jié)果，算法結(jié)束。

3.2實驗設(shè)置

為了比較本文提出的算法性能，設(shè)計了其與PSO算法的對比實驗，利用這兩種算法分別對圖像分割經(jīng)典的圖像Lena進(jìn)行分割，然后對兩種算法得到的分割結(jié)果進(jìn)行對比分析。

自適應(yīng)種子優(yōu)化算法：由于一幅數(shù)字圖像包含的灰度通常固定在[0， 255]區(qū)域內(nèi)，即解空間是[0，255]，所以所有種子的位置范圍均為[0， 255]，設(shè)置種子數(shù)量popsize為20，種子的維度分別為2和3（即雙閾值和三閾值分割問題），父種個數(shù)為3，最大迭代次數(shù)為50，負(fù)二項分布概率pnbrnd=0.5。