Accelerating Non-Maximum Suppression: A Graph Theory Perspective

We sincerely appreciate Reviewer HR1f's thoughtful review of our work and the insightful questions you have raised. Your feedback is invaluable in helping us improve and refine our research. We will address each of your concerns in detail.

Q1: The connection between the proposed methods and graph theory appears weak.

A1: In fact, our methods are closely linked to graph theory for the following two reasons:

The first reason is that the goal of the algorithms is to construct the graph $\mathcal{G}$ or its approximate graph $\tilde{\mathcal{G}}$ more quickly and efficiently (see Section 4). However, due to the highly skillful design of our algorithm, there is no need to explicitly construct the graph in implementation.

We explained in Section 4.1 (Lines 174-177) that QSI-NMS does not require explicit construction of the graph $\tilde{\mathcal{G}}$. If we use different pivot selection methods or partitioning criteria, graph construction becomes unavoidable. The situation is similar in BOE-NMS. If we do not sort by confidence scores, we can still obtain $\mathcal{G}$, and the result after dynamic programming will be the same. However, this approach would incur additional space and time overhead. We conducted an experiment to support our analysis, where we did not sort by confidence but performed dynamic programming at the end, keeping everything else unchanged. The results tested on YOLOv8-N are as follows:

The second reason is that the algorithms' design is based on the analysis of WCCs in the graph $\mathcal{G}$, ensuring the algorithm's effectiveness. In the analysis in Section 3(Lines126-135 and Figure 2), we identified two crucial characteristics of $\mathcal{G}$: the number of WCCs is large, and their sizes are generally small. The first characteristic inspired the design of QSI-NMS, and the second characteristic inspired BOE-NMS(Lines 131-135).

Specifically, QSI-NMS is based on the divide-and-conquer strategy, where subproblems do not interfere with each other. If there are few WCCs, the divide-and-conquer process will repeatedly split the same WCC, leading to accuracy issues. BOE-NMS must traverse each WCC, and the smaller the WCCs, the faster BOE-NMS will be. Assuming there are $w$ WCCs and the size of the $i$-th WCC is $n_i$, we can perform a formal analysis using the following inequality:

The right half of the inequality shows that BOE-NMS is always better than Original NMS, while the left half shows the lower bound of BOE-NMS optimization. Therefore, the more WCCs there are, the greater the optimization space for BOE-NMS, and when each $n_i$ is as small as possible, it will be closer to this lower bound.

In summary, both the number and size of WCCs affect our two methods. The main reason is that the more WCCs there are, the better the accuracy performance of QSI-NMS; the smaller the WCCs, the higher the efficiency of BOE-NMS.

Q2: In section 5. 2 Results, we can find QSI-NMS operates with some performance decrease, and the paper doesn't thoroughly discuss what aspects of the algorithm might be causing this decline (maybe missing some data but exactly what is missed).

A2: Your question is very insightful, and other reviewers are also interested in this issue. Therefore, we have included the response to this question in the global rebuttal. Please refer to Q1 of the global rebuttal for the details.

Q3: Regarding eQSI-NMS, there are questions about the clarity and effectiveness of the methods. The pseudo-code in Appendix E. 2 is difficult to understand, and there might be an issue with the line "for $s\in\mathcal{S}$ do $s\leftarrow -s$;" in eQSI-NMS. It’s unclear how this part of the code functions and whether it introduces any problems.

A3: There was indeed a mistake here, and we appreciate your feedback. What we intended to express is "for $c \in \mathcal{C}$ do $c \leftarrow -c$" This is because we should first sort $\mathcal{C}$ in ascending order. Next, by maintaining a stack, we can find the position of the last element greater than the current confidence score before it in $\mathcal{O}(n)$ time; let’s call this algorithm $A$. Additionally, we need to find the first element greater than the current confidence score after it, which can be done by sorting $-\mathcal{C}$ in ascending order and then performing algorithm $A$. This explanation is indeed prone to misunderstanding, and we will rewrite this part of the pseudo-code in our revised version. We will first sort $\mathcal{C}$ in ascending order, then process it from front to back and back to front once each. However, our implementation is correct, and we suggest you refer to eQSINMS.hpp in the supplementary material. Our code is easy to understand.

