黎曼流形框架上半监督判别分析

针对传统黎曼流形上判别分析算法仅考虑了带标签数据统计信息,忽略了无标签数据的问题,基于图正则化思想,提出一个新颖的基于黎曼流形框架上半监督判别分析算法,并将其应用于视觉分类任务中.该算法将非奇异协方差矩阵表示为黎曼流形上的点,引入JBLD(Jensen-Bregman LogDet divergence)度量黎曼流形上点与点之间相似性测度.首先将数据点映射到黎曼切空间中,获得数据向量化表示;其次采用有标签数据和无标签数据构建近邻图刻画黎曼切空间局部几何结构,使其作为正则化项添加到费舍尔测地线判别分析目标函数中;最后最小化目标函数获取最优变换矩阵,并在变换黎曼流形中进行分类.在3个视觉分类数据集上实验结果表明,文中算法在分类精度上获得了相当大的提升.     

黎曼流形上非线性凸规划最优性条件的研究

利用黎曼流形上Lipschitz函数的Penot广义方向导数和Clarke广义梯度,得到了黎曼流形上凸函数的判别,并得到了黎曼流形上凸规划极小点的充分条件,给出了黎曼流形上的等式约束优化问题、不等式约束优化问题及带有等式和不等式约束的优化问题的Lagrange定理、Lagrange充分条件、Kuhn-Tucker定理及极小点充分条件。     

基链分治算法与Voronoi区的面积计算定理研究

基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时,在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法.     

基于推广流形学习的高分辨遥感影像目标分类

针对传统的流形学习算法不能对位于黎曼流形上的协方差描述子进行有效降维这一问题，本文提出一种推广的流形学习算法，即基于Log-Euclidean黎曼核的自适应半监督正交局部保持投影（Log-Euclidean Riemannian kernel-based adaptive semi-supervised orthogonal locality preserving projection，LRK-ASOLPP），并将其成功用于高分辨率遥感影像目标分类问题.首先，提取图像每个像素点处的几何结构特征，计算图像特征的协方差描述子；其次，通过采用Log-Euclidean黎曼核将协方差描述子投影到再生核Hilbert空间；然后，基于流形学习理论，建立黎曼流形上半监督正交局部保持投影算法模型，利用交替迭代更新算法对目标函数进行优化求解，同时获得相似性权矩阵和低维投影矩阵；最后，利用求得的低维投影矩阵计算测试样本的低维投影，并用K—近邻、支持向量机（Support victor machine，SVM）等分类器对其进行分类.三个高分辨率遥感影像数据集上的实验结果说明了该算法的有效性与可行性.     

粗糙域Voronoi图离散生成算法研究

Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A‘算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A’算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A’算法估价函数权值与粗糙域粗糙特性正相关,并以此获得r算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。     

基于Voronoi图的定性路径推理

动态空间知识的表示与推理是定性空间推理研究的重要内容.基于Voronoi图及其动态变化,提出运动路径定性表示与推理方法.先根据Voronoi图空间邻近关系定义Voronoi图生成子空间关系,进一步定义定性位置及概念邻域,并应用概念相邻的定性位置序列给出定性路径表示.再由动态Voronoi图的边集变化和给出的概念邻域中定性位置间最短路径的启发式算法,设计并实现具有观察者角度的定性路径推理算法.最后,实验分析并验证该方法的有效性.     

黎曼核局部线性编码

最近的研究表明:在许多计算机视觉任务中,将对称正定矩阵表示为黎曼流形上的点能够获得更好的识别性能.然而,已有大多数算法仅由切空间局部逼近黎曼流形,不能有效地刻画样本分布.受核方法的启发,提出了一种新的黎曼核局部线性编码方法,并成功地应用于视觉分类问题.首先,借助于最近所提出的黎曼核,把对称正定矩阵映射到再生核希尔伯特空间中,通过局部线性编码理论建立稀疏编码和黎曼字典学习数学模型;其次,结合凸优化方法,给出了黎曼核局部线性编码的字典学习算法;最后,构造一个迭代更新算法优化目标函数,并且利用最近邻分类器完成测试样本的鉴别.在3个视觉分类数据集上的实验结果表明,该算法在分类精度上获得了相当大的提升.     

