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

На правах рукописи

Королев Сергей Владимирович

«Разработка и исследование методов и алгоритмов сжатия данных трехмерных анимаций для потоковых приложений в телекоммуникационных системах и компьютерных сетях»

Специальность 05.13.13— «Телекоммуникационные системы и компьютерные сети»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2009

003484219

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Мясковский государственный институт электроники и математики (Технический университет)» на кафедре «Вычислительные системы и сети»

Научный руководитель: кандидат технических наук, доцент

Петр Борисович Панфилов Официальные оппоненты: доктор технических наук, профессор

Александр Петрович Свиридов, доктор физико-математических наук, профессор Михаил Васильевич Михайлюк

Ведущая организация: Федеральное государственное унитарное

предприятие «Государственный научно-исследовательский институт авиационных систем» (г.Москва)

Защита диссертации состоится 24 ноября 2009 г. в 12:00 на заседании диссертационного совета Д 212.133.03 в Московском государственном институте электроники и математики (Технический университет) по адресу: 109028, г.Москва, Б.Трехсвятительный пер., д.3.

С диссертацией можно ознакомиться в библиотеке МИЭМ (ТУ). Автореферат разослан .» октября 2009 г.

Ученый секретарь

диссертационного совета Д 212.133.03, к.т.н., доцент

Ю. Л. Леохин

Общая характеристика работы

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

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

Особенностью описания трехмерных данных по отношению к аудиб.и вн-; део является то, что объем, необходимый для хранения трехмерной сцены или модели при увеличении ее качества в п раз, пропорционален (где Бо — исходный размер), в отличие от аудио (£%) или видео (5цп). То есть при сравнимом масштабировании качества размер ЗО-сцен существенно возрастает по сравнению с аудио- и видеоданными. Кроме того, векторный формат, в котором, как правило, описываются трехмерные модели, позволяет конечному пользователю просматривать отдельные ее части в небольших масштабах, что делает проблему точности описания еще более острой.

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

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

Задачи исследований. Для достижения поставленной цели в работе сфор-

мулированы и решены следующие задачи:

• Анализ существующих методов сжатия, определение их основных характеристик, классификация, а также оценка степени применимости методов для сетевых приложений.

• Разработка алгоритмов, методов и средств сжатия трехмерной анимации с ориентацией на потоковую передачу по сети.

• Разработка программного обеспечения сжатия трехмерной анимации на базе разработанных методов.

• Разработка клиент-серверного программного комплекса вещания ЗБ-ани-мации.

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

К основным научным результатам, представляемым в диссертационной работе и выносимым на защиту, относятся:

» Результаты анализа и сравнения существующих стандартов, а также исследовательских методов сжатия трехмерной анимации; оценка применимости существующих методов к сетевым приложениям.

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

• Алгоритмы, модифицирующие этапы метода сжатия, основанного на кластеризации: алгоритм кластеризации 30-моделей на основе жадного алгоритма и балансировки (позволяет ускорить этап кластеризации на 14%—46% для рассмотренных тестовых моделей по сравнению с методом ЕАМС-ЬО), альтернативный метод решения задачи назначения кластерных весов вершин (переопределенная система уравнений заменяется обычной линейной), алгоритм замены аффинных кластеров на строгие (заменяет афииные преобразования с 12 коэффициентами на строгие с 7 для некоторых кластеров), алгоритм адаптивного поиска множества значимых соседних кластеров (улучшает показатели сжатия до 32% для рассмотренных моделей по сравнению с неадаптивным методом), алгоритм сжатия списка шагов квантования (улучшают качество сжатия до 55% для рассмотренных моделей по отношению к тому же методу, не использующего сжатие шагов).

• Результаты анализа влияния входных параметров методов на выходные показатели сжатия, а также сравнения описанных методов между собой и методом FAMC-LD из стандарта MPEG-4. Экспериментально показано, что метод, основанный на кластеризации, лучше адаптируется к уменьшению размера блока кадров, чем FAMC-LD.

Практическая ценность и реализация результатов работы. Научные результаты, полученные в диссертации, доведены до практического применения при построении прототипа системы распределенной виртуальной лаборатории, в том числе, при выполнении госбюджетного научно-исследовательского проекта «Разработка распределенного виртуального технопарка на базе вузов России» в рамках аналитической ведомственной целевой программы Минобрнауки РФ «Развитие научного потенциала высшей школы (2009-2010 годы)». Результаты диссертации внедрены в компании ООО «Вимком-Оптик» при построении сетей интерактивных мультимедийных услуг, группе компаний «Традиция» для разработки сетевых виртуальных сред тренажерного назначения, а также использованы в учебном процессе кафедры ВСиС МИЭМ в рамках дисциплины «Новые информационные технологии».

Достоверность полученных в диссертации результатов и выводов пс)д-тверждается:

• согласованностью с имеющимися результатами других авторов; ^

• корректностью выводов математических зависимостей в описании алгоритмов сжатия и оценке их качества;

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

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:

• научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2005-2008);

• международной конференции 3DTV CONFERENCE 2008 (Стамбул, Турция, 2008);

• российско-австрийском научном семинаре «Визуальный компьютинг в фундаментальной, академической и прикладной науке и исследованиях» (Москва, 2009);

• заседаниях кафедры ВСиС МИЭМ.

Публикации. По теме диссертации опубликовано 5 работ, в том числе 1 публикация в журнале, рекомендованном ВАК.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы из 68 наименований. Диссертация содержит 170 страниц текста, 118 рисунков и 9 таблиц.

Краткое содержание работы

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

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

В таблице 1 даны краткие сравнительные характеристики стандартных методов сжатия, которые наиболее важны при кодировании анимированных трехмерных сцен с целью передачи их по сети.

Свойства/ Потоковая Временная Масштаб. Пространств.

стандарт передача масштаб. по качеству масштаб.

VRML — - - -

X3D — — ± ±

MPEG-4 AFX + + + +

Таблица 1. Сравнение основных свойств методов описания Зй-сцен

Стандарт VRML, предложенный в 1997 году, изначально не был предназначен для кодирования анимации, в том числе и потоковой. Единственный способ описания изменения модели в этом случае — интерполяторы. Так же как и VRML, X3D не предназначен для потоковой передачи, что обуславливает его неспособность к временной масштабируемости сцен. Однако за счет гибкости формата на основе X3D, используя расширения, можно описывать сцены с различной степенью детализации (на примере расширения фирмы Lattice). В целом эти стандарты за счет недостаточной степени сжатия и некомпактного текстового представления плохо подходят для описания динамических трехмерных сцен с изменяющимися характеристиками и движением объектов, плохо описываемым функционально (например, движения человека или животных).

Методы, входящие в стандарт MPEG-4, изначально разрабатывались для описания динамических трехмерных сцен с ориентацией на потоковую передачу, поэтому действующий стандарт в совокупности с черновыми вариантами 2008-2009 годов (ISO/IEC 14496- 16:2006/Amd 3:2008 и ISO/IEC 14496-16:2006/Amd 2:2009) обладает всеми желаемыми качествами. Однако на данный момент в стандарте, принятом в 2004 году и несколько модифицированном в 2006, используется метод AFX-IC (сжатие на основе интерполяторов), который с учетом изменившихся возможностей современных аппаратных средств использует вычислительно алгоритмы и дает низкие показатели сжатия.

Помимо стандартных методов, начиная с 1999 года, в связи с растущей потребностью компактного описания и передачи трехмерных сцен исследователями предлагались различные способы их сжатия, которые можно условно разделить на следующие группы (в скобках указаны имена некоторых методов): 1) сжатие на основе вершинных предсказателей (LBPC); 2) динамическое разбиение пространства модели восьмеричным деревом и компенсация движения на основе трилинейной интерполяции (D3DMC); 3) представление анимации в виде матрицы, содержащей координаты вершин и дальнейшее сжатие этой матрицы на основе SVD-разложения (ORLPCA); 4) разбиение модели на кластеры и компенсация их движения с помощью аффинных преобразований (FAMC-DCT, FAMC-LD, Skinning); 5) представление трехмерных моделей в виде двумерных изображений (MCGV); 6) сжатие с использованием вейвлет-разложения для предсказания положения вершин, как в пространстве, так и во времени (Wavelet).

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

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

LBPC D3DMC ORLPCA FAMC Wavelet MCGV

Пот. кодир. + + -

Пот. перед. + + - + ±2 +

Иерарх, сеток + - + ' ±3

Выч. сложн. Средняя Низкая Высокая Средняя Средняя Высокая

Таблица 2. Сравнение основных свойств методов описания сцен, необходимых для кодирования потоковой трехмерной анимации

Сводная таблица 2 характеризует методы с точки зрения функциональности. Метод ОИ1-СРА (рис. 1) дает наилучшие показатели сжатия, однако при этом имеет высокую вычислительную сложность и очень низкую гибкость: модели, сжатые таким способом, не могут передаваться в виде потока. Поэтому данный метод хорош для хранения моделей, трансляция по сети которых не требуется. Методы ЬВРС и ЕАМС дают сравнимые результаты, обладая при этом одинаковой функциональностью и вычислительной сложностью.

0,008 0,007 0.006 0.005 0,004 0,003 0,002 0,001 О

AFX-IC D3PMC 1 __

'1

FAMC-DCT 4

MCGV 5 —Ь-

:А___

i \

4 6

bpvf

б)

Рис. 1. Показатели сжатия методов из различных классов для модели Chicken в метрике: a) KG, б) RMSE

Метод D3DMC среди рассматриваемых методов выделяется тем, что способен кодировать анимацию «на лету», однако он обладает сравнительно низкими показателями сжатия и не способен описывать модели в виде иерархии сеток, что является предпочтительной характеристикой для методов, ориентированных на потоковую передачу. Методы Wavelet и MCGV имеют низкие показатели сжатия и плохо подходят для использования в сетях, кроме того, метод MCGV обладает высокой вычислительной сложностью, поскольку для декодирования анимации требуется как компенсация движения на основе аффинных преобразований, так и декодирование ошибок компенсации декодером видеокадров.

'С учетом метода FAMC-LD.

2Поддерживает только AWC.

3В зависимости от размера GOF.

Во второй главе предложен метод сжатия трехмерной анимации на основе двумерного вейвлет-разложения (метод 2D Wavelet), а также в рамках способа сжатия на основе разбиения трехмерной модели на кластеры (метод Clustering) предложены следующие алгоритмы: 1) «жадный» алгоритм кластеризации вершин с последующей балансировкой; 2) метод решения задачи назначения весов для наиболее значимых вершинных кластеров; 3) метод поиска множества значимых соседних кластеров в задаче расчета кластерных весов вершин; 4) алгоритм сжатия списка шагов квантования при кодировании блоков анимации.

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

Рис. 2. Этапы сжатия Граф связности в рассматриваемом методе сжимается хорошо известным методом ЕёдеЬгеакег, результирующий битовой поток которого в дальнейшем сжимается энтропийным кодером и формирует заголовок потока анимации.

Координаты вершин на первом этапе сжатия (матрица А) разделяется на три подматрицы, соответствующие трем координатным осям X, У и И: Ах, Ау и Аг, которые рассматриваются независимо. Данными строк этих подматриц являются траектории вершин, спроецированные на соответствующую координатную ось. Идея предлагаемого алгоритма заключается в сжатии траекторий с помощью двумерного вейвлет-разложения: в соседних строках сжимаемой матрицы размещаются траектории таких вершин, движение которых с некоторой ошибкой можно считать одинаковыми. При этом длина траекторий и число вершин, входящих в матрицу, определяется ее размером, равным 2ю х 2Ш. Перед распределением по матрицам траектории вершин сортируются в соответствии с их относительным расстоянием друг от друга. Значение ги в предложенном алгоритме задается вручную. На последнем этапе работы алгоритма квантован-

ные коэффициенты матриц сжимаются арифметическим кодером.

Для построения отсортированного списка траекторий, каждая из которых имеет длину 2Ш, определяется расстояние между г-м и j-м векторами скоростей соответствующих вершин: Ьц = - и^-1) - (¿¿ь - ¿¿>-1)!, где и* — одна

из компонент х, у или г координаты г'-й вершины на к-м кадре при к е [2шп + 1,тт(2ш(п +1)^) -1], п = 0,1,2,..., Задачей этапа сортировки траекторий является построение такого упорядоченного списка траекторий П" = {иг}, который бы минимизировал функцию = а^ттп 131=Г2 |4*а><+1 - ¿ш,+ьШ,+21.

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

В начале сортировки выбирается произвольная вершина, а затем ищется ближайшая к ней вершина. После этого путь дополняется с конца или с начала: находится ближайшая вершина к щ и к с^щ с расстояниями соответственно ЬШ|>Р и ЬЫ|п|,д. Если ЬШиР < то к началу списка добавляется р-я вершина, иначе —д-я к концу списка.

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

При удалении (обнулении) вейвлет-коэффициентов ту матрицы М для ограничения вносимой в кодируемую модель ошибки используется пороговое значение б, которое задает максимальное значение суммарной квадратической ошибки:

\\М-М\\1<5222юе, (1)

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

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

Оставшиеся коэффициенты матриц в дальнейшем квантуются однородным квантователем с мертвой зоной в области нуля: д = д +1 . / = , где / —

исходное квантуемое число с плавающей точкой, q — целочисленное квантованное значение, А — выбранный шаг квантования, а / — приближенное восстановленное значение. Значение Д выбирается на основе модуля максимального квантуемого значения и количества бит квантования: Д = ""^Г'1^, где Ь — выбранное количество бит квантования с учетом знакового бита.

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

Рис. 3. Основные этапы кодирования

Основные этапы сжатия второго метода показаны на рис. 3. Так же как и в предыдущем методе, граф связности модели кодируется методом Е<1§еЬгеакег и выводится в выходной битовой поток. Помимо графа статическим кодером сеток, который также основан на методе Edgebreaker, кодируется опорный кадр анимации в виде статической модели и в дальнейшем используется на всех этапах сжатия.

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

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

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

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

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

На последнем этапе кодирования все данные передаются энтропийному кодеру, формирующему сжатый выходной поток.

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

У/:||Г'^)-«/|[<е, (2)

где щ — координата .7-ой вершины на опорном базовом кадре, — опе-

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

Для этого каждому полигону р, рассматриваемому в качестве начального кластера, назначается оценка г)р = £/=1ИЙ1-«/|Р> гДе — объединенное множество соседних по отношению к вершинам полигона вершин.

Ci.uster()

1 C<-0

2 clustered <— false

3 while not clustered

4 do p <— Gf.tFreePolygon()

5 ifp=-l

