重定位非極大值抑制算法

蘇樹智，陳潤斌，朱彥敏，蔣博文

（1. 安徽理工大學 計算機科學與工程學院，安徽 淮南 232001；2. 合肥綜合性國家科學中心能源研究院（安徽省能源實驗室），安徽 合肥 230031；3. 安徽理工大學 機械工程學院，安徽 淮南 232001）

1 引 言

目標檢測［1］是計算機視覺的主要研究領域之一。它的任務是找出圖像或視頻中人們感興趣的物體，并檢測出它們的位置和大小。不同于圖像分類［2］任務，目標檢測不僅要解決分類問題，還要解決定位問題。此外，目標檢測構成了許多其他計算機視覺任務的基礎，例如實例分割［3］、圖像標注［4］和目標跟蹤［5］。自2014 年區域卷積網絡目標檢測算法［6］問世以來，基于卷積神經網絡［7］的目標檢測算法一直處于研究的前沿，相較于傳統的目標檢測算法，精度和速度都有了很大的提升。

基于卷積神經網絡的目標檢測算法［8-13］在預測階段返回大量位置和尺寸不同的候選框，這些候選框大部分聚集在可能包含感興趣目標的區域，對這些候選框執行保留和抑制操作很有必要。這些候選框只包含坐標與類別置信度信息。其中，坐標并不能作為決定最優邊界框的依據，而類別置信度作為一個類別概率標簽，用于表示候選框中存在某個類別物體的概率，類別置信度越高，候選框中存在某個類別物體的可能性越大。最優邊界框的選定會影響后續的候選框抑制操作，如果不選擇類別置信度得分最高的候選框而是選擇其它候選框作為最優邊界框，會導致類別置信度得分最高的候選框在候選框抑制階段被移除，重復此操作，使得所保留的大部分最優邊界框的定位精度較低，進而導致檢測精度下降。因此，傳統非極大值抑制（Non-Maximum Suppression，NMS）算法通常將類別置信度作為最優邊界框的評價指標，對候選框按類別置信度降序排列［13］，并且選擇類別置信度得分最高的候選框作為最優邊界框［14-16］。然后，保留最優邊界框并利用該框抑制與其交并比（Intersection over Union，IoU）大于一定閾值的候選框，如果在這些候選框中有多個對象存在，則選擇剩余候選框中類別置信度最高的候選框作為下一個對象的最優邊界框，并重復抑制過程，直到候選框全部被移除。傳統NMS 算法僅依靠類別置信度選擇最優候選框，導致其定位精度較差。類別置信度是一個類別概率標簽，它和定位精度之間的相關性很低［17］，因此類別置信度并不能有效代表定位精度［18］。傳統NMS算法使用它來決定最優邊界框意味著很容易返回次優邊界框。 雖然出現了很多改進算法［17，19-20］，但這些算法大部分需要在主干網絡添加新的損失函數并重新訓練目標檢測模型，增加了時間成本。Jiang 等［17］提出在網絡中添加預測分支來學習定位置信度，使用定位置信度作為最優候選框的篩選依據。He 等［15］提出在網絡中添加邊界框回歸損失函數，用于學習邊界框變換和定位置信度。

上述改進算法通過為每個候選框分配利用網絡學習到的定位置信度來避免選擇最優邊界框時依賴類別置信度。傳統NMS 算法認為與最優邊界框重疊越大的候選框，越有可能是冗余框，因此，設定閾值用于判斷候選框是否是冗余框。Liu 等［19］發現在不同的目標檢測場景下設置不同的閾值能夠提高召回率，提出了Adaptive-NMS 算法。Adaptive-NMS 算法通過在網絡中添加密度預測模塊來學習框的密度，根據圖像中物體分布的稀疏程度確定閾值從而獲得更高的召回率。Soft-NMS 算法［21］通過衰減而不是消除高度重疊邊界框的類別置信度的策略，在一定程度上提高了召回率。但是上述算法的選框思想完全源自傳統NMS 算法，即選擇類別置信度得分最高的候選框為最優邊界框，并不能從根本上解決所選最優邊界框定位精度不高的問題。為了解決該問題，本文提出一種重定位非極大值抑制（Relocation Non-Maximum Suppression，RNMS）算法。該算法通過衡量邊界框之間的距離，構建了一種利用最優邊界框與其周圍候選框之間的位置關系調整最優邊界框位置的重定位選框法，在PASCAL VOC2012 和MS COCO2014 數據集上的實驗表明，R-NMS 算法的mAP 相較于傳統NMS 算法和Soft-NMS 算法有顯著的提高。

