МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Донецкий государственный технический университет

Кафедра прикладной математики и информатики

 

 

 

 

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе на тему

"Разработка автоматизированной системы

анализа видеозаписей футбольных матчей"

 

 

 

 

Руководитель: _____________________________  доц. Ладыженский Ю.В.

                         (ПОДПИСЬ)                       (ДАТА)

 

Разработал:     _____________________________   ст. гр. ПО-01г Середа А.А.

                         (ПОДПИСЬ)                       (ДАТА)  

 

 

 

 

 

ДОНЕЦК

2005

РЕФЕРАТ

 

 

         Пояснительная записка к курсовой работе: 41 стр., 2 библ., 6 илл., 1 прил.

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

 

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

 

СОДЕРЖАНИЕ

 

 

Введение……………………………………………………………………….. 4

1.     Общее описание системы…………………………………………………. 5

1.1.  Назначение системы………………………………………………….. 5

1.2.  Требования к системе………………………………………………….6

1.3.  Выбор метода решения задачи………………………………………. 6

1.4.  Общая структура……………………………………………………….8

2.     Подсистема видеозаписи…………………………………………………..10

3.     Подсистема автоматического анализа видеозаписей…………………….11

3.1.  Общая структура……………………………………………………….11

3.2.  Модели движения объектов………………………………………….. 12

3.3.  Поиск объекта в заданной области поля в заданный момент времени...13

3.3.1.    Сравнение изображения с фоном………………………………15

3.3.2.    Поиск изображения изолированного объекта…………………18

3.3.3.    Поиск изображения неизолированного объекта………………19

3.3.4.   Алгоритм анализа формы области кадра……………………….21

3.3.5.   Отслеживание координат мяча………………………………….22

3.4.  Поиск новых объектов на поле……………………………………….23

3.5.  Алгоритм поиска всех объектов в заданный момент времени……. 24

3.6.  Алгоритм анализа видеозаписей матча……………………………...26

3.7.  Определение положения камер………………………………………27

3.8.  Фильтрация изображения…………………………………………….29

3.8.1.    Компенсация нелинейных искажений объектива камеры….. 29

3.8.2.    Компенсация дрожания камер…………………………………29

3.9.  Параллельная обработка…………………………………………….. 31

3.10.                 Распознавание игровых ситуаций………………………………32

3.11.                 Диаграмма классов………………………………………………32

4.     Подсистема анализа траекторий……………………………………….. 35

5.     Реализация алгоритмов…………………………………………………. 36

5.1.  Сравнение изображения с фоном…………………………………...36

Заключение…………………………………………………………………..38

Используемая литература………………………………………………….. 39

Приложение А. Листинг алгоритмов, используемых в

     программе SearchBack……………………………………………………40

ВВЕДЕНИЕ

 

 

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

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

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

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

1 ОБЩЕЕ ОПИСАНИЕ СИСТЕМЫ

 

 

1.1 Назначение системы

 

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

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

1. Информация о каждом игроке:

- число результативных подач;

- общее время владения мячом;

- средняя скорость;

- наиболее часто посещаемые участки поля;

- другое.

2. Определение уровня физической подготовки каждого игрока.

3. Воспроизведение различных моментов матча:

                   - анимацией;

                   - показ реальных видеозаписей.

4. Анализ тактики:

         - выявление слабых мест в защите и нападении своей команды и соперника;

         - выдача рекомендаций по улучшению игры команды.

 

1.2 Требования к системе

 

Помимо выполнения основной функции – получения и отображения существенной для тренера информации о матче информации к системе предъявляется ряд дополнительных требований:

1.     Достоверность получаемой информации должна быть как можно выше.

2.     Стоимость системы должна быть приемлема для футбольного клуба.

3.     Время анализа футбольного матча должно быть приемлемым для тренера.

4.     Система должна быть легко переносимой с одного стадиона на другой.

5.     Желательна возможность использования системы без согласия администрации стадиона и команды-противника.

6.     Система должна получать как можно больше информации автоматически и использовать как можно меньше ручного ввода информации.

 

1.3 Выбор метода решения задачи

 

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

         Таким образом, решение задачи можно разделить на 2 этапа: получение координат всех объектов на поле в каждый момент времени (далее – траекторий) и анализ полученных траекторий.

         В настоящее время автоматическое получение траекторий объектов на поле можно осуществить двумя способами:

         1. Установкой на объектах специальных датчиков.

         2. Анализом видеозаписей матча.

         К преимуществам анализа видеозаписей можно отнести следующее:

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

         2. Возможно использование системы без согласия команды-противника.

         В данной работе рассматривается получение траекторий путем анализа из видеозаписей.

