Вычисление координат робота
Под координатами робота понимается точка в трехмерном евклидовом пространстве. Координаты этой точки (x,y,α) обозначают положение робота в двумерной системе координат, связанной с полем и угол направления робота в этой же системе координат.
Для мяча и чужих роботов мы рассматриваем двумерное пространство координат (x,y). Мы рассмотрим метод, описанный в предыдущей работе и его улучшение для увеличения качества. Под качеством понимается точность и устойчивость к ошибкам.
Метод нахождения положения. Устойчивость к ошибкам.
Для вычисления положения использовался распространенный метод нахождения центра масс. Распределение масс считалось равномерным. Т.е. определялось среднее по всем точкам от координат (x,y).
Действительно, для всех объектов, которые нам интересны центр масс видимого региона совпадает с той точкой, координаты которой мы желаем определить (варианты видимых регионов – квадрат и круг).
Здесь надо сделать оговорку, что мы не делаем никаких предположений насчет того, какой формы регионы мы получим у роботов противника. Но для этих объектов точность определения положения важна меньше, поэтому полученная точка, если она находится в пределах размера вражеского робота, будет достаточным приближением его положения.
Проведем простой теоретический расчет, показывающий качественно устойчивость этого алгоритма к ошибкам сегментации.
Разделим ошибки, проявляющиеся при сегментации на два рода. Ошибки первого рода: добавление ложных точек Ошибки второго рода: потери точек объекта.
Пусть  – точки объекта, – добавленные ложные точки, кроме того точки  потеряны при сегментации (d ≥ 0 – количество добавленных точек, p ≥ 0 – количество потерянных точек). Пусть  искомый центр объекта, учитывая, что известными формами объекта являются круг и квадрат, то совпадает с центром масс, взятым по точкам объекта.  . Теперь рассмотрим центр масс фигуры, полученной сегментированием.
Вектор смещения центра масс из-за ошибок сегментирования будет равен
Учитывая, что  и  ,  – центры масс добавленных и потерянных точек
 Это означает, что суммарный вектор ошибки состоит из разности вектора смещения в сторону центра масс добавленных и вектора смещения в сторону центра потерянных с весовыми коэффициентами, показывающими вес точек этой ошибки по сравнению с точками, которые были найдены правильно.
В самом деле, добавленные точки «утяжеляют» наш объект, смещая центр масс к себе, а потерянные «уменьшают», смещая центр масс от себя. (Error: Reference source not found)
На величину вектора сдвига влияет не только количество точек, сегментированных неправильно, но и симметричность их распределения относительно центра масс. Регион наблюдаемых объектов также обладает свойством симметричности. Ошибки первого типа располагаются в окрестности границы объекта (если алгоритм сегментации не вызывает значительных несимметричных изменений формы объекта).
По этому, вполне ожидаемо, добавление ошибок первого типа, вызванных некими причинами, действие равномерно на всем изображении (или хотя бы в пределах размеров объектов) будет оказывать влияние, пропорционально их количеству, но с малым коэффициентом.
Рассуждения о симметричности также применимы к ошибкам второго рода, за одним исключением.
Ошибки второго рода, можно разделить на ошибки, примыкающие к границе объекта и ошибки, создающие ложные границы внутри объекта. Для ошибок, примыкающих к границе справедливо также, что часто влияние источника их возникновения сказывается равномерно на границе и вследствие ее симметрии влияние этих ошибок также снижается.
Используемый алгоритм сегментации (в своей изначальной форме, т.е. использующий только значение компонент цвета пикселя) допускает образование ошибок второго рода, создающих ложные границы. Эти ошибки обычно вызываются особенностями цветов объекта, например, при переходе красный-зеленый точки на границе имеют низкую интенсивность по всем трем компонентам и могут быть причислены к фону.
Эти особенности не обладают симметричностью и вносят существенный вклад в изменение центра тяжести. Особенно заметно, если на границе симметрично распределены ошибки второго типа в большом количестве. Тогда их вклад не большой (вследствие симметричности) однако к ним прибавляется вклад ошибок внутри и при несимметричности их суммарный вектор направления смещения будет обладать существенным модулем, кроме того этот вектор будет умножен на суммарное количество ошибок второго рода, которое также существенно. А в результате получаем большую ошибку определения центра масс.
Внутренние ошибки второго типа легко устранимы, если использовать, например, медианную фильтрацию или найти внешнюю границу и определять регион объекта как все внутренние точки границы.
Заметим, что медианная фильтрация использовалась в предыдущей работе для подобной цели. Однако медианный фильтр внесет дополнительные ошибки в определении границы объекта, что приводит к необходимости отказаться от него в будущем.
В качестве итога, рассмотрим, что можно сделать для улучшения определения положения. Алгоритм нахождения центра масс толерантен к шуму (ошибка делится на площадь объекта). И поэтому мы оставляем этот метод для нахождения положения.
Казалось бы, что можно улучшить этот метод введением весов точек для уменьшения влияния граничного шума.  . Т.е. исходя из знания формы искомой фигуры и желаемого распределения цветов в ней, мы уменьшаем вес точек, которые более вероятно не являются точками региона объекта.
Можно предлагать различные методы для выявления таких функций. Однако высказывается предположение, что верно одно из двух:
Мы знаем, как вычислять весовую функцию F - значит, мы знаем центр масс, и формула оказывается бесполезной, т.к. она не уточняет центр масс, а только еще раз дает уже известный результат.
Весовое распределение F вносит дополнительную ошибку, либо не изменяет устойчивость.
Проведем рассуждения, приводящие к такому предположению.
F центрально. Т.е. если объект определен правильно, то результат суммы должен совпадать с центром. . Наше распределение не должно давать постоянной ошибки.
Логически можно разделить F на функции от трех сложных переменных
 – непосредственно вектор координат. Если существует зависимость от этой переменной, то весовая функция меняется при переносе координат и поступательных движениях объекта.
 – цветовая информация об объекте. Важным является то, что эта информация не зависит от положения объекта
 – положение точки внутри объекта