2 相關工作

在目標檢測任務中，通常使用傳統NMS 算法和Soft-NMS 算法對預測階段得到的候選框進行保留和抑制處理。

2.1 傳統NMS

傳統NMS 算法中，候選框抑制過程中類別置信度Sf的計算過程如下：

式中：M代表最優邊界框，bi為候選框。IoU 用于衡量兩個框之間的重合程度。

式中Nt為人工設定的閾值。當框M與bi框的重合程度大于N t時，bi框的類別置信度置為0，bi框被框M抑制。

2.2 Soft-NMS

Soft-NMS 算法是一種基于傳統NMS 的改進算法。與傳統NMS 算法相同，其候選框也根據類別置信度排序，置信度得分最高的候選框被選為最優邊界框。不同于傳統NMS 算法，Soft-NMS 算法采用“權值懲罰”的方式調整類別置信度，即：

在Soft-NMS 算法中，與框M有顯著重疊的候選框不會立即被移除，但是它們的置信度得分會衰減。這一方式有效地提高了召回率，但Soft-NMS 算法作為傳統NMS 算法的改進算法，其選擇最優邊界框的思想完全繼承了傳統NMS 算法，不能從根本上解決所選最優邊界框定位精度不高的問題。

3 R-NMS 算法

3.1 接近度P

曼哈頓距離是兩點之間的垂直和水平距離之和，點u(x1，y1)和v(p1，q1)之間的曼哈頓距離HM(u，v)為：

本文提出兩個邊界框之間的接近度P可以用 圖1 中 點u(x1，y1)，v(p1，q1)之 間 的 曼 哈 頓 距離以及點m(x2，y2)，n(p2，q2)之間的曼哈頓距離之和表示：

圖1 曼哈頓距離Fig.1 Manhattan distance

接近度P和IoU 都能表示邊界框之間的接近程度，然而P值隨著重疊面積的改變呈現線性變化，如圖2 所示。相比之下，IoU 的變化是非線性的，在一定程度上其閾值更加敏感。為了證明在衡量邊界框之間的距離時P值優于IoU，4.2.2節對P和IoU 在R-NMS 算法上的性能進行了比較。

圖2 P 和IoU 的 對 比Fig.2 Stability of P compared to IoU

3.2 坐標標準化

接近度P在邊界框尺寸相似的情況下能夠有效地表示邊界框之間的距離關系。然而，在目標檢測的后處理階段存在大量尺寸不同的候選框，圖3 在右側顯示了兩個大邊框，左側有兩個小框。對每組邊框進行P值計算，得到：

圖3 兩組框在坐標軸上的展示Fig.3 Display of two sets of boxes on coordinate axes

顯然，當兩個框的尺寸有明顯差異時，P值并不能準確衡量它們的重合程度。為了解決這一問題，本文引入了邊界框坐標點標準化這一方法，該方法能夠使坐標被固定到0～1 之間，同時還能保持邊界框之間的關系。坐標標準化公式如下：

式中：norm 用于坐標標準化，X，Y分別表示兩個框的橫坐標、縱坐標的集合，max(X)，min(X)表示兩個框中橫坐標的最大值和最小值。利用橫坐標xi到最小值的距離比上最大值和最小值之間的距離即可得到標準化后的橫坐標，縱坐標的標準化計算過程和橫坐標的相同。對圖3 中右側的兩個邊界框的坐標執行標準化操作后，它們的邊 界 框 坐 標 由u(10，2)，v(20，10)，m(9，3)，n(19，11) 變 換 為u(0.091，0)，v(1，0.899)，m(0，0.111)，n(0.909，1)。它們的P值利用式（8）計算后為0.404。同理，圖中左側邊界框的坐標分 別 由a(2，4)，b(3，6)，c(3，5)，d(4，7) 轉 為a(0，0)，b(0.5，0.667)，c(0.5，0.333)，d(1，1)，最終P值為1.666。顯然，坐標標準化后兩組邊界框的P值不相同。因此，標準化坐標后計算得到的P值能夠區分邊界框的重合情況。

