【作者】 吴松；

【导师】 曾培峰；

【作者基本信息】 东华大学 ， 控制理论与控制工程， 2004， 硕士

【摘要】 距离转换，实际上就是计算实体间的距离，它在图像处理、模式识别、机器人以及形态学等研究领域有重要的应用。其中，欧几里德距离转定义了空间两点间的直线距离，它是一种最常见的距离转换方式，在相关领域中，尤其在图像处理中，它的应用十分广泛。随着数字电路技术和图像处理技术的飞速发展，人们对欧几里德距离转换的相关研究也逐渐成熟起来。 本文详细阐述了一种基于二值图像的欧几里德距离转换算法的硬件实现原理。此外，还介绍了现有的各种欧几里德距离转换算法的实现方法及性能。针对欧几里德距离转换算法的实用性，本文在吸取前人研究成果的基础上，分析了不同算法的实现原理和计算性能，对计算性能最接近实际应用要求的算法，在实现方案上做了相应的改进，提高算法实现电路计算速度和减小其电路规模，从而使基于硬件实现的欧几里德距离转换算法更具有实用性。 首先，根据实际应用的需要，本文将基于软件实现的欧几里德距离转换算法改为基于硬件实现，并保持其计算时间o(n~2)不变。其次，在面向硬件的设计方案中，本文引入了“内置”(in-place)算法——将电路计算过程中产生的中间数据和最终计算结果用同一个存储器保存，以便减少电路中存储器的使用数量，从而达到优化电路规模的目的。同时，根据算法的特点，在硬件实现时，我们用体积较小且计算速度较快的加法器和比较器来代替乘法器的功能，用以提高电路的计算速度。最后，根据硬件算法的实现原理，本文采用stp-by-step的设计方案，选择相关硬件，实现了一种基于二维图像的欧几里德距离转换算法电路。 相比之下，本文所实现的基于硬件的欧几里德转换算法有以下优点： 其一，在计算速度方面有很大提高，使其计算速度从o(n~3)提高到o(n~2)，从而使算法具有实用性。 其二，通过“内置”算法和复杂原件替代等方案将电路的尺寸大大减小，进一步优化了该算法的性能。 最后，作为本次论文的一个重要环节，在欧几里德距离转换算法的理论设计实现后，本文还设计了算法实现的具体硬件电路。借助于高速集成电路硬件描述下语言VHDL(、殆ryhighspeedinte盯atedcireuitHardwareDeseriptionLan罗age)，我们采用由顶向下(t叩一t。一down)的方法，设计了一个基于复杂可编程逻辑器件CpLD(Co哪lex progammable Logie Deviee)的基本电路，用以验证基于硬件的欧几里德距离转换算法的各项性能。然后，选用Altera公司的EDA开发平台MAX+Phisn对该电路系统进行逻辑综合、时序分析和仿真验证。更多还原

【Abstract】 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.更多还原