Table of ContentsClose
Coder for Life
2011-10-22 3:22 pm

Livewire

I have been working on an assisted-segmentation (a.k.a. semi-automatic segmentation) algorithm called livewire for use in the SLASH project.

Livewire is an algorithm where the user select a point and then moves the mouse and in real time it shows the "best" path between the point and the mouse. There are other implementations of this algorithm available online, many open-source. However this implementation sets itself apart with speed and quality of results.

Related Pages


Downloads

Source code is released under the GPL v2 license. The source code includes a minimal demo program. The only full program that includes this library is IMOD, an cross-platform image processing program. Source code for the algorithm is fairly well-commented, however other parts are currently lacking comments.

Test image used by all the demos (774.29 KB, updated 2012-11-08)

Livewire in C++/Qt:

Source Code (33.59 KB, updated 2012-11-08)

Demo EXE 32-bit (51 KB, updated 2012-11-08) Demo EXE 64-bit (63 KB, updated 2012-11-08)

Demo Dependencies for Windows (Qt and MSVC libraries). These only need to be downloaded once.

32-bit (4.84 MB, updated 2012-11-08) 64-bit (5.65 MB, updated 2012-11-08)

Livewire in Flash

Note: this is currently incomplete and only has a minimal Weight Calculator

Source Code (28.84 KB, updated 2012-11-08)

Demo SWF (7.35 KB, updated 2012-11-08)

Livewire in C#

Coming soon!


Updates

11/22/2011: Updates to C++ source code and demo program only

  • Reduced memory footprint significantly more for large images by making the LivewireCalculator and PointPriorityQueue use a 'SparseMatrix' that only allocate blocks of memory for regions of non-zeroes.
  • This now allows incredibly fast processing on very large images (tested on a 24000x16000 pixel image - ~370 megapixels).
  • Memory blocks are used in a pool to reduce allocations / frees
  • Entries in the PointPriorityQueue are also in a pool

11/15/2011: Updates to C++ source code and demo program only

  • Weight calculator now calculates blocks at a time instead of the whole image. This is critical for large images such as the ones used here in NCMIR (all the way up to 64000x64000 pixel images)
  • Livewire calculator requests that blocks in a particular region are calculated so that the entire image is never done at once
  • The blocks are completed in order of distance from the last livewire start point
  • All of the above has significantly changed how the classes are used
  • The demo program shows you which blocks are queued to be calculated and which ones are not calculated

11/7/2011: Updates to C++ source code only

  • Added support for even-sized windows when binning
  • Made some changes so GCC can compile it

10/22/2011: Initial Public Release


How to Use

Running the program will start it, however you need to give it an image to use (there are no options for this in the interface). By default it will use the image named "test.png" in the current directory. You can also specify an image as the first command line argument.

Clicking once starts the livewire from that point. Calculation progress is displayed in top left.

Another click will save the current livewire and start again from the new point.

A double click will save the current and wrapping livewires and start the wrapping from the double-clicked point (not available in Flash demo).


How it Works

Weight Calculator

Image data is processed by a series of filters to convert it into a set of weights, each pixel being represented by a value 0-255

  • Coalescing: convert the 3-channeled image data into a single byte-sized data channel:
    • RedChannel, GreenChannel, BlueChannel: Just the red, green, or blue channel of the data
    • AvgRGB: Average of the red, green, and blue channels
    • Luma, Luma601, LumaSMPTE: The luminance of the pixel, as defined by Rec. 709, Rec. 601, and SMPTE 240M respectively
    • WeightedHSV, WeightedHSL, WeightedHSI: The weighted sum of the hue, saturation, and value(brightness)/luminance/intensity of the pixel using the formula 0.6 * [V or L or I] + 0.3 * H + 0.1 * S

  • Optional Pixel Reduction: improves speed and memory usage by binng the pixel data; uses the same filters that noise reduction uses (and also allows for even-sized windows)

  • Optional Noise Reduction: improves performance by removing noise
    • MedianFilter3pxWindow, MedianFilter5pxWindow: Median filter with a 3px or 5px window size

    • MeanFilter3pxWindow, MeanFilter5pxWindow: Mean filter with a 3px or 5px window size

    • GaussianFilter3pxWindow, GaussianFilter5pxWindow: Gaussian filter with a 3px or 5px window size (std dev = 1)

  • Optional Edge Detection: follow edges instead of the data itself
    • Sobel

  • Optional Accentuation: make darks darker and lights lighter
    • Sigmoid

  • Optional Inversion: invert the data

Livewire Calculator

Uses the weights to find shortest paths

  • Uses Dijkstra's algorithm with a highly optimized binary heap based priority queue with scores that can be decreased
  • The score to traverse to a pixel is either the weight of the pixel for direct neighbors or the weight of the pixel * sqrt(2) for diagonal neighbors
  • As soon as a pixel has been visited it can be used in the interface to show a path, no need to wait for every pixel to become visited


Current Issues / Todo List