6 then clustered <— (rue

7 else к«- NewCluster(C)

8 C= <- VerticesOf(p)

9 С' <- AddVertices(C*, false)

10 C1 <- AddVertices(C=, true)

11 return С

Рис. 4. Алгоритм кластеризации модели

В начале формирования списка кластеров множество С пусто. На каждом этапе формирования нового кластера алгоритм выполняет следующие действия (рис. 4): 1) выбирается исходный полигон с наименьшим значением у которого ни одна из трех вершин еще не входит ни в один из уже созданных мастеров (ОЕтРлЕЕРситеом). 2) Создается новый кластер с индексом к (ЫешСи^те!*) и в него добавляются все вершины полигона р (УенткебОр). 3) Созданный кластер сначала пополняется вершинами, движение которых можно предсказать только строгими с учетом (2), а затем — аффинными. При этом операторы преобразования рассчитываются, исходя из выражения:

= (3)

/=1

Преобразования как в случае строгих, так и в случае аффинных преобразований в общем виде можно описать аффинными матрицами, кроме того, минимизация (3) возможна на каждом кадре по отдельности. Таким образом, значения матриц на каждом кадре / ищутся одним из двух способов: 1) на основе матриц Адк, описывающих аффинные преобразования в однородных координатах; 2) на основе дуальных кватернионов, из которых в дальнейшем строятся матрицы строгих преобразований. В первом случае для получения коэффициентов матрицы А^ минимизируется выражение Рл(А^к) = — ||2 через систему уравнений дР'.= 0, г = ТД ] — 174. Во втором случае для подбора строгих преобразований используется алгебра дуальных кватернионов, поскольку поиск матрицы, описывающей только вращение и перенос, в явном виде с добавлением ограничений к (3) приводит к нелинейной задаче минимизации.

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

ре на заданный кадр /, можно найти, минимизируя выражение: Fr(q^) = £i(v{q/,fc - q^v;), где v/ = 1 + + jv{iy + — координата вершины v{, описанная в виде дуального кватерниона. Для его минимизации решается си-стемаМ1 = 0,г = Т77.

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

В общем случае предсказание координаты вершин на каждом кадре / описывается выражением v{ = Yl\;=i A^Si-iwi kvi, где Sj — множество индексов кластеров, влияющих на поведение вершины и,, w^k — их весовые коэффициенты.

В работе рассматривается несколько вариантов формирования Sf. 1) самый простой случай описывает зависимость движения вершины только от того кластера, в который она входит; 2) на поведение вершины влияют все кластеры, в которые входят соседние по отношению к и* вершины; 3) список значимых кластеров состоит из кластеров являющихся соседними по отношению к кластеру, в который входит vc 4) список, взятый из варианта 3, но сокращенный на основе RD-оптимизации (rate-distortion optimization).

Для оценки влияния кластеров на каждую вершину используется минимизация выражения: wг = argminWj ]C/=i II J2t=i к — v{||2 , где w, = (wi,i!..., w^k) — множество весов, описывающих влияние к-го кластера на вершину г. В предыдущих работах эта система решалась с помощью метода наименьших квадратов через переопределенную систему, однако раскрытие сумм в выраженнии и решение через взятие производных дает линейную систему

уравнений »(ЕГ-. 112^*^11') = 0,V* = М?.

В первом случае выбора весов, когда на каждую вершину г», влияет только один «родной» кластер к, Si = {к} для всех вершин данного кластера, а вектор wi = (1). Во втором случае также большинство вершин имеют только один значимый кластер, за исключением граничных. На основе графа связности модели для каждой вершины строится уникальный набор кластеров, в которые входят ее соседние (непосредственно связанные с ней) вершины. Третий вариант использует алгоритм, который принимает множество кластеров {Ск}, множества {GP} соседних вершин для vj и количество вершин V, строя множества значимых кластеров {Nk} для каждого кластера, а не вершины. Адаптивный метод выбора значимых кластеров основывается на полученных значениях {Nk}, глобально выбирая для каждого кластера только те соседние кластеры, которые имеют наибольшее влияние на поведение его вершин.

Выбор таких кластеров основан на так называемой RD-оптимизации: на

каждом шаге алгоритм, изменяя количество значимых кластеров для кластера к, отслеживает два глобальных параметра Р* —размер модели (в метрике Ьри/), который получится в результате сохранения только отобранных значимых кластеров, а также текущее значение Ег — глобальное значение суммарной квадратической ошибки, которая также меняется при изменении {Лг'г}. Алгоритм строит таблицу кумулятивных ошибок, оценивая для каждого кластера к постепенное добавление соседних кластеров в строку таблицы.

Для выбора пары (Д, Д) используется значение оценки ® = ДЕ*. Для расчета используется таблица, хранящая список пар (пк,ек), отсортированных по значению ек для каждого кластера (здесь пк — номер добавленного соседнего значимого кластера, — кумулятивное значение ошибки).

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

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

При кодировании анимации, так же как и при кодировании обычного видеопотока, используется понятие 1-, Р- и иерархических В-кадров порядка Ь. 1-кадр является полностью независимым и просто кодирует координаты модели статическим кодером. При этом статическая модель на 1-кадре кодируется простой реализацией метода Е(1деЬгеакег, который используется как для кодирования графа связности, так и для кодирования положений координат вершин. Кроме того, 1-кадр содержит также информацию о разбиении вершин на кластеры — множества Ск. Все остальные кадры модели кодируются как кадры Р- и В-типа. Р-кадры хранят только разности преобразований = — ТГ,к, где Т^к — матрица или дуальный кватернион (в зависимости от типа кластера), а /' — индекс опорного кадра. При использовании В-кадров порядка Ь кадры кодируются единым блоком, состоящим из 2Ш кадров. При этом на каждом /-ом уровне сохраняются разности преобразований: £>/* = Г/Л- _ I (у/Л'',к _ т/+2<-\^ , г = оГХ.

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

расчета значения шага квантования Д, который связан с квантуемыми данными.

Для сокращения списка шагов квантования W — {Дь Д2,..., Дл1} можно удалить часть шагов, заменив их близкими к ним по значению. Для этого W сортируется по возрастанию, а затем удаляются элементы Д; таким образом, что соседние значения отличаются друг от друга не более чем на к > 1. При квантовании выбирается приближенное или точное значение шага Д'* в сокращенном множестве W, такое что Д* < Д';. При этом сохраняется не значение А',, а его индекс г, который, как правило, требует существенно меньше бит для кодирования, чем само значение Д'¿. При замене Д* на Дзначение ошибки, вносимое этапом квантования, возрастает в к раз, и реальная ошибка е будет лежат в диапазоне § < е < ^.

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

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

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

Серверная часть реализует следующие функции: 1) хранение базы данных трехмерных анимированных моделей в виде, пригодном для потокового вещания по сети; 2) прием и обслуживание клиентов, запрашивающих вещание (3D по запросу); 3) поддержание базы данных активных клиентов; 4) передача клиентам информации об имеющихся анимированных последовательностях; 5) рассылка одного или нескольких потоков анимации.

Клиентская часть выполняет: 1) подключение к серверу ЗЭ-анимации и запрос описания заданной анимированной последовательности; 2) прием и декодирование потока; 3) воспроизведение потока.

Взаимодействие между клиентом и сервером происходит с использованием двух типов протоколов: TCP и UDP (multicast). Для реализации надежного

механизма инициации запроса клиентом вещания нового потока используется протокол TCP. Непосредственно рассылка данных ЗБ-анимации по аналогии с системами вещания видео и аудио поверх IP-сетей реализуется на основе потоковой multicast-рэссылки, содержащей последовательность байт, описывающей блоки кадров анимации (GOF —group of frames). Протокол взаимодействия клиента и сервера состоит из следующих этапов: 1) клиент с помощью входящего TCP-соединения запрашивает информацию о конкретном анимационном потоке; 2) сервер передает запрашиваемые данные, сохраняет запись об активном клиенте и начинает multicast-рассылку; 3) клиент принимает поток анимации, периодически информируя сервер о том, что он по-прежнему является получателем multicast-рассылки; 4) клиент завершает работу, посылая извещение серверу о прекращении членства в группе (рассылка извещения осуществляется средствами ненадежного протокола UDP, поэтому сервер может не узнать о завершении работы клиента); 5) сервер принимает извещение о прекращении членства клиента в группе (или время жизни записи о клиенте истекает) и останавливает рассылку, если больше не существует подписчиков для данного потока.

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

После отсылки данных об анимации сервер начинает рассылку блоков кадров анимации. Данные рассылаются с использованием multicast-пакетов (рис. 5)

Поле Part хранит номер пакета в рамках одного блока кадров, Count — общее количество пакетов в блоке, S —размер поля Stream в байтах, Start и End — метки времени начала и окончания воспроизведения блока кадров в миллисекундах, Frames — количество кадров в блоке, Stream —часть данных блока. Размер всего пакета не превышает 512 байт.

0 4 12 16

Part (4 байта) Count (4 банта) S (4 байта) . Start (4 байта)

Frames (4 байта)

Рис. 5. Формат тиШсаэ^пакета, содержащего часть блока кадров

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

Сервер принимает два типа запросов: запрос на информацию об анимационной последовательности и запрос на обновление БД активных клиентов.

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

Данные об анимации Ми№са&-лотоки

Запросы на Запросы

подключение и на обновление

получение данных записи в БД

(заголовков енинаций) активных клиентов

Рис. 6. Структура многопоточного тиШсав^сервера рассылки ЗО-анимации

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

База данных анимаций состоит из набора файлов, содержащих анимирован-ные последовательности в формате, пригодном для тиШсаБ^рассылки (рис. 7).

Заголовок анимации Вм Таблица блоков Описатель файла

Рис. 7. Структура файла с анимацией

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

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

При рассылке информации о потоке сервер посылает клиенту заголовок анимации, а во время тиШсаБ^ассылки — соответствующий блок кадров в виде набора 1ЮР-пакетов.

Рис. 8. Структура клиента

Клиент (рис. 8) собирает пакеты в закодированные блоки кадров, объединяя их поля Stream в единый буфер, который затем распаковывается соответствующим декодером.

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

Как видно из сравнительных графиков на рис. 1, наилучшие значения показателей сжатия дают методы FAMC-DCT и ORLPCA, однако они не подходят для потоковой передачи; подход LBPC — это, по сути, метод, лежащий в основе FAMC-LD, таким образом, описанные подходы целесообразно сравнивать с наилучшим на данный момент методом кодирования FAMC-LD, подходящим для потоковой передачи анимации. При сравнении методов сжатия анимации основными показателями выступают зависимость качества модели от ее размера, а также время кодирования.

На рис. 9 приведены сравнительные графики описанных методов FAMC-LD, 2D Wavelet и Clustering для четырех тестовых моделей. В методе FAMC-LD коэффициенты квантуются при q = 16, графики для 2D Wavelet получены при w = 5, а для Clustering — при 7 = 1,05 и L = 5. Результаты 2D Wavelet и Clustering показаны для значений q, равных 12, 14 (модель Chicken) и 16.

Clustering, 12 —

Clustering, 12 -Oustering, 6 = 16 -2D Wavelet, b =

bpvf

6)

Clustering, 6=12 — Clustering, 6 = 16 — 2D Wavelei, 6 г= 12 ••-»■• 2D Wavelet, 16 -«-FAMc+LD -

Clustering. 6 = 12 Clustering. 6=16 — 2D Wavelei 6=12 -»-2D Wavelet, 6 = 16 —

FAMC+LD —e-

O

0 1 2 3 4 5 bpvf

B) r)

Рис. 9. Показатели сжатия методов 2D Wavelet, Clustering и FAMC-LD: a) Chicken, 6) Cow, в) Dance, г) Snake

На всех графиках видно, что метод 2D Wavelet дает самые низкие показатели сжатия, метод Clustering близок к FAMC-LD, но отстает от него в области очень высокого качества модели (приблизительно при bpvf > 3, кроме модели Snake). Невысокое качество модели, закодированной методом Clustering, при больших значениях bpvf обусловлено тем, что в случае моделей со сложным поведением для точного предсказания требуется большое количество кластеров. Но даже точное разбиение множеством кластеров не всегда приводит к хорошему предсказанию (это хорошо видно на предсказание ошибок. Однако визуально уже при значении KG <0,5 ошибка моделей достаточно мала и трудно заметна при воспроизведении модели в ее естественном масштабе.

Однако он обладает сравнимыми показателями сжатия при 0,2 < KG < 0,5, что соответствует визуально хорошему качеству модели, при этом его время

кодирования меньше, чем у FAMC-LD с любым из двух методов разбиения на кластеры. Сложность декодирования у метода FAMC-LD выше по сравнению с описанными методами из-за наличия дополнительного вычислительно сложного этапа предсказания ошибок на основе вершинного предсказателя predangie(v/).

Метод FAMC-LD на предварительном этапе кластеризации использует два метода разбиения и балансировки: с использованием метода К-средних и иерархическую кластеризацию. В табл. 3 показаны времена кодирования моделей для Clustering и 2D Wavelet, а также время этапов кластеризации и балансировки FAMC-LD. В скобках указано количество кластеров; все значения даны в секундах.

Модель Clustring 2D Wavelet FAMC-LD, K-средних FAMC-LD иерарх.

Chicken 214 (66) 25 456 (63) 5800 (63)

Cow 145 (65) 13 255 (70) 3374 (70)

Dance 184 (24) 86 214 (20) 2187 (20)

Таблица 3. Время кодирования (Clustering, 2D Wavelet) и этапов кластеризации и балансировки для двух вариантов в методе FAMC-LD: с использованием метода К-средних и иерархического подхода

Метод кластеризации FAMC-LD с использованием К-средних дает лучшие результаты (меньшую ошибку при кластеризации), чем иерархический подход, но при этом тратит существенно больше времени. Как видно из таблицы 3, Clustring, применяя «жадный» алгоритм кластеризации, в некоторых случаях затрачивает меньше времени на 14%—46%, чем быстрый FAMC-LD. 2D Wavelet хотя и дает низкие показатели сжатия, при сжатии моделей Chicken и Cow работает существенно быстрее остальных методов, кроме того, его работа может быть существенно ускорена за счет распараллеливания, давая возможность кодирования и трансляции анимации «на лету».

1.4 1,2

vT Без весов —■— Соседние вершины —х— Соседние кластеры —ж— Адаптивный —о—

HV TU

iVl

1 \:\ AiV

\

-—Hi

Ü ¡S

Без весов ■ »--Соседние вершины —х-~ Соседние кластеры —*— Адаптивный —о—

\\

\ *

"Г*—'

0,4 0.6

Ьри}

а)

б)

Рис. 10. Результаты сжатия моделей Chicken (а) и Snake (б) с использованием различных способов назначения весов (Ь= 16, 7 = 1,05, )

Рис. 10а показывает влияние значений L и к на кривые сжатия модели Chicken. С одной стороны, как показывают результаты, значение L слабо влияет на положение кривой, с другой, — изменение к; с 1 до 2 может давать существенное уменьшение ошибки (вплоть до 55% в области низкого качества модели) при одном и том же размере закодированной анимированной последовательности.

