Empirical study of variation in lidar point density over different land covers

Point density in airborne lidar surveys is one of the key parameters that influence not only the accuracy of generated DSM/DEM but also processing and costs. Point density variations occur (independently of keeping constant flight parameters) throughout the survey depending on the topography, the land cover, and the laser scanning mechanism. In this article, variations in point density across different land covers are analysed with an airborne oscillating mirror laser scanner. A wide group of samples from the different land covers is taken from single flight strips over level ground in order to minimize the effect of topography. The influence of the oscillating mirror laser scanner system is also minimized considering points along the central swath area. Mean values for each land cover are established regarding ground point density and first pulse returns. Significant differences in both raw points as well as on-the-ground points are registered, mainly due to the presence of features over the ground and the degree of opacity thereof. Regarding ground points, the relative differences between the two software packages used are 5% approximately. Significant point density differences can be found among the six analysed land covers. Furthermore, extrapolated pulse rate increments are presented to fulfil lidar specifications that neglect land cover as an input parameter to satisfy ground point density values, namely in non-overlapping areas.     

Out-of-core selection and editing of huge point clouds

In this paper we present an out-of-core editing system for point clouds, which allows selecting and modifying arbitrary parts of a huge point cloud interactively. We can use the selections to segment the point cloud, to delete points, or to render a preview of the model without the points in the selections. Furthermore, we allow for inserting points into an already existing point cloud. All operations are conducted on a rendering optimized data structure that uses the raw point cloud from a laser scanner, and no additionally created points are needed for an efficient level-of-detail (LOD) representation using this data structure. We also propose an algorithm to alleviate the artifacts when rendering a point cloud with large discrepancies in density in different areas by estimating point sizes heuristically. These estimated point sizes can be used to mimic a closed surface on the raw point cloud, also when the point cloud is composed of several raw laser scans.     

Outlier detection for scanned point clouds using majority voting

When scanning an object using a 3D laser scanner, the collected scanned point cloud is usually contaminated by numerous measurement outliers. These outliers can be sparse outliers, isolated or non-isolated outlier clusters. The non-isolated outlier clusters pose a great challenge to the development of an automatic outlier detection method since such outliers are attached to the scanned data points from the object surface and difficult to be distinguished from these valid surface measurement points. This paper presents an effective outlier detection method based on the principle of majority voting. The method is able to detect non-isolated outlier clusters as well as the other types of outliers in a scanned point cloud. The key component is a majority voting scheme that can cut the connection between non-isolated outlier clusters and the scanned surface so that non-isolated outliers become isolated. An expandable boundary criterion is also proposed to remove isolated outliers and preserve valid point clusters more reliably than a simple cluster size threshold. The effectiveness of the proposed method has been validated by comparing with several existing methods using a variety of scanned point clouds.     

Constructing the generalized local Voronoi diagram from laser rangescanner data

We consider the problem of building local free space representation by a circular-base robot, operating in an unknown bounded planar environment populated by obstacles of arbitrary shape. In the unknown environment, the robot depends on its sensors; in our case, this is the laser range scanner. A new structure is represented, termed the generalized local Voronoi diagram (GLVD), constructed directly from sensory data, obtained from an observation of the local environment, that is from the visible region, GLVD is obtained by deleting some edges from the ordinary Voronoi diagram, which is generated by the measured scanned points from the visible region. Crucial for the acquisition of the GLVD is the clusterization of the scanned points. Clusterization means grouping of the scanned points into distinct clusters, each having a specific property, e.g., for a particular point in the cluster, the nearest neighboring point should not lie further than a prescribed distance away. The relevant part of GLVD, the portion of GLVD which is in accordance with the generalized Voronoi diagram of the environment, is determined. Eventual differences between these two structures are discussed and experimental results are presented. With the superposition of several GLVDs we show that this structure can be used to construct a global map of the environment, for which the position and the orientation of the robot is needed     

Comparative study of different digitization techniques and their accuracy

The various manufacturers of digitization systems speak of the effectiveness and accuracy of their tools under optimal conditions, but actual experimentation with simple or complex objects and different materials yields results that on occasions refute the effectiveness of those systems. In order to help choose a digitization system on the basis of its accuracy and the quality of the distribution of points and triangular meshes, in the field of reverse engineering, we compared five digitization techniques (three versions of the laser scanner, a fringe projection version and an X-ray version): (1) an ordered point cloud obtained with a laser incorporated in a CMM, (2) a disordered point cloud obtained with a manual laser the position of which is determined with a Krypton Camera, (3) an Exascan manual laser with targets, (4) an ordered point cloud obtained by high precision Computerized Tomography (CT) and (5) an Atos fringe projection scanner with targets. Each of the three calibrated pieces (a sphere, a cylinder and a gauge block) was measured five times by the five digitization systems to confirm the accuracy of the measurement. A comparison was also made of the meshes generated by the five software packages (Focus-Inspection, Metris, VxScan, Mimics and Atos) of the five digitization systems for the three calibrated pieces and two more complex pieces (a bone and an automobile window winder pulley) to determine meshing quality. Finally, all the pieces were meshed by triangulation in the Catia V5 DSE (Digitized Shape Editor) module in order to test the quality of the points distribution.     

A novel method for 3D reconstruction: Division and merging of overlapping B-spline surfaces

B-spline surfaces, extracted from scanned sensor data, are usually required to represent objects in inspection, surveying technology, metrology and reverse engineering tasks. In order to express a large object with a satisfactory accuracy, multiple scans, which generally lead to overlapping patches, are always needed due to, inter-alia, practical limitations and accuracy of measurements, uncertainties in measurement devices, calibration problems as well as skills of the experimenter. In this paper, we propose an action sequence consisting of division and merging. While the former divides a B-spline surface into many patches with corresponding scanned data, the latter merges the scanned data and its overlapping B-spline surface patch. Firstly, all possible overlapping cases of two B-spline surfaces are enumerated and analyzed from a view of the locations of the projection points of four corners of one surface in the interior of its overlapping surface. Next, the general division and merging methods are developed to deal with all overlapping cases, and a simulated example is used to illustrate aforementioned detailed procedures. In the sequel, two scans obtained from a three-dimensional laser scanner are simulated to express a large house with B-spline surfaces. The simulation results show the efficiency and efficacy of the proposed method. In this whole process, storage space of data points is not increased with new obtained overlapping scans, and none of the overlapping points are discarded which increases the representation accuracy. We believe the proposed method has a number of potential applications in the representation and expression of large objects with three-dimensional laser scanner data.     

High-Speed Multisensor Method of Measurement,Control and 3D Analysis of Complex Object Shapes in Production Environment

In this research, methods and algorithms of calibration of optical schemes and elements of a triangulation laser system were analyzed. Recommendations for precision enhancement of an optical system are further used in improving parameters of a laser and reverse engineering they are also implemented in engineering of a high-speed linear laser 3D scanner.     

Registration of surfaces minimizing error propagation for a one-shot multi-slit hand-held scanner

We propose an algorithm for the on-line automatic registration of multiple 3D surfaces acquired in a sequence by a new hand-held laser scanner. The laser emitter is coupled with an optical lens that spreads the light forming 19 parallel slits that are projected to the scene and acquired with subpixel accuracy by a camera. Splines are used to interpolate the acquired profiles to increase the sample of points and Delaunay triangulation is used to obtain the normal vectors at every point. A point-to-plane pair-wise registration method is proposed to align the surfaces in pairs while they are acquired, conforming paths and eventually cycles that are minimized once detected. The algorithm is specially designed for on-line applications and can be classified as a closing-the-loop technique, where there are not that many competing methods, though it has been compared to the literature. Experiments providing qualitative and quantitative evaluation are shown by means of synthetic and real data and we demonstrated the reliability of our technique.     

Development of a low-cost active 3D triangulation laser scanner for indoor navigation of miniature mobile robots

For miniaturized mobile robots that aim at exploring unknown environments, no-contact 3D sensing of basic geometrical features of the surrounding environment is one of the most important capabilities for survival and the mission. In this paper, a low-cost active 3D triangulation laser scanner for indoor navigation of miniature mobile robots is presented. It is implemented by moving both a camera and a laser diode together on the robot’s movable part. The movable part is actuated by a servo motor through a gear train to achieve ±90° scanning view angle. The software module includes image processing and data post-processing. 3D world coordinates are calculated from 2D image coordinates based on the triangulation principle. With a 3D laser scanning method, navigation algorithms for obstacle avoidance and gateway passing are proposed. Finally, experiments are conducted to validate performance of the scanner and to test the efficiency of the navigation algorithms.     

Capacity-Constrained Delaunay Triangulation for point distributions

Sample point distributions possessing blue noise spectral characteristics play a central role in computer graphics, but are notoriously difficult to generate. We describe an algorithm to very efficiently generate these distributions. The core idea behind our method is to compute a Capacity-Constrained Delaunay Triangulation (CCDT), namely, given a simple polygon P in the plane, and the desired number of points n, compute a Delaunay triangulation of the interior of P with n Steiner points, whose triangles have areas which are as uniform as possible. This is computed iteratively by alternating update of the point geometry and triangulation connectivity. The vertex set of the CCDT is shown to have good blue noise characteristics, comparable in quality to those of state-of-the-art methods, achieved at a fraction of the runtime. Our CCDT method may be applied also to an arbitrary density function to produce non-uniform point distributions. These may be used to half-tone grayscale images.     

Direct generation of extended STL file from unorganized point data

An extended STL file format is presented in this paper. Differing with existing solutions, it proposes a new format to produce and store triangles. The format uses a cluster unit composed of several triangles. The main advantages of the format are that it contains both geometry and topological information and has improved storage capability. Direct generation of the extended STL from the scanned data has a great advantage in that it can reduce the time and error in modeling process. In order to obtain the format from unorganized point cloud, a new triangulation algorithm was introduced. The algorithm is based on reconstructing the relative Delaunay triangulation of the sample points on the surface. Other advantages of the extended STL format were also presented in this paper.     

Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。     

基于QT的机载三维激光扫描仪软件系统设计

随着测绘技术的发展,利用机载三维激光扫描仪获取点云数据,从点云数据中提取模型信息成为现代测绘技术的一种发展趋势. 点云数据处理的相关应用也越来越多,点云数据的处理软件参差不齐,需求和功能也各不相同. 针对上述问题,在基于QT编程平台下,利用PCL开发机载三维激光扫描仪点云数据处理软件,集中处理点云数据. 该系统由点云数据读写、三维显示、点云滤波、网格重构、点拾取、点云分割及NARF关键点提取等功能模块组成. 各模块采用面向对象的思想设计,功能易于扩展,以完成进一步的测绘工作. 实践表明,该系统具有良好的工程实用价值,可以快速完成机载三维激光扫描仪的数据处理工作.     

Adaptivity of conditional random field based outdoor point cloud classification

In this paper we present how adaptable learned models of graphical models are and how they can be used for classification tasks of 3D laser point clouds with different distributions and density. In order to model the contextual information we use a pair-wise conditional random field and an adaptive graph down-sampling method based on voxel grids. As feature we apply the rotation invariant histogram-of-oriented-residuals operator to describe the local point cloud distribution. We validate the approach with data collected from different laser range finders with varying point cloud distribution and density. Our experiments imply, that conditional random field models learned from one dataset can be applied to another dataset without a significant loss of precision.     

SkelTre

Terrestrial laser scanners capture 3D geometry of real world objects as a point cloud. This paper reports on a new algorithm developed for the skeletonization of a laser scanner point cloud. The skeletonization algorithm proposed in this paper consists of three steps: (i) extraction of a graph from an octree organization, (ii) reduction of the graph to a skeleton, and (iii) embedding of the skeleton into the point cloud. For these three steps, only one input parameter is required. The results are validated on laser scanner point clouds representing 2 classes of objects; first on botanic trees as a special application and secondly on popular arbitrary objects. The presented skeleton found its first application in obtaining botanic tree parameters like length and diameter of branches and is presented here in a new, generalized version. Its definition as Reeb Graph, proofs the usefulness of the skeleton for applications like shape analysis. In this paper we show that the resulting skeleton contains the Reeb Graph and investigate the practically relevant parameters: centeredness and topological correctness. The robustness of this skeletonization method against undersampling, varying point density and systematic errors of the point cloud is demonstrated on real data examples.     

基于离散曲率的点云光顺算法

通过对三维激光扫描仪扫描测量数据的误差来源进行分析,设计了一种基于离散曲率的点云光顺处理的快速算法,该算法以曲率特征为索引,能够快速判别点云数据的特征点,对非特征点采用[w]邻域内[X,Y]两个方向拟合三次B样条曲线做光顺处理。最后通过实例证明了所提方法的有效性。     

Delaunay三角剖分在离群点检测中的应用

在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。     

基于凸壳技术的Delaunay三角网生成算法

该文提出了一种针对散乱点集的快速构建Delaunay的算法。该算法首先对散乱点按有向角进行排序,以排序后的点顺序为基础,利用凸壳特性快速将散乱点联结成三角网,最后利用拓扑结构快速将其优化为Delaunay三角网。在联网过程中,充分利用有序点子集的凸壳特性,避免了所有的交点测试,从而保证了对散乱点集生成Delaunay三角网的效率。     

An adaptive normal estimation method for scanned point clouds with sharp features

Normal estimation is an essential task for scanned point clouds in various CAD/CAM applications. Many existing methods are unable to reliably estimate normals for points around sharp features since the neighborhood employed for the normal estimation would enclose points belonging to different surface patches across the sharp feature. To address this challenging issue, a robust normal estimation method is developed in order to effectively establish a proper neighborhood for each point in the scanned point cloud. In particular, for a point near sharp features, an anisotropic neighborhood is formed to only enclose neighboring points located on the same surface patch as the point. Neighboring points on the other surface patches are discarded. The developed method has been demonstrated to be robust towards noise and outliers in the scanned point cloud and capable of dealing with sparse point clouds. Some parameters are involved in the developed method. An automatic procedure is devised to adaptively evaluate the values of these parameters according to the varying local geometry. Numerous case studies using both synthetic and measured point cloud data have been carried out to compare the reliability and robustness of the proposed method against various existing methods.     

具有聚类功能的边界检测技术的研究

为快速有效地检测聚类的边界点,提出了一种新的基于三角剖分的聚类边界检测算法DTBOUND。该算法通过计算三角剖分图中每个数据点的变异系数将数据集分解成内部点和外部点两部分,然后从每一个未分类的内部点开始进行深度优先遍历,将相连的内部点以及和内部点相连的外部点作为一个聚类;最后从得到的聚类中提取边界点。该算法只有一个参数（变异系数阈值β）,实验结果表明该算法可以快速、有效地识别任意形状、不同大小和不同密度的聚类和聚类的边界点。