illumium.org

Где-то здесь я уже рассказывал о том как я делал перспективное преобразование с помощью opencv. Всё это я делал не просто так, этот код входит в программу, которую я писал для своей магистерской диссертации. Суть работы заключалась в том, чтобы научить робота вычислять свое положение.

Задача

Так как наш робот принимал участие в соревнованиях, полигон для которых состоял из черных и белых квадратов, как шахматная доска, то я подумал, а почему бы собственно не использовать эти квадраты для навигации!

Тестировать правда пришлось на кафельной плитке, которая несколько менее черно-белая и менее контрастная, но всё получилось неплохо.

Идея алгоритма

Идея заключалась в следующем: как правило во время соревнований робот ползал по полигону достаточно медленно. Говоря медленно я имею ввиду что за время между двумя кадрами обычной веб-камеры (примерно 30 кадров в секунду), робот не успевает перепрыгнуть целый квадрат. Раз двигаемся мы медленно, то почему бы во время движения не отслеживать углы квадратов и не считать своё положение относительно этих углов ?

Есть конечно большой минус этой идеи : нужно иметь карту, но есть и плюс: карта представляет собой просто сетку из квадратов. Всё.

Собственно алгоритм

Запасемся квадратами и вперед:

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

В итоге из такой картинки:

Получается такая:

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

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

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

Несложная тригонометрия: A-положение камеры, B-положение точки, на которую смотрит камера, а также куча углов и векторов из которых нас интересуют векторы d и l.

Но вот что стоит отметить, так это симметрию квадратов в сетке. Так как нет никакой разницы с какой стороны робот подъезжает к углу квадрата, то получается, что есть 4 вероятных направления таких, что камера снимет один и тот же кадр. Здесь нас спасает медлительность нашего робота. Мы просто считаем что робот движется медленно, а значит надо выбирать то направление обзора, которое возможно если робот передвинулся немного или не двигался вовсе.

На этом рисунке видно что без дополнительной информации есть много вероятных векторов d и l, условие минимального перемещения позволяет выбрать одну пару.

Тестовый заезд можно посмотреть на youtube: http://www.youtube.com/watch?v=YIbBNPjt9fc . А ниже можно увидеть график, на котором приведены фактическая траектория и траектория построенная роботом.