一个基于超像素的图像分割算法

刘乘风+徐刚

摘要：图像分割技术是计算机视觉领域的基础工作，目前的图像分割技术大多以像素为单位进行。随着图像分辨率的提升，图像分割的成本越来越高，于是寻找降低图像分割成本的需求越来越迫切。基于超像素的图像分割算法就是这样一种方法。超像素其实就是将具有相似纹理、颜色、亮度等特征的相邻像素进行合并后的图像块。采用超像素的图像分割算法后，可以消除像素间的冗余，大大降低后续图像处理任务的成本，加快图像识别的速度。

关键词：计算机视觉； 图像分割； 超像素； K-means聚类； 归一化分割

中图分类号：TP317 文献标识码：A 文章编号：1009-3044（2017）25-0165-02

Abstract：Image segmenting is the basic technology in computer vision， and most image segmenting technology is Based on pixels in nowadays. With the promoting of image resolution， the cost of image segmenting is higher and higher， so the requirement of lower image segmenting method is more and more urgent. Image segmenting Based on superpixel is such method. In fact superpixel is an image block consisting of neighbor pixels， which has the similar texture，color，and brightness. By taking superpixel method， it will eliminate redundancy of pixels，and decrease the cost of following image processing， and accelerate image recognizing.

Key words：computer vision； image segmenting； superpixel； K-means clustering； normalized cut

1 概述

图像特征反映了图像的基本特性，一般可分为全局特征、局部特征和空间关系特征。

全局特征主要有颜色特征和纹理特征。颜色特征和纹理特征描述了图像所对应的对象的表面性质。

局部特征主要是轮廓特征和区域特征。轮廓特征主要描述了物体的外边界，区域特征則描述整个形状区域。

空间关系特征是指图像中分割出来的多个目标之间的相互的空间位置或相对方向关系。空间关系又分为两类：相对空间位置信息和绝对空间位置信息。相对空间位置关系强调的是目标之间的相对情况，如上下左右等，绝对空间位置信息关系强调的是目标之间的距离大小以及方位，如邻接、重叠、和包容等。

图像分割技术是一种根据图像特征进行图像划分的技术。图像分割技术要求将图像分割成互不重叠的区域，并且每个区域具有各自特征，区域间的特征值差别明显。图像分割应满足以下条件：1）分割后所得到的各个区域的总和应能够覆盖整个图像，即各个区域的并集等于图像全集；2）各区域之间不能有重叠，即各个区域的交集是空集；3）同一区域的像素特征值相似或相近，例如具有相近的颜色、纹理值；4）同一个对象可以分割在一个区域内，也可以分割到多个区域中[1]。

图像分割技术发展到今天，已经有出现了许多方法，归纳起来主要有三类：1）边缘检测方法；2）区域提取方法；3）阈值分割方法[2]。

2 基于超像素的图像分割算法

目前对图像的分割处理大都以像素为单位进行。核心思想就是利用二维矩阵来表示一张图像，直接在二维矩阵的基础上进行分割处理。这种做法并未考虑像素之间的空间组织关系，这使得效率过低，于是Ren[3]提出了超像素（Superpixel）这一概念。超像素其实就是将具有相似纹理、颜色、亮度等特征的相邻像素进行合并后的图像块。利用超像素进行图像分割，可以消除冗余，降低后续图像处理任务的成本。超像素分割算法是一种基于区域提取的图像分割方法。

2.1 K-means聚类算法及其应用

在使用超像素技术时，将用到其核心算法K-means算法[4]。

K-means聚类算法的主要步骤如下：首先随机给定K个聚类中心，按照最邻近原则把待分类样本点分到各个簇中；然后按平均法重新计算各个簇的质心，从而确定新的聚类中心；一直迭代下去，直到聚类中心移动的距离小于某个给定的值， 或聚类次数达到要求为止。

由K-means算法得到的K个点集能保证聚类的性能最佳。我们把这种方法用于聚类图像中的像素点，这是超像素算法中重要的一步。

2.2 超像素特征提取技术研究

超像素技术基于一个测度谓词——超像素，其利用图像的基于图论的表示法来判定两区域的边界。我们将原始图像预分割为多个区域一致性和边缘描述性较好的区域，这些区域在本文中被称为超像素[5，6]。

基于超像素技术，本文使用一种叫做Ncut（Normalized cut）的技术进行图像分割[7，8]。Ncut技术又称归一化分割，它遵循归一化准则‘Ncut，使得分割出的超像素类间距离尽可能大，并且类内距离尽可能小。

第二步：求解特征系统[（D-W）y=λDy]方程。当我们把y的取值范围放宽到实数时，则求最小化Ncut，就相当于是求解特征系统[（D-W）y=λDy]方程。在Ncut方法中，我们采用的是其特征方程的第二个最小特征值所对应的特征向量作为该问题的解。endprint

第三步：利用K-means算法对上一步骤中的特征向量y进行聚类。得到超像素集SP。

第四步：对SP集合中的区域块边界进行画线，保留画线。

3 实现方案

本文用Noramlized Cut和K-means方法提取超像素集合，并對超像素的边界进行分割。我们在Intel酷睿i5，主频3.4GHz、内存4GB的计算机上，利用在Matlab2014a实现了图像分割。我们分别对风景、人物图片做了分割实验，取得了不错的效果。图1为使用超像素算法处理图片的一个实验结果。

图1（a）为原图I，图1（b）为N_SP=20时超像素块的边界I_SP，图1（c）为N_SP2=200时的边界I_SP2 。基于对运行效率以及特征信息的高敏感性的考虑，我们采用N_SP=20作为实验参数。

参考文献：

[1] 章毓晋. 图像分割[M]. 北京： 科学出版社， 2001.

[2] 周强.图像分割算法研究[J].世界科技研究与发展， 2012，32（3）：157- 158.

[3] X. Ren ， J. Malik. Learning a classification model for segmentation[C]. In Proc. 9th Int. Conf. Computer Vision， 2003 （1）：10-17.

[4] 刘雄. 基于K-means的改进聚类融合算法的研究与应用[D].中南大学. 2011.

[5] O. Veksler， Y. Boykov， P. Mehrani. Superpixels and Supervoxels in an Energy Optimization Framework[C]. In European Conference on Computer Vision， 2010：211-224.

[6] 赵渊，彭济根，高义. 基于SLIC超像素分割的图分割算法[J].工程数学学报， 2016，33（5）：441-449.

[7] 姜长龙. 基于Graph Cuts图像分割的Mean Shift目标跟踪算法研究[D].西安电子科技大学，2010.

[8] 席秋波. 基于Ncut的图像分割算法研究[D].电子科技大学，2010.endprint