完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

恶意模型下计算欧几里德距离的协议

安全多方计算（MPC）是一个允许多个参与方在保持各自输入隐私的前提下联合计算一个函数。Yao和Goldreich等人（STOC’87）开创性的工作表明,存在陷门置换的前提下,任何一个函数都存在安全多方计算协议,并给出了安全多方计算的一个通用解决方案,但是该方案由于效率问题而不实用。因此,Goldreich同时指出需要针对特定问题提出特定的安全多方计算协议。提出了一个新的基于分布式EI Gamal加密的计算两个向量欧几里德距离的安全协议,并在混合模型下给出了协议的安全性证明。与原来的方案比较,该协议的计算和通信复杂度都较低,适用于计算和通信能力都有限的应用环境。     

基于差分矩因子的灰度图像矩快速算法

由于不变矩对图像的平移放大旋转的不敏感性,因此在图像处理、模式识别、场景匹配和计算机视觉等领域获得越来越广泛的应用．但是,求矩运算过程复杂,计算量大,使它的应用受到限制．快速求矩算法不少,但大多限于二值图像．文中提出一种新的适用于灰度图像的快速求矩算法．算法基于文中提出和证明的差分求和定理,即两个离散函数数组的乘积,等于将其中一个差分、另一个累进求和后的乘积．将矩因子作为一个函数数组,图像作为另一个函数数组,对矩因子数组实施多次差分,差分结果使得矩因子数组除边界1个或几个数组元素外,其余数组元素值皆为0．这样需对所有数组元素的乘积变为只对边界1个或几个数组元素的乘积．由于边界上不为0的数组元素值几乎都为1,这实际上就无需乘法计算．该算法原理简单,编程容易,求矩结果精确,适用于任意灰度图像．利用该算法,对任意大小和任意级别的灰度图像,无需任何乘法计算,且加法运算次数也大幅减少．和其它求矩算法相比,计算复杂性大大降低．     

2维Otsu自适应阈值的快速算法

Otsu自适应阈值法作为图像阈值分割的经典算法，在图像处理领域得到了广泛的应用，在其基础上发展起来的2维Otsu阈值法却因为计算时间长而制约了其应用。针对2维Otsu自适应阈值方法计算复杂度高的缺点，通过改变2维直方图上的区域划分，将2维阈值转换为1维阈值，从而提高了2维自适应阈值算法的计算速度。实验结果表明，该算法的计算时间远远小于原始2维Otsu算法，分割效果和原始算法基本一致。     

跳跃与环顾最优匹配的快速图像恢复算法

Best Neighborthood Marching(BNM)是目前对损坏图像进行修复并能产生高质量可接受图像的图像恢复算法，然而，BNM却具有计算复杂度的局限性，因而限制了其实现应用，文中从BNM中影响虎法复杂度的关键环节－为坏块寻找最优匹配的搜索路径出发，参照人寻找相似块时的快速智能方法，提出跳跃环顾BNM图像恢复算法（JLBNM）。同时,对于进行匹配的核心步骤，提出具有自适应阈值匹配标准的优化方法，有关的计算复杂度度量分析及模拟实验均证明JLBNM具有计算复杂度低，对损坏图像恢复质量高的特点。     

基于差分有序数组的图像匹配快速算法

本文提出了一种对模板匹配算法进行改进的快速算法。首先，对模板内所有像素进行排序并差分变换为函数F1（），将模板覆盖下的子图像函数f（x，y）累进求和变换为函数F2（），然后求取F1（）与F2（）乘积的最大值。由于模板存在大量灰度值相同的像素，经排序差分后F1（）中会有很多0和1，乘1和0的运算可以不做，从而消去了模板运算中的大量乘法和加法运算，同时在模板匹配移动过程中利用相邻窗口间的数据相关性，减少重复运算，和传统匹配算法相比，计算复杂度大大降低。     

Hausdorff距离和量子粒子群的二维图像匹配

提出了一种基于Hausdorff距离和量子粒子群算法的二维图像匹配算法。为了实现二维图像的搜索,首先利用Canny算子提取图像的边缘,再利用Hausdorff距离作为图像搜索的目标函数,然后引入了带量子行为的粒子群的优化算法来求解搜索所需的空间变化参数,实验结果表明,带量子行为的粒子群的优化算法（QPSO）能够迅速地在全局范围内找到最优解,因此应用于二维图像搜索是可行的。     

灰度图像质心快速算法

对矩因子x^py^q。做差分变换为函数Fl(),将图像函数f(x,y)做累进求和变换为函数F2()．用Fl()和F2()相乘求取质心．由于0阶和1阶矩因子中的P,q不大于1,经差分后的F1()除右端点外,其值都为1,乘1的运算当然可以不做,从而消去了乘法运算．对任意大小和任意级别的灰度图像,乘除法运算次数仅为3次,而加法运算次数也有降低．文中算法计算结果精确,其运算效率高于已有其他算法．     

基于围线扫描的快速完全欧氏距离变换算法

欧几里德距离变换（EDT）是为由黑白像素构成的二值图像中所有像素找到距离其最近的黑色像素,并计算它们之间的欧几里德距离,目前广泛地应用于图像分析和计算机视觉等领域.本文采用基于围线扫描的思想,提出了一个在二值图像中进行完全欧氏距离变换的算法.算法首先将二值图像中的像素进行分类,对那些本身既不是特征像素且其4-邻域内也没有特征像素的点作上标记,然后对这些标记的像素自内向外进行围线扫描,搜索与它最近的黑点并计算它们的欧氏距离.算法能够计算精确的欧氏距离.同时对算法的时间复杂度进行了简单的分析,并给出了程序实现中得到的一些实验数据,结果表明该算法运算速度快,时空需求在当前的硬件环境下令人满意,是一种有效的和有着巨大实际应用价值的距离变换算法.     