На рис. 106 показаны результаты сжатия моделей Chicken и Snake с использованием различных способов назначения весов. Адаптивный способ способен выбирать как предельные (отсутствие дополнительных кластеров или выбор всех), так и промежуточные варианты, именно поэтому на всех графиках он фактически является огибающей для группы кривых, давая лучший результат из четырех возможных. Как видно из рисунка 106 адаптивный метод способен улучшать показатели сжатия до 32% по сравнению с неадаптивным методом (в случае выбора всех соседних кластеров).

Сводная таблица 4 содержит выходные значения для модели Chicken: К — количество кластеров, ereai — действительное значение максимальной ошибки, вычисленной для всех кадров анимации, выраженной в процентном соотношении относительно длины диагонали первого кадра, R — коэффициент сжатия. Сжатие методом 2D Wavelet дает значения R порядка десятков, в то время как коэффициенты Clustering могут достигать сотен, даже при небольшом максимальном значении ошибки ereai.

2D Wavelet Clustering

KG bpvf ereal R ^шах К 6re.il KG bpvf R

ю-9 0,51 8,43 1 11 0,002 248 0,96 0,12 7,90 12

5 • 1ГВ 0,52 6,98 1,01 14 0,005 137 0,96 0,14 4,34 22

ю-8 0,54 6,35 1,01 15 0,01 84 1,08 0,17 2,66 36

5 • Ю-8 0,73 4,95 i,i6 19 0,015 66 1,12 0,24 2,10 46

ю-7 0,94 4,40 1,59 22 0,02 52 1,54 0,37 1,73 56

5 • Ю-7 1,98 3,24 3,62 30 0,025 43 2,38 0,51 1,45 67

ю-6 2,78 2,8 5,01 34 0,03 38 2,39 0,74 1,30 74

5 • Ю-6 6,11 1,9 10,73 51 0,035 34 2,76 0,87 1,17 83

0,04 30 6,49 1 1,05 92

0,045 25 6,48 1,53 0,89 108

Таблица 4. Результаты кодирования методом 2D Wavelet (Хаар, w = Ь, Ь — 16) и Clustering модели Chicken (L = 5, 7 = 1,05, Ь = 16)

На рис. 11 показана зависимость изменения размера модели Chicken от размера блока кадров (при В = 2, 4, 8, 16, 32 и 64) для методов FAMC-LD и Clustering. Как видно из рисунка, для больших размеров блоков (В > 16) методы дают одинаковое значение bpvf, однако при уменьшении В Clustering

превосходит ЕАМС-ЬБ за счет экономного кодирования коэффициентов кластерных весов и шагов квантования, что делает его более подходящим для кодирования анимации блоками небольших размеров. Слабая зависимость является важной характеристикой для метода, кодирующего анимацию, предназначенную для трансляции по сети. Уменьшение размера кодируемых блоков позволяет снизить вероятность их искажения.

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

о

1,6 1.4 1.2

I

0.8 0,6 0.4 0,2 О

1? f L = 5. к = 1 — L = 5, л = 2 —X— L - 0, к = 1 —*-h = 0, к. = 2 е~

iV,....... -г.....-- ........... •-W Л........-

.......- 1 ^а

3

bpef

а)

б)

Рис. 11. Показатели сжатия модели Chicken: а) влияние параметра L и к на кривую сжатия; б) влияние параметра L на размер модели при сжатии методами FAMC-LD (b = 16) и Clustering (b = 16, 7 = 1,05, Emax = 4,58 • Ю-3.)

Модели, сжатые вейвлетами Хаара, обладают визуально неприятным эффектом, выражающимся в появлении хорошо заметных высокочастотных ошибок, вносимых в траекторию движения вершин и сильном огрублении анимации. При этом вейвлеты с1аиЬ4 и Ыо97 дают визуально более сглаженные результаты, поскольку при фильтрации используют большее количество коэффициентов, чем вейвлеты Хаара, однако дают худшие показатели сжатия.

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

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

Таким образом, метод 2D Wavelet полезен при необходимости кодирования анимации «на лету» и наличии относительно большой пропускной полосы для трансляции анимации. Метод, основанный на кластеризации, хорошо подходит для кодирования больших моделей со средним качеством из-за невысокой вычислительной сложности как кодирования, так и декодирования по сравнению с FAMC-LD, давая одновременно сравнимые с FAMC-LD результаты в области

t, сек.

а)

| L = 2 —у— L = 3 —L = 4 —La5

А 1 ж

//¡1 \

L—(——Ъз

t, сек. б)

