周 苑，周 巖

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

基于變尺度進(jìn)化的多目標(biāo)圖像分割算法

周 苑，周 巖

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

針對進(jìn)化計(jì)算在圖像處理方面的應(yīng)用存在計(jì)算代價(jià)高和評價(jià)函數(shù)單一的缺點(diǎn)，提出了一種變尺度進(jìn)化的多目標(biāo)圖像分割算法。該算法在進(jìn)化的不同階段將不同數(shù)量的相鄰像素作為同一像素處理，從而在不同尺度下完成圖像的分割，降低了算法的計(jì)算時(shí)間。同時(shí)，設(shè)計(jì)了監(jiān)測關(guān)鍵解變化量的方法來控制不同尺度的過渡時(shí)機(jī)。在評價(jià)函數(shù)上則采用包含緊致度和連接度的多目標(biāo)方式，以更為全面地評估分割的質(zhì)量。其中，連接度檢查鄰接像素所屬類別的連續(xù)性，有效抑制了噪聲和小樣本類的干擾。對Sailboat和Terra圖像的分割結(jié)果顯示，所提出的算法能有效地將不同對象分割開來，同時(shí)在計(jì)算時(shí)間上僅為幾種同類對比算法的48.08%～55.53%。

進(jìn)化計(jì)算；多目標(biāo)；圖像分割；變尺度；連接度

圖像分割質(zhì)量的好壞對后續(xù)的圖像處理具有重要的影響[1]，而進(jìn)化計(jì)算作為一種具有良好全局尋優(yōu)性能的智能隨機(jī)搜索技術(shù)，已廣泛應(yīng)用于圖像的分割、檢索、復(fù)原和壓縮等方面[2-3]。但進(jìn)化計(jì)算通常采用單一的目標(biāo)函數(shù)來評價(jià)圖像處理的質(zhì)量，存在評價(jià)標(biāo)準(zhǔn)過于片面的不足[4]。而多目標(biāo)進(jìn)化優(yōu)化技術(shù)作為近些年進(jìn)化計(jì)算領(lǐng)域新興的一個(gè)研究方向，致力于同時(shí)處理多個(gè)相互制約的目標(biāo)函數(shù)的優(yōu)化問題，已經(jīng)取得了大量的研究成果[5-6]。這使得將多目標(biāo)進(jìn)化優(yōu)化技術(shù)應(yīng)用于圖像處理領(lǐng)域具有了可行性。目前已有一些學(xué)者提出了各自的多目標(biāo)進(jìn)化圖像處理算法[7]。如Shirakawa等人[8]提出了用于圖像分割的多目標(biāo)進(jìn)化算法，而Bandyopadhyay等人[9]則提出了用于遙感圖像分類的多目標(biāo)進(jìn)化聚類算法。上述方法均直接以單個(gè)像素點(diǎn)作為樣本來進(jìn)行數(shù)據(jù)聚類，但圖像中包含的像素點(diǎn)往往很多，這影響了算法的處理效率，限制了多目標(biāo)進(jìn)化算法的應(yīng)用范圍。圖像分割的目的是將圖像中不同種類的對象區(qū)分開，而圖像中像素之間的差異并非都屬于不同類對象的差異，在同類對象內(nèi)部實(shí)際也存在些許細(xì)節(jié)差異[10]。但這些內(nèi)部差異對圖像分割并無太大貢獻(xiàn)，反而會讓算法耗費(fèi)時(shí)間去計(jì)算這些細(xì)節(jié)差異，影響了優(yōu)化的速度。為了提高處理效率，可以在早期將若干相差不大的鄰域像素合并，便于算法快速找出不同類對象的大致輪廓，再將合并的像素逐步拆分，最終準(zhǔn)確確定不同對象的邊界。為此，提出了一種變尺度進(jìn)化的多目標(biāo)圖像分割算法(Multi-objective Evolutionary Image Segmentation with Varying-scale，MEISV)，采用了變尺度進(jìn)化的方法，對各尺度過度的時(shí)機(jī)進(jìn)行了控制，還采用了多目標(biāo)進(jìn)化的框架，并改進(jìn)了連接度目標(biāo)函數(shù)。對Sailboat圖像的分割則表明了算法改進(jìn)的有效性。

