Алгоритм TILT або нестандартне використання рангу матриці

Алгоритм TILT або нестандартне використання рангу матриці

Сьогодні ми розглянемо алгоритм TILT (Transform Invariant Low-rank Texture) і безліч його методів застосування в області Computer Vision. Стаття буде нести дещо оглядовий характер, без щільного заглиблення в математичні дебрі.

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

Зображення це теж матриця!

Ми будемо використовувати визначення рангу матриці

Рангом системи рядків (стовпчиків) матриці A з m рядків і n стовпчиків називається максимальна кількість лінійно незалежних рядків (стовпчиків). Декілька рядків (стовпчиків) називаються лінійно незалежними, якщо жоден з них не виражається лінійно через інші. Ранг системи рядків завжди дорівнює рангу системи стовпчиків, і це число називається рангом матриці.

І яке ж зображення матиме низький ранг? Наприклад зображення де є регулярні структури:

Як показано на картинці зверху посту, ми моделюємо нашу вихідну матрицю як матрицю низького рангу (low rank) + розріджену матрицю з шумом, тобто насправді це може виглядати якось так:

Тепер про сам алгоритм TILT:

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

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

Але на практиці не мінімізують ранг матриці безпосередньо, а беруть nuclear norm, причому для матриці з шумом береться L1 norm, як я розумію це робиться для регуляризації, тобто щоб матриця була розрідженою.

Постановка завдання мінімізації:

Потім алгоритм ітеративно сходитися до оптимального рішення, використовуючи методи оптимізації, як показано на відео:

Невеликий бонус-приклад: зниження розмірності матриці через SVD:

Взято зображення з регулярною структурою і в ньому виконана прямокутна дірка (колір пікселів прирівняний до 0)

ранг 5

ранг 15

ранг 100

Код

clc, clear

k = 100; % rank

% A is the mxn matrix we want to decompose

A = im2double(rgb2gray(imread('low_rank_img.jpg')))';

sz= size(A)

%make black hole

A(100:100+sz(1)/8,100:100+sz(2)/10)=0;

kmax= min(size(A));

if(k>kmax)

k= kmax;

end

tic

% Compute SVD of A directly

[u0, S0, V0] = svd(A,'econ');

A0 = U0(:,1:k) * S0(1:k,1:k) * V0(:,1:k)';

rank(A0)%test if rank = k

toc

display(['SVD Error: ' num2str(norm(A(:)-A0(:)) / norm(A(:)))])

clear U0 S0 V0

Тепер переходимо до найцікавішого, а саме до практичних застосувань:

Автокалібрування лінз:

Доповнена реальність:

Автоповорот тексту, вивісок і штрих-кодів:

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

Автоповорот осіб, козлів і будь-яких предметів, що мають симетрію:

Автоповорот автомобільного номера (невеликий привіт недавнім постам про розпізнавання автомобільного номера від ZlodeiBaal зображення взяті звідси):

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

А що, алгоритм і правда такий хороший?

Не зовсім. Схожість алгоритму до правильного рішення залежить від ініціалізації, ось пара негативних прикладів:

Що далі?

Посилання на оригінальний код на Matlab: TILT code

Посилання на C++ код від Smorodov: TILT-Cpp-port и SelfCalibration

Посилання на публікації: TILT: Transform Invariant Low-rank Textures

Посилання на лекції: Low-rank modeling | The Pursuit of Low-dimensional Structures in High-dimensional Data, Yi Ma, Microsoft

Image