This paper describes a parallel algorithm for the Euclidean distance transform on a special-purpose architecture based on a reconfigurable mesh interconnection network. The proposed architecture, which supports the Euclidean distance transform algorithm as well as other low-level image processing algorithms, is particularly interesting because it can be effectively implemented in hardware and it can be programmed at a high level. The Euclidean distance transform algorithm described in this paper exploits the specific features of the reconfigurable interconnection network of the proposed dedicated architecture and takes advantage of the natural matching both between the data structure of the problem (a mesh of pixels) and that of the dedicated architecture (a mesh of processing elements) and between the nature of the computation (distance computation) and the capability of the interconnection network to let information flow from one node to a set of nodes by means of reconfigurable buses. The proposed algorithm has been implemented and has been validated through simulation, its computational complexity is O(N) (worst case) for pictures of N/spl times/N pixels on an architecture with N/spl times/N processing elements.
Euclidean distance transform on a dedicated architecture based on a reconfigurable mesh network
01.01.1999
212028 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Euclidean Distance Transform on a Dedicated Architecture based on a Reconfigurable Mesh Network
British Library Conference Proceedings | 1999
|A Constant-Time Algorithm for computing the Euclidean Distance Transform on Reconfigurable Meshes
British Library Conference Proceedings | 1997
|Skeletonization using an extended Euclidean distance transform
British Library Online Contents | 1995
|Efficient Computation of the Euclidean Distance Transform
British Library Online Contents | 2000
|