Получение траекторий разбивается на 2 этапа: получение видеозаписей матча и получение собственно траекторий путем анализа полученных видеозаписей.

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

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

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

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

 

Рисунок 1.1 – процесс получения информации из видеозаписей

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

 

1.4 Общая структура

 

Общая структурная схема системы приведена на рисунке 1.2.

Рисунок 1.2 - структура схема системы

 

Отдельные подсистемы будут рассмотрены подробнее в следующих разделах.

2 ПОДСИСТЕМА ВИДЕОЗАПИСИ

 

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

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

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

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

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

 

3 ПОДСИСТЕМА АВТОМАТИЧЕСКОГО АНАЛИЗА ВИДЕОЗАПИСЕЙ

 

 

         3.1 Общая структура

 

         Пытаться искать все возможные объекты на каждом кадре нецелесообразно по затратам процессорного времени. Одним из основных принципов, положенных в основу разрабатываемой подсистемы анализа видеозаписей является использование при нахождении положений игроков в текущий момент времени информации об их положениях в предыдущие моменты времени. Под моментом времени матча понимается промежуток времени 0.05 – 0.1 с.

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

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

         В системе не используется распознавание номеров футболистов на футболках. Главная причина – низкое разрешение видеозаписей, полученных при съемке камерой с коротким фокусным расстоянием. Вместо распознавания номеров используется отслеживание футболистов вместе с заданными вручную номерами. Все сказанное справедливо и для отслеживания судей, медперсонала и остальных людей на поле.

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

         Обобщая изложенное выше, система автоматического анализа видеозаписей состоит из 3 основных частей:

1.     Математические модели движения объектов различных типов.

2.     Процедуру поиска заданного объекта в заданной области поля в заданный момент времени.

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

 

3.2   Модели движения объектов

 

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

         Рассмотрим для примера простейшую модель движения человека. Пусть максимальный модуль скорости человека равен maxv, а максимальный модуль ускорения равен maxa. Пусть в момент времени t i-й человек на поле имел скорость V=(vx,vy). Тогда можно считать, что в момент времени t+dt его скорость V1=(v1x,v1y) может принимать значения из области minvx≤v1x≤maxvx, minvy≤v1y≤maxvy, где

minvx=max(-maxv,vx-maxa*dt);

maxvx=min(maxv,vx+maxa*dt);

minvy=max(-maxv,vy-maxa*dt);

maxvy=min(maxv,vy+maxa*dt).

Для небольших интервалов dt (когда на протяжении всего интервала ускорение меняется мало) перемещение человека D=(dx,dy) может принимать занчения из следующей области:

(vx+minvx)/2*dt≤dx≤(vx+maxvx)/2*dt;

(vy+minvy)/2*dt≤dy≤(vy+maxvy)/2*dt.

Для больших dt (когда человек мог после ускоренного движения значительное расстояния двигаться с постоянной скоростью V1) верно, что

minvx*dt≤dx≤maxvx*dt;

minvy*dt≤dy≤maxvy*dt.

Эту оценку можно применять и для коротких интервалов dt.

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

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

 

         3.3 Поиск объекта в заданной области поля в заданный момент времени

 

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

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

         Перед поиском объекта в кадре координаты области его возможного положения на поле переводятся в координаты области возможного положения его изображения в данном кадре.

Из-за перспективы изображение объекта может иметь разные размеры в разных частях области кадра. Поэтому определяются ожидаемые размеры изображения в разных частях области кадра. Целесообразно для каждой камеры вычислить ожидаемые размеры изображений объектов для каждой точки кадра 1 раз до анализа видеозаписей.

         Рассмотрим 2 случая поиска изображения объекта в данном кадре:

1.     Объект изолированный – при любом положении других объектов на поле их изображения не пересекаются с областью кадра, где может находиться изображение данного объекта.

2.     Объект не изолированный – в области кадра, где может находиться изображение данного объекта, могут частично или полностью находиться изображения других объектов.

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

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

Оба используемых алгоритма поиска изображений объектов (изолированных и неизолированных) кроме координат объектов возвращают также коэффициенты надежности (далее КН). КН – целое число из интервала [0,100], показывающее, насколько можно доверять результатам поиска данного объекта. Это число используется в дальнейшем при разрешении сложных ситуаций. В сложных ситуациях алгоритмы поиска могут возвращать не одни координаты объекта, а список координат с низкими КН.

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

