超像素分割算法研究综述
1.引言
图像分割是指按照一定的相似性准则将图像划分成具有特殊语义的不同区域，其研究最早可以追溯至20 世纪60 年代，已历经几十年的发展。图像分割作为计算机视觉领域的基本问题，是图像理解的重要组成部分。与此同时，它在图像处理、模式识别和人工智能等多个领域也扮演了关键的角色。
目前对图像的处理大多以像素为单位，用二维矩阵来表示一张图像，并未考虑像素之间的空间组织关系，这使得算法处理效率过低。2003 年，Ren等人［1］最早提出了超像素这一概念，所谓超像素，是指具有相似纹理、颜色、亮度等特征的相邻像素构成的图像块。它利用像素之间特征的相似程度将像素分组，可以获取图像的冗余信息，在很大程度上降低了后续图像处理任务的复杂度。
超像素生成算法大致可分为基于图论的方法和基于梯度下降的方法两类。具有代表性的基于图论的超像素分割方法有Shi 等人［6］提出的Normalized cuts 算法( 简称NC)、Moore等人［7］提出的Superpixel lattices算法(简称SL), Veksler等人［8］提出的Compact superpixels和Constant-intensity superpixels 两种超像素分割算法(简称GCa和GCb)等。
对于基于梯度下降法，已有的研究有Comaniciu 等人［18］提出了基于核密度梯度估计的迭代式搜索算法Mean Shift，Levinshtein等人［19］提出的Turbopixel算法，Achanta等人［9］提出了基于颜色相似度和空间距离关系的局部迭代聚类算法SLIC( simplelinear iterative clustering),Ren等人［21］提出的基于CUDA(compute unifieddevice architecture) 框架的GPU并行加速SLIC等。
由于超像素能够提取中层图像特征，它通常作为分割算法的预处理步骤，已经成为视觉领域的一项关键技术。此外，许多的研究工作表明，超像素技术已成功应用于多种视觉任务，如骨架提取［13］、图像分割［14 - 16］、人体姿势估计［17， 18］、目标识别［19， 20］、目标跟踪［21 - 24］等，因此它在计算机视觉应用中也越来越受到研究者的重视，具有很大的发展潜能和应用价值。本文对超像素分割算法，特别是近几年来出现的新思路、新方法给出了介绍和分析，并在文章的最后对超像素的应用进行了展望。
2.1 基于图论的超像素分割方法
基于图论的图像分割是一种自上而下的全局分割方法，其主要思想是把整幅图像看做一幅带权无向图，图像中每一个像素对应图中的一个节点，像素之间的相邻关系对应图的边，像素特征之间的差异或相似性对应边上的权重。然后在所建立的图上利用各种分割准则来对图中的节点进行划分，进而完成对图像的分割。
Shi 等人［6］提出的Normalized cuts算法(简称NC)利用轮廓特征和纹理特征递归地进行图分割。该算法的特点是产生的超像素较为规则，但其边缘贴合度(boundary adherence) 较差，计算速度较慢，尤其不适用于大尺寸图像分割［3］。边缘贴合度［3］指超像素边缘与真值(ground truth) 边缘的吻合程度。
