Реконструкция 3D-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки

Реконструкция 3Б-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки

Гошин Е.В., Фурсов В. А.

РЕКОНСТРУКЦИЯ 3Б-СЦЕН ПО РАЗНОРАКУРСНЫМ ИЗОБРАЖЕНИЯМ ПРИ НЕИЗВЕСТНЫХ ВНЕШНИХ ПАРАМЕТРАХ СЪЁМКИ

Е.В. Гошин1’2, В.А. Фурсов1 '2

1 Институт систем обработки изображений РАН, Самара, Россия,

2 Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательскийуниверстиет) (СГАУ), Самара, Россия

Аннотация

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

Ключевые слова: разноракурсные изображения, определение положения камеры, внутренние параметры камеры, сопоставление изображений, 3Б-реконструкция.

Цитирование: Гошин, Е.В. Реконструкция 3Б-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки / Е.В. Гошин, В.А. Фурсов // Компьютерная оптика. - 2015. - Т. 39, № 5. - С. 770-776. - Б01: 10.18287/0134-2452-2015-39-5-770-776.

Введение

1. Постановка задачи

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

Такой путь решения задачи был предложен в работе [2]. Однако вследствие того, что процедуры восстановления трёхмерных моделей крайне чувствительны к неизбежным погрешностям определения параметров фундаментальной матрицы, технология в целом часто оказывается неработоспособной. В работах [3, 4] решается задача определения внешних параметров камер с использованием уравнений Круппа. Наибольшее число известных работ, посвящённых этой проблеме, направлено на исследование различных способов калибровки. Наиболее известные в области калибровки работы [5, 6] решают задачу определения как внешних, так и внутренних параметров камеры, в том числе параметры дисторсии. Однако калибровка камеры проводится с использованием плоского шаблона (например, шахматной доски), что, как правило, неосуществимо в реальных условиях съёмки.

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

Для восстановления 3Б-сцены по разноракурсным изображениям будем использовать модель камеры-обскуры [7]. Предполагается, что разноракурсные изображения получены путём перемещения в пространстве одной камеры с известными внутренними параметрами, заданными матрицей:

f 0 U0

K =

0 f v0 0 0 1

где f - фокусное расстояние камеры, а (u0, v0), - координаты главной точки камеры в системе координат, связанной с камерой.

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

m =

( u ' ~ K (R t) M = K ( r 41 Г12 r13 *1 's ( x 1 Y

v Г21 Г22 Г23 *2 Z

V 1 J v Г31 Г32 r33 *3 J V 1 J

,

где u, v - однородные координаты точек на изображении вида, X, Y, Z - глобальные координаты точки M, а (R | t) - объединённая матрица поворота-сдвига, называемая также матрицей внешних параметров.

С учётом связи пиксельных и однородных координат точек:

m

соотношение (2) можно представить в виде

m

x

У

11J

( r 11 r12 r13

r21 r22 r23

V r31 r32 r33

*2 *3 J

( X 1

Y

Z

770

Компьютерная оптика, 2015, том 39, №5

Реконструкция 3Б-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки

Гошин Е.В., Фурсов В.А.

Далее под координатами точки m всюду подразумеваются координаты m(x,y), удовлетворяющие (4).

С использованием соотношения (4) строится процедура вычисления 3Б-координат сцены. В частности, записав с использованием неизвестных множителей g и g' соотношения вида (4) для соответствующих точек m(x,y) и m(x',y') [8] в виде равенств:

x

У

1

/'

X

/

У

1

R

g

X" " t1" Л

Y - t2

Z Lt3 _ У

-R'

g

Гг xi

Z

VL -1 L 3 _У

1

1

Y

t

2

и приравняв фигурирующие в (5), (6) векторы координат [X, Y, Z]T, получаем:

x f x " t1 -11 ’'

gR-1 У 7 p* bo 1 r У = c - t2 - t2 '

1 1 Lt3 - t3'_

Соотношение (7) представляет собой систему из трёх уравнений относительно двух неизвестных - g и g'. Посредством подстановки найденных из этой системы указанных множителей в соотношение (5) и/или (6) формируется вектор координат трёхмерной точки [X, Y, Z]T.

Из соотношений (3) - (7) видно, что для реконструкции 3Б-сцены необходимо знать параметры матрицы поворота-сдвига (R | t). Проблема состоит в том, что часто эти параметры оказываются неизвестными и вначале требуется определить их по заданным на двух видах координатам N пар соответствующих точек m(x,у) и m(x',y1). Решению этой задачи и посвящена настоящая статья.

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

2. Формулировка задачи оптимизации

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

QX = ZrX+tx Qy = zr + ty > Qy = z r + tz ^

где

rx = ri m i = riix i + ri2 y, +

r = r2 mi = r2ixi + r22y, + Г23 , *

Г = Г3 mi = Г31 x< + Г32уi + Г33

Г1 =[^^n, ^ Г13 ] а Г2 =[r21, Г22 , Г23 ] * r3 = [r31, r32, r33 ]

Зададим критерий оптимальности проективного преобразования в виде суммы квадратов разностей координат соответствующих точек на изображениях видов. С учётом обозначений (8), (9), (10) этот критерий представляется в виде:

r,t, z ) = £

i=1

где r = [r1, r2, r3]T - 9*1-вектор параметров поворота камеры, составленный из векторов-строк (10) матрицы поворота R, а z - вектор, компонентами которого являются глобальные координаты Zi, i =1, N точек сцены. Заметим, что для векторов-строк матрицы поворота r1, r2, r3 должны выполняться требования ортонормальности.

Поскольку глобальные координаты Z, i = 1, N, также являются неизвестными, в результате решения должны быть оценены N + 12 неизвестных параметров - компонент вектора Y = [r , t , Z ] , являющегося прямой суммой векторов r, t, z. С учётом сказанного задача формулируется следующим образом. Найти

(xQ - Qx )2 +(yQ - Qy )2

Y*: Q

при условии

Ы=INI=hll=1,

(rl, r2 ) = (rl, r3 ) = ( r2 , r3 ) =0,

r1 X r2 = rз, r2 X r3 = rl, r3 X r1 = r2 ,

где W - область допустимых значений параметров сдвига, поворота и координат Zi, i =1, N .

Поставленную задачу можно переформулировать как задачу безусловной оптимизации, если вместо вектора параметров r = [r1, r2, r3]T оценивать вектор параметров, составленный из углов поворота вокруг осей X, Y, Z . При этом выполнение ограничений (5) обеспечивается тем, что матрица R формируется в виде

R = RX Ry Rz ,

где

Г1 о о ^

R x

0 cos (a) ± sin (a) ,

v 0 + sin (a) cos (a) ,

Компьютерная оптика, 2015, том 39, №5

771

Реконструкция 3Б-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки

Е.В. Гошин, В. А. Фурсов

^ cos(b) 0 ± sin (b)Л

Ry = 0 1 0

ч+sin (b) 0 Cos(b) у

^ cos (g) ± sin (g) 0''

R z = + sin (g) cos ( g) 0

l 0 0 1 у

Здесь знак перед синусом указывает направление поворота.

Выполнив в векторе r = [rb r2, r3]T замены, соответствующие представлению (14):

r11 = Cos b Cos g, r12 = Cos b Sin g,

r13 = Sin b,

r21 =- Cos a Sin g- Sin a Sin b Cos g, r22 = Cos a Cos g-Sin a Sin b Sin g, r23 = Sin a Cos b,

r31 =-Sin a Sin g-Cos a Sin b Cos g, r32 = - Sin a Cos g- Cos a Sin b Sin g, r33 = Cos a Cos b,

задачу (12) можно представить в следующем виде. Найти

Y': s

где j = [a, b, g], а t и Z те же, что и выше. Подчеркнём, что в данном случае отсутствуют ограничения на искомые параметры.

3. Построение вычислительной процедуры

Сформулированная задача является многомерной и в общем случае многоэкстремальной. Несмотря на устранение ограничений и снижение размерности, она остаётся достаточно громоздкой в вычислительном отношении. Поэтому для её решения воспользуемся идеей блочной многошаговой схемы оптимизации [9], [10], [11].

Представим вектор Y в виде

Y = [У ,TT J ,

где T = [tT, ZT]T - (N+ 3)*1-вектор, являющийся прямой суммой векторов t и Z. Теперь задача определения минимума в правой части (15) может быть представлена в виде [11]:

min Q (ф,Т) = min min Q (ф,Т),

9,TeQ^Y™ ' TeQ^ '

где Wj, WT - подобласти допустимых значений, являющиеся проекциями исходной области Q на подпространства, соответствующие макропеременным j, T соответственно.

Применяя к макропеременным j, Т схему многошаговой оптимизации [10], можно записать алгоритм определения значений j, T, доставляющих минимум критерию (15) на k-м шаге, в виде следующей после-

довательности вложенных оптимизационных задач меньшей размерности:

Ф: Q

mn Q К, Т У))

ф eQ9 4 '

где

ГУ): QУ, TУ )) = minQУ, Т).

