LUBYAGIN

Обнаружение лиц по методу Виолы-Джонса

На основе исходного кода трех OpenSource-проектов, восстановлен алгоритм распознавания лиц (метод Виолы-Джонса). Алгоритм использует стандартный каскад Хаара из OpenCV и реализован на языке Си++. Скорость работы программной реализации, на изображениях 512x512 пикс – порядка 3 кадров/сек. Предназначен для обнаружения лиц "в фас" на любых фотографиях.

Реализация метода Виолы-Джонса в оригинальных работах авторов не описана, поэтому данная работа представляет значительную ценность для тех, кому надо разобраться в методе Виолы-Джонса, либо – реализовать обнаружение лиц в своем проекте/программе.


Автор текста и программы: Александр Лубягин.

Документация опубликована на условиях Creative Commons Attribution-ShareAlike 4.0.
Дата публикации кода и документации: 6 декабря 2011 года.

GitHub repo: https://github.com/lubyagin/sqface

1. Что мы делаем

Этим летом один английский коллега попросил меня написать программную библиотеку для обнаружения лиц на фотографиях. Ему это нужно было для Интернет-магазина одежды. Я написал эту программу на основе OpenCV.

Спустя месяц, эта программа пригодилась. Один питерский предприниматель заказал мне исследовать код OpenCV, и по результатам исследования сделать отчет. Исследования я решил продолжить, и в декабре 2011 года опубликовал данную статью об этом интересном методе обнаружения лиц.

Метод называется: "метод Виолы-Джонса" (по фамилиям двух его авторов). Предназначен для обнаружения объектов на изображениях в реальном времени (например, на кадрах видео-потока). Метод отвечает на вопросы: "есть ли на изображении лица людей?", и "где они, предположительно, находятся?".

Метод реализован в проектах: HxMarilena, OpenClooVision, "MATLAB: Viola-Jones Object Detection", OpenCV, и других.

В Интернете есть много статей, поверхностно описывающих метод Виолы-Джонса по части распознавания. Часть обучения (так называемый метод AdaBoost) описан три дня назад в статье на "Хабр" неизвестным автором: http://habrahabr.ru/blogs/algorithm/133826/. Таким образом, если учесть ещё и мою статью, сейчас в Интернете метод Виолы-Джонса описан более-менее полностью (на русском языке).

2. Ещё раз о скорости и "ложных срабатываниях"

Моя программа обрабатывала кадр 512x512 пикселей за 0.19 секунды. В то время, как OpenCV делала то же самое за 0.03 секунды. Одна из целей, которые можно поставить на ближайшее будущее (декабрь 2011 - весна 2012 года), это ускорение программы, устранение множественности обнаружения (вместе с уменьшением числа "ложных срабатываний"), выпуск кода как в виде отдельной программы, так и в виде программной библиотеки. Вот как программа обнаруживает лица на стандартных, типичных фотографиях:

Для работы в режиме real-time моей программе надо приблизиться к уровню OpenCV. Реализации других исследователей были такими:
Viola, Jones, 2001: 384x288 пикс - 15 кадров/сек на Intel Pentium III, 700 MHz
Viola, Jones, 2001: 2 кадра/сек на Strong Arm, 200 MIPS
R.Lienhart, J.Maydt: 320x240 пикс - 15 кадров/сек на Intel P4, 2 GHz

"Ложные срабатывания", которые вы видели на видео (по приведенным выше ссылкам), кореллируют в рамках метода Виолы-Джонса с долей правильных ответов:

То есть, повышая долю правильных ответов, мы вносим лишние "ложные срабатывания".

3. Общая схема метода Виолы-Джонса

Алгоритм распознавания по методу Виолы-Джонса основан на "суммировании" пикселов (с определенными весовыми коэффициентами) под скользящим [по растру] окном. Распознавание в этом методе осуществляется по "прецедентам". В помощью "обучающей выборки" строится набор "сильных классификаторов", каждый из которых для квадратного окна говорит: "предположительно, в окне - лицо", или - "определенно, не лицо". Таким образом, для того, чтобы алгоритм признал картинку в окне за лицо, необходимо, чтобы все "сильные классификаторы" (stages) ответили: "да, лицо предположительно есть". Если хотя бы один из них отверг окно (сказал, что "лица определенно нет"), то алгоритм сразу же отвергает данное окно, другие "сильные классификаторы" не использует, и переходит к следующему окну.

4. Немного математики

В методе Виолы-Джонса используются функции, основанные на вейвлетах Хаара. По-английски, эти функции называются "Haar wavelet-like features". Вейвлеты Хаара - это одиночные "волны" прямоугольного вида (один интервал "высокого" уровня, и один - "низкого"). На плоскости - это два прилегающих квадрата. Комбинации таких форм - вейвлетами Хаара не являются. Эти Haar-like features показаны на рисунке:

Именно свёртка двумерного функционала интенсивности пикселов с такими функциями, с определенными весами, и представляет собой упомянутое выше "суммирование".

