СПОСОБЫ И УСТРОЙСТВО ДЛЯ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ТРАЕКТОРИИ АНИМАЦИИ С ИСПОЛЬЗОВАНИЕМ ЛИНЕЙНОЙ АППРОКСИМАЦИИ Российский патент 2004 года по МПК H03M7/30 H03M13/39 

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

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

На фиг.1 показана схема, поясняющая траекторию анимации в обычной 3D-анимации, причем вертикальная ось представляет ключевые значения (КЛЮЧЕВОЕ_ЗНАЧЕНИЕ), а горизонтальная ось представляет ключи (КЛЮЧ).

Как показано на фиг.1, траектория 20 анимации изображает след анимации 3D-модели 10. Траектория 20 информации анимации является двухмерной кривой, изменяющейся во времени, как показано на фиг.1. Траекторию анимации можно представить множеством способов, пояснение которых приведено в главе 9 книги А.К.Джайна "Основы цифровой обработки изображений", опубликованной издательством "Прентис Холл" в 1989 г. (А.К.Jain, "Fundamentals of Digital Image Processing", Prentice Hall, 1989).

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

На фиг.2 представлен пример выражения (скалярного интерполятора) траектории анимации, используемого в языке моделирования виртуальной реальности (ЯМВР) или в четвертой версии алгоритма сжатия подвижного изображения, разработанного Экспертной группой по кинематографии, т.е. алгоритма ЭГК-4 (MPEG-4). Обрабатываемая информация включает в себя ключи и ключевые значения, а линейная интерполяция осуществляется с использованием заданной информации.

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

На фиг.3 представлена условная схема для пояснения формата данных 3D-анимации и показан кодер 30, декодер 40, формат 50 файлов данных 3D-анимации. В данном случае формат 50 файлов 3D-анимации, выводимый из кодера 30, сформирован так, что в нем присутствуют данные модели, данные анимации, атрибуты, видео/текстура и звук.

На фиг.3 отмечено, что интерполятор соответствует данным анимации, которые эффективно выражают траекторию 3D-анимации. Данные 3D-анимации, выраженные с помощью ЯМВР или алгоритма MPEG-4, сформированы с информацией, показанной на фиг.3. Хотя для аудио-, видео- и 3D-моделей разработаны стандартизированные технологии сжатия, только технологии сжатия общего назначения, ориентированные на выражение, разработаны для интерполятора с целью определения траектории анимации. В анимации, включающей в себя аудио- и/или видеоданные, объем данных для траекторий анимации наряду с 3D-моделями составляет большинство необходимого объема данных.

Следовательно, наряду с технологией сжатия 3D-моделей важна и технология сжатия траекторий анимации. Хотя двоичный формат для сцены (ДФС), соответствующий алгоритму MPEG-4, обеспечивает основной метод квантования и/или сжатия для анимации, этот метод отражает не технологию, предназначенную для интерполяторов, а технологию общего назначения, и имеет плохую рабочую характеристику сжатия. Это описано в статье Эюи С.Джэнга "Кодирование 3D-анимации: его история и основные положения" в сб. трудов Международной конференции и экспозиции по мультимедиа, проведенной в г. Нью-Йорк в 2000 г. (Euee S.Jang "3D Animation Coding: its History and Framework", proceedings of the International Conference on multimedia and Expo held in New York city in 2000).

На фиг.4а и 4b представлены блок-схемы известных устройств для сжатия и восстановления траекторий анимации соответственно. Известное устройство для сжатия, показанное на фиг.4а, выполнено с блоком 60 скалярного квантования, а известное устройство для восстановления, показанное на фиг.4b, выполнено с блоком 70 скалярного деквантования. Исходная траектория анимации вводится в форме (ключ, ключевое значение) через входной вывод ВХ1 в блок 60 скалярного квантования, показанный на фиг.4а, и подвергается скалярному квантованию. Закодированный поток битов, который является результатом скалярного квантования, выводится через выходной вывод ВЫХ1. Блок 70 скалярного деквантования, показанный на фиг.4b, принимает этот закодированный поток битов через входной вывод ВХ2 и выводит данные в форме восстановленной траектории анимации (ключ, ключевое_значение) через выходной вывод ВЫХ2.

