Source-linked AI summary
Optimal Separable Algorithms to Compute the Reverse Euclidean Distance Transformation and Discrete Medial Axis in Arbitrary Dimension
David Coeurjolly, Annick Montanvert
TL;DR
Efficiently reconstructing shapes from Euclidean distance data and extracting a reversible discrete medial axis are linked problems in d-dimensional images. The paper gives time-optimal separable algorithms for REDT and reversible medial-axis extraction, plus a filtering process with two controls. Its conclusion reports O(nd) algorithms and a reversible medial-axis subset of the classic discrete medial axis.
Problem
The paper asks how to efficiently reconstruct a shape from points associated with Euclidean distance values and extract a discrete medial axis under the Euclidean metric.
Source: §1 · p. 1, §4.1 · p. 4Method
It uses separable one-dimensional maximization steps for REDT and builds a reversible medial-axis subset using the related envelope-based process.
Source: §6 · p. 10Results
The paper reports O(nd) time-optimal algorithms for REDT and reversible RDMA extraction, with the proposed RDMA a subset of the classic discrete medial axis.
Source: §6 · p. 10Takeaways & Limitations
Filtering RDMA balls by thickness and covering provides two controls, and the covering value bounds the grid-point difference after removing a ball.
Source: §5 · p. 10The reversible representation may not use the minimal number of disks, and reducing the RDMA point count remains future work.
Source: §1 · p. 2, §6 · p. 10
Abstract
from arXiv · showhide
In binary images, the distance transformation (DT) and the geometrical skeleton extraction are classic tools for shape analysis. In this paper, we present time optimal algorithms to solve the reverse Euclidean distance transformation and the reversible medial axis extraction problems for $d$-dimensional images. We also present a $d$-dimensional medial axis filtering process that allows us to control the quality of the reconstructed shape.
1 INTRODUCTION
The introduction places Euclidean distance transformations and medial-axis extraction among shape-analysis tools, then frames efficient reconstruction and reversible medial-axis extraction in arbitrary dimensions as the paper’s focus. It also motivates filtering for applications where boundary sensitivity makes a simplified, nonreversible description useful.
1 INTRODUCTION
- In a discrete shape, the medial axis is reversible: the shape can be exactly reconstructed from its medial-axis points.The distance-transform value at a point corresponds to the radius of the largest ball centered there and contained in the shape.Source: §1 · p. 1
- The paper proposes time-optimal methods for reconstructing shapes from Euclidean distance data and extracting a reversible subset of the medial axis in d dimensions.The reversible representation may use more disks than the minimum necessary.Source: §1 · pp. 1–2
- Boundary sensitivity can make a simplified, nonreversible description useful, motivating the paper’s d-dimensional medial-axis filtering process.The introduction presents filtering as a postprocess for such applications.Source: §1 · p. 2
- The paper’s roadmap covers linear-time d-dimensional EDT methods, optimized REDT, reversible medial-axis extraction, and filtering linked to computational geometry.The REDT and medial-axis algorithms are based on separable techniques.Source: §1 · p. 2
2 d-DIMENSIONAL EUCLIDEAN DISTANCE TRANSFORMATION
The section formulates the squared Euclidean distance transformation as separable one-dimensional passes. A lower-envelope computation combines the results, yielding linear total work in the number of grid points for d-dimensional images.
2 d-DIMENSIONAL EUCLIDEAN DISTANCE TRANSFORMATION
- In 2D, the first pass computes distances along x, and the y-axis pass minimizes the resulting squared-distance candidates to form the SDT map.The mixing step is the lower envelope of parabolas; in the illustrated column, [4, 1, 2, 1] becomes [2, 1, 2, 1].Source: §2 · p. 2, Figure 2 · p. 2
- The d-dimensional SDT uses an initial one-dimensional EDT followed by a mixing pass for each additional coordinate direction, for O(nd) total work.The initial pass and the lower-envelope mixing passes are each linear in the number of grid points across the image.Source: §2 · p. 2
- The optimal mixing algorithm computes the parabola lower envelope in linear time, and repeating it across dimensions preserves O(nd) complexity.The algorithm maintains candidate parabolas and scans the resulting envelope to assign distance-map values.Source: §2 · pp. 2–3
3 REVERSE EUCLIDEAN DISTANCE TRANSFORMATION
The section defines REDT as reconstructing the union of disks specified by center points and squared radii, and derives a separable maximization procedure. Its optimal algorithm computes upper envelopes in linear time per dimension and extends to d-dimensional images.
3 REVERSE EUCLIDEAN DISTANCE TRANSFORMATION
- REDT reconstructs the pixels lying within the disks defined by a set of center points and their associated squared radii.The shape is obtained by thresholding the computed map at strictly positive values.Source: §3 · p. 3
3.2 Optimal REDT Algorithm
- The reconstruction is separable: each coordinate direction applies a one-dimensional maximization, and the parabola upper-envelope formulation is reused for medial-axis extraction.The method constructs the upper envelope and then builds the map from its parabolas.Source: §3 · p. 3, §3.2 · p. 4
- The optimal REDT algorithm runs in O(nd) time for d-dimensional images, which the paper identifies as time optimal.Its upper-envelope procedure costs O(n) per one-dimensional pass; for an n × n image, the stated total is O(n²).Source: §3.2 · p. 4
4 EUCLIDEAN MEDIAL AXIS EXTRACTION
The paper develops separable algorithms for extracting a reversible, compact discrete medial axis in arbitrary dimension. Its reduced discrete medial axis (RDMA) is a subset of the discrete medial axis, preserves reconstruction, and is extracted in linear time.
4.1 Definitions and State-of-the-Art
- Earlier Euclidean inclusion-test approaches can require N^2 tests with worst-case cost proportional to disk radii, while lookup-table methods require loading a precomputed table into memory.The paper motivates its separable, time-optimal approach in part by these computational and memory costs.Source: §4.1 · pp. 4–5
4.3 Reduced Discrete Medial Axis Extraction
- Unlike the continuous case, Sk need not be a subset of the discrete medial axis, so the reduction removes Sk points whose discrete disks are nonmaximal.In the continuous plane, maximal disks correspond to maximal elliptic paraboloids, and Sk is a subset of the medial axis while still permitting reconstruction.Source: §4.1 · pp. 5–6
- The skeleton Sk is computed from the squared distance transform using the optimal reverse distance transform algorithm in O(n^d) time.The full pipeline then reduces Sk to the RDMA.Source: §4.1 · pp. 6–7
- A one-dimensional reduction sorts associated segments and greedily tests consecutive candidates, retaining a parabola when its discrete disk is not contained by the last retained disk.The list and reduction each take O(n) time per image row; in higher dimensions the process is applied along each dimension.Source: §4.1 · pp. 6–7
- The RDMA is a subset of the discrete medial axis, preserves reversibility, and is extracted in O(n^d) time.The authors describe it as a more compact reversible representation than the classic medial axis.Source: §4.1 · p. 7
5 DISCUSSION
The discussion relates REDT and RDMA computation to power diagrams, then uses power-cell measurements to filter medial-axis points in any dimension.
5 DISCUSSION
- In the continuous plane, maximal disks correspond to empty power-diagram cells, while REDT is linked to finding nonempty cells.For a discrete shape, Sk is the set of sites in the power diagram and RDMA is a subset selected by filtering.Source: §5 · pp. 9–10
- The filtering process does not control the global connectivity of the reconstructed shape.Source: §5 · p. 10
- Thickness measures ball radius and covering measures the number of grid points in its power cell, bounding the grid-point difference after removal by the covering value.Filtering retains balls according to thresholds on both measurements.Source: §5 · p. 10
- The RDMA and its filtering measurements can be computed in O(n^d) time for a d-dimensional binary object.The power labeling is computed through an upper envelope of d-dimensional elliptic paraboloids.Source: §5 · p. 10
6 CONCLUSION
The paper concludes with time-optimal algorithms for REDT and reversible RDMA extraction in d dimensions, plus a two-parameter filter to control reconstructed shape. It identifies reducing RDMA point counts and exploring other geometric descriptions as future directions.
6 CONCLUSION
- The optimized REDT and reversible RDMA extraction algorithms run in time O(n^d) for d-dimensional images.The paper reports O(n^d) time as optimal for REDT.Source: §6 · p. 10
- The proposed RDMA is a subset of the classic discrete medial axis, and two-parameter filtering controls reconstructed-object shape.The paper also details algorithms and provides a reference to C++ implementations.Source: §6 · p. 10
- Reducing RDMA point counts toward a minimal-point reversible skeleton is identified as future work,.The authors describe this as the goal of further RDMA extraction optimization.Source: §6 · p. 10
- Links between medial axes and computational-geometry objects suggest exploring other metrics and high-level features based on unions of maximal balls.Source: §6 · p. 11