ES2282209T3 - Procedimiento y aparato de compresion de datos. - Google Patents
Procedimiento y aparato de compresion de datos. Download PDFInfo
- Publication number
- ES2282209T3 ES2282209T3 ES01309832T ES01309832T ES2282209T3 ES 2282209 T3 ES2282209 T3 ES 2282209T3 ES 01309832 T ES01309832 T ES 01309832T ES 01309832 T ES01309832 T ES 01309832T ES 2282209 T3 ES2282209 T3 ES 2282209T3
- Authority
- ES
- Spain
- Prior art keywords
- key
- breakpoints
- animation
- trajectory
- keys
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T13/00—Animation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/001—Model-based coding, e.g. wire frame
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/20—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using video object coding
- H04N19/25—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using video object coding with scene description coding, e.g. binary format for scenes [BIFS] compression
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/20—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using video object coding
- H04N19/27—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using video object coding involving both synthetic and natural picture components, e.g. synthetic natural hybrid coding [SNHC]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
- H04N19/593—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving spatial prediction techniques
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Processing Or Creating Images (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
Un procedimiento para comprimir una trayectoria de animación en 3D, que comprende las etapas de: (a) seleccionar dos puntos de ruptura en ambos puntos extremos entre los puntos de ruptura de la trayectoria de animación; (b) seleccionar un punto de ruptura entre los restantes puntos de ruptura excluyendo los dos puntos de ruptura seleccionados; (c) interpolar valores de clave de los restantes puntos de ruptura con exclusión de los puntos de ruptura seleccionados, utilizando los puntos de ruptura seleccionados; (d) formar una trayectoria aproximada en base a los puntos de ruptura seleccionados y a los valores de clave interpolados, seleccionando una trayectoria de animación aproximada que tenga la diferencia más pequeña entre la trayectoria de animación original y la trayectoria de animación aproximada, y seleccionar puntos de ruptura correspondientes a la trayectoria de animación seleccionada, y (e) seleccionar un punto de ruptura entre los restantes puntos de ruptura excluyendo los puntos de ruptura seleccionados en las etapas (a) y (b), y repetir las etapas (c) a (e) hasta que la diferencia de trayectoria sea menor que una diferencia permisible, en el que las etapas (a) a (e) se repiten para cada uno de los tres ejes, y los puntos de ruptura en cada eje son diferentes de aquellos de los otros ejes; comprendiendo además el procedimiento registrar una banderola de clave para cada punto de ruptura que indica información sobre cuál de los tres ejes ha sido elegido para el valor de clave del punto de ruptura.
Description
Procedimiento y aparato de compresión de
datos.
La presente invención se refiere a animación de
modelos gráficos de 3 dimensiones (3D), y más en particular a
aparatos para compresión y reconstrucción de una trayectoria de
animación, que se utiliza en animación, con utilización de
aproximación lineal, a los procedimientos de compresión y
reconstrucción utilizados en los aparatos, y a formatos de datos
para los aparatos y los procedimientos.
En animación por ordenador en 3D, se utilizan
interpoladores para expresar el movimiento y la rotación en el
espacio, la aplicación de morphing al modelo, los cambios de color,
etc, de un objeto modelo en 3D.
La Figura 1 es un diagrama para explicar una
trayectoria de animación en animación 3D ordinaria, y el eje
vertical representa valores clave (KEY_VALUE) y el eje horizontal
representa claves (KEY).
Según se muestra en la Figura 1, la trayectoria
20 de animación expresa la traza de animación de un modelo 10 en
3D. La trayectoria 20 de información de animación es una curva de 2
dimensiones que varía con respecto al tiempo, como se muestra en la
Figura 1. La trayectoria de animación puede ser representada
mediante una diversidad de métodos, los cuales se explican en el
Capítulo 9 de "Fundamentals of Digital Image Processings,
Fundamentos de Procesamiento Digital de Imágenes", de A. K. Jain,
publicado por Prentice Hall en 1989.
En una expresión que utiliza un interpolador, la
trayectoria 20 de animación que tiene forma de curva, según se
muestra en la Figura 1, puede ser representada mediante líneas
rectas definidas con la utilización de una pluralidad de segmentos.
La información esencial en esta expresión incluye puntos de ruptura
o vértices de cada segmento de línea recta definida. Aquí, los
puntos de ruptura o vértices se expresan como puntos sobre la
trayectoria 20 de animación de la Figura 1. Utilizando interpolación
lineal, la curva original puede ser reconstruida a partir de los
puntos de ruptura.
La Figura 2 es un ejemplo de expresión
(Interpolador Escalar) de una trayectoria de animación utilizada en
el Lenguaje de Modelación de Realidad Virtual (VRML) o
MPEG-4. La información que ha de ser procesada
incluye claves y valores de clave, y la interpolación lineal se
realiza utilizando una información dada.
Los interpoladores pueden dividirse
aproximadamente en 6 clases: interpoladores escalares,
interpoladores de posición, interpoladores de coordenadas,
interpoladores de orientación, interpoladores normales, e
interpoladores de color. Entre éstos, los interpoladores escalares
pueden ser expresados como se muestra en la Figura 2. Las
características y funciones de las 6 clases de interpoladores se
muestran en la tabla 1 que sigue, y todos los interpoladores son
conjuntos de claves dadas y de valores de clave correspondientes a
las claves.
La Figura 3 es un diagrama esquemático para
explicar un formato de datos de animación de 3D, y muestra un
codificador 30, un descodificador 40, y un formato 50 de archivo de
animación de 3D. En este caso, la salida de formato 50 de archivo
de animación de 3D desde el codificador 30 hasta el descodificador
40, se forma con datos de modelo, datos de animación, atributos,
video/textura, y sonido.
Con referencia a la Figura 3, un interpolador
corresponde a datos de animación que expresan eficazmente una
trayectoria de animación de 3D. Los datos de animación de 3D
expresados mediante el VRML o MPEG-4, se forman con
la información que se muestra en la Figura 4. Mientras que se
proporcionan tecnologías de compresión estandarizadas para el
audio, video y modelos 3D, solamente se proporcionan tecnologías de
compresión de propósito general de expresión orientada para el
interpolador, para la determinación de una trayectoria de animación.
En la animación que excluye el audio/video, la cantidad de datos
para las trayectorias de animación junto con los modelos 3D
adquieren la mayor parte de la cantidad de datos necesarios. Por lo
tanto, junto con la tecnología para la compresión de modelos 3D, la
tecnología para la compresión de trayectorias de animación resulta
esencial. Aunque el Formato Binario para Scene (BIFS)
MPEG-4 proporciona un método básico de
cuantificación/ compresión para animación, el método no es una
tecnología dedicada para los interpoladores, sino una tecnología de
compresión de propósito general y tiene un pobre rendimiento de
compresión. Esto se describe en Euee S. Jang: "3D Animation
Coding: its History and Framework", procedentes de la Conferencia
Internacional sobre multimedia y Expo celebradas en la ciudad de
Nueva York en 2000.
Las Figuras 4a y 4b son diagramas de bloques de
aparatos de compresión y de reconstrucción de trayectoria de
animación de la técnica anterior, respectivamente. El aparato de
compresión de la técnica anterior que aparece en la Figura 4a, ha
sido formado con una unidad 60 de cuantificación escalar, y el
aparato de reconstrucción de la técnica anterior de la Figura 4b
está formado por una unidad 70 de descuantificación escalar. Una
trayectoria original de animación se introduce en forma de (key,
key_value) a través de un terminal de entrada IN1 en la unidad 60
de cuantificación escalar de la Figura 4a, y constituye el escalar
cuantificado. Una corriente codificada de bits que es el resultado
de la cuantificación escalar, se emite a través de un terminal OUT1
de salida. La unidad 70 de descuantificación escalar de la Figura
40 recibe la corriente de bits codificada a través de un terminal
IN2 de entrada y emite datos en forma de trayectoria de animación
reconstruida (key, key_value) a través de un terminal OUT2 de
salida.
La compresión de interpolador en el
MPEG-4 BIFS de la técnica anterior, necesita
cuantificación escalar según se muestra en la Figura 4a. El proceso
de compresión de la técnica anterior mostrado en la Figura 4, se
aplica no sólo a interpoladores sino a todos los elementos que
necesiten compresión en los BIFS. En el orden inverso de la
compresión, una trayectoria de animación se reconstruye a través de
la unidad 70 de descuantificación escalar, utilizando la corriente
de datos codificada introducida en el aparato de reconstrucción de
la técnica anterior mostrado en la Figura 4b. En los aparatos de
las Figuras 4a y 4b, las claves y los valores de clave de los
interpoladores son comprimidos de manera uniforme, sin considerar
las características de cada clase, de modo que la compresión no
puede ser optimizada.
Bourges-Sevenier et al,
en "Animation Framework for MPEG-4 systems",
Multimedia y Expo 2000, ICME 2000, p 1115 a 1118, describe una
estructura de animación con una curva original interpolada
utilizando claves y valores de clave.
El documento EP 851684 describe la codificación
automática del contorno de un objeto, añadiendo vértices hasta que
la línea entre vértices se aproxima al contorno del objeto.
El documento WO 87/04032 describe un
procedimiento de transmisión de una señal de video en forma de
muestras utilizando un codificador de entropía.
De acuerdo con un primer aspecto de la
invención, se proporciona un aparato para comprimir una trayectoria
de animación según se define en la reivindicación 3, que posee una
unidad de análisis de interpolador para extraer un número
predeterminado de puntos de ruptura desde una trayectoria de
animación, y emitir claves y valores de clave correspondientes a
los puntos de ruptura; un codificador de claves para codificar las
claves que se emiten desde la unidad de análisis de interpolador;
un codificador de valores de clave para codificar valores de clave
emitidos desde la unidad de análisis de interpolador; y un
codificador de entropía para la codificación de entropía de las
claves y de los valores de clave que son codificados en el
codificador de claves y en el codificador de valores de clave,
respectivamente, y la emisión de corrientes de bits codificadas.
La presente invención puede proporcionar así un
aparato y un procedimiento para la compresión de una trayectoria de
animación utilizando aproximación lineal, en la que los datos de
animación en forma de interpolador, son comprimidos eficazmente de
modo que la transmisión y el almacenamiento de datos de realiza
rápidamente.
También, se proporciona un procedimiento para
comprimir una trayectoria de animación según se define en la
reivindicación 1.
También se proporciona un aparato para la
reconstrucción de la trayectoria de animación de acuerdo con la
reivindicación 9, y un procedimiento correspondiente de acuerdo con
la reivindicación 11.
Se prefiere que la diferencia de trayectoria se
exprese mediante la suma de las áreas de los trapezoides o de los
trapezoides alabeados que se forman mediante la trayectoria de
animación original y la trayectoria de animación aproximada.
Se prefiere que en un interpolador de
orientación, la diferencia de trayectoria se defina como el ángulo
de rotación diferencial en una transformación de rotación
diferencial, que es la diferencia entre una transformación de
rotación de la trayectoria de animación original y una
transformación de rotación de la trayectoria aproximada.
También, se proporciona un procedimiento de
reconstrucción de una trayectoria de animación que posee las etapas
de recepción y descodificación de entropía de una corriente de bits
codificada; descodificar claves y valores de clave a partir del
resultado de la descodificación de entropía; y reconstruir una
trayectoria de animación original mediante la obtención de valores
de clave vacíos mediante interpolación lineal en base a las claves
y a los valores de clave descodificados.
Una corriente de bits se puede obtener
codificando una trayectoria de animación, teniendo la corriente de
bits una banderola de clave para indicar valores de clave cuyos ejes
se eligen entre valores de clave correspondientes a una coordenada
x, y, o z de cada punto de ruptura de la trayectoria de animación;
una clave matricial para indicar que se elige al menos uno o más
valores de clave entre valores de clave correspondientes a una
coordenada x, y o z de cada punto de ruptura; y valores de clave
matriciales para indicar valores de clave elegidos para cada punto
de ruptura.
La presente invención proporciona también un
formato de datos para la compresión de datos de trayectoria de
animación.
Los objetos y ventajas anteriores de la presente
invención, se pondrán de manifiesto con la descripción en detalle
de realizaciones preferidas de la misma con referencia a los dibujos
anexos, en los que:
La Figura 1 es un diagrama para explicar una
trayectoria de animación en animación de 3 Dimensiones (3D)
ordinaria;
la Figura 2 es un ejemplo de una trayectoria de
animación utilizada en el Lenguaje de Modelación de Realidad
Virtual (VRML) o MPEG-4;
la Figura 3 es un diagrama esquemático para la
explicación de un formato de datos de animación 3D;
las Figuras 4a y 4b son diagramas de bloques de
aparatos de compresión y reconstrucción de trayectoria de animación
de la técnica anterior, respectivamente;
las Figuras 5a y 5b son diagramas de bloques de
aparatos de compresión y reconstrucción de trayectoria de animación
de acuerdo con la presente invención, respectivamente;
la Figura 6 es un diagrama de bloques de una
realización preferida del aparato de compresión conforme a la
presente invención, de la Figura 5a;
la Figura 7 es un diagrama de bloques de una
realización preferida del aparato conforme a la presente invención,
de la Figura 5b;
las Figuras 8a a 8h son diagramas para la
explicación de una realización preferida de extracción de puntos de
ruptura utilizando aproximación lineal de acuerdo con la presente
invención;
la Figura 9 es un diagrama para la explicación
de un método para la obtención de la diferencia entre una
trayectoria de animación real y una trayectoria de animación
aproximada;
la Figura 10 es un diagrama de un proceso de
cuantificación, y más en particular, de un método de codificación
de Modulación de Código de Pulso Diferencial (DPCM) que se utiliza
de forma general;
las Figuras 11a a 11e son diagramas que muestran
formatos de corriente de bits codificada de acuerdo con la presente
invención;
la Figura 12 es una tabla para explicar un
proceso de descodificación expresado en una expresión de sintaxis
de acuerdo con la presente invención;
las Figuras 13a a 13d son gráficos de secuencias
de animación experimentales para comparar el procedimiento de
compresión de la presente invención con el procedimiento de
compresión de la técnica anterior, y
las Figuras 14a a 14f son diagramas para la
explicación de otra realización preferida de extracción de puntos
de ruptura utilizando aproximación lineal esférica de acuerdo con la
presente invención.
En la descripción que sigue de la presente
invención, las expresiones de interpolador utilizadas son aquellas
que se utilizan en el VRML/MPEG-4, y los campos en
los que se utilizan los interpoladores incluyen los juegos de
ordenador en línea, los anuncios de animación, etc.
La Figura 5a es un diagrama de bloques para la
compresión de una trayectoria de animación de acuerdo con la
presente invención, incluyendo el aparato una unidad 80 de análisis
de interpolador, un codificador 82 de Claves (K), un codificador 84
de Valores de Clave (KV), y un codificador 86 de entropía. La
Figura 5b es un diagrama de bloques de un aparato para la
reconstrucción de una trayectoria de animación de acuerdo con la
presente invención, incluyendo el aparato un descodificador 90 de
entropía, un descodificador 92 de claves, un descodificador 94 de
valores de clave, y una unidad 96 de reconstrucción de
interpolador.
La unidad 80 de análisis de interpolador del
aparato de compresión de la Figura 5a elige las claves y los
valores de clave que han de ser codificados, y puede estar diseñada
en función de las características de diferentes tipos de
interpoladores. Un ejemplo de análisis detallado va a ser explicado
en lo que sigue.
La Figura 6 es un diagrama de bloques de una
realización preferida del aparato de compresión de acuerdo con la
invención, de la Figura 5a. El aparato de compresión de la Figura 6
incluye la unidad 80 de análisis de interpolador que tiene una
unidad 100 de normalización y una unidad 102 de minimización de
punto de ruptura, teniendo el codificador 82 de claves un
cuantificador 104 de Modulación de Código de Pulso Diferencial
(DPCM), teniendo el codificador 84 de valores de clave una unidad
106 de cuantificación DPCM, y el codificador 86 de entropía.
La Figura 7 es un diagrama de bloques de una
realización preferida del aparato de reconstrucción de acuerdo con
la presente invención, de la Figura 5b. El aparato de
reconstrucción incluye el descodificador 90 de entropía, el
descodificador 92 de claves que tiene un descuantificador 126 DPCM,
el descodificador 94 de valores de clave que tiene un
descuantificador 128 DPCM, y la unidad de reconstrucción de
interpolador que tiene una unidad 95 de reconstrucción de clave
& valor de clave.
La expresión de interpolador proporcionada a la
entrada de la unidad 80 de análisis de interpolador incluye claves
(K) y valores de clave (KV). En el aparato de compresión de la
Figura 6, la unidad 80 de análisis de interpolador ajusta el número
de puntos de ruptura de modo que una trayectoria de animación que es
introducida a través de un terminal IN3 de entrada, puede ser
expresada mediante un número mínimo de puntos de ruptura. Si el
número original de puntos de ruptura de la trayectoria de animación
es N, el número de puntos de ruptura emitido desde la unidad 80 de
análisis de interpolador se ajusta a M (M \leq N). Es decir, la
unidad 80 de análisis de interpolador extrae puntos de ruptura
desde la trayectoria de animación original introducida en el
terminal IN3 de entrada.
En un interpolador, una clave y valores de clave
pueden ser respectivamente normalizados y utilizados. Para esto, la
unidad de normalización 100 normaliza cada uno de clave y valores de
clave de la trayectoria de animación original que se introduce a
través del terminal IN3 de entrada, y emite resultados normalizados
para la unidad 102 de minimización de punto de ruptura. Una clave
soportada por el VRML tiene un valor entre 0 y 1 inclusive.
La forma en que la unidad 80 de análisis de
interpolador ajusta el número de puntos de ruptura, puede ser
determinada de modo que la diferencia de la trayectoria de animación
generada por los puntos de ruptura ajustados y la trayectoria de
animación original, se reduzca al mínimo. Para ello, la unidad 102
de minimización de punto de ruptura realiza puntos de ruptura
extraídos desde la clave y valores de clave normalizados, los cuales
se emiten desde la unidad 102 de normalización, de modo que el
número de puntos de ruptura extraídos se reduce al mínimo. Por
ejemplo, para un interpolador de posición, la unidad 102 de
minimización de puntos de ruptura determina los puntos de ruptura
de modo que el área que representa el error entre la trayectoria
real y la trayectoria cuantificada, que se determina mediante la
unidad 80 de análisis de interpolador, se reduce al mínimo.
Mientras tanto, se va a explicar ahora la
extracción de puntos de ruptura utilizando aproximación lineal,
llevada a cabo en la unidad 102 de minimización de punto de ruptura
de la Figura 6.
Las Figuras 8a a 8h son diagramas para la
explicación de una realización preferida de extracción de puntos de
ruptura utilizando aproximación lineal de acuerdo con la presente
invención. Cada punto de las trayectorias de animación representa
un punto de ruptura. La Figura 8a es la trayectoria de animación
original. La Figura 8b muestra un procedimiento para hallar ambos
puntos extremos (A, B) de la trayectoria. La Figura 8c muestra un
procedimiento para seleccionar un punto de ruptura que sea el más
cercano a la trayectoria original. La 8d muestra los puntos de
ruptura A, B y C que se seleccionan en primer lugar. La Figura 8e
muestra un procedimiento para extracción de los segundos puntos que
están cerca de la trayectoria original. La Figura 8f muestra puntos
de ruptura A, B, C y D, los cuales se seleccionan en segundo lugar.
La Figura 8g muestra puntos de ruptura A, B, C, D y E, los cuales
se eligen en tercer lugar. La Figura 8h muestra los puntos de
ruptura A, B, C, D, E y F que se eligen en cuarto lugar.
Cuando se da la trayectoria de animación
original como en la Figura 8a, se repite un procedimiento para
hallar puntos de ruptura (M puntos de ruptura, siendo 2 \leq M
\leq N) que representan una trayectoria aproximada que tiene la
diferencia más pequeña con la trayectoria original, entre puntos de
ruptura (N) de la trayectoria de animación original, tomando ambos
puntos A y B extremos como puntos de partida. Este procedimiento se
muestra en las Figuras 8b a 8h. En ese momento, la extracción de
puntos de ruptura puede ser repetida hasta que se determine que la
trayectoria de aproximación es suficientemente cercana a la
trayectoria original.
Con referencia a los dibujos anexos, se va a
explicar ahora un procedimiento que utiliza una diferencia de área
como método de obtención de la diferencia entre una trayectoria
aproximada y una trayectoria real.
La Figura 9 es diagrama para explicar un
procedimiento de obtención de la diferencia entre una trayectoria
de animación real y una trayectoria de animación aproximada. Con
referencia a la Figura 9, la diferencia entre las dos trayectorias
se expresa mediante un trapezoide o un trapezoide alabeado. La
ecuación 1 para obtención del área del trapezoide, y la ecuación 2
para la obtención del área del trapezoide alabeado, se proporcionan
a continuación. La diferencia entre la trayectoria 200 de animación
real y la trayectoria 210 de animación aproximada puede ser
expresada mediante la suma del área de los trapezoides y del área de
los trapezoides alabeados. La suma de las áreas es la diferencia de
área (D_{A}) entre las dos trayectorias según se muestra mediante
la ecuación 3.
(1)D_{trapezoide} =
\frac{(a+b)h}{2}
(2)D_{trapezoide\_alaberado} =
\frac{1}{2} \frac{(a^{2} + b^{2})}{(a + b)} \cdot
h
(3)D_{A} =
\sum\limits_{i} D_{trapezoide} + \sum\limits_{j}
D_{trapezoide\_alabeado}
Los puntos de ruptura se extraen de modo que la
diferencia de área (D_{A}) de la ecuación 3 se minimiza. De ese
modo, la unidad 102 de minimización de punto de ruptura extrae
puntos de ruptura. Pasando a través de la unidad 80 de análisis de
interpolador, se extraen puntos de ruptura esenciales de la
trayectoria de animación. Cuando se necesita un procesamiento sin
pérdidas, el número de puntos (M) de ruptura extraídos puede ser el
mismo que el número original de puntos de ruptura.
En un interpolador de posición, los valores
clave representan una posición en un espacio 3D que tiene ejes X, Y
y Z, y una trayectoria de animación viene representada por tres
curvas sobre los ejes X, Y y Z. La unidad 80 de análisis de
interpolador puede extraer puntos de ruptura en cada eje, y en ese
momento, los puntos de ruptura de cada eje pueden ser diferentes de
los correspondientes a los otros ejes. La tabla 2 que sigue muestra
el resultado de extraer nuevos puntos de ruptura en una unidad 80 de
análisis de interpolador desde una trayectoria real que tiene 8
puntos de ruptura (p0, p1, p2, p3, p4, p5, p6 y p7).
En la tabla 2, key_flag indica una banderola de
clave, y kv_{x}, kv_{y} y kv_{z} indican valores de clave
sobre los ejes X, Y y Z, respectivamente. "O" indica que se ha
elegido un valor de clave correspondiente a la coordenada x, y o z
de cada punto de ruptura. Por ejemplo, el valor de clave kv_{x} se
elige para el punto límite PO. "X" indica que no se ha elegido
un valor de clave correspondiente a un eje en cada punto de
ruptura. La banderola de clave indica los valores de clave cuyos
ejes se han elegido entre los valores de clave de los ejes X, Y, Z
en cada punto de ruptura. Por ejemplo, "7" indica que todos los
valores de clave de todos los ejes han sido seleccionados, y
"6" indica que todos los valores de clave, excluyendo el valor
de clave del eje X, kv_{x}, han sido seleccionados.
Según se muestra en la tabla 2, los puntos de
ruptura P1, P2 y P6 están referenciados como puntos de ruptura
innecesarios (marcados con "-" en el espacio key_flag) debido a
que ninguno de los valores de clave de los ejes X, Y, Z ha sido
seleccionado en los puntos de ruptura. P0 y P7 son puntos límite por
ambos extremos de la trayectoria, y los valores de clave de todos
los ejes han sido seleccionados. En P2, el valor de clave del eje X
no ha sido seleccionado, pero se han seleccionado valores de clave
en los otros ejes. Por lo tanto, la unidad 80 de análisis de
interpolador determina claves correspondientes a 5 puntos de
ruptura, en vez de los 8 puntos de ruptura originales, y determina
valores de clave de cada eje correspondientes a los puntos de
ruptura seleccionados. En la tabla 2, se necesitan 5 claves y 11
valores de clave. La relación correspondiente entre una clave y un
valor de clave puede estar representada por una banderola de clave
(key_flag), que es transmitida adicionalmente. De ese modo, el
número de claves y de valores de clave se reduce desde 32 en la
trayectoria real (4 x 8 = 32) hasta 16 claves y valores de clave,
más una banderola de clave adicional. Por lo tanto, se consigue la
simplificación de la expresión mediante el procedimiento.
Las Figuras 14a a 14f son diagramas para
explicar otra realización preferida de extracción de puntos de
ruptura utilizando aproximación lineal esférica de acuerdo con la
presente invención. Éstas muestran un procedimiento para reducir
los puntos de ruptura (también mencionados como estructura de clave)
en un interpolador de orientación.
La Figura 4a muestra valores de clave (=
Q_{0}, Q_{1}, Q_{2}, ..., Q_{n}) en cada punto de ruptura
con respecto a los n+1 puntos de tiempo sobre la trayectoria de
animación original, y los valores de clave han sido marcados
mediante puntos negros. Según se muestra en la Figura 14b, dos
puntos límite (=Q_{0}, Q_{n}) correspondientes a dos extremos
de la trayectoria de animación, son seleccionados en primer lugar.
Los puntos seleccionados se muestran como puntos blancos.
La Figura 14c muestra un procedimiento para
seleccionar un punto de ruptura (el tercer punto de ruptura) entre
los restantes puntos de ruptura excluyendo los dos puntos límite
extremos seleccionados. En este momento, el número de métodos para
seleccionar un punto de ruptura es (n-1). La Figura
14c muestra un ejemplo en el que se seleccionan dos candidatos
(=Q_{1}, Q_{k}). Para cada uno de los (n-1)
candidatos, con la utilización de los tres puntos de ruptura
seleccionados, la interpolación lineal esférica se lleva a cabo para
valores de clave de puntos de ruptura que no han sido
seleccionados. Comparando la trayectoria de animación original y
cada una de las (n-1) trayectorias de animación de
candidato obtenidas por interpolación, se selecciona una
trayectoria de animación de candidato que tenga la menor diferencia
de trayectoria. Un punto de ruptura correspondiente a la
trayectoria de animación de candidato seleccionada, se elige entre
los (n-1) puntos de ruptura de candidato. Como
ejemplo, la Figura 14d muestra que se elige la trayectoria de
candidato 2 de la Figura 1. El error entre trayectorias se obtiene
utilizando el error medio E_{m}.
Haciendo referencia a la Figura 14e, el cuarto
punto de ruptura se elige realizando el procedimiento explicado con
referencia a las Figuras 14c y 14d, y seleccionando a continuación
un punto de ruptura candidato entre los restantes puntos de ruptura
excluyendo los tres puntos de ruptura seleccionados de la Figura
14d. Por ejemplo, la Figura 14f muestra que se ha elegido el
candidato 1. Repitiendo el proceso de selección de punto de ruptura
de la Figura 14e hasta que el error medio sea menor que un error
permisible, se seleccionan los puntos de ruptura, cuyo número es el
mismo que, o menor que, el número de puntos de ruptura de la
trayectoria original.
El error medio E_{m}, el cual ha sido
mencionado en lo que antecede, va a ser explicado ahora. Se define
un error de cuantificación como un ángulo de rotación diferencial en
una transformación de rotación diferencial, que es la diferencia
entre la transformación de rotación de la trayectoria de animación
original y la de una trayectoria de animación reconstruida.
Es decir, suponiendo que (\overline{r}, \theta) indica un
valor de clave de un nodo de interpolador de orientación y
(\overline{r}', \theta') indica un valor de clave
reconstruida en la unidad 96 de reconstrucción (el vector r indica
un eje de rotación, \theta indica una cantidad de rotación, y la
cantidad de rotación satisface \theta \epsilon [-\pi, \pi]),
cuando se realiza la transformación de rotación desde una posición
arbitraria arbitraria de
rotación \overline{x} a \overline{y} e \overline{y'} en un
espacio 3D mediante (\overline{r}, \theta) y (\overline{r}',
\theta'), se calcula el error de cuantificación que se produce
como la diferencia entre \overline{y} e \overline{y'}. De
ese modo, si \overline{e}(\overline{x}) representa un
vector de error de cuantificación,
\overline{e}(\overline{x}) = \overline{y} –
\overline{y'}. En expresión de cuaternio, X, Y e Y' se definen
como en la ecuación 4 que sigue:
Si Q y Q' indican expresiones cuaternio de
(\overline{r}, \theta) y de (\overline{r}', \theta'),
respectivamente, que representan la transformación de rotación, se
derivan las ecuaciones 5 que siguen:
Y = Q * X *
Q'
(5)X = Q' * Y *
Q
En este caso, A*B indica multiplicación
cuaternio de A y B, y A^{\text{*}} indica el conjugado de A. Por
lo tanto, se deriva la ecuación 6 que sigue:
(6)Y' =
Q'*X*Q'^{\text{*}} = Q'*Q^{\text{*}}*Y*Q*Q'^{\text{*}} =
Q''*Y*Q''^{\text{*}}
Aquí, Q'' es un valor para
indicar la relación de transformación rotacional entre
\overline{y} e \overline{y'}, y se define mediante la ecuación 7
que sigue:
(7)Q'' = Q' *
Q^{\text{*}}
Por lo tanto, si \theta'' indica un
ángulo de rotación diferencial entre \overline{y} e
\overline{y'}, \theta'' puede ser obtenido utilizando una
ecuación de conversión de cuaternio y la ecuación 7, como se muestra
en la ecuación 8 que sigue:
(8)\theta'' =
2cos^{-1}q_{0}'' = 2cos^{-1}(Q'\text{*}Q), \theta'' \epsilon
[0,\pi], q_{0}'' =
Q'\text{*}Q,
(* indica una operación de producto
interior)
\newpage
La ecuación 8 indica un error de cuantificación
instantáneo que se produce en un determinado momento entre todos
los puntos de ruptura de animación. Con el fin de derivar una
ecuación para obtener un error de cuantificación de todos los
intervalos de animación, un error de cuantificación instantánea en
un instante t determinado, puede ser expresado como la ecuación 9
que sigue:
(9)E(t)
=
2arcos(Q(t)*Q'(t))
Si la ecuación 9 se aplica a todos los
intervalos de punto de ruptura de la animación mediante los
interpoladores de orientación, el error E_{m} medio y el error
E_{p} máximo para la totalidad del intervalo [t_{0}, t_{L}]
puede ser derivado como las ecuaciones 10 que siguen:
Aquí, la suma parcial E^{j}_{m} se obtiene
primero para el intervalo [t_{j-1}, t_{j}] con
el fin de obtener E_{m}, utilizando la ecuación 11 que sigue:
(11)E_{m}{}^{i} =
\int_{-1}e^{2}(t)dt = 4\int_{-1}
arcos^{2}(Q(t)\text{*}Q'(t))dt
Mientras tanto, se deriva también la ecuación 12
que sigue:
(12)4arccos^{2}(Q(t)\text{*}Q'(t))
= \phi^{2}(\alpha), t = t_{i+1} +\alpha(t_{i} -
t_{i-1})
Por lo tanto, se deriva la ecuación 13 que
sigue:
(13)E'_{m} =
(t_{i} - t_{i-1})\int^{1}_{0}
\phi^{2}(\alpha)d\alpha
Debido a que es difícil obtener la integral
definida de la función \phi^{2}(\alpha) entre 0 y 1, la
aproximación se realiza según se muestra en las ecuaciones 14 que
siguen:
(14)\phi(\alpha) \cong
\phi(0) + \alpha(\phi(1) - \phi(0))
\phi^{2}(\alpha) \cong \phi^{2}(0) + \alpha^{2}(\phi(1) -
\phi(0))^{2} + 2\alpha\phi(0)(\phi(1) -
\phi(0))
Aquí,
(15)Cos
\frac{\phi(0)}{2} =
Q(t_{i-1})\text{*}Q'(t_{i-1}),
cos \frac{\phi(1)}{2} =
Q(t_{i})\text{*}Q'(t_{i})
Utilizando la función de aproximación 14, la
suma parcial E^{j}_{m} se obtiene como la ecuación 16 que
sigue:
(16)E^{j}{}_{m} \cong
\frac{1}{3}(t_{i} - t_{i-1})(\phi^{2}(0) +
\phi^{2}(1) +
\phi(0)\phi(1))
Estas ecuaciones pueden ser reorganizadas del
modo de la ecuación 17 que sigue:
(17)E^{j}{}_{m} \cong
\frac{4}{3}(t_{i} -
t_{i-1})(arccos^{2}(Q(t_{i-1})\text{*}Q'(t_{i-1}))
+ arccos^{2}(Qt_{i})\text{*}Q'(t_{i})) +
arccos(Q(t_{i-1})\text{*}Q'(t_{i-1}))arccos(Q(t_{i})\text{*}Q'(t_{i})))\hskip3cm
\newpage
La suma parcial E'_{m} se suma en el intervalo
completo [t_{0}, t_{L}] para obtener el error medio E_{m}
según se muestra en la ecuación 18 que sigue:
(18)E_{m}
\cong \sqrt{\frac{1}{t_{L} - t_{0}} \sum\limits^{L}_{i=0}
E^{j}{}_{m}}
Para obtener el error máximo E_{p}, se elige
un valor máximo entre los valores del error máximo E_{p}' en cada
intervalo [t_{j-1}, t_{j}], el cual se obtiene
mediante la siguiente ecuación 19:
(19)E^{j}{}_{p} \cong
máx|e(t)| =
máx2|arccos(Q(t)\text{*}Q'(t))|
Utilizando la función de aproximación descrita
anteriormente, E_{p}' puede ser aproximado como se muestra en la
ecuación 20 que sigue:
(20)E^{j}{}_{p} \cong
máx(\phi(0), \phi(1)) =
máx\{2|arccos(Q(t_{i-1})\text{*}Q'(t_{i-1}))|,
2|arccos(Q(t_{i})\text{*}Q'(t_{i}))|\}
El error máximo E_{p} en el intervalo completo
[t_{0}, t_{L}] se expresa mediante la ecuación 21 que sigue:
(21)E_{p}
\cong máx E^{j}_{p}, para i = 1, 2, ...,
L
La unidad 80 de análisis de interpolador
mostrada en la Figura 6, envía información 114 sobre el número de
claves, el valor mínimo y el valor máximo de los valores de clave
normalizados, las resoluciones de clave y de valor de clave, y la
banderola de clave, hasta el codificador 86 de entropía. En ese
momento, la unidad 80 de análisis de interpolador envía claves 110
hasta el codificador 82 de clave, y envía información sobre los
valores de clave, incluyendo el valor mínimo y el valor máximo de
los valores de clave normalizados hasta el codificador 84 de valor
de clave.
Ahora se va a explicar la codificación de claves
y de valores de clave en el codificador 82 de clave y en el
codificador 84 de valor de clave. Las claves y los valores de clave
son métodos de cuantificación DPCM comprimidos en el codificador 82
de clave y en el codificador 84 de valor de clave, respectivamente.
La información cuantificada, junto con otras informaciones, se
envía al codificador 86 de entropía, y la salida como compresión
finalmente de corriente de bits es codificada a través del terminal
de salida OUT3. Por ejemplo, el cuantificador 104 DPCM del
codificador 82 de clave, codifica en cuantificación DPCM (es decir,
codifica la diferencia entre el valor actual y el valor
inmediatamente anterior) una clave enviada desde la unidad 80 de
análisis de interpolador, y emite el resultado codificado para el
codificador 86 de entropía. En ese momento, el cuantificador 106
DPCM del codificador 84 de valor de clave, codifica en
cuantificación DPCM (es decir, codifica la diferencia entre el
valor actual y el valor inmediatamente anterior) los valores de
clave, y el valor mínimo y el valor máximo de los valores de clave,
los cuales son enviados por la unidad 80 de análisis de
interpolador, y emite el resultado codificado para el codificador
86 de entropía.
La Figura 10 es un diagrama de un procedimiento
de cuantificación, y muestra el método DPCM que se utiliza en
general. Con referencia a la Figura 10, en el caso de la clave (k),
un error final (e) se comprime en cuantificación conforme a la
ecuación 22 que sigue. La Figura 10 explica la ecuación 22. Es
decir, se obtiene la diferencia (d1) entre un valor inmediatamente
anterior (K_{i-1}) y el valor anterior
(K_{i-2}) anterior del mismo. El valor (d1) de
diferencia, se añade al valor (K_{i-1})
inmediatamente anterior para generar un valor (\hat{K}_{i})
aproximado. A continuación, el error final (e) se obtiene como la
diferencia entre el valor aproximado (\hat{K}_{i}) y el valor
actual (K_{i}). Mientras tanto, el error (e) puede ser obtenido
simplemente como la diferencia entre el valor actual (K_{i}) y el
valor (K_{i-1}) inmediatamente anterior.
- \quad
- K_{i} = 0, para i<0
- \quad
- d1 = K_{i-1} – K_{i-2},
- \quad
- K_{i} = K_{i-1} + dl,
- \quad
- d2 = K_{i} – \hat{K}_{i},
- e = d2
- (22)
Las Figuras 11a a 11e son diagramas que muestran
formatos de corrientes de bits codificadas de acuerdo con la
presente invención. La Figura 11a muestra el formato de una
corriente de bits codificada de acuerdo con la presente invención,
la cual incluye el número de claves (n_key), la resolución de claves
(k_res), la resolución de valores de clave (kv_res), el valor
mínimo y el valor máximo de la matriz de valores 230 de clave
([min/max]), una matriz 232 de banderola de clave ([key_flag]), y
una matriz 236 de valores de clave ([kv]). Aquí, [] indica una
matriz. La Figura 11b muestra el formato del valor mínimo y del
valor máximo de la matriz 230 de valores de clave de la Figura 11a.
La Figura 11c muestra el formato de la matriz 232 de banderola de
clave, la Figura 11d muestra el formato de la matriz 234 de clave,
y la Figura 11e muestra el formato de la matriz 236 de valores de
clave.
El valor mínimo y el valor máximo de la matriz
230 de valores de clave de la Figura 11a, se forman con los valores
mínimos de los ejes X, Y y Z (min_{x}, min_{y}, min_{z}), y
con los valores máximos de los ejes X, Y y Z (max_{x}, max_{y},
max_{z}), según se muestra en la Figura 11b. La matriz 232 de
banderola de clave se forma con n banderolas de clave
(key_flag_{0}, key_flag_{1}, key_flag_{2}, key_flag_{3},
..., key_flag_{n-1}). Aquí, n indica el número de
claves. La matriz 234 de clave se forma con n claves (key_{0},
key_{1}, key_{2}, ..., key_{n-1}). Aquí, los
datos de las claves y de las banderolas de clave para los puntos de
ruptura que se conceptúen como innecesarios, por ejemplo, los puntos
de ruptura P1, P3 y P6 de la Tabla 2, pueden ser excluidos de la
matriz de clave o de la matriz de banderola de clave. De ese modo,
la matiz de clave y/o la matriz de banderola de clave pueden
consistir en menos datos que el número (n) de claves originales. La
matriz 236 de valores de clave se forma con p primeros valores de
clave (kv_X_{0}, kv_X_{1}, ..., kv_X_{p-1}),
q segundos valores de clave (kv_Y_{0}, kv_Y_{1}, ...,
kv_Y_{q-1}), y r terceros valores de clave
(kv_Z_{0}, kv_Z_{1}, ..., kv_Z_{r-1}). Aquí,
p\leqn, q\leqn, y r\leqn.
Mientras tanto, el aparato y el procedimiento
para la reconstrucción de una trayectoria de animación de acuerdo
con la presente invención se realizan como la inversa del proceso de
compresión. El descodificador 90 de entropía de la Figura 7 recibe
una corriente de bits codificada a través del terminal de entrada
IN4, descodifica en entropía la corriente de bits, y emite el
resultado descodificado de entropía tanto para el descodificador 92
de clave como para el descodificador 94 de valor de clave. El
descodificador 92 de clave y el descodificador 94 de valor de clave
reciben claves y valores de clave cuantificados, respectivamente,
los cuales son el resultado de la descodificación de entropía y,
utilizando información adicional tal como la banderola de clave,
reconstruyen los datos con anterioridad a la cuantificación. Es
decir, el descodificador 92 de clave recibe el resultado
descodificado de entropía, y descodifica las claves, y el
descodificador 94 de valor de clave recibe el resultado
descodificado de entropía, y descodifica los valores de clave. Para
esto, el descodificador 92 de clave puede ser implementado como
descuantificador 126 DPCM, y el descodificador 94 de valor de clave
puede ser implementado como descuantificador 128 DPCM. Cada
descuantificador 126 ó 128 DPCM descodifica los datos de entrada que
son descodificados en el descodificador 90 de entropía por medio
del procedimiento de descuantificación DPCM.
La unidad 96 de reconstrucción de interpolador
recibe los datos descodificados en el descodificador 92 de clave y
en el descodificador 92 de valor de clave, y reconstruye la
trayectoria de animación original. La unidad 96 de reconstrucción
de interpolador recibe información 124 sobre el número de claves, el
valor mínimo y el valor máximo de valores de clave normalizados,
las resoluciones de las claves y de los valores de clave, y las
banderolas de clave, desde el descodificador 90 de entropía, las
claves 120 desde el descodificador 92 de clave, e información 122
sobre los valores de clave y el valor mínimo y el valor máximo de
valores de clave normalizados desde el descodificador 94 de valor
de clave. La unidad 94 de reconstrucción de interpolador
reconstruye valores de clave vacíos mediante interpolación lineal,
utilizando información de entrada. Por ejemplo, en la tabla 2, el
valor de clave del eje X en el punto P2 de ruptura puede ser
reconstruido por interpolación lineal, utilizando valores de clave
de P0 y P4. Para esto, la unidad 96 de reconstrucción de
interpolador puede ser implementada como unidad 96 de
reconstrucción de clave & valor de clave. La trayectoria de
animación reconstruida en forma de (clave, valores de clave), se
emite a través del terminal de salida OUT4.
La Figura 12 es una tabla para explicar un
procedimiento de descodificación expresado en un lenguaje de
programa de acuerdo con la presente invención. La tabla se menciona
también como sintaxis de corriente de bits.
Con referencia a los dibujos anexos, el
procedimiento para la compresión de una trayectoria de animación
utilizando aproximación lineal de acuerdo con la presente
invención, va a ser comparado ahora con el procedimiento de la
técnica anterior para la compresión de interpolador utilizando el
BIFS MPEG-4.
Las Figuras 13a a 13d son gráficos de secuencias
de animación experimentales para la comparación del procedimiento
de compresión de la presente invención con el procedimiento de
compresión de la técnica anterior. El eje vertical representa
grados de distorsión, el eje horizontal representa el número de
bits, el procedimiento para la compresión de una trayectoria de
animación de acuerdo con la presente invención ha sido marcado con
líneas gruesas, y el procedimiento de compresión de la técnica
anterior ha sido marcado con líneas de puntos. Las Figuras 13a a
13d muestran los resultados de simulaciones, en cada una de las
cuales se aplica una trayectoria de animación diferente. El
procedimiento de la presente invención muestra crecientemente
mejores resultados en el orden de las Figuras
13b - 13a - 13d - 13c. A las mismas velocidades de bits, el procedimiento de compresión de la presente invención mostró una calidad de imagen mucho mejor que el procedimiento BIFS de la técnica anterior, mientras que a la misma calidad de imagen, el procedimiento de compresión de la presente invención mostró una velocidad de compresión mucho mejor.
13b - 13a - 13d - 13c. A las mismas velocidades de bits, el procedimiento de compresión de la presente invención mostró una calidad de imagen mucho mejor que el procedimiento BIFS de la técnica anterior, mientras que a la misma calidad de imagen, el procedimiento de compresión de la presente invención mostró una velocidad de compresión mucho mejor.
Según se ha descrito en lo que antecede, la
expresión de interpolador de una trayectoria de animación se utiliza
para la simplificación de la trayectoria utilizando puntos de
ruptura. Sin embargo, en el procedimiento de la técnica anterior,
el intervalo entre cada clave se forma uniformemente en la expresión
de la trayectoria, y por lo tanto, los puntos de ruptura son
re-muestreados. Sin embargo, en la presente
invención, analizando los puntos de ruptura, se obtiene una
corriente de bits codificada simplificada, que tiene un número
mínimo de puntos de ruptura. La compresión DPCM mantiene una
correlación lineal más alta entre puntos de ruptura, y por lo
tanto, se permite una compresión eficaz utilizando la correlación
más alta.
Claims (12)
1. Un procedimiento para comprimir una
trayectoria de animación en 3D, que comprende las etapas de:
(a) seleccionar dos puntos de ruptura en ambos
puntos extremos entre los puntos de ruptura de la trayectoria de
animación;
(b) seleccionar un punto de ruptura entre los
restantes puntos de ruptura excluyendo los dos puntos de ruptura
seleccionados;
(c) interpolar valores de clave de los restantes
puntos de ruptura con exclusión de los puntos de ruptura
seleccionados, utilizando los puntos de ruptura seleccionados;
(d) formar una trayectoria aproximada en base a
los puntos de ruptura seleccionados y a los valores de clave
interpolados, seleccionando una trayectoria de animación aproximada
que tenga la diferencia más pequeña entre la trayectoria de
animación original y la trayectoria de animación aproximada, y
seleccionar puntos de ruptura correspondientes a la trayectoria de
animación seleccionada, y
(e) seleccionar un punto de ruptura entre los
restantes puntos de ruptura excluyendo los puntos de ruptura
seleccionados en las etapas (a) y (b), y repetir las etapas (c) a
(e) hasta que la diferencia de trayectoria sea menor que una
diferencia permisible,
en el que las etapas (a) a (e) se repiten para
cada uno de los tres ejes, y los puntos de ruptura en cada eje son
diferentes de aquellos de los otros ejes;
comprendiendo además el procedimiento registrar
una banderola de clave para cada punto de ruptura que indica
información sobre cuál de los tres ejes ha sido elegido para el
valor de clave del punto de ruptura.
2. El procedimiento de la reivindicación 1, en
el que la diferencia se expresa mediante la suma de las áreas de
los trapezoides o de los trapezoides alabeados que se forman
mediante la trayectoria de animación original y la trayectoria de
animación aproximada.
3. Un aparato para comprimir una trayectoria de
animación en 3D, que comprende:
una unidad (80) de análisis de interpolador para
extraer un número de puntos de ruptura de una trayectoria de
animación y emitir claves y valores de clave correspondientes a los
puntos de ruptura;
un codificador (82) de claves para codificar
claves emitidas desde la unidad de análisis de interpolador;
un codificador (84) de valor de claves para
codificar valores de claves emitidos desde la unidad de análisis de
interpolador, y
un codificador (86) de entropía para codificar
en entropía las claves y los valores de clave que son codificados
en el codificador de claves y en el codificador de valores de clave,
respectivamente, y emitir corrientes de bits codificadas,
en el que la unidad (80) de análisis de
interpolador está dispuesta para extraer ambos puntos extremos de
la trayectoria de animación original como puntos límite de partida,
para extraer puntos de ruptura que representan una trayectoria
aproximada que tiene la diferencia más pequeña respecto a la
trayectoria de animación original, entre los puntos de ruptura de
la trayectoria de animación original, y repetir este procedimiento
hasta que la trayectoria aproximada sea cercana a la trayectoria de
animación original;
en el que la unidad (80) de análisis de
interpolador está dispuesta para extraer puntos de ruptura en cada
uno de los tres ejes de modo que los puntos de ruptura de cada eje
son diferentes de aquellos de los otros ejes, y para registrar una
banderola de clave para cada punto de ruptura que indica información
sobre cuál de los tres ejes ha sido elegido para el valor de clave
del punto de ruptura.
4. El aparato de la reivindicación 3, en el que
la unidad (80) de análisis de interpolador determina el número de
puntos de ruptura de modo que la diferencia entre una trayectoria de
animación aproximada, que se obtiene mediante el número
predeterminado de puntos de ruptura extraídos entre los puntos de
ruptura de la trayectoria de animación original, y la trayectoria
de animación original, es mínima.
5. El aparato de la reivindicación 3, en el que
el codificador (82) de claves está dispuesto para codificar las
claves que salen de la unidad de análisis de interpolador mediante
el método de cuantificación de Modulación de Código de Pulso
Diferencial (DPCM).
\newpage
6. El aparato de la reivindicación 3, en el que
el codificador (84) de valor de clave está dispuesto para codificar
los valores de clave emitidos desde la unidad de análisis de
interpolador mediante el método de cuantificación de Modulación de
Código de Pulso Diferencial (DPCM).
7. El aparato de la reivindicación 4, en el que
los puntos de ruptura se determinan de modo que la diferencia de
áreas entre la trayectoria de animación original y la trayectoria de
animación aproximada, es la más pequeña.
8. El aparato de la reivindicación 5 ó 6, en el
que la cuantificación DPCM codifica la diferencia entre un valor
actual y el valor previo inmediato, o codifica la diferencia entre
un valor actual y un valor aproximado que se obtiene mediante la
adición del valor inmediatamente anterior a la diferencia entre el
valor inmediatamente anterior y el valor previo del mismo.
9. Un aparato para reconstruir una trayectoria
de animación en 3D, que comprende:
un descodificador (90) de entropía para recibir
una corriente de bits en la que están codificados en entropía las
claves, los valores de clave y las banderolas de clave para los
puntos de ruptura sobre los tres ejes, en el que los puntos de
ruptura sobre cada eje son diferentes de aquellos de los otros ejes,
y la banderola de clave para cada punto de ruptura indica
información sobre cuál de los tres ejes ha sido elegido para el
valor de clave del punto de ruptura, y descodificar en entropía la
corriente de bits;
un descodificador (92) de claves para recibir el
resultado descodificado de entropía y descodificar las claves;
un descodificador (94) de valor de clave para
recibir el resultado descodificado de entropía, y descodificar los
valores de clave, y
una unidad (96) de reconstrucción de
interpolador para identificar los valores clave vacíos en base a las
banderolas de clave, obteniendo los valores clave vacíos por
interpolación lineal en base a las claves y a los valores clave
descodificados en el descodificador de claves y en el descodificador
de valores de clave, respectivamente, y reconstruir la trayectoria
de animación en forma de claves y de valores clave para los puntos
de ruptura.
10. El aparato de la reivindicación 9, en el que
el descodificador (92) de claves descodifica el resultado
descodificado de entropía que proviene del descodificador de
entropía por medio del método de descuantificación DPCM.
11. El aparato de la reivindicación 9, en el que
el descodificador (94) de valores de clave descodifica el resultado
descodificado de entropía que proviene del descodificador de
entropía mediante el método de descuantificación DPCM.
12. Un procedimiento para la reconstrucción de
una trayectoria de animación en 3D, que comprende las etapas
de.
recibir una corriente de bits en la que las
claves, los valores de clave y las banderolas de clave para los
puntos de ruptura sobre los tres ejes, están codificados en
entropía, en el que los puntos de ruptura sobre cada eje son
diferentes de aquellos de los otros ejes, y la banderola de clave
para cada punto de ruptura indica información sobre cuál de los
tres ejes ha sido seleccionado para el valor de clave del punto de
ruptura y para la descodificación en entropía de la corriente de
bits;
descodificar las claves y los valores de clave a
partir del resultado de la descodificación de entropía, e
identificar los valores de clave vacíos en base
a las banderolas de clave, y obtener los valores de clave vacíos
mediante interpolación lineal en base a las claves y a los valores
de clave descodificados, para reconstruir la trayectoria de
animación en forma de claves y de valores de clave para los puntos
de ruptura.
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR10-2000-0070090 | 2000-11-23 | ||
| KR20000070090 | 2000-11-23 | ||
| KR1020010040704A KR100561835B1 (ko) | 2000-11-23 | 2001-07-07 | 선형 근사화를 이용한 애니메이션 궤적의 압축 및 복원 방법, 이 방법을 수행하는 장치 |
| KR10-2001-0040704 | 2001-07-07 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2282209T3 true ES2282209T3 (es) | 2007-10-16 |
Family
ID=36648539
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES01309832T Expired - Lifetime ES2282209T3 (es) | 2000-11-23 | 2001-11-22 | Procedimiento y aparato de compresion de datos. |
Country Status (8)
| Country | Link |
|---|---|
| US (1) | US7006097B2 (es) |
| EP (1) | EP1209626B1 (es) |
| JP (1) | JP3694477B2 (es) |
| CN (1) | CN1215440C (es) |
| CA (1) | CA2363385C (es) |
| DE (1) | DE60126895T2 (es) |
| ES (1) | ES2282209T3 (es) |
| RU (1) | RU2236751C2 (es) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7809203B2 (en) * | 2001-11-27 | 2010-10-05 | Samsung Electronics Co., Ltd. | Apparatus for encoding and decoding key data and key value data of coordinate interpolator and recording medium containing bitstream into which coordinate interpolator is encoded |
| US7809204B2 (en) * | 2002-10-18 | 2010-10-05 | Samsung Electronics Co., Ltd. | Method and apparatus for encoding and decoding key value data of coordinate interpolator |
| DE502004006411D1 (de) * | 2003-02-27 | 2008-04-17 | T Mobile Deutschland Gmbh | Verfahren zur komprimierten übertragung von bilddaten für eine 3-dimensionale darstellung von szenen und objekten |
| US20050168485A1 (en) * | 2004-01-29 | 2005-08-04 | Nattress Thomas G. | System for combining a sequence of images with computer-generated 3D graphics |
| US8243078B2 (en) * | 2005-02-28 | 2012-08-14 | Kenneth Perlin | Method and apparatus for creating a computer simulation of an actor |
| US7653528B2 (en) * | 2005-03-08 | 2010-01-26 | Microsoft Corporation | Resource authoring incorporating ontology |
| US20060274070A1 (en) * | 2005-04-19 | 2006-12-07 | Herman Daniel L | Techniques and workflows for computer graphics animation system |
| US7477254B2 (en) * | 2005-07-13 | 2009-01-13 | Microsoft Corporation | Smooth transitions between animations |
| US11408572B2 (en) | 2014-03-15 | 2022-08-09 | Ideal Industries Lighting Llc | Luminaires utilizing optical waveguide |
| CA2980169A1 (en) | 2016-09-26 | 2018-03-26 | Norman R. Byrne | Cord system for height-adjustable furniture |
| CN111343462B (zh) * | 2020-03-08 | 2021-10-22 | 苏州浪潮智能科技有限公司 | 一种图像数据压缩传输方法、装置及存储介质 |
Family Cites Families (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1987004032A1 (en) | 1985-12-24 | 1987-07-02 | British Broadcasting Corporation | Method of transmitting a video signal in sampled form |
| JP3250841B2 (ja) | 1992-06-12 | 2002-01-28 | 新日鉄ソリューションズ株式会社 | 図形データの処理方法及び装置 |
| FR2697360B1 (fr) * | 1992-10-26 | 1994-12-30 | Jeux Franc | Système d'acquisition et de restitution d'une séquence d'images vidéo animée en temps réel. |
| KR100363588B1 (ko) * | 1993-03-25 | 2003-02-17 | 세이코 엡슨 가부시키가이샤 | 화상처리장치 |
| JP3038143B2 (ja) | 1994-12-29 | 2000-05-08 | 現代電子産業株式会社 | 映像機器の物体別形状情報の減縮装置及びその減縮方法並びに多角近似化方法 |
| JP3597583B2 (ja) | 1995-02-03 | 2004-12-08 | 富士通株式会社 | アニメーションパス作成装置 |
| KR970064261A (ko) | 1996-02-09 | 1997-09-12 | 모리시타 요우이치 | 윤곽 부호화 방법, 윤곽 복호화 방법, 및 그의 방법을 이용한 윤곽 부호화 장치, 윤곽 복호화 장치 및 그의 방법을 기록한 기록 매체 |
| US5909218A (en) | 1996-04-25 | 1999-06-01 | Matsushita Electric Industrial Co., Ltd. | Transmitter-receiver of three-dimensional skeleton structure motions and method thereof |
| KR100212552B1 (ko) | 1996-12-23 | 1999-08-02 | 전주범 | 이산적 사인 변환을 이용한 윤곽선 영상 신호 부호화 방법 및 그 장치 |
| US6034697A (en) * | 1997-01-13 | 2000-03-07 | Silicon Graphics, Inc. | Interpolation between relational tables for purposes of animating a data visualization |
| TW388843B (en) | 1997-04-24 | 2000-05-01 | Mitsubishi Electric Corp | Moving image encoding method, moving image encoder and moving image decoder |
| US6028608A (en) * | 1997-05-09 | 2000-02-22 | Jenkins; Barry | System and method of perception-based image generation and encoding |
| EP1086412A4 (en) | 1998-06-08 | 2008-05-07 | Microsoft Corp | COMPRESSION OF TIME-DEPENDENT GEOMETRY |
| JP3428513B2 (ja) | 1998-07-17 | 2003-07-22 | 松下電器産業株式会社 | 多次元ストリームデータを用いた、送信装置、送信方法、受信装置、受信方法および通信システム |
| WO2001055971A1 (en) * | 2000-01-31 | 2001-08-02 | Ivast, Inc. | Textual format for animation in multimedia systems |
| US6559848B2 (en) * | 2000-12-13 | 2003-05-06 | Intel Corporation | Coding and decoding three-dimensional data |
-
2001
- 2001-11-20 US US09/988,708 patent/US7006097B2/en not_active Expired - Fee Related
- 2001-11-21 CA CA 2363385 patent/CA2363385C/en not_active Expired - Fee Related
- 2001-11-22 DE DE2001626895 patent/DE60126895T2/de not_active Expired - Lifetime
- 2001-11-22 RU RU2001131591A patent/RU2236751C2/ru not_active IP Right Cessation
- 2001-11-22 ES ES01309832T patent/ES2282209T3/es not_active Expired - Lifetime
- 2001-11-22 EP EP20010309832 patent/EP1209626B1/en not_active Expired - Lifetime
- 2001-11-22 JP JP2001357514A patent/JP3694477B2/ja not_active Expired - Fee Related
- 2001-11-23 CN CNB011394234A patent/CN1215440C/zh not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN1356669A (zh) | 2002-07-03 |
| US7006097B2 (en) | 2006-02-28 |
| CA2363385A1 (en) | 2002-05-23 |
| DE60126895D1 (de) | 2007-04-12 |
| RU2236751C2 (ru) | 2004-09-20 |
| EP1209626B1 (en) | 2007-02-28 |
| DE60126895T2 (de) | 2007-11-08 |
| JP3694477B2 (ja) | 2005-09-14 |
| CN1215440C (zh) | 2005-08-17 |
| EP1209626A2 (en) | 2002-05-29 |
| US20020097246A1 (en) | 2002-07-25 |
| EP1209626A3 (en) | 2003-11-12 |
| JP2002230581A (ja) | 2002-08-16 |
| CA2363385C (en) | 2006-07-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4759284B2 (ja) | ３次元体積データの符号化／復号化方法及び装置 | |
| JP4166679B2 (ja) | ３次元オブジェクトデータの符号化及び復号化方法、並びに、その装置 | |
| KR100513732B1 (ko) | 3차원 객체 데이터 부호화 및 복호화 방법 및 장치 | |
| ES2374064T3 (es) | Estructura de nodos para representar objetos tridimensionales usando imágenes con profundidad. | |
| EP1321893B1 (en) | Node structure for representing 3-dimensional objects using depth image | |
| JP3884509B2 (ja) | 圧縮された幾何学形状三次元グラフィックス・データの圧縮解除のための方法及び装置 | |
| EP1321894B1 (en) | Apparatus and method for representing 3-dimensional objects using depth images | |
| EP0957450B1 (en) | Data compression and decompression system and method | |
| KR100554805B1 (ko) | 이미지 압축 시스템 및 방법 | |
| ES2284787T3 (es) | Procedimiento y equipo de codificacion de informacion de un objeto en 3d. | |
| KR101334173B1 (ko) | 그래픽 데이터 부호화 및 복호화 방법과 장치 | |
| ES2282209T3 (es) | Procedimiento y aparato de compresion de datos. | |
| US12587681B2 (en) | Point cloud data frames compression | |
| JP3592168B2 (ja) | 画像データの符号化復号化方法及び装置 | |
| JP2004272590A (ja) | データ符号化装置及びデータ符号化方法、並びにコンピュータ・プログラム | |
| CN119678187A (zh) | 用于编码和解码3d点云的方法、编码器及解码器 | |
| KR20020040538A (ko) | 선형 근사화를 이용한 애니메이션 궤적의 압축 및 복원방법들, 이 방법들을 수행하는 장치들 및 이를 위한데이타 포맷 | |
| CN119605179A (zh) | 用于编码及解码3d点云的方法、编码器及解码器 | |
| TW202545198A (zh) | 八叉樹資訊的編碼及解碼 | |
| CN117897732A (zh) | 网格面元句法 | |
| CN120266163A (zh) | 用于编码和解码3d点云的方法、编码器及解码器 |