Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

РАСПОЗНАВАНИЕ И РЕКОНСТРУКЦИЯ 3D-ОБЪЕКТОВ ПО СПУТНИКОВЫМ ИЗОБРАЖЕНИЯМ НА ОСНОВЕ СРАВНЕНИЯ СПЕКТРОВ ГРАФОВ

Тужилкин А.Ю. 1
1 Муромский институт (филиал) Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых
В статье представлен подход к реконструкции трехмерных моделей населенных пунктов по спутниковым изображениям. Показана актуальность работы. Приведены возможные сферы использования результатов исследований. Рассмотрены существующие подходы для реконструкции трехмерных объектов. Реконструкция основана на распознавании изображений и поиске трехмерной модели объекта в базе данных. Распознавание осуществляется на основе сравнения спектров графов эталона и изображения. Для построения графа используется векторизация изображений. Линейные сегменты выделяются на основе преобразования Хафа. Ребрами графа являются отрезки. Точки пересечения отрезков являются узлами графа. Для формирования спектра графа используется матрица смежности. Для реконструкции используются изображения крыш зданий. Приведены результаты работы алгоритмов.
распознавание изображений
трехмерная реконструкция
спектр графа
1. Жизняков А.Л., Привезенцев Д.Г. Использование характера распределения самоподобия в качестве признака цифрового изображения в задаче обнаружения объектов по аэрофотоснимкам // Радиотехнические и телекоммуникационные системы. – 2013. – № 4. – C. 24–32.
2. Захаров А.А., Тужилкин А.Ю., Веденин А.С. Алгоритм определения положения и ориентации трехмерных объектов по видеоизображениям на основе вероятностного подхода // Фундаментальные исследования. – 2014. – № 11 (часть 8). – С. 1683–1687.
3. Захаров А.А. Автоматическая реконструкция трехмерных объектов по техническому чертежу // Программные продукты и системы. – 2011. – № 4. – С. 168–170.
4. Захаров A.A., Ткачук М.И. Алгоритм автоматической реконструкции трехмерных сцен по видеопоследовательности // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. – 2011. – № 3(126). – С. 129–134.
5. Орлов А.А., Ермаков А.А. Технология сравнения и идентификации растровых изображений линий // Программные продукты и системы. – 2008. – № 1. – С. 68–70.
6. Cадыков С.С., Захаров А.А. Выбор уровня детальности при непрерывном упрощении поверхностей полигональных объектов // Вычислительные методы и программирование. –2003. – T. 4, № 1. – C. 86–97.
7. Тужилкин А.Ю., Захаров А.А., Яшков В.С. Алгоритм нахождения соответствий на изображениях на основе подхода минимизации энергии // Современные проблемы науки и образования. – 2015. – № 1; URL: http://www.science-education.ru/121-17497.
8. Chung F.R.K. Spectral graph theory. – AMS. – 1997. – 207 p.
9. Kolbe T.H., Groger G., Plumer L. Citygml interoperable access to 3d city models // Proc. of the first International Symposium on Geo-Information for Disaster Management. – 2005. – Р. 21–23.
10. Shokoufandeh A., Dickinson S.J., Siddiqi K., Zucker S.W. Indexing using a spectral encoding of topological structure // Int’l Conf. Computer Vision and Pattern Recognition. – 1999. – Vol. 2. – Р. 491–497.
11. Umeyama S. An eigendecomposition approach to weighted graph matching problems // IEEE transactions on pattern analysis and machine intelligence. – 1988. – Vol. 10, № 5. – Р. 695–703.
12. Zakharov A.A., Barinov A.E. Synthesis algorithm of three-dimensional objects from video images using stereo correspondence// Pattern Recognition and Image Analysis. – 2015. – Vol. 25, № 1. – Р. 117–121.
13. Zakharov A., Zhiznyakov A. Synthesis of three-dimensional models from drawings based on spectral graph theory // Applied Mechanics and Materials. – 2015. – Vol. 756. – Р. 598–603.
14. Zhiznyakov A.L., Privezentsev D.V. Detection of uncharacteristic blocks in an image with self-similarity // Pattern Recognition and Image Analysis. – 2013. –Vol. 23, № 3. – Р. 375–380.
15. Zhiznyakov A.L., Zuev V.V., Orlov A.A., Privezentsev D.G. A method of comparison of image skeletons with account of features of hereditary factors// Pattern Recognition and Image Analysis. – 2011. – Vol. 21, № 2. – Р. 365–368.

Наглядность представления визуальной обстановки населенных объектов и удобство работы с данными являются важными свойствами для информационных систем различного назначения. Компьютерные трехмерные модели городских сцен могут быть использованы для решения следующих задач [2, 3, 4, 9, 12]: проектирования коммуникаций; моделирования чрезвычайных ситуаций (наводнения, пожары), транспортных потоков, процессов микроклимата; планирования схем эвакуации населения и антитеррористических операций; синтеза визуальной обстановки для тренажеров транспортных средств, геоинформационных систем, систем виртуального туризма. Целью работы является разработка алгоритмического и программного обеспечений автоматической трехмерной реконструкции визуальной обстановки городских сцен по спутниковым снимкам.

