Euclidean distance transform on a dedicated architecture based on areconfigurable mesh network

摘要

This paper describes a parallel algorithm for the Euclideandistance transform on a special-purpose architecture based on areconfigurable mesh interconnection network. The proposed architecture,which supports the Euclidean distance transform algorithm as well asother low-level image processing algorithms, is particularly interestingbecause it can be effectively implemented in hardware and it can beprogrammed at a high level. The Euclidean distance transform algorithmdescribed in this paper exploits the specific features of thereconfigurable interconnection network of the proposed dedicatedarchitecture and takes advantage of the natural matching both betweenthe data structure of the problem (a mesh of pixels) and that of thededicated architecture (a mesh of processing elements) and between thenature of the computation (distance computation) and the capability ofthe interconnection network to let information flow from one node to aset of nodes by means of reconfigurable buses. The proposed algorithmhas been implemented and has been validated through simulation, itscomputational complexity is O(N) (worst case) for pictures of N×Npixels on an architecture with N×N processing elements