余洪山 張文豪 楊振耕 李松松 萬琴 林安平

摘 要：基于超像素的傳統(tǒng)圖像分割方法在邊緣分割的一致性、計(jì)算效率和融合算法的自適應(yīng)性等方面仍存在諸多問題. 文章結(jié)合國內(nèi)外相關(guān)研究進(jìn)展，提出了一種新型超像素融合的圖像分割方法. 方法采用ERS超像素過分割算法，以強(qiáng)度、梯度直方圖作為超像素特征，并采取EMD方法計(jì)算特征距離，通過混合Weibull模型獲取融合自適應(yīng)閾值，進(jìn)而完成分割. 算法時(shí)間復(fù)雜度降至為O（N），分割過程中不需要手動(dòng)選取待分割區(qū)域，有效提高了算法的自適應(yīng)性. 實(shí)驗(yàn)結(jié)果表明本方法在分割邊界準(zhǔn)確度和處理效率方面優(yōu)于現(xiàn)有方法.

關(guān)鍵詞：超像素；區(qū)域融合；陸地移動(dòng)距離；混合Weibull模型；圖像分割

中圖分類號(hào)：TP273 文獻(xiàn)標(biāo)志碼：A

Abstract：Traditional image segmentation methods based on superpixel still have many problems in terms of consistency of edge segmentation， computational efficiency and adaptability of merging algorithms. We combine domestic and foreign research advances and propose a novel superpixel merging image segmentation method， which adopts ERS superpixel oversegmentation algorithm and uses intensity and gradient histogram as superpixel features. Additionally， EMD method is used to calculate feature distance and the merging self-adaptive threshold is obtained by mixing Weibull model to complete the segmentation. As a result， the time complexity of proposed algorithm is reduced to O（N）， and the segmentation process is not required to manually select the region to be segmented. Compared with current methods， experiment results show that the proposed method has better performance on boundary accuracy and processing efficiency.

Key words：superpixel；region merging；earth movers distance；weibull mixture model；image segmentation

圖像分割是利用顏色、紋理和灰度等特征將圖像分割成一定數(shù)量的符合人類視覺感知分類的區(qū)域. 由于自然圖像中場景的復(fù)雜性，加之人的視覺感知上的主觀性，人們對(duì)圖像場景理解不盡相同，因此圖像分割一直是計(jì)算機(jī)視覺中的一個(gè)難點(diǎn). 傳統(tǒng)方法以像素為基本處理單元，使得算法時(shí)間消耗大、效率低. 超像素是指具有相似紋理、顏色和亮度等特征的相鄰像素構(gòu)成的圖像塊[1]，它利用像素之間特征的相似程度將像素分組，在很大程度上降低了后續(xù)圖像處理任務(wù)的復(fù)雜度. 然而超像素分割會(huì)對(duì)圖像產(chǎn)生過分割，并不能達(dá)到符合人的視覺感知的分割結(jié)果. 超像素算法多用于圖像分割預(yù)處理，在后續(xù)圖像處理中用超像素來代替像素，大大降低了時(shí)間的消耗.

