Light Detection And Ranging (LiDAR), as well as many other applications and sensors, involve segmenting sparse sets of points (point clouds) for which point density is the only discriminating feature. The segmentation of these point clouds is challenging for several reasons, including the fact that the points are not associated with a regular grid. Moreover, the presence of noise, particularly impulsive noise with varying density, can make it difficult to obtain a good segmentation using traditional techniques, including the algorithms that had been developed to process LiDAR data. This dissertation introduces novel algorithms and frameworks based on statistical techniques and image analysis in order to segment and extract surfaces from sparse noisy point clouds. We introduce an adaptive method for mapping point clouds onto an image grid followed by a contour detection approach that is based on an enhanced version of region-based Active Contours Without Edges (ACWE). We also proposed a noise reduction method using Bayesian approach and incorporated it, along with other noise reduction approaches, into a joint framework that produces robust results. We combined the aforementioned techniques with a statistical surface refinement method to introduce a novel framework to detect ground and canopy surfaces in micropulse photon-counting LiDAR data. The algorithm is fully automatic and uses no prior elevation or geographic information to extract surfaces. Moreover, we propose a novel segmentation framework for noisy point clouds in the plane based on a Markov random field (MRF) optimization that we call Point Cloud Densitybased Segmentation (PCDS). We also developed a large synthetic dataset of in plane point clouds that includes either a set of randomly placed, sized and oriented primitive objects (circle, rectangle and triangle) or an arbitrary shape that forms a simple approximation for the LiDAR point clouds. The experiment performed on a large number of real LiDAR and synthetic point clouds showed that our proposed frameworks and algorithms outperforms the state-of-the-art algorithms in terms of segmentation accuracy and surface RMSE. / Ph. D.

Computer vision is a research field in which images are the main object of study. One of its category of problems is shape description. Object classification is one important example of applications using shape descriptors. Usually, these processes were performed on 2D images. With the large-scale development of new technologies and the affordable price of equipment that generates 3D images, computer vision has adapted to this new scenario, expanding the classic 2D methods to 3D. However, it is important to highlight that 2D methods are mostly dependent on the variation of illumination and color, while 3D sensors provide depth, structure/3D shape and topological information beyond color. Thus, different methods of shape descriptors and robust attributes extraction were studied, from which new attribute extraction methods have been proposed and described based on 3D data. The results obtained from well known public datasets have demonstrated their efficiency and that they compete with other state-of-the-art methods in this area: the RPHSD (a method proposed in this dissertation), achieved 85:4% of accuracy on the University of Washington RGB-D dataset, being the second best accuracy on this dataset; the COMSD (another proposed method) has achieved 82:3% of accuracy, standing at the seventh position in the rank; and the CNSD (another proposed method) at the ninth position. Also, the RPHSD and COMSD methods have relatively small processing complexity, so they achieve high accuracy with low computing time. / Visão computacional é uma área de pesquisa em que as imagens são o principal objeto de estudo. Um dos problemas abordados é o da descrição de formatos (em inglês, shapes). Classificação de objetos é um importante exemplo de aplicação que usa descritores de shapes. Classicamente, esses processos eram realizados em imagens 2D. Com o desenvolvimento em larga escala de novas tecnologias e o barateamento dos equipamentos que geram imagens 3D, a visão computacional se adaptou para este novo cenário, expandindo os métodos 2D clássicos para 3D. Entretanto, estes métodos são, majoritariamente, dependentes da variação de iluminação e de cor, enquanto os sensores 3D fornecem informações de profundidade, shape 3D e topologia, além da cor. Assim, foram estudados diferentes métodos de classificação de objetos e extração de atributos robustos, onde a partir destes são propostos e descritos novos métodos de extração de atributos a partir de dados 3D. Os resultados obtidos utilizando bases de dados 3D públicas conhecidas demonstraram a eficiência dos métodos propóstos e que os mesmos competem com outros métodos no estado-da-arte: o RPHSD (um dos métodos propostos) atingiu 85:4% de acurácia, sendo a segunda maior acurácia neste banco de dados; o COMSD (outro método proposto) atingiu 82:3% de acurácia, se posicionando na sétima posição do ranking; e o CNSD (outro método proposto) em nono lugar. Além disso, os métodos RPHSD têm uma complexidade de processamento relativamente baixa. Assim, eles atingem uma alta acurácia com um pequeno tempo de processamento.

Le traitement de nuages de points 3D de lidars permet aux robots mobiles autonomes terrestres de construire des modèles sémantiques de l'environnement extérieur dans lequel ils évoluent. Ces modèles sont intéressants car ils représentent des informations qualitatives, et ainsi donnent à un robot la capacité de raisonner à un niveau plus élevé d'abstraction. Le coeur d'un système de modélisation sémantique est la capacité de classifier les observations venant du capteur. Nous proposons un système de classification centré sur l'apprentissage non-supervisé. La prémière couche, la couche intermédiaire, consiste en un modèle de mélange gaussien. Ce modèle est déterminé de manière non-supervisée lors d'une étape de training. Il definit un ensemble de classes intermédiaires qui correspond à une partition fine des classes présentes dans l'environnement. La deuxième couche, la couche finale, consiste en un regroupement des classes intermédiaires dans un ensemble de classes finales qui, elles, sont interprétables dans le contexte de la tâche ciblée. Le regroupement est déterminé par un expert lors de l'étape de training, de manière supervisée, mais guidée par les classes intermédiaires. L'évaluation est basée sur deux jeux de données acquis avec de différents lidars et possédant différentes caractéristiques. L'évaluation est quantitative pour l'un des jeux de données, et qualitative pour l'autre. La concéption du système utilise la procédure standard de l'apprentissage, basée sur les étapes de training, validation et test. L'opération suit la pipeline standard de classification. Le système est simple, et ne requiert aucun pré-traitement ou post-traitement. / The processing of 3D lidar point clouds enable terrestrial autonomous mobile robots to build semantic models of the outdoor environments in which they operate. Such models are interesting because they encode qualitative information, and thus provide to a robot the ability to reason at a higher level of abstraction. At the core of a semantic modelling system, lies the capacity to classify the sensor observations. We propose a two-layer classi- fication model which strongly relies on unsupervised learning. The first, intermediary layer consists of a Gaussian mixture model. This model is determined in a training step in an unsupervised manner, and defines a set of intermediary classes which is a fine-partitioned representation of the environment. The second, final layer consists of a grouping of the intermediary classes into final classes that are interpretable in a considered target task. This grouping is determined by an expert during the training step, in a process which is supervised, yet guided by the intermediary classes. The evaluation is done for two datasets acquired with different lidars and possessing different characteristics. It is done quantitatively using one of the datasets, and qualitatively using another. The system is designed following the standard learning procedure, based on a training, a validation and a test steps. The operation follows a standard classification pipeline. The system is simple, with no requirement of pre-processing or post-processing stages.

