Алгоритм TILT или нестандартное использование ранга матрицы

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


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

Изображение это тоже матрица!
Мы будем использовать определение ранга матрицы
Рангом системы строк (столбцов) матрицы A с m строк и n столбцов называется максимальное число линейно независимых строк (столбцов). Несколько строк (столбцов) называются линейно независимыми, если ни одна из них не выражается линейно через другие. Ранг системы строк всегда равен рангу системы столбцов, и это число называется рангом матрицы.
И какое же изображение будет иметь низкий ранг? Например изображение где есть регулярные структуры:



Как показано на картинке сверху поста, мы моделируем нашу исходную матрицу как матрицу низкого ранга (low rank) + разреженную матрицу с шумом, т.е. на деле это может выглядеть как-то так:



Теперь про сам алгоритм TILT:
К изначальной постановке задачи мы добавляем искажение, т.е. мы восстанавливаем не только матрицу низкого ранга и матрицу с шумом, но и геометрическое искажение(например поворот, аффинное преобразование, проективное преобразование) при котором минимизируется ранг матрицы.

Мы будем задавать наше преобразование матрицей гомографии, хотя возможно задать и более сложное преобразование.
Но на практике не минимизруют ранг матрицы напрямую, а берут nuclear norm, причем для матрицы с шумом берется L1 norm, как я понимаю это делается для регуляризации, т.е. чтобы матрица была разреженной.

Постановка задачи минимизации:




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



Небольшой бонус-пример: снижение размерности матрицы через SVD:
Взято изображение с регулярной структурой и в нем проделана прямоугольная дырка(цвет пикселей приравнен к 0)
ранг 5
image
ранг 15
image
ранг 100
image
Код
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
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 10

    +18
    На самом деле ИМО даже неудачные варианты отработаны не так уж и плохо ^^
      0
      Спасибо) интересно) захотелось попробовать на своих примерах )
        0
        Интересно еще про зашумленные изображения)
          +3
          Из статьи нифига не понял. В частности как именно работает алгоритм.
          Как по мне — набор слов без смысла :)

          Обрабатываете изображение — а оперируете матрицами… Для ламеров, в двух словах о получении матриц было бы не плохо.

          И что само ужасно! Не строчки кода!!!
          Как жить? Как жить я вас спрашиваю, господа? :)
          0
          Классный алгоритм. Конечно, любопытно было бы сравнить когда он даёт отказы и насколько они часты.
          Особенно интересно с лицами. Поиск симметрии на лицах эта целая задачка большая. Мы когда-то с ней сталкивались. Но ни один из открытых алгоритмов или алгоритмов по которым есть статьи нам не показался действительно стабильным и рабочим.

          Ещё любопытно про его скорость работы и сходимость. Вы как-то оценивали эти параметры? Например если пробовать довернуть 10mpx картинку, то сильно нужно её размерность уменьшать? Если ест несколько локальных минимумов, то он сойдётся в какой-то один, или будет прыгать туда-сюда?
            0
            Да, и в догонку. Вы сами алгоритм пробовали? В реальности часто оказывается, что статья красиво написанная, с виду всё работает, а возьмёшься делать алгоритм, а там никакой стабильности работы и в помине нет. Моар камеры всё убивает.
              +2
              Там в коде используется пирамида для ускорения вычислений, а еще там куча параметров, что не радует, так как не понятно как их настраивать, но по ощущениям код работает быстро.

              Какого то полномаштабного сравнения не производил, но я попробовал на реальных автомобильных номерах(надо выбирать рект ближе к номеру(чтобы было поменьше фона), не всегда срабатывает правильно, т.е. не доворачивает), а так же на лицах.Но на самом деле для лиц нам нужен не просто разворот, а нам нужно совмещение лиц(обычно делают просто совмещение по глазам и рту) и есть модификация основанная всё на той же кухне которая это делает, возможно я напишу об этом статью попозже.

              Ошибки он делает, я даже привел в статье случаи, и бывает еще хуже если он за что то уцепиться и сойдется не туда, биения я не наблюдал.

              пример для лиц с детектором матлаба

                0
                Круто! Нужно будет при случае как-нибудь затестить:)

            Only users with full accounts can post comments. Log in, please.