Какие способы в этом случае учета информации пунктов b и c может быть. Например, цветовая информация может быть учтена сравнением цветов с некоторой моделью, однако не понятно как это делать, не зная положение объекта. Другой способ брать коэффициент из метода сегментации  , который использовался для сравнения с порогом. Однако вычисление коэффициентов через него введет дополнительную ошибку, т.к. самые яркие области сосредоточены не внутри центра.
Для информации о положении можно, например, считать вес как функцию от расстояния до границы. Однако т.к. действия ошибок, прежде всего, сказываются на границе, то увеличения точности ожидать не приходится.
Если веса считать по функции расстояния от центра области, полученного по границе или по центру всей наблюдаемой области (что эквивалентно), то мы получим формулу, которая притягивает точку к этому центру.
Если рассматривать точки области, как реализации случайной величины с симметричным распределением относительно центра объекта, то оценка центра масс с равномерной массой будет наилучшим.
Получим еще один вполне ожидаемый результат. Для этого рассмотрим область  , отличающуюся от реальной области  , добавлением одной лишней точки. Ошибка, возникающая при использовании весовой функции в системе координат, проходящей через реальный центр, будет  ,  – веса, построенные на базе наблюдаемой области . Если веса выбраны так, чтобы и «лишней» точки сумма равняется нулю. Например  , то  , т.е. наилучшей функцией в этом случае будет например индикатор области , которую мы считаем неизвестной. Также уменьшению ошибки способствует симметричность функции  , но подсчет непостоянной симметричной функции основывается на знании центра, а эту информацию мы тоже считаем недоступной.
Таким образом, есть смысл отказаться от поиска весовой функции, и модифицировать качество алгоритма двумя путями:
Улучшать точность построения границы
Стремится к симметричности расположения ошибок по границе.
Далее будет описан метод уточнения границы, включенный в данную реализацию.
Метод нахождения вершин
Рассмотрим теперь использовавшийся в предыдущей работе метод нахождения вершин. Этот метод применялся для нахождения направления роботов команды.
Он заключался в том, чтобы брать в качестве вершин точки объекта, через которые проходит ограничивающий прямоугольник. Если на какой-либо из границ таких точек оказывается много, то берется средняя из таких точек. Исключение составляют малые углы поворота робота, для которых в качестве границы брался сам ограничивающий прямоугольник. Для определения какой метод надо использовать используется оценка угла по отношению площадей области и ограничивающего прямоугольника. Из простых геометрических соображений:  . α – угол между стороной квадрата и осью Ox.  – площадь ограничивающего квадрата,  – площадь области.
Очевидной проблемой такого подхода. Является то, что во всех случаях, когда срабатывает критерий малости угла мы получаем ошибку определения из-за того, что считаем в этом случае угол равным нулю. Ошибки построения области не дают нам сделать порог малым. Например, в реализации системы использовался порог 10 градусов.
 
