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

Систе́ма Ві́оли — Джо́нса виявля́ння об'є́ктів (англ. 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].

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Слайди, що подають цю систему (англ.)
• Інформація щодо гаарових базисних функцій (англ.)
• Розширення системи Віоли — Джонса з використанням ознаки 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 (англ.)