Q4: The evaluation is primarily limited to the YOLOv8-N model on the MS COCO 2017 dataset. To gain a more comprehensive understanding of the algorithms' generalizability, broader evaluations across various models and datasets would be beneficial.

A4: We evaluated our methods on various datasets and models. On COCO 2017, we tested YOLOv8 models (one-stage, anchor-free model), YOLOv5 models (one-stage, anchor-based model), and Faster R-CNN models (two-stage, anchor-based model), as detailed in Table 1 of Section 5.2. We also tested the YOLOv8 models on the more mature and robust Open Images V7 dataset, as shown in Table 2.

Thank you for your detailed review and valuable feedback. We appreciate your recognition of our innovative approach, comprehensive evaluation, and practical impact. Below, we will address each of your concerns one by one.

Q1: Details on Graph Construction (Line 99-104): The paper mentions the construction of graph G using bounding boxes and suppression relationships. Could you elaborate on the computational overhead of this graph construction process and its impact on the overall efficiency of NMS?

A1: The computational overhead of constructing the graph in our algorithms is zero. Constructing the graph and topological sorting incurs an additional $\mathcal{O}(\vert \mathcal{V}\vert + \vert \mathcal{E}\vert)$ computational overhead. Although this does not affect the complexity of our methods, it can slow down their practical performance. To address this issue, we design our algorithm such that the order of the nodes we iterate over follows a valid topological sort. Therefore, dynamic programming can be completed without explicitly constructing the graph. As a result, our algorithm does not incur the extra overhead of graph construction.

For QSI-NMS, lines174-177 explain why explicit graph construction is unnecessary. The same applies to BOE-NMS, where sorting the boxes by confidence scores from high to low already provides a valid topological sort. We can also quickly locate the mutually suppressing boxes withoud sorting, thereby obtaining $\mathcal{G}$, and performing dynamic programming yields the same results.

However, In BOE-NMS, not sorting in advance would introduce additional computational overhead of constructing the graph and topological sorting. We conducted an experiment to support our analysis. We did not sort by confidence but performed dynamic programming at the end while keeping everything else unchanged. The results on YOLOv8-N are shown in the table below:

Q2: Experimental Setup (Line 260-265): The results presented are impressive; however, could more information be provided on how the different configurations of bounding boxes were handled during the experiments, especially concerning their distribution and density?

A2: Our experimental data is derived from the actual outputs of commonly used models on public datasets, as described in Section 5.1. Each bounding box is represented by $x, y, w, h$ to denote its position and size, along with a confidence score $score$, as defined in Section 2. For detailed statistics related to the bounding boxes, please refer to Appendix D.

Q3: Proof of Theorem 1 (Line 510-520): Could you clarify how the dynamic programming approach adapts to variations in graph structure, particularly for non-standard configurations of bounding boxes?

A3: As proven in Theorem 1, variations in the graph structure do not affect the correctness of the results obtained through dynamic programming. However, the structure of the graph can influence the efficiency of dynamic programming since its complexity is $\mathcal{O}(\vert\mathcal{V}\vert +\vert\mathcal{E}\vert)$. By pre-sorting, the complexity can be reduced to $\mathcal{O}(\vert\mathcal{V}\vert\log\vert\mathcal{V}\vert+\vert\mathcal{V}\vert)$. Therefore, when the graph has many nodes or edges, the efficiency of dynamic programming decreases, especially in cases where all bounding boxes are very dense (which are rare in real-world data).

Q4: Complexity of Graph-Theoretical Analysis: The paper's reliance on graph theory might limit its accessibility to those without a background in this area. The proofs and theoretical explanations are dense and could be challenging to follow for non-specialists.

A4: We understand that the graph-theoretical aspects may be complex. To address this, we've included detailed explanations and supplementary materials to clarify the key points(see Appendix A). Additionally, we emphasize the practical applications to highlight the relevance of our work.

Q5: Limited Discussion on Scalability: While the paper shows efficiency improvements, it does not extensively discuss the scalability of the proposed methods across different hardware or larger datasets beyond those tested.

A5: We did not have enough time to test on different hardware environments, but our methods indeed reduce computational overhead (see Appendix D.3, Figure 6). Moreover, we implemented our methods in the torchvision library, and their performance surpasses that of highly parallel CUDA NMS (see Appendix D.3), demonstrating that the efficiency of our methods does not rely on specific hardware and can be applied to low-power edge devices.

