Про котів і математику, або Магія 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 і когнітивна асиметрія мозку

А тепер давайте спробуємо розв'язків зв'язати іншу «дитячу» завдання, умова якої наведена на малюнку (думаю, ви вже її зустрічали ):

В описі задачі сказано, що програмісти розв'язків язують її за годину. Ми це зробимо швидше.

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

для другої:

і так далі. Знайшовши невідомі коефіцієнти , ми можемо порахувати суму

що і буде відповіддю на поставлене питання. Альо як знайті коефіцієнти ? Запишемо умову задачі у матричній формі:

де — вектор-стовпець змінних, його розмір, як вказувалось, , — це вектор-стовпець чисел, що стояти у правій частині наших рівностей, розмір (— це число наших рівностей), а від матриця визначається дещо складніше.

Розмір її — , кожне значення — це кількість разів, які цифра зустрічається у записі числа -ї рівності . Не дуже зрозуміло? Давайте подивімось на прикладі.

Для першої рівності цифра в числі зустрічається 1 раз, таким чином ; цифри не зустрічаються зовсім, отже ; зустрічається двічі, тому ; аналогічно, . Заповнюємо таким чином повністю матрицю .

Таким чином, кількість змінних рівно , кількість рівнянь — , що є більше за , отже наша система є перевизначеною. Але ми вже знаємо, як діяти далі! Додадаємо трохи магії Мура-Пенроуза:

знаходимо зв'язок розв'язків системи:

і шуканий результат:

З використанням MATLAB в годину вкладаємось. Перевірено.

Але що означає символ для значення ? У даному випадку цей символ використовується для позначення невизначеного (тобто, будь-якого) значення. Так сталося тому, що цифра у записі лівих частин рівностей не зустрічалась жодного разу.

Ок, знайшовши відповідь, ми відкриваємо Google, щоб порівняти з правильною, і на нас чекає велика несподіванка! Ні, знайдена відповідь (число ) є правильною, але розв'язків зв'язок пропонується шукати як кількість «кружечків» у кожній цифрі!

Чи допоможе нам у тому MATLAB? Допоможе.

Передусім переформулюємо завдання пошуку «кружечків». Зрозуміло, що тепер будемо працювати не з абстрактними системами рівнянь, а із зображенням, картинкою з вихідними даними задачі. Кожен «кружечок», як цифра , чи закруток у цифрі , цікаві тім, що ділять площину на 2 незв'язні області — внутрішню і зовнішню, а якщо подивитися, наприклад, на цифри чі , які не мають «кружечків», то площина на незв'язні області не ділиться, отже загальна кількість областей буде рівною . Взагалі-то це називається топологією.

Визначимо тепер поняття зв'язку язності: будемо називати дві точки зв'язку язаними, якщо відстань між ними -метриці рівна . Простішими словами, кожна точка має рівно чотири зв'язку язаних сусіди (північ, південь, захід, схід), тому ми будемо називати цей випадок 4-зв'язку язністю.

Тепер зрозуміло, що ми маємо робити далі.

1) Беремо фрагмент віхідної картинки, що містить зображення числа :

2) Трохи згладжуємо (за допомогою гаусівського фільтру):

3) Бінаризуємо (за Відсутності), у залишковому бінарному зображенні значенню відповідає білий колір, а значенню — чорний:

А тепер замалюємо кожну 4-зв'язку язну область, що складається виключно з , своїм кольором — фон нехай буде мідь, а «острови» у цифрі — у жовтий і ціановий (як же цей колір правильно називається ?):

Отже, загальна кількість 4-зв'язку язних областей для нашого фрагмента дорівнює , а якщо не рахувати фон (інакше всі праві частини наших рівностей були би збільшені на ), то результат буде рівним , що знову дає правильну відповідь.

Два спосібі розв'язків язку нашої «дитячої» задачі — алгебраїчний і топологічний — відображають два спосібі, якими людина пізнає світ. Не будучи фахівцем з нейрофізіології, мені все ж таки видається, що людям з домінантною лівою (абстрактно-логічною) півкулею мозку ближче буде алгебраїчний підхід, а тим, у кого провідною є права (образно-емоційна), — топологічний.

Ілюзія обману, або Чи завжди ми бачимо те, що бачимо

Коли ми говоримо про Computer Vision, комп'ютерній ютерне бачення, то маємо на увазі спробу алгоритмізувати (що б ми не розуміли під цим терміном) деякі аспекти людського бачення, таку собі гру в імітацію. Але чи добре ми розуміємо, як саме влаштовано Human Vision? Картинка нижче (автор її — Едвард Адельсон ) показує, що не дуже — що б нам не говорили, ми абсолютно впевнені, що квадрат А має чорний колір, а квадрат — білий. І взагалі всі білі квадрати (так само, як і всі чорні) мають однаковий колір.

Але подивіться на гіфку:

Невже колір залежить від оточення?! Але яким чином мозок розуміє, що саме ми повинні побачити, яким чином фільтрується вплив тіні?

Давайте розбиратися.

Наша гіпотеза буде така: ми бачимо світ не як сукупність точок різного кольору (пікселів), під час сприйняття зображень наш мозок робить якесь проміжне перетворення. І ми спробуємо знайте, яке саме.

Передусім згадаємо (і повсякденний досвід підтверджує це), що найбільш інформативними областями зображення є границі між областями (edges).

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

Добре, але чи можемо ми з градієнтів отримати вихідне зображення? Виявляється, що так, і в цьому нам знову допоможе псевдообернення Мура-Пенроуза. Не зупиняючись на математичних деталях, можемо одразу показати результат:

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

Ну, добре, припустімо, що мозок справді тримає інформацію про зображення у вигляді кількох градієнтів, але яким саме чином це пояснює нашу ілюзію? Насправді, залишилось зробити ще один крок — будемо вважати, що мозок зберігає градієнти не абсолютно точно (це дозволив бі робити точну реконструкцію зображення), викидає малі за модулем елементи (тобто заміняє малі за модулем значення нулями). Кодування з втратами, щось по типу алгоритму jpeg. І вісь тут бачимо найцікавіше: якщо зробити реконструкцію з модифікованих градієнтів, то ефект від тіні зникає! Дивіться самі (я зробив бінаризацію за порогом 1/2 для вихідного зображення і зображення, що зібрано з модифікованих градієнтів):

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

Чи справді мозок саме таким чином зберігає зображення, як було описано — я не знаю. Повторюся, я не є спеціалістом з нейрофізіології. Але цей спосіб є вибачимо, достатня зрозумілим і дозволяє побудувати ефективний алгоритм обробки зображень при наявності нерівномірного освітлення. Як на мене, це по-справжньому красиво!

Отож, завершити цю статтю хочу закликом із попередньої : нехай ваші рішення будуть не лише ефективними, але й красивими!

Опубліковано: 16/12/19 @ 11:00
Розділ Різне

SEO Блог