Устройство и способ кодирования и декодирования ключевых данных для графической анимации

 

Изобретение относится к средствам компьютерной анимации изображений. Его использование для кодирования и декодирования ключевой информации позволяет обеспечить технический результат в виде повышения эффективности кодирования. Этот технический результат достигается за счёт того, что устройство кодирования содержит: устройство квантования для квантования ключевых данных; блок обработки дифференциальной импульсно-кодовой модуляцией (ДИКМ) для неоднократного выполнения обработки ДИКМ с выведением данных, имеющих наименьшую дисперсию среди данных ДИКМ N-го порядка; блок удаления полярных значений, уменьшающий диапазон данных путем удаления полярного значения; и энтропийный кодер, удаляющий избыточность битов в выходных данных и формирующий уплотнённый и кодированный поток бинарных битов. При этом устройство декодирования содержит энтропийный декодер, блок восстановления полярных значений, блок обработки обратной ДИКМ и устройство обратного квантования. 10 с. и 20 з.п. ф-лы, 13 ил.

Текст описания в факсимильном виде (см. графическую часть).

Формула изобретения

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

2. Устройство кодирования по п.1, отличающееся тем, что блок обработки ДИКМ содержит блок обработки N-й ДИКМ, обрабатывающий ДИКМ квантованные данные, принимающий данные, обработанные ДИКМ, и, путём неоднократного выполнения обработки ДИКМ, формирующий данные ДИКМ N-го порядка; блок обработки дисперсии, для каждого порядка получающий и выводящий дисперсию выходных данных ДИКМ из блока обработки ДИКМ N-го порядка; и блок выделения минимальной дисперсии, выбирающий данные ДИКМ, соответствующие порядку, имеющему наименьшую дисперсию среди дисперсий, вычисленных в блоке обработки дисперсии, и выводящий выбранные данные ДИКМ к блоку удаления полярных значений.

3. Устройство по п.1, отличающееся тем, что блок удаления полярных значений содержит блок предварительной обработки, обнуляющий данные, наиболее частые среди выходных данных блока обработки ДИКМ, и распределяющий около нуля остальные данные так, чтобы среднее значение остальных данных было близко к нулю; и блок основной обработки, удаляющий положительное полярное значение и отрицательное полярное значение среди предварительно обработанных данных так, чтобы уменьшить диапазон между максимальным и минимальным значениями.

4. Устройство кодирования по п.3, отличающееся тем, что блок предварительной обработки содержит генератор наиболее вероятного значения, получающий данные, наиболее частые среди выходных дифференциальных данных блока обработки ДИКМ, как наиболее вероятное значение; блок обработки смещением, вычитающий из дифференциальных данных наиболее вероятное значение, полученное генератором наиболее вероятного значения так, чтобы смещение дифференциальных данных было такое же, как наиболее вероятное значение; блок обработки свёрткой, создающий положительное число из данных, меньших нуля, среди данных, обработанных смещением; и делитель, вычитающий заданное значение из данных, обработанных в блоке обработки свёрткой, в соответствии с размером данных так, чтобы уменьшить диапазон данных между максимальным и минимальным значениями.

5. Устройство кодирования по п.3, отличающееся тем, что блок основной обработки содержит блок обработки делением вверх/вниз, выделяющий из предварительно обработанных данных максимальное и минимальное значения, сравнивающий их абсолютные значения, в соответствии с результатом сравнения, осуществляемым неоднократно, М раз, выполняющий обработку делением вниз, при которой данные, большие половины максимального значения, преобразуются в значение, аппроксимируемое нулём, или обработку делением вверх, при которой данные, меньшие половины максимального значения, преобразуются в значение, аппроксимируемое нулём, и формирующий данные, обработанные делением; и блок вывода данных, вычисляющий для каждого порядка дисперсию выходных данных деления вверх или данных деления вниз из блока обработки делением вверх/вниз, и выбирающий и выводящий данные, обработанные делением, соответствующие порядку, имеющему наименьшую дисперсию.

6. Способ кодирования, предназначенный для кодирования ключевых данных, соответствующих переменным времени, среди данных графической анимации, заключающийся в том, что: (а) квантуют ключевые данные и формируют квантованные данные; (b) обрабатывают квантованные данные дифференциальной импульсно-кодовой модуляцией (ДИКМ), принимают данных, обработанные ДИКМ, и, путём неоднократного выполнения обработки ДИКМ, выбирают и выводят данные ДИКМ, имеющие наименьшую дисперсию среди данных ДИКМ N-го порядка, сформированных при обработке ДИКМ; (с) уменьшают диапазон изменения данных путем удаления полярного значения в выходных данных ДИКМ операции (b); и (d) удаляют избыточность бинарных битов в выходных данных операции (с) и формируют уплотнённый и кодированный поток битов.

7. Способ кодирования по п. 6, отличающийся тем, что при операции (b): (b1) обрабатывают ДИКМ квантованные данные, принимают данные, обработанные ДИКМ, и, путем неоднократного выполнения обработки ДИКМ, формируют данные ДИКМ N-го порядка; (b2) вычисляют для каждого порядка дисперсии данных ДИКМ, сформированных при операции (b1); и (b3) выбирают и выводят данные ДИКМ, соответствующие порядку, имеющему наименьшую дисперсию среди дисперсий, вычисленных при операции (b2).

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

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

