Conclusion and perspectives

In this thesis, we have presented an extended review of distance transformation algorithms and their applications to medical image processing. While doing so, we have proposed a number of new algorithms. Some solve old problems faster, some address new problems by extending the distance transformation concept.
To a large extent, the problem of computing the exact Euclidean DT in two dimensions can be considered solved by the algorithms of chapters 3 and 5. They have a theoretically optimal O(n²) computational complexity on $n \times n$ images and a computational cost similar to that of approximate algorithms, which can reasonably be considered as the practical optimum.
In 3 dimensions, Saito's algorithm is the fastest for relatively small images, with a row or column size below 260. For larger datasets, the hybrid method of chapter 6 - combining slice by slice 2D EDT with the algorithm of chapter 5 and Saito's method along the inter-slice axis - performs best. Within the limits we explored, its computational cost is nearly independent of the image size.
Chapter 8 (geodesic DT) and chapter 10 (k-DT) explore extensions of the basic DT concept. Both are similar in the sense that they propose numerical rasterized solutions to problems that were traditionally considered within a continuous, analytical framework: the planning of a robot's path through a complex environment and k-NN classification of multi-spectral data.
Rasterizing other analytical problems represents a first major perspective for further extensions of this work. In particular, fast Delaunay triangulation and mesh generation techniques on complex data-sets could likely be addressed with modified DT algorithms.
This may appear to contradict the approach chosen by Breu [17], Guan [69] or Embrechts [44] (section ) who find efficient solutions to the discrete EDT problem by moving back to the continuous description of the Voronoi diagram. On the contrary, it stresses the fact that such issues are best handled when one can consider both sides of the problem - continuous and digital. This both-sides approach is best illustrated by the algorithm of chapter 5, that detects corners of the digital Voronoi diagram, then analytically computes the extent of these corners in the continuous space.
Considering the geodesic and k-DT algorithms further, both appear to have an optimal computational complexity, propagating from each pixel only once (or k times). On the other hand, both algorithms are only approximate Euclidean DTs, similarly to Danielsson's [37] or the PSN algorithm. One may wish to explore ways to generate exact geodesic or k-DTs, but it should be noted that no application currently requires this.
On the other hand, a second promising perspective resides in the search for algorithms with a better-than-optimal complexity. This apparently impossible task could be achieved using a multi-resolution approach, in which the full resolution is only computed in the few locations where it really is needed. For instance, k-NN classification only requires an exact k-DT on the borders separating the various classes, a tiny fraction of the complete sample space.
Beside its algorithmic content, this thesis also presents a broad range of medical image processing applications. In all cases, the distance transformation is only a part of the whole image processing pipe-line. In chapter 4, myelin sheath thickness can only be evaluated after the image was thresholded and filtered with connected morphological operators. In chapter 7, surface-based registration methods require the preliminary segmentation of similar features in both images. In chapter 9, virtual endoscopy works in three steps. First the organ is segmented and a 3D model of it is computed, then the geodesic DT is used to plan the camera's path, and finally the 3D model and the camera locations are used to generate the endoscopic visualization. In chapter 11, pixel classification in multi-channel MRI requires to manually pick samples of each tissue types. Alternatively, the k-NN classification can be embedded into a more global framework in which the anatomical knowledge is inserted using deformable templates.
From this brief review, it is clear that applications - particularly in the medical imaging field - is where most perspectives are open for further creative research. In our experience, creativity is often stimulated by practical examples. We hope that those presented in this thesis have contributed to stimulate the reader's mind.