Ю.А. Левчук, А.Г. Новиков, В.Г. Дзюба – Алгоритм нахождения линий дорожной разметки

Оригинал статьи

277

УДК 681.3

Ю.А. Левчук, А.Г. Новиков, В.Г. Дзюба

Алгоритм нахождения линий дорожной разметки

Разработан алгоритм распознавания дорожной разметки c использованием метода Осу, преобразования Хафа и отслеживания линий. Полученные результаты позволяют использовать алгоритм как основу для разработки эффективной интеллектуальной системы распознавания дорожной разметки.

The algorithm of road traffic lane detection was developed. During the development the Otsu method, Hough transformation and lane tracking method were used. Gained results allow the usage of the algorithm as a basis for development of the intellectual lane detection system.

Введение

Современный мир компьютерных систем широко использует технологии машинного, или компьютерного, зрения. В частности популярность приобретают решения, предназначенные для автомобилей, снижающие вероятность аварий и всячески облегчающие жизнь водителю. Среди таковых стоит отметить разработки «EyeQ» и «Opel Eye», которые являются комплексным решением по распознаванию разметки, дорожных знаков, пешеходов, машин и т. д.

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

Результатом интенсивной работы в данной области является множество научных исследований [1-3], некоторые из которых запатентированы в разных странах мира.

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

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

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

разметки на изображении, их отслеживание; исследование характеристик системы на тестовых изображениях.

1. Предварительная обработка изображений

Исходное цветное изображение обычно представляется в формате, где каждый пиксель зашифрован тремя значениями базовых цветов (красный, зеленый, синий) от 0 до 255 (RGB формат). Для дальнейших действий с изображением необходимо преобразовать его в формат оттенков серого (intensity format). Такое преобразование выполняется по следующей формуле [4]:

/ = 0.229R + 0.587G + 0.114B, где / - интенсивность серого, R, G, В - красная, зеленая и синяя составляющие соответственно.

Необходимость линейной фильтрации обоснована наличием множества низкочастотных помех на изображении.

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

фильтра является сумма произведений коэффициентов фильтра и соответствующих писке-лов окрестности, которые накрываются фильтрующей маской. Для маски тхп предполагается, что т = 2а + 1 и п = 2Ь + 1, где а и b - неотрицательные целые числа. Учитывая машинные затраты на наложение фильтра была подобрана простая маска М , полностью удовлетворяющая поставленной задаче: M = [-1 0 1],

где М - фильтрующая маска

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

Метод Оцу ищет порог, уменьшающий девиацию внутри класса, которая определяется как взвешенная сумма девиаций двух классов:

a2(f) = co₁(f)a₁²(f) + co₂(f)a|(f)

278 Электроника и связь. Тематический выпуск «Электроника и нанотехнологии», ч.2, 2009

Веса со, - это вероятности двух классов разделенных порогом t, а а² - девиация этих

классов. Оцу показал, что минимизация девиации внутри класса это то же самое, что и максимизация девиации между классами:

