Хабрахабр

Знаки свыше: как мы избавили картографов от лишней работы и красных глаз

image

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

Что такое Fiji и зачем в нём знаки

Fiji — картографический редактор, который мы разрабатываем для наших ГИС-специалистов. Это классическое клиент-серверное приложение. На хабре уже есть несколько статей, в которых мы рассказываем про Fiji:

Как собирали знаки раньше

В Fiji есть специальный режим работы для сбора и актуализации знаков. В этом режиме картограф может открыть видео, записанное видеорегистратором. В отдельном окне отображается само видео, а на карте отображается его трек. Маркером показана текущая позиция.
image
Поверх видео нанесена сетка — она позволяет определять расстояние до знака. Как только знак становится размером с ячейку, картограф делает паузу и создаёт знак. Мы в этот момент знаем текущую позицию и расстояние до знака, поэтому сдвигаем его вперёд и притягиваем к звену. Звено в нашей терминологии — это схематичное изображение участка дороги. У каждого знака есть свой числовой код, его картограф вносит в специальное поле.

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

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

Как собираем теперь

Нам по-прежнему нужны видео с регистраторов. Но теперь, вместо того, чтобы отсматривать каждое, картограф просто выбирает нужные файлы и жмёт кнопку «Загрузить». После этого он может заниматься другими делами — видео обработается и на карте появятся дорожные знаки. Разные сомнительные случаи будут специально отмечены. Поэтому всё, что остаётся картографу — пройтись по этим случаям и исправить их.

Архитектура

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

Сервис отправляет файл в хранилище, делает об этом запись себе в БД и создаёт задачи на его обработку. Первым идёт VideoPreprocessingService — именно туда загружается видеофайл. Сделано это для того, чтобы можно было легко менять количество этих самых воркеров. Нужно вырезать из видео кадры с определённой частотой, подобрать для них GPS-точки из трека, отправить результат работы на Frames Processing service.
Первые две задачи выполняет не сам сервис, а Worker. Увеличивая тем самым производительность, если есть такая потребность.

А ещё он выгружает кадры в очередь. FrameProcessingService сохраняет себе все полученные кадры и точки. Он распознаёт дорожные знаки. Её читает сервис, который написали наши коллеги — специалисты по Machine Learning. Зная размер прямоугольника, мы понимаем расстояние до знака. Само собой, FrameProcessingService читает и ответы от этого сервиса — это коды знаков, если они есть на кадре, и прямоугольники, в которые вписан этот знак. А когда все кадры из видео обработались — он отправляет их на наш карт-сервер.

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

Общее описание

Наши картографические данные — это геообъекты. Геообъект — это геометрия (то есть расположение объекта в пространстве) и набор атрибутов. Их мы храним в БД и ими оперируем. Но от FrameProcessingService мы получаем только код знака, координаты точки, из которой распознали знак, сам кадр и маску знака на этом кадре. А значит нам нужно превратить этот набор данных в геообъект. Каждый геообъект принадлежит к какому-то классу. Каждый вид дорожных знаков — это отдельный класс. Его мы без проблем можем получить из кода знака. Ещё из кода знака мы можем получить специфичные для этого класса атрибуты. Например нам пришёл код 3_24_60. 3_24 — говорит, что это ограничение скорости (знак 3.24 в ПДД). Для этих знаков должно быть указано значение ограничения. Его нам сообщает третья часть кода — здесь это будет 60 км/ч.

Казалось бы, уже можно создать геообъект. Итак, класс геообъекта определён, специфичные для него атрибуты тоже. Во-первых, каждый знак имеет атрибут «Направление», который говорит, в каком направлении действует знак. Но пока ещё рано. У нас есть точка, из которой мы знак увидели. Во-вторых, у нас всё ещё нет геометрии для этого геообъекта. Кроме того, его геометрия влияет на значение атрибута «Направление». А значит, сам знак находится на каком-то удалении от нас.

