劉斌，渠星星，陳相庭

（河南大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，開封 475000）

最新的超像素算法研究綜述

劉斌，渠星星，陳相庭

（河南大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，開封 475000）

超像素是指受一定相似性準(zhǔn)則約束的分割區(qū)域，它可以獲取圖像的冗余信息，降低處理圖像的復(fù)雜度，受到越來(lái)越多研究者的關(guān)注。對(duì)最新的超像素分割算法進(jìn)行論述，并對(duì)超像素的應(yīng)用場(chǎng)景進(jìn)行介紹。

超像素；圖像分割；圖像處理

0 引言

圖像分割是將圖像細(xì)分為構(gòu)成它的子區(qū)域，并使同一區(qū)域在灰度、顏色、紋理等特征方有相似性，而在不同的區(qū)域間呈現(xiàn)差異性。圖像分割作為計(jì)算機(jī)視覺領(lǐng)域的基本問題，是圖像理解的重要部分[1]。傳統(tǒng)的分割方法是以像素為基本處理單位，在處理數(shù)據(jù)量很大的圖像時(shí)，計(jì)算效率往往很低。2003年，Ren等人[2]提出了超像素的概念，所謂超像素，是指圖像中局部的、具有連續(xù)性，能夠保持圖像局部結(jié)構(gòu)特征的子區(qū)域[3]。超想素分割技術(shù)多用在圖像的預(yù)處理階段，用超像素替代圖像原有的像素，這樣可以獲取圖像的冗余信息，降低處理圖像的復(fù)雜度，同時(shí)還可以避免欠分割。

目前的超像素分割算法大概可以分為兩類:基于圖論的方法和基于梯度上升的方法?；趫D論的方法基本思想是用圖中的節(jié)點(diǎn)表示像素，圖中邊的權(quán)重表示相鄰像素的相似度，將超像素分割轉(zhuǎn)化為圖分割問題，通過最小化目標(biāo)函數(shù)獲得超像素。除了幾種比較經(jīng)典的基于圖論的超像素分割算法外，還有近年來(lái)由Bergh等人[4]提出的基于能量驅(qū)動(dòng)的SEEDS算法，Veksler等人[5]提出Compact Superpixels和Constant-intensity superpixels算法?；谔荻壬仙姆椒ɑ舅枷胧菑淖畛醯南袼亻_始聚類，采用梯度上升法迭代修改聚類結(jié)果直到滿足收斂標(biāo)準(zhǔn)。其中近年來(lái)提出的基于梯度上升的超像素分割算法有，Levinshtein等人[6]提出的Turbopixels算法。

1 幾種最新的超像素分割算法

Bergh等人[4]提出SEEDS算法是一種基于能量驅(qū)動(dòng)獲取超像素的方法。Bergh等人認(rèn)為超像素為有顏色分布和邊界形狀的區(qū)域，超像素分割是能量最大化問題。SEEDS算法定義了一個(gè)基于超像素顏色分布直方圖和超像素邊界形狀的能量函數(shù)，通過爬山算法最大化能量函數(shù)來(lái)獲取超像素?；舅枷胂劝褕D像分割為網(wǎng)格狀的超像素，然后不斷交換邊界附近的像素點(diǎn)來(lái)改善超像素的邊界。能量函數(shù)定義為：

其中H（s）是顏色分布項(xiàng)，G（s）是邊界項(xiàng)，γ為權(quán)重因子。

（1）顏色分布項(xiàng)H（s）如下：

其中，Ak為超像素k的像素集，Hj為顏色分布直方圖中區(qū)間j，CA（j）為Ak的顏色分布直方圖，I（i）為像素Ki的顏色，Z為直方圖歸一化因子，δ（·）為函數(shù)符號(hào)。Ψ（CAK）為顏色分布的質(zhì)量計(jì)算方法，Ψ（CAK）函數(shù)可以使直方圖集中在一個(gè)或幾個(gè)顏色區(qū)域，這樣超像素包含的像素之間顏色相似，當(dāng)顏色分布直方圖只有一個(gè)區(qū)間時(shí)Ψ（CA）值最大且為1，其他情況Ψ（CA）值較小。HKK（s）為全部超像素的質(zhì)量評(píng)價(jià)。

（2）邊界項(xiàng)G（s）懲罰超像素邊界的局部不規(guī)則，有助于產(chǎn)生邊緣平滑的超像素。先在圖像的每個(gè)像素周圍放置N×N的格子塊（最小為3×3格子塊），Ni表示像素i周圍的格子塊。邊界項(xiàng)的質(zhì)量計(jì)算同樣采用直方圖，假設(shè)直方圖有k個(gè)區(qū)間，每個(gè)區(qū)間為一個(gè)超像素標(biāo)簽。邊界項(xiàng)G（s）如下：