目前，基于超像素融合的圖像分割研究開始獲得越來越多的關(guān)注，典型方案有基于SLIC或Normalized cuts產(chǎn)生超像素過分割，然后提取超像素的特征（顏色、紋理和直方圖等），再基于一定的相似性度量標(biāo)準(zhǔn)計(jì)算相鄰兩個(gè)超像素的特征相似性距離. Hsu C Y等[2]提出了基于譜聚類的融合策略，該方法通過對(duì)SLIC 產(chǎn)生的超像素進(jìn)行譜聚類取得了較高的效率，但其對(duì)于復(fù)雜場景的分割結(jié)果不夠理想. Song X等[3]采用了基于分層超像素的區(qū)域融合策略-MSRM（maximal similarity based region merging）[4]，針對(duì)前景對(duì)象很少的圖像，該方法可以得到較好的分割結(jié)果，但需要人為給定前景對(duì)象所在的大致矩形區(qū)域. 當(dāng)場景前景對(duì)象很多且分散時(shí)，該算法將很難處理，因此存在很大的局限性. Han B等[5]利用Normalized cuts[6]產(chǎn)生超像素，基于直方圖的相似性度量計(jì)算相鄰超像素間的非相似性距離來完成對(duì)圖像的分割. 該方法雖然對(duì)相似的超像素進(jìn)行了融合，但是融合比較保守導(dǎo)致分割結(jié)果過于細(xì)化，即在明顯應(yīng)該分割為一個(gè)對(duì)象的區(qū)域中存在沒有融合的超像素邊界. 綜上所述，目前基于超像素融合的圖像分割方案在邊緣分割的一致性、特征相似性度量的可靠性、計(jì)算效率和融合算法的自適應(yīng)性方面仍需進(jìn)一步改善.

針對(duì)上述問題，本文結(jié)合國內(nèi)外相關(guān)研究進(jìn)展，提出了一種改進(jìn)超像素融合的圖像分割方法. 主要改進(jìn)如下：1）本文采用ERS（entropy rate superpixel）算法生成與真實(shí)邊緣一致性更佳的超像素圖像；2）選用穩(wěn)定性好且計(jì)算簡易的直方圖特征（強(qiáng)度、顏色及方向直方圖），并采用陸地移動(dòng)距離EMD（Earth Movers distance）計(jì)算超像素節(jié)點(diǎn)間相似性，以適應(yīng)多種結(jié)構(gòu)尺寸；3）采用Weibull 模型對(duì)相鄰超像素的EMD 分布進(jìn)行估計(jì)，獲取融合處理的自適應(yīng)閾值，從而提高了本文算法的魯棒性. 本文算法時(shí)間復(fù)雜度為O（N），處理過程中不需要手動(dòng)選取待分割區(qū)域，分割結(jié)果的邊界準(zhǔn)確率和處理效率均具有明顯的提高.

1 改進(jìn)的超像素融合圖像分割方法

如圖1 所示，本文提出的超像素融合圖像分割方法可劃分為三部分：1）超像素過分割方法選擇及圖像預(yù)分割；2）以超像素節(jié)點(diǎn)為單位，求取強(qiáng)度、顏色以及方向（梯度）的特征直方圖，基于特征相似性距離EMD模型，計(jì)算相鄰節(jié)點(diǎn)各自特征直方圖之間的相似性距離；3）建立Weibull 混合模型（Weibull mixture model），對(duì)模型中的參數(shù)進(jìn)行估計(jì)，確定節(jié)點(diǎn)特征相似性距離閾值γf ，并根據(jù)其進(jìn)行超像素融合.

1.1 基于超像素算法的圖像預(yù)分割

1.1.1 超像素算法選擇

目前，超像素算法主要分為兩大類：基于圖論的算法和基于梯度上升的算法.超像素的評(píng)價(jià)標(biāo)準(zhǔn)[7]主要包括：1）邊緣貼合度；2）緊密度；3）計(jì)算效率等. 邊緣貼合度指的是超像素邊緣與真值邊沿的吻合程度. 某些超像素方法雖然可以產(chǎn)生超像素，但是超像素的邊緣可能穿過場景中物體的實(shí)際邊緣. 緊密度反映了超像素形狀是否規(guī)則以及邊緣平滑程度. 常見的超像素算法性能比較[7]如表1 所示（使用公測(cè)數(shù)據(jù)集Berkeley dataset[8]中圖片進(jìn)行測(cè)試，其中邊緣貼合度通過邊界召回率boundary recall[7]反映）.

1.2 特征提取與相似性度量

1.2.1 超像素節(jié)點(diǎn)特征提取

