PaperlayerView exact revision on arXiv

Source-linked AI summary

Monte Carlo Convolution for Learning on Non-Uniformly Sampled Point Clouds

Pedro Hermosilla, Tobias Ritschel, Pere-Pau Vázquez, Àlvar Vinacua, Timo Ropinski

arXiv:1806.01759v2cs.CV

TL;DR

Existing convolution methods are not generally defined for sparse, non-uniform point clouds, whose sampling density limits prior approximations. The paper introduces Monte Carlo convolutions with MLP kernels, multilevel sampling, and Poisson disk hierarchies, and reports strong performance across segmentation, classification, and normal estimation while remaining robust to sampling variations.

  • Problem

    Convolution is well defined for structured data but remains limited for general sparse point clouds, especially when real-world acquisition produces non-uniform sampling.

  • Method

    The method represents kernels with MLPs, formulates convolution as Monte Carlo integration with density handling, combines multiple samplings, and builds hierarchies with Poisson disk sampling.

  • Results

    The approach outperforms most state-of-the-art methods on segmentation, classification, and normal-estimation benchmarks while achieving state-of-the-art performance on uniformly sampled data.

  • Takeaways & Limitations

    The networks are robust to unseen sampling variations and can obtain the best performance without data augmentation when sample density is considered.

  • Takeaways & Limitations

    The method relies on kernel density estimation to obtain the probability density function, requiring careful bandwidth selection for an accurate approximation.

Abstract

from arXiv · show

Deep learning systems extensively use convolution operations to process input data. Though convolution is clearly defined for structured data such as 2D images or 3D volumes, this is not true for other data types such as sparse point clouds. Previous techniques have developed approximations to convolutions for restricted conditions. Unfortunately, their applicability is limited and cannot be used for general point clouds. We propose an efficient and effective method to learn convolutions for non-uniformly sampled point clouds, as they are obtained with modern acquisition techniques. Learning is enabled by four key novelties: first, representing the convolution kernel itself as a multilayer perceptron; second, phrasing convolution as a Monte Carlo integration problem, third, using this notion to combine information from multiple samplings at different levels; and fourth using Poisson disk sampling as a scalable means of hierarchical point cloud learning. The key idea across all these contributions is to guarantee adequate consideration of the underlying non-uniform sample distribution function from a Monte Carlo perspective. To make the proposed concepts applicable to real-world tasks, we furthermore propose an efficient implementation which significantly reduces the GPU memory required during the training process. By employing our method in hierarchical network architectures we can outperform most of the state-of-the-art networks on established point cloud segmentation, classification and normal estimation benchmarks. Furthermore, in contrast to most existing approaches, we also demonstrate the robustness of our method with respect to sampling variations, even when training with uniformly sampled data only. To support the direct application of these concepts, we provide a ready-to-use TensorFlow implementation of these layers at https://github.com/viscom-ulm/MCCNN

1 INTRODUCTION

The paper targets convolution on non-uniformly sampled point clouds, where sampling density can compromise existing approaches. It proposes Monte Carlo-based, MLP-parameterized convolutions, multilevel sampling operations, and Poisson disk hierarchies, achieving strong results across point-cloud tasks.

  • Motivation: Non-uniform sampling in real-world point clouds has severe implications, motivating a method designed specifically for varying sample densities.The paper also targets competitive performance on uniformly sampled data.
  • Core approach: The convolution kernel is represented as a multilayer perceptron that maps spatial offsets to scalar weights.The paper motivates this representation because kernels perform precisely this offset-to-weight mapping.
  • Core approach: The method treats convolution as a Monte Carlo estimate and normalizes by sampling probability to avoid density-induced bias.Without this normalization, duplicated or unevenly distributed points can reduce learning ability.
  • Multilevel learning: The framework generalizes convolutions across resolutions and combines multiple input samplings to learn multiscale information.These operations support pooling, up-sampling, and other level-of-detail changes.
  • Multilevel learning: Poisson disk sampling constructs a scalable point hierarchy while bounding the maximum number of samples in a receptive field.The paper contrasts its scalability with Farthest Point sampling.
  • Evaluation: Experiments compare the approach with state-of-the-art methods for segmentation, classification, and normal estimation on non-uniform and uniform point clouds.The authors report outperforming state of the art on non-uniform data while retaining state-of-the-art performance on uniform data.

2 PREVIOUS WORK

