Q-MAT: Computing medial axis transform by quadratic error minimization

Abstract

The medial axis transform (MAT) is an important shape representation for shape approximation, shape recognition, and shape retrieval. Despite of 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 {em 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.