Способ и устройство кодирования информации изменения формы трехмерного объекта

 

Изобретение относится к области сжатия данных, в частности к способу и устройству кодирования информации изменения формы трехмерного (3D) объекта. Его использование позволяет получить технический результат в виде увеличения скорости передачи данных и надежности при их передаче, а также уменьшения вероятности возникновения ошибок при передачи упомянутых данных. Технический результат достигается за счет того, что информация о вершинах, формирующих форму 3D объекта, описывается способом ключевого кадра для выполнения изменения формы 3D объекта, при этом кодирование содержит этапы, на которых (а) выделяют ключи, указывающие положения ключевых кадров на оси времени, ключевые значения, показывающие характеристическую информацию ключевых кадров, и связанную информацию, путем анализа информации узла 3D объекта, (b) генерируют информацию связности вершины из связанной информации, (с) генерируют дифференциальные значения для каждого из ключей, из которых должна быть удалена, временная избыточность данных и ключевых значений, из которых должна быть удалена пространственно-временная избыточность данных, на основе информации связности вершины, (d) квантуют дифференциальные значения, и (е) удаляют избыточность среди битов и генерируют сжатый поток битов посредством статистического кодирования, путем приема квантованных ключей и ключевых значений. 8 c. и 36 з.п. ф-лы, 22 ил.

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

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

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

2. Способ кодирования по п.1, отличающийся тем, что на этапе (а) информация узла делится на узел координатного интерполятора (КИ) и узел набора индексированной грани (НИГ), и данные поля, сформированные из ключей и ключевых значений, выделяются из узла КИ, а данные поля координатного индекса (CIdx) выделяются из узла НИГ.

3. Способ кодирования по п.2, отличающийся тем, что на этапе (b) данные поля CIdx, выделенные из узла НИГ, принимаются как связанная информация, и информация поиска в ширину (ПВШ) для определения пространственной корреляции данных между вершинами, которая формируется как информация связности вершины.

4. Способ кодирования по п.3, отличающийся тем, что на этапе (b) данные поля CIdx принимаются и сохраняются в очереди для каждой вершины, и генерируется информация ПВШ, на основе того, посещается или нет каждая вершина по очереди.

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

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

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

8. Способ кодирования по п.1, отличающийся тем, что на этапе (е) избыточность среди битов удаляется с учетом вероятности появления символа.

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

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

11. Способ кодирования по п.10, отличающийся тем, что на этапе (а) информация узла разделяется на узел координатного интерполятора (КИ) и узел набора индексированной грани (НИГ), и данные поля, сформированные из ключей и ключевых значений, выделяются из узла КИ, а данные поля координатного индекса (CIdx) выделяются из узла НИГ.

12. Способ кодирования по п.10, отличающийся тем, что на этапе (b) данные поля CIdx, выделенные из узла НИГ, принимаются как связанная информация, и формируется информация поиска в ширину (ПВШ) как информация связности вершины для определения пространственной корреляции данных между вершинами.

13. Способ кодирования по п.12, отличающийся тем, что на этапе (b) данные поля CIdx принимаются и сохраняются в очереди для каждой вершины, и генерируется информация ПВШ, на основе того, посещалась или нет каждая вершина по очереди.

14. Способ кодирования по п.10, отличающийся тем, что этап (d) дополнительно содержит этапы, на которых (d1) принимают информацию связности вершины, информацию координат узла НИГ, как связанную информацию, и ключевые значения, и генерируют дифференциальные значения между всеми ключевыми значениями изменения положения в 3D пространстве, (d2) удаляют избыточность данных в дифференциальных значениях согласно пространственной корреляции между вершинами, на основе информации связности вершины, и (d3) обрабатывают с помощью дифференциальной импульсно-кодовой модуляции (ДИКМ) каждый из ключей, выделенных на этапе (а), и ключевых значений, из которых удаляется избыточность данных вследствие пространственной корреляции.

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

