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

In this paper we present parallel algorithms for the Distance Transfor mation (DT) with the Chamfer 3-4 distance measure. These algorithms ar e 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 subreg ions and are combined to obtain global information from which the glob al DTs can be calculated locally. Special care for the combination ste p leads to the same calculation complexities as for the CB distance, e xcept for the distributed calculation approach of the hierarchical alg orithm, where unavoidably a higher number of messages need to be sent. This paper contains, for the DT with Chamfer 3-4 distance, a descript ion of the algorithms, a complexity analysis and timings on an iPSC/2 parallel computer.