Efficient Block-Based Medial Axis Transforms Based on L∞ Metric

Almost all of the existing two-dimensional block-based medial axis transform (2D_BB_MAT) parallel algorithm are devised for solving the 2D_BB_MAT problem only and are very difficult to extend to a solution of the 3D_BB_MAT problem in parallel. In this paper, we propose efficient O(1) time algorithms for solving the hD_BB_MAT problems, where h is 2 or 3, on the linear array with a reconfigurable pipelined bus system (LARPBS) model. The proposed 2D_BB_MAT algorithm can easily extend to a solution of the 3D_BB_MAT problem in parallel by reducing the hD_BB_MAT problems to the forward chessboard distance transform problems. To the best of our knowledge, the proposed algorithms are the most efficient O(1) time algorithms compared with all the previously published algorithms known.