2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Помощь с численными методами (Bundle adjustment)
Сообщение14.05.2013, 09:53 


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$)
и в минимайзер надо пихать только якобиан\хессиан? нельзя само значение функции?

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение14.05.2013, 18:52 


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 писал(а):
и в минимайзер надо пихать только якобиан\хессиан? нельзя само значение функции?

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

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение15.05.2013, 13:07 


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$ относительно первого зафиксированного изображения, можем посчитать пересечения и разницу пикселей на пересечении, а как посчитать этот якобиан?

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение15.05.2013, 22:18 


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$ и получаем Якобиан.
Смотрите, здесь подробнее описано: Якобиан и Метод Левенберга-Марквардта

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение16.05.2013, 13:57 


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

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение16.05.2013, 15:19 


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(т.е. почему они хотят чтобы пользователь сверху их функции считал градиент)?

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение16.05.2013, 21:35 


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

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

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение17.05.2013, 09:24 


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?)

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение20.05.2013, 21:02 


09/02/13
31
mrgloom_ в сообщении #724961 писал(а):
что значит "ошибку для каждого изображения" ?

Имеется в виду ошибка проецирования общих точек.
mrgloom_ в сообщении #724961 писал(а):
это я понял, вопрос можно ли использовать не квадрат, если функция всегда положительна?

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

Здесь непонятно, что вы имеете в виду. Что значит "корреляцию между всеми возможными парами"?
Вам надо искать максимум корреляции между кусочком одного тайла (это Template image), на втором тайле (Source image).
Я уже приводил ссылочку на реализацию этого механизма вOpenCV. Положение максимума корреляции и определит сдвиг между тайлами. Если тайлы не пересекаются, то значение в максимуме будет низкое, а профиль функции корреляции в окрестности максимума будет пологим. По этим критериям можно отсечь "ложные" совпадения.
mrgloom_ в сообщении #724961 писал(а):
Например биологические снимки с микроскопа типа такого
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3312714/

К сожалению, там нет снимков, либо они очень малы.

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

В плоскости XY у них движется головка микроскопа, да и то с небольшим сдвигом по Z в процессе фокусировки.
Связь между координатами кадров (тайлами) описывается другими соотношениями.
Если у вас такой же принцип получения изображений, то вам следует обратить внимание на случай одного-двух изображений Single View and Two-View Geometry Andrew Zisserman, и на книгу, на которую ссылаются в приведенной вами статье "Hartley R, Zisserman A. Cambridge: Cambridge University Press; 2003. Multiple View Geometry in Computer Vision" - весьма полезная книга по вашей теме.

mrgloom_ в сообщении #724961 писал(а):
использование SIFT кстати ничего не меняет, задача остаётся та же, мы всё равно имеет пары все со всеми

На моей практике, при применении SIFT и иже с ним, на снимках, не имеющих реального перекрытия, существенно меньше соответствий, нежели на снимках с реальным перекрытием, и расположенны они хаотично. Такие пары легко отсекаются алгоритмами вроде RANSAC.
В работоспособности SIFT'а не следует сумлеваться - попробуйте. Благо реализаций полно. На одну из нах я уже давал ссылку.
Попробуйте скормить ваши снимки готовым программам вроде ICE или Hugin.

mrgloom_ в сообщении #724961 писал(а):
(это и называется bundle adjustment?)

Не совсем.
"bundle adjustment" на русский переводится как "уравнивание связок" - один из методов уравнивания блока изображений.

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение21.05.2013, 10:01 


20/04/12
114
Цитата:
Имеется в виду ошибка проецирования общих точек.

всё равно непонятно. Допустим $k$ изображений имеют $m$ общих точек(SIFT), дальше?
Цитата:
функционал, состоящий из суммы квадратов, легко распадается на систему уравнений, что приводит к более простому решению.

всмысле можем разбить на систему уравнений где нужно найти минимум каждого члена? (хотя вроде это не тоже самое)
Цитата:
Здесь непонятно, что вы имеете в виду. Что значит "корреляцию между всеми возможными парами"?
Вам надо искать максимум корреляции между кусочком одного тайла (это Template image), на втором тайле (Source image).
Я уже приводил ссылочку на реализацию этого механизма вOpenCV. Положение максимума корреляции и определит сдвиг между тайлами. Если тайлы не пересекаются, то значение в максимуме будет низкое, а профиль функции корреляции в окрестности максимума будет пологим. По этим критериям можно отсечь "ложные" совпадения.

