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

 Автор текста и программы: Александр Лубягин
 Опубликовано на условиях лицензии "CC-SA 3.0"
 Дата публикации: 06 декабря 2011 года

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

Материалы исследования включают в себя отчет на 12 страниц А4, программу
на Си++ (порядка 1 тыс. строк кода), а также – изображения, иллюстрирующие
качество работы алгоритма. Для обнаружения лиц на видео-потоке алгоритм
подходит мало, удовлетворительное качество достигается при съемке лица
"крупным планом" (например, если человек сидит перед веб-камерой).

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

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

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

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

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

В Интернете есть много статей, поверхностно описывающих метод Виолы-Джонса
по части распознавания. Часть обучения (так называемый метод AdaBoost) описан
три дня назад в статье на "Хабр" неизвестным автором:
https://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.cpp - AGPLv3+:
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as published
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program. If not, see http://www.gnu.org/licenses/

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

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

Дополнение от 25.09.2012:
код выложен на github.com/lubyagin

Дополнение от 28.03.2012:
Во время написания работы я решил поискать диссертации по теме распознавания лиц в базе диссертаций РГБ.
Одну такую диссертацию нашел: "Алгоритмы обнаружения лица человека для решения прикладных задач анализа
и обработки изображений" (Кудряшов, Павел Павлович), Волгоград, 2007.

В упомянутой диссертации действительно содержательная часть - это про
удаление красных глаз. Также, по подобному алгоритму можно удалять
"белые глаза", "желтые глаза" и проч. (на фотографиях животных)

Библиография
[64] Lienhart R., Kuranov A., Pisarevsky V. An extended set of Haar-like features for rapid
object detection, IEEE ICIP, p.900-903, Rochester, NY, Sep.2002.
[131] Yang M.H., Kriegman D., Ahuja N. Detecting faces in images: A survey. PAMI, 24(1), p.34-58, Jan.2002.
[143] Вежневец А.П. Методы классификации с обучением по прецедентам в задаче распознавания
объектов на изображениях, 2006. (см. на graphicon.ru)

Дополнение от 06.02.2013:
Литература
Вчера обнаружил в интернете статью с конференции
«Применение гибридных высокопроизводительных вычислительных систем
для решения научных и инженерных задач» (проводилась в Нижегородском
государственном университете, 2010). Статья называется "Реализация
алгоритма Viola-Jones для архитектуры NVIDIA CUDA", авторы - И.И.Зиновьев,
Т.Е.Овчинникова, П.Ю.Шамин. В этой статье расписаны оценки производительности
для двух реализаций алгоритма: на CPU Intel Core I7 и на NVIDIA CUDA.
Реализация на процессоре работает с той же скоростью, что и у меня.
А реализация на GPU - даёт ускорение в 3-5 раз. Ссылка: PDF

См. также слайды от Антона Обухова из корпорации NVIDIA, с конференции GraphiCon'2009.
Там даны апостерироные оценки производительности основного цикла алгоритма.

Дополнение от 07.02.2013:
В 2012 году появилась статья Спицына В.Г., Буй Тхи Тху Чанга и Фан Нгок Хоанга,
"Распознавание лиц на основе применения метода Виолы-Джонса, вейвлет-
преобразования и метода главных компонент" (опубликована в журнале "Известия
Томского политехнического университета, 2012, том 320, выпуск 5).
Код УДК: 004.93'1;004.032. Суть метода авторов состоит в вычислении
вейвлет-коэффициентов в области, найденной по алгоритму Виолы-Джонса.
Эти коэффициенты используются как признаки лица. Соответственно,
можно производить поиск по базе на основе этих признаков.
Keywords:
вейвлеты Хаара, признаки Хаара, каскады Хаара, метод Виолы-Джонса, OpenCV
--