Система Віоли — Джонса виявляння об'єктів

Систе́ма Ві́оли — Джо́нса виявля́ння об'є́ктів (англ. Viola–Jones object detection framework) — це система машинного навчання виявляння об'єктів, запропонована 2001 року Полом Віолою^[en] та Майклом Джонсом^[en].^[1]^[2] Її було вмотивовано головно задачею виявляння облич, хоча її можливо пристосовувати й для виявляння інших класів об'єктів.

Цей алгоритм ефективний для свого часу, здатний виявляти обличчя на зображеннях 384 на 288 пікселів зі швидкістю 15 кадрів за секунду на звичайному Intel Pentium III 700 МГц. Він також стійкий, забезпечує високі влучність та повноту.

Хоч він і має нижчу точність за сучасніші методи, такі як згорткова нейронна мережа, його ефективність і компактний розмір (лише близько 50 тисяч параметрів у порівнянні з мільйонами параметрів для типових ЗНМ, таких як DeepFace^[en]) означають, що його все ще використовують у випадках з обмеженою обчислювальною потужністю. Наприклад, у первинній праці^[1] повідомили, що цей виявляч облич може працювати на Compaq iPAQ з 2 кадрами за секунду (цей пристрій має малопотужний StrongARM без апаратного забезпечення рухомої коми).

Опис задачі ред.

Виявляння облич — це задача бінарної класифікації, поєднана з задачею встановлення розташування: для заданого зображення вирішити чи воно містить обличчя, і побудувати обмежувальні рамки для облич.

Щоби зробити це завдання легшим, алгоритм Віоли — Джонса виявляє лише повністю видимі (без затуляння) фронтальні (без повороту голови) вертикальні (без нахилу), добре освітлені повнорозмірні (займають більшу частину кадру) обличчя на зображеннях із фіксованою роздільністю.

Ці обмеження не такі суворі, як здається, оскільки можливо унормовувати картинку, щоби наближувати її до вимог Віоли — Джонса.

будь-яке зображення можливо перемасштабувати до фіксованої роздільності
для загального зображення з обличчям невідомого розміру та спрямування можливо виконувати виявляння плям, щоби виявляти потенційні обличчя, а потім масштабувати й повертати їх у вертикальне, повнорозмірне положення.
яскравість зображення можливо виправляти за допомогою балансування білого.
обмежувальні рамки можливо знаходити, ковзаючи вікном усім зображенням та позначуючи кожне вікно, яке містить обличчя.
- Як правило, це виявлятиме одне й те ж обличчя декілька разів, до чого можливо застосовувати методи усування дублювання, наприклад, придушування немаксимумів.

Вимога «фронтальності» не підлягає обговоренню, оскільки не існує простого перетворення зображення, яке могло би перетворювати обличчя з профілю на анфас. Проте можливо натренувати декілька класифікаторів Віоли — Джонса, по одному на кут: один для анфасу, один для огляду в 3/4, один для профілю, ще кілька для кутів між ними. Потім під час виконання можливо виконувати всі ці класифікатори паралельно, щоби виявляти обличчя під різними кутами огляду.

Вимога «повної видимості» також не підлягає обговоренню, і її неможливо виконати, просто навчивши більше класифікаторів Віоли — Джонса, оскільки існує занадто багато можливих способів затуляння обличчя.

Складові системи ред.

Повне подання алгоритму наведено в ^[3].

Розгляньмо зображення $I(x,y)$ фіксованої роздільності $(M,N)$ . Наше завдання — ухвалити бінарне рішення: чи це фотографія стандартизованого обличчя (фронтального, добре освітленого тощо), чи ні.

Віола — Джонс — це, по суті, алгоритм навчання ознак з підсилюванням, тренований за допомогою видозміненого алгоритму AdaBoost^[en] на класифікаторах гааровими ознаками для пошуку послідовності класифікаторів $f_{1},f_{2},...,f_{k}$ . Класифікатори гааровими ознаками грубі, але обчислюються дуже швидко, а видозмінений AdaBoost створює сильний класифікатор із багатьох слабких.

Під час виконання задане зображення $I$ послідовно перевіряють на $f_{1}(I),f_{2}(I),...f_{k}(I)$ . Якщо в будь-який момент $f_{i}(I)=0$ , алгоритм негайно повертає «обличчя не виявлено». Якщо всі класифікатори повертають 1, тоді алгоритм повертає «обличчя виявлено». Через це класифікатор Віоли — Джонса також називають «каскадним гааровим класифікатором» (англ. "Haar cascade classifier").

Класифікатори гааровими ознаками ред.

Розгляньмо перцептрон $f_{w,b}$ , визначений двома змінними $w(x,y),b$ . Він бере зображення $I(x,y)$ фіксованої роздільності, й повертає

$f_{w,b}(I)={\begin{cases}1,\quad {\text{якщо }}\sum _{x,y}w(x,y)I(x,y)+b>0\\0,\quad {\text{інакше}}\end{cases}}$

Приклад прямокутних елементів, показаних відносно охопного вікна виявляння

Класифікатор гааровими ознаками — це перцептрон $f_{w,b}$ з дуже особливим видом $w$ , що робить його надзвичайно невитратним для обчислення. А саме, якщо ми випишемо матрицю $w(x,y)$ , ми виявимо, що вона набуває лише трьох можливих значень $\{+1,-1,0\}$ , і якщо ми забарвимо матрицю білим на $+1$ , чорним на $-1$ , та прозорим на $0$ , то ця матриця це один з 5 можливих шаблонів, показаних праворуч.

Кожен шаблон також мусить бути симетричним відносно x та y (без урахування зміни кольору), тому, наприклад, для горизонтальної біло-чорної ознаки ці два прямокутники мусять мати однакову ширину. Для вертикальної біло-чорно-білої ознаки білі прямокутники мусять мати однакову висоту, але обмежень щодо висоти чорного прямокутника немає.

На обличчя накладено гаарову ознаку, схожу на перенісся

На обличчя накладено гаарову ознаку, схожу на область очей, темнішу за верхню частину щік

Обґрунтування гаарових ознак ред.

Гаарові ознаки, які використовують в алгоритмі Віоли — Джонса, — це підмножина загальніших гаарових базисних функцій, які раніше використовували в галузі виявляння об'єктів на основі зображень.^[4]

Незважаючи на грубість порівняно з такими альтернативами як керовані фільтри, гаарові ознаки достатньо складні, щоби їх було можливо зіставляти з ознаками типових людських облич. Наприклад:

Область очей темніша за верхню частину щік.
Область перенісся світліша за очі.

Склад властивостей, які утворюють зіста́вні ознаки обличчя:

Розташування й розмір: очі, рот, перенісся
Значення: напрямлені градієнти яскравості пікселів

Крім того, будова гаарових ознак дозволяє ефективно обчислювати $f_{w,b}(I)$ з використанням лише сталої кількості додавань і віднімань, незалежно від розміру прямокутних елементів, завдяки використанню таблиці сумарних площ.

Навчання та використання класифікатора Віоли — Джонса ред.

Обрати роздільність $(M,N)$ для класифікування зображень. У первинній статті радили $(M,N)=(24,24)$ .

навчання ред.

Зібрати навчальний набір, де одні зображення містять обличчя, а інші ні. Виконати певне видозмінене тренування AdaBoost на наборі всіх класифікаторів гааровими ознаками розмірності $(M,N)$ , поки не буде досягнуто бажаного рівня влучності та повноти. Цей видозмінений алгоритм AdaBoost видаватиме послідовність класифікаторів гааровими ознаками $f_{1},f_{2},...,f_{k}$ .

Деталі видозміненого алгоритму AdaBoost розкрито нижче.

використання ред.

Щоби скористатися класифікатором Віоли — Джонса з $f_{1},f_{2},...,f_{k}$ на зображенні $I$ , послідовно обчислити $f_{1}(I),f_{2}(I),...f_{k}(I)$ . Якщо в будь-який момент, $f_{i}(I)=0$ , алгоритм негайно повертає «обличчя не виявлено». Якщо всі класифікатори повертають 1, то алгоритм повертає «виявлено обличчя».

Алгоритм навчання ред.

Одначе швидкість, з якою можливо оцінювати ознаки, не компенсує належним чином їхню кількість. Наприклад, у стандартному підвікні розміром 24x24 пікселі загалом є $M = 162336$ ^[5] можливих ознак, і було би до неможливого витратно під час перевірки зображення оцінювати їх усі. Тож ця система виявляння об'єктів використовує варіант алгоритму навчання AdaBoost^[en] як для обрання найкращих ознак, так і для тренування класифікаторів, які їх використовують. Цей алгоритм створює «сильний» класифікатор як лінійну комбінацію зважених простих «слабких» класифікаторів.

h(\mathbf {x} )=\operatorname {sgn} \left(\sum _{j=1}^{M}\alpha _{j}h_{j}(\mathbf {x} )\right)

Кожен слабкий класифікатор — це порогова функція на основі ознаки $f_{j}$ .

h_{j}(\mathbf {x} )={\begin{cases}-s_{j}&{\text{якщо }}f_{j}<\theta _{j}\\s_{j}&{\text{інакше}}\end{cases}}

Порогове значення $\theta _{j}$ та полярність $s_{j}\in \pm 1$ визначають тренуванням, як і коефіцієнти $\alpha _{j}$ .

Тут подано спрощену версію алгоритму навчання:^[6]

Вхід: Набір із $N$ позитивних і негативних тренувальних зображень із їхніми мітками ${(\mathbf {x} ^{i},y^{i})}$ . Якщо зображення $i$ є обличчям, $y^{i}=1$ , якщо ні, $y^{i}=-1$ .

Ініціалізація: призначити вагу $w_{1}^{i}={\frac {1}{N}}$ кожному зображенню $i$ .
Для кожної ознаки $f_{j}$ з $j=1,...,M$
1. Перенормувати ваги так, щоб вони давали в сумі одиницю.
2. Застосувати ознаку до кожного зображення в тренувальному наборі, а потім знайти оптимальні поріг та полярність $\theta _{j},s_{j}$ , які мінімізують зважену похибку класифікування. Тобто, $\theta _{j},s_{j}=\arg \min _{\theta ,s}\;\sum _{i=1}^{N}w_{j}^{i}\varepsilon _{j}^{i}$ , де $\varepsilon _{j}^{i}={\begin{cases}0&{\text{if }}y^{i}=h_{j}(\mathbf {x} ^{i},\theta _{j},s_{j})\\1&{\text{інакше}}\end{cases}}$
3. Призначити вагу $\alpha _{j}$ пороговій функції $h_{j}$ , що обернено пропорційно частоті помилок. Таким чином на найкращі класифікатори зважають більше.
4. Ваги для наступної ітерації, тобто $w_{j+1}^{i}$ , зменшують для зображень $i$ , які було класифіковано правильно.
Встановити остаточний класифікатор в $h(\mathbf {x} )=\operatorname {sgn} \left(\sum _{j=1}^{M}\alpha _{j}h_{j}(\mathbf {x} )\right)$

Каскадна архітектура ред.

Позитивними (обличчями) є в середньому лише 0,01 % усіх підвікон
На всі підвікна витрачається однаковий час обчислення

Мусимо витрачати більшу частину часу на лише потенційно позитивні підвікна.

