company_banner

Как превратить спутниковые снимки в карты. Компьютерное зрение в Яндексе

    Один из главных источников данных для сервиса Яндекс.Карты — спутниковые снимки. Чтобы с картой было удобно работать, на снимках многоугольниками размечаются объекты: леса, водоёмы, улицы, дома и т. п. Обычно разметкой занимаются специалисты-картографы. Мы решили помочь им и научить компьютер добавлять многоугольники домов без участия людей.

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


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

    Задачу семантической сегментации сейчас решают различные сети (FCN, SegNet, UNet и т. п.). Надо только выбрать, какая из них лучше нам подходит.

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

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

    Итак, вырисовывалась такая схема:


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

    Инструменты


    Затем следовало определиться с инструментами. Здесь всё было достаточно очевидно: для задач компьютерного зрения лучше всего подходит OpenCV. Выбор нейронных сетей несколько шире. Мы остановились на Tensorflow. Её плюсы:

    • достаточно развитый набор готовых «кубиков», из которых можно собирать свои сети;
    • Python API, удобный для быстрого создания структуры сети и для тренировки;
    • натренированную сеть можно использовать в своей программе через C++ интерфейс (сильно небогатый по сравнению с Python-частью, но вполне достаточный для запуска готовых сетей).

    Для тренировок и прочих тяжёлых вычислений планировали применять Нирвану — чудесную платформу Яндекса, о которой мы уже рассказывали.

    Датасет


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

    Уточнение датасета


    Когда человек ищет дома на спутниковом снимке, то первым делом он замечает крыши. Но высота домов различается, спутник может снять одну и ту же местность с разных углов — и если мы поместим на векторную карту многоугольник, соответствующий крыше, то нет гарантий, что при обновлении снимка крыша не уедет. А вот фундамент врыт в землю и, с какого угла его ни снимай, всё время остаётся на одном месте. Именно поэтому дома на векторной Яндекс.Карте размечены «по фундаментам». Это правильно, но для задачи сегментирования снимков лучше научить сеть искать крыши: надежда, что сетка натренируется распознавать фундаменты, очень невелика. Поэтому в датасете всё должно быть размечено по крышам. Значит, чтобы создать хороший датасет, нам надо научиться сдвигать векторную разметку домиков от фундаментов к крышам.

    Мы пробовали и не сдвигать, но качество получалось очень не очень, и это понятно: углы съёмки спутника разные, высоты домов разные, в итоге на фотографиях фундамент смещался в разные стороны и на разное расстояние от крыши. Сеть теряется от такого разнообразия и в лучшем случае тренируется на что-то среднее, в худшем — на что-то непонятное. Причём сеть для семантической сегментации выдаёт результат, похожий на что-то приемлемое, но при поиске рёбер качество падает драматически.

    «Растровый» подход


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


    «Геометрический» подход


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



    «Ручной» подход


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

    Нейронная сеть


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

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


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


    Разные территории — разные дома


    На Яндекс.Картах есть множество интересных территорий и государств. Но даже в России дома крайне разнообразны, что сказывается на том, как они выглядят на спутниковых снимках. Значит, надо отразить разнообразие в датасете. Причём изначально мы не очень понимали, как правильно справляться со всем этим великолепием. Собирать огромный датасет и потом тренировать на нём одну сеть? Делать свой датасет для каждого (условного) типа застройки и обучать отдельную сеть? Тренировать некую базовую сеть и потом дотренировывать её под конкретный тип застройки?


    Опытным путём мы выяснили, что:

    1. Несомненно, надо расширять датасет под разные типы застройки, на которых планируется применять инструмент. Сеть, обученная на одном типе, способна выделять здания другого типа, хотя очень некачественно.
    2. Лучше тренировать одну большую сеть на всём наборе данных. Она довольно хорошо обобщается на различные территории. Если обучать отдельные сети для каждого типа застройки, качество либо останется прежним, либо едва-едва повысится. Так что внедрять разные сети для разных территорий бессмысленно. К тому же это требует большего количества данных и дополнительного классификатора типа застройки.
    3. Если использовать старые сети при добавлении новых территорий в данные, сети обучаются значительно быстрее. Дообучение старых сетей на расширенных данных приводит примерно к тому же результату, что и обучение сети с нуля, однако требует намного меньше времени.


    Варианты решения


    Семантическая сегментация


    Семантическая сегментация — достаточно хорошо исследованная задача. После появления статьи Fully Convolutional Networks она в основном решается при помощи нейронных сетей. Остаётся только выбрать сеть (мы рассматривали FCN, SegNet и UNet), подумать, нужны ли нам дополнительные ухищрения типа CRF на выходе, и определиться, как и с какой функцией ошибки будет проходить обучение.


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


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

    Детектирование рёбер


    Чтобы справиться с этой задачей, можно найти рёбра на изображении. Для детектирования рёбер мы решили тоже обучить сеть (алгоритмы поиска рёбер, не использующие нейронные сети, явно уходят в прошлое). Тренировали сеть типа HED, которая описана в работе Holistically-Nested Edge Detection. В оригинальной статье сеть обучалась на наборе данных BSDS-500, в котором на изображениях размечены все рёбра. Обученная сеть находит все явно выраженные рёбра: границы домов, дорог, озёр и т. д. Этого уже хватало, чтобы разделить близко стоящие здания. Но мы решили пойти дальше и использовать для обучения тот же датасет, что и для семантической сегментации, только при растеризации не закрашивать многоугольники зданий целиком, а отрисовывать лишь их границы.

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


    Детектирование вершин


    Поскольку сеть типа HED дала отличный результат на рёбрах, мы решили натренировать её же для обнаружения вершин. Фактически у нас получилась сеть с общими весами на свёрточных слоях. У неё было два выхода одновременно: для рёбер и для вершин. В итоге мы сделали ещё один вариант векторизации зданий, и в некоторых случаях он показывал вполне вменяемые результаты.


    Mask R-CNN


    Mask R-CNN — это относительно новое расширение сетей типа Faster R-CNN. Mask R-CNN ищет объекты и выделяет для каждого из них маску. В результате для домов мы получим не только ограничивающие прямоугольники, но и уточнённую структуру. Этот подход выгодно отличается от простого детектирования (мы не знаем, как здание расположено внутри прямоугольника) и от обычной сегментации (несколько домов могут склеиться в один, и непонятно, как их разделять). С Mask R-CNN уже не надо думать о дополнительных ухищрениях: достаточно векторизовать границу маски для каждого объекта и сразу получить результат. Есть и минус: размер маски для объекта всегда фиксированный, т. е. для больших зданий точность разметки пикселей будет низкой. Результат работы Mask R-CNN выглядит так:


    Мы попробовали Mask R-CNN последним и убедились, что для некоторых типов застройки этот подход выигрывает у других.

    Векторизация


    Векторизация прямоугольниками


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

    1. Берём растровую область, соответствующую «дому».
    2. Находим прямоугольник минимальной площади, который содержит эту область (например, вот так: OpenCV::minAreaRect). Задача решена.

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

    Векторизация многоугольниками


    Если качество сегментации достаточно хорошее, можно более точно воссоздать контур дома. У большинства зданий сложной формы углы в основном прямые, поэтому мы решили свести задачу к задаче построения многоугольника с ортогональными сторонами. Решая её, мы хотим добиться сразу двух целей: найти наиболее простой многоугольник и как можно точнее повторить форму зданий. Эти цели конфликтуют между собой, поэтому приходится вводить дополнительные условия: ограничивать минимальную длину стен, максимальное отклонение от растровой области и т. д.

    Алгоритм, который первым пришёл нам в голову, был основан на построении проекции точек на прямые:

    1. Найти контур растровой области, соответствующий одному дому.
    2. Сократить количество точек в контуре, упростив его, например алгоритмом Дугласа-Пекера.
    3. Найти самую длинную сторону в контуре. Именно её угол наклона определит угол всего будущего ортогонального многоугольника.
    4. Построить проекцию из следующей точки контура на предыдущую сторону.
    5. Продлить сторону до точки проекции. Если расстояние от точки до её проекции больше самой короткой стены здания, добавить получившийся отрезок в контур здания.
    6. Повторять пункты 4 и 5, пока контур не замкнётся.


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

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


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


    Улучшение векторизации


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

    • Обычно стены рядом стоящих домов параллельны. Более того: чаще всего дома можно объединить в наборы, внутри которых все элементы выравнены.
    • Если на снимке уже размечены улицы, то весьма вероятно, что стороны многоугольников будут параллельны улицам.
    • Если многоугольники пересеклись, то, скорее всего, есть смысл подвигать стены, чтобы пересечение исчезло.

    В результате появился такой алгоритм:

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

    Результат


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

    Ниже вы увидите несколько примеров распознавания.








    Яндекс
    575,00
    Как мы делаем Яндекс
    Поделиться публикацией

    Комментарии 34

      0
      del
        +1
        неправильно комментируете и вот :)
          +2
          Да я просто передумал разводить срач на ровном месте.
        0
        Интересно Народную карту модераторы контролируют или АИ проверяет изменения. Рисую свалку — её не утверждают.
          0

          На ручном приводе асессорами, по-крайней мере такая отбивка приходила на почту после подтверждения моей правки.

          +1
          Вот бы нам, в OSM такой инструмент. Хотя бы как плагин к josm. эх…
            0
            В OSM было много докладов на эту тему. В этом году и Microsoft делал, и Facebook и еще пару разных проектов. Проблема всегда одна: кто будет адреса пилить?
            В Америке домики отрисованы, но смысл без адреса почти нулевой.
              0
              А когда дому присваивают кокой-то адрес, он в каких документах появляется? Может быть эти документы есть в публичном доступе? Тогда можно использовать другую нейросеть и распарсить какой-нибудь канцелярит. Потом соотнести его с существующими реалиями и выяснить о каком доме идёт речь.
                0
                В России адреса можно поставить по кадастровой карте. Так же есть APIб которое возвращает кадастровый адрес по координатам.

                  0
                  Проблема всегда одна: кто будет адреса пилить?
                  Как минимум в MAPS.ME при наличии отрисованного здания у человека появляется возможность изменить/добавить адрес. Это не массовые правки, но уже что-то.
                    0
                    Я на дачах разметил линии номерами и центральные улицы назвал именами дачных массивов все председатели именно так и рисуют на планах, но кому то не понравилось рефы улиц и их выпилили.Кстати Павел Гурдэ не заморачивался поиском топонимов а тракты просто нумеровал, в Верном только в 1957 году стали улицам давать имена улицам до этого были № квартала как в Порт Артуре.
                    +1
                    Чтобы задать адрес, домик уже должен быть. Не представляете как сложно собирать адреса когда домов нет/частично есть. Потом разбирать записи и выяснять какому из домов соответствует заметка — гораздо сложнее. Хуже только в чистом поле без дорог и домиков пытаться что-то сделать.
                      0
                      адрес может присваиваться не только домику но и участку земли.
                        0
                        Я к тому что точку в пяти метрах от себя не все могут найти на экране смартфона, когда там нет ничего. А когда потом ещё выясняется, что GPS мобильника тебя держал на 20 метров левее (или кто-то рисовал дороги по спутнику без коррекции смещения снимка) — и подавно. А так хоть с реальностью есть возможность сопоставить.
                      0
                      > смысл без адреса почти нулевой

                      смысл? Ну например в «векторизации» Генштаба )))
                      0
                      Согласен, что было бы здорово. При этом, я постоянно везде пишу, что контуры домов — наименее приоритетные объекты на карте. Ну, после крышек люков, наверное. Главное — их параметры: адрес, этажность. Этого ни с какого спутникового снимка не получишь, и именно для таких данных яндекс сделал «народную карту», а не полагается на автоматику.
                      0

                      Не пробовали использовать GAN для "предобработки" изображений?
                      image

                        0
                        GAN'ы в этой задаче пока не использовали.
                        «Карты», которые выдает генератор в Pix2Pix, выглядят довольно красиво, но их также придется дополнительно обработать, чтобы получить векторизованные здания, а это, кажется, еще более сложная задача, чем обработать семантическую сегментацию.
                        Есть множество работ, в которых GAN'ы используются для улучшения качества семантической сегментации. Например, вот эта Semantic Segmentation using Adversarial Networks. Возможно, стоит попробовать их.
                          0
                          Я как раз и говорил про «предобработку» изображения
                          Хотя кажется, что можно сделать ту же самую сегментацию и на картинках после Pix2Pix :)
                            0
                            Сложная схема получается, но такой эксперимент выглядит достаточно интересно. Можно попробовать :)
                        +3
                        Увидел тему, изображение и сначала не понял, что моя курсовая работа времен института (Разработка методов распознавания городской застройки по аэрофотоснимкам) делает в блоге Яндекса, ну очень уж похоже :D

                        image

                        Правда меня в дипломе интересовала больше скорость распознавания и возможность использования алгоритмов в реалтайме, потому что целевая задача была иной и я не рассматривал возможность использования нейросети. Тем не менее, результаты точности распознавания в статье прекрасны, я впечатлен)
                          0
                          Действительно, похоже. Видимо, зеленый цвет лучше всего смотрится на спутниковых снимках :)
                          А какие методы для распознавания Вы использовали? Расскажите, пожалуйста, очень интересно.
                            +6
                            Так как главная актуальность в дипломе была определена, кажется, как «определять местоположение по зданиям», а вторичная — «искать изменения городской местности со временем», то у меня использовались не особо интересные методы с современной точки зрения (ну и, конечно, тот факт, что времени на все это было в обрез, тоже повлиял). Первый способ подходил вообще только для зданий, которые просто были внесены в базу вручную, это достаточно сильное отклонение от темы, но выглядело это примерно так:

                            image

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

                            Второй мой алгоритм ближе к теме, но гораздо более прост и неточен, чем те, что описываются в статье:

                            image

                            Сначала выделяются контура алгоритмом Line Segment Detector (он быстрее и лучше, чем использовать Canny edge detector или Hough Transform), потом линии достраиваются и, наконец, проходят простой фильтр наличия отрезков на всех изначально обнаруженных и достроенных сторонах, в принципе это все, на что меня хватило на тот момент. Прямоугольные здания, конечно, распознавались очень неплохо, чего нельзя было сказать про сложные строения, ну зато это происходило достаточно быстро. Думаю, если бы покопался подольше, поискал нужные фильтры, добавил бы полигональный билдер какой-нибудь, это все работало повеселее :D
                              0
                              Прям, получилась статья в статье, чтобы читая статью мы могли читать статью.

                              image
                          0
                          Писал магистерскую — так и не дошел до выделения отдельных зданий.
                            0
                            А на чем закончили?
                              0
                              Там было больше про спектральные индексы:
                              Разделение на растительность, почву, воду и искусственные объекты. Определение изменений состояния растительности. Поиск изменений формы областей, занимаемых растительностью, почвой и т.д. Ну и все в таком духе.
                              Закончил на разделении области искусственных объектов методом k-средних.
                              image
                              image
                              image
                              А до алгоритма, который точно бы указывал — здание это или нет, не дошло.
                            0
                            Пробовал как-то unet для поиска трещин на фото стекол, к сожалению эта сеть плохо работает, если классы на выходе (черные и белые) сильно не сбалансированны (трещин мало и они тонкие), что с этим делать — не понятно.
                              +1
                              а какую функцию потерь Вы использовали?
                                +1
                                Работает отлично, только учить надо не под BCE, а под смесь Focal + Dice, например, или под что-то подобное.
                                0
                                Хотелось бы посмотреть распознанное изображение вида сверху материнской платы.
                                Там тоже свои конденсаторы — высотки и слоты — панельные многоквартирники
                                  0

                                  Изображение справа тоже сегментировано Mask R-CNN? Удивительно, что у вас получилось выделить плотно расположенные однотипные объекты. В моих попытках для таких случаев region proposal network обучить не удавалось, но сеть маски работала очень хорошо.
                                  image

                                    0
                                    Для такой плотной застройки более хороший результат показала комбинация семантической сегментации и детектирования ребер, но и Mask R-CNN тут тоже не безнадежен :)
                                    0
                                    3. Найти самую длинную сторону в контуре. Именно её угол наклона определит угол всего будущего ортогонального многоугольника.

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

                                    Делал ортогонализатор как раз для домов (на C, на Java), пришёл к выводу, что перебор и самая длинная сторона — не лучшие способы. В итоге сделал через доворот (шагами по 90 градусов) всех векторов контура внутрь сектора 90 градусов, умножение длин векторов на их квадрат и сложение всех векторов. Суммарный вектор даёт базовое направление, но чтобы избежать проблем на границе сектора приходится считать 2 варианта — для секторов -45..+45 градусов и 0..90 градусов, и выбирать какой даёт меньшее отклонение контура.
                                    Далее проецируем все вектора контура на базовое направление или ортогональное.

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

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

                                    Самое читаемое