自由曲面环切刀位规划

提出一种快速求解测地线的算法。以此算法为基础，将Voronoi图区域划分思想推广到二维黎曼流形。采用递归方法解决了包含孤岛的自由曲面区域划分，实现了数控加工环切轨迹规划计算，并通过实例验证了该算法的正确性。     

关于k(1≤k＜n)阶Voronoi图生成算法的研究

k( 1≤k 相似文献   

二维限定Voronoi网格剖分细化算法

给出了限定点、限定线在Voronoi网格中存在的充要条件,提出了二维限定Voronoi网格细化算法,通过设置初始检测带,然后细分检测带来实现限定Voronoi网格的剖分;同时证明了该算法对于任意平面线段图输入限定条件的收敛性.对于生成的限定Voronoi网格,给出了尺寸控制和质量控制算法,并对其时间复杂度进行了分析.最后通过实例验证了文中算法的有效性.     

分区加权Voronoi图的性质及其面积计算

分区加权Voronoi图是Voronoi图和加权Voronoi图的推广,可以用来模拟移动通信中基站发射天线分扇区以不同功率向周围发射时所覆盖区域的形状。首先,给出了分区加权Voronoi图的性质、定理及相关证明;其次,分析了分区加权Voronoi图中的各种区域,并给出了一种计算相应区域面积的算法;最后,利用分区加权Voronoi图模拟石家庄市部分城区中的基站建设情况,并对模拟产生的重复覆盖、服务区和盲区面积进行了计算。     

A parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub‐Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable. After constructing the sub‐Voronoi diagrams, we extracted the boundary points of the four sides of each sub‐group and used to construct boundary site Voronoi diagrams. Finally, the sub‐Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright © 2013 John Wiley & Sons, Ltd.     

3D hyperbolic Voronoi diagrams

Voronoi diagrams have useful applications in various fields and are one of the most fundamental concepts in computational geometry. Although Voronoi diagrams in the plane have been studied extensively, using different notions of sites and metrics, little is known for other geometric spaces. In this paper, we are interested in the Voronoi diagram of a set of sites in the 3D hyperbolic upper half-space. We first present some introductory results in 3D hyperbolic upper half-space and then give an incremental algorithm to construct Voronoi diagram. Finally, we consider five models of 3D hyperbolic manifolds that are equivalent under isometries. By these isometries we can transform the Voronoi diagram of each model to others.     

关于一般图形Voronoi图的离散构造法的研究

生成元为任意图形的一般图形Vomnoi图，由于其生成元的任意性，使得构造一般图形Voronoi图的算法均比较复杂。本文给出了在生成元边界上选取母点，利用点为生成元的Voronoi图的离散画法进行构造，从而得到一般图形Voronoi图的离散构造法。与其它算法相比，该算法的实现与生成元的形状无关，无需复杂计算，无需考虑误差控制，因而更加实用，效率也更高。实验结果表明，该算法简单，具有较高的理论价值和应用价值。     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

平面点集二阶Voronoi图的性质及算法

本文叙述作者新近发现的平面点集二阶Voronoi图的一些性质，并依据这些性质设计了构造二阶Voronoi图的一种算法，算法的时间复杂性为O（nlogn)，优于J－D Boissonna t和M Yvinec所著Algorithmic Geometry一书中提出的算法。     

MapReduce模型下Voronoi图栅格生成算法

针对"海量"点组成的平面点集Voronoi图栅格生成算法的效率问题,对其进行易并行性抽象,提出了一种MapReduce模型下基于欧氏距离的Voronoi图栅格生成算法,该算法采用三个MapReduce Job来实现。在第一个MapReduce Job中,将栅格按照隶属代码进行归属分类。在第二个MapReduce Job中,将新数据按照其对应的行号进行归类。在第三个MapReduce Job中,并行生成全局有序的Voronoi图部分文件,并连接各个部分文件,生成最终的Voronoi图。在多个不同大小数据集上的实验结果表明,这种MapReduce模型下的算法部署在Hadoop集群上运行具有较好的加速比和扩展性。     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。