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

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

基于围线追踪的完全欧氏距离变换算法

本文以吴立德等１９９６年中文提出了基于边过程的围线追踪算出发点，设计并实现了一个在二值图像中进行完全欧氏距离变换的算法，算法首先求出二值图像的围线，然后沿围线从近向远扩展计算欧氏距离，算法能够计算精确的欧氏距离，对算法的时间和空间需求进行了简要的分析，讨论了算法的一些有关性质，并给出了实现程序运行中得到的一些实验数据，结果表明算法在多数情况下能够运行快，占用内存少，有较好的自适应性，因此有较好的实     

三维欧氏距离变换的一种新方法

常见的三维距离变换算法大都是对城市街区、棋盘等二维近似欧氏距离变换算法的三维扩展,得到的依然是近似欧氏距离.提出一种新的三维欧氏距离变换算法,可以得到完全欧氏距离,时间复杂度为O(n3logn).将该算法应用于三维医学CT图像内部软组织的显示,取得了较好的效果.     

基于SIFT的图像盲取证方法

采用一种基于尺度不变特征变换的算法提取图像特征,使用乘积量化的近似最近邻搜索方法对子空间分别进行量化,运用非对称距离算法计算特征向量之间的欧氏距离,提出一种新的数字图像复制粘贴被动盲取证方法。实验结果表明,该方法能够准确地对复制区域经过预处理的伪造进行检测,减少内存的使用量和空间复杂度,缩短搜索时间。     

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

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

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

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

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

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

自适应的快速非局部图像去噪算法

文章对非局部均值（NL-Means) 图像去噪算法进行了改进,提出一种定量估计算法滤波参数最优值的方法,由噪声图像估计噪声方差,进而由噪声方差与图像方差估计滤波参数h。另外,根据局部区域加权欧氏距离的对称性,将算法中复杂度最高的两像素间距离计算由两次降为一次,从而在不损失性能的条件下使计算复杂度降低到原来的一半左右。在多个典型图像上的实验结果表明,提出的自适应非局部均值算法(ANL-Means)可达到近似最优性能,且处理时间只有标准NL-Means算法的一半左右。     

基于Bandelets域的自适应图像压缩

针对第二代Bandelets变换,提出一种新的图像压缩算法。在图像剖分子块时,依据父、子目标函数值的计算比较,优化四叉树剖分,并利用最小二乘法改进剖分区域的最优方向搜索,实现图像压缩,既保留图像丰富的边缘及纹理效果,又降低计算复杂度。实验结果表明,该算法相比JPEG2000的峰值信噪比可提高0.1 dB以上。     

半色调图像纹理特征提取方法

提出基于局部二值化模式和像素相关算子的半色调图像纹理特征提取方法,以实现误差分散类半色调图像的分类。该方法是将误差分散类图像先进行局部二值化模式变换,再以任一像素点为中心,取适当的距离提取八个方向的像素相关值作为图像的特征向量,最后将提取的特征通过BP神经网络进行分类。实验结果表明,提出的算法适用于二值图像的特征提取,能够降低局部二值模式的特征维数,提高时间效率和空间利用率;相对灰度共生矩阵算法提出的算法在计算复杂度、识别精度等性能方面都有所改善。     

Parallel computation of the Euclidean distance transform on a three-dimensional image array

In a two- or three-dimensional image array, the computation of Euclidean distance transform (EDT) is an important task. With the increasing application of 3D voxel images, it is useful to consider the distance transform of a 3D digital image array. Because the EDT computation is a global operation, it is prohibitively time consuming when performing the EDT for image processing. In order to provide the efficient transform computations, parallelism is employed. We first derive several important geometry relations and properties among parallel planes. We then, develop a parallel algorithm for the three-dimensional Euclidean distance transform (3D-EDT) on the EREW PRAM computation model. The time complexity of our parallel algorithm is O(log/sup 2/ N) for an N/spl times/N/spl times/N image array and this is currently the best known result. A generalized parallel algorithm for the 3D-EDT is also proposed. We implement the proposed algorithms sequentially, the performance of which exceeds the existing algorithms (proposed by Yamada, 1984). Finally, we develop the corresponding parallel programs on both the emulated EREW PRAM model computer and the IBM SP2 to verify the speed-up properties of the proposed algorithms.     

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

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

On Computing the Exact Euclidean Distance Transform on Rectangular and Hexagonal Grids