在二維彩色圖像中，顏色、強(qiáng)度以及方向梯度是三種常用且易提取的直方圖特征. 超像素是一定范圍內(nèi)像素點(diǎn)的集合，因此本文選取強(qiáng)度直方圖、顏色直方圖和方向直方圖特征作為超像素節(jié)點(diǎn)特征.強(qiáng)度直方圖是一個(gè)1維256區(qū)間的直方圖，顏色直方圖是由色調(diào)（hue）和飽和度（saturation）（HSV顏色空間中）構(gòu)成的76*76（顏色位數(shù)為8位）的2維直方圖，梯度直方圖是用方向梯度（即垂直方向梯度與水平方向梯度的反正切）構(gòu)成的1 維的360 區(qū)間的直方圖，這個(gè)特征與HOG 特征類似. 為便于計(jì)算處理，算法將所有的特征直方圖歸一化處理.

1.2.2 基于EMD的相似性度量

1）EMD度量標(biāo)準(zhǔn)

為了計(jì)算上述特征直方圖相似性從而為超像素融合提供判斷依據(jù)，本文采用EMD作為相似性度量標(biāo)準(zhǔn). EMD是一種在某種區(qū)域兩個(gè)概率分布距離的度量，即被熟知的Wasserstein度量標(biāo)準(zhǔn). 如果兩個(gè)分布被看作在區(qū)域上兩種不同方式堆積一定數(shù)量的山堆，那么EMD是把一堆變成另一堆所需要移動(dòng)單位小塊最小的距離之和.

2.2 Weibull模型的有效性分析

為了驗(yàn)證本文算法加入Weibull模型的有效性，本文另通過手動(dòng)選取相似性閾值γf ，對(duì)不同場景圖像進(jìn)行超像素融合實(shí)驗(yàn). 實(shí)驗(yàn)結(jié)果（超像素融合后的均值填充效果圖）如圖6所示.

圖6中最右側(cè)為與真實(shí)場景最一致的融合效果圖. 由實(shí)驗(yàn)結(jié)果可知，要得到良好的融合效果，必須手動(dòng)調(diào)節(jié)多次閾值直至結(jié)果滿意為止. 而且，對(duì)于不同場景的圖像，其最佳相似性閾值不盡相同.

加入Weibull模型后，最佳相似性閾值可由Weibull分布估計(jì)求得. 與上述手動(dòng)調(diào)節(jié)閾值相比，具有更好的靈活性，避免了繁瑣的調(diào)節(jié)閾值的步驟，可方便應(yīng)用于不同的場景圖像，極大地提高了算法的魯棒性.

2.3 分割結(jié)果直觀效果對(duì)比

為了驗(yàn)證本文算法的分割效果，本文選取了2種常用的基于超像素融合的分割算法并與其進(jìn)行了對(duì)比，分別為DBSCN算法[18]對(duì)SLIC超像素融合的分割方法（SLICDBSCN），基于原型對(duì)象（protoobject）的分割方法[12]（PO）.

不同算法的實(shí)驗(yàn)結(jié)果對(duì)比如圖7所示，其中（a）為原始圖像，（b）、（c）和 （d）分別為SLICDBSCN算法、PO算法以及本文算法的分割結(jié)果. 超像素?cái)?shù)目均設(shè)定為600. 由圖7中分割結(jié)果的對(duì)比可得，在產(chǎn)生相同超像素個(gè)數(shù)的情況下，本文方法得到的分割結(jié)果在保持邊界的性能上優(yōu)于SLICDBSCN算法和PO方法，分割結(jié)果視覺效果上更符合人的視覺感知. 圖8為圖7的局部細(xì)節(jié)放大對(duì)比. 進(jìn)一步從分割細(xì)節(jié)上進(jìn)行了對(duì)比說明.

2.4 分割結(jié)果性能量化對(duì)比

為了對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行量化評(píng)價(jià)，本文采用了3種量化指標(biāo)：1）PRI（Probabilistic Rand Index）[19]，它統(tǒng)計(jì)了實(shí)驗(yàn)的分割結(jié)果的邊界標(biāo)記像素與真實(shí)分割結(jié)果保持一致的數(shù)目，即分割結(jié)果的邊緣準(zhǔn)確度；2）VOI（Variation of Information）[20]，該指標(biāo)針對(duì)兩個(gè)類之間的信息的不同進(jìn)行了距離度量；3）BDE（Boundary Displacement Error）[21]，該指標(biāo)表示分割結(jié)果與真值之間的區(qū)域邊界的平均位移.

從以上指標(biāo)可以得出，PRI越高，VOI，BDE越小，則分割結(jié)果的性能越好. 本文分割方法與Normalized cut（Ncut）[6]，Mean Shift[22]，Ultrametric Contour Maps（UCM）[23]，Segmentation by Aggregating Superpixels （SAS）[24]，SLICDBSCN算法以及PO算法的量化比較如表2所示，其中文獻(xiàn)[6]、[22]、[23]、[24]的性能量化數(shù)據(jù)來自于文獻(xiàn)[2]，實(shí)驗(yàn)數(shù)據(jù)集采用BSD.

由表看出，本文算法具有較高的時(shí)間效率，相較于SLICDBSCN算法具有明顯的優(yōu)勢(shì)，與PO算法相差無幾. 隨著超像素的數(shù)目增多，時(shí)間消耗亦隨之增加，雖然N越大，超像素對(duì)邊緣的貼合度越好，但是并不是對(duì)任何圖像都將超像素的數(shù)目N設(shè)置的越大越好，對(duì)于圖像尺寸較小時(shí)，如BSD數(shù)據(jù)集的尺寸為481×321，N設(shè)置600即可獲得很好的分割結(jié)果.

3 結(jié) 論

本文在圖像預(yù)處理階段（超像素分割）采用了ERS算法，通過產(chǎn)生數(shù)目更少的超像素便可達(dá)到更好的邊緣保持性能，這一點(diǎn)對(duì)后續(xù)的分割至關(guān)重要.

此外，本文的算法充分運(yùn)用了統(tǒng)計(jì)學(xué)，距離度量采用EMD ，通過 Weibull分布建立EMD統(tǒng)計(jì)模型.因此，該方法的實(shí)驗(yàn)結(jié)果具有很高的邊緣準(zhǔn)確性. 本文采用AIC信息準(zhǔn)則確定自適應(yīng)閾值，無需手動(dòng)調(diào)節(jié)，從而提高了超像素聚類的魯棒性，使得該算法能夠適應(yīng)復(fù)雜場景的分割. 在時(shí)間消耗上，本文的分割方法首先采用ERS超像素過分割，使得后續(xù)的融合都是基于超像素級(jí)的. 另外，本文的分割方法兩次利用了“圖”的結(jié)構(gòu)（ERS為第一次利用“圖”結(jié)構(gòu)，然后基于超像素過分割的結(jié)果第二次建立“圖”的結(jié)構(gòu)），這使得我們的算法具有很好的存儲(chǔ)效率.

與其他經(jīng)典的傳統(tǒng)分割算法（[22]，[23]，[24]）以及基于超像素融合的分割方法（[2]，[12]，[18]等）的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，本文對(duì)圖像的分割結(jié)果性能優(yōu)于其他方法，特別是在圖像場景比較復(fù)雜的情況下，本文的分割結(jié)果對(duì)物體的邊界保持得非常好. 在對(duì)超像素融合后，將各個(gè)區(qū)域進(jìn)行均值賦色，最后生成的分割圖像的視覺效果和人類視覺的感知一致.

參考文獻(xiàn)

[1] MALIK J. Learning a classification model for segmentation[J]. Proc Iccv， 2003，1（1）：10-17.

[2] HSU C Y， DING J J. Efficient image segmentation algorithm using SLIC superpixels and boundaryfocused region merging[C]// Communications and Signal Processing. Melmaruvathur： IEEE， 2014：1-5.

[3] SONG X， ZHOU L， LI Z， et al. Interactive image segmentation based on hierarchical superpixels initialization and region merging[C]// International Congress on Image and Signal Processing. Dalian： IEEE， 2015： 410-414.

