趙 鳳, 惠房臣, 韓文超

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

基于過分割的多目標閾值圖像分割算法

趙 鳳, 惠房臣, 韓文超

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

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

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

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

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

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

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

1 基于過分割的多目標閾值分割

1.1 分水嶺過分割

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

1.2 多目標閾值分割

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

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

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

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

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

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

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

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

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

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

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

其中

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

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

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

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

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

其中

分別為圖像背景的熵和目標的熵。

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

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

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

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

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

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

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

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

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

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

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

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

1.3 算法流程

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

圖1 MOTIS_OS算法流程

2 實驗結(jié)果與分析

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

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

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

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

圖2 實驗圖像

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

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

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

(a) 標準分割 (b) 最大類間方差法

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

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

(a) 標準分割 (b) 最大類間方差法

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

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

(a) 標準分割 (b) 最大類間方差法

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

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

(a) 標準分割 (b) 最大類間方差法

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

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

(a) 標準分割 (b) 最大類間方差法

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

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

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

每幅Berkeley圖像都有標準分割結(jié)果，故可采用分割準確率[15]來定量評價各個算法的性能。各個算法在5幅Berkeley圖像上獲得的分割準確率如表1所示。

表1 各算法分割準確率對比

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

3 結(jié)語

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

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

[1] 謝勰, 王輝, 張雪鋒. 圖像閾值分割技術(shù)中的部分和算法綜述[J]. 西安郵電學院學報, 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]. 西安郵電學院學報,2012,17(3): 10-14.

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

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

[7] 張蕾蕾. 半局部凸多目標半無限規(guī)劃的對偶性[J]. 西安郵電學院學報, 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] 余旺盛, 侯志強, 宋建軍. 基于標記分水嶺和區(qū)域合并的彩色圖像分割[J]. 電子學報, 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.

[責任編輯:瑞金]

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

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

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

10.13682/j.issn.2095-6533.2015.03.010

TP751

A

2095-6533(2015)03-0060-05