title: Seeded ND medical image segmentation by cellular automaton on GPU.
abstract: OBJECTIVE
  We present a GPU-based framework to perform organ segmentation in N-dimensional (ND) medical image datasets by computation of weighted distances using the Ford-Bellman algorithm (FBA). Our GPU implementation of FBA gives an alternative and optimized solution to other graph-based segmentation techniques.
  
  
  METHODS
  Given a number of K labelled-seeds, the segmentation algorithm evolves and segments the ND image in K objects. Each region is guaranteed to be connected to seeds with the same label. The method uses a Cellular Automata (CA) to compute multiple shortest-path-trees based on the FBA. The segmentation result is obtained by K-cuts of the graph in order to separate it in K sets. A quantitative evaluation of the method was performed by measuring renal volumes of 20 patients based on magnetic resonance angiography (MRA) acquisitions. Inter-observer reproducibility, accuracy and validity were calculated and associated computing times were recorded. In a second step, the computational performances were evaluated with different graphics hardware and compared to a CPU implementation of the method using Dijkstra's algorithm.
  
  
  RESULTS
  The ICC for inter-observer reproducibility of renal volume measurements was 0.998 (0.997-0.999) for two radiologists and the absolute mean difference between the two readers was lower than 1.2% of averaged renal volumes. The validity analysis shows an excellent agreement of our method with the results provided by a supervised segmentation method, used as reference.
  
  
  CONCLUSIONS
  The formulation of the FBA in the form of a CA is simple, efficient and straightforward, and can be implemented in low cost vendor-independent graphics hardware. The method can efficiently be applied to perform organ segmentation and quantitative evaluation in clinical routine.
authors.affiliation: Department of Medical Imaging, Notre-Dame Hospital, CHUM, 1560 Sherbrooke East, Montreal, QC H2L 4M1, Canada. claude.kauffmann@gmail.com
authors.forename: Claude
authors.initials: C
authors.lastname: Kauffmann
authors.forename: Nicolas
authors.initials: N
authors.lastname: Piché
mesh_terms: D000465:Algorithms; D003196:Computer Graphics / Q000592:standards; D005260:Female; D006801:Humans; D007090:Image Interpretation, Computer-Assisted; D021621:Imaging, Three-Dimensional; D007668:Kidney / Q000473:pathology*; D018810:Magnetic Resonance Angiography / Q000379:methods*; D008297:Male; D009716:Numerical Analysis, Computer-Assisted; D015588:Observer Variation; D010363:Pattern Recognition, Automated