На первом шаге вектор j0 должен быть каким-либо образом задан.

Процедура останавливается, если

где

A9k = 9k - 9k-1, Atk =tk - tk-1, AZk = Zk - Zk-1

и

где

AQ (Yk ) = Q (Yk)-Q (Yk-1), а e<p, et, eZ, £q - заданные положительные числа (пороговые значения). Полученное на k-м шаге значение критерия считается оптимальным:

Q (Yk) - Q (Y*),

а соответствующие значения jk, tk, Zk - решением задачи.

Для определения минимума в (18) решается система уравнений

xiQZ - QX = 0, i = 1, N

xiQZ - Qy = 0, i = 1, N

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

С использованием выражений (8), (9) система уравнений (21) приводится к виду:

Z, ( r11Xi + Г12 У, + Г13 )+ *x =

= X

Z, (Г21Х, + Г22У, + Г23 )+ *x ==

X

При заданных значениях координат N пар соответствующих точек m(x,y), m(x',y’) и параметров r = [r1, r2, r3]T, однозначно определяемых через значения углов jk, данная система включает 2N уравнений с N+3 неизвестными. Она может быть решена любым из методов решения нелинейных систем. В настоящей работе эта система решалась итеративно с начальным приближением

Z, = 0, i = 1N .

772

Компьютерная оптика, том 39, №5

Реконструкция 3Б-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки

Гошин Е.В., Фурсов В. А.

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

Шаг 1.

Задаётся начальный вектор j = {0 0 0}, для него вычисляются значения векторов t и Z.

Шаг 2.

Для заданного (небольшого) А и всех возможных новых значений фк\

К-1 ±А,р -Р gk-1 ],

К-р р-1 ±4 gk-i ],

К-р Pk-l, gk-i ±А]

вычисляются значения векторов t и Z и из указанных вариаций выбирается щ, которое минимизирует критерий Q(jk, Tk) - (15). Шаг 2 повторяется до момента, определённого правилом остановки.

Правило остановки: алгоритм завершает работу в случае, если выполняются правила остановки (19), (20) или для любого из новых значений 9k значение критерия превышает значения критерия для фг1. В этом, последнем, случае в качестве искомых параметров принимаются значения jk-i, Tk-i.

4. Пример реконструкции ЗБ-сцены

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

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

"960 0 960"

K = K 2 = 0 960 540

0 0 1

"1 0 0" Р II о

R = 0 1 0 Р = 0°

0 0 1 / II О

"0,99377 -0,0869 -0,06976" Р II 00

R 2 = 0,07664 0,9873 -0,1388 Р = 4°

0,0809 0,1326 0,9879 / II Ui

"0" "-0.8"

C = 0 , C2 = 0

0 0

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

поворота второй камеры и соответствующая им матрица поворота:

"0,9939 -0,0867 -0,0689" ' a = 7,964°Л

R2 = 0,0765 0,9874 -0,1382 P = 3,953°

0,0801 0,1321 0,9880 vg = 4,988° ,

а также относительный сдвиг:

2

-0.6902

