  Window-based transformers have demonstrated strong ability in large-scale
point cloud understanding by capturing context-aware representations with
affordable attention computation in a more localized manner. However, because
of the sparse nature of point clouds, the number of voxels per window varies
significantly. Current methods partition the voxels in each window into
multiple subsets of equal size, which cost expensive overhead in sorting and
padding the voxels, making them run slower than sparse convolution based
methods. In this paper, we present ScatterFormer, which, for the first time to
our best knowledge, could directly perform attention on voxel sets with
variable length. The key of ScatterFormer lies in the innovative Scatter Linear
Attention (SLA) module, which leverages the linear attention mechanism to
process in parallel all voxels scattered in different windows. Harnessing the
hierarchical computation units of the GPU and matrix blocking algorithm, we
reduce the latency of the proposed SLA module to less than 1 ms on moderate
GPUs. Besides, we develop a cross-window interaction module to simultaneously
enhance the local representation and allow the information flow across windows,
eliminating the need for window shifting. Our proposed ScatterFormer
demonstrates 73 mAP (L2) on the large-scale Waymo Open Dataset and 70.5 NDS on
the NuScenes dataset, running at an outstanding detection rate of 28 FPS. Code
is available at https://github.com/skyhehe123/ScatterFormer

Computer Vision and Pattern Recognition