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

Меня зовут Владимир Быстрицкий, я работаю в группе AI-картографирования. В этой статье расскажу о процессе детектирования дорожных знаков в картопроизводстве Яндекса: с чего всё началось, как развивалось, какие технологии использовались. Ну и попробую ответить на самый, на мой взгляд, главный вопрос в любой ML-задаче: как собрать датасет и не разориться?

Откуда взялась идея детектировать дорожные знаки

В 2016 году в Яндекс Картах был запущен проект «Зеркала». В дополнение к панорамам появились снимки улиц, сделанные пользователями во время поездки на машине. Такие фотографии помогали и помогают картографам поддерживать актуальность данных на карте. 

Сейчас эти снимки можно увидеть и на большой карте, ткнув на кнопку с фотоаппаратом:

Выглядит это примерно вот так:

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

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

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

Первый детектор: бинарный классификатор и капля нейросетей

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

Всё у нас было устроено по классике:

Шаг 1. Тренируем бинарный классификатор, который для картинки фиксированного размера (у нас размер был 32 × 32 пикселя) даёт ответ: есть на ней объект или его нет.

Сильно погружаться не буду, но, чтобы сделать классификатор, мы тогда использовали ACFFeatures (подробности про ACFFeatures можно найти в статье от 2014 года), бинарные решающие деревья и waldboost (waldboost описан в статье аж 2005 года).

Шаг 2. Берём картинку, на которой мы хотим детектировать дорожные знаки, и превращаем её в пирамиду изображений.

По каждому изображению в пирамиде запускаем скользящее окно того же размера, что и вход нашего классификатора из первого шага, — 32×32 пикселя. Для каждого положения окна классификатор даёт ответ, является ли то, что есть внутри окна, искомым объектом или нет. 

Таким образом, на выходе имеем некоторое количество кандидатов на детекции. Учитывая, что мы бегаем скользящим окном с перекрытием, да ещё и по пирамиде масштабов, обычно на один реальный объект на фотографии мы находим несколько кандидатов, поэтому далее в действие вступает non-maximum suppression (NMS).

Шаг 3. Прогоняем кандидатов через NMS-алгоритм, склеивая дубли, — и вот они, наши знаки.

В данном конвейере самое важное — это первый пункт. И тут было два крайних варианта:

• А. Тренируем бинарный классификатор на дорожный знак вообще. То есть мы совсем не различаем дорожные знаки и просто детектируем все одним детектором — ответ «да» должен быть на любой дорожный знак.

• Б. Для каждого типа дорожного знака тренируем свой бинарный классификатор (один для знака пешеходного перехода, второй для запрета поворота налево, третий для ограничения скорости и т. д.).

Вариант Б мы сразу отвергли, потому что, даже если обрабатывать 20–30 типов знаков из 200+, которые есть в ПДД, то тренировать для каждого свой классификатор — сложно и долго. 

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

Поэтому сделали промежуточный вариант. Все знаки разбили на категории:

1. Жёлтый ромб (главная дорога, конец главной дороги и т. п.).

2. Белый круг с красной границей (запрещающие знаки).

3. Синий круг (предписывающие знаки).

4. Белый треугольник с красной границей (предупреждающие знаки).

5. Перевёрнутый белый треугольник с красной границей (уступи дорогу).

6. Белый круг с чёрной границей (конец действия знака).

7. Синий прямоугольник (парковка, односторонняя дорога и т. п.).

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

Таким образом, находить на картинке знаки дорожного движения мы научились. Но хотелось получать в качестве ответа не просто «на этой фотографии есть дорожные знаки вот в таких, таких и таких координатах», но и какие именно это дорожные знаки. Поэтому дополнительно мы натренировали простенькую свёрточную нейросеть для классификации кандидатов, которые выдавал детектор. Благо на тот момент тема с классификацией изображений свёрточными сетями уже была достаточно раскопана и пребывала на пике популярности. На вход этой сети мы подавали кроп размера 32×32 пикселя, а сама нейросеть состояла всего из трёх свёрточных слоёв. К основному набору классов дорожных знаков мы добавили класс «none», и сеть заодно исправляла ошибки детектора.

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

Выглядело это следующим образом. Допустим, на фотографии мы нашли знак ограничения скорости 50 км/ч, а на карте рядом с местом съёмки на всех дорогах ограничение 90 км/ч. Мы помещаем на карту гипотезу для картографов:

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

Второй детектор: только свёрточные нейросети

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

False positives вели к появлению лишних гипотез и, соответственно, лишней нагрузке для картографов. Например, детектор ошибся и нашёл на фотографии ограничение скорости 20 км/ч, а вокруг на карте на всех дорогах стоит ограничение 60 км/ч. Мы же на базе этой ошибки сгенерируем гипотезу, которая, очевидно, бесполезна. 

False negatives также могли приводить к тому, что мы не подсвечивали ошибки на карте: тут ситуация не симметричная, детектор может не найти как знак, который никак не влияет на карту, так и такой, который помог бы исправить ошибку.

Мы проанализировали ошибки детектора, точнее, в основном его «близорукость». Детектор на классических технологиях хорошо находил знаки, которые смотрели ему прямо в лицо, а вот если знак был слегка повёрнут — детектор его не видел.