Все Haar-like features (или просто, features) для одного каскада изображены на большой картинке:

Как работает "сильный классификатор".
Для выбранной позиции скользящего окна, перебираются все "сильные классификаторы" (stages) / "хааро-подобные функции" (features). Для каждой feature считается сумма интенсивностей пикселов с определенным весовым коэффициентом по "белой" области feature (см. рисунки выше), и вычитается сумма по "тёмной" области, с другим весовым коэффициентом. Полученная сумма умножается на величину inv (см. ниже формулы в алгоритме), и сравнивается с порогом "feature threshold", умноженным на величину stddev. Если первое - меньше второго, то к сумме по stage ("сильному классификатору") добавляется величина left_val данного feature, иначе - добавляется величина right_val.

Для ускорения "суммирования" используется "интегральная матрица" (Summed area table, см. на Википедии). За счёт неё у меня программа ускорилась в 35 раз.

Чтобы представлять, где и как брать значения left_val и т.п., приведу часть первого stage из стандартного каскада:

<opencv_storage>
<haarcascade_frontalface_alt type_id="opencv-haar-classifier">
  <size>20 20</size>	# вначале задается размер «окна» в пикселах
  <stages>
    <_>			# затем описываются этапы каскада: от 0 до 21
      <!-- stage 0 -->
      <trees>
        <_>		# на каждом этапе несколько «деревьев»
          <!-- tree 0 -->
          <_>		# в данном случае, каждое дерево — это один «корень»
            <!-- root node -->
            <feature>	# «корню» принадлежит один признак (feature)
              <rects>		# в нашем случае — несколько прямоугольников (x,y,w,h) с заданными весами (w,)
                <_>3 7 14 4 -1.</_>
                <_>3 9 14 2 2.</_></rects>
              <tilted>0</tilted></feature>	# поворот признака (в нашем случае, alt — не используется)
	# см. также correction_ratio на github.com
            <threshold>4.0141958743333817e-003</threshold>		# порог, с которым сравнивается разн. Ч-Б
            <left_val>0.0337941907346249</left_val>
            <right_val>0.8378106951713562</right_val></_></_>
        <_>
          <!-- tree 1 -->
          <_>
            <!-- root node -->
            <feature>
              <rects>
                <_>1 2 18 4 -1.</_>
                <_>7 2 6 4 3.</_></rects>
              <tilted>0</tilted></feature>
            <threshold>0.0151513395830989</threshold>
            <left_val>0.1514132022857666</left_val>
            <right_val>0.7488812208175659</right_val></_></_>
        ….
      # после всех признаков (деревьев) ...
      <stage_threshold>6.9566087722778320</stage_threshold>
      <parent>0</parent>
      <next>-1</next></_>

Структура данных XML-каскада изображена также на следующей схеме:

Значения left_val и right_val для данного каскада - неотрицательны:

5. Алгоритм

def Sum(x,y,w,h):
  for x,y in [w,h]:
    S += pixel_intensivity
  return S/256.0

def SumSq(x,y,w,h): for x,y in [w,h]: S += pixel_intensivity^2 return S/(256.0*256.0)

factor = 1.2 dscale = 1.0 цикл window_w = window_w_base * dscale window_h = window_h_base * dscale x_step = max(1, min(4, window_w/8)) # определено эмпирически y_step = max(1, min(4, window_h/8)) # от 1 до 4 пикс inv = 1/float(window_w*window_h) цикл по y1 = 0 ... h1-1-window_h с шагом y_step цикл по x1 = 0 ... w1-1-window_w с шагом x_step mean = Sum(x1,y1,window_w, window_h)*inv var = SumSq(x1,y1,window_w, window_h)*inv - mean*mean если var >= 0, то stddev = sqrt(var) иначе stddev = 1.0 цикл по stages (сильным классификаторам) sum_stage = 0.0 цикл по features (функциям Хаара) sum_feature = 0.0 цикл по rects (прямоугольникам) sum_feature += Sum(x1+rect.x*dscale, y1+rect.y*dscale, rect.w*dscale+2, rect.h*dscale+2)*rect.weight sum_feature *= inv если sum_feature < feature_threshold*stddev, то sum_stage += feature.left_val иначе sum_stage += feature.right_val если sum_stage < stage_threshold, то f_failed = 1; break; если (!failed) нарисовать [x1,y1,x2,y2] dscale *= factor

6. Программа

Архив с полным исходным кодом программы и каскадом: sqface-first.tar.gz

За консультациями по реализации алгоритма, обращайтесь: lubyagin@yandex.ru

Лицензия на исходный код sqface.cpp - AGPLv3+

Также, вы можете изучить алгоритм распознавания по другим реализациям:
- Проект HxMarilena - HxMarilena: ObjectDetector.hx
- Скрипт на языке MATLAB - MATLAB: Viola-Jones Object Detection
- Проект OpenClooVision (Viola-Jones) - http://opencloovision.codeplex.com/
- Проект корпорации Intel, OpenCV - OpenCVWiki