Сжатие с помощью интерполятора в известном ДФС, соответствующем алгоритму MPEG-4, требует скалярного квантования, как показано на фиг.4а. Известный процесс сжатия, показанный на фиг.4а, применим не только к интерполяторам, но и ко всем элементам, которые требуют сжатия в ДФС. В порядке, обратном порядку сжатия, траектория анимации восстанавливается посредством блока 70 скалярного деквантования, и это происходит с использованием закодированного потока битов, вводимого в известное устройство для восстановления, показанное на фиг.4b. В устройствах, показанных на фиг.4а и 4b, ключи и ключевые значения интерполяторов сжимаются одинаковым образом, без учета характеристик каждого вида (интерполяторов), так что сжатие нельзя максимизировать.

Краткое изложение сущности изобретения

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

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

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

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

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

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

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

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

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

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

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

Краткое описание чертежей

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

на фиг.1 представлена схема, поясняющая траекторию анимации в обычной трехмерной анимации (3D-анимации),

на фиг.2 представлен пример выражения траектории анимации, используемого в языке моделирования виртуальной реальности (ЯМВР) или алгоритме MPEG-4,

на фиг.3 представлена условная схема, поясняющая формат данных 3D-анимации,

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

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

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

на фиг.7 представлена блок-схема предпочтительного конкретного варианта осуществления устройства для восстановления согласно настоящему изобретению, показанного на фиг.5b,

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

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

на фиг.10 представлена схема процесса квантования, а более конкретно широко применяемого метода кодирования посредством дифференциальной импульсно-кодовой модуляции (ДИКМ),

на фиг.11а - 11е представлены схемы, изображающие форматы закодированных потоков битов согласно настоящему изобретению,

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

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

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

Описание предпочтительных конкретных вариантов осуществления

В нижеследующем описании настоящего изобретения употребляемые выражения интерполяторов являются выражениями, используемыми в ЯМВР и/или алгоритме MPEG-4, а области, в которых применяются интерполяторы, включают в себя компьютерные игры в диалоговом режиме, анимационные рекламные объявления и т.д.

На фиг.5а представлена блок-схема устройства для сжатия траектории анимации согласно настоящему изобретению, включающего в себя блок 80 интерполяционного анализа, кодер 82 ключей (К-кодер 82), кодер 84 ключевых значений (КЗн-кодер 84) и статистический кодер 86. На фиг.5b представлена блок-схема устройства для восстановления траектории анимации согласно настоящему изобретению, включающего в себя статистический декодер 90, декодер 92 ключей, декодер 94 ключевых значений и блок 96 интерполяционного восстановления.

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

На фиг.6 представлена блок-схема предпочтительного варианта осуществления устройства для сжатия согласно настоящему изобретению, показанного на фиг.5а. Устройство для сжатия, показанное на фиг.6, включает в себя блок 80 интерполяционного анализа, имеющий блок 100 нормализации и блок 102 минимизации точек разрыва, кодер 82 ключей, имеющий квантователь 104, работающий в режиме дифференциальной импульсно-кодовой модуляции (ДИКМ-квантователь 104), кодер 84 ключевых значений, имеющий блок 106 квантования посредством ДИКМ (блок 106 ДИКМ-квантования), и статистический кодер 86.

На фиг.7 представлена блок-схема предпочтительного варианта осуществления устройства для восстановления согласно настоящему изобретению, показанного на фиг.5b. Это устройство для восстановления включает в себя статистический декодер 90, декодер 92 ключей, имеющий деквантователь 126, работающий в режиме ДИКМ (ДИКМ-деквантователь 126), декодер 94 ключевых значений, имеющий ДИКМ-деквантователь 128, и блок интерполяционного восстановления, имеющий блок 95 интерполяционного восстановления ключей и ключевых значений.