Previous point-cloud learning methods use grids, neighborhood structures, graphs, lattices, or discrete kernel representations, but many remain sensitive to density, graph structure, or restricted sampling assumptions.

  • Direct point-cloud learning: Grid-based resampling enables structured-data methods but does not constitute direct learning on unstructured point clouds.The paper therefore focuses on methods operating directly on unstructured data.
  • Nonconvolutional approaches: PointNet and related methods address permutation or rotation invariance, but PointNet++ and PCP Net are not fully convolutional.PointNet++ adds localized subnetworks, while PCP Net estimates local properties such as curvature or normals.
  • Neighborhood-based methods: k-d-tree convolution is sensitive to varying density because tree leaves contain fixed numbers of points.The contrasted approach uses a regular grid for constant-time neighbor access across multiple scales.
  • Graph-based methods: Graph-based methods can remain sensitive to graph structure, while dynamic graph neighborhoods add implementation complexity and reduce efficiency on large point clouds.These limitations distinguish them from methods designed for density-aware multiscale processing.
  • Learned neighborhood transformations: PointCNN applies an MLP-learned transformation to k-nearest-neighbor features before standard image convolution.Its neighborhood construction remains based on k nearest neighbors.
  • Alternative convolution representations: Lattice and radial-basis approaches address sparse-data or uniform-resampling issues but do not fully consider non-uniform sampling settings.SPLATNet handles uneven lattice distributions by convolving a unit signal, while Atzmon et al. provide uniform-resampling invariance by construction.
  • Alternative convolution representations: MLP kernel representations were explored concurrently, but SpiderCNN reported worse performance than step functions and identified continuous parameterizations as future work.The paper reports favorable MLP performance in its own architectures.
  • Neighborhood-based methods: k-nearest-neighbor methods are sensitive to non-uniform density because neighborhoods shrink in dense regions and expand in sparse ones.This changes the spatial features captured by the learned kernel.

3 CONVOLUTION KERNELS

The paper formulates convolution kernels as MLPs that map normalized spatial offsets to learned weights, supporting compact kernels and efficient multi-output computation on point-cloud features.

  • Convolution as an integral: Convolution is defined as the integral of a feature function multiplied by a spatial kernel.The feature function may encode coordinates, color, normals, or features from previous convolutions.
  • Convolution as an integral: Compact support and receptive-field normalization provide scale handling while preserving translation invariance through dependence on relative positions.The kernel is restricted to a unit sphere and evaluated using offsets divided by the receptive-field radius.
  • Multilayer perceptron kernels: The kernel is represented by an MLP that maps normalized three-dimensional offsets to scalar weights.The offset is normalized by the receptive-field radius; the described implementation uses two hidden layers of 8 neurons.
  • Multilayer perceptron kernels: A shared MLP can output 8 kernels, reducing the number of MLPs by a factor of 8 for high-dimensional feature mappings.The multi-output design is presented as reducing computation and learnable parameters compared with separate kernels.
  • Single- and multi-feature convolution: Single-feature convolution preserves the number of features, whereas multi-feature convolution sums convolved inputs to produce output features using M × L kernels.Multi-feature layers follow the standard convolutional pattern but are more computationally demanding.

4 MONTE CARLO CONVOLUTION

The method estimates point-cloud convolutions with Monte Carlo integration, using neighborhood samples weighted by locally estimated sampling densities. Kernel Density Estimation supplies the density values needed for non-uniform samples and permits arbitrary output locations.

  • Monte Carlo integration: Monte Carlo integration estimates the convolution integral from input points or a quasi-random subset within each receptive field.The neighborhood consists of samples inside a sphere of radius r around the output point.
  • Monte Carlo integration: Each neighboring sample receives a probability-density value that depends on both its position and the receptive field centered at x.This dependence reflects the non-uniform distribution of point-cloud samples.
  • Monte Carlo integration: The output point x may be absent from the input set, enabling resampling to other levels or irregular and regular domains.The convolution is therefore not restricted to evaluating only at observed input points.
  • Estimating the PDF: Kernel Density Estimation approximates the unknown sample density, producing higher values in dense regions and lower values in sparse regions.The implementation uses bandwidth σ = .25r and a Gaussian density-estimation kernel.
  • Estimating the PDF: Density values are computed relative to all samples in each receptive field, so they cannot be precomputed per point; uniform sampling makes the density constant.The local dependence follows from the receptive-field definition used by the estimator.

5 MC CONVOLUTION ON MULTIPLE SAMPLINGS

MC convolution extends beyond identical input and output samplings to learned mappings among multiple resolutions and feature sources. Density estimation remains relative to each input sampling, while Poisson disk sampling supports scalable hierarchies.

  • Multiple samplings: MC convolution handles convolution between two or multiple different samplings, including distinct input and output point sets.This generalizes the single-sampling case without requiring matching sample locations.
  • Multiple samplings: Different-sampling mappings support learned upsampling, downsampling, pooling, and transposed convolution in hierarchical architectures.The output can be formed at a higher or lower resolution than the input.
  • Multiple samplings: Density estimation is performed relative to each input sampling when processing multiple-sampling inputs.Samples from A and B therefore use their respective local density estimates.
  • Multiple samplings: The method can combine inputs from mutually different samplings and feature channels into a common output sampling.A typical use combines information from multiple resolutions in a hierarchy.
  • Point hierarchies: Poisson disk sampling constructs a scalable point hierarchy and bounds the maximum number of samples in a receptive field.The hierarchy uses receptive-field and Poisson-disk relationships to control neighborhood sizes across levels.
  • Point hierarchies: The receptive-field size can vary across samplings so each neighborhood contains roughly a constant number of points, with density estimation compensating residual variation.This permits scale-specific receptive fields while retaining density correction.

6 POISSON DISK HIERARCHY

The paper favors Poisson disk sampling for scalable, hierarchical point-cloud learning because it preserves non-uniformity while controlling sample spacing and receptive-field occupancy.

  • Poisson disk sampling: Poisson disk sampling preserves the sampling pattern while providing scalability and a minimum-distance constraint between samples.Its network-layer realization outputs samples separated by the Poisson disk radius r_p.
  • Hierarchical construction: Multiple Poisson disk layers form a multi-resolution hierarchy that supports encoder-decoder networks with multi-samplings convolutions.
  • Practical constraint: Poisson disk sampling generates a non-fixed number of samples, preventing use of frameworks that reserve forward-pass memory in advance.The networks nevertheless achieve good performance despite this constraint.
  • Scalability: Poisson disk sampling scales linearly with model point count, whereas farthest-point sampling requires more than 100 seconds for 100 k samples from a 1,000 k-point model.
  • Sample-count bound: Poisson disk sampling retains non-uniformity while bounding the number of points within a receptive field through minimum-distance packing.The bound applies to balls of radius r_p packed inside a receptive field of radius r.
  • Sampling scales: Maintaining a ratio between receptive-field radius and sampling radius of 4 to 8 provides approximately 30 samples in receptive fields.

7 IMPLEMENTATION

The implementation supports variable-size point clouds and Monte Carlo convolutions through probability precomputation, neighbor lookup structures, and memory-efficient GPU kernels.

  • Monte Carlo computation: Monte Carlo convolution divides neighboring values by their sampling probabilities, requiring probability computation and lookup in addition to averaging.
  • Probability computation: A voxel grid computes sampling probabilities in time and space linear in the number of points.Hashing could provide further scalability beyond the regular grid.
  • Neighbor lookup: Flat neighbor-index and probability lists enable constant-time lookup, but can become arbitrarily long at high density and large receptive-field radius.
  • Sampling randomness: Parallel GPU voxelization introduces different within-cell point orderings across executions, creating randomness in Poisson disk outputs that is preferred during learning.
  • MLP evaluation: A single GPU kernel evaluates the MLP without expanding neighboring features and coordinates, addressing the memory demands of standard implementations.
  • Batch processing: Variable-size inputs and all-neighbor convolutions prevent standard tensor-based parallel batch processing.The implementation instead uses a model identifier for each point and maintains separate acceleration structures per model.

8 EVALUATION

The evaluation tests classification, segmentation, and normal estimation under uniform and artificially generated non-uniform sampling protocols. The method generally remains competitive or outperforms comparison networks, including when trained only on uniform data.

  • Evaluation setup: The evaluation introduces artificially non-uniform samplings from uniformly sampled point clouds to study sampling effects explicitly.Five rejection-sampling protocols are used: Uniform, Split, Gradient, Lambertian, and Occlusion.
  • Classification: 90.9 %, 87.6 % and 87.3 % accuracy were achieved on Uniform, Split and Gradient protocols, versus 89.1 %, 84.4 % and 79.7 % for PointNet++ when training only on uniform data.
  • Classification: When trained on non-uniform data, MC achieved 90.1 % to 90.6 % accuracy across protocols, compared with 89.1 % to 89.8 % for PointNet++.
  • Comparison networks: The MC network outperformed AVG in the reported comparisons, while AVG showed greater difficulty generalizing and severe over-fitting.
  • Segmentation: The segmentation network achieved 85.9 on uniform data, slightly below PointCNN’s 86.1, but exceeded PointNet++ across all non-uniform protocols.
  • Classification: MC accuracy was higher than AVG on Uniform and Gradient protocols but lower on Split, Lambertian and Occlusion, with small differences overall.
  • Normal estimation: MC convolutions outperformed PointNet++ across all non-uniform protocols for normal estimation when trained on both uniform and non-uniform point clouds.On uniform data, the method achieved mean cosine distance .16 versus .19 reported by Atzmon et al.
  • Large-scale evaluation: The method achieved 62.5 % mean per-class voxel accuracy, compared with 60.2 % for PointNet++ and 50.8 % for ScanNet.

9 LIMITATIONS

The method has two main limitations: estimating sampling density with KDE and balancing locality against Monte Carlo estimator variance.

  • KDE-based probability density estimation requires careful bandwidth selection to approximate the sampling PDF reliably.The authors suggest cross-validation, ballooning, or automated bandwidth selection as future improvements.
  • Small receptive fields improve locality and computation speed but produce noisier convolution estimates.
  • Large receptive fields reduce estimator noise but are slower and less localized.

10 CONCLUSIONS

The paper concludes that Monte Carlo convolution supports strong learning results on non-uniform point clouds by modeling sampling density and hierarchical resampling. It also emphasizes robustness to unseen sampling patterns while identifying higher-dimensional inputs as future work.

  • Monte Carlo convolution, MLP kernels, density correction, Poisson disk pooling, and MC resampling together support superior results on segmentation, classification, and normal estimation.
  • The model generalizes robustly to unseen sampling patterns, which the authors identify as important for real-world point-cloud applications.
  • Future work includes extending the approach to animated point clouds and point clouds with additional attributes such as color.

A ARCHITECTURES A.1 Classification

The classification architecture builds a multi-level point hierarchy with spatial convolutions, feature-mixing 1 × 1 convolutions, and Poisson disk sampling. A second pathway is added to improve robustness under poor sampling.

  • Architecture: Each hierarchy level convolves features, applies Poisson disk sampling, and downsamples to compute features for the next level.
  • Architecture: 1 × 1 convolutions combine features between deeper single-feature spatial convolutions.
  • Hierarchy: The network forms four hierarchy levels, ending in a single-point representation when the final sampling radius spans the bounding-box diagonal.
  • Output: The final feature vector is processed by a two-hidden-layer MLP to produce the model representation.
  • Robustness: A replicated shorter pathway combines probability vectors with the main pathway to increase robustness under poor samplings.
  • Training: Training uses cross-entropy loss and Adam with dropout applied to final MLPs and point features.

A.2 Segmentation

The segmentation architectures use encoder-decoder hierarchies built with Poisson disk sampling and task-specific assumptions. Semantic segmentation adapts radii to room scale and limits early computation to reduce operations and memory.

  • Segmentation: The segmentation network uses a four-level hierarchy generated by Poisson disk sampling with radii .025, .1, and .4.
  • Segmentation: The segmentation setup assumes the model class is known and concatenates its one-hot encoding before the final MLP predicts part probabilities.
  • Segmentation: Training uses cross-entropy loss, Adam, dropout, and point dropout over 90 epochs.
  • Normal estimation: The normal-estimation network uses a three-level encoder-decoder hierarchy with Poisson disk radii .1 and .4.
  • Semantic segmentation: Semantic segmentation uses five Poisson-disk levels with radii .1, .2, .4, and .8 meters for rooms of varying size.
  • Semantic segmentation: To reduce operations and memory, semantic segmentation omits convolution at the first hierarchy level and pools directly into the second.
  • Semantic segmentation: Semantic segmentation training uses point dropout, weight decay, and dropout over 100 epochs.
  • Semantic segmentation: Variable-size room inputs are batched by filling a budget of 600 k points rather than using a fixed number of rooms.
Loading 1806.01759v2…