по мотивам http://forum.vingrad.ru/forum/topic-361629/view-all.html
Итак на входе имеем N картинок, можем посчитать попарные соответствия и получить относительный сдвиг(dx,dy).

1.Вариант с решением линейной системы 
тут предлагают решить систему линейных уравнений
http://users.soe.ucsc.edu/~davis/panorama/...es/slide011.jpg
http://scien.stanford.edu/pages/labsite/20...t13/global.html  тут подробней, но непонятно как они получили систему уравнений, где матрицы как элементы, т.е. как её развернуть в нормальный вид http://scien.stanford.edu/pages/labsite/20.../Images/eq3.gif
кол-во переменных= 2*кол-во изображений
кол-во уравнений= 2*кол-во пар изображений
по идее можно составить разреженную переопределенную линейную систему уравнений
Только вот я не понимаю решиться ли она, если там есть выбросы?т.е. проблема в том, что мы туда запихиваем все связи, даже те которых не существует.
Вообщем нужен какой то метод решения, который умеет работать с выбросами.

Пример берем 3 изображения которые у нас соединены как полоска.
1-2 dx=100 dy=0
1-3 нет связи
2-3 dx=100 dy=0

код на opencv


2.Вариант с минимизацией целевой функции.
Есть еще вариант поставить задачу как предлагают тут (но тут для 1 картинки похоже).
http://cns.bu.edu/~brumberg/CS580/mosaic/MAIN/mosaic.html
кол-во переменных= 2*кол-во изображений
Только непонятно будет ли это работать, ибо целевая функция будет как я понимаю не непрерывная функция, т.к. внутри функции будет искаться кол-во пересечений изображений и суммироваться разность пикселей на границе и непонятно как выбирать начальное приближение и сойдется ли вообще.

Это сообщение отредактировал(а) mrgloom - 31.5.2013, 15:31

решил попробовать на простом примере, 4 картинки и только реально существующие связи, но что то не работает.
Связи 1-2,1-3,2-4,3-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



Добавлено через 3 минуты и 20 секунд
возможно из-за противоречия в цепочках 1-2-4 и 1-3-4

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


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

просто если её построчно разложить, то получиться
u1*I*P1=u1*I => P1=I
u2*I*P2=u2*A21*P1 =>P2=A21*P1 и т.д. т.е. коэффициенты ui сокращаются

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

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

Это сообщение отредактировал(а) mrgloom - 4.6.2013, 10:25

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


Допустим у меня есть переопределённая разреженная система линейных уравнений.
m уравнений и n неизвестных (m>n)
k уравнений из этой системы мусор\выбросы.

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

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

Система переопределена, это так. А она совместна? Каков ранг расширенной матрицы? Может не надо ничего выкидывать, оно само решится?
Например, начинаете решать методом Гаусса и отслеживаете момент возникновения противоречий.

Дело в том, что переопределенные системы могут быть двух типов - с единственным решением или без решений. Второе возникает когда есть противоречивые уравнения. Например х+у=5 и х+у=2. В этом случае нормального решения нет. 

В виду того что исходные данные с ошибками. И то что в процессе вычислений как правила есть ошибки. То ранг матрицы невозможно определить.

Все примеры в теме с целочисленными коеффициентами. Ицпользуйте целочисленный вариант Гаусса и накопления ошибок не будет. Так что в этой ситуации ранг всегда можно посчитать 

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

не считал, но я так понимаю что это всё к вопросу о совместности?

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

если рассмотреть пример

то получиться 
x1=0 y1=0
x2=522 y2=4
x3=0 y3=480
x4= 522 y4=490 или x4= 530 y4=484
это мы получаем 2 возможных решения?(или несовместную систему?), на графе это связи 1-2,1-3,2-4,3-4 ,т.е. пути 1-2-4 и 1-3-4 дают разный ответ.(но в этом примере все связи настоящие и применение тут МНК нам только размазывает ошибку усредняя)   

тут вот вроде как пишут о переопределенных системах которые несовместны
http://www.pereplet.ru/obrazovanie/stsoros/988.html

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


и я наконец то понял, что они делают тут http://scien.stanford.edu/pages/labsite/20...t13/global.html
сначала считаем все попарные связи между изображениями, потом по порогу обрубаем слабые связи, потом методом взвешенных наименьших квадратов считаем решение системы, потом смотрим ошибки для каждой связи и до тех пор пока сумма ошибок не упадёт до определенного порога мы итеративно обрубаем связь с самой большой ошибкой.
но в такой процедуре участвует аж 2 порога.