次分水岭对输入图像进行预处理，然后将得到的小区域代替像素点构造一个加权图，并且利用图像的色彩和空间信息构造新的权值矩阵，最后应用 Ncut 方法得到最终的图像分割结果。
依据凝聚层次聚类算法的思想，我们在经过初始过分割之后，得到了保留了原图像边界信息的超像素集。随后，在将超像素合并以弥补 Normalized Cuts 的过分割时，总是把图像中最相似的两个超像素合并，变成一个新的超像素，然后更新合并之后的超像素的有关统计量以及和它邻接的超像素对的能量函数。综合分析了其他算法的优势和缺点，我们的算法是在合并的初始阶段，使用Normalized Cuts 算法将原图像过分割为 s 个超像素，每个超像素大小相近，形状类似，并且能很好地保留了原图像中的边界。在初始分割时，类别数目也就是超像素的数目可以选择固定的数目，比如 100 个左右的超像素，这样既满足初始过分割的要求，又能取得较高的运算效率。定义一个 s*s 的能量函数矩阵C，C(vi,vj)表示超像素vi和 vj合并的代价，C(vi,vj)越小，超像素vi和 vj越应该早合并。C(vi,vj)的初始值为：
vi,vjareadjacent?(1????)D(vi,vj)??B(vi,vj)??U(vi,vj)C(vi,vj)?? （13）
??v,varenonadjacentij?其中 0< α,β <1 ， 0< α + β <1 ，实验过程中，初始阶段由于超像
素相对比较小，边界面积所占的比重较大，即交集信息比较重要，我们给α赋值为 0.3，β赋值为 0.4。当聚类到后期，类别数目小于 20 的时候，边界面积相对于各个超像素自身的面积较小，交集信息的可信度变弱，所以将α的值调整为 0.2。D(vi,vj)、B(vi,vj)和(vi,vj)的含义见上一章，分别表示超像素包含的像素点集、交集信息和并集信息对于两个超像素是否合并的影响。因此，合并的过程就是每次将能量函数矩阵C中C(vi,vj)值最小的两个超像素vi和 vj合并，然后更新能量函数矩阵C。因为超像素vi和 vj的合并只会影响到之前vi或 vj相邻的超像素与vi,vj合并后的超像素的能量函数值，所以只需要更新在vi和 vj合并之前C(x,vi)或者 C(x,vj)不为 0 的超像素x与vi,vj合并后的超像素的能量值就可以了。
以下先展示的是未进行合并策略的超像素分割后的图片：
21
SLIC Marker-Watershed Graph-based Meanshift
区域合并基本方法：区域合并是实现比较精细的分割重要方法，常采用的方
法可以是层次区域合并（Hierarchical Stepwise Region Merging),也可以是简单的剔除小区域（EDISON源码里面的Prune函数)。层次区域合并虽已提出多年，但仍然是顶尖的方法（K. Harris, 1998, IEEE TIP, Hybrid image segmentation using watershed and fast region merging），这个文章里面提及了区域邻接图
（Region Adjacent Graph, RAG）和最近邻域图（Nearest Neighbor Graph，NNG）的概念，非常清晰明了。虽然后来有些人对RAG和NNG翻译了一下，在中文期刊上发表了不少文章，其实都是简单的实现了一遍，翻译了一下。在我看来没有啥创新，不过大家可以搜搜看，作为学习的参考。对这些方法的改进提了一些，但是有些是站不住脚的，仅仅是因为编程水平有限，没有把别人的方法实现好，以此却说别人的方法效率低。具体我就不点出来了。 RAG和NNG记录区域合并一个简单的示例
区域合并的代价：最早，区域合并是问题的数学解释其实是分片的影像拟合（Jean-Marie Beaulieu，1989， IEEE TPAMI, Hierarchy in Picture Segmentation: A
22
Stepwise Optimization Approach ),每次的区域合并都会带来整个拟合误差的增加，这个增加量称之为合并代价，在图2中表现为，图的每条边都是有权重的，这个权重就表示这两个区域合并对整个图像拟合误差带来的增加量。 Ci,j?Ni?NjNi?Nj??i??j?2 其中N表示面积，μ表示区域的光谱平均值，这个合并代价后来又衍生出了很多版本这个是大家关注的重点。比如把（μi-μj)2换成光谱直方图距离的，加，入形状约束的，加入纹理约束的等等。这个选择取决于你处理的图像是啥，比如对于SAR图像，可能得更多的考虑统计特性，对于高光谱的遥感影像，得考虑光谱曲线相似性等。因为个人是研究遥感图像处理的，对于普通的遥感图像，自然影像，推荐Multi-resolution, object-oriented fuzzy analysis of remote sensing data for GIS-ready information这篇文章中的准则,主要是其适应性比较好，比较稳定。（顺便打个小广告：A Spatially-Constrained Color-Texture Model for Hierarchial VHR Image Segmentation，其实效果也很好，不过稍慢一些，毕竟模型复杂很多)。以下是两者准则下的效果：
通过对比就可发现了，其实SLIC对于区域合并而言，效果一般。其实在当前流行的超像素分割中，SLIC已经算好的了，其他的方法效果相比真是没法看了....
23
算法效率：如果按照原版的RAG和NNG实现，速度非常快的，关键看你技术水平怎么样了，具体实现非常麻烦，我用到了RBTree这样的结构，如果有用C++编程实现该功能的看官，可以考虑下什么地方可以用这个优化下。在我实现的版本里，对于481*321的图，采用以上超像素分割方法和推荐的合并准则，对于约700个初始区域，包括读取影像，区域合并，保存结果，花费0.236s，1200个初始区域 0.26s，更极端的，154401个初始区域（1个像素1个区域），花费2.1s，用我那个相比复杂一点的准则，时间略多一些，大概是前一组实验的2.5倍时间。 2.1s合并掉15W个区域，速度其实已经满足绝大多数的计算机视觉和模式识别中的图像处理需求了，如果进行并行可以实现近乎实时了。
24
第4章 总结与展望
当前，图像分割作为图像理解领域关注的一个热点，未来的发展需要研究者们借鉴数学、统计学、神经学、认知心理学、计算机科学等众多领域的成果，并且综合运用，不断引入新的理论和方法。过去几年，研究人员不断将相关领域出现的新理论和新方法应用到图像分割中，虽然取得了一定的效果，但仍未出现一种令人满意的通用有效的方法。其主要原因是人类对视觉系统还没有充分的认识，已有的模型只是从功能上来模拟，而不是从结构上来实现。超像素的计算是近年来研究学者们广泛关注的一个话题，其能量函数同时考虑边界的信息约束和区域信息的约束，在获得能量最小的同时达到全局最优的分割结果，有效避免了容易陷入局部最优的分割结果。鉴于 Normalized Cuts 的良好特性，该方法己越来越广泛的被应用于图像处理领域。 本文采用了基于超像素的渐进合并算法进行图像分割，使用超像素作为节点来代替传统的像素节点，大大地减少了图的节点数，同时很好地保留了图像本身的边界信息。超像素块单一的特征描述并不能很好的描述超像素的全部信息。为了使得不同种类的超像素块有更鲜明的区别性，同一种类的超像素块有更好的一致性。本文方法使用位置、颜色、纹理和边界特征组合对超像素进行描述。实验表明，该种组合特征能更准确的捕获超像素的更全面的信息，有利于衡量相邻超像素的简单相似性。
超像素还可以应用在图像处理任务的其他方面，Gu 等人将超像素运用于图像场景分类，先把图片分割为超像素 子块，并提取图像 SIFT 特征，形成上下文视觉特征描述符，Tighe 等人将超像素运用在场景成分分析中，提出了一种简单、无参 数且高效的图像解析方法。Fulkerson 等人阐述了在图像上 使用超像素来定位目标和分割目标类的方法。他们的方法在 Graz-02 和 PASCAL VOC 2007 数据集上实验的效果超过了现 有的许多图像分割方法。 基于层次聚类思想的渐进合并算法效率低下仍是难以避免的缺点。每一次合并之后都需要更新能量函数矩阵，计算量比较大。总之，运用图论的方法研究图像中各个元素之间的关系，综合考虑全局与局部特性，进而进行图像分割的方法符合人类视觉原理，可以取得比较好的实际分割效果。要使分割效果更加理想，我们认为应该从两个方面入手：第一，进一步研究人
类视觉探测和分析的原理，进而才能对其进行模拟；第二，进一步探索图的性质和图的分割方法，加快算法的运行效率。
25