Взяти кредит, оформити візу, та й просто запустити смартфон останньої моделі - зробити все це сьогодні неможливо без участі алгоритмів розпізнавання осіб. Вони допомагають поліцейським у розслідуваннях, музикантам - на сцені, але потроху перетворюються на всевидяче око, що стежить за всіма нашими діями онлайн і офлайн.
Алгоритми (технології)
Визначити людину за фото з точки зору комп'ютера означає два дуже різні завдання: по-перше, знайти обличчя на знімку (якщо воно там є), по-друге, вичленувати із зображення ті особливості, які відрізняють цю людину від інших людей з бази даних.
1. Знайти
Спроби навчити комп'ютер знаходити обличчя на фотографіях проводилися ще з початку 1970-х років. Було випробувано безліч підходів, але найважливіший прорив стався істотно пізніше - зі створенням у 2001 році Полом Віолою і Майклом Джонсом методу каскадного бустингу, тобто ланцюжка слабких класифікаторів. Хоча зараз є і більш хитрі алгоритми, можна посперечатися, що і у вашому стільниковому телефоні, і у фотоапараті працює саме старий добрий Віола - Джонс. Вся справа в чудовій швидкості і надійності: навіть у далекому 2001 році середній комп'ютер за допомогою цього методу міг обробляти по 15 знімків на секунду. Сьогодні ефективність алгоритму задовольняє всім розумним вимогам. Головне, що потрібно знати про цей метод, - він влаштований дивно просто. Ви навіть не повірите наскільки.
- Крок 1. Прибираємо колір і перетворюємо зображення на матрицю яскравості.
- Крок 2. Накладаємо на неї одну з квадратних масок - вони називаються ознаками Хаара. Проходимося з нею по всьому зображенню, змінюючи положення і розмір.
- Крок 3. Складаємо цифрові значення яскравості з тих комірок матриці, які потрапили під білу частину маски, і віднімаємо з них ті значення, що потрапили під чорну частину. Якщо хоча б в одному з випадків різність білих і чорних областей виявилася вище певного порогу, беремо цю область зображення в подальшу роботу. Якщо ні - забуваємо про неї, тут обличчя немає.
- Крок 4. Повторюємо з кроку 2 вже з новою маскою - але тільки в тій області зображення, яка пройшла перше випробування.
Чому це працює? Подивіться на знак [1]. Майже на всіх фотографіях область очей завжди трохи темніше області безпосередньо нижче. Подивіться на ознаку [2]: світла область посередині відповідає переносиці, розташованій між темними очима. На перший погляд чорно-білі маски зовсім не схожі на обличчя, але при всій своїй примітивності вони мають високу узагальнюючу силу.
Чому так швидко? В описаному алгоритмі не позначено один важливий момент. Щоб відняти яскравість однієї частини зображення з іншої, потрібно було б складати яскравість кожного пікселя, а їх може бути багато. Тому насправді перед накладенням маски матриця переводиться в інтегральне уявлення: значення в матриці яскравості заздалегідь складаються таким чином, щоб інтегральну яскравість прямокутника можна було отримати складанням всього чотирьох чисел.
Як зібрати каскад? Хоча кожен етап накладення маски дає дуже велику помилку (реальна точність ненабагато перевищує 50%), сила алгоритму - в каскадній організації процесу. Це дозволяє швидко викидати з аналізу області, де обличчя точно немає, і витрачати зусилля тільки на ті області, які можуть дати результат. Такий принцип складання слабких класифікаторів у послідовності називається бустингом (докладніше про нього можна прочитати в жовтневому номері «ПМ» або тут). Загальний принцип такий: навіть великі помилки, будучи перемножені один на одного, стануть невеликі.
2. Спростити
Знайти особливості особи, які дозволили б ідентифікувати її власника, означає звести реальність до формули. Мова йде про спрощення, причому вельми радикальне. Наприклад, різних комбінацій пікселів навіть на мініатюрному фото 64 ст.164 пікселя може бути величезна кількість - (28) 64 ст.164 = 232768 штук. При цьому для того, щоб пронумерувати кожного з 7,6 млрд людей на Землі, вистачило б всього 33 біти. Переходячи від однієї цифри до іншої, потрібно викинути весь сторонній шум, але зберегти найважливіші індивідуальні особливості. Фахівці зі статистики, добре знайомі з такими завданнями, розробили безліч інструментів спрощення даних. Наприклад, метод головних компонент, який і заклав основу ідентифікації осіб. Втім, останнім часом згорточні нейромережі залишили старі методи далеко позаду. Їх будова досить своєрідна, але, по суті, це теж метод спрощення: його завдання - звести конкретне зображення до набору особливостей.
Крок 1
Накладаємо на зображення маску фіксованого розміру (правильно вона називається ядром згортки), перемножуємо яскравість кожного пікселя зображення на значення яскравості в масці. Знаходимо середнє значення для всіх пікселів у віконці і записуємо його в одну комірку наступного рівня.
Крок 2.
Зсуваємо маску на фіксований крок, знову перемножуємо і знову записуємо середнє в карту ознак.
Крок 3.
Пройшовшись по всьому зображенню з однією маскою, повторюємо з іншою - отримуємо нову карту ознак.
Крок 4.
Зменшуємо розмір наших карток: беремо кілька сусідніх пікселів (наприклад, квадрат 2 ст.12 або 3 ст.13) і переносимо на наступний рівень тільки одне максимальне значення. Те ж саме проводимо для карт, отриманих з усіма іншими масками.