Algoritmos para el pre procesamiento de nubes de puntos mediante representaciones dispersas

Abstract

Nowadays, 3D scanners have become a standard source that provides millions of points as input for a growing number of applications areas such as industry, entertainment, medicine, computer vision, photogrammetry, etc. The large number of points generated by the scanning device is called point clouds. Point clouds often become complicated to handle due to multiple problems, such as the noise produced in the scanning process, lack of information (holes), or excess of information (points). Also, it is crucial in some applications to detect sharp features, like edges and valleys. We addressed all these problems in a stage of surface reconstruction called point cloud pre-processing. The focus of this thesis is the use of sparse representations for developing robust computational algorithms to solve the problems included in the pre-processing stage. Sparse representations are methods inspired in the human visual system, which can be adapted to the characteristics of problems found in the pre-processing of point clouds. We present contributions on some fundamental topics as denoising, sharp features extraction, hole detection, and simplification. With the direct use of the 3D points, we avoid the need for surface reconstruction methods, which are computationally complex and time-consuming. In this thesis, we introduce a smoothing method, which is effective in removing noise and preserving the sharp features and corners. The features preserving capability comes from the combining L1 median and L1 norm to estimate the normals and the point positions update. To reduce the sampling complexity of the cloud, we present a simplification method based on saliency. A Dictionary learning and sparse coding process are carried out over the normals and curvatures to find the saliencies. Next, it makes a selection of the sparse coefficients that represent the most salient features, carrying out in this way the simplification. We introduce a method for detecting features and holes in point clouds. First, we build a covariance matrix from the geometric information in a neighborhood around each point in the cloud. Then we estimate the eigenvalues of the covariance matrix, and combining them, we build feature vectors. The feature vectors are the signals to carry out a dictionary learning followed by a sparse coding process. At last, Imposing a threshold over the sparse coefficients, we detect features (edges, corners, valleys) and holes. We show the effectivity of our algorithms in a wide range of scanned geometric models of varying sizes, complexity, and details.

Hoy en día, los escáneres 3D se han convertido en una fuente estándar que proporciona millones de puntos como entrada para un número creciente de áreas de aplicaciones como: industria, entretenimiento, medicina, fotogrametría, visión por computadora etc. La gran cantidad de puntos que se generan a partir del proceso de escaneo se denomina nube de puntos y, a menudo, se vuelve complicado de manejar debido a múltiples problemas, como el ruido producido por el proceso de escaneo, la falta de información (agujeros) y el exceso de información (puntos), también es importante en algunas aplicaciones detecta características sobresalientes, como bordes y valles. Todos estos problemas se abordan en la etapa de la reconstrucción de superficies llamada preprocesamiento de la nube de puntos. El objetivo de esta tesis es el uso de representaciones para desarrollar algoritmos computacionales robustos para resolver los problemas presentes en el preprocesamiento de nubes de puntos.Las representaciones dispersas son métodos inspirados in el sistema de visión humano, los cuales pueden ser adaptados a las características de los problemas encontrados en el pre procesamiento de nubes de puntos. Presentamos contribuciones sobre algunos temas fundamentales como, la eliminación de ruido, la extracción de características finas, la simplificación de puntos y la detección de huecos. Al usar directamente los puntos 3D, evitamos la necesidad de métodos de reconstrucción de superficie, que son complejos y requieren mucho tiempo de procesamiento. En esta tesis, se introduce un método de suavizado el cual es efectivo para eliminar el ruido y preservar las bordes y esquinas en nubes de puntos. La capacidad de preservación de características proviene de la combinación de la mediana L1 y la norma L1 para estimar las normales y la actualización de las posiciones de los puntos. Para reducir la complejidad del muestreo de la nube, presentamos un método de simplificación basado en saliencia. Para ello, se lleva a cabo un proceso de aprendizaje de diccionario y codificación dispersa sobre las normales y las curvaturas para encontrar las saliencias. A continuación, se realiza una selección de los vectores dispersos que representan las características con mas saliencia, llevando a cabo de esta manera la simplificación. Introducimos un método para detectar bordes y huecos en nubes de puntos. Primero,construimos una matriz de covarianza a partir de la información geométrica en un vecindario alrededor de cada punto en la nube. Luego se estiman los valores propios de la matriz de covarianza, y se combinan para formar vectores de características, que se utilizan como señales para llevar a cabo un aprendizaje de diccionario seguido de un proceso de codificación disperso. Finalmente, al imponer un umbral sobre los coeficientes dispersos, detectamos las características (bordes, esquinas, valles) y agujeros. Demostramos la utilidad de todos nuestros algoritmos en una amplia variedad de modelos geométricos escaneados de diferentes tamaños, complejidad y detalles.