Machine Learning Concept（二）：Non-Maximum Suppression（NMS）

Machine Learning Concept（二）：Non-Maximum Suppression（NMS）

2018/05/08

前言：

物件偵測時，難免會發生重複偵測的現象，大部分演算法都會附加一個 NMS 演算法來處理，但這個功能有沒有可能直接嵌入 CNN 呢？

Summary：

本文討論 object detection [1] 中，YOLO 演算法 [2] 與 Non-Maximum Suppression（NMS，刪除相似偵測）[3]-[8] 的關係。

-----

Fig. 1. Non-Maximum Suppression（NMS）[4].

-----

Outline

一、Non-Maximum Suppression（NMS）
二、YOLO and NMS

-----

一、Non-Maximum Suppression（NMS）

如圖1 所示，在 object detection 中，有時會出現重複偵測的狀況，譬如圖1左有三個相似的偵測結果，置信度分別是 0.9、0.8、0.7，這時你只能留下一個置信度最高的框框，把其餘的刪除，這就是 Non-Maximum Suppression（NMS）。

「非極大值抑制的流程如下：

a. 根據置信度得分進行排序。
b. 選擇置信度最高的比邊界框添加到最終輸出列表中，將其從邊界框列表中刪除。
c. 計算所有邊界框的面積。
d. 計算置信度最高的邊界框與其它候選框的 IoU。
e. 刪除IoU大於閾值的邊界框 重複上述過程，直至邊界框列表為空。」[4]

根據以上的演算法加以說明：

a. 必須是要同一類別。
b. 先找出一個置信度最高的框框，假定命名為 T (Target)。輸出列表數目為1。
c ~ e. 設定一個閾值，把跟 T 的 IoT [5] 高於閾值的框框都刪除掉。假定邊界框列表還有一些，那要再挑一個到輸出列表，這時輸出列表數目為2，然後再根據閾值刪除框框，依此原則反覆進行。

重點在於閾值的設定，以圖1為例，如果閾值設為 0.6，則會留下 3 個建議框，0.5 會留下 2 個，0.4 才能剩下一個 [4]。
 
-----

二、YOLO and NMS 

如圖2 所示，YOLO 的最後一步驟是 NMS。

以 YOLO 的演算法，出現圖1左的三個框框可能性應該很低（？），最多就是出現兩個框框，這時就可以套用 NMS 去掉一個。

TensorFlow 有提供 NMS 的函式：tf.image.non_max_suppression [6]-[8]，YOLO 使用 NMS 的時機則在 CNN 輸出之後，計算 loss 之前。

-----

Fig. 2. YOLO [2].

-----

Conclusion

以 NMS 使用的時機而言，YOLO 「勉強」稱的上是 ent-to-end 的設計，如果 NMS 能由神經網路直接完成，那就更酷了！

-----

References

[1] 關於影像辨識，所有你應該知道的深度學習模型 – Steven Shen – Medium
https://medium.com/@syshen/%E7%89%A9%E9%AB%94%E5%81%B5%E6%B8%AC-object-detection-740096ec4540 

[2]  Redmon, Joseph, et al. "You only look once: Unified, real-time object detection." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.
https://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Redmon_You_Only_Look_CVPR_2016_paper.pdf

[3] 非極大值抑制（Non-Maximum Suppression，NMS） - 掃文資訊
https://hk.saowen.com/a/ee16d85c2614981f2c5bc9f20ce37b806546b4b954fdbea87cba09774e02267f

[4] 非極大值抑制(Non-Maximum Suppression) - 掃文資訊
https://hk.saowen.com/a/be0b7a61e12326c4d8c6b509b2d2c4a9fce9331ea3bfd81271c1e63dd2e78f18

[5] Machine Learning Concept（一）：Mean Average Precision（mAP）
http://hemingwang.blogspot.tw/2018/04/machine-learning-conceptmean-average.html

[6] YOLO算法的原理与实现 - 云+社区 - 腾讯云
https://cloud.tencent.com/developer/article/1052865 

[7] tf.image.non_max_suppression  _  TensorFlow
https://www.tensorflow.org/api_docs/python/tf/image/non_max_suppression

[8] tensorflow_image_ops_impl.py at r1.8 · tensorflow_tensorflow · GitHub
https://cloud.tencent.com/developer/article/1052865