Full search page →

Attention on sparse voxels: windows, sets and sequences

Optional · supplementary note 3 of 5 for DLCV 03B · 3D Object Detection: LiDAR, Cameras and Bird's-Eye View. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

On this page

Supplementary notes · 5

  1. Yaw encodings compared: raw angle, sine error and (sin, cos)
  2. Sparse and submanifold convolution
  3. Attention on sparse voxels: windows, sets and sequences
  4. Ground-truth sampling in detail
  5. Computing NDS step by step

Paper guides · 3

  1. Guide to the Modern view surveys
  2. PointPillars: a reading guide
  3. Lift-Splat-Shoot: a reading guide

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

This note explains how transformer and sequence-model backbones organize the occupied voxels of a LiDAR scan so that the computation stays affordable.

The problem. A sweep has NN occupied voxels, often tens of thousands. Full self-attention compares every voxel with every other, so its cost grows like N2N^2. All practical designs therefore let each voxel interact only with a group of others, and they differ in how the groups are formed.

Windows. Divide the grid into non-overlapping windows of fixed size (for example 12×1212 \times 12 voxels) and run attention among the occupied voxels inside each window. The catch is that windows hold very different numbers of voxels: many near the sensor, a handful far away. GPUs want equal-size batches, so a naive implementation pads every window to the largest one, and the padding dominates the cost. SST [25] groups voxels by region in this way and also uses regions shifted by half their size, so that objects cut by a region border still exchange information.

Equal-size sets. DSVT [26] splits each window into sets that all hold the same number τ\tau of voxels. For a window with NwN_w occupied voxels, the number of sets is

Sw=⌈Nwτ⌉,S_w = \left\lceil \frac{N_w}{\tau} \right\rceil,

where ⌈⋅⌉\lceil \cdot \rceil rounds up. The voxels are sorted by an index inside the window and spread evenly over the SwS_w sets; a set that would be short is filled with repeated voxels, which are masked out of the attention. Every set now has exactly τ\tau tokens, so all sets of all windows are processed in one parallel batch, and a dense window simply receives more sets. Because attention now stays inside a set, DSVT alternates two sortings in consecutive layers, along the xx axis and along the yy axis, so that voxels in different sets of one layer meet in the next.

The snippet counts the attention pairs (the cost of attention is the number of token pairs) on a toy scan, for padding every window to the largest versus equal-size sets.

Code · Python · 17 lines
import numpy as np

rng = np.random.default_rng(0)
# occupied BEV voxels of a toy scan: density falls with range, as for a spinning LiDAR
r = 2 + 70 * rng.random(20000) ** 2                   # more points close to the sensor
a = rng.uniform(-np.pi, np.pi, r.size)
cells = np.unique(np.floor(np.column_stack([r * np.cos(a), r * np.sin(a)]) / 0.32).astype(int), axis=0)