Nos últimos anos a utilização de pontos como primitiva gráfica básica vem mostrandose uma poderosa e versátil ferramenta para a computação gráfica. Considerável esforço de pesquisa vem sendo dedicado para encontrar formas eficientes de aquisição, representação, processamento, renderização e animação para conjuntos de pontos. As representações baseadas em pontos têm-se destacado como uma estratégia eficiente em computação desde que se tornou comum extrair modelos geométricos a partir de Scanners 3D, os quais geram grandes quantidades de pontos que aproximam a geometria do objeto. Este trabalho apresenta um conjunto de métodos para tratar a visibilidade aproximada para nuvens de pontos sem informação de conectividade e topologia. Primeiramente é proposto uma abordagem baseada em clusters para acelerar o operador de remoção de pontos proposto por Katz et al. A principal motivação para esta otimização é a possibilidade de conseguir um equilíbrio entre a velocidade e a qualidade do resultado. Também é apresentado uma técnica de renderização baseada em pontos acelerada por hardware chamada Surface Splatting. Esta abordagem utiliza mapeamento de textura com alpha blending para aproximar um filtro de reamostragem Elliptical Weighted Average no espaço de objeto. Juntamente com o Geometry Shader das modernas placas gráficas, produz de forma eficiente imagens de alta qualidade de superfícies amostradas por surfels. Por último é proposto um novo operador de remoção de pontos ocultos acelerado por hardware baseados na técnica de splatting juntamente com um operador morfológico de erosão modificado para reduzir o efeito de silhuetas no resultado final do operador. A motivação para a criação deste novo operador é a baixa eficiência demonstrada pelos métodos existentes para a utilização em aplicações em tempo real onde as nuvens de pontos são muito densas. Todas as técnicas apresentadas neste trabalho podem ser utilizadas em visualização científica com taxas interativas, em particular na visualização direta de geometria baseada em pontos. / In recent years the use of points as a fundamental graphics primitive has proved to be a powerful and versatile tool for computer graphics. Considerable research has been devoted to the efficient representation, modeling, processing, rendering and animation of point-sampled geometry. The point-based representation has gained increasing attention in computer graphics because 3D scanning systems easily extract large information from real-world objects. On the other hand, point sets are more flexible when compared to triangle meshes, because they are not required to maintain consistent topological information. This work presents a set of tools to determine the visibility and also to render a point-based geometry efficiently. Firstly, a cluster-based approach is proposed to speed up the hidden point removal operator proposed by Katz et al. The main idea of this study is to trade-off speed and quality in dynamic scenes of moving or deforming point clouds. After that, a hardware based point rendering technique called Surface Splatting is introduced. This approach uses the texture mapping with alpha blending and the Geometry Shader to approximate the Elliptical Weighted Average filter in object space. This efficient technique produces high quality images as surfel-based geometry. Finally, a new hidden point removal operator is presented. This operator, based on the splatting technique and also hardware accelerated, applies a morphological erosion operation in the depth buffer to reduce the silhouette effect in the final image. The motivation to develop a new operator is the low efficiency demonstrated by existing hidden point removal methods in real time applications, where the point cloud is very dense. All the techniques introduced in this work can be used in scientific visualization with interactive frame rates, particularly when visualizing point-based geometry sets.

Detecção automática de regiões planares em nuvens de pontos é um importante passo para muitas aplicações gráficas, de processamento de imagens e de visão computacional. Enquanto a disponibilidade de digitalizadores a laser e a fotografia digital tem nos permitido capturar nuvens de pontos cada vez maiores, técnicas anteriores para detecção de planos são computacionalmente caras, sendo incapazes de alcançar desempenho em tempo real para conjunto de dados contendo dezenas de milhares de pontos, mesmo quando a detecção é feita de um modo não determinístico. Apresentamos uma abordagem determinística para detecção de planos em nuvens de pontos não estruturadas que apresenta complexidade computacional O(n log n) no número de amostras de entrada. Ela é baseada em um método eficiente de votação para a transformada de Hough. Nossa estratégia agrupa conjuntos de pontos aproximadamente coplanares e deposita votos para estes conjuntos em um acumulador esférico, utilizando núcleos Gaussianos trivariados. Uma comparação com as técnicas concorrentes mostra que nossa abordagem é consideravelmente mais rápida e escala significativamente melhor que as técnicas anteriores, sendo a primeira solução prática para detecção determinística de planos em nuvens de pontos grandes e não estruturadas. / Automatic detection of planar regions in point clouds is an important step for many graphics, image processing, and computer vision applications. While laser scanners and digital photography have allowed us to capture increasingly larger datasets, previous techniques are computationally expensive, being unable to achieve real-time performance for datasets containing tens of thousands of points, even when detection is performed in a non-deterministic way. We present a deterministic technique for plane detection in unorganized point clouds whose cost is O(n log n) in the number of input samples. It is based on an efficient Hough-transform voting scheme and works by clustering approximately co-planar points and by casting votes for these clusters on a spherical accumulator using a trivariate Gaussian kernel. A comparison with competing techniques shows that our approach is considerably faster and scales significantly better than previous ones, being the first practical solution for deterministic plane detection in large unorganized point clouds.

