基于局部随机游走的超像素分割方法  

Superpixel segmentation based on local random walk

作　　者：马志国[1] 苗军[1] 卿来云[2] 陈熙霖[1] 

机构地区：[1]中国科学院智能信息处理重点实验室中国科学院计算所,北京100190 [2]中国科学院大学计算机与控制学院,北京100049

出　　处：《高技术通讯》2014年第10期991-998,共8页Chinese High Technology Letters

基　　金：973计划(2009CB320900);国家自然科学基金(61175115;61272320;61070116)资助项目

摘　　要：针对基于图论的超像素分割方法缺乏超像素紧凑性控制和运算复杂度过高的问题,提出了一种基于局部懒惰随机游走(LLRW)的超像素分割方法,并将超像素分割形式化为像素邻接图的局部划分问题,提出了一种直观的分割质量度量。该方法首先将均匀平铺的六边形重心作为超像素种子点初始位置;然后利用局部随机游走算法计算种子点与周围像素的相关程度,将其最相关种子点的标号赋予该像素;最后计算新的超像素重心,并将其作为下一轮迭代的种子点位置,通过若干次迭代逐步优化超像素分割结果。此算法具有线性的时间复杂度和线性的空间复杂度,同时超像素分割质量具有理论保证。通过标准数据集上的实验证明,该方法不仅能够较好地保持图像边界,还可以保证超像素的紧凑性,从而达到理想的超像素分割效果。A novel approach to generate superpixeis based on local lazy random walk （LLRW） was proposed to improve the compactness of superpixels and reduce the computational complexity. The superpixel segmentation was formula- ted as a problem of local partition of pixel adjacency graphs, and an intuitive quality measure for superpixel seg- mentation was given. The LLRW approach firstly initializes the centroids of uniformly titled hexagons as the posi- tions of superpixel seeds, and then uses the local lazy random walk （LLRW） algorithm to calculate the correlation between nearby pixels and superpixel seeds, and sets the label of each pixel as the label of its most correlated seed. Finally, it calculates the new centroids of superpixels as the next iteration＇ s seed positions, and iterates these steps to refine the superpixel segmentation result. This algorithm has the linear time complexity and the space complexi- ty, as well as a theoretical guarantee on the quality of superpixels. The experimental results show that the new method can preserve smooth boundaries and generate compact superpixels, so it is an ideal algorithm for real-world applications.

关 键 词：超像素分割 归一化割 局部图划分 传导率 局部懒惰随机游走(LLRW) 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]