Charles Z.

从层次聚类到Graph-based图像分割

Filed under Computer Vision and Machine Learning on 21 Apr, 2014


本文源于上周知乎面试中面试老师的一个问题，“除了k-means聚类以外，你还知道哪些聚类方法？”想了半天，发现居然不知道其他任何的聚类方法，回来后赶紧补充了一下，发现一类更简单直观的聚类方法，叫做层次聚类，而由层级聚类联想到基于图的图像分割，两者非常相似，后者是将前者就图像领域的应用进行了拓展，并且做了更多的全局性上的优化。本文分三步走，首先介绍层次聚类，其次讲解基于图的图像分割算法，最后对两者的特点进行比对与总结。

一、层次聚类

首先我们大致了解一下目前常用的聚类算法：

代码

层次聚类算法又称为树聚类算法,它使用数据的联接规则,透过一种层次架构方式,反复将数据进行分裂或聚合,以形成一个层次序列的聚类问题解.本文仅以层次聚类算法中的层次聚合算法为例进行介绍.层次聚合算法的计算复杂性为O(n2),适合于小型数据集的分类. 该算法由树状结构的底部开始逐层向上进行聚合,假定样本集 S={o1,o2,...,on}共有 n 个样本.

  1. [初始化]. 置每个样本 oi 为一个类; 共形成 n 个类:o1,o2,...,on
  2. [找最近的两个类]. \(distance(o_r,o_k) = min_{\forall{o_u,o_v \in S,o_u \neq o_v}}distance(o_u,o_v)\)从现有的所有类中找出距离最近(相似度最大)的两个类 or 和 ok3. [合并\(o_r\)和\(o_k\)]. 将类\(o_r\)和\(o_k\)合并成一个新类\(o_rk\); 现有的类数将减 1
  3. 若所有的样本都属于同一个类,则终止本算法;否则,返回步骤HA2.

如何判断两个cluster之间的距离？一开始每个数据点独自作为一个类，它们的距离就是这两个点之间的距离。而对于包含不止一个数据点的cluster，就可以选择多种方法了。最常用的，就是average-linkage，即计算两个cluster各自数据点的两两距离的平均值。类似的还有single-linkage/complete-linkage，选择两个cluster中距离最短/最长的一对数据点的距离作为类的距离。个人经验complete-linkage基本没用，single-linkage通过关注局域连接，可以得到一些形状奇特的cluster，但是因为太过极端，所以效果也不是太好。

层次聚类最大的优点，它一次性地得到了整个聚类的过程，只要得到了上面那样的聚类树，想要分多少个cluster都可以直接根据树结构来得到结果，改变cluster数目不需要再次计算数据点的归属。层次聚类的缺点是计算量比较大，因为要每次都要计算多个cluster内所有数据点的两两距离。另外，由于层次聚类使用的是贪心算法，得到的显然只是局域最优，不一定就是全局最优，这可以通过加入随机效应解决，这就是另外的问题了。

由聚类我们自然的想到它的一个应用场景，就是图像的分割，如果把图像中的每一个像素点看成是一个item，那么图像分割的任务就是将所有的items进行聚类，属于一个类里面的所有像素就构成了一个区域，最终的分割结构就是若干个区域组成的。由此我们过渡到本文的第二部分，基于图的图像分割算法。

二、基于图的图像分割算法

1、背景介绍

主要参考的是这篇文章《Efficient Graph-Based Image Segmentation》 Pedro F.Felzenszwalb

文章首先自己定义一种区域边界的度量方法，其度量方法是在基于图的图像表示法之上去定义的。 在这种度量方法之上，我们衍生出来比较高效的图像分割算法。该算法是一种贪婪算法，并且分割结果满足全局属性。

通过上述逻辑关系可以看出，文章定义的度量方法需要比较准确，有一定的物理意义在里面，不然即使算法再高效，度量本身有问题，那么分割出来的图像区域也是不准确的。那么文章自然的可以分为两个部分1）区域度量方法。2）高效分割算法

图像分割的在很多应用中非常重要，是很多高层应用的前提，比如识别、索引等，我们不具体举例。我们认为图像分割的方法有下面这样的特性：

  • 能够捕捉到感知上比较重要的区域，这通常体现在图像的全局特性方面。这里有两个关键点，一方面要提供感知重要的精准属性，另一方面能够确定给定的分割技术是做什么的。我们认为应该有对分割结果属性的经确定以，这样的方法才能够更好的被理解，进而与其他的方法进行比较。
  • 高效，接近图像像素点数量的线性时间复杂度。为了能够实际使用，我们认为分割方法应该与边缘检测或者其他low-level图像处理技术有着相似的时间复杂度，意味着时间复杂度是线性，而且常系数也比较小。比如每一秒能对几帧图像进行分割的算法就能 够处理实时的视频数据。

然而，近几年的一些方法并不能够达成上述两方面要求，哪些方法太慢以致不能实践中使用。相比较而言，本文提到的方法已经因公在大尺度图像数据集应用上。有一些其他的方法可以比较快速的进行图像分割，但是这些方法不能捕捉感知上重要的非局部特性，下文会提到。总而言之，本文在保证效率的同时考虑到了图像全局属性上的感知重要区域。

