Система обнаружения и сопровождения видеомаркеров для обеспечения навигации робота

Размещено на http://www.allbest.ru

СИСТЕМА ОБНАРУЖЕНИЯ И СОПРОВОЖДЕНИЯ ВИДЕОМАРКЕРОВ ДЛЯ ОБЕСПЕЧЕНИЯ НАВИГАЦИИ РОБОТА

А.В. Калиниченко (tooboos@mail.ru)

Институт прикладной математики

им. М.В. Келдыша РАН, Москва

В работе описывается система обнаружения и сопровождения видеомаркеров. Эта система может быть использована в качестве дополнительного источника данных в системах глобальной и локальной навигации мобильного робота, а также для обеспечения автоматического слежения роботом за каким-либо объектом. Распознавание маркеров выполняется на основе вычисления локальных дифференциальных инвариантов на изображении с последующим поиском межкадровых соответствий и вычислением проективного преобразования.

ВВЕДЕНИЕ

Для облегчения решения задачи глобальной навигации в районе перемещения робота могут быть установлены маркеры. В данной работе маркером будем называть прямоугольный объект с нанесенным на него изображением и известными заранее размерами. Маркеры должны быть установлены таким образом, чтобы обеспечить видимость их с максимально возможной части района перемещения роботов. Будем считать, что данные обо всех маркерах заранее известны роботу - система навигации располагает снимками всех маркеров, а также координатами маркеров в системе отсчета связанной с Землей (например, полученных при помощи GPS).

Заметим, что также возможно использование системы в ручном режиме, когда оператор выделяет какой-либо объект на изображении, полученном с сенсоров робота. После этого система продолжает сопровождение этого объекта на протяжении всего его времени видимости.

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

Для нормальной работы системы на робот потребуется установить управляемую в 2-х плоскостях камеру с максимальным углом обзора. Это позволит максимально расширить область охвата системы сопровождения маркеров.

ПЕРВОНАЧАЛЬНАЯ ОБРАБОТКА ИНФОРМАЦИИ О МАРКЕРАХ

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

1. Поиск особых точек на изображении

Для дальнейшего сопоставления на изображениях маркеров обнаруживаются особые точки, это делается при помощи метода Харриса [Harris, 1988]. На изображении обнаруживаются «уголки». Этот метод основан на том, как меняется изображение внутри поисковой рамки. На однородном участке изображения, или при смещении рамки вдоль направления грани, содержимое рамки не меняется (рис.1, а, b), но если, же рамка попала на угол (рис.1,c), то ее содержимое меняется при движении в любом направлении. видеомаркер навигация мобильный робот

a) b) c)

Рис. 1. Рамка на однородной части изображения (a), на границе (b) и на уголке (с)

Изменение содержимого рамки при сдвиге на вектор (u,v) равно E(u,v) Функция описания изменения содержимого рамки E(u,v):

где:

I(x,y) - изображение маркера

w(x,y) - оконная функция.

Для небольших смещений E(u,v) можно приблизить билинейной формой.

где M матрица из производных по изображению 2х2:

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

После этого этапа _min(x,y) рассматривалось как изображение, локальные максимумы яркости которого и являлись особыми точками на изображении.

Рис. 2. Работа детектора особых точек, слева исходное изображение, справа белым цветом выделены особые точки

2. Вычисление локальных инвариантов на изображении

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

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

Рис. 3. Различные дифференциальные инварианты представлены в виде изображений

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

ПОИСК МЕЖКАДРОВЫХ СООТВЕТСТВИЙ

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

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

ВЫЧИСЛЕНИЕ ПРОЕКТИВНОГО ПРЕОБРАЗОВАНИЯ

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

Проективное преобразование будем искать в виде:

(3.1)

где:

x'', y'' - однородные координаты особых точек на изображение маркера, а x, y - однородные координаты точек на кадре из видео.

Подставим в уравнение (3.1) координаты соответствующих точек, для каждой пары точек получим 2 линейных уравнения, таким образом, для n точек получим 2n линейных уравнений относительно 9 неизвестных (элементов матрицы M). Решим эту систему методом сингулярного разложения [Press, 1998]. Получим проективное преобразование, которое переводит множество точек {x'', y''} в {x', y'}.

Процедура поиска проективного преобразования была усовершенствована по методу RANSAC [Fischler, 1981]. Для решения системы линейных уравнений использовались не все пары соответствий, а небольшая их часть, выбранная случайным образом. Процедура случайного выбора и последующего решения системы проводилась несколько раз. Затем выбиралось решение, которое удовлетворяло максимальному количеству пар соответствий, не задействованных в решении системы. Этот метод позволил уменьшить влияние на конечный результат ложных соответствий, которые неизбежны при инвариантном поиске.

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

Рис. 4. Результаты работы поиска маркеров на видеопоследовательности

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ЛИТЕРАТУРЫ

[Fischler, 1981] Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. Of the ACM 24:

[Harris, 1988] C. Harris and M.J. Stephens [1988]. A combined corner and edge detector. In Alvey Vision Conference.

[Press, 1998] William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery [1998] Numerical Recipes in C.

[Schmid, 1997] Cordelia Schmid, Roger Mohr [1997] Local Grayvalue Invariants for Image Retrieval. IEEE Trans. Pattern Anal. Mach. Intell. 19(5).

Размещено на Allbest.ru