2 of October - MS Stage Free Online conference: .NET, MS SQL, MS Azure, Cosmos DB. REGISTER
×Закрыть

Про котів і математику, або Магія 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 для вихідного зображення і зображення, що зібрано з модифікованих градієнтів):

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

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

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

LinkedIn

38 комментариев

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

Автору дякую! :). А сам пішов читати математику... :)

Дуже цікава та дотепна стаття, що відкриває завісу того, як насправді працює Computer Vision. Дякую автору за детальні пояснення!

Неймовірно цікава стаття. А ще дуже сподобався стиль оповіді. Велике Дякую!

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

Было бы хорошо, если бы вы выложили код для наглядности. Например, не совсем понятно, что было на входе SVD котов и собак: я так понимаю, что по-канально исходное изображение в frequency domain? Если был бы код, то все можно было бы посмотреть глазами.

ні, не frequency domain, а банальний rgb:

[im,map] = imread(url);
if ~isempty(map)
    im = ind2rgb(im,map);
end
f = im2double(im);

for k=1:size(f,3)
    [U(:,:,k),S(:,:,k),V(:,:,k)] = svd(f(:,:,k));
end

Чудова стаття. Автор, не зупиняйтесь

Крутая статья! Рад такое видеть на доу!

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

А вообще столько много математики ради изобретения Cel shading :) en.wikipedia.org/wiki/Cel_shading

Если вести речь про статью указанную в статье, то это ничем не отличается от восстановления сигнала после реверберации. Цвет это или звук разницы нет. Блюр — это цветое эхо.

Если интересует психо-аккустическо-перцептуальная сторона вопроса работы мозга, то глаз это очень продвинутая HDR камера с низким разрешением. Поэтому мозг очень сильно обрабатывает входящее изображение, пытаясь восстановить его после своих же трансформаций. Основная проблема в том, что точное цветовое восприятие с максимальным разрешением идёт только по центру, по переферии изображение очень низкого цветового и пиксельного разрешения, поэтому мозг достраивает изображение, например, если мы видим группу из трёх человек, мозг заставляет глаз просканировать три лица или другие области интереса и только затем приступает к финальной обработке изображения. Перспектива и выраженные тени (low light) — это две области в которых человеческий мозг нещадно портит входное изображение, пытаясь восстановить изображение.

Возвращаясь к checker board и тени на ней, при low light освещении (тень) мозг выделяет две области интереса, то что в тени и то, что не в тени, обрабатывая каждую область независимо, используя различную HDR трансформацию, хотя освещение картинки одинаковое, но мозг об этом не знает, он знает что в тени всё не так, как на свету, таким образом он видит два различных цвета и это действительно два различных цвета для мозга, ведь его задача не передать точный цвет, а воостановить контраст изображения.

Есть такая книга: onlinelibrary.wiley.com/...​ook/10.1002/9781119951483

Color Constancy is HDR (Pages: 273-281) , в гугле можно ознакомиться бесплатно:
books.google.ca/...​PT344#v=onepage&q&f=false

Тут другая статья, очень короткая, в общих чертах описывающая тот же процесс:
thebrain.mcgill.ca/...​icles/color_constancy.pdf

дякую за розгорнутий коментар! я непогано орієнтуюся в сучасних поясненнях checker board ілюзії і безумовно знаю, що таке Color Constancy) в даному випадку це була дещо хуліганська спроба залзіти на чуже поле, не більше того; що ж — маємо наразі а) ще одне пояснення; б) працючий алгоритм shadow corection

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

Например, почему-то во всех CV статьях, особенно где работают с градиентами цветов не используют CIECAM02 цветовую модель — en.wikipedia.org/wiki/CIECAM02 , а банальную BT.601, применяемую в аналоговом телевидении www.itu.int/...​601-7-201103-I!!PDF-E.pdf , а ведь заложенная чувствительность к синему цвету в CAM02 в два раза выше, чем в аналоговом телевидении, которое просто воспроизводит характеристики люминофора CRT телевизоров и ограничений полосы пропускания радиосигнала, а не свойства человеческого глаза.

Например, доказали, что цветовая память основана на длине волны и угла повоорота тона: en.wikipedia.org/wiki/Hue . Что с лёгкостью объясняет старческое брюзжание, что раньше солнце было ярче и трава зеленее, это совсем не старческий маразм, а обычное старение зрения у человека, видя ту же траву спустя 30 лет, мозг с лёгкостью выделяет цветое различие.

я не понял
что вы имели ввиду

характеристики люминофора CRT телевизоров и ограничений полосы пропускания радиосигнала

Что именно не понял? Какое из утверждений? В BT.601 стандарте всё это описано.

Непогано для 2009 року.

Правильно, пускай будут только статьи про трактор, вайти и аджайл.
А кому нужно тот пойдет на Medium или Хабр если с английским не але.

А автору статьи спасибо.

Порекомендуйте тогда, что-то более актуальное. Материалов по CV много, но зачастую там какая-то банальщина.

