,v·s·cos(h)](i)，其中，h，s，v 为图像在彩色空间（HSV）的值，对于纹理图像分割F(i)=[I*f1,......,I*fn(i)]，其中fi是DOOG滤波器的输出。
Normalized cut，Ncut (归一化割分割方法)是由Shi等人提出的，测量图G所有连接节点的总边界权重为分割成本通过下式（广义特征值系统的特征值及其对应的特征向量）：
?D?W?y?yDy （2-2）
D — 对角线上为d的M×M的对角矩阵；
Ｗ— w(i,j)＝wij的M×M矩阵；
向量ｙ满足：y(i)?{1,?b},yTD1?0,１为单位向量。Ncut分割的真实解是广义特征值系统的第二个最小特征向量。
在不同的空间分离半径rij下，W性质不同，Shi等人对其进行了改进，提出了有偏差的归一化分割，相较于传统的Ncut算法，它存在两个优势：a)允许使用top-down先验证信息来寻求解决方法；b)给定未约束问题的谱方法，约束问题的解决方案可以在很短时间内计算，且允许算法以交互的模式来运行。Ｒen 等人提出了学习一个分类器来进行图像分割的方法。首先用Ncut算法将图像映射为超像素图，它认为好的分割应从相似性、邻近性和连续性等方面来评判，因此采用了经典的 Gestalt 准则来衡量分割质量的好坏，包括区域内和区域间的纹理相似性、亮度相似性、轮廓能量和曲线连续性四方面的特征。最后，归一化这些特征，并训练相应的分类器来对分割后的结果进行分类。它是一种严格的图论分割，能约束产生 许多小的、紧凑的、近似均匀区域。
基于图论的图像分割是一种自上而下的全局分割方法，其主要思想是把整幅图像看做一幅带权无向图，图像中每一个像素对应图中的一个节点，像素之间的相邻关系对应图的边，像素特征之间的差异或相似性对应边上的权重。然后在所建立的图上利用各种分割准则来对图中的节点进行划分，进而完成 对图像的分割。在基于图论的超像素计算方法中，每个像素点被视作是图里面的节点，像素之间的相邻关系对应图中的边，边的权重设置为与两节点间相似度成比例的对应值。运用图论的研究成果，根据图像中各个局部之间的关系和相似性，将图像分割成各具特性的子图的方法。它考虑的是图像全局的性质分布，相对于一些传统的分割方法具有自己的独特优势。首先，图论算法很好的体现了局部和全局之间的结合关系。由初始图像构造图时，图中连接各个顶点的边的权值体现了像素之间的局部联系，这种联系既可以是像素的灰度、颜色、纹理的相似性，也可以是这些性质的组合，或者可以有更
6
为复杂的规则。而将图分割成一个个的子图则体现了图像特征的全局分布特性。基于图论方法的这种局部和全局的结合特性，与人类视觉也有着惊人的相似。其次，引入图论做图像处理的一个很重要的优势就是可以利用大量现有的图论研究成果。
Ncut 方法是利用边缘和纹理信息递归地将图像进行分割得到结果的，综合考虑了全局和局部的信息特点获得全局最优化处理，因此，可以取得在图中所定义的能量函数的全局最小值。 将图 G = ( V，E) 分割为两个不相交的集合 A、 B，且存在 A∪B = V，A∩B = ?。评价分割质量好坏的最小割标准为
cut(A,B)??w(u,v) ( 1)
u?A,v?B使用图论中的最优化分割理论就可以获得 cut(A,B)的最小化解 Min-cut，但是这种方法存在一个严重的缺点就是偏向于割开单个节点或者小数节点集，如图
图1 最小化解 Min-cut 偏向于割开单个节点
早期的Ncut方法由Shi等人于1997年提出，并于2000年作了相应的改进。Ncut 对最小割算法进行改进，采用新颖的归一化割标准，同时度量了区域间的差异和区域内的相似性，很好地避免了最小割准则存在的缺陷。Ncut 准则定义如下:
cu(tA,B)cu(t,A)B?B? Ncu(t,A) （2） asso(c,A)Vas(so,c)BV其中: assoc( A，V) 是指子集 A 中所有节点到图中所有节点的边连接权重总
和，assoc( B，V) 也是类似的定义。这样定义两个区域之间的不相关性，使单个顶点分割的结果不再满足Ncut 值最小，因此不会偏向分割单个孤立的顶点。
Ncut( A，B) 值越低表示相似度高的顶点分配到一个子图中，相似度低的
7
顶点分配到不同子图中，是一种较理想的评价 分割质量的标准。但由于Ncut 被证明是 NP-hard 问题，且随着图中节点数目的增加，问题的求解变得异常复杂。在实际应用中，常把Ncut 准则转换为矩阵计算的形式，并求解方程的特 征值和特征向量。通常选择第二个最小特征值所对应的特征向量，它代表了图划分的最优解，并取一个合适的分裂点，将特征向量离散化为两个值，根据离散化后的值将图分割为两部分。如需要再细分，可以迭代地调用该算法进行二分。 Ncut 算法分割结果的特点是可以控制超像素的数量，且形状比较规整和紧凑。但是 Ncut 算法速度较慢，尤其对于尺寸比较大的图片，计算量很大。
Maji 等人在 Ncut 算法的基础上进行修改，提出了有偏差的归一化分割。相比于传统的 Ncut 算法，它存在两个优势: a) 允许使用 top-down 先验信息来寻求解决方法; b) 给定了未约束问题的谱方法，约束问题的解决方案可以在很短的时间内计算，且允许算法以交互的模式来运行。
2.1.2 基于梯度的分割方法
对于基于梯度的方法，由初始的粗聚类开始，通过梯度方法不断地更新聚类，直到收敛为止。
1）分水岭方法：
分水岭方法用拓扑地形图来描述一幅图像，当应用于图像分割时，图像中每个像素的灰度值表示该点的海拔高度，每个局部极小值及其影响区域为集水盆，而集水盆的边界就形成了分水岭，大致模型可用图2描述。分水岭分割算法借鉴了数学形态学的理论知识，最初由 Digabel 等人将分水岭算法引入到了二值黑白图像的分析 过程中; 随后，Beucher 等人进行了深入的探讨，建立了较为完 善的分水岭理论体系。比较经典的计算方法是 Vincent 等人提出的，采用了浸没算法的实现方案，将分水岭计算分为排序过程和浸没过程。目前三种经典的分水岭分割算法是基于梯度的分水岭分割、基于距离变换的分水岭分割和基于标记的分水岭分割。分水岭算法的优点是简洁、复杂度低、运行时间短，且提取出的物体边缘轮廓线是封闭的，能准确定位目标物体。但是它也存在一定的缺点，分水岭分割会得到成千上万的集水盆，结果很细致，导致图像出现非常严重的过分割现象。 2）基于 Mean-shift 方法
Mean-shift 算法最早在 1975 年由 Fukunaga 等人提出，1995年Cheng
8
发表的文献定义了核函数和权值系数，使 Mean-shift 算法得到了广泛应用。 Comaniciu 等人提出了一种无参数的、基于核密度梯度估计的快速统计迭代算法。其基本思想是在核窗口依次计算所有特征空间数据点的 Mean-shift 矢量，沿着 Mean-shift 梯度上升方向移动，直到收敛到密度最大处，如图3所示。通过有限次迭代计算，能够快速找到数据分布的稳定点，即模点。利用Mean-shift 做图像分割，就是把具有相同模点的像素聚类到同一超像素中的过程。该方法在实际应用中具有较好的稳定性和抗噪性，但速度慢，且由于分割时缺少图像语义信息，分割效果不够理想，存在过分割问题。
图2 分水岭示例 图3 Mean-shift 示意图
Vedaldi 等人提出 Quick-shift 分割算法类似于 Mean- shift 策略的模式搜索，但是速度更快。它不断促使像素特征空间中的每一个数据点，向着能使 Parzen 密度估计增大的最近的像素移动来实现图像的分割。该算法是非迭代的，不能明确地控制超像素的大小和数量。Wang等人提出了各向异性核 Mean-shift 方法，而不是传统的径向对称核来估计局部密度，该方法在性能上优于传统均值漂移的方法，分割后的超像素更光滑、视觉上更符合人类感知系统。Tao等人提出一种Mean-shift 与Ncut相结合的新方法，先利用 Mean-shift 算法对输入目标图像进行预处理生成超像素，再用Ncut方法进行图像分割，把每个超像素看做图的节点，解决了谱聚类在图像分割时计算量大的问题，提高了算法分割效率，但分割效果并不是很理想。
2.2 几种常见的算法
2.2.1 Graph-based 方法
Felzenszwalb 等人提出的基于图论分割方法采用了最小生成树的思想，目的是使同一区域内的元素尽可能相似，不同区域的元素尽可能不相似。该方法的思想是将一幅图像映射为无向图时，为每条边 e 定义了权值 w( e) ，它
9
用来表示边 e 所连接的两个顶点 vi 和vj的差异性。V 是图中所有顶点的集 合，一个分割S就是将V分成不同区域的一种划分，每个小区域 C∈S 对应于图G' = ( V，E') 的一个连通子图，其中 E'是E的非空子集。对于子集C?V 的内部差异就是该区域最小生成树MST ( C， E) 上的最大权值，计算公式为：
int(C)?maxw(e) (3)
e?MST(C,E)两部分子集 C1， C2 ?V 的区域间差异为连接这两部分的最小权值边，即：
minw((vi,vj)) （4） dif(C1,C2)?vi?C1,vj?C2,(vi,vj)?E如果两个部分间的区域差异 dif( C1，C2) 大于 C1、C2 中至 少一个部
分的内部差异 int( C1) 或 int( C2) ，则说明这两部分不 能合为一体，否则就可以合并，用下面公式来说明:
?trueifdif(C1,C2)?MInt(C1,C2) D(C1,C2)?? (5)
otherwise?false MInt(C1,C2)?min(int(C1)??(C1),int(C2)??(C2))
其中: 函数 τ( C) = k/ |C|， k 是常数， |C|是区域 C 的尺寸大小。 函数τ( C)用来控制两个区域 C1、C2 差异性的程度，使得区域 间的差异值必须大于它们的区域内差异。Graph-based 方法通过将图上的节点进行聚类来实现，且生成的超像素就是像素集合的最小生成树。它的运行速度很快，但不能控制超像素的数量和紧凑度。Hoiem 等人将 Graph-baased 用于深度估计中。 2.2.2 Superpixel lattice 方法
对于目前的一些超像素分割算法，存在丢失原始图像重要 的拓扑结构信息这一缺陷，Moorer 等人提出了一种 super- pixel lattice 无监督的过分割算法。该方法描述了一种能保持 图像拓扑结构的贪心算法，虽然增加了拓扑信息约束条件，但 是它在速度和分割精度上保持了良好的性能。 Superpixel lattice 算法输入的是图像的边界图，目的是搜 寻穿过图像的最小权重路径，在边界代价图最小处分割图像。 通过在垂直和水平条带两个方向搜索最优路径，不断地将图像 从垂直和水平方向进行二分来得到常规网格超像素。( a) 是将图像从左到右、从上到下依次分割图像，每条路径 将图像分为两部分，就可以得到四个区域，且在预先设定的带 条中搜索最优路径; ( b) 是不断在水平和垂直方向增加路径， 使图像被分割为九个区域。
10