Additionally, we tested on a larger and more robust dataset, Open Images V7. Please refer to Section 5.2, Table 2 for details.

Q6: Dependency on Specific Conditions: The effectiveness of the proposed methods may depend heavily on the characteristics of the data and the specific architectures of the detection systems used, which may not generalize well to all types of object detection tasks.

A6: We believe that our analysis of the characteristics of $\mathcal{G}$ is widely applicable (Lines 126-135).

Thank you for your valuable feedback and for acknowledging the value of our work. We will address your questions and concerns in the following responses.

Q1: A case study that illustrates the overly suppressed samples is welcomed.

A1: This question is fundamental and others are also interested in this issue. The proof of Theorem 4 demonstrates that BOE-NMS does not overly suppress boxes compared to Original NMS, leading to the same results. In QSI-NMS, however, in some special cases, nodes within the same WCC might be incorrectly assigned to different subproblems, resulting in retaining some boxes that should have been suppressed. To provide a comprehensive and clear explanation, we have included our response in the global rebuttal. We kindly ask you to review our response in A1 of the global rebuttal.

Q2: How was the average latency calculated, more information if preferred. This is not clear. Please report the time of graph construction and the time of NMS, respectively.

A2: The latency calculation begins from the input of bounding boxes and ends when the retained bounding boxes are output. For a dataset containing $N$ images, latency is measured by using the bounding boxes generated per image as input, and the total latency for the $N$ images is averaged. To mitigate random errors, this measurement is repeated 5 times, and the average of these measurements is used as the final average latency. Thus, the average latency is the average time taken to execute NMS.

We do not need any additional time to construct the graph. Constructing the graph and topological sorting incurs an additional $\mathcal{O}(\vert \mathcal{V}\vert + \vert \mathcal{E}\vert)$ computational overhead. Although this does not affect the complexity of our methods, it can slow down their practical performance. To address this issue, we design our algorithm such that the order of the nodes we iterate over follows a valid topological sort. Therefore, dynamic programming can be completed without explicitly constructing the graph. As a result, our algorithm does not incur the extra overhead of graph construction.

For QSI-NMS, lines 174-177 explain why explicit graph construction is unnecessary. The same applies to BOE-NMS, where sorting the boxes by confidence scores from high to low already provides a valid topological sort. We can also quickly locate the mutually suppressing boxes without sorting, thereby obtaining $\mathcal{G}$, and performing dynamic programming yields the same results.

However, In BOE-NMS, not sorting in advance would introduce additional computational overhead of constructing the graph and topological sorting. Please check the table below:

Q3: How is the performance of the proposed algorithm on the Yolo V10 and mask RCNN.

A3: At the time of conducting this research, YOLOv10 had not yet been open-sourced, and we currently do not have sufficient time to include experiments with it. However, we tested our methods on the Instance segmentation task using Mask R-CNN and YOLOv8, where our methods also demonstrated significant superiority over others. Please refer to the tables below.

Table 1: Latency ($\mu s$) of various methods

Table 2: Box mAP(%) of various methods

Table 3: Mask mAP(%) of various methods

Q4: Although the proposed method is tested on the proposed NMS-Bench, experimental results in detection bench-mark algorithms are still preferred.

A4: To demonstrate the practical value of our methods, we not only tested them on NMS-Bench but also implemented them in torchvision. The results show that our methods are more efficient than the highly parallel CUDA NMS, which is the currently used program for NMS. For detailed information and experimental results, please refer to Appendix D.3.

Thank you for your feedback and for recognizing the value of our new graph theory perspective on non-maximum suppression. We will address your concerns in the following responses.

Q1: The worst case complexity of the proposed approaches is still $\mathcal{O}(n \log n)$, while other approaches, stated above claim $\mathcal{O}(n)$ complexity. Does this imply the other approaches scale better?

A1: Among the papers you mentioned, only PSRR-MaxpoolNMS claims to achieve $\mathcal{O}(n)$ complexity. However, we do not believe that PSRR-MaxpoolNMS has better scalability compared to our methods for two reasons:

