Допустим хотим объединить картинки в панораму.
Считаем корреляцию попарно для каждой пары картинок.
получаем матрицу NxN.
Теперь должны расставить их.

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

как можно решить? 

Приведите пример такой матрицы - как она должна выглядеть?

в общем виде
a11 a12 a13
a21 a22 a23
a31 a32 a33

по диагонали 0, т.к. само с собой мы не рассматриваем.
0   a12 a13
a21 0   a23
a31 a32 0

элементы через диагональ одинаковые, т.е.
0   a12 a13
a12 0   a23
a13 a23 0


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

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


допустим было 8 изображений, у меня получились пары
0 1
1 2
2 1  - т.е. тут разрыв образовалась 1 группа и 2 но на самом деле это была 1 группа изображений. 
3 4
4 5
5 4
6 5
7 6

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

Это сообщение отредактировал(а) mrgloom - 31.1.2013, 16:40

Если алгоритм выделения пар ошибся - то никакой дальнейший алгоритм тебе ничего не даст.
Ну получил ты 2 несвязных блока - какой ставить слева, какой справа? Получил три - какой слева, какой в середину, какой справа?

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

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

Это сообщение отредактировал(а) Akina - 31.1.2013, 17:19

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

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

Это сообщение отредактировал(а) mrgloom - 1.2.2013, 09:56

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

Откажись от этого условия. Остальное - оставь.

так это я пробовал в самом начале ,т.е. находить максимум по строке т.е. лучшую пару.
и получались 2 разрывные группы, типа 0-1-2 и 3-4-5-6-7, а должна быть одна группа.
0 1
1 2
2 1  - т.е. обрыв
3 4
4 5
5 4
6 5
7 6



еще некоторые соображения

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

рассмотрим набор из 3 изображений, матрица будет.
  _1___2___3__  
1| 0   a12 a13
2| a12 0   a23
3| a13 a23 0

Если мы для каждого элемента выбираем по 1 паре, то получается N*(N-1) комбинаций.
1 - 2 | 1 - 3
2 - 1 | 2 - 3
3 - 1 | 3 - 2
Но на самом деле у 1 изображения может быть несколько пар, на самом деле до N-1, и мы должны составить какую то функцию которую должны максимизировать основываясь на значении пиков и  взаимном расположении изображений.

примеры 
http://dl.dropbox.com/u/8841028/panorama/%...D1%8B%D0%B9.PNG



Это сообщение отредактировал(а) mrgloom - 1.2.2013, 12:16

Тебя обматерить? ты читать будешь, что тебе пишут?

Не можешь понять по описанию - сделай в Экселе таблицу 8*8, в каждой из 64 клеток корреляция соотв. пары (номер строки и номер столбца), диагональ само собой ноль, остальное - чем больше значение, тем больше вероятность, что это пара. Я тебе на неё покажу порядок рассуждения.

И ещё одно - при расчёте "корреляции" ты просто обязан получать не только степень соответствия, но и для каждого рисунка пары сведения, какая из сторон рисунка дала эту корреляцию. Ведь для пары ты посчитал 2 коэффициента - совпадение, если к первому стыковать второй справа, и если стыковать слева. Какой из полученных коэффициентов ты даёшь? надо - оба, с указанием, какой из них какой.

Если алгоритм расчёта этого не даёт - изменяй. Он обязан.

Это сообщение отредактировал(а) Akina - 1.2.2013, 13:00

ну наверно я вас не понял.

по порядку:


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


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


про порог и так понятно, но от ошибочных пар это не спасает, так что всё равно надо фильтровать геометрически (что не всегда возможно- случай когда эл-т крайний)
Если я правильно понял про "объединять по одной связи, каждый раз выбирая максимальную из оставшихся."
т.е. находим максимальную пару и присоединяем.
потом мы должны взять еще 1 максимальную пару (из всех или которая присоединяется к тем которые уже соединили?)


у меня находит смещение одного фото относительно другого и никакого лево-право-верх-низ, просто вектор смещения.


вот пример, я брал критерий такой: берем последовательно пары с максимальной корреляцией и чтобы хотя бы 1 элемент присутствовал в том, что уже объединили (если этого не делать, то можем получить 2 несвязанных между собой графа и надо думать как их объединять).
Но как видно на картинке алгоритм работает неправильно, либо надо потребовать чтобы у каждой пары было только по 1 связи, либо чтобы покрывались все фото и как то убивать "лишние" связи.
http://dl.dropbox.com/u/8841028/panorama/1.PNG
на картинке номера фото ничего не значат, просто порядковые номера, внизу картинка как это примерно должно было выглядеть на самом деле.В табличке первые 2 цифры пары, вторые две смещение.
http://dl.dropbox.com/u/8841028/panorama/%...D1%8B%D0%B9.PNG
тут пример того как мы используя доп связи фильтруем ложную пару, 
т.е. на самом деле должна была быть пара 3-4, а у нас 2-4, но мы имеет доп связь 1-8 и так можем восстановить картину.  

Это сообщение отредактировал(а) mrgloom - 6.2.2013, 09:11

Меня - один!!!
Да, вероятно. Попробую ещё раз.

Итак, у нас есть 8 (как в примере выше) элементов. Сравнивая их попарно, получаем некий коэффициент соответствия для каждой пары. Всего 28. Из всех 28 выбираем максимальный. Совмещаем соотв. пару. В результате мы получаем НОВЫЙ НАБОР элементов - в котором 6 элементов из старого набора, и один новый, который является совмещением пары, показавшей максимальное подобие. Для 6 старых мы уже имеем коэффициенты (15 штук). Получаем (считаем) теперь коэфф. подобия нового (двойного) элемента с каждым из 6 старых элементов, и в результате имеем набор из 7 элементов, и к нему 21 коэффициент. Снова выбираем один максимальный из этих 21, и совмещаем соотв. пару, получая уже набор из 6 элементов. И так далее - до тех пор, пока в итоге не останется набор из 2 элементов, которые по определению обязаны совмещаться (впрочем, ради единого образия неплохо бы посчитать коэфф. их соответствия, хотя бы для очистки совести).

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

понял.

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



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


http://dl.dropbox.com/u/8841028/panorama/3.PNG
вот на примере 4-х изображений мы получаем полный граф корреляции между ними и возможно сколько то различных взаиморасположений.

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


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

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

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


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



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

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

Но есть примеры когда что то можно сделать проанализировав глобальную структуру, как тут
http://dl.dropbox.com/u/8841028/panorama/%...D1%8B%D0%B9.PNG

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


Именно.
Твоё предложение - это фактически на каждом шаге выбирать оптимальный шаг из полученных изначально и к текущему моменту ещё невыбранных и не отсеившихся.
Моё предложение - на каждом шаге выбирать оптимальный шаг из всех возможных на данном шаге. Т.е. учитывать уже выбранные шаги и результат от того, что они выбраны, влияние их на состояние системы.
Думаю, мой вариант будет более устойчив.



А тут никакой алгоритм тебе ничего не даст. С точки зрения твоего принципа обработки какой-нить вариант -к-к-к\с-с\к-к-к-к более правилен, так как даёт наибольшую корреляцию и минимальную невязку, и твой, и мой алгоритмы при правильном построении ОБЯЗАНЫ будут дать именно такой результат, разорвав картину на две части по той связи, где корреляция наименьшая. Это - правильно. Потому что ты анализируешь корреляцию без учёта глобальной картины. И предлагаемый тобой подход в принципе не может этого сделать. Мой - теоретически может, если такая возможность будет заложена в алгоритм расчёта корреляции двух (мульти)блоков.

ну и как вы себе это представляете? выводим результат и кнопку попробовать еще раз?)


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




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


непонятно что это значит.




еще я нашел как эту задачу решают, когда используются особые точки.
называется Bundle adjustment раздел Global alignment.
http://szeliski.org/Book/drafts/SzeliskiBo...00903_draft.pdf
но пока не придумал как это всё перенести на текущую задачу.

Если не считать текста надписи - именно так. Возможно, плюс ещё средства, позволяющие показать те самые точки привязки.

вот тут нашел решение 
http://www.inf.ethz.ch/personal/chzach/pdf...10-preprint.pdf

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