Подавление не-максимумов

Алгоритмы детектирования генерируют избыточное количество выделений объектов интересующих классов, как показано на рисунке справа-вверху [1]:

Эти выделения соотносятся классу (классификатором) и немного уточняется их местоположение (регрессором), как показано справа внизу. Чтобы отобрать минимально достаточный набор всех выделений используется алгоритм подавления не-максимумов (non-maximum supression, NMS), фильтрующий лишние детекции для каждого класса в отдельности.

Алгоритм принимает на вход набор детекций (выделяющих рамок) $B$ и соответствующих рейтингов (вероятностей интересующего класса) $S$, а на выходе выдаёт самые явные детекции без повторений $D$ с соответствующими рейтингами $S$. Он работает следующим образом:

• ВХОД:

  • $B=\{b_1,...b_N\}$ - первоначальные детекции

  • $S=\{s_1,...s_N\}$ - их рейтинги

  • $\alpha\in (0,1]$ - гиперпараметр NMS

• АЛГОРИТМ:

  • $D=\{\}$ - инициализируем выходные детекции

  • пока $B\ne \{\}$:

    • $m:=\arg\max S$

    • $D:=D\cup \{b_m\}$

    • $B:=B-\{b_m\}$

    • для $b_i \in B$:

      • если $IoU(b_m,b_i)\ge \alpha$, то

        • $B:=B-\{b_i\}$

        • $S:=S-\{s_i\}$

  • вернуть $D,S$

Мягкий вариант алгоритма

Традиционный NMS алгоритм жёстко отсеивает выделения, имеющие IoU$\ge\alpha$ с выделением, имеющим более высокий рейтинг. Это может негативно сказаться на количестве обнаруженных объектов (recall), которые сильно пересекаются, как на рисунке ниже:

Для того, чтобы так не происходило, в работе [1] предлагается оставлять все детекции, но для детекций, имеющих сильное пересечение с высокорейтинговыми детекциями, дополнительно снижать рейтинг. Итоговыми детекциями будут те, у которых рейтинг выше некоторого порога $\beta>0$, устанавливая который достаточно низким, можно извлечь большее число объектов (ценой более частых дублирующихся выделений одного объекта). Формально алгоритм называется мягким подавлением не-максимумов (soft-NMS) выглядит следующим образом:

• ВХОД:

  • $B=\{b_1,...b_N\}$ - первоначальные детекции

  • $S=\{s_1,...s_N\}$ - их рейтинги

  • $\alpha\in (0,1]$ - гиперпараметр NMS

• АЛГОРИТМ:

  • $D=\{\}$ - инициализируем выходные детекции

  • пока $B\ne \{\}$:

    • $m:=\arg\max S$

    • $D:=D\cup \{b_m\}$

    • $B:=B-\{b_m\}$

    • для $b_i \in B$:

      • $S:=S\cdot f(IoU(b_m,b_i))$

  • вернуть $D,S$

Как видим, в качестве $b_m$ в этот раз перебираются все детекции из $B$, в результате чего $D=B$, т.е. выходные детекции совпадают со входными, однако рейтинг детекций, имеющих сильное пересечение с высокорейтинговыми, оказывается сниженным за счёт домножения исходного рейтинга на $f(IoU(b_m,b_i))$ для убывающей функции, принимающей значения на отрезке $[0,1]$. Предлагаются два варианта этой функции:

• линейное перевзвешивание:

$$f(IoU(b_m,b_i))= \begin{cases} 1, & IoU(b_m,b_i)<\alpha, \\ 1-IoU(b_m,b_i), & IoU(b_m,b_i)\ge\alpha \\ \end{cases}$$

• Гауссово перевзвешивание:

  $$f(IoU(b_m,b_i))=e^{-\frac{IoU(b_m,b_i)}{\sigma}},\quad \sigma>0 \text{ - гиперпараметр}$$

Линейное перевзвешивание приводит к разрывномому масштабированию, в отличие от Гауссова. В экспериментах [1] мягкое подавление не-максимумов оказалось лучше, чем жёсткое. При этом иногда доминировало линейное, а иногда Гауссово.

Литература

1. Bodla N. et al. Soft-NMS--improving object detection with one line of code //Proceedings of the IEEE international conference on computer vision. – 2017. – С. 5561-5569.