IMAT: The Iterative Medial Axis Transform
Yonghyeon Lee
Department of Mechanical Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorJonghyuk Baek
Department of Mechanical Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorYoung Min Kim
Department of Electrical and Computer Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorCorresponding Author
Frank Chongwoo Park
Department of Mechanical Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorYonghyeon Lee
Department of Mechanical Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorJonghyuk Baek
Department of Mechanical Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorYoung Min Kim
Department of Electrical and Computer Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorCorresponding Author
Frank Chongwoo Park
Department of Mechanical Engineering, Seoul National University, Seoul, Korea
Search for more papers by this authorAbstract
We present the iterative medial axis transform (IMAT), an iterative descent method that constructs a medial axis transform (MAT) for a sparse, noisy, oriented point cloud sampled from an object's boundary. We first establish the equivalence between the traditional definition of the MAT of an object, i.e., the set of centres and corresponding radii of all balls maximally inscribed inside the object, with an alternative characterization matching the boundary enclosing the union of the balls with the object boundary. Based on this boundary equivalence characterization, a new MAT algorithm is proposed, in which an error function that reflects the difference between the two boundaries is minimized while restricting the number of balls to within some a priori specified upper limit. An iterative descent method with guaranteed local convergence is developed for the minimization that is also amenable to parallelization. Both quantitative and qualitative analyses of diverse 2D and 3D objects demonstrate the noise robustness, shape fidelity, and representation efficiency of the resulting MAT.
References
- [ABE09] Attali D., Boissonnat J.-D., Edelsbrunner H.: 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, 2009, pp. 109–125.
- [ACK01] Amenta N., Choi S., Kolluri R. K.: The power crust. In Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications (2001), ACM, pp. 249–266.
10.1145/376957.376986 Google Scholar
- [AIM] 3d skeletonization benchmark. http://visionair.ge.imati.cnr.it/ontologies/shapes/. Accessed 3 May 2020.
- [AM97] Attali D., Montanvert A.: Computing and simplifying 2D and 3D continuous skeletons. Computer Vsion and Image Understanding 67, 3 (1997), 261–273.
- [ATCO*10] Au O. K.-C., Tai C.-L., Cohen-Or D., Zheng Y., Fu H.: Electors voting for fast automatic shape correspondence. Computer Graphics Forum (2010), 29, 645–654.
- [B*67] Blum H., et al.: A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form 19, 5 (1967), 362–380.
- [BO04] Bradshaw G., O'Sullivan C.: Adaptive medial-axis approximation for sphere-tree construction. ACM Transactions on Graphics (TOG) 23, 1 (2004), 1–26.
- [BP07] Baran I., Popović J.: Automatic rigging and animation of 3D characters. ACM Transactions on Graphics (TOG) (2007), 26, 72.
- [CL05] Chazal F., Lieutier A.: The
-medial axis. Graphical Models 67, 4 (2005), 304–331.
- [FLM03] Foskey M., Lin M. C., Manocha D.: Efficient computation of a simplified medial axis. In Proceedings of the Eighth ACM Symposium on Solid Modeling and Applications (2003), ACM, pp. 96–107.
- [GMPW09] Giesen J., Miklos B., Pauly M., Wormser C.: The scale axis transform. In Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry (2009), ACM, pp. 106–115.
- [JBPS11] Jacobson A., Baran I., Popovic J., Sorkine O.: Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics 30, 4 (2011), 78.
- [KG13] Karimipour F., Ghandehari M.: Voronoi-based medial axis approximation from samples: Issues and solutions. In Transactions on Computational Science XX. Springer, 2013, pp. 138–157.
10.1007/978-3-642-41905-8_9 Google Scholar
- [KJT16] Kustra J., Jalba A., Telea A.: Computing refined skeletal features from medial point clouds. Pattern Recognition Letters 76 (2016), 13–21.
- [Kol08] Kolluri R.: Provably good moving least squares. ACM Transactions on Algorithms (TALG) 4, 2 (2008), 18.
- [LKB07] Lien J.-M., Kurillo G., Bajcsy R.: Skeleton-based data compression for multi-camera tele-immersion system. In International Symposium on Visual Computing (2007), Springer, pp. 714–723.
- [LLF*20] Lan L., Luo R., Fratarcangeli M., Xu W., Wang H., Guo X., Yao J., Yang Y.: Medial elastics: Efficient and collision-ready deformation via medial axis transform. ACM Transactions on Graphics (TOG) 39, 3 (2020), 1–17.
- [LWS*15] Li P., Wang B., Sun F., Guo X., Zhang C., Wang W.: Q-mat: Computing medial axis transform by quadratic error minimization. ACM Transactions on Graphics (TOG) 35, 1 (2015), 8.
- [LY*84] Luenberger D. G., Ye Y., et al.: Linear and Nonlinear Programming, vol. 2. Springer, 1984.
- [MBC12] Ma J., Bae S. W., Choi S.: 3D medial axis point approximation using nearest neighbors and the normal field. The Visual Computer 28, 1 (2012), 7–19.
- [MGP10] Miklos B., Giesen J., Pauly M.: Discrete scale axis representations for 3d geometry. ACM Transactions on Graphics (TOG) 29, 4 (2010), 101.
- [RAV*19] Rebain D., Angles B., Valentin J., Vining N., Peethambaran J., Izadi S., Tagliasacchi A.: Lsmat least squares medial axis transform. In Computer Graphics Forum (2019), vol. 38, Wiley Online Library, pp. 5–18.
- [RT08] Reniers D., Telea A.: Segmenting simplified surface skeletons. In International Conference on Discrete Geometry for Computer Imagery (2008), Springer, pp. 262–274.
- [SCYW15] Sun F., Choi Y.-K., Yu Y., Wang W.: Medial meshes–a compact and accurate representation of medial axis transform. IEEE Transactions on Visualization and Computer Graphics 22, 3 (2015), 1278–1290.
- [SFM05] Sud A., Foskey M., Manocha D.: Homotopy-preserving medial axis simplification. In Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling (2005), ACM, pp. 39–50.
10.1145/1060244.1060250 Google Scholar
- [SSCO08] Shapira L., Shamir A., Cohen-Or D.: Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24, 4 (2008), 249.
- [SSGD03] Sundar H., Silver D., Gagvani N., Dickinson S.: Skeleton based shape matching and retrieval. In 2003 Shape Modeling International. (2003), IEEE, pp. 130–139.
10.1109/SMI.2003.1199609 Google Scholar
- [SVC] 2d skeletonization benchmark. https://www.cs.rug.nl/svcg/Shapes/SkelBenchmark. Accessed 3 May 2020.
- [TD17] Tsogkas S., Dickinson S.: Amat: Medial axis transform for natural images. In Proceedings of the IEEE International Conference on Computer Vision (2017), pp. 2708–2717.
- [TDS*16] Tagliasacchi A., Delame T., Spagnuolo M., Amenta N., Telea A.: 3d skeletons: A state-of-the-art report. Computer Graphics Forum (2016), 35, 573–597.
- [Vor08] Voronoi G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik 134 (1908), 198–287.
- [YYW*20] Yang B., Yao J., Wang B., Hu J., Pan Y., Pan T., Wang W., Guo X.: P2mat-net: Learning medial axis transform from sparse point clouds. Computer Aided Geometric Design (2020), 101874.
- [Zan69] Zangwill W. I.: Nonlinear Programming: A Unified Approach, vol. 196. Prentice-Hall, Englewood Cliffs, NJ, 1969.
