сшивка в панораму

[mrgloom 242]

помниться из методов оптимизации там был такой метод, что фиксируем все переменные кроме одной и её начинаем варьировать и так для каждой переменной.

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

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

но всё это как то получается вычислительно жирно.

может дешевле даже сделать перебор всех вариантов по графу.

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

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

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

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

по идее в матрице кросскорреляции мы имеем наивыгоднейшие относительные положения для всех пар, но мы не знаем какие пары настоящие, а какие нет.

может только примерно предположить по значению пика.

[Smorodov 579]

Может применить что-то подобное grabcut (или MinCut)?

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

[mrgloom 242]

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

[mrgloom 242]

посмотрел снова xuvtools, поставил XuvStitch-1.8.1-beta4-Win32(теперь можно 2D загружать и собирать панораму)

не смотря на то что большую панораму он плохо сшивает (хотя 1 линию почему то довольно хорошо, даже если длинная)

там есть 1 интересное свойство, что он как бы перебирает комбинации(в итоге не всегда что то хорошее выводит).

[mrgloom 242]

тут предлагается решить линейную систему

кол-во переменных 2*кол-во изображений

кол-во уравнений 2*кол-во пар изображений

по идее можно составить разреженную переопределенную линейную систему уравнений

(только вот я не понимаю решиться ли она, если там есть выбросы?)

http://scien.stanford.edu/pages/labsite/2000/ee368/projects2000/project13/global.html

но непонятно как они получили систему уравнений, где матрицы как элементы, т.е. как её развернуть в нормальный вид http://scien.stanford.edu/pages/labsite/20.../Images/eq3.gif

[mrgloom 242]

Попробовал для 4 картинок, которые имеют реальные связи(как на картинке) и всё равно что то не получилось.

10 уравнений, 8 неизвестных.

x1=0

y1=0

x2= 522+x1

y2= 4+y1

x3= 0+x1

y3= 480+y1

x4= 0+x2

y4= 486+y2

x4= 530+x3

y4= 4+y3

