TILT: Transform Invariant Low-rank Textures (Must know!)

[Smorodov 579]

Интересные статьи и код на матлабе (на opencv перевести дело пары часов):
http://perception.csl.illinois.edu/matrix-rank/tilt.html
Запускаемые файлы hello_*.m.

Здесь лекция на англ. http://videolectures.net/mlss2011_candes_lowrank/

[mrgloom 242]

я не понял там используется симметрия или текстура?

что если применить к изображению, где есть непостоянная текстура?

[Smorodov 579]

Там используются текстуры.

А именно то свойство, что текстуры имеют сильную структурную связь.

Из чего следует, что ранг матрицы (ранг отражает кол-во информации содержащейся в матрице) имеет маленькое значение относительно размера картинки с текстурой.

Насколько я понял, выровненная текстура имеет ранг меньший чем не выровненная.

В алгоритме берется кусочек картинки с текстурой, и некоторое преобразование (в примере, как варианты используется аффинное, гомография и евклидово).

У каждого преобразования есть несколько параметров искажений (поворот, сдвиг, ...).

После того, как все это задано, мы имеем дело с задачей минимизации ранга матрицы. Решив которую, получаем параметры преобразования в той модели которую использовали для искажения картинки.

Вот кратко, что я понял.

Еще интересные вещи здесь: https://sites.google.com/site/igorcarron2/matrixfactorizations

http://blog.sciencenet.cn/blog-594639-594851.html

[mrgloom 242]

http://perception.csl.illinois.edu/matrix-rank/introduction.html#RPCA

что то я не понял, а как PCA используется для вписывания линий?

[mrgloom 242]

http://www.cs.unc.edu/~jmf/publications/ECCV_2010_Wu_et_al.pdf

http://homes.cs.washington.edu/~ccwu/figures/poster-eccv10.pdf

нечто смежное

позволяет находить повторяющиеся структуры.

тут код

http://cs.unc.edu/~ccwu/repetition/download.html

[Smorodov 579]

http://perception.csl.illinois.edu/matrix-rank/introduction.html#RPCA

что то я не понял, а как PCA используется для вписывания линий?

Множество точек рассматривается как некоторое распределение, PCA дает нам оси в порядке величины дисперсии. Вдоль линии дисперсия максимальна, следовательно первый собственный вектор будет направлен вдоль линии.

[mrgloom 242]

Наткнулся я на RASL который основан на том же аппарате, что и TILT, посмотрел таки эту видеолекцию.

Ну вообщем математическую часть не понял, точнее только в общих чертах,

 

для последующего ознакомления тэги:

low rank matrix approximation, robast pca, netflix prize, blind deconvolution, truncated svd,face subspace,low dimensional linear structure,convex programming, semidefinite programming.

 

Как я понял, что для того чтобы сделать совмещения лиц надо во-первых лица одного и того же человека(как выкинуть из выборки лишние там не рассказали)

и видимо это можно потом использовать чтобы получить совмещенное и усредненное лицо и использовать его как образ человека(т.е. по сути одно нормированное лицо вместо n лиц), т.е. даже если мы в базе получим хорошие нормированные и наложенные лица, то когда придет новое лицо мы его не сможем развернуть.

Еще метод используется для вычитания фона, и еще что то там было про изменение освещенности (changing lighting conditions) , я так и не понял боиться ли он их или наоборот хорошо справляется.

 

И еще непонятно как TILT работает с человеком который держит кубок и с автомобильным номером, как я понял, он ищет представление в котором ранг матрицы минимален, т.е. много зависмых строк, а если у нас неоднородная структура на кубке и на номере буквы, то вроде как это условие нарушается, или же алгоритм не обращает на это внимание? и как бы под low rank approximation подразумевается, что у нас есть некий желтый овальнй предмет(кубок) и зеленый прямоугольник(табличка с номером).

[Smorodov 579]

По поводу выравнивания кучи изображений посмотрите еще 

congealing, здесь есть и pdf-ка и исходники:

http://vis-www.cs.umass.edu/code/congealingcomplex/

 

По поводу мужика с кубком, я думаю что кубок воспринимается алгоритмом как толстая линия с высокочастотным рисунком на почти равномерном фоне.

И алгоритм пытается выставить его (путем концентрации всех неоднородностей в небольшом количестве строк/столбцов ) так, чтобы ось была вдоль (или поперек) изображения, увеличив, тем самым, количество одинаковых

строк/столбцов, то есть уменьшив ранг. Симметрия, кстати, тоже уменьшает ранг матрицы, так как удваивает количество одинаковых

строк/столбцов.

[mrgloom 242]

По поводу мужика с кубком, я думаю что кубок воспринимается алгоритмом как толстая линия с высокочастотным рисунком на почти равномерном фоне.

И алгоритм пытается выставить его (путем концентрации всех неоднородностей в небольшом количестве строк/столбцов ) так, чтобы ось была вдоль (или поперек) изображения, увеличив, тем самым, количество одинаковых

строк/столбцов, то есть уменьшив ранг.

 

Ну да это я и имел ввиду

 

 

Мне кажется высокочастотные детали алгоритм воспринимает как шум (на картинке разреженная матрица).

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

 

 

И еще тут лекция почти тоже самое

 

 

но у него ужасный акцент так что лучше пейпер

http://web.stanford.edu/group/mmds/slides2012/s-ma.pdf

 

 

Еще материалы:

http://www.eecs.berkeley.edu/~yang/courses/ECCV2012/

Изменено July 22, 2015 пользователем mrgloom

[mrgloom 242]

вот такая обзорная статья получилась преимущественно из картинок

