重定位非極大值抑制算法

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

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

1 引 言

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

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

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

2 相關(guān)工作

在目標(biāo)檢測任務(wù)中，通常使用傳統(tǒng)NMS 算法和Soft-NMS 算法對預(yù)測階段得到的候選框進行保留和抑制處理。

2.1 傳統(tǒng)NMS

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

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

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

2.2 Soft-NMS

Soft-NMS 算法是一種基于傳統(tǒng)NMS 的改進算法。與傳統(tǒng)NMS 算法相同，其候選框也根據(jù)類別置信度排序，置信度得分最高的候選框被選為最優(yōu)邊界框。不同于傳統(tǒng)NMS 算法，Soft-NMS 算法采用“權(quán)值懲罰”的方式調(diào)整類別置信度，即：

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

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值隨著重疊面積的改變呈現(xiàn)線性變化，如圖2 所示。相比之下，IoU 的變化是非線性的，在一定程度上其閾值更加敏感。為了證明在衡量邊界框之間的距離時P值優(yōu)于IoU，4.2.2節(jié)對P和IoU 在R-NMS 算法上的性能進行了比較。

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

3.2 坐標(biāo)標(biāo)準(zhǔn)化

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

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

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

式中：norm 用于坐標(biāo)標(biāo)準(zhǔn)化，X，Y分別表示兩個框的橫坐標(biāo)、縱坐標(biāo)的集合，max(X)，min(X)表示兩個框中橫坐標(biāo)的最大值和最小值。利用橫坐標(biāo)xi到最小值的距離比上最大值和最小值之間的距離即可得到標(biāo)準(zhǔn)化后的橫坐標(biāo)，縱坐標(biāo)的標(biāo)準(zhǔn)化計算過程和橫坐標(biāo)的相同。對圖3 中右側(cè)的兩個邊界框的坐標(biāo)執(zhí)行標(biāo)準(zhǔn)化操作后，它們的邊 界 框 坐 標(biāo) 由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。同理，圖中左側(cè)邊界框的坐標(biāo)分 別 由a(2，4)，b(3，6)，c(3，5)，d(4，7) 轉(zhuǎn) 為a(0，0)，b(0.5，0.667)，c(0.5，0.333)，d(1，1)，最終P值為1.666。顯然，坐標(biāo)標(biāo)準(zhǔn)化后兩組邊界框的P值不相同。因此，標(biāo)準(zhǔn)化坐標(biāo)后計算得到的P值能夠區(qū)分邊界框的重合情況。

3.3 最優(yōu)邊界框重定位

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

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

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

3.4 邊界框的保留和抑制

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

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

R-NMS 算法的執(zhí)行步驟如下：

4 實驗分析與討論

4.1 實驗數(shù)據(jù)、模型及參數(shù)

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

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

4.2 實驗結(jié)果

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

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

圖6 YOLOv3 算法在VOC 數(shù)據(jù)集上的部分檢測結(jié)果Fig.6 Experimental results of VOC test dataset on YOLOv3

圖7 YOLOv3 算法在COCO 數(shù)據(jù)集上的部分檢測結(jié)果Fig.7 Partial experimental results of COCO test dataset on YOLOv3

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

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

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

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

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

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

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

表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 時最優(yōu)邊界框及其周圍候選框的位置信息（彩圖見期刊電子版），左圖的綠框代表最優(yōu)邊界框，紅框代表最優(yōu)邊界框周圍接近度P小于閾值的候選框，右圖綠框表示利用重定位選框法得到的最優(yōu)邊界框。當(dāng)接近度P的閾值 為0.5 時，圖10 中R-NMS 算 法 的mAP 由67.2%提高到67.6%，此時最優(yōu)邊界框周圍的候選框數(shù)量較少但定位精度較高，利用它們的位置信息能夠提高最優(yōu)邊界框?qū)ξ矬w的包圍程度。因此，圖9（a）右圖中最優(yōu)邊界框的定位精度相較于左圖有所提升。當(dāng)接近度P的閾值為1.0 時，最優(yōu)邊界框周圍候選框的數(shù)量增多，但是這些新增候選框遠(yuǎn)離最優(yōu)邊界框并且包圍物體的程度較低，利用該位置信息對最優(yōu)邊界框重定位會導(dǎo)致定位精度下降。 此時，R-NMS 算法在VOC2012 測試集上的mAP 下降至67%，低于傳統(tǒng)NMS 算法的67.2%。

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

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

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

4.3 定性分析

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

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

5 結(jié) 論

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