基于變尺度進化的多目標圖像分割算法

周 苑，周 巖

(河南工程學院 計算機學院，河南 鄭州 451191)

基于變尺度進化的多目標圖像分割算法

周 苑，周 巖

(河南工程學院 計算機學院，河南 鄭州 451191)

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

進化計算；多目標；圖像分割；變尺度；連接度

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

1 總體架構變尺度進化框架的設計

本文所提變尺度進化包含合并、進化、判別和分解4個步驟。框架如圖1所示。

圖1 變尺度進化框架的示意圖

圖2 區域合并示意圖

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

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

圖3 關鍵解示意圖

分解步驟是對于當前尺度下的每個圖像區域，分別以橫向和縱向的中間位置為邊界，將其劃分為4個子區域。然后計算每個子區域像素的R，G，B均值，再對各個子區域相鄰邊界位置的像素進行局部調整。調整的方式為：對于邊界位置的每一個像素，計算其與各個子區域R，G，B均值的歐氏距離，按照距離最近原則劃歸新的子區域，最后更新各子區域的R，G，B均值。經過分解以后圖像中的區域數量將變為原先的4倍，當某一區域的像素個數等于或少于4個時，則直接分解為單個像素。

2 多目標圖像分割算法的設計

2.1 多目標函數的設計

本文所設計的多目標函數為2個，稱為緊致度指標和連接度指標。其中緊致度指標與文獻[8]所提類似，如式(1)所示

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

(2)

(3)

圖4 噪聲和小樣本對連接度指標的干擾示意圖

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

2.2 算法描述

3 實驗結果與分析

為了驗證算法的有效性，選取標準圖像Sailboat和Terra做測試，如圖5所示。

圖5 用于測試的標準圖像

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

3.1 參數設置

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

3.2 分割效果對比與分析

3種算法在Sailboat和Terra圖像上的測試結果，如圖6和圖7所示。圖6和圖7中，子圖a～c為本文所提算法MEISV在優化結束時所得3個關鍵解的分割結果，子圖d～f為對比算法CMEISV所得關鍵解的分割結果，子圖g則為文獻[8]所提供的MOCKIS的最佳分割結果。

圖6 3種算法對圖像Sailboat的分割結果對比

圖7 3種算法對圖像Terra的分割結果對比

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

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

3.3 運算時間對比

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

表1 3種算法的計算時間對比

s

圖像名稱耗時MEISVMEISMOCKISSailboat53211106710889Terra71331284513015

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

4 小結

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

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

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

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

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

[5] 王璐，胡晰遠， 彭思龍. 基于分塊的空間變化抖動模糊圖像的全局模糊去除[J]. 計算機輔助設計與圖形學學報， 2012， 24(6)：766-774.

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

[7] 李磊， 金良海， 宋恩民. 基于區域合并和圖割的非監督彩色圖像分割算法[J]. 華中科技大學學報：自然科學版， 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]. 光學精密工程，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

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

周 苑(1978— )，女，講師，碩士，主要研究方向為多媒體技術與信息處理；

周 巖(1981— )，女，講師，碩士，主要研究方向為計算機應用與數據庫技術。

責任編輯：時 雯