简单线性复杂度的超像素分割算法

超像素算法大体上可以归为两类，要么是基于图的方法，要么是基于梯度上升的方法。基于图的方法将每个像素看作图中的一个节点，节点之间边的权重代表邻近像素的相似性比例。超像素通过最小化一个基于图的代价函数来产生。基于梯度上升方法从一个粗略的初始像素聚类开始，反复使用梯度上升方法改善聚类结果，直到满足某些收敛准则形成超像素。这两类方法的复杂度较高，最好情况为O（N log N），SLIC超像素方法是一种比以上方法更加快速的超像素方法，其复杂度为O（N）。

SLIC超像素方法是在一个五维空间中进行邻近像素聚类，这五维空间分别被定义为每个像素在CIELAB颜色空间中的L、a、b值和像素的x、y坐标，可表示为pi=［Li ai bi xi yi］T。该方法仅仅需要一个唯一的参数K来指定期望的超像素个数。对于CIELAB颜色空间中一幅具有N个像素的图像，它被分为等大小的N/K个超像素。因而，对于初始超像素而言，在每一个等量的网格间隔内有一个像素中心，该等间隔为：

在初始化过程中，SLIC算法以网格间距S选择K个超像素聚类中心Ci（公式7.12），为了避免超像素中正好处于图像边界位置或者噪声点，超像素中心在一个3×3邻接范围内不断移动到梯度最小位置。(www.xing528.com)

接下来，每个像素i被分配到最邻近超像素中心。不同于传统的k均值聚类算法需要与所有的聚类中心相比较，SLIC算法通过计算距离测量函数D（将在7.2.3节描述）来确定最邻近聚类中心。因此，超像素期望的空间扩展区域是一个接近S×S的区域，其相似像素的搜索范围可以限定在围绕超像素中心的2S×2S的范围内。这是SLIC算法能够获得接近于线性复杂度的关键。

一旦每个像素都被分配到了邻近像素中心，一个更新步骤将超像素中心矫正到该簇所有像素的平均［L a b x y］T向量所代表的像素点。在这个过程中，一个L2范式被用来计算新聚类中心和先前聚类中心的残差E。然后分配和更新步骤不断迭代直到残差收敛，SLIC算法通过实验发现对于大部分图像只要10次迭代已经非常充分，因而文献［9］中所有的方法都只迭代10次，并获得了很好的效果。最后一个后加工步骤用来强制将不相交的孤立像素连接到邻近超像素，本书省略该过程，孤立像素点将会通过后续区域合并完成。