Интерполяционное выражение, подаваемое на вход блока 80 интерполяционного анализа, включает в себя ключи (К) и ключевые значения (КЗн). В устройстве для сжатия, показанном на фиг.6, блок 80 интерполяционного анализа регулирует количество точек разрыва таким образом, что траекторию анимации, которую вводят через входной вывод ВХ3, можно выразить с помощью минимального количества точек разрыва. Если исходное количество точек разрыва траектории анимации составляет N, то количество точек разрыва, выводимых из блока 80 интерполяционного анализа, регулируется до величины М (M≤N). То есть, блок 80 интерполяционного анализа выделяет точки разрыва из исходной траектории анимации, вводимой на входной вывод ВХ3.

В интерполяторе ключ и ключевое значение можно соответственно нормализовать и использовать. Для этого блок 100 нормализации нормализует каждый из ключей и каждое из ключевых значений на исходной траектории анимации, вводимые через входной вывод ВХ3, и выводит нормализованные результаты в блок 102 минимизации точек разрыва. Ключ, поддерживаемый ЯМВР, имеет значение в диапазоне между 0 и 1 включительно.

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

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

На фиг.8а - 8h представлены схемы, поясняющие предпочтительный вариант выделения точек разрыва с использованием линейной аппроксимации согласно настоящему изобретению. Каждая точка на траекториях анимации представляет собой точку разрыва. На фиг.8а представлена исходная траектория анимации. На фиг.8b показан процесс поиска обеих концевых точек (А, В) этой траектории. На фиг.8с показан процесс выбора точки разрыва, которая является ближайшей к исходной траектории. На фиг.8d показаны точки разрыва А, В и С, которые выбраны первыми. На фиг.8е показан процесс выделения вторых точек разрыва, которые близки к исходной траектории. На фиг.8f показаны точки разрыва А, В, С и D, которые выбраны вторыми. На фиг.8g показаны точки разрыва А, В, С, D и Е, которые выбраны третьими. На фиг.8h показаны точки разрыва А, В, С, D, E и F, которые выбраны четвертыми.

Когда исходная траектория анимации задана такая, как показано на фиг.8а, повторяется процесс поиска точек разрыва (М точек разрыва, 2≤M≤N), представляющих кривую анимации, которая имеет наименьшее отличие (наименьшую разность) от исходной траектории, среди точек разрыва (N) на исходной траектории анимации, при этом обе концевые точки А и В принимаются за начальные точки. Этот процесс показан на фиг.8b - 8h. В то же время можно повторять выделение точек разрыва до тех пор, пока не будет определено, что кривая аппроксимации достаточно близка к исходной кривой.

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

На фиг.9 представлена схема, поясняющая способ получения разности между действительной траекторией анимации и аппроксимированной траекторией анимации. Обращаясь к фиг.9, отмечаем, что разность между этими двумя траекториями выражается трапецоидом или "скрученным" трапецоидом. Уравнение (1) для получения площади трапецоида и уравнение (2) для получения площади "скрученного" трапецоида приведены ниже. Разность между действительной траекторией 200 анимации и аппроксимированной траекторией 210 анимации можно выразить суммой площади трапецоидов и площади "скрученных" трапецоидов. Сумма этих площадей является разностью (D_пл) площадей между этими двумя траекториями, как показано в уравнении (3).

Точки разрыва выделяют таким образом, что минимизируется разность (D_пл) площадей, получаемая с помощью уравнения (3). Таким образом, блок 102 минимизации точек разрыва выделяет точки разрыва. Существенные точки разрыва траектории анимации выделяются путем пропускания через блок 80 интерполяционного анализа. Когда необходима обработка без потерь, количество (М) выделенных точек разрыва может быть таким же, как количество исходных точек разрыва.

В позиционном интерполяторе ключевые значения представляют положение в 3D-пространстве, имеющем оси X, Y и Z, а траектория анимации представляется тремя кривыми в осях X, Y и Z. Блок 80 интерполяционного анализа может выделять точки разрыва по каждой оси, и в то же время точки разрыва на каждой оси могут отличаться от точек разрыва на других осях. В нижеследующей таблице 2 приведен результат выделения новых точек разрыва в блоке 80 интерполяционного анализа из действительной траектории, имеющей 8 точек разрыва (Т0, Т1, Т2, Т3, Т4, Т5, Т6 и Т7).

