Publications on interactive curve extraction from images (live-wires, intelligent scissors, snakes) used in Computer Graphics :

• Image Snapping, M. Gleicher, SIGGRAPH'95.
• AutoKey: Human Assisted Key Extraction, T. Mitsunaga et al., SIGGRAPH'95.
• Intelligent Scissors for Image Composition, E.N.Mortensen & W.A.Barrett, SIGGRAPH'95.
• Interactive Segmentation with Intelligent Scissors, E.N.Mortensen & W.A.Barrett, GMIP 1998.
• User-Steered Image Segmentation Paradigms: Live Wire and Live Lane, A.X. Falcão et al., GMIP 1998.

BibTeX references.

Summary :

Gradient descent on blurred feature maps (e.g. edges) extracted from an image.

Summary :

Processes color images.
 

Summary :

• Use simple gesture motions with a mouse to extract objects from images quickly and accurately.
• Discrete Dynamic Programming (DP) as a 2D graph-searching problem for live-wire boundary detection.
• On-the-fly (interactive) dynamic training to increase robustness.
• Boundary cooling automatically freezes unchanging segments and automates the input of additional seed points.
• Spatial frequency equivalencing matches the lowest frequency spectra to all other image components.

Cost function :

Function of 3 measures :

• F1 : Laplacian zero-crossings for localisation.
• F2 : Gradient magnitude for local cost proportional to edge strength.
• F3 : Gradient direction fo a smoothness constraint.

Relative weighting of each function: 43% F1 + 43% F2 + 14% F3.

Dynamic Programming - Graph search :

• A wavefront of active point emanating from the seed propagates faster where local costs are lower.
• The 2D DP's search window is the entire image.
• Live-wire boundaries are piecewise optimal (between seed points).

Interactive dynamic training :

• Based on learned edge characteristics from the most recent portion of an object's boundary.
• Turned on and off interactively for portions of a wire.

Interactive optimal 2D path selection :

1. The live-wire is interactivel initialized with just a single seed point.
2. Generates, at interactive speeds, all possible optimal paths from the seed point to every other point in the image.

We present a new, interactive tool called Intelligent Scissors which we use for image segmentation. Fully automated segmentation is an unsolved problem, while manual tracing is inaccurate and laboriously unacceptable. However, Intelligent Scissors allow objects within digital images to be extracted quickly and accurately using simple gesture motions with a mouse. When the gestured mouse position comes in proximity to an object edge, a live-wire boundary "snaps" to, and wraps around the object of interest. Live-wire boundary detection formulates boundary detection as an optimal path search in a weighted graph. Optimal graph searching provides mathematically piece-wise optimal boundaries while greatly reducing sensitivity to local noise or other intervening structures. Robustness is further enhanced with on-the-fly training which causes the boundary to adhere to the specific type of edge currently being followed, rather than simply the strongest edge in the neighborhood. Boundary cooling automatically freezes unchanging segments and automates input of additional seed points. Cooling also allows the user to be much more free with the gesture path, thereby increasing the efficiency and finesse with which boundaries can be extracted.

In multidimensional image analysis, there are, and will continue to be, situations wherein automatic image segmentation methods fail, calling for considerable user assistance in the process. The main goals of segmentation research for such situations ought to be (i) to provide effective control to the user on the segmentation process while it is being executed, and (ii) to minimize the total user's time required in the process. With these goals in mind, we present in this paper 2 paradigms, referred to as live wire and live lane, for practical image segmentation in large applications. For both approaches, we think of the pixel vertices and oriented edges as forming a graph, assign a set of features to each oriented edge to characterize its ``boundariness,'' and transform feature values to costs. We provide training facilities and automatic optimal feature and transform selection methods so that these assignments can be made with consistent effectiveness in any application. In live wire, the user first selects an initial point on the boundary. For any subsequent point indicated by the cursor, an optimal path from the initial point to the current point is found and displayed in real time. The user thus has a live wire on hand which is moved by moving the cursor. If the cursor goes close to the boundary, the live wire snaps onto the boundary. At this point, if the live wire describes the boundary appropriately, the user deposits the cursor which now becomes the new starting point and the process continues. A few points (live-wire segments) are usually adequate to segment the whole 2D boundary. In live lane, the user selects only the initial point. Subsequent points are selected automatically as the cursor is moved within a lane surrounding the boundary whose width changes as a function of the speed and acceleration of cursor motion. Live-wire segments are generated and displayed in real time between successive points. The users get the feeling that the curve snaps onto the boundary as and while they roughly mark in the vicinity of the boundary.

We describe formal evaluation studies to compare the utility of the new methods with that of manual tracing based on speed and repeatability of tracing and on data taken from a large ongoing application. The studies indicate that the new methods are statistically significantly more repeatable and 1.5-2.5 times faster than manual tracing.

Page created & maintained by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu