Способы улучшения зрения

Размещено:  Флеболог

Page 1

Самокалибрующаяся система трехмерного зрения и анализ ее приме-
нимости в робототехнике и спутниковой съемке земного рельефа.
Н.В. Свешникова, А.С. Чернышев, Д.В. Юрин.
ЦОС и ВТ МФТИ, ФГУП НПП ОПТЭКС
Москва, Россия

Аннотация
Разработана расширяемая система восстановления трехмер-
ных сцен, движения и параметров камеры. Путем численного
моделирования найден критерий для адаптивного выбора
приближения в зависимости от получаемой системой оценки
расстояния до объекта. Проведены оценки точности и приме-
нимости системы для аэрокосмических задач.
Ключевые слова: Восстановление трехмерных сцен, метод
факторизации, триангуляция, VRML модель, комбинирован-
ный алгоритм.
1. ВВЕДЕНИЕ
Задача восстановления трехмерных сцен по цифровым изо-
бражениям является востребованной и интенсивно развивае-
мой во всем мире [1-10]. Среди всего комплекса задач выде-
лим три наиболее типичных:
1) Восстановление земного рельефа по аэрокосмическим
изображениям для нужд картографии и мониторинга
промышленных объектов и чрезвычайных ситуаций.
2) Восстановление плана помещений по изображениям,
полученным с цифровых фотоаппаратов и кинокамер для
нужд перепланировки и оборудования промышленных
помещений и архитектуры.
3) Системы зрения мобильных роботов.
В настоящее время уже есть примеры успешного построения
таких систем, однако в целом задача далека от окончательно-
го решения, а часть таких систем требует точных измерений
и калибровки, что не всегда удобно. Например, на борту
спутника Terra[6] находится два прибора, дающих возмож-
ность восстанавливать трехмерные сцены MISR (9 идентич-
ных телескопов с пространственным разрешением 250м) и
ASTER (стерео система с пространственным разрешеним 15м
Заметим, что при съемке высокого разрешения (d=1-10м.) для
типичной высоты орбиты h=1000 км. ориентацию камер надо
знать с точностью d/h=10-5-10-6 рад., а координаты спутника
с точностью порядка d. Такие точности в принципе достижи-
мы, но приводит к сложной и дорогостоящей системе со зна-
чительными массогабаритными характеристиками. Поэтому
представляют интерес подходы, позволяющие восстанавли-
вать эти параметры непосредственно из видео данных.
Большинство описанных в литературе систем, построено на
основе какого то одного физического принципа. В то же вре-
мя, разные подходы [1-4,7-10] взаимно дополняют друг друга
и имеют различные «плохие случаи». Таким образом пред-
ставляется целесообразным построить комбинированную
систему, использующую различные алгоритмы восстановле-
ния трехмерных сцен в комбинации, с выбором оптимального
для данной сцены и ее различных частей алгоритма.
2. СТРУКТУРА СИСТЕМЫ
В качестве основы системы была выбрана группа алгорит-
мов, основанных, на факторизации матриц [2-4]. Основанием
для такого выбора послужили следующие причины:
1) Возможность восстановления не только формы сцены,
но и движения, ориентации и фокусных расстояний ка-
мер.
2) Возможность работы с нестационарными сценами [3].
3) Высокая точность метода и из-за больших баз съемки.
4) Невысокая вычислительная сложность.
В результате применения подходов [2,4] получаются трех-
мерные координаты некоторых точек объекта с высокой
точностью, по которым может быть построена поверхность в
виде сетки или меша [5], координаты и ориентация камер, и
при наличии близких объектов фокусные расстояния камер.
Структура алгоритмов [2,4] открывает возможности интегра-
ции с другими подходами и сопутствующими данными двумя
способами.
Shape from motion,
scene, motion and
camera recover.
Multibody Analysis [3]
ForEach object
3D restore [2,4] with
adaptive select
algorithm (this article)
Dense map building:
ForEach mesh triangle
if no texture
use Shape From Shading
else if object is near and texture is fine
use Defocus [8]
else
use Multiway Cut Segmentation [7]
Texture
Analysis
KLT-1
(Feature
detection)
Line
Detector
Create mesh
(triangulation)
Multibody analysis and
camera-object
distance estimation on
the base of Stereo,
Focusing or Defocus
Mesh
Refine
Bitmap images
stream
KLT-2
(Tracking)
Compass, gyrocompass, gyroscope,
GPS, orbit parameters, etc.
Insert new fragment to 3D
scene or refine existing
Export
VRML
Coarse
image
fitting
3D model
Collision
Detection

