Введение
Задача автоматического распознавания дорожных знаков на изображении приобретает все большую актуальность. На сегодняшний день существуют проекты по разработке автономных автомобилей, такие как 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 четырёхугольников, в числе которых присутствует искомый дорожный знак.
Дальнейшие исследования могут включать в себя отсеивание дорожных знаков по внутреннему содержимому четырехугольников методами машинного обучения.