VCells: Simple and Efficient Superpixels Using Edge-Weighted Centroidal Voronoi Tessellations
Abstract
CentroidalVoronoitessellations(CVTs)arespecialVoronoitessellationsforwhichthegeneratorsofthetessellationarealsothecentersofmass(ormeans)oftheVoronoicells or clusters. Recently, we generalize the CVTs to the Edge-Weighted Centroidal Voronoi Tessellations (EWCVTs) by limiting the length of cluster boundaries. We apply this newly developed EWCVT for generating superpixels, which are in fact an oversegmentation of the image. EWCVT can segment the image and the clusters nicely preserve image local color difference. Moreover, the undersegmentation errors can be effectively limited in a controllable manner. It is well known that k-means algorithm can be used to generate Centroidal Vononoi tessellation. The simplicity and efficiency of k-means are well inherited by our EWCVT model. Meanwhile our new model is capable to generate high-quality superpixels on very complicated images. Even for megapixel sized images, EWCVT is able to generate the superpixels in a matter of seconds. We will provide the segmentation results on a wide range of complicated images. The simplicity and efficiency of our models will be demonstrated by complexity analysis, time and accuracy evaluations.