16. Способ кодирования информации изменения формы 3-мерного (3D) объекта, в котором информация о вершинах, формирующих форму 3D объекта, кодируется способом ключевого кадра для выполнения изменения формы 3D объекта, при этом упомянутый способ кодирования содержит этапы, на которых (а) выделяют ключи, указывающие положение ключевых кадров на оси времени, ключевые значения, показывающие характеристическую информацию ключевых кадров, и связанную информацию, путем анализа информации узла 3D объекта, (b) генерируют информацию начала поиска в ширину (ПВШ) для определения пространственной корреляции данных между вершинами 3D объекта, (с) генерируют информацию связности вершины из связанной информации, извлеченной на этапе (а), и информации начала поиска, генерированной на этапе (b), (d) генерируют дифференциальные значения каждого из ключей, из которых удаляется временная избыточность данных, и ключевых значений, из которых удаляется пространственно-временная избыточность данных, на основе информации связности вершины, (е) квантуют дифференциальные значения, (f) принимают квантованные ключи и значения ключей, и генерируют шаги квантования кодированных битов ключевых значений, и (g) принимают шаги квантования кодированных битов и удаляют избыточность среди битов в квантованных значениях.

17. Способ кодирования по п.16, отличающийся тем, что на этапе (а) информация узла делится на узел координатного интерполятора (КИ) и узел набора индексированной грани (НИГ), и данные поля, сформированные из ключей и ключевых значений, извлекаются из узла КИ, а данные поля координатного индекса (CIdx) извлекаются из узла НИГ.

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

19. Способ кодирования по п.16, отличающийся тем, что этап (f) содержит этапы, на которых (f1) сравнивают максимальное значение и минимальное значение для каждой из координат X, Y и Z, формирующих квантованные ключевые значения, (f2) если абсолютное значение минимального значения меньше или равно максимальному значению каждой из координат X, Y и Z, то шаг квантования кодированных битов выводится как Qstep=int{(log₂|Min|)+1}, (f3) если абсолютная величина минимального значения больше, чем максимальное значение в каждой из координат X, Y и Z, то шаг квантования кодированных битов выводится как Qstep=int{(log₂|Max|)+l}.

20. Способ кодирования по п.16, отличающийся тем, что на этапе (g) избыточность среди битов удаляется с учетом вероятности появления символа.

21. Способ кодирования по п.16, отличающийся тем, что поток битов, полученный способом кодирования, содержит информацию заголовка, содержащую размер квантования ключевых значений, шаг квантования кодированных битов координат для Х ключевых значений, шаг квантования кодированных битов координат для Y ключевых значений, шаг квантования кодированных битов координат для Z ключевых значений, минимальные значения и максимальные значения, которые используются при нормировке дифференциальных значений квантованных ключей и ключевых значений для получения значений между 0 и 1 включительно, и информацию ключевых значений согласно порядку поиска ПВШ.

22. Способ кодирования информации изменения формы 3-мерного (3D) объекта, в котором информация о вершинах, формирующих форму 3D объекта, кодируется способом ключевого кадра для выполнения изменения формы 3D объекта, при этом упомянутый способ кодирования содержит этапы, на которых (а) выделяют ключи, указывающие положение ключевых кадров на оси времени, ключевые значения, показывающие характеристическую информацию ключевых кадров, и связанную информацию, путем анализа информации узла 3D объекта, (b) генерируют информацию начала поиска в ширину (ПВШ) для определения пространственной корреляции данных между вершинами 3D объекта, (с) генерируют информацию связности вершины из связанной информации, выделенной на этапе (а), и информации начала поиска, генерированной на этапе (b), (d) квантуют ключи и ключевые значения, (е) генерируют дифференциальные значения каждого из квантованных ключей, из которых удаляется временная избыточность данных, и квантованных ключевых значений, из которых удаляется пространственно-временная избыточность данных, на основе информации связности вершины, (f) принимают дифференциальные значения и генерируют шаги квантования кодированных битов ключевых значений, и (g) принимают шаги квантования кодированных битов и удаляют избыточность среди битов в квантованных значениях.