Рис. 1. Общая схема системы.
1) Для близких объектов первоначальная оценка расстояний
может быть выполнена методами дефокусировки или стерео
[8-9], или использованы априорные данные (GPS, гироскопы
International Conference Graphicon 2003, Moscow, Russia, http://www.graphicon.ru/

Page 2

и т.п.), что дает информацию для выбора приближения и ус-
коряет сходимость [4]. Может быть выполнено грубое разде-
ление сцены на области различной удаленности, и для них
использованы наилучшие приближения. Использование сте-
рео или дефокусировки с совмещенной камерой [10], позво-
ляет произвести выделение быстро движущихся объектов и
облегчить их обработку трэкером характеристических точек.
2) Построенный меш является хорошим начальным прибли-
жением с точно определенными узлами. Поверхность может
уточняться методами [7-10] до достижения плотной карты
глубин сцены. Метод уточнения выбирается на основе анали-
за текстур изображения и полученного расстояния от камер
до уточняемой области объекта, оцениваемой как расстояние
от камеры до поверхности, задаваемой мешем.
Общая структура системы изображена на рис.1, реализован-
ные в настоящий момент блоки отмечены жирной рамкой.
Система реализована на языке C++ в независимом от опера-
ционной системы виде.
3. ОБНАРУЖЕНИЕ И СОПРОВОЖДЕНИЕ
ХАРАКТЕРИСТИЧЕСКИХ ТОЧЕК
Идея алгоритма [1] сопровождения состоит в том, что при
малых изменениях положения и ориентации камеры, область
в более позднем изображении
щением некоторой области предыдущего изображения
Тогда смещение можно найти из минимизации функционала.
r
r
()
2
∫∫
d
линеаризации функций яркости, решение этой задачи сводит-
ся к итерационному решению линейной системы [1]:
r
=
может быть получена сме-
J
I .
xdxw
d
2
xI
d
xJ
rr
r
r
)( ] )([
2
−−+=ε

(1)
Здесь
вектор смещения,
r
)(xwr
- функция окна. Путем
edZ
r

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

=
i
вычисляются независимо для каждого канала по формулам из
[1].
,
J I векторами, компонен-
как и уравнение (2), но
и ,где Z
=
N
Z
i Z
1

=
i
=
N
ie
1
r
er
i и ei –
Работа с изображениями ведется по пирамиде разрешений.
4. ФОРМИРОВАНИЕ ПЛОТНОЙ МАТРИ-
ЦЫ ИЗМЕРЕНИЙ.
При сопровождении точек по серии изображений, возможна
как потеря, так добавление новых отметок. Однако, для алго-
ритма восстановления трехмерной сцены требуется наличие
всех отслеживаемых точек на всех кадрах. Таким образом,
появляется задача выделения наибольшей полностью запол-
ненной матрицы, в которой строки – это кадры, а столбцы –
отслеживаемые точки.
Предлагается решать эту задачу через поиск клик графа.
Граф Г={X,E} строится следующим образом. Множеством
его вершин
слеживаемые точки P. Множество ребер E задается двумя
условиями. Подмножества F и P являются полностью зави-
симыми множествами. Ребро между вершинами
Pp∈
есть только в том случае, если отметка p присутству-
ет в кадре f, (см. рис. 2).
}{PFX
∪=
являются все кадры F и все от-
Ff ∈
и

1 2 3 4 5
Win=
P
F
заполненность
матрицы
граф Г:
F
1 2 3 4
P
Wout=
2 3 4
1 2 1
3 3 2
5 6 6
7 6 5
5 6 7
1 2 3 4 5
1 1 2 1 1
4 3 3 2 -
4 5 6 6 -
- 7 6 5 -
- 5 6 7 -
- 9 - 9 8
- 3 - 4 5

Рис. 2. Поиск плотной подматрицы через клику графа Г,
F,P – число кадров и точек (отметок).

При выделении из графа перекрывающихся клик появляется
возможность восстановления отдельных частей сцены с по-
следующей их сшивкой по общим точкам. Это позволяет
более полно восстановить сцену, так как алгоритмы [2-4]
требуют видимости всех отслеживаемых точек на всех кад-
рах, что далеко не всегда выполнимо. Для нахождения клики,
используется алгоритм [11].
5. АЛГОРИТМ ВОССТАНОВЛЕНИЯ
ТРЕХМЕРНОЙ СЦЕНЫ.
В системе реализованы линейные алгоритмы [2] и итераци-
онный алгоритм в перспективной проекции [4]. Заметим, что
алгоритм [4] на каждом шагу итерации использует прибли-
жение масштабированной ортографии [2], что позволяет в
принципе прервать цикл итераций и ограничиться прибли-
женным решением. Так как итерационный алгоритм извлека-
ет дополнительную информацию из перспективных искаже-
ний, то при большой дальности до объекта, итерации не при-
водят к повышению точности. Вопрос о критерии отключе-
ния итераций рассматривается в разделе, посвященном ре-
зультатам.
6. ПОСТРОЕНИЕ ТРЕХМЕРНОЙ СЦЕНЫ
В ВИДЕ СЕТКИ, ЭКСПОРТ В VRML.
В результате решения задачи восстановления получаются
координаты и ориентация камер, фокусные расстояния (если
использовался итерационный алгоритм) и трехмерные коор-
динаты тех точек объекта, которые были обнаружены и ус-
пешно сопровождались трэкером (разделы 3-4). Теперь по
этим точкам надо построить поверхность объекта в виде ме-
ша. В настоящей работе используется следующий подход.
Так как в проекции на каждый кадр взаимное расположение
отметок всегда правильно, и для кадра с номером f двумер-
ные координаты отметок на этом этапе доступны и содержат-
ся в строках 2f+1 и 2f+2 матрицы (3), то триангуляция
производится в плоскости кадра в двумерном пространстве
по этим точкам. Затем полученные соединения формально
применяются к восстановленным трехмерным координатам
соответствующих точек. Такой подход позволяет применить
быстрый алгоритм [5] и исключает возможность соединения
ребром точек с различных поверхностей (сторон) объекта,
например при круговой съемке объекта, так как такие точки
International Conference Graphicon 2003, Moscow, Russia, http://www.graphicon.ru/

Page 3

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

7. РЕЗУЛЬТАТЫ: АНАЛИЗ ПРИМЕНИ-
МОСТИ И ОЦЕНКА ПОГРЕШНОСТЕЙ.
Предложенный алгоритм тестировался на реальных и синте-
тических данных. Для синтетических данных в виде трех-
гранного угла приведены графики сравнительной точности
восстановления в различных приближениях в зависимости от
отношения расстояния до объекта L к размеру объекта a.
На рис.3-5 видно, что на малых расстояниях точность метода
[4] существенно превосходит остальные. Однако по мере
увеличения расстояния точность различных приближений
становится примерно одинаковой, и для метода [4] начиная с
некоторого расстояния становится сопоставима или хуже
(рис. 4.5), чем для линейных методов [3]. Это связано с ис-
чезновением перспективных искажений в цифровых изобра-
жениях. Поэтому система должна автоматически переклю-
чаться на приближение масштабированной ортографии или
параперспективный метод.
Рис. 3. Погрешность восстановления формы сцены. Угол
обхода камеры 600, разрешение изображения 1024 пиксе-
ля.

Критерий переключения в системе выбирался по результатам
численного моделирования на описанных синтетических
данных. За основной параметр анализа был принят безраз-
мерный параметр L/a. Очевидно, что точность восстановле-
ния зависит и от других параметров:
-
углового разрешения камеры;
-
углового размера восстанавливаемого объекта:
-
отношения максимального перемещения камеры к
среднему расстоянию до объекта;
-
угла обхода камеры вокруг объекта.
Результаты численного моделирования показывают, что за-
висимость пороговой величины от этих параметров слабая.
Рис. 4. Погрешность восстановления ориентации камер в
радианах. Угол обхода камеры 600, разрешение изображе-
ния 1024 пикселя.
На рис. 3-5 видно, что переключение должно происходить в
различных диапазонах для восстанавливаемых величин –
формы, ориентации матриц и положения камер: перспектив-
ный метод более точно восстанавливает форму в диапазоне
расстояний равных 1 - 102, ориентации камер – 1 – 20, поло-
жение камер – 1 – 5 размеров восстанавливаемого объекта.

На рис. 4. также приведен участок графика, соответствующий
съемке объекта в условиях, сопоставимых с условиями спут-
никовой съемки. Из этого участка графика видно, что при-
ближение масштабируемой ортографии и параперспективное
приближение способны давать результат с приемлемой для
спутниковой съемки точностью.
На рис. 7-10 представлено восстановление реальной сцены.
На рис. 7 и 8 показаны начальный и конечный кадры серии.
На рис. 9 отмечены точки, сопровожденные трекером. Изо-
бражение восстановленной VRML-модели представлено на
рис. 10. Искажения формы вызваны тем, что на ребрах объек-
та не были найдены подходящие для сопровождения точки, и
алгоритм триангуляции не смог построить реальные границы
коробки без них. Однако, координаты узлов меша восстанов-
лены точно. Построенная модель может использоваться как
хорошее начальное приближение для уточнения формы объ-
екта.
Рис. 5. Погрешность восстановления XY компонент по-
ложения камер. Угол обхода камеры 600, разрешение изо-
бражения 1024 пикселя.
International Conference Graphicon 2003, Moscow, Russia, http://www.graphicon.ru/

Page 4

Рис. 7,8. Начальный и конечный кадры серии.

Рис. 9. Кадр с выделенными характеристическими точ-
ками.

Рис. 10. Восстановленная VRML-модель с другой точки
зрения, справа –то же в виде сетки.
8. ЗАКЛЮЧЕНИЕ
Разработана базовая составляющая системы восстановления
трехмерных сцен по последовательности цифровых изобра-
жений. Путем численного моделирования найден критерий
адаптивного выбора модели (приближения) вычислений.
Проведены оценки точности восстановления. Предложен
подход к выделению плотной подматрицы измерений, осно-
ванный на поиске клики графа. Показано, что применительно
к аэрокосмическим системам достижима высокая точность
восстановления рельефа, и точность восстановления ориен-
тации камеры. Установлено, что наиболее слабым местом
текущего состояния системы является требование малого
изменения изображений между парами последовательных
кадров, и планируемый блок грубого совмещения сущест-
венно необходим. В случае больших дальностей необходим
альтернативный способ устранения неоднозначности формы
[3,4], основанный, например, на априорном грубом знании
смещения камеры между некоторыми парами кадров.
9. ЛИТЕРАТУРА:
[1] Carlo Tomasi, Takeo Kanade. Shape and Motion from Image
Streams: a Factorization Method, Part 3, Detection and Tracking
of Point Features //Technical Report CMU-CS-91-132 / School of
Computer Science, Carnegie Mellon University. — April 1991.
[2] Conrad I. Poelman, Takeo Kanade. A Paraperspective Fac-
torization Method for Shape and Motion Recovery: //Technical
Report CMU-CS-93-219 / School of Computer Science, Carnegie
Mellon University. — 11 December 1993.
[3] J.Costeria and T. Kanade. A multi-body factorization method
for motion analysis. Technical report, School of Computer Sci-
ence, Carnegie Mellon University, Pittsburgh, PA 15213, Sep-
tember 1994. CMU-CS-TR-94-220.
[4] Янова Н.В., Юрин Д.В. Итеративный алгоритм восстанов-
ления трехмерных сцен, движения и фокусного расстояния
камеры в перспективной проекции, основанный на фактори-
зации матриц. //В сб. Труды конференции. 12-я Международ-
ная Конференция по Компьютерной Графике и Машинному
Зрению ГрафиКон’2002 –С. 123–129. Нижний Новгород, 16-
21 сентября 2002 г.
[5] Shewchuk J.R. Triangle: Engineering a 2d quality mesh gen-
erator and delaunay triangulator. First ACM Workshop on Ap-
plied Computational Geometry. 1996.
[6] The First EOS Satellite. NASA’S Earth Observing System
EOS AM-1. http://terra.nasa.gov/Publications/AM-
1_brochure.pdf
[7] Stan Birchfield and Carlo Tomasi. Multiway Cut for Stereo
and Motion with Slanted Surfaces //Proceedings of the Seventh
IEEE International Conference on Computer Vision, Kerkyra,
Greece, September 1999.
[8]Y.Xiong and S.Shafer. Depth from focusing and defocusing.
http://www.cs.cmu.edu/ yx/papers/IUW93.ps.Z.
[9] Vladimir Kolmogorov and Ramin Zabih. Computing Visual
Correspondence with Occlusions using Graph Cuts. // In: Interna-
tional Conference on Computer Vision, July 2001.
[10] M. Watanabe S. K. Nayar and M. Noguchi. Real-time focus
range sensor. Technical report, Department of Computer Science,
Columbia University, New York, USA, June 1994. CUCS-028-
94.
[11]C. Bron and J. Kerbosch. Algorithm 457: Finding All Cliques
of an Undirected Graph. CACM, 16(9):575-577, 1973.
Об авторах
Наталья Владимировна Свешникова – студентка 5-го курса
ФФКЭ Московского Физико - Технического Института.
E-mail:

Андрей Сергеевич Чернышов – студент 4-го курса ФФКЭ
Московского Физико -
E-mail:
Технического Института.

Юрин Дмитрий Владимирович, к.ф.-м.н., ФГУП НПП «ОПТ-
ЭКС», нач. отдела.
E-mail:
International Conference Graphicon 2003, Moscow, Russia, http://www.graphicon.ru/

Источник: http://www.researchgate.net/publication/260319385_...