-0,0503

-0,0595

Рис. 1. Исходные смоделированные стереоизображения

Как видно из приведённых результатов оценивания, ошибка в определении сдвига составила около 13 %, а ошибка по углу - менее 1,2 %.

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

Для иллюстрации предложенной информационной технологии ниже приводится также пример реконструкции трёхмерной сцены по тестовым стереоизображениям из базы данных «Tsukuba». Выбор связан с тем, что для этих изображений отсутствует информация о внешних параметрах камеры, при которых эти изображения получены. Исходные тестовые изображения приведены на рис. 3а, б.

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

Компьютерная оптика, 2015, том 39, №5

773

Реконструкция 3Б-сцен по разноракурсным изображениям при неизвестных внешних параметрах съёмки

Е.В. Гошин, В.А. Фурсов

Рис. 2. Восстановленная трёхмерная сцена

Рис. 4. Карта диспарантности Tsukuba

На рис. 4а приведена соответствующая приведённым стереоизображениям карта диспарантности, взятая из базы данных.

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

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

Заключение

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

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

Благодарности

Работа выполнена за счет гранта Российского научного фонда (проект № 14-31-00014).

Литература

1. Кудинов, И.А. Реализация алгоритма определения пространственных координат и угловой ориентации объекта по реперным точкам, использующего информацию от одной камеры / И.А. Кудинов, О.В. Павлов, И.С. Холопов // Компьютерная оптика. - 2015. - Т. 39, № 3. -

С. 413-419.

2. Hartley, R. Multiple view geometry in computer vision / R. Hartley, A. Zisserman. - Cambridge university press, 2003. - 655 c.

774

Компьютерная оптика, том 39, N°5

Решение задачи автокалибровки камеры с использованием метода согласованной идентификации

Е.В. Гошин, В.А. Фурсов

3. Sun, Q. Self-calibration of multi-camera networks without feature correspondence between different cameras / Q. Sun,

D. Xu // Optik-International Journal for Light and Electron Optics. - 2014. - Vol. 125, Issue 13. - P. 3331-3336.

4. Фурсов, В.А. Решение задачи автокалибровки камеры с использованием метода согласованной идентификации /

В.А. Фурсов, Е.В. Гошин // Компьютерная оптика. -2012. - Т. 36, № 4. - С. 605-610.

5. Tsai, R.Y. A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses / R.Y. Tsai // Robotics and Automation, IEEE Journal of. - 1987. - Vol. 3, Issue 4. -P. 323-344.

6. Zhang, Z. A flexible new technique for camera calibration / Z. Zhang // Pattern Analysis and Machine Intelligence, IEEE Transactions on. - 2000. - Vol. 22, Issue 11. -P. 1330-1334.

7. Форсайт, Д. Компьютерное зрение. Современный подход / Д. Форсайт, Ж. Понс. - М.: Издательский дом «Вильямс», 2004. - 928 с.

8. Грузман, И.С. Цифровая обработка изображений в информационных системах: учеб. пособие / И.С. Грузман, В.С. Киричук, В.П. Косых [и др.] - Новосибирск: Издательство НГТУ, 2002. - 352 c.

9. Гергель, В.П. Многомерная многоэкстремальная опти-

мизация на основе адаптивной многошаговой редукции размерности / В.П. Гергель, В.А. Гришагин,

A. В. Гергель // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2010. - № 1. - С. 163-170.

10. Strongin, R.G. Global Optimization with Non-Convex Constraints / R.G. Strongin, Y.D. Sergeyev. - Springer US, 2000. - 704 с.

11. Стронгин, Р.Г. Параллельные вычисления в задачах глобальной оптимизации / Р.Г. Стронгин, В.П. Гергель,

B. А. Гришагин, К.А. Баркалов. - М.: Издательство Московского университета, 2013. - 280 с.

References

[1] Kudinov IA, Pavlov OV, Kholopov IS. Implementation of an algorithm for determining the spatial coordinates and the angular orientation of an object based on reference marks, using information from a single camera. Computer Optics 2015; 39(3): 413-9.

[2] Hartley R. Multiple view geometry in computer vision. Cambridge university press; 2003.

[3] Sun Q, Xu D. Self-calibration of multi-camera networks without feature correspondence between different cameras. Optik-International Journal for Light and Electron Optics 2014; 125(13): 3331-6.

[4] Fursov VA, Goshin YeV. Information technology for digital terrain model reconstruction from stereo images [In Russian]. Computer Optics 2014; 38(2): 335-42. ISSN 0134-2452.

[5] Tsau RY. A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses. Robotics and Automation, IEEE Journal of 1987; 3(4): 323-44.

[6] Zhang Z. A flexible new technique for camera calibration. Pattern Analysis and Machine Intelligence, IEEE Transactions on 2000; 22(11): 1330-4.

[7] Forsyth D, Ponce J. Computer Vision: A Modern Approach. Prentice Hall; 2002.

[8] Gruzman IS et al. Digital image processing in information systems [In Russian]. Novosibirsk: “NGTU” Publisher; 2002.

[9] Gergel VP, Grishagin VA, Gergel AV. Multidimensional multiextreme optimization based on adaptive multistep dimensionality reduction. Vestnik Nizhegorodskogo uni-versiteta im NI Lobachevskogo 2010; 1: 163-70.

[10] Strongin RG, Sergeyev YD. Global Optimization with Non-Convex Constraints. - Springer US; 2000.

[11] Strongin RG, Gergel VP, Grishagin VA, Barkalov KA. Parallel methods of global optimization problems solving [In Russian]. - Moscow: Moscow State University Publisher; 2004.

3D SCENE RECONSTRUCTION FROM STEREO IMAGES WITH UNKNOWN EXTRINSIC PARAMETERS

Ye. V. Goshin1’2, V.A. Fursov1 '2,

1 Image Processing Systems Institute, Russian Academy of Sciences, Samara, Russia,

2 Samara State Aerospace University, Samara, Russia

Abstract

In this paper we consider an information technology of 3D scene reconstruction from stereo images which were obtained from a camera with unknown extrinsic parameters. The main idea of the present paper is to compute rotation and translation of the camera directly from the corresponding points.

Keywords: stereo images, camera position estimation, intrinsic camera parameters, image matching, 3D reconstruction.

Citation: Goshin YeV, Fursov VA. 3D scene reconstruction from stereo images with unknown extrinsic parameters. Computer Optics 2015; 39(5): 770-6. - DOI: 10.18287/0134-2452-2015-39-5-770-776.

Acknowledgements: The work was financially supported by the Russian Scientific Foundation (RSF), grant No. 14-31-00014.

Сведения об авторах

Фурсов Владимир Алексеевич, д.т.н., профессор, заведующий кафедрой суперкомпьютеров и общей информатики в Самарском государственном аэрокосмическом университете. Область научных интересов: теория

Компьютерная оптика, том 39, №5

775

Моделирование последовательности рельефов по опорным изображениям местности

Е.В. Гошин, В. А. Фурсов

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

E-mail: fursov@ssau.ru.

Vladimir Alekseyevich Fursov is a Doctor of Sciences in Engineering, a Professor and the head of Supercomputers and General Informatics sub-department of Samara State Aerospace University, and a lead researcher at IPSI RAS. His research interests are development of the theory of estimation from a small number of observations, methods of image processing and pattern recognition, the development of high-performance parallel methods and algorithms of image processing and pattern recognition implemented using multiprocessor computing systems.

Гошин Егор Вячеславович, к.т.н., ассистент кафедры суперкомпьютеров и общей информатики Самарского государственного аэрокосмического университета. Область научных интересов: методы обработки и распознавания изображений, параллельные вычисления, стереозрение.

E-mail: goshine@yandex.ru.

Yegor Vyacheslavovich Goshin is a Candidate of Sciences in Engineering. His current research interests are in image processing, recognition algorithms, parallel computations and stereovision.

Поступила в редакцию 4 ноября 2015 г. Окончательный вариант - 1 декабря 2015 г.

776

Компьютерная оптика, том 39, №5