锐客网

  1. 首页 > it技术 > >

图像分割|mean shift（从图像分割到特征空间分析）

计算机视觉图像分割

mean shift：从图像分割到特征空间分析 题外话
我最先看到mean shift是作为一种图像分割的方法，原文来源(Comaniciu & Meer, 2002)。从作者介绍可以知道，mean shift并不是他提出来的，这个方法是模式识别的一种老方法，他发现这个方法在CV中很好用。
在CV的书籍中，这个方法通常被介绍作为图像分割的方法，但是这是一个值得推敲的方法，可以在很多的地方使用。
定义：一种求特征空间概率密度函数局部极大值的非参数化方法，而mean shift（以下都简称MS）是梯度的方向，即最速上升方向。
1 mean shift原理 1.1 Parzen窗方法
Parzen窗方法也叫kernel density estimation，一种特征空间概率密度函数评价的非参数化方法。
特征空间有很多特征点，不同位置的特征点的概率密度是不同的，真实的概率密度我们无法得到，只能通过已知的特征点去估计。点稠密的区域对应的概率密度会相对大一些，稀疏的地方概率密度要小一些。
在Duda的《模式分类》一书的第4章有详细的介绍，比MS文章的作者讲的更加的清楚，这里就没有必要详细介绍了。
1.2 概率密度函数梯度评价
对概率密度函数直接求导，推导过程见原文。
最重要的一点是，MS的方向和梯度方向是一致的。
其中，很重要的一步做了如下的变换
图像分割|mean shift（从图像分割到特征空间分析）
文章图片

对于该公式，我的理解是，梯度是空间所有点投票获得，每个点可以投的票数是不同的，也就是权重。第二行未拆开表示的梯度方向，是所有 向量加权获得，第三行拆开表示的梯度方向，是所有 向量加权减去 得到。前者是相对坐标，后者是绝对坐标，后者物理意义更加直观一些，有点类似于重心的概念。此外最重要的一点是，前者得到的是梯度方向，获得下一个迭代点需要考虑步长， ，而后者这种巧妙的设置，避开了步长的设置，自适应步长，直接得到下一个迭代点。
上述公式中的拆分部分，是原始的MS算法就有的，还是作者的原创，这个就没有去调查了，但是这一步是很重要的一步。
2 应用举例 2.1 非连续保护平滑
MS是求概率密度极大值的方法，那么怎么和图像关联呢？
mean shift不是直接寻找image的波峰，而是需找pdf的波峰，也就是样本点最密集的区域。
一幅图像的输入空间一般表示为二维数组，每个位置是p维向量，二维数组是像素坐标即空间域spatial domain，每个位置的值是范围域range domain，灰度图p为1，彩色图p为3。将空间域和范围域结合构成特征空间，所以维度d=p+2，每个点可以表示为(x, y, I)。
本文采用的导数核G是uniform kernel，也就是在bandwidth内取1，之外取0。mean shift等效的物理意义是，bandwidth约定一个空间长方体，求其内部特征点的重心，就是下一个迭代点。经过迭代，最终的位置就是概率密度局部极大值的位置，也是点局部最稠密的位置。每个特征点的空间域值不变，但是范围域设定为这个局部极大值，从而实现了非连续平滑保护。
原文对这一现象，从物理上形象的解释。局部极大值就像是一个引力中心，周围的点都被吸引进去，在边界上会形成了相反的两种流向。所以最终得到的图像是一块一块的，每块都由一个局部极大值决定。仔细观察原文cameraman的图像可以发现这一现象。
下面对不同的图像区域类型进行说明：
1，不同区域处理：range domain超出范围的两个区域是不会互相干扰的，所以不同区域是独立的。此外，靠近边缘的点会向区域内部靠拢。
2，同一区域处理：可以将泥泞的道路变成相对平滑的道路，但是，不是完全平的。
3，边缘处理：斜坡会变得更加的平滑，但是处于斜坡的点不会减少。对于像是椒盐噪声，是不会处理的，基本原样保持。
图像分割|mean shift（从图像分割到特征空间分析）
文章图片

