趙 鳳, 惠房臣, 韓文超

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

基于過(guò)分割的多目標(biāo)閾值圖像分割算法

趙 鳳, 惠房臣, 韓文超

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

提出一種基于過(guò)分割的多目標(biāo)閾值圖像分割算法。使用分水嶺算法獲得待分割圖像的過(guò)分割區(qū)域和分割邊界，將類間方差函數(shù)和熵函數(shù)作為優(yōu)化目標(biāo)函數(shù)，采用多目標(biāo)閾值算法對(duì)區(qū)域的代表點(diǎn)及分割邊界上的像素進(jìn)行劃分，再將區(qū)域代表點(diǎn)的劃分結(jié)果擴(kuò)展到各區(qū)域中，以獲得整幅圖像的分割結(jié)果。在多幅Berkeley圖像上進(jìn)行分割測(cè)試，并以分割準(zhǔn)確率作為算法性能的評(píng)價(jià)指標(biāo)，結(jié)果顯示，新方法在大多數(shù)情況下能夠獲得高于最大類間方差法和最大熵法的分割準(zhǔn)確率，此外，由于圖像區(qū)域信息的使用，使得圖像目標(biāo)能夠較為完整地從背景中分離出來(lái)。

多目標(biāo)優(yōu)化；閾值分割；類間方差；熵；過(guò)分割

在圖像分割的諸多方法中，閾值化技術(shù)[1-4]是一類簡(jiǎn)單有效的方法，其中，最大類間方差法[2]和最大熵法[3]是兩個(gè)最常用的分割算法。

最大類間方差法原理簡(jiǎn)單，容易實(shí)現(xiàn)，對(duì)于大多數(shù)圖像都能得到較好的分割效果。然而，當(dāng)圖像中目標(biāo)與背景的面積相差很大，或者圖像直方圖中沒(méi)有明顯的雙峰時(shí)，最大類間方差法的分割效果不佳。最大熵法在圖像的總體輪廓和邊界細(xì)節(jié)保持方面比較好，但當(dāng)目標(biāo)和背景的區(qū)別不是很明顯時(shí)，該方法無(wú)法獲得理想的分割效果。最大類間方差法和最大熵法的上述缺點(diǎn)是因?yàn)闆](méi)有利用圖像的區(qū)域信息造成的。

不同的閾值準(zhǔn)則具有不同的特性，可以在多個(gè)閾值準(zhǔn)則下尋求均衡，采用多目標(biāo)優(yōu)化來(lái)解決圖像分割問(wèn)題。多目標(biāo)優(yōu)化算法是函數(shù)優(yōu)化領(lǐng)域的一個(gè)研究熱點(diǎn)[5-8]，它在多個(gè)目標(biāo)間協(xié)調(diào)權(quán)衡，使得所有目標(biāo)函數(shù)盡可能達(dá)到最優(yōu)。

針對(duì)閾值分割方法未考慮圖像區(qū)域信息及準(zhǔn)則單一的問(wèn)題，本文擬給出一種基于過(guò)分割的多目標(biāo)閾值圖像分割(Multi-objective thresholding image segmentation based on over-segmentation，MOTIS_OS)算法，即引入分水嶺算法[9]，獲得圖像的過(guò)分割區(qū)域和分割邊界，以保證分割結(jié)果中保留圖像中的區(qū)域信息和邊緣信息，并采用多目標(biāo)優(yōu)化算法[8]在類間方差和熵兩個(gè)閾值準(zhǔn)則下，對(duì)獲得的過(guò)分割區(qū)域代表點(diǎn)和分割邊界上的像素進(jìn)行劃分，進(jìn)而將區(qū)域代表點(diǎn)的劃分結(jié)果擴(kuò)展到各區(qū)域中，獲得整幅圖像的分割結(jié)果。

1 基于過(guò)分割的多目標(biāo)閾值分割

1.1 分水嶺過(guò)分割

分水嶺算法是一種基于數(shù)學(xué)形態(tài)學(xué)的分割方法[9-11]。該算法簡(jiǎn)單、速度快，且對(duì)圖像的微弱邊緣比較敏感。MOTIS_OS算法采用分水嶺算法對(duì)圖像進(jìn)行過(guò)分割，將每個(gè)分割區(qū)域的灰度均值作為區(qū)域代表點(diǎn)，將所有區(qū)域的代表點(diǎn)和位于分水嶺上的像素灰度作為后續(xù)處理的數(shù)據(jù)集。分水嶺過(guò)分割的目的是為了保留圖像的區(qū)域信息和邊緣信息。

