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

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

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

围线扫描欧氏距离变换算法是一种快速的完全欧氏距离变换算法,其时间复杂度达到最优,但需在围线区域进行全局搜索,计算时间并未优化。针对此问题,提出了一种基 于围线分层扫描的完全欧氏距离算法。该算法首先根据中心像素的围线性质对二值图像像素点进行重新分类,然后按照围线区域像素与中心像素的空间关系,对中心像素的围线区 域进行分层搜索,并给出了搜索的终止条件。该算法保持了最优的时间复杂度,可通过定量分析单个像素的计算时间来证明其计算时间已得到优化。实验结果表明,该算法能够得到 准确的欧氏距离图像,且运行速度快。     

线性四元树表示二值图像的围线追踪和Euler数的计算

本文将基于边过程的围线追踪算法推广应用于四元树表示的二值图像，给出了一个对线性四元树表示二值图像实现围线追踪的算法，算法利用输入的四分形编码确定四分形左上及右下角处象互的位置坐标，由此确定图像中的所有非零边过程，再进行基于边过程的围线追踪，算法求得围线的树结构，表达和图像的拓扑性质，利用围线的树结构给出了一个计算图像的Ｅｕｌｅｒ数的非常简便的方法。     

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

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

基于改进的等距离映射算法的人脸识别

针对等距离映射(Isomap)算法在处理扰动图像时拓扑结构不稳定的缺点,提出了一种改进算法。改进算法将图像欧氏距离(IMED)嵌入到等距离映射算法之中。首先引入坐标度量系数计算图像的坐标度量矩阵,通过线性变换将原始图像从欧氏距离(ED)空间转换到图像欧氏距离空间;然后计算变换空间中样本的欧氏距离矩阵,并在此基础上构建样本邻域图,得到近似测地距离矩阵;最后采用多维标度(MDS)分析算法构造样本的低维表示。对ORL和Yale人脸数据库降维并结合最近邻分类器进行实验,基于改进算法的识别率平均分别提高了5.57%和3.95%,表明与原算法相比,改进算法在人脸识别中对图像扰动具有较好的鲁棒性。     

利用数据场和欧氏距离的图像边缘提取

图像边缘是图像分析和识别的基础,图像边缘信息的准确性和完整性对后续图像分析和识别有重要影响。为实现图像边缘有效提取,提出一种利用数据场和图像欧氏距离的图像边缘提取方法。首先,该方法利用数据场理论构建图像数据场,实现图像灰度值特征空间到数据场势值空间的转换。然后,在对图像数据场的势值计算时引入图像欧氏距离,利用图像区域欧氏距离扩大像素差异,抑制微小细节和噪声,得到"背景"和"目标"相对分离的势值图。最后,用改进Canny算法对势值图进行边缘提取。实验表明,用本文方法可以有效提高边缘提取的准确性,减少伪边缘,抑制冗余细节和噪声。     

一种精确匹配的全景图自动拼接算法

本文提出一种全景图像自动拼接算法,能够实现特征点对的精确筛选和匹配,以及输入图像的自动排序和拼接。首先提取输入图像的尺度不变特征变换SIFT特征点,并采用k-d树搜索得到图像之间所有初始特征匹配对;利用欧氏距离比值和中值滤波器对初始特征点对进行筛选后,再应用随机抽样一致算法RANSAC得到图像间精确匹配的特征点对;计算出图像之间的单应性矩阵,在此基础上完成对输入图像的自动排序和配准,最终拼接合成全景图像。实验结果表明,该算法能获得比结合欧氏距离比值的RANSAC算法更高的配准精度,全景图拼接效果较好,具有良好的鲁棒性。     

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

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

基于欧氏距离图的图像边缘检测

图像边缘检测技术直接影响以目标识别为目的的后续图像处理操作,有效地提取出图像中所携带的目标信息是图像边缘检测的主要目的.为了实现目标轮廓的有效提取,提出一种基于欧氏距离图的图像边缘检测算法.该方法计算图像内像素点之间的欧氏距离,得到图像的距离图,距离图很好地描述了图中景物的外部轮廓;对距离图进行改进的Canny算子边缘检测,可以有效地得到图中物体的轮廓.与一般的边缘检测算法相比,本文算法能够抑制过于细小和琐碎的细节,并能够准确地提取目标的整体轮廓信息,为后续目标识别奠定了良好基础.     

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

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

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.     

改进的加权t-SNE算法及在故障诊断中的应用

