文章介绍了当前 State-of-the-Art 的5种超像素 (Superpixel) 的算法, 并主要从其对于图像边缘信息的拟合程度 (their ability to adhere to image boundaries), 速度, 内存利用效率, 以及它们对于图像分割性能的影响 (their impact on segmentation performance) 来综合评价.

同时, 本文还提出了一种 SLIC (simple linear iterative clustering) 的算法, 用的是 k-means clustering 的方法.

Introduction

超像素算法主要是将一幅图像中, 具有相似颜色, 纹理或者亮度等信息的相邻的像素点聚集起来, 组成一些具有一定视觉意义的像素块, 为后续处理做准备. 这种算法用少量的超像素来代替原来的图像像素, 能够减少图像的冗余度, 为计算图像特征做了很好的铺垫, 并且显著地降低了随后的图像处理步骤的复杂度. 超像素算法作为一个预处理的步骤, 现在已经成为了很多计算机视觉算法中的重要一环, 比如说图像分割 (image segmentation), 深度估计(depth estimation), 姿态预估 (body model estimation) 和目标定位 (object localization) 这些领域.

Images_segmented_using_SLIC_into_superpixels

生成超像素的方法有很多, 各自有各自的优点和缺陷. 在此主要考虑以下方面来评测对比这些算法:

Existing Superpixel Methods

Graph-Based Algorithms

这类算法主要就是把整个图像看成一张图, 各个像素是节点, 相邻像素之间的相似度作为边上的权值. 超像素就是根据最小化损失函数来构建的.

相关的方法有:

Gradient-Ascent-Based Algorithms

这类方法生对像素生成一个随机的初始聚类, 然后不断迭代优化, 直到满足收敛条件.

相关的方法有:

SLIC Superpixels

SLIC (simple linear iterative clustering) 算法是 k-means 在超像素生成方面的一个改写. 主要有以下特性:

Algorithm

  1. 聚类初始化: 按照设定的超像素个数$k$, 采取步长$S=\sqrt{N/k}$, 在图像中均匀采样选取聚类中心$C_i = \begin{bmatrix} l_i & a_i & b_i & x_i & y_i \end{bmatrix}^T$. 然后在聚类中心的$3\times 3$领域内寻找梯度最小的点, 作为新的聚类中心的位置.

    • 图像色彩空间采用 CIELAB
    • 步长$S=\sqrt{N/k}$是为了使得聚类中心分布均匀
    • 移动聚类中心是为了避免把中心建在边缘或者噪点上
  2. 像素点分类: 将每个像素点$i$与离其最近并且搜索域覆盖到它的聚类中心相关联. 若是该像素点在多个聚类中心的搜索域内, 则取距离$D$最小的那个作为其关联的聚类中心.

    • 搜索域为$2S\times 2S$

    • 将搜索域限制在一个较小的范围内, 避免了传统的 k-means 方法里每个像素点要和所有的聚类中心比较的缺点, 使得运行速度大大提高. 这也是本算法速度快的最重要的一个原因.

    reducing_the_superpixel_search_regions

  3. 分类更新: 在所有的像素都已经关联到聚类中心之后, 我们需要调整聚类中心的位置, 使得其位于与其关联的像素点的中心.

    • 这样的分配(assign)然后再更新(update)的步骤可以迭代多次, 直到满足收敛条件为止.
    • 一般来说10次就差不多了
  4. 后续处理: 通过将不相交的点分配给相邻的超像素来增强联通性 (enforces connectivity by reassigning disjoint pixels to nearby superpixels).

伪代码如下:

/* Initialization */
Initialize cluster centers C_k = [l_k, a_k, b_k, x_k, y_k] by sampling pixels at regular grid steps S.
Move cluster centers to the lowest gradient position in a 3x3 neighborhood.
Set label l(i) = -1 for each pixel i.
Set distance d(i) = \infty for each pixel i

repeat
  /* Assignment */
  for each cluster center C_k do
    for each pixel i in a 2Sx2S region around C_k do
      Compare the distance between C_k and i.
      if D < d_i then
        set d(i) = D
        set l(i) = k
      end if
    end for
  end for
  /* Update */
  Compute new cluster centers.
  Compute residual error E
until E <= threshold

Distance Measure

SLIC 算法用的是 CIELAB 的色彩空间, 再加上像素本身的坐标, 因此一个像素的全部信息需要用一个5维的向量$\begin{bmatrix} l_i & a_i & b_i & x_i & y_i \end{bmatrix}^T$来表示, 也可以说是在一个$labxy$的图像空间内.

$(l, a, b)$表示颜色信息, $(x ,y)$表示位置信息, 因此不能简单地用5维空间的欧氏距离来衡量两个像素之间的距离. 为了统一色彩与空间上的接近程度, 需要引入归一化 (normalization).

$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{(d_c / N_c)^2 + (d_s / N_s)^2}$

其中$N_c$与$N_s$分别代表最大的色彩与空间距离. $N_s$很好确定, 就是超像素的大小, $N_s = S = \sqrt{N/k}$. 然而$N_c$则根据每个聚类区域的不同而不同, 为了方便起见, 将其设定为一个常数值$m$. 因此距离$D$的定义即可表示为:

$D’ = \sqrt{(d_c / m)^2 + (d_s / S)^2}$

进而可简化为

$D = \sqrt{d_c^2 + (d_s / S)^2 m^2}$

  • $m$其实也是用来衡量色彩与空间相似度哪个更加重要的标志. $m$较大时, 表示空间相似度更为重要, 产生的超像素会更为紧凑, 区域/边缘比率较低; 当$m$较小时, 表示色彩相似度更为重要, 产生的超像素会紧贴边缘, 但是大小与形状就不会很规整. 一般来说, 使用 CIELAB 色彩空间时, $m \in [1,40]$.
  • 对于灰阶图像, $d_c = \sqrt{(l_j - l_i)^2}$
  • 对于三维的超体素, $d_s = \sqrt{(x_j - x_i)^2 + (y_j - y_i)^2 + (z_j - z_i)^2}$

Postprocessing

SLIC 和其他算法一样并不严格地强制保证连通性 (connectivity). 聚类完成时候, 会有一些与其聚类中心不属于同一个连通单元 (connected component) 的孤立像素存在. 为了对此做出校正, 这些像素会根据某种连通单元算法 (connected components algorithm) 来分配到另外一个最近的聚类中心上.

(To be continued…)