簡単なNMSの改善手法：Soft-NMS -- Improving Object Detection With One Line of Code

# 概要
物体検出には様々な手法がありますが、多くの手法で共通する後処理として、NMS(Non-Maximum Suppression)があります。これは、同一の物体に対して重複して得られた検出候補のなかから、もっともスコアの高いもののみを残して、それと重なりの多い候補は除外するという操作を行うことで、検出精度を高めようという方法です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4010/59fd0797-1a73-c30c-7b32-94d3a44b46d4.png)

NMSは、物体のカテゴリごとに行われます。このとき、以下の図のように、同一のカテゴリの物体が重なって存在しているときに少々問題が生じます。赤の矩形で囲まれた馬と緑の矩形で囲まれた馬は、どちらもスコアは0.95, 0.80といずれも高いですが、かなりの部分が重なっています。NMSは候補同士の重なり具合を表すIoUによるしきい値によって、その候補を除外するか否かを決めるので、しきい値によっては緑の馬の方が赤い馬と同一と見なされ、検出候補から除外されてしまします。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4010/a8fdf8d2-f3ec-5088-3849-03cc0710bc46.png)


このような問題を軽減するために提案されたのが、Soft-NMSです。Soft-NMSは、通常のNMSをハードな方法だとすれば、ソフトな方法と言えます。Soft-NMSでは候補間の重なりが大きいときに、片方を除外せずに、スコアを現象させます。例えば、先程の緑の方の候補は、赤の候補と重なりが大きいので、スコアを下げられます。最終的にはスコアのしきい値を適用するので、あまりにも重複が大きい候補はスコアによって除外されますが、十分にスコアが大きいのであれば最終的な検出結果に残ることになります。

なお、直接モデルに重複除去の仕組みを入れる手法[^1]もあり、こちらのほうが精度的に良い傾向にありますが、Soft-NMSは既存のNMSに対してほんの少し変更を加えて実現できるという点で優れています。

[^1]: https://qiita.com/agatan/items/1c2cadeaabfc9f122f6f

# 書誌情報
- Bodla, Navaneeth, et al. "Soft-NMS--improving object detection with one line of code." Proceedings of the IEEE international conference on computer vision. 2017.

# 手法

以下に、通常のNMSとSoft-NMSの疑似コードを示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4010/374ab76d-b66b-e755-c36b-312126772751.png)

$\mathcal{B, S}$は、それぞれ検出候補とそのスコアの集合です。whileループの中では、得られた検出候補からもっともスコアの高い候補$\mathcal{M}$を取り出し、残りの候補とIoUを比較します。IoUがしきい値$N_t$以上であれば、$\mathcal{B}$から除外する、というのがNMSの処理の流れです。

NMSの処理の赤枠部分を緑枠のように変更するだけで、Soft-NMSは実現できます。Soft-NMSは、候補を$\mathcal{B}$から除外するか否かを決めるのではなく、候補$b_i$に関するスコア$s_i$を$f(\mathop{iou}(\mathcal{M}, b_i))$倍することでスコアを調整します。

$f(\mathop{iou})$は、2通り提案されていて、それぞれ以下のように表されます。

- Linear Weighting

```math
f(\mathop{iou}) = \begin{cases} 1, & \mathop{iou} < N_t \\ 1 - \mathop{iou}, & \mathop{iou} \geq N_t \end{cases}
```

- Gaussian Weighting

```math
f(\mathop{iou}) = e^{- \frac{\mathop{iou}}{\sigma}}
```

いずれも、IoUが大きければ大きいほど0に近づき、IoUが0ならば1になるという関数です。これによって、$\mathcal{M}$と重複が大きい検出候補のスコアは小さく、そうでない候補のスコアはそのままになります。

1つ目の式ではしきい値$N_t$が、2つ目の式では$\sigma$がハイパーパラメータとなります。

# 実験
MS-COCOでの精度測定の結果が、以下の表になります。GがGaussian Weighitng, LがLinear Weightingを表し、それぞれのハイパーパラメータは$\sigma=0.5, N_t=0.3$としています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4010/c6694f4f-f79c-d152-e0e0-2b380addcf32.png)

各手法でAP(Average Precision)が上昇していることが確認できます。また、Recallの方は大幅に上昇していることがわかります。これは、Soft-NMSが検出候補をすぐには除外せず、保持し続けていたことによる効果と言えます。

以下の例は、Gaussian Weightingを用いた時の、Precisionの上昇する（つまり誤検出が減る）例です。スコアが0.501という微妙な候補は、スコアが0.716の候補との重複が小さいために、通常のNMSでは除外されないまま残っています。しかし、Soft-NMSではある程度の重なりがあればスコアが抑制されるため、除外されることになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4010/e217a078-5c6e-4ef8-20e7-50c62e9bd320.png)

以下の例は、Gaussian Weightingを用いた時の、Recallが上昇する（検出漏れが減る）例です。2頭のシマウマはかなり領域に重なりがあるので、スコアは抑制されますが、最終的にはそれなりのスコアが残っているために、適切に検出できています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4010/54ea0966-3efd-d84d-24bd-28502367dec6.png)


# まとめ

ざっとですがSoft-NMSについて紹介しました。

細かいところですが、Soft-NMSは通常のNMSと計算量$\mathcal{O}(N^2)$は変わりません。また、Soft-NMSの方は、処理途中でスコアがしきい値を下回った候補を順次除外するという処理が必要になりますが、大した計算コストでは無いので、計算時間は通常のNMSとほぼ同じになります。