BGU - Computational Vision Course - Student Project Page
Live-Wire Segmentation with"shortest path"
By Ilan Smoly
Feb, 2011
1. Introduction
What is segmentation? Segmentation is merely labeling pixels in an image, such that each pixel p is labeled F(p).Segmentation’s goal is to group image pixels into logical groups or segments which may represent objects in the scene. Segmentation is typically posed as a binary labeling problem where foreground and background constitutes the set of labels assigned to pixels. To get accurate segmentations, occasionally, user input is provided into the labeling problem by allowing the user to pre-label some pixels as foreground and some as background.
Fully and partly automatic general image segmentation is one of the biggest riddle of the 2-dimensional computational vision these days due to the wide variety of image sources, contents and complexities. It is considered to be the main output of the biological visual system to cognition (in addition to 3D conception, etc.). We like to receive data to our cognitive mind as whole objects, instead of merely colorful dots (pixels) in space, but how this data is being analyzed in the visual cortex is still a mystery.
Several methods (such as ‘relaxation labeling’ and 'normalized cut',etc.) has been introduced to us during the course, in addition to the variety of semi-automated approaches that in use today.In my project, I will present a powerful tool that uses the 'optimal path' (also known as 'shortest path') algorithm to solve the segmentation problem in 2D imageswith a low order polynomial running time, known as 'Live-wire'. I will explain shortly about the tool and display the results I got while testing Livewire personally.
Livewire is a computational segmentation technique that is used in many image editors (as plug-in) and medical applications. It is based on a modification of Dikstra's algorithm, which in a modular form finds the shortest path between 2 pixels that were received as input from the user. In such a way, a user can easily crop an image into pieces, with minimum manual intervene and a lot of computer's assistance, which leads to significant high-quality results, as shown in the figure to the right:
2. Livewire Algorithm
Livewire algorithmprovides the user with full control oversegmentation whilethe computer does most of the detail work. Therefore, theuser’s knowledge complements the ability of the computer to segment an image properly.In Livewire, the user clicks to indicate a starting point, and then asthe mouse is moved it trails a “live wire” behind it. When the user clicks again, thislivewire freezes, and a new live wire starts from the clicked point.
In Livewire, the user draws a “sticky contour” that shape boundaries in theimage. The “stickiness” of each pixel in the image is determined by measuring its localimage characteristics. The stickiest pixels are those near a boundary between structures inthe image. These pixels attract the livewire. Consequently, when the user selects pointsof interest for segmentation, the contour is drawn along the “stickiest” pixel path betweenthem.
There are 2 mainsteps of Live-wire (which will be discussed next):
1)Thecreation of a weighted graph using image information.
2)Calculation and displayof the shortest paths in the graph.
2.1 Creation of the Weighted Graph
The first step of Livewire employs image filtering to extract features of interest in the image, which are then passed through a cost function to produce graph weights.
A directed weighted graph G = (V,E), consists of a set of nodes V and a set of directed edges E that connect them. The nodes correspond to pixels, voxels, or other features. Edgesconnect pairs of neighboring pixels (where a neighborhood could be defined variously). The cost of an edge corresponds to a penalty for discontinuity between the pixels.
How the weights should be calculated? The weight, orcost, is the penalty for traveling from one node to another along the edge. The shortest pathbetween any two nodes is defined as that path which has the lowest total cost (a sum of costs along all edges in the path). Hence, the edges weights are derived from some combination of image features, such as gradients, Laplacian zero-crossings and intensity values. Generally, the features are computed in a neighborhood around each graph edge, giving low edge costs to more desirable feature values.
These features contribute to three main areas that are used to evaluate the weight:
1)Edge Detection. Edge detection is fundamental in the livewire segmentation process. The gradient and the Laplacian zero-crossingare primarily useful in edge detection. These features are the main attractors for the livewire.
2)Directionality.In the presence of noise or near other attractive structures, small incorrect steps may happened, even though the overall summing of costs along the path leads to higher path cost in the end.Various features can influence which direction the path should take locally. Directional gradients computed with oriented kernels, based on the angle between each potential edge direction and the local gradients, provide local direction information. If the direction of segmentation is known, Livewire distinguishes between inside and outside pixels. Consequently, instead of being attracted by all areas with gradient of X, the livewire can pay attention only to those regions with such a gradient where the inside is, for example, brighter than the outside.
3)Training. The process by which the user indicates (in a pre-set popup box) a preference for a certain type of boundary, and the features are transformed accordingly to give low graph edge costs to the regions preferred by the user.
2.1.1 Methods
Aligning the graph with the image data can be done in 2 ways according to literature:
1)Pixels cracks.A node is a corner of a pixel.The edges are aligned with the“cracks” between pixels. In this approach, the boundary may appear as a whole pixel.
2)Path along pixels.Each pixel is aligned to a node in the graph. The edges are connectors between pixels. Here, the boundary cuts edges, so pixels that should belong to both regions may be chosen as part of the “boundary line”.
Two methods of aligning the weighted graph and the image. The dashed
Squares represent pixels in the image. The circles are graph nodes, and all edges leavingthe blue center nodes have been drawn. On the left, the graph is aligned with the imagesuch that the pixel corners are the graph nodes, and the edges separate pixels. On the right,the graph is aligned so that nodes are in the center of each pixel, and edges connect pixels.
Pixel cracks -"Oriented Boundary".The neighborhood on this approach(nodes are pixel corners) is used to computefeatures relevant to the dark graph edge in the center of the two colored pixels. Note thatthis neighborhood is rotated for all possible orientations anddirections of the graph edge,and the features are computed with each orientation.
1)?Intensity on the “positive” and "negative" sides of the edge, where positive and negative are defined relative to thelocal gradient direction.
2)Various gradient magnitude:
3)Orientation-sensitive gradient magnitude, which multiplies the gradient magnitude defined above by (-1))if the local gradient orientation does not match the neighborhood orientation.
4)Distance from boundary traced on the last item (3).
One local neighborhood for computing livewire features. Each squarerepresents a pixel, and in this system the graph edges are the “cracks” between pixels. Sothe dark line separating the blue and green pixels is an edge in the weighted graph.
The advantage of the preceding definitions is that they are selective for boundary orientation.This means that the algorithm can tell the difference between a boundary with40darker pixels inside than outside, and the reverse: a similar boundary with light pixels insideand dark outside. This, however, assumes that the user is consistently tracing eitherclockwise or counterclockwise.
Paths along Pixels - “Intelligent Scissors".
1)Laplacian Zero-Crossing.Convolution with a Laplacian kernel, and zero-crossing the pixel closest to 0.
2)Gradient Magnitude -
3)Gradient Direction: a constraint that says that the link between two pixels should run according to the gradient directions at both pixels. This is evaluated by using the 2 direction vectors of the local gradient and the graph edge direction.
The advantage of this formulation is that it includes an explicit directional smoothnessconstraint. But it does not differentiate between boundary orientations.
2.2 Finding Shortest Paths
The second step uses Dijkstra’s algorithm, a well-known shortest-path algorithm, to find shortest paths in the graph. So each “sticky contour” drawn on the image is actually a shortest path, where the distance metric that defines “shortest” is based on image information.
Dijkstra’s Algorithm
In the standard Dijkstra’s algorithm, shortest paths to all nodes from an initialnode are found. The algorithm works by finding paths in order of increasing path length,until all shortest paths have been found. In the context of image segmentation, shortest pathsare found from the original point to all points in the image. This does not make much sense,as the user is highly unlikely to segmentfrom the center of the image to a corner in one step.
So using Dijkstra’salgorithm as is would be computationally wasteful.
Livewire on the Fly
"Livewire on the Fly" algorithm computes the shortestpaths for only as much of the image as necessary. It uses a modified version of Dijkstra’salgorithm that stores nodes currently under investigation in a sorted circular queue,and is able to stop executing when it reaches the user-defined endpoint. Computedshortest path information is retained and re-used when the user moves the mouse again tochoose another endpoint. This is possible because of the classic characteristic of Dijkstra’salgorithm, that each shortest path is comprised of prior shortest paths
3. Results
I tested the Livewire plug-in for ImageJ 1.42q using 'intelligent scissors' method.
The ‘Magnitude’,’ Directionality’ and ‘power’ define the relative weight when combining the edges weights by adding the features ‘gradient magnitude’, ‘gradient direction’ and ‘laplacian zero-crossing’, respectively.
3.1 One parameter only
Directionality = 80
Power = 0
Magnitude = 0
Directionality = 0
Power = 0
Magnitude = 80
Directionality = 0
Power = 80
Magnitude = 0
Clearly, we can see that lacking the intensity property (that leaves us with direction) for the edges weight results in an inexact contour in areas where intensities contrast are dominant (as shown in 1).
However, losing the directionality results inmiss-segmentation where the intensities contrast are relatively small (as shown in 2, 3in the central fingers area).
3.2 One parameter elimination
Directionality = 80
Power = 80
Magnitude = 0
Directionality = 0
Power = 80
Magnitude = 80
Directionality = 80
Power = 0
Magnitude = 80
As in the previous results, the absence of directionality element to edges weight affects the central area where intensities of the "object" and "background" are similar.
The lack of magnitude and power leads to incoherent contour (on the right hand in the image), where edges direction fits, but pixels intensities differential can lead to many directions.
The magnitude, clearly, helps to decrease extensive wide edges and to tighten up the "object" limits. (As shown in the right hand where the background is brown.)
3.3 Three parameters combinations
Directionality = 80
Power = 80
Magnitude = 80
Directionality = 13
Power = 30
Magnitude = 43
Directionality = 50
Power = 10
Magnitude = 50
Directionality = 50
Power = 50
Magnitude = 10
Directionality = 10
Power = 50
Magnitude = 50
4. Discussion
On general, the Livewire tool provides the user the ability to segment the image efficiently with minimal error. Moreover, if errors occurred, the pre-set properties can be changed to fit the image properties. In addition to this, the user can always choose to label pixels with smaller distance between them. All of the above and the fact that all calculations are performed in a blink of an eye, make the Livewire a powerful and efficient tool for image editing and analyzing.
However, trying to apply Livewire algorithm to long distance pathways, I found that the algorithm had many errors contouring parts of the image where intensities do not change significantly or where directionality can continue in several ways. I found that using the mentioned pre-set options did not help much and no other solution but reducing the pathways distance, led to sufficiently acceptable results.
In conclusion, this imply that as an image editor, Livewire increases user's capabilities to crop images to "objects", but yet, one cannot employ the algorithm to complex images with long-distance object boundaries.
Improvements
Changing the neighborhooddefinition when determining edges weight,by using random long distance relations between pixels located far from one another. This will help evaluating contour and orientation, without changing running time. This solution brings biological elements, as we showed in class that neurons send long axons randomly to other neurons located far away. However, a profound modulation of Dikstra’s algorithms must be considered for this.
5. Bibliography
- Graph Cut Matching In Computer Vision,Toby Collins
- Interactive Segmentation with Intelligent Scissors, Eric N. Mortensen,William A. Barrett, Brigham Young University
- Efficient Graph-Based Image Segmentation,F.Felzenszwalb,Massachusetts Institute of Technology,Daniel P. Huttenlocher, Cornell University
- Semi-Automatic Medical Image Segmentation, Lauren O’Donnell, Massachusetts Institute of Technology