基于连接点的3D多角弧匹配

为了满足实际应用的要求，快速地进行多角弧匹配是必要的，因此，提出了一种快速的3D多角弧表示和匹配的方法。该方法是在分析多角弧几何形状基础上，引入连接点的概念，同时，通过在连接点处建立局部直角坐标系来得到每一连接点处的球面坐标。并用连接点的球面坐标集表示多角弧，因这一表示在旋转和平移变换下是不变的，所以可取该球面坐标集作为多角弧匹配的特征集，用该特征集可保持多角弧的几何属性和拓扑结构。这样3D多角弧匹配就降为1D数值串匹配，从而使使匹配变得简单快速。其测量函数为对应连接点间的均方差。实验结果表明，该匹配算法效果良好，并且对于数值污染具有健壮性。     

基于连接点的二维多角弧匹配

多角弧匹配问题的关键是，其既能反映多角弧的几何性质，又能反映多角弧拓扑结构的特征选取．在分析了多角弧几何形状的基础上，引入了连接点的概念，并用连接点集表示多角弧，这一表示在旋转和平移变换下是不变的。进一步取该连接点集作为匹配的特征集，给出了特征集之间匹配的算法．该算法是将连接点间的距离积分作为测量函数，使二维多角弧的匹配由连接点的匹配来决定．给出的模拟试验结果表明，该算法效果良好，并且对于数值污染具有健壮性。     

Matching sets of 3D line segments with application to polygonal arcmatching

In this paper, we consider two sets of corresponding 3D line segments of equal length. We derive a closed-form solution for the coordinate transform (rotation and translation) that gives the best match between the two sets; best in the sense of a least-squares distance measure between the sets. We use these results as the basis to construct efficient algorithms for solving other problems in computer vision. Specifically, we address the problem of matching polygonal arcs, that is, the problem of finding a match between a short arc and a piece of long arc     

利用几何代数进行线段模型匹配和运动估计

首先探讨了Clifford代数（几何代数）在计算机视觉中的应用,并得到了2D与3D旋转的统一表达公式,进而探讨了该公式在直线模型匹配和运动估计中的应用;在改进2D多角弧匹配算法的基础上,提出了一个同时进行线段模型的匹配和运动估计的算法。该算法通过最小化模型线段与被检测线段间的距离（距离函数定义为对应点间欧氏距离的积分）而求得的最佳运动估计中的旋转,可由一个矩阵的奇异值分解来表示,从而为首次同时解决这两个问题,进行了初步尝,且该算法不受维数限制。最后的模拟实验结果表明,该算法效果良好。     

Digital curves in 3D space and a linear-time length estimationalgorithm

We consider simple digital curves in a 3D orthogonal grid as special polyhedrally bounded sets. These digital curves model digitized curves or arcs in three-dimensional Euclidean space. The length of such a simple digital curve is defined to be the length of the minimum-length polygonal curve fully contained and complete in the tube of this digital curve. So far, no algorithm was known for the calculation of such a shortest polygonal curve. The paper provides an iterative algorithmic solution for approximating the minimum-length polygon of a given simple digital space-curve. The theoretical foundations of this algorithm are presented as well as experimental results     

Conflating two polygonal lines

A basic technique in comparing and detecting changes in geographical spatial data from satellite images consists of identifying linear features or edges in the image and then matching those features. A chain of connected linear features which form a polygonal line is used as the basic unit for matching two images. We develop a distance measure between two polygonal lines and an efficient algorithm for conflating or optimally matching two polygonal lines based on this distance measure. We show that some of the alternative approaches used in the literature, including Hausdorff's distance, fail to satisfy the basic requirements of a distance measure for image conflation.     

Polygonal approximation of 2-D shapes through boundary merging

In this paper we present a shape approximation method which yields accurate and unique polygonal approximations. The approach first looks for arcs with two or three runs along the shape boundary whose arc-to-chord deviations are not only the smallest in their local areas but also smaller than a tolerance value. These arcs are then replaced by their respective chords. This process goes on iteratively until no arc can be reduced for the given tolerance.     

Near-Linear Time Approximation Algorithms for Curve Simplification

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P’ whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P’ while ensuring that the error between P’ and P is below a certain threshold. We consider two different error measures: Hausdorff and Frechet. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ε > 0, compute a simplified polygonal curve P’ whose error is less than ε and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in ℝ² in the case of the Hausdorff error measure under the uniform distance metric and arbitrary curves in any dimension for the Frechet error measure under L_p metrics. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.     

三维复杂实体表面生成方法研究

该文提出了生成三维复杂实体表面的一种新方法。该方法由以下过程组成：由分布在折面上的一维数据(点或直线段)，通过映射得到平面上相应的一维数据；再经二维剖面编辑得到二维剖面数据(弧段、曲线和多边形)；通过逆映射得到折面上相应的数据(弧段、曲线和多边形)，即得到三维剖面数据；最后从三维剖面上的弧段、曲线和多边形重建实体表面。     

A Normalization Method of Moment Invariants for 3D Objects on Different Manifolds

3D objects can be stored in computer of different describing ways, such as point set, polyline, polygonal surface and Euclidean distance map. Moment invariants of different orders may have the different magnitude. A method for normalizing moments of 3D objects is proposed, which can set the values of moments of different orders roughly in the same range and be applied to different 3D data formats universally. Then accurate computation of moments for several objects is presented and experiments show that this kind of normalization is very useful for moment invariants in 3D objects analysis and recognition.     

Visual saliency guided normal enhancement technique for 3D shape depiction

Visual saliency can effectively guide the viewer's visual attention to salient regions of a 3D shape. Incorporating the visual saliency measure of a polygonal mesh into the normal enhancement operation, a novel saliency guided shading scheme for shape depiction is developed in this paper. Due to the visual saliency measure of the 3D shape, our approach will adjust the illumination and shading to enhance the geometric salient features of the underlying model by dynamically perturbing the surface normals. The experimental results demonstrate that our non-photorealistic shading scheme can enhance the depiction of the underlying shape and the visual perception of its salient features for expressive rendering. Compared with previous normal enhancement techniques, our approach can effectively convey surface details to improve shape depiction without impairing the desired appearance.     

Supporting Focus and Context Awareness in 3D Modelling Tasks Using Multi‐Layered Displays

Most 3D modelling software have been developed for conventional 2D displays, and as such, lack support for true depth perception. This contributes to making polygonal 3D modelling tasks challenging, particularly when models are complex and consist of a large number of overlapping components (e.g. vertices, edges) and objects (i.e. parts). Research has shown that users of 3D modelling software often encounter a range of difficulties, which collectively can be defined as focus and context awareness problems. These include maintaining position and orientation awarenesses, as well as recognizing distance between individual components and objects in 3D spaces. In this paper, we present five visualization and interaction techniques we have developed for multi‐layered displays, to better support focus and context awareness in 3D modelling tasks. The results of a user study we conducted shows that three of these five techniques improve users' 3D modelling task performance.     

Out-of-core real-time haptic interaction on very large models

In this paper we address the problem of fast inclusion tests and distance calculation in very large models, an important issue in the context of environments involving haptic interaction or collision detection. Unfortunately, existing haptic rendering or collision detection toolkits cannot handle polygonal models obtained from 3D digitized point clouds unless the models are simplified up to a few thousand polygons, which leads to an important lack of detail for the scanned pieces. We propose a data structure that is able to manage very large polygonal models (over 25M polygons), and we explain how this can be used in order to compute the inclusion of a point into the solid surface very efficiently, performing several thousand point-in-solid tests per second. Our method uses a data structure called EBP-Octree (Extended Bounding-Planes Octree), which is a very tight hierarchy of convex bounding volumes. Based on a spatial decomposition of the model using an octree, at each node it defines a bounding volume using a subset of the planes of the portion of the polygonal model contained at that node. We use the EBP-Octree in a haptic interaction environment, where distance tests and the orientation of collided triangles must be accurate and fast. We also demonstrate that the proposed algorithm largely meets the interactive query rate demanded by a haptic interaction (1 kHz), despite being executed in a single CPU thread on a commonly available computer.     

On-the-fly Curve-skeleton Computation for 3D Shapes

The curve-skeleton of a 3D object is an abstract geometrical and topological representation of its 3D shape. It maps the spatial relation of geometrically meaningful parts to a graph structure. Each arc of this graph represents a part of the object with roughly constant diameter or thickness, and approximates its centerline. This makes the curve-skeleton suitable to describe and handle articulated objects such as characters for animation. We present an algorithm to extract such a skeleton on-the-fly, both from point clouds and polygonal meshes. The algorithm is based on a deformable model evolution that captures the object's volumetric shape. The deformable model involves multiple competing fronts which evolve inside the object in a coarse-to-fine manner. We first track these fronts' centers, and then merge and filter the resulting arcs to obtain a curve-skeleton of the object. The process inherits the robustness of the reconstruction technique, being able to cope with noisy input, intricate geometry and complex topology. It creates a natural segmentation of the object and computes a center curve for each segment while maintaining a full correspondence between the skeleton and the boundary of the object.     

Efficient Simplification Methods for Generating High Quality LODs of 3D Meshes

Two simplification algorithms are proposed for automatic decimation of polygonal models,and for generating their LODs.Each algorithm orders vertices according to their priority values and then removes them iteratively.For setting the priority value of each vertex,exploiting normal field of its one-ring neighborhood,we introduce a new measure of geometric fidelity that reflects well the local geometric features of the vertex.After a vertex is selected,using other measures of geometric distortion that are ...     

一种基于可视图的机器人避障路径规划

该文首先提出用Minkowski和的工具将多边形机器人的路径规划问题转化为点机器人的情况,然后基于移动机器人的安全考虑,提出了一种改进的可视图法。该方法用尽可能远离障碍物的路径表示弧,先确定可能的路径点作为节点,然后考虑可能路径,建立结点间的弧,并用Dijkstra算法求出图中的最短路径。最后通过仿真研究表明,用文章提出的方法规划的路径可以达到或接近最优路径。     

一种半监督三维模型语义自动标注方法

三维模型语义自动标注的目标是自动给出最适合描述模型的标注词集合,是基于文本的三维模型检索的重要环节。语义鸿沟的存在使得相似匹配技术得到的标注效果有待提高。为了在用户提供的有限模型数量和对应的标注词信息下,在自动标注过程中利用大量的未标注样本改善三维模型的标注性能,提出了一种半监督测度学习方法完成三维模型语义自动标注。该方法首先使用基于图的半监督学习方法扩展已标注模型集合,并给出扩展集合中语义标签表征模型的语义置信度,使用改进的相关成分分析方法学习马氏距离度量,依据学习到的距离和语义置信度形成多语义标注策略。在PSB（Princeton Shape Benchmark）数据集上的测试表明,该方法利用了大量未标注样本参与标注过程,取得了比较好的标注效果。