Технологии компьютерного зрения позволяют в сегодняшних реалиях сделать жизнь и бизнес проще, дешевле, безопаснее. По оценкам разных экспертов этот рынок будет двигаться в ближайшие годы только в сторону роста, что и позволяет развиваться соответствующим технологиям как в сторону производительности, так и качества. Одним из наиболее востребованных разделов является Object Detection (обнаружение объектов) – определение объекта на изображении или в видео потоке.

Времена, когда обнаружение объектов решалось исключительно путем классического машинного обучения (каскады, SVM...) уже прошли – сейчас в этой сфере царят подходы, основанные на Deep Learning. В 2014 году был предложен подход, существенно повлиявший на последующие исследования и разработки в этой области – R-CNN модель. Последующие его улучшения (в виде Fast R-CNN и Faster R-CNN) сделали его одним из самых точных, что и стало причиной его использования по сей день.

Помимо R-CNN есть еще много подходов реализующих поиск объектов: семейство Yolo, SSD, RetinaNet, CenterNet… Кто-то из них предлагает альтернативный подход, а кто-то развивает текущий в сторону увеличения показателя производительности. Обсуждение почти каждого из них можно вынести в отдельную статью, по причине обилия фишек и ухищрений :)

К изучению предлагаю набор статей с разбором двухступенчатых Object Detection моделей. Умение разбираться в их устройстве приносит понимание базовых идей, применяемых и в других реализациях. В этом посте рассмотрим самую базовую и, соответственно, первую из них – R-CNN.

Терминология


Ограничивающая рамка (bounding box) – координаты, ограничивающие определенную область изображения, – чаще всего в форме прямоугольника. Может быть представлена 4 координатами в двух форматах: центрированный ($c_{x},c_{y},w,h$) и обычный ($x_{min},y_{min},x_{max},y_{max}$).

Гипотеза (Proposal), P – определенный регион изображения (заданный с помощью ограничивающей рамки), в котором предположительно находится объект.

End-to-end обучение – обучение, при котором на вход сети поступают сырые изображения, а на выходе – готовые ответы.

IoU (Intersection-over-Union) – метрика степени пересечения между двумя ограничивающими рамками.

R-CNN


Одним из первых подходов, применимых для определения нахождения объекта на картинке, является R-CNN (Region Convolution Neural Network). Его архитектура состоит из нескольких последовательно выполняемых шагов и проиллюстрирована на изображении 1:

  1. Определение набора гипотез.
  2. Извлечение из предполагаемых регионов признаков с помощью сверточной нейронной сети и их кодирование в вектор.
  3. Классификация объекта внутри гипотезы на основе вектора из шага 2.
  4. Улучшение (корректировка) координат гипотезы.
  5. Все повторяется, начиная с шага 2, пока не будут обработаны все гипотезы с шага 1.

Рассмотрим каждый шаг подробнее.



Поиск гипотез


Имея определенное изображение на входе первым делом, оно разбивается на маленькие гипотезы разных размеров. Авторы этой статьи используют Selective Search – верхнеуровнево, он позволяет составить набор гипотез (класс объекта пока не имеет значения), на основе сегментации определить границы объектов по интенсивности пикселей, перепаду цветов, контраста и текстур. При этом авторы отмечают, что можно использовать любой аналогичный алгоритм. Таким образом выделяется примерно 2000 разных регионов, которые частично друг друга перекрывают. Для более точной последующей обработки каждая гипотеза дополнительно расширяется на 16 пикселей во всех 4 направлениях – как бы добавляя контекст.

Итог:

  • Вход: исходное изображение.
  • Выход: набор гипотез разного размера и соотношения сторон.

Кодирование изображения


Каждая гипотеза из предыдущего шага независимо и по отдельности друг от друга поступает на вход сверточной нейронной сети. В качестве нее используется архитектура AlexNet без последнего softmax-слоя. Главной задачей сети является кодирование поступаемого изображения в векторное представление, которое извлекается из последнего полносвязного FC7 слоя. Так на выходе получается 4096-размерное векторное представление.

Можно заметить, что вход AlexNet имеет размерность 3?227?227, а размер гипотезы может быть почти любого соотношения сторон и размера. Эта проблема обходится простым сжатием или растягиванием входа до нужного размера.

