Pan Li
Bin Wang
Abstract
The medial axis transform (MAT) is an important shape representation for shape approximation, shape recognition, and shape retrieval. Despite years of research, there is still a lack of effective methods for efficient, robust and accurate computation of the MAT. We present an efficient method, called Q-MAT, that uses quadratic error minimization to compute a structurally simple, geometrically accurate, and compact representation of the MAT. We introduce a new error metric for approximation and a new quantitative characterization of unstable branches of the MAT, and integrate them in an extension of the well-known quadric error metric (QEM) framework for mesh decimation. Q-MAT is fast, removes insignificant unstable branches effectively, and produces a simple and accurate piecewise linear approximation of the MAT. The method is thoroughly validated and compared with existing methods for MAT computation.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Q-MAT: Computing Medial Axis Transform By Quadratic Error Minimization
- N. Amenta and M. Bern. 1998. Surface reconstruction by voronoi filtering. In Proceedings of the 14th Annual Symposium on Computational Geometry (SCG'98). ACM, New York, 39--48. Google Scholar
Digital Library
- N. Amenta, S. Choi, and R. K. Kolluri. 2001. The power crust. In Proceedings of the 6th ACM symposium on Solid modeling and applications. ACM, 249--266. Google ScholarDigital Library
- D. Attali, J.-D. Boissonnat, and H. Edelsbrunner, H. 2009. Stability and computation of medial axes-a state-of-the-art report. In Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Springer, 109--125.Google Scholar
- D. Attali, and A. Montanvert, A. 1996. Modeling noise for a better simplification of skeletons. In Proceedings of the International Conference on Image Processing. Vol. 3. IEEE, 13--16.Google Scholar
- H. Blum et al. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form 19, 5, 362--380.Google Scholar
- F. Chazal and A. Lieutier. 2005. The λ-medial axis. Graphical Models 67, 4, 304--331. Google ScholarDigital Library
- X. Chen, A. Golovinskiy, and T. Funkhouser. 2009. A benchmark for 3d mesh segmentation. ACM Transactions on Graphics 28, 73. Google ScholarDigital Library
- S. W. Choi and H.-P. Seidel. 2001. Hyperbolic Hausdorff distance for medial axis transform. Graphical Models 63, 5, 369--384. Google ScholarDigital Library
- T. K. Dey, H. Edelsbrunner, S. Guha, and D. V. Nekhayev 1998. Topology preserving edge contraction. Publ. Inst. Math. (Beograd) N.S 66, 23--45.Google Scholar
- T. K. Dey and W. Zhao. 2004. Approximate medial axis as a Voronoi subcomplex. Computer-Aided Design 36, 2, 195--202.Google ScholarCross Ref
- N. Faraj, J.-M. Thiery, and T. Boubekeur. 2013. Progressive medial axis filtration. In SIGGRAPH Asia 2013 Technical Briefs. ACM, 3. Google ScholarDigital Library
- M. Foskey, M. C. Lin, and D. Manocha. 2003. Efficient computation of a simplified medial axis. Journal of Computing and Information Science in Engineering 3, 4, 274--284.Google ScholarCross Ref
- M. Garland and P. S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 209--216. Google ScholarDigital Library
- Z. Ji, L. Liu, and Y. Wang. 2010. B-mesh: A modeling system for base meshes of 3d articulated shapes. In Computer Graphics Forum. Vol. 29. Wiley Online Library, 2169--2177.Google Scholar
- B. Miklos, J. Giesen, and M. Pauly. 2010. Discrete scale axis representations for 3d geometry. ACM Transactions on Graphics 29, 4, 101. Google ScholarDigital Library
- Pixologic. 2001. Zbrush.Google Scholar
- S. M. Pizer, K. SIDDIQI, G. Székely, J. N. Damon, and S. W. Zucker, 2003. Multiscale medial loci and their properties. International Journal of Computer Vision 55, 2--3, 155--179. Google ScholarDigital Library
- K. Siddiqi and S. M. Pizer. 2008. Medial Representations. Mathematics, Algorithms and Applications. Springer. Google ScholarDigital Library
- A. Sud, M. Foskey, and D. Manocha. 2005. Homotopy-preserving medial axis simplification. In Proceedings of the ACM Symposium on Solid and Physical Modeling (SPM'05). ACM, New York, 39--50. Google ScholarDigital Library
- F. Sun, Y. Choi, Y. Yu, and W. Wang. 2013. Medial meshes for volume approximation. CoRR abs/1308.3917.Google Scholar
- F. Sun, Y. Choi, Y. Yu, and W. Wang. 2014. Medial meshes: A compact and accurate medial shape representation. IEEE Transactions on Visualization and Computer Graphics.Google Scholar
- J.-M. Thiery, É. Guy, and T. Boubekeur. 2013. Sphere-meshes: shape approximation using spherical quadric error metrics. ACM Transactions on Graphics 32, 6, 178. Google ScholarDigital Library
Recommendations
Voxel cores: efficient, robust, and provably good approximation of 3D medial axes
We present a novel algorithm for computing the medial axes of 3D shapes. We make the observation that the medial axis of a voxel shape can be simply yet faithfully approximated by the interior Voronoi diagram of the boundary vertices, which we call the ...
Q-MAT+: An error-controllable and feature-sensitive simplification algorithm for medial axis transform
AbstractThe medial axis transform (MAT), as an intrinsic shape representation, plays an important role in shape approximation, recognition and retrieval. Q-MAT is a state-of-the-art algorithm driven by quadratic error minimization to compute a ...
Homotopy-preserving medial axis simplification
SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modelingWe present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial ...
Comments