ChenJM
图像分割

  01 Jan 2015

Graph-cut

一种基于边界和区域的交互式图像分割算法、一种基于图论的全局优化算法。其基本思想是，图像映射为带权无向图G=<V,E,W>，把图像中ｎ个像素视为图中节点集V，E为在某个邻域系统下相邻节点之间的边集。根据图像中像素之间的空间关联度以及局部相似性特征来构造该图中各个边的权值W，从而把对原始图像的分割转化为对图的标号问题。设一个割C将节点集V分为两个互不相交且互补的集合A和B,则割C的容量为它所经过的边权值之和, ，最后图的标号过程可以通过使用组合优化中的最大流/最小割准则求得最小割 来实现。从而得到近似的全局最优结果。

Grab-cut

与graph-cut的区别:

  1. Graph Cut的目标和背景的模型是灰度直方图，Grab Cut取代为RGB三通道的混合高斯模型GMM；

  2. Graph Cut的能量最小化（分割）是一次达到的，而Grab Cut取代为一个不断进行分割估计和模型参数学习的交互迭代过程；

  3. Graph Cut需要用户指定目标和背景的一些种子点，但是Grab Cut只需要提供背景区域的像素集就可以了。也就是说你只需要框选目标，那么在方框外的像素全部当成背景，这时候就可以对GMM进行建模和完成良好的分割了。即Grab Cut允许不完全的标注（incomplete labelling）。

分水岭算法

两种方法实现方法：基于标记的分水岭变换（1）（2）、欧几里德距离映射法（3）。

  1. (记)基于标记的分水岭变换从参考图象的全局极小值点开始,假定当前值为h+1,每个极小值小于或等于h的蓄水盆会被分配一个唯一标记,对当前值为h+ 1的像素,若其邻域有已经标记过的像素,则给它分配相同标记,若周围没有一个像素是标记过的,就认为是一个新的蓄水盘,并给它分配一个新标记,反复进行标记,直到图象中的每一个像素都归类到某个蓄水盘,即属于某个对象区域为止,分水岭变换则告完成。

  2. 先把图像转化成灰度梯度级图像，在图像梯度空间内逐渐增加一个灰度阈值，进行阈值化，每当它大于一个局部极大值时，就把当时的二值图像与前一个时刻（即灰度阈值上一个值的阈值化情况）的二值图像进行逻辑异或（XOR）操作，从而确定出灰度局部极大值的位置。根据所有灰度局部极大值的位置集合可确定分水岭。

  3. 欧几里德距离映射法是通过腐蚀二值图象,即通过计算各像素欧几里德距离映射(EuclideanDistanceM aps, EDM )来生成EDM图象。并以此作为拓扑表面,再通过对其像素取值作判断来获得分割结果.EDM从最亮值开始,迭代递减至1,重复运算直至除边界线外所有的像素都填充为止.用上述方法实现初始分割时,需要首先划分出了几块大的区域,由于该方法避免了在某个大目标内,对目标进行逐层循环腐蚀,因而在速度和存储上十分有效.

种子填充算法：

  • 递归方法：选择一个种子点往外搜索新的种子点，直至搜索完毕。

  • 线扫描：线扫描的种子填充算法执行步骤如下（以手部为目标区域作为例子）：

    1. 在手部区域定位后得到的方框内，对肤色图像构建灰度积分图。

    2. 检测出积分图中峰值作为第一个种子点，因为之前的定位好的手部区域中手部的实际位置在该方框中占多数，所以该方法寻找到的第一个种子点将会落在手部的实际位置中且方便快捷。若积分图的峰值正好落在漏检的地方，则在附近另取一点。将该种子点压入堆栈。

    3. 种子点出堆栈。

    4. 由该种子点开始先往左、往右搜索像素点，遇到像素值为0的地方，保存其x轴坐标，左右分别为xl、xr。

    5. 对与扫描区域y坐标减1，以第4步中得到的xl、xr带到上一行，设定标志位初始化为0，从xr往xl进行搜索，若出现肤色像素且标志位为0，则将其作为新的种子点，压入堆栈内并将标志位置1。若标志位为1且遇到非肤色像素，则标志位置0，继续往左搜索，以解决肤色块内有缺陷（空洞）的问题。

    6. 对扫描区域y坐标加2，后与第5步相同，进行搜索，将新的种子点压入堆栈。

    7. 跳转至第3步，循环进行，直至堆栈中种子数量为零，完成连通域的搜索。