Итог:

  • Вход: каждая из предложенных на предыдущем шаге гипотеза.
  • Выход: векторное представление для каждой гипотезы.

Классификация


После получения характеризующего гипотезу вектора становится возможна ее дальнейшая обработка. Для определения, какой именно объект находится в предполагаемом регионе, авторы используют классический метод классификации разделяющими плоскостями на базе SVM (Support Vector Machine – машина опорных векторов, можно смоделировать с помощью Hinge loss). Причем должно быть $N_{c}+1$ отдельных (здесь, $N_{c}$ обозначает количество определяемых классов объектов, а единица добавляется для отдельного определения фона) моделей, обученных по принципу OvR (One vs. Rest – один против всех, один из методов мультиклассовой классификации). По сути, решается задача бинарной классификации – есть ли конкретный класс объекта внутри предполагаемого региона или нет. Таким образом, выходом является $N_{c}+1$-размерный вектор, отображающий уверенность в конкретном классе содержащегося в гипотезе объекта (фон исторически обозначается нулевым классом, $C_{i}=0$).

Итог:

  • Вход: вектор каждой из предложенных гипотез из предпоследнего слоя сети (в случае AlexNet это FC7).
  • Выход: после последовательного запуска каждой гипотезы, получаем матрицу размерности $2000?N_{c}$, отображающую класс объекта для каждой гипотезы.

Уточнение координат гипотез


Гипотезы, полученные на шаге 1 не всегда содержат правильные координаты (например, объект может быть неудачно «обрезан»), поэтому имеет смысл их дополнительно исправлять. По заверению авторов, это приносит дополнительные 3-4 % к метрикам. Так, гипотезы, содержащие какой-либо объект (наличие объекта определяется на шаге классификации), дополнительно обрабатываются линейной регрессией. То есть гипотезы с классом «фон» не нуждаются в дополнительной обработке регионов, ведь на самом деле там нет объекта…

Каждый объект, специфично для своего класса, имеет определенные размеры и соотношения сторон, поэтому, что логично, рекомендуется применять собственный регрессор на каждый класс.

В отличие от предыдущего шага, авторы для наилучшей работы используют на входе не вектор из слоя FC7, а карты признаков, извлеченные из последнего MaxPooling слоя (в AlexNet это $MaxPool_{5}$, размерность 256?6?6). Объяснение тут следующее – вектор сохраняет информацию о наличии объекта с какими-то характеристическими подробностями, а карта признаков наилучшим образом сохраняет информацию о местоположении объектов.

Итог:

  • Вход: карта признаков из последнего MaxPooling слоя для каждой гипотезы, которая содержит любой объект, кроме фона.
  • Выход: поправки к координатам ограничивающей рамки гипотезы.

Вспомогательные трюки


Прежде чем переходить к подробностям обучения модели, рассмотрим два необходимых трюка, которые понадобятся нам позднее.

Обозначение позитивных и негативных гипотез


При обучении с учителем всегда необходим определенный баланс между классами. Обратное может привести к плохой точности классификации. Например, если в выборке с двумя классами первый встречается лишь в нескольких процентах случаев, то сети сложно обучиться его определять – ведь это можно интерпретировать как выброс. В случае задач Object Detection как раз присутствует такая проблема — на картинке с единственным объектом лишь несколько гипотез (из ~2000) содержат этот самый объект ($C_{i}>0$), а все остальные являются фоном ($C_{i}=0$).

Примем необходимое обозначение: гипотезы, содержащие объекты, будем называть позитивными (positive), а без объектов (содержащие только фон, или незначительную часть объекта) – негативными (negative).

Для того, чтобы в последующем определить пересечения между двумя регионами изображения будет использоваться метрика Intersection over Union. Она считается довольно просто: площадь пересечения двух областей делится на общую площадь регионов. На изображении ниже можно увидеть иллюстрации примеров подсчета метрики.



С позитивными гипотезами все понятно – если класс определен неверно, нужно штрафовать. Но как быть с негативными? Их намного больше, чем позитивных… Для начала отметим, что не все негативные гипотезы одинаково сложно распознавать. Например, случаи, содержащие только фон (easy negative) гораздо проще классифицировать, чем содержащие другой объект или малую часть нужного (hard negative).

На практике easy negative и hard negative определяются по пересечению ограничивающей рамки (как раз используется Intersection over Union) с правильным положением объекта на изображении. Например, если пересечения нет, или оно крайне мало – это easy negative ($C_{i}=0$), если большое – это hard negative или positive.

Подход Hard Negative Mining предлагает использовать для обучения только hard negative, поскольку, научившись распознавать их, мы автоматический добиваемся наилучшей работы с easy negative гипотезами. Но такая идеология будет применяться только в последующих реализациях (начиная с Fast R-CNN).

Non-maximum suppression


Довольно часто получается так, что модель выделяет несколько гипотез с большой уверенностью указывающие на один и тот же объект. С помощью Non-maximum suppression (NMS) можно обработать такие случаи и оставить только одну, наилучшую, ограничивающую рамку. Но при этом не стоит забывать о случае, когда на изображении может быть два разных объекта одного класса. На изображении 3 проиллюстрирован эффект работы до (слева) и после (справа) работы алгоритма.



Рассмотрим алгоритм работы на одном классе (в реальности он применяется на каждый класс по отдельности):

  1. На вход функция принимает набор гипотез для одного класса и порог, задающий величину максимального пересечения между гипотезами.
  2. Гипотезы сортируются по их «уверенности».
  3. В цикле выбирается первая гипотеза (имеет наибольшую величину уверенности) и добавляется в результирующий набор.
  4. В цикле выбирается следующая, вторая гипотеза (среди оставшихся после шага 3).
  5. Если между выбранными гипотезами пересечение больше, чем выбранный порог (пересечение считается на основе Intersection of Union), то вторая гипотеза отбрасывается и далее не присутствует в результирующем наборе.
  6. Все повторяется, начиная с шага 3 до момента полного перебора гипотез.

Псевдокод выглядит так:

function nms(hypotheses, threshold):
    sorted = sort(hypotheses.values, key=hypotheses.scores)
    result = []
    for first in sorted:
        result.join(first)
        without_first = sorted / first
        for second in without_first:
            if IoU(first, second) > threshold:
                 sorted.remove(second)
    return result


Обучение


Блок выделения гипотез не подлежит обучению.

Поскольку сеть разделена на несколько отдельных друг от друга блоков, то она не может обучаться по принципу end-to-end. Так, обучение представляет собой последовательный процесс.

Обучение векторного представления


За основу берётся предобученная на ImageNet сеть – такие сети уже умеют хорошо извлекать важные признаки из поступающих изображений, – остается обучить их работать с нужными классами. Для этого необходимо изменить размерность выходного слоя на $N_{c}$ и обучить уже модифицированный вариант. Первые слои можно заблокировать, поскольку они извлекают первичные (почти одинаковые для всех изображений) признаки, а последующие во время обучения адаптируются под признаки нужных классов. Так сходимость будет достигаться гораздо быстрее. Но если обучение все же идет плохо, можно разблокировать и первичные слои. Поскольку необходимо именно донастроить уже имеющиеся веса. Использовать большой темп обучения (learning rate) не рекомендуется, – можно очень быстро затереть уже имеющиеся веса.

Когда сеть обучилась хорошо классифицировать объекты, последний слой с SoftMax активацией отбрасывается и выходом становится слой FC7, выход которого в свою очередь можно интерпретировать как векторное представление гипотезы.

Позитивными на этом шаге считаются гипотезы, которые пересекаются с правильным положением объекта (по IoU) более чем на 0.5. Негативными же считаются все остальные. Для обновления весов используется мини-батч размерности 128, состоящий из 32 позитивных и 96 негативных гипотез.

Обучение классификаторов


Напомню, для классификации каждой гипотезы используется $N_{c}+1$ SVM моделей, которые получают на вход векторное представление гипотезы, и на основе принципа один против остальных (One-vs-Rest) определяют класс объекта. Обучаются они как обычные SVM модели за одним исключением – на этом шаге определение позитивов и негативов немного отличается. Здесь за негативы берутся те гипотезы, пересечение которых с правильным положением менее 0.3.

Обучение регрессоров


Обозначим:

  • $G=(g_{x},g_{y},g_{w},g_{h})$ – правильные координаты объекта;
  • $\hat{G}=(\hat{g_{x}},\hat{g_{y}},\hat{g_{w}},\hat{g_{h}})$ – исправленное положение координат гипотез (должно совпадать с $G$);
  • $T=(t_{x},t_{y},t_{w},t_{y})$ – правильные поправки к координатам;
  • $P=(p_{x},p_{y},p_{w},p_{h})$ – координаты гипотезы;

Так регрессоры (по одному, на каждый класс) представляют собой четыре функции:

  • $d_{x}(P)$, $d_{y}(P)$ – определяют поправки к координатам центра ($x,y$). Для достижения эффекта независимости от исходного размера поправка должна быть нормализованной.
  • $d_{w}(P)$ и $d_{h}(P)$ – определяют поправки к ширине и высоте в логарифмическом пространстве (логарифмическое пространство используется для численной устойчивости, а деление – для определения направления поправки).

Обозначим как $\varphi_{5}(P)$ карту признаков, полученную из $MaxPool_{5}$ слоя сети (напоминаю, он имеет размерность 256?6?6, потом просто вытягивается), при подаче в сеть гипотезы, ограниченной координатами $P$. Будем искать преобразование $P$ в $G$ как:

\begin{align}
\hat{g_x} &= p_w d_x(P) + p_x \\
\hat{g_y} &= p_h d_y(P) + p_y \\
\hat{g_w} &= p_w e^{d_w(P)} \\
\hat{g_h} &= p_h e^{d_h(P)}
\end{align}
При этом $d_{*}(P)={w_{*}}^{T}\varphi_{5}(P)$ (здесь $*?(x,y,w,h)$) является линейной функцией, а вектор $w_{*}$ ищется с помощью задачи оптимизации (ridge регрессия):

$w_{*}=argmax_{\hat{w_{*}}}\sum_{i}^{N}(T_{i_{*}}-d_{*}(P))^{2}+\lambda \left \| \hat{w_{x}} \right \|^{2}$


Для определения поправок к координатам соберем пары между правильным положением гипотез $G$ и их текущем состоянием $P$, и определим значения $T_{*}$ как:

\begin{align}

T_x &= \frac{g_x-p_x}{p_w} \\

T_y &= \frac{g_y-p_y}{p_h} \\

T_w &= \log{\frac{g_w}{p_w}} \\

T_h &= \log{\frac{g_h}{p_h}}\qquad

\end{align}
Обозначения в формулах внутри этой статьи с целью наилучшего понимания могут расходиться с обозначениями оригинальной статьи.

Поскольку по итогу работы сети на выходе имеется ~2000 гипотез, они объединяются с помощью Non-maximum suppression. Авторы статьи также указывают, что если вместо SVM использовать SoftMax слой (который был откинут на втором шаге), то точность падает на ~4-4.5 % (датасет VOC 2007), но при этом отмечают, что лучшая «подгонка» весов вероятно поможет избавиться от такой проблемы.

В заключение выделим основные недостатки такого подхода:


  1. Гипотезы, предложенные на шаге 1, могут частично дублировать друг друга – разные гипотезы могут состоять из одинаковых частей, а каждая такая гипотеза отдельно обрабатывалась нейронной сетью. Так получается, что большая часть запусков сети более или менее дублирует друг друга без надобности.
  2. Нельзя использовать для real-time работы, поскольку на проход 1 изображения (кадра) тратится ~53 секунды (NVIDIA Titan Black GPU).
  3. Алгоритм выделения гипотез никак не обучается, а поэтому дальнейшее улучшение качества почти невозможно (никто не отменял плохие гипотезы).

На этом разбор самой первой R-CNN модели заканчивается. Более усовершенствованные реализации (в виде Fast R-CNN и Faster R-CNN) будут разобраны в следующей статье, которую выложу в ближайшее время. Следите за обновлениями.

Список литературы


1. R. Girshick, J. Donahue, T. Darrell, and J. Malik. «Rich feature hierarchies for accurate object detection and semantic segmentation.» In CVPR, 2014. arXiv:1311.2524

2. R. Girshick, J. Donahue, T. Darrell, and J. Malik. «Region-based convolutional networks for accurate object detection and segmentation.» TPAMI, 2015

Автор: Сергей Михайлин, специалист машинного обучения «Инфосистемы Джет»