Для работы в режиме 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/
Также, вы можете изучить алгоритм распознавания по другим реализациям:
- Проект HxMarilena - HxMarilena: ObjectDetector.hx
- Скрипт на языке MATLAB - MATLAB: Viola-Jones Object Detection
- Проект OpenClooVision (Viola-Jones) - http://opencloovision.codeplex.com/
- Проект корпорации Intel, OpenCV - OpenCVWiki
----
Если кому-то нужна консультация по этому алгоритму, обращайтесь:
E-mail: lubyagin@yandex.ru
Jabber: lubyagin@jabber.ru
ICQ: 386-551-505
Дата публикации: 06 декабря 2011 года.
Автор: Александр Лубягин aka pacify, http://pacify.ru/
Дополнение от 06.12.2011: Спустя несколько часов после публикации анонса на Linux.Org.Ru, исходный код проекта был выложен пользователем tommy2001 на github.com с целью его дальнейшего развития: "sqface на github"
Дополнение от 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) В упомянутой диссертации действительно содержательная часть - это про удаление красных глаз. Также, по подобному алгоритму можно удалять "белые глаза", "желтые глаза" и проч. (на фотографиях животных)