Fast parallel chessboard distance transform algorithms

Abstract

In this paper, based on the diagonal propagation approach, we first provide an O(N/sup 2/) time sequential algorithm to compute the chessboard distance transform (CDT) of an N/spl times/N image, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2-D binary image array of size N/spl times/N can be computed in O (log N) time on the EREW PRAM model using O(N/sup 2//log N) processors, O(log N/log log N) time on the CRCW PRAM model using O(N/sup 2/log log N/log N) processors and O(log N) time on the hypercube computer using O(N/sup 2/) processors. Following the mapping as proposed by Y.H. Lee and S.J. Horng (1995), the algorithm for the MAT is also efficiently derived. The medial axis transform of a 2-D binary image array of size N/spl times/N can be computed in O(log N) time on the EREW PRAM model using O(N/sup 2//log N) processors, O(log N/log log N) time on the CRCW PRAM model using O(N/sup 2/log log N/log N) processors, and O(log N) time on the hypercube computer using O(N/sup 2/) processors. Our algorithms are faster than the best previous results as proposed by J.F. Jenq and S. Sahni (1992).