3.3.1 Сравнение кадра с фоновым изображением

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

Рисунок 3.1 - вычитание кадра из фонового изображения

         Данный алгоритм может давать следующие ошибки:

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

2.     За пиксели изображения объекта могут быть приняты пиксели, принадлежащие тени объекта на поле.

3.     Некоторые пиксели изображения объекта могут быть приняты за пиксели фона, если они совпадают по цвету с фоном (например, белая форма футболиста на фоне белой полосы разметки).

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

Можно уменьшить число ошибок типа 2, сравнивая цвета в цветовом пространстве не RGB, а яркость + хроматические компоненты (например, YCrCb). Пиксели поля, попавшие в тень игрока, сильно отличаются от незатененных пикселей по яркости и сабо по оттенку (хроматическим компонентам).

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

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

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

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

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

1.     Зная геометрическое положение камеры и размеры поля, строится карта ожидаемого фонового изображения. Все пиксели карты имеют значения “зеленый”, “белый” или “произвольный” (возможно использование еще нескольких цветов).

2.     Задается величина d – максимальное расстояние между пикселями карты и кадра, при котором можно считать, что пиксель кадра соответствует данному пикселю карты.

3.     Все пиксели фонового изображения помечаются как “неопределенные”.

4.     Выбирается некоторый кадр, относящийся к началу матча.

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

6.     Шаги 4-5 выполняются пока все пиксели фона той части кадра, где отображается футбольное поле, не станут “определенными”, но не более, чем N раз.

7.     Цвет каждого “неопределенного” пикселя приравнивается цвету ближайшего “определенного”.

Под соответствием цвета пикселя карты и кадра понимается то, что разность их цветов не превышает определенной величины. “Произвольный” пиксель карты может соответствовать пикселю кадра с любым цветом.

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

Считается, что оставшаяся область кадра не может содержать изображения объектов, т.е. она содержит только фоновое изображение. Затем для всех пикселей оставшейся области и соответствующих пикселей фонового изображения производится пересчет по формуле новый_пиксел_фона = старый_пиксел_фона*p + пиксел_кадра*(1-p), где 0≤p<1.

При p=0 происходит замена пикселей фона пикселями кадра. Значения p>0.5 делают обновление фона более помехоустойчивым: если случайно пиксель объекта был отнесен к фону, то цвет пикселя фонового изображения изменится, но все еще будет близок к цвету реального фона. Если при последующих обновлениях в данной точке кадра не будут находиться объекты, то его цвет вернется к правильному значению. На практике можно использовать значения p=0.8-0.9.

3.3.2 Поиск изображений изолированных объектов

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

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

3.3.3 Поиск изображений неизолированных объектов

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

Для выделения изображения неизолированного объекта был разработан следующий алгоритм:

1.     Все пиксели области, отличные от фона, помечаются как “относящиеся к неизвестному объекту”.

2.     Число_найденных_объектов = 0.

3.     Для каждого “относящегося к неизвестному объекту” пикселя запускается рекурсивная процедура заливки, которая устанавливает для него номер_объекта = число_найденных_объектов, после чего обрабатывает таким же образом все соседние “относящиеся к неизвестному объекту” пиксели. Увеличивается число_найденных_объектов. Процедура может быть выполнена поиском в ширину или глубину.

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

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

6.     Если осталась одна область, то возвращаются координаты ее центра и высокий КН.

7.     Если остались несколько областей, то определить, в какой из них находится изображение искомого объекта, не представляется возможным. Возвращается список координат подходящих областей. Для каждой области возвращается низкий КН. Ем больше осталось областей, тем ниже КН каждой из них.

Данный алгоритм корректно обрабатывает следующие сложные ситуации:

1.     Изображения любого числа игроков одной команды находятся рядом, но не пересекаются.

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

3.     Изображения любого числа игроков людей могут частично или полностью пересекаться, но при этом все люди имеют различные цвета формы (например, близко находятся игрок команды 1, игрок команды 2 и судья).

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

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

3.3.4 Алгоритм анализа формы области кадра

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

1. Установить для всех объектов признак “не проанализирован”.

2. Выбирается самое верхнее, самое нижнее, самое левое или самое правое из ожидаемых изображений “не проанализированных” объектов (по мат. модели).

3. Выделяется соответственно самая верхняя, самая нижняя, самая левая или самая правая подобласть сложной области, соответствующая изображению объекта размером 0.6x1.8 метров. В зависимости от того, насколько хорошо выбранная подобласть вписывается в область предполагаемого нахождения объекта, зависит КН данного объекта.

