（a） (b)
图3 超像素网格的形成过程
在搜索最优路径的策略上，Moore 等人采用了两种方案: s-t最小割方法和动态规划方法，前者产生任意拓扑路径，后者则产生无回归路径。其中，最优路径需要满足三个条件: a) 每条垂直和水平路径只交叉一次; b) 任意两条垂直路径不交 叉; c) 任意两条水平路径不交叉。 虽然 superpixel lattice 算法已取得良好的分割效果，但其分 割质量仍然依赖于图像边界图，且隐含地规定了图像均匀分割 需要两个机制: a) 图像带的分布均匀直接影响了路径的均匀分布; b) 最小代价路径策略有利于形成图像上相对较直和较短的路径。因此，Moore 等人.于2009 年在该算法的基础上加入先 验信息，提出了基于场景形状先验的超像素分割。利用概率密度模型来描述图像物体边界的空间密度，采用一种过分割算法，使得超像素间的密度大致相等的同时适应了局部目标边界。随后，Moore 等人又提出了 lattice-cut方法，它是一种无监督的分割，采用交替选择最优策略，用单一图像割交替地在水平或者垂直方向更新超像素边界，同时考虑了图像边界和超像素区域内的一致性。整个超像素产生过程可以用来自图 4描述。图中，( a) 首先将图像分割为均匀间距的网格超像素，且属于同个超像素中的像素点具有相同的标签;( b) ～ ( d) 建立马尔可夫随机场模型，不断交替地在水平和垂直方法更新超像素晶格边界，即改变相关像素点的标签;( e) ( f) 对于垂直或水平方向更新，像素的标签决定了该像素属于哪个垂直或水平带条。Lattice-cut 方法优于现有的计算超像素网格算法，它的性能与某些没有网格限制的分割算法具有可比性。
（c）SLIC 超像素结果及其局部放大 （d）LAttices 超像素结果及其局部放大 图4 原始图像和3种超像素结果及其局部放大比较
11
2.2.3 基于熵率的方法
Liu 等人提出的基于熵率的超像素分割算法，描述了一种基于图拓扑的能量函数。他们采用了一种新型的目标函数， 包括图像随机游走熵率和平衡项两部分。其中，熵率有利于形成结构紧凑、均匀的集群，促使获得的超像素仅覆盖图中的单一目标对象。平衡项促使集群有相似的尺寸，降低不平衡超像素的个数。该目标函数可以表示为:
(??)BA( maxH'A (6)
A其中: A 是选择的边集 A∈E， H'( A) 表示图像随机游走熵率，B ( A) 表示平
衡项，λ≥0 是一个权重值。通过最大化上述目标函数，就可以将图像进行分割。a) 熵率是用来衡量一个随机过程 X = { Xt |t∈T} 的不确定性，对于离散的随机过程，熵率可以用如下公式来表示:
H'(X)?limH(XtXt?1,Xt?2,?,Xt) (7)
t??对于图像随机游走熵率，它作为衡量集群的紧凑度和均匀程度的标准，图 G = ( V， A) 上的随机游走熵率可以表示为:
H'(X)???ui?pi,j(A)log(pi,j(A)) ( 8)
ij其中: μi = wi /wT，且 wi 是图中与节点i相连的边的权重之和，Wt是图中所有边权重的总和。Wi，j是节点i 到节点j的转移概率，Pi, j是随机游走的转移概率，其定义如下:
?wi,j?wi? p(A)??0?i,j??1??j:ei,j?Awi,j?wi?ifi?jandei,j?Aifi?jandei,j?A (9)
ifi?j虽然添加集合A中的任意边能增加熵率的值，但是选择涨幅更大的边有助于形
成紧凑和均匀的集群。如图5所示，集群( a)的紧凑度较高，且它的熵率值大于集群( b)的熵率值;集群( c) 的结构相对较均匀，且它的熵率值大于集群( b) 的熵率值。
12
（a）熵率=0.81 （b）熵率=0.43 （c）熵率=0.64 （d）熵率=0.61
图5 熵率对集群紧凑度和均匀性的作用
b) 平衡项用于促成集群具有相同的尺寸，用如下的公式表示: B(A)?H(zA)?NA???pzA(i)log(pzA(i))?NA （10）
i其中: NA是图中连通分支的个数，ZA是集群成员的分布，若边集A的图分割是S??S1,S2,?,SNA?，那么ZA的分布如式( 11) 所示: pzA(i)?SiVi??1,?,NA? (11)
图 6 展示了平衡值在获得近似尺寸集群时所起的作用。细线和粗线条连接的连通区域代表了不同的集群，( a)中集群的平衡值大于( b)中集群的平均值，且可以看出( a) 中集群分布更均匀。
(a)平衡值=-1.00 (b)平衡值=-1.19 图6 熵率对集群相似尺度的作用
2.2.4 Turbopixels 方法
Levinshtein 等人描述了一种基于几何流的水平集方法，能快速地产生超像素。他们通过膨胀初始化种子点，并结合曲率演化模型和背景区域的骨架
13
化过程，将图像分割为网格状的超像素。 Turbopixels 生成的超像素需要符合五个基本原则: a) 均匀尺寸，算法应把图像分为尺寸和形状大致相同的超像素，可以通过设计几何流来膨胀初始均匀分布的种子达到此目的; b) 连通性，每个超像素应该表示一个简单连通的像素集合，采用结合水平集的几何流扩张方法能确保此约束总是满足; c) 紧凑性，为了使超像素最大限度地紧凑，需要使强度均匀的区域在法线向外方向产生恒定的运动; d) 平滑和边缘保持，当种子增长停止时，超像素边界应该和图像边界相吻合，这需要几何流公式在边界强度弱或者没有边界的地方，曲线运动速度大，而边界强度较强的地方，曲线速度慢甚至停止，从而实现图像的分割; e) 超像素不重叠，算法应该把每个像素分配到单一超像素中。因此,当两个不同的种子膨胀到即将碰撞时，应该停止边界增长。整个算法步骤如图8所示，包括: a) 初始化等间距的种子点。b) 迭代以下步骤，直至不再有进一步的演化。( a) 第 T 次演化边界; ( b) 估计未分配区域的骨架; ( c) 更新边界上像素点的速度和在边界附近未分配像素点的速度。
（a）放置种子点 (b) 第T次化 （c）更新骨架 （d) 更新速度 （e）速度扩展 图8 Turbopixels算法步骤
该方法生成的超像素不仅保持了图像的局部边界，还通过一个紧凑度约束条件限制了欠分割。它的运算速度很快，算法复杂度与图像的尺寸成近似线性关系，并且对于万像素级图像，在几分钟内就可以获得高密度的超像素。Xiang 等人提出从待分割的图像中构建多维特征图像的方法，应用于 Turbopixel 框架超像素分割中。Cigla 等人介绍了一种快速的 Turbopixel 高效图论分割方法，先采用快速Turbopixel算法把图像分割为超像素，再建立加权图，用Ncut算法得到图的最终分割结果。
2.2.5 SLIC 方法
Achanta 等人提出了一种思想简单、实现方便的算法，将彩色图像转换为 CIELAB 颜色空间和 XY 坐标下的 5 维特征向量，然后对5 维特征向量构造度量标准，对图像像素
14
进 行局部聚类的过程。该算法速度较快，能生成紧凑、近似均匀的超像素，具体步骤为: a) 初始化种子点。假设图像有N个像素点，预分割为K个相同尺寸的超像素，那么每个超像素的大小为 N/K，且每个 种子点的距离近似为 S =
N/K。为了避免种子点处在图像
的边缘位置，以及对后续的聚类过程造成干扰，需要将种子点在 以它为中心的 3 ×3 的窗口内移动到梯度值最小的位置，同时 为每个种子分配一个单独的标签。 b) 相似度衡量。对于每个像素点，分别计算与之距离最近的种子点之间的相似程度，将最相似种子点的标签赋给该像素。通过不断迭代该过程，直到收敛，则相似度的衡量关系如下:
dlab?(lk?li)2?(ak?ai)2?(bk?bi)2 （12） dxy?(xk?xi)2?(yk?yi)2mDi?dlab?dxyS其中: dlab为像素点间的颜色差异，dxy为像素点间的空间距离，Di为两个像素的相
似度; S为种子点的间距，m为平衡参数，用来衡量颜色值与空间信息在相似度衡量中的比重。Di 取值越大，说明两个像素越相似，为了提高算法的运算速度，对每个种子点聚类时，只在以种子点为中心的 2S × 2S 区域内搜索相似像素点，而不是在整张图像中寻找（如图 9 所示）。
（a）在整张图新中的搜索 （b）SLIC在限定区域内的搜索 图9 减少像素的搜索范围
Ｒen 等人使用GPU和 NVIDIA CUDA 框架实现 SLIC 算法，能将速度提高 10 ～ 20 倍，促使 SLIC 能应用于实时系统。 Lucchi 等人利用SLIC分割算法作预处理，然后以超像素为节点、空间相邻节点以边连接建立了图模型，给出相应的条件随机场定义，提出了使用核心化特征的结构图像分割。
15