Автоиндустрия считается «первопроходцем» в области применения технологий машинного зрения и самым крупным их потребителем. По данным аналитиков, автомобильная индустрия формирует 23% рынка продуктов компьютерного зрения в Германии. А по данным VDMA, для Европы эта цифра составляет 21%.
Поэтому не удивительно, что алгоритмы машинного зрения постепенно начали использоваться в самих автомобилях, а не только на этапах их производства. В настоящее время они применяются в технологиях автопилотирования и распознавания полос.
В сегодняшнем материале мы начнем говорить о том, что «видят» автомобили и как они это делают, используя базовые алгоритмы и методы в качестве отправной точки цикла рассказов.
Welcome on board! / изображение WayRay
Используя массивы датчиков и камер, автомобили научились распознавать вокруг себя бортики, деревья, столбы и припаркованный транспорт. Принцип определения расстояния до объектов основывается на параллаксе движения.
Когда мы двигаемся влево или вправо, предметы вдалеке смещаются меньше, чем ближние. На основании этого смещения и определяется расстояние от наблюдателя.
Техника получила название structure from motion. На соответствующей странице в «Википедии» предложены несколько инструментов для воссоздания трехмерных моделей из видео или набора фотографий. В основе лежит анализ стереопары.
Стереопара, заснятая двумя камерами / фото cobravictor / PD
Стереопара позволяет идентифицировать пары сопряженных точек в пространстве, на основании которых строится карта расстояний. На ней дистанция до объекта обозначается оттенками серого — чем дальше, тем темнее. Пример такого изображения есть в работе Райнхарда Клетте (Reinhard Klette) из Оклендского технологического университета. Когда карта построена, производится анализ движения объектов (скорость, траектория) — это нужно для определения вероятных конфликтов.
Анализ движения начинается с расчета оптического потока, который используется для вычисления карты смещений. Он позволяет отследить смещение точек, то есть найти их на втором изображении стереопары. Обычно этот метод используется для слежения за объектами, обнаружения столкновений и в дополненной реальности.
Из простых методов определения сдвига выделяют метод фазовой корреляции — это вычисление преобразования Фурье для обоих изображений и нахождение их свертки. Также применяется поблочное сравнение: находится сдвиг, минимизирующий норму разности изображений в окне.
Классическим подходом для вычисления потока является алгоритм Лукаса — Канаде. В его основу ложится предположение, что значения пикселей переходят из одного кадра в следующий без изменений. Таким образом, мы делаем допущение, что пиксели, относящиеся к одному и тому же объекту, могут сместиться в сторону, но их значение останется неизменным.
Конечно же, в реальных условиях постоянно меняется освещенность, однако на практике это допущение не сильно сказывается на результате. Теория работы алгоритма Лукаса — Канаде подробно расписана в этой статье.
Этот метод хорошо определяет маленькие сдвиги, в рамках которых картинка похожа на свое линейное приближение. Но есть и другие подходы: метод Гуннара Фарнебака, который рассчитывает поток для всего изображения сразу, и алгоритм Хорна — Шранка, основанный на гипотезе об ограничении изменения проекций векторов оптического потока.
Почитать дополнительно о построении карт смещений и расстояний можно здесь и здесь.
На основании полученных карт алгоритмы строят маршруты и оценивают траектории: уход от столкновений, маневрирование. Алгоритмы строят вероятностные модели для предсказания маршрутов объектов вокруг.
При автопилотировании система выстраивает примерный план маршрута до точки назначения и регулярно мониторит окружение. Транспортное средство определяет направления движения, в которых может проследовать, с учетом текущей скорости и углового положения.
Затем отсеивает маршруты, пересекающиеся с препятствиями или подходящие к ним слишком близко. Также оценивается безопасность маневра. Например, автомобиль, двигающийся со скоростью 90 км/ч, не сможет через 5 метров резко повернуть направо.
Когда путь выбран, то контроллер автомобиля подает команды акселератору, тормозам, рулевой системе и силовым приводам.
Отметим, что есть и другие способы определения расстояния до препятствий и избегания столкновений. Их появление и реализация станут возможными при распространении интернета вещей. Эти алгоритмы работают по-другому — их авторы предлагают использовать не камеры, а системы связи «автомобиль-автомобиль» и «автомобиль-инфраструктура».
Алгоритм Decentralized Reactive Collision Avoidance предполагает, что если автомобили находятся на большом расстоянии друг от друга, они следуют по намеченным маршрутам. Если машины сближаются, то система выполняет маневр по избеганию столкновения. Блок-схема выглядит следующим образом:
/ Блок-схема DRCA-алгоритма
Для определения того, столкнутся ли автомобили, DRCA использует концепцию «конуса столкновения» (collision cone), описываемого векторами скорости. Если угол β между вектором относительного положения r⌄ij и вектором относительной скорости v⌄ij больше или равен α — углу между вектором относительного положения и концом конуса столкновения — то конфликта маршрутов нет.
/ Конус столкновения — это угол между пунктирными линиями. Если вектор v оказывается в этой зоне, то автомобили «конфликтуют»
Алгоритм помогает объехать и статичные объекты, однако не годится, если транспортные средства двигаются в формации. DRCA предложит автомобилям набрать безопасное расстояние относительно друг друга и «разобьёт» строй.
Может применяться в комбинации с DRCA. Он основывается на вычислении искусственных силовых полей. Автомобили — это заряженные частицы. Частицы с одинаковым зарядом отталкиваются, а с противоположным — притягиваются. Поэтому автомобилям назначаются отрицательные заряды, а их желаемым маршрутам — положительные. Силовые векторы вычисляются на основании этих зарядов, а затем используются для определения направления движения.
Для оценки векторов силы притяжения применяются несколько способов. Yunior I. Cruz из Вашингтонского университета в своей работе описывает прием, который также был предложен для прокладывания маршрута самолетов с неизменяемой геометрией крыла.
Вокруг транспортного средства формируется овальная «зона безопасности», за пределами которой влияние «зарядов» других ТС становится незначительным. Сила притяжения точки назначения считается константой. Все это позволяет оценить силу притяжения, которую «ощущают» автомобили, и на основании этих данных корректировать маршрут.
Автомобили также используют компьютерное зрение для определения полосы движения. Они научились предупреждать водителя о наезде на разметку и даже самостоятельно корректировать траекторию. Ученые рассматривают несколько вариантов реализации этого функционала. Первый — когда инфраструктура является частью интеллектуальных систем (используются умные маячки), однако он связан со сложностью и дороговизной перестройки дорог. Второй — автомобили сами анализируют дорогу и принимают решения.
Такие системы используют камеры и методы выделения характерных признаков для обозначения границ полосы. Сперва на картинке с камеры находят линии, расположенные под определенным углом к объективу. После чего у выделенных полос выделяют крайние пиксели с использованием троичного поиска.
Далее проводится выделение полезной информации. Дело в том, что система отмечает все линии, которые удовлетворяют заданным условиям. Как это выглядит, вы можете увидеть в работе Люка Флетчера (Luke Fletcher) по ссылке.
К решению этой проблемы компании подходят по-разному. Например, в Suzuki используют проективное преобразование. Камера проецирует две линии, которые сходятся в точке перспективы. Система учитывает только те полосы, которые параллельны спроецированным. Однако это не спасает от выделения трещин на асфальте, которые идут вдоль дороги.
Еще один способ определения полос получил название «Птичий глаз» (Bird’s Eye) и описан в книге «Mathematical Morphology and Its Application to Signal and Image Processing». Алгоритм начинает работу с того, что преобразует изображение в ортографическую проекцию, как бы поворачивая изображение вертикально. После чего также происходит выделение полос и вычисляются поля расстояния, например, с помощью Евклидова преобразования.
Другие алгоритмы полагаются на поиск регионов, изменяющих цвет с черного на белый, однако использовать только этот подход не следует, поскольку качество разметки на разных дорогах отличается. Поэтому исследователи рекомендуют использовать комбинированные методы.
Алгоритм распознавания с построением бинарных изображений и кодом можно найти по ссылке на GitHub. Представленный проект является частью программы Udacity Self-Driving Car Nanodegree. Еще один пример с кусками кода из библиотеки алгоритмов OpenCV вы можете найти здесь.
Поэтому не удивительно, что алгоритмы машинного зрения постепенно начали использоваться в самих автомобилях, а не только на этапах их производства. В настоящее время они применяются в технологиях автопилотирования и распознавания полос.
В сегодняшнем материале мы начнем говорить о том, что «видят» автомобили и как они это делают, используя базовые алгоритмы и методы в качестве отправной точки цикла рассказов.
Welcome on board! / изображение WayRay
Видят препятствия
Используя массивы датчиков и камер, автомобили научились распознавать вокруг себя бортики, деревья, столбы и припаркованный транспорт. Принцип определения расстояния до объектов основывается на параллаксе движения.
Когда мы двигаемся влево или вправо, предметы вдалеке смещаются меньше, чем ближние. На основании этого смещения и определяется расстояние от наблюдателя.
Техника получила название structure from motion. На соответствующей странице в «Википедии» предложены несколько инструментов для воссоздания трехмерных моделей из видео или набора фотографий. В основе лежит анализ стереопары.
Стереопара, заснятая двумя камерами / фото cobravictor / PD
Стереопара позволяет идентифицировать пары сопряженных точек в пространстве, на основании которых строится карта расстояний. На ней дистанция до объекта обозначается оттенками серого — чем дальше, тем темнее. Пример такого изображения есть в работе Райнхарда Клетте (Reinhard Klette) из Оклендского технологического университета. Когда карта построена, производится анализ движения объектов (скорость, траектория) — это нужно для определения вероятных конфликтов.
Анализ движения начинается с расчета оптического потока, который используется для вычисления карты смещений. Он позволяет отследить смещение точек, то есть найти их на втором изображении стереопары. Обычно этот метод используется для слежения за объектами, обнаружения столкновений и в дополненной реальности.
Из простых методов определения сдвига выделяют метод фазовой корреляции — это вычисление преобразования Фурье для обоих изображений и нахождение их свертки. Также применяется поблочное сравнение: находится сдвиг, минимизирующий норму разности изображений в окне.
Классическим подходом для вычисления потока является алгоритм Лукаса — Канаде. В его основу ложится предположение, что значения пикселей переходят из одного кадра в следующий без изменений. Таким образом, мы делаем допущение, что пиксели, относящиеся к одному и тому же объекту, могут сместиться в сторону, но их значение останется неизменным.
Конечно же, в реальных условиях постоянно меняется освещенность, однако на практике это допущение не сильно сказывается на результате. Теория работы алгоритма Лукаса — Канаде подробно расписана в этой статье.
Этот метод хорошо определяет маленькие сдвиги, в рамках которых картинка похожа на свое линейное приближение. Но есть и другие подходы: метод Гуннара Фарнебака, который рассчитывает поток для всего изображения сразу, и алгоритм Хорна — Шранка, основанный на гипотезе об ограничении изменения проекций векторов оптического потока.
Почитать дополнительно о построении карт смещений и расстояний можно здесь и здесь.
На основании полученных карт алгоритмы строят маршруты и оценивают траектории: уход от столкновений, маневрирование. Алгоритмы строят вероятностные модели для предсказания маршрутов объектов вокруг.
При автопилотировании система выстраивает примерный план маршрута до точки назначения и регулярно мониторит окружение. Транспортное средство определяет направления движения, в которых может проследовать, с учетом текущей скорости и углового положения.
Затем отсеивает маршруты, пересекающиеся с препятствиями или подходящие к ним слишком близко. Также оценивается безопасность маневра. Например, автомобиль, двигающийся со скоростью 90 км/ч, не сможет через 5 метров резко повернуть направо.
Когда путь выбран, то контроллер автомобиля подает команды акселератору, тормозам, рулевой системе и силовым приводам.
Отметим, что есть и другие способы определения расстояния до препятствий и избегания столкновений. Их появление и реализация станут возможными при распространении интернета вещей. Эти алгоритмы работают по-другому — их авторы предлагают использовать не камеры, а системы связи «автомобиль-автомобиль» и «автомобиль-инфраструктура».
DRCA-алгоритм
Алгоритм Decentralized Reactive Collision Avoidance предполагает, что если автомобили находятся на большом расстоянии друг от друга, они следуют по намеченным маршрутам. Если машины сближаются, то система выполняет маневр по избеганию столкновения. Блок-схема выглядит следующим образом:
/ Блок-схема DRCA-алгоритма
Для определения того, столкнутся ли автомобили, DRCA использует концепцию «конуса столкновения» (collision cone), описываемого векторами скорости. Если угол β между вектором относительного положения r⌄ij и вектором относительной скорости v⌄ij больше или равен α — углу между вектором относительного положения и концом конуса столкновения — то конфликта маршрутов нет.
/ Конус столкновения — это угол между пунктирными линиями. Если вектор v оказывается в этой зоне, то автомобили «конфликтуют»
Алгоритм помогает объехать и статичные объекты, однако не годится, если транспортные средства двигаются в формации. DRCA предложит автомобилям набрать безопасное расстояние относительно друг друга и «разобьёт» строй.
Метод искусственных силовых полей
Может применяться в комбинации с DRCA. Он основывается на вычислении искусственных силовых полей. Автомобили — это заряженные частицы. Частицы с одинаковым зарядом отталкиваются, а с противоположным — притягиваются. Поэтому автомобилям назначаются отрицательные заряды, а их желаемым маршрутам — положительные. Силовые векторы вычисляются на основании этих зарядов, а затем используются для определения направления движения.
Для оценки векторов силы притяжения применяются несколько способов. Yunior I. Cruz из Вашингтонского университета в своей работе описывает прием, который также был предложен для прокладывания маршрута самолетов с неизменяемой геометрией крыла.
Вокруг транспортного средства формируется овальная «зона безопасности», за пределами которой влияние «зарядов» других ТС становится незначительным. Сила притяжения точки назначения считается константой. Все это позволяет оценить силу притяжения, которую «ощущают» автомобили, и на основании этих данных корректировать маршрут.
Распознают полосы
Автомобили также используют компьютерное зрение для определения полосы движения. Они научились предупреждать водителя о наезде на разметку и даже самостоятельно корректировать траекторию. Ученые рассматривают несколько вариантов реализации этого функционала. Первый — когда инфраструктура является частью интеллектуальных систем (используются умные маячки), однако он связан со сложностью и дороговизной перестройки дорог. Второй — автомобили сами анализируют дорогу и принимают решения.
Такие системы используют камеры и методы выделения характерных признаков для обозначения границ полосы. Сперва на картинке с камеры находят линии, расположенные под определенным углом к объективу. После чего у выделенных полос выделяют крайние пиксели с использованием троичного поиска.
Далее проводится выделение полезной информации. Дело в том, что система отмечает все линии, которые удовлетворяют заданным условиям. Как это выглядит, вы можете увидеть в работе Люка Флетчера (Luke Fletcher) по ссылке.
К решению этой проблемы компании подходят по-разному. Например, в Suzuki используют проективное преобразование. Камера проецирует две линии, которые сходятся в точке перспективы. Система учитывает только те полосы, которые параллельны спроецированным. Однако это не спасает от выделения трещин на асфальте, которые идут вдоль дороги.
Еще один способ определения полос получил название «Птичий глаз» (Bird’s Eye) и описан в книге «Mathematical Morphology and Its Application to Signal and Image Processing». Алгоритм начинает работу с того, что преобразует изображение в ортографическую проекцию, как бы поворачивая изображение вертикально. После чего также происходит выделение полос и вычисляются поля расстояния, например, с помощью Евклидова преобразования.
Другие алгоритмы полагаются на поиск регионов, изменяющих цвет с черного на белый, однако использовать только этот подход не следует, поскольку качество разметки на разных дорогах отличается. Поэтому исследователи рекомендуют использовать комбинированные методы.
Алгоритм распознавания с построением бинарных изображений и кодом можно найти по ссылке на GitHub. Представленный проект является частью программы Udacity Self-Driving Car Nanodegree. Еще один пример с кусками кода из библиотеки алгоритмов OpenCV вы можете найти здесь.
