Science is the new black, або фізика і Computer Vision
Привіт! Мене звати Олександр, я — Head of Science в компанії Abto Software, PhD, маю досвід викладання. За освітою я — фізик-теоретик і це, безперечно, накладає певний відбиток на все, з чим я маю справу.
Упродовж останніх 15 років я працюю в R&D-командах, а це означає, що кожен новий проект — terra incognita, дослідити яку можна лише безперервно експериментуючи. Ви ніколи не знаєте напевно, де шукати рішення і чи існує воно взагалі.
Третій закон Кларка стверджує, що кожна достатньо розвинута технологія не відрізняється від магії. Я би додав, що розвинута технологія насправді мало чим відрізняється від мистецтва. Адже коли ми говоримо про технологію як про мистецтво, то маємо на увазі два аспекти — красиві результати (про що власне й говорив Кларк!) і красиві рішення, коли розв’язок часткової проблеми народжується з цілісного уявлення про Всесвіт та людські знання.
У цій статті я розповім, як теорія еволюції, спеціальна теорія відносності і теорія графів були корисними у Computer Vision проектах.
Отже, чим Чарльз Дарвін, Альберт Айнштайн та Леонард Ойлер можуть допомогти в обробці зображень і відео?
Дарвін, або Як теорія еволюції допомагає зрозуміти багатовимірні дані
Перша історія про те, як ми намагалися зрозуміти багатовимірні дані за допомогою теорії еволюції.
Отож, уявіть собі, що нам потрібно створити програму для вимірювання розмірів людського тіла на основі короткого відеозапису за участі цієї людини. Перше, що спадає на думку в такому випадку, — це йти і вимірювати реальних людей, а далі тренувати модель, використовуючи якийсь з Machine Learning-підходів.
Звучить начебто просто, але проблема полягає в тому, що наша модель може стати «занадто тренованою» до певних нетипових даних, як наприклад, у випадку з Тіріоном Ланністером чи Грегором Кліганом.
Ось таблиця з вимірами тіл групи людей. У першому рядку — мої особисті дані, а поруч з таблицею — силует мого тіла. Далі у таблиці маємо виміри інших людей — їхній зріст, окружність шиї, грудей, талії тощо. Неозброєним оком складно виявити серед цих даних випадки з нетиповими пропорціями тіла.
Далі один зі способів, як це можна зробити:
Те, що ви бачите, називається star-діаграми. Їх часто використовують для швидкої візуальної оцінки даних. Кожен із параметрів, зазначених у таблиці, — це радіальна лінія, спиця в star-діаграмі. Чисельне значення відповідає довжині спиці.
Завдяки такій візуалізації ми вже бачимо, що в наборі даних є нетипові елементи. Деякі зірки значно відрізняються за розмірами і загальною формою. Це дещо полегшує нам розуміння даних, чи не так?
Однак така візуалізція має свої недоліки:
- По-перше, важко відстежувати особливості, тим паче — різного масштабу. Всі спиці виглядають однаково, тому важко порівняти, наприклад, висоту людини з окружністю шиї. Нормалізація даних звичайно допомагає, але повністю проблеми не вирішує.
- По-друге, складно описати форми по суті. Особливо коли параметрів (променів зірки) є більше п’яти.
Чи можемо ми використовувати щось більш знайоме нам, більш значуще, ніж просто спиці на star-діаграмі?
На щастя, еволюція забезпечила нас неймовірно потужним візуальним аналізатором, який точно налаштований виділяти і розпізнавати особливості людських облич.
Американський математик Герман Чернов (Herman Chernoff) застосував цей факт для розробки відомої системи візуалізації багатовимірних даних, де дані були зіставлені з рисами обличчя.
Наприклад, так:
Зріст відповідає розміру обличчя, окружність шиї — формі лоба і так далі.
Спробуймо тепер замість зірок намалювати обличчя!
Відповідно до візуалізації облич Чернова, наші дані виглядатимуть ось так:
Які бачимо переваги?
- По-перше, легко визначити нетипові дані (зверніть, наприклад, увагу на обличчя, що знаходиться по центру).
- По-друге, легко визначити спільні риси та формування кластерів за розміром або формою обличчя. Легше порівнювати та обговорювати дані.
На цю ідею можна подивитися під іншим кутом. Суб’єктивно, все красиве часто є в якомусь сенсі оптимальним. Але чи є оптимальне красивим, хоча б іноді?
Наприклад, ми хочемо порівняти декілька алгоритмів, які виконують мінімізацію якоїсь цільової функції. Є відомі метрики порівняння, але чи можна результат побачити у прямому сенсі цього слова?
Ідея така: давайте порівнювати ці алгоритми на тестовій задачі наближення людського обличчя за допомогою геометричних примітивів, таких як лінії, прямокутники тощо. Переможцем, як правило, є алгоритм, який малює більш красиве обличчя.
На малюнках нижче показано результат запуску генетичного алгоритму оптимізації з різними початковими параметрами (конкретніше, мінявся параметр EliteCount, що відповідає за частку популяції, яка переходить в наступне покоління). Значення цільової функції в обох випадках однакове! Тим не менш, верхня картинка (EliteCount=50) виглядає гірше за нижню (EliteCount=5). І справді, як свідчать експерименти, другий варіант збігається до кращого значення цільової функції.
Ми точно не розуміємо, чому і як це працює на біологічному рівні, але це працює. Як підказує теорія Дарвіна, в результаті мільйонів років еволюції людський мозок придбав надзвичайну здатність обробляти риси людських облич, оскільки це було необхідним для виживання в суспільстві.
Це підводить нас до висновку, що ми можемо візуалізувати та розуміти багатовимірні дані. Для цього просто треба знайти правильну візуалізацію, бажано таку, що підтримується «програмним» та «апаратним» забезпеченням вашого мозку.
Айнштайн, або Як спеціальна теорія відносності допомагає рахувати об’єкти
Ще один приклад того, як знання з інших галузей допомагають у задачах Computer Vision. Мені як фізику цей приклад особливо подобається, і зараз ви зрозумієте чому.
Ось експеримент з підрахунком об’єктів.
Уявіть, будь ласка, стрічку конвеєра в пекарні: булочки рухаються ременем конвеєра, і ми повинні порахувати їх з певною точністю. Наше рішення, звичайно, буде засноване на Computer Vision. Для початку ставимо камеру і знімаємо на відео булочки, які перетинають певну, заздалегідь визначену лінію. Далі намагаємося відстежувати булочки та підраховувати, скільки разів їхні траєкторії перетинають лінію підрахунку.
І цей метод працює. Здебільшого. В чому тоді недосконалість?
- Цей метод чутливий до точного відстеження об’єктів (це непроста задача — спробуйте точно ідентифікувати кожну булочку на конвеєрі);
- Як наслідок, обчислювальна складність рішення є високою.
Окрім того, нам дуже хочеться, щоб рішення було універсальним. Але різні типи об’єктів вимагають різних алгоритмів обробки, що робить проект дорогим.
І тут нам приходять на допомогу ідеї спеціальної теорії відносності Айнштайна: замість покадрового представлення (обробка відео проводиться послідовно кадр за кадром), спробуємо використати представлення просторово-часового куба.
Ось монтаж послідовних кадрів, які повинні бути оброблені:
Традиційний підхід, де кожний кадр аналізується індивідуально, вимагає ідентифікації та відстеження кожного об’єкту, що є дуже обтяжливою задачею і знижує точність підрахунку.
З іншого боку, ми можемо підрахувати ці об’єкти на стороні гіперкуба після того, як розрізали його вздовж лінії підрахунку. Це дозволяє нам переходити від підрахунку в 3D (як це було з традиційним підходом) до підрахунку в 2D, що значно спрощує завдання та підвищує точність. З обчислювальної точки зору, це також означає, що для кожного кадру ми повинні обробляти лише один рядок пікселів замість всього зображення. А це зменшує обчислювальні затрати на 3 порядки!
Як бачите, нам не потрібно відстежувати кожну булочку. Замість послідовності багатьох кадрів, тепер ми маємо лише одне довге зображення з усіма булочками одночасно.
Ті з вас, хто бачив фільм «Прибуття» або читали новелу Теда Чана, що лягла в основу фільму, можуть простежити подібність цього представлення та холістичного способу, через який прибульці-гептаподи сприймали наш світ.
Звичайно, ми все одно повинні порахувати булочки, але тепер це просто.
Наскільки універсальний такий підхід? Що ще можна порахувати, використовуючи його? Насправді — все, що рухається і перетинає якусь лінію: людей, автомобілі, велосипеди тощо.
Ось як алгоритм може бути застосовано до підрахунку транспортних засобів, які перетинають перехрестя.
Все, що нам потрібно — це визначити лінію підрахунку (червона лінія на малюнку). Вона навіть не повинна бути паралельною до країв кадру.
Зліва показано результат роботи алгоритму, що нагадує булочки на конвеєрі. І навіть найскладніший фон не є проблемою: його можна оцінити, а потім видалити, просто усереднивши відповідні пікселі за часом (центральний малюнок). Ви також можете побачити, як менші об’єкти, такі як люди чи собаки, можуть бути відфільтровані за розміром (тому ми залишили на самому правому малюнку тільки автомобілі).
Також зауважте, що (майже в дусі спеціальної теорії відносності) довжина об’єктів точно не відповідає їх фізичній довжині. Вона стискається для швидких об’єктів.
Тепер ми можемо легко порахувати машини.
Ще раз — цей підхід досить універсальний. Він забирає дуже мало часу, коштів і може використовуватися для підрахунку всього, що рухається. Вам просто потрібно думати про відео не як про послідовність кадрів, що розгортається у часі, а як про гіперкуб, де 2D-кадри поскладані один над одним.
Технологія і мистецтво тісно переплітаються — саме цей підхід був використаний нью-йоркським художником Джеєм Марком Джонсоном для створення картини танцівниці.
Ойлер, або Як теорія графів допомагає в сегментації зображень
Сегментація — це процес розділення зображення на певним чином схожі частини: вони можуть мати однаковий колір або спільну межу. Сегментація є основною частиною комп’ютерного бачення. Згадайте, як у попередньому прикладі ми сегментуємо перерізи гіперкубів для підрахунку булочок або автомобілів.
Існує велика кількість різних методів сегментації зображення. І проблема з ними полягає в тому, що найшвидші з них неточні, тоді як найбільш точні — дуже повільні. Ми, звичайно, хочемо отримати і точність, і швидкість. І для цього нам знову буде потрібно дивитися на зображення з іншої точки зору: але тепер замість представлення зображення як матриці пікселів, ми розглядатимемо його як граф.
Коротко про те, що таке граф. Граф — це структура, побудована з ряду об’єктів. Зазвичай вони називаються вершинами або вузлами, а зв’язки між вузлами — дугами або ребрами.
Ось для прикладу графічне зображення
Повернімося знову до матриці пікселів і будемо розглядати кожен піксель як вузол графа, з’єднаний з сусідами по краях. Для цілей сегментації ми розглядаємо простий поділ на передній план і фон. Кожен піксель може належати або до переднього плану, або до фону — з певною ймовірністю. З іншого боку, ми можемо розглянути геометричну відстань від кожного пікселя до його сусідів.
Ці два спостереження дозволяють нам працювати з малюнком як з графом і переформулювати завдання сегментації в термінах теорії графів.
Виявляється, що ця проблема добре відома і має ефективне рішення — теорема про максимальний потік у графі. Тепер сегментація зображення — це розрізування певним чином відповідного графа так, як це схематично показано на малюнку.
Ще один експеримент, який демонструє силу графової сегментації зображення. Цього разу ми попрацюємо з відео.
Ось кадр із відео, де зображено серфінгістку на хвилях. І нам треба відділити її від заднього фону.
Ви можете побачити, як вода і піна у фоновому режимі повністю видаляються на кожному кадрі.
Зверніть увагу, що тінь серфера стає частиною переднього плану. При необхідності тінь також можна видалити, але це вже тема іншої розмови.
Про що говорять нам всі ці історії? У першу чергу, вони про те, що іноді для розв’язання непідйомної проблеми потрібно зробити крок назад і поглянути на неї з перспектив інших сфер. Ви ніколи не знаєте, чи найкраще рішення не сховане на іншому боці вашої книжкової полиці.
Світ єдиний. Це тільки в школі вивчення ділиться на предмети. Цілісно дивіться навкруги, пробуйте шукати відповіді у сусідніх дисциплінах. І нехай ваші рішення будуть не лише ефективними, але й красивими!
