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

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

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

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

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

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

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

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

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

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

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

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

依據(jù)父種的播撒方程，即種群的分布演化模型，每個(gè)父種生成自己的后代種子，然后在新的后代種子中按照父種選擇機(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ù)二項(xiàng)分布的種群分布演化模型、種子優(yōu)化算法的Markov鏈模型[16]和基于混沌的種子優(yōu)化算法[17]，并在路徑優(yōu)化[18]、恢復(fù)重建選址[19]等領(lǐng)域開展了應(yīng)用研究，得到了國(guó)內(nèi)外研究學(xué)者的認(rèn)可。

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

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

3.1 算法設(shè)計(jì)

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

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

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

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

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

1）父種選擇

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

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

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

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

3.2實(shí)驗(yàn)設(shè)置

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

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