基于類間螞蟻競(jìng)爭(zhēng)模型的顯著圖像分割算法

黃小童，程 虹，羅 穎

(湖北文理學(xué)院，湖北 襄陽(yáng) 441053)

0 引 言

圖像分割和對(duì)象提取一直是圖像處理中的重要分支，在計(jì)算機(jī)視覺、智能圖像識(shí)別、生物醫(yī)學(xué)、氣象、軍事、遙感等眾多領(lǐng)域有著廣泛的應(yīng)用。近年來(lái)交互式的半自動(dòng)分割通過(guò)用戶交互，獲取盡可能多的分割信息，大多是基于圖論的最優(yōu)分割，基本原則是使得劃分的子圖(區(qū)域)內(nèi)部相似度最大，子圖之間的相似度最小，同時(shí)應(yīng)約束劃分區(qū)域的特性。其中常見的圖像聚類問題或分割割集準(zhǔn)則包括：Minimum Cut、Average Cut、Grow Cut、Normalized Cut[1]、Random Walks[2]、Geodesic[3]、Spline Regression[4]，其缺點(diǎn)在于需要人工交互，從很大程度上依賴用戶的標(biāo)記情況，自動(dòng)性較差。

20世紀(jì)末，意大利學(xué)者Dorigo提出了蟻群優(yōu)化(ant colony optimization，ACO)的概念和算法，該算法是通過(guò)觀察螞蟻尋找食物的過(guò)程，能夠找到從巢穴到食物源最短路徑這一現(xiàn)象。近年來(lái)，蟻群算法在圖像分割方面的應(yīng)用研究主要包括以下幾個(gè)改進(jìn)：

(1)最優(yōu)分割的收斂：文獻(xiàn)[5]設(shè)計(jì)了一種基于隨機(jī)游走更新策略的螞蟻聚類算法，通過(guò)螞蟻的群體智能自組織地產(chǎn)生聚類，能自適應(yīng)更新參數(shù)。文獻(xiàn)[6]采用蟻群搜索與模糊聚類相結(jié)合的方法，蟻群搜索僅僅用來(lái)確定聚類數(shù)目和中心。根據(jù)“分而治之”的原則，單蟻群可演化到多蟻群策略，即先由各蟻群獨(dú)立優(yōu)化各自子問題，然后采用動(dòng)態(tài)自適應(yīng)信息交換策略進(jìn)行局部最優(yōu)解傳遞，成功降低了二維圖像分割中最小能量化函數(shù)的病態(tài)性[7]。(2)邊緣斷裂的改善：文獻(xiàn)[8]首先進(jìn)行邊緣檢測(cè)獲取由真實(shí)邊緣和噪聲組成的邊緣備選集，以較大概率選擇梯度值高的像素點(diǎn)，使搜索向邊緣收斂，然后根據(jù)蟻群搜索路徑上信息素的累積結(jié)果提取邊緣。但是該方法計(jì)算量大，同時(shí)邊緣散亂不連續(xù)。為此，引入幅度、相位和搜索方向信息作為啟發(fā)信息，加強(qiáng)蟻群邊緣提取中的抑噪能力[9]。

