×Закрыть

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-кадри поскладані один над одним.

Технологія і мистецтво тісно переплітаються — саме цей підхід був використаний нью-йоркським художником Джеєм Марком Джонсоном для створення картини танцівниці.

Ойлер, або Як теорія графів допомагає в сегментації зображень

Сегментація — це процес розділення зображення на певним чином схожі частини: вони можуть мати однаковий колір або спільну межу. Сегментація є основною частиною комп’ютерного бачення. Згадайте, як у попередньому прикладі ми сегментуємо перерізи гіперкубів для підрахунку булочок або автомобілів.

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

Коротко про те, що таке граф. Граф — це структура, побудована з ряду об’єктів. Зазвичай вони називаються вершинами або вузлами, а зв’язки між вузлами — дугами або ребрами.

Ось для прикладу графічне зображення 4-вимірного гіперкуба, тессеракта.

Повернімося знову до матриці пікселів і будемо розглядати кожен піксель як вузол графа, з’єднаний з сусідами по краях. Для цілей сегментації ми розглядаємо простий поділ на передній план і фон. Кожен піксель може належати або до переднього плану, або до фону — з певною ймовірністю. З іншого боку, ми можемо розглянути геометричну відстань від кожного пікселя до його сусідів.

Ці два спостереження дозволяють нам працювати з малюнком як з графом і переформулювати завдання сегментації в термінах теорії графів.

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

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

Ось кадр із відео, де зображено серфінгістку на хвилях. І нам треба відділити її від заднього фону.

Ви можете побачити, як вода і піна у фоновому режимі повністю видаляються на кожному кадрі.

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

Про що говорять нам всі ці історії? У першу чергу, вони про те, що іноді для розв’язання непідйомної проблеми потрібно зробити крок назад і поглянути на неї з перспектив інших сфер. Ви ніколи не знаєте, чи найкраще рішення не сховане на іншому боці вашої книжкової полиці.

Світ єдиний. Це тільки в школі вивчення ділиться на предмети. Цілісно дивіться навкруги, пробуйте шукати відповіді у сусідніх дисциплінах. І нехай ваші рішення будуть не лише ефективними, але й красивими!

LinkedIn

31 комментарий

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Большое спасибо за статью!

Я работаю в компании, которая создает промышленные сортировочные машины. Булочки и прочие орешки действительно считаются высокоскоростной линейной камерой, и в большинстве случаем главным объектом для работы у нас является именно одна линия изображения.

Только я никогда бы не проассоциировал такой подход с пространственно-временным гиперкубом. Для меня это просто одно бесконечное в одном направлении изображение, которое обрабатывается как непрерывный поток.

Загальновідома тестова картинка Лєна значно цікавіша якщо взяти її повну tech.velmont.net/...​iles/2009/04/len_full.jpg

Надо же, а сколько раз эта картинка упоминается в учебниках и научных статьях =)

Напомнить мой недавний вброс по порнохаб и ML?
Ну и задача по разделение порно и не порно давно востребована. Когда-то ее мыщьх пытался решать, но ему знаний в образах не хватило и срок у него был 1-2 месяца только. А я так быстро не умею подобные задачи делать. Так что чем там у него с той задачкой закончилось я знаю. Знаю, что заказчик у него был, но очень нетерпеливый. Да и сам мыщьх еще тот псих был — работать с ним ну очень сложно.
Да и собственно задачка потребует только полгода на первый кривой прототип и еще от 1.5 года на доводку до рабочего варианта.

В наших краях о потребностях в такой задаче не слышал. У мыщъха в Америки закачик был.

В CS багато чого з’явилося завдяки військовим, порно і рекламі.

В CS багато чого з’явилося завдяки військовим, порно і рекламі.

Реклама военного порно? %)

И задачки на графах, типа как с минимальными усилиями разбить транспортную сеть на изолированные области.

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

Lena Söderberg, Playboy, November 1972. В CG, в те времена, кстати это была традиция — сканить плейбой для сэмпловых изображений.

Дякую за статтю!

OFFTOPIC: Технічна стаття на ДОУ в п’ятницю?!

А коли ж ще публікувати такі картинки?
s.dou.ua/storage-files/girl2.png

Спасибо за статью! Техника с гиперкубом очень крутая.

Дякую. Чудова стаття, читається дуже легко.

Спасибо за статью, особенно за булочки — очень познавательно!

Еще один необычный способ показать признаки — рисовать кривые (по одной на каждый образец) как сумму синусоид (базовая частота, х2, х3 и т.д.) где амплитуда каждой синусоиды определяется значением конкретного признака.

типу зворотнього Фур’є-перетворення? класна ідея, спробую!

Да. А ваша идея с булочками в гиперпространстве преследует меня целый день =)

Дякую, дуже цікава стаття.

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

Трохи вірніше буде сказати, ви вважаєте, що за теорією Дарвіна люди, яки не вміли обробляти риси людських облич, вмерли не залишивши нащадків, залишили тільки ті, хто мали таку здатність.

Годный контент. Спасибо!

Ну а за ГА покритикую. Он сам по себе хорош, но считает обычно нуууууу ооооочеееееень дооооооолгоооооо.

считает обычно нуууууу ооооочеееееень дооооооолгоооооо

все от реализации зависит))

Расскажи про быстрые реализации.

В моем случае все от fitness-function зависело — на нее 95% cpu usage приходилось.
Соответственно все упиралось в ее оптимизацию. Если помнишь я как-то делал сравнение по производительности фильтрации сигналов для разных языков — github.com/doomviruz/PerfTests
это как раз оно (естественно сильно упрощенное).

Вот в этом и особенность ГА. В каждом случае нужно сильно с ним повозиться, чтобы ускорить его. Получается, что если подходить что попроще, то лучше его заюзать. Для поиска глобального максимума тот же SA попроще и возни поменьше. Да еще может когда развлекусь им и на Куду (опенцл) положу — не очень сложно он выглядит для распараллеливания в отличие от градиентных или ГА.

ГА був обраний просто для прикладу. Я згоден з вами, що збігається він достатньо повільно, основна його перевага — в більшості випадків не залипає в локальних екстремумах, особливо коли цільова функція не дуже гладка

Критика была больше в том, что в работе чаще нет возможности долго возиться с ГА и вынужден юзать что попроще и придумывать обходные пути.

Окрема подяка за Айнштайна! А тепер можна й почитати :)

Max-flow/min-cut вже нерелевантні. Нейронні мережі більш надійні у сегментації.
Алгоритм для підрахунку авто буде помилятися у випадках різкої зміни освітлення.

Для смены освещения можно добавить адаптацию по фону, например.

приблизно так це і зроблено) я в статті просто хотів показати красиву ідею

А за это спасибо. Идея с «разрезанием» очень понравилась. С одной стороны она лежит на поверхности, но с другой, часто просто не видишь таких идей. А то, что ты ее описал позволяет мне ее явно в память положить и воспользоваться в нужный момент.

Подписаться на комментарии