1.2 多目標(biāo)閾值分割

為了兼顧類間方差和熵閾值準(zhǔn)則的優(yōu)良特性[2-3]，采用第二代非支配排序遺傳算法(Non-dominated sorting genetic algorithm II，NSGA-II)[8]同時(shí)優(yōu)化這兩個(gè)閾值準(zhǔn)則，實(shí)現(xiàn)分水嶺過(guò)分割獲得的區(qū)域代表點(diǎn)及分割邊界上像素的劃分。

在多目標(biāo)優(yōu)化問(wèn)題中，很難找到一個(gè)解使得所有目標(biāo)函數(shù)同時(shí)最優(yōu)，因此多目標(biāo)優(yōu)化最終所得的是一個(gè)折衷解的集合，稱為Pareto最優(yōu)解集(或非支配解集)。對(duì)于兩個(gè)解x1和x2，稱為x1Pareto支配x2，當(dāng)且僅當(dāng)對(duì)所有子目標(biāo)，x1不比x2差，且至少存在一個(gè)子目標(biāo)，使得x1比x2好。一個(gè)解x*被稱為Pareto最優(yōu)解(或非支配解)，當(dāng)且僅當(dāng)不存在其他解xPareto支配x*。所有Pareto最優(yōu)解構(gòu)成的集合稱為Pareto最優(yōu)解集。

多目標(biāo)閾值分割算法的基本要素包括染色體編碼、種群初始化、適應(yīng)度函數(shù)設(shè)計(jì)、非支配排序與擁擠距離計(jì)算、選擇、交叉與變異操作、精英策略和最優(yōu)解的選擇。

(1) 染色體編碼與種群初始化

染色體表示問(wèn)題的可能潛在解。MOTIS_OS算法對(duì)灰度閾值進(jìn)行編碼，編碼方式采用實(shí)數(shù)制編碼，編碼范圍是0～255。

初始種群中每個(gè)染色體按照如下方式產(chǎn)生：隨機(jī)產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)d，則該染色體為[255d]。設(shè)定種群大小為80，最大代數(shù)G=100。

(2) 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來(lái)描述種群中染色體的性能。MOTIS_OS算法采用類間方差函數(shù)和熵函數(shù)作為多目標(biāo)優(yōu)化的兩個(gè)適應(yīng)度函數(shù)。

設(shè)N表示一幅圖像中包含的像素?cái)?shù)目，[0,L]表示圖像灰度級(jí)范圍，ni表示灰度級(jí)為i的像素個(gè)數(shù)，則灰度級(jí)i的出現(xiàn)概率

假設(shè)t表示選取的圖像閾值，類間方差函數(shù)主要考察該閾值下獲得的圖像目標(biāo)和背景這兩個(gè)類之間的方差，定義為

f1(t)=W0(u0-uT)2+W1(u1-uT)2,

其中

分別表示圖像背景和目標(biāo)出現(xiàn)的概率，而

分別表示圖像背景的灰度均值、圖像目標(biāo)的灰度均值和整幅圖像的灰度均值。

通常利用類間方差f1(t)的最大化來(lái)獲取最佳的閾值t*。

假設(shè)t表示選取的圖像閾值，熵函數(shù)主要考察該閾值下獲得的圖像目標(biāo)和背景的熵之和，定義為

f2(t)=H0(t)+H1(t),

其中

分別為圖像背景的熵和目標(biāo)的熵。

某一閾值t對(duì)應(yīng)的熵函數(shù)f2(t)越大，則認(rèn)為分割結(jié)果保留原圖像中的信息越多，則該閾值t越優(yōu)。

(3) 非支配排序與擁擠距離計(jì)算

非支配排序[8]是將種群按支配關(guān)系分成若干層，第一層為當(dāng)代種群中非支配個(gè)體的集合，該集合中所有個(gè)體的序值均為1；第二層是種群去掉第一層個(gè)體后非支配個(gè)體的集合，該集合中所有個(gè)體的序值均為2，以此類推，將種群中所有個(gè)體排序。