從整體來(lái)看，蟻群圖像分割算法的相關(guān)研究尚處于起步階段。該文的研究重點(diǎn)是類間螞蟻競(jìng)爭(zhēng)模型的顯著圖像分割，發(fā)展具有人工干預(yù)少、精度高、可靠性好等優(yōu)點(diǎn)的顯著圖像分割算法。在此基礎(chǔ)之上進(jìn)行的應(yīng)用研究將使得本項(xiàng)目的研究有著重要的現(xiàn)實(shí)意義。著名的單種群動(dòng)力學(xué)Logistic模型關(guān)注了單個(gè)種群的數(shù)量變化情況，事實(shí)上任何生物種群中都存在類間競(jìng)爭(zhēng)情況，從而實(shí)現(xiàn)種群之間的協(xié)同進(jìn)化。受到這種競(jìng)爭(zhēng)關(guān)系的啟發(fā)，該文以傳統(tǒng)蟻群算法為基礎(chǔ)，提出類間螞蟻的競(jìng)爭(zhēng)模型，設(shè)想基于兩類螞蟻相互競(jìng)爭(zhēng)的顯著圖像分割。算法首先采用SLIC(simple linear iterative clustering)超像素分割對(duì)圖像的預(yù)處理，保留原始圖像信息，將圖像分割成不同區(qū)域，既可以提高分割精度得到理想的分割結(jié)果，同時(shí)可以縮短運(yùn)算時(shí)間。然后根據(jù)蟻群算法的思想，為了彌補(bǔ)單類螞蟻分割易造成的欠分割或者過(guò)分割，引入兩類螞蟻，每一類螞蟻尋找各自目標(biāo)(前景/背景)，不同類別的螞蟻之間進(jìn)行信息互補(bǔ)與競(jìng)爭(zhēng)，使得分割結(jié)果更加準(zhǔn)確。根據(jù)種群競(jìng)爭(zhēng)思想，設(shè)定兩類螞蟻，根據(jù)每類螞蟻設(shè)定食物目標(biāo)不同，從而相互競(jìng)爭(zhēng)，最終找到各自的食物，多類螞蟻相互競(jìng)爭(zhēng)，“優(yōu)勝劣汰”，最終根據(jù)兩類螞蟻分泌的信息素競(jìng)爭(zhēng)得到最終的結(jié)果。

1 改進(jìn)的類間螞蟻競(jìng)爭(zhēng)模型顯著圖像分割

首先將SLIC超像素分割引入算法中，然后分別從類內(nèi)螞蟻的運(yùn)動(dòng)模型和類間螞蟻的競(jìng)爭(zhēng)模型進(jìn)行闡述。

1.1 SLIC超像素分割，構(gòu)建區(qū)域鄰接圖

傳統(tǒng)的蟻群算法為了保證分割結(jié)果的有效性，需要在圖中放置大量螞蟻，導(dǎo)致運(yùn)算時(shí)間復(fù)雜度較大。該文引用SLIC算法[10]，即簡(jiǎn)單的線性迭代聚類。它是將彩色圖像轉(zhuǎn)化為CIELAB顏色空間和XY坐標(biāo)下的5維特征向量，然后對(duì)5維特征向量構(gòu)造距離度量標(biāo)準(zhǔn)，對(duì)圖像像素進(jìn)行局部聚類的過(guò)程。該文采用文獻(xiàn)[11]超像素分割的方法將圖像分成n個(gè)超像素塊R={Ri|i=1,2,…,n}，圖1所示為經(jīng)SLIC預(yù)分割后的結(jié)果圖像，其主要區(qū)域較好地保持了原始圖像結(jié)構(gòu)信息，而且運(yùn)行速度、生成超像素的緊湊度、輪廓保持方面都比較理想。為了提高蟻群算法的運(yùn)算速度，螞蟻被放入每個(gè)超像素塊內(nèi)，該文根據(jù)預(yù)分割的超像素塊建立區(qū)域鄰接圖G=(V,E)，區(qū)域塊Ri構(gòu)成V，其相鄰區(qū)域構(gòu)成E，每個(gè)頂點(diǎn)vi的顏色值Ii是區(qū)域內(nèi)像素的顏色均值。該文所有的計(jì)算均是針對(duì)區(qū)域鄰接圖。

圖1 SLIC超像素預(yù)分割結(jié)果

1.2 顯著性計(jì)算

目前的顯著性目標(biāo)檢測(cè)方法是通過(guò)對(duì)輸入圖像多特征通道分析，來(lái)得到圖像中每個(gè)像素點(diǎn)感興趣程度的顯著性分布圖，其采用的低層特征主要集中在圖像的顏色和對(duì)比度。

當(dāng)前景和背景顏色有重合的時(shí)候，僅僅依賴于它們的顏色和梯度等相關(guān)特征是基本不起作用的，且圖像分割是由邊界區(qū)域決定。為了彌補(bǔ)這一影響，該文將引入顯著性，顯著值越高的區(qū)域，用戶越能被吸引，則這一區(qū)域?qū)儆谇熬暗目赡苄暂^大；顯著值越低的區(qū)域，用戶越不能被吸引，屬于背景的可能性較大[12-17]。圖2顯示了圖像上顯著性檢測(cè)及感興趣目標(biāo)區(qū)域提取結(jié)果[14]。顯著圖通常也被直接用來(lái)進(jìn)行圖像分割，但是其中大多數(shù)都是基于閾值分割的方法[15-17]，往往缺少通用性。該文在蟻群算法的框架下，將圖像內(nèi)容的顯著性用來(lái)輔助顏色進(jìn)行分割，較好地解決了這一問題。