图 1. 基于mean shift的灰度图滤波与分割结果.(a)input.(b)像素点mean shift路径，黑点是收敛点.(c)滤波结果 .(d)分割结果.
2.2 图像分割
mean shift的图像分割是非连续保护平滑算法的一个扩展，每个像素都关联一个在它周围的显著mode。结合聚类的方法分割图像，其实和mean shift没什么关系了。
2.3 图像跟踪
在[14]，定义模型分布于潜在目标的距离，非刚性物体可以在严重畸变下实现跟踪。距离在新帧兴趣区域内的像素求解，MS的方法用于寻找目标mode。
这部分文章只是提了一下，有时间可以看作者2003年的CAMshift。
3数学本质 3.1最优化问题视角
定义：一种求特征空间概率密度函数局部极大值的非参数化方法，而mean shift（以下都简称MS）是梯度的方向，即最速上升方向。
所以从数学的角度，MS方法是一种无约束优化方法。优化问题是寻找极值的问题，包含两个重要元素，方向和步长。常见的最速下降法（也就是梯度下降法），采用的方向是负梯度方向，而步长需要自己另外想办法解决。
沿着局部梯度方向可以保证无限步的最终收敛。基于梯度的步长对整体的表现很重要，如果步长太大，算法就不会收敛，而如果步长太小，算法就会收敛太慢。关于步长选择有一些特别的方法。
这种方法可以保证收敛的原因是mean shift向量的自适应幅度，从而就不需要额外的步骤选择合适步长了，这是这个方法优越于传统基于梯度方法的主要优点。
3.2 特征空间分析推广
第一次读本文前言可能会觉得很奇怪，因为很后面部分好像没什么关联，而作者的意图是站在一个更高的角度去看待这个方法，该方法在特征空间分析中可以推广。主要包括下面3点：
1，输入空间到特征空间的映射，特征提取必然会引入少量的参数控制。这部分是依赖于应用的。比如，本文获取概率密度函数，就需要设定窗的bandwidth。
2，特征空间cluster。特征空间稠密的区域，也就是cluster，往往对应重要的特征，描述cluster是分析的目标。这部分是独立于应用的。
图像的特征空间中，有多个特征点聚集的区域，所以图像分割类似于聚类。
3，聚类的方法很多，包括参数化方法和非参数化方法，实际主要是非参数化方法，包括分层聚类和密度评价。基于密度评价的非参数化聚类方法的原理是，特征空间可以当成所表示的空间概率密度函数。稠密的区域对应于概率密度函数的极大值，也就是未知密度的modes。一旦一个mode的位置确定了，cluster就能基于局部结构得以描述。
所以，mean shift方法可以求解概率密度函数的局部极大值，也就是一个mode，从而可以描述cluster，可以在求特征空间cluster的问题上推广使用。
4 补充 4.1 核函数选择
实际上，本文用的核都是Epanechnikov kernel，它的导数核G是uniform kernel，虽然正态核的结果几乎总是要优于它，但是步数太多。
收敛的步数与核是有关的，当G是uniform kernel，由于距离均值是有限的，在有限步长会收敛；当G是有不同权重的核（权重按照离中心的距离），mean shift就是无限收敛的，通常需要设置mean shift平移最小距离来终止。
4.2 bandwidth窗口选择
bandwidth的选择和具体的任务相关，本文没有实现自动的选择方式，而是测试不同bandwidth，决定选取。
参考文献 【图像分割|mean shift（从图像分割到特征空间分析）】Comaniciu, D., & Meer, P. (2002). Mean shift: A robust approach toward feature space analysis. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 24(5), 603-619.

    推荐阅读


    上一篇：邮件接收服务器（pop3)与发送服务器（smtp)大全

    下一篇：CASIA-B数据集的一些粗糙理解2