首先我们来看一幅人造图像：

代码

我们人眼会认为这幅图像有三个区域，这个例子能够解释什么是感知重要属性（conceptually important property）。首先，亮度的变化不应该单独的座位分割区域的衡量标准。比如图像中左侧渐变区域和右侧的高频噪声区域都有较大的亮度变化，但是我们他们应该被分割成多个区域。因此，假设一个区域有着接近恒定的或变化很小的亮度是不正确的。 第二个感知重要属性是有意义的区域不能单纯的依靠局部划分标准。还是在图上我们可以看到原因，渐变图像与常量区域的边界上的亮度差值比很多高频区域的差值要小，因此我们得出结论，为了分割一幅图像，我们需要引入一些适应性的或者非局部的衡量标准。 我们在下一节提出的衡量标准会比较两个属性：

  • 边界的亮度差值
  • 区域内部的邻居像素间的亮度差值

直观上，两个区域的边界上的亮度差值如果比比两个区域中至少一个区域的内部像素差值大的话，那么边界亮度差值会更多的影响我们的感知，这个时候我们说边界亮度差是感知重要的。

2、基于图的图像表示

好下面我们来进入正题，基于图的图像分割（Graph-Based Segmentation）。 我们使用基于图的方法来做图像分割，令\(G=(V,E)\)表示一个无向图，点集\(v_i \in V\)，待分割的元素集合。边\((v_i,v_j) \in E\)有一个相应的权重\(w((v_i,v_j))\)，是一个非负值，描述两个相邻元素\(v_i\)和\(v_j\)的不相似度。在图像分割，也就是本文的语境下，V中的元素就是像素点，边就是它的两个像素点（这两个像素点是相邻的）不相似性的某种度量（例如亮度，颜色，运动，位置或者其他局部属性）。在文章的最后我们会讨论比较特殊的边集合和权重函数，不过这里的公式和不相似性度量的方法是独立的，我们可以按照自己的需求定制度量方案，这里讨论的是大框架。

