Multi-Scale Point Cloud Analysis

(1)

EUROGRAPHICS 2019/ O. Bimber and A. Fusiello Poster

Multi-Scale Point Cloud Analysis

T. Lejemble¹, C. Mura², L. Barthe¹and N. Mellado¹

1IRIT, Université de Toulouse, CNRS, INPT, UPS, UT1C, UT2J

2Department of Informatics, University of Zurich

Figure 1:Left: Region growing performed from low to high scale. Right: Four of the most persistent components.

Abstract

Surfaces sampled with point clouds often exhibit multi-scale properties due to the high variation between their feature size.

Traditional shape analysis techniques usually rely on geometric descriptors able to characterize a point and its close neighborhood at multiple scale using smoothing kernels of varying radii. We propose to add a spatial regularization to these point-wise descriptors in two different ways. The first groups similar points in regions that are structured in a hierarchical graph. The graph is then simplified and processed to extract pertinent regions. The second performs a spatial gradient descent in order to highlight stable parts of the surface. We show two experiments focusing on planar and anisotropic feature areas respectively.

1. Introduction

3D acquisition techniques are very popular for modeling our en- vironment because of their affordable price and their ease of use.

Most of the acquisition processes, such as laser scanner and pho- togrammetry, generate an unstructuredpoint cloudsampling the scanned surface. The surface is unknown and the point cloud needs to be analyzed for performing tasks such as shape retrieval, object classification and interactive visualization to name a few.

As the capabilities of scanning devices increase, point cloud data become more complex. The resolution and the accuracy are such that it is possible to scan an entire building at the millimeter scale, producing several millions, or even billions, of samples. Data con- tains thin details as well as coarser shapes depending on the scale at which we observe it. This variation in feature size raises the need ofmulti-scaleanalysis methods that are able to characterize the geometry at different levels of scale.

Multi-scale shape analysis Inspired by the scale-space theory in- troduced in computer vision [Lin94], multi-scale analysis has been applied to 3D data [PKG03,MGB^∗12]. The point set is convoluted by a smoothing operator of progressively increasing size. While

these methods are efficient for local geometry processing, they are intrinsically local and therefore lack of global or regional regularization.

A multi-scale representation of a point cloud can also be obtained by computing a super-segmentation and incrementally merg- ing groups of segments until obtaining a coarse, over-simplified representation [AP10,FLD18]. However, the generation of candi- date segmentations is based on greedy merge operations, which is likely to miss intermediate representations that are meaningful in the context of a high level, multi-scale analysis.

2. Overview

Our goal is to extend point-wise multi-scale surface descriptors [MGB^∗12] to a regional level of analysis. We base our work on one of theMoving Least Squares(MLS) point-set surfaces frame- work [GG07]. This method locally fits an implicit surface in a scalar fields:IR³→IRcomputed from the neighboring samples of a point. The radiust∈IRof the spherical neighborhood defines thescaleof analysis.

c 2019 The Author(s)

Eurographics Proceedings c2019 The Eurographics Association.

DOI: 10.2312/egp.20191047 https://www.eg.org https://diglib.eg.org

(2)

T. Lejemble et al. /Multi-ScalePointCloudAnalysis In order to add a spatial regularization, we propose two differ-

ent approaches. The first one (Section3) groups similar samples in regions at different scales using a similarity function based on the scalar fields. The segmentations performed at different level of scale are then structured in a graph that is simplified for only extracting pertinent planar regions.

The second solution (Section4) is to progress through the three dimensional space by following the direction that locally maximize the stability ofsat each iteration. The flow lines obtained by re- peating this procedure starting from multiple points highlight stable anisotropic parts of the point clouds.

3. Segmentations graph

The goal of the segmentation is to evolve from a local point-wise description toward a more high level scope of analysis by group- ing similar points together. We perform independentlyNsegmen- tations at increasing scales{t0. . .tN−1}and we represent them in a hierarchical graph encoding similarities between regions at consecutive levels of scale. Finally, a subset of region are extracted by performing a topological graph clustering algorithm.

Segmentations The segmentation at one scalet∈IRis done with a seeded region growing using thek-nearest neighbor graph of the point cloud. The gradient∂xsof the MLS scalar fields, computed at scalet, is used to estimate surface normal vectors. A region grows from one seed sample to its neighbors if the deviation between their estimated normal is below an angular thresholdθ. To favors planar regions, the seeds are chosen with the minimal absolute values of principals curvatures obtained from∂²xs. Figure1shows 3 segmentations at different level of scale.

Hierarchical Graph Each of the N segmentations gives rise to one level in the graph. A region obtained at scaletjis represented by one node at thej^thlevel in the graph, which defines a bijection between nodes and regions. The connection between the nodes is done between two consecutive scalestj andtj+1. Two nodes are connected by an edge if the intersection between their underlying point sets is not empty. Such graph encodes the similarity between pair of regions at consecutive levels.

Topological Simplification The graph is finally filtered in order to extract only a reduced set of the numerous regions. Inspired by the persistence theory in computational geometry [ELZ00], we compute persistent components from the hierarchical graph. In our context, acomponentis defined by a sequence of nodes across scales from a birth and to a death level of scale.

At initialization, one component is born for each node of the low- est level of scalet0. Then, each component propagates from node to node toward the highest level of scalet_N−1by favoring nodes with the highest number of shared points. At the end, every node is asso- ciated to one single component. Components can be represented by their birth and death levels in a 2D persistence diagram [ELZ00].

Finally, a thresholding on the persistence value of components per- mits to extracts principal components that are stable across scales as illustrated by Figure1.

4. Flow Lines

In order to emphasize stable anisotropic regions, we compute 3D curved lines following the direction that locally maximize the stability of the sampled geometry. This gradient descent can be seen as the integration of path lines within a 3D vector field. The vector field is computed as the minimal principal curvature direction of the scalar fields.

Figure 2: Flow lines at two different scales A subset of sampled points are se-

lected from the input point cloud using Poisson sampling. They are used as starting points to generate the flow lines. Similarly to the segmentations performed at multiple level of scale, the set of flow lines can be obtained at different level of scale. Figure2shows the result on a twisted cable where the lines highlight either the fine fibers at low scale or the whole cable at a higher scale.

5. Future Work

We plan to investigate two main points. The single-scale gradient descent (Section4) could be improved by adapting the scale as measure as a path line is generated. This would results in a scale- space gradient descent avoiding the choice of a specific subset of scales. Finally, the graph obtained from the multi-scale segmentation (Section3) seems to include lots of redundancy. Similar pat- terns in the graph corresponding to repetitive features on the 3D surface may be extracted using the graph topology only.

References

[AP10] ATTENE M., PATANÈG.: Hierarchical structure recovery of point-sampled surfaces. InComputer Graphics Forum(2010), vol. 29, Wiley Online Library, pp. 1905–1920.1

[ELZ00] EDELSBRUNNERH., LETSCHERD., ZOMORODIANA.: Topo- logical persistence and simplification. InFoundations of Computer Sci- ence. Proceedings. 41st Annual Symposium on(2000), pp. 454–463.2 [FLD18] FANGH., LAFARGEF., DESBRUNM.: Planar shape detection

at structural scales. InIEEE Conference on Computer Vision and Pattern Recognition (CVPR)(2018).1

[GG07] GUENNEBAUDG., GROSSM.: Algebraic point set surfaces. In ACM Transactions on Graphics (TOG)(2007), vol. 26, ACM, p. 23.1 [Lin94] LINDEBERG T.: Scale-Space Theory in Computer Vision.

Kluwer Academic Publishers, Norwell, MA, USA, 1994.1

[MGB^∗12] MELLADON., GUENNEBAUDG., BARLAP., REUTERP., SCHLICKC.: Growing least squares for the analysis of manifolds in scale-space. InComputer Graphics Forum(2012), vol. 31, Wiley Online Library, pp. 1691–1701.1

[PKG03] PAULYM., KEISERR., GROSS M.: Multi-scale feature ex- traction on point-sampled surfaces. InComputer graphics forum(2003), vol. 22, Wiley Online Library, pp. 281–289.1

c

2019 The Author(s) Eurographics Proceedings c2019 The Eurographics Association.

18