Course Home
Administration
Syllabus
References
Lecture Notes
Readings
Assignments
Projects
Resources


Comments? Idea?























































































































































































































































































































































Live-Wire Segmentation with "shortest path"

Final project by

Ilan Smoly

smolyi@bgu.ac.il


Introduction

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 images with a low order polynomial running time, known as 'Live-wire'. I will explain shortly about the tool and display the results I got while experimenting Livewire personally.
Livewire is a computational tool that is used in many image editors (as plug-in) and medical applications. It is based on the powerful 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.

Approach and Method

Livewire algorithm provides the user with full control over segmentation while having the computer do much of the detail work. Therefore, the user’s knowledge complements the ability of the computer to segment an image properly. Initially when using Livewire, the user clicks to indicate a starting point, and then as the mouse is moved it trails a “live wire” behind it. When the user clicks again, this live wire freezes, and a new live wire starts from the clicked point.
In Livewire, the user draws with a “sticky contour” that snaps to boundaries in the image. The “stickiness” of each pixel in the image is determined by measuring its local image characteristics. The stickiest pixels are those near a boundary between structures in the image. These pixels attract the livewire. Consequently, when the user selects points of interest for segmentation, the contour is drawn along the “stickiest” pixel path between them.

Results

On general, the Livewire tool provides the user the ability the 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 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.

Conclusions

Changing the neighborhood definition 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.

Additional Information

References

  • 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