对随机邻域嵌入算法(stochastic neighbor embedding, SNE)中的距离进行改进,提出一种基于Manhattan距离的加权t-SNE(Mwt-SNE)算法。使用受空间维数影响较小的Manhattan距离作为度量方式,使用k均值聚类算法将高维空间数据样本点距离分为三类,基于表格法进行权重参数寻优与加权,以加权相对Manhattan距离代替欧式绝对距离计算相似度条件概率,从而增大数据对象之间的区分度,提升降维效果,增强分类显著性。提出基于Mwt-SNE算法的在线故障诊断模型,使用核密度估计(KDE)确定控制限并进行在线监控。TE化工过程实验表明Mwt-SNE算法能有效降低误报率和漏报率,从而提高故障诊断稳定性和准确性。     

基于遗传算法的聚类分析

给出了一种基于遗传算法的聚类分析方法。采用二进制编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的欧氏距离的和来判断聚类划分的质量，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到便聚类划分效果最好的聚类中心。实验结果显示，该方法的聚类划分效果明显优于传统的K-均值方法。     

开放环境下未知材质的识别技术

针对开放环境下未知物体材质识别的问题,本文提出一种利用欧氏距离区分未知类别和已知类别的物体材质识别方法框架,在该框架下利用支持向量机对物体材质进行识别,分类效果显著。该方法利用距离度量中的欧氏距离与阈值进行比较,距离的均值小于阈值的物体判定为已知类别物体材质,并进行分类;距离大于阈值的物体判定为未知类别物体材质,并利用支持向量机算法进行重新学习识别。本文在慕尼黑工业大学的触觉数据集中的声音数据上进行实验,对比了5种距离度量方法,选择了欧氏距离;与开集稀疏表示分类方法对比,显示出本文提出的方法在声音数据集上具有一定的优势;通过实验选出了合理的阈值,并最终实现了开放环境下识别所有物体材质。实验验证了该框架可以很好地解决开放环境下触觉感知信息的物体材质识别问题。     

Computational surface flattening: a voxel-based approach

A voxel-based method for flattening a surface in 3D space into 2D while best preserving distances is presented. Triangulation or polyhedral approximation of the voxel data are not required. The problem is divided into two main parts: Voxel-based calculation of the minimal geodesic distances between points on the surface and finding a configuration of points in 2D that has Euclidean distances as close as possible to these distances. The method suggested combines an efficient voxel-based hybrid distance estimation method, that takes the continuity of the underlying surface into account, with classical multidimensional scaling (MDS) for finding the 2D point configuration. The proposed algorithm is efficient, simple, and can be applied to surfaces that are not functions. Experimental results are shown     

一种基于主动视觉的三维结构恢复和直接欧氏重建算法

利用三正交平移运动, 提出了一种三维结构恢复和直接欧氏重建新算法. 算法仅需利用主动视觉平台控制相机作一组三正交平移运动, 然后通过图像对应点和平移运动的距离就可以恢复平面结构信息和进行欧氏重建. 并且无需假定相机畸变因子为零. 算法计算过程中无需求解相机的内参数, 也无需进行分层重构, 它是一种直接的欧氏重建算法, 避免了传统算法中的相机标定、仿射重建等两大难题, 并且计算过程完全线性化, 简单实用. 最后用模拟实验和真实图像实验对算法进行验证, 实验结果表明了算法的有效性和准确性.     

A Multiscale Approach to Optimal Transport

In this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth‐mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart.     

基于多代表点近邻传播的大数据图像分割算法

基于多代表点近邻传播聚类算法,提出一种有效的大数据图像的快速分割算法。 该算法首先运用均值漂移算法将彩色图像分割成很多小的同质区域,然后计算每个区域中所有 像素的颜色向量平均值,并用区域数目代替原图像像素点数目,选用区域间的距离作为相似度 的测度指标,最后应用多代表点近邻传播聚类算法在区域相似度矩阵上进行二次聚类,得到最 终的图像分割结果。实验结果证明,提出的算法在大数据图像的分割中取得了较为满意的分割 效果,且分割效率较高。     

结肠癌患者诊断的基因标志物识别算法*

为了得到具有强分类信息的极少结肠癌特征基因,实现对结肠癌患者的准确识别,文中提出结肠癌患者诊断的基因标志物识别算法.首先提出基因密度和基因距离的概念,构造以基因密度和基因距离分别为横纵坐标的基因2D空间散列图,选择处于密度峰值点的基因构成优选基因子集,然后采用密度峰值K中心点(DP_K-medoids)算法对降维后的结肠数据集样本进行聚类分析.基因距离和样本距离分别采用欧氏距离、曼哈顿距离、切比雪夫距离和夹角余弦距离度量.实验表明,在夹角余弦距离下,文中算法可以选择到具有高准确率、高灵敏度、高特异度和高马修斯相关系数的规模较小的结肠癌基因子集.