МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Донецкий государственный технический университет
Кафедра прикладной математики и информатики
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к научно-исследовательской работе студента на тему
"Системы автоматизированного анализа
футбольных матчей"
Руководитель: _____________________________ доц. Ладыженский Ю.В.
(ПОДПИСЬ) (ДАТА)
Разработал: _____________________________ ст. гр. ПО-01г Середа А.А.
(ПОДПИСЬ) (ДАТА)
ДОНЕЦК
2005
РЕФЕРАТ
Пояснительная записка к научно-исследовательской работе студента: 36 стр., 2 библ., 2 илл.
Работа посвящена обзору существующих автоматизированных систем анализа футбольных матчей и описанию основных алгоритмов, используемых в системах анализа видеозаписей спортивных соревнований.
ФУТБОЛ, МАТЧ, АНАЛИЗ, ДАТЧИК, КАМЕРА, ВИДЕОЗАПИСЬ, ИЗОБРАЖЕНИЕ, РАСПОЗНАВАНИЕ, ПОИСК, ОТСЛЕЖИВАНИЕ, АЛГОРИТМ, ФИЛЬТРАЦИЯ
СОДЕРЖАНИЕ
Введение………………………………………………………………………… 4
Общее описание системы……………………………………………………6
Назначение системы…………………………………………………….6
Требования к системе………………………………………………….. 6
Общий подход к решению задачи…………………………………….. 7
Обзор существующих решений……………………………………………..10
Системы записи и просмотра видеозаписей без анализа мачта……...10
Системы на основе датчиков…………………………………………...10
Orad…………………………………………………………………11
Trakus……………………………………………………………….11
Системы анализа видеозаписей………………………………………..12
ProZone……………………………………………………………..12
Sport Universal …………………………………………………….13
Lucent Vision………………………………………………………13
ИТС Zenit………………………………………………………….13
Обзор используемых алгоритмов…………………………………………..15
Общие подходы к анализу видеозаписей……………………………..15
Независимый анализ различных моментов времени…………..16
Анализ с учетом предыдущих моментов времени……………..17
Коллизии и их разрешение………………………………………17
Отслеживание положения мяча…………………………………18
Математические модели движения объектов………………………..18
Алгоритмы поиска изображений объектов в кадре…………………20
Сравнение кадра с фоновым изображением……………………21
Сравнение кадра с предыдущим кадром………………………..24
Поиск в кадре определенных цветов……………………………25
Поиск неизолированных объектов………………………………26
Сравнение с шаблонами…………………………………………29
Другие алгоритмы………………………………………………30
Алгоритмы фильтрации изображения………………………………30
Выравнивание яркости участков поля…………………………31
Повышение резкости изображения…………………………….31
Компенсация нелинейных искажений объектива камеры……31
Компенсация дрожания камер………………………………….32
Фильтрация теней……………………………………………….33
Фильтрация шума……………………………………………….34
Заключение……………………………………………………………………35
Используемая литература……………………………………………………36
ВВЕДЕНИЕ
Перед каждым тренером футбольной команды стоит задача как можно сильней повысить эффективность игры своей команды. Чтобы правильно определять стратегию игры команды и основное направление тренировок тренер должен обладать различной информацией о текущем состоянии команды в целом и каждого ее игрока. Не менее важной является подробная информация о команде-противнике, позволяющая лучше использовать слабые стороны этой команды.
Одним из основных источников подобной информации являются футбольные матчи (как официальные, так и тренировочные). Получить всю ценную информацию непосредственно из просмотра мачта, не упустив ни одной важной детали, – невыполнимая задача даже для опытного тренера. Человек не может следить за всем полем сразу и запоминать все важные события.
Тренеры часто используют запись матча на видео и для последующего просмотра и анализа видеозаписей. Такой способ позволяет получить гораздо больше ценной информации о матче, однако является весьма трудоемким. Для уменьшения затрат времени на анализ матча и повышения его эффективности необходимо автоматизировать процесс получения существенной для тренера информации о матче.
Таким образом, в настоящее время востребованы автоматизированные системы, предназначенные для тренеров футбольных команд, производящие автоматический анализ футбольных матчей и предоставляющие тренерам информацию в удобном и наглядном виде.
На рынке существуют несколько подобных систем. Однако каждая из них обладает своими недостатками – высокой стоимостью, недостаточной мобильностью, неудобным представлением информации.
Все перечисленное в той или иной степени справедливо для всех игровых видов спорта, однако, благодаря очень высокой популярности футбола в современном мире, для него эта задача наиболее актуальна.
У систем анализа матчей есть еще одно практическое применение – организация интернет-трансляции спортивных соревнований и предоставление телезрителям дополнительной информации о матче в реальном времени. Информация о проанализированном матче может быть передана по низкоскоростным линиям связи и затем быть визуализирована на компьютерах пользователей средствами 3D-графики.
1 ОБЩЕЕ ОПИСАНИЕ СИСТЕМЫ
1.1 Назначение системы
Разрабатываемая система предназначена для получения и отображения в удобном для анализа виде различной информации о футбольном матче. Получаемая информация предназначена для тренера футбольной команды и должна быть существенна для него. К существенной информации, которую система может выдать тренеру, можно отнести следующее:
1. Информация о каждом игроке:
- число результативных подач;
- общее время владения мячом;
- средняя скорость;
- наиболее часто посещаемые участки поля;
- другое.
2. Определение уровня физической подготовки каждого игрока.
3. Воспроизведение различных моментов матча:
- анимацией;
- показ реальных видеозаписей.
4. Анализ тактики:
- выявление слабых мест в защите и нападении своей команды и соперника;
- выдача рекомендаций по улучшению игры команды.
1.2 Требования к системе
Помимо выполнения основной функции – получения и отображения существенной для тренера информации о матче информации к системе предъявляется ряд дополнительных требований:
Достоверность получаемой информации должна быть как можно выше.
Стоимость системы должна быть приемлема для футбольного клуба.
Время анализа футбольного матча должно быть приемлемым для тренера.
Система должна быть легко переносимой с одного стадиона на другой.
Желательна возможность использования системы без согласия администрации стадиона и команды-противника.
Система должна получать как можно больше информации автоматически и использовать как можно меньше ручного ввода информации.
1.3 Общий подход к решению задачи
Условно разделим всю информацию о матче на первичную и вторичную. К первичной отнесем информацию о перемещении игроков и мяча по полю во время матча и различные существенные для игры действия игроков и судьи (удар по мячу, удаление с поле, и т.д.). Ко вторичной информации отнесем различную статистическую информацию об игроках, команде в целом и информацию, полученную при анализе тактики команды.
Наиболее ценной для тренера является вторичная информация, т.к. ее получения связано с большими трудозатратами. Однако удобное и наглядное представление тренеру первичной информации (воспроизведений анимации или видеозаписи определенных моментов матча) также важно.
Всю вторичную информацию о матче можно получить из первичной. Таким образом, решение задачи, выполняемое системой, можно разделить на 2 этапа:
Получение первичной информации о матче.
Получение вторичной информации из первичной.
Первичная информация может обладать разной степенью подробности. Например, при анализе фола существенной является информация о положении отдельных частей тел игроков. Автоматизированное получение такой информации является очень сложной задачей. Для анализа большинства ситуаций тренеру достаточно знать лишь координаты игроков и мяча на поле. В ситуации, когда требуется более подробная информация о происходящем на поле, тренер может обратиться к визуальному анализу видеозаписи интересующего его момента. Таким образом, в автоматизированной системе можно ограничить степень подробности первичной информации о матче движениями людей и мяча как неделимых объектов.
Далее для краткости будем обозначать всех людей, находящихся на поле во время матча (игроки, судьи, медперсонал) и мяч просто объектами.
Можно определить первичную информацию как совокупность координат каждого объекта в каждый момент времени и некоторой дополнительной информации. Дополнительная информация может включать в себя:
Протокол всех событий игры (приход игроков на поле и уход игроков с поля, получение и потеря игроком мяча, нарушение правил, пенальти, угловой, и т.д.).
Номер игрока, владеющего мячом в каждый момент времени.
Состояние игрока (например, стоит/бежит или сидит/лежит).
Большая часть дополнительной информации может быть получена из основной или не является очень важной для анализа матча. Есть смысл включать такую дополнительную информацию в первичную ради повышения удобства последующего анализа первичной информации и повышения ее наглядности.
В дальнейшем для краткости первичная информация рассматривается лишь как совокупность координат каждого объекта в каждый момент времени (далее – траекторий объектов).
В настоящее время автоматическое получение траекторий объектов на поле можно осуществить двумя способами:
1. Установкой на объектах специальных датчиков на объектах.
2. Анализом видеозаписей матча.
Соответственно, существующие системы подразделяются на 2 группы: получающие траектории путем анализа видеозаписей или путем анализа данных, полученных от датчиков. Возможен также комбинированный способ.
ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ
Системы записи и просмотра видеозаписей без анализа матча
Системы такого типа выполняют следующие типичные функции:
Осуществляют запись футбольного матча одной или несколькими камерами.
Позволяют просматривать отснятые видеозаписи, при этом осуществляют удобный и быстрый выбор просматриваемого момента матча, приближаю/отдаляют изображение, позволяют просматривать момент матча сразу с нескольких точек, и т.д.
Позволяют протоколировать различные события матча и просматривать полученные протоколы вместе с видеозаписями.
Позволяют производить некоторый монтаж видеозаписей матча.
Системы этого типа появились довольно давно. Как видно, они не отвечают всем поставленным в данной работе требованиям, поскольку не производят никакого автоматического анализа матча. В то же время, они также повышают эффективность труда тренера и стоят гораздо дешевле систем, производящих анализ мачта. Поэтому они могут рассматриваться как более дешевая альтернатива системам, анализирующим матч.
К таким системам относятся австралийская система Sportstec и итальянская система Digital Soccer.
Системы на основе датчиков
Большим достоинством таких систем является возможность получать координаты спортсменов в реальном времени без больших объемов вычислений и независимо то сложности ситуации на поле. Поэтому их особенно хорошо использовать при организации вещания спортивных соревнований по телевидению или через интернет.
Главный недостаток подобных систем – необходимость размещать датчики на игроках и спортивном снаряде, что может быть невозможно осуществить при несогласии организаторов матча или команды-соперника.
2.2.1 Orad
Компания Orad разрабатывает системы анализа и визуализации спортивных соревнований, созданные главным образом для телевизионных и интернет-трансляций.
Разработанная этой компанией система SporTrack использует датчики весом 20 грамм, установленные на игроках для отслеживания их положения.
Система предоставляет большое количество статистической информации о каждом игроке и игре в общем.
Система ToPlay Soccer способна в реальном времени визуализировать матч средствами 3D-графики и смотреть на поле под любым углом. Информация, используемая для моделирования матча, получается как путем отслеживания игроков, так и путем ручного вода.
2.3.2 Trakus
Компания Trakus разрабатывает систему Digital Sports Information, использующую датчики для отслеживания в реальном времени перемещений спортсменов на различных спортивных соревнованиях.
Одна из задач, решаемых системой – предоставление в реальном времени информации о спортивном матче для теле- и интернет- трансляций. Другая задача – предоставление различной информации о спортивных соревнованиях тренерам.
В настоящее время система поддерживает следующие виды спорта: хоккей, гольф и мотоспорт.
Компания Trakus разрабатывает систему, использующую комбинацию датчиков и анализа видео для отслеживания игроков и мяча в американском футболе.
Системы анализа видеозаписей
К преимуществам анализа видеозаписей перед использованием датчиков можно отнести следующее:
1. Не требуется никакой специальной аппаратуры кроме видеокамер, устройств оцифровки полученных видеозаписей (если используются аналоговые видеокамеры) и компьютеров для анализа полученных записей.
2. Можно получать информацию о команде-сопернике даже без ее согласия.
3. Даже при использовании датчиков для последующего визуального анализа желательно иметь также видеозаписи матча.
Исходя из этого, для анализа футбольных матчей после игры, а не в реальном времени применение систем на основе анализа видеозаписей выглядит более удобным.
2.4.1 ProZone
ProZone – английская компания, разрабатывающая систему анализа видеозаписей футбольных матчей. Анализ матчей состоит из 4 частей: анимация, анализ игры, фитнес и статистика.
В режиме анимации игроки представлены кружками. Можно просматривать как анимацию всех или выбранных игроков.
Во всех режимах работы система предоставляет очень много числовой и визуальной информации об игре.
Система использует 8 камер, расположенных вокруг стадиона, а также человека-оператора. Оператор не только протоколирует игровые события типа фолов, но и помогает системе анализа видео.
ProZone – стационарная система. Ее установка на стадион стоит 100000 фунтов. Анализ каждой игры также стоит денег.
Этой системой пользуются футбольные клубы Манчестер Юнайтед и Арсенал.
К основным недостаткам данной системы можно отнести ее стационарность, высокую стоимость и большое количество вводимой вручную информации.
2.4.2 Sport Universal
Sport Universal – французская компания, разрабатывающая большое число программ для анализа спортивных соревнований как для футбольных клубов, так и для СМИ.
Разработанная этой компанией система Amisco System использует камеры, расположенные вокруг стадиона операторов ручного ввода. Операторы протоколируют игровые события. Система оцифровывает информацию в реальном времени.
Amisco Pro – система, анализирующая данные, полученные системой Amisco System. Ее функции очень похожи на функции системы ProZone. Анализ матча состоит из 3 частей: анимации, анализа тактики и физического анализа.
Эту систему используют 5 французских, 7 испанских клубов и 2 итальянских футбольных клуба.
Система имеет те же недостатки, что и ProZone – высокую стоимость, стационарность и большой объем ручного ввода.
Lucent Vision
Эта компания разрабатывает систему для анализа и визуализации теннисных матчей. Используется большое число высокоскоростных камер. Система способна обрабатывать информацию в реальном времени и передавать полученные данные по сети.
В связи с серьезными отличиями анализа видеозаписей теннисных и футбольных матчей, данная система не относится к предмету рассмотрения данной работы.
2.4.4 ИТС “Zenit”
Российская разработка – система ИТС "Zenit" решает следующие задачи: видеосъёмка хоккейной площадки или её фрагмента и вывод видеоизображения на монитор оператора, запись на жёсткий диск компьютера фрагментов матча или тренировки, просмотр записанных видеофрагментов, в том числе и покадровый.
Автоматический анализ записанных видеофрагментов включает нахождение скоростей и траекторий спортсменов, расчёт и отображение биомеханических и физиологических параметров движения объектов слежения на выделенном фрагменте тренировки или матча.
Поддерживается динамическое моделирование анализируемых тактических построений игры в тренировочном занятии с обратной визуальной связью (как надо сделать - как сделал - разбор ошибок).
3 ОБЗОР ИСПЬЗУЕМЫХ АЛГОРИТМОВ
3.4 Подходы к анализу видеозаписей
Любой анализ видеозаписи в общем случае включает в себя анализ отдельных кадров и объединение информации, полученной при анализе различных кадров.
В случае системы анализа матчей на основе одной видеозаписи анализ кадра включает в себя нахождение координат объектов в кадре (или на поле),
Задача нахождения всех людей на одном кадре является практически решаемой за приемлемое время и с приемлемой точностью. При этом будут найдены координаты игроков, относящихся к разным командам. Определение номеров всех футболистов в кадре без учета других кадров возможно лишь путем распознавания номеров на футболках. Эта задача является практически трудноразрешимой по следующим причинам:
Изображение номера на футболках может быть очень сильно искажено.
Разрешающая способность недорогих камер недостаточна для номеров, особенно для футболистов на дальнем от камеры краю поля.
Во многие моменты времени номер футболиста не виден на кадрах со всех камер (например, когда за его спиной находится другой футболист).
Таким образом, объединение результатов обработки различных кадров должно включать нахождение соответствия между объектами на соседних кадрах. Это делает возможным отслеживание координат объектов вместе с их единожды определенными номерами.
В реальных системах кадры, полученные с разных камер, покрывают различные участки поля. Каждый объект может одновременно присутствовать на одних кадрах и отсутствовать на других. При этом в зависимости от положения камер и объекта кадры с различных камер могут лучше или хуже подходить для определения координат данного объекта. Поэтому поиск объектов в определенный момент времени матча производится не в одном кадре, а сразу в нескольких кадрах, снятых в этот момент. Координаты объектов при этом должны быть представлены в только в СК поля. Поэтому далее будем различать поиск изображения объекта в данном кадре и поиск объекта в данный момент времени матча.
Для анализа можно использовать черно-белые и цветные видеозаписи. Оцифрованные черно-белые видеозаписи занимают меньше места и в некоторых случаях их анализ можно провести быстрее. Однако, цветные видеозаписи содержат гораздо больше информации, чем черно-белые и их анализ может быть более точным. Поскольку сейчас почти все камеры являются цветными и разница в цене между ними и черно-белыми камерами незначительна, использование цветных записей выглядит предпочтительным.
3.1.1 Независимый анализ различных моментов времени
Один из очевидных методов анализа видеозаписей – определение координат всех объектов в каждый момент времени, а затем нахождение соответствий между объектами, обнаруженными в соседние моменты времени матча. При этом некоторому объекту, обнаруженному момент времени t ставится в соответствие один из ближайших к нему объектов того же типа, найденный в момент времени t+dt.
Некоторые области поля присутствуют сразу на нескольких кадрах, относящиеся к одному моменту времени, но разным камерам. Из-за погрешностей определения координат объект, изображение которого находится сразу на нескольких кадрах, может иметь разные координаты в СК при определении его положения на этих кадрах. Поэтому также требуется процедура сопоставления объектов, найденных на разных кадрах в один момент времени. Частичным решение этой проблемы является анализ каждой области поля только на одном из кадров, однако и в этом случае должно присутствовать небольшое перекрытие областей, иначе возможно не обнаружить объект, находящийся на стыке областей.
3.1.2 Анализ с учетом предыдущих моментов времени
Предыдущий подход к анализу видеозаписей требует много процессорного времени, поскольку анализируются все участки поля на разных кадрах. Время анализа видеозаписей можно существенно сократить, используя информацию о положении объектов в предыдущий момент времени. При этом их поиск в текущий момент времени производится только в областях кадров, соответствующих областям поля, в которых объект может находиться в данный момент.
Для предсказания областей возможного положения объектов в текущий момент времени строятся математические модели их движения, учитывающие кинематические характеристики объектов.
При поиске каждого объекта можно выбирать кадр, лучше всего подходящий для анализа области его возможного положения. Таким образом, можно не решать задачу сопоставления объектов в разных кадрах в один момент времени.
Задача нахождения соответствия между объектами в соседние моменты времени возникает, когда несколько объектов одного типа находятся рядом и их области возможного нахождения на поле пересекаются.
Еще одно преимущество описываемого подхода перед независимым анализом различных моментов времени – легкость определения положения мяча. Определение положения мяча является трудноразрешимой задачей, т.к. он имеет малые размеры, часто сливается с изображением игрока и может быть не виден в полете на фоне трибун. Однако, зная область возможного положения мяча можно найти его в этой области с достаточно высокой точностью.
3.1.3 Коллизии и их разрешение
Под коллизиями понимаются ситуации, когда рядом оказываются несколько игроков одной команды и их изображения в кадре перекрываются. После того как они расходятся, часто бывает невозможно определить, кто из игроков имел номер до столкновения какой номер. В этой ситуации система может попытаться проанализировать использовать изображение того же участка поля, полученное с другой камеры или попытаться провести детальный анализ столкновения и отследить движение игроков, когда их изображения в кадре перекрываются.
Когда системе не удается отследить объекты при столкновении, требуется ручное указание их номеров. Ручной ввод можно осуществлять сразу при обнаружении нераспознаваемой ситуации. Другой подход заключается в том, что при обнаружении нераспознаваемой ситуации система откладывает ручной ввод до окончания анализа всего матча. После окончания автоматического анализа производится ручной ввод информации сразу о всех коллизиях. Такой подход является предпочтительным, так как позволяет более эффективно использовать время оператора, производящего ручной ввод.
3.1.4 Отслеживание положения мяча
Отслеживание координат мяча существенно отличается от отслеживания людей:
1. Мяч имеет малые размеры.
2. Мяч может имеет высокую скорость.
3. Мяч перемещается в трехмерном пространстве.
4. Изображение мяча часто сливается с изображением игроков.
5. Летящий мяч трудноразличим на фоне трибун.
Когда мяч находится у определенного игрока, нецелесообразно пытаться отслеживать его как отдельный объект. Лучше пометить соответствующего игрока как “имеющего мяч” и отслеживать координаты игрока. При этом важно не упустить момент потери мяча игроком.
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 группы:
Алгоритмы, применяемые к области кадра, в которой находится изолированный объект.
Алгоритмы, применяемые к области кадра, в которой могут находиться неизолированные объекты.
Алгоритмы, способные анализировать коллизии.
Далее рассмотрим различные алгоритмы подробнее.
К группам 1 и 2 можно отнести следующие часто используемые га практике алгоритмы и их комбинации:
1. Сравнение кадра с фоновым изображением.
2. Сравнение кадра с предыдущим кадром.
3. Поиск в кадре определенных цветов.
Эти алгоритмы по определенным признакам классифицируют пиксели кадра как относящиеся к изображениям объектов или относящихся к фоновому изображению (полю или трибунам).
При поиске изолированного объекта в некоторой области известно, что все точки данной области, относящиеся к изображения объектов, относятся к изображению данного объекта. Поэтому для нахождения центра изображения объекта достаточно любым из этих алгоритмов найти центр масс точек, относящихся к объектам.
Процедура поиска изображений неизолированных объектов с использованием этих алгоритмов несколько сложнее и рассмотрена в соответствующем разделе.
Существует и множество других, не рассмотренных в данной работе алгоритмов.
Сравнение кадра с фоновым изображением
Пусть для данной камеры имеется фоновое изображение – кадр, на котором запечатлено поле без объектов на нем (т.е. без судьи, игроков и мяча). Тогда сравнивая попиксельно некоторый кадр с фоном (или вычитая попиксельно одно изображение из другого) можно определить пиксели, принадлежащие объектам. Большинство пикселей, не принадлежащих объектам, будут у этих двух изображений иметь близкие цвета и их разность будет близка к 0. Большинство пикселей, принадлежащих объектам, будут по цвету отличаться от фона и их разность будет далека от 0. Иллюстрация к вычитанию кадра из фонового изображения приведена на рисунке 3.1.
Рисунок 3.1 - вычитание кадра из фонового изображения
Пиксель считается относящимся к изображению объекта, ели он отличается по цвету от соответствующего пикселя фона более, чем на некоторую предельную величину.
Данный алгоритм может давать следующие ошибки:
За пиксели изображения объекта могут быть приняты случайные помехи, свойственные записи любой недорогой видеокамеры.
За пиксели изображения объекта могут быть приняты пиксели, принадлежащие тени объекта на поле.
Некоторые пиксели изображения объекта могут быть приняты за пиксели фона, если они совпадают по цвету с фоном (например, белая форма футболиста на фоне белой полосы разметки).
Можно уменьшить число ошибок типа 1 и 2, используя соответствующие фильтры.
Следует отметить, что даже без дополнительной фильтрации алгоритм все равно обладает достаточно высокой точностью.
Для работы алгоритма требуется постоянно иметь в памяти фоновое изображение для каждой камеры. Это изображение может меняться при изменении времени суток и погодных условий, поэтому его необходимо периодически пересчитывать.
Первоначальное задание фонового изображения может быть выполнено вручную, автоматически или комбинированным методом.
Ручное задание заключается в указании программе для каждой камеры одной или нескольких областей одного или нескольких кадров, которые нужно считать фоновым изображением. При этом объединение всех указанных областей должно полностью покрывать часть кадра, на которой изображается поле.
Автоматическое задание фонового изображения для каждой камеры можно осуществить, например, следующим алгоритмом:
Зная геометрическое положение камеры и размеры поля, строится карта ожидаемого фонового изображения. Все пиксели карты имеют значения “зеленый”, “белый” или “произвольный” (возможно использование еще нескольких цветов).
Задается величина d – максимальное расстояние между пикселями карты и кадра, при котором можно считать, что пиксель кадра соответствует данному пикселю карты.
Все пиксели фонового изображения помечаются как “неопределенные”.
Выбирается некоторый кадр, относящийся к началу матча.
Для каждого “неопределенного” пикселя фонового изображения проверяется: можно ли соответствующий пиксель кадра считать пикселем фона. Пиксель считается относящимся к фону, если среди пикселей карты, отстоящих от него не более, чем на d, имеется пиксель, соответствующий ему по цвету. Если проверка пройдена успешно, цвет пикселя кадра копируется в соответствующий пиксель фонового изображения и пиксель фона помечается как “определенный”.
Шаги 4-5 выполняются пока все пиксели фона той части кадра, где отображается футбольное поле, не станут “определенными”, но не более, чем N раз.
Цвет каждого “неопределенного” пикселя приравнивается цвету ближайшего “определенного”.
Под соответствием цвета пикселя карты и кадра понимается то, что разность их цветов не превышает определенной величины. “Произвольный” пиксель карты может соответствовать пикселю кадра с любым цветом.
Обновление уже существующего фонового изображения можно осуществить следующим алгоритмом. Пусть в текущий момент известны координаты всех объектов на поле. Для каждой камеры производится перевод координат всех объектов из системы координат поля в систему координат камеры. Зная размеры объектов и максимальную погрешность определения координат, определяются все области кадра, которые могут содержать изображения объектов и не участвуют в рассмотрении. Из оставшихся пикселей исключаются те, для которых нет соответствующих им по цвету пикселей карты, отстоящих от них не более, чем на d.
Считается, что оставшаяся область кадра не может содержать изображения объектов, т.е. она содержит только фоновое изображение. Затем для всех пикселей оставшейся области и соответствующих пикселей фонового изображения производится пересчет по формуле новый_пиксел_фона = старый_пиксел_фона*p + пиксел_кадра*(1-p), где 0≤p<1.
При p=0 происходит замена пикселей фона пикселями кадра. Значения p>0.5 делают обновление фона более помехоустойчивым: если случайно пиксель объекта был отнесен к фону, то цвет пикселя фонового изображения изменится, но все еще будет близок к цвету реального фона. Если при последующих обновлениях в данной точке кадра не будут находиться объекты, то его цвет вернется к правильному значению. На практике можно использовать значения p=0.8-0.9.
Возможны и другие варианты использования этого алгоритма.
Был реализован и протестирован алгоритм сравнения изображения с фоном, показавший достаточно высокую эффективность. Время нахождения всех точек, отличных от фона для кадра размером 851x553 пикселей на компьютере с процессором Athlon XP 2.2 составило 0.2 с. Если считать, что в процессе анализа видео обрабатывается 10% пикселей каждого кадра, то ожидаемое время обработки составит 0.02 с. Поскольку обрабатывался один кадр, а не видеозапись, фоновое изображение не вычислялось автоматически, а было сгенерировано вручную.
Сравнение кадра с предыдущим кадром
Рассмотрим движущийся объект. Его изображение в двух последовательных кадрах будет смещено на некоторое расстояние. Цвета пикселей, которые на 1-м кадре принадлежали объекту, а на 2-м кадре стали принадлежать фону, или, наоборот, на 1-м кадре принадлежали фону, а на 2-м кадре стали принадлежать объекту, скорее всего, будут отличаться. Цвета пикселей, которые на обеих кадрах принадлежали объекту, могут отличаться или совпадать. Цвета пикселей, которые на обеих кадрах принадлежали фону, будут совпадать.
Если интервал времени между кадрами достаточно велик, то при сравнении их будут найдены 2 группы отличающихся пикселей, соответствующих изображениям объектов на этих кадрах.
Таким образом, выполнив сравнение двух соседних кадров, можно легко обнаружить движущиеся объекты. В отличие от сравнения с фоном, нет необходимости поддерживать постоянно обновляемое фоновое изображение поля.
Недостаток алгоритма заключается в том, что он не обнаруживает медленно движущихся или не движущихся объектов. Этот недостаток можно компенсировать при объединении результатов обработки различных кадров. Если некоторый объект не был обнаружен в его предполагаемой области нахождения, то нужно считать, что он находится там, же где был в предыдущий момент времени и его скорость равна 0.
Еще один недостаток в сравнении с предыдущим подходом заключается в том, что область найденных пикселей изображения движущегося объекта всегда больше по размерам, чем изображение объекта. Это снижает точность анализа и может привести к коллизиям в тех ситуациях, где предыдущий алгоритм еще смог бы выполнить анализ.
Как и в предыдущем случае, можно повысить точность анализа, производя фильтрацию теней и шума.
Поиск в кадре определенных цветов
Алгоритм заключается в простом поиске всех точек, имеющих цвета, близкие к основным цветам формы. Алгоритм является простым и быстрым, однако не очень точным.
Анализ реальных кадров показывает, что цвета изображений сильно искажены. Цвета мелких деталей искажаются сильнее, чем цвета крупных. Все цвета имею тенденцию приближаться к цвету фона – зеленому. Поэтому реально можно искать лишь основной цвет футболки и шорт. При невысоком разрешении или для отдаленных футболистов становится трудно искать даже пиксели цвета шорт.
Из-за разницы в росте и различных поз футболистов определение координат игрока только по изображению футболки уступает по точности предыдущим методам.
Руки, ноги и голову при съемке обычными найти только по ожидаемым цветам вообще невозможно. Однако, можно быстро найти по цветам футболку, а для уточнения координат человека искать в ее окрестностях другие части тела, используя другие признаки.
Также трудно искать по цвету в кадре изображение мяча, поскольку он может выглядеть как светло-зеленое пятно.
Большую проблему представляет поиск игрока в белой форме на фоне разметки, т.к. алгоритм будет выделять все пиксели линии разметки как принадлежащие форме игрока.
Поиск неизолированных объектов
Когда в области присутствуют изображения нескольких объектов, необходимо для каждого пикселя, отнесенного к изображению некоторого объекта одним из описанных выше алгоритмов, определить к изображению какого именно объекту он относится. Для решения этой задачи можно использовать то, что все пиксели изображения одного объекта находятся недалеко в ограниченной связной области, напоминающей по форме и размерам изображение ожидаемого объекта.
Из-за перспективы изображение объекта может иметь разные размеры в разных частях области кадра. Поэтому определяются ожидаемые размеры изображения в разных частях области кадра. Целесообразно для каждой камеры вычислить ожидаемые размеры изображений объектов для каждой точки кадра 1 раз до анализа видеозаписей.
Для нахождения отдельных связных областей, соответствующих объектам, можно использовать известные алгоритмы заливки.
Задача несколько усложняется, если изображения объектов касаются друг друга. Если изображения слабо накладываются друг на друга, часто можно по форме области определить, что она содержит несколько объектов и разделить ее на соответствующие подобласти.
Если область содержит изображения объектов разных цветов, то координаты этой области можно считать общими координатами этих объектов. При этом потери номеров не происходит, т.к. при разделении изображений объектов по цветам можно будет определить, какой объект соответствовал какому до столкновения.
В целом, поиск неизолированных объектов занимает больше процессорного времени, чем поиск точек изолированного объекта.
Можно привести множество различных алгоритмов. Приведем один из них. Пусть известна область возможного нахождения неизолированного объекта. Для определения его возможных координат выполним следующие шаги:
Все пиксели области, относящиеся не к фону, а к изображениям объектов, помечаются как “относящиеся к неизвестному объекту”. Процедура поиска точек аналогична описанным процедурам в алгоритмах поиска изолированных объектов.
Число_найденных_объектов = 0.
Для каждого “относящегося к неизвестному объекту” пикселя запускается рекурсивная процедура заливки, которая устанавливает для него номер_объекта = число_найденных_объектов, после чего обрабатывает таким же образом все соседние “относящиеся к неизвестному объекту” пиксели. Увеличивается число_найденных_объектов. Процедура может быть выполнена поиском в ширину или глубину.
Просматриваются образовавшиеся области пикселей с одинаковым номером и те из них, в которых эвристический алгоритм обнаруживает контуры двух и более людей, разбиваются соответствующим образом на несколько областей. Области, не подходящие по форме для изображений искомого объекта исключаются из рассмотрения.
Чтобы определить, к какой именно области относится изображение искомого объекта, в каждой области ищутся пиксели, имеющие ожидаемые цвета объекта. Области, не имеющие достаточно пикселей нужных цветов, исключаются из рассмотрения. Этот шаг не применяется, если пиксели первоначально выделялись поиском цветов.
Список координаты оставшихся областей и будет результатом работы алгоритма.
Данный алгоритм корректно обрабатывает следующие сложные ситуации:
Изображения любого числа игроков одной команды находятся рядом, но не пересекаются.
Изображения любого числа игроков одной команды слегка касаются друг друга, но при этом возможно однозначно разбить получившуюся сложную область на области, содержащие по одному игроку.
Изображения любого числа игроков людей могут частично или полностью пересекаться, но при этом все люди имеют различные цвета формы (например, близко находятся игрок команды 1, игрок команды 2 и судья).
Данный алгоритм не может проанализировать коллизии, т.е. ситуации, когда достаточно сильно пересекаются изображения нескольких людей в одинаковой форме. В этом случае требуются еще более сложные алгоритмы, анализирующие не силуэты людей в целом, а их отдельные части. Однако во многих случаях может быть достаточно проанализировать этот же участок поля, снятый другой камерой.
Сравнение с шаблонами
В программе имеется заранее составленная библиотека силуэтов (шаблонов) людей в различных позах. Перед началом анализа конкретного матча эти силуэты раскрашиваются в цвета формы команд и цвета формы других возможных людей на поле.
Одним из описанных выше алгоритмов (например, сравнением с фоном) определяются области кадра, содержащие изображения нескольких объектов. Затем для каждого объекта в области с различным смещением координат различных его точек применяются различные шаблоны из библиотеки шаблонов. Целесообразно начинать анализ от краев области, поскольку они соответствуют краям изображений футболистов. Выбираются лучше всего совпавшие шаблон и участок изображения. Определяются соответствующие координаты объекта. Все пиксели, совпавшие с шаблоном, помечаются как “распознанные”. Затем пока в оставшейся области продолжается поиск оставшихся объектов уже без учета “распознанных” пикселей.
Описанная процедура имеет смысл, только если до начала наложения шаблонов координаты объектов уже были известны с высокой точностью. Поэтому перед началом разбора коллизии таким алгоритмом необходимо вернуться на несколько кадров назад и произвести сравнение с шаблонами изображений игроков в нормальной игровой ситуации.
Чем большее число шаблонов используется, тем выше точность и ниже скорость работы алгоритма. Целесообразно создавать процедуру сравнения участка кадра с шаблоном так, чтобы небольшие возможные искажения формы изображения на кадре компенсировались и не приводили к большому снижению степени совпадения с шаблоном. Это позволит сильно сократить число используемых шаблонов. Простейшее решение заключается в выборе для каждого пикселя кадра наиболее подходящего по цвету пикселя шаблона из нескольких соседних.
Данный алгоритм можно использовать не только для разрешения коллизий, но и для более точного определения координат в нормальных игровых ситуациях
Другие алгоритмы
Интересным подходом является поиск в кадре отдельных частей изображений игроков (ног, рук, головы, шорт, футболки) и нахождение игроков по списку имеющихся частей. Такой алгоритм мог бы использоваться для разрешения коллизий.
Можно также использовать эвристические алгоритмы, выделяющие все изображение игрока начиная с некоторой точки, принадлежащей этому изображению. Такие алгоритмы также можно было бы использовать для разрешения коллизий.
Для классификации участков кадра и поиска объектов возможно использование нейросетей. Однако, без аппаратной реализации этот подход трудно применять к анализу видео из-за низкой скорости работы программно эмулируемых нейросетей.
Существует и множество других подходов к поиску объектов в изображение.
Алгоритмы фильтрации изображения
Эти алгоритмы могут применяться ко всему кадру или его части изображению в явном виде до начала анализа изображения или являться частью алгоритма анализа (как в случае с фильтрацией теней и шумов в алгоритме сравнения кадра и фона). Цель таких алгоритмов – сделать изображение более удобным для анализа. Рассмотрим различные фильтры, которые может быть полезно применять к одному кадру или видеозаписи в целом.
Выравнивание яркости участков поля
Различные участки поля обычно освещены по-разному. Поиск цветов формы работал бы лучше, ели бы освещение было везде одинаково.
Можно выровнять яркость всего кадра или его части следующим адаптивным фильтром: цвет каждого пикселя умножается на NY/CY, где NY – желаемый уровень средней яркости, CY – средняя яркость области вокруг данного пикселя.
Можно также применять выравнивание яркости неявно во время сравнения цветов пикселей, производя сравнение в цветовом пространстве яркость+хроматические компоненты (например, YCrCb) и отдавая яркостной составляющей незначительную долю в общей оценке.
Можно предположить, что первый способ должен быть эффективней, поскольку во втором случае при сравнении используется не вся информация о цветах пикселей.
Повышение резкости изображения
Причина применения такой фильтрации – недостаточная резкость записей, получаемых с недорогих видеокамер.
Можно осуществляется стандартным фильтром со скользящим окном, повышающим высокочастотные составляющие сигнала. Цвет каждого пикселя заменяется суммой произведений его цвета и цветов его соседей на соответствующие элементы некоторой матрицы (маски), наложенной на изображение с центром в текущем пикселе. Пример такой маски представлен на рисунке 3.2.
|
0 |
-1 |
0 |
|
-1 |
5 |
-1 |
|
0 |
-1 |
0 |
Рисунок 3.2 - пример маски фильтра, повышающего резкость,
Компенсация нелинейных искажений объектива камеры
Объективы многих камеры имеют заметную бочкообразную дисторсию. Это снижает точность преобразования координат из СК поля в СК камеры и обратно. Для компенсации таких искажений достаточно:
Найти элементы матриц DX и DY такие, что точка кадра с координатами (x,y) и идеальным объективом соответствует точке (DX[x,y], DY[x,y]) с реальным объективом.
Для каждой точки кадра (x,y) использовать вместо нее точку (DX[x,y], DY[x,y]).
Преобразование можно выполнить 1 раз для всего кадра или его области до анализа или пересчитывать координаты непосредственно во время анализа.
4.3.4 Компенсация дрожания камер
Не всегда представляется возможным закрепить камеры достаточно жестко. Возможно дрожание камер в процессе съемки, вызванное ветром и вибрациями самого здания стадиона. Дрожание представляет из себя комбинацию параллельного перемещения и вращения камеры. Параллельное перемещение на несколько миллиметров в любую сторону никак не сказывается на видеозаписи. Поворот камеры в вертикальной или горизонтальной плоскости даже на небольшой угол приведет к смещению полученного кадра относительно предыдущего в вертикальном или горизонтальном направлении. Поворот камеры вокруг оси ее объектива приведет к повороту кадра относительно предыдущего.
Как видно, вращения камеры в процессе съемки осложнят анализ видеозаписей и снизят его точность. Поэтому для некоторых камер к видеозаписям необходимо применять фильтрацию, уменьшающую эффект от дрожания камеры. Компенсировать вертикальные/горизонтальные повороты камеры и повороты вокруг оси объектива могут быть скомпенсированы параллельным перемещением кадра и его поворотом соответственно.
Фильтрацию можно осуществить непосредственно перед анализом текущего момента времени следующим образом:
Некоторый кадр данной камеры принимается за эталонный.
В эталонном кадре выделяются несколько контрастных статичных участков изображения (например, границы поля, линии разметки, рекламные щиты вокруг поля). Для компенсации дрожания достаточно лишь двух таких участков, но на других кадрах часть участков может быть закрыта изображениями объектов.
Для кадра каждой камеры выполнить шаги 4-5.
Для каждого отобранного участка эталонного кадра, в котором на данном кадре не может быть объекта: определяется такие dx и dy (–maxd ≤ dx, dy ≤ maxd), что при сдвиге данного кадра на dx и dy по горизонтали и вертикали соответственно достигается наилучшее совмещение данного участка эталонного и данного кадров. Если при всех dx и dy разница между участками превышает пороговую величину, то данный участок в дальнейшем не рассматривается.
По списку 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 и ими можно пренебречь.
Это преобразование также можно выполнять 1 раз для всего кадра или его области до анализа или пересчитывать координаты непосредственно во время анализа.
Фильтрация теней
Проблема теней возникает при сравнении кадра и фона или сравнении соседних кадров. Проверку цветов необходимо осуществлять таким образом, чтобы цвета учаска поля в тени и на свету считались совпадающими. Этого можно достичь, сравнивая цвета в цветовом пространстве не RGB, а яркость + хроматические компоненты (например, YCrCb). Пиксели поля, попавшие в тень игрока сильно отличаются от незатененных пикселей по яркости и сабо по оттенку (хроматическим компонентам).
Фильтрация шума
Фильтрацию шума можно выполнять как непосредственно при анализе кадра, так и до начала анализа.
В случае сравнения кадра и фона или сравнения соседних кадров фильтрацию шума можно выполнить, если считать пиксели, отличные в двух изображениях, но не имеющие отличных в этих изображениях соседей, одинаковыми. Поскольку шумы всех пикселей независимы, вероятность большого скопления случайных различных на двух изображениях пикселей мала.
Для предварительной фильтрации шума можно использовать различные стандартные алгоритмы. Наилучшие результаты дает использование алгоритмов на основе классификации областей, но они являются слишком медленными для задачи анализа видео. Можно использовать достаточно линейный восстанавливающий фильтр.
ЗАКЛЮЧЕНИЕ
В данной работе была рассмотрена сфера применения систем автоматизированного анализа футбольных матчей. Были сформулированы основные требования к системе.
Были рассмотрены существующие подобного рода системы. Все системы автоматизированного анализа спортивных соревнований на рынке можно разделить на 2 группы: системы на основе анализа видео и системы на основе специальных датчиков. Присутствуют также системы записи и воспроизведения видео, не производящие никакого анализа, но облегчающие ручной анализ.
Был рассмотрен общий подход к анализу матча на основе анализа его видеозаписей.
Были рассмотрены основные алгоритмы и подходы, которые можно использовать в системах анализа видеозаписей футбольных матчей. Среди них математические модели движения объектов, алгоритмы поиска изображений объектов в кадре, полезные в данной системе алгоритмы фильтрации изображения.
Основную проблему при анализе видеозаписей представляют ситуации, когда несколько игроков, особенно из одной команды, оказываются рядом. В этом случае системы не могут сами проанализировать сложную ситуацию и требуется ручной ввод. Ручной ввод также во всех существующих системах для протоколирования игровых событий.
Основными недостатками существующих систем на основе анализа видеозаписей является их высокая стоимость, большой объем ручного ввода и стационарная установка на определенном стадионе. Поэтому задача разработки новой системы с улучшенными характеристиками все еще является актуальной.