在基于图的方法中，一个分割方案S是V的一个划分，每一个区域(region or component)\(C \in S\)对应着图 \(G^` = (V,E^`)\)的一个连通区域，其中\(E^` \subseteq E\)。有许多方法来衡量一个分割的好坏，大体上我们希望一个区域内部的元素尽可能相似，不同区域之间的像素尽可能不同。这意味着同一区域内，相邻两个点的有相对来说比较小的权值，不同区域的相邻两个点的边有大的权值。

3、成对的区域比较预测，内部不相似度与外部不相似度

这一节我们首先定义一个预测，D，来估计是否存在一个显著的证据表明有一个边界能将两个区域分割开。就像上文说的，就是对外部的不相似性与内部不相似进行比较，也就是比较inter-component和within component的差值。

我们定义内部不相似性为该区域最小生成树的最大边，\(MST(C,E)\)，即： \[Int(C) = \mathop {\max }\limits_{e \in MST(C,E)}w(e)\] 这个方法潜在的直觉是一个区域C，它保持连通的最低要求是Int(C)这个edge所决定的。

定义两个区域的不同：区域\(C_1,C_2 \subseteq V\)，连接这两个区域的所有边的权值中，最小的那个权值。即，

\[Dif(C_1,C_2) = \mathop {\min }\limits_{v_i \in C_1 ,v_j \in C_2, (v_i,v_j) \in E}w((v_i,v_j)).\] 如果两个区域没有连接的边，则令\(Dif(C_1,C_2) = \infty\) 这个定义理论上可能会有问题，因为它只反映了（或者说只考虑到了）两个区域间权值最小的那条边。在实践中我们发现尽管有显著的局限，但这种度量方式结果颇佳。值得一提的是，改变这个衡量标准也是可以的，比如采用中位数或者其他的分位点，提升对异常值的鲁棒性，但这种改变会使问题编程NP-hard问题。因此一个小小的分割标准的改变会大大改变解决问题的难度。

区域比较预测法通过比较\(Dif(C_1,C_2)\)和\(Int(C_1)\)与\(Int(C_2)\)中较小的一个，来判断这两个区域是否有一个边界（换言之这两个区域是否有足够的理由保持两个区域）。

\[f(n) =\begin{cases} true, \mbox {if } \mbox Dif(C_1,C_2) > M Int(C_1,C_2)\\\\ false, otherwise \end{cases}\]

我们引入了一个阈值函数来控制我们希望的外部不相似度与内部不相似度的相差程度。 \[MInt(C_1,C_2) = min(Int(C_1) + \tau(C_1),Int(C_2) + \tau(C_2))\] 对于比较小的区域，\(Int(C)\)并不能够较好的反应局部特性，比如最极端的情况下，当\(|C| = 1\)时，\(Int(C) = 0\)。因此我们需要一个跟区域大小相关的阈值函数 \[\tau (C) = \frac{k}{|C|}\] 其中\(|C|\)表示的是区域C的大小，k是一个常数。越是小的区域，我们越希望较大的外部不相似性。 在实际中，我们可以调整k的取整来获得不同的效果。当k值很大时，算法倾向于分割出来较大的块，当k值较小时，算法倾向于更细的划分。

本节最后我们探讨一个比较有趣的话题，就是\(\tau\)函数的选取，如果我们改变这个函数，不会对算法的大框架造成影响，而会对分割结果的倾向性有影响。比如我们可以让分割倾向于某一种形状A，令\(\tau\)函数在区域不是形状A的时候较大即可。这种形状上的倾向可以比较简单，比如希望正方形的或者扁平状的，也可以比较复杂，是一种特殊的形状。

4、分割算法

本节讲解主要的算法部分，怎样利用上述的定义，在基于图的表示方法下，做出高效而准确的分割。算法的核心： 输入是一个图\(G=(V,E)\)，有n个点和m个边。输出是一个分割V，分割成\(S=(C_1,...,C_2).\)

  1. 对E进行排序，生成非递减的序列\(\pi = (o_1,...,o_m)\)
  2. 从初始分割\(S^0\)开始，每一个点\(v_i\)自己就是一个区域
  3. 对于每一个\(q = 1,...,m\)重复步骤3
  4. 通过\(S^{q-1}\)构建\(S^q\)，使用如下的方式：令\(v_i\)和\(v_j\)表示按顺序排列的第q条边的两个点，比如\(o_q = (v_i,v_j)\)。如果\(v_i\)和\(v_j\)在\(S^{q-1}\)中连个不同的区域下，并且\(w(o_q)\)比两个区域的内部不相似度都小，那么合并这连个区域，否则什么也不做。用公式来表达就是：令\(C_{i}^{q-1}\)是\(S^{q-1}\)的一个区域，它包含点\(v_i\)；令\(C_{j}^{q-1}\)是\(S^{q-1}\)的一个区域，它包含点\(v_j\)。如果\(C_{i}^{q-1} \neq C_{j}^{q-1}\) 并且\(w(o_q) \leq MInt(C_i^{q-1},C_j^{q-1})\)，那么通过合并\(C_{i}^{q-1}\)和\(C_{j}^{q-1}\)我们得到了\(S^q\)；否则的话\(S^q = S^{q-1}\)
  5. 返回\(S = S^m\)

分类结果如图所示：

代码

三、总结

可以感受到本文提到的图像分割算法跟层次聚类算法非常相似，将层次聚类改造成本文的算法需要采用以下三种措施：1）将层次聚类每次计算类中心的方法设置为每次计算类内部所有点最小成生树的最大权值，2）判断是否合并两个类时设置一个权重函数，3）将聚类的终止条件设置为所有外部不相似度大于内部不相似度超过了一定阈值。

从某种意义上说，层次聚类是一个大的框架，而基于图的图像分割是在图像分割上多加了骨头，使他更适用于图像分割的领域，而使用者可以在骨头上继续加肉来达到不同的分割效果。

A survey of graph theoretical approaches to image segmentation这篇文章对各种基于graph的图像分割做了总结，文章将分类方法分成5类：

  1. 最小生成树法
  2. 基于代价函数图分割算法
  3. 基于马尔科夫随机场模型的图分割算法
  4. 基于最短路径法
  5. 其它方法

文章对MST方法做了如下的评价：

MST based algorithms explicitly define the structures of clusters. Pixels expressed by low level features such as intensity, color or texture can be intuitively organized by these algorithms. However, the algorithms are strongly based on the assumption that labeling of pixels in the same segment is consistent. This is not always the case when these pixels belong to different object classes. Therefore, this category of algorithms is often used as an initial processing for other high-level applica- tions [41,42]. MST often forms a segmentation by cutting it at the highest edge weights, so a further region can be obtained by making a further cut in the tree. This implies a hierarchical segmentation in MST, which provides a mechanism for converting any over-segmentation into the higher-level counterparts with- out loss of the cluster feature.

这种算法假设一个分割内的所有像素的标签都是一致的，这个假设在大多数情况下成立，当这些像素属于不同的。

本文提到的图分割是第一种方法里的一种高级算法

图像分割的算法讲解高于段落，如果之后有时间会深入进行源码的分析讲解。

参考

  • Felzenszwalb, P. F., & Huttenlocher, D. P. (2004). Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2), 167–181. doi:10.1109/ICIP.2010.5653963
  • Peng, B., Zhang, L., & Zhang, D. (2013). A survey of graph theoretical approaches to image segmentation. Pattern Recognition, 46(3), 1020–1038. doi:10.1016/j.patcog.2012.09.015
  • 孙吉贵, 刘杰, 赵连宇. (2008). 聚类算法研究. 软件学报, 19(1), 48–61. doi:10.3724/SP.J.1001.2008.00048
  • 聚类算法实践（一）——层次聚类、K-means聚类
  • Source Code Matlab Version

Show Comments