PARALLEL EXECUTION FO DISTANCE TRANSFORMATION OPERATION ON A LINEAR ARRAY ARCHITECTURE

Abstract

DT (Distance Transformaiton) has been widely used for image matching and shape analysis. In this paper, a parallel algorithm for compution distance transformation is presented. It is shown that the algorithm has an execution time of 6N-4 cycles, for an N*N image using a parallel architecture which require [N/2] parallel processors. In addition, the algotithm proposed can be used with various distance functions and its execution time is independent of the image content. Futhermore, we shall propose a partition method to process an image when the parallel architecture has a less number of PEs(Processing Elements). However, the total execution time is better than the four-pass algorithm with the same number of PEs.