数字图像处理大作业：图像分割项目之论文阅读（使用SLIC获取超像素，对超像素使用AP聚类）

本文先对论文“SLIC Superpixels Compared to State-of-the-Art Superpixel Methods”做一个论文阅读报告，再稍微介绍一下其他论文，介绍算法原理。下一篇文章会按之前小作业的格式写技能学习、编程过程、代码结构介绍、实验结果分析与感想。

SLIC论文阅读报告

在搜索引擎中可以找到很多分析此论文的中文博客。比如这篇博客分析了代码实现原理。论文中的代码实现网页我怎么都打不开，只能从这篇博客里来获取代码实现的细节。另一篇博客分析了论文代码实现上的性能缺陷。直接看一些中文博客的分析就能对论文的方法理解个大概，再看论文的时候就会比较顺利。

内容梗概

本文对当时的5种超像素方法进行了比较，并提出了一种simple linear iterative clustering (SLIC)(简单线性迭代聚类)的生成超像素的算法。

超像素就是一些像素的集合。超像素的边缘要和图像中物体边缘大致符合。一般获取超像素是其他数字图像处理的预处理工作。图像分割就可以先进行超像素预处理，把每个超像素当成原来算法中的像素来处理，减少数据规模。

算法流程

算法整体上接受一个参数$k$，表示期望的超像素的个数。算法输出$k$个超像素中心以及每个像素属于哪个超像素。

每个像素被看成一个五维量$(l,a,b,x,y)$，前三维是LAB颜色空间信息，后两维是像素位置信息。算法均匀地初始化$k$个超像素中心，并计算超像素间距$S=\sqrt{N/k}$（$N$是像素个数）。之后遍历所有像素中心，找到每个像素周围$2S\times2S$范围内在一种距离度量下”最近“的超像素中心。每个像素”分类“完成后，把一类像素的五维平均值当成新的超像素中心，并以计算本轮分类方式和上一轮的残差。算法不断重复上述过程直到残差收敛至0。

以上只是一个算法的大致描述，算法的具体细节如下：

距离度量方式

如果单纯地把两个像素的距离定义成五维量的距离，就会出现一个问题：像素距离给整体距离的影响是不确定的。如果要求的$k$值较小，每个像素离超像素中心的距离较大，那么像素距离就会给整体的距离带来更大的影响。为了让像素距离和颜色距离对距离的影响权重更为平衡，文章提出了如下的距离度量方式：

$$\begin{aligned} d_c &= \sqrt{(l_j-l_i)^2+(a_j-a_i)^2+(b_j-b_i)^2} \\ d_s &= \sqrt{(x_j-x_i)^2+(y_j-y_i)^2} \\ D' &= \sqrt{(\frac{d_c}{N_c})^2+(\frac{d_s}{N_s})^2} \end{aligned}$$

其中$i,j$表示两个进行距离比较的像素，$N_c,N_s$是用于标准化颜色距离和像素距离的量。

文章取 $N_s = S=\sqrt{N/k} $，$N_c$直接定义为一个常数$m$。文章建议$m$取$[1,40]$。现在距离定义成了如下形式：

$$\begin{aligned}D' &= \sqrt{(\frac{d_c}{m})^2+(\frac{d_s}{S})^2}\end{aligned}$$

实际实现时出于方便，距离用以下公式计算：

$$\begin{aligned}D &= \sqrt{ {d_c}^2+(\frac{d_s}{S})^2m^2}\end{aligned}$$

另外，当图片的形式发生变化时，公式可以很方便地修改。如果图片是灰度图，那么颜色度量只需要考虑灰度之间的差就行了；如果不是图片而是三维体素，那么只需要把空间距离加上$z$分量。

保证超像素连续性

由于像素分类的时候除了位置的相似性外，还考虑了颜色的相似性，这样会出现一些问题：一个靠左的像素，可能属于右边像素中心；一个靠右的像素，可能属于左边像素中心。这样的话同类的像素可能被另一类的像素切成了两块，在图像上并不连续。

