Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems
✍ Scribed by Yu-Hua Lee; Shi-Jinn Horng
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 290 KB
- Volume
- 73
- Category
- Article
- ISSN
- 1077-3142
No coin nor oath required. For personal study only.
✦ Synopsis
The distance transform (DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide an O(N 2 ) time sequential algorithm to compute the chessboard distance transform (CDT) of an N × N image, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of size N × N can be computed in O(log N) time on the EREW PRAM model using O(N 2 /log N) processors, O(log log N) time on the CRCW PRAM model using O(N 2 /log log N) processors, and O(log N) time on the hypercube computer using O(N 2 /log N) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of size N × N can be computed in O(log N) time on the EREW PRAM model using O(N 2 /log N) processors, O(log log N) time on the CRCW PRAM model using O(N 2 /log log N) processors, and O(log N) time on the hypercube computer using O(N 2 /log N) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.