PaperlayerView exact revision on arXiv

Source-linked AI summary

Grid-GCN for Fast and Scalable Point Cloud Learning

Qiangeng Xu, Xudong Sun, Cho-Ying Wu, Panqu Wang, Ulrich Neumann

arXiv:1912.02984v5cs.CVcs.LG

TL;DR

Point-based GCNs preserve point granularity and relationships but are limited by costly data structuring, affecting speed and scalability. Grid-GCN introduces coverage-aware voxel querying and grid-context aggregation, achieving state-of-the-art accuracy and speed across classification and segmentation benchmarks, including real-time ScanNet processing.

  • Problem

    Point-based GCNs incur substantial data-structuring costs from operations such as FPS and neighbor querying, limiting speed and scalability.

  • Method

    Grid-GCN uses Coverage-Aware Grid Query for voxel-based center sampling and neighborhood querying, together with Grid Context Aggregation for local context graph convolution.

  • Results

    Grid-GCN achieves state-of-the-art performance across classification and segmentation benchmarks, including 93.1% classification accuracy, average 5× faster classification, and 10× faster segmentation.

  • Takeaways & Limitations

    Grid-GCN supports large-scale real-time point-cloud learning, processing 81920 ScanNet points per scene within 20 ms.

  • Takeaways & Limitations

    Volumetric comparisons remain constrained because MinkowskiNet does not report overall accuracy and its ScanNet latency is cited from a GitHub example.

Abstract

from arXiv · show

Due to the sparsity and irregularity of the point cloud data, methods that directly consume points have become popular. Among all point-based models, graph convolutional networks (GCN) lead to notable performance by fully preserving the data granularity and exploiting point interrelation. However, point-based networks spend a significant amount of time on data structuring (e.g., Farthest Point Sampling (FPS) and neighbor points querying), which limit the speed and scalability. In this paper, we present a method, named Grid-GCN, for fast and scalable point cloud learning. Grid-GCN uses a novel data structuring strategy, Coverage-Aware Grid Query (CAGQ). By leveraging the efficiency of grid space, CAGQ improves spatial coverage while reducing the theoretical time complexity. Compared with popular sampling methods such as Farthest Point Sampling (FPS) and Ball Query, CAGQ achieves up to 50X speed-up. With a Grid Context Aggregation (GCA) module, Grid-GCN achieves state-of-the-art performance on major point cloud classification and segmentation benchmarks with significantly faster runtime than previous studies. Remarkably, Grid-GCN achieves the inference speed of 50fps on ScanNet using 81920 points per scene as input.

1. Introduction

Point-based GCNs preserve point granularity and local relationships but incur substantial data-structuring costs. Grid-GCN addresses this with CAGQ for efficient, coverage-aware grouping and GCA for local graph aggregation.

  • Motivation: Point-based models preserve accurate point locations, but GCN architectures incur high costs from FPS and k-NN data structuring.Data structuring can reach up to 88% of overall computational cost in three popular point-based models.
  • Grid-GCN: Grid-GCN processes point clouds through GridConv layers that structure data before aggregating local graph information.Each layer samples representative centers, queries neighboring points, builds a local graph, and aggregates information to the center.
  • CAGQ: CAGQ accelerates center sampling and neighbor querying by voxelizing points and computing only on occupied areas.It is designed to provide more complete point-cloud coverage while reducing data-structuring overhead.
  • GCA: GCA performs graph convolution over point groups by aggregating local grid context for edge-relation computation without extra overhead.Grid context pooling extracts neighborhood context features used in edge relation computation.
  • Results: 93.1% overall accuracy without voting and average 5× faster runtime were reported on ModelNet10 and ModelNet40 classification.Grid-GCN also achieved average 10× speed-up on ScanNet and S3DIS segmentation tasks.
  • Results: 81920 points per ScanNet scene were processed within 20 ms, demonstrating large-scale real-time point-based learning.This corresponds to an inference speed of 50 fps.

2. Related Work

Prior point-cloud methods trade off data granularity, computational efficiency, and data-structuring cost. Grid-GCN combines grid-based organization with point-group graph processing and coverage-aware querying.

  • Voxel-based methods: Volumetric methods use occupancy grids and volumetric convolution, but high resolution increases memory and computation while empty voxels waste processing.Approximately 90% of voxels are empty for most point clouds.
  • Point-based methods: Point-based methods preserve point information and permutation invariance, but their computation or data structuring becomes costly as point counts grow.PointNet’s computation cost grows linearly with the number of points, while later methods downsample into representative group centers.
  • Data structuring strategies: FPS selects widely separated centers but can require O(N^2) computation, whereas RPS has low overhead but is sensitive to density imbalance.An approximate FPS algorithm can reduce complexity to O(NlogN).
  • GCN for point cloud learning: Graph convolutional methods build local graphs and aggregate point data through geometric or semantic relations between centers and nodes.Grid Context Aggregation additionally uses coverage and context features to compute semantic relations.
  • Data structuring strategies: CAGQ combines grid organization with point-group sampling by selecting occupied voxels, querying neighborhood context points, and computing group centers.Its figure contrasts voxel-based center selection and neighborhood querying with FPS, RPS, and Ball Query.

3. Methods

Grid-GCN’s GridConv layers combine voxel-based CAGQ structuring with graph-based GCA aggregation. CAGQ selects covered center voxels and neighboring nodes, while GCA aggregates node features using geometric, semantic, and coverage context.

  • GridConv: GridConv maps N input points to M group centers through CAGQ structuring and GCA aggregation, with upsampling layers supporting segmentation.Downsampling layers use N > M, while upsampling layers use N < M.
  • Coverage-Aware Grid Query: CAGQ voxelizes the input, stores up to nv points per occupied voxel, retrieves neighboring context points, and computes each group center from K node-point barycenters.For each center voxel, context points come from neighboring voxels and are queried for node selection.
  • Coverage-Aware Grid Query: CAGQ offers Random Voxel Sampling, Cube Query, and context-restricted K-nearest-neighbor querying to address center selection and node selection.Cube Query can cover more space than Ball Query under imbalanced point densities, while restricted KNN searches only context points.
  • Coverage-Aware Grid Query: Coverage-Aware Sampling greedily replaces incumbent center voxels with challengers when the coverage gain exceeds the coverage loss.With β set to 0, each replacement is guaranteed to improve space coverage.
  • Grid Context Aggregation: GCA constructs a local center-node graph, transforms node features, computes edge-aware contributions, and aggregates them into the group-center feature.Its edge attention incorporates node location, feature information, coverage weight, and pooled context features.
  • Grid Context Aggregation: Coverage weight records how many previous-layer points contributed to each node, while grid context pooling supplies a semantic reference from stored neighboring points.The pooled context feature is shared across edge computations and adds little computational overhead.

4. Analysis of CAGQ

CAGQ combines voxel-based sampling and querying to improve point-cloud coverage while reducing data-structuring latency. Its CAS and RVS variants outperform FPS in coverage or speed across the tested conditions.

  • Experimental Setup: The analysis varies input points N, neighbors per group K, and point groups M when comparing sampling and querying methods.Compared methods include RPS, FPS, RVS, CAS, Ball Query, Cube Query, and k-NN.
  • Space Coverage: CAS covers 75.2% of occupied space, exceeding RPS at 45.6% and FPS at 65%.CAS leads space coverage in all tested cases and provides 30% more coverage than RPS.
  • Space Coverage: RVS samples center voxels from occupied space, making it more resilient to point-density imbalance than point-based sampling.CAGQ also distributes points evenly across occupied voxels, reducing local coverage loss.
  • Latency: CAS achieves 50× speed-up over FPS, while CAS with Cube Query can outperform RPS with Ball Query on large point clouds.The advantage is attributed to faster neighborhood querying and better time complexity.
  • Latency: RVS with k-NN achieves 6× speed-up over FPS with k-NN and leads across all tested conditions.The reported advantage follows from the better time complexity of the voxel-based approach.

5. Experiments

Grid-GCN is evaluated on object classification and scene segmentation, including accuracy, latency, scalability, and ablations. Across these settings, it delivers state-of-the-art performance with faster inference and improved large-scale processing.

  • 5.1. 3D Object Classification: Grid-GCN achieves state-of-the-art accuracy on ModelNet10 and ModelNet40 while offering the best speed-accuracy trade-off across four settings.The experiments use different feature-channel and first-layer group-node configurations, and results are reported without voting.
  • 5.2. 3D Scene Segmentation: The S3DIS evaluation trains on areas 1–4 and 6 and tests on area 5, while ScanNet uses 1201 training scenes and 312 test scenes.ScanNet training samples 8192 points, and S3DIS training samples 4096 points per divided section.
  • 5.2. 3D Scene Segmentation: 10× average speed-up is achieved on ScanNet segmentation compared with other models while maintaining state-of-the-art accuracy.The comparison includes full and compact models using different numbers of neighbor nodes.
  • 5.2. 3D Scene Segmentation: 4× to 14× faster runtime is achieved on S3DIS by compact Grid-GCN, which is also 1.6× faster than PointNet with a 12% mIOU gain.The full model remains fastest and achieves 2× speed-up over PVCNN++.
  • 5.3. Ablation Studies: 37% speed-up follows from reducing feature channels, whereas reducing K or removing Grid context pooling provides little speed benefit but lowers accuracy.Coverage weight adds little latency while increasing overall accuracy.
  • 5.3.1 Scalability Analysis: 11× speed-up over PointNet++ is achieved when ScanNet input increases from 4096 to 81920 points.At 2048 points, the two models have similar latency; the comparison uses batch size 1.

6. Conclusion

The paper concludes that Grid-GCN combines efficient data structuring and computation through CAGQ with context-aware graph convolution through GCA. It reports state-of-the-art accuracy and speed across benchmarks, supporting large-scale real-time point cloud processing applications.

  • 6. Conclusion: CAGQ reduces data-structuring cost through voxelization while providing point groups with complete point-cloud coverage.GCA incorporates context features and coverage information into graph convolution.
  • 6. Conclusion: Grid-GCN achieves state-of-the-art accuracy and speed across various point cloud benchmarks.The conclusion connects these results to large-scale real-time point cloud processing applications.

A. Time complexity deductions of center sampling/node querying methods

The paper analyzes center-sampling and neighbor-querying complexity under a constant voxel-neighbor parameter. It reports quadratic complexity for FPS in the relevant regime and linear reporting for practical random sampling.

  • Center sampling methods: RPS is reported as O(N) in practice because MlogM has the same or smaller magnitude as N.The general expression is O(min(N, MlogM)).
  • Center sampling methods: FPS has O(N^2) complexity on a finite point set when M is not extremely small.The passage also notes an approximate algorithm with O(NlogN) complexity.

B. Training Details

The experiments use dataset-specific training schedules and GridConv configurations. CAGQ structures groups by voxel indexing, center-voxel sampling, neighborhood retrieval, and coverage-weighted center calculation.

  • Training setup: Adam uses beta1 = 0.9 and beta2 = 0.999 across all four datasets, with batch normalization and one RTX 2080 GPU.
  • Training setup: ModelNet10 and ModelNet40 use two downsampling GridConv layers with 1024 and 128 point groups, followed by a global GridConv layer.Training starts at learning rate 0.001, decays by 0.7 every 60 epochs, and stops at 330 epochs without weight decay.
  • Training setup: ScanNet uses three downsampling and three upsampling GridConv layers, with 1024, 256, and 24 point groups in the downsampling layers.The learning rate decays by 0.7 every 150 epochs through 1500 epochs, and weight decay is 10^-5.
  • Training setup: S3DIS uses three downsampling and three upsampling GridConv layers, with 512, 256, and 24 point groups in the downsampling layers.The learning rate decays by 0.8 every 40 epochs through 200 epochs, and weight decay is 10^-8.
  • CAGQ procedure: CAGQ k-NN restricts candidates to neighboring points, searches inner voxel layers first, and avoids sorting when a layer contains fewer than the remaining required points.The search stops once K points have been collected.
  • CAGQ procedure: CAGQ builds a voxel-point index, samples center voxels, retrieves neighboring context points, and selects node points from voxel neighborhoods.Cube Query or k-NN can be used for neighborhood retrieval, while RVS or CAS can be used for center-voxel sampling.
  • Center calculation: Each point group’s center is the coverage-weighted barycenter of its K node points, with coverage weight wc computed by summing node-point weights.

F. Performance comparisons of data structuring methods (more conditions)

The paper evaluates data-structuring methods under varied point, group, and neighborhood conditions on ModelNet40, reporting occupied-space coverage and latency.

  • Comparison design: Coverage is reported for center-sampling methods combined with Ball Query or Cube Query, because k-NN targets nearest neighbors rather than evenly spread node points.The remaining sections report latency.
  • Comparison design: Table 9 compares RPS, FPS, CAGQ’s RVS and CAS, plus Ball Query, Cube Query, and k-Nearest Neighbors under varied N, M, and K settings.Occupied space coverage is the fraction of occupied queried voxels relative to the original point cloud’s occupied voxels.

G. Performance on each object class and more visual results of S3DIS

The S3DIS area 5 evaluation reports per-class segmentation quality and visual predictions from the full Grid-GCN model. Grid-GCN performs accurately on several objects but can confuse boundaries between planar surfaces.

  • Visual results: Visualizations show accurate predictions for chairs and tables, while borders between planar objects such as boards and walls are sometimes mislabeled.The visual results come from the full Grid-GCN model.
  • Per-class results: Grid-GCN achieves the highest overall accuracy and mean class IoU among four models on S3DIS area 5.Table 10 also reports per-class IoU for each object category.
  • Visual results: Figures 7 and 8 provide additional visual results for S3DIS area 5.
Loading 1912.02984v5…