Исследование и разработка алгоритмов поиска и восстановления населенных пунктов на наборе аэрофотоснимков

Первая глава посвящена обзору научной литературы по изучаемой проблеме, описываются достоинства и недостатки существующих решений, вводится оригинальная классификация методов. На основе представленных
данных для решения поставленной задачи выбирается подход, основанный на обработке нескольких аэрофотоснимков одной местности с информацией о внешнем ориентировании за счет высокой доступности исходных данных с высокой потенциальной точностью. Основным недостатком подобных подходов является скорость их работы, вызванная необходимостью обрабатывать и выполнять сопоставление снимков целиком. В случае промышленной аэрофотосъемки, где размер каждого снимка составляет несколько гигабайт, а количество снимков может достигать нескольких десятков, такой недостаток является критическим.
По этой причине работа в основном посвящена ускорению алгоритмов и ограничению площади, на которой применяются ресурсоемкие алгоритмы. Для достижения этого предлагается использовать выделение примитивов на снимке, в частности, отрезков, в качестве основы описываемого подхода. Это в свою очередь позволяет использовать выделенные отрезки в качестве базового элемента для последующих операций, тем самым уменьшая ресурсоемкий анализ растровых данных. Также предложен оригинальный подход выделения областей, представляющих интерес для дальнейших вычислений, с отсечением остальных частей изображения, не содержащих полезной информации.
В конце главы кратко описывается предлагаемый подход. Его можно разделить на четыре этапа: обнаружение границ и отрезков; выделение областей; сопоставление областей; трехмерная реконструкция.
Во второй главе рассматривается задача обнаружения границ и отрезков. В этой главе описываются и анализируются существующие подходы поиска отрезков на изображении, такие как метод Хафа, EdLines и LSD. На основе проведенных исследований существующих подходов, делается вывод, что метод LSD позволяет получить наиболее точное и полное выделение отрезков на снимках меньших размеров в рамках поставленной задачи. Но с увеличением размеров снимков этот метод допускает все больше и больше пропущенных прямых линий, что приводит к снижению качества итогового результата. Также значимым фактором является ограничение по оперативной памяти, не позволяющее обрабатывать все изображение за один раз. Деградация точности выделения отрезков методом LSD обусловлена тем, что он использует метрику для фильтрации, которая настроена работать по аналогии со зрением человека. То есть при увеличении изображения некоторые детали могут пропадать.
Для преодоления этого недостатка предлагается разбивать изображение на сегменты, к которым и применять метод LSD. В работе приведены оценки размера сегмента в зависимости от желаемой точности, проанализирована зависимость размера сегмента от погрешности обнаружения отрезка. Далее необходимо объединять отрезки, попавшие в соседние сегменты снимка. Для достижения этой цели для каждого отрезка строится его проекция на границы сегмента. В данной работе вводится термин “проекция отрезка на сегмент” – множество точек границы сегмента, на которых может находиться конец отрезка
(или конец его продолжения) с учетом погрешности нахождения отрезка (сдвиг, поворот). В дальнейшем происходит проверка на наличие подходящих отрезков в областях, смежных с проекцией рассматриваемого отрезка на сегмент, и их слияние в один с усреднением параметров.
На следующем этапе для каждого необработанного отрезка проверяется наличие отрезков на заданном расстоянии. Это значение является входным параметром моего подхода и соответствует среднему размеру строений в пикселах. В представленной работе используется значение по умолчанию, соответствующее 15-и метрам для рассматриваемого проекта, что соответствует среднему размеру домов в США (максимальный средний размер домов), выраженное в пикселах. Расстояние между отрезками определяется минимальным расстоянием между их концами. Для отрезков выполняется дополнительная проверка на необходимость их слияния (по углу наклона, изменению угла результирующего отрезка и проверка поля градиентов между ними) и построение результирующего объединенного отрезка.
LSD
EdLines
Предложенный метод
Время (сек) 2.68 Количество отрезков 2511 Ложные срабатывания 471 (шт.)
1.56 3.58 1467 4289 213 1167
Табл. 1. Сравнение методов обнаружения отрезков.
В Табл. 1 представлены сравнения результатов выделения отрезков предложенным методом, EdLines и LSD на исходном изображении размером 1655 х 1698 пикселей. Из таблицы видно, что предложенный метод медленнее, но находит большее количество отрезков, при этом у него больше ложных срабатываний, но не настолько много, чтобы существенно отразиться на производительности. Так как дальнейшая обработка легко справляется с шумом и ложными срабатываниями, то предложенный метод является наиболее подходящим для разрабатываемого подхода реконструкции моделей зданий.
В третьей главе рассматривается задача выделения областей. Обычно большую часть аэрофотоснимков занимают поля, леса, огороды, дороги, которые не представляют особого интереса в рамках поставленной задачи. Использование методов реконструкции строений на подобных участках приводит к существенному понижению скорости работы всего рассматриваемого подхода. По этой причине в рамках разработанной технологии мной был предложен новый метод выделения областей интереса, который позволяет существенно сократить площадь, к которой применяются методы трехмерной реконструкции. Это достигается за счет анализа уже полученных отрезков и их взаимного положения. Данный метод имеет низкую
вычислительную сложность, но при этом позволит выделить области, представляющие интерес для дальнейшего анализа, и отсеять такие участки, как поля, леса и водные пространства. Предложенный метод состоит из двух этапов.
Первый этап представляет собой поиск пар отрезков, которые можно было бы скомпоновать в зависимости от их взаимного положения. В результате этого этапа мы получим ломаные, которые в общем случае не являются замкнутыми. Поскольку цель метода, описываемого в данной главе, – это получить области интереса, то возникает необходимость произвести замыкание ломаных контуров в замкнутые области, что и выполняется на втором этапе метода.
На первом этапе поочередно рассматриваются случаи, когда отрезки лежат на одной прямой, на пересекающихся прямых и на параллельных прямых (анализ производится именно в таком порядке). Случай, когда отрезки лежат на одной прямой, обрабатывается аналогично объединению отрезков, рассмотренному в главе 2. Если два отрезка находятся на пересекающихся прямых, то выполняется их продление до пересечения друг с другом. В этом случае возможны два варианта для каждого из отрезков. Первый вариант – точка пересечения находится на самом отрезке. Тогда отрезок разделяется на два точкой пересечения в случае, если производится объединение. Второй вариант – точка пересечения находится на продолжении отрезка. Рассмотрение этого варианта идентично рассмотрению случая с отрезками на одной прямой за тем исключением, что не производится проверка угла наклона. То есть рассматривается расстояние продолжения отрезка до пересечения и происходит анализ градиента. Если отрезки лежат на параллельных прямых (с учетом погрешности угла наклона), то рассмотрению подлежат следующие варианты: отрезки сдвинуты относительно друг друга, отрезки мало отличаются по длине и их концы на небольшом расстоянии друг от друга. В остальных случаях отрезки остаются как есть. В первом варианте предлагается построить отрезок, соединяющий ближайшие концы параллельных отрезков. Далее по аналогии с предыдущими этапами проверяется градиент в области построенного отрезка и на этой основе принимается решение о создании нового соединительного отрезка. Во втором варианте рассматривается расстояние между отрезками (перпендикуляр). Если оно незначительно (сильно зависит от качества снимков и порога, определяющего незначительность расстояния и задаваемого как входной параметр метода), и если один из отрезков является частью контура, то тогда контур расширяется до второго отрезка. В противном случае все остается как есть.
На втором этапе производится замыкание ломаных, полученных на первом этапе. Поскольку ломаные линии могут получиться разветвленными и иметь больше двух концов и минимизация пропусков имеет высокий приоритет в рамках рассматриваемого подхода выделения областей, то рассматриваться будут все концы, соединение которых не приведет к пересечению замыкающего отрезка с остальной ломаной. Если некоторые замыкающие отрезки имеют
пересечения друг с другом, то они разбиваются точкой пересечения на разные отрезки, каждый из них тоже считается замыкающим.
Данная операция производится исключительно с целью уменьшения вычислительных затрат посредством уменьшения площади изображения, к которой в последующем применяется алгоритм реконструкции крыш по снимкам. Поэтому неточность выделения не влияет на качество конечного результата. Стоит отметить, что внутрь областей попадают не только сами строения, но и тени от них.
Ошибки типа false negative (ошибочно не найденные строения) составляет порядка 5%-10%. Но поскольку этот метод используется как предобработка снимков для алгоритма, обрабатывающего снимки снятых с разных ракурсов, то это не так важно. Если на одном снимке строение не обнаружено, то оно будет обнаружено на другом, снятым с более удобного ракурса. Таким образом, итоговая точность обнаружения будет примерно такой же, как и в более затратном методе, но количество данных, обрабатываемых этим алгоритмом, будет значительно меньше.
На аэрофотоснимках данный алгоритм выделял для будущей обработки 20- 30% от общей площади для сельской местности и 50-70% для местности городского типа. Это позволяет рассчитывать на ускорение всего подхода порядка 30-60%, поскольку данные, полученные на всех этапах, кроме анализа полученных отрезков и соединения их в контуры, используются в алгоритме реконструкции зданий по набору аэрофотоснимков. Дополнительные вычислительные затраты малы, поскольку обработка векторных данных вычислительно проще, чем анализ растров.
В четвертой главе рассматривается задача сопоставления областей. Выделение областей, представляющих интерес для дальнейших операций, значительно уменьшают количество проводимых вычислений. Здесь также, как и при выделении областей важно, чтобы выигрыш от применения этой операции был больше, чем затраты на нее. Наиболее распространенные существующие методы такие, как SIFT (Scale-Invariant Feature Transform) или ORB (Oriented FAST and Rotated BRIEF) не подходят как раз из-за большой вычислительной сложности, а точность этих методов не оправдывает временных затрат на них. По этой причине возникла необходимость разработать новый метод, использующий особенности рассматриваемых данных и работающий быстрее существующих аналогов.
Предложен подход, опирающийся на упрощенное сопоставление крупных примитивов (отрезков) внутри областей с использованием априорной информации о том, что в рассматриваемых областях находятся строения. Для поиска соответствующей области используется преобразование из координат одного снимка в геодезические, после чего из геодезических координат в координаты второго снимка. Поскольку нельзя восстановить высоту точки по одному рассматриваемому снимку, то представленные преобразования
параметризуются. В результате, в общем случае точка на одном снимке переходит в луч или отрезок на другом. Исходная точка может находиться где угодно на полученном луче или отрезке в зависимости от ее положения в трехмерном пространстве. По аналогии отрезок перейдет в множество отрезков, концы которых находятся на лучах, образованных конечными точками исходного отрезка.
При идеальном совпадении отрезок должен заканчиваться у границ зоны сопоставления. По этой причине в качестве веса используется отношение длин сопоставляемого отрезка к рассматриваемому. Чем ближе значение веса к единице, тем более вероятно, что сопоставление верно.
Наконец, вычисляются веса для оценки соответствия областей на сопоставляемом снимке. Для каждой сопоставляемой области вес высчитывается как усредненная сумма весов отрезков, вычисленная на предыдущем этапе. Чем ближе вес к единице, тем более вероятно, что области коррелируют.
Однако, из-за того, что единственный метод при сопоставлении областей между снимками, – это геометрические операции, то есть вероятность того, что описанный выше метод даст некорректное сопоставление. По этой причине вместо того, чтобы выбрать одну область, сопоставляемые области сортируются по значениям веса. Далее используется верификационный алгоритм, описанный ниже.
Сначала рассчитываются расстояния между областями на исходном и сопоставляемом снимках. В качестве соответствующих областей выбираются те, что имеют наибольший вес. После этого расстояния между соответствующими областями сравниваются. Далее на сопоставляемом снимке находятся те области, расстояния между которыми больше остальных отличаются от расстояний связанных областей на исходном снимке. Тогда для исходной области ставится в соответствие следующая область в списке, полученном на предыдущем этапе.
Сельская местность Городская застройка
Точность Скорость Точность Скорость
SIFT 93% 247 сек. 85% 20 мин.
Предложенный метод 87%
43 сек.
78%
9 мин.
Табл. 2. Сравнение методов сопоставления областей между двумя снимками.
Данная операция продолжается для всех связей до тех пор, пока не будет установлен минимум разницы расстояний.
Результаты, полученные на этапе сопоставления областей, представлены в Табл. 2. Сравнение производится на данных для городской и сельской местности с результатами метода SIFT, который является одним из наиболее распространенных подходов сопоставления изображений.
Из таблицы следует, что предложенный метод дает существенное ускорение за счет некоторой потери точности сопоставления областей между двумя снимками. Потеря точности больше для снимков плотной городской высокоэтажной застройки с множеством однотипных строений. В этом случае и ускорение не такое большое, как для сельской местности.
Потеря точности частично компенсируется при сопоставлении множества пар снимков. Также снимки городской застройки менее востребованы, поэтому более важными являются больший выигрыш в скорости и меньшая потеря точности для снимков сельской местности.
В пятой главе описывается метод построения трехмерной модели строений. В связи с тем, что основной фокус данной работы направлен на аэрофотосъемку, которая ведется с большой высоты, то строения практически полностью определяются крышами, а их стены либо сложно, либо невозможно восстановить. По этой причине предлагается сделать упор именно на восстановление крыш строений, а их стены строить как вертикальные плоскости, отступающие от края крыш.
Для решения поставленной задачи предлагается использовать подход, опирающийся на метод перебора плоскостей. В данной работе разработана новая модификация метода перебора плоскостей, работающая значительно быстрее при небольшой потере точности. Ускорение метода предлагается достичь за счет использования информации о пересечении отрезков, полученной на этапе поиска контуров. Поскольку два пересекающихся отрезка однозначно задают плоскость, то вместо полного перебора плоскостей можно сразу ее построить по двум отрезкам. Полученную плоскость нельзя использовать как конечный результат по нескольким причинам. Во-первых, пересечение рассматриваемых отрезков может быть результатом ошибки их построения. Во- вторых, точность построения плоскости по двум отрезкам будет меньше, чем точность построения плоскости методом перебора. По этой причине найденную по двум отрезкам плоскость будем использовать как первое приближение. Далее метод перебора плоскостей будем применять, рассматривая только отклонения в окрестности угла, образующего построенную плоскость-приближение, и используя один из отрезков как ось.
При таком подходе можно получить уточненные данные и также выполнить контроль корректности, поскольку ни одна из перебираемых плоскостей не пройдет отбор по величине корреляции. Если у рассматриваемого отрезка есть несколько связанных с ним отрезков, то описанная выше процедура применяется для каждого из них. Точность построения плоскостей можно еще больше увеличить следующим образом.
Рассматриваются отрезки, находящиеся на проекции плоскости на изображения. Из этих отрезков отфильтровываются короткие для исключения шума и деталей крыши (обычно достаточно фильтровать все отрезки короче трех метров в трехмерном пространстве, но конкретная величина зависит от качества
и вида снимков). Далее отфильтровываются отрезки, расстояние от концов, которых до плоскости превышает погрешность при построении. Данная величина высчитывается на основе шага угла при переборе плоскостей и размера рассматриваемого отрезка: расстояние от одного из концов отрезка до плоскости при его отклонении от нее на угол, равный шагу перебора. Также не рассматриваются отрезки, находящиеся дальше удвоенного размера отрезка-оси. Из оставшихся отрезков выбираются не более десяти, имеющих наименьшие отклонения. И по трехмерным координатам концов отрезков проводится линейная регрессия для уточнения плоскости. Данная операция сходится быстро благодаря точному начальному приближению, полученному на предыдущем этапе.
Заключительным этапом метода является финальное построение результата (крыш) по имеющимся плоскостям. Для этого в представленной работе предлагается использовать аналогичный этап метода перебора плоскостей без существенных изменений. Его суть заключается в ограничении полуплоскостей отрезками, лежащими на них, и выделении новых граней за счет пересечения полуплоскостей. Также на этом этапе проходит фильтрация объектов по таким параметрам как размер (отсеиваются машины, гаражи), высота объектов и их протяженность (отсеиваются дороги и поля).
К преимуществам приведенного подхода можно отнести субпиксельную точность построения результирующего объекта и высокую скорость работы. Это достигается за счет предварительной обработки, что позволяет проводить на порядок меньше сопоставлений, которые имеют большую вычислительную сложность.
К недостаткам можно отнести пропускание мелких деталей на крышах, таких как, например, трубы. Однако для большинства случаев это не имеет принципиального значения и может заменяться наложением текстуры на полученный объект.
В шестой главе предоставляются результаты работы. Реализация представленного подхода проходила проверку на компьютере с 8-ядерном процессором AMD FX-8370 4GHz, 16 Gb RAM, GPU Radeon RX470 4Gb, SSD 500Gb. Тестирование и оценка результатов предложенного метода проводилась на следующих наборах данных (далее проектах): UltraCamX (6 снимков, 9420х14430), NewZealand (16 снимков, 14336х14848), UAS_MINI (27 снимков, 4912х3264), UltraCamX_part (6 снимков 700х800). Выбор проектов проводился на основе подбора широкого диапазона видов данных для наиболее широкого покрытия функциональности описанного подхода и получения более точных оценок при сравнении с другими алгоритмами, решающими схожую задачу. Стоит отметить, что проект UltraCamX_part представляет из себя небольшой сегмент проекта UltraCamX. Это было сделано для получения более комфортных для восприятия и сравнения данных, как визуальных, так и численных
(например, где используются абсолютные величины, такие как количество найденных отрезков).
Для оценки точности обнаружения в работе предлагается использовать известную метрику F-мера (также обозначаемая, как F1). На рис. 1 показаны результаты работы описанного подхода на каждом из проектов. На основе этих данных, можно сделать вывод, что предложенный поход обладает высокой точностью и имеет очень маленькое количество ложных срабатываний. Ожидаемо, наилучшие результаты представленный подход дает для проекта UltraCamX, где самое высокое качество съемки.
1,20 1,00 0,80 0,60 0,40 0,20 0,00
0,96 0,96 0,96
0,93 0,90 0,92
0,91
0,80 0,71
1,00
UltraCamX
NewZealand Точность Полнота
UAS_MINI F-мера
UltraCamX_part
0,88 0,78
Рис.1. Оценка результатов работы предложенного подхода.
Метрика
Метод Baillard’00
Метод Peng’16
Представленный метод
Точность Полнота F-мера (F1)
0.94 0.82 0.93 0.96 0.86 0.90 0.95 0.84 0.92
Табл. 3. Сравнение представленного метода с существующими по точности распознавания на проекте NewZealand.
Также можно заметить, что при обработке данных, снятыми беспилотными летательными аппаратами (проект UAS_mini), значительно падает полнота. Это связано с тем, что съемка такого рода проектов ведется зачастую под наклоном, а не вертикально вниз (надир). Это и приводит к снижению качества обнаружения, хотя и незначительно.
Из табл. 3 следует, что предложенный метод немного уступает по точности методу перебора плоскостей (Baillard’00), но по-прежнему превосходит метод, опирающийся на ортофото (Peng’16).
На рис. 2 представлены результаты работы рассматриваемого метода с точки зрения точности построения трехмерной модели. Для нормализации метрик все данные представлены в пикселях. Данные значения получаются путем приведения значений в метрической системе в пиксельные с использованием параметра «размер пикселя»
4,50 4,00 3,50 3,00 2,50 2,00 1,50 1,00 0,50 0,00
UltraCamX
счредняя ошибка по плану (XY), пикс
UAS_MINI
средняя ошибка по высоте (Z), пикс
NewZealand
UltraCamX_part
Рис. 2. Оценка результатов предложенного подхода.
Метрика
Метод Baillard’00
Метод Dahlke’15
Представленный метод
Ошибка по плану (пикс)
Ошибка по высоте (пикс)
Время (мин)
0.89 0.68 0.81 2.98 2.01 2.76 86 197 43
Табл. 4. Сравнение представленного метода с существующими по точности построения и времени работы на проекте UltraCamX_part.
На представленной диаграмме (рис. 2) видно, что предложенный метод работает заметно хуже на проекте БПЛА (UAS_mini). Это вызвано тем, что метод рассчитан и оптимизирован с расчетом на вертикальную (надирную) аэросъемку. Съемка с БПЛА не имеет строго вертикального направления, ведется с меньшей высоты и при помощи более дешевого оборудования и, как следствие, имеет менее качественный результат. Также при съемке с БПЛА может существенно меняться высота (на проекте UAS_mini эти изменения не существенны, что
является исключением из правил для БПЛА съемки), что противоречит допущениям разработанного подхода.
Из данных, представленных в таблице 4, можно сделать вывод, что представленный метод работает быстрее, чем метод перебора плоскостей (Baillard’00), при близкой точности. Метод, основанный на облаке точек (Dahlke’15), превосходит по точности описанный подход. Данная разница объясняется компромиссом между точностью и скоростью работы. Помимо этого, метод на основе построения облака точек, восстанавливает не только строения, а всю сцену целиком, что также сказывается на скорости работы.
Основные результаты
1. Предложен новый подход, решающий задачу выделения и построения трехмерных моделей строений по снимкам, полученным в результате надирной аэрофотосъемки в автоматическом режиме, за счет выделения и сопоставления отрезков на снимках. Представленный метод имеет высокую точность сопоставления и распознавания, не уступающую существующим методам. При этом предложенный подход имеет большую скорость работы.
2. Предложена оригинальная модификация метода LSD, основанная на разбиении изображения на области и последующем объединении отрезков. Данный подход позволяет увеличить количество распознанных отрезков на снимках за счет незначительного увеличения времени работы, потраченного на объединение отрезков.
3. Представлен оригинальный метод ускорения обработки аэрофотоснимков за счет выделения областей интереса и их сопоставления. Это позволяет отсеять до 80% изображения. При этом количество пропущенных строений не превышает 2%.
4. На основе предложенного подхода реализована программная компонента, используемая в индустриальном программном продукте Photomod, что приводит к повышению производительности операторов при решении задач, связанных с трехмерной реконструкцией населенных пунктов, зданий и строений.
Приложение 1. Детали программной реализации. В рамках данной работы была реализована программная компонента, составляющая порядка 15 000 строк кода, написанная на языке программирования C++. В процессе реализации наибольшие трудности вызвали следующие подзадачи: работа с изображениями большого размера (2GB и более) и работа с отрезками.
Первая проблема связана с тем, что невозможно держать все изображения, с которыми надо проводить преобразования, в памяти. Поэтому была реализована структура классов для работы с сегментами изображения,
обеспечивающая виртуальный доступ к произвольному прямоугольнику на изображении. Реализованная структура также позволяет использовать гибкие «цепочки» преобразований изображения.
Вторая проблема связана с операциями над отрезками. Практически на всех этапах предложенного подхода используется поиск отрезков по заданным критериям (угол поворота, положение). Кроме того, часть отрезков являются объединением из других отрезков. Поэтому была реализована специальная структура, позволяющая осуществлять быстрый поиск и доступ к отрезкам по заданным параметрам. Это достигается разбиением каждого из параметров (угол наклона, положение, размер) на непересекающиеся группы, в которые складываются индексы отрезков, относящиеся к нему. При поиске отрезков вычисляется, в каких сегментах находятся интересующие отрезки, что является быстрой операцией. После этого выполняется фильтрация отрезков, попавших в эти сегменты посредством перебора.