圖2 顯著圖

1.3 類內(nèi)螞蟻的運(yùn)動(dòng)模型

(1)

(2)

(3)

其中，h和c分別表示梯度和顏色特征，s表示區(qū)域塊Ri的顯著均值：

h(i,j)=max|Ii,j-Im,n|,m=i-1,i,

i+1,n=j-1,j,j+1

(4)

(5)

其中，‖Ii-Ij‖2是第i個(gè)超像素塊與第j個(gè)超像素塊的像素平均值的歐氏距離，σ為鄰接像素的顏色距離均值。

1.4 類間螞蟻的競(jìng)爭(zhēng)模型

由于單類螞蟻分割易造成欠分割或者過(guò)分割，根據(jù)種群間存在的競(jìng)爭(zhēng)關(guān)系，提出類間螞蟻的競(jìng)爭(zhēng)模型，設(shè)想基于類間螞蟻競(jìng)爭(zhēng)模型的顯著圖像分割。

算法設(shè)定兩類螞蟻，每一類螞蟻尋找各自目標(biāo)，一類螞蟻以前景(顯著圖像)為目標(biāo)進(jìn)行尋找，另一類螞蟻以圖像背景為目標(biāo)進(jìn)行尋找。兩類螞蟻分別以各自目標(biāo)尋找最優(yōu)解，并留下可供交換信息的信息素，當(dāng)信息素分布趨于穩(wěn)定時(shí)，兩類螞蟻進(jìn)行種群競(jìng)爭(zhēng)。兩類螞蟻信息素的更新如下所示：

(6)

(7)

最后將得到的信息素map圖通過(guò)形態(tài)學(xué)后處理得到最終的map圖，圖3表示兩類螞蟻信息素在待分割圖像上最終的分布，其中黑色部分和灰色部分分別表示第一類螞蟻所處的前景區(qū)域和第二類螞蟻所處的背景區(qū)域。

圖3 兩類螞蟻競(jìng)爭(zhēng)后最終的分布

1.5 基于類間螞蟻競(jìng)爭(zhēng)模型的顯著圖像分割算法流程

Step1：預(yù)處理，采用SLIC算法對(duì)輸入圖像進(jìn)行超像素預(yù)分割，得到區(qū)域塊和其在HSV空間的顏色值，構(gòu)建區(qū)域鄰接圖。

Step2：采用類間螞蟻的競(jìng)爭(zhēng)模型對(duì)圖像進(jìn)行分割。

Step2.1：初始化兩類螞蟻以及信息素矩陣，計(jì)算顯著圖和顯著值，并結(jié)合SLIC預(yù)分割結(jié)果對(duì)每個(gè)區(qū)域 計(jì)算顯著均值和初始化啟發(fā)式矩陣與信息素矩陣；

Step2.2：兩類螞蟻各自根據(jù)式(1)的狀態(tài)轉(zhuǎn)移概率進(jìn)行路徑選擇，完成覓食；

Step2.3：每一次進(jìn)行路徑選擇后，對(duì)路徑信息素進(jìn)行更新，如式(6)；

Step2.4：判斷是否尋到最優(yōu)，否則跳轉(zhuǎn)到(3)；

Step2.5：根據(jù)式(7)完成兩類螞蟻競(jìng)爭(zhēng)。

