Введение

Задача автоматического распознавания дорожных знаков на изображении приобретает все большую актуальность. На сегодняшний день существуют проекты по разработке автономных автомобилей, такие как Google Self-Driving Car Project, AutoNOMOS Labs, а также различные системы помощи водителю. Одно из ключевых требований к подобным системам — это распознавание дорожных знаков.

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

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

На сегодняшний день существует много методов детектирования дорожных знаков. В [6] для поиска знаков, имеющих форму правильного многоугольника, используется преобразование Хафа, в котором голосование проводится за возможный центр многоугольника. Хорошие результаты показывают методы машинного обучения. В [7] используется подход, похожий на тот, что использовался для детектирования пешеходов в [2], а именно — HOG + SVM. Помимо градиента в качестве признаков изображения авторы используют несколько фильтров Габора и каналы изображения в цветовом пространстве LUV. Такой подход носитназвание — Integral channel features [4]. В результате авторам удалось достичь 90% точности детектирования.

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

В данной статье, для поиска четырёхугольников, предлагается использовать подход, предложенный в [1], но с некоторыми изменениями. В указанной статье предлагается построить граф для обнаруженных отрезков и искать четырёхугольники как всевозможные циклы из 4-х вершин в этом графе. В данной же статье, с учетом ограничений на угол наклона сторон дорожного знака, предлагается искать те циклы, которые содержат ровно два вертикальных и два горизонтальных отрезка. Таким образом, результатом работы алгоритма станут не всевозможные четырёхугольники, а лишь те, что удовлетворяют заданному условию.

Поиск четырёхугольников

Задачу поиска четырёхугольников предлагается решать при следующих ограничениях:

• знаки не имеют повреждений и деформаций,
• не закрыты посторонними объектами,
• верхняя и нижняя стороны имеют угол наклона менее , а левая и правая — более.

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

Поиск отрезков

Для поиска отрезков можно использовать алгоритм line segment detector (LSD) [5]. Он обладает достаточной точностью для исследуемой задачи, а также отличается хорошей скоростью работы, т.к. имеет линейную сложность относительно количества пикселей изображения. Ещё одним плюсом является общедоступная реализация в библиотеке OpenCV. Результат работы такого алгоритма можно видеть на рисунке Рисунок.

Рисунок 1: Пример работы алгоритма поиска отрезков: а) оригинальное изображение, б) обнаруженные отрезки

Поиск замкнутых областей

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

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

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

Если в матрице найдутся четыре ненулевых элемента с индексами , то соответствующиеточки являются точками четырехугольника.

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

Результаты

Тестирование алгоритма

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

Рисунок 2: Пример детектирования четырёхугольников, четырёхугольники обозначены красным цветом

пиксели как фоновые, то алгоритм будет ошибаться редко, т.к. площадь знака мала по сравнению с площадью фона, а значит даст высокую точность. Проблема возникает из-за того, что выборка пикселей сильно не сбалансирована. В таких случаях для измерения качества классификации предлагается использовать -метрику [3]. Если ввести следующие обозначения:

• — количество верных срабатываний в области, знака (true positive),
• — количество неверных срабатываний в области знака (false positive),
• — количество неверных срабатываний в области фона (false negative),
• — точность (precision),
• — полнота (recall),

то -метрику можно определить следующим образом .

Тестовая выборка

Для тестирования метода детектирования четырёхугольников использовалась выборка из 501 изображения, каждое из которых имеет разрешение . Каждому изображению с дорожным знаком соответствует такое же бинарное, где пиксели принимают значение 255 для области знака и 0 в противном случае. Фрагменты таких изображений приведены на рисунке Рисунок.

Так как интерес представляет качество детектирования дорожных знаков, то из всех четырёхугольников предлагается выбирать тот, что даёт максимальное значение -метрики. Соответствующая гистограмма приведена на рисунке Рисунок а. Она показывает количество дорожных знаков, которые обнаружены с той или иной точностью, измеряемой с помощью F-метрики. Большое количество дорожных знаков (386 из 521) обнаружено с хорошей точностью. Значение F-метрики для них превышает 0,9 при максимуме 1,0. На рисунке Рисунок б можно видеть гистограмму, отражающую количество детектируемых четырёхугольников на изображении. Для большинства изображений обнаружилось до 1000 четырёхугольников.

Рисунок 3: Пример изображений из размеченный выборки: а), б) изображения с дорожными знаками, в), г) их разметки

Рисунок 4: Гистограммы распределения а) значений F-метрики, б) количества обнаруженных четырёхугольников

Рисунок 5: Примеры поиска четырёхугольных знаков : а), б) F = 0.965, 0.989, в), г) F = 0.678, 0.765, д), е) F = 0.643, 0.811, ж), з) F = 0, 0

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

Заключение

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

Для тестирования предложенного алгоритма была собрана и размечена выборка из 501 изображения, а для измерения качества алгоритма была выбрана - метрика. В результате проведения эксперимента на 74% изображений было обнаружено не более 1000 четырёхугольников, в числе которых присутствует искомый дорожный знак.

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