Про котів і математику, або Магія Computer Vision
Привіт! Мене звати Олександр, я працюю у компанії Abto Software, і це вже друга моя публікація на DOU. Кажуть, що всі автори все життя пишуть одну велику книгу, а я, мабуть, намагаюся написати одну велику статтю про те, що світ єдиний, що немає непотрібних знань, а поділ на предмети — умовний.
Минулого разу ми спробували показати, як «непотрібні» шкільні знання можуть суттєво допомогти в практичних Computer Vision проектах, а зараз поговоримо про теорію матриць. Про котиків і теорію матриць.
Скромна чарівливість сингулярного розкладу
Все починалося як гра — проходження тестів на уважність. Ну, ви знаєте: на малюнку є багато-багато однотипних елементів, потрібно знайти один чи декілька, що відрізняються від решти (Google легко знаходить такі картинки, спробуйте, щось типу find the odd one out hard).
Ось декілька прикладів:
Я би сказав, що це такий собі тест Тюрінга навпаки. Людський мозок не дуже пристосований до вирішення подібних задач.
Чи можна то якось автоматизувати? Перше, що приходить на думку — вирізати один із однотипних елементів:
...і, використовуючи його як шаблон, порахувати матрицю кореляції для всього зображення (окремо для кожного RGB-каналу).
І це справді працює!
Ви вже знаєте, де шукати кота? Ок, давайте ще перемножимо поелементно RGB-канали отриманої кореляційної матриці, тоді результат стане очевидним:
Але це не дуже зручно у практичних застосуваннях! Проблема у тому, що для кожної картинки шаблон треба вибирати вручну. Окрім того, у реальному світі зображення того самого об’єкта можуть досить сильно відрізнятися (наприклад, залежно від освітлення). І ось тут нам на допомогу приходить теорія матриць, якщо точніше — сингулярний розклад матриці (сингулярне представлення матриці чи англ. singular value decomposition, SVD). У вікіпедії можна трохи прочитати, що це таке, хоча основна ідея доволі проста: ми представляємо матрицю вигляді матричного добутку деяких матриць
(
транспоноване):
Основна властивість сингулярного розкладу полягає в тому, що він (SVD) дає оптимальне наближення для матриці , якщо у матриці
залишити тільки перші
елементів, а решту просто занулити:
Зауважимо, що у діагональній матриці усі елементи впорядковані за спаданням (
), тому нам потрібно відкидати найменші елементи.
Але повернімося до наших котиків :) Гіфка нижче показує, як буде виглядати наше зображення, якщо залишати рівно елементів у матриці
для його сингулярного розкладу.
Основна ідея тепер така: оцінюємо зображення, залишаючи сингулярних значень і знаходимо між ними різницю по модулю, яка і покаже, де сховався наш кіт!
Але як знайти ? Скільки саме сингулярних значень потрібно залишати? Можна показати, що
має бути рівним рангу матриці, але ми зробимо інакше.
Коли ми генерували гіфку, що була показана вище, то зберігали кожне зображення у форматі .png. Оскільки це растровий формат збереження графічної інформації, що використовує стиснення без втрат, то давайте побудуємо графік розміру у байтах для кожного зображення. Ми очікуємо, що для оптимального значення зображення буде мати максимальний розмір (оскільки в ньому буде міститися максимальна кількість інформації при мінімальній надлишковості).
Кружечком відмічено точку, що відповідає значенню , при цьому розмір файлу є максимальним і рівним 325 737 байт.
Це працює і для решти картинок, що наведені на початку:
Сингулярний розклад використовується для розв’язування найрізноманітніших задач — від наближення методом найменших квадратів і розв’язку систем рівнянь до стискання зображень. При цьому використовуються різні властивості сингулярного розкладу, наприклад, здатність показувати ранг матриці і наближати матриці даного рангу. А ще SVD дозволяє обчислювати обернені і псевдообернені матриці великого розміру, що робить його корисним інструментом під час вирішення задач регресійного аналізу.
Про псевдообернені матриці ми й будемо говорити далі.
«Найпростіша у світі неможлива проблема»
Назва цього розділу — це переклад назви статті Кліва Баррі Моулера, що вийшла у 1990 році. Ім’я її автора відоме тим, хто користується програмою MATLAB. Клів Моулер (англ. Cleve Barry Moler; народився 17 серпня 1939 у Солт-Лейк-Сіті) — американський математик і програміст, що спеціалізується на чисельному аналізі. Це людина, яка придумала MATLAB (у 1984 році Моулер разом із Джеком Літтлом заснували компанію MathWorks, щоб комерціалізувати цю програму).
Так от, у вказаній статті Клів Моулер ставить просте питання: «Я задумав два числа, їхнє середнє рівне 3, які саме це числа?» Подумайте хвилинку: а як би ви відповіли на це питання? Подумали? Добре, читаємо далі :)
Зрозуміло, що «правильних» відповідей є безліч (мене мучать сумніви, чи є сенс писати «правильних» у лапках!), кожен з вас може навести свої два числа і, якщо їхнє середнє рівне 3, то ваш варіант, безумовно, є правильним. Але давайте формалізуємо задачу і запишемо її умову у матричній формі:
де — вектор-стовпець (розміром
) для наших невідомих чисел, введена деяка матриця
розміром
, а
— просто число (вектор розміром
).
Ок, але що це нам дає? Ця система є недовизначеною (кількість змінних перевищує кількість рівнянь) і, не вводячи додаткових обмежень, ми не можемо зафіксувати розв’язок.
Одна з «правильних» відповідей є такою: якщо — матриця
(при чому
) і
— вектор-стовпець з
компонентами, то
є рішенням у сенсі найменших квадратів для недовизначеної системи рівнянь
. (Здається, я розумію, чому я використовую лапки!)
У нашому випадку маємо і
. Наша матриця має повний ранг, але найбільше його значення є
. Отже, ми отримуємо рішення як мінімум з однією ненульовою складовою. Більше того, є рівно два рішення з однією ненульовою складовою,
та
. Здебільшого залишають той варіант, де ненульова компонента має найменший індекс:
.
Інша «правильна» відповідь — це узагальнення операції обертання матриці, зокрема, псевдообернення Мура-Пенроуза. Якщо дуже просто — розв’язок, що отримується за допомогою псевдообернення Мура-Пенроуза, мінімізує довжину вектора , що у нашому випадку дає:
. Цей розв’язок виглядає «правильнішим», бо він простий і єдиний! Запам’ятаємо це.
«Дитяче питання», або MATLAB і когнітивна асиметрія мозку
А тепер давайте спробуємо розв’язати іншу «дитячу» задачу, умова якої наведена на малюнку (думаю, ви вже її зустрічали):
В описі задачі сказано, що програмісти розв’язують її за годину. Ми це зробимо швидше.
Основна гіпотеза, яку ми перевіримо: кожна цифра , що використовується для запису
; а числа, що стоять у правій частині рівностей — це сума ваг зліва. Наприклад, для першої рівності маємо:
для другої:
і так далі. Знайшовши невідомі коефіцієнти , ми можемо порахувати суму
що і буде відповіддю на поставлене питання. Але як знайти коефіцієнти ? Запишемо умову задачі у матричній формі:
де — вектор-стовпець змінних, його розмір, як вказувалось,
,
— це вектор-стовпець чисел, що стоять у правій частині наших рівностей, розмір
(
— це число наших рівностей), а от матриця
визначається дещо складніше.
Розмір її — , кожне значення
— це кількість разів, які цифра
зустрічається у записі числа
-ї рівності
. Не дуже зрозуміло? Давайте подивимось на прикладі.
Для першої рівності цифра
у числі
зустрічається 1 раз, таким чином
; цифри
не зустрічаються зовсім, отже
;
зустрічається двічі, тому
; аналогічно,
. Заповнюємо таким чином повністю матрицю
.
Таким чином, кількість змінних рівно , кількість рівнянь —
, що є більше за
, отже наша система є недовизначеною. Але ми вже знаємо, як діяти далі! Додадаємо трохи магії Мура-Пенроуза:
знаходимо розв’язок системи:
і шуканий результат:
З використанням MATLAB в годину вкладаємось. Перевірено.
Але що означає символ для значення
? У даному випадку цей символ використовується для позначення невизначеного (тобто, будь-якого) значення. Так сталося тому, що цифра
у записі лівих частин рівностей не зустрічалась жодного разу.
Ок, знайшовши відповідь, ми відкриваємо Google, щоб порівняти з правильною, і на нас чекає велика несподіванка! Ні, знайдена відповідь (число ) є правильною, але розв’язок пропонується шукати як кількість «кружечків» у кожній цифрі!
Чи допоможе нам в тому MATLAB? Допоможе.
Передусім переформулюємо задачу пошуку «кружечків». Зрозуміло, що тепер будемо працювати не з абстрактними системами рівнянь, а із зображенням, картинкою з вихідними даними задачі. Кожен «кружечок», як цифра , чи закруток у цифрі
, цікаві тим, що ділять площину на 2 незв’язні області — внутрішню і зовнішню, а якщо подивитися, наприклад, на цифри
чи
, які не мають «кружечків», то площина на незв’язні області не ділиться, отже загальна кількість областей буде рівною
. Взагалі-то це називається топологією.
Визначимо тепер поняття зв’язності: будемо називати дві точки зв’язаними, якщо відстань між ними у -метриці рівна
. Простішими словами, кожна точка має рівно чотири зв’язаних сусіди (північ, південь, захід, схід), тому ми будемо називати цей випадок 4-зв’язністю.
Тепер зрозуміло, що ми маємо робити далі.
1) Беремо фрагмент вихідної картинки, що містить зображення числа :
2) Трохи згладжуємо (за допомогою гаусівського фільтру):
3) Бінаризуємо (по Отсу), у остаточному бінарному зображенні значенню відповідає білий колір, а значенню
— чорний:
А тепер замалюємо кожну 4-зв’язну область, що складається виключно з , своїм кольором — фон нехай буде синій, а «острови» у цифрі
— у жовтий і ціановий (як же цей колір правильно називається?):
Отже, загальна кількість 4-зв’язних областей для нашого фрагмента дорівнює , а якщо не рахувати фон (інакше всі праві частини наших рівностей були би збільшені на
), то результат буде рівним
, що знову дає правильну відповідь.
Але правильну чи «правильну»? Що є істина? ©
Два способи розв’язку нашої «дитячої» задачі — алгебраїчний і топологічний — відображають два способи, якими людина пізнає світ. Не будучи фахівцем з нейрофізіології, мені все ж таки видається, що людям з домінантною лівою (абстрактно-логічною) півкулею мозку ближче буде алгебраїчний підхід, а тим, у кого провідною є права (образно-емоційна), — топологічний.
Ілюзія обману, або Чи завжди ми бачимо те, що бачимо
Коли ми говоримо про Computer Vision, комп’ютерне бачення, то маємо на увазі спробу алгоритмізувати (що би ми не розуміли під цим терміном) деякі аспекти людського бачення, таку собі гру в імітацію. Але чи добре ми розуміємо, як саме влаштовано Human Vision? Картинка нижче (автор її — Едвард Адельсон) показує, що не дуже — що би нам не говорили, ми абсолютно впевнені, що квадрат А має чорний колір, а квадрат В — білий. І взагалі всі білі квадрати (так само, як і всі чорні) мають однаковий колір.
Але подивіться на гіфку:
Невже колір залежить від оточення?! Але яким чином мозок розуміє, що саме ми повинні побачити, яким чином фільтрується вплив тіні?
Давайте розбиратися.
Наша гіпотеза буде така: ми бачимо світ не як сукупність точок різного кольору (пікселів), під час сприйняття зображень наш мозок робить якесь проміжне перетворення. І ми спробуємо знайти, яке саме.
Передусім згадаємо (і повсякденний досвід підтверджує це), що найбільш інформативними областями зображення є границі між областями (edges).
Але чи не забагато інформації ми відкидаємо? Напевно, що так, з попереднього малюнку ми не можемо точно відновити вихідне зображення. Але ідея з границями нам подобається, просто треба враховувати не лише наявність переходів між кольорами, а й величину і знак цього переходу. Хто ще трохи пам’ятає фізику, той одразу зрозуміє, що мова йде про градієнти:
Добре, але чи можемо ми з градієнтів отримати вихідне зображення? Виявляється, що так, і в цьому нам знову допоможе псевдообернення Мура-Пенроуза. Не зупиняючись на математичних деталях, можемо одразу показати результат:
Якщо цікаві всі викладки, можете знайти їх у статті. Внесок автора власне і був у тому, щоб використовуючи ідею псевдообернення, стиснути декілька сторінок достатньо складного для розуміння тексту у просту формулу:
Ну, добре, припустімо, що мозок справді тримає інформацію про зображення у вигляді кількох градієнтів, але яким саме чином це пояснює нашу ілюзію? Насправді, залишилось зробити ще один крок — будемо вважати, що мозок зберігає градієнти не абсолютно точно (це дозволило би робити точну реконструкцію зображення), викидає малі за модулем елементи (тобто заміняє малі за модулем значення нулями). Кодування з втратами, щось по типу алгоритму jpeg. І ось тут бачимо найцікавіше: якщо зробити реконструкцію з модифікованих градієнтів, то ефект від тіні зникає! Дивіться самі (я зробив бінаризацію за порогом 1/2 для вихідного зображення і зображення, що зібрано з модифікованих градієнтів):
Що ми бачимо: для вихідного зображення об’єктивний колір квадратів і
є однаково білим, хоча сприймаються вони по-різному. Що стосується зображення із градієнтів, то все стало на свої місця: чорні клітинки стали чорними, білі — білими, вплив тіні майже відсутній.
Чи справді мозок саме таким чином зберігає зображення, як було описано — я не знаю. Повторюся, я не є спеціалістом з нейрофізіології. Але цей спосіб є простим, достатньо зрозумілим і дозволяє побудувати ефективний алгоритм обробки зображень при наявності нерівномірного освітлення. Як на мене, це по-справжньому красиво!
Отож, завершити цю статтю хочу закликом із попередньої: нехай ваші рішення будуть не лише ефективними, але й красивими!
