Livewire Segmentation

About

Example of livewire segmentation on a baby's photo (courtesy of wikipedia)

Livewire, also known as Intelligent Scissors, is a segmentation technique which allows a user to select regions of interest to be extracted quickly and accurately using a relatively small number of mouse clicks. There are many variation on livewire, but perhaps the best known example is the "magnetic lasso" tool in Photoshop. Even more sophisticated versions may take into account training data and/or lines drawn around images from neighboring slices or frames (in the case of 3D image data or animation). Livewire can be a huge help in quick image segmentation and so on this page I've collected links to any freely available code and papers on the topic.

How Livewire Works

Livewire typically works as two stage process.

1. The entire image must be filtered using filters such as the Median filter, and/or edge detection algorithms such as the Sobel filter and (if not already) converted to grayscale such that black regions (the smallest value) represent the most desirable paths.
2. A lowest cost path algorithm, such as Dijkstra's algorithm, is applied to the modified image to find the best path from one point, to another. In resulting "graph" each pixels is a node with edges going to the 4 (up,down,left,right) or 8 pixels around it and the edge costs are defined on a cost function based on the pixel value, and possibly other factors.

Examples of Livewire in Popular Programs

• "Magnetic Lasso" in Adobe Photoshop - without a doubt one of the best tools and works just as well (probably better) on complex colored photos as greyscale images. I have no idea exactly how this works - we suspect it's a bit different from a "pure" livewire algorithm. Rather than drawing point to point it considers how you move your mouse and will actually add points automatically (see youtube video), even if you don't want a point in that spot!
• "Intelligent Scissors" in GIMP - implemented very well here... although it doesn't show a predicted path from the last point clicked to where you're mouse is - what it does do is let you click anywhere on the line and drag to add a new point between those existing ones... which is very cool. This youtube video shows the basic operation, but not the modifying the line part.
• "Ivussnakes plugin" in ImageJ - seems to do very well at tracing along an edge - for example the outline of a boundary.... however by default allows only a relatively small distance between consecutive points. From a practical point of view it's very annoying to use because (a) you have to download the .jar from here, extract and put it in correct directory and (b) every-time you start ImageJ you seem to have to run macro to reinstall the plugin so it appears... and even then you might find memory issues occur. Is a shame because it seems very accurate when it comes to tracing.

Livewire Source Code

• ivussnakes ImageJ Plugin - written in Java - you can download and extract this .jar file and has decent comments, but with all its ImageJ GUI integration feature it might be a bit full on to understand unless you have a real desire to learn ImageJ code.

• Live-Wire-ing the Insight Toolkit with Intelligent Scissors - written in C++ - download the .zip file and shows a relatively small amount of code to get intelligent scissors working. The tricky part is that it's based on the Insight Segmentation and Registration Toolkit (ITK), so you'd need to install and compile ITK to get it working. Also on this page is a nice paper.

• Progressive Livewire - written in C++ with a simple version in Java. On the main page they have a java applet to demonstrate on an MRI image. It's actually really bad at first, but when you hit "train" it adjusts the filtering so that when you "switch image" it will do better on the next. From this page you can download the Java applet version or more complete C++ version, but my biggest problem is that neither have ANY code comments! The Java version we got compiling, but the C++ requires GLUT installed and on a Mac machine I got seg faults so gave up.

LiveWire in IMOD (just 4 points)

• Jeff's Livewire - written in C++ using Qt, but also version in C# and Flash ActionScript (demo here). Jeffrey Bush is a PhD student working in the same lab as me and set out to design faster, more efficient and more accurate live-wire than the other pieces of code, and he's done just that (see the image on the right drawn with just 4 well placed points - much fewer than in the other screenshots). What makes his LiveWire so effective is the intelligent choice of image adjustment and filtering options to reduce image noise in one thread, while one or more other threads run live-wire over the filtered image. With Jeff's help it took us just a few hours to get his code integrated into the IMOD tool suite used for segmentation of noisy grayscale "electron microscope" images, but his code has many smart options for color images too.

Papers

• Neural Process Reconstruction from Sparse User Scribbles, Roberts et al. Takes "sparse scribble annotations" by users and propagates segmentation in3D on EM image of brain tissue.
• Live-Wire Revisited, Salah et al. Short paper that proposes an "adaptive propagation as an alternative to individually processing all image slices or shape-based interpolation of live-wire contours".

Links

• Livewire Segmentation Technique - Wikipedia

Acknowledgements: Jeff Bush, Raj Singh and Rich Stoner from UCSD for getting me interested in this time-saving segmentation technique. Liz Jurrus for sending links to some papers and extra source code.