Создание панорамы, Global optimization (Bundle adjustment)

[rte123 0]

Добрый вечер!

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

Объясните пожалуйста или поделитесь материалом, по возможности, где можно прочесть или, лучше, посмотреть на пример. Что то подобное есть у Сжельского, Зиссермана и Хартли, но это все профессорские выкладки. Интересует сама реализация кода

[mrgloom 242]

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

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

(Допустим вы запустили алгоритм(sift и т.д.) и нашли пары, отфильтровали как то ложные пары)

Пример имеем пару изображений 1-2, 2-3 тогда у нас есть соотношения.

x2-x1=a1

y2-y1=b1

x3-x2=a2

y3-y2=b2

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

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

(-1)x1+(1)x2+(0)x3=a1

(-1)y1+(1)y2+(0)y3=b1

(0)x1+(-1)x2+(1)x3=a2

(0)y1+(-1)y2+(1)y3=b2

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

аля

http://www.mathworks.com/help/optim/ug/fsolve.html

вот тут мои поиски

http://www.compvision.ru/forum/index.php?showtopic=1162

p.s. в opencv таки в модуле stittching есть строчка findMaxSpanningTree и еще используется CvLevMarq solver (Levenberg–Marquardt algorithm is used to solve non-linear least squares problems.)

https://github.com/Itseez/opencv/blob/master/modules/stitching/src/motion_estimators.cpp

[rte123 0]

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

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

(Допустим вы запустили алгоритм(sift и т.д.) и нашли пары, отфильтровали как то ложные пары)

Пример имеем пару изображений 1-2, 2-3 тогда у нас есть соотношения.

x2-x1=a1

y2-y1=b1

x3-x2=a2

y3-y2=b2

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

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

(-1)x1+(1)x2+(0)x3=a1

(-1)y1+(1)y2+(0)y3=b1

(0)x1+(-1)x2+(1)x3=a2

(0)y1+(-1)y2+(1)y3=b2

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

аля

http://www.mathworks.com/help/optim/ug/fsolve.html

вот тут мои поиски

http://www.compvision.ru/forum/index.php?showtopic=1162

p.s. в opencv таки в модуле stittching есть строчка findMaxSpanningTree и еще используется CvLevMarq solver (Levenberg–Marquardt algorithm is used to solve non-linear least squares problems.)

https://github.com/Itseez/opencv/blob/master/modules/stitching/src/motion_estimators.cpp

дело еще и в том, что Bundle adjustment, в случае панорам, изменяет геометрию снимков как показано тут

Может быыть Вам известно как и зачем?

(После BA даже приходится пользоваться выравниванием/вытягиванием для коррекции внесенных геометрич искажений)

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

[BeS 53]

дело еще и в том, что Bundle adjustment, в случае панорам, изменяет геометрию снимков как показано тут

http://www.youtube.com/watch?v=x2VjOva4pFg.

Может быыть Вам известно как и зачем?

(После BA даже приходится пользоваться выравниванием/вытягиванием для коррекции внесенных геометрич искажений)

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

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

Алгоритм Левенберга-Марквардта - это один из способов решения задачи о наименьших квадратах - это и есть один из способов реализовать Bundle Adjustment по сути.

[mrgloom 242]

дело еще и в том, что Bundle adjustment, в случае панорам, изменяет геометрию снимков как показано тут

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

я честно говоря не осилил эти поворотные матрицы в 3D и все эти штуки с Multiple View Geometry.

но это как раз и используется в opencv

http://www-scf.usc.edu/~boqinggo/Stitching.htm

Сжельского

это Richard Szeliski?

Алгоритм Левенберга-Марквардта - это один из способов решения задачи о наименьших квадратах - это и есть один из способов реализовать Bundle Adjustment по сути.

ага.

еще можете загуглить sparse bundle adjustment (хотя оно вроде для SFM аля multiple view reconstruction)

а вообще всё делиться на 2 части: составление уравнений и выбор метода оптимизации для решения этих уравнений.

[rte123 0]

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

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

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

я честно говоря не осилил эти поворотные матрицы в 3D и все эти штуки с Multiple View Geometry.

но это как раз и используется в opencv

http://www-scf.usc.edu/~boqinggo/Stitching.htm

В том то все и дело, там написано про реконструкцию 3Д сцены, т.е. по схееме: много камер - один кадр

Я задаюсь другой проблемой - создание панорамы, тут все наобарот: одна камера - много кадров

это Richard Szeliski?

Он самый))

а вообще всё делиться на 2 части: составление уравнений и выбор метода оптимизации для решения этих уравнений.

Ну так то оно так) ВА в этом случае, как я понял, выступает в качестве постобработки, ну, или даже, в качестве осномного средства оптимизации

[mrgloom 242]

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

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

ну и что это за с# библиотека?

Richard Szeliski

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

вот его труд по панорамам, вроде бы есть еще и в составе книги(Computer Vision: Algorithms and Applications), но там тоже самое.

вам там нужно две главы Motion models и Global registration

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

Before we can register and align images, we need to establish the mathematical relationships that

map pixel coordinates from one image to another. A variety of such parametric motion models

are possible, from simple 2D transforms, to planar perspective models, 3D camera rotations, lens

distortions, and the mapping to non-planar (e.g., cylindrical) surfaces (Szeliski 1996).

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

In most applications, we are given more than a single pair of

images to register. The goal is then to find a globally consistent set of alignment parameters that