Конечно же, у нас есть дорожная сеть. image
Здесь сделаем небольшое отступление. Каждое звено — это линия. Она состоит из отдельных звеньев. Стрелками показано направление, в котором они были отрисованы, т.е. На первой части рисунка у нас как раз нарисовано два звена. Направление движения — это отдельный атрибут, оно не равно направлению отрисовки. левое рисовали снизу вверх, а правое — сверху вниз.
Каждое звено несёт информацию о том, в каком направлении по нему можно двигаться. На второй части рисунка оба звена имеют одинаковое значение этого атрибута, а на третьем рисунке — противоположные значения. Этот атрибут говорит нам о том, в каком направлении можно двигаться по звену, относительно направления отрисовки.

Итак, мы двигаемся по звеньям снизу вверх, и видим какой-то знак. Как это связано со знаками? такие же, как и звенья на третьем рисунке. Так вот, на левом звене знак будет иметь направление «Только прямо», на правом — «Только обратно», т.е. В реальности же очень большое количество звеньев являются двусторонними, т.е. Здесь всё получилось просто, но это потому, что звенья у нас односторонние. А знак всегда направлен в какую-то одну сторону, и нам нужно понимать — в какую. их направление имеет значение «В обе стороны».

Map matching

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

Это позволит решить сразу ряд проблем:

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

Алгоритм

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

Алгоритм никак не учитывал направления на дорожных звеньях, поэтому первое, что мы сделали — начали их учитывать: теперь, если звено одностороннее, мы понимаем, с каким направлением мы должны по нему двигаться. В процессе работы мы внесли в алгоритм несколько дополнений. И если это направление не совпадает с направлением звена — мы это звено отбрасываем.

Но потом мы начали проверять видео, записанные в жилых кварталах, и всё оказалось не так радужно. Изначально нам казалось, что этого будет достаточно, и первые тесты это подтверждали. Соответственно, у нас отрисованы все внутриквартальные проезды, вплоть до мельчайших деталей. Дело в том, что у нас очень высокая точность данных, в том числе и по дорогам. А если ехать по дороге, вокруг которой высокие здания, то точки в треке могут уехать довольно сильно. С другой стороны — как я уже говорил, GPS может быть не очень точным или даже очень неточным. В результате получается, что многие точки находятся близко к тем дорогам, по которым мы не ехали. Бывало, что точки съезжали в сторону более чем на 20 метров. Следовательно, скорее всего, в большинстве случаев автомобиль двигался по основным улицам. Итогом усадки таких треков была вот такая картина:
image
Здравый смысл подсказал нам, что на таких дорогах знаков мало, а потому собирать их там особого смысла нет. Под штрафом мы понимаем уменьшение количества очков у дороги. Поэтому для внутриквартальных проездов мы ввели штраф. В итоге проблема с внутриквартальными проездами была решена — они не выбирались, когда мы по ним не ехали, а когда по ним реально ехали, то даже несмотря на штраф, они оказываются наилучшим вариантом и тогда мы их выбираем.

И нам казалось, что с мапматчингом покончено. После этого результаты стали уже совсем хороши. Совершенно внезапно оказалось, что есть случаи, когда от дороги ответвляется другая дорога, причём делает это очень плавно. Но беда пришла, откуда не ждали. При этом, напоминаю, GPS-трек практически никогда не находится поверх звеньев, по которым мы ехали, он немного смещён в какую-то сторону от него. А усугубилось всё тем, что ответвившаяся дорога может ещё и идти параллельно с нашей, по крайней мере, какое-то время. Из-за чего в лучшем случае мы получали несколько звеньев, по которым на самом деле не ехали. Ну и конечно же, благодаря этому всему, алгоритм стал цеплять эти ответвления. Берём предыдущую и следующую точки GPS-трека относительно точки, из которой мы выбрали звено. А в худшем — усаживали трек совсем неправильно.
image
Поэтому мы придумали делать дополнительную оценку дороги. Если же отличается сильно — штрафуем это звено. И смотрим, чтобы азимут в этих точках не слишком сильно отличался от азимута движения по этому звену.

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

