Автоматическое распознавание зданий на аэрофотоснимках

Л.В. Новоторцев,
асп., torets13@gmail.com,
А.Г. Волобой,
в.н.с., д. ф.-м.н.,
voloboy@gin.keldysh.ru,
ИПМ им. М.В. Келдыша РАН, г. Москва

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

One of the main tasks in photogrammetry is the detection of three-dimensional objects on aero photo images, buildings in particular, and their automatic reconstruction into three-dimensional model. The existing methods elaborated for solution of the problem either operate with one image only or have low precision and limitations or process data too long. In the article the combined approach is proposed. Its first step is to roughly detect areas which contain buildings. Then apply precise straight line correlation and reconstruction method.

Введение

На данный момент очень актуальна задача анализа изображений по аэро- и космоснимкам и снимкам, сделанным с помощью БПЛА (Беспилотный Летательный Аппарат). Это вызвано с тем, что на данный момент идёт активное освоение новых территорий и актуализация задач, связанных с отслеживанием уже освоенных мест. В связи с этим растёт необходимость в автоматизации обработки данных, поскольку ручная обработка занимает слишком много времени и средств. По этой причине большое внимание в современных исследованиях уделяется полуавтоматическому и автоматическому анализу снимков.

Решением такого рода задач занимается фотограмметрия. Фотограмметрия - это научно-техническая дисциплина, занимающаяся определением характеристик объектов, таких как форма, размеры, положение в пространстве по их изображениям. Одной из распространенных подзадач фотограмметрии является нахождение и трёхмерная реконструкция строений. Это используется для решения таких задач, как построение карт GIS, построение моделей городов и их развития, обнаружение незаконных или опасных застроек.

Основные источники данных, используемые фотограмметрии, – это, как упоминалось выше, космоснимки, аэрофотоснимки и снимки с БПЛА. В рамках данной статьи рассматриваются данные, полученные в результате аэрофотосъёмки. Основной причиной подобного выбора является наибольшая распространённость аэрофотоснимков за счёт оптимального соотношения цены и качества. Основными особенностями аэрофотоснимков являются:

- Надирная съёмка (съёмка ведётся перпендикулярно земле).

- Высокое разрешение снимков.

- Съёмка ведётся маршрутами (один пролёт самолёта над интересующей областью).

- К снимкам прилагается информация о приблизительных координатах центра снимка и направлении съёмки (ориентации снимка).

1. Обзор существующих методов

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

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

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

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

Один из подходов, использующий несколько снимков, ориентирован на построение плотной матрицы высот: ЦММ (Цифровая Модель Местности) и ЦМР (Цифровая Модель Рельефа). ЦММ представляет собой матрицу с данными о высоте земной поверхности, включая здания, растительность и другие высотные объекты. ЦМР же учитывает исключительно рельеф. После построения ЦММ и ЦМР обрабатывается с целью обнаружения и реконструкции зданий. Обобщённые методы выделения изображений [9, 10, 11] дают довольно неточные результаты. По этой причине часто применяются методы, использующие априорную информацию об искомых объектах [12]. Кроме того построение точной матрицы высот подразумевает выполнение полного ориентирования снимков (задание соответствия всех точек между снимками). Это всё приводит к значительным временным затратам.

Ещё один подход опирается на обнаружение линейных черт на различных изображениях, последующее сопоставление этих черт и построение трёхмерной модели на основе результатов сопоставления [13]. Такой подход обеспечивает хорошие результаты за счёт сбора информации с нескольких изображений. Большая скорость работы обусловлена отсутствием необходимости выполнять полное уравнивание.

2. Основная идея

Недостаток, связанный с длительным временем сопоставления отрезков, можно компенсировать, ограничив область каждого изображения, которую обрабатывает алгоритм, и выполнить сопоставление выделенных областей по наиболее характерным элементам внутри них. Достаточно выполнить небольшое количество сопоставлений, чтобы выбрать коррелирующие между собой области на разных снимках. Это позволит более точным методам работать быстрее, поскольку для сопоставления отрезков придётся гораздо меньше обрабатывать отрезков-кандидатов. Полный алгоритм можно разбить на следующие подзадачи:

1. Выделение прямых линий и отрезков.

2. Объединение отрезков в замкнутые контуры и отбраковка контуров.

3. Выполнение сопоставления областей.

4. Выполнение точного алгоритма сопоставления отрезков и построение трёхмерной модели.

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

3. Предобработка снимков

Первым шагом представленного алгоритма является выделение прямых и отрезков на изображении. Наиболее распространённым методом решения этой задачи является метод Хафа [8] и его модификации [14, 15, 16, 17]. Суть этого метода заключается в применении фильтра Кэнни [7] и его модификации [18, 19]. В данной работе для решения этой задачи предлагается использовать следующий подход. Вначале мы разделяем изображение на равные квадратные области (за исключением границ изображения). Для каждой области применяется модификация метода Хафа, оперирующая с окрестностями отрезков [14]. Отрезки, найденные на соседних сегментах, объединяются, если они лежат на одной прямой.

Следующим важным этапом является объединение отрезков, поученных на предыдущем этапе в ломаные и замкнутые контуры [20].

Общий принцип заключается в следующем. Поочерёдно выполняются этапы:

1. Объединение отрезков, лежащих на одной прямой.

2. Объединение отрезков, лежащих на пересекающихся прямых.

3. Объединение отрезков, лежащих на параллельных прямых.

4. Замыкание полученных ломанных и фильтрация.

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

4. Сопоставление областей

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

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

Рассмотрим случай обработки одной области и попытки сопоставить её с одной из областей на снимке, имеющий перекрытие с первым снимком на интересующем нас сегменте.

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

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

После этого области-претенденты отсортируем согласно двум критериям: площадь пересечения с рассматриваемой областью и расстояние между центрами областей. Сортировка по второму параметру ведётся только в случае совпадения по первому.

Дальнейшую обработку будем проводить, перебирая области-претенденты по порядку согласно проведённой сортировке. Это обуславливается тем, что области, расположенные ближе друг к другу, с большей вероятностью окажутся коррелирующими.

Выбираем на исходной области особые точки по следующим критериям:

- точки находятся в вершинах ломанных, построенных на этапе, описанном в разделе 4;

- точки распределены по области;

- вес точки определяет её кратность;

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

Для каждой тройки из этих трёх точек выполняем сопоставления [21, 22, 23] с тройками "особых" точек, аналогично связанных отрезками, рассматриваемой области второго снимка. Важно отметить, что на втором снимке не ищется угол, а ищутся пары точек, связанные отрезком, поскольку одна из точек, как упоминалось ранее, может пропасть.

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

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

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

5. Сопоставление отрезков внутри областей

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

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

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

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

6. Реконструкция строений

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

На следующем этапе проходит ограничение плоскостей с использованием отрезков, относящихся к данной плоскости и пересечениями с другими. Помимо этого, плоскости, закрытые другими (т.е. почти полностью перекрывающиеся по Z-координате), отфильтровываются. Также фильтруются плоскости, близкие к вертикальным.

7. Результаты

На рисунке 1 приведены результаты выделения замкнутого контура и ему принадлежащих отрезков (фильтруются все отрезки вне контура) на снимках, сделанных с разных ракурсов при аэрофотосъёмке.

На рисунке 2 праведен результат трёхмерной реконструкции по выделенным элементам, при этом точность построения составляет 0,2 метра.

Рис 1. Результаты выделения линий

рис 2. Построенная модель крыши

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

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

Литература

1. Rottensteiner F., Briese C. A new method for building extraction in urban areas from high-resolution LIDAR data. International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences, 34(3/A), pp 295-301, 2002.

2. Sohn G., Dowman I. Data fusion of high-resolution satellite imagery and LIDAR data for automatic building extraction. ISPRS Journal of Photogrammetry and Remote Sensing, 62(1), pp. 43-63, 2007.

