Перейти к основному содержимому

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

Базовый алгоритм NMS

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

Эти выделения соотносятся тому или иному классу классификатором, назначающим рейтинг (score) принадлежности каждого выделения классу. Расположение самого выделения немного уточняется регрессором, как показано справа внизу.

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

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

ВХОД:

  • B={b1,...bN}B=\{\mathbf{b}_1,...\mathbf{b}_N\} - первоначальные детекции

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

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

АЛГОРИТМ:

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

  • S={}S'=\{\} - инициализируем выходные рейтинги

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

    • m:=argmaxSm:=\arg\max S

    • B:=B+{bm}B':=B'+ \{\mathbf{b}_m\}

    • B:=B{bm}B:=B-\{\mathbf{b}_m\}

    • для biB\mathbf{b}_i \in B:

      • если IoU(bm,bi)α\text{IoU}(\mathbf{b}_m,\mathbf{b}_i)\ge \alpha, то

        • B:=B{bi}B:=B-\{\mathbf{b}_i\}

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

  • вернуть B,SB',S

где прибавление/вычитание из набора элемента означает добавление/исключение этого элемента из набора.

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

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

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

Этот алгоритм называется мягким подавлением не-максимумов (soft-NMS) и работает следующим образом:

ВХОД:

  • B={b1,...bN}B=\{\mathbf{b}_1,...\mathbf{b}_N\} - первоначальные детекции

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

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

АЛГОРИТМ:

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

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

    • m:=argmaxSm:=\arg\max S

    • B:=B+{bm}B':=B'+\{\mathbf{b}_m\}

    • B:=B{bm}B:=B-\{\mathbf{b}_m\}

    • для biBb_i \in B:

      • si:=sif(IoU(bm,bi))s_i:=s_i\cdot f(\text{IoU}(\mathbf{b}_m,\mathbf{b}_i))
  • вернуть D,SD,S

Как видим, в качестве bm\mathbf{b}_m в этот раз перебираются все детекции из BB, в результате чего B=BB'=B, т.е. выходные детекции совпадают со всеми входными, однако рейтинг детекций, имеющих сильное пересечение с другими высокорейтинговыми выделениями, оказывается сниженным за счёт домножения исходного рейтинга на f(IoU(bm,bi))f(\text{IoU}(\mathbf{b}_m,\mathbf{b}_i)) для некоторой убывающей функции f()f(\cdot), принимающей значения на отрезке [0,1][0,1]. Предлагаются два варианта этой функции:

  • линейное перевзвешивание:
f(IoU(bm,bi))={1,IoU(bm,bi)<α,1IoU(bm,bi),IoU(bm,bi)αf(\text{IoU}(b_m,b_i))= \begin{cases} 1, & \text{IoU}(\mathbf{b}_m,\mathbf{b}_i)<\alpha, \\ 1-\text{IoU}(\mathbf{b}_m,\mathbf{b}_i), & \text{IoU}(\mathbf{b}_m,\mathbf{b}_i)\ge\alpha \\ \end{cases}
  • Гауссово перевзвешивание:

    f(IoU(bm,bi))=eIoU(bm,bi)σ,σ>0 - гиперпараметрf(\text{IoU}(\mathbf{b}_m,\mathbf{b}_i))=e^{-\frac{\text{IoU}(\mathbf{b}_m,\mathbf{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.