1 總體架構(gòu)變尺度進(jìn)化框架的設(shè)計(jì)

本文所提變尺度進(jìn)化包含合并、進(jìn)化、判別和分解4個(gè)步驟?？蚣苋鐖D1所示。

圖1 變尺度進(jìn)化框架的示意圖

圖2 區(qū)域合并示意圖

區(qū)域合并步驟只在整個(gè)算法的初始階段執(zhí)行一次，通過將圖像等分而得到粗粒度的像素，此后進(jìn)化算法對這些粗粒度像素進(jìn)行分割，達(dá)到一定判別準(zhǔn)則后即進(jìn)行粗粒度像素的分解，再對分解后的像素執(zhí)行進(jìn)化算法，直到所有像素均分解為單一像素且達(dá)到進(jìn)化算法的迭代停止準(zhǔn)則。

判別步驟是為了保證圖像分割的準(zhǔn)確度，在進(jìn)化到一定時(shí)期以后通過關(guān)鍵解的變化情況來決定是否需要對粗粒度像素進(jìn)行逐步分解。所謂關(guān)鍵解是指相對于周圍其他解，它的某些目標(biāo)函數(shù)取值僅有小幅變化，而另外一些目標(biāo)函數(shù)取值則出現(xiàn)大幅變化，如圖3所示。

圖3 關(guān)鍵解示意圖

分解步驟是對于當(dāng)前尺度下的每個(gè)圖像區(qū)域，分別以橫向和縱向的中間位置為邊界，將其劃分為4個(gè)子區(qū)域。然后計(jì)算每個(gè)子區(qū)域像素的R，G，B均值，再對各個(gè)子區(qū)域相鄰邊界位置的像素進(jìn)行局部調(diào)整。調(diào)整的方式為：對于邊界位置的每一個(gè)像素，計(jì)算其與各個(gè)子區(qū)域R，G，B均值的歐氏距離，按照距離最近原則劃歸新的子區(qū)域，最后更新各子區(qū)域的R，G，B均值。經(jīng)過分解以后圖像中的區(qū)域數(shù)量將變?yōu)樵鹊?倍，當(dāng)某一區(qū)域的像素個(gè)數(shù)等于或少于4個(gè)時(shí)，則直接分解為單個(gè)像素。

2 多目標(biāo)圖像分割算法的設(shè)計(jì)

2.1 多目標(biāo)函數(shù)的設(shè)計(jì)

本文所設(shè)計(jì)的多目標(biāo)函數(shù)為2個(gè)，稱為緊致度指標(biāo)和連接度指標(biāo)。其中緊致度指標(biāo)與文獻(xiàn)[8]所提類似，如式(1)所示

k=1,2,…,C(x)

(2)

(3)

圖4 噪聲和小樣本對連接度指標(biāo)的干擾示意圖

圖4中“·”、“□”和“#”分別表示3類對象，“△”表示噪聲像素，原先連接度傾向于將區(qū)域①和③作為兩類對象，而改進(jìn)后的連接度可以去除噪聲的干擾，正確地將其劃分為一類對象。

2.2 算法描述

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

為了驗(yàn)證算法的有效性，選取標(biāo)準(zhǔn)圖像Sailboat和Terra做測試，如圖5所示。

圖5 用于測試的標(biāo)準(zhǔn)圖像

設(shè)置了兩種對比算法，分別為：1)文獻(xiàn)[8]提出的多目標(biāo)聚類圖像分割算法，記為MOCKIS；2)連接度指標(biāo)未做改進(jìn)，其余與本文算法相同，記為CMEISV。

3.1 參數(shù)設(shè)置

相關(guān)參數(shù)的設(shè)置為：MOCKIS的所有參數(shù)設(shè)置與文獻(xiàn)[8]相同；MEISV和CMEISV的種群大小為50，存儲多目標(biāo)優(yōu)化所得解集的集合大小也為50，合并步驟中p和q的取值均為8，判別步驟中參數(shù)k0，z，t0以及ε的取值分別為3，3，10和10-3，區(qū)域像素在4個(gè)鄰域方向上的近鄰數(shù)量l1，l2，l3，l4均取值為5，最大類數(shù)Cmax則設(shè)為50，迭代停止條件為所有區(qū)域分解為單個(gè)像素并且連續(xù)t0代關(guān)鍵解的變化量小于閾值ε。所有算法中像素的相似性度量均是以R，G，B值之間的歐氏距離作為評價(jià)標(biāo)準(zhǔn)的。

