Source-linked AI summary
Escape from Cells: Deep Kd-Networks for the Recognition of 3D Point Cloud Models
Roman Klokov, Victor Lempitsky
TL;DR
3D recognition needs scalable alternatives to ConvNets built on uniform grids, whose memory and processing demands limit fine-grained and high-resolution applications. The paper introduces Kd-networks, which use kd-trees for computation and parameter sharing, and reports competitive performance across several recognition tasks with greater efficiency.
Problem
Uniform-grid ConvNets for 3D data incur large memory and processing costs, while scaling to fine-grained and high spatial representations remains problematic.
Method
Kd-networks use kd-trees instead of uniform grids to build computational graphs, share learnable parameters, and compute hierarchical representations from point clouds.
Results
Kd-networks achieve results comparable to current state-of-the-art across classification, retrieval, and part segmentation, with efficient training and testing.
Takeaways & Limitations
Kd-trees can serve as scalable underlying structures for deep architectures operating directly on unstructured 3D point clouds.
Takeaways & Limitations
Kd-networks are not rotation-invariant because their underlying kd-trees are not invariant to rotations.
Abstract
from arXiv · showhide
We present a new deep learning architecture (called Kd-network) that is designed for 3D model recognition tasks and works with unstructured point clouds. The new architecture performs multiplicative transformations and share parameters of these transformations according to the subdivisions of the point clouds imposed onto them by Kd-trees. Unlike the currently dominant convolutional architectures that usually require rasterization on uniform two-dimensional or three-dimensional grids, Kd-networks do not rely on such grids in any way and therefore avoid poor scaling behaviour. In a series of experiments with popular shape recognition benchmarks, Kd-networks demonstrate competitive performance in a number of shape recognition tasks such as shape classification, shape retrieval and shape part segmentation.
1. Introduction
3D model recognition is increasingly important, but adapting ConvNets to 3D data is difficult because uniform voxel grids impose severe memory and processing costs. Kd-networks address this by using kd-trees as the structural basis for deep computation and parameter sharing.
- Growing 3D scans and model archives increase the importance of recognizing and analyzing 3D geometric models.
- Rasterizing 3D models onto uniform voxel grids causes excessively large memory footprints and slow processing times.
- Kd-networks use kd-trees to form computational graphs, share learnable parameters, and compute hierarchical representations bottom-up.
- Experiments show Kd-networks approach or exceed ConvNet accuracy for classification, retrieval, and part segmentation.
- Kd-networks require smaller memory footprints and more efficient training and testing computations than uniform voxel-grid approaches.
2. Related Work
Prior 3D recognition approaches adapt ConvNets through voxel grids, projections, or non-Euclidean geometries, but each has scalability or information-retention trade-offs. Kd-networks relate to recursive, octree, and graph-based architectures while structuring parameter sharing around kd-trees.
- Uniform 3D grids support coarse-level classification but make scaling to fine-grained tasks and high spatial representations problematic.
- Projection-based methods improve efficiency but may lose information needed for difficult 3D shape recognition tasks.
- Spectral and anisotropic ConvNets generalize convolutional processing to non-Euclidean geometries such as mesh surfaces.
- Kd-networks share tree-structured computation with recursive neural networks but use more structured parameter sharing across the tree.
- Kd-networks are closely related to OctNets and graph-based ConvNets, using kd-trees as their underlying spatial graph structure.
3. Shape Recognition with Kd-Networks
Kd-networks process point clouds through kd-tree-structured, bottom-up representations rather than uniform grids. They share direction- and level-specific transformations, support classification and retrieval, and provide partial jitter robustness but remain rotation-sensitive.
- Architecture: Kd-networks construct hierarchical representations from kd-trees, applying bottom-up computations from individual point representations to the root.Each non-leaf node combines its two child representations according to the node's split direction.
- Architecture: At each tree level, the split direction selects one of three learnable affine transformations followed by a non-linearity.The transformations use concatenated child representations as input and have parameters shared across nodes at the same level and split type.
- Recognition tasks: The root representation can feed a linear classifier for class odds or be learned as a descriptor vector for shape retrieval.Retrieval training uses embedding-learning losses over matching and non-matching shapes.
- Properties: Small point jitter is ignored when it preserves kd-tree topology, because the main forward operation does not use split thresholds.Under those conditions, jitter affects outputs only through leaf representations.
- Properties: Kd-networks are not rotation-invariant because their underlying kd-trees change under rotations.The paper identifies this as inferior to intrinsic ConvNets and mentions alignment or augmentation as standard remedies.
- Recognition tasks: Kd-network processing uses kd-tree structure both to determine which leaf representations are merged and to provide shape information independently of leaf features.The kd-tree structure itself can serve as a shape descriptor.
4. Experiments
Experiments evaluate Kd-networks on classification, retrieval, and part segmentation benchmarks, including ablations, augmentation variants, and different kd-tree depths. Results show competitive recognition performance, with randomized trees helping classification and global-rotation sensitivity limiting retrieval on perturbed shapes.
- Shape classification: Kd-network classification models used depth-10 and depth-15 architectures with shared transformations over kd-tree-organized point clouds and geometric augmentations.Training and testing used translation and anisotropic-scaling augmentations together with deterministic or randomized kd-trees.
- Shape classification: 99.1% accuracy was obtained on MNIST, placing Kd-networks near ConvNet results without additional tricks.This result is reported for the MNIST benchmark in Table 2.
- Shape classification: The ablation results indicate that hierarchical data flow and structured weight sharing outperform a linear split-information baseline, while split direction is more informative than leaf representation.The ablated model with trivial leaf representations comes close to the full method, and the linear baseline performs much worse than Kd-network.
- Shape classification: Randomized kd-trees considerably improve generalization, whereas geometric augmentations have a smaller effect; increasing depth produces saturation without overfitting.For smaller models, epochs take longer to converge, while kd-tree construction and point sampling become the bottleneck for larger models.
- Shape retrieval and part segmentation: Kd-networks perform on par with multiview CNNs for normal retrieval data and competitively after a 20-rotation modification, but global-rotation sensitivity degrades the unmodified model on perturbed data.Part segmentation is competitive but does not improve over the state of the art; one example occupies less than 120 Mb during learning.
5. Conclusion
The paper introduces Kd-networks for direct point-cloud recognition, using kd-trees instead of uniform grids and achieving competitive results across recognition tasks.
- Kd-networks work directly with point clouds and use kd-trees to build computational graphs and share learnable parameters.
- Their representations support varied 3D recognition problems, with results comparable to current state-of-the-art across classification, retrieval, and part segmentation.
- Competitive kd-tree performance motivates investigating octrees, PCA-trees, and bounding volume hierarchies as alternative structures for deep architectures.