В таблице 2 "метка_ключа" обозначает метку ключа, а кзн_х, кзн_у и кзн_z обозначают ключевые значения по осям X, Y и Z соответственно. "О" указывает, что выбрано ключевое значение, соответствующее координате х, у или z каждой точки разрыва. Например, ключевое значение кзн_х выбрано для точки Т0 разрыва. "X" указывает, что ключевое значение, соответствующее какой-либо оси в каждой точке разрыва, не выбрано. Метка ключа указывает ключевые значения, оси которых выбраны, среди ключевых значений для осей X, Y, Z в каждой точке разрыва. Например, "7" указывает, что все ключевые значения для всех осей выбраны, а "6" указывает, что выбраны все ключевые значения, за исключением ключевого значения кзн_х для оси X.

Как показано в таблице 2, точки Т1, Т3 и Т6 разрыва относятся к необязательным точкам разрыва (помечены прочерком, "-", в графе "метка_ключа"), потому что в точках разрыва не выбрано ни одно ключевое значение для осей X, Y и Z. Т0 и Т7 являются точками разрыва на обоих концах траектории, в которых выбраны ключевые значения для всех осей. В Т2 не выбрано ключевое значение для оси X, но выбраны ключевые значения по другим осям. Следовательно, блок 80 интерполяционного анализа определяет ключи, соответствующие 5-ти точкам разрыва, вместо исходных 8-ми точек разрыва, а также определяет ключевые значения для каждой оси, соответствующие выбранным точкам разрыва. В таблице 2 показано, что необходимы 5 ключей и 11 ключевых значений. Соответствующее соотношение между ключом и ключевыми значениями можно представить меткой ключа (метка ключа), которая передается дополнительно. Таким образом, количество ключей и ключевых значений уменьшается с 32 у действительной траектории (4·8=32) до 16 ключей и ключевых значений плюс одна дополнительная метка ключа. Следовательно, посредством такого процесса достигается упрощение в выражении.

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

На фиг.14а показаны ключевые значения (=Q₀, Q₁, Q₂, ..., Q_n) в каждой точке разрыва применительно к количеству n+1 временных точек на исходной траектории анимации, и эти ключевые значения отмечены черными точками. Как показано на фиг.14b, первыми выбирают две точки разрыва (=Q₀, Q_n), соответствующие двум концам траектории анимации. Эти выбранные точки разрыва показаны как белые точки.

На фиг.14с показан процесс выбора точки разрыва (третьей точки разрыва) среди остающихся точек разрыва, за исключением двух выбранных концевых точек разрыва. В этот момент количество способов выбора одной точки разрыва составляет (n-1). На фиг.14с показан пример, в котором выбираются два кандидата (=Q₁, Q_k). Для каждого из (n-1) кандидатов с использованием трех уже выбранных точек разрыва осуществляют сферическую линейную интерполяцию по ключевым значениям точек разрыва, которые не выбраны. Сравнивая исходную траекторию анимации и каждую из (n-1) траекторий-кандидатов анимации, полученных путем интерполяции, выбирают траекторию-кандидата анимации, имеющую наименьшую разность траекторий. Точку разрыва, соответствующую выбранной траектории-кандидату анимации, выбирают среди (n-1) точек-кандидатов разрыва. В качестве примера на фиг.14d изображен вариант, в котором выбрана траектория кандидата 2, как показано на фиг.1. Погрешность между траекториями получают путем использования понятия средней погрешности Е_ср.

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

