The Problem: Brittleness in Shape Analysis
The Medial Axis Transform (MAT) is a fundamental tool in shape analysis, representing an object as a collection of "maximally inscribed spheres." The centers of these spheres form a "skeleton" that captures the object's topology and thickness. This representation is vital for tasks ranging from character animation to medical imaging.
However, traditional MAT algorithms are notoriously "brittle." Because they rely on exact computational geometry—such as Voronoi diagrams—even a tiny amount of noise on the surface of an object can trigger the creation of "spurious branches." These extra skeletal fingers do not represent the actual shape and often obscure the underlying structure. While researchers have historically attempted to fix this with post-processing filters, these methods often struggle with heavy noise or objects with varying feature sizes.
Methods: A Continuous Optimization Approach
Instead of treating the medial axis as a combinatorial geometry problem, LSMAT frames it as a continuous optimization problem. The authors define an energy function for a sphere $s$ (with center $c$ and radius $r$) and minimize it using an iterative Gauss-Newton solver. The core energy function consists of two competing terms:
- Maximality Energy ($E_{maximal}$): This acts like internal air pressure, constantly trying to expand the sphere's radius.
- Inscription Energy ($E_{inscribed}$): This penalizes the sphere for extending outside the object's boundary.
To make this work with unorganized point clouds, the method utilizes a blended Signed Distance Function (SDF) that combines point-to-point and point-to-plane distances. Crucially, they introduce a "Pinning" constraint to keep each sphere associated with its starting boundary point, ensuring the entire skeleton is covered. Because each sphere is optimized independently, the algorithm is trivially parallelizable and runs efficiently on GPUs.
Key Insights: Numerical vs. Combinatorial
A core insight of LSMAT is that seeking an approximate least-squares solution rather than an exact geometric one naturally filters out high-frequency noise. By treating the problem numerically, the algorithm effectively ignores the surface "jitter" that would otherwise create spurious branches in a Voronoi-based approach. Furthermore, the "constant pressure" design of the maximality term ensures that the optimization scale is consistent; small features are not overpowered by larger ones, allowing the algorithm to capture fine details even in complex shapes with varying thickness.
Key Results: Stability Under Noise
LSMAT demonstrates superior robustness compared to state-of-the-art methods like QMAT and Scale Axis Transform (SAT). In head-to-head comparisons, LSMAT remained stable at noise levels where other methods produced nonsensical results.
For instance, on the "Horse" model (Figure 1), LSMAT handled noise an order of magnitude larger than previous work. 2D experiments showed that as noise increased, LSMAT’s error (distance to the ground-truth medial axis) remained significantly lower and more stable than Voronoi-based filtering methods. While the iterative numerical solver is computationally heavier than simple geometric heuristics—taking approximately 11 seconds for 10k spheres—it provides a much higher quality result in noisy conditions, offering a "set-and-forget" robustness for practical applications.
Limitations and Future Work
The current method requires oriented point clouds; if surface normals are noisy or flipped, the inscription energy can fail. Additionally, as an iterative solver, it is slower than simple heuristics. Future directions include exploring robust norms (like $L_1$ optimization) to handle extreme outliers and adding smoothness priors to ensure neighboring spheres on the skeleton have similar radii, further improving results on sparse or incomplete data.
Summary updated