Одним из основных источников данных для сервиса Яндекс.
Карты являются спутниковые снимки.
Чтобы было удобно работать с картой, на изображениях полигонами отмечаются объекты: леса, водоемы, улицы, дома и т.п.
Обычно разметку выполняют специалисты-картографы.
Мы решили им помочь и научить компьютер складывать полигоны домов без участия человека.
За операции с изображениями отвечает область ИТ, называемая компьютерным зрением.
За последние несколько лет большинство задач в этой области было весьма успешно решено с помощью нейронных сетей.
Сегодня мы расскажем читателям Хабра о нашем опыте использования нейронных сетей в картографии.
Прежде всего, мы обучим нейронную сеть, которая будет заниматься семантической сегментацией, т. е.
определять, принадлежит ли каждая точка на спутниковом снимке дому.
Почему семантическая сегментация, а не просто обнаружение объектов? Когда задача обнаружения будет решена, мы получим на выходе набор прямоугольников, причем конкретных: две стороны вертикальные, две стороны горизонтальные.
Причем дома обычно повернуты относительно осей изображения, а некоторые здания еще и имеют сложную форму.
Проблему семантической сегментации сейчас решают различные сети ( ФКН , СегНет , UNet и так далее.
).
Нам просто нужно выбрать, какой из них нам больше подходит. Получив маску со спутникового снимка, выделим достаточно большие кластеры точек, принадлежащих домам, соберем их в связные области и представим границы участков в векторной форме в виде полигонов.
Понятно, что маска не будет абсолютно точной, а значит, соседние дома могут склеиться в одну целостную область.
Чтобы справиться с этой проблемой, мы решили дополнительно обучить сеть.
Она найдет на изображении края (границы домов) и отдельные здания, слипшиеся между собой.
Итак, получилась следующая схема: 
Мы не стали полностью отказываться от сетей обнаружения и попытались Маска R-CNN .
Его преимуществом по сравнению с традиционной сегментацией является то, что Mask R-CNN одновременно обнаруживает объекты и генерирует маску, поэтому нет необходимости заморачиваться с разделением общей маски на связанные области.
Ну и минусом (как же без него) является фиксированное разрешение маски каждого объекта, т.е.
для больших домов со сложной границей эта граница заведомо будет упрощена.
Инструменты
Затем нужно было определиться с инструментами.Тут всё было совершенно очевидно: для задач компьютерного зрения лучше всего подходит OpenCV .
Выбор нейронных сетей несколько шире.
Мы остановились на Тензорный поток .
Его преимущества:
- достаточно развитый набор готовых «кубиков», из которых можно собирать свои сети;
- Python API, удобный для быстрого создания сетевой структуры и для обучения;
- обученную сеть можно использовать в своей программе через C++-интерфейс (очень убогий по сравнению с Python-частью, но вполне достаточный для запуска готовых сетей).
Набор данных
Восемьдесят процентов успеха в работе с нейросетью — это хороший набор данных.Это означает, что сначала нам нужно было собрать такой набор данных.
У Яндекса огромное количество спутниковых снимков с уже отмеченными объектами.
Кажется, все просто: достаточно скачать эти данные и собрать их в датасет. Однако есть одно предостережение.
Уточнение набора данных
Когда человек ищет дома на спутниковом снимке, первое, что он замечает — это крыши.Но высота домов разная, спутник может снимать одну и ту же местность под разными углами - и если разместить на векторной карте полигон, соответствующий крыше, то нет гарантии, что крыша не сдвинется при съемке изображения.
обновляется.
Но фундамент вкапывается в землю и, под каким углом его ни возьми, он всегда остается на одном месте.
Именно поэтому дома на векторной Яндекс.
Карте отмечены «по фундаментам».
Это правильно, но для задачи сегментации изображений лучше обучить сеть искать крыши: надежды на то, что сеть научится распознавать фундаменты, очень мало.
Поэтому все в наборе данных должно быть отмечено крышами.
Это значит, что для создания хорошего набора данных нам нужно научиться смещать векторную разметку домов с фундаментов на крыши.
Мы старались его не перемещать, но качество получилось очень плохим, и это понятно: углы съемки со спутника разные, высота домов разная, в результате на фотографиях фундамент сместился в разные стороны.
и на разном расстоянии от крыши.
Сеть теряется от такого разнообразия и в лучшем случае обучена на что-то среднее, в худшем — на что-то непонятное.
Более того, сеть семантической сегментации выдаёт результат, вроде бы приемлемый, но при поиске ребер качество резко падает.
«Растровый» подход
С тех пор как мы попали в область компьютерного зрения, первое, что мы сделали, это опробовали подход, соответствующий этому самому компьютерному зрению.Сначала векторная карта растеризуется (полигоны домов рисуются белыми линиями на черном фоне), Фильтр Собеля выделяет края на спутниковом изображении.
А затем находится смещение двух изображений относительно друг друга, которое максимизирует корреляцию между ними.
Края после фильтра Собеля довольно зашумлены, поэтому если применить такой подход к одному зданию, то не всегда получится приемлемый результат. Однако метод хорошо работает на участках со зданиями одинаковой высоты: если искать смещение сразу на большой площади изображения, результат будет более стабильным.
«Геометрический» подход
Если территория застроена не однотипными, а разными домами, предыдущий метод не подойдет. К счастью, иногда мы знаем высоту зданий на векторной карте Яндекса и положение спутника во время съемки.Таким образом, мы можем воспользоваться школьными знаниями геометрии и посчитать, куда и насколько сместится крыша относительно фундамента.
Этот метод позволил улучшить набор данных в районах с высотной застройкой.
«Ручной» подход
Самый трудоёмкий способ: засучить рукава, вытащить мышку, пялиться в монитор и вручную перемещать векторные разметки домов от фундаментов к крышам.Методика приносит просто ошеломляющие результаты, но массово ее использовать не рекомендуется: разработчики, занимающиеся такими задачами, быстро впадают в апатию и теряют интерес к жизни.
Нейронная сеть
В результате мы получили достаточно спутниковых снимков, хорошо заметных на крышах.Значит, есть шанс обучить нейросеть (пока, правда, не для сегментации, а для улучшения маркировки других спутниковых снимков).
И мы сделали это.
Входными данными для сверточной нейронной сети были спутниковое изображение и смещенный растровый макет. На выходе мы получили двумерный вектор: вертикальные и горизонтальные смещения.
С помощью нейросети мы нашли необходимое смещение, что позволило добиться хороших результатов на зданиях, не имеющих заданной высоты.
В результате мы значительно сократили ручную коррекцию разметки.
Разные территории – разные дома
На Яндекс.Картах много интересных территорий и государств.
Но даже в России дома чрезвычайно разнообразны, что влияет на то, как они выглядят на спутниковых снимках.
Это означает, что разнообразие должно быть отражено в наборе данных.
Более того, изначально мы не очень понимали, как правильно справиться со всем этим великолепием.
Собрать огромный набор данных и затем обучить на нем одну сеть? Сделать свой датасет для каждого (условного) типа разработки и обучать отдельную сеть? Обучить определенную базовую сеть, а затем обучить ее конкретному типу разработки? 
Экспериментальным путем мы выяснили, что:
- Несомненно, необходимо расширить набор данных для разных типов зданий, на которых планируется использовать инструмент. Сеть, обученная на одном типе, способна идентифицировать здания другого типа, хотя и очень плохо.
- Лучше обучать одну большую сеть на всем наборе данных.
Он довольно хорошо распространяется на разные территории.
Если обучать отдельные сети для каждого типа разработки, качество либо останется прежним, либо едва улучшится.
Поэтому нет смысла реализовывать разные сети для разных территорий.
Кроме того, для этого требуется больше данных и дополнительный классификатор типа здания.
- Если вы используете старые сети при добавлении к данным новых территорий, сети обучаются гораздо быстрее.
Дополнительное обучение старых сетей на расширенных данных приводит примерно к тому же результату, что и обучение сети с нуля, но требует гораздо меньше времени.
Варианты решения
Семантическая сегментация
Семантическая сегментация является достаточно хорошо изученной проблемой.После появления статьи Полностью сверточные сети В основном она решается с помощью нейронных сетей.
Остается только выбрать сеть (мы рассматривали ФКН , СегНет И UNet ), подумаем, нужны ли нам на выходе дополнительные трюки типа CRF, и решим, как и с какой функцией ошибок будет проходить обучение.
В результате мы остановились на архитектуре типа U-Net с универсальная функция Intersection Over Union как функция ошибки.
Для обучения спутниковые снимки и соответствующая разметка (разумеется, растрированная) разрезались на квадраты и собирались в датасеты.
Получилось довольно красиво, а местами просто великолепно.
В районах с одиночной застройкой семантической сегментации было достаточно для перехода к следующему этапу – векторизации.
Там, где застройка плотная, дома иногда слипаются в единую территорию.
Необходимо было их разлучить.
Обнаружение края
Чтобы справиться с этой задачей, можно найти края на изображении.Для обнаружения ребер мы также решили обучить сеть (алгоритмы поиска ребер, не использующие нейронные сети, явно остались в прошлом).
Мы обучили сеть типа HED, которая описана в работе Целостное обнаружение границ .
В оригинальной статье сеть обучалась на наборе данных BSDS-500, в котором были помечены все края изображений.
Обученная сеть находит все четко очерченные края: границы домов, дорог, озер и т. д. Этого уже было достаточно для разделения близлежащих зданий.
Но мы решили пойти дальше и использовать для обучения тот же набор данных, что и для семантической сегментации, только при растеризации мы не раскрашиваем полигоны здания целиком, а рисуем только их границы.
Результат оказался настолько потрясающе красивым, что мы решили векторизовать здания прямо по краям, полученным из сети.
И это сработало весьма хорошо.
Обнаружение вершин
Поскольку сеть HED дала отличные результаты на ребрах, мы решили обучить ее обнаружению вершин.Фактически мы получили сеть с общими весами на сверточных слоях.
У нее было два выхода одновременно: для ребер и для вершин.
В результате мы сделали еще один вариант векторизации зданий, и в некоторых случаях он показал вполне приемлемые результаты.
Маска R-CNN
Маска R-CNN Это относительно новое расширение сетей типа Faster R-CNN. Маска R-CNN ищет объекты и выделяет маску для каждого из них.В результате мы получим не только ограничивающие дома прямоугольники, но и изысканную структуру.
Этот подход выгодно отличается от простого обнаружения (мы не знаем, как расположено здание внутри прямоугольника) и от обычного сегментирования (несколько домов могут склеиться в один, и непонятно, как их разделить).
С Mask R-CNN вам больше не нужно думать о дополнительных хитростях: достаточно векторизовать границу маски для каждого объекта и сразу получить результат. Есть и минус: размер маски объекта всегда фиксирован, т.е.
для больших зданий точность разметки пикселей будет низкой.
Результат Mask R-CNN выглядит так: 
В последнюю очередь мы пробовали Mask R-CNN и обнаружили, что для некоторых типов разработки этот подход превосходит другие.
Векторизация
Векторизация с помощью прямоугольников
При всем современном архитектурном разнообразии дома на спутниковых снимках все же чаще всего выглядят как прямоугольники.При этом большинство территорий не требуют разметки сложными полигонами.
Но я все равно хочу, чтобы дома были отмечены на карте.
(Ну, например, садоводческое товарищество: домов там обычно много, вручную размечать их не так актуально, а вот разметить прямоугольниками на карте - очень хорошо.
) Поэтому первый подход к векторизации был предельно простым.
.
- Берем растровую область, соответствующую «дому».
- Находим прямоугольник минимальной площади, содержащий эту площадь (например, так: OpenCV::minAreaRect ).
Проблема решена.
Однако алгоритм достаточно прост и работает во многих случаях.
Векторизация с помощью полигонов
Если качество сегментации достаточно хорошее, контур дома можно воссоздать более точно.Большинство зданий сложной формы имеют в основном прямые углы, поэтому мы решили свести задачу к задаче построения многоугольника с ортогональными сторонами.
Решая ее, мы хотим достичь сразу двух целей: найти простейший полигон и максимально точно повторить форму зданий.
Эти цели противоречат друг другу, поэтому приходится вводить дополнительные условия: ограничение минимальной длины стен, максимального отклонения от площади растра и т. д. Алгоритм, который первым пришел нам в голову, был основан на построении проекции точек на прямые:
- Найдите контур растровой области, соответствующий одному дому.
- Уменьшите количество точек контура, упростив его, например Алгоритм Дугласа-Пекера .
- Найдите самую длинную сторону контура.
Именно его угол наклона будет определять угол всего будущего ортогонального многоугольника.
- Постройте проекцию от следующей точки контура на предыдущую сторону.
- Продлите сторону до точки проекции.
Если расстояние от точки до ее проекции больше, чем самая короткая стена здания, добавьте полученный отрезок к контуру здания.
- Повторяйте шаги 4 и 5, пока цепь не замкнется.
Этот алгоритм чрезвычайно прост и быстро дает результаты, но все же контур здания иногда получается довольно зашумленным.
Пытаясь разобраться с этой проблемой, мы столкнулись с довольно интересной вариант решения задача, которая использует квадратную сетку в пространстве для аппроксимации многоугольника.
Кратко описанный алгоритм состоит из трех этапов:
- Постройте квадратную сетку в пространстве с центром в нуле.
- В точках сетки, расположенных не дальше определенного расстояния от исходного контура, постройте различные многоугольники.
- Выберите многоугольник с минимальным количеством вершин.
Поскольку требуемый угол поворота сетки заранее неизвестен, приходится перебирать несколько значений, что плохо сказывается на производительности.
Однако алгоритм позволяет добиться более визуально красивых результатов.
Улучшенная векторизация
До сих пор мы фактически работали с каждым домом отдельно.Когда первый этап пройден, можно работать с картинкой в целом и улучшать результат. Для этого был добавлен алгоритм постобработки набора полигонов.
Мы использовали следующие эвристики:
- Обычно стены соседних домов параллельны.
Более того: чаще всего дома можно объединять в комплексы, внутри которых все элементы выровнены.
- Если на изображении уже отмечены улицы, то весьма вероятно, что стороны многоугольников будут параллельны улицам.
- Если полигоны пересекаются, то, скорее всего, имеет смысл переместить стены, чтобы пересечение исчезло.
- Группируем найденные дома по расстоянию между ними и углу поворота.
Мы усредняем ротацию зданий в каждом кластере.
Повторяем до тех пор, пока положение зданий не перестанет меняться или пока дома не начнут слишком сильно отклоняться от первоначального положения.
- Выбираем дома возле дорог, находим сторону, которая длиннее и ближе всего к дороге.
Вращаем дом до тех пор, пока выбранная сторона и дорога не станут параллельными.
- Убираем пересечения между полигонами, сдвигая стороны двух пересекающихся зданий пропорционально размеру сторон.
Результат
В результате мы получили инструмент, способный распознавать здания различного типа застройки.Он помогает картографам в их непростой работе: существенно ускоряет поиск пропущенных домов и заполнение новых, еще не обработанных территорий.
На данный момент с помощью этого инструмента на Народную карту добавлено более 800 тысяч новых объектов.
Ниже вы увидите несколько примеров распознавания.
Теги: #Машинное обучение #Алгоритмы #искусственный интеллект #Яндекс #Обработка изображений #нейронные сети #компьютерное зрение #Яндекс.
карты #компьютерное зрение
-
Тесла, Никола
19 Oct, 24 -
Яндекс.картинки: Время Перемен
19 Oct, 24 -
Что Нового В Gecko 1.9
19 Oct, 24
