PPT Slide
We developed an Exact Euclidean DT algorithm in 2D.
It is based on the well know 4SSED algorithm, followed by an “error correction” step.
The computational cost is o(n²) for n×n images, whatever the image.
The computational cost is similar to EDT approximations, i.e. an order of magnitude faster than current EDTs.
Olivier Cuisenaire’s work is funded by the Belgian Fonds pour la formation à la Recherche dans l’Industrie et l’Agriculture (FRIA).
Saito, Eggers and PMN’s computational complexities are highly orientation dependent. CSSED’s complexity is to a large extent orientation independent, similarly to Chamfer and 4SSED, the EDT approximations.
This result could be amplified by a third test image: a straight line of various orientations. This is indeed the worst case scenario for Eggers’ and Ragnelmam’s DTs. In this case too CSSED is largely image independent.