MIMD DIVIDE-AND-CONQUER ALGORITHMS FOR THE DISTANCE TRANSFORMATION .1. CITY-BLOCK DISTANCE

We present parallel algorithms for the Distance Transformation (DT) with the City Block (CB) distance measure. They are 'divide-and-conquer' algorithms operating on an image that is divided into subregions. Locally calculated partial DTs are combined into global information from which the global DT can be calculated locally. The computational complexity of the two local phases is proportional to the number of subregion pixels. The execution time of the combination step varies, depending on the combining strategy, from proportional to the image perimeter to proportional to the subregion perimeter. This paper contains, for the DT with CB distance, a description of the algorithm, a complexity analysis, a discussion on load balance and timings on an iPSC/2 parallel computer.