4 (0 = а² - а² (0 = _Ю₁ (0а>₂ (О Ь (0 " Ц₂ (О]² ,

которая выражается в терминах вероятности со,

и среднее арифметическое класса ц,, которое в

свою очередь может обновляться итеративно.

На основании данного подхода разработан алгоритм бинаризации изображений:

1. Вычислить гистограмму и вероятность для каждого уровня интенсивности.

2. Вычислить значения для г, и ц,-.

3. Для каждого значения порога от t = 1 до максимальной интенсивности:

1) обновляем со/ и ц/-

2) вычисляем a²(f);

3) если а больше чем имеющееся, то запоминаем а и значение порога.

4. Искомый порог соответствует максимуму

a²(f).

Оцу показал, что минимизация девиации внутри класса это тоже самое, что и максимизация девиации между классами [4]:

4 (0 = с² - а² (0 = _Ю1 (f)co₂(ОЬИ (0 " ^2С)]² ■

2. Нахождение линий на изображении.

Один из подходов к выполнению подобных действий основан на преобразовании Хафа [А].

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

Имея преобразование Хафа, возможен иной подход. В этом преобразовании используется параметрическое представление линий: р = xcos(8) + ysin(8)

Переменная р представляет собой расстояние от центра координат до линии вдоль вектора, перпендикулярного к линии. Параметр

8 представляет собой угол между осью х и этим вектором. Имея матрицу р и 8 можем

найти максимумы преобразования Хафа по следующему алгоритму:

1) найти ячейку преобразования Хафа, в которой лежит наибольшая величина, и записать ее местоположение;

2) обнулить ячейки в ближайшей окрестности положения, найденного на шаге 1;

3) повторять шаги 1 и 2 до тех пор, пока желаемое число максимумов не будет найдено или после достижения заданного порога.

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

Опытным путем было установлено, что для целей распознавания дорожной разметки пороговая длинна при размере изображения 640х480 не составляет более a = 5 .

Для использования метода Хафа, разобьем изображение на верхнюю и нижнюю части, прямые линии будем искать в нижней части изображения, так как именно туда попали интересующие нас линии разметки. Результат нахожения линий методом Хафа в среде MATLAB показан на рисунке 1 (исходные размеры фреймов 360х240).

Рис 1. Нахождение линий:а – исходное изображение (разрешение изображения: 320х240); б – бинарное изображение с найденными линиями (разрешение изображения: 320х120)

Далее производится процедура первоначального нахождения линий разметки: находятся две линии угол между которыми лежит в пределах от 25° до 50°и обе эти линии имеют угол пересечения с горизонталью от -25° до 25°.

Результат нахождения линий в среде MATLAB разметки представлен на рисунке 2.

Информационные системы и технологии

279

участок трассы Киев-Одесса протяженностью 50 км. В качестве аппаратной части использовался ноутбук Acer Aspire 6935g, который имеет следующие технические характеристики:

- процессор: Core 2 Duo T9400 2,53GHz;

- оперативная память: 4Gb DDR3;

- видеокарта: NVIDIA GeForce 9600M GT. Параметры входного сигнала были следующими:

- размер фрейма 640х480 пикселей.

- представление сигнала в формате RGB.

- частота фреймов: 25 фреймов в секунду. В результате тестирования были получены

следующие результаты:

- распознанных фреймов: 95%;

- ошибка при идентификаций линий: 5%;

- время на обработку одного фрейма: 0.25 секунды.

Вывод

В данной работе был разработан алгоритм распознавания дорожной разметки за счет решения следующих задач: получение изображения с внешнего источника и предварительная обработка, нахождение линий на изображении, отслеживание линий. Разработанный алгоритм требует для однозначного определения линии обработки не более 3 фреймов, что позволяет использовать его для распознавания в режиме реального времени. Было проведено тестирование системы в среде MATLAB с использованием видеоматериала, отснятого в реальных условиях, которое подтвердило эффективность и точность предлагаемого алгоритма.

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

Литература

1. S. Beucher, X. Yu. Road recognition in complex traffic situations. – Addison Westley, 1991. – 76 p.

2. Paetzold F., Franke U. Road recognition in urban environment. – Academic Press, 1995. – 53 p.

3. M. Foedisch, C. Schlenoff, R. Madhavan. Performance Analysis of Symbolic Road Recognition for On-road Driving. – Academic Press, 1999. – 110 p.

4. Р. Гонсалес, Р.Вудс. Цифровая обработка изображений // М.: Техносфера – 2005. – 1072с.

5. N. Otsu. A threshold selection method from gray-level histograms. – Academic Press, 1975. – 153 p.

Рис. 2. Исходное изображение с найденными линиями разметки (разрешение изображения: 320х240).

3. Отслеживание линий

Отслеживание линий разметки должно удовлетворять двум требованиям: четко определять являются ли найденные линии в каждом фрейме линиями разметки; позволять работу р реальном режиме времени.

Был разработан следующий алгоритм отслеживания линий:

1) Все найденные линии на новом фрейме проверяются на сходство с линиями разметки находящимися в «хранилище линий». «Хранилище линий» представляет собой координаты краев линий разметки на предыдущих фреймах. Схожими линиями будем считать те, расстояния между краями которых не превышают β пискелей:

где

–

координаты краев сравниваемых линий.

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

При тестировании данного алгоритма в среде MATLAB был определен параметр β =15 для изображения размером 640х480.

4. Экспериментальное исследование алгоритма распознавания дорожных знаков

Исследование точности и быстродействия алгоритма выполнялось в среде MATLAB 7.7 с использованием тестового видеоролика, на котором был заснят камерой



	Оригинал статьи	277

	УДК 681.3 Ю.А. Левчук, А.Г. Новиков, В.Г. Дзюба Алгоритм нахождения линий дорожной разметки

	Разработан алгоритм распознавания дорожной разметки c использованием метода Осу, преобразования Хафа и отслеживания линий. Полученные результаты позволяют использовать алгоритм как основу для разработки эффективной интеллектуальной системы распознавания дорожной разметки. The algorithm of road traffic lane detection was developed. During the development the Otsu method, Hough transformation and lane tracking method were used. Gained results allow the usage of the algorithm as a basis for development of the intellectual lane detection system. Введение Современный мир компьютерных систем широко использует технологии машинного, или компьютерного, зрения. В частности популярность приобретают решения, предназначенные для автомобилей, снижающие вероятность аварий и всячески облегчающие жизнь водителю. Среди таковых стоит отметить разработки «EyeQ» и «Opel Eye», которые являются комплексным решением по распознаванию разметки, дорожных знаков, пешеходов, машин и т. д. Основной операцией в работе этих систем является распознавание дорожной разметки, поскольку существует тенденция к учащению случаев выезда водителей за разметку, что приводит к возникновению ДТП. Результатом интенсивной работы в данной области является множество научных исследований [1-3], некоторые из которых запатентированы в разных странах мира. Существование коммерческих, следовательно, засекреченных вариантов решения данной проблемы и побудило авторов к разработке собственного подхода к распознаванию линий дорожной разметки. Основными моментами в распознавании разметки являются задачи нахождения линий самой разметки на изображении и их отслеживания. Целью данной работы является разработка нового алгоритма распознавания разметки, требующего минимальных машинных ресурсов и обеспечивающего приемлемое быстродействие для работы в режиме реального времени. Для достижения данной цели выделены следующие основные задачи: нахождение линий	разметки на изображении, их отслеживание; исследование характеристик системы на тестовых изображениях. 1. Предварительная обработка изображений Исходное цветное изображение обычно представляется в формате, где каждый пиксель зашифрован тремя значениями базовых цветов (красный, зеленый, синий) от 0 до 255 (RGB формат). Для дальнейших действий с изображением необходимо преобразовать его в формат оттенков серого (intensity format). Такое преобразование выполняется по следующей формуле [4]: / = 0.229R + 0.587G + 0.114B, где / - интенсивность серого, R, G, В - красная, зеленая и синяя составляющие соответственно. Необходимость линейной фильтрации обоснована наличием множества низкочастотных помех на изображении. Механизм линейной пространственной фильтрации заключается в перемещении центра фильтрующей маски т от точки к точке изображения. В каждой точке (х,у) откликом фильтра является сумма произведений коэффициентов фильтра и соответствующих писке-лов окрестности, которые накрываются фильтрующей маской. Для маски тхп предполагается, что т = 2а + 1 и п = 2Ь + 1, где а и b - неотрицательные целые числа. Учитывая машинные затраты на наложение фильтра была подобрана простая маска М , полностью удовлетворяющая поставленной задаче: M = [-1 0 1], где М - фильтрующая маска В области компьютерного распознавания образов и обработки изображения, метод Оцу используется для выполнения пороговой бинаризации полутоновых изображений [5]. Алгоритм предполагает наличие в изображении двух классов пикселей (значимые и фоновые) и ищет оптимальный порог, разделяющий эти два класса так, что бы их внутриклассовая дисперсия была минимальна. Метод Оцу ищет порог, уменьшающий девиацию внутри класса, которая определяется как взвешенная сумма девиаций двух классов: a2(f) = co₁(f)a₁²(f) + co₂(f)a\|(f)