Laser scanners provide a three-dimensional sampled representation of the surfaces of objects. The spatial resolution of the data is much higher than that of conventional surveying methods. The data collected from different locations of a laser scanner must be transformed into a common coordinate system. If good a priori alignment is provided and the point clouds share a large overlapping region, existing registration methods, such as the Iterative Closest Point (ICP) or Chen and Medioni’s method, work well. In practical applications of laser scanners, partially overlapping and unorganised point clouds are provided without good initial alignment. In these cases, the existing registration methods are not appropriate since it becomes very difficult to find the correspondence of the point clouds. A registration method, the Geometric Primitive ICP with the RANSAC (GPICPR), using geometric primitives, neighbourhood search, the positional uncertainty of laser scanners, and an outlier removal procedure is proposed in this thesis. The change of geometric curvature and approximate normal vector of the surface formed by a point and its neighbourhood are used for selecting the possible correspondences of point clouds. In addition, an explicit expression of the position uncertainty of measurement by laser scanners is presented in this dissertation and this position uncertainty is utilised to estimate the precision and accuracy of the estimated relative transformation parameters between point clouds. The GP-ICPR was tested with both simulated data and datasets from close range and terrestrial laser scanners in terms of its precision, accuracy, and convergence region. It was shown that the GP-ICPR improved the precision of the estimated relative transformation parameters as much as a factor of 5. / In addition, the rotational convergence region of the GP-ICPR on the order of 10°, which is much larger than the ICP or its variants, provides a window of opportunity to utilise this automated registration method in practical applications such as terrestrial surveying and deformation monitoring.

During several years research has been performed at the Department of Laser Systems, the Swedish Defense Research Agency (FOI), to develop methods to produce high resolution 3D environment models based on data acquired with airborne laser systems. The 3D models are used for several purposes, both military and civilian applications, for example mission planning, crisis management analysis and planning of infrastructure. We have implemented a new format to store laser point data. Instead of storing rasterized images of the data this new format stores the original location of each point. We have also implemented a new method to detect outliers, methods to estimate the ground surface and also to divide the remaining data into two classes: buildings and vegetation. It is also shown that it is possible to get more accurate results by analyzing the points directly instead of only using rasterized images and image processing algorithms. We show that these methods can be implemented without increasing the computational complexity.

<p>During several years research has been performed at the Department of Laser Systems, the Swedish Defense Research Agency (FOI), to develop methods to produce high resolution 3D environment models based on data acquired with airborne laser systems. The 3D models are used for several purposes, both military and civilian applications, for example mission planning, crisis management analysis and planning of infrastructure.</p><p>We have implemented a new format to store laser point data. Instead of storing rasterized images of the data this new format stores the original location of each point. We have also implemented a new method to detect outliers, methods to estimate the ground surface and also to divide the remaining data into two classes: buildings and vegetation.</p><p>It is also shown that it is possible to get more accurate results by analyzing the points directly instead of only using rasterized images and image processing algorithms. We show that these methods can be implemented without increasing the computational complexity.</p>

Many laser devices acquire directly 3D objects and reconstruct their surface. Nevertheless, the final reconstructed surface is usually smoothed out as a result of the scanner internal de-noising process and the offsets between different scans. This thesis, working on results from high precision scans, adopts the somewhat extreme conservative position, not to loose or alter any raw sample throughout the whole processing pipeline, and to attempt to visualize them. Indeed, it is the only way to discover all surface imperfections (holes, offsets). Furthermore, since high precision data can capture the slightest surface variation, any smoothing and any sub-sampling can incur in the loss of textural detail.The thesis attempts to prove that one can triangulate the raw point cloud with almost no sample loss. It solves the exact visualization problem on large data sets of up to 35 million points made of 300 different scan sweeps and more. Two major problems are addressed. The first one is the orientation of the complete raw point set, an the building of a high precision mesh. The second one is the correction of the tiny scan misalignments which can cause strong high frequency aliasing and hamper completely a direct visualization.The second development of the thesis is a general low-high frequency decomposition algorithm for any point cloud. Thus classic image analysis tools, the level set tree and the MSER representations, are extended to meshes, yielding an intrinsic mesh segmentation method.The underlying mathematical development focuses on an analysis of a half dozen discrete differential operators acting on raw point clouds which have been proposed in the literature. By considering the asymptotic behavior of these operators on a smooth surface, a classification by their underlying curvature operators is obtained.This analysis leads to the development of a discrete operator consistent with the mean curvature motion (the intrinsic heat equation) defining a remarkably simple and robust numerical scale space. By this scale space all of the above mentioned problems (point set orientation, raw point set triangulation, scan merging, segmentation), usually addressed by separated techniques, are solved in a unified framework.

No description available.