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

劉斌，渠星星，陳相庭

（河南大學計算機科學與信息工程學院，開封 475000）

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

劉斌，渠星星，陳相庭

（河南大學計算機科學與信息工程學院，開封 475000）

超像素是指受一定相似性準則約束的分割區域，它可以獲取圖像的冗余信息，降低處理圖像的復雜度，受到越來越多研究者的關注。對最新的超像素分割算法進行論述，并對超像素的應用場景進行介紹。

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

0 引言

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

目前的超像素分割算法大概可以分為兩類:基于圖論的方法和基于梯度上升的方法。基于圖論的方法基本思想是用圖中的節點表示像素，圖中邊的權重表示相鄰像素的相似度，將超像素分割轉化為圖分割問題，通過最小化目標函數獲得超像素。除了幾種比較經典的基于圖論的超像素分割算法外，還有近年來由Bergh等人[4]提出的基于能量驅動的SEEDS算法，Veksler等人[5]提出Compact Superpixels和Constant-intensity superpixels算法。基于梯度上升的方法基本思想是從最初的像素開始聚類，采用梯度上升法迭代修改聚類結果直到滿足收斂標準。其中近年來提出的基于梯度上升的超像素分割算法有，Levinshtein等人[6]提出的Turbopixels算法。

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

Bergh等人[4]提出SEEDS算法是一種基于能量驅動獲取超像素的方法。Bergh等人認為超像素為有顏色分布和邊界形狀的區域，超像素分割是能量最大化問題。SEEDS算法定義了一個基于超像素顏色分布直方圖和超像素邊界形狀的能量函數，通過爬山算法最大化能量函數來獲取超像素。基本思想先把圖像分割為網格狀的超像素，然后不斷交換邊界附近的像素點來改善超像素的邊界。能量函數定義為：

其中H（s）是顏色分布項，G（s）是邊界項，γ為權重因子。

（1）顏色分布項H（s）如下：

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

（2）邊界項G（s）懲罰超像素邊界的局部不規則，有助于產生邊緣平滑的超像素。先在圖像的每個像素周圍放置N×N的格子塊（最小為3×3格子塊），Ni表示像素i周圍的格子塊。邊界項的質量計算同樣采用直方圖，假設直方圖有k個區間，每個區間為一個超像素標簽。邊界項G（s）如下：

其中，bNi（k）為Ni的分布直方圖，遠離邊界像素的格子塊只屬于一個超像素時bNi（k）值最大且為1，邊界附近的像素的格子塊可能屬于多個超像素bNi（k）值較小。當多數像素的格子塊只屬于一個超像素時G（s）值較大，超像素的邊界形狀較好。懲罰包含多個超像素的格子塊，減少邊界附近的像素數量，有助于得到邊緣平滑的超像素。

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

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

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

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

其中，S（l）表示標簽l的圖像塊覆蓋的像素。能量函數中平滑項系數定義為：

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

Levinshtein等人[6]提出TurboPixels算法，該算法描述了一種基于幾何流的方法獲取超像素，這種方法很好的保持了圖像的局部邊緣而且速度非常快，它的算法復雜度幾乎是跟著圖像的尺寸成線性關系。算法結合了計算機視覺中的曲率演化模型和背景區域骨架化過程，通過膨脹種子點把圖像分割成網格狀、緊湊的超像素。

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

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

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

TurboPixels算法詳述:

①水平集的含義。TurboPixels算法結合了幾何流和水平集的方法，基本思想是通過曲線演化來獲得超像素的邊界。水平集的表達式Ψt=-S||▽Ψ||，其中S為邊界上的像素向外法線的運動速度，水平集的幾何意義為邊界在速度S下的運動軌跡。

②初始化種子點位置。一個關鍵的目標是生成的超像素均勻的分布在圖像上，假定用戶給定的超像素個數是K，使K個種子點呈網格狀分布，因此網格相鄰的種子點距離近似相等且為，其中N是圖像的像素數量，以上的策略確保了超像素均勻分布這一目標。由于圖像的不統一，這使得種子點會落在圖像局部邊緣上，為避免過早的膨脹種子點，應使每個種子點避免落在圖像的高梯度區域。

③水平集演化。

上式的每次應用對應邊界的一次演化，控制演化的關鍵為速度SISB，這是算法的核心。SI依賴于圖像的局部結構和超像素邊界的形狀，SB依賴與邊界上像素點和其它超像素。

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

⑤圖像速度。圖像速度SI結合了反應擴散項和雙重項，反應擴散項使邊界演化到圖像的高梯度區域時速度變慢。雙重項使超像素的邊界和圖像的局部邊界保持一致。

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

⑦結束條件。當邊界停止演化時算法結束。

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

2 超像素的應用

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

近年來，超像素分割技術越來越多的應用在計算機視覺中，如深度估計、人體姿勢估計、目標檢測等。Mori等人[7]用超像素分割技術對圖像中的人體姿勢進行估計，他們先將圖像分割為超像素圖像，對圖像中人體關節和四肢等重要信息進行提取，然后將這些信息組合起來進行人體姿勢估計。文獻[8]基于超像素分割技術對時空顯著的運動目標進行檢測，他們利用目標靜態灰度特征和運動特征，結合目標運動連續特征，對時空顯著的運動目標進行檢測。

超像素分割技術在對醫學圖像處理方面也有很廣泛的應用。文獻[9]采用SLIC算法和DBSCAN聚類對眼底圖像中的硬性滲出進行自動檢測。首先采用SLIC超像素分割算法對彩色眼底圖像進行分割，然后用DBSCAN對以上分割得到的超像素進行聚類形成簇，最后分割出目標圖像。

3 結語

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

[1]王春瑤，陳俊周，李煒.超像素分割算法研究綜述[J].計算機應用研究，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]宋熙煜，周利莉，李中國，陳健，曾磊，閆鑌.圖像分割中的超像素方法研究綜述[J].中國圖象圖形學報，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]云紅全，徐力，孫驍，明德烈，鞠雯.基于超像素時空顯著性的運動目標檢測算法[J].紅外技術，2015，37（5）.

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

[10]饒倩，文紅，喻文，等.超像素及其應用綜述[J].電腦與信息技術，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-），男，河南新鄭人，碩士研究生，研究方向為數字圖像處理

2016-10-25

2016-12-05

渠星星（1992-），女，河南許昌人，碩士研究生，研究方向為數字圖像處理

陳相庭（1991-），男，河南安陽人，碩士研究生，研究方向為數字圖像處理