Нейромережі це круто, але це далеко не весь CV. Навіть сьогодні.

приблизно це ж саме я й хотів сказати)

У такому вигляді CV мало сенс у 2009. Зараз має суто історичну цінність, як і MATLAB.

www.youtube.com/watch?v=oBklltKXtDE

Де тут CV у сенсі «те, що було до появи AlexNet»?

Тут є декілька моментів.

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

Так, це правда, що якщо ми говоримо про такі мейнстрім задачі як classification, object detection чи segmentation — тут на сьогодні використовувати щось окрім нейронок особливо сенсу немає, вони просто працюють суттєво краще.

Але, по-перше, треба враховувати, що дуже часто deep learning підходи використовуються разом з класичними CV алгоритмами (тут можна гуглити watershed, selective search, non-maximum supression, object tracking), без яких нейронки просто не будуть мати сенсу. А по-друге, є ціла низка задач, де класичні підходи до сих пір набато більше популярні за deep learning.

не говорить ні слова про те, наскільки застарілі (або не застарілі) є ті чи інші підходи.

Так, не говорить. Вони просто застарілі і все.

без яких нейронки просто не будуть мати сенсу.

Навіть перетворення кольорового простору тренується, як частина мережі. Оте все, що перераховане — засохле гівно мамонта, окрім object tracking, що взагалі до CV не має відношення.

А по-друге, є ціла низка задач, де класичні підходи до сих пір набато більше популярні за deep learning.

Дехто досі фронтенд вчить за w3schools.

Навіть перетворення кольорового простору тренується, як частина мережі.

Зачем?

Чтоб самим формулу не программировать. Сетка на такую формулу запросто обучится.
Но 99% сеток заточены на RGB. Причина проста — исследователю удобнее с RGB работать. Но более прикольно после. Видео читается и конвертится формат из GPU в RAM, там конвертится в RGB (кодеки часто YUV отдают), затем дается на вхож сетки, которая его снова из RAM в GPU запихивает. А если там 4k, то начинается весело с тормозами наваяного.
И в итоге четка за 5 ms кадр обрабатывает и еще ms 100 его по памяти туда-сюда гоняют.
Но и тут не все плохо. numpy пишут очень грамотные ребята и уже предусмотрели там почти любую дурь юзеров пользователей этой либы.

Сдуру можно много чего, но та же формула легко кладётся на GPU

Но вот почему-то 99% людей предпочитают именно так.

И для релиза логичнее сетке отдать сразу в YUV и в GPU. Но, сетку учить долго и дорого, а есть куча предобученных и опенсурсных бесплатных, но в RGB и из RAM. И тут сразу вспоминаются раки по 3 и по 5.
И самое смешное, что почти всегда работодателям и заказчикам выгоднее, когда по годами мужественно преодолевают тщательно разложенные грабли, а не раскладывают их.
И это только о таких тупейших граблях. Я уже не пишу о граблях, что раскладываются в силу незнания ЦОС и других подходов, кроме нейронок.

Мені здається, що ви не зовсім зрозуміли в чому сенс цієї статті. Чи, швидше, зовсім не)
Я намагався написати легкий по формі текст, в якому хотів довести просту істину — іноді, щоб отримати результат, треба трохи поміняти точку зору. Не більше, але й не менше. А котики, матан і computer vision — це просто засіб, ілюстративний матеріал, за допомогою якого я свою думку довожу. І щоб двічі не вставати — Вам достатньо сказати, що математика мала сенс десь у ХІХ сторіччі, а зараз має суто історічну цінність, і останнє слово назавжди залишиться за Вами)

Вы удивитесь, сколько задач CV можно решить сугубо алгоритмически! На ДОУ была прекрасная статья про подсчет булок на конвейере, которая не требует ML. Другой пример: обнаружение структуры чертежа — это задача CV, но не ML. Знание DL не освобождает от знания теоремы Котельникова, в частности — необходимость low-pass filter перед downsampling`ом ;)

На ДОУ была прекрасная статья про подсчет булок на конвейере, которая не требует ML.

«Добре зафіксований паціент не потребує анестезії» ©

обнаружение структуры чертежа
знания теоремы Котельникова

У вас якась саморобна термінологія. Те, що ви мали на увазі Nyquist—Shannon sampling theorem я згодом зрозумів. А ось що мається на увазі під «обнаружение структуры чертежа» я не дуже.

Тогда предлагаю вам повысить эрудицию, поискав все принятые имена sampling theorem (подсказка: названа по именам ученых, которые ее независимо открыли и опубликовали)

Поплачусь. Сейчас это не модно и не поощряется. Взяли туториал к движку нейронок, по туториалу скопировали код на питоне и запустили — вот что сейчас массово требуется и поощряется.

Тут скорее наглядное подтверждение закона Данинга-Крюгера )

Більше того, згадана Вами стаття про булочки — належить тому ж самому автору :) . Посилання для наглядності: dou.ua/...​/science-computer-vision

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