я беру 1 изображение и смотрю его корреляцию(в opencv https://code.ros.org/trac/opencv/browser/trunk/opencv/samples/cpp/phase_corr.cpp?rev=6646) со всеми остальными, так получаю все пары отношения(имею значение пика корреляции + сдвиг), как критерий силы связи использую значение пика корреляции.(в случая использования SIFT)
SIFT удобнее тем, что не надо контролировать область пересечения(всмысле если она маленькая), но основная проблема возникает тогда когда есть дисторсии(типа бочка) на изображениях и тут даже RANSAC не поможет, либо надо эти искажения встраивать в модель которую RANSAC пытается вписать.
Если резать изображение на тайлы, то время выполнения будет больше(если делать через FFT) и это получится что то типа самого простого оптического потока, но к деформациям будет зато больше будет независимость.

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

Еще про RANSAC в opencv, во-первых он не учитывает дисторсии, надо как то закладывать их самому в модель, потом надо еще изменять как то код, чтобы ограничить матрицу гомографии только до сдвига, т.е.
$\begin{pmatrix}1 & 0 & dx \\0 & 1 & dy \\0 & 0 & 1\end{pmatrix}$

ICE не сшивает нормально мои снимки, с HUGIN не разобрался, т.к. там надо вводить FOV и focal length или что то такое.Еще пробовал autopano, но тоже никакой магии без ручного вмешательства.

Цитата:
"bundle adjustment" на русский переводится как "уравнивание связок" - один из методов уравнивания блока изображений.

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

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

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение21.05.2013, 11:16 


20/04/12
114
попробовал еще раз ICE он пары похоже находит правильно, но мозаика получается вся искаженная в общем, даже при использовании
Цитата:
Planar Motion 1: This option computes the best overlap between the images, without peforming any skewing or perspective distortion (allowing only translation, rotation, and scaling of the images). Planar Motion 1 is useful for stitching together multiple overlapping flat-bed scans of a large document.


хотя для большой панорамы(330 изображений) 34 изображения просто выкинуто + вся панорама перекошенная.

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение22.05.2013, 20:37 


09/02/13
31
mrgloom_ в сообщении #726534 писал(а):
всё равно непонятно.

mrgloom_ в сообщении #726534 писал(а):
ну а по сути там что делается? ищутся глобальные параметры камеры для каждого изображения в панораме?

Мне придется здесь книгу написать. Возьмите готовую. Параграф 88 смотрите и особенно 88.3
Назаров. Фотограмметрия.
mrgloom_ в сообщении #726534 писал(а):
Еще про RANSAC в opencv, во-первых он не учитывает дисторсии, надо как то закладывать их самому в модель, потом надо еще изменять как то код, чтобы ограничить матрицу гомографии только до сдвига, т.е.
$\begin{pmatrix}1 & 0 & dx \\0 & 1 & dy \\0 & 0 & 1\end{pmatrix}$

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



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

-- 22.05.2013, 20:40 --

mrgloom_ в сообщении #726557 писал(а):
хотя для большой панорамы(330 изображений) 34 изображения просто выкинуто + вся панорама перекошенная

Вы можете привести пример ваших снимков?
Несколько перекрывающихся, с которыми у вас проблема.

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение30.05.2013, 09:37 


20/04/12
114
Не удалось еще почитать книгу по фотограмметрии,которую вы порекомендовали, но я так предполагаю там 3D, а мне бы хотелось не усложнять и решить задачу в 2D.(У снимков с микроскопа только сдвиг и небольшой поворот может быть, а не как у снимков со спутника)

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

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

нашел еще такую программу http://www.xuvtools.org/download (я пытаюсь сделать примерно тоже самое)
попробовал XuvStitch-1.8.1-beta4-Win32 (можно 2D изображения загружать и собирать панораму)
Вообщем она довольно кривая и ошибается(хотя может надо настроить параметры), но интересно то, что там при расстановке на поле как будто перебирает комбинации и как раз это и интересно.(т.е. это и есть глобальная оптимизация о которой я говорил)

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение31.05.2013, 10:00 


20/04/12
114
Цитата:
In order to reduce accumulated registration errors, we apply global alignment (block adjustment) to the whole sequence of images, which results in an optimally registered image mosaic.

http://research.microsoft.com/apps/pubs ... x?id=75614
вроде тут 6 секция
http://research.microsoft.com/pubs/7561 ... IJCV00.pdf
но всё равно непонятно

-- 31.05.2013, 11:20 --

хотя может быть это применяется с той точки зрения, что если последовательно присоединять изображения, то будет накапливаться ошибка.
https://sites.google.com/site/armanelibol/research

 Профиль  
                  
 
 Re: Помощь с численными методами (Bundle adjustment)
Сообщение31.05.2013, 15:09 


20/04/12
114
тут понятней
http://scien.stanford.edu/pages/labsite ... index.html
http://scien.stanford.edu/pages/labsite ... aicing.pdf

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group