Keep the geometries: Image segmentation by K-MSVC with random region grouping and propagation

We propose new techniques to address low-level image segmentation problem under clustering theory. The goal of this paper is to provide a compromised solution between methods that produce two different kinds of segmentation results: one generates coherent regions but views disjoint regions as totally different objects, and the others do not consider the spatial relationship at all. For our approach, spatial geometries are partially preserved and disjoint regions are also allowed to be grouped into a single cluster. The approach is built on the feature space clustering algorithm called K-MSVC, but constrained by the graph to maintain the capability of partially preserving the spatial coherence. A new type of graph called Random Grouping Graph (RGG) is introduced then, to overcome the high computational cost on the grid-graph based image representation. It´s fast to construct, greatly reduce the graph size and can speedup other graph-based segmentation algorithms. Though with less vertices, the segmentation on RGG works better than on downsampled version of the image. Nontrivial experimental results on the Berkeley Segmentation Dataset demonstrate that our method outperforms the existing algorithms and yields more satisfactory results.