Для создания трехмерных моделей объектов местности обычно применяются системы трехмерного моделирования, позволяющие создавать геометрию при помощи типовых операций в интерактивном режиме. Однако этот способ достаточно трудоемок. Также в последнее время используется метод на основе лазерного сканирования. Преимуществами такого подхода являются высокая скорость и точность создания трехмерных моделей. Однако в этом случае формируется облако трехмерных точек. Поэтому в автоматическом режиме невозможно выделить характерные объекты из сцены. Например, поверхность рельефа и фасады зданий представляют в такой системе единое целое. Из-за этого трехмерным данным нельзя назначить атрибуты и использовать в качестве физических моделей, имеющих определенные свойства. Кроме того, лазерное сканирование характеризуется большим объемом получаемых данных, что предъявляет высокие требования к вычислительным возможностям систем. Предлагается использовать подход на основе автоматического восстановления трехмерной геометрии по изображениям. В качестве изображений применяются спутниковые снимки высокого разрешения. На снимках могут быть выделены точечные, линейные и площадные признаки, которые в дальнейшем могут быть использованы для распознавания и реконструкции [1, 5, 14, 15]. Создание системы автоматической реконструкции на основе цифровых изображений позволит сократить временные и материальные затраты при синтезе трехмерных моделей.

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

Модели реконструируемых объектов

Уровнями детальности (LoD – Level of Detail) называют степень подробности представления трехмерного объекта средствами компьютерной графики [6]. В этом случае создаются несколько вариантов представления одного объекта с различными степенями детализации (рис. 1). Уровни детальности используют для универсального представления, хранения и обмена моделей местности. Ассоциацией OGC (Open Geospatial Consortium) разработан язык CityGML (City Geography Markup Language), который определяет классы и отношения объектов, основываясь на их топологических, семантических и геометрических свойствах [9]. Для процесса трехмерной реконструкции моделей местности предполагается использовать уровень LoD2. Уровень детальности LoD2 отображает здания в упрощенном виде. Уровень LoD2 может включать такие элементы, как стены, крыши, трубы.

В работе представлен процесс реконструкции на примере синтеза модели крыш зданий. Модели крыш зданий представлены набором полигонов. В простейшем случае будем рассматривать выпуклые полигоны. Каждый полигон может иметь разное количество сторон, в зависимости от конструкции крыш. Для распознавания и реконструкции объектов используются графы. При распознавании происходит сравнение графа объекта-эталона и графа анализируемого объекта. На место распознанного объекта помещается трехмерная параметризованная модель объекта. Таким образом, необходимо создать базу данных основных параметризованных объектов местности. Высота объектов определяется на основе карты высот, вычисленной по стереоизображениям [7]. Точки пересечения прямых линий, на которых лежат выделенные отрезки, считаются вершинами графа. Отрезки, соединяющие вершины, в рассматриваемой модели называются ребрами. При помощи простых подграфов описываются примитивы, на основе которых можно создать библиотеку трехмерных моделей крыш (табл. 1).

Модель реконструируемого объекта описывается следующим образом:

θ = {Q, H, T},

где Q – параметры контура объекта; H – высота элементов объекта; T – текстура крыши базового объекта здания. Структура контурного изображения проекции объекта определяется вектором:

Q = {Q1, Q2, ..., Qi, ..., Qn},

где Qi – точки, определяющие структуру контурного изображения. Набор отрезков, расположенных на плоскости, получается в результате векторизации изображения. Отрезки выделяются на основе преобразований Хафа. Отрезок характеризуется координатами конечных точек. Однако отрезки не всегда могут быть соединены друг с другом. Отрезки, конечные точки которых расположены на расстоянии меньше ε друг от друга, представляют собой смежные ребра графа. Вершинами графа являются точки пересечения прямых линий, которым принадлежат отрезки.

Угол между векторами, на которых лежат смежные ребра графа, не должен превышать 170°. Если угол между отрезками превышает 170° и конечные точки расположены на расстоянии меньше ε друг от друга, то такие отрезки объединяются. Конечными точками полученного отрезка становятся несмежные точки объединяемых отрезков. Также не рассматриваются отрезки, размеры которых меньше задаваемого значения.

pic_25.tif

Рис. 1. Представление 3D-объекта с помощью уровней детальности по стандарту CityGML

Таблица 1

Контурные изображения крыш зданий, используемые при реконструкции

Номер объекта

Трехмерная модель

Вид сверху

Фронтальный вид

1

pic_26.tif

pic_32.wmf

pic_38.wmf

2

pic_27.tif

pic_33.wmf

pic_39.wmf