23. Способ кодирования по п.22, отличающийся тем, что на этапе (а) информация узла делится на узел координатного интерполятора (КИ) и узел набора индексированной грани (НИГ), и данные поля, сформированные из ключей и ключевых значений, выделяются из узла КИ, данные поля координатного индекса (CIdx) выделяются из узла НИГ.

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

25. Способ кодирования по п.22, отличающийся тем, что этап (f) содержит этапы, на которых (f1) сравнивают максимальное значение и минимальное значение для каждой из координат X, Y и Z, формирующих квантованные ключевые значения, (f2) если абсолютное значение минимального значения меньше или равно максимальному значению каждой из координат X, Y и Z, то шаг квантования кодированных битов выводится как Qstep=int{(log₂|Min|)+1}, (f3) если абсолютная величина минимального значения больше, чем максимальное значение в каждой из координат X, Y и Z, то шаг квантования кодированных битов выводится как Qstep=mt{(log₂|Max|)+1}.

26. Способ кодирования по п.22, отличающийся тем, что на этапе (g) удаляется избыточность среди битов с учетом вероятности появления символа.

27. Способ кодирования по п.22, отличающийся тем, что поток битов, полученный способом кодирования, содержит информацию заголовка, содержащую размер квантования ключевых значений, шаг квантования кодированных битов координат для Х ключевых значений, шаг квантования кодированных битов координат для Y ключевых значений, шаг квантования кодированных битов координат для Z ключевых значений, минимальные значения и максимальные значения, которые используются при нормировке дифференциальных значений квантованных ключей и ключевых значений для получения значений между 0 и 1 включительно, и информацию ключевых значений согласно порядку поиска ПВШ.

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

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

30. Устройство кодирования по п.28 или 29, отличающееся тем, что блок ввода данных поля содержит анализатор для разделения информации узла на узел координатного интерполятора (КИ) и узел набора индексированной грани (НИГ), и демультиплексор для выделения данных полей, сформированных с использованием ключей и ключевых значений узла КИ, и выделения данных поля координатного индекса (CIdx) узла НИГ.

31. Устройство кодирования по п.30, отличающееся тем, что блок обработки связности вершины принимает данные поля CIdx, выделенные из узла НИГ в качестве связанной информации, и формирует информацию поиска в ширину (ПВШ) для определения пространственной корреляции данных между вершинами в качестве информации связности вершины.

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

33. Устройство кодирования по п.28 или 29, отличающееся тем, что блок обработки АДИКМ содержит генератор дифференциальных значений для приема информации связности вершины, информации координат узла ПИТ в качестве связанной информации и ключевых значений, и генерации дифференциальных значений между всеми значениями положения ключевых значений изменения в 3D пространстве, блок предсказания для удаления избыточности данных в дифференциальных значениях согласно пространственной корреляции между вершинами, на основе информации связности вершины, и блок обработки с помощью дифференциальной импульсно-кодовой модуляции (ДИКМ) для ДИКМ обработки каждого из ключей и ключевых значений, из которых удаляется избыточность данных вследствие пространственной корреляции.

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

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

36. Устройство кодирования информации изменения формы 3-мерного (3D) объекта, в котором информация о вершинах, формирующих форму 3D объекта, кодируется способом ключевого кадра для выполнения изменения формы 3D объекта, при этом упомянутое устройство кодирования содержит блок ввода данных поля для выделения ключей, указывающих положение ключевых кадров на оси времени, ключевых значений, показывающих характеристическую информацию ключевых кадров, и связанной информации, анализируя информацию узла 3D объекта, блок обработки связности вершины для генерации информации связности вершины из связанной информации, генератор начальной вершины для определения начальной вершины информации связности вершины из связанной информации, блок обработки с помощью адаптивной дифференциальной импульсно-кодовой модуляции (АДИКМ) для генерации дифференциальных значений каждого из ключей, из которых удаляется временная избыточность данных, и ключевых значений, из которых удаляется пространственно-временная избыточность данных, на основе информации связности вершины, блок квантования для квантования дифференциальных значений, блок генерации шага квантования для приема квантованных ключей и ключевых значений и генерации шагов квантования кодированных битов для координат X, Y и Z квантованных ключевых значений, и блок статистической обработки для приема шагов квантования кодированных битов для координат X, Y и Z и удаления избыточности среди битов в квантованных значениях.

