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

摘要

针对基于图论的超像素分割方法缺乏超像素紧凑性控制和运算复杂度过高的问题，提出了一种基于局部懒惰随机游走（LLRW）的超像素分割方法，并将超像素分割形式化为像素邻接图的局部划分问题，提出了一种直观的分割质量度量。该方法首先将均匀平铺的六边形重心作为超像素种子点初始位置；然后利用局部随机游走算法计算种子点与周围像素的相关程度，将其最相关种子点的标号赋予该像素；最后计算新的超像素重心，并将其作为下一轮迭代的种子点位置，通过若干次迭代逐步优化超像素分割结果。此算法具有线性的时间复杂度和线性的空间复杂度，同时超像素分割质量具有理论保证。通过标准数据集上的实验证明，该方法不仅能够较好地保持图像边界，还可以保证超像素的紧凑性，从而达到理想的超像素分割效果。%A novel approach to generate superpixels based on local lazy random walk (LLRW) was proposed to improve the compactness of superpixels and reduce the computational complexity. The superpixel segmentation was formulated as a problem of local partition of pixel adjacency graphs, and an intuitive quality measure for superpixel segmentation was given. The LLRW approach firstly initializes the centroids of uniformly titled hexagons as the positions 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 complexity, 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.