3.3 最優邊界框重定位

傳統NMS 和Soft-NMS 算法選取最優候選框的過程是一致的。首先，候選框按類別置信度降序排列，然后選擇類別置信度得分最高的候選框為最優邊界框。然而，候選框的定位精度和類別置信度之間的相關性不大，類別置信度得分最高的候選框不一定是最優邊界框。為此，RNMS 算法在得到最優邊界框的基礎之上，利用重定位選框法對它執行重定位操作，重定位過程如圖4 所示。第一步，找到與最優邊界框的接近度P小于閾值（閾值取值在0～1.0，取0.3～0.5最佳）的候選框；第二步，計算最優邊界框和符合第一步要求的候選框之間的平均偏移量；第三步，最優邊界框利用第二步獲取到偏移量進行重定位。計算過程如下：

圖4 邊界框重定位流程Fig.4 Process of relocating bounding boxes

式中：B為符合條件的候選框集合，Bi為候選框，O為B中所有候選框與最優邊界框M的偏移量。最優邊界框M加上偏移量O即可得到R-NMS 算法的最優邊界框MR。

3.4 邊界框的保留和抑制

在模型預測階段，同一個目標上會產生大量相似的候選框，存在大量的冗余數據，因此邊界框的保留和抑制至關重要。在對這些邊界框進行處理時，首先根據類別置信度對候選框排序，選擇得分最高的候選框作為最優邊界框，然后借助重定位選框法對最優邊界框執行重定位操作得到新的最優邊界框。最后，采用最優邊界框抑制其他候選框。圖5 中，左圖的紅框為借助重定位選框法得到的最優邊界框，利用該最優邊界框抑制藍色的候選框，最終只保留紅色邊界框（彩圖見期刊電子版）。

圖5 邊界框的保留與抑制過程Fig.5 Process of reserving and suppressing bounding boxes

R-NMS 算法的執行步驟如下：

4 實驗分析與討論

4.1 實驗數據、模型及參數

本文的實驗建立在公開可用的MS COCO2014 和PASCAL VOC2012 數據集上。MS COCO2014 數據集共有80 個類、164 042 張圖片，可分為訓練集、驗證集和測試集，分別有82 783，40 504，40 755 張 圖 片。在PASCAL VOC2012中訓練、測試及驗證數據集共包含17 125 幅圖像，20 個類。這些數據集用于訓練和評估深度學習目標檢測模型。

實驗選用pytorch 框架，使用python3.8 編程，硬件設備中CPU 使用AMD Ryzen 9 3900X，內存為32 GB，GPU 型號為GeForce RTX 2080Ti，顯存為11 GB，系統環境為Ubuntu18.04。使用目標檢測器YOLOv3、YOLOv5以及Faster RCNN 對傳統NMS，Soft-NMS 和RNMS 算法的性能進行了比較評估。實驗過程中，類別置信度的閾值設為0.2，IoU 的閾值和接近度P的閾值都設為0.5。

4.2 實驗結果

4.2.1 R-NMS 算法和其他算法的性能對比

利用YOLOv3，YOLOv5 以及Faster RCNN算法在PASCAL VOC2012 和MS COCO2014測試集上比較了傳統NMS，Soft-NMS 和RNMS 的性能，結果如表1～表2 所示。與傳統NMS 相比，使用Soft-NMS 作為目標檢測任務的后處理算法時，在抑制邊界框階段對冗余邊界框的類別置信度得分采取了“權值懲罰”策略，一定程度上減少了目標漏檢，使得召回率有所提高，但是同時帶來了目標重復檢測問題，如圖6～圖7所示，部分目標被重復檢測。重復檢測導致精確率下降。在PASCAL VOC2012 測試集上，YOLOv3 算法的精確率由80.6%降至80.3%，YOLOv5 算法的精確率降低了0.1%。在MS COCO2014 測 試 集 上，YOLOv3 算 法 和YOLOv5 算法的精確率都有所下降。

