The scale axis transform

ABSTRACT

We introduce the scale axis transform, a new skeletal shape representation for bounded open sets O ⊂ R^d. The scale axis transform induces a family of skeletons that captures the important features of a shape in a scale-adaptive way and yields a hierarchy of successively simplified skeletons. Its definition is based on the medial axis transform and the simplification of the shape under multiplicative scaling: the s-scaled shape O_s is the union of the medial balls of O with radii scaled by a factor of s. The s-scale axis transform of O is the medial axis transform of O_s, with radii scaled back by a factor of 1/s. We prove topological properties of the scale axis transform and we describe the evolution s → O_s by defining the multiplicative distance function to the shape and studying properties of the corresponding steepest ascent flow. All our theoretical results hold for any dimension. In addition, using a discrete approximation, we present several examples of two-dimensional scale axis transforms that illustrate the practical relevance of our new framework.

REFERENCES

• 1: Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.
• 2: Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376986]
• 3: Dominique Attali, Jean-Daniel Boissonnat, and Herbert Edelsbrunner. Stability and computation of the medial axis - a state-of-the-art report. Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, 2007.
• 4: Jean-Daniel Boissonnat, Camille Wormser, and Mariette Yvinec. Curved Voronoi diagrams. In Jean-Daniel Boissonnat and Monique Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, pages 67--116. Springer-Verlag, Mathematics and Visualization, 2006.
• 5: Kevin Buchin , Tamal K. Dey , Joachim Giesen , Matthias John, Recursive geometry of the flow complex and topology of the flow complex filtration, Computational Geometry: Theory and Applications, v.40 n.2, p.115-137, July, 2008 [doi>10.1016/j.comgeo.2007.05.005]
• 6: Piermarco Cannarsa and Carlo Sinestrari. Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control. Birkhauser, Boston, USA, 2004.
• 7: Frédéric Chazal , André Lieutier, The "λ-medial axis", Graphical Models, v.67 n.4, p.304-331, July 2005 [doi>10.1016/j.gmod.2005.01.002]
• 8: Marc-Olivier Czarnecki and Ludovic Rifford. Approximation and regularization of Lipschitz functions: Convergence of the gradients. Transactions-American Mathematical Society, 358(10):4467, 2006.
• 9: Tamal Dey and Wulue Zhao. Approximate medial axis as a Voronoi subcomplex. Computer-Aided Design, 36(2):195--202, 2004.
• 10: Herbert Edelsbrunner. Deformable smooth surface design. Discrete & Computational Geometry, 21(1):87--115, 1999.
• 11: Karsten Grove and Katsuhiro Shiohama. A generalized sphere theorem. The Annals of Mathematics, 106(1):201--211, 1977.
• 12: Andre Lieutier. Any open bounded subset of R n has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029--1046, 2004.
• 13: Anton Petrunin. Semiconcave functions in Alexandrov's geometry. In Surveys in Differential Geometry: Metric and Comparison Geometry, volume XI. Internationational Press of Boston, 2007.
• 14: Stephen M. Pizer , Kaleem Siddiqi , Gabor Székely , James N. Damon , Steven W. Zucker, Multiscale Medial Loci and Their Properties, International Journal of Computer Vision, v.55 n.2-3, p.155-179, November-December 2003 [doi>10.1023/A:1026135101267]
• 15: R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis. Springer, 1997.
• 16: Avneesh Sud , Mark Foskey , Dinesh Manocha, Homotopy-preserving medial axis simplification, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.39-50, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060250]
• 17: Roger C. Tam , Wolfgang Heidrich, Feature-Preserving Medial Axis Noise Removal, Proceedings of the 7th European Conference on Computer Vision-Part II, p.672-686, May 28-31, 2002
• 18: Xiaofei Wang and Christina A. Burbeck. Scaled medial axis representation: evidence from position discrimination task. Vision Research, 38(13):1947--1958, 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory

Keywords:
medial axis, skeleton, topology