Рис. 12. Загрузка канала при передаче модели Snake (Т = 6 сек., b = 16,) для методов сжатия: а) на основе вейвлет-разложения (е = 10"5, вейвлеты Хаара), б) с использованием кластеризации (К = 8) На рис. 12а показана загрузка сетевого канала при передаче модели Snake, закодированной первым методом, для различных размеров блока кадров. Как видно из рисунка, объем передаваемых данных существенно увеличивается при уменьшении размера блока кадров. Трансляция анимации, сжатой вторым методом, может давать очень неоднородную загрузку канала (рис. 126), связанную с тем, что размер I-кадра может быть существенно больше Р- и В-кадров в том случае, когда размер сжатой статической сетки велик (например, при кодировнии модели, состоящей из десятков или сотен тысяч вершин), а ее поведение хорошо описывается небольшим количеством кластеров.

Результаты работы

Основные научные результаты работы состоят в следующем:

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

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

3. Разработаны алгоритмы, модифицирующие этапы метода сжатия, основанного на кластеризации: алгоритм кластеризации ЗО-моделей на основе жадного алгоритма и балансировки (позволяет ускорить этап кластеризации на 14%-46% для рассмотренных тестовых моделей по сравнению с методом РАМС-ЬО), альтернативный метод решения задачи назначения кластерных весов вершин (переопределенная система уравнений заменяется обычной линейной), алгоритм замены аффинных кластеров на строгие (заменяет афииные преобразования с 12 коэффициентами на строгие с 7 для некоторых кластеров), алгоритм адаптивного поиска множества значимых соседних кластеров (улучшает показатели сжатия до 32% для рассмотренных моделей по сравнению с неадаптивным методом), алгоритм сжатия списка шагов квантования (улучшают качество сжатия до 55% для рассмотренных моделей по отношению к тому же методу, не использующего сжатие шагов).

4. Выполнен анализ влияния входных параметров методов на выходные показатели сжатия, а также сравнение описанных методов между собой и методом РАМС-ЬО из стандарта МРЕО-4. Экспериментально показано, что метод, основанный на кластеризации, лучше адаптируется к уменьшению размера блока кадров, чем РАМС-ЬО.

Публикации по теме диссертационной работы

1. Королев, С. В. Сжатие трехмерных анимированных последовательностей с постоянной связностью на основе двумерного вейвлет-разложе-ния / C.B. Королев, П.Б. Панфилов, A.A. Никитин // Автоматизация и современные технологии. — 2008. — Май. — № 5. — С. — 3-9.

2. Королев, С. В. Метод сжатия трехмерной анимации с постоянной связностью / C.B. Королев // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. — МИЭМ, 2007. - Февраль-Март. - С. 218-218.

3. Королев, С. В. Метод сжатия трехмерных анимированных моделей, ориентированный на потоковую передачу / С. В. Королев // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. — МИЭМ, 2008. — Февраль-Март. — С. 185-186.

4. Королев, C.B. Методы построения распределенных систем визуализации трехмерной сцены / C.B. Королев, A.A. Никитин // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. — МИЭМ, 2006. — Февраль-Март. — С. 170-171.

5. Korolev, S. V. 2D wavelet-based compression of 3D animation sequencés with fixed connectivity / S.V. Korolev, P.B. Panfilov, A.A. Nikitine // 3DTV

2008. - IEEE Xplore, 2008. - May 28-30. - Pp. 109-112.

Подписано в печать 20.10.2009. Формат 60x84/8. Бумага типографская № 2. Печать - ризография. Усл. печ. л. 1,6 Тираж 100 экз. Заказ /00%

Московский государственный институт электроники и математики 109028, Москва, Б.Трехсвятительский пер., 3.

!, transmission and display ot 3D video,

Центр оперативной полиграфии (495) 916-88-04, 916-89-25

Введение

Глава 1. Обзор и анализ современных сетевых технологий описания трехмерных сцен

1.1. Международные стандарты описания трехмерных сцен.

1.1.1. VRML.

1.1.2. X3D.

1.1.3. MPEG-4 AFX.

1.1.4. Сравнение стандартов.

1.2. Современные методы сжатия ЗО-анимации. Обзор и классификация

1.2.1. Формальная постановка задачи сжатия трехмерной анимации

1.2.2. Методы оценки качества сжатия анимированных ЗБ-моделей

1.2.2.1. Метрика KG.

1.2.2.2. Метрика RMSE.

1.2.2.3. Метрика Da (ленточная оценка).

1.2.3. Сжатие на основе вершинных предсказателей.

1.2.4. Методы, основанные на восьмеричном дереве.

1.2.5. Сжатие на основе разложения по основным базисным векторам

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

1.2.7. Кодирование трехмерной анимации двумерными изображениями

1.2.8. Сжатие на основе вейвлет-разложения.

1.2.9. Сравнение методов.

1.3. Выводы.

Глава 2. Методы сжатия трехмерной анимации

2.1. Сжатие ЗБ-анимации на основе двумерного вейвлет-разложения

2.1.1. Вейвлет-анализ сигнала

2.1.2. Общее описание метода

2.1.3. Сортировка траекторий.

2.1.4. Сжатие траекторий

2.1.5. Кодирование коэффициентов разложения методом нуль-дерева

2.1.6. Квантование коэффициентов

2.1.7. Свойства и особенности метода.

2.2. Сжатие ЗО-анимации на основе компенсации движения вершин аффинными и строгими преобразованиями.

2.2.1. Алгебра дуальных кватернионов.

2.2.2. Общее описание метода

2.2.3. Кластеризация

2.2.4. Балансировка.

2.2.5. Назначение кластерных весов.

2.2.6. Выявление строгих кластеров.

2.2.7. Кодирование преобразований.

2.2.8. Квантование коэффициентов.

2.2.9. Энтропийное кодирование

2.2.10. Свойства и особенности метода

2.3. Выводы.

Глава 3. Клиент-серверный программный комплекс вещания ЗО-анимации

3.1. Архитектура клиент-серверного ПО, реализующего потоковое вещание трехмерной анимации.

3.2. Протокол запроса описания потока.

3.3. Формат multicast-пакета

3.4. Структура сервера.

3.4.1. Рассылка multicast-потока.

3.5. Структура клиента.

3.5.1. Прием закодированного потока ЗО-анимации.

3.5.2. Декодирование потока.

3.5.3. Воспроизведение кадров.

3.6. Кодер и декодер анимации на основе вейвлет-разложения.

3.6.1. Вейвлет-кодер.

3.6.1.1. Общий алгоритм кодирования.

3.6.1.2. Кластеризация вершин (распределение по матрицам

3.6.1.3. Заполнение матриц и кодирование их коэффициентов

3.6.2. Вейвлет-декодер.

3.6.2.1. Декодирование матриц.

3.7. Кодер и декодер, использующие кластеризацию модели.

3.7.1. Кодирование.

3.7.1.1. Предварительная оценка кластеров.

3.7.1.2. Кластеризация.

3.7.1.3. Балансировка.

3.7.1.4. Подбор строгих преобразований

3.7.1.5. Кодирование кластеров

3.7.1.6. Кодирование преобразований.

3.7.1.7. Выбор значимых кластеров.

3.7.1.8. Назначение и сохранение кластерных весов.

3.7.2. Декодирование

3.7.2.1. Декодирование списка кластеров

3.7.2.2. Декодирование весов

3.7.2.3. Декодирование преобразований и кадров анимации.

3.8. Выводы.

Глава 4. Экспериментальные результаты

4.1. Результаты сжатия метода на основе двумерного вейвлет-разложения

4.1.1. Входные значения.

4.1.2. Выходные значения

4.1.3. Влияние параметра w и типа вейвлет-разложения на показатели сжатия.

4.1.4. Время сжатия и распаковки.

4.1.5. Влияние этапа квантования коэффициентов на качество сжатия

4.1.6. Результаты сжатия.

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

4.2.1. Входные значения.

4.2.2. Выходные значения

4.2.3. RD-кривые сжатия.

4.2.4. Максимальное значение ошибки.

4.2.5. Результаты кластеризации.

4.2.6. Влияние количества бит квантования на показатель сжатия

4.2.7. Временная сложность и время работы алгоритма.

4.2.8. Результаты сжатия.

4.3. Сравнение результатов.

4.4. Выводы.

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

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

Особенностью описания трехмерных данных по отношению к аудио и видео является то, что объем, необходимый для хранения трехмерной сцены или модели при увеличении ее качества в п раз, пропорционален Sln (где S0 — исходный размер), в отличие от аудио (Sfi) или видео (Sq71). То есть при сравнимом масштабировании качества размер ЗБ-сцен существенно возрастает по сравнению с аудио- и видеоданными. Кроме того, векторный формат, в котором, как правило, описываются трехмерные модели, позволяет конечному пользователю просматривать отдельные ее части в небольших масштабах, что делает проблему точности описания еще более острой.

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

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

Задачи исследований. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

• Анализ существующих методов сжатия, определение их основных характеристик, классификация, а также оценка степени применимости методов для сетевых приложений.

• Разработка алгоритмов, методов и средств сжатия трехмерной анимации с ориентацией на потоковую передачу по сети.

• Разработка программного обеспечения сжатия трехмерной анимации на базе разработанных методов.

• Разработка клиент-серверного программного комплекса вещания ЗО-анимации.

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

К основным научным результатам, представляемым в диссертационной работе и выносимым на защиту, относятся:

• Результаты анализа и сравнения существующих стандартов, а также исследовательских методов сжатия трехмерной анимации; оценка применимости существующих методов к сетевым приложениям.

• Метод сжатия трехмерной анимации на основе двумерного вейвлет-разложения (экспериментально показано, что вейвлеты Хаара дают наилучший коэффициент сжатия по сравнению с другими рассмотренными типами разложений).

• Алгоритмы, модифицирующие этапы метода сжатия, основанного на кластеризации: алгоритм кластеризации ЗБ-моделей на основе жадного алгоритма и балансировки (позволяет ускорить этап кластеризации на 14%-46% для рассмотренных тестовых моделей по сравнению с методом FAMC-LD), альтернативный метод решения задачи назначения кластерных весов вершин (переопределенная система уравнений заменяется обычной линейной), алгоритм замены аффинных кластеров на строгие (заменяет афииные преобразования с 12 коэффициентами на строгие с 7 для некоторых кластеров), алгоритм адаптивного поиска множества значимых соседних кластеров (улучшает показатели сжатия до 32% для рассмотренных моделей по сравнению с неадаптивным методом), алгоритм сжатия списка шагов квантования (улучшают качество сжатия до 55% для рассмотренных моделей по отношению к тому же методу, не использующего сжатие шагов).

• Результаты анализа влияния входных параметров методов на выходные показатели сжатия, а также сравнения описанных методов между собой и методом FAMC-LD из стандарта MPEG-4. Экспериментально показано, что метод, основанный на кластеризации, лучше адаптируется к уменьшению размера,блока кадров, чем FAMC-LD.

Практическая ценность и реализация результатов работы. Научные результаты, полученные в диссертации, доведены до практического применения при построении прототипа системы распределенной виртуальной лаборатории, в том числе, при выполнении госбюджетного научно-исследовательского проекта «Разработка распределенного виртуального технопарка на базе вузов России» в рамках аналитической ведомственной целевой программы Минобрнауки РФ «Развитие научного потенциала высшей школы (2009-2010 годы)». Результаты диссертации внедрены в компании ООО «Вимком-Оптик» при построении сетей интерактивных мультимедийных услуг, группе компаний «Традиция» для разработки сетевых виртуальных сред тренажерного назначения, а также использованы в учебном процессе кафедры ВСиС МИЭМ в рамках дисциплины «Новые информационные технологии».

Достоверность полученных в диссертации результатов и выводов подтверждается:

• согласованностью с имеющимися результатами других авторов;

• корректностью выводов математических зависимостей в описании алгоритмов сжатия и оценке их качества;

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

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:

• научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2005-2008);

• международной конференции 3DTV CONFERENCE 2008 (Стамбул, Турция, 2008);

• российско-австрийском научном семинаре «Визуальный компьютинг в фундаментальной, академической и прикладной науке и исследованиях»

Москва, 2009);

