DISTANCE TRANSFORMATIONS:
FAST ALGORITHMS AND APPLICATIONS
TO MEDICAL IMAGE PROCESSING
Olivier CUISENAIRE
Thèse présentée en vue de l'obtention du grade de
Docteur en Sciences Appliquées
Octobre 1999
Foreword
Contents
General Overview
Introduction
Basic concepts
A typical application
Implementation issues
Aims of this thesis
A review of distance transformations
Definitions.
Approximate distance transformations.
Chamfering.
Vector propagation.
Exact Euclidean distance transformations.
Parallel processing.
Sequential processing by propagation.
Sequential processing by raster scanning.
Independent scanning
Voronoi transformation
Extended concepts
Geodesic distances
k-distance transformations
Distance transformations on gray-scale images
Applications
Discussion.
Euclidean distance transformation by propagation
Propagation with a single neighborhood
Errors in approximate EDT
Errors with a
neighborhood
Influence of the neighborhood size
Influence of the propagation process
Propagation with multiple neighborhoods
The PMN algorithm
Oriented neighborhoods
Computational Complexity
Using the Euclidean DT to implement mathematical morphology
Mathematical morphology operators
Fast implementations
Morphological dilation using PMN
Discussion
Application: morphometry of nerve cross-sections
Introduction
Anatomy of the nervous system
Nerve morphometry
Image acquisition
Animals and tissue preparation
Photography
Segmentation procedure
Pixel classification
Connected operators filtering
Myelin sheath thickness evaluation
False positive detection
Correction of obliquity
Experimental results
Detection ratios
Comparison with the manual procedure
Comparison with an arbitrary sampling
Discussion
Signed Euclidean DT with error detection and correction.
Signed EDT and Voronoi diagrams
Error correction
CSED Algorithm
Computational Complexity
Euclidean DT in 3 dimensions
Extending the approximate EDT to 3D
Possible error detection and correction methods in 3D
Limitations to the 3D error detection and correction methods
Hybrid algorithm, combining 4SSED+ and Saito's methods
Application: registration of MR images
Introduction
Applications
State of the Art
Methods using fiducial markers
Manual retrospective methods
Automatic retrospective methods
Discussion
Localization of transcranial magnetic stimulation
Registration method
Results
Registration of MR images with a Computerized Brain Atlas
Registration method
Results
Geodesic Distance Transformation
Geodesic metrics
Geodesic DT algorithms
Bucket sorting algorithm
Circular propagation algorithm
Accuracy
Computational complexity.
Application: Camera path-planning in virtual endoscopy
Virtual Endoscopy
Computing the shortest path from the
B
d
-geodesic DT
Path centering
Experimental results
k
-NN classification and
k
-distance transformation
Introduction
The
k
-DT algorithm.
Computational complexity.
Application: tissue classification in T1, T2 MR images.
The physics of T1- and T2-weighted MRI
T1,T2 classification
Results
Conclusion and perspectives
Related publications
List of Figures
Bibliography
About this document ...
Olivier Cuisenaire
1999-10-05