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
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 occupied voxels, often tens of thousands. Full self-attention compares every voxel with every other, so its cost grows like . 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 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 of voxels. For a window with occupied voxels, the number of sets is
where rounds up. The voxels are sorted by an index inside the window and spread evenly over the sets; a set that would be short is filled with repeated voxels, which are masked out of the attention. Every set now has exactly 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 axis and along the 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 setsMost 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
- 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
- R. Qian, X. Lai and X. Li, “3D object detection for autonomous driving: A survey,” Pattern Recognition, vol. 130, 2022. doi
- 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
- 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
- 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
- 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
- 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
- Y. Zhou and O. Tuzel, “VoxelNet: End-to-end learning for point cloud based 3D object detection,” in Proc. IEEE CVPR, 2018. CVF
- Y. Yan, Y. Mao and B. Li, “SECOND: Sparsely embedded convolutional detection,” Sensors, vol. 18, no. 10, 3337, 2018. doi
- 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
- T. Yin, X. Zhou and P. Krähenbühl, “Center-based 3D object detection and tracking,” in Proc. IEEE/CVF CVPR, 2021. CVF
- I. E. Sutherland and G. W. Hodgman, “Reentrant polygon clipping,” Communications of the ACM, vol. 17, no. 1, 1974. doi
- X. Zhou, D. Wang and P. Krähenbühl, “Objects as points,” arXiv:1904.07850, 2019. arXiv
- 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
- 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
- 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
- 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
- S. Shi, X. Wang and H. Li, “PointRCNN: 3D object proposal generation and detection from point cloud,” in Proc. IEEE/CVF CVPR, 2019. arXiv
- 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
- B. Graham, M. Engelcke and L. van der Maaten, “3D semantic segmentation with submanifold sparse convolutional networks,” in Proc. IEEE CVPR, 2018. CVF
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Z. Tian, C. Shen, H. Chen and T. He, “FCOS: Fully convolutional one-stage object detection,” in Proc. IEEE/CVF ICCV, 2019. arXiv
- 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
- J. Philion and S. Fidler, “Lift, splat, shoot: Encoding images from arbitrary camera rigs by implicitly unprojecting to 3D,” in Proc. ECCV, 2020. arXiv
- 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
- Y. Liu, T. Wang, X. Zhang and J. Sun, “PETR: Position embedding transformation for multi-view 3D object detection,” in Proc. ECCV, 2022. arXiv
- 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
- 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
- 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
- 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
- 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
- S. Vora, A. H. Lang, B. Helou and O. Beijbom, “PointPainting: Sequential fusion for 3D object detection,” in Proc. IEEE/CVF CVPR, 2020. arXiv
- 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
- 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
- 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
- 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
- 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
- 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
- R. Nabati and H. Qi, “CenterFusion: Center-based radar and camera fusion for 3D object detection,” in Proc. IEEE/CVF WACV, 2021. doi
- 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
- A. Geiger, P. Lenz and R. Urtasun, “Are we ready for autonomous driving? The KITTI vision benchmark suite,” in Proc. IEEE CVPR, 2012. doi
- nuScenes devkit, “nuScenes detection task,” official evaluation documentation (classes, detection ranges, mAP, TP metrics, NDS, submission rules). link
- Waymo Open Dataset, “3D detection challenge (2020),” official challenge page (APH, IoU thresholds, LEVEL_1/LEVEL_2, range breakdown). link
- 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
- Waymo Open Dataset,
metrics_utils.cc, official metric implementation (functionComputeHeadingAccuracy). code - 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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