A Hardware Design Of Edt Algorithm Applied To Binary Images

Distance transformation are widely used in the fields such as pattern recognition, morphology and artificial intelligence. Among the various distance definitions, the Euclidean distance transformation (EDT) has good accuracy for most applications. With the development of image processing technology and electronic technology, many researches are invested into the Euclidean distance transformation algorithms.This paper describes a hardware Euclidean distance transformation algorithm applied on the binary images. For the practicability, the principles of different EDT algorithms are analyzed and the calculation results are compared. Then a feasible algorithm is selected as the basis. In the paper, the computing speed is chosen as the key index. In the further design, the details of the algorithm and the architecture of the corresponding system are redesigned to improve the computing speed. All these ensure that the hardware EDT algorithm has better real-time performance.In the research, according to the characteristics of hardware algorithm, this paper selects an efficient software EDT algorithm as the basis and keeps the O(N2) time complexity. Then during the hardware algorithm design process, the distinctions of the EDT in the software platform and hardware platform are listed. Based on these distinctions, the algorithm is designed to be modularized so that the computing time and memory resource overhead are reduced. The circuit scale is also optimized. In this design, addition and shifting are used in place of multiplication. It makes the computing speed improved greatly. As a whole, in view of the hardware computing system, this paper also proposes the adjustment scheme to form a more efficient pipelined architecture eventually.In the research, the hardware EDT algorithm proposed in this paper has the following advantages:The computing speed is greatly improved so that the O(N2) time complexity of the corresponding software algorithm is now reduced to O(N). Obviously the hardware algorithm has better real-time performance. Then by modularization and some detail design, the cost of memory resources is decreased so that the space complexity is optimized. The adjustment scheme for the entire system architecture is proposed to form a more efficient pipelined architecture. It also makes the computing speed improved.In the end, the hardware algorithm is achieved as a two-order pipeline hardware computing system based on the Verilog HDL language and FPGA platform. The logic synthesis, timing simulation can be done by the EDA tools to verify the design functions. The computing performance and system resources are analyzed based on the corresponding reports.