[4] NING J， ZHANG L， ZHANG D， et al. Interactive image segmentation by maximal similarity based region merging[J]. Pattern Recognition， 2010， 43（2）： 445-456.

[5] HAN B， YAN J. A novel segmentation approach for color images with progressive superpixel merging[C]// International Conference on Computer Science and Network Technology. Changchun： IEEE， 2013： 433-437.

[6] SHI J， MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888-905.

[7] ACHANTA R， SHAJI A， SMITH K， et al. SLIC superpixels compared to stateoftheart superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（11）： 2274-2282.

[8] 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]// International Conference on Computer Vision.Vancouver： IEEE， 2001， 2： 416-423.

[9] LIU M Y， TUZEL O， RAMALINGAM S， et al. Entropy rate superpixel segmentation[C]// Computer Vision and Pattern Recognition.Colorado ： IEEE， 2011： 2097-2104.

[10]RUBNER Y， TOMASI C， GUIBAS L J. A metric for distributions with applications to image databases[C]// International Conference on Computer Vision. Bombay： IEEE Computer Society， 1998：59.

[11]LEVINA E， BICKEL P. The earth mover's distance is the mallows distance： Some insights from statistics[C]//

Eighth IEEE International Conference on Computer Vision. Vancouver： IEEE， 2001， 2： 251-256.

[12]BURGHOUTS G J， SMEULDERS A W M， GEUSEBROEK J M. The distribution family of similarity distances[C]//

Conference on Neural Information Processing Systems.Vancouver： DBLP， 2009：201-208.

[13]YU C P， HUA W Y， SAMARAS D， et al. Modeling clutter perception using parametric protoobject partitioning[C]// International Conference on Neural Information Processing Systems. Lake Tahoe： Curran Associates Inc， 2013：118-126.

[14]NELDER J A， MEAD R. A simplex method for function minimization[J]. The Computer Journal， 1965， 7（4）： 308-313.

[15]LAGARIAS J C， REEDS J A， WRIGHT M H， et al. Convergence properties of the NelderMead simplex method in low dimensions[J]. SIAM Journal on Optimization， 1998， 9（1）： 112-147.

[16]LUMLEY T， SCOTT A. AIC and BIC for modeling with complex survey data[J]. Journal of Survey Statistics and Methodology， 2015， 3（1）： 1-18.

[17]XIAO J， HAYS J， EHINGER K A， et al. Sun database： Largescale scene recognition from abbey to zoo[C]// Computer Vision and Pattern Recognition. San Francisco： IEEE， 2010：3485-3492.

[18]ESTER M. A densitybased algorithm for discovering clusters in large spatial Databases with Noise [C]// International Conference on Knowledge Discovery and Data Mining. Portland： AAAI Press， 1996：226-231.

[19]UNNIKRISHNAN R， PANTOFARU C， HEBERT M. Toward objective evaluation of image segmentation algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2007， 29（6）：929.

[20]MEIL M. Comparing clusterings： an axiomatic view[C]//Proceedings of the 22nd International Conference on Machine Learning. Bonn： DBLP， 2005： 577-584.

[21]FREIXENET J， MUOZ X， RABA D， et al. Yet another survey on image segmentation： region and boundary information integration[J]. Lecture Notes in Computer Science， 2002， 2352：21-25.

[22]COMANICIU D， MEER P. Mean shift： A robust approach toward feature space analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（5）： 603-619.

[23]ARBELAEZ P， MAIRE M， FOWLKES C， et al. From contours to regions： An empirical evaluation[C]//Computer Vision and Pattern Recognition. Miami： IEEE， 2009： 2294-2301.

[24]LI Z， WU X M， CHANG S F. Segmentation using superpixels： A bipartite graph partitioning approach[C]// Computer Vision and Pattern Recognition. Rhode Island： IEEE， 2012：789-796.