局部几何与全局结构联合感知的三维形状分类方法

针对复杂结构的三维形状分析与识别问题,提出了新颖的图卷积分类方法,建立了局部几何与全局结构联合图卷积学习机制,有效提高了三维形状数据学习的鲁棒性与稳定性。首先,通过最远点采样与最近邻方法构造局部图,并建立动态卷积算子,有效提取局部几何特征;同时,基于特征域采样构造全局的特征谱图,通过卷积算子获得全局结构信息。进而,构建加权的联合图卷积学习网络模型,引入注意力机制,实现自适应的特征融合。最终,在联合优化目标函数约束下,有效提高特征学习的性能。实验结果表明,融合局部几何与全局结构的联合图卷积网络学习机制,有效提高了深度特征的表示能力及区分性,具有更为优秀的识别力和分类性能。提出的研究方法可应用于大规模三维场景识别、三维重建以及数据压缩,在机器人、产品数字化分析、智能导航、虚拟现实等领域具有着重要的工程意义与广泛的应用前景。     

Modeling and rendering of points with local geometry

We present a novel rendering primitive that combines the modeling brevity of points with the rasterization efficiency of polygons. The surface is represented by a sampled collection of Differential Points (DP), each with embedded curvature information that captures the local differential geometry in the vicinity of that point. This is a more general point representation that, for the cost of a few additional bytes, packs much more information per point than the traditional point-based models. This information is used to efficiently render the surface as a collection of local geometries. To use the hardware acceleration, the DPs are quantized into 256 different types and each sampled point is approximated by the closest quantized DP and is rendered as a normal-mapped rectangle. The advantages to this representation are: 1) The surface can be represented more sparsely compared to other point primitives, 2) it achieves a robust hardware accelerated per-pixel shading - even with no connectivity information, and 3) it offers a novel point-based simplification technique that factors in the complexity of the local geometry. The number of primitives being equal, DPs produce a much better quality of rendering than a pure splat-based approach. Visual appearances being similar, DPs are about two times faster and require about 75 percent less disk space in comparison to splatting primitives.     

一种改进的中轴骨架三维模型检索算法

针对三维模型检索算法性能较低的问题,提出了一种改进的中轴骨架三维模型检索算法。     

基于中轴表达的三维模型轮廓提取方法

三维网格模型的轮廓信息在网格检索、网格简化、网格重建中有着广泛应用。现有的轮廓提取方法较为复杂,需要分析和过滤网格模型的几何特征,计算量大且有时无法生成完整的轮廓信息。近年来,三维模型的中轴表达研究趋于成熟,在表达模型几何拓扑关系上有独特的优势。因此,提出了一种基于中轴表达的三维模型轮廓提取方法：首先提取三维模型的中轴表达信息,将中轴角点投影到三维模型表面;然后根据每个区域的拓扑关系选择适合的角点连接关系,将投影点连接形成模型区域轮廓;再针对投影过程中产生的误差进行分析和纠正;最后合并区域轮廓得到三维模型的完整轮廓。通过对多个模型数据库中代表性的三维网格模型进行实验和重建误差比较,该方法的平均重建质量较现有方法约有10%的提升,在重建质量和轮廓信息完整度方面优于现有方法。     

A local adaptation-based generation method of medial axis for efficient engineering analysis

Currently engineering analysis is regarded as an integrated part of design process and medial axis (MA) is often utilized. However, the generation of MA of complicated models is computation intensive since it is always generated from scratch even if a tiny modification is imposed. A novel local adaptation-based approach to generating the MA for efficient engineering analysis is proposed in this study. With this method, the MA of a resultant model constructed from two other models via a Boolean operation or parameter modification is generated by adapting the MAs of the operand models in a certain way, instead of regenerating the MA from scratch. First, several new properties of the MA which are the fundamental basis of the proposed method are investigated. Then, the boundaries that will vanish from or be added into the resultant model during the Boolean operation or parameter modification are found, and the region in which the MA segments (MASs) need to be regenerated is determined. Finally, the new MASs are generated for the region using an improved tracing method. The final MA of the resultant model is thus constructed by combining the newly generated MASs with the reserved MASs of the operated model(s). Some examples are given to illustrate the high computational efficiency of the proposed method for engineering analysis.     

An algorithm for the medial axis transform of 3D polyhedral solids

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes     

3D block-based medial axis transform and chessboard distance transform based on dominance

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N³, our parallel algorithm can be run in O(logN) time using N³ processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size.     

3D medial axis point approximation using nearest neighbors and the normal field

We present a novel method to approximate medial axis points given a set of points sampled from a surface and the normal vectors to the surface at those points. For each sample point, we find its maximal tangent ball containing no other sample points, by iteratively reducing its radius using nearest neighbor queries. We prove that the center of the ball constructed by our algorithm converges to a true medial axis point as the sampling density increases to infinity. We also propose a simple heuristic to handle noisy samples. By simple extensions, our method is applied to medial axis point simplification, local feature size estimation and feature-sensitive point decimation. Our algorithm is simple, easy to implement, and suitable for parallel computation using GPU because the iteration process for each sample point runs independently. Experimental results show that our method is efficient both in time and in space.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

Use of medial axis transforms for computing normals at boundary points

Medial axis transform (MAT) is well known for object representation. It is interesting to explore its use in different kinds of computations. In this paper an algorithm has been proposed for computation of normals at the boundaries of two-dimensional objects based on their MATs. In this technique, there is no requirement of linking boundary points during the computation compared to other existing techniques. The added advantage in the computation is that the computation can be restricted purely in the integer domain.     

基于局部特征点的三维模型变换域水印算法HHME2013-ID83

为进一步提高变换域水印的鲁棒性,解决多分辨率小波变换对三角形网格形状的限制,本文提出一种基于局部特征点的变换域算法。首先根据经度角和纬度角对模型分区,并求出局部特征点;其次由局部特征点的模长与非局部特征点模长的均值构成的比例组成二维矩阵,对二维矩阵进行离散小波变换,并修改小波系数中的各分辨率层的中高频系数以嵌入水印;最后通过逆向离散小波变换得到空域信号,修改三维模型局部特征点的模长以得到含水印的三维网格模型。实验结果表明,该算法具有很好的鲁棒性和不可见性,对模型的网格形状无严格要求,能够不受平移、旋转、均匀缩放和顶点重排序的影响,并能有效抵抗噪声、简化、剪切、细分、量化和联合攻击等一系列的常见攻击。     

Research on 3D medial axis transform via the saddle point programming method

The present paper investigates the 3D medial axis transform of objects bounded by freeform surfaces via the saddle point programming method, a mathematical programming approach used to identify the saddle points of a function. After exploring the local geometry and saddle point property of 3D medial axis transform, the mathematical programming method is employed to construct the saddle point programming models. Based on the optimality conditions that the optimal solutions should satisfy, a generic algorithm for computing various medial axis points is developed. In order to identify the junction points and localize the problem, the boundary and the skeletal curves are divided into skeletal segments, and it is proved to be efficient and accurate by numerical examples.     

A min-max medial axis transformation

Blum's medial axis transformation (MAT) of the set S of 1's in a binary picture can be defined by an iterative shrinking and reexpanding process which detects ``corners' on the contours of constant distance from S?, and thereby yields a ``skeleton' of S. For unsegmented (gray level) pictures, one can use an analogous definition, in which local MIN and MAX operations play the roles of shrinking and expanding, to compute a ``MMMAT value' at each point of the picture. The set of points having high values defines a good ``skeleton' for the set of high-gray level points in the given picture.     

局部特征点的3维模型变换域水印算法

目的 为进一步提高变换域水印的鲁棒性,解决多分辨率小波变换对三角形网格形状的限制,提出一种基于局部特征点的变换域水印算法。方法 首先根据经度角和纬度角对模型分区,并求出局部特征点;其次由局部特征点的模长与非局部特征点模长的均值构成的比值组成2维矩阵,对2维矩阵进行离散小波变换,并修改小波系数中的各分辨率层的中高频系数来嵌入水印;最后通过逆向离散小波变换得到空域信号,修改3维模型局部特征点的模长以得到含水印的3维网格模型。结果 本文方法能够不受平移、旋转、均匀缩放和顶点重排序的影响,并能有效抵抗噪声、简化、剪切、细分、量化和联合攻击等一系列的常见攻击。结论 实验结果表明,该算法具有很好的鲁棒性和不可见性,对模型的网格形状无严格要求。     

基于局部指纹曲面片的点云三维物体识别

提出一种新的基于局部描述符的点云物体识别算法。算法根据点云的位置信息提取出邻域以及曲率信息,进而得到形状索引信息。根据形状索引提取到特征点,在每个特征点根据样条拟合原理得到测地距离和矢量夹角分割曲面得到曲面片集。每个曲面片的等距测地线构成了曲面片指纹,通过矢量和半径的变化描述,可以把每个模型物体得到的曲面片集描述存入数据库。对于给定的一个物体,根据上面步骤同样得到其曲面片集描述,通过和数据库中模型物体曲面片集的比对,得到初始识别结果。对每对初始识别结果进行对应滤波后,通过最近点迭代方法得到最终的识别结果。最后通过具体的实验说明了算法的有效性和高效性。     

基于2个灭点和局部尺度的三维空间尺度估计

三维空间尺度估计是三维重建中的一个重要工作,现实世界中也存在一些基于单幅图像进行三维空间尺度估计的需求。通常情况下,尺度估计需先对相机进行标定。根据单目图像符合透视原理的特性,提出了一种基于2个灭点和局部尺度信息的方法对相机进行标定,从而得到单目图像物体中三维空间尺度信息的估计。首先,从单目图像中选择2组互相正交的平行线组,得到对应2个灭点的坐标;然后,利用灭点坐标和焦距信息得到世界坐标系和相机坐标系之间的旋转矩阵,再利用灭点的性质和已知局部尺度信息得到平移向量,完成单目相机的标定;最后,还原二维图像中像素点对应的三维世界坐标值,计算出图像中2个像素点在三维空间的尺度信息。实验结果表明,该方法能有效地对单幅图像中的建筑物体进行尺度估计。     

Anamorphic 3D geometry

An anamorphic image appears distorted from all but a few viewpoints. They have been studied by artists and architects since the early fifteenth century. Computer graphics opens the door to anamorphic 3D geometry. We are not bound by physical reality nor a static canvas. Here we describe a simple method for achieving anamorphoses of 3D objects by utilizing a variation of a simple projective map that is well-known in the computer graphics literature. The novelty of this work is the creation of anamorphic 3D digital models, resulting in a tool for artists and architects.