3D Squared Euclidean Distance Transform in optimal time

sedt is a simple program to compute the squared Euclidean distance transform of a binary object (using the VOL format) in optimal time (i.e. in O(n) if n is the number of voxels). It is an implementation of the Saito and Toriwaki algorithm [SAITO_1994] with the optimization proposed by [HIRATA_1996] and [MEIJSTER_2000].

The output (SEDT) is a file in the longvol format.

Download sedt3D-0.3.tgz (TAR GZIPPED file) version 0.3 (C++ bugs fixed to speed up the algorithm, see the README file)
Compilation: standard C++ program, see the Makefile. To compile, you need the VOL and the LONGVOL libraries. To generate the commented source files, you also need the documentation system doxygen.
Main references:
Feed back: David Coeurjolly

The code is really simple and code comments can be browsed using doxygen (just enter "make doc" and browse the resulting html files). See the README file.

Just an example, let us consider a simple cube with length 5 (see Volgen) :

Once sedt compiled, you can launch it :

 sedt cube_5.vol cube_5_output.longvol

You will obtain and longvol file containing the SEDT values and the program also prints in the standard output the SEDT values slice by slice (Z axis). Since the code is really simple, this last point can be easily disabled.

Standard output:


0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 4 4 4 1 0 0 
0 0 0 1 4 4 4 1 0 0 
0 0 0 1 4 4 4 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 1 4 4 4 1 0 0
0 0 0 1 4 9 4 1 0 0
0 0 0 1 4 4 4 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 4 4 4 1 0 0 
0 0 0 1 4 4 4 1 0 0 
0 0 0 1 4 4 4 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

dcoeurjo

Last modified: Tue Feb 4 17:42:27 MET 2003