图划分算法

Ⅰ 什么是图像分割

1 数字图像处理技术是一个跨学科的领域。随着计算机科学技术的不断发展，图像处理和分析逐渐形成了自己的科学体系，新的处理方法层出不穷，尽管其发展历史不长，但却引起各方面人士的广泛关注。首先，视觉是人类最重要的感知手段，图像又是视觉的基础，因此，数字图像成为心理学、生理学、计算机科学等诸多领域内的学者们研究视觉感知的有效工具。其次，图像处理在军事、遥感、气象等大型应用中有不断增长的需求。

基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热点。该方法将图像映射为带权无向图，把像素视作节点。利用最小剪切准则得到图像的最佳分割 该方法本质上将图像分割问题转化为最优化问题。是一种点对聚类方法。对数据聚类也具有很好的应用前景。但由于其涉及的理论知识较多，应用也还处在初级阶段。因此国内这方面的研究报道并不多见，本文将对图论方法用于图像分割的基本理论进行简要介绍，并对当前图论方法用于图像分割的最新研究进展进行综述，并着重介绍基于等周图割的图像分割的方法。

2 图像目标分割与提取技术综述

图像分割是一种重要的图像技术，在理论研究和实际应用中都得到了人们的广泛重视。图像分割的方法和种类有很多，有些分割运算可直接应用于任何图像，而另一些只能适用于特殊类别的图像。有些算法需要先对图像进行粗分割，因为他们需要从图像中提取出来的信息。例如，可以对图像的灰度级设置门限的方法分割。值得提出的是，没有唯一的标准的分割方法。许多不同种类的图像或景物都可作为待分割的图像数据，不同类型的图像，已经有相对应的分割方法对其分割，同时，某些分割方法也只是适合于某些特殊类型的图像分割。分割结果的好坏需要根据具体的场合及要求衡量。图像分割是从图像处理到图像分析的关键步骤，可以说，图像分割结果的好坏直接影响对图像的理解。

3 定义及分割方法
为后续工作有效进行而将图像划分为若干个有意义的区域的技术称为图像分割(Image Segmentation)
目前,有许多的图像分割方法,从分割操作策略上讲,可以分为基于区域生成的分割方法,基于边界检测的分割方法和区域生成与边界检测的混合方法.

Ⅱ 如何在matlab中进行图像的网格划分。

可以使用meshgrid函数

meshgrid是MATLAB中用于生成网格采样点的函数。在使用MATLAB进行3-D图形绘制方面有着广泛的应用，函数效果如下图所示：

函数功能：

生成绘制3-D图形所需的网格数据。在计算机中进行绘图操作时， 往往需要一些采样点，然后根据这些采样点来绘制出整个图形。在进行3-D绘图操作时，涉及到x、y、z三组数据，而x、y这两组数据可以看做是在Oxy平面内对坐标进行采样得到的坐标对(x, y)

例如， 要在“3<=x<=5，6<=y<=9，z不限制区间” 这个区域内绘制一个3-D图形，如果只需要整数坐标为采样点的话。可能需要下面这样一个坐标构成的矩阵：

(3,9),(4,9),(5,9);

(3,8),(4,8),(5,8);

(3,7),(4,7),(5,7);

(3,6),(4,6),(5,6);

在matlab中可以这样描述这个坐标矩阵：

把各个点的x坐标独立出来，得：

3,4,5;

3,4,5;

3,4,5;

3,4,5;

再把各个点的y坐标也独立出来：

9,9,9;

8,8,8;

7,7,7;

6,6,6;

这样对应的x、y结合，便表示了上面的坐标矩阵。meshgrid就是产生这样两个矩阵，来简化我们的操作。然后根据(x, y)计算获得z，并绘制出三维图形。

在Matlab命令窗口中键入type meshgrid可以查看该函数的源代码（由此可以理解meshgrid的算法思想）， 键入doc meshgrid或者help meshgrid可以获得帮助文档。

语法

[X,Y] =meshgrid(x,y)

meshgrid返回的两个矩阵X、Y必定是行数、列数相等的，且X、Y的行数都等于输入参数y中元素的总个数，X、Y的列数都等于输入参数x中元素总个数（这个结论可以通过查看meshgrid的源代码得到，可以通过示例程序得到验证）。

[X,Y]=meshgrid(x)与[X,Y]=meshgrid(x,x)是等同的

[X,Y,Z]=meshgrid(x,y,z)生成三维数组，可用来计算三变量的函数和绘制三维立体图

相关函数： plot3、mesh、surf、automesh、ndgrid

Ⅲ 选择性搜索算法 （Selective Search)

计算机视觉领域有几个基本的任务：

object detection 的基础是 object recognition，只不过要先将图片进行分割，对每个分割之后的子图区域 region （也称为 patch） 进行 object recognition.

由于事先并不知道物体在图片的哪个位置，为了避免漏检，我们应该对图片中尽量多的 region 进行搜索。理论上来说，可以有无穷多个 region。这里就需要一种 region proposal 的算法，以比较高效的方式提出图片划分 region 的方式，从而加速整个 object detection 的过程并且提高准确率。

本文将要介绍的 selective search 算法 ，是比较经典的，也是 R-CNN 中使用的 region proposal 算法。

参考文献：

为了避免蛮力搜索，selective search 算法首先需要一个基于像素的图像分割。这里用的是 Felzenszwalb and Huttenlocher 算法 （因为是当时速度最快的算法，而且是公开的），得到一个 oversegmented 的图像分割。例如：

这里之所以用 oversegmented 图像，是为了得到尽可能细分的区域，再以此为基础逐步合并，形成更大的区域。

image segmentation 可以用作 region proposal 的基础，每个分割的区域都可以看作一个潜在的 region，但是一个 object 往往包含了多个分割的区域，例如盛有咖啡的杯子，咖啡和杯子应该作为一个整体来看待。因此，还要根据某种相似性原则进行分割区域的合并，得到更大范围的 region。

Selective search 算法考虑了 4 种相似性度量，取值都在 [0,1] 之间，越大越相似。

最终的相似性度量是上述四个度量的组合：

其中 取 0 或 1.

总结起来，selective search 的算法步骤非常简单：

环境配置：

具体程序：

最后效果如下：

显示的 100 个 region 已经包含了我们感兴趣的待检测区域，说明了 selective search 算法的高效。