Fast exact shortest distance queries for massive point clouds

This paper describes a new efficient algorithm for the rapid computation of exact shortest distances between a point cloud and another object (e.g. triangulated, point-based, etc.) in three dimensions. It extends the work presented in Eriksson and Shellshear (2014) where only approximate distances were computed on a simplification of a massive point cloud. Here, the fast computation of the exact shortest distance is achieved by pruning large subsets of the point cloud known not to be closest to the other object. The approach works for massive point clouds even with a small amount of RAM and is able to provide real time performance. Given a standard PC with only 8GB of RAM, this resulted in real-time shortest distance computations of 15 frames per second for a point cloud having 1 billion points in three dimensions.     

云桌面应用研究概述

随着信息技术的发展,数量巨大的PC设备使得企业对于员工个人电脑的日常管理成为了一项复杂的工作,升级补丁、安全策略、日常的设备维护等往往需要企业投入大量的人力与物力。而随着工作地点的分散、移动设备开始应用于办公,传统的 PC 设备已不能完全适应企业的办公需求。近年来云计算概念开始兴起,云桌面这一新型办公设备形式也进入了人们的视野。作为虚拟化技术的延伸,云桌面依赖于服务器端计算,安全度高、管理方便,而且适用于移动设备。云桌面在国内外已经有了众多的应用案例,为企业的IT办公设备选择指明了一个新的方向。整理了云桌面的相关应用,并结合云桌面的技术特性,对云桌面的应用进行了分析。     

Surface processing methods for point sets using finite elements

We present a framework for processing point-based surfaces via partial differential equations (PDEs). Our framework efficiently and effectively brings well-known PDE-based processing techniques to the field of point-based surfaces. At the core of our method is a finite element discretization of PDEs on point surfaces. This discretization is based on the local assembly of PDE-specific mass and stiffness matrices, using a local point coupling computation. Point couplings are computed using a local tangent plane construction and a local Delaunay triangulation of point neighborhoods. The definition of tangent planes relies on moment-based computation with proven scaling and stability properties. Once local stiffness matrices are obtained, we are able to easily assemble global matrices and efficiently solve the corresponding linear systems by standard iterative solvers. We demonstrate our framework by several types of PDE-based surface processing applications, such as segmentation, texture synthesis, bump mapping, and geometric fairing.     

应用激光雷达与相机信息融合的障碍物识别

针对探测器在地外星体表面软着陆过程中的障碍物识别问题,提出了一种融合三维点云数据与灰度图像数据进行精确障碍物识别的方法。首先利用坐标转换将灰度图像与三维点云归一化到同一坐标系下,实现传感器数据的融合。然后采用改进K均值聚类算法对预处理后灰度图像进行图像分割,生成光学障碍图。最后利用开源库PCL(Point Cloud Library)对激光雷达生成的三维激光点云数据进行处理,采用随机采样一致性算法提取着陆区地形水平面,对去除水平面后的点云数据进行点云分割,分离出突起物、凹坑等障碍物,并通过激光雷达与相机转换坐标系,投影到像平面,生成最终障碍图。     

基于PCL库三维点云树枝重建

随着三维扫描技术的不断提高以及国内对于开源PCL(Point Cloud Library)库不断深入的研究,三维重建技术被学者们应用到诸多领域中。比如在数字城市、逆向工程等方面有了极速的发展,而对于数字城市的模拟中,实现树枝的重建是加强城市真实感最重要的部分。文中主要在图形用户界面应用程序开发框架Qt的基础上,通过利用PCL点云库实现对三维点云树枝的三维重建的方法。首先针对树枝数据采用体素化网格方法实现下采样,减少点云数量同时保持形状特征;利用Kd树存储点云实现空间划分以及搜索操作;其次通过最小二乘法平面拟合估计方法计算出点云的法向量;最后运用PCL中的贪婪投影三角化实现树枝点云的重建。结果显示,三角化重建能够较好的保留树枝的形态特征,可以为各个需树枝重建的场景中提供良好的基础。     

一种大规模地形模型的视相关简化算法

提出了一种基于点删除的视相关简化算法。首先依据视锥准则、背离面准则和屏幕投影误差对原始网格进行可见性预处理，再对预处理后的网格依据顶点重要度大小进行点删除简化。重要度以顶点到平均平面的距离表示，在计算过程中，采用了距离加权的办法，从而进一步加强了视相关简化效果。实验表明，算法具有较高的绘制速度，并且绘制帧速率基本独立于模型的复杂度。     

改进法线方向的点云实时分割提取平面方法研究

为了提高服务机器人在室内环境中目标物体抓取的效率,提出一种针对三维点云数据改进表面法线估计的方法。重点研究了如何提高使用三维点云数据实时性和准确性,这是机器人抓取过程的关键因素。使用消费级别的传感器kinectV2获取点云数据,提出使用积分图像降低滤波区域内像素的遍历消耗的时间,从而提高实时性;采用动态调整平滑区域的大小以及分配权重的方法平滑处理点云数据的噪声,提高法线估计精度。依据改进后的法线方向,利用区域生长算法对不同方向的法线进行分类,然后对点云数据实施分割提取平面。最后,采用提出的方法和点云库中的相关算法,进行了平面分割提取测试比较。结果表明,利用kinectV2获取的深度数据（1-5米）比目前点云库中的平面分割算法数据精度更高、实时性更强。     

