M2M Day 185: Моя попытка объяснить как работает один из алгоритмов самоуправляемого автомобиля
Вчера я наконец-то понял как работает алгоритм распознавания линий дорожной разметки на фотографиях сделанных с автомобиля. Ну... Как минимум я понял как работает код, который я использовал.
Ниже вы можете увидеть блок этого кода. Я скопировал основную функцию, которая называется draw_lane_lines. В качестве аргумента этой функции передается изображение, далее с ним проводятся манипуляции и возвращается новое черно-белое изображение с выделенными линиями дорожной разметки.
Комментарии показывают основные этапы работы приведенного алгоритма. Всего фотография проходит 7 стадий обработки.
Мы же рассмотрим первые пять этапов. Последние два отвечают за подготовку фотографии к выводу и особой роли не играют.
Изображение
Изображение представляет собой набор пикселей, расположенных в определенной последовательности. В нашем случае это набор размером 960x540 пикселей.
Каждый пиксель представляет собой определенную комбинацию красного, зеленого и синего, и может быть представлен тремя числами, соответствующими каждому из цветов (RGB) и отражающими их интенсивность. Эти числа не могут быть меньше 0 и больше 255, где 0 это наименьшая интенсивность, а 255 - наибольшая.
Например, белый пиксель можно представить как (255, 255, 255), а черный (0, 0, 0).
Наше изображение состоит из 960x540=518,400 таких RGB-чисел.
Теперь, когда мы разобрались, что изображение это последовательность чисел, мы можем начать работать с изображением используя математику.
1. Обесцвечиваем изображение
Работая с цветными изображениями нам приходится работать с группой из 3 чисел. Согласитесь, что было бы намного проще оперировать только одним числом. К счастью, в черно-белых изображениях каждый пиксель можно представить как одно число в диапазоне от 0 до 255, где 0 - это черный цвет, а 255 - белый.
Поэтому давайте преобразуем нашу фотографию в черно-белое изображение. Изначально я думал, что это можно сделать путем сложения красного, синего и зеленого и получения среднего арифметического.
Например, при таком подходе, цвет неба:
Который может быть предстsxxaxавлен как (120, 172, 209) в формате RGB.
В черно белом изображении будет (120 + 172 + 209)/3 = 167
Но, оказалось, что функция которую я использовал в коде генерирует немного другой серый цвет, числовое представление которого равно 164.
На самом деле, мой способ с вычислением среднего арифметического также верен. Но принято использовать взвешенное арифметическое, которое позволяет определить тот цвет, который лучше воспринимается нашим глазом. Наши глаза имеют больше "зеленых" рецепторов чем красных или синих, поэтому значение зеленного должно быть весомее.
Метод из кода использует такую формулу: 0.2126 Красного + 0.7152 Зеленого + 0.0722 Синего.
И после преобразования мы получаем следующее...
2. Размытие по Гауссу
Следующим шагом будет добавление размытия на изображение с помощью фильтра Гаусса.
Небольшое размытие уберет шум с фотографии, и сделает блоки пикселей более гладкими, что упростит их анализ.
Обычно, чтобы добавить размытие вам нужно сделать следующее:
1. Выбрать пиксель на фото и определить его значение
2. Определить значения всех соседних пикслей
3. Берем значение нашего пикселя и соседних пикселей и вычисляем среднее арифмитическое
4. Заменяем текщий пиксель на полученное значение
5. Делаем то же самое с остальными пикселями
Иными словами мы просто делаем каждый пиксель более похожим на другие пиксели.
В фильтре Гаусса используется Гауссовское распределение (Нормальное распределение). Его суть в том, что каждый пиксель имеет свой вес: чем ближе соседний пиксель к текущему пикселю, тем больше его вес.
И вот что получается...
3. Алгоритм Кэнни
Теперь, когда мы имеем преобразованное черно-белое изображение, нужно найти его границы.
Граница это область на изображении где есть резкий скачок в значении.
Например на серой дороге есть белая пунктирная линия (дорожная разметка). Серая дорога имеет значение близкое к 126, а белая линия 255, и между ними нет никакого последовательного перехода. Это и есть граница.
Алгоритм Кэнни очень прост:
- Выбираем пиксель на изображении.
- Определяем значения групп пикселей слева и справа относительно выбранного пикселя.
- Определяем разницу между этими группами путем обычного вычитания.
- Изменяем значение выбранного пикселя на полученную разницу.
- Делаем тоже самое для остальных пикселей.
Для примера возьмем 3 последовательно расположенных пикселя. Средний будет текущим пикселем, с которым идет работа, а левый и правый это пиксели для определения разницы. Мы не используем группу пикселей для простоты примера. Пусть их значения будут такими: (левый пиксель, выбранный пиксель, правый пиксель) = (133, 134, 155). Далее мы вычисляем разницу между правым и левым пикселем, 155-133=22, и задаём полученное значение среднему пикселю.
Если текущий пиксель это граница, то разница между боковыми пикселями будет близка к 255 и поэтому на изображении будет показана белым цветом. Если выбранный пиксель не является границей, то разница будет близка к 0.
Как вы могли заметить, что мы определили границы только для горизонтальной последовательности. Тоже самое нужно сделать и для вертикальной последовательности.
Кстати, эта разница называется градиентом, и мы можем вычислить общий градиент используя Теорему Пифагора. Формула выглядит так: общий градиент²=вертикальный градиент²+горизонтальный градиент² .
Так, например, если вертикальный градиент = 22 и горизональный = 143, то общий градиент = sqrt(22²+143²) = ~145.
На выходе получаем такое изображение...
С помощью Алгоритма Кэнни мы завершили еще один этап обработки.
Но Алгоритм Кэнии также определяет не только все границы, но и выбирает из них самые важные.
Для этого нужно задать рамки: максимальное и минимальное значение градиента. Представим, что максимальное значение равно 200, а минимальное 150.
Любой общий градиент, значение которого больше максимально допустимого считается границей и поэтому цвет пикселя заменяется на белый (255). Любой градиент, значение которого меньше минимально допустимого границей не считается и поэтому цвет этого пикселя заменяется на черный (0).
Пиксель, градиент которого находится между 150 и 200, будет считаться границей только если он непосредственно граничит с другой границей.
Иначе говоря если слабая граница граничит с сильной границей, то это вероятнее всего одна граница.
После выполнения всех этих процессов мы получаем что-то вроде этого...
4. Убираем ненужное
Этот шаг очень простой: по заданной маске убираем все части изображения, которые не линии.
На выходе имеем это:
5. Преобразование Хафа
На этом этапе мы будем использовать Преобразование Хафа чтобы найти математическое представление дорожных линий.
Честно говоря, алгоритм используемый в Представлении Хафа немного сложнее того, что мы рассматривали на предыдущих этапах.
Концепция выглядит так:
Алгоритм преобразования Хафа использует массив, называемый аккумулятором, для определения присутствия прямой y = mx + b. Размерность аккумулятора равна количеству неизвестных параметров пространства Хафа. Для каждой точки и её соседей алгоритм определяет, достаточен ли вес границы в этой точке. Если да, то алгоритм вычисляет параметры прямой и увеличивает значение в ячейке аккумулятора, соответствующей данным параметрам.
Потом, найдя ячейки аккумулятора с максимальными значениями, обычно поиском локального максимума в пространстве аккумулятора, могут быть определены наиболее подходящие прямые. Однако в разных ситуациях разные методы могут давать разные результаты. Так как полученные прямые не содержат информацию о длине, следующим шагом является нахождение частей изображения, соответствующих найденным прямым.
В итоге получается такая минималистичная картина:
Результат
Мы закончили разбирать алгоритм обработки изображения.
В итоге функция возвращает изображение, полученное на этапе 2 совмещенное с линиями найденными на этапе 5:
Lane line 1
Lane line 2
Оригинал: