Smooth Transitions Between Parallel Coordinates and Scatter Plots via Polycurve Star Plots

This paper presents new techniques for seamlessly transitioning between parallel coordinate plots, star plots, and scatter plots. The star plot serves as a mediator visualization between parallel coordinate plots and scatter plots since it uses lines to represent data items as parallel coordinates do and can arrange axes orthogonally as used for scatter plots. The design of the transitions also motivated a new variant of the star plot, the polycurve star plot, that uses curved lines instead of straight ones and has advantages both in terms of space utilization and the detection of clusters. Furthermore, we developed a geometrically motivated method to embed scatter points from a scatter plot into star plots and parallel coordinate plots to track the transition of structural information such as clusters and correlations between the different plot types. The integration of our techniques into an interactive analysis tool for exploring multivariate data demonstrates the advantages and utility of our approach over a multi-view approach for scatter plots and parallel coordinate plots, which we confirmed in a user study and concrete usage scenarios.     

Sunspot Plots: Model-based Structure Enhancement for Dense Scatter Plots

Scatter plots are a powerful and well-established technique for visualizing the relationships between two variables as a collection of discrete points. However, especially when dealing with large and dense data, scatter plots often exhibit problems such as overplotting, making the data interpretation arduous. Density plots are able to overcome these limitations in highly populated regions, but fail to provide accurate information of individual data points. This is particularly problematic in sparse regions where the density estimate may not provide a good representation of the underlying data. In this paper, we present sunspot plots, a visualization technique that communicates dense data as a continuous data distribution, while preserving the discrete nature of data samples in sparsely populated areas. We furthermore demonstrate the advantages of our approach on typical failure cases of scatter plots within synthetic and real-world data sets and validate its effectiveness in a user study.     

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.     

Ground object recognition and segmentation from aerial image‐based 3D point cloud

Several attempts have been made to grasp three‐dimensional (3D) ground shape from a 3D point cloud generated by aerial vehicles, which help fast situation recognition. However, identifying such objects on the ground from a 3D point cloud, which consists of 3D coordinates and color information, is not straightforward due to the gap between the low‐level point information (coordinates and colors) and high‐level context information (objects). In this paper, we propose a ground object recognition and segmentation method from a geo‐referenced point cloud. Basically, we rely on some existing tools to generate such a point cloud from aerial images, and our method tries to give semantics to each set of clustered points. In our method, firstly, such points that correspond to the ground surface are removed using the elevation data from the Geographical Survey Institute. Next, we apply an interpoint distance‐based clustering and color‐based clustering. Then, such clusters that share some regions are merged to correctly identify a cluster that corresponds to a single object. We have evaluated our method in several experiments in real fields. We have confirmed that our method can remove the ground surface within 20 cm error and can recognize most of the objects.     

Estimation of planes of a rock mass in a gallery wall from point cloud data based on MD PSO

LiDAR (laser imaging detection and ranging) has been developed to measure the distance of the mesh of points on an object with a high level of accuracy. It provides high-resolution point cloud data as a result of distance measurement. Detailed 3D shapes of objects can be estimated from point cloud data. LiDAR has been used to identify discontinuities in a rock mass of a tunnel gallery wall. To identify discontinuities, it is necessary to approximate the rock mass surface with small planes. Normal vectors of the planes are important to identify discontinuities. We developed an algorithm for estimation of planes based on multi-dimensional particle swarm optimization (MD PSO) from point cloud data. Point cloud data were segmented into bounding boxes and grouped into clusters by MD PSO. Planes were estimated using the least squares method for point cloud data in the respective clusters. The newly developed algorithm based on MD PSO was evaluated using point cloud data obtained from a gallery wall. Evaluation was carried out in comparison with the previous developed variable-box segmentation (VBS) algorithm. The MD PSO-based algorithm showed a 7% higher accuracy than that of the VBS algorithm.     

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.     

Brushing of attribute clouds for the visualization of multivariate data

The visualization and exploration of multivariate data is still a challenging task. Methods either try to visualize all variables simultaneously at each position using glyph-based approaches or use linked views for the interaction between attribute space and physical domain such as brushing of scatterplots. Most visualizations of the attribute space are either difficult to understand or suffer from visual clutter. We propose a transformation of the high-dimensional data in attribute space to 2D that results in a point cloud, called attribute cloud, such that points with similar multivariate attributes are located close to each other. The transformation is based on ideas from multivariate density estimation and manifold learning. The resulting attribute cloud is an easy to understand visualization of multivariate data in two dimensions. We explain several techniques to incorporate additional information into the attribute cloud, that help the user get a better understanding of multivariate data. Using different examples from fluid dynamics and climate simulation, we show how brushing can be used to explore the attribute cloud and find interesting structures in physical space.     

基于密度聚类和投票判别的三维数据去噪方法

本文介绍的是一种有效发现和去除三维数据噪音方法,它既能改善去除噪音的效果,又能保持特征信息。该方法是一种两阶段噪音数据处理方法。该方法首先通过密度聚类将数据分类为正常簇集合、疑似簇集合、异常簇集合,然后利用正常簇集合中的点对疑似簇集合中各点进行投票判断,最终得到一个合理的三维点云数据模型。实验结果证明,本方法能够有效去除制造类工件模型的三维点云数据中的噪音数据,同时能良好保持模型表面的特征,加快处理效率。     

Adaptive random sample consensus approach for segmentation of building roof in airborne laser scanning point cloud

ABSTRACT

This work proposes a three-step method for segmenting the roof planes of buildings in Airborne Laser Scanning (ALS) data. The first step aims at mainly avoiding the exhaustive search for planar roof faces throughout the ALS point cloud. Standard algorithms for processing ALS point cloud are used to isolate building regions. The second step of the proposed method consists in segmenting roof planes within building regions previously delimited. We use the RANdom SAmple Consensus (RANSAC) algorithm to detect roof plane points, taking into account two adaptive parameters for checking the consistency of ALS building points with the candidate planes: the distance between ALS building points and candidate planes; and the angle between the gradient vectors at ALS building points and the candidate planes’ normal vector. Each ALS building point is classified as consistent if computed parameters are below corresponding thresholds, which are automatically determined by thresholding histograms constructed for both parameters. As the RANSAC algorithm can generate fragmented results, in the third step, a post-processing is accomplished to merge planes that are approximately collinear and spatially close. The results show that the proposed method works properly. However, failures occur mainly in regions affected by local anomalies such as trees and antennas. Average rates around 90% and higher than 95% have been obtained for the completeness and correction quality parameters, respectively.     

Robust and Efficient Implicit Surface Reconstruction for Point Clouds Based on Convexified Image Segmentation

We present an implicit surface reconstruction algorithm for point clouds. We view the implicit surface reconstruction as a three dimensional binary image segmentation problem that segments the entire space $\mathbb R ^3$ or the computational domain into an interior region and an exterior region while the boundary between these two regions fits the data points properly. The key points with using an image segmentation formulation are: (1) an edge indicator function that gives a sharp indicator of the surface location, and (2) an initial image function that provides a good initial guess of the interior and exterior regions. In this work we propose novel ways to build both functions directly from the point cloud data. We then adopt recent convexified image segmentation models and fast computational algorithms to achieve efficient and robust implicit surface reconstruction for point clouds. We test our methods on various data sets that are noisy, non-uniform, and with holes or with open boundaries. Moreover, comparisons are also made to current state of the art point cloud surface reconstruction techniques.     

面向RGBD深度数据的快速点云配准方法

目的 真实物体的3维重建一直是计算机图形学、机器视觉等领域的研究热点。针对基于RGBD数据的非匀速非固定角度旋转物体的3维重建问题,提出一种利用旋转平台重建物体3维模型的配准方法。方法 首先通过Kinect采集位于旋转平台上目标物的深度数据和颜色数据,对齐融合并使用包围盒算法去除背景噪声和不需要的外部点云,获得带有颜色信息的点云数据。并使用基于标定物不同角度上的点云数据标定出旋转平台中心轴的位置,从而获得Kinect与旋转平台之间的相对关系;然后通过曲率特征对目标点云进行特征点提取并寻找与相邻点云的对应点;其中对于特征点的选取,首先针对点云中的任意一点利用kd-tree搜寻其k个邻近点,对这些点进行曲面拟合,进而计算其高斯曲率,将高斯曲率绝对值较大的n个点作为点云的特征点。n的取值由点云的点个数、点密度和复杂度决定,具体表现为能反映物体的大致轮廓或表面特征信息即可。对于对应点的选取,考虑到欧氏距离并不能较好反映点云中的点对在旋转过程中的对应关系,在实际配准中,往往会因为点云重叠或距离过远等原因找到大量错误的对应点。由于目标物在扫描过程中仅绕旋转轴进行旋转,因此采用圆弧最小距离寻找对应点可有效减少错误点对。随后,使用二分迭代寻找绕中心轴的最优旋转角度以满足点云间的匹配误差最小;最后,将任意角度获取的点云数据配准到统一的坐标系下并重建模型。结果 使用斯坦福大学点云数据库和自采集数据库分别对该方法和已有方法在算法效率和配准结果上进行对比实验,实验结果显示在拥有平均75 000个采样点的斯坦福大学点云数据库上与传统ICP算法和改进ICP算法相比,迭代次数分别平均减少86.5%、57.5%,算法运行时间分别平均减少87%、60.75%,欧氏距离误差平方和分别平均减少70%、22%;在具有平均57000个采样点的自采集点云数据库上与传统ICP算法和改进ICP算法相比,迭代次数分别平均减少94%、75%,算法运行时间分别平均减少92%、69%,欧氏距离误差平方和分别平均减少61.5%、30.6%;实验结果显示使用该方法进行点云配准效率较高且配准误差更小;和KinectFusion算法相比在纹理细节保留上也表现出较好的效果。结论 本文提出的基于旋转平台标定的点云配准算法,利用二分迭代算法能够有效降低算法复杂度。与典型ICP和改进的ICP算法的对比实验也表明了本文算法的有效性。另外,与其他方法在具有纹理的点云配准对比实验中也验证了本文配准方法的优越性。该方法仅采用单个Kinect即可实现对非匀速非固定角度旋转物体的3维建模,方便实用,适用于简单快速的3维重建应用场合。     

空间分割与曲率相融合的点云精简算法研究

非接触式扫描方法获得点云数据存在大量的冗余数据。为便于模型重构,针对点云数据精简是必不可少的数据预处理手段,提出了一种基于空间分割和曲率特征信息的点云数据精简算法。通过K-邻域计算、二次曲面拟合、曲率估算和曲率阈值可调的数据分区等关键精简技术,实现了对同一数据不同区域应用不同精简算法,进行不同比例的数据精简。实例验证表明,该算法能适应各种类型曲面数据的精简要求,保证精简效率的同时,很好地保留点云的特征信息。     

结合超体素和区域增长的植物器官点云分割

点云分割是点云识别与建模的基础。为提高点云分割准确率和效率，提出一种结合超体素和区域增长的自适应分割算法。根据三维点云的空间位置和法向量信息，利用八叉树对点云进行初始分割得到超体素。选取超体素的中心体素组成一个新的重采样后的密度均匀点云，降低原始点云数据处理量，从而减少运算时间。建立重采样后点云数据的K-D树索引，根据其局部特征得到点云簇。最后将聚类结果返回到原始点云空间。分别选取植物三个物候期的激光扫描点云，对该方法的有效性进行验证。实验结果表明，该方法分割后点云与手工分割平均拟合度达到93.38%，高于其他同类方法，且算法效率得到明显提升。     

A one‐dimensional homologically persistent skeleton of an unstructured point cloud in any metric space

Real data are often given as a noisy unstructured point cloud, which is hard to visualize. The important problem is to represent topological structures hidden in a cloud by using skeletons with cycles. All past skeletonization methods require extra parameters such as a scale or a noise bound. We define a homologically persistent skeleton, which depends only on a cloud of points and contains optimal subgraphs representing 1‐dimensional cycles in the cloud across all scales. The full skeleton is a universal structure encoding topological persistence of cycles directly on the cloud. Hence a 1‐dimensional shape of a cloud can be now easily predicted by visualizing our skeleton instead of guessing a scale for the original unstructured cloud. We derive more subgraphs to reconstruct provably close approximations to an unknown graph given only by a noisy sample in any metric space. For a cloud of n points in the plane, the full skeleton and all its important subgraphs can be computed in time O(n log n).     

一种散乱分层点云的有序化精简方法

针对激光扫描仪所得点云散乱分层的特点,提出一种有序化的精简方法。首先基 于已知标记点建立三维R-tree 和八叉树集成的空间索引,快速准确地获取局部点云数据,保证 良好的数据检索效率。然后根据局部点云数据的参考平面法向量信息,选取工件坐标系中的一 个坐标轴作为参数化的方向,对局部点云数据进行参数化并拟合二次曲面。最后对R-tree 叶节 点内的二次曲面进行有序化采样,使散乱分层的点云变为单层,得到整个型面的有序参考点集。 应用实例表明,该方法适用于大规模的、具有复杂几何特征且存在一定程度散乱分层的点云, 可以有效地提高数据点的整体精确度,且不会丢失点云的细节特征,具有较强的实用性。     

Enhancing Scatterplots with Multi‐Dimensional Focal Blur