3.2 分割效果對比與分析

3種算法在Sailboat和Terra圖像上的測試結(jié)果，如圖6和圖7所示。圖6和圖7中，子圖a～c為本文所提算法MEISV在優(yōu)化結(jié)束時(shí)所得3個(gè)關(guān)鍵解的分割結(jié)果，子圖d～f為對比算法CMEISV所得關(guān)鍵解的分割結(jié)果，子圖g則為文獻(xiàn)[8]所提供的MOCKIS的最佳分割結(jié)果。

圖6 3種算法對圖像Sailboat的分割結(jié)果對比

圖7 3種算法對圖像Terra的分割結(jié)果對比

從圖6結(jié)果顯示，本文提出的MEISV所得的3個(gè)關(guān)鍵解均可以將樹木(近處)、草地、樹林(遠(yuǎn)處)、天空和湖泊這些景物區(qū)分開，其中子圖b和c還識別出湖泊中的船，子圖c還識別出天空中的部分云彩。相比而言，對比算法CMEISV雖然也將大部分景物識別，但是由于連接度指標(biāo)對噪聲和少量像素構(gòu)成的對象過于敏感，使得圖像分割以后顯示出大量小的分割區(qū)域，反而不利于主要信息的判別。對比算法MOCKIS的結(jié)果則更為粗糙一些，其未能將圖中的樹林與草地、天空和云彩、湖泊和船只區(qū)分開來。此外，由子圖a～c還可以發(fā)現(xiàn)MEISV所得到的幾個(gè)關(guān)鍵解隨著分割類數(shù)的增加，其細(xì)節(jié)信息也逐漸增多，顏色相近的兩個(gè)物體(如天空和云彩)也逐漸區(qū)分。這可以為技術(shù)人員提供不同層次下有價(jià)值的圖像分割信息。

從圖7中結(jié)果也可以得出類似結(jié)論：本文算法可以將遠(yuǎn)近不同的樹林、田野、山巒等區(qū)分開，而對比算法CMEISV則得到的結(jié)果過于雜亂，缺乏層次性，MOCKIS則劃分得過于簡單，一些信息被忽略(如近處草地中包含有黃色和綠色兩種草)。

3.3 運(yùn)算時(shí)間對比

除了分析算法所得圖像分割結(jié)果的質(zhì)量，本文還在相同運(yùn)行條件下測試了所提算法MEISV、MOCKIS和MEIS在運(yùn)行時(shí)間上的差別。其中MEIS與本文算法MEISV采用相同的編碼、交叉和變異以及目標(biāo)函數(shù)，只是不進(jìn)行變尺度操作，直接對各個(gè)像素點(diǎn)進(jìn)行多目標(biāo)圖像分割。3種算法的迭代停止條件均設(shè)為函數(shù)調(diào)用次數(shù)達(dá)到預(yù)先設(shè)定的15 000次。測試結(jié)果如表1所示。

表1 3種算法的計(jì)算時(shí)間對比

s

圖像名稱耗時(shí)MEISVMEISMOCKISSailboat53211106710889Terra71331284513015

從表1結(jié)果可以看出本文算法在所用時(shí)間最短，在圖像Sailboat上為MEIS的48.08%，為MOCKIS的48.86%，在圖像Terra上則分別為55.53%和54.80%。可見變尺度進(jìn)化框架在保持求解質(zhì)量的前提下，可以有效減少優(yōu)化過程所消耗的時(shí)間。

4 小結(jié)

提出的變尺度進(jìn)化的多目標(biāo)圖像分割算法設(shè)計(jì)了先將局部像素合并再在進(jìn)化過程中逐步分解的框架，有效降低了算法的運(yùn)行時(shí)間，同時(shí)保證了圖像分割的質(zhì)量。其中設(shè)計(jì)的改進(jìn)連接度指標(biāo)對噪聲和少量像素所構(gòu)成的對象不敏感，從而有效降低了算法所受到的干擾。標(biāo)準(zhǔn)圖像Sailboat的實(shí)驗(yàn)結(jié)果表明了改進(jìn)算法的有效性，其所得分割結(jié)果能識別出圖像中的主要內(nèi)容，具有層次清晰的特點(diǎn)，而且算法消耗的時(shí)間最多減少達(dá)一半以上。

[1] 江成順， 汪先超. 兩相圖像變分分割凸松弛模型快速算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2013，36(5)：1086-1096.

[2] 靳璐， 付夢印. 基于遺傳模糊核聚類的圖像分割 [J]. 模式識別與人工智能，2013，26(1)：205-210.

[3] 任通，程江華，金陽. 一種基于白像素增量比的字幕圖像分割算法[J]. 電視技術(shù)，2014， 38(5)：190-193.

[4] 李永樂，婁靜濤，張茂軍，等. 基于全向總變分最小化的折反射散焦模糊圖像復(fù)原方法[J]. 光學(xué)學(xué)報(bào)， 2013(8)：99-105.

[5] 王璐，胡晰遠(yuǎn)， 彭思龍. 基于分塊的空間變化抖動(dòng)模糊圖像的全局模糊去除[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2012， 24(6)：766-774.

[6] 王冬冬， 張煒， 金國鋒， 等. 尖點(diǎn)突變理論在紅外熱波檢測圖像分割中的應(yīng)用[J]. 紅外與激光工程， 2014， 43(3)：1009-1015.

[7] 李磊， 金良海， 宋恩民. 基于區(qū)域合并和圖割的非監(jiān)督彩色圖像分割算法[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版， 2013， 41(12)： 44-47.

[8] SHIRAKAWA S， NAGAO T. Evolutionary image segmentation based on multiobjective clustering[C]//Proc. 2009 IEEE Congress on Evolutionary Computation. NY， USA：IEEE Press，2009：2466-2473.

[9] BANDYOPADHYAY S， MAULIK U， MUKHOPADHYAY A. Multiobjective genetic clustering for pixel classification in remote sensing imagery [J]. IEEE Trans. Geoscience and Remote Sensing，2007，45(5)：1506-1511.

[10] HANDL J，KNOWLES J. An evolutionary approach to multiobjective clustering[J]. IEEE Trans. Evolutionary Computation，2007，11(1)：56-76.

[11] 陳愷，陳芳，戴敏，等. 基于螢火蟲算法的二維熵多閾值快速圖像分割[J]. 光學(xué)精密工程，2014， 22(2)：517-523.

Multi-objective Evolutionary Image Segmentation Algorithm Based on Varying-scale

ZHOU Yuan，ZHOU Yan

(SchoolofComputer，HenanInstituteofEngineering，Zhengzhou451191，China)

Evolutionary computing has some shortages such as high computational cost and single measurement when it is used in the field of image processing. Hence，a novel multi-objective evolutionary image segmentation algorithm based on varying scale is proposed. The algorithm regards different regions of image as one pixel in different stages of evolution so that the image is segmented in different scales and the total consumed time is reduced. The transition moments among different scales are controlled by monitoring the variation of important solutions. On the other hand of measurement， a multi-objective version of compactness and connectivity is used to well estimate the image’s quality，wherein the connectivity is modified by checking the continuity of cluster label among neighboring pixels. This modification can effectively suppress the influence of noise and small clusters. Experimental results on standard images of “sailboat” and “terra” show that the proposed algorithm can well distinguish different patterns in the images and the time consumed is remarkable reduced to 48.08%～55.53%of those in other algorithms.

evolutionary computing；multi-objective；image segmentation；varying-scale；connectivity

TP391.41

A

10.16280/j.videoe.2015.17.006

2014-11-12

【本文獻(xiàn)信息】周苑，周巖.基于變尺度進(jìn)化的多目標(biāo)圖像分割算法[J].電視技術(shù),2015，39(17).

周 苑(1978— )，女，講師，碩士，主要研究方向?yàn)槎嗝襟w技術(shù)與信息處理；

周 巖(1981— )，女，講師，碩士，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用與數(shù)據(jù)庫技術(shù)。

責(zé)任編輯：時(shí) 雯