In this paper we prove an equivalence relation between the distance transform of a binary image, where the underlying distance is based on a positive definite quadratic form, and the erosion of its characteristic function by an elliptic poweroid structuring element. The algorithms devised by Shih and Mitchell [18] and Huang and Mitchell [7], for calculating the exact Euclidean distance transform (EDT) of a binary digital image manifested on a square grid, are particular cases of this result. The former algorithm uses erosion by a circular cone to calculate the EDT whilst the latter uses erosion by an elliptic paraboloid (which allows for pixel aspect ratio correction) to calculate the square of the EDT. Huang and Mitchell's algorithm [7] is arguably the better of the two because: (i) the structuring element can be decomposed into a sequence of dilations by 3 × 3 structuring elements (a similar decomposition is not possible for the circular cone) thus reducing the complexity of the erosion, and (ii) the algorithm only requires integer arithmetic (it produces squared distance). The algorithm is amenable to both hardware implementation using a pipeline architecture and efficient implementation on serial machines. Unfortunately the algorithm does not directly transpose to, nor has a corresponding analogue on, the hexagonal grid (the same is also true for Shih and Mitchell's algorithm [7]). In this paper, however, we show that if the hexagonal grid image is embedded in a rectangular grid then Huang and Mitchell's algorithm [7] can be applied, with aspect ratio correction, to obtain the exact EDT on the hexagonal grid.     

基于DCT子空间失真测度的快速矢量编码算法

在本文中，我们介绍了一种基于离散余弦变换子空间失真测度的恢复速失量编码算法。该算法利用ＤＣＴ子空间映射，将失真测度维数从１６降至４，从而使编码计算复杂度隆为１／４，并且结合部分失真算法进一步减少了编码 计算复杂度。     

一种适用于H.264的分数像素快速运动估计算法

新的视频标准H.264为了获得更精确的运动向量和更高的压缩比,引入了分数像素运动补偿技术,但同时也增加了运动补偿过程的复杂度.为了克服这一局限,充分利用搜索点失真度随着与全局最小点之间距离的增加而增大的特点,以及运动向量具有中心偏置的特性提出了一种新的快速分数像素运动估计算法.实验表明：该算法在保持图像质量和码率基本不变的情况下大大减少了搜索点的数目,提高了分数像素运动估计的速度,有效地减少了其复杂度.     

Turbo乘积码译码算法的优化和改进

Chase2算法是Turbo乘积码(TPC)软判决译码中常采用的算法之一。由于传统的Chase2算法中欧氏距离计算以及寻找竞争码字都需要大量的运算,因而在硬件上实现比较复杂。为此,在传统Chase2算法的基础上,采用相关度量等价替代欧氏距离的度量,简化寻找竞争码字的过程,以降低译码复杂度;调整竞争码字不存在时的软输出信息值,以提高编码增益。仿真结果表明：改进算法比传统的Chase算法译码速度更快,译码性能更好,非常适合硬件实现。      

基于轮廓跟踪的连通域标记算法优化

由于需要大量堆栈操作和反复搜索像素邻域,一次扫描算法往往效率不高.基于轮廓跟踪的连通域标记算法先跟踪目标的封闭轮廓,再线扫描轮廓内的像素,以减少像素邻域搜索及堆栈访问的次数,提高算法的效率.本文提出的基于轮廓跟踪的连通域标记算法,屏弃堆栈访问,并采用高效的轮廓跟踪算法,以提高算法的效率.本算法与其它连通域算法相比,具有效率更高、稳定性好等优点.     

Extraction of the Euclidean skeleton based on a connectivity criterion

The skeleton is essential for general shape representation. The commonly required properties of a skeletonization algorithm are that the extracted skeleton should be accurate; robust to noise, position and rotation; able to reconstruct the original object; and able to produce a connected skeleton in order to preserve its topological and hierarchical properties. However, the use of a discrete image presents a lot of problems that may influence the extraction of the skeleton. Moreover, most of the methods are memory-intensive and computationally intensive, and require a complex data structure.In this paper, we propose a fast, efficient and accurate skeletonization method for the extraction of a well-connected Euclidean skeleton based on a signed sequential Euclidean distance map. A connectivity criterion is proposed, which can be used to determine whether a given pixel is a skeleton point independently. The criterion is based on a set of point pairs along the object boundary, which are the nearest contour points to the pixel under consideration and its 8 neighbors. Our proposed method generates a connected Euclidean skeleton with a single pixel width without requiring a linking algorithm or iteration process. Experiments show that the runtime of our algorithm is faster than the distance transformation and is linearly proportional to the number of pixels of an image.