{'fraction_non_alphanumeric': 0.03369146563957024, 'fraction_numerical': 0.012203527265355767, 'mean_word_length': 4.860299358517462, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DBQ-SSD: Dynamic Ball Query for Efficient 3D Object Detection

Many point-based 3D detectors adopt point-feature sampling strategies to drop some points for efficient inference. These strategies are typically based on fixed and handcrafted rules, making difficult to handle complicated scenes. Different from them, we propose a Dynamic Ball Query (DBQ) network to adaptively select a subset of input points according to the input features, and assign the feature transform with suitable receptive field for each selected point. It can be embedded into some state-of-the-art 3D detectors and trained in an end-to-end manner, which significantly reduces the computational cost. Extensive experiments demonstrate that our method can reduce latency by 30%-60% on KITTI and Waymo datasets. Specifically, the inference speed of our detector can reach 162 FPS and 30 FPS with negligible performance degradation on KITTI and Waymo datasets, respectively.


Introduction
3D object detection, as a fundamental task in 3D scene recognition has made significant progress. It targets to recognize and localize objects from a point cloud and paves the way for several real applications like autonomous driving [1], robotic system [2], and augmented reality [3].
The structure of point clouds is sparse, unordered, and semantically deficient, making it difficult to encode point features like highly structured image features. To eliminate this barrier, voxel-based methods are proposed to organize the overall point cloud as neatly distributed voxels. Therefore, the naive 3D convolution or its efficient variant, i.e., 3D sparse convolution [4], can be used to extract voxel features like image processing manner. Although the voxel-based methods bring convenience to the processing of point cloud, they are prone to drop detail information, making it inescapable to suffer from suboptimal performance. Another stream of methods are point-based methods [2,5,6] inspired from PointNet++ [7]. They employ a series of operations, i.e., farthest point sample (FPS), query, and grouping, to directly extract informative feature from naive point cloud. However, the straightforward pipeline is cumbersome and costly. 3D-SSD [2] first proposes a single stage architecture, i.e., using encoder-only architecture, which replaces the geometric Distance-based FPS (D-FPS) with the Feature similarity-based FPS (F-FPS) to recall more foreground point features and further discards feature propagation (FP) layers for reducing latency. Although eliminating the overhead of FP layer, F-FPS operations still occupy vast latency. IA-SSD [6] further proposes contextual centroid prediction module to replace F-FPS, which directly predicts the classification scores of each point and adopts efficient top-k operation to further recall more foreground, and further cut computation overhead.
The current advanced designs mainly credit to efficient foreground recall, but they may still have redundancy in the other parts like the background points or the network structure. In this paper, we conduct several empirical analysis of IA-SSD [6] on two representative benchmarks, i.e., KITTI [1] and Waymo [8], to uncover the full picture of its inference speed bottleneck. We first calculate the latency distribution of all detector's modules to figure out which parts are the main speed bottlenecks. Then we count the ratio of background points and the scale distribution of all objects to further explore potential redundancy clues over the cumbersome modules. Our study reveals three valuable points: (1) MLP network occupies over half latency. (2) Tremendous spatial redundancy exists in background point features that appears in each stage of detector. (3) The size of each object is varying, making it unusable to align each receptive field of the conventional multi-scale grouping (MSG) and suffering from branch redundancy in MSG.
The above valuable finding motivates us to further build a more efficient detector with higher speed by reducing the redundant background points and blocking useless MSG branches. As shown in Fig. 2, we propose Dynamic Ball Query (DBQ) to replace the vanilla ball querying module. It dynamically activates useful and compact point features and blocks redundant background point features for each branch of MSG. For each point feature sampled by FPS or top-k classification score, we design a dynamic query multiplexer to determine which branch to go through. Specifically, we apply a light-weight MLP network for point features to predict N masks corresponding to N branches of MSG, where the value of mask is {0, 1} corresponding to blocking and activating states. The overall dynamic router procedure is data-driven so that the point features are adaptively activated or blocked with suitable combination among all receptive fields of MSG. Ulteriorly, we introduce a resource budget loss for DBQ to learn a trade-off between latency and performance.
To verify the efficiency of our method, we conduct extensive experiments on two typical datasets, i.e., KITTI [1] and Waymo [8]. Our Dynamic Ball Query enables the 3D detector to cut the latency from 9.85 ms (102 FPS) to 6.172 ms (162 FPS) on KITTI scene and speed up the inference speed from 20 FPS to 30 FPS on Waymo scene while keeping the comparable performance. In particular, the latency of the MLP network is reduced by over 50%.
2 Related Work

3D Detectors
The task of 3D detection is to predict 3D bounding boxes and class labels for each object in a point cloud scene. The detection algorithms can be split into voxel-based [9,4,10,11] and pointbased [12,2,5,6] methods. Voxel-based methods convert point cloud into regular voxels or pillars, make it natural to apply 3D convolution or its sparse variant [4] for feature extraction. This regular partition method may lead to detail information lost, so point-based methods are proposed to directly process vanilla point cloud. Inspired by PointNet++ [7] and Faster R-CNN [13], PointRCNN [12] employs SA and FP layers to extract feature for each point and designs a region proposal network (RPN) to produce proposals, and utilizes a extra stage of module to predict bounding boxes and class labels. Similar with single-stage 2D detectors [14,15,16,17,18], 3DSSD [2] and IA-SSD [6] discard the region proposal network, and use encoder-only architecture to localize 3D objects. Our work focus on dynamically dropping the redundant background point features for single stage point-based detector, which is rarely researched in previous works. Our method endow detector with super inference speed.

Efficient 3D Point-based Detectors
Point-based method need to process large scale of vanilla point feature, which requires to build cumbersome models and suffers expensive computation cost. Therefore, several works [2,5,6] aim at design a lightweight and effective point-based detector. 3D-SSD [2] proposes feature-based fastest point sampling (F-FPS) strategy by measuring the similarity of point features to replace geometric distance of D-FPS [7]. The policy makes it reasonable to discard FP layers, since F-FPS can recall more foreground points instead of compensating foreground information by cumbersome FP layers. Even so, the F-FPS operation suffer from high complexity bottleneck. IA-SSD introduces a contextual centroid prediction module for replacing the F-FPS operation to efficient recall more foreground points. It predicts the classification score for each point feature and applies efficient top-k operation to all points ordered by category independent scores. Instead of focusing on foreground part by efficient sampling policies, we explore the spatial redundancy of background points. Our introduce a dynamic network mechanism to adaptively reduce useless background points in in a data-dependent regime.

Dynamic Network
Dynamic networks target to adaptively change the structure of network and parameters in data-driven manner. In the field of model automation designing, dynamic network mechanism is used to drop blocks [19,20,21,22], pruning channels [23,24,25], adjusting layer-level scales [26,27] and changing spatial typologies [28,29]. DRNet [26] aims at learning an automatic scale transformation for a feature pyramid network in semantic segmentation scene. Switch Transformer [30] employs the Mixture of Experts (MoE) [31] model to choose different parameters for each input data. Deformable convolution [32] learn a convolution of arbitrary shapes by predicting an offset for each parameter. Dynamic Grained Encoder [33] adopts a dynamic gate mechanism to select the spatial granularity of input query in transformer network. Dynamic Convolution [34], Dynamic Head [35] focus on learning a sparse mask for network to discard redundant image features. In this paper, we focus on 3D detection on point cloud scene and aim at design a point-wise dynamic network to drop redundant background points.

Analysis and Motivation
To explore what hampers the higher speed for 3D detection task, we conduct several experiments on both KITTI val and Waymo val sets with the state-of-the-art point-based 3D-detector [6]. To establish a strong baseline, we split the point cloud into four parallel parts to speed up the first FPS operation. We first measure the latency on each detector module. As shown in Fig. 1(a), the MLP network occupies the major part of the overall time overhead, i.e., 6.44 ms (65.4%) and 28.56 ms (56.5%) on KITTI and Waymo scenes, respectively. Therefore, optimizing the cumbersome and costly MLP network is a top priority for building an efficient detector.
Decreasing the input scale of points or network parameters are natural and empirical manner for reducing the latency but the policies are prone to damage the performance. To avoid both notorious drawbacks, we attempt to analyze the redundancy of background points in each backbone stage. As shown in Fig. 1(b), it indicates that the number of background points (point features) dominates the proportion of over 70% at any network level. The phenomenon reveals that significant redundancy exists in background points which may be discarded for speeding up the detection procedure.
Going one step further, we point out that the conventional multi-scale grouping (MSG) operation [7] of the set abstraction (SA) layer may be also redundant. As shown in Fig. 1(c), it reflects that the size of each object varies in either KITTI or Waymo scenes. Therefore, the given receptive field of MSG may not entirely align with the size of object. In this regime, some grouping branches of MSG are useless. The valuable observation motivates us to block and choose optimal grouping branches to process point feature, which can further make the detector efficient.

Dynamic Ball Querying
Our DBQ-SSD framework is established on the efficient IA-SSD framework, which adopts set abstraction (SA) layers to encode point features. To achieve a better balance between effectiveness and efficiency, we introduce the dynamic network mechanism into the IA-SSD framework. Specifically, we propose the Dynamic Ball Querying (DBQ) to replace the vanilla ball querying in each set abstraction layers, which is shown in Fig. 2. It is able to adaptively select a subset of input points as queries and extract local features in a suitable spatial radius. The dynamic ball querying is a generic module which can be easily embedded into the encoder blocks in mainstream point-based 3D detection frameworks.
Given an input point sequence x c ∈ R N ×3 with the corresponding features x f ∈ R N ×C , N denotes the length of sequence and C indicates the number of feature channels. Besides, the coordinate sequence of input queries is denoted as q c ∈ R Nq×3 , where N q is the number of queries. For efficiency, most of previous point-based methods [2,6] use Farthest Point Sampling (FPS) or its variants (e.g., dividing point cloud by multiple parallel parts to reduce computational complexity) to generate the query points. For each query, the vanilla ball querying samples a predefined number of local points within a specific spatial radius. Since different object instances require different receptive fields, in a set abstraction layer, the previous 3D detectors [2,6] typically adopt multiple groups of vanilla ball querying with different radii to increase feature diversity.
Specifically, for one set abstraction layer, we define the set of predefined radii as R = {r k } K and the number of sampling points as Φ = {φ k } K , where K indicates the number of groups. Based on these, we establish a set of K vanilla ball querying blocks. As shown in Fig. 2, our dynamic ball querying is made up of a query multiplexer and a set of vanilla ball querying blocks. Similar to the gate-based dynamic networks [33,22,26], the query multiplexer adopts a fine-grained routing process to select a suitable combination of vanilla ball querying blocks for each query.

Inference
For an input query i ∈ {1, 2, ..., N q } with coordinate q c (i), we first obtain the corresponding query feature according to its coordinate for the query multiplexer. The query feature can be used as the basis for dynamic decisions. Specifically, we adopt the nearest sampling technique to obtain its representation from the features of input points. Albeit the sampling process with more sample points, e.g., top-k sampling and ball gathering, can lead to a slight performance gain, it causes a significant decrease in efficiency. The previous variants of ball querying employ heuristic and handdesigned rules. Different from them, the routing process of our query multiplexer is performed in a data-dependent way. To achieve it, we predict the gating logits for each query by a linear projection: where W ∈ R C×K and b ∈ R 1×K denotes the weight and bias, respectively. Moreover, the binary gating masks for the i-th query and the k-th group are generated by quantizing the gating logits: The gating masks control which ball querying group is enabled, i.e., the group with positive mask value is enabled and vice versa. Based on this, we can adaptively reduce the number of queries and obtain the coordinates of sparse queries for each group: Furthermore, the sparse coordinates are used to guide the vanilla ball querying with corresponding settings to generate the sparse query features. Following the conventional protocols in the PointNetlike methods, the sparse query features are then transformed by the predefined MLP layers and max pooling operator:ẑ To fuse the sparse transformed features in different groups, we remap them into the dense form according to the gating mask. The output feature of the SA layer are then blended by summation: where the Aggregation k is a linear layer, which is adopted to transform the features in different groups into same dimension.

Training
Since the sparse selection in Eq. 3 is non-differentiable, it is nontrivial for the dynamic ball querying to enable fully end-to-end training. To achieve it, we replace the determined decisions in Eq. 3 with a stochastic sampling process. Concretely, we consider the gating logits unnormalized log probabilities under the Bernoulli distribution. To this end, with noise samples g and g drawn from a standard Gumbel distribution [36], a discrete gating mask can be yielded: , where g, g ∼ Gumbel(0, 1).
To enable end-to-end training, motivated by the previous dynamic networks, we use the Gumbel-Sigmoid technique [36] to give a differentiable approximation for the Eq. 6 by replacing the hard step function to the soft sigmoid function. The likelihood of the i-th query in k-th group being selected is: where τ is the temperature coefficient. In the training phase, we use the Eq. 6 as the gating mask to select the sparse queries and employ a straight-through estimator [37,34] to obtain the gradients of gating logits:

Latency Constraint
Without latency constraint, the dynamic ball querying typically enables more queries for each group to obtain high accuracy. To achieve a better balance between effectiveness and efficiency, we introduce the latency constraint as a training target to reduce the inference time. Different from the computational complexity employed in many previous dynamic networks [33,22,26], the latency can represent the actual runtime in specific devices. To this end, we first establish a latency map for each group in each SA layer, which records the latency wrt the number of queries. Based on this, we can calculate the latency ratio of all the SA layers with dynamic ball querying: where Ψ l,k indicates the latency map of k-th group in l-th layer. Finally, the latency is constrained by using the Euclidean distance to design a budget loss, thus the total loss is: For simplicity, the objective latency budget γ is set to 0 in all experiments. The hyper-parameter λ is used to scale the budget loss. In addition, if input is batched format, Ψ need to be averaged along the batch dimension to estimate the average overhead of the network.

Small (2) Small (3) Small (4)
Large ( Evaluation metrics. For KITTI scene, we report the performance of all classes by measuring average precision (AP) metric. Follow most of state-of-the-art methods, we adopt 0.7, 0.5, and 0.5 of the IoU thresholds for Car, Pedestrian, and Cyclist, respectively. In addition, three levels of difficulty ("Easy", "Moderate", and "Hard") are also reported. To evaluate Waymo, we use the official metrics, Average Precision (AP) and Average Precision weighted by Heading (APH), and report the performance on LEVEL 1 (L1) and LEVEL 2 (L2) difficulty levels.
Implementation Details Following the stream of single-stage point-based methods, we use encoder-only architecture like [2,5,6]. Specially, we split the point features into four parallel fan parts to speed up D-FPS of the first sampling layer, which will be acted as the efficient and strong baseline. Other sampling layers follow the default setting of [6]. We employ two groups of each MSG with corresponding radius ([0.

Evaluation on KITTI Dataset
We randomly sample 16,384 points from overall point cloud per single view frame. We train our model by ADAM [38] optimizer with onecycle learning strategy [39]. The batch size is set to 16 with 8 GPUs. The initial learning rate is 0.01 and is decayed by 0.1 at 35 and 45 epochs.

Dynamic vs Static
To verify the efficient of our method, we first report the performance and latency on KITTI scene. As shown in Fig. 3(a), our detector achieves super speed while maintaining comparable performance with other detectors. When λ is set to 0.1, the performance surpasses the efficient baseline. Therefore, we set the scale parameter to 0.1 for all experiment by default. As increasing the supervision on resource budget loss, the speed is further improved to 223 FPS. The impressive results shows that our method endows point-based 3D detector with efficient detection capability. Going one step further, we report the reduction of latency on two revenue modules, i.e., query & grouping operation, and MLP network. As shown in Fig. 3(b), our method cut considerable overhead of both in different SA layers. It verifies that adaptively turning off useless points by DBQ can speed up the computation of both modules.
Activation and Blocking Points To explore which points are activated or blocked, we conduct quantitative and qualitative experiments using visualization and statistics respectively. Fig. 3(c) counts the activation ratios of point features in different layers. It indicates that a considerable large part of points is discarded. Next, we dip into visualization results to figure out the reason for the quantitative results. As shown in Fig. 4, it reflects clearly that the activating points (red points) are  almost distributed around objects, while other points away from the objects are blocked. It reveals that our method discards most redundant background points which may be useless for the localization and classification of objects, making it reasonable for detector to speed up inference. Remaining foreground points and surrounding points are used to support the structure of objects and enrich context information. Therefore, our method does not damage the performance of detection. It echoes our analysis in Sec. 3.

Routing Manner and Branch Redundancy
Tab. 1 compares the effectiveness between layer-wise and point-wise routing manner. During inference, the layer-wise routing manner only speeds up by 18 FPS with small performance gains, while our point-wise manner not only achieves significant performance improvement but also reduces considerable latency. In addition, the contrast on whether to predict split mask or share identity mask for each group of MSG indicates that the former is optimal policy. Generating two masks for different scales of group allow each point to reach an optimal combination of receptive field. Corresponding statistical and visualization results can be seen in Fig. 3(d) and Fig. 4, which reveals that more points go through both groups in early layers while most points are only keen on a single branch or even be killed. The phenomenon agrees well with the empirical analysis in Sec. 3.

Main Results
As illustrated in Tab. 2, our method outperforms the efficient baseline on all categories, while achieving higher inference speed (162 vs 102). It verifies that our method can not only drop redundant points for speeding up inference, but extract more useful information for localization and classification. By comparing with other state-of-the-art methods, our detector outperforms their speed with a large margin while maintains comparable accuracy.

Evaluation on Waymo Dataset
To verify the generalization of our method, we further evaluate the performance on Waymo [8] dataset. Because Waymo scene is made up of the 360-degree point cloud which scale is larger than KITTI scene, we increase the input number of points by sampling from 16,384 to 65,536. The batch size is set to 2 for each GPU. We train 30 epochs with 8 GPUs. Other settings are the same as the experiments of KITTI scene.
As shown in Tab 3, we report the performance and inference speed of our DBQ-SSD. As carrying out suitable supervision (i.e., λ = 0.05) for the detector, it achieves impressive performance in all classes. Especially, some categories achieve state-of-the-art accuracy in evaluation metrics or levels of difficulty. Meanwhile, it also improves the inference speed of efficient the baseline from 20 FPS to 27 FPS. The results show that adaptively blocking redundant point features and activating high-quality point features are the key to endow our detector with efficient performance. When conducting larger scale of supervision for DBQ-SSD, it is capable of detecting objects with real-time speed (30 FPS) and achieves comparable accuracy. The real-time speed is significantly important in autonomous driving scene since low latency is indispensable condition for several applications like streaming perception [50,51,52]. It can provide flexible configuration for practical applications to realize the best trade-off between accuracy and overhead cost.

Conclusion
In this paper, we point out the existing spatial redundancy on background points and useless receptive field groups in MSG. This redundancy impedes the further inference efficiency improvement of point-based 3D detectors. To eliminate the dilemma, we propose a dynamic ball query, which can dynamically generate gate masks for each group of MSG to process useful points and block redundant background points. The extensive experiments demonstrate our analysis and show the effectiveness of our method. In short, we launch a new view to focus on redundant background points instead of the limited foreground part, which further deepen the understanding of the sparsity of point cloud. We hope this work can shed the light to the research of efficient point-based models and inspire future works.
Limitation and Future Work With increasing the supervision on resource budget (increasing the value of γ.), the performance will decrease accordingly. We suspect that dropping too many point clouds may eliminate the part of the useful point cloud. Therefore, this paper targets to achieve a better trade-off between accuracy and inference speed, which maintaining or even achieving gain in accuracy, and significantly speeding up inference. In this paper, we can not specifying what point to drop but our detector equips strong ability to eliminate redundancy. Therefore, we look forward to inspire future works for focusing on dropping more redundant point cloud without performance degradation.