其中，bNi（k）為Ni的分布直方圖，遠(yuǎn)離邊界像素的格子塊只屬于一個(gè)超像素時(shí)bNi（k）值最大且為1，邊界附近的像素的格子塊可能屬于多個(gè)超像素bNi（k）值較小。當(dāng)多數(shù)像素的格子塊只屬于一個(gè)超像素時(shí)G（s）值較大，超像素的邊界形狀較好。懲罰包含多個(gè)超像素的格子塊，減少邊界附近的像素?cái)?shù)量，有助于得到邊緣平滑的超像素。

Veksler等人[6]提出Compact superpixels和Constantintensity superpixels兩種超像素分割方法（簡(jiǎn)稱GCa和GCb）。算法定義了一種新的能量函數(shù)，采用圖割法使能量函數(shù)全局最小進(jìn)行超像素分割。兩種算法是基于同一能量函數(shù)的兩種變形，GCa算法生成的超像素比較緊湊、均勻，GCb算法生成的超像素邊緣保持度較好。

（1）結(jié)合圖割法使能量函數(shù)全局最小。給定像素集P，圖像塊標(biāo)簽集L，給任意像素p分配標(biāo)簽l，其中p屬于像素集P，l屬于圖像塊標(biāo)簽集L，fp表示像素p已經(jīng)分配標(biāo)簽。因此全局能量函數(shù)定義：

其中，DP（fp）表示像素p和標(biāo)簽fp的相似度，Vpq（fp，fq）=min（1，|fp-fq|）表示標(biāo)簽fp和標(biāo)簽fq的相似度，系數(shù)wpq是反轉(zhuǎn)系數(shù)，它有助于超像素的邊緣圖像的邊緣保持一致，N表示像素p鄰域中的像素。l為權(quán)重因子。

（2）GCa算法的基本思想是用相互重疊的圖像塊覆蓋圖像的任意像素，這樣像素可能被多個(gè)圖像塊覆蓋，因此需要在圖像塊之間尋找邊緣使任意像素只屬于唯一的圖像塊。GCa算法的能量函數(shù)的數(shù)據(jù)項(xiàng)定義為:

其中，S（l）表示標(biāo)簽l的圖像塊覆蓋的像素。能量函數(shù)中平滑項(xiàng)系數(shù)定義為：

其中，c（l）表示圖像塊S（l）的中心的像素，新的DP（l）有助于標(biāo)簽為l的像素和S（l）的中心點(diǎn)具有相同的強(qiáng)度。這樣可以避免將強(qiáng)度相差很大的像素結(jié)合成為同一超像素，有助于生成的超像素有更好的邊緣貼合度。

Levinshtein等人[6]提出TurboPixels算法，該算法描述了一種基于幾何流的方法獲取超像素，這種方法很好的保持了圖像的局部邊緣而且速度非?？欤乃惴◤?fù)雜度幾乎是跟著圖像的尺寸成線性關(guān)系。算法結(jié)合了計(jì)算機(jī)視覺中的曲率演化模型和背景區(qū)域骨架化過程，通過膨脹種子點(diǎn)把圖像分割成網(wǎng)格狀、緊湊的超像素。

TurboPixels算法生成的超像素應(yīng)符合以下5條基本原則：①均勻的大小，算法把圖像分割為近似均勻的大小和形狀。②連通性，每個(gè)超像素代表一個(gè)簡(jiǎn)單連通

其中，Ip表示像素p的強(qiáng)度，dist（p，q）表示像素p和鄰域中像素q的歐氏距離。圖像中邊緣附近像素的梯度值相差較大對(duì)應(yīng)圖中邊的權(quán)值很大，系數(shù)wpq可以使較大的權(quán)值變換成較小的權(quán)值，這樣有助于圖割法在圖像的邊緣進(jìn)行分割，因?yàn)閳D割法采用圖中的最小割算法，即分割邊的權(quán)值之和最小，也就是最小割正好對(duì)應(yīng)能量函數(shù)的最小化。

（3）GCb算法基本思想和GCa相同，只是對(duì)能量函數(shù)進(jìn)行了變形，使GCb算法生成的超像素有更好的邊緣貼合度。GCb算法中能量函數(shù)的數(shù)據(jù)項(xiàng)定義為：的像素集。③緊湊性，通過緊湊性約束條件，把圖像分割為近似網(wǎng)格狀緊湊的超像素。④平滑、邊緣保持，生成超像素邊緣要和圖像的局部邊緣保持一致。⑤超像素不重疊，圖像的每個(gè)像素應(yīng)該分配到單一的超像素中。