圖6 YOLOv3 算法在VOC 數據集上的部分檢測結果Fig.6 Experimental results of VOC test dataset on YOLOv3

圖7 YOLOv3 算法在COCO 數據集上的部分檢測結果Fig.7 Partial experimental results of COCO test dataset on YOLOv3

表1 三種不同NMS 算法在VOC 數據集上的實驗結果Tab.1 Experimental results of three different NMS algorithms on VOC test dataset （%）

表2 三種不同NMS 算法在COCO 數據集上的實驗結果Tab.2 Experimental results of three different NMS algorithms on COCO test dataset （%）

本文提出的R-NMS 算法，在傳統NMS 和Soft-NMS 算法所選的最優邊界框基礎上充分利用其周圍框的位置信息，對最優邊界框執行重定位，最終獲取到定位精確的最優邊界框。在PASCAL VOC2012 測試集上，R-NMS 作為YOLOv3 和YOLOv5 算 法的后處理算法，R-NMS 算法的精確率高于傳統NMS 算法的80.6%，82.6%，R-NMS 算法的召回率也從Soft-NMS 算法的72.6%，77.7% 提升至72.9%，78.3%。YOLOv3 算法的mAP@0.5：0.95 指標分別提升了0.7%，0.5%。YOLOv5 算法的mAP@0.5∶0.95 由 傳 統NMS 算 法 的56.7%，Soft-NMS 的56.8% 提升至R-NMS 的57.2%。在MS COCO2014 測 試 集 上，YOLOv3 和YOLOv5 的 實 驗結果如表2 所示。R-NMS 算法的mAP@0.5∶0.95 指標都優于傳統NMS 算法和Soft-NMS 算法，召回率和精確率同上。在此基礎之上，對3 種非極大值抑制算法在PASCAL VOC2012 測試集的實驗結果進行了展示，如圖6～圖7 所示，圖中傳統NMS 和Soft-NMS 算法所選的最優邊界框經過R-NMS 算法的重定位選框法處理后定位精度得到提升。圖6 和圖7 只選取了部分檢測結果，利用R-NMS 算法得到的最優邊界框能準確地包圍目標，傳統NMS，Soft-NMS 算法與之相比存在明顯的差距。圖8 展示了Faster RCNN 算法在PASCAL VOC 2012測試集上的部分實驗結果，在mAP 這一指標上R-NMS 算法相較于傳統NMS，Soft-NMS算法分別提高了0.53%，0.36%。

圖8 Faster RCNN 算法在PASCAL VOC 上的實驗結果Fig.8 Experimental results of VOC test dataset on Faster RCNN

以上實驗結果證明了R-NMS 算法的性能優于傳統NMS 和Soft-NMS 算法。相比傳統NMS算法和Soft-NMS 算法，R-NMS 算法不僅解決了傳統NMS 算法召回率低的問題，還提高了精確率。

4.2.2 接近度P和IoU 的消融實驗

本節比較了在R-NMS 算法上IoU 和接近度P的性能。實驗建立在PASCAL VOC2012 數據集上，實驗結果如表3 所示，接近度P在R-NMS算法上的各個性能評價指標上的表現均優于IoU。因此，當最優邊界框周圍存在大量候選框時，接近度P能夠幫助R-NMS 算法選取更加合適的候選框用于后續重定位操作。

表3 P 和IoU 在R-NMS 算法上的實驗對比Tab.3 Experimental results of R-NMS with P or IoU （%）

4.2.3 R-NMS 算法的閾值敏感性分析

