На основе исходного кода трех 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. Суть метода авторов состоит в вычислении
вейвлет-коэффициентов в области, найденной по алгоритму Виолы-Джонса.
Эти коэффициенты используются как признаки лица. Соответственно,
можно производить поиск по базе на основе этих признаков.
Для работы в режиме 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