• заседаниях кафедры ВСиС МИЭМ.

Публикации. По теме диссертации опубликовано 5 работ, в том числе 1 публикация в журнале, рекомендованном ВАК.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы из 68 наименований. Диссертация содержит 170 страниц текста, 118 рисунков и 9 таблиц.

4.4. Выводы

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

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

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

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

Метод, применяя «жадный» алгоритм кластеризации, в случае рассмотренных тестовых ЗБ-моделеи затрачивает меньше времени на 14%-46%, чем быстрый FAMC-LD.

Увеличение значения к до 2 позволяет улучшить показатели сжатия до 55% (модели Dance и Snake) по сравнению со значением к = 1, в тех случаях, когда большая часть данных приходится на список шагов квантования кластерных весов.

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

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

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

Как показывает сравнение описанных методов с FAMC-LD, метод 2D Wavelet дает самые низкие показатели сжатия, однако является самым производительным даже без применения методов оптимизации и распараллеливания. В то же время второй метод дает схожие с FAMC-LD результаты в области bpvf < 3, но уступает им при значении bpvf > 3, поскольку не способен точно кодировать анимацию в области очень высокого качества из-за отсутствия этапа кодирования ошибок предсказания. Однако он обладает сравнимыми показателями сжатия при 0,2 < KG < 0,5, что соответствует визуально хорошему качеству модели, при этом его время кодирования меньше, чем у FAMC-LD с любым из двух методов разбиения на кластеры.