實驗中使用YOLOv3 檢測器和PASCAL VOC2012 測 試 集，對R-NMS 算 法 中 接 近 度P的閾值進行了敏感性分析。圖9 展示了接近度P的閾值分別為0.5，1.0 時最優邊界框及其周圍候選框的位置信息（彩圖見期刊電子版），左圖的綠框代表最優邊界框，紅框代表最優邊界框周圍接近度P小于閾值的候選框，右圖綠框表示利用重定位選框法得到的最優邊界框。當接近度P的閾值 為0.5 時，圖10 中R-NMS 算 法 的mAP 由67.2%提高到67.6%，此時最優邊界框周圍的候選框數量較少但定位精度較高，利用它們的位置信息能夠提高最優邊界框對物體的包圍程度。因此，圖9（a）右圖中最優邊界框的定位精度相較于左圖有所提升。當接近度P的閾值為1.0 時，最優邊界框周圍候選框的數量增多，但是這些新增候選框遠離最優邊界框并且包圍物體的程度較低，利用該位置信息對最優邊界框重定位會導致定位精度下降。 此時，R-NMS 算法在VOC2012 測試集上的mAP 下降至67%，低于傳統NMS 算法的67.2%。

圖9 不同接近度閾值下的最優邊界框Fig.9 Optimal bounding box with different proximity thresholds

圖10 接近度的閾值敏感性分析Fig.10 Threshold sensitivity analysis of proximity

當接近度P的閾值較低時，最優邊界框能夠利用的有效位置信息較多，使得重定位選框法得到的最優邊界框包圍物體的程度提高。隨著閾值的提高，最優邊界框獲得更多周圍候選框的位置信息，但是這些位置信息無效并且會降低最優邊界框的定位精度。由此可知，R-NM 法的性能在閾值較低時能夠獲得更好的性能。

4.3 定性分析

傳統NMS 算法和Soft-NMS 算法選擇類別置信度最高的候選框作為最優邊界框，然后借助該框抑制任何與其高度重合的候選框，從而完成候選框的保留與抑制。但是在實驗中發現，類別置信度和定位之間的相關性不高，有時候置信度低的邊界框能更好地包圍目標。圖11 中左側的檢測結果來自傳統NMS 算法，而右側的檢測結果來自實驗。傳統NMS 算法只是簡單地返回類別置信度最高的邊界框，即使該邊界框不是很準確，忽略了類別置信度得分和定位精度之間的相關性很小。在傳統NMS 算法的處理下，包圍騎手的邊界框的類別置信度為0.48。但是候選框集合中存在另外一個能夠將騎手包圍的候選框，而該候選框的類別置信度只有0.40。顯然，傳統NMS 算法只選擇了類別置信度得分最高的候選框為最優邊界框，而置信度得分較低但是能夠精確包圍目標的候選框卻被丟棄。本文提出的RNMS 算法充分考慮到最優邊界框周圍存在類別置信度得分較低但是與最優邊界框重合程度較高的候選框，充分利用它們的位置信息并融合到最優邊界框，就能得到定位更加準確的最優邊界框。上述實驗證明了R-NMS 算法的有效性，利用R-NMS 算法處理得到的最優邊界框與真實框的重合程度更高，因此R-NMS 算法相較于傳統NMS，Soft-NMS 算法，所有評價指標都有明顯的提升。

圖11 定位精度和置信度的關系Fig.11 Relationship between classification confidence and positioning accuracy

5 結 論

傳統NMS 算法及其變體Soft-NMS 算法在選框階段根據類別置信度選出最優邊界框，而定位精度和類別置信度之間的相關性很低，類別置信度得分最高的候選框的不一定是最優邊界框。針對上述問題，本文提出R-NMS 算法。該算法綜合考慮最優邊界框與其周圍候選框的位置信息，構建了一種重定位選框法，最優邊界框可以借助該方法重新調整位置，最終提高其定位精度。實驗結果證明：采用PASCAL VOC2012 數據集測試，與傳統NMS 算法和Soft-NMS 算法相比，R-NMS 算法在目標檢測器YOLOv3 上的mAP 分 別 提 高0.7%，0.5%，R-NMS 算 法 在Faster-RCNN 上的mAP 達到80.83%。該算法能提高目標檢測器的檢測精度。