Помощь с численными методами (Bundle adjustment)

mrgloom_ · 20/04/12 114

Есть такая задача Bundle adjustment
http://en.wikipedia.org/wiki/Bundle_adjustment

вот тут подробнее и нагляднее
http://cns.bu.edu/~brumberg/CS580/mosaic/MAIN/mosaic.html

но всё равно непонятно.

если мы пытаемся найти
$\min(F(X))$ , где $X=(x_0,x_1,...,x_n)$ , $n= (N-1)2$ (т.к. одно изображение зафиксировали и у нас только сдвиг по x,y)
Допустим $F$ это у нас сумма разности пикселей по области пересечения между всеми изображениями панорамы.
дупустим начальное приближение $X_0$ все изображения в $(0,0)$ (возможно не лучшее решение)
непонятно как минимайзер будет сам передвигать нам все изображения?
непонятно при чем там система уравнений перехода координат? (если мы используем только $F$ )
и в минимайзер надо пихать только якобиан\хессиан? нельзя само значение функции?

AndrewSu · 09/02/13 31

mrgloom_ в сообщении #723593 писал(а):

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

Обычно предполагают, что изображение описывается функцией проецирования координат обьектов в 3D пространстве в 2D пространство изображения (видимо, вы это называете уравнением перехода координат?)
$\begin{pmatrix} x_p \\ y_p \end{pmatrix}= \begin{pmatrix} F_x(\Omega,X,Y,Z) \\ F_x(\Omega,X,Y,Z) \end{pmatrix}$ ,
где $\Omega$ - совокупность параметров камеры (положение и ориентация в пространстве, фокусное расстояние, дисторсия...) они и должны определяться в процессе минимизации. Изображение не двигается, изменяется положение камеры, снявшей его.
В случае со статьей http://cns.bu.edu/~brumberg/CS580/mosai ... osaic.html $\Omega$ - набор параметров $m_0...m_7$ .

mrgloom_ в сообщении #723593 писал(а):

и в минимайзер надо пихать только якобиан\хессиан? нельзя само значение функции?

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

mrgloom_ · 20/04/12 114

Цитата:

Обычно предполагают, что изображение описывается функцией проецирования координат обьектов в 3D пространстве в 2D пространство изображения (видимо, вы это называете уравнением перехода координат?)
$\begin{pmatrix} x_p \\ y_p \end{pmatrix}= \begin{pmatrix} F_x(\Omega,X,Y,Z) \\ F_x(\Omega,X,Y,Z) \end{pmatrix}$ ,
где $\Omega$ - совокупность параметров камеры (положение и ориентация в пространстве, фокусное расстояние, дисторсия...) они и должны определяться в процессе минимизации. Изображение не двигается, изменяется положение камеры, снявшей его.
В случае со статьей http://cns.bu.edu/~brumberg/CS580/mosai ... osaic.html $\Omega$ - набор параметров $m_0...m_7$ .

у меня простейший случай когда только сдвиг, т.е.
$x' = x + m_1$
$y' = y + m_2$
т.е. изображения просто двигаются по плоскости.

Цитата:

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

задачу о панораме? или задачу без якобиана?
как я писал выше

Цитата:

Допустим $F$ это у нас сумма разности пикселей по области пересечения между всеми изображениями панорамы.

допустим на текущем шаге мы знаем смещение всех изображений $m_1, m_2$ относительно первого зафиксированного изображения, можем посчитать пересечения и разницу пикселей на пересечении, а как посчитать этот якобиан?

AndrewSu · 09/02/13 31

mrgloom_ в сообщении #724161 писал(а):

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

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

mrgloom_ в сообщении #724161 писал(а):

задачу о панораме? или задачу без якобиана?

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

mrgloom_ в сообщении #724161 писал(а):

а как посчитать этот якобиан?

Ваш минимизируемый функционал должен выглядеть примерно так:
$F=(f_1(\Omega))^2 + (f_2(\Omega))^2 + ... + (f_n(\Omega))^2$
$\Omega = (m_1^1,m_2^1,m_1^2,m_2^2 ... m_1^n,m_2^n)$
где $m_1^n,m_2^n$ параметры сдвига изображения с номером $n$
Все это хозяйство распадается на систему уравнений:
$\begin{pmatrix} f_1(\Omega) = 0 \\ f_2(\Omega) = 0 \\ f_n(\Omega) = 0 \end{pmatrix}$
Далее дифференцируем каждое из уравнений $f_n(\Omega) = 0$ по каждому $m_i^n$ и получаем Якобиан.
Смотрите, здесь подробнее описано: Якобиан и Метод Левенберга-Марквардта

mrgloom_ · 20/04/12 114

Функция $f_i$ задаётся для пары?т.е. для всех возможных пар и получается кол-во $n=(k-1)+(k-2)+...+1$ , где $k$ это кол-во изображений в панораме.
Кол-во переменных $2(k-1)$ .

$F=(f_1(\Omega))^2 + (f_2(\Omega))^2 + ... + (f_n(\Omega))^2$
если у меня $f_i(\Omega)$ и так всегда положительная всё равно надо брать квадрат?

Непонятно как выразить эти условия $f_i(\Omega)=0$ , ибо функция, то будет задаваться "не просто какой то функцией", а последовательностью действий.

Сама $f_i$ функция выгляди так:
При текущих параметрах $\Omega$ найти пересечение $i$ -ой пары изображений и посчитать сумму модулей разностей для каждого пикселя области пересечения.
а если непонятно как задать функцию "в обычном виде", то непонятно как и посчитать якобиан.

http://cns.bu.edu/~brumberg/CS580/mosai ... osaic.html
может тут они решает задачу для 1 пары, а не для всей мозаики?
т.к. пишут

Цитата:

In this implmentation, for each pair of images (1 and 2), (2 and 3) the first image was treated as the base image and a transformation was calculated minimizing intensity error during registration of the second image. To determine the final transformation matrix for image 3 to the base image, the individually calculated transformation matrix (i.e. image 3 to 2) was multiplied by the previously calculated transformation (e.g. image 2 to 1).

опять же еще вопрос какое выбрать начальное приближение, может быть вообще быстрее решить задачу перебором имея матрицу корреляций?
тут пытался решить задачу путем нахождения минимального остова в графе, но это не даёт оптимальное решение.
Так же есть вариант использовать циклы в графе или делать полные перебор остовов, но это как то долго возможно может есть что то поумнее?
http://stackoverflow.com/questions/1652 ... d-panorama
http://stackoverflow.com/questions/1628 ... ationships

тут я пытался сделать регистрацию 2-х изображений на матлабе через FFT и оптимизацию параметров, но ничего не получилось, возможно неправильно использовал GlobalSearch.
topic63176.html

например для этого минимизатора http://www.chokkan.org/software/liblbfgs/ необходимо посчитать значение функции и градиент(хотя непонятно всё равно как его считать).

тут вроде понятней написано чем на википедии про матрицы Якоби и Гессе
http://www.machinelearning.ru/wiki/inde ... 1%81%D0%B5

mrgloom_ · 20/04/12 114

хотя возможно для вычисления градиента(якобиана), я должен просто посчитать частные производные,
как тут
http://ru.wikipedia.org/wiki/%D0%A7%D0% ... 0%B0%D1%8F
только как выбрать дельта $x$ ? просто маленькое типа 0.001 ?

http://www.machinelearning.ru/wiki/inde ... 1%81%D0%B5
тут это называется метод конечных разностей

так в чем проблема подавать в функцию минимизации только F и epsilon(т.е. почему они хотят чтобы пользователь сверху их функции считал градиент)?

AndrewSu · 09/02/13 31

mrgloom_ в сообщении #724586 писал(а):

Функция $f_i$ задаётся для пары?

Это конечно зависит от реализации. В моем случае $f_i$ описывала ошибку для каждого изображения.

mrgloom_ в сообщении #724586 писал(а):

$F=(f_1(\Omega))^2 + (f_2(\Omega))^2 + ... + (f_n(\Omega))^2$
если у меня $f_i(\Omega)$ и так всегда положительная всё равно надо брать квадрат?

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

mrgloom_ в сообщении #724586 писал(а):

http://cns.bu.edu/~brumberg/CS580/mosai ... osaic.html
может тут они решает задачу для 1 пары, а не для всей мозаики?

У них действительно выкладки сделаны для одной пары изображений. Для мозаики следует просуммировать функции ошибок по всем парам перекрывающихся изображений и минимизировать общую функции.

mrgloom_ в сообщении #724586 писал(а):

опять же еще вопрос какое выбрать начальное приближение

Начальное приближение может быть получено либо из знания процесса съемки, либо методами поиска соответствий между изображениями. В приведенной вами статье CS580 начальное приближение вообще задаётся вручную:

Цитата:

Request image tie points from user: user presses keys 1-6 (according to tie point) and left clicks desired location, and calculate affine transformation parameters from second image to base (first) image

Если в вашей задаче имеется только сдвиг между изображениями, то начальное приближение проще всего искать корреляционными методами. Более того, если количество изображение невелико (<10), то это начальное приближение сойдет и за окончательный ответ. Если между изображениями более сложная трансформация то следует применять SIFT или SURF методы для поиска соответствий (вроде они упоминались в ваших постах). Многие для этого изпользуют библиотеку OpenCV. Более того в данной библиотеке содержится готовый инструментарий для склейки панорам class Stitcher

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

mrgloom_ · 20/04/12 114

Цитата:

В моем случае $f_i$ описывала ошибку для каждого изображения.

что значит "ошибку для каждого изображения" ?

Цитата:

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

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

Цитата:

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

ну так я так и сделал, нашел корреляции между всеми возможными парами, а проблема, то как раз в том как их расставить
вот тут я эту проблему описал подробнее
http://stackoverflow.com/questions/1652 ... d-panorama
т.е. получается начальное приближение будет так же трудно выбрать как и сложить вообще панораму похоже.

Цитата:

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

Например биологические снимки с микроскопа типа такого
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3312714/

использование SIFT кстати ничего не меняет, задача остаётся та же, мы всё равно имеет пары все со всеми и надо потом как то это расставить, только как меру "удачности совмещения" вместо значения корреляции мы имеем кол-во совпавших точек (это и называется bundle adjustment?)

AndrewSu · 09/02/13 31