稀疏體素上的注意力:視窗、集合與序列
選讀・DLCV 03B・三維物件偵測:光達、相機與鳥瞰視角 的補充資料(第 3/5 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
這則補充說明 Transformer 與序列模型骨幹如何組織一次光達掃描中被占用的體素,使計算量維持在負擔得起的範圍。
問題。 一次掃描有 個被占用的體素,常常是數萬個。完整的自注意力讓每個體素與其他每個體素比較,所以成本約隨 成長。因此所有實用的設計都讓每個體素只與一群其他體素互動,差別在於如何形成這些群組。
視窗。 把網格切成不重疊、大小固定的視窗(例如 個體素),並在每個視窗內被占用的體素之間執行注意力。麻煩在於各視窗含有的體素數相差很大:靠近感測器的很多,遠處的只有寥寥幾個。GPU 想要大小相等的批次,所以天真的實作會把每個視窗都補到最大視窗的大小,而補的部分就主導了成本。SST [25] 以這種方式依區域把體素分組,也使用平移半個區域大小的區域,讓被區域邊界切開的物體仍能交換資訊。
等大小集合。 DSVT [26] 把每個視窗切成若干集合,每個集合都含有相同的 個體素。對一個有 個被占用體素的視窗,集合數是
其中 表示無條件進位。體素依視窗內的索引排序,平均分配到 個集合中;不足的集合以重複的體素補滿,這些體素會在注意力中被遮罩掉。這樣每個集合恰好有 個 token,所以所有視窗的所有集合可以在同一個平行批次中處理,而稠密的視窗只是得到更多的集合。因為注意力現在停留在集合內,DSVT 在連續的層交替使用兩種排序,分別沿著 軸與 軸,讓同一層中不同集合的體素在下一層相遇。
下面的程式碼在一次玩具掃描上計算注意力配對數(注意力的成本就是 token 配對的數量),比較把每個視窗補到最大視窗,與使用等大小集合。
程式碼 · Python · 17 行
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")輸出
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大多數視窗幾乎是空的(中位數 8 個體素),只有少數靠近感測器的視窗是滿的,所以補到最大視窗的成本,是等大小集合的十倍配對數。這個比較不算完全公平:使用集合時,每個體素只在自己的集合內做注意力,這就是為什麼需要交替的分割。
序列。 第二個家族先把體素序列化(serialize):沿著一條空間填充曲線(space-filling curve)排序,這是一條恰好經過網格每個格子一次的路徑,並讓空間上靠近的格子在順序中大多也靠近。Point Transformer V3 的骨幹就是圍繞這種序列化建立的 [60]。線性時間的序列模型接著讓非常長的群組變得負擔得起:LION [27] 把線性遞迴網路套用在大群體素上,Voxel Mamba [28] 則用希爾伯特曲線(Hilbert curve)把整個場景的所有體素變成單一序列,交給狀態空間模型,完全不做分組。
陷阱。 沒有任何一種二維或三維網格的排序,能讓所有鄰居都保持相鄰:曲線在任何折返之處,空間上並排的兩個體素,在序列中都可能相距很遠。因此以序列化為基礎的設計會加入跨越曲線跳躍來混合資訊的方式:Point Transformer V3 在多種序列化模式之間切換 [60],Voxel Mamba 則在序列模型中加入第二個較粗的尺度 [28]。
參考文獻
- 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