MIMD DIVIDE-AND-CONQUER ALGORITHMS FOR THE DISTANCE TRANSFORMATION .2. CHAMFER-3-4 DISTANCE

In this paper we present parallel algorithms for the Distance Transformation (DT) with the Chamfer 3-4 distance measure. These algorithms are similar to the algorithms for the City Block (CB) distance measure, described in an earlier paper, although somewhat more complex. As for the CB distance partial DTs are calculated locally over several subregions and are combined to obtain global information from which the global DTs can be calculated locally. Special care for the combination step leads to the same calculation complexities as for the CB distance, except for the distributed calculation approach of the hierarchical algorithm, where unavoidably a higher number of messages need to be sent. This paper contains, for the DT with Chamfer 3-4 distance, a description of the algorithms, a complexity analysis and timings on an iPSC/2 parallel computer.