win = 12                                              # windows of 12 x 12 voxels
_, n = np.unique(cells // win, axis=0, return_counts=True)   # occupied voxels per window
tau = 36                                              # voxels per set
S = -(-n // tau)                                      # ceil(N / tau) sets per window

print(f"{len(cells)} occupied voxels in {len(n)} non-empty windows; "
      f"per window: min {n.min()}, median {int(np.median(n))}, max {n.max()}")
print(f"pad every window to {n.max()}:  {len(n) * n.max() ** 2 / 1e6:5.1f} M attention pairs")
print(f"equal-size sets, tau = {tau}: {S.sum() * tau ** 2 / 1e6:5.1f} M attention pairs in {S.sum()} sets")

Output

14431 occupied voxels in 1136 non-empty windows; per window: min 1, median 8, max 120
pad every window to 120:   16.4 M attention pairs
equal-size sets, tau = 36:   1.6 M attention pairs in 1234 sets

Most windows are nearly empty (median 8 voxels) while a few near the sensor are full, so padding to the largest window costs ten times more pairs than equal-size sets. The comparison is not quite like for like: with sets, each voxel attends only within its set, which is why the alternating partitions are needed.

Sequences. A second family first serializes the voxels: it orders them along a space-filling curve, a path that visits every cell of the grid once and keeps cells that are close in space mostly close in the order. Point Transformer V3 builds its backbone around such serialization [60]. Linear-time sequence models then make very long groups affordable: LION [27] applies linear recurrent networks to large groups of voxels, and Voxel Mamba [28] uses a Hilbert curve to turn all voxels of a scene into a single sequence for a state space model, with no grouping at all.

Pitfall. No ordering of a 2D or 3D grid keeps all neighbours adjacent: wherever the curve turns back, two voxels side by side in space can end up far apart in the sequence. Serialization-based designs therefore add ways to mix information across the curve’s jumps: Point Transformer V3 switches between several serialization patterns [60], and Voxel Mamba adds a second, coarser scale to its sequence model [28].

References

  1. J. Mao, S. Shi, X. Wang and H. Li, “3D object detection for autonomous driving: A comprehensive survey,” International Journal of Computer Vision, vol. 131, no. 8, 2023. doi
  2. R. Qian, X. Lai and X. Li, “3D object detection for autonomous driving: A survey,” Pattern Recognition, vol. 130, 2022. doi
  3. P. Sun, H. Kretzschmar, X. Dotiwalla, A. Chouard, V. Patnaik et al., “Scalability in perception for autonomous driving: Waymo Open Dataset,” in Proc. IEEE/CVF CVPR, 2020. CVF
  4. H. Caesar, V. Bankiti, A. H. Lang, S. Vora, V. E. Liong et al., “nuScenes: A multimodal dataset for autonomous driving,” in Proc. IEEE/CVF CVPR, 2020. CVF
  5. M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, 1981. doi
  6. M. Ester, H.-P. Kriegel, J. Sander and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proc. KDD, 1996. AAAI
  7. X. Zhang, W. Xu, C. Dong and J. M. Dolan, “Efficient L-shape fitting for vehicle detection using laser scanners,” in Proc. IEEE Intelligent Vehicles Symposium (IV), 2017. doi
  8. Y. Zhou and O. Tuzel, “VoxelNet: End-to-end learning for point cloud based 3D object detection,” in Proc. IEEE CVPR, 2018. CVF
  9. Y. Yan, Y. Mao and B. Li, “SECOND: Sparsely embedded convolutional detection,” Sensors, vol. 18, no. 10, 3337, 2018. doi
  10. A. H. Lang, S. Vora, H. Caesar, L. Zhou, J. Yang and O. Beijbom, “PointPillars: Fast encoders for object detection from point clouds,” in Proc. IEEE/CVF CVPR, 2019. CVF
  11. T. Yin, X. Zhou and P. Krähenbühl, “Center-based 3D object detection and tracking,” in Proc. IEEE/CVF CVPR, 2021. CVF
  12. I. E. Sutherland and G. W. Hodgman, “Reentrant polygon clipping,” Communications of the ACM, vol. 17, no. 1, 1974. doi
  13. X. Zhou, D. Wang and P. Krähenbühl, “Objects as points,” arXiv:1904.07850, 2019. arXiv
  14. N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov and S. Zagoruyko, “End-to-end object detection with transformers,” in Proc. ECCV, 2020. doi
  15. Y. Wang, V. Guizilini, T. Zhang, Y. Wang, H. Zhao and J. Solomon, “DETR3D: 3D object detection from multi-view images via 3D-to-2D queries,” in Proc. Conference on Robot Learning (CoRL), 2021. arXiv
  16. C. R. Qi, H. Su, K. Mo and L. J. Guibas, “PointNet: Deep learning on point sets for 3D classification and segmentation,” in Proc. IEEE CVPR, 2017. arXiv
  17. C. R. Qi, L. Yi, H. Su and L. J. Guibas, “PointNet++: Deep hierarchical feature learning on point sets in a metric space,” in Advances in Neural Information Processing Systems (NeurIPS), 2017. NeurIPS
  18. S. Shi, X. Wang and H. Li, “PointRCNN: 3D object proposal generation and detection from point cloud,” in Proc. IEEE/CVF CVPR, 2019. arXiv
  19. S. Ren, K. He, R. Girshick and J. Sun, “Faster R-CNN: Towards real-time object detection with region proposal networks,” IEEE TPAMI, vol. 39, no. 6, 2017. doi
  20. B. Graham, M. Engelcke and L. van der Maaten, “3D semantic segmentation with submanifold sparse convolutional networks,” in Proc. IEEE CVPR, 2018. CVF
  21. S. Shi, C. Guo, L. Jiang, Z. Wang, J. Shi, X. Wang and H. Li, “PV-RCNN: Point-voxel feature set abstraction for 3D object detection,” in Proc. IEEE/CVF CVPR, 2020. arXiv
  22. W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu and A. C. Berg, “SSD: Single shot multibox detector,” in Proc. ECCV, 2016. arXiv
  23. T.-Y. Lin, P. Goyal, R. Girshick, K. He and P. Dollár, “Focal loss for dense object detection,” in Proc. IEEE ICCV, 2017. doi
  24. J. Huang, G. Huang, Z. Zhu, Y. Ye and D. Du, “BEVDet: High-performance multi-camera 3D object detection in bird-eye-view,” arXiv:2112.11790, 2021. arXiv
  25. L. Fan, Z. Pang, T. Zhang, Y.-X. Wang, H. Zhao, F. Wang, N. Wang and Z. Zhang, “Embracing single stride 3D object detector with sparse transformer,” in Proc. IEEE/CVF CVPR, 2022. CVF
  26. H. Wang, C. Shi, S. Shi, M. Lei, S. Wang, D. He, B. Schiele and L. Wang, “DSVT: Dynamic sparse voxel transformer with rotated sets,” in Proc. IEEE/CVF CVPR, 2023. CVF
  27. Z. Liu, J. Hou, X. Wang, X. Ye, J. Wang, H. Zhao and X. Bai, “LION: Linear group RNN for 3D object detection in point clouds,” in Advances in Neural Information Processing Systems (NeurIPS), 2024. NeurIPS
  28. G. Zhang, L. Fan, C. He, Z. Lei, Z. Zhang and L. Zhang, “Voxel Mamba: Group-free state space models for point cloud based 3D object detection,” in Advances in Neural Information Processing Systems (NeurIPS), 2024. NeurIPS
  29. T. Wang, X. Zhu, J. Pang and D. Lin, “FCOS3D: Fully convolutional one-stage monocular 3D object detection,” in Proc. IEEE/CVF ICCV Workshops, 2021. arXiv
  30. Z. Tian, C. Shen, H. Chen and T. He, “FCOS: Fully convolutional one-stage object detection,” in Proc. IEEE/CVF ICCV, 2019. arXiv
  31. Y. Wang, W.-L. Chao, D. Garg, B. Hariharan, M. Campbell and K. Q. Weinberger, “Pseudo-LiDAR from visual depth estimation: Bridging the gap in 3D object detection for autonomous driving,” in Proc. IEEE/CVF CVPR, 2019. arXiv
  32. J. Philion and S. Fidler, “Lift, splat, shoot: Encoding images from arbitrary camera rigs by implicitly unprojecting to 3D,” in Proc. ECCV, 2020. arXiv
  33. Y. Li, Z. Ge, G. Yu, J. Yang, Z. Wang, Y. Shi, J. Sun and Z. Li, “BEVDepth: Acquisition of reliable depth for multi-view 3D object detection,” in Proc. AAAI, 2023. arXiv
  34. Y. Liu, T. Wang, X. Zhang and J. Sun, “PETR: Position embedding transformation for multi-view 3D object detection,” in Proc. ECCV, 2022. arXiv
  35. Z. Li, W. Wang, H. Li, E. Xie, C. Sima, T. Lu, Y. Qiao and J. Dai, “BEVFormer: Learning bird’s-eye-view representation from multi-camera images via spatiotemporal transformers,” in Proc. ECCV, 2022. arXiv
  36. X. Zhu, W. Su, L. Lu, B. Li, X. Wang and J. Dai, “Deformable DETR: Deformable transformers for end-to-end object detection,” in Proc. ICLR, 2021. arXiv
  37. S. Wang, Y. Liu, T. Wang, Y. Li and X. Zhang, “Exploring object-centric temporal modeling for efficient multi-view 3D object detection,” in Proc. IEEE/CVF ICCV, 2023. CVF
  38. X. Jiang, S. Li, Y. Liu, S. Wang, F. Jia, T. Wang, L. Han and X. Zhang, “Far3D: Expanding the horizon for surround-view 3D object detection,” in Proc. AAAI, 2024. arXiv
  39. Y. Wang, Q. Mao, H. Zhu, J. Deng, Y. Zhang, J. Ji, H. Li and Y. Zhang, “Multi-modal 3D object detection in autonomous driving: A survey,” International Journal of Computer Vision, vol. 131, no. 8, 2023. doi
  40. S. Vora, A. H. Lang, B. Helou and O. Beijbom, “PointPainting: Sequential fusion for 3D object detection,” in Proc. IEEE/CVF CVPR, 2020. arXiv
  41. X. Chen, H. Ma, J. Wan, B. Li and T. Xia, “Multi-view 3D object detection network for autonomous driving,” in Proc. IEEE CVPR, 2017. arXiv
  42. C. R. Qi, W. Liu, C. Wu, H. Su and L. J. Guibas, “Frustum PointNets for 3D object detection from RGB-D data,” in Proc. IEEE CVPR, 2018. CVF
  43. Z. Liu, H. Tang, A. Amini, X. Yang, H. Mao, D. Rus and S. Han, “BEVFusion: Multi-task multi-sensor fusion with unified bird’s-eye view representation,” in Proc. IEEE ICRA, 2023. arXiv
  44. T. Liang, H. Xie, K. Yu, Z. Xia, Z. Lin, Y. Wang, T. Tang, B. Wang et al., “BEVFusion: A simple and robust LiDAR-camera fusion framework,” in Advances in Neural Information Processing Systems (NeurIPS), 2022. arXiv
  45. X. Bai, Z. Hu, X. Zhu, Q. Huang, Y. Chen, H. Fu and C.-L. Tai, “TransFusion: Robust LiDAR-camera fusion for 3D object detection with transformers,” in Proc. IEEE/CVF CVPR, 2022. arXiv
  46. H. Wang, H. Tang, S. Shi, A. Li, Z. Li, B. Schiele and L. Wang, “UniTR: A unified and efficient multi-modal transformer for bird’s-eye-view representation,” in Proc. IEEE/CVF ICCV, 2023. arXiv
  47. R. Nabati and H. Qi, “CenterFusion: Center-based radar and camera fusion for 3D object detection,” in Proc. IEEE/CVF WACV, 2021. doi
  48. A. Geiger, P. Lenz, C. Stiller and R. Urtasun, “3D object detection evaluation 2017,” The KITTI Vision Benchmark Suite, official benchmark page (data sizes, IoU thresholds, difficulty levels, 40 recall positions). link
  49. A. Geiger, P. Lenz and R. Urtasun, “Are we ready for autonomous driving? The KITTI vision benchmark suite,” in Proc. IEEE CVPR, 2012. doi
  50. nuScenes devkit, “nuScenes detection task,” official evaluation documentation (classes, detection ranges, mAP, TP metrics, NDS, submission rules). link
  51. Waymo Open Dataset, “3D detection challenge (2020),” official challenge page (APH, IoU thresholds, LEVEL_1/LEVEL_2, range breakdown). link
  52. A. Simonelli, S. Rota Bulò, L. Porzi, M. López-Antequera and P. Kontschieder, “Disentangling monocular 3D object detection,” in Proc. IEEE/CVF ICCV, 2019. doi
  53. Waymo Open Dataset, metrics_utils.cc, official metric implementation (function ComputeHeadingAccuracy). code
  54. M. Hahner, C. Sakaridis, D. Dai and L. Van Gool, “Fog simulation on real LiDAR point clouds for 3D object detection in adverse weather,” in Proc. IEEE/CVF ICCV, 2021. arXiv
  55. Y. Dong, C. Kang, J. Zhang, Z. Zhu, Y. Wang, X. Yang, H. Su, X. Wei et al., “Benchmarking robustness of 3D object detection to common corruptions in autonomous driving,” in Proc. IEEE/CVF CVPR, 2023. arXiv
  56. Y. Wang, X. Chen, Y. You, L. E. Li, B. Hariharan, M. Campbell, K. Q. Weinberger and W.-L. Chao, “Train in Germany, test in the USA: Making 3D object detectors generalize,” in Proc. IEEE/CVF CVPR, 2020. arXiv
  57. Y. Guo, H. Wang, Q. Hu, H. Liu, L. Liu and M. Bennamoun, “Deep learning for 3D point clouds: A survey,” IEEE TPAMI, vol. 43, no. 12, 2021. doi
  58. Y. Ma, T. Wang, X. Bai, H. Yang, Y. Hou, Y. Wang, Y. Qiao, R. Yang and X. Zhu, “Vision-centric BEV perception: A survey,” IEEE TPAMI, vol. 46, no. 12, 2024. doi
  59. H. Li, C. Sima, J. Dai, W. Wang, L. Lu, H. Wang, J. Zeng, Z. Li et al., “Delving into the devils of bird’s-eye-view perception: A review, evaluation and recipe,” IEEE TPAMI, vol. 46, no. 4, 2024. doi
  60. X. Wu, L. Jiang, P.-S. Wang, Z. Liu, X. Liu, Y. Qiao, W. Ouyang, T. He and H. Zhao, “Point Transformer V3: Simpler, faster, stronger,” in Proc. IEEE/CVF CVPR, 2024. arXiv
  61. Y. Hu, J. Yang, L. Chen, K. Li, C. Sima, X. Zhu, S. Chai, S. Du et al., “Planning-oriented autonomous driving,” in Proc. IEEE/CVF CVPR, 2023. arXiv