Расстановка знаков

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

Первым делом надо получить дополнительную информацию, которая нам поможет поставить знак в нужное место:

  1. Азимут знака. Если знак расположен точно по центру кадра, он совпадает с азимутом в GPS-точке. Если знак не по центру — это азимут в точке + угол между центром кадра и знаком. Азимут GPS-точки у нас уже есть, а угол между центром кадра и знаком мы можем посчитать, т.к. знаем, где расположена маска знака на кадре и знаем угол обзора, с которым было записано видео.
  2. Расстояние до знака из GPS-точки. Его можем вычислить, т.к. знаем размеры маски знака, разрешение кадра и угол обзора, с которым записано видео.

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

  1. Среди дорог, на которые был усажен трек, оставляем только те, которые пересекают какой-то буфер вокруг нашей GPS-точки;
  2. Вычисляем расстояние до каждой выбранной дороги и сортируем их по его возрастанию;
  3. Берём дорогу, вычисляем проекцию GPS-точки на неё;
  4. Получаем направление, с которым мы двигаемся в этой точке по этой дороге;
  5. Если направление из п.4 недопустимо на этой дороге, то возвращаемся в п.3 и берём там следующую дорогу;
  6. Если направление допустимо, то останавливаемся.

На самом деле, эта дорога, а значит и точка, могут быть выбраны неверно. Теперь у нас есть дорога, по которой мы ехали, когда ставили GPS-точку, и проекция этой точки на нашу дорогу. Либо, если ошиблись, заменить дорогу на верную и получить проекцию на неё. Например при поворотах очень легко ошибиться.
image
Поэтому, прежде чем двигаться дальше, надо убедиться, что мы не ошиблись. В результате получим дорогу, которая лучше всего подходит для данной точки и построим проекцию на неё. Для этого возьмём дороги, которые соединяются с нашей дорогой и оценим их по расстоянию и азимуту.

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

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

Мерж знаков

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

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

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

Если в этом наборе есть уже существующий геообъект — оставить только его и отметить, что он был актуализирован. Что нам требуется с ними сделать: нужно понять по их классам, атрибутам и геометриям, что какой-то набор этих геообъектов — это один и тот же знак. Если в наборе только новые геообъекты — оставить только один из них.

Делаем мы это в четыре шага:

  1. Группируем геообъекты по их классу;
  2. В каждой группе из шага 1 получаем группы по атрибутам;
  3. Для каждой группы из шага 2 собираем группы по геометриям;
  4. Если в группе из шага 3 есть существующий знак — оставляем только его (если их несколько — то оставляем их все), а если существующих знаков в группе нет — оставляем тот, что стоит в середине.

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

Ближайшие планы

Знаки с боковых дорог

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

Например, ограничение скорости 5км/ч вряд ли будет стоят на магистрали, зато очень вероятно оно будет стоять на въезде на АЗС. Для решения проблемы планируем использовать ряд семантических правил при постановке знака на звено.

Трекинг знаков

Иногда мы недомерживаем знаки, а иногда наоборот — мержим знаки, которые мержить не надо. Поэтому планируем сделать трекинг знаков по кадрам — чтобы узнавать один и тот же знак на разных кадрах ещё до того, как мы превратим их в геообъекты. И использовать это знание при мерже.

Заключение

Текущая версия — это, по сути, бета. Поэтому она неидеальна. Есть проблемы, которые мы собираемся решать в ближайшее время. Есть проблемы, которые пока непонятно как решить. А есть такие, которые вообще вряд ли получится решить с помощью алгоритмов. Например, GPS-треки могут быть очень плохого качества. Или видео, где изображение и трек рассинхронизированы — и это можно понять, только посмотрев его. В общем, задача оказалась гораздо сложнее, чем мы изначально рассчитывали.

А значит, будем решать. Перед нами огромное поле для решения различных проблем. Ну и конечно, рассказывать, если наткнёмся на что-то интересное.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть