About


Overview Poster

Updating segmentation results in real-time based on repeated user input is a reliable way to guarantee accuracy, paramount in medical imaging applications, while making efficient use of an expert’s time. The random walker algorithm with priors is a robust method able to find a globally optimal probabilistic segmentation with an intuitive method for user input. However, like many other segmentation algorithms, it can be too slow for real-time user interaction. We propose a speedup to this popular algorithm based on offline precomputation, taking advantage of the time images are stored on servers prior to an analysis session. Our results demonstrate the benefits of our approach. For example, the segmentations found by the original random walker and by our new precomputation method for a given 3D image have a Dice’s similarity coefficient of 0.975, yet our method runs in 1/25th of the time.
[Back to the top]

 

Publications


[Paper, Poster
, BibTex]  Shawn Andrews, Ghassan Hamarneh, and Ahmed Saad. Fast Random Walker with Priors using Precomputation for Interactive Medical Image Segmentation. In Lecture Notes in Computer Science, Medical Image Computing and Computer-Assisted Intervention (MICCAI), pages III:9-16, 2010.
 

[Report, BibTex] Shawn Andrews, Ghassan Hamarneh, and Ahmed Saad.   Fast Random Walker with Priors using Precomputation for Interactive Medical Image Segmentation. Technical Report TR 2010-07, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada, June 2010.  

[Back to the top]


Software


The Fast Random Walker is available for download.  
You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. We kindly ask you to acknowledge the use of this software and cite our related paper(s) (listed above) in your publications and presentations. Download this software from:  here .
[Back to the top]



Sample Results


The figure below shows a comparison in runtime for images of increasing size (number of pixels) for different methods. The original RW with priors is in blue. Our proposed algorithm is in red.


 

The figure below shows the results achieved with our method in terms of accuracy and speed up. Note for example in the bottom left subfigure how the online runtime drops from 0.552 to 0.097 seconds when our precomputation method is used, and the accuracy is suffers only marginally, having a 0.996 Dice Similarity Coefficient.

 




The figure below shows the results achieved with our method on a 3D image of a knee. Seeds were placed in only one of the 3 disconnected bones, so RW with priors must be used to segment all of the bones. When our precomputation method is used, the online runtime drops from 40.5 to 1.56 seconds, while a Dice Similarity Coefficient of 0.975 is maintained.

[Back to the top]

 



Contacts


email us
 

PhD Student: Shawn Andrews

PhD Student: Ahmed Saad
Principal Investigator: Ghassan Hamarneh

[Back to the top]




Credits


Thanks to Leo Grady, whose work ours extends, and whose Graph Toolbox is a basis for our software. Leo Grady's Graph Toolbox is available for download
here and on his site.
[Back to the top]