擁擠距離[8]用于比較非支配排序后同級(jí)中不同個(gè)體的性能。某個(gè)個(gè)體的擁擠距離是通過(guò)計(jì)算與該個(gè)體相鄰的兩個(gè)個(gè)體的每個(gè)目標(biāo)函數(shù)的距離之和獲得的。

(4) 選擇、交叉與變異操作

選擇就是挑選染色體產(chǎn)生交配池的過(guò)程，為交叉和變異操作準(zhǔn)備父代染色體。MOTIS_OS算法采用擁擠二進(jìn)制錦標(biāo)賽選擇方法[8]產(chǎn)生交配池，即采用錦標(biāo)賽辦法，按照個(gè)體的非支配排序等級(jí)和擁擠距離從初始種群中選擇出一半數(shù)量的個(gè)體作為父代。

交叉操作是按照一定的交叉概率對(duì)兩個(gè)染色體進(jìn)行交配重組，產(chǎn)生新的染色體。設(shè)置交叉概率為0.9，交叉操作采用模擬二進(jìn)制交叉方法[12]，其中，交叉分布指數(shù)設(shè)置為20。

變異操作是按照一定的變異概率對(duì)染色體的基因位進(jìn)行修改，可在種群中引入缺失的基因，以實(shí)現(xiàn)對(duì)可行解空間的全局搜索。設(shè)置變異概率為0.1，變異操作采用多項(xiàng)式變異[13]，其中，變異分布指數(shù)設(shè)置為20。

(5) 精英策略和最優(yōu)解的選擇

采用NSGA-II算法作為多目標(biāo)框架來(lái)解決閾值分割問(wèn)題。眾所周知，NSGA-II算法最具特色的部分就是它的精英操作。通過(guò)精英操作，父代和子代中的非支配解會(huì)遺傳到下一代種群中，因此，迄今為止發(fā)現(xiàn)的最優(yōu)解就會(huì)被保留下來(lái)。

算法最終獲得的是由非支配解構(gòu)成的一個(gè)集合。在理論上，所有非支配解都同等重要，然而，在實(shí)際應(yīng)用中，用戶往往只需要一個(gè)解。根據(jù)多次實(shí)驗(yàn)發(fā)現(xiàn)，非支配解集中的前兩個(gè)解對(duì)應(yīng)的視覺(jué)分割效果較好，故可從中選擇一個(gè)作為最終解。

按照最優(yōu)解(即最優(yōu)閾值)對(duì)區(qū)域代表點(diǎn)及分水嶺邊界上的像素進(jìn)行劃分，并將區(qū)域代表點(diǎn)的劃分結(jié)果擴(kuò)展到各區(qū)域中，從而獲得整幅圖像的分割結(jié)果。

1.3 算法流程

MOTIS_OS算法的具體流程如圖1所示。

圖1 MOTIS_OS算法流程

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

實(shí)驗(yàn)中采用最大類間方差法和最大熵法作為比較算法。采用5幅Berkeley圖像[14]作為實(shí)驗(yàn)圖像，如圖2所示。5幅圖像的分割結(jié)果分別如圖3至圖7所示，其中，每幅圖像的標(biāo)準(zhǔn)分割結(jié)果在(a)圖中給出，最大類間方差法的分割結(jié)果在(b)圖中給出，最大熵法的分割結(jié)果在(c)圖中給出，MOTIS_OS算法的分割結(jié)果在(d)圖中給出。

如圖3所示，對(duì)于圖像#3096，雖然三種算法都將部分背景錯(cuò)分成了目標(biāo)，但MOTIS_OS算法的錯(cuò)分區(qū)域最小，而且飛機(jī)機(jī)身保持的最好，其分割結(jié)果最接近標(biāo)準(zhǔn)分割結(jié)果。

對(duì)于圖像#42049，最大類間方差法和最大熵法都存在把位于圖像四角處的背景錯(cuò)分為目標(biāo)的現(xiàn)象，MOTIS_OS算法的分割結(jié)果大大改善了這一問(wèn)題，但在樹(shù)枝末端存在細(xì)節(jié)信息丟失的現(xiàn)象，具體結(jié)果可參見(jiàn)圖4。

(a) 圖像#3096(b) 圖像#42049(c) 圖像#135069 (d) 圖像#3063(e) 圖像#8068

圖2 實(shí)驗(yàn)圖像

