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

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-），男，河南安阳人，硕士研究生，研究方向为数字图像处理