37. Устройство кодирования информации изменения формы 3-мерного (3D) объекта, в котором информация о вершинах, формирующих форму 3D объекта, кодируется способом ключевого кадра для выполнения изменения формы 3D объекта, при этом упомянутое устройство кодирования включает в себя блок ввода данных поля для выделения ключей, указывающих положение ключевых кадров на оси времени, ключевых значений, показывающих характеристическую информацию ключевых кадров, и связанной информации, путем анализа информации узла 3D объекта, блок обработки связности вершины для генерации информации связности вершины из связанной информации, генератор начальной вершины для определения начальной вершины информации связности вершины из связанной информации, блок квантования для квантования ключей и ключевых значений, блок обработки с помощью адаптивной дифференциальной импульсно-кодовой модуляции (АДИКМ) для генерации дифференциальных значений квантованных ключей, из которых удаляется временная избыточность данных, и дифференциальных значений квантованных ключевых значений, из которых удаляется пространственно-временная избыточность данных, на основе информации связности вершины, блок генерации шага квантования для генерации шагов квантования кодированных битов для координат X, Y и Z разностных ключевых значений, и блок статистической обработки для приема шагов квантования кодированных битов для координат X, Y и Z и удаления избыточности среди битов в квантованных значениях.

38. Устройство кодирования по п.36 или 37, отличающееся тем, что блок ввода данных поля содержит анализатор для разделения информации узла на узел координатного интерполятора (КИ) и узел набора индексированной грани (НИГ), и демультиплексор для выделения данных полей, сформированных с использованием ключей и ключевых значений узла КИ, и выделения данных поля координатного индекса (CIdx) узла НИГ.

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

40. Устройство кодирования по п.38, отличающееся тем, что блок обработки связности вершины принимает данные поля CIdx, выделенные из узла НИГ в качестве связанной информации, формирует информацию поиска в ширину (ПВШ) для определения пространственной корреляции данных между вершинами как информацию связности вершины, принимает информацию начальной вершины, генерированную генератором начальной вершины, и генерирует информацию ПВШ, с помощью которой выполняется поиск начальной вершины.

41. Устройство кодирования по п.38, отличающееся тем, что блок генерации шага квантования содержит блок вычисления максимума и минимума для приема ключевых значений, данных, соответствующие первому ключевому кадру узла КИ, и информации связности вершины, и вывода максимальных значений и минимальных значений для координат X, Y и Z ключевых значений, и генератор шага квантования для генерации шагов квантования кодированных битов, достаточных для выражения диапазона квантованных данных, соответствующих координатам X, Y и Z.

42. Устройство кодирования по п.41, отличающееся тем, что генератор шага квантования сравнивает максимальное значение и минимальное значение для каждой из координат X, Y и Z элементов данных, вводимых из блока вычисления максимума и минимума, и если абсолютная величина минимального значения меньше или равна максимальному значению, то шаг квантования кодированных битов выводится как Qstep=int{(log₂|Min|)+1}, а если абсолютная величина минимального значения больше, чем максимальное значение, то шаг квантования кодированных битов выводится как Qstep=int{(log₂|Max|)+1}.

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

44. Устройство кодирования по п.43, отличающееся тем, что поток битов содержит информацию заголовка, содержащую размер квантования ключевых значений, шаг квантования кодированных битов для координат Х ключевых значений, шаг квантования кодированных битов для координат Y ключевых значений, шаг квантования кодированных битов для координат Z ключевых значений, минимальные значения и максимальные значения, которые используются при нормировке дифференциальных значений из блока квантования для получения значений между 0 и 1 включительно, и информацию ключевого значения согласно порядку поиска ПВШ.

РИСУНКИ

Рисунок 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, Рисунок 46, Рисунок 47, Рисунок 48, Рисунок 49, Рисунок 50, Рисунок 51, Рисунок 52, Рисунок 53, Рисунок 54, Рисунок 55, Рисунок 56, Рисунок 57