Continuous global optimization in surface reconstruction from an oriented point cloud

We introduce a continuous global optimization method to the field of surface reconstruction from discrete noisy cloud of points with weak information on orientation. The proposed method uses an energy functional combining flux-based data-fit measures and a regularization term. A continuous convex relaxation scheme assures the global minima of the geometric surface functional. The reconstructed surface is implicitly represented by the binary segmentation of vertices of a 3D uniform grid and a triangulated surface can be obtained by extracting an appropriate isosurface. Unlike the discrete graph-cut solution, the continuous global optimization entails advantages like memory requirements, reduction of metrication errors for geometric quantities, and allowing globally optimal surface reconstruction at higher grid resolutions. We demonstrate the performance of the proposed method on several oriented point clouds captured by laser scanners. Experimental results confirm that our approach is robust to noise, large holes and non-uniform sampling density under the condition of very coarse orientation information.     

Hierarchical Optimization of Network Resource for Heterogeneous Service in Cloud Scenarios

With limited homogeneous and heterogeneous resources in a cloud computing system, it is not feasible to successively expand network infrastructure to adequately support the rapid growth in the cloud service. In this paper, an approach for optimal transmission of hierarchical network for heterogeneous service in Cloud Scenarios was presented. Initially, the theoretical optimal transmission model of a common network was transformed into the hierarchical network with the upper and lower optimization transmission model. Furthermore, the computation simplification and engineering transformation were presented for an approximation method at the low cost of computational complexity. In the final section, the average delay in the engineering method shows its influence on the capability of access for common nodes.     

Approximate medial axis as a Voronoi subcomplex

Medial axis as a compact representation of shapes has evolved as an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to approximate them. One line of research considers the point cloud representation of the boundary surface of a solid and then attempts to compute an approximate medial axis from this point sample. It is known that the Voronoi vertices converge to the medial axis for a curve in 2D as the sample density approaches infinity. Unfortunately, the same is not true in 3D. Recently, it is discovered that a subset of Voronoi vertices called poles converge to the medial axis in 3D. However, in practice, a continuous approximation as opposed to a discrete one is sought.Recently few algorithms have been proposed which use the Voronoi diagram and its derivatives to compute this continuous approximation. These algorithms are scale or density dependent. Most of them do not have convergence guarantees, and one of them computes it indirectly from the power diagram of the poles. Recently, we proposed a new algorithm that approximates the medial axis straight from the Voronoi diagram in a scale and density independent manner with convergence guarantees. In this paper, we present several experimental results with this algorithm that support our theoretical claims and also show its effectiveness on practical data sets.     

基于属性的BGN型密文解密外包方案

云计算的安全问题是制约其发展的关键瓶颈,其中对云计算结果的访问控制是当前研究的一个热点。在经典的类同态BGN方案基础上,结合CP-ABE（Ciphertext-Policy Attribute-Based Encryption）型密文解密外包设计,构造了基于属性的BGN型密文解密外包方案,部分密文的解密被外包到云上进行,减小了用户的存储开销与计算开销,并且只有用户属性满足访问策略时,才会得到正确的解密结果。与现有的基于属性的外包方案相比,新方案能对密文进行任意次加法同态和一次乘法同态操作。最后,分析了方案的安全性。所提方案在子群判定问题假设下达到语义安全,在随机预言机模型下满足属性安全。     

基于点重要性判断的点云简化

为了有效保持散乱点云的显著几何特征,提高点云简化的精度和效率,提出一种点重要性判断点云简化方法.首先,计算点云中点的重要性,并根据重要性提取特征点;然后,采用八叉树算法对非特征点进行简化,从而保留点云的主要细节特征,实现点云简化处理;最后,通过对公共点云和文物点云数据模型的简化实验来验证该点云简化方法.结果表明,该点重要性判断点云简化方法可以在有效保持点云细节几何特征的同时,实现点云的有效简化,是一种快速、高精度的点云简化方法.     

Point cloud simplification for the boundary preservation based on extracted four features

This paper proposes a simplification algorithm based on four feature parameters, aiming at solving the problem that the edge features cannot be retained due to the incompletely extracted sharp features during point cloud simplification. Firstly, K neighborhood searching is carried out for point cloud, and K neighborhood points are quickly found by a dynamic grid method. Then, four features including: the curvature of the point, the average of the normal angle of a point from a neighborhood point, the average distance between the point and the neighborhood point and the distance between the point and the center of gravity of the neighborhood point, are calculated according to the K neighborhood of the data point. The four parameters are used to define the feature discrimination parameters and feature thresholds, to compare the size and extract the feature points; finally, the non-feature points are reduced twice by the method of the bounding box, and the reduced point cloud and feature points are spliced to achieve the purpose of simplification. The experimental results show that the distance between the point and the center of gravity of the neighborhood has a great influence on the simplified model boundary, which effectively guarantees the accuracy of the simplified model.     