Простий 2-ознаковий класифікатор може досягати майже 100 % рівня виявляння з 50 % рівнем ХП.
Цей класифікатор може діяти як 1-й шар ряду для відфільтровування більшості негативних вікон
2-й рівень із 10 ознаками може впоруватися зі «складнішими» негативними вікнами, які вижили на 1-му рівні, й так далі…
Каскад поступово складніших класифікаторів досягає ще кращих рівнів виявляння. Оцінювання сильних класифікаторів, породжених процесом навчання, можливо робити швидко, але недостатньо швидко для реального часу. Через це сильні класифікатори впорядковують у каскад у порядку складності, де кожен наступний класифікатор навчається лише на тих обраних зразках, які проходять через попередні класифікатори. Якщо на будь-якій стадії каскаду класифікатор відхиляє підвікно, яке перевіряє, то подальшу обробку не виконують, і продовжують пошук у наступному підвікні. Тому каскад має вигляд виродженого дерева. У випадку облич перший класифікатор у каскаді — званий оператором уваги — використовує лише дві ознаки, досягаючи хибнонегативного рівня приблизно 0 % й хибнопозитивного рівня 40 %.^[7] Дія цього єдиного класифікатора полягає в зменшенні кількості оцінювання всього каскаду приблизно вдвічі.

У каскадуванні кожен етап складається з сильного класифікатора. Таким чином, усі ознаки згруповано в кілька етапів, де кожен етап має певну кількість ознак.

Робота кожного етапу полягає у визначенні того, чи дане підвікно точно не обличчя, чи воно може ним бути. Дане підвікно негайно відкидають як не обличчя, якщо воно не проходить будь-якого з етапів.

Нижче наведено просту систему для навчання каскаду:

f = пошаровий максимально прийнятний хибнопозитивний рівень.
d = пошаровий мінімально прийнятний рівень виявляння.
Ftarget = цільовий загальний хибнопозитивний рівень.
P = набір позитивних прикладів.
N = набір негативних прикладів.

F(0) = 1,0; D(0) = 1,0; i = 0

поки F(i) > Ftarget
  збільшити i
  n(i) = 0; F(i)= F(i-1)

  поки F(i) > f × F(i-1)
    збільшити n(i)
    використати P та N для тренування класифікатора з n(i) ознаками за допомогою AdaBoost^[en]
    Оцінити поточний каскадний класифікатор на затверджувальному наборі, щоби визначити F(i) та D(i)
    зменшити поріг для i-того класифікатора (тобто скільки слабких класифікаторів потрібно задовольнити, щоби задовольнити сильний)
      допоки поточний каскадний класифікатор не матиме рівня виявляння принаймні d × D(i-1) (це також впливає на F(i))
  N = ∅
  якщо F(i) > Ftarget то 
    оцінити поточний каскадний виявляч на наборі зображень без облич 
    та помістити будь-які хибні виявлення до набору N.

Каскадна архітектура має цікаві наслідки для продуктивності окремих класифікаторів. Оскільки активування кожного класифікатора повністю залежить від поведінки його попередника, хибнопозитивний рівень всього каскаду становить

F=\prod _{i=1}^{K}f_{i}.

Аналогічно, рівень виявляння

D=\prod _{i=1}^{K}d_{i}.

Отже, щоби відповідати хибнопозитивним рівням, яких зазвичай досягають інші виявлячі, кожен класифікатор може виходити з напрочуд низькою продуктивністю. Наприклад, для 32-етапного каскаду для досягнення хибнопозитивного рівня 10⁻⁶ кожен класифікатор повинен досягти хибнопозитивного рівня лише приблизно 65 %. Водночас, проте, кожен класифікатор повинен мати виняткові можливості для досягання адекватного рівня виявляння. Наприклад, щоби досягти рівня виявляння близько 90 %, кожному класифікаторові у вищезгаданому каскаді потрібно досягти рівня виявляння близько 99,7 %.^[8]

Використання Віоли — Джонса для відстежування об'єктів ред.

У відео рухомих об'єктів не потрібно застосовувати функцію виявляння об'єктів до кожного кадру. Замість цього можливо використовувати такі алгоритми відстежування як алгоритм КЛТ, щоб виявляти характерні ознаки в обмежувальних рамках виявляння та відстежувати їхнє переміщення між кадрами. Це не лише покращує швидкість відстежування, усуваючи потребу повторно виявляти об'єкти в кожному кадрі, але й покращує стійкість, оскільки характерні ознаки стійкіші до обертання та фотометричних змін, ніж система виявляння Віоли — Джонса.^[9]

Примітки ред.

