''A Scalable and Efficient Algorithm for Computing the City Block Distance Transform on Reconfigurable Meshes''

Yi Pan

Jerry L. Trahan

Ramachandran Vaidyanathan

The Computer Journal, vol. 40, no. 7, pp. 435-440, 1997
Appeared in preliminary form: Proc. IASTED International Conference on Parallel and Distributed Computing Systems, (Washington, DC, Oct. 1997), pp. 85-90.


The distance transform is a basic operation in computer vision, pattern recognition, and robotics. In this paper, we consider the city block (L_1) distance metric. An algorithm for computing the city block distance transform on reconfigurable meshes is proposed in this paper. The time complexity and scalability of the algorithm are analyzed. The results indicate that the algorithm is scalable and efficient.

This work was supported in part by the National Science Foundation under grant number CCR-9503882 and the Louisiana Board of Regents through the Louisiana Education Quality Support Fund under contract number LEQSF(1994-96)-RD-A-07.