Livewire Segmentation Technique

Example of livewire segmentation on a baby's photo

Livewire, is a segmentation technique which allows a user to select regions of interest to be extracted quickly and accurately, using simple mouse clicks.^[1] 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.^[2]

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 (up, down, left right).^[1] 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^[1]

Live-Wire 2-D DP graph search algorithm in pseudocode ^[2]

    Input:
          s                       {Start (or seed) pixel.}
          l(q,r)                  {Local cost function for link between pixels q and r.} 
    Data Structures:
          L                       {List of active pixels sorted by total cost (initially empty).}
          N(q)                    {Neighborhood set of q (contains 8 neighbors of pixel).} 
          e(q)                    {Boolean function indicating if q has been expanded/processed.}
          g(q)                    {Total cost function from seed point to q.}
    Output: 
          p                       {Pointers from each pixel indicating the minimum cost path.}
    Algorithm:
          g(s) ← 0; L ← s;       {Initialize active list with zero cost seed pixel.}
          while L≠∅ do begin      {While still points to expand.}
                    q ← min(L);             {Remove minimum cost pixel q from active list.}
                    e(q) ←TRUE;             {Mark q as expanded (i.e., processed).}
                   for each r∈N(q) such that not e(r) do begin
                               gtmp ←g(q)+l(q,r);           {Compute total cost to neighbor.}
                               if r∈L and gtmp<g(r) then     {Remove higher cost neighbor’s from list.}
                                            r←L;                      
                               if r∉L then begin                  {If neighbor not on list, }
                                    g(r)←gtmp;                   {assign neighbor’s total cost, }
                                    p(r)←q;                      {set (or reset) back pointer, } 
                                    L←r;                         {and place on (or return to)  active list.} 
                               end                                
                    end 
           end

Livewire Variants

Recently, in 2013, shape-based information was integrated into the Livewire framework.,^[3]^[4] Livewire, posed as a shortest path problem, is essentially driven by lower level image based features. All the higher level knowledge about the problem domain is obtained from the user through mouse clicks. A higher level feature, namely shape up to a rigid transform, is integrated into the Livewire framework, thus reducing the burden on the user and the subjectivity involved in the annotation procedure, especially during instances of occlusions, broken edges, noise and spurious boundaries. The above-mentioned scenarios are commonplace in medical image annotation applications and, hence, such a tool will be of immense help to the medical community. As a first step, an offline training procedure is performed in which a mean shape and the corresponding shape variance is computed by registering training shapes up to a rigid transform in a level-set framework. The user starts the interactive segmentation procedure by providing a training segment, which is a part of the target boundary. A partial shape matching scheme based on a scale-invariant curvature signature is employed in order to extract shape correspondences and subsequently predict the shape of the unsegmented target boundary. A ‘zone of confidence’ is generated for the predicted boundary to accommodate shape variations.

References

1 2 3 BAGGIO, Daniel L´elis. GPGPU Based Image Segmentation Livewire Algorithm Implementation. 2007. 108f. Thesis of Master in Science – Technological Institute of Aeronautics, S˜ao Jos´e dos Campos. http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20February%2015th.pdf
1 2 MORTENSEN, E. N.; BARRETT, W. A. Intelligent scissors for image composition. In: SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. New York, NY, USA: ACM Press, 1995. p. 191–198. ISBN 0-89791-701-4.
↑ S. Kamalakannan; B. Bryant; H. Sari-Sarraf; R. Long; S. Antani; G. Thoma Integrating shape into an interactive segmentation framework, SPIE 8670, Medical Imaging 2013 http://spie.org/Publications/Proceedings/Paper/10.1117/12.2007262
↑ Demo of interactive shape segmentation https://sites.google.com/site/sridharanresearch/research#TOC-Integrating-Internal-properties-into-an-Interactive-Segmentation-Framework1

External links

This article is issued from Wikipedia - version of the 6/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Livewire Segmentation Technique