Санкт-Петербургский Государственный Университет

Курсовая работа

по программированию:

«Применение методов фильтрации при обработке визуальной информации»

Руководитель:

Граничин О. Н.

Исполнитель:

студент 242 группы

математико-механического факультета

Ушаков К. С.

Санкт-Петербург 2004

Содержание

Введение.............................................................................................................................. 3

Описание............................................................................................................................. 4

Определение своего местоположения по двум флагам............................................. 5

Используя все флаги (с весами)................................................................................... 6

Используя все флаги (фильтрация).............................................................................. 6

Реализация........................................................................................................................... 7

Литература........................................................................................................................... 8

Введение

Идея проведения турниров по виртуальному футболу впервые возникла в середине 90-х годов. Эти турниры являются не только спортивным соревнованием, но и той проблемой, к над которой уже почти десять лет бьются многие умы в нашем мире. Итоговая цель организации RoboCup, которая проводит эти турниры:

«К середине 21-го века создать команду полностью автономных гуманоидных роботов, которая выиграет футбольный матч, играя по официальным правилам FIFA, против победителя последнего чемпионата мира среди людей.»

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

Несколько слов о системе, использующейся на чемпионатах по виртуальному футболу в лиге Simulation, то есть в лиге, где игра полностью моделируется на компьютере. Само поле и все игроки «находятся» на сервере, который запущен на центральном компьютере. Этот сервер моделирует футбольное поле, игроков, тренеров, мяч. Так как возможности сети по передаче данных ограничены, игра на поле моделируется дискретно, длина цикла 100 ms. Раз в несколько циклов (в зависимости от выбора самого игрока) игроку с сервера приходит визуальная информация про все объекты, которые находятся в зоне его видимости. Для определения расположения объектов на поле нас интересует информация про статические объекты – флаги и линии. Флаги – это статические объекты, которые помещены на поле для того, чтобы игроку было удобнее ориентироваться. Вот как расположены эти объекты на поле.

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

Описание

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

d’ = Quantize(exp(Quantize(log(d), quantize_step_l), 0.1),

где d’ – новое значение расстояния d, а функция Quantize(P, Q) = round(P/Q)*Q. Quantize_step_l чаще всего равен для статических объектов 0.01. Таким образом на расстоянии 1 метр шум может быть 10 см., а на расстоянии 10 до 1 метра. Угол Fi при наведении шумов переходит в угол round(Fi), где все углы в градусах. С такими большими шумами определение своего местоположения может быть очень неточным. Давайте по порядку рассмотрим алгоритмы, которые используются для борьбы с этим.

Определение своего местоположения по двум флагам

Пусть у нас есть два флага (см. Рис. 1)

Тогда:

Находим координаты точки p’

Здесь cos(α) = Δx/d и sin(α) = Δy/d. Тогда

где sign отвечает за то, в какую сторону мы отойдем от прямой fg,

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

Используя все флаги (с весами)

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

Применим наш алгоритм для всех пар видимых флагов. Тогда мы получим некоторые возможные координаты нашего текущего местоположения. Давайте заметим, что если расстояние до одного флага большое, то теряется точность, так как на это расстояние наводится некоторый шум. Тогда логично было бы брать каждую точку с весом (1/(dist(f) + dust(g)), тогда при маленьких расстояниях точка будет сильно учитываться, а при больших нет. Точность такого алгоритма выше и составляет примерно 10-12 сантиметров, при времени работы около 1 ms, что просто ничтожно. Здесь, как и в следующем алгоритме надо учитывать тот факт, что если флаги находятся примерно на одной прямой, то возникает большая ошибка, так как мы можем отложить отрезок P’P не в ту сторону от прямой. Тогда у нас появится ошибка, которая сильно испортит точность измерения. По этому мы не будем учитывать такие пары флагов в нашем алгоритме.

Используя все флаги (фильтр)

Давайте посмотрим на процесс определения нашего местоположения. Пусть мы получили на шаге n некоторую точку. Теперь на шаге n+1, когда мы получаем новое значение, мы должны учитывать его с некоторым коэффициентом. Какой же он?

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

R_Min = exp(invMin(ln(invMin(r’, 0.1)), quantize_step_l),

R_Max = exp(invMax(ln(invMin(r’, 0.1)), quantize_step_l), где

Inv(Min|Max)(P, Q) = (round(P/Q) (-|+) 0.5)*Q.

Таким образом, площадь пересечения двух максимальных кругов, обозначим ее s_i для шага номер i, является хорошей характеристикой того, на сколько надо учитывать тот или иной результат. Пусть K = s_i/(s_i + s_(i+1)). Тогда можно записать, что y(i+1) = y(i) + (x(i+1) – y(i)), где y(i) – наше положение после I – го шага, а x(i+1) – то, что мы получили при i+1-м измерение. Итого мы последовательно приближаемся к нашему итоговому значению.

Реализация

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

Литература

О.Н. Граничин, Б.Т. Поляк Рандомизированые алгоритмы оценивания и оптимизации при почти произвольных помехах, Издательство «Наука», 2003.

RoboCup Soccer Server Manual, July 2002