A Hardware Algorithm For Euclidean Distance Transform Based On Binary Images

Distance transform can find many applications in the research of image processing, pattern recognition, robotics and morphologic etc. Euclidean distance transform is one of most useful distance transform algorithms. It defines the distance of the line between two points in the space. The fast progress of multimedia technology and image processing pushes the research in algorithms for distance transform into a further level.In this paper, the principle of Euclidean distance transform based on binary images was demonstrated in detail, and it also introduced the implementation schemes and calculation capabilities of those algorithms for Euclidean distance transform which are known. With focus on the practical application, we took some reforms in this paper to implement the distance transform algorithm based on the advantages of previous researches.Firstly, we changed the implementation scheme, which is oriented on software for Euclidean distance transform, to an easy design of hardware with the calculationcomplexity of o(n2). Secondly, in our design, by using "in-place" calculation, theintermediate data and the result output can use the same memory.This reduces the number of memory in order to improve the scale of the circuit. Also, we use fast and small size components such as adders and comparators to implement the function of multipliers so as to speed up the calculation. Finally, with the step-by-step scheme, we implemented the fast hardware algorithm for Euclidean distance transform based on two-dimension images.Our design, compared with previous schemes, has these following advantages: (1) the calculation speed was accelerated from o(n3) to o(n2) , this make theimplementation of Euclidean distance transform possible. (2) by using the "in-place" calculation and replacing the complex components, the size of the circuit was greatlyreduced, these reforms also optimized the algorithm and added its possibilities for practical application.As a research trial for this thesis, we designed a real circuit based on CPLD (Complex Programmable Logic Device) by VHDL (Very high speed integrated circuit Hardware Description L anguage) for the hardware algorithm for Euclidean distance transform with multilayer design method, called top-to-down. In order to examine the feasibility and practicality of this algorithm, we use the EDA implement "MAX + Plusl0.0" of Altera Company to execute the logic compiling, time analyzing and simulating for the designed circuit.