Ничего особо неожиданного в этом не было, и способ борьбы с этой проблемой на тот момент (а это был конец 2017 года) уже был хорошо известен — надо использовать нейронные сети.

Для детектирования объектов на картинках при помощи нейронных сетей в это время применялся один из двух подходов: Faster R-CNN и Single Shot Detector. И там и там в базе использовалась свёрточная нейронная сеть, которая по изображению генерировала тензор признаков. Тензор получался меньшей пространственной размерности, чем исходное изображение (обычно в 32 раза), но при этом вместо трёх цветовых каналов (картинка на входе у нас была цветная в формате RGB) содержал 512 или 1024.

Faster R-CNN — это архитектура, которая была описана в статье и продолжала линейку R-CNN и Fast R-CNN. Модель реализовывала двухстадийный подход: вначале на базе тензора признаков специальным блоком под названием Region Proposal Network (RPN) отбирались прямоугольники — кандидаты на объекты, а затем для этих кандидатов уточнялись координаты боксов и определялись классы.

Single Shot Detector описан в статье SSD: Single Shot MultiBox Detector, он развивает идеи, заложенные в YOLO, и реализует одностадийный подход, когда, используя тензор признаков, модель просто проверяет некий заранее заданный список прямоугольников — кандидатов на объекты.

Сравнения показывали, что SSD быстрее, но Faster R-CNN показывает лучшее качество и, что было для нас немаловажно, — он намного лучше работает с небольшими объектами. Учитывая, что скорость нас не особо ограничивала, так как мы всё равно собирались запускать процесс детектирования в офлайн, мы решили натренировать Faster R-CNN.

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

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

На тот момент мы не собирались поддерживать все 200+ дорожных знаков. В основном нас интересовали те, которые непосредственно влияют на навигацию: ограничения скорости, манёвры, движение по полосам, парковки и так далее. Всего мы отобрали около 50 штук. 

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

Мы сделали два проекта в Яндекс Заданиях. Первый предлагал обвести на картинке прямоугольниками все имеющиеся знаки:

Второй показывал вырезанный из большой картинки знак, которому надо было приписать класс.

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

Каждое задание показывалось нескольким исполнителям, потом их ответы объединялись.

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

Долго ли, коротко ли, но мы собрали и разметили порядка 90 000 фотографий. Для каждого нужного нам класса в датасете было собрано не меньше 500 представителей.

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

Собрав датасет, мы натренировали детектор дорожных знаков, который поддерживал 50+ классов и показывал на них качество порядка 95%. Далее последовали улучшения качества работы детектора, а для этого мы допиливали под наши нужды модель Faster R-CNN.

Первым делом объединили все знаки скоростных ограничений в один большой класс. На первом этапе под каждое конкретное ограничение был свой подкласс — то есть в отдельном подклассе был знак ограничения 60, в другом 40, в третьем 20. Это было не очень хорошо, потому что какие-то числа встречаются постоянно, а какие-то ещё пойди найди. Затем натренировали маленькую дополнительную сетку, которая на вырезанном знаке распознавала числа. Так, основной детектор ищет знаки ограничения скорости вообще, а дополнительный уточняет конкретное ограничение.

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

Поэтому мы сложили все знаки направления движения по полосам в один класс и натренировали дополнительную модель, которая по картинке знака выдавала бинарный вектор с описанием, какие направления на этом знаке присутствуют.

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

А модель нарезала такие знаки на части, которые потом подавались в классификатор знаков полосности:

Однако мы работали только с 30% от полного набора типов знаков, которые представлены в ПДД. Ситуацию нужно было исправлять — другими словами, нужно было масштабироваться.

Расширение датасета на все знаки РФ

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

Чтобы решить эту задачу, вначале мы натренировали детектор, который искал на картинках что-то похожее на дорожный знак. Этому детектору было позволено сильно заблуждаться и принимать за знаки то, что ими не являлось, но очень сильно не ��азрешалось пропускать кого-то из кандидатов. Говоря формально, его тренировали на полноту, а не на точность. Таким образом, мы могли нарезать из наших фотографий очень большой набор изображений знаков, среди которых надо было научиться находить нужные.

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

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

Поэтому схему немного поменяли. Собственно, претендентов, эмбеддинги и косинус расстояния оставили, а вот пиктограмму выкинули. Вместо неё для каждого нового класса брали некоторое количество уже имеющихся изображений (для большинства классов в нашем датасете уже было размечено 10–20 примеров, они случайно попадались на тех фотографиях, которые собирали для других знаков) и тренировали на эмбеддингах few-shot-классификатор. С его помощью для каждого нового класса отбирался набор фотографий-претендентов, которые уже можно было отправлять в наш конвейер в Яндекс Заданиях.

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

Таким образом, окончательный вариант нашего пайплайна для добавления нового знака выглядит как-то так:

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

Подводя итоги

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

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

Сейчас в нашем датасете более 300 000 фотографий, на которых размечено более 1 500 000 знаков. При этом процесс добавления нового типа знаков отлажен, так что мы присматриваемся к обработке знаков и в других странах.

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