SLIC超级像素分割算法的原理与实现+文献综述(4)
1.2.1 基于图论的方法
基于图论的超级像素分割算法是一种自上而下的全局分割方法。其基本思想是把整幅图像看做一幅带权无向图，图像中每一个像素对应图中的一个节点，像素之间的相邻关系对应图的边，像素特征之间的差异或相似性对应边上的权重。然后在所建立的图上利用各种分割准则来对图中的节点进行划分，进而完成对图像的分割。
1.2.1.1 Graph-based segmentation方法
Fezenszwalb等人提出的Graph-based segmentation[11]方法(以下简称GS04）采用了最小生成树的思想。该方法的思想是将一幅图像映射为无向图时，为每条边定义用来表示边所连接的两个顶点的差异性的权值。
GS04方法通过将图上的节点进行聚类来实现，且生成的超级像素就是像素集合的最小生成树。它的复杂度是O(NlogN)，N为图像中像素的数目（本文接下来描述算法复杂度时，N皆为图片中像素的数目）。它能较好地保持图像边界，速度较快，但不能控制超级像素的数量，且生成超级像素的形状非常不规则。Hoiem等人将GS04用于深度估算中[2]。
1.2.1.2 Normalized cuts方法
Shi等人提出的Normalized cuts方法(以下简称NC05），它的基础是最小割（Min-cut）方法。最小割方法是一种寻找子图间代价函数的最小划分的方法。但它只考虑子图间耦合度最低，而忽略了子图中节点耦合的情况，因此最小割会趋向于分离单个或者小簇顶点。使用最小割方法划分图，虽然可以达到最小代价的目的，却违背了最优分割的标准，无法得到真正的最佳分割。于是归一化割（Normalized cuts）方法就被提出了。
早期的NC05方法由Shi等人1997年提出[12]，并于2000年作了相应的改进[13]。NC05对最小割算法进行改进，采用新颖的归一化割标准，同时度量了区域间的差异和区域内的相似性，很好地避免了最小割准则存在的缺陷，是一种较理想的评价分割质量的标准。
NC05方法的复杂度是O(N1.5)[18]，NC05分割算法的特点是可以控制生成超级像素的数量，且形状比较规整和紧凑，但是它对图像边界保持的不太好。而且它的运算速度较慢，对于尺寸很大的图片，计算时间很长，以致于经常无法产生运算结果。
Cour等人[19]、Maji等人[20]提出过对NC05算法的改进。NC05算法是[1]和[7]图像分割模式的基础，NC05被应用于人体姿势估计[7]和骨架提取[6]。
1.2.1.3 Superpixel lattices方法
对于一些超级像素分割算法存在丢失原始图像重要的拓扑结构信息这一缺陷，Moore等人提出了一种无监督的过分割算法Superpixel Lattices[14]（ 以下简称SL08）。该方法描述了一种能保持图像拓扑结构的贪心算法，虽然增加了拓扑信息约束条件，但是它在速度和分割精度上保持了良好的性能。
SL08算法输入的是图像的边界图，目的是搜寻穿过图像的最小权重路径，在边界代价图最小处分割图像。通过在垂直和水平条带两个方向搜索最优路径，不断地将图像从垂直和水平方向进行二分来得到常规网格超级像素。在搜索最优路径的策略上，SL08采用了两种方案：s-t最小割方法和动态规划方法。根据作者，SL08的复杂度是O(N1.5logN)。
虽然SL08算法允许控制超级像素的大小、数量、紧凑度，并且拥有很快的速度。但是，它的分割质量和速度严重依赖于分割前测量的图像边界图。因此Moore等人[21]于2009年在该算法的基础上加入先验信息，提出了基于场景形状先验的超级像素分割。利用概率密度模型来描述图像物体边界的空间密度，采用一种过分割算法，使得超级像素间的密度大致相等的同时适应了局部目标边界。
随后Moore等人又提出了Lattice Cut[22]方法。它是一种无监督的分割，采用交替选择最优策略，用单一图像割交替地在水平或者垂直方向更新超像素边界，同时考虑了图像边界和超级像素区域内的一致性。Lattice Cut方法的性能与某些没有网格限制的分割算法具有可比性。