基于图的图像分割

I. 简介

基于图的图像分割，论文“基于图的有效图像分割”，P. Felzenszwalb，D. Huttenlocher，国际计算机视觉杂志，第1卷. 59，第2号，2004年9月

本文下载和论文提供的C ++代码在这里.

基于图的分割是一种经典的图像分割算法，其作者Felzenszwalb还是提出DPM（可变形零件模型）算法的大牛.

基于图的分割算法是基于图的贪婪聚类算法，该算法易于实现，相对快速且准确. 但是，目前，应将其直接用于较少的细分. 许多算法将其用作垫脚石. 例如，Object Propose的开创性作品“将分割作为对象识别的选择性搜索”使用它来生成过度分割.

第二，图的基本概念

由于该算法使用加权图对图像进行抽象，因此补充了图的一些基本概念.

1，图片

由顶点集V（顶点）和边缘集E（edges）组成，表示为G =（V，E），顶点v∈V，是纸上的单个像素，连接一对顶点边（vi，vj）的权重为w（vi，vj），在本文中，其含义是顶点之间的不相似（不相似），并且使用了无向图.

2. 树

特殊图. 图中的任何两个顶点都是通过路径连接的，但是没有循环. 如下图所示，黑边连接在一起. 如果您将其视为一堆乱七八糟的小珠，只将小珠和金属丝保留在树中，则可以选择任何小珠来拾取树中的所有小珠.

如果还保留了顶点i和h，则顶点h，i，c，f和g形成一个循环.

3. 最小生成树

特殊树. 给定要连接的顶点，选择边缘权重总和最小的树.

在本文中，每个像素在初始化期间都是一个顶点，然后逐渐合并以得到一个区域，特别是将该区域中的像素连接起来的MST. 如下所示，棕色圆圈是顶点，线段是边缘，通过合并棕色顶点生成的MST对应于分割区域. 分裂的结果实际上是一片森林.

三，相似性

由于它是一种聚类算法图像分割技术，应使用什么规则来确定何时将两者合并为一个，何时应继续划清界限？对于两个孤立的像素，差异是灰度值. 自然，灰色距离用于测量两个点的相似性. 在本文中，使用RGB的距离，即

当然，您也可以使用在视觉上统一的Luv或Lab颜色空间. 对于灰度图像，只能使用亮度值. 此外，您还可以先使用纹理特征过滤，然后再计算距离. 距离距离.

第四，全局阈值>>区域的自适应阈值，类内差异和类间差异

如上所述，应该使用亮度值的差异来测量两个像素之间的差异. 对于两个区域（子图）或一个区域与一个像素的相似性，最简单的方法是仅考虑连接两个边缘的不相似性. 如下图所示，已形成棕色和绿色两个区域，现在使用紫色边缘确定两个区域是否合并. 然后，我们可以设置一个阈值，并且当两个像素之间的差异（即相异性）小于此值时，两者将变为一个. 迭代合并最终将合并成区域，其效果类似于区域增长: 星星之火可以引发草原之火.

插图:

对于右上图，显然应该将其分为左上图所示的三类: 高频区域h，斜率区域s和平坦区域p.

如果我们设置一个全局阈值，那么如果要将h区域合并为一个片段，则应该选择非常大的阈值，但是p和s区域也将包括在内，并且分割结果也是如此粗. 如果将p用作参考，则应将阈值选择为特别小的值. 在这种情况下，p区域将被合并为一个片段，而h区域将被合并为特别多的小片段，例如相同的碎片镜，因此分割结果太精细. 显然，全局阈值不合适，因此使用自适应阈值是很自然的. p区的阈值特别小，s区的阈值稍大，h区的阈值大.

首先有两个定义. 原始文本基于这两个附加信息获得自适应阈值.

区域内的类内差异Int（C）

可以理解为一个区域内最大的亮度差，定义为MST中相异度最大的一侧.

两个区域之间的差异（C1图像分割技术，C2）:

也就是说，边缘的不相似性在连接两个区域的所有边缘中具有最小的相似性，即两个区域中最相似的位置的不相似性.

直观判断，何时:

何时

，这两个区域应该合并！

五个算法步骤

1. 计算每个像素与其8个相邻像素或4个相邻像素之间的相异度.

如上图所示，实线仅计算4个字段，虚线是8个邻域的计算. 灰线很好.

2. 根据不递减的不相似性（从小到大）对边缘进行排序，以获得e1，e2，...，en.

3. 选择ei

4. 对当前选定的边ej（vi和vj不属于区域）执行合并判断. 令连接的顶点为（vi，vj），

如果差异小于内部差异:

5. 更新阈值和类别标签

其他:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-183016-1.html