PARALLEL COMPUTATION OF DISEASE TRANSFORMS

Abstract

Distance transforms are an important computational tool for the processing of binary images. For an n x n image, distance transforms can be computed in time O(n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple O(log n) algorithm for the distance transform with respect to the L1-metric, an O(log2 n) algorithm for the transform with respect to the L infinity -metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for any L(k)-metric and takes time O(log3 n).