Сегодня мы рассмотрим алгоритм TILT (Transform Invariant Low-rank Texture) и множество его методов применения в области Computer Vision. Статья будет нести несколько обзорный характер, без плотного углубления в математические дебри.
Идея алгоритма, можно сказать, произрастает из конкурса Netflix Prize, который, по сути, является задачей коллаборативной фильтрации, где мы имеем матрицу пользователей и их оценок: матрица разреженная, в ней отсутствуют элементы, а так же может присутствовать шум, а нам надо для каждого фильма предугадать, какую оценку ему поставит каждый пользователь, т.е. мы заполняем матрицу.
Изображение это тоже матрица!
Мы будем использовать определение ранга матрицы
Как показано на картинке сверху поста, мы моделируем нашу исходную матрицу как матрицу низкого ранга (low rank) + разреженную матрицу с шумом, т.е. на деле это может выглядеть как-то так:
Теперь про сам алгоритм TILT:
К изначальной постановке задачи мы добавляем искажение, т.е. мы восстанавливаем не только матрицу низкого ранга и матрицу с шумом, но и геометрическое искажение(например поворот, аффинное преобразование, проективное преобразование) при котором минимизируется ранг матрицы.
Мы будем задавать наше преобразование матрицей гомографии, хотя возможно задать и более сложное преобразование.
Но на практике не минимизруют ранг матрицы напрямую, а берут nuclear norm, причем для матрицы с шумом берется L1 norm, как я понимаю это делается для регуляризации, т.е. чтобы матрица была разреженной.
Постановка задачи минимизации:
Затем алгоритм итеративно сходиться к оптимальному решению, используя методы оптимизации, как показано на видео:
Небольшой бонус-пример: снижение размерности матрицы через SVD:
Взято изображение с регулярной структурой и в нем проделана прямоугольная дырка(цвет пикселей приравнен к 0)
ранг 5
ранг 15
ранг 100
Теперь переходим к самому интересному, а именно к практическим применениям:
Автокалибровка искажения линз:
Дополненная реальность:
Автоповорот текста, вывесок и штрихкодов:
И да, низкий ранг имеют не только картинки с повторяющейся структурой, но и симметрия снижает ранг! Еще стоит заметить, что если у человека повязка на одном глазу(человек-пират) или на одну сторону зачёсана челка, это не помешает алгоритму «найти симметрию» ведь мы помним что алгоритм моделирует так же и шум.
Автоповорот лиц, козлов и любых предметов имеющих симметрию:
Автоповорот автомобильного номера(небольшой привет недавним постам про распознавание автомобильного номера от 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
Идея алгоритма, можно сказать, произрастает из конкурса 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
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