2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證該算法的正確性和有效性，在Windows 7操作系統(tǒng)下，采用Matlab R2010進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)集是公開數(shù)據(jù)集：Berkeley Segmentation Data Set and Benchmarks 500 (BSDS50)(https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html#algorithms)，并從分割效果、分割準(zhǔn)確率、交互時(shí)間3個(gè)方面分析算法的性能。

2.1 分割效果

實(shí)驗(yàn)中，對(duì)類間螞蟻競(jìng)爭(zhēng)模型算法的參數(shù)設(shè)置為：α=1,β=4,ρ=0.2，經(jīng)類間螞蟻競(jìng)爭(zhēng)模型算法計(jì)算得到的分割結(jié)果對(duì)比不同算法，如表1所示。

表1 分割結(jié)果對(duì)比

由表1可得，當(dāng)前景和背景顏色差別較小時(shí)，GrowCut算法分割結(jié)果性能降低，并且GrowCut需要人工預(yù)先標(biāo)定圖片的前景和背景，且分割效果很大程度上依賴于人工預(yù)先標(biāo)定。文中所提出的算法不需要人工干預(yù)，直接由算法分割出顯著圖像，由于算法采用SLIC超像素分割使得圖像原有的結(jié)構(gòu)得到保留，類間螞蟻競(jìng)爭(zhēng)模型使得兩類螞蟻各自尋找自己的目標(biāo)，一類尋找前景，一類尋找背景，相互合作，提高了分割效果準(zhǔn)確性。

2.2 分割準(zhǔn)確率

為了定量計(jì)算文中算法的分割正確率，對(duì)圖片庫(kù)中所有500幅圖片的分割效果進(jìn)行比較，將實(shí)驗(yàn)數(shù)據(jù)庫(kù)中的標(biāo)注結(jié)果作為評(píng)價(jià)標(biāo)準(zhǔn)(ground truth)，計(jì)算文中算法和傳統(tǒng)分割算法的敏感性(TPF)和特異性(FPF)。TPF是指正確識(shí)別的目標(biāo)顯著圖像素?cái)?shù)與參考標(biāo)準(zhǔn)中的目標(biāo)顯著圖像素?cái)?shù)的比率，其代表了算法針對(duì)目標(biāo)區(qū)域的有效性，其值越高則表示算法越有效；FPF是指正確識(shí)別的背景像素?cái)?shù)與參考標(biāo)準(zhǔn)中的背景像素?cái)?shù)的比率，代表了算法可能出現(xiàn)的對(duì)非目標(biāo)區(qū)域的正確分割能力，其值越高則表示算法能力越強(qiáng)。測(cè)試結(jié)果如表2所示。

表2 不同分割算法性能對(duì)比

由表2可以看出，對(duì)于圖片庫(kù)中所有500幅圖片進(jìn)行測(cè)試，文中算法的分割效果、平均敏感性和特異性優(yōu)于其他2種算法。

2.3 交互時(shí)間

文中算法的運(yùn)行時(shí)間由SLIC超像素預(yù)分割的時(shí)間、顯著圖的計(jì)算時(shí)間和類間螞蟻競(jìng)爭(zhēng)模型算法時(shí)間構(gòu)成，由于SLIC預(yù)處理算法與顯著圖只需要計(jì)算一次，分割過(guò)程可能需要多次交互，多次運(yùn)行類間螞蟻競(jìng)爭(zhēng)模型。算法的運(yùn)行時(shí)間比較如表3所示，文中算法由于在區(qū)域鄰接圖上進(jìn)行計(jì)算，交互時(shí)間有了大幅的縮減，提高了算法效率。

表3 交互時(shí)間對(duì)比 s

3 結(jié)束語(yǔ)

針對(duì)單類蟻群算法分割易造成欠分割或過(guò)分割這一現(xiàn)象，提出基于類間螞蟻競(jìng)爭(zhēng)模型的顯著圖像分割算法。首先采用SLIC超像素分割算法對(duì)圖像進(jìn)行預(yù)分割，將圖像分割成多個(gè)區(qū)域，不僅可以提高分割精度得到理想的分割結(jié)果，同時(shí)可以縮短運(yùn)算時(shí)間。然后根據(jù)種群競(jìng)爭(zhēng)思想，設(shè)定兩類螞蟻，根據(jù)每類螞蟻設(shè)定食物目標(biāo)(前景/背景)，從而相互競(jìng)爭(zhēng)，找到各自的食物，最終根據(jù)兩類螞蟻分泌的信息素競(jìng)爭(zhēng)得到最終的結(jié)果。結(jié)果表明，該算法運(yùn)行快速，分割結(jié)果更加精確。同時(shí)算法可進(jìn)一步由兩類螞蟻延伸至多類螞蟻，由邏輯映射到線性映射轉(zhuǎn)變，以實(shí)現(xiàn)更加復(fù)雜的分割。