Semi-Automatic Foreground Extraction For Natural Images
TR-2005-64, Authors: Andreas Rishede Hyllested and Martin Wallengren Nilsson
Semi-Automatic Foreground Extraction For Natural Images
Andreas Rishede Hyllested
Martin Wallengren Nilsson
March 2005
Abstract
The work described in this thesis was carried out at the IT University of Copenhagen, Denmark from September 2004 to March 2005. The focus of the work has been defined together with the collaboration partner Laerdal-Sophus A/S who seeks to replace a current manual segmentation method with a semi-automatic segmentation method.
The thesis produces a method for and describes the framework of interactive segmentation of foreground objects in natural images. The basis technology is segmentation by graph cut. To increase interactivity speed the graph construction is preceded by a toboggan watershed segmentation of the input image. The watershed segmentation is implemented in a multi-scale framework where different normalisation methods are tested. Based on the watershed segmented image is built a graph, in which every watershed segment corresponds to one node. The minimum-cut is efficiently computed using the new augmenting path based Boykov-Kolmogorov algorithm. To increase performance of the algorithm an initial pre-augmentation of all terminal links is proposed.
For fine tuning of the segmentation we propose a new method that uses a local graph representation to perform a pixel-based minimum-cut in specified areas. The method has automatic input of seed points. For difficult parts of the object boundary the locally found minimum-cut improves the result by overriding the global segmentation.
Two new methods to enter seed points for the min-cut/max-flow algorithm are demonstrated. The first method is based on finding shortest paths through elongated image structures and converting the found paths into dense rows of seed points. The other method automatically enters background seed points by subtraction of a background image.
The advanced Bayesian framework for alpha matting proposed by Chuang et al. is tested. It shows to have the potential for producing good alpha mattes even for difficult segments, but it occurs to be too slow to match Laerdal-Sophus A/S’s need for interactivity. Instead, by applying Gaussian low-pass filtering to the alpha channel we obtain decent alpha transitions for simple borders in a few seconds. This simple approach can be allowed, at least, in the specific case Laerdal-Sophus A/S, because their image segments usually have simple borders.
All implementation is done in C++ to integrate with Picture Factory, which is an image editing application currently used by Laerdal-Sophus A/S.
Technical report TR-2005-64 in IT University Technical Report Series, March 2005.
Available as PDF.