Efficient Segmentation Using Feature-Based Graph Partitioning Active Contours

Abstract

Graph partitioning active contours (GPAC) is a recently introduced approach that elegantly embeds the graph-based image segmentation problem within a continuous optimization framework. GPAC can be used within parametric snake-based or implicit level set-based active contour continuous paradigms for image partitioning. However, GPAC similar to many other graph-based approaches has quadratic memory requirements which severely limits the scalability of the algorithm to practical problem domains. An N xN image requires O(N(4)) computation and memory to create and store the full graph of pixel inter-relationships even before the start of the contour optimization process. For example, an 1024x1024 grayscale image needs over one terabyte of memory. Approximations using tile/block-based or superpixel-based multiscale grouping of the pixels reduces this complexity by trading off accuracy. This paper describes a new algorithm that implements the exact GPAC algorithm using a constant memory requirement of a few kilobytes, independent of image size.