如圖5所示，最大熵法將圖像#135069的大部分目標(biāo)錯(cuò)分為背景，只分割出了小部分目標(biāo)，最大類間方差法和MOTIS_OS算法的分割結(jié)果比較理想，MOTIS_OS算法在細(xì)節(jié)信息保持上要優(yōu)于最大類間方差法，具體見(jiàn)圖5(c)和圖5(d)。

如圖6所示，最大類間方差法錯(cuò)將圖像#3063的背景分為目標(biāo)飛機(jī)，最大熵法和MOTIS_OS算法的分割結(jié)果比較令人滿意，但最大熵法背景處還存在一些錯(cuò)分點(diǎn)，MOTIS_OS算法在飛機(jī)螺旋槳處有少量信息丟失的問(wèn)題，具體見(jiàn)圖6(c)和圖6(d)。

從圖7可以看出，由于圖像#8086中水中倒影的存在，使得三種算法的分割結(jié)果均不是很理想，最大熵法受水中倒影的影響最大，最大類間方差法存在部分目標(biāo)信息丟失的問(wèn)題，MOTIS_OS算法獲得了相對(duì)較好的分割結(jié)果，具體見(jiàn)圖7(d)。

(a) 標(biāo)準(zhǔn)分割 (b) 最大類間方差法

(c) 最大熵法 (d) MOTIS_OS算法

圖3 圖像#3096分割結(jié)果

(a) 標(biāo)準(zhǔn)分割 (b) 最大類間方差法

(c) 最大熵法 (d) MOTIS_OS算法

圖4 圖像#42049分割結(jié)果

(a) 標(biāo)準(zhǔn)分割 (b) 最大類間方差法

(c) 最大熵法 (d) MOTIS_OS算法

圖5 圖像#135069分割結(jié)果

(a) 標(biāo)準(zhǔn)分割 (b) 最大類間方差法

(c) 最大熵法 (d) MOTIS_OS算法

圖6 圖像#3063分割結(jié)果

(a) 標(biāo)準(zhǔn)分割 (b) 最大類間方差法

(c) 最大熵法 (d) MOTIS_OS算法

圖7 圖像#8068分割結(jié)果

綜合以上分割結(jié)果可以發(fā)現(xiàn)，由于MOTIS_OS算法利用了圖像的區(qū)域信息，使得目標(biāo)能夠較為完整的從背景中提取出來(lái)，在大多數(shù)情況下獲得了優(yōu)于最大類間方差法和最大熵法的視覺(jué)分割效果。

每幅Berkeley圖像都有標(biāo)準(zhǔn)分割結(jié)果，故可采用分割準(zhǔn)確率[15]來(lái)定量評(píng)價(jià)各個(gè)算法的性能。各個(gè)算法在5幅Berkeley圖像上獲得的分割準(zhǔn)確率如表1所示。

表1 各算法分割準(zhǔn)確率對(duì)比

由表1可知，MOTIS_OS算法在圖像#3096、圖像#42049、圖像#135069和圖像#3063上的分割準(zhǔn)確率都是三種算法中最高的；對(duì)于圖像#8068，MOTIS_OS算法的分割準(zhǔn)確率略低于最大類間方差法。表1中數(shù)據(jù)統(tǒng)計(jì)與前面的視覺(jué)評(píng)價(jià)結(jié)果基本一致，表明MOTIS_OS算法的分割性能是比較理想的，能夠在大多數(shù)情況下獲得優(yōu)于最大類間方差法和最大熵法的分割結(jié)果。

3 結(jié)語(yǔ)

提出了一種基于過(guò)分割的多目標(biāo)閾值圖像分割算法，由于圖像區(qū)域信息的使用，使得圖像目標(biāo)能夠較為完整地從背景中分離出來(lái)。在多幅Berkeley圖像上進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，該算法在大多數(shù)情況下能夠獲得高于最大類間方差法和最大熵法的分割準(zhǔn)確率。

該算法的最優(yōu)解是從最后一代非支配解集中按照視覺(jué)分割效果選擇的，因此，最優(yōu)解的自適應(yīng)選擇仍是一個(gè)值得研究的問(wèn)題。此外，該算法僅適用于單閾值分割，如何將算法擴(kuò)展到多閾值分割也值進(jìn)一步研究。

[1] 謝勰, 王輝, 張雪鋒. 圖像閾值分割技術(shù)中的部分和算法綜述[J]. 西安郵電學(xué)院學(xué)報(bào), 2011, 16(3): 1-5.