4. Установить для данного объекта признак “проанализирован”.

5. Выделенная подобласть проверяется на наличие цветов, соответствующих данному объекту. Если цвета найдены – переход на шаг 7.

6. Если в сложной области имеются изображения более, чем одного объекта и еще не все объекты проанализированы, перейти к п.2, иначе –  перейти к п.10

7. Поставить выбранному объекту в соответствие выбранную подобласть.

8. Удалить из сложной области все точки выбранной подобласти.

9. Перейти к п.1.

10. Если осталась область с изображениями более, чем одного объекта, то присвоить всем таким объектам координаты центра этой области и самый низкий КН.

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

3.3.5 Отслеживание координат мяча

Отслеживание координат мяча существенно отличается от отслеживания людей:

1. Мяч имеет малые размеры.

2. Мяч может имеет высокую скорость.

3. Мяч перемещается в трехмерном пространстве.

4. Изображение мяча часто сливается с изображением игроков.

5. Летящий мяч трудноразличим на фоне трибун.

В разрабатываемой системе мяч в каждый момент времени может находиться в одном из 3 состояний:

1. Свободен

2. Находится у определенного игрока.

3. Потерян

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

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

Когда мяч потерян, каждые несколько кадров на его наличие проверяется все поле.

Мяч многократно переходит из одного состояния в другое в процессе игры.

 

3.4 Поиск новых объектов на поле

 

Кроме отслеживания координат существующих объектов необходимо раз в несколько секунд производить поиск новых объектов. Новые объекты – люди, перешедшие на поле из не анализируемой зоны вокруг поля. Если максимальная скорость человека v, а время, через которое производится поиск новых объектов t, то достаточно искать новые объекты в зоне шириной v/t метров, прилегающей к краям поля.

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

 

3.5   Алгоритм поиска всех объектов в заданный момент времени

 

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

Был разработан следующий алгоритм:

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

2.      (собственно поиск объекта) Для каждого объекта: повторять шаги 3-6.

3.      Получить упорядоченный список камер в порядке удобства их использования для области данного объекта.

4.      Если объект изолирован, выполнить его поиск на кадре 1-й камере из списка как изолированного, иначе – как не изолированного.

5.      Если получен высокий КН или в списке 1 камера – перейти к шагу 6, иначе – удалить 1-ю камеру в списке и перейти к шагу 4.

6.      Из всех списков возможных координат объекта, полученных при анализе кадров разных камер, выбрать список с наибольшим КН элементов.

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

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

9.      Удалить из временного списка одинаковые координаты.

10.  Для всех координат из временного списка: добавить к списку объектов новый объект с новым номерам, данными координатами и высоким КН. Для нового номера запомнить, из каких номеров он мог быть получен.

11.  Если мяч свободен, произвести его поиск в области, определенной моделью его движения, если потерян – на всем поле, если принадлежит игроку и текущее время делится на некоторую константу – то произвести его поиск в области вокруг имеющего мяч игрока. В зависимости от результатов поиска, возможно, изменить состояние мяча.

12.  Обновить модели движения всех объектов с высоким КН и инициализировать модели вновь появившихся объектов.

Для примера рассмотрим коллизию с участием двух игроков одной команды. До того, как они сблизились, они имели различные координаты и высокий КН. После того, как они сблизились и их изображения стали пересекаться, они все еще имели высокие КН, но их координаты стали одинаковыми (и, соответственно, области возможно положения стали почти накладываться). Когда они разошлись достаточно далеко, в области возможного положения каждого из них возникло 2 изображения, причем каждое из них могло принадлежать каждому игроку. Следовательно, оба игрока получили низкий КН. На шагах 8-10 игроки будут удалены из списка объектов и заменены новыми. Условие на минимальное расстояние в D метров гарантирует, что после инициализации моделей объекты окажутся достаточно далеко и в следующий момент времени им не будут присвоены новые номера.

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

 

3.6   Алгоритм анализа видеозаписей матча

 

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

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

2. Задать начальный фон для всех камер.

3. Очистить список известных объектов.

4. Произвести поиск новых объектов на поле.

5. Повторять шаги 6-9 для всех моментов времени матча.

6. Произвести поиск известных объектов на поле в областях их возможного нахождения.

7. Если номер_кадра mod N1=0, то произвести поиск новых объектов на поле.

8. Сохранить координаты и номера всех объектов.

         9. Если номер_кадра mod N2 =0, то обновить фон.

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

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

 

         3.7 Определение положения камер

 

         Системе необходимо иметь некоторую информацию для правильного преобразования координат точки из СК поля в СК кадра и обратно. Эти данные предполагается вводить вручную. Система ручного вода положения камер должна:

1.            Вводить или вычислять все данные, необходимые для преобразования координат из системы координат (далее СК) поля в систему координат кадра камеры и обратно.

2.            Быть достаточно точной.

3.            Быть удобной в использовании.

Например, непосредственный ввод трехмерных координат камеры на стадионе в СК, связанной с полем, и углов ее поворота является неудобным для пользователя и недостаточно точным. Это обусловлено трудностью измерения указанных величин.

Для перевода координат из СК поля в СК кадра камеры и обратно необходимо также знать оптические характеристики камеры – фокусное расстояние ее объектива в 35 мм эквиваленте или угол обзора.

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

Центральное проецирование точки поля в точку кадра одной из камер можно описать следующими формулами:

x’ = a1*x+b1*y+d1*z+c1;

y’ = a2*x+b2*y+d2*z+c2;

z’ = a3*x+b3*y+d3*z+c3;

x” = x’ / z’;

y” = y’ / z’;

Здесь (x,y,z) – координаты точки в СК поля, а (x”,y”) – координаты точки в СК кадра. Для всех объектов на поле примем z=0 и получим:

x’ = a1*x+b1*y+c1;

y’ = a2*x+b2*y+c2;

z’ = a3*x+b3*y+c3;

x’ = x” * z’;

y’ = y” * z’;

Исключим x’, y’ и z’:

a1*x+b1*y+c1 = x” * (a3*x+b3*y+c3);

a2*x+b2*y+c2 = y” * (a3*x+b3*y+c3);

Здесь искомыми величинами являются коэффициенты a1, b1, c1, a2, b2, c2, а известными – x, y, x”, y”. Чтобы определить 9 искомых величин необходимо 9 уравнений. Поскольку ввод одной точки дает 2 уравнения, необходимо указать как минимум 5 точек. Можно указать большее число точек, при этом коэффициенты, найденные по различным группам точек, будут усредняться и точность результата будет выше.

Приведенный способ является достаточно точным и удобным для пользователя.

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

 

3.8 Фильтрация изображений

 

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

3.8.1 Компенсация нелинейных искажений объектива камеры

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

1.     Найти элементы матриц DX и DY такие, что точка кадра с координатами (x,y) и идеальным объективом соответствует точке (DX[x,y], DY[x,y]) с реальным объективом.

2.     Для каждой точки кадра (x,y) использовать вместо нее точку (DX[x,y], DY[x,y]).

Преобразование выполняется 1 раз для всех точек каждой области кадра до ее анализа. Алгоритму поиска объектов в области подается на вход не область реального кадра, а область, состоящая из его точек, смещенных согласно матрицам DX и DY.

Для камер с малыми геометрическими искажениями для ускорения процесса анализа видео указанную фильтрацию можно не выполнять.

3.8.2 Компенсация дрожания камер

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

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

Фильтрацию можно осуществить непосредственно перед анализом текущего момента времени следующим образом:

1.     Некоторый кадр данной камеры принимается за эталонный.

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

3.     Для кадра каждой камеры выполнить шаги 4-5.

4.     Для каждого отобранного участка эталонного кадра, в котором на данном кадре не может быть объекта: определяется такие dx и dy (–maxd ≤ dx, dy ≤ maxd), что при сдвиге данного кадра на dx и dy по горизонтали и вертикали соответственно достигается наилучшее совмещение данного участка эталонного и данного кадров. Если при всех dx и dy разница между участками превышает пороговую величину, то данный участок в дальнейшем не рассматривается.

5.     По списку dx и dy для различных участков вычисляется сдвиг вдоль оси x и y и угол поворота для всего кадра. По ним вычисляются коэффициенты a1, a2, b1, b2, такие, что компенсацию дрожания данного кадра можно выполнить по формулам x’=x+a1*y+b1, y’=y+a2x+b2.

Таким образом, когда анализируется пиксель кадра с координатами (x,y), вместо должен быть проанализирован пиксель с координатами (x+a1*y+b1,y+a2x+b2).

Полное преобразование, выполняющее необходимое аффинное преобразование, имеет вид x’=c1*x+a1*y+b1, y’=c2*y+a2x+b2. Однако c1 и c2 на практики должны быть очень близки к 1 и ими можно пренебречь.

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

 

         3.9 Параллельная обработка

 

         Для уменьшения времени анализа видеозаписей процесс анализа можно выполнять на любом числе процессоров одновременно почти без снижения производительности. Для этого каждый i-й процессор обрабатывает свой период времени матча [t_i,t_i+1]. Объединение результатов работы разных процессоров i и i+1 состоит в нахождении соответствия между объектами, присутствующими на поле в момент времени t_i+1 и обнаруженных i-м процессором в конце его анализируемого периода, а i+1-м – в начале. Эта задача является достаточно простой.

На практике целесообразно использовать несколько обычных компьютеров, объединенных в локальную сеть (кластер). Требования к пропускной способности сети низки, т.к. во время вычислений обмена данными между вычислительными узлами не происходит.

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

3.10Распознавание игровых ситуаций

 

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

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

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

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

 

3.11 Диаграмма классов

 

Система разрабатывается на языке программирования C++ с использованием  объектно-ориентированного подхода.

Основные классы подсистемы автоматического анализа видеозаписей:

1. CVideoFile – инкапсулирует все действия, связанные с открытием и чтением одного видеофайла;

2. CPixel – цвет одного пикселя и операции над ним.

3. CBackground – содержит и обновляет фоновое изображение для камеры.

4. CCamera – содержит ссылку на CVideoFile, CBackground, геометрические параметры камеры, процедуры преобразования координат, процедуру ввода положения камеры, фильтрацию изображения и определение принадлежности пикселя к фону.

5. CArea – содержит описание области поля или кадра.

6. CImage – содержит изображение одного кадра или его области. Возвращается методами классов CVideoFile и CBackground как результат.

7. CGame – содержит дополнительные сведения о матче (например, цвета команд) и процедуры их ввода.

8. CTraceTable – таблица с траекториями объектов.

9. CVideoAnalyser – главный класс подсистемы. Содержит классы всех камер и экземпляр CGame, инкапсулирует общий алгоритм анализа видео и алгоритм поиска всех объектов в данный момент времени. Как результат генерирует CTraceTable.

10. CGameObject – базовый класс всех объектов на поле. Он его потомки содержат методы, соответствующие поиску изображений объекта на поле в кадре.

11. CBall:: CGameObject – модель движения и свойства мяча.

12. CMan:: CGameObject – модель движения и свойства человека.

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

         Диаграмма классов подсистемы автоматического анализа видеозаписей представлена на рисунке 3.2.

Рисунок 3.2 - диаграмма классов подсистемы автоматического анализа видеозаписей

4 ПОДСИСТЕМА АНАЛИЗА ТРАЕКТОРИЙ

 

 

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

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

Может быть реализована функция определения физической подготовки игрока на основе его статистических данных.

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

         Будет предусмотрена возможность воспроизведения отдельных моментов матча как анимацией, так и реальными видеозаписями, использовавшимися при анализе.

         Сложная экспертная система, анализирующая тактику, реализована не будет.

5 РЕАЛИЗАЦИЯ АЛГОРИМОВ

 

 

5.1   Сравнение изображения с фоном

 

Была создана тестовая программа SearchBack, реализующая поиск изолированных объектов путем сравнения кадра и фонового изображения. Экран программы состоит из 3 частей. В верхней части находятся управляющие кнопки, в нижней левой – изображение кадра, в нижней правой – изображение фонового рисунка. Экранная форма программы приведена на рисунке 5.1.

Рисунок 5.1 - экранная форма программы SearchBack

 

При нажатии на кнопку “Загрузить тестовые данные” программа открывает изображения поля и фона из текущей директории, находящиеся в файлах frame.bmp и back.bmp и файл с координатами областей кадра, в которых находятся объекты coord.txt.

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

Файл coord.txt имеет следующую структуру: в каждой строке находятся 4 целых числа – координаты левого верхнего и правого нижнего углов прямоугольной области, где находится некоторый объект.

При нажатии на кнопку “ Найти неизвестные объекты” программа производит поиск объектов на всем пространстве кадра, не используя данных из файла coord.txt. В случае нахождения рядом нескольких объектов программа может неправильно их определять, поскольку вокруг каждой точки, отличной от фона, ищутся лишь изолированные объекты.

Листинг алгоритмов, реализованных в программе SearchBack, приведен в приложении А.

 

ЗАКЛЮЧЕНИЕ

 

 

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

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

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

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

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

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