IMAT: Iterative Medial Axis Transform

[ Information ]

Computer Graphics Forum, vol. 40, no. 6. Wiley Online Library, 2021, pp. 162-181. 

[ Authors ]

Yonghyeon Lee, Jonghyuk Baek, Young Min Kim, and Frank C. Park

[ Abstract ]

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.