TurboPixels算法詳述:

①水平集的含義。TurboPixels算法結(jié)合了幾何流和水平集的方法，基本思想是通過曲線演化來(lái)獲得超像素的邊界。水平集的表達(dá)式Ψt=-S||▽?duì)穦|，其中S為邊界上的像素向外法線的運(yùn)動(dòng)速度，水平集的幾何意義為邊界在速度S下的運(yùn)動(dòng)軌跡。

②初始化種子點(diǎn)位置。一個(gè)關(guān)鍵的目標(biāo)是生成的超像素均勻的分布在圖像上，假定用戶給定的超像素個(gè)數(shù)是K，使K個(gè)種子點(diǎn)呈網(wǎng)格狀分布，因此網(wǎng)格相鄰的種子點(diǎn)距離近似相等且為，其中N是圖像的像素?cái)?shù)量，以上的策略確保了超像素均勻分布這一目標(biāo)。由于圖像的不統(tǒng)一，這使得種子點(diǎn)會(huì)落在圖像局部邊緣上，為避免過早的膨脹種子點(diǎn)，應(yīng)使每個(gè)種子點(diǎn)避免落在圖像的高梯度區(qū)域。

③水平集演化。

上式的每次應(yīng)用對(duì)應(yīng)邊界的一次演化，控制演化的關(guān)鍵為速度SISB，這是算法的核心。SI依賴于圖像的局部結(jié)構(gòu)和超像素邊界的形狀，SB依賴與邊界上像素點(diǎn)和其它超像素。

④邊界速度。邊界速度SB應(yīng)確保超像素邊界在膨脹過程不能越過另一超像素的邊界，為此把未分配區(qū)域分割為二維骨架輪廓，當(dāng)（x，y）在骨架上時(shí)SB（x，y）= 0，在其他區(qū)域SB（x，y）=1。這意味著超像素在膨脹過程中速度S僅與SI有關(guān)，只有在很接近另一超像素時(shí)才與SB的有關(guān)，因此在曲線演化的過程中未分配區(qū)域骨架輪廓也需要更新。

⑤圖像速度。圖像速度SI結(jié)合了反應(yīng)擴(kuò)散項(xiàng)和雙重項(xiàng)，反應(yīng)擴(kuò)散項(xiàng)使邊界演化到圖像的高梯度區(qū)域時(shí)速度變慢。雙重項(xiàng)使超像素的邊界和圖像的局部邊界保持一致。

⑥速度擴(kuò)展。SI和SB作用在當(dāng)前超像素的邊界上，即Ψ的0水平集，由于Ψ的0水平集定義很模糊，速度擴(kuò)展需要更新邊界附近窄帶像素的速度。

⑦結(jié)束條件。當(dāng)邊界停止演化時(shí)算法結(jié)束。

⑧算法復(fù)雜度。算法的復(fù)雜度和圖像的大小呈線性關(guān)系，圖像變大算法會(huì)變慢，超像素的密度增加，算法的速度會(huì)變快，對(duì)于固定的超像素密度，算法的迭代次數(shù)是恒定的，因此，整體上算法的復(fù)雜度為O（N）。

2 超像素的應(yīng)用

Ren等人[1]首次提出超像素時(shí)，超像素就被于圖像分割，他們結(jié)合圖像的紋理、輪廓、亮度等特征，訓(xùn)練了一種線性分類器對(duì)圖像進(jìn)行分割，取得了較好的分割結(jié)果。

近年來(lái)，超像素分割技術(shù)越來(lái)越多的應(yīng)用在計(jì)算機(jī)視覺中，如深度估計(jì)、人體姿勢(shì)估計(jì)、目標(biāo)檢測(cè)等。Mori等人[7]用超像素分割技術(shù)對(duì)圖像中的人體姿勢(shì)進(jìn)行估計(jì)，他們先將圖像分割為超像素圖像，對(duì)圖像中人體關(guān)節(jié)和四肢等重要信息進(jìn)行提取，然后將這些信息組合起來(lái)進(jìn)行人體姿勢(shì)估計(jì)。文獻(xiàn)[8]基于超像素分割技術(shù)對(duì)時(shí)空顯著的運(yùn)動(dòng)目標(biāo)進(jìn)行檢測(cè)，他們利用目標(biāo)靜態(tài)灰度特征和運(yùn)動(dòng)特征，結(jié)合目標(biāo)運(yùn)動(dòng)連續(xù)特征，對(duì)時(shí)空顯著的運(yùn)動(dòng)目標(biāo)進(jìn)行檢測(cè)。