↑ ^а ^б Viola, P.; Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001. IEEE Comput. Soc. 1. doi:10.1109/cvpr.2001.990517. ISBN 0-7695-1272-0. S2CID 2715202. (англ.)
↑ Viola, Paul; Jones, Michael J. (May 2004). Robust Real-Time Face Detection. International Journal of Computer Vision. 57 (2): 137—154. doi:10.1023/b:visi.0000013087.49260.fb. ISSN 0920-5691. S2CID 2796017. (англ.)
↑ Wang, Yi-Qing (26 червня 2014). An Analysis of the Viola-Jones Face Detection Algorithm. Image Processing on Line. 4: 128—148. doi:10.5201/ipol.2014.104. ISSN 2105-1232. (англ.)
↑ C. Papageorgiou, M. Oren and T. Poggio. A General Framework for Object Detection. International Conference on Computer Vision, 1998 (англ.)
↑ Viola-Jones' face detection claims 180k features. stackoverflow.com. Процитовано 27 червня 2017. (англ.)
↑ R. Szeliski, Computer Vision, algorithms and applications, Springer (англ.)
↑ Viola, Jones: Robust Real-time Object Detection, IJCV 2001 Див. с. 11. (англ.)
↑ Torbert, Shane (2016). Applied Computer Science (вид. 2nd). Springer. с. 122—131. (англ.)
↑ Face Detection and Tracking using the KLT algorithm (англ.)

Посилання ред.

Слайди, що подають цю систему (англ.)
Інформація щодо гаарових базисних функцій (англ.)
Розширення системи Віоли — Джонса з використанням ознаки SURF. Архів оригіналу за 18 жовтня 2020. (англ.)
IMMI - Rapidminer Image Mining Extension. Архів оригіналу за 3 липня 2022. — інструмент із відкритим кодом для добування з зображень
Robust Real-Time Face Detection (PDF). Архів оригіналу (PDF) за 2 лютого 2019. (англ.)
An improved algorithm on Viola-Jones object detector (англ.)
Цитування алгоритму Віоли — Джонса в Академії Google
Video lecture on Viola–Jones algorithm на YouTube — Пояснення Adaboost з ppt від Ціна Чена, Discovery Labs, Університет Оттави, та відеолекція від Рамшрі Ґутхама.

Втілення ред.

Jensen, Ole Helvig. Implementing the Viola–Jones Face Detection Algorithm (PDF). Архів оригіналу (PDF) за 21 жовтня 2018. (англ.)
MATLAB: [1], [2]
OpenCV: втілено як cvHaarDetectObjects() .
- Гаарове каскадне виявляння в OpenCV (англ.)
- Тренування гаарового каскаду в OpenCV (англ.)

[:0-1] а ^б Viola, P.; Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001. IEEE Comput. Soc. 1. doi:10.1109/cvpr.2001.990517. ISBN 0-7695-1272-0. S2CID 2715202. (англ.)

[Viola_137–154-2] Viola, Paul; Jones, Michael J. (May 2004). Robust Real-Time Face Detection. International Journal of Computer Vision. 57 (2): 137—154. doi:10.1023/b:visi.0000013087.49260.fb. ISSN 0920-5691. S2CID 2796017. (англ.)

[3] Wang, Yi-Qing (26 червня 2014). An Analysis of the Viola-Jones Face Detection Algorithm. Image Processing on Line. 4: 128—148. doi:10.5201/ipol.2014.104. ISSN 2105-1232. (англ.)

[4] C. Papageorgiou, M. Oren and T. Poggio. A General Framework for Object Detection. International Conference on Computer Vision, 1998 (англ.)

[5] Viola-Jones' face detection claims 180k features. stackoverflow.com. Процитовано 27 червня 2017. (англ.)

[6] R. Szeliski, Computer Vision, algorithms and applications, Springer (англ.)

[7] Viola, Jones: Robust Real-time Object Detection, IJCV 2001 Див. с. 11. (англ.)

[8] Torbert, Shane (2016). Applied Computer Science (вид. 2nd). Springer. с. 122—131. (англ.)

[9] Face Detection and Tracking using the KLT algorithm (англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]