Submanifold Sparse Convolutional Networks

This is the PyTorch library for training Submanifold Sparse Convolutional Networks.

Spatial sparsity

This library brings Spatially-sparse convolutional networks to PyTorch. Moreover, it introduces Submanifold Sparse Convolutions, that can be used to build computationally efficient sparse VGG/ResNet/DenseNet-style networks.

With regular 3x3 convolutions, the set of active (non-zero) sites grows rapidly:

With Submanifold Sparse Convolutions, the set of active sites is unchanged. Active sites look at their active neighbors (green); non-active sites (red) have no computational overhead:

Stacking Submanifold Sparse Convolutions to build VGG and ResNet type ConvNets, information can flow along lines or surfaces of active points.

Disconnected components don't communicate at first, although they will merge due to the effect of strided operations, either pooling or convolutions. Additionally, adding ConvolutionWithStride2-SubmanifoldConvolution-DeconvolutionWithStride2 paths to the network allows disjoint active sites to communicate; see the 'VGG+' networks in the paper.

From left: (i) an active point is highlighted; a convolution with stride 2 sees the green active sites (ii) and produces output (iii), 'children' of hightlighted active point from (i) are highlighted; a submanifold sparse convolution sees the green active sites (iv) and produces output (v); a deconvolution operation sees the green active sites (vi) and produces output (vii).

Dimensionality and 'submanifolds'

SparseConvNet supports input with different numbers of spatial/temporal dimensions. Higher dimensional input is more likely to be sparse because of the 'curse of dimensionality'.

Dimension	Name in 'torch.nn'	Use cases
1	TemporalConvolution	Text, audio
2	SpatialConvolution	Lines in 2D space, e.g. handwriting
3	VolumetricConvolution	Lines and surfaces in 3D space or (2+1)D space-time
4	-	Lines, etc, in (3+1)D space-time

We use the term 'submanifold' to refer to input data that is sparse because it has a lower effective dimension than the space in which it lives, for example a one-dimensional curve in 2+ dimensional space, or a two-dimensional surface in 3+ dimensional space.

In theory, the library supports up to 10 dimensions. In practice, ConvNets with size-3 SVC convolutions in dimension 5+ may be impractical as the number of parameters per convolution is growing exponentially. Possible solutions include factorizing the convolutions (e.g. 3x1x1x..., 1x3x1x..., etc), or switching to a hyper-tetrahedral lattice (see Sparse 3D convolutional neural networks).

Hello World

SparseConvNets can be built either by defining a function that inherits from torch.nn.Module or by stacking modules in a sparseconvnet.Sequential:

import torch
import sparseconvnet as scn

# Use the GPU if there is one, otherwise CPU
use_gpu = torch.cuda.is_available()

model = scn.Sequential().add(
    scn.SparseVggNet(2, 1,
		     [['C',  8], ['C',  8], ['MP', 3, 2],
		      ['C', 16], ['C', 16], ['MP', 3, 2],
		      ['C', 24], ['C', 24], ['MP', 3, 2]])
).add(
    scn.SubmanifoldConvolution(2, 24, 32, 3, False)
).add(
    scn.BatchNormReLU(32)
).add(
    scn.SparseToDense(2,32)
)
if use_gpu:
    model.cuda()

# output will be 10x10
inputSpatialSize = model.input_spatial_size(torch.LongTensor([10, 10]))
input = scn.InputBatch(2, inputSpatialSize)

msg = [
    " X   X  XXX  X    X    XX     X       X   XX   XXX   X    XXX   ",
    " X   X  X    X    X   X  X    X       X  X  X  X  X  X    X  X  ",
    " XXXXX  XX   X    X   X  X    X   X   X  X  X  XXX   X    X   X ",
    " X   X  X    X    X   X  X     X X X X   X  X  X  X  X    X  X  ",
    " X   X  XXX  XXX  XXX  XX       X   X     XX   X  X  XXX  XXX   "]

#Add a sample using set_location
input.add_sample()
for y, line in enumerate(msg):
    for x, c in enumerate(line):
	if c == 'X':
	    location = torch.LongTensor([x, y])
	    featureVector = torch.FloatTensor([1])
	    input.set_location(location, featureVector, 0)

#Add a sample using set_locations
input.add_sample()
locations = []
features = []
for y, line in enumerate(msg):
    for x, c in enumerate(line):
	if c == 'X':
	    locations.append([x,y])
	    features.append([1])
locations = torch.LongTensor(locations)
features = torch.FloatTensor(features)
input.set_locations(locations, features, 0)

model.train()
if use_gpu:
    input.cuda()
output = model.forward(input)

# Output is 2x32x10x10: our minibatch has 2 samples, the network has 32 output
# feature planes, and 10x10 is the spatial size of the output.
print(output.size(), output.type())

Examples

Examples in the examples folder include

For example:

cd examples/Assamese_handwriting
python VGGplus.py

Setup

Tested with Ubuntu 16.04, Python 3.6 in Miniconda and PyTorch 1.0.

conda install pytorch-nightly -c pytorch # See https://pytorch.org/get-started/locally/
conda install google-sparsehash -c bioconda   # OR apt-get install libsparsehash-dev
conda install -c anaconda pillow
git clone git@github.com:facebookresearch/SparseConvNet.git
cd SparseConvNet/
bash develop.sh

To run the examples you may also need to install unrar:

apt-get install unrar

License

SparseConvNet is Attribution-NonCommercial 4.0 International licensed, as found in the LICENSE file.

Citations

If you find this code useful in your research then please cite:

3D Semantic Segmentation with Submanifold Sparse Convolutional Networks, CVPR 2018
Benjamin Graham,
Martin Engelcke,
Laurens van der Maaten,

@article{3DSemanticSegmentationWithSubmanifoldSparseConvNet,
  title={3D Semantic Segmentation with Submanifold Sparse Convolutional Networks},
  author={Graham, Benjamin and Engelcke, Martin and van der Maaten, Laurens},
  journal={CVPR},
  year={2018}
}

and/or

Submanifold Sparse Convolutional Networks, https://arxiv.org/abs/1706.01307
Benjamin Graham,
Laurens van der Maaten,

@article{SubmanifoldSparseConvNet,
  title={Submanifold Sparse Convolutional Networks},
  author={Graham, Benjamin and van der Maaten, Laurens},
  journal={arXiv preprint arXiv:1706.01307},
  year={2017}
}

QiuLiru/SparseConvNet