一种基于散乱点云的边界提取算法

点云边界是曲面的重要特征之一,边界线的快速准确提取对于提高曲面重构的效率和质量具有重要意义。首先,采用基于kd-tree搜索的方法建立点云空间拓补关系,进行K邻域快速搜索,以采样点及其K邻域作为局部型面参考依据拟合微切平面,将其向微切平面投影;其次,在微切平面上建立局部坐标系,并对投影点进行参数化,根据邻域点集在采样点处的场力大小之和可以表示点集的平均作用来识别点云的边界特征点;最后,从提高边界线连续性的角度,利用NURBS曲线插值方法连接边界线。实验结果表明,该算法可以快速、有效地提取出点云的边界特征点,并得到C2连续的边界线,满足曲面重构的要求。     

尖锐特征诱导的点云自动分片算法

点云模型的分片技术是数字几何处理领域的基础技术之一.提出一种尖锐特征诱导的点云模型自动分片算法.算法首先计算点云模型的局部微分属性,并以此来识别模型上的尖锐特征点;然后采用改进的折线生长算法生成并完善特征折线,并基于特征折线采用三次B样条曲线来逼近的尖锐特征点;最后采用区域生长方法将点云模型分割成多个几何特征单一、边界整齐的点云数据面片.实验表明,本文算法运行稳定,可以准确地分割点云模型.该算法可用于点云模型的形状匹配、纹理映射、CAD建模、以及逆向工程等应用中.     

基于优化DRG的三维人体点云骨架提取方法

针对离散Reeb图（Discrete Reeb Graph,DRG）描述人体骨架时分支部位骨架线偏离中轴的问题,采用了能量函数最小化的方法对DRG曲线进行优化。将人体模型的DRG曲线作为初始骨架,定义其能量函数,在点云模型的距离场梯度的作用下,迭代地调整偏离中轴目标段的曲线位置使其逐渐逼近中轴,能量函数最小时得到优化的骨架。将该算法应用于同一模特四个不同姿势和四个不同模特同一姿势的人体点云模型,并与基于拉普拉斯算子的点云收缩的骨架提取方法进行了比较。结果表明,该算法能够很好地适应各种不同姿势和体型,模型分叉部位的特征得到更加完善的描述,得到的骨架曲线更接近模型的中轴。     

基于保特征无参数投影的快速几何重建

为了使现有的无参数化投影算法拥有更好的保特征能力,提出一种保特征的基于无参数投影的点模型几何重建算法.首先,提出一个结合联合双边滤波器的局部优化投影算子,并利用点集的空间信息和几何特征信息,有效地保持了几何模型的特征;进一步,使用八叉树剖分技术对算法进行加速,为处理大规模点云提供了支撑;此外,还给出了自适应局部支撑的计算方法.实验结果表明,文中算法比无参数化投影算法保特征、速度快.     

基于自适应椭圆距离的点云分区精简算法

利用传统点云精简算法进行散乱点云简化会导致点云模型部分细节特征的丢失或模糊以及影响非平面区域的光顺性。针对这些问题,提出基于自适应椭圆距离的点云分区精简算法。首先,通过对邻域点集进行微切平面与局部曲面的拟合,计算出各点的法矢及曲率等;其次,利用所得几何特征信息,提取点云边界特征以及完成点云平面区域与非平面区域的划分;最后,采用改进后的精简算法对不同区域进行简化。实验结果表明,该算法不但能够快速完成符合要求精简率的数据简化,还能保护点云模型的细节特征以及保证模型非平面部分的光顺性。经过软件分析得出,精简后模型与原始模型的距离误差的标准偏差为0.015 mm。     

基于SIFT相似性度量的图像缩放

针对传统图像缩放算法存在的图像内容破坏与失真等问题,提出一种结合接缝雕刻和标准缩放的图像缩放算法。利用接缝雕刻算法对原始图像进行尺寸调整,分别从原始图像和缩放图像上提取尺度不变特征变换(SIFT)特征,并对2幅图像的SIFT特征进行匹配计算,得到两者的相似性距离。当原始图像与缩放图像之间的相似性距离达到某阈值时,即在图像重要目标或内容将要被破坏之前,停止使用接缝雕刻算法,采用标准缩放算法进行整体尺寸的调整操作。实验结果表明,该算法不仅可以有效避免图像内容的破坏与失真,而且可以较好地保护图像局部结构和全局视觉效果。     

一种改进的散乱点云边界特征点提取算法

提出一种新的散乱点云边界特征点提取算法。根据点云数据小邻域内点用最小二乘法拟合建立微切平面,并将这些数据点向其微切平面投影,利用点集中每个点的场力大小之和可以体现点集平均作用的理论来分析投影面上点集的几何分布特性,据此检测边界特征点。利用双向最近点搜索算法对提取出来的特征点进行排序并自动生成边界曲线。实验结果证明该算法能够快速、准确、有效地提取点云的边界。     

基于Z曲线和八叉树的高效Hausdorff距离计算方法

为提高计算点云模型之间Hausdorff距离(HD距离)的效率,提出基于Z曲线和八叉树的Hausdorff距离计算方法.首先利用Z曲线和八叉树实现点云模型预处理;然后在八叉树结构中定义了2类邻居(邻居点和邻居节点),并提出基于八叉树的局部搜索,以某一个叶子节点作为搜索的起点,递归地搜索其邻居直到根节点;最后结合模型预处理和局部搜索,给出了算法的实现细节.针对三维高斯随机数据和点云模型进行大量实验,并与经典方法进行对比,结果验证了文中方法的高效性.     