三维欧氏距离变换快速算法

为了提高三维距离变换在实际应用中的计算效率,提出一种三维快速距离变换算法.首先将三维图像降维为多张二维图像,为每张二维图像设置2个标记数组,并根据标记数组运用围线扫描方法依次计算出每一像素在二维图像上的距离变换;然后依据二维结果计算出所有像素在三维图像中的距离变换.实验结果表明,文中算法实现简单,比已有的边界剥离算法及基于Voronoi图的算法在时间和空间消耗上均有较大的提高,有更好的实用性.     

基于改进欧式距离的硬件木马检测

传统欧式距离判别方法用于硬件木马检测时,存在判别准确率较低的问题。为此,分析芯片运行时的侧信道功耗信息,根据木马模块触发产生额外功耗的特征,提出一种指数变换改进方案。加入可调参数,以增大硬件木马的可识别度。实验结果表明,与传统欧氏距离判别法相比,参数可调的欧氏距离改进方案可使判别性能提升29%,且木马检测准确率高达98%。     

A Fast Euclidean Algorithm for Gaussian Integers

A new version of the Euclidean algorithm is developed for computing the greatest common divisor of two Gaussian integers. It uses approximation to obtain a sequence of remainders of decreasing absolute values. The algorithm is compared with the new (1  +  i)-ary algorithm of Weilert and found to be somewhat faster if properly implemented.     

一种新的完全欧氏距离变换算法

论文提出了一种基于边界剥离的二维完全欧氏距离变换算法。该算法从物体目标的最外层边界开始,自外向内、逐层对物体目标区域进行边界跟踪、剥离。在跟踪过程中,根据当前边界像素点的已获得距离变换结果或为背景的邻域像素信息,计算其与最近背景像素间的欧氏距离,从而实现距离变换。和已有算法相比,文中算法具有简单快速、容易实现,得到的是完全欧氏距离的优点,在分离粘连物体的应用中,取得了良好分离效果。     

近似欧氏距离变换的一种并行算法

提出了一种基于超大规模集成电路(VLSI)硬件结构的新型距离变换并行处理算法。距离变换是一种基于二值图像的全局操作，在骨架抽取、形状匹配、目标重建、机器人避障等图像分析与模式识别算法中有着广泛的应用。欧氏距离是精确的L2范数距离，但是由于欧氏距离的非线性，不利于各种并行算法和加速算法的设计与实现，因此在应用中各种变形的加权距离作为欧氏距离的近似得到了实际推广。本文算法是有别于传统近似欧氏距离的并行计算方法，可应用于传统IC硬件或数字信号处理芯片(DSP)。理论分析和实验结果表明，该方法具有算法简单、快速、误差小等特点，可以更好地近似欧氏距离，并同时得到图像的Voronoi图，是一种实际可行的升级算法。     

基于边界跟踪的快速欧氏距离变换算法

提出了一种基于边界跟踪、剥离的快速二维欧氏距离变换算法.从目标区域的最外层边界开始,自外向内、逐层对目标区域进行边界跟踪、剥离,直至目标区域为空.每跟踪到一个边界像素点,即根据其邻域像素所传递的最短距离信息来计算与最近背景像素间的欧氏距离,并利用一个链表结构来完成对已经过距离变换的像素点的距离更新,以解决距离传递的路径可能改变的问题.实验结果表明,该算法能够得到准确的欧氏距离,并且算法时间不到3×3倒角近似欧氏距离变换算法的2倍,比基于桶排序的欧氏距离变换算法快几十至上千倍.     

基于欧氏距离变换的肺实质修补

在胸部CT图像的肺实质提取过程中,往往存在诸如过分割等问题,因此有必要对分割出的肺实质图像进行修补,论文提出了一种基于欧氏距离变换的肺实质修补算法.该算法是在初提取肺实质之后,利用欧氏距离变换将肺部边缘的血管和肺结节恢复,从而得到包含病灶区域在内的完整的肺实质.采用该算法对45个病人的胸部CT图像中缺失的肺实质进行了修补,结果显示该算法的正确率达90％以上,证明了该方法的可靠性和有效性.     

一种适于硬件实现的快速模乘算法

RSA算法是目前应用最广泛的一种公钥加密算法,随着人们对加密安全性和加密速度要求的提高,硬件实现加密算法成了密码学应用的一个趋势。模乘算法是模幂算法的核心,基于Montgomery算法,结合Booth2算法的思想,文章给出了一种改进的高效算法,并且通过FPGA实现。对该算法和参考文献中算法的性能进行了比较,可以看出这一改进算法在速度和面积上优于现有的算法。     

Constant-Time Algorithm for the Euclidean Distance Transform on Reconfigurable Meshes

The Euclidean distance transform (EDT) is an operation to convert a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. The EDT has many applications in computer vision and image processing. In this paper, we present a constant-time algorithm for computing the EDT of an N×N image on a reconfigurable mesh. Our algorithm has two variants. (i) If the image is initially given in an N×N mesh, one pixel per processor, our algorithm requires an N×N×N mesh for computing the EDT. (ii) If the image is given in an N×N² mesh, each row of the image in the first row of a separate N×N mesh, we can compute the EDT in the same N×N² mesh. The AT² bounds for these two variants are O(N⁴) and O(N³) respectively. The best previously known algorithm (Y. Pan and K. Li, Inform. Sci.120 (1999), 209–221) for this problem assumes input similar to the second variant of our algorithm and runs in constant-time on an N²×N² reconfigurable mesh with an AT² bound of O(N⁴). Hence both variants of our algorithm improve upon the processor complexity of the algorithm in Pan and Li (1999) by a factor of N and the second variant improves upon the AT² complexity by a factor of N.