Euclidean Distance Transform (Version 1.00)
links
executables
usage
changes
This software supports the computation of the Euclidean Distance Transform (EDT). Supported applications include:
- computation of the signed EDT of a volume represented by a voxel grid, using the method of [Saito and Toriwaki, 1994],
- computation of the unsigned EDT of a polygon mesh, using the methods of [Saito and Toriwaki, 1994] and [Danielsson, 1990],
- iso-surface extraction using marching cubes (and variants).
LINKS
EXECUTABLES
EDTFromMesh:
Computes the unsigned EDT from a triangle mesh and outputs a regular grid of dimension 2d×2d×2d sampling the distance values.
- --in <input mesh>
- This strings specifies the the names of the mesh.
The input mesh is assumed to be in PLY format, giving the set of vertices with the x-, y-, and z-coordinates of the positions encoded by the properties x, y, and z.
- [--out <output unsigned EDT>]
- This string is the name of the file to which the unsigned EDT is written. In addition to the values of the EDT (represented as single-precision floats, describing the distance to the surface in voxel units) the file also stores the similarity transformation mapping grid coordinates to model coordinates.
- [--depth <depth of the grid>]
- This integer specifies the depth of the grid used to sample the unsigned EDT. If the value of this parameter is d, the grid will have resolution 2d×2d×2d.
The default value for this parameter is 8.
- [--scale <bounding box scale>]
- This floating point values specifies the scaling of the bounding cube defining the domain over which the EDT is sampled.
The default value for this parameter is 2.
- [--radius <neighbor radius>]
- This integer values specifies the radius over which exact distances are computed. If the value is non-negative then the more precise method of Danielsson is used, with this value prescribing the radius for exact distance computation. Otherwise, the less precise (but more efficient) method of Saito and Toriwaki is used.
The default value for this parameter is -1.
EDTFromGrid:
Computes the signed EDT from a voxel mask and outputs a regular grid of dimension 2d×2d×2d with the distance values. For this implementation, the mask is represented by a set of color images (all of the same resolution) and a color specifiying the interior label. The output distance function will have negative values for points inside the labelled region and positive value for points outside of it.
- --in <input image list>
- This string is the name of the file listing the images in the stack.
The images can be in bmp, png, jpg, or jpeg format. The use of JPEG format is discouraged due to the lossy compression.
- --id <mask red> <mask green> <mask blue>
- This triplet of integer values values specifies the color that is used to define the interior of the mask.
- [--out <output signed EDT>]
- This string is the name of the file to which the signed EDT is written. In addition to the values of the EDT (represented as single-precision floats) the file also stores the similarity transformation mapping grid coordinates to model coordinates.
MarchingCubes:
Computes the level-set of an implicit function represented by its discrete samples over a regular grid using the Marching Cubes algorithm of Lorensen and Cline.
- --in <input grid>
- This string is the name of the regular grid sampling the implicit function.
- --value <iso-value>
- This floating point value specifies the iso-value used for surface extraction.
The default value for this parameter is 0.
- [--out <output surface>]
- This string is the name of the file to which extracted surface will be written. The surface will be written out in PLY format.
- [--fit <interpolation type>]
- This integer value specifies the way in which a 1D polynomial is fit to a grid edge.
- 0: a linear polynomial interpolating the values at the two end-points is used.
- 1: a quadratic polynomial interpolating the values at the two end-points and providing a least-squares fit to the derivatives at the two end-points is used.
- 2: a cubic polynomial interpolating the values at the two end-points and the two neighbors is used.
- 3: a (cubic) Catmull-Rom spline fit to the two end-points and the two-neighbors is used.
The default value for this parameter is 0.
- [--polygons]
- If this flag is specified, a polygon mesh is extracted. Otherwise the polygons are triangulated (using a minimum area triangulation) and a triangle mesh is returned.
USAGE EXAMPLES (WITH SAMPLE DATA)
EDTFromMesh/MarchingCubes
To run this executable you must specify the input mesh and the output voxel grid:
% Bin/*/EDTFromMesh --in bunny.ply --out bunny.saito.edt --depth 9
This generates a 512×512×512 voxel grid file of unsigned EDT values using Saito and Toriwaki's method. Using a non-negative radius:
% Bin/*/EDTFromMesh --in bunny.ply --out bunny.danielsson.edt --depth 9 --radius 1
generates a 512×512×512 voxel grid file of unsigned EDT values using Danielsson's method.
You can then extract the iso-surface at a distance of 5 voxels by calling:
% Bin/*/MarchingCubes --in bunny.saito.edt --out bunny.saito.ply --value 5
% Bin/*/MarchingCubes --in bunny.danielsson.edt --out bunny.danielsson.ply --value 5
The figure below shows a visualization of the input mesh (left) the iso-surface extracted from the EDT computed using Saito and Toriwaki's method (middle) and the iso-surface extracted from the EDT computed using Danielsson's method.
| 
| 
|
| Input
| Saito and Toriwaki's EDT
| Danielsson's EDT
|
EDTFromGrid/MarchingCubes
To run this executable you must specify the input masks (represented as a list of images), the (color) identifier of the mask of interest, and the output voxel grid:
% Bin/*/EDTFromMesh --in zeta.txt --id 249 249 209 --out zeta.A.edt
% Bin/*/EDTFromMesh --in zeta.txt --id 177 121 100 --out zeta.B.edt
This generates a 579×641×475 voxel grid file of signed EDT values using Saito and Toriwaki's method.
You can then extract the iso-surface at distance of -2, 0, and 5 voxels by calling:
% Bin/*/MarchingCubes --in zeta.A.edt --out zeta.A.-2.ply --value -2
% Bin/*/MarchingCubes --in zeta.A.edt --out zeta.A.0.ply --value 0
% Bin/*/MarchingCubes --in zeta.A.edt --out zeta.A.5.ply --value 5
% Bin/*/MarchingCubes --in zeta.B.edt --out zeta.B.-2.ply --value -2
% Bin/*/MarchingCubes --in zeta.B.edt --out zeta.B.0.ply --value 0
% Bin/*/MarchingCubes --in zeta.B.edt --out zeta.B.5.ply --value 5
The figure below shows a visualization of the iso-surfaces extracted from the EDT.
| 
| 
|
| id = (249,249,209); d = -2
| id = (249,249,209); d = 0
| id = (249,249,209); d = 5
|
| 
| 
|
| id = (177,121,100); d = -2
| id = (177,121,100); d = 0
| id = (177,121,100); d = 5
|
HISTORY OF CHANGES
HOME