A cost optimal parallel algorithm for weighted distance transforms

✍ Scribed by Akihiro Fujiwara; Michiko Inoue; Toshimitsu Masuzawa; Hideo Fujiwara

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 147 KB
• Volume: 25
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00006-x

✦ Synopsis

The distance transform and the nearest feature transform are useful operations in image processing. These transforms are based on various kinds of distance functions because the distance functions have dierent eciency or usefulness. In this paper, we consider these transforms based on the weighted distance, which is a generalization of many distances, such as city block, chessboard and chamfer distances. This paper presents a parallel algorithm for these transforms of an n  n binary image. The algorithm runs in O log n time using n 2 a log n processors on the EREW PRAM and in O log logn time using n 2 a log logn processors on the common CRCW PRAM. The algorithm also runs in On 2 ap 2 n time on a p  p mesh and in On 2 ap 2 nlog pap time on a p 2 processor hypercube (for 1 T p T n). From these complexities, the algorithm is cost optimal on all models. Also we obtained an X log n lower bound for the transform on the CREW PRAM. This implies that the algorithm is time optimal on the EREW PRAM.