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

Author/Creator

Author/Creator ORCID

Date

2020-01-20

Department

Computer Science and Electrical Engineering

Program

Computer Science

Citation of Original Publication

Rights

Distribution Rights granted to UMBC by the author.
This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu

Subjects

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.