Distance Transform Algorithm for Bit-Serial SIMD Architectures

✍ Scribed by Jarmo H Takala; Jouko O Viitanen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 172 KB
• Volume: 74
• Category: Article
• ISSN: 1077-3142
• DOI: 10.1006/cviu.1999.0756

✦ Synopsis

A distance transform converts a binary image consisting of foreground (feature) and background (nonfeature) elements into a gray level image, where each element contains the distance from the corresponding element to the nearest foreground element. The calculation of exact Euclidean distance transform is a computationally intensive task and, therefore, approximations are often utilized. These algorithms are typically iterative or require several passes to complete the transform. In this paper, a novel parallel singlepass algorithm for the calculation of constrained distance transform is presented. The algorithm can be implemented by utilizing only bit-wise logical operations; thus, it is well suited for low-cost bit-serial SIMD architectures or conventional uniprocessors with a large word width, where the SIMD operation is emulated. Implementations on a parallel SIMD architecture and a sequential architecture are described. Comparisons are provided, showing results of the implementations of the presented algorithm, a sequential local algorithm utilizing integer approximated distances and an algorithm utilizing exact Euclidean distances.