Ниже приведено пояснение средней погрешности Е_ср, которая упоминалась выше. Погрешность квантования определяется как дифференциальный угол поворота в дифференциальном преобразовании поворота, являющемся разностью между преобразованием поворота исходной траектории анимации и преобразованием поворота восстановленной траектории анимации. То есть, в предположении, что (, θ) обозначает ключевое значение узла ориентационного интерполятора, а (’, θ') обозначает ключевое значение, восстановленное в блоке 96 интерполяционного восстановления (вектор обозначает ось поворота, θ обозначает величину поворота, и что эта величина поворота удовлетворяет условию θ∈[-π, π]), когда осуществляется преобразование поворота из произвольного положения в и в 3D-пространстве с использованием (, θ) и (’, θ’), возникающую погрешность квантования вычисляют как разность между и . Таким образом, если представляет вектор погрешности квантования, то . В кватернионном выражении X, Y и Y' определяются, как следующие уравнения (4):

Если Q и Q’ обозначают кватернионные выражения для (, θ) и (, θ') соответственно, которые представляют преобразование поворота, то отсюда вытекают следующие уравнения (5):

Здесь А*В обозначает умножение кватернионов А и В, а А* обозначает кватернион, сопряженный с А. Отсюда вытекает следующее уравнение (6):

Здесь Q’’ - это величина, необходимая для указания связи преобразования поворота между и и определяемая следующим уравнением (7):

Следовательно, если θ’’ обозначает дифференциальный угол поворота между и , то θ’’ можно получить, пользуясь уравнением преобразования кватерниона и уравнения (7), как показано в следующем уравнении (8):

(где • обозначает операцию скалярного произведения).

Уравнение (8) указывает мгновенную погрешность квантования, возникающую в предварительно определенный момент, по всем точкам разрыва траектории анимации. Чтобы вывести уравнение для получения погрешности квантования всех интервалов анимации, мгновенную погрешность квантования в предварительно определенный момент t можно выразить в виде следующего уравнения (9):

Если уравнение (9) применяется посредством ориентационных интерполяторов ко всем интервалам анимации с точками разрыва, то можно вывести среднюю погрешность Е_ср и максимальную погрешность Е_макс для всего интервала [t₀, t_L] в виде следующих уравнений (10):

Здесь нужно отметить, что для получения Е_ср сначала получают частичную сумму Еiср

Вместе с тем, выводят также следующее уравнение (12):

А отсюда выводят следующее уравнение (13):

Поскольку трудно получить определенный интеграл функции φ²(α) в интервале между 0 и 1, осуществляют аппроксимацию, показанную в следующих уравнениях (14):

Здесь

Используя аппроксимированную функцию (14), получают частичную сумму Еiср

Эти уравнения можно перегруппировать в виде следующего уравнения (17):

Чтобы получить среднюю погрешность Е_ср, суммируют частичную сумму Еiср

Чтобы получить максимальную погрешность Е_макс, выбирают максимальное значение среди значений максимальной погрешности Еiмакс

Пользуясь вышеописанной функцией аппроксимации, можно аппроксимировать Еiмакс

Максимальную погрешность Е_макс во всем интервале [t₀, t_L] выражают следующим уравнением (21):

Блок 80 интерполяционного анализа, показанный на фиг.6, посылает информацию 114 о количестве ключей, минимальное значение и максимальное значение нормализованных ключевых значений, разрешения ключа и ключевого значения, а также метку ключа в статистический кодер 86. В то же время блок 80 интерполяционного анализа посылает ключи 110 в кодер 82 ключей и посылает информацию о ключевых значениях, включающую в себя минимальное значение и максимальное значение нормализованных ключевых значений, в кодер 84 ключевых значений.

Ниже приведено пояснение кодирования ключей и ключевых значений в кодере 82 ключей и кодере 84 ключевых значений. Ключи и ключевые значения сжимаются методом ДИКМ-квантования в кодере 82 ключей и кодере 84 ключевых значений соответственно. Квантованная информация вместе с другой информацией посылается в статистический кодер 86 и выводится в виде потока битов, подвергнутого окончательному кодированию сжатием, через выходной вывод ВЫХ3. Например, ДИКМ-квантователь 104 кодера 82 ключей осуществляет кодирование методом ДИКМ-квантования (т.е. кодирует разность между текущим значением и непосредственным предыдущим значением) ключа, посылаемого из блока 80 интерполяционного анализа, и выводит закодированный результат в статистический кодер 86. В то же время ДИКМ-квантователь 106 кодера 84 ключевых значений осуществляет кодирование методом ДИКМ-квантования (т.е. кодирует разность между текущим значением и непосредственным предыдущим значением) ключевых значений, а также минимального значения и максимального значения ключевых значений, посылаемых из блока 80 интерполяционного анализа, и выводит закодированный результат в статистический кодер 86.

На фиг.10 представлена схема процесса квантования и проиллюстрирован широко применяемый метод ДИКМ. Обращаясь к фиг.10, отмечаем, что в случае ключа (k) окончательная погрешность (е) подвергается сжатию квантованием, как показывает следующее уравнение (22). Фиг.10 поясняет уравнение (22). То есть, получают разность (d1) между непосредственным предыдущим значением (K_i-1) и его предыдущим значением (K_i-2). Значение разности (d1) прибавляют к непосредственному предыдущему значению (K_i-1) для формирования аппроксимированного значения (K_i). Затем получают окончательную погрешность (е) как разность между аппроксимированным значением (K_i) и текущим значением (K_i). Кстати, погрешность (е) можно легко получить как разность между текущим значением (K_i) и непосредственным предыдущим значением (k_i-1).

На фиг.11а - 11е представлены схемы, показывающие форматы закодированных потоков битов согласно настоящему изобретению. На фиг.11а показан формат закодированного потока битов согласно настоящему изобретению, который включает в себя количество ключей (кол_ключей) разрешение ключей (разр_к), разрешение ключевых значений (разр_кзн), массив ([мин/макс]) 230 минимального значения и максимального значения ключевых значений, массив ([метка_ключа]) 232 меток ключей, массив ([ключ]) 234 ключей и массив ([кзн]) 236 ключевых значений. Здесь квадратные скобки [] обозначают массив. На фиг.11b показан формат массива 230 минимального значения и максимального значения ключевых значений, на фиг.11с показан формат массива 232 меток ключей, на фиг.11d показан формат массива 234 ключей, а на фиг. 11е показан формат массива 236 ключевых значений.

Массив 230 минимального значения и максимального значения ключевых значений, показанный на фиг.11а, сформирован из минимальных значений для осей X, У и Z (мин_х, мин_у и мин_z) и максимальных значений для осей X, У и Z (макс_х, макс_у и макс_z). Массив 232 меток ключей сформирован из n меток ключей (метка₀_ключа, метка₁_ключа, метка₂_ключа, метка₃_ключа, ..., метка_n-1_ключа). Здесь n обозначает количество ключей. Массив 234 ключей сформирован из n ключей (ключ₀, ключ₁, ключ₂, ключ₃, ..., ключ_n-1). Здесь данные ключей и меток ключей для точек разрыва, которые классифицированы как необязательные, например - точки разрыва Т1, Т3 и Т6 из таблицы 2, можно исключить из массива ключей или массива меток ключей. Таким образом, массив ключей и/или массив меток ключей может состоять из данных, количество которых меньше количества (n) исходных ключей. Массив 236 ключевых значений сформирован из р первых ключевых значений (кзн_Х₀, кзн_Х₁, ..., кзн_X_p-1), q вторых ключевых значений (кзн_Y₀, кзн_Y₁, ..., кзн_Y_q-1) и r третьих ключевых значений (кзн_Z₀, кзн_Z₁, ..., кзн_Z_r-1). Здесь p≤n, q≤n и r≤n.

Между тем, устройство и способ восстановления траектории анимации согласно настоящему изобретению реализуются как инверсия процесса сжатия. Статистический декодер 90, показанный на фиг.7, принимает закодированный поток битов через входной вывод BХ4, осуществляет статистическое декодирование этого потока битов и выводит результат статистического декодирования как в декодер 92 ключей, так и в декодер 94 ключевых значений. Декодер 92 ключей и декодер 94 ключевых значений принимают квантованные ключи и ключевые значения соответственно, которые являются результатом статистического декодирования, и, используя дополнительную информацию, например метку ключа, восстанавливают данные, имевшиеся перед квантованием. То есть, декодер 92 ключей принимает результат статистического декодирования и декодирует ключи, а декодер 94 ключевых значений принимает результат статистического декодирования и декодирует ключевые значения. Для этого декодер 92 ключей может быть выполнен в виде ДИКМ-деквантователя 126, а декодер 94 ключевых значений может быть выполнен в виде ДИКМ-деквантователя 128. Каждый ДИКМ-деквантователь - 126 или 128 - декодирует вводимые данные, декодированные в статистическом декодере 90, методом ДИКМ-деквантования.

Блок 96 интерполяционного восстановления принимает данные, декодированные в декодере 92 ключей и декодере 94 ключевых значений, и восстанавливает исходную траекторию анимации. Блок 96 интерполяционного восстановления принимает информацию 124 о количестве ключей, минимальное значение и максимальное значение нормализованных ключевых значений и флаги ключей из статистического декодера 90, ключи 120 из декодера 92 ключей и информацию 122 о ключевых значениях из декодера 94 ключевых значений. Блок 96 интерполяционного восстановления восстанавливает пустые ключевые значения посредством линейной интерполяции, пользуясь вводимой информацией. Например, в таблице 2 ключевое значение для оси Х в точке Т2 разрыва можно восстановить посредством линейной интерполяции, пользуясь ключевыми значениями для точек Т0 и Т4. Для этого блок 96 интерполяционного восстановления может быть выполнен в виде блока 95 интерполяционного восстановления ключей и ключевых значений. Восстановленная траектория анимации в форме (ключ, ключевые значения) выводится через выходной вывод ВЫХ4.

На фиг.12 представлена таблица, поясняющая процесс декодирования, выраженный на языке программирования согласно настоящему изобретению. Эту таблицу также называют синтаксисом потоков битов.

Обращаясь к прилагаемым чертежам, отмечаем, что способ сжатия траектории анимации с использованием линейной аппроксимации согласно настоящему изобретению теперь будет сравниваться с известным способом интерполяционного сжатия с использованием ДФС в соответствии с алгоритмом МРЕ6-4.

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

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

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

1. Устройство для сжатия траектории анимации, содержащее блок анализа интерполятора для выделения предварительно определенного количества точек разрыва из траектории анимации и выдачи ключей и ключевых значений, соответствующих точкам разрыва, кодер ключей для кодирования ключей, выдаваемых из блока анализа интерполятора, кодер ключевых значений для кодирования ключевых значений, выдаваемых из блока анализа интерполятора, и статистический кодер для статистического кодирования ключей и ключевых значений, которые закодированы в кодере ключей и кодере ключевых значений соответственно, и вывода закодированных потоков битов.2. Устройство по п.1, в котором блок анализа интерполятора определяет количество точек разрыва таким образом, что минимизируется разность между аппроксимированной траекторией анимации, которую получают с помощью предварительно определенного количества точек разрыва, выделенных среди точек разрыва исходной траектории анимации, и исходной траекторией анимации.3. Устройство по п.1, в котором кодер ключей кодирует ключи, выводимые из блока анализа интерполятора, методом квантования посредством дифференциальной импульсно-кодовой модуляции (ДИКМ-квантования).4. Устройство по п.1, в котором кодер ключевых значений кодирует ключевые значения, выдаваемые из блока анализа интерполятора, методом ДИКМ-квантования.5. Устройство по п.1, в котором принимают обе концевые точки исходной траектории анимации за начальные точки, блок анализа интерполятора находит среди точек разрыва точки разрыва, представляющие аппроксимированную траекторию анимации, которая имеет наименьшую разницу от исходной траектории анимации, и этот процесс повторяется до тех пор, пока аппроксимированная траектория анимации не станет близкой к исходной траектории.6. Устройство по п.5, в котором точки разрыва определяются таким образом, что разность площадей между исходной траекторией анимации и аппроксимированной траекторией анимации является наименьшей.7. Устройство по любому из п.3 или 4, в котором ДИКМ-квантование представляет собой кодирование разности между текущим значением и непосредственным предыдущим значением или представляет собой кодирование разности между текущим значением и аппроксимированным значением, которое получено путем прибавления непосредственного предыдущего значения к разности между непосредственным предыдущим значением и его предыдущим значением.8. Устройство для восстановления траектории анимации, содержащее статистический декодер для приема закодированного потока битов и статистического декодирования этого потока битов, декодер ключей для приема результата статистического декодирования и для декодирования ключей, декодер ключевых значений для приема результата статистического декодирования и для декодирования ключевых значений, и блок восстановления интерполятора для получения ключевых значений путем линейной интерполяции на основании ключей и ключевых значений, декодированных в декодере ключей и декодере ключевых значений соответственно, и восстановления исходной траектории анимации.9. Устройство по п.8, в котором декодер ключей декодирует результат статистического декодирования, который вводится из статистического декодера, методом ДИКМ-деквантования.10. Устройство по п.8, в котором декодер ключевых значений декодирует результат статистического декодирования, который вводится из статистического декодера, методом ДИКМ-деквантования.11. Способ восстановления траектории анимации, включающий в себя этапы, на которых осуществляют прием и статистическое декодирование закодированного потока битов, декодируют ключи и ключевые значения, исходя из результата статистического декодирования, и восстанавливают исходную траекторию анимации, получая ключевые значения путем линейной интерполяции на основании декодированных ключей и ключевых значений.12. Способ сжатия траектории анимации, включающий в себя этапы, на которых выделяют предварительно определенное количество точек разрыва из траектории анимации, выделяют ключи и ключевые значения с использованием выделенных точек разрыва и кодируют эти ключи и ключевые значения, и осуществляют статистическое кодирование закодированных ключей и ключевых значений для получения закодированных потоков битов, при этом количество точек разрыва регулируется таким образом, чтобы разность между траекторией анимации, сформированной выделенными точками разрыва и исходной траекторией анимации, минимизируется.13. Способ по п.12, в котором, дополнительно, данные располагают в закодированных потоках битов в виде формата, содержащего метки ключа в виде массива для указания ключевых значений, оси которых выбраны среди ключевых значений, соответствующих координате х, у или z каждой точки разрыва траектории анимации, ключи в виде массива для указания того, что, по меньшей мере, одно или более ключевых значений выбраны среди ключевых значений, соответствующих координате х, у или z каждой точки разрыва, и ключевые значения в виде массива, выбранных для каждой точки разрыва.14. Способ по п.13, в котором формат дополнительно содержит минимальные значения ключевых значений, соответствующих осям X, Y и Z координат, и максимальные значения ключевых значений, соответствующих осям X, Y и Z координат.15. Способ по п.13, в котором массив меток ключа включает в себя М данных, а М равно количеству исходных ключей или меньше этого количества.16. Способ по п.13, в котором массив ключей включает в себя М данных, а М равно количеству исходных ключей или меньше этого количества.17. Способ по п.13, в котором ключевые значения включают в себя р (≤n) первых ключевых значений, соответствующих оси х, q (≤n) вторых ключевых значений, соответствующих оси у, и r (≤n) третьих ключевых значений, соответствующих оси z, a n обозначает количество ключей.18. Способ выделения точек разрыва траектории анимации, включающий этапы, на которых (а) выбирают две точки разрыва в обеих концевых точках исходной траектории анимации среди точек разрыва на траектории анимации, (б) выбирают одну точку разрыва среди остающихся точек разрыва, за исключением двух выбранных точек разрыва, (в) интерполируют ключевые значения остающихся точек разрыва, за исключением выбранных точек разрыва, с использованием выбранных точек разрыва, (г) формируют аппроксимированную траекторию анимации на основании выбранных точек разрыва и интерполированных ключевых значений, выбирают аппроксимированную траекторию анимации, которая имеет наименьшую разность траекторий между исходной траекторией анимации и этой аппроксимированной траекторией анимации, и выбирают точки разрыва, соответствующие выбранной траектории анимации, и (д) выбирают одни точки разрыва среди остающихся точек разрыва, за исключением точек разрыва, выбранных на этапах (а) и (б), и повторяют этапы (в)-(д) до тех пор, пока разность траекторий не станет меньше, чем допустимая разность.19. Способ по п.18, при котором разность траекторий выражают суммой площадей трапецоидов или скрученных трапецоидов, которые образованы исходной траекторией анимации и аппроксимированной траекторией анимации.20. Способ по п.18, при котором разность траекторий в ориентационном интерполяторе определяют как дифференциальный угол поворота в дифференциальном преобразовании поворота, представляющем собой разность между преобразованием поворота исходной траектории анимации и преобразованием поворота аппроксимированной траектории.