double m_a[10][8] = 

	{   {1,0,0,0,0,0,0,0},//

		{0,1,0,0,0,0,0,0},//

		{-1,0,1,0,0,0,0,0},// 1-2

		{0,-1,0,1,0,0,0,0},

		{-1,0,0,0,1,0,0,0},// 1-3

		{0,-1,0,0,0,1,0,0},

		{0,0,-1,0,0,0,1,0},// 2-4

		{0,0,0,-1,0,0,0,1},

		{0,0,0,0,-1,0,1,0},// 3-4

		{0,0,0,0,0,-1,0,1}

	};

	Mat A= Mat(10, 8, CV_64F, m_a);

	int dx12= 522;

	int dy12= 4;

	int dx13= 0;

	int dy13= 480;

	int dx24= 0;

	int dy24= 486;

	int dx34= 530;

	int dy34= 4;

	double m_b[10][1]={{0},{0},{dx12},{dy12},{dx13},{dy13},{dx24},{dy24},{dx34},{dy34}};

	Mat b= Mat(10, 1, CV_64F, m_;

	Mat x;

	solve(A,b,x,DECOMP_SVD);

	cout<<x<<endl;[/code]

возможно из-за противоречия в цепочках 1-2-4 и 1-3-4

хотя я ошибся наоборот всё нормально, только всё равно непонятно как работать с ложными связями.

[mrgloom 242]

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

просто если её построчно разложить, то получиться

u1*I*P1=u1*I => P1=I

u2*I*P2=u2*A21*P1 =>P2=A21*P1 и т.д. т.е. коэффициенты сокращаются

т.е. как составить систему уравнений из

понятно, но тут не участвуют эти коэффициенты.

[Smorodov 579]

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

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

[mrgloom 242]

да про коэффициенты я понял, это как раз weighted least squares, но эти коэффициенты стоят при каждом квадратичном члене функции которую мы минимизируем и по идее можно изменить начальные уравнения домножив левую и правую часть (хотя наверно надо домножать на sqrt от весов).

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

We therefore in general chose a rather low matching threshold and iteratively discarded the registration pair that ended up having the worst square error after global registration, until the total square error was below another threshold.

вот это я не понимаю что они делали, т.е. "that ended up having the worst square error after global registration" какая ошибка тут имеется ввиду, по идее мы тут можем посчитать только разницу по пикселям как наложилось, а вот например когда мы в точки вписываем линию мы можем 1 раз посчитать МНК, потом отбросить точки которые плохо вписались и 2 раз посчитать МНК.

или же они имеют ввиду, что у нас есть функция минимизации Fmin= Sum(w(i)*r(i)^2) и потом после глобальной регистрации смотриться значение Fmin и значение r^2 для какой либо пары?

[mrgloom 242]

вообщем вопрос остался с тем как быть с выбросами.

Допустим у меня есть переопределённая разреженная система линейных уравнений.

m уравнений и $n$ неизвестных (m>n)

k уравнений из этой системы мусор\выбросы.

можно было бы взять из m все комбинации размера n и потом взять лучший вариант, но это как то не оптимально, возможно есть вариант лучше?

например LMEDS, но я не уверен подходит ли это тут?

http://graphics.stanford.edu/~jplewis/lscourse/

нашел еще iterative reweighred least squares,LMeds,M-estimators.

[Smorodov 579]

Похоже на задачу, решаемую при помощи RANSAC.

[mrgloom 242]

можно было бы взять из m все комбинации размера n и потом взять лучший вариант, но это как то не оптимально, возможно есть вариант лучше?

ну так по идее это и будет ранзак, только если перебрать не все, а сколько то итераций.

но хотелось бы точное решение и за приемлемое время.

кстати опять же непонятно что брать за функцию ошибки, можно сумму разницы пикселей по всей панораме, а можно

Fmin= Sum((b-b_estimated)^2) (т.е. для всех уравнений подставляем наши полученные после решения системы значения и вычисляем правую часть и смотрим разницу того что должно быть и того что получилось)

[Smorodov 579]

Попиксельно, мне думается не самое лучшее решение.

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

использовал сильные градиенты для сопоставления (особенно их направления на границе пересечения изображений).

[mrgloom 242]

кстати еще о решении через псевдообратную матрицу

http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0

это как то связано с SVD?

и еще там про линейную независимость строк -> одно решение, в противном случае множество решений или не решается?

вот даже понятно откуда псевдообратная матрица появилась

http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2

только всё равно непонятно откуда первое уравнение, видимо из условия

Таким образом, вектор \mathbf{p} должен быть проекцией \mathbf{y} на пространство столбцов и вектор невязки A\mathbf{w}-\mathbf{y} должен быть ортогонален этому пространству. Ортогональность состоит в том, что каждый вектор в пространстве столбцов есть линейная комбинация столбцов с некоторыми коэффициентами v_1,...,v_N, то есть это вектор A\mathbf{v}. Для всех v в пространстве A\mathbf{v}, эти векторы должны быть перпендикулярны невязке A{\mathbf{w}}-\mathbf{y}:

SVD просто дополнительно помогает

При обращении матрицы (A^TA)^{-1} предполагается, что эта матрица невырождена и не плохо обусловлена. О том, как работать с плохо обусловленными матрицами см. в статье Сингулярное разложение.

[Smorodov 579]

Линейные уравнения получаются путем приравнивания производной ошибки (суммы квадратов разностей) к нулю.

Решение через SVD позволяет решать переопределенные системы.

При недостатке уравнений, решений бесконечное множество (решения лежат в "нуль пространстве").

[mrgloom 242]

Решение через SVD позволяет решать переопределенные системы.

вопрос был не в этом.

а в том что можно посчитать псевдообратную матрицу и без SVD и получить ответ, только видимо это всегда сработает ибо

При обращении матрицы (A^TA)^{-1} предполагается, что эта матрица невырождена и не плохо обусловлена.

при решении переопределенной системы вообще не может быть случая когда нет решения?

http://stat.ethz.ch/education/semesters/ss2010/regression/RobustRegression-notes.pdf

кстати получается что МНК это всего лишь подвид регрессии.

[Smorodov 579]

МНК выдает решение/приближение, если есть достаточное/избыточное количество условий (при переопределенной системе они есть всегда), то и решение будет.

кстати получается что МНК это всего лишь подвид регрессии.

МНК - это не подвид регрессии, это наиболее часто применяющийся метод восстановления линейной регрессии.

[mrgloom 242]

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

но вообще это похоже всё таки сводиться к нахождению остовов (есть даже алгоритм который находит random spanning tree).

но когда мы находим остовы мы отказываемся от дополнительных связей, по идее можно даже находить и подграфы графа, которые содержат все вершины, но это еще дольше.

а lmeds я так до конца и не понял, там как и в ранзаке производиться какое то сэмплирование?

http://research.microsoft.com/en-us/um/people/zhang/INRIA/Publis/Tutorial-Estim/node25.html

[Smorodov 579]

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

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

[mrgloom 242]

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

вообще не понял

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

так я вот не понял из-за чего нужно это сэмплирование?

LMedS problem cannot be reduced to a weighted least-squares problem. It is probably impossible to write down a straightforward formula for the LMedS estimator. It must be solved by a search in the space of possible estimates generated from the data. Since this space is too large, only a randomly chosen subset of data can be analyzed.

дело в том что в обычном least squares мы можем в явном виде написать формулу для X через псевдообратную матрицу, а тут нет?

[mrgloom 242]

http://research.microsoft.com/en-us/um/people/zhang/INRIA/Publis/Tutorial-Estim/node25.html

прочитал еще раз

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

на основании которого считаются коэффициенты для взвешенного МНК

собсвенно смысл всего этого всего лишь убрать некоторые аутлайнеры (в нашем случае связи)

еще там описан метод для сэмплирования точек regularly random selection method, видимо чтобы не брать точки близко, что бы заведомо не получать нестабильного решения.

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

[mrgloom 242]

вообщем в итоге я тут вижу несколько методов.

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

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

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

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

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

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