为了强制同一类超像素连通，算法在迭代结束后又对超像素进行了处理。算法从上到下，从左到右尝试搜索未标记的像素。对正在搜索的像素，把其四邻域中与它属于同一个旧超像素的像素加入搜索队列，并标记其和当前搜索像素属于同一个新超像素。当前这片新超像素搜索结束后，若新超像素总数少于期望超像素大小的一半，则把当前超像素的标记改成上一个新超像素的标记。上一个新超像素是当前新超像素搜索起点四邻域中的一个新超像素。

初始超像素中心优化

初始的超像素中心如果处于梯度比较大的点的话，可能会影响算法之后的表现。

该算法实现时，计算每个初步选择的超像素中心的$3\times3$邻域的梯度，把梯度最小的像素作为最终的初始超像素中心。

梯度的计算是$x,y$方向上梯度之和。$x$方向梯度是左右两个像素颜色向量的差平方和，$y$方向梯度是上下两个像素颜色向量的差平方和。

默认参数

由于残差收敛很快，算法默认迭代10次。这样残差可以不用计算了。

颜色距离参数$m$固定为10。

基于超像素的图像分割

仅获得了图像的超像素还不够，还需要一些其他的方法来做图像分割。我又去找了一些基于超像素的图像分割论文。

我浏览了以下论文：

[1] Li Z, Wu X M, Chang S F. Segmentation using superpixels: A bipartite graph partitioning approach[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2012: 789-796.

[2] Zhou B. Image segmentation using SLIC superpixels and affinity propagation clustering[J]. Int. J. Sci. Res, 2015, 4(4): 1525-1529.

[1]论文本身质量较高，且没有使用深度学习的方法。论文提出了一种基于超像素和二分图分割的图像分割方法，需要输入类别数$k$，输出图像分割结果。我一开始看到了标题中的二分图，以为图像分割会被转换成一个可以用我十分熟悉的二分图算法解决的问题。但是文章莫名其妙地把问题变成了一个我很陌生的二分图分割的问题。我既没有从文章不清晰的叙述中理解问题转换的原理，也不愿去学一个看起来比较复杂的二分图分割算法。所以最后放弃了实现这篇论文的方法。

在Google上搜索”superpixel based segemenataion”或”image segmentation using superpixel”，都能搜出这个网站。该网站的作者实现了一个基于超像素的图像分割算法，其算法来自论文[2]。论文[2]非常直接地把SLIC和AP聚类两个算法拼接起来，得到了一种基于超像素和聚类的图像分割算法，该算法不用指定类别数。正好，我觉得超像素这个预处理已经对图像分割帮助很大了，只需要一个简单的超像素分类算法即可。我最终决定学习论文[2]的方法。

学论文[2]不应该去看那篇论文，而应该去看AP聚类算法的论文Clustering by Passing Messages Between Data Points。这种聚类算法比较有名气，搜索引擎上可以找到不少分析此算法的中文内容。

AP算法需要提供数据间的相似度这一二元关系矩阵，输出每个数据点属于的数据中心。AP算法的思想我没有理解，但其流程十分简单：算法构建了两个关系矩阵$r，a$，用以描述某个点适合作为另一个但数据中心的程度。算法用两个公式来更新这两个关系矩阵直至矩阵收敛。特别地，为了防止数值上的问题，算法引入了一个更新系数$\lambda$，每次保留$\lambda$倍的上一轮值，加上$(1 - \lambda)$倍更新值。这个比例系数在数值算法中非常常见，有点像梯度下降中的学习率。

如果我把AP算法理解了，会写一篇博客来详细介绍这一算法。

把AP算法运用在图像分割中，只需要定义图像任意两个超像素间的相似度就行了。论文[2]的主要贡献也就是定义相似度。论文[2]比较了3种相似度定义方式，最终选择了效果最好，也最简单的一种定义方式：相似度定义为负带权颜色向量差平方和，即：

$$s(i,j)=-[w_l(L_i-L_j)^2+w_a(a_i - a_j)^2+w_b(b_i-b_j)^2]$$

其中$s(i,j)$表示超像素$i,j$间相似度，$L,a,b$是超像素平均LAB颜色空间颜色向量分量。

论文中超像素数$K=600$，超像素颜色距离参数$m=20$，颜色权值$w_l=3,w_a=10,w_b=10$。理论上这些参数都是可以调的，甚至相似度的定义参数也是可以调的。