超像素分割技術(shù)在對(duì)醫(yī)學(xué)圖像處理方面也有很廣泛的應(yīng)用。文獻(xiàn)[9]采用SLIC算法和DBSCAN聚類對(duì)眼底圖像中的硬性滲出進(jìn)行自動(dòng)檢測(cè)。首先采用SLIC超像素分割算法對(duì)彩色眼底圖像進(jìn)行分割，然后用DBSCAN對(duì)以上分割得到的超像素進(jìn)行聚類形成簇，最后分割出目標(biāo)圖像。

3 結(jié)語(yǔ)

本文對(duì)最新的超像素分割算法進(jìn)行了論述，并對(duì)超想素的應(yīng)用進(jìn)行了介紹。通常要求超像素分割算法快速，易于使用，并且能夠產(chǎn)生規(guī)則、均勻的分割效果[10]，未來(lái)計(jì)算效率更高，能夠滿足大數(shù)據(jù)量和實(shí)時(shí)性要求的分割算法將是新的研究方向。

[1]王春瑤，陳俊周，李煒.超像素分割算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2014，31（1）:6-12[DOI:10.3969/j.issn.1001-3695.2014. 01，002]

[2]Ren Xiao-feng，MALIK J.Learning a Classification Model for Segmentation[C].Proc of the 9th IEEE International Conference on Computer Vision.Washing DC:IEEE Computer Society，2003:10-17

[3]宋熙煜，周利莉，李中國(guó)，陳健，曾磊，閆鑌.圖像分割中的超像素方法研究綜述[J].中國(guó)圖象圖形學(xué)報(bào)，2015，20（5）:0599-0608 [DOI:10.11834/jig.20150502]

[4]Bergh M V D，Boix X，Roig G，et al，SEEDS:Superpixels Extracted Via Energy-Driven Sampling[M].Computer Vision-ECCV 2012. Berlin Heidelberg:Springer，2012:13-26[DOI:10.1007/s11263-014-0744-2]

[5]Veksler O，Boykov Y，Mehrani P.Superpixels and Supervoxels in an Energy Optimization Framework[M].Computer Vision ECCV 2010.Berlin Heidelberg:Springer，2010:211-224.[DOI:10.1007/978-3-642-15555-016]

[6]LEVINSHTEIN A，STERE A，KUTULAKOS K N，et al.Turbopixels:Fast Superpixels Using Geometric Flows[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2009，31（12）:2290-2297.

[7]G.Mori，X.Ren，A.A.Efros，J.Makil.Recovering Human Body Configurations:Combining Segmentation and Recognition.In CVPR，2004.

[8]云紅全，徐力，孫驍，明德烈，鞠雯.基于超像素時(shí)空顯著性的運(yùn)動(dòng)目標(biāo)檢測(cè)算法[J].紅外技術(shù)，2015，37（5）.

[9]凌朝東，陳虎，楊驍，張浩，黃信.結(jié)合SLIC超像素和DBSCAN聚類的眼底圖像硬性滲出檢測(cè)方法[J].華僑大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，36（4）[DOI:10.11830/ISSN.1000-5013.2015.04.0399]

[10]饒倩，文紅，喻文，等.超像素及其應(yīng)用綜述[J].電腦與信息技術(shù)，2013，21（5）:1-3[DOI:10.3969/j.issn.1005-1228.2013.05.001]

Review on the Latest Superpixel Algorithms

LIU Bin，QU Xing-xing，CHEN Xiang-ting

（College of Computer Science&Information Engineering，Henan University，Kaifeng 475000）

Superpixel represents a restricted from of a region segmentation,it can capture the redundancy of the image and reduce the complexity of image processing,attracts more and more researchers'attention.Discusses the latest superpixel segmentation algorithms,and introduces application of superpixel.

Superpixel;Image Segmentation;Image Processing

1007-1423（2016）35-0062-04

10.3969/j.issn.1007-1423.2016.35.013

劉斌（1988-），男，河南新鄭人，碩士研究生，研究方向?yàn)閿?shù)字圖像處理

2016-10-25

2016-12-05

渠星星（1992-），女，河南許昌人，碩士研究生，研究方向?yàn)閿?shù)字圖像處理

陳相庭（1991-），男，河南安陽(yáng)人，碩士研究生，研究方向?yàn)閿?shù)字圖像處理