Рисунок 6. Ошибка в определении угла. При постоянной ошибке первого рода. Слева 1/20 площади. Справа -1/20 площади
Покажем влияние ошибок на этот метод оценки, чтобы продемонстрировать, почему нельзя эту оценку самостоятельно использовать для определения угла.
Для этого построим графики влияния ошибки на разницу реального и определяемого угла.
Обратим формулу:  ;  ; Как видим, разница углов будет сложной функцией от ошибки.
Разделим ошибки, возникающие в результате неправильного определения площади фигуры (т.е. добавление и потеря пикселей), не затрагивающее углы квадрата. И ошибки «срезания» углов квадрата. Тогда оценки площадей, полученные от реальных данных, будут
для площади области и
Для площади ограничивающего прямоугольника. Здесь  аддитивная ошибка первого типа, мы будем предполагать ее принадлежащей отрезку  .  – количество углов (от 0 до 4) подвергающихся ошибке второго рода. и  являются функциями от количества углов и сдвигом внутрь фигуры из-за «срезания» угла.
 В качестве исходных параметров будем задавать , α, , , . Будем рассматривать типичный случай  , реальные значения этой площади лежат вблизи этого значения.
Рисунок 7. Зависимость ошибки по углу от ошибки по площади (-1/10...1/10) площади
Для начала построим график, считая, что ошибок второго типа нет. На рисунке (Рисунок 6) изображены графики зависимости невязки от угла поворота квадрата для постоянных значений ошибки положительного и отрицательного. Интересно, что при увеличении угла до 45 градусов наблюдается увеличение влияния постоянной ошибки. Это свойство не позволяет использовать этот метод самостоятельно для нахождения угла. Для определения, когда угол использование этого алгоритма кажется допустимым. В самом деле, при такой ошибке пороги, рассчитываемые по желаемой ошибке 5-10 градусов, могут быть использованы. Для иллюстрации этого приведем также график зависимости ошибки угла от ошибки первого типа при постоянном угле 20 градусов (Рисунок 7).
Большие ошибки по углу возникают в результате действия ошибок второго типа. Рассмотрим подробнее их влияние. Для начала определимся, что допустимыми значениями ошибок  являются значения в отрезке [0,3] причем матожидание величины ошибки не нулевое.
Значения интересующие нас 2 и 4. Т.е. ошибка действует симметрично, либо только для углов одной координаты, либо для всех четырех. Причем действие на каждый угол одинаковое. Этот факт был получен опытным путем и объясняется особенностями алгоритмов сегментации, описанными выше.
 Влияние ошибки сказывается и на площадь, считаемую по количеству точек, и на площадь ограничивающего прямоугольника.
Для площади по точкам, нам необходимо вычисть площадь угловых треугольников отрезаемых горизонтальной или вертикальной линией, располагающейся от угла на расстоянии . Площадь такого треугольника (Error: Reference source not found) будет составлять  , т.е. ошибка для площади по пикселям будет  .
Для вычисления площади ограничивающего квадрата введем размер  , тогда для количества углов 2 и 4
Сначала построим график при постоянном угле в 20 градусов и вариации ошибки error2 от -4 до 4 пикселей (Рисунок 8). Видим большой отклик при любой отрицательной ошибке (т.е. не срезания, а добавления углов), и ошибку порядка 10 градусов при ошибке срезания одного пикселя. Немного лучшая ситуация в случае двух углов, ошибка определения угла при срезании одного пикселя.
Определение позиции. Выводы.
Предположим, что сегментация, проделанная на предыдущем шаге, была произведена без ошибок, т.е. алгоритм сегментации показал свой наилучший результат, на который был способен. Замечание состоит в том, что и в этом случае мы получаем ошибку, связанную с тем, что алгоритм сегментации работает с целыми значениями пикселей, следовательно, в нем изначально заложена ошибка, связанная с дискретизацией определения границы.
 
Рисунок 8. Зависимость ошибки по углу от ошибки "срезания" углов.
Справа: подвержены 4 угла, Слева: подвержены 2 угла
Кроме того возможность возникновения ошибок потерь пикселей внутри области приводит нас к мысли о том, что необходимо вводить дополнительно алгоритм позиционирования границы и считать положение и угол по результату его работы. Кроме того, если алгоритм нахождения положения сохраняется неизменным, то алгоритм определения угла будет изменен на метод с большей аккуратностью.
Сегментация, проведенная на первом шаге, дает нам примерное положение объекта и его границы, поэтому можно ввести дополнительно алгоритм с большим количеством вычислений, так как область поиска границы достаточно мала.
|