A new approach to z-level contour machining of triangulated surface models using fillet endmills

Precision z-level contour machining is important for various computer-aided manufacturing (CAM) applications such as pocket machining and high-speed machining (HSM). This paper presents a new z-level contour tool-path generation algorithm for NC machining of triangulated surface models. Traditional approaches of z-level machining rely on the creation of accurate CL (cutter location) surfaces by surface offsetting or high-density z-map generation, which is computationally expensive and memory demanding. In contrast, this paper presents a novel approach to the generation of CL data directly from the section polygon of a triangulated surface model. For each polygon vertex of the contour, the offset direction is determined by the normal to the edge, while the offset distance is not fixed but is determined from the cutter shape and the part surface. An interference-free tool-path computation algorithm using fillet endmills is developed. Since there is no need to create a complete CL surface or high-density z-map grids, this proposed method is highly efficient and more flexible, and can be directly applied to triangulated surfaces either tessellated from CAD models, or reconstructed from 3D scanned data for reverse engineering (RE) applications.     

点云重构三角网格的生长型神经气算法

为克服点云噪声、不均匀分布和复杂拓扑结构对三角网格重构的限制,改进了生长型神经气重构算法.以样本在网格局部投影作为神经元插入判据,自适应调节网格增长速度,保持几何变换与拓扑变换的协调.利用非流形边检测机制删除冗余连接,保持网格的拓扑有效性.网络学习过程中动态更新三角片结构,且在孔洞修复阶段扩大近邻查找范围,连接近邻节点中的边界点,直到网格收敛,最终得到正确的欧拉示性数.算例表明,改进的算法对带噪声点云具有鲁棒性,可根据非均匀点云的分布自动调整网格密度,且能重构具有复杂拓扑结构的曲面.重构的三角网格对曲面逼近精度较高,网格出度均匀,三角形近似等边.     

一种无记忆点云迭代简化算法

针对目前点云迭代简化算法在简化过程中需要保持原始模型信息而占用较大内存的问题,提出了一种无记忆点云迭代简化算法,简化过程中不需要记录原始模型相关几何信息。该算法使用体积优化和距离优化计算点对收缩后的最优点位置并对点对进行排序。实验表明,该算法可以在内存占用较小的情况下得到误差较小的简化模型。     

Cloud data integrity checking with an identity-based auditing mechanism from RSA

Cloud data auditing is extremely essential for securing cloud storage since it enables cloud users to verify the integrity of their outsourced data efficiently. The computation overheads on both the cloud server and the verifier can be significantly reduced by making use of data auditing because there is no necessity to retrieve the entire file but rather just use a spot checking technique. A number of cloud data auditing schemes have been proposed recently, but a majority of the proposals are based on Public Key Infrastructure (PKI). There are some drawbacks in these protocols: (1) It is mandatory to verify the validity of public key certificates before using any public key, which makes the verifier incur expensive computation cost. (2) Complex certificate management makes the whole protocol inefficient. To address the key management issues in cloud data auditing, in this paper, we propose ID-CDIC, an identity-based cloud data integrity checking protocol which can eliminate the complex certificate management in traditional cloud data integrity checking protocols. The proposed concrete construction from RSA signature can support variable-sized file blocks and public auditing. In addition, we provide a formal security model for ID-CDIC and prove the security of our construction under the RSA assumption with large public exponents in the random oracle model. We demonstrate the performance of our proposal by developing a prototype of the protocol. Implementation results show that the proposed ID-CDIC protocol is very practical and adoptable in real life.     

基本初等函数的保密云计算服务协议

目前云计算已经成为解决很多问题的一个有力平台,同时也带来了大量的安全隐患。其中,关于基本初等函数的保密计算是所有云计算的基础和核心。 提出了所有基本初等函数的保密云计算服务协议,其基本思想是将原始数据做变换后,把计算复杂部分发给云平台,通过云计算将结果反馈给接受服务方,从而保密地计算相应函数。通过广泛接受的模拟范例证明了协议的安全性。协议中接受计算服务方可用很少的计算资源解决复杂的计算问题,保证了较低的计算复杂度和通信复杂度,因此提出的协议是有效可行的,可以成为云保密计算中的基础子协议。     

基于EM-ICP的三维人脸简化点云并行配准算法

提出了一种基于离散曲率估计和kd-tree简化人脸点云的并行EM-ICP配准算法.首先建立人脸点云的三维空间kd-tree,并结合离散高斯曲率对点云进行了保留几何特征的简化;然后基于CUDA对EM-ICP算法进行并行加速,对简化的人脸点云进行配准.该算法能够避免局部配准等缺陷,同时EM-ICP算法并行保证了配准工作的高效.实验证实了本文算法的健壮性和稳定性.