[2] Otsu N. A threshold selection method from gray-level histograms[J]. IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(1): 62-66.

[3] Kapur J N, Sahoo P K, Wong A K C. A new method for gray-level picture thresholding using the entropy of the histogram[J]. Computer Vision, Graphics and Image Processing, 1985, 29(3): 273-285.

[4] 趙鳳, 范九倫. 融合灰度和非局部空間灰度特征的二維Otsu法[J]. 西安郵電學(xué)院學(xué)報(bào),2012,17(3): 10-14.

[5] 鄭金華. 多目標(biāo)進(jìn)化算法及應(yīng)用[M]. 北京: 科學(xué)出版社, 2010: 21-26.

[6] 公茂果, 焦李成, 楊咚咚, 等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào), 2009, 20(2): 271-289.

[7] 張蕾蕾. 半局部凸多目標(biāo)半無(wú)限規(guī)劃的對(duì)偶性[J]. 西安郵電學(xué)院學(xué)報(bào), 2008, 13(5): 145-147.

[8] Deb K, Agrawal S, Pratab A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//Proceedings of the Parallel Problem Solving from Nature VI Conference. France Paris: Springer, 2000: 849-858.

[9] Vincent L, Soille P. Watersheds in digital space: an efficient algorithm based on immersion simulation[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 1991, 13(6): 583-598.

[10] 余旺盛, 侯志強(qiáng), 宋建軍. 基于標(biāo)記分水嶺和區(qū)域合并的彩色圖像分割[J]. 電子學(xué)報(bào), 2011, 39(5): 1007-1012.

[11] Yang H G, Ahuja N. Automatic segmentation of granular objects in images: combining local density clustering and gradient-barrier watershed[J]. Pattern Recognition, 2014, 47(6): 2266-2279.

[12] Beyer H G, Deb K. On self-adaptive features in real-parameter evolutionary algorithm[J]. IEEE Transactions on Evolutionary Computation, 2001, 5(3): 250-270.

[13] Raghuwanshi M M, Kakde O G. Survey on multiobjective evolutionary and real coded genetic algorithms[C]//Proceedings of the 8th Asia Pacific Symposium on Intelligent and Evolutionary Systems. Australia Cairns: Springer, 2004: 150-161.

[14] Martin D, Fowlkes C, Tal D, et al. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[C]//Proceedings of Eighth IEEE International Conference on Computer Vision. Canada Vancouver: IEEE, 2001: 416-423.

[15] Wu M, Sch?lkopf B. A local learning approach for clustering[C]//Advances in Neural Information Processing Systems. American Cambridge: MIT, 2007: 1529-1536.

[責(zé)任編輯:瑞金]

Multi-objective thresholding image segmentation algorithm based on over-segmentation

ZHAO Feng, HUI Fangchen, HAN Wenchao

(School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

A multi-objective thresholding image segmentation algorithm is presented in this paper based on over-segmentation. The watershed algorithm is firstly used to obtain the over-segmentation regions and boundaries of an image; then the multi-objective thresholding algorithm, which adopts the variance between clusters and the entropy as the objective functions, is used to partition the representative points of the segmentation regions and the pixels on the boundaries; finally the partitioning results of the representative points are extended to their respective segmentation regions to acquire the segmentation result of the whole image. Some Berkeley images are adopted in the segmentation experiment and the segmentation accuracy is used as the evaluation index of algorithm performance. Experimental results show that the new method can obtain higher segmentation accuracy than the maximum variance between clusters method and the maximum entropy method in most cases. Moreover, the object can be more completely partitioned from the background due to utilizing the image region information.

multi-objective optimization, thresholding segmentation, variance between clusters, entropy, over-segmentation

2015-02-05

國(guó)家自然科學(xué)基金資助項(xiàng)目(61102095, 61202153);陜西省科技計(jì)劃資助項(xiàng)目(2014KJXX-72); 陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃資助項(xiàng)目(2012JQ8045, 2014JQ8336); 中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(GK201503063)

趙鳳(1980-)，女，博士，副教授，從事模式識(shí)別、圖像處理和模糊信息處理研究。E-mail: fzhao.xupt@gmail.com 惠房臣(1991-)，男，碩士研究生，研究方向?yàn)樾盘?hào)與信息處理。E-mail: 390620477@qq.com

10.13682/j.issn.2095-6533.2015.03.010

TP751

A

2095-6533(2015)03-0060-05