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

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

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

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

• UI в Enterprise-приложении, или как мы делали удобную систему для создания карт
• Как мы делаем карту для тех, кто делает карту
• Бесконечная локализация, или как мы переводим карту в режиме реального времени

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

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



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

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

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

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

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

Архитектура

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

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

Первые две задачи выполняет не сам сервис, а Worker. Сделано это для того, чтобы можно было легко менять количество этих самых воркеров. Увеличивая тем самым производительность, если есть такая потребность.

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

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

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

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

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



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

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

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

Map matching

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

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

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

Алгоритм

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

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

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


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

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



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

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

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

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

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

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

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

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

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



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

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

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

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

Мерж знаков

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

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

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

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

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

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

После этого у нас остаётся нужное количество знаков, которые наконец-то можно сохранить.



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

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

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

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

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

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

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

Заключение

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

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