An improved segmentation approach for planar surfaces from unstructured 3D point clouds
The extraction of object features from massive unstructured point clouds with different local densities, especially in the presence of random noisy points, is not a trivial task even if that feature is a planar surface. Segmentation is the most important step in the feature extraction process. In practice, most segmentation approaches use geometrical information to segment the 3D point cloud. The features generally include the position of each point (X, Y and Z) locally estimated surface normals and residuals of best fitting surfaces; however, these features could be affected by noisy points and in consequence directly affect the segmentation results. Therefore, massive unstructured and noisy point clouds also lead to bad segmentation (over segmentation, under segmentation or no segmentation) While the RANSAC (random sample consensus) algorithm is effective in the presence of noise and outliers, it has two significant disadvantages, namely, its efficiency and the fact that the plane detected by RANSAC may not necessarily belong to the same object surface; that is, spurious surfaces may appear, especially in the case of parallel gradual planar surfaces such as stairs. The innovative idea proposed in this paper is a modification for the RANSAC algorithm called Seq NV RANSAC. This algorithm checks the normal vector (NV) between the existing point clouds and the hypothesised RANSAC plane, which is created by three random points, under an intuitive threshold value. After extracting the first plane, this process is repeated sequentially (Seq) and automatically, until no planar surfaces can be extracted from the remaining points under the existing threshold value. This prevents the extraction of spurious surfaces, brings an improvement in quality to the computed attributes and increases the degree of automation of surface extraction. Thus the best fit is achieved for the real existing surfaces. Resume L'extraction d'objets dans de grands nuages de points non structures et presentant des densites locales variables, notamment en presence de points aleatoirement bruites, n'est pas une tache simple meme si l'objet recherche est une surface plane. La segmentation est l'etape la plus importante du processus d'extraction d'objets. En pratique, la plupart des methodes de segmentation s'appuient sur une information geometrique pour segmenter le nuage de points 3D. Les objets recherches incluent generalement les positions de chaque point (X, Y, Z) des directions normales a la surface estimees localement et les residus des surfaces qui optimisent l'ajustement; cependant, ces objets peuvent etre affectes par des points bruites ce qui peut directement affecter le resultat de la segmentation. C'est pourquoi de grands nuages de points non structures et bruites conduisent aussi a une mauvaise segmentation (sursegmentation, sous segmentation ou impossibilite de segmenter) Bien que l'algorithme RANSAC (Random Sample Consensus) soit efficace en presence de bruit ou de points aberrants, il presente deux inconvenients significatifs, a savoir, d'une part, son efficacite, et d'autre part, le fait que le plan detecte par RANSAC ne coincide pas forcement avec la surface de l'objet recherche. Ainsi, des surfaces parasites peuvent apparaitre, notamment dans le cas de series de surfaces planes comme des escaliers. L'idee innovante proposee dans cet article est une modification de l'algorithme RANSAC appelee Seq NV RANSAC, qui modifie le vecteur normal entre les nuages de points existants et le plan suppose par RANSAC, lequel est cree par trois points au hasard, au dessous d'une valeur seuil intuitive. Apres l'extraction du premier plan, le processus est repete sequentiellement et automatiquement jusqu'a ce que plus aucune surface plane ne puisse etre extraite des points restant au dessous du seuil. Cela empeche l'extraction de surfaces parasites, ameliore la qualite des attributs calcules et accroit le degre d'automatisation de l'extraction de surfaces. On obtient un resultat optimal pour des surfaces existantes. Zusammenfassung Die Erfassung von Objektmerkmalen groser, unstrukturierten Punktwolken mit unterschiedlich lokalen Dichten und bei verrauschten Punkten ist keine einfache Aufgabe, auch wenn nur eine ebene Oberflache extrahiert werden soll. Segmentierung ist der wichtigste Schritt bei der Merkmalsextraktion. In der Praxis nutzen die meisten Segmentierungsansatze geometrische Information, um die 3D Punktwolke zu segmentieren. Die Merkmale umfassen ublicherweise die Lage jeden Punktes (X, Y und Z) die lokal bestimmte Oberflachennormale und Verbesserungen fur angepasste Oberflachen: allerdings konnen diese Merkmale durch verrauschte Punkte beeinflusst werden, und damit auch die Ergebnisse der nachfolgenden Segmentierung. Daher konnen stark unstrukturierte und verrauschte Punktwolken zu schlechten Segmentierungen fuhren (Ubersegmentierung, Untersegmentierung oder sogar keiner Segmentierung) Wahrend der RANSAC (Random Sample Consensus) Algorithmus effektiv bei Rauschen und groben Fehlern arbeitet, hat er doch zwei signifikante Nachteile: seine Effizienz und die Ebene, die mit RANSAC detektiert wurde muss nicht unbedingt zu der gleichen Oberflache gehoren, d.h. unechte Oberflachen konnen generiert werden. Dies ist vor allem im Fall von stufenweise ebenen Oberflachen wie bei Treppen gegeben. Die Innovation dieses Beitrages liegt in der Modifizierung des RANSAC Algorithmus, dem sogenannten Seq NV RANSAC. Dieser Algorithmus pruft, mit Hilfe eines intuitiven Schwellwertes, den Normalenvektor (NV) zwischen den existierenden Punktwolken und der Hypothese der RANSAC Ebene, die durch 3 zufallige Punkte festgelegt wird. Nach der Extraktion der ersten Ebene, wird dieser Prozess sequentiell (Seq) automatisch wiederholt, bis keine weiteren ebenen Oberflachen aus den verbliebenen Punkten bei den gegebene Schwellwert extrahiert werden konnen. Dies verhindert die Extraktion von virtuellen Oberflachen, ergibt eine Qualitatsverbesserung der berechneten Attribute und erhoht den Grad der Automation bei der Oberflachenextraktion. Damit wird die beste Ubereinstimmung fur die vorliegenden Oberflachen erreicht. Resumen La extraccion de objetos a partir de nubes no estructuradas de puntos con diferentes densidades locales, especialmente en presencia de puntos ruidosos aleatorios, no es una tarea trivial incluso si el objeto es una superficie plana. La segmentacion es el paso mas importante en el proceso de extraccion de objetos. En la practica, la mayor parte de los procedimientos de segmentacion utilizan informacion geometrica para fragmentar la nube de puntos tridimensional. Habitualmente los objetos incluyen informacion de la posicion de cada punto (X, Y y Z) las normales a la superficie estimadas localmente y los residuos de las superficies de mejor ajuste. Sin embargo estos objetos podrian verse influenciados por puntos ruidosos y, consecuentemente, afectar directamente a los resultados de la segmentacion. Por lo tanto, las nubes de puntos ruidosos no estructuradas y masivas tambien dan lugar a una segmentacion inadecuada (sobresegmentacion, infrasegmentacion, o falta de segmentacion) Aunque el algoritmo RANSAC (Random Sample Consensus) es eficaz en presencia de ruido y valores extremos, tiene dos desventajas: su baja eficiencia y el hecho de que el plano detectado por el algoritmo RANSAC no tiene por que pertenecer necesariamente a la misma superficie del objeto. Esto quiere decir que pueden aparecer superficies espurias, especialmente en el caso de superficies planas, graduales y paralelas, como en el caso de escaleras. La idea novedosa propuesta en este articulo es una modificacion del algoritmo RANSAC, denominada Seq NV RANSAC, que verifica si el vector normal entre las nubes de puntos disponibles y el plano determinado por RANSAC, que se construye a partir de tres puntos aleatorios, esta por debajo de un umbral intuitivo. Tras extraer el primer plano, el proceso se repite secuencial (Seq) y automaticamente hasta que no se pueden extraer mas superficies planas a partir de puntos restantes por debajo de los umbrales establecidos. Esto evita la extraccion de superficies espurias, mejora la calidad de los atributos calculados e incrementa el nivel de automatizacion de la extraccion de superficies. De este modo se obtiene el mejor ajuste para las superficies existentes.