3

pic_28.tif

pic_34.wmf

pic_40.wmf

4

pic_29.tif

pic_35.wmf

pic_41.wmf

5

pic_30.tif

pic_36.wmf

pic_42.wmf

6

pic_31.tif

pic_37.wmf

pic_43.wmf

Распознавание и реконструкция объектов

Предлагается описать граф с помощью матрицы смежности. Матрица смежности неориентированного графа G = (V, E) – квадратная симметричная матрица A(G) порядка n tugil01.wmf, элементы aij которой равны числу ребер, соединяющих вершины vi и vj. Сравнение графов состоит в поиске соответствий между структурами графов на основе более или менее строгих ограничений. Предлагается использовать методы сравнения на основе спектральной теории графов [8, 10, 13]. Спектр представляет множество собственных значений tugil02.wmf, упорядоченных по убыванию или возрастанию. Спектральные методы основаны на следующем свойстве: собственные значения и собственные векторы матрицы смежности графа инвариантны относительно перестановок вершин в матрице. Следовательно, если два графа изоморфны, их матрицы смежности будут иметь одинаковые собственные значения и векторы. Однако обратное утверждение не всегда верно: существуют графы с различными структурами, но с одинаковым спектром (коспектральные графы). Так, например, спектр графа объекта № 3 имеет вид S3 = (2,741 0,71 0,681 –0,231 –1,618 –2,22), а спектр графа объекта № 4 представлен следующим образом S4 = (3 1 0 0 –2 –2).

pic_44.wmf

Рис. 2. Нахождение соответствий между вершинами графов

Разложение матрицы смежности на собственные значения имеет вид

A(G) = UΛUT,

где tugil03.wmf – диагональная матрица упорядоченных собственных значений; tugil04.wmf – матрица собственных векторов. Для нахождения соответствий между вершинами графов объекта-эталона и объекта на изображении используется сингулярное разложение матрицы смежности [11]. Пусть имеются графы G и Z, которые представлены на рис. 2. Необходимо найти соответствия между каждой вершиной этих графов.

Матрицы смежности графов G и Z имеют вид

tugil05.wmf

tugil06.wmf

Выполним сингулярное разложение матриц смежности: tugil07.wmf, tugil08.wmf. В матрицах собственных векторов UG и UZ изменим значение отрицательных элементов, используя модуль числа. В результате разложения получим матрицы tugil09.wmf и tugil10.wmf:

tugil11.wmf

tugil12.wmf

Для нахождения соответствий перемножим матрицы tugil13.wmf и tugil14.wmf. На основе полученной матрицы сформируем матрицу перестановок P. Наибольшие значения в каждом столбце заменяются единицами, а остальные значения устанавливаются равными нулю.

tugil15.wmf

tugil16.wmf

                          

pic_45.tifpic_47.tifpic_49.tifpic_51.tif
pic_46.tifpic_48.tif pic_50.tifpic_52.tif

  а                              б                    в                           г

 

Рис. 3. Реконструкция крыш зданий: а – спутниковые снимки реконструируемых объектов; б – результаты выделения контуров с использованием преобразования Хафа; в – векторизованные изображения; г – реконструируемые модели

В полученной матрице перестановок номер столбца равен номеру узла в графе G, номер строки – номеру узла в графе Z. Единица в матрице перестановок обозначает соответствие между узлами из графа G и графа Z. Из полученной матрицы P видно, что вершине V1 графа G могут соответствовать вершины V1 и V4 графа Z, вершине V2 графа G – вершины V1 и V4 графа Z и т.д. Это объясняется тем, что структура графа симметрична. Поэтому не имеет значения, какая из двух точек будет выбрана при нахождении соответствия. В результате был осуществлен синтез трехмерной модели крыши здания (рис. 3).

Заключение

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

Работа выполнена при поддержке гранта РФФИ 15-07-01612-А, задания на выполнение государственных работ в сфере научной деятельности в рамках базовой части государственного задания Минобрнауки России (проект № 2918).

 

Рецензенты:

Жизняков А.Л., д.т.н., профессор, первый зам. директора, МИ (ф) ВлГУ, г. Муром;

Орлов А.А., д.т.н., доцент, зав. кафедрой физики и прикладной математики, МИ (ф) ВлГУ, г. Муром.

Работа поступила в редакцию 17.04.2015.


Библиографическая ссылка

Тужилкин А.Ю. РАСПОЗНАВАНИЕ И РЕКОНСТРУКЦИЯ 3D-ОБЪЕКТОВ ПО СПУТНИКОВЫМ ИЗОБРАЖЕНИЯМ НА ОСНОВЕ СРАВНЕНИЯ СПЕКТРОВ ГРАФОВ // Фундаментальные исследования. – 2015. – № 2-17. – С. 3727-3732;
URL: http://fundamental-research.ru/ru/article/view?id=37846 (дата обращения: 13.12.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074