3. Ghaffarian S., Ghaffarian S. Automatic building detection based on supervised classification using high resolution Google Earth images. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 40(3), pp 101-106, 2014.

4. Jin X., Davis C. H. Automated building extraction from high-resolution satellite imagery in urban areas using structural, contextual, and spectral information. EURASIP Journal on Applied Signal Processing, 2005, pp 2196-2206, 2005.

5. Ok A. O. Automated Extraction of Buildings and Roads in a Graph Partitioning Framework. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences II-3/W3, pp 79-84, 2013.

6. Singhal S., Radhika S. Automatic Detection of Buildings from Aerial Images Using Color Invariant Features and Canny Edge Detection. International Journal of Engineering Trends and Technology(IJETT) 11(8), pp 393-396, 2014.

7. Canny J. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, pp. 679-698, 1986.

8. Hough P. V. C. Method and Means for Recognizing Complex Patterns, U.S. Patent 3069654, Dec. 18, 1962.

9. Brunn A., Weidner U. Extracting buildings from digital surface models. International Archives of Photogrammetry and Remote Sensing, 32(3) sect. 4W2, pp. 27-34, 1997.

10. Cord M., Paparoditis N., Jordan M. Dense, reliable and depth discontinuity preserving DEM computation from HRV urban stereopairs. International Archives of Photogrammetry and Remote Sensing, 32, pp. 49-56, 1997.

11. Girard S. et al. Building detection from high-resolution color images. Remote Sensing – International Society for Optics and Photonics, pp 278-289, 1998.

12. Berthod M. et al. High-resolution stereo for the detection of buildings. Automatic Extraction of Man-Made Objects from Aerial and Space Images. – Birkhäuser Basel, pp. 135-144, 1995.

13. Baillard C., Zisserman A. A plane-sweep strategy for the 3D reconstruction of buildings from multiple images. International Archives of Photogrammetry and Remote Sensing, 33(B2) part 2, pp 56-62, 2000.

14. Du, S., van Wyk, B. J., Tu, C., & Zhang, X. An improved Hough transform neighborhood map for straight line segments. IEEE Transactions on Image Processing, 19(3), pp. 573-585, 2010.

15. Li H., Lavin M. A., Le Master R. J. Fast Hough transform: A hierarchical approach. Computer Vision, Graphics, and Image Processing, 36(2), pp. 139-161, 1986.

16. Nguyen T. T., Pham X. D, and Jeon J. An improvement of the Standard Hough Transform to detect line segments. IEEE International Conference on Industrial Technology, pp. 1-6, 2008.

17. O'Rourke J. Dynamically Quantized Spaces for Focusing the Hough Transform. IJCAI, 81, pp. 24-28, 1981.

18. Bao P., Zhang D., Wu X. Canny edge detection enhancement by scale multiplication. IEEE transactions on pattern analysis and machine intelligence, 27(9), pp. 1485-1490, 2005.

19. Dollár P., Zitnick C. L. Fast edge detection using structured forests. Pattern Analysis and Machine Intelligence, IEEE Transactions, 37(8), pp. 1558-1570, 2015.

20. Novotortsev,L., Voloboy,A. Automated Detection of Buildings on Aero Images. WSCG Posters Proceedings, Vol. 23, pp. 23-28. 2015.

21. Chen Y., Wang J. Z. A region-based fuzzy feature matching approach to content-based image retrieval. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 24(9), pp. 1252-1267, 2002.

22. Miksik O., Mikolajczyk K. Evaluation of local detectors and descriptors for fast feature matching. Pattern Recognition (ICPR), IEEE International Conference on, pp. 2681-2684, 2012.

23. Roux M., McKeown D. M. Feature matching for building extraction from multiple views. Computer Vision and Pattern Recognition, 1994. Proceedings CVPR'94. IEEE Computer Society Conference on, pp. 46-53, 1994.