Livewire Segmentation Technique


Livewire, is a segmentation technique which allows a user to select regions of interest to be extracted quickly and accurately, using simple mouse clicks. It is based on the lowest cost path algorithm, by Edsger W. Dijkstra. Firstly convolve the image with a Sobel filter to extract edges. Each pixel of the resulting image is a vertex of the graph and has edges going to the 4 pixels around it, as up, down, left, right. The edge costs are defined based on a cost function. In 1995, Eric N. Mortensen and William A. Barrett made some extension work on livewire segmentation tool, which is known as Intelligent Scissors.

Livewire segmentation

The user sets the starting point clicking on an image's pixel, known as an anchor. Then, as he starts to move the mouse over other points, the smallest cost path is drawn from the anchor to the pixel where the mouse is over, changing itself if the user moves the mouse. If he wants to choose the path that is being displayed, he simply clicks the image again.
One can easily see in the right image, that the places where the user clicked to outline the desired region of interest are marked with a small square. It is also easy to see that the livewire has snapped on the image's borders.

Livewire algorithm

Convolve the image with a Sobel filter to extract edges. Using this filtered image create a graph using pixels as nodes with edges in four directions. Edges are weighted with features gathered from the Sobel filter making it less costly to stay on an edge. Several different cost methods are possible but the most important is the gradient magnitude
Live-Wire 2-D DP graph search algorithm in pseudocode
algorithm Livewire is
input:
s
l
data structures:
L
N
e
g
output:
p
g ← 0; L ← s;
while L≠∅ do begin
q ← min;
e ← TRUE;
for each r∈N such that not e do begin
gtmp ←g + l;
if r∈L and gtmp < g then
r ← L;
if r∉L then begin
g ← gtmp;
p ← q;
L ← r;
end
end
end'

Extension to 3D

In 2010, Leo Grady extended the Livewire algorithm to 3D. This extension treated the 2D Livewire algorithm as enabling a user to specify a 0-dimensional boundary and finding the minimal 1-dimensional coboundary connecting those points, where the minimum is defined in terms of image properties. In order to extend the algorithm to 3D, the user is instead asked to specify one or more 1-dimensional boundaries and the algorithm finds the minimal 2-dimensional coboundary bounded by the 1-dimensional curves, where the minimum surface is defined in terms of image properties. This 3D extension of Livewire leans heavily on concepts of discrete exterior calculus to reinterpret the 2D Livewire algorithm from the standpoint of boundary/coboundary operators and then apply these concepts in 3D. An efficient algorithm for computing the 3D minimal surface is also provided in the Grady paper.