minimize the mis-registration between all pairs of images (Szeliski and Shum 1997, Shum and

Szeliski 2000, Sawhney and Kumar 1999, Coorg and Teller 2000). In order to do this, we need to

extend the pairwise matching criteria (44), (94), and (121) to a global energy function that involves

all of the per-image pose parameters (§5.1).

One way to register a large number of images is to add new images to the panorama one at a time,

aligning the most recent image with the previous ones already in the collection (Szeliski and Shum

1997), and discovering, if necessary, which images it overlaps (Sawhney and Kumar 1999). In

the case of 360◦ panoramas, accumulated error may lead to the presence of a gap (or excessive

overlap) between the two ends of the panorama, which can be fixed by stretching the alignment

of all the images using a process called gap closing (Szeliski and Shum 1997). However, a better

alternative is to simultaneously align all the images together using a least squares framework to

correctly distribute any mis-registration errors.

The process of simultaneously adjusting pose parameters for a large collection of overlapping

images is called bundle adjustment in the photogrammetry community (Triggs et al. 1999). In

computer vision, it was first applied to the general structure from motion problem (Szeliski and

Kang 1994) and then later specialized for panoramic image stitching (Shum and Szeliski 2000,

Sawhney and Kumar 1999, Coorg and Teller 2000).

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

[rte123 0]

ну и что это за с# библиотека?

sharpstitch называется)

[rte123 0]

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

Не, Сзелиски это звучит как ягоды какие-то, лучше Зеленски или Сжельски)

Вы не подскажете, может быть есть какой то способ посмотреть, что содержится внутри класса, вызываемого из openCv. Я просто новичок в программировании, и хочу знать как функционирует этот "черный ящик" Bundle Adjustment. Слышал про open source, но при всем уважении к разработчикам, не готов выкладывать тысячи долларов). Встречаются ли ресурсы, где есть подобная информация? Можете посоветовать какие-нибудь или сказать ключевые слова при поиске?

[Smorodov 579]

Дык в исходниках OpenCV: у меня лежит в папке opencv-master\modules\stitching\src\

Сами исходники качать здесь: https://github.com/Itseez/opencv

[rte123 0]

Дык в исходниках OpenCV: у меня лежит в папке opencv-master\modules\stitching\src\

Сами исходники качать здесь: https://github.com/Itseez/opencv

Ну это-то да, но там в Bundle Adjustment передают данные, а потом он выдает готовый результат. Мне бы хотелось узнать, каким образом он обрабатывает полученные данные, какой алгоритм действий скрыт за вызываемым методом

[rte123 0]

Скажите пожалуйста, это есть описание метода, который вызывается из openCV как BundleAdjusterRay, или я путаю?

void BundleAdjusterRay::calcJacobian(Mat &jac)

{

    jac.create(total_num_matches_ * 3, num_images_ * 4, CV_64F);


    double val;

    const double step = 1e-3;


    for (int i = 0; i < num_images_; ++i)

    {

        for (int j = 0; j < 4; ++j)

        {

            val = cam_params_.at<double>(i * 4 + j, 0);

            cam_params_.at<double>(i * 4 + j, 0) = val - step;

            calcError(err1_);

            cam_params_.at<double>(i * 4 + j, 0) = val + step;

            calcError(err2_);

            calcDeriv(err1_, err2_, 2 * step, jac.col(i * 4 + j));

            cam_params_.at<double>(i * 4 + j, 0) = val;

        }

    }

}

[Smorodov 579]

Насколько я понимаю, это вычисление Якобиана для функции оптимизации параметров.

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

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

Кстати поиск выдал мне несколько файлов с Bundle adjustment:

opencv-master\modules\contrib\include\opencv2\contrib\compat.hpp 

opencv-master\modules\legacy\src\levmarprojbandle.cpp 

opencv-master\modules\stitching\include\opencv2\stitching\detail\motion_estimators.hpp 

opencv-master\modules\stitching\src\motion_estimators.cpp [/code]


Может в них еще чего интересного есть.

[rte123 0]

вот его труд по панорамам, вроде бы есть еще и в составе книги(Computer Vision: Algorithms and Applications), но там тоже самое.

вам там нужно две главы Motion models и Global registration

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

Алгоритм Левенберга-Марквардта - это один из способов решения задачи о наименьших квадратах - это и есть один из способов реализовать Bundle Adjustment по сути.

Кстати поиск выдал мне несколько файлов с Bundle adjustment:

opencv-master\modules\contrib\include\opencv2\contrib\compat.hpp 

opencv-master\modules\legacy\src\levmarprojbandle.cpp 

opencv-master\modules\stitching\include\opencv2\stitching\detail\motion_estimators.hpp 

opencv-master\modules\stitching\src\motion_estimators.cpp 

Может в них еще чего интересного есть.

Спасибо за помощь и участие

[mrgloom 242]

заходим сюда https://github.com/Itseez/opencv и используем поиск, находим исходники всех ф-ий.

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

и да судя по этой презентации

3D rotation имеет всего 3 степени свободы, видимо имеется ввиду когда мы стоим на одной точке и снимаем панораму поворачиваясь.

там еще описано преимущество Rotational mosaics перед Plane perspective mosaics

[BeS 53]

заходим сюда https://github.com/Itseez/opencv и используем поиск, находим исходники всех ф-ий.

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

и да судя по этой презентации

3D rotation имеет всего 3 степени свободы, видимо имеется ввиду когда мы стоим на одной точке и снимаем панораму поворачиваясь.

там еще описано преимущество Rotational mosaics перед Plane perspective mosaics

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