http://habrahabr.ru/post/245497/

без обзора RASL,RPCA.

[Nuzhny 243]

Интересно, спасибо. Надо будет как-нибудь на OpenCV переписать и побаловаться.

[Smorodov 579]

Ну чтобы не писать с нуля, вот начальная версия, делал давно, прилеплялку баннера так и не закончил:

 

 

 

исходник:

 

TILT.cpp 

 

Если что то улучшите, будет здорово.

 

Юзаге:

 

щелкаем левой кнопкой в одном углу начальной рамки затем в другом (ничего не отображается) затем жмем кнопку и ждем.

[mrgloom 242]

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

Почему в якобиане вычисляется разница изображений? Какой в этом смысл?

Не мешает то что при трансформе изображение получаются черные бока?

В простейшем случае можно было бы прокрутить маленькое изображение на определенный градус(получиться N изображений с разным углом и у всех посчитать ранг, точнее nuclear norm через svd) хотя у вас так похоже и делается в ф-ии getInitialGuess.

 

 

Еще можно было бы дать ссылку на форум, но я боюсь, что он упадёт.Или на ваш код с указанием автора(если вы не против).

Кстати dropbox тоже отказывает говорят и у яндекс диска есть ограничение на скорость если файл очень популярный.

Думаю оптимальный вариант это githhub или gist.

[Nuzhny 243]

Разность изображений - это первое приближение производной.

 

P.S. Не являюсь участником Хабра, но статьи иногда на нём попадаются интересные. Полезно иметь на нём аккаунт (который по инвайтам)? Что он даёт?

[Smorodov 579]

 

Еще можно было бы дать ссылку на форум, но я боюсь, что он упадёт.Или на ваш код с указанием автора(если вы не против).

Кстати dropbox тоже отказывает говорят и у яндекс диска есть ограничение на скорость если файл очень популярный.

Думаю оптимальный вариант это githhub или gist.

 

Сделал начальный коммит: https://github.com/Smorodov/TILT-Cpp-port

 

Записал видео работы:

[mrgloom 242]

там 2 типа аккаунтов сейчас, мне по-моему автоматом дали ридонли когда я регался на toster.ru (хотя уже не помню), а инвайт за статью.

http://habrahabr.ru/info/help/registration/

 

 

Попробую пока набросать простенький пример на матлабе, и еще чем чревато использование ф-ии fminsearch ? (без якобиана)

fminsearch can often handle discontinuity, particularly if it does not occur near the solution. fminsearch may only give local solutions.

 

кстати в матлабе ранг матрицы считается через svd http://www.mathworks.com/help/matlab/ref/rank.html

 

 

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

[Smorodov 579]

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

 

Что то типа этого имелось ввиду?

 

http://www.compvision.ru/forum/index.php/topic/977-%D0%BF%D0%BE%D0%BD%D0%B8%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5-%D1%80%D0%B0%D0%BD%D0%B3%D0%B0-%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B-%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F-matrix-rank-approximation/?hl=%D1%80%D0%B0%D0%BD%D0%B3

 

По поводу якобиана, я думаю это скажется главным образом на скорости сходимости.

[mrgloom 242]

Нет, по ссылке это "сжатие" изображения через svd.

 

А я про

http://habrastorage.org/files/ba5/b5d/4bb/ba5b5d4bb47c42598596f69a666ea8c4.PNG

http://habrastorage.org/files/77f/e2a/4ff/77fe2a4ffd8942e2b42778247534e593.PNG

http://habrastorage.org/files/48a/02e/4f1/48a02e4f14da480ab366035f7372ae28.PNG

[Smorodov 579]

Я думаю что если в регулярной картинке проделать "дырку", затем уменьшить ранг, то "дырка" заделается как нерегулярность.

[mrgloom 242]

Сначала думал не закрасит,т.к. думал что "воспримет как часть изображения", но при очень малом ранге действительно закрашивает, но толку от этого никакого, т.к. само изображение всё размазано.

 

А в TILT черный квадрат бы воспринялся как часть матрицы с шумом и тем самым бы убрался с низкоранговой матрицы.

 

 

ранг 5 15 100

http://habrastorage.org/files/746/bb4/c7e/746bb4c7ee254561b479fd1ae377b3c1.PNG
http://habrastorage.org/files/784/29c/f49/78429cf49472453a84d89aa1ffd37a9e.PNG

http://habrastorage.org/files/c23/18a/b29/c2318ab2972344a0ba4c9afba383bc73.PNG

 

 

п.с. SelfCalibration.cpp можно в тот же проект на гитхаб запихнуть.

[Smorodov 579]

 

 

п.с. SelfCalibration.cpp можно в тот же проект на гитхаб запихнуть.

 

Запихнул 

 

https://github.com/Smorodov/SelfCalibration

[mrgloom 242]

Вопрос по коду

void transformImg(Mat& img,vector<Point2f>& src_pts,Mat& Tau,Mat& dst)

https://github.com/Smorodov/TILT-Cpp-port/blob/master/src/TILT.cpp#L49

1. Почему мы сразу не берем Tau, которая как я понимаю и есть матрица перспективного преобразования, а ищем по точкам?

2. Как решается проблема: когда мы берем некий кроп от изображения и варпаем то на краях будет черная область \ либо не валидная старая которая по идее будет мешать оптимизации? По идее надо брать всегда рамку заведомо меньше чем изображение, чтобы при любом варпе не было таких областей.

 

[Smorodov 579]

Я уж точно не помню что и почему там делал.

С вырезанием картинок там вообще какая то заморочка была, так тогда и не нашел проблему.