基于特征点检测的三维模型最佳视点选择

针对三维模型最佳视点选择问题,提出了一种基表面特征点检测的视点选择算法。首先引入一种基于局部平均形心距离差的顶点显著性度量方法,认为三维网格模型表面某顶点的显著性是由该顶点与形心之间距离和该顶点邻域内的顶点与形心之间距离的平均差值来刻画,而不是该点所在位置的弯曲程度所决定;然后根据顶点的显著性大小进行三维模型表面特征点检测;最后针对视点球体上的每个候选视点分析该视点下可见特征点的几何分布和显著度大小计算视点质量,提取出最佳视点。实验结果验证了基于三维模型特征点的视点选择方法的有效性,在能够选择出质量较优的视点的同时保证算法的效率。     

一种高效的二进制点云局部特征描述算法

针对现有点云局部特征描述算法时效性和紧凑型不能满足实际应用需求的问题,提出一种二进制多层切片距离特征描述算法(B-MSD)。首先在特征点处建立了一种稳健的局部参考坐标系;然后设计了两种多层切片和子区域划分方式并计算平均距离,以提取点云局部三维形状特征;最后通过量化的方法将各子区域计算的平均距离转化为二进制码串,串联所有码串生成最终的二进制描述子。在多个公开点云数据集上与几个经典描述子进行仿真对比,结果表明,在鉴别力更强的基础上,上述算法的紧凑性、计算效率和匹配速度方面综合表现更好。3D目标检测和点云配准应用实验也验证了上述算法的有效性。     

基于动态几何技术的平面几何资源库检索

在几何资源库中使用传统的方法检索相似的几何题,效果并不理想。对于基于动态几何技术的平面几何资源库,提出使用几何特征量进行相似性检索的方法。几何特征量量化了几何命题中的各几何元素,可以由动态几何作图指令序列提取,该方法能较好地检索相似的几何命题。     

Settling the bound on the rectilinear link radius of a simple rectilinear polygon

We improve the best known bound on the rectilinear link radius of a simple rectilinear polygon with respect to its rectilinear link diameter. The new bound is tight and is compatible with the known bound on the (regular) link radius of a (regular) simple polygon with respect to its (regular) link diameter. The previous bound on the rectilinear link radius of a simple rectilinear polygon was proven by Nilsson and Schuierer in 1991.     

Some notes on digital triangles

This note discusses some simple properties of digital triangles, whose vertices are lattice points and whose side lengths are measured using city block distance. Many of the familiar theorems of geometry break down in this situation.     

画法几何新解

从几何学的角度重新认识画法几何,结合计算化需求,梳理画法几何的理论体系。 首先,以新的视角,分析画法几何教材在表述上的一些问题;其次,揭示了投影、2D/3D 对应 和尺规作图以及轴测图、阴影与透视等理论的本质;并讨论上述理论的计算化问题,给出了画 法几何在理论与应用方面进一步发展的设想。     

计算机二维绘图系统的射影几何表征

文章给出了一种在传统的计算机二维绘图系统增加射影几何方法的途径。该方法基于位于以视点为中心的单位球表面上的点与图像面上的点之间的投影变换。简要介绍了射影几何基础以及用它来处理视图的基本方法,用实例初步演示了该系统的某些优点和准三维功能。     

An optimal algorithm for the boundary of a cell in a union of rays

In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal (n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.This work was partly supported by CEE ESPRIT Project P-940, by the Ecole Normale Supérieure, Paris, and by NSF Grant ECS-84-10902.This work was done in part while this author was visiting the Ecole Normale Supérieure, Paris, France.     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

Theorems about quadrilaterals and conics

We study quadrilaterals inscribed and circumscribed about conics and prove interesting theorems. Theorems are discovered by experimenting with dynamical geometry software. The Poncelet theorem for quadrilaterals is proved by elementary means together with Poncelet's grid property.     

Affine shape representation from motion through reference points

This paper shows how an affine representation of spatial configuration is obtained from a pair of projection views. Calibration of cameras and knowledge of the camera's motion are not necessary; however, some preselected reference points and their correspondences are needed. Projective and affine geometry invariants are trickily manipulated to do the affine reconstruction. The method is thus geometrically constructive. When it is compared with the solution proposed in 1989 by J.J. Koenderink and A.J. Van Doorn (Affine Structure from Motion, Technical Report, Utrect University), the method provides a viewpoint-independent affine representation under parallel projections. Further, we investigate the central-projection case in which, with three additional special reference points, the same affine reconstruction can be done. We also discuss some important applications of this viewpoint independence of shape representation.     

Self-Calibration of a Moving Camera from Point Correspondences and Fundamental Matrices

We address the problem of estimating three-dimensional motion, and structure from motion with an uncalibrated moving camera. We show that point correspondences between three images, and the fundamental matrices computed from these point correspondences, are sufficient to recover the internal orientation of the camera (its calibration), the motion parameters, and to compute coherent perspective projection matrices which enable us to reconstruct 3-D structure up to a similarity. In contrast with other methods, no calibration object with a known 3-D shape is needed, and no limitations are put upon the unknown motions to be performed or the parameters to be recovered, as long as they define a projective camera.The theory of the method, which is based on the constraint that the observed points are part of a static scene, thus allowing us to link the intrinsic parameters and the fundamental matrix via the absolute conic, is first detailed. Several algorithms are then presented, and their performances compared by means of extensive simulations and illustrated by several experiments with real images.