Scatterplots directly depict two dimensions of multi‐dimensional data points, discarding all other information. To visualize all data, these plots are extended to scatterplot matrices, which distribute the information of each data point over many plots. Problems arising from the resulting visual complexity are nowadays alleviated by concepts like filtering and focus and context. We present a method based on depth of field that contains both aspects and injects information from all dimensions into each scatterplot. Our approach is a natural generalization of the commonly known focus effects from optics. It is based on a multidimensional focus selection body. Points outside of this body are defocused depending on their distance. Our method allows for a continuous transition from data points in focus, over regions of blurry points providing contextual information, to visually filtered data. Our algorithm supports different focus selection bodies, blur kernels, and point shapes. We present an optimized GPU‐based implementation for interactive exploration and show the usefulness of our approach on several data sets.     

一种基于降采样后关键点优化的点云配准方法

针对工件点云数据多而导致点云配准耗时长的问题,提出一种基于降采样后关键点优化的点云配准方法。计算点云若干体素的重心,利用kd-tree快速遍历重心的邻近点来代替该体素;提出自适应的点云平均距离计算方法,对降采样后的点云提取ISS3D关键点,并采用基于球邻域的边界点判断方法对其优化;对优化后的关键点进行FPFH特征描述,利用SAC-IA求解近似变换阵,使用ICP算法精配准而解得工件的精确位姿信息。实验结果表明,相较于其他四种配准算法,配准精度分别提高了96.9%、98.1%、93.3%和3.5%,配准速度分别提高了77.2%、77.7%、76.9%和85.4%,表明了该方法的有效性。     

Skeleton-based intrinsic symmetry detection on point clouds

We present a skeleton-based algorithm for intrinsic symmetry detection on imperfect 3D point cloud data. The data imperfections such as noise and incompleteness make it difficult to reliably compute geodesic distances, which play essential roles in existing intrinsic symmetry detection algorithms. In this paper, we leverage recent advances in curve skeleton extraction from point clouds for symmetry detection. Our method exploits the properties of curve skeletons, such as homotopy to the input shape, approximate isometry-invariance, and skeleton-to-surface mapping, for the detection task. Starting from a curve skeleton extracted from an input point cloud, we first compute symmetry electors, each of which is composed of a set of skeleton node pairs pruned with a cascade of symmetry filters. The electors are used to vote for symmetric node pairs indicating the symmetry map on the skeleton. A symmetry correspondence matrix (SCM) is constructed for the input point cloud through transferring the symmetry map from skeleton to point cloud. The final symmetry regions on the point cloud are detected via spectral analysis over the SCM. Experiments on raw point clouds, captured by a 3D scanner or the Microsoft Kinect, demonstrate the robustness of our algorithm. We also apply our method to repair incomplete scans based on the detected intrinsic symmetries.     

Evaluation of Cluster Identification Performance for Different PCP Variants

Parallel coordinate plots (PCPs) are a well‐known visualization technique for viewing multivariate data. In the past, various visual modifications to PCPs have been proposed to facilitate tasks such as correlation and cluster identification, to reduce visual clutter, and to increase their information throughput. Most modifications pertain to the use of color and opacity, smooth curves, or the use of animation. Although many of these seem valid improvements, only few user studies have been performed to investigate this, especially with respect to cluster identification. We performed a user study to evaluate cluster identification performance – with respect to response time and correctness – of nine PCP variations, including standard PCPs. To generate the variations, we focused on covering existing techniques as well as possible while keeping testing feasible. This was done by adapting and merging techniques, which led to the following novel variations. The first is an effective way of embedding scatter plots into PCPs. The second is a technique for highlighting fuzzy clusters based on neighborhood density. The third is a spline‐based drawing technique to reduce ambiguity. The last is a pair of animation schemes for PCP rotation. We present an overview of the tested PCP variations and the results of our study. The most important result is that a fair number of the seemingly valid improvements, with the exception of scatter plots embedded into PCPs, do not result in significant performance gains.     

三维激光扫描点云数据的空间压缩

三维激光扫描获得的点云数据,其数据量比较大。采用点云数据建立物体模型,存在模型分辨率的问题。模型的多分辨率表示是指对于同一模型,存在着由简到繁、由粗到精的集中表示。本文分析激光扫描数据的特点,基于其线扫描的特点,提出了扫描线斜率变化为准则实施数据压缩,其次对于密集数据又给出格网数据压缩方法。最后通过实例给出了压缩结果,并对压缩率和压缩效果作了比较分析。