Поэтому не удивительно, что алгоритмы машинного зрения постепенно начали использоваться в самих автомобилях, а не только на этапах их производства. В настоящее время они применяются в технологиях автопилотирования и распознавания полос.
В сегодняшнем материале мы начнем говорить о том, что «видят» автомобили и как они это делают, используя базовые алгоритмы и методы в качестве отправной точки цикла рассказов.
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 вы можете найти здесь.
Комментарии (19)
ZlodeiBaal
28.10.2017 20:45-1Господи. Что это за статья со ссылками на 2001 год. Ребят, за последние 5 лет прорыв произошёл в том как всё это устроено. Технологии прошлого поколения уже дано никто не использует. Тут нет ни единого слова в статье которое бы соответствовало текущей реальности.
erwins22
28.10.2017 21:20Да. Тогда еще не знали, что нейросети могут легко НАУЧИТЬСЯ водить машину.
Прям как описание самолетов у Г. Уэллса. Летчик стоит за штурвалом и ему в лицо дует ветер.
AVKinc
28.10.2017 21:45+3Никакого прорыва нет и не привидится с существующей элементной базой, нейросети эту проблему решить не могут в принципе.
Вождение автомобиля штука очень сложная. Чрезвычайно сложная с точки зрения алгоритмизации.
Вот кстати, насчет прогресса, автоматический перевод как был чудовищным так и остался, хотя нейросети, мощные процессоры, терабайты и гигафлопы, тоси-боси, куры гуси. Ничего не изменилось. Потому что нужен именно интеллект, а не псевдо интеллект электронный, нужна принципиально новая аппаратная платформа. Как там в фантастике — биопроцессоры, нейропроцессоры. Скорее всего такие штуки появятся очень нескоро, если вообще появятся.
Bal
28.10.2017 23:39В электронном переводе прогресс огромный. У меня неплохой словарный запас английского, но почти нулевые знания грамматики (учил немецкий). Этого хватает, чтобы читать технические тексты, но абсолютно недостаточно для общения, например, на форумах.
Впервые пытался я это делать через электронные переводчики ещё с начала нулевых годов. Но результат был отвратительный. Меня через электронные переводчики практически не понимали. Ну и я сам многое с трудом понимал… Но периодически, раз в год—два проводил такие эксперименты :)
Два года назад результаты электронного перевода оказались внезапно достаточны для вполне возможного общения. Хотя требовались ухищрения. Например, я переводил предложение в google, yandex и bing и выбирал тот вариант, что мне самому и через обратный перевод казался точнее. Это было медленно, но началось моё активное общение на американских политфорумах! :) При чём взаимного непонимания из-за ошибок перевода почти не было. Единичные случаи на тысячи постов!
В этом году Гугл внедрил перевод через нейросети и я был шокирован ростом качества! Да, результат всё ещё нужно вычитывать на предмет ошибок перевода неоднозначных слов, изредка бывают ошибки, типа некорректной работы с отрицаниями, иногда пропадают фрагменты предложения. Но в целом работа стала почти однопроходной :) Другие переводчики были заброшены, скорость общения выросла многократно. Без труда пишутся длинные ответы на сложный политфлейм :)
Так что прогресс огромный. И не только в ретроспективе на 20 лет, но даже за год :)
ankh1989
29.10.2017 11:52+1Хотел было написать скептический комментарий к вашему «росту качества», для примера перевёл этот абзац и офигел — я бы сам вряд ли лучше перевёл: «This year, Google introduced a translation through the neural network and I was shocked by the growth of quality! Yes, the result still needs to be read for errors in the translation of ambiguous words, occasionally there are errors, such as incorrect work with negatives, sometimes fragments of the sentence disappear. But in general, the work became almost one-pass :) Other translators were abandoned, the speed of communication has grown many times. Easily write long answers to a complex political flair :)»
vics001
29.10.2017 00:00Каждый, кто пробовал современные «автопилоты», от простых круиз-контроли до Tesla autopilot, понимает, что все это еще очень не готово. Мы даже не говорим про дорожные знаки и дорожную обстановку!
К сожалению, большинство популяризаторов нейронных сетей, должны признать, что человек не является ни венцом эволюции интеллекта и не является супер-компьютером. Компьютеры действительно гораздо быстрее считают и гораздо лучше мыслят тактически и стратегически, поэтому они выигрывают в любые игры людей от шахмат до покера. Человеческая ветвь эволюции возможно является самой сильной в стратегическом мышлении среди всех животных, но отнюдь не является самой сильной в «компьютерном зрении», то есть в скорости реакции, в зоркости глаз, в распознавании объектов, в ночном видении.
Эволюция развивала во многих животных именно зрение как орган взаимодействия с окружающим миром. Даже не стратегическое мышление! Когда мы говорим о «компьютерном зрении», сложно представить, какой огромный объем работы сделала для нас эволюция и какими совершенными технологиями владеет человек по сравнению с видеопроцессорами. Вождение автомобиля для нас прежде всего является одним из способов передвижения, где наше «тело» является «автомобилем». ПДД являются базовыми правилами и достаточно простыми, по сравнению с алгоритмами распознавания препятствий, полос и других субъектов движения.
Есть подозрение, что биологический компьютер наподобие мозга муравья, будет гораздо успешнее справляться с этим, чем любой сегодня существующий аналог.
Zmiy666
можно было бы наносить разметку краской, отражающей радиоволны. Тогда бы система зрения видела бы ее даже сквозь снег, лед и грязь. Ну и знаки тоже можно продублировать символами, видимыми в радиодиапазоне. Стоит копейки и сильно упросит создание автопилота. да и вообще безопасности прибавит. В те же светофоры можно было бы вставить радиомодуль, оповещающий о значении сигнала — тогда разглядеть светофор не помешало бы солнце, вывески, всякая растительность и стоящая перед тобой машина.
Но почему-то большинство создателей автопилотов пытаются перенести в него все человеческие недостатки, а наше зрение весьма ущербно.
alinatestova Автор
Задумка хорошая, но была бы инфраструктура. Ее отсутствие — это одна из причин работы над более универсальными возможностями, которые не в такой степени зависят от окружения.
DjSens
У нашего зрения идеальная амортизация тряски, хорошее разрешение и мгновенное вычисление карты глубины каждое мгновение с одновременным распознаванием объектов. Фокус внимания узковат правда. Современным камерам и алгоритмам ещё далеко до нас
immaculate
Вряд ли возможно создать и поддерживать идеальную разметку на всех дорогах. Ни одна страна не может поддерживать все дороги в идеальном состоянии, кроме, разве что, совсем крохотных. А если где-то разметка, на которую полагается автомобиль, нарушена?
В границах городов, возможно, это достижимо. Хотя у нас даже не во всех городах дороги нормальные. Этим летом проезжал через Краснодар (и множество других городов, но Краснодар — большой и богатый город), так там на многих улицах не то что разметки нет, а само дорожное полотно как будто после ковровой бомбардировки.
alinatestova Автор
Это точно, но в той или иной степени будущее все-таки за комплексными решениями. С этим сложно спорить.
Serge78rus
При поэтапном внедрении автопилотов, неизбежно возникает переходный этап, когда автоматика лишь помогает водителю, либо действует под его присмотром. В этом случае, для избежания конфликтных действий человека и машины, желательно, чтобы при принятии решений они руководствовались схожей информацией.
nehrung
Tyusha
Это проблема обратной совместимости. Понятно, что быстрее, проще, дешевле и надёжнее было бы, если каждый автомобиль, светофор и умный перекрёсток транслировал бы всем в радиоканале свои координаты, текущее состояние и намерения. И они бы все «договаривались» между собой супер оптимальным образом по своему какому-то протоколу для избегания столкновений и пробок. Тогда никакое машинное зрение было бы не нужно. Но из-за пенсионера Алексея Петровича на «Москвиче», который не оснащён такой системой, всем остальным 99,8% автомобилей приходится заморачиваться с компьютерным зрением, и быть «каждому за себя».
sim31r
На старый автомобиль можно крошечный передатчик поставить и воспринимать его как помеху на дороге способную к перемещению. Передатчик даст сведения о текущих координатах, направлении движения и ускорении. Помеху просто будут объезжать все. Передатчиком может быть и телефон со специальной программой логгером.
То же самое и с пешеходами. В любом месте тебя пропустят и объедут на безопасном расстоянии. Главное предупредить систему хотя бы за секунду до начала движения.
То же самое с кольцами любой сложности, удобнее когда машины заранее группируются в колонны для движения в одном направлении, а не когда всё кольцо ждет пока одна машина проедет.
Для начала можно просто оптимизировать движение, когда водитель принимает рекомендацию, ехать за той-то машиной, не отставая и не обгоняя, когда набирается большая группа дать им зеленый коридор.
Serge78rus
То же самое с домашними и дикими животными, упавшими деревьями и т.д.?
Мы живем не в идеальном, а реальном мире. На дороге всегда может оказаться помеха, которой там не должно было быть, и, соответственно, она не может быть заблаговременно оснащена маячком. Тот же самый «умный» автомобиль, после серьезной аварии, может превратиться в совершенно «глупую» груду железа на проезжей части.
kuber
>> можно было бы наносить разметку краской, отражающей радиоволны.
Можно. Но также легко представить себе недовольного своей жизнью школьника, который по ночам будет вам такую разметку рисовать. Посмотрите на стены, которые изрисованы граффити. Мы не в идеальном обществе живем.