Программирование, 2019, № 6, стр. 13-22

1. ВВЕДЕНИЕ

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

Значительную роль в этом играет автоматизация обработки информации. Автоматический или даже полуавтоматический режимы работы с данными значительно ускоряют весь процесс, что в свою очередь ведет к увеличению актуальности результирующих данных. Однако есть и негативная сторона автоматизации. Дело в том, что за значительное увеличение скорости работы мы платим ухудшением результирующего качества и точности. Часто это не является существенным недостатком, но также нередки случаи, когда точность является важным критерием оценки результатов. Именно достижению наибольшей скорости обработки исходных данных, сохраняя при этом приемлемую точность, посвящены работы последних нескольких десятилетий [1–3].

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

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

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

2. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ

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

Рис. 1.

Классификация существующих методов по типу используемых данных.

Алгоритмы, опирающиеся на обработку данных лидара (LiDAR) дают высокую точность [4, 5]. Существенным недостатком данного подхода является низкая доступность данных LiDAR и их высокая стоимость.

Методы, использующие космоснимки [6, 7], часто опираются на использование особенностей спутниковой съемки, наличие дополнительных данных (каналов изображения) и высокое качество снимков. Алгоритмы, относящиеся к данной категории, имеют довольно высокую точность обнаружения объектов. Но из-за малой доступности качественных космоснимков их применение ограничено, хотя и в меньшей степени, чем алгоритмов, использующих данные LiDAR.

Методы, использующие ортофото [1, 8], дают также высокую точность, но получение ортофото является очень долгим процессом, требующим большого количества вычислительных ресурсов. Как следствие, получение этого вида данных связано либо с большими временными затратами, либо с большой ценой.

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

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

В методах, опирающихся на обработку единичных снимков [12–14], предлагается использовать анализ цветности и яркости отдельных сегментов изображений, выделения геометрических элементов и теней, a также сегментирования [15]. Такие подходы могут давать высокую точность. Однако они все равно уступают по точности методам, опирающимся на анализ нескольких изображений.

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

В таблице 1 приведено сравнение рассмотренных классов методов.

3. ОСНОВНАЯ ИДЕЯ

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

• снимки обладают высоким качеством;

• сравнительно низкая цена снимков;

• маршрутная съемка (большие пересечения снимков на местности);

• надирная съемка (строго вертикальное направление съемки).

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

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

1. выделение отрезков на каждом изображении;

2. связывание соседних отрезков в контуры;

3. сопоставление областей и отрезков;

4. предварительное построение плоскостей;

5. валидация и уточнение плоскостей;

6. построение результата.

4. ВЫДЕЛЕНИЕ ОТРЕЗКОВ НА СНИМКАХ

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

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

Самыми распространенными методами обнаружения отрезков являются:

1. метод Хафа [20];

2. LSD [21];

3. EdLines [22].

Метод Хафа широко используется и имеет большое количество модификаций, улучшающих его и приспосабливающих под конкретные задачи. Однако существенными недостатками этого метода является его низкая скорость и крайне большое количество ложных срабатываний (выделение отрезков там, где их нет). Помимо этого точность данного подхода при низком качестве снимков заметно ниже LSD и EdLines.

Метод EdLines более быстрый, но часто дублирует отрезки при работе с аэрофотоснимками (рис. 2), что затрудняет дальнейшую обработку.

Рис. 2.

Пример работы метода EdLines.

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

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

Мы предлагаем решить обе проблемы разбиением каждого изображения на квадратные сегменты постоянного размера и применением метода LSD к каждому из них. Размер каждого сегмента определяется на основе табл. 2, исходя из точности, которую хотим получить при определении угла наклона отрезка.

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

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

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

Рис. 3.

Проекция отрезка на границы сегмента.

1. Ближайшие концы отрезков находятся на расстоянии, не превышающем $\Delta $L пикселей.

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

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

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

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

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

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

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

5. СВЯЗЫВАНИЕ СОСЕДНИХ ОТРЕЗКОВ В КОНТУРЫ

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

Существует три варианта взаимного расположения отрезков, причем обработка происходит для каждого из вариантов по всем снимкам, прежде чем переходить к следующему:

1. Отрезки лежат на одной прямой.

2. Отрезки лежат на пересекающихся прямых.

3. Отрезки лежат на параллельных прямых.

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

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

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

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

Во втором варианте рассматривается расстояние между отрезками (перпендикуляр). Если оно незначительно (сильно зависит от качества снимков и рассматривается как входной параметр метода), и если один из отрезков является частью контура, то тогда контур расширяется до второго отрезка. В противном случае все остается как есть.

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

6. СОПОСТАВЛЕНИЕ ОБЛАСТЕЙ И ОТРЕЗКОВ

Существуют точные методы сопоставления объектов на снимках между собой, таких как SIFT [24] или ORB [25]. Однако использование этих методов по всем снимкам может значительно увеличить время всего процесса. По этой причине был разработан новый метод, использующий особенности рассматриваемых данных и работающий быстрее существующих методов.

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

Рис. 4.

Проекция точки на второе изображение.

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

Рис. 5.

Проекция отрезка на второе изображение и область поиска, соответствующая ему.

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

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

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

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

Рис. 6.

Области и их соответствие на двух снимках.

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

7. ПОСТРОЕНИЕ ПЛОСКОСТЕЙ

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

Данная операция дает точные результаты, но полный перебор плоскостей занимает слишком много времени (минуты), особенно если использовать маленький шаг дискретизации угла [16], и является самым длительным этапом алгоритма (до 50% вычислительного времени).

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

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

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

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

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

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

8. РЕЗУЛЬТАТЫ

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

Рис. 7.

Пример построения трехмерной сцены по набору снимков.

В таблице 3 приведены данные сравнения представленного метода с методом перебора плоскостей и подходом [26], основанном на использовании облака точек. Представленные методы также были реализованы авторами.

Данные приведены для набора из шести фрагментов снимков размером 1028 × 891 пикселей с глубиной 24 бит. Сцена, представленная на изображениях, содержит 8 строений.

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

Ввиду особенностей представленного метода, все объекты, построенные в процессе его выполнения, классифицируются как строения. По этой причине данный метод можно рассматривать как метод поиска строений. В таблице 4 приведено сравнение точностии времени работы представленного метода с существующими, в частности с [1, 16].

В данной таблице использовалась метрика F-мера. Основными параметрами этой метрики являются точность (Precision, Prec) и полнота (Recall, Rec). Вычисление этих параметров, как и самой меры, приведено в формуле (1) – (3), где TP (true positive) – количество верных обнаружений; FP (false positives) – количество неверных обнаружений; FN (false negative) – количество необнаруженных объектов.

Из представленной таблицы видно, что предложенный метод несколько проигрывает по точности методу перебора плоскостей [16], но при этом значительно выигрывает по скорости работы. Также рассматриваемый подход сопоставим по точности с методом [1], хоть и уступает ему по скорости работы (что закономерно, учитывая, что [1] использует данные LiDAR и ортофото).

9. ВЫВОДЫ

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

Разработана система обнаружения и восстановления населенных пунктов как в полностью автоматическом, так и в полуавтоматическом режиме (с незначительным участием оператора).

На основе предложенного подхода была реализована и внедрена программная компонента в программное обеспечение “АО Фирма “Ракурс” PHOTOMOD. Идеи, изложенные в статье, могут представлять интерес и быть применимы и для других геодезических программных продуктов.