“Q-MAT: Computing Medial Axis Transform By Quadratic Error Minimization” by Yan, Sykes, Chambers, Letscher and Ju

  • ©Yajie Yan, Kyle Sykes, Erin Chambers, David Letscher, and Tao Ju

Conference:


Type:


Title:

    Q-MAT: Computing Medial Axis Transform By Quadratic Error Minimization

Session/Category Title: GEOMETRY

Presenter(s)/Author(s):


Moderator(s):


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.

References:


    1. 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. 
    2. 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. 
    3. 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.
    4. 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.
    5. 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.
    6. F. Chazal and A. Lieutier. 2005. The λ-medial axis. Graphical Models 67, 4, 304–331. 
    7. X. Chen, A. Golovinskiy, and T. Funkhouser. 2009. A benchmark for 3d mesh segmentation. ACM Transactions on Graphics 28, 73. 
    8. S. W. Choi and H.-P. Seidel. 2001. Hyperbolic Hausdorff distance for medial axis transform. Graphical Models 63, 5, 369–384. 
    9. 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.
    10. T. K. Dey and W. Zhao. 2004. Approximate medial axis as a Voronoi subcomplex. Computer-Aided Design 36, 2, 195–202.
    11. N. Faraj, J.-M. Thiery, and T. Boubekeur. 2013. Progressive medial axis filtration. In SIGGRAPH Asia 2013 Technical Briefs. ACM, 3. 
    12. 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.
    13. 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. 
    14. 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.
    15. B. Miklos, J. Giesen, and M. Pauly. 2010. Discrete scale axis representations for 3d geometry. ACM Transactions on Graphics 29, 4, 101. 
    16. Pixologic. 2001. Zbrush.
    17. 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. 
    18. K. Siddiqi and S. M. Pizer. 2008. Medial Representations. Mathematics, Algorithms and Applications. Springer. 
    19. 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. 
    20. F. Sun, Y. Choi, Y. Yu, and W. Wang. 2013. Medial meshes for volume approximation. CoRR abs/1308.3917.
    21. 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.
    22. J.-M. Thiery, É. Guy, and T. Boubekeur. 2013. Sphere-meshes: shape approximation using spherical quadric error metrics. ACM Transactions on Graphics 32, 6, 178.

ACM Digital Library Publication:


Overview Page: