Source-linked AI summary
3D Semantic Segmentation with Submanifold Sparse Convolutional Networks
Benjamin Graham, Martin Engelcke, Laurens van der Maaten
TL;DR
Dense convolutional networks are inefficient for sparse high-dimensional data, and prior sparse convolutions can progressively dilate active regions. The paper introduces submanifold sparse convolutions and SSCNs for 3D point-cloud semantic segmentation, reporting superior performance across tasks and computational efficiency.
Problem
Dense convolutional networks are inefficient for sparse high-dimensional data, while prior sparse convolutions can rapidly increase active sites across deep networks.
Method
The paper introduces submanifold sparse convolutions that preserve active-site locations and uses them with strided sparse convolutions in FCN and U-Net architectures for 3D point-cloud segmentation.
Results
SSCNs outperform state-of-the-art approaches for semantic segmentation of object parts and larger scenes and are computationally efficient compared with alternatives.
Takeaways & Limitations
Preserving sparsity makes deep, efficient networks practical for point-wise semantic segmentation of low-dimensional data embedded in higher-dimensional space.
Takeaways & Limitations
Shape-context FLOP comparisons omit the integer-arithmetic cost of calculating shape-context features, making those reported costs potentially misleading.
Abstract
from arXiv · showhide
Convolutional networks are the de-facto standard for analyzing spatio-temporal data such as images, videos, and 3D shapes. Whilst some of this data is naturally dense (e.g., photos), many other data sources are inherently sparse. Examples include 3D point clouds that were obtained using a LiDAR scanner or RGB-D camera. Standard "dense" implementations of convolutional networks are very inefficient when applied on such sparse data. We introduce new sparse convolutional operations that are designed to process spatially-sparse data more efficiently, and use them to develop spatially-sparse convolutional networks. We demonstrate the strong performance of the resulting models, called submanifold sparse convolutional networks (SSCNs), on two tasks involving semantic segmentation of 3D point clouds. In particular, our models outperform all prior state-of-the-art on the test set of a recent semantic segmentation competition.
1 Introduction
Sparse high-dimensional data makes conventional dense convolution inefficient, motivating operations and networks that preserve sparsity for 3D point-cloud segmentation. SSCNs outperform top-performing entries in a recent part-based segmentation competition.
- Motivation: 3D and higher-dimensional grids can contain sparse data, making sparsity important for reducing computational resources.The number of grid points grows exponentially with dimensionality, especially in structures such as sparsely populated 4D RGB-D videos.
- Motivation: Traditional convolutional implementations cannot process sparse data efficiently, while prior sparse methods reduce FLOPs and/or memory.Prior approaches restrict computation and storage to active sites, but still apply full convolutions that dilate sparse data.
- Contribution: SSCNs use sparse convolutions and a submanifold sparse convolution operator to keep the same sparsity level throughout the network.The networks are optimized for efficient semantic segmentation of 3D point clouds.
- Results: SSCNs outperform all compared top-performing entries on the test set of a recent part-based segmentation competition.The paper also reports that source code for the sparse-convolution library is publicly available online.
2 Related Work
Related work includes sparse and dense convolutional approaches, voxel-free point-cloud methods, and multiscale segmentation architectures. The paper distinguishes SSCNs by fixing active-site locations across many layers for efficient point-wise segmentation.
- Dense convolutions: Dense 3D convolutional methods suffer from high memory usage and slow inference, limiting the size of models that can be used.The related-work discussion identifies these computational obstacles as one reason point-cloud methods often avoid dense 3D convolutions.
- Sparse convolutions: Prior sparse convolutional operators increase the number of active sites with each layer, whereas SSCs keep active-site locations unchanged for many layers.This fixed sparsity makes deep networks resembling VGG networks or ResNets practical for point-wise semantic segmentation.
- Sparse convolutions: OctNets store sparse voxels in oct-trees and still compute on surfaces of empty regions, whereas submanifold convolutions perform no calculations in empty regions.For an empty cube of size 8^3, a size-3 OctNet convolution requires 2^3% of dense 3D convolution calculation.
- Point-cloud processing: Voxel-free methods process point clouds with Kd-trees or directly as unordered point sets, avoiding voxelization and its possible information loss.Kd-Networks construct a tree in O(N log N) time, while PointNet uses pooling to produce a global feature vector.
- Segmentation architectures: FCNs preserve low-level information through multiscale processing, and U-Nets use convolutions to merge information from different scales before classification.These architectures originated in 2D image segmentation and motivate related segmentation designs.
3 Spatial sparsity for ConvNets
Sparse convolutional networks define activity over spatial sites, but ordinary convolutions rapidly expand active regions. This submanifold dilation problem limits deep architectures on low-dimensional structures embedded in higher-dimensional grids.
- Sparse representations: A d-dimensional convolutional network represents d spatial or temporal dimensions plus one feature-space dimension.Each grid site carries a feature vector, and activity is determined spatially rather than along the feature dimension.
- Sparse representations: A site is active when any feature-vector element is outside the ground state, while inactive sites share the ground-state feature vector.The ground state need not be zero when convolutions use a bias term.
- Activity propagation: Hidden-layer activity is propagated when any input site connected to a location is active, so inactive sites retain the ground-state vector.With size-3 convolutions, each site is connected to 3^d sites in the preceding hidden layer.
- Submanifold dilation problem: Ordinary convolutions rapidly expand active sites across layers, creating a submanifold dilation problem for deep networks.A single active site produces 3^d active sites after one convolution and 5^d after a second convolution of the same size.
4 Submanifold Convolutional Networks
The section introduces sparse and submanifold sparse convolutions that reduce computation while preserving the spatial pattern of active sites. These operators support efficient deep sparse networks, with pooling and striding enabling information flow between disconnected components.
- Motivation: Regular convolutions rapidly reduce feature sparsity through repeated applications, creating the submanifold dilation problem.Even small 3 × 3 convolutions can cause sparsity to disappear quickly on curves or surfaces.
- Network Construction: Pooling and strided convolutions are essential because they allow information to flow between disconnected active components.Without such operations, neighboring connected components can be treated independently by restricted sparse convolutions.
- Sparse Convolution: SC identifies active output sites from receptive-field activity, while discarding ground-state inputs at non-active sites to reduce computation.The output size follows the convolution filter size and stride, as in a regular convolution.
- Submanifold Convolution: SSC restricts active outputs to locations that are active in the input, preserving sparsity across layers.It pads the input to retain spatial size and computes features only at corresponding active sites.
- Implementation: SSC preserves sparsity like OctNets, but empty space adds no computational or memory overhead in its implementation.The implementation reuses the input hash table and rule book across networks until pooling or subsampling changes the sparsity pattern.
- Implementation: For FCN and U-Net architectures, constructing all hash tables and rule books costs O(a) when active sites decrease multiplicatively during downsampling.Here, a denotes the number of active points in the input layer.
5 Submanifold FCNs and U-Nets for Semantic Segmentation
The paper applies SSC and strided SC convolutions to sparse voxelized 3D point clouds, building FCN and U-Net architectures for semantic segmentation. The models use pre-activated SSC blocks and residual variants.
- Task and Representation: The models segment 3D objects or scenes represented as point clouds by assigning each input point a part label.The approach uses a sparse voxelized input representation.
- Architectures: SSCNs combine SSC convolutions with strided SC convolutions to construct sparse versions of FCN and U-Net architectures.These networks are designed for low-dimensional data embedded in higher-dimensional spaces.
- Network Blocks: The basic model block is a pre-activated SSC(·, ·, 3) convolution preceded by batch normalization and a ReLU nonlinearity.Residual variants use blocks containing two SSC(·, ·, 3) convolutions with identity residual connections.
6 Experiments
Experiments evaluate SSCNs against sparse, dense, and multi-view baselines on ShapeNet, under randomized poses and varying computational budgets, and also test NYU Depth scenes. SSCNs generally deliver higher segmentation accuracy with lower computational cost, while downsampling architectures perform best among SSCN variants.
- Experimental setup: Experiments compare SSCNs with shape contexts, dense 3D convolutional networks, and 2D multi-view convolutional networks on ShapeNet and NYU Depth v2.The evaluation focuses on segmentation accuracy and computational efficiency measured in FLOPs.
- Experimental setup: ShapeNet objects are randomly translated and rotated, making segmentation more challenging than on the original axis-aligned dataset.The evaluation uses the intersection-over-union metric, averaged across part classes and categories.
- ShapeNet results: 6-8% higher average IoU at 10^8 FLOPs: SSCNs substantially outperform shape contexts, multi-view 2D ConvNets, and dense 3D ConvNets.The baselines perform roughly on par in accuracy per FLOP, while SSCNs retain performance despite restricting information to submanifolds.
- Architecture ablation: FCNs and U-Nets outperform single-resolution C3 SSCNs, which the authors conjecture results from the larger receptive field obtained through downsampling.The comparison covers the three SSCN architecture types.
- Scale ablation: SSCN performance is similar across voxel scales, although larger scales perform slightly better at higher FLOP counts.At scale S = 48, the voxelized representations are approximately 99% sparse.
- Competition results: 85.98% test error: the FCN SSCN outperforms other competition methods by ≥0.49% IoU on aligned point clouds with 10-view testing.This configuration uses S = 24, 64 input filters, three downsampling levels, residual blocks, and random affine augmentation.
- Scene segmentation: Up to 7% higher pixel accuracy than 2D FCN: SSCNs also substantially reduce computational costs on NYU Depth v2.Testing computes probabilities only for part labels appearing in each object, assuming the object category is known.
7 Conclusions
The paper presents SSCNs for efficient processing of high-dimensional sparse data and demonstrates their efficacy on 3D point-cloud semantic segmentation. SSCNs outperform state-of-the-art alternatives across object-part and scene recognition tasks while remaining computationally efficient.
- Conclusions: SSCNs process high-dimensional sparse input data efficiently using submanifold sparse convolutions.The paper evaluates them on semantic segmentation of three-dimensional point clouds.
- Conclusions: SSCNs outperform a range of state-of-the-art approaches for both object-part segmentation and object recognition in larger scenes.The conclusion also reports computational efficiency compared with alternative approaches.