First, we implemented PSRR-MaxpoolNMS and conducted efficiency comparisons. To better illustrate the impact of bounding box count on runtime, we performed experiments on YOLOv5-N, which has the highest number of bounding boxes, as shown in Figure 3 (a) of the global rebuttal PDF. Original NMS has the highest time cost due to its quadratic growth. For a clearer comparison between our methods and PSRR-MaxpoolNMS, we excluded Original NMS, as shown in Figure 3 (b). As the number of boxes increases, PSRR-MaxpoolNMS is faster than BOE-NMS and QSI-NMS but consistently slower than eQSI-NMS.

Second, strictly speaking, the complexity of PSRR-MaxpoolNMS is not $\mathcal{O}(n)$. PSRR-MaxpoolNMS requires prior knowledge of the input image size and generates confidence score maps related to the size of the image. This aspect is not considered in the complexity analysis (whereas our methods are designed and analyzed independently of the image size). During the Channel Recovery stage of PSRR-MaxpoolNMS, the complexity of computing the nearest distances for channel mapping is $\mathcal{O}(n_sn_rn)$, where $n_s$ and $n_r$ represent the number of anchor box scales and ratios, respectively. These quantities vary with different datasets and detectors and increase as image size and object count increase. The remaining stages: Spatial Recovery, Pyramid MaxpoolNMS, and Shifted MaxpoolNMS can all be completed in $\mathcal{O}(n)$ time. Thus, the overall complexity of PSRR-MaxpoolNMS is $\mathcal{O}(n_s n_r\lfloor \frac{W}{\beta} \rceil \lfloor \frac{H}{\beta} \rceil + n_s n_r n)$.

Q2: The paper does not compare against (or even cite) other approximations to NMS proposed in the literature such as MaxPoolNMS, PSRR-MaxpoolNMS or ASAP-NMS. It's unclear how the contribution, and performance of proposed approximations differs from the literature.

A2: Our research focuses on NMS methods applicable to general cases, so we inadvertently missed these important papers. Thank you very much for pointing this out. We will cite these papers in our revised version. Next, we will illustrate how our contributions differ from these papers through the following comparisons:

Maxpool NMS and ASAP-NMS can only be used in the first stage of two-stage detectors, while PSRR-MaxpoolNMS, although applicable to various stages, is limited to anchor-based models. Our methods, however, can be used in any stage of any detector because we address general cases (see Section 2).

The complexity of Maxpool NMS is $\mathcal{O}(n_sn_r\lfloor\frac{W}{\beta}\rceil\lfloor\frac{H}{\beta}\rceil+n\log n)$, ASAP-NMS is $\mathcal{O}(n^2)$, and the complexity of PSRR-MaxpoolNMS has been analyzed in A1. None of these methods are more efficient than eQSI-NMS.

These methods involve many manually defined hyperparameters and are complex to implement, which limits their generalization across different models and datasets. In contrast, our methods require no additional parameters beyond those in Original NMS and are easy to implement.

Q3: The idea behind BOE-NMS, using locality suppression relationships is already explored in the above works. What is the difference between BOE-NMS and these methods?

A3: Although these methods also consider locality, BOE-NMS employs a fundamentally different approach and analysis. Not suppressing non-overlapping boxes is a very intuitive idea, but the key is how to locate these boxes. We discuss this issue in Appendix C.3 and prove that directly determining non-overlapping boxes is a more difficult problem than checking whether the centroid of one box falls within another box (the basic idea of BOE-NMS), as shown in Appendix B.6. Therefore, BOE-NMS can be efficiently implemented. In contrast, methods in the literature use complex techniques to find approximate solutions to this problem. Additionally, BOE-NMS is rigorously proven not to cause any loss of accuracy (Theorem 4), whereas the methods in the literature are not as rigorous and exhibit some degree of accuracy degradation.

Q4: Can this approach be utilized for two-stage object detectors as well for both stages of NMS? The proposed benchmark only applies the methods this for single-stage object detectors, it's unclear how the method performs on two-stage detectors.

A4: Yes, our methods are applicable to various stages of various detectors. We tested not only one-stage detectors but also two-stage detectors (Faster R-CNN). Please refer to Table 1 in Section 5.2. We have also added experiments for the first stage in Faster R-CNN. The results demonstrate that our methods still exhibit strong performance advantages, with QSI-NMS and eQSI-NMS even surpassing Original NMS in terms of accuracy. Please see the tables below.

Table 1:R50-FPN

Table 2:R101-FPN

Table 3:X101-FPN