EFFICIENT GRAPH-BASED IMAGE SEGMENTATION WITH THE NON-LATTICE TOPOLOGIES.

Abstract

We present a novel algorithm to segment an image into regions of similar appearance that resolves several of limitations of the popular Efficient Graph Based Image Segmentation (EGBIS) algorithm.? EGBIS is a graph-based image segmentation algorithm that obtains an optimal segmentation under the assumption of a boundary predicate in O(V+E) time.? We address and resolve the following three limitations of EGBIS (a) the assumption of a lattice topology which is less expressive than non-lattice topologies such as clique (b) the need for a tunable hyper-parameter k which in practice requires running EGBIS many times in order to suitably determine (c) the restriction of the boundary predicate to only consider minimum weight edge between components.? The proposed algorithm obtains an EGBIS-like segmentation for all k-values in O(V^2 log V) runtime which compares favorably to the O(V^2) time necessary to run traditional EGBIS only once on a clique topology.? The resulting segmentations although not strictly identical are very similar in appearance to traditional EGBIS on both lattice and non-lattice topologies.? Furthermore, the ability to evaluate variants of the boundary predicate including is an additional advantage of the proposed algorithm.