Сложность декодирования у метода FAMC-LD выше по сравнению с описанными методами из-за наличия дополнительного вычислительно сложного этапа предсказания ошибок на основе вершинного предсказателя predangie(v{).

Таким образом, метод 2D Wavelet полезен при необходимости кодирования анимации «на лету» и наличии относительно большой пропускной полосы для трансляции анимации.

Метод, основанный на кластеризации, хорошо подходит для кодирования больших моделей со средним качеством из-за невысокой вычислительной сложности как кодирования, так и декодирования по сравнению с FAMC-LD, давая одновременно сравнимые с FAMC-LD результаты в области bpvf < 3. Кроме того, как показывают экспериментальные результаты, данный метод лучше адаптируется к изменению размера блока кадров (общий размер сжатой модели растет медленнее при уменьшении размера блока) по сравнению с FAMC-LD.

Заключение

Основные научные результаты работы состоят в следующем:

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

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

3. Разработаны алгоритмы, модифицирующие этапы метода сжатия, основанного на кластеризации: алгоритм кластеризации ЗО-моделей на основе жадного алгоритма и балансировки (позволяет ускорить этап кластеризации на 14%-46% для рассмотренных тестовых моделей по сравнению с методом FAMC-LD), альтернативный метод решения задачи назначения кластерных весов вершин (переопределенная система уравнений заменяется обычной линейной), алгоритм замены аффинных кластеров на строгие (заменяет афииные преобразования с 12 коэффициентами на строгие с 7 для некоторых кластеров), алгоритм адаптивного поиска множества значимых соседних кластеров (улучшает показатели сжатия до 32% для рассмотренных моделей по сравнению с неадаптивным методом), алгоритм сжатия списка шагов квантования (улучшают качество сжатия до 55% для рассмотренных моделей по отношению к тому же методу, не использующего сжатие шагов).

4. Выполнен анализ влияния входных параметров методов на выходные показатели сжатия, а также сравнение описанных методов между собой и методом FAMC-LD из стандарта MPEG-4. Экспериментально показано, что метод, основанный на кластеризации, лучше адаптируется к уменьшению размера блока кадров, чем FAMC-LD.

1. Ahn, J.-H. Predictive compression of geometry, color and normal data of 3-D mesh models / J.-H. Ahn, C.-S. Kim, Y.-S. Ho // IEEE Transactions on circuits and systems for video technology. — 2006. — February. — Vol. 16, no. 2. — Pp. 291-299.

2. Alexa, M. Representing animations by principal components / M. Alexa, W. Miiller 11 Computer graphics forum. — 2000. — September. — Vol. 19, no. 3. — Pp. 411-426.

3. Alliez, P. Valence-driven connectivity encoding of 3D meshes / P. Alliez, M. Des-brun // Computer Graphics Forum.— 2001. — September. — Vol. 20, no. 3.— Pp. 480-489. http://cgal.inria.fr/Publications/2001/AD01a.

4. Amjoun, R. Efficient compression of 3D dynamic mesh sequences / R. Amjoun, W. S. er // Journal of WSCG.- 2007. February. - Vol. 15, no. 1-3,- Pp. 99106. http://wscg.zcu.cz/wscg2007/Papers2007/journal/C31-full.pdf.

5. Besl, P. J. A method for registration of 3-D shapes / P. J. Besl, N. D. McKay // Pattern Analysis and Machine Intelligence, IEEE Transactions on. — 1992. — Febri-ary. — Vol. 14, no. 2. — Pp. 239-256. http://www.stanford.edu/class/cs273/refs/icp.pdf.

6. Cheng, Y. Mean shift, mode seeking, and clustering / Y. Cheng 11 IEEE transactions on pattern analysis and machine intelligence. — 1995. — August. — Vol. 17, no. 8. — Pp. 790-799.

7. Collins, G. A rigid transform basis for animation compression and level of detail / G. Collins, A. Hilton // Proceedings of vision, video, and graphics conference. — 2005. July 7-8. - Pp. 21-29.

8. Coors, V. Delphi encoding: improving Edgebreaker by geometry based connectivity prediction. GVU tech. report GIT-GVU-03-30 / V. Coors, J. Rossignac. — 2003. — April. http://www.gvu.gatech.edu/~jarek/papers/Delphi.pdf.

9. Dual quaternions for rigid transformation blending. Technical report / L. Kavan, S. Collins, C. O'Sullivan, J. Zara. — Dublin: Trinity College, 2006. — 11 August. — 10 pp. https://www.cs.tcd.ie/publications/tech-reports/reports.06/TCD-CS-2006-46.pdf.

10. Gupta, S. Compression of dynamic 3D geometry data using iterative closest point algorithm / S. Gupta, K. Sengupta, A. A. Kassim // Computer vision and image understanding. 2002. - July. - Vol. 87, no. 1-3. - Pp. 116-130.

11. Gupta, S. Registration and partitioning-based compression of 3-D dynamic data / S. Gupta, K. Sengupta, A. A. Kassim // IEEE transactions on circuits and systems for video technology. 2003. - Vol. 13, no. 11,— Pp. 1144-1155.

12. Interpolator data compression for MPEG-4 animation / E. S. Jang, J. D. K. Kim, S. Y. Jung et al. // IEEE transactions on circuits and systems for video technology. 2004. - July. - Vol. 14, no. 7. - Pp. 989-1008.

13. Kami, Z. Compression of soft-body animation sequences / Z. Kami, C. Gots-man // Computer and graphics.— 2004.— Vol. 28, no. 1,— Pp. 25-34. http://www.es. technion.ac.il/~gotsman/AmendedPubl/Zachi/animation.pdf.

14. Mamou, K. Compression de maillages 3D statiques et dynamiques: Ph.D. Dissertation / Computing. — Universite Paris V — Rene Descartes, France, 2008. — September. — 268 pp. http://www-artemis.it-sudparis.eu/Publications/library/These-Mamou.pdf.

15. Marais, P. Distance-ranked connectivity compression of triangle meshes / P. Marais,

16. G. James, D. Shreiner // Computer graphics forum. — 2007. — Vol. 26, no. 4. — Pp. 813-823. http://people.cs.uct.ac.za/~jgain/publications/distrank.pdf.

17. Briceno, H. M. Geometry videos: a new representation for 3D animations: Ph.D. Thesis / Computing. — MIT, 2003. September. — 114 pp. http://www710.univ-lyonl.fr/~hbriceno//research/geometryvideos/HectorBricenophdthesisA4double.pdf.

18. Mudur, S. P. Advancing fan-front: 3D triangle mesh compression using fan based traversal / S. P. Mudur, D. S. S. Venkata Babji // Image and Vision Computing.- 2004,- Vol. 22, no. 14,— Pp. 1165-1173. http://www.ee.iitb.ac.in/~icvgip/PAPERS/197.pdf.

19. The new MPEG-4/FAMC standard for animated 3D mesh compression / K. Mamou, N. Stefanoski, H. Kirchhoffer et al. // 3DTV conference: The true vision — Capture, transmission and display of 3D video. — IEEE Xplore, 2008. — May 28-30. Pp. 97100.

20. OpenGL. Официальное руководство программиста: Пер. с англ. / В. Мейсон,

21. H. Джеки, Д. Том, Ш. Дейв. СПб: ООО «ДиаСофт ЮП», 2002. - 592 с.

22. Payan, F. Wavelet-based compression of 3D mesh sequences / F. Payan, M. An-tonini // Proceedings of IEEE 2nd ACIDCA-ICMI'2005. 2005. - November. http://www.i3s.unice.fr/~fpayan/data/publications/PayanICMI2005.pdf.

23. Ramanathan, S. Impact of vertex clustering on registration-based 3D dynamic mesh coding / S. Ramanathan, A. A. Kassim, T.-S. Tan // Image and Vision Computing. — 2008.-July 2,-Vol. 26, no. 7. Pp. 1012-1026.

24. Skinning arbitrary deformations / L. Kavan, R. McDonnell, S. Dobbyn et al. // Proceedings of Symposium on Interactive 3D graphics and games. — New York, NY, USA: ACM, 2007,— Pp. 53-60. http://www.cgg.cvut.cz/~kavanll/papers/sad-i3d07.pdf.

25. Skinning with dual quaternions / K. L., M. R., D. S. et al. // 2007 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. — ACM Press, 2007. — May. — Pp. 39-46. http://www.cgg.cvut.cz/~kavanll/papers/sdq-i3d07.pdf.

26. Sullivan, G. J. Video compression — from concepts to the H.264/AVC standard / G. J. Sullivan, T. Wiegand // Proceedings of the IEEE. — 2005. — Vol. 93, no. 1. — Pp. 18-31. http://dx.doi.org/10.1109/JPROC.2004.839617.

27. A survey on coding of static and dynamic 3D meshes / A. Smolic, R. Sondershaus, N. Stefanoski et al. // Three-Dimensional Television. — Berlin: Springer, 2008. — Pp. 239-311.

28. Vdsa, L. Methods for dynamic mesh size reduction. Technical report no. DCSE/TR-2006-07 / L. Vasa; University of West Bohemia. — 2006.— October. http://herakles.zcu.cz/~lvasa/papers/vasarigo.pdf.

29. Zhang, J. Octree-based animated geometry compression / J. Zhang, С. B. Owen // DCC'04: Proceedings of the Conference on data compression. — Washington, DC, USA: IEEE Computer Society, 2004. Pp. 508-517.

30. Zhang, J. Optimizing octree motion representation for 3D animation / J. Zhang, J. Xu // Proceedings of the 44th annual Southeast regional conference. — New York, NY, USA: ACM, 2006. Pp. 50-55.

31. Форсайт, Д. А. Компьютерное зрение: современный подход: Пер. с англ. / Д. А. Форсайт, Ж. Понс. — М.: Издательский дом «Вильяме», 2004. — 928 с.

32. Королев, С. В. Метод сжатия трехмерной анимации с постоянной связностью / С. В. Королев // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. — МИЭМ, 2007. — Февраль-Март. — С. 218-218.

33. Королев, С. В. Сжатие трехмерных анимированных последовательностей с постоянной связностью на основе двумерного вейвлет-разложения / С. В. Королев, П. Б. Панфилов, А. А. Никитин // Автоматизация и современные технологии. 2008. - Май. - № 5. - С. 3-9.

34. Методы компьютерной обработки изображений / М. В. Гашников, Н. И. Глумов, Н. Ильясова и др.; Под ред. В. А. Сойфера. — М.: ФИЗМАТЛИТ, 2003. — 784 с.

35. Столниц, Э. Вейвлеты в компьютерной графике: Пер. с англ. / Э. Столниц, Т. Де-Роуз, Д. Салезин. — Ижевск: «НИЦ» регулярная и хаотическая динамика, 2002. — 272 с.1. УТВЕРЖДАЮ»

36. Генерал йдаи^директор ОООЖ'Шмком-Оптик» ГЖ /жЧ^ШтШМ. "Копорушкин7 ч \игГлi1. ■•■■i ' " •'июня /,' 2009 г.-rt-i1. АКТоб использовании результатов диссертационной работы КОРОЛЕВА Сергея Владимировича на тему:

37. Разработка и исследование методов и алгоритмов сжатия данных трехмерных анимаций для потоковых приложений в телекоммуникационныхсистемах и компьютерных сетях»

38. Использование разработанных в диссертации моделей и методов позволило сократить сроки разработки и предложить заказчикам компании проектные решения эффективные как по параметрам производительности, так и по стоимости.

39. Технический директор ООО «Вимком-Оптик»1. АКТ ВНЕДРЕНИЯрезультатов диссертационной работы Королева Сергея Владимировича на тему

40. Разработка и исследование методов и алгоритмов сжатия данных трехмерных анимаций для потоковых приложений в телекоммуникационныхсистемах и компьютерных сетях»

41. Генеральный директор ООО НПГ «Традиция»,к.э.н.1. АКТоб использовании результатов диссертационной работы Королева С.В.

42. Разработка и исследование методов и алгоритмов сжатия данных трехмерных анимаций для потоковых приложений в телекоммуникационных системах и компьютерных сетях» в учебном процессе МИЭМ

43. Зав. кафедрой «Вычислительные системы доктор технических наук, профессор