10. Способ удаления полярного значения в данных, которые требуется передать, для повышения эффективности кодирования в устройстве кодирования для кодирования данных передачи, которые требуется передать, заключающийся в том, что: (а) получают, как наиболее вероятное значение, данные, наиболее частые среди данных передачи; (b) вычитают из соответствующих данных передачи наиболее вероятное значение; (с) создают положительные числа из данных, меньших нуля, среди данных, обработанных при операции (b); (d) выполняют обработку делением, уменьшающую диапазон данных между максимальным и минимальным значениями путём вычитания заданного значения из данных, обработанных при операции (с), в соответствии с размером данных; (е) выделяют максимальное и минимальное значения из предварительно обработанных данных, сравнивают их абсолютные значения и, в соответствии с результатом сравнения, неоднократно выполняют, М раз, процесс преобразования данных, которые больше половины максимального значения, в данные, аппроксимируемые нулём, или данных, которые меньше половины максимального значения, в значение, аппроксимируемое нулём, и формируют данные, обработанные делением; и (f) вычисляют для каждого порядка дисперсию данных, сформированных при операции (е), и выбирают и выводят данные, обработанные делением, соответствующие порядку, имеющему наименьшую дисперсию, как данные, в которых удалены полярные значения.

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

12. Способ по п.10, отличающийся тем, что при операции (d): (d1) определяют, являются или нет данные, сформированные при операции (с), большими половины максимального значения; (d2) если при операции (d1) данные больше половины максимального значения, то создают данные в виде отрицательного числа путем вычитания из данных, сформированных при операции (с), выражения (максимальное значение +1); и (d3) если при операции (d1) данные не больше половины максимального значения, то поддерживают значение без изменения.

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

14. Способ по п.13, отличающийся тем, что при операции (е2): (е21) если при операции (е1) абсолютное значение максимального значения больше абсолютного значения минимального значения, то при операции (d) определяют, являются или нет данные, обработанные делением, большими или равными нулю; (е22) если при операции (е21) данные, обработанные делением, являются отрицательными числами, то умножают на 2 данные, обработанные делением, и формируют результат, как данные деления вниз; (е23) если данные, обработанные делением, являются большими и равными нулю, то определяют, превышают или нет данные, обработанные делением, половину максимального значения; (е24) если при операции (е23) данные, обработанные делением, превышают половину максимального значения, то формируют данные, вычисленные путём следующего уравнения, как данные деления вниз:

где D^к_i обозначает данные деления вниз, Е^к_i обозначает данные, обработанные делением, а max(E^к_i) обозначает максимальное значение; (е25) если при операции (е23) данные, обработанные делением, не превышают половины максимального значения, то формируют данные, обработанные делением, как данные деления вниз.

15. Способ по п.13, отличающийся тем, что при операции (е3): (е31) если при операции (е1) абсолютное значение минимального значения больше абсолютного значения максимального значения, то при операции (d) определяют, являются или нет данные, обработанные делением, отрицательным числом; (е32) если при операции (е31) данные, обработанные делением, не являются отрицательным числом, то формируют данные, обработанные делением, как данные деления вверх, без изменения; (е33) если при операции (е31) данные, обработанные делением, являются отрицательным числом, то определяют, являются или нет данные, обработанные делением, меньшими половины минимального значения; (е34) если при операции (е33) данные, обработанные делением, меньше половины минимального значения, то формируют данные, вычисленные путем следующего уравнения, как данные деления вверх:

где D^к_i обозначает данные деления вверх, Е^к_i обозначает данные, обработанные делением, а min(Е^к_i) обозначает минимальное значение; (е35) если при операции (е33) данные, обработанные делением, не меньше половины минимального значения, то формируют значение, полученное путем умножения на 2 данных, обработанных делением, как данные деления вверх.

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

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

18. Носитель данных для хранения потока битов, сформированного в любом из пп.1 и 6, содержащий информацию заголовка, которая содержит поле, в котором хранится количество битов квантования, в которые квантуются ключевые данные, поле, в котором хранится количество действительных битов, необходимых при кодировании ключевых данных, поле, в котором хранится количество битов, необходимых при передаче наиболее вероятного значения, минимального значения и максимального значения, поле, в котором хранится ряд ключевых данных, поле, в котором хранится порядок ДИКМ, имеющий наименьшую дисперсию, и порядок деления, имеющий наименьшую дисперсию, соответственно, и поле, в котором хранится наиболее вероятное значение, минимальное значение и максимальное значение, соответственно; и поле ключевой информации, в котором хранятся кодированные ключевые данные.

19. Носитель данных по п.18, отличающийся тем, что поле информации заголовка дополнительно содержит поле, в котором хранятся с первых по n-е кодированные ключевые данные среди данных, полученных n-й ДИКМ, результат которой имеет минимальную дисперсию, а в поле ключевой информации хранится информация о количестве (n) кодированных ключевых данных, которые хранятся в поле информации заголовка, и остальные кодированные ключевые данные, кроме кодированных ключевых данных, которые хранятся в поле информации заголовка.

20. Носитель данных по п.19, отличающийся тем, что каждое из полей, в котором хранятся кодированные ключевые данные, соответствует порядку ДИКМ, а в полях, в которых хранятся наиболее вероятное значение, минимальное значение и максимальное значение, соответственно, хранится знаковый бит, определяющий знак данных, которые хранятся в поле.

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

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

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

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

25. Способ декодирования по п.24, отличающийся тем, что при операции (b): (b1) сравнивают с нулем полярное значение каждого порядка деления в восстановленных данных заголовка, и если полярное значение равно или больше нуля, то обрабатывают обратным делением вниз ключевые данные, восстановленные в энтропийном декодере, а если полярное значение меньше нуля, то обрабатывают обратным делением вверх ключевые данные, так, чтобы восстанавливалось положительное или отрицательное значение; и (b2) смещают данные, полярное значение которых восстановлено при операции (b1), на наиболее частое значение, так, чтобы ключевые данные, распределенные вокруг нуля, восстановились распределенными вокруг наиболее частого значения.

26. Способ декодирования по п.25, отличающийся тем, что при обработке обратным делением вниз операции (b1): (b21) если ключевые данные, восстановленные при операции (а), равны или больше нуля, то формируют восстановленные ключевые данные, как данные, обработанные обратным делением вниз, без изменения; (b22) если ключевые данные, восстановленные при операции (а), меньше нуля и являются нечётным числом, то формируют данные, вычисляемые следующим уравнением, как данные, обработанные обратным делением вниз:

(здесь Е^к_i является данными, полученными путем обработки обратным делением вниз, Мах_i обозначает полярное значение для каждого порядка деления, a D^к_i является ключевыми данными, восстановленными при операции (а)); и (b23) если ключевые данные, восстановленные при операции (а), меньше нуля и являются четным числом, то формируют результат деления на 2 ключевых данных, восстановленных при операции (а), как данные, обработанные обратным делением вниз, а при обработке обратным делением вверх операции (b1), (b24) если ключевые данные, восстановленные при операции (а), равны или больше нуля, то формируют восстановленные ключевые данные без изменения, как данные, обработанные обратным делением вверх; (b25) если ключевые данные, восстановленные при операции (а), меньше нуля и являются нечетным числом, то формируют данные, вычисляемые следующим уравнением, как данные, обработанные обратным делением вверх:

(здесь Е^к_i является данными, полученными путем обработки обратным делением вверх, Мах_i обозначает полярное значение для каждого порядка деления, a D^к_i является ключевыми данными, восстановленными при операции (а)); и (b26) если ключевые данные, восстановленные при операции (а), меньше нуля и являются четным числом, то формируют результат деления на 2 ключевых данных, восстановленных при операции (а), как данные, обработанные обратным делением вверх.

27. Способ декодирования по п.25, отличающийся тем, что при операции (b2): (b21) делают данные, полярные значения которых восстановлены при операции (b1), равными или большими нуля путём добавления максимального значения к данным, в соответствии с размером данных; (b22) обрабатывают обратной сверткой данные, обработанные при операции (b21), так чтобы нечётные числа в данных преобразовались в отрицательные числа; и (b23) обрабатывают обратным смещением данные, при операции (b22) обработанные обратной сверткой, путём смещения данных на наиболее частое значение, так чтобы данные, распределенные вокруг нуля, восстановились распределёнными вокруг наиболее частого значения.

28. Способ декодирования по п.27, отличающийся тем, что при операции (b21) определяют, превышают или нет данные, сформированные при операции (b1), нулевое значение, и если данные равны или больше нуля, то поддерживают значение, а если данные меньше нуля, то к данным, сформированным при операции (b1), добавляют выражение (максимальное значение +1).

29. Способ декодирования по п.27, отличающийся тем, что при операции (b22): (b221) если данные, обработанные при операции (b21), являются нечетным числом, то формируют данные, вычисляемые на основе следующего выражения, как данные, обработанные обратной сверткой:

(здесь Е^к обозначает данные, обработанные обратной сверткой, a D^К обозначает данные, обработанные при операции (b21)); и (b222) если данные, обработанные при операции (b21), являются нулём или четным числом, то формируют результат деления на 2 данных, обработанных при операции (b21), как данные, обработанные обратной сверткой.

30. Носитель, выполненный с возможностью считывания компьютером, со встроенной компьютерной программой для способа декодирования по п.24.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16, Рисунок 17, Рисунок 18, Рисунок 19, Рисунок 20, Рисунок 21, Рисунок 22, Рисунок 23, Рисунок 24, Рисунок 25, Рисунок 26, Рисунок 27, Рисунок 28, Рисунок 29, Рисунок 30, Рисунок 31, Рисунок 32, Рисунок 33, Рисунок 34, Рисунок 35, Рисунок 36, Рисунок 37, Рисунок 38, Рисунок 39, Рисунок 40, Рисунок 41, Рисунок 42, Рисунок 43, Рисунок 44, Рисунок 45