MXPA05012403A

MXPA05012403A - Transformacion reversible para compresion de datos 2-d con perdida y sin perdida.

Info

Publication number: MXPA05012403A
Application number: MXPA05012403A
Authority: MX
Inventors: Sridhar Srinivasan
Original assignee: Microsoft Corp
Priority date: 2004-12-17
Filing date: 2005-11-17
Publication date: 2006-06-19
Also published as: BRPI0506084B1; RU2413983C2; KR101036731B1; EP1672517A2; RU2005135847A; AU2005237142A1; BRPI0506084A8; BRPI0506084A; CA2526762A1; KR20060069254A; CN1791222B; US20060133683A1; EP1672517A3; JP2006197572A; AU2005237142B2; JP4874642B2; EP1672517B1; US7471850B2; CN1791222A; CA2526762C

Abstract

Una transformacion 2D y su inversa tienen una implementacion como una secuencia de pasos de realce ordenados para complejidad de calculo reducida (es decir, reducir un numero de operaciones no triviales). Este par de transformacion tiene propiedades de compactacion de energia similar a la transformacion de coseno separado (DCT), y tambien es sin perdida y libre de clasificacion. Mientras se compara con la transformacion de DCT separable implementada como transformaciones de DCT 1D aplicadas de forma separada a filas y columnas de un bloque de datos 2D, las operaciones de transformaciones son reordenadas en una cascada de transformaciones elementales, incluyendo la transformacion Hadamard de 2x2, y transformaciones de 2x2 incorporando rotaciones de realce. Estas transformaciones elementales tienen implementaciones como una secuencia de operaciones de realce.

Description

TRANSFORMACION REVERSIBLE PARA COMPRESION DE DATOS 2-D CON PERDIDA Y SIN PERDIDA CAMPO TÉCNICO La invención generalmente se refiere a la compresión de medios digitales basados en transformación de bloque (por ejemplo, video e imagen).

ANTECEDENTES Codificación Basada en Transformación de Bloque La codificación de transformación es una técnica de compresión utilizada en muchos sistemas de compresión de audio, imagen y vídeo. La imagen y vídeo digitales no comprimidos son típicamente representados o capturados como muestras de elementos o colores de imágenes en ubicaciones en un cuadro de imagen o vídeo ordenado en una cuadrícula bidimensional (2D). Esto es denominado como una representación de dominio espacial de la imagen o vídeo. Por ejemplo, un formato típico para imágenes consiste de una corriente de muestras de elemento de imagen a color de 24-bits ordenadas como una cuadrícula. Cada muestra es un número que representa componentes de color en una ubicación de píxel en la cuadrícula dentro de un espacio de color, tal como RGB, o YIQ, entre otros. Varios sistemas de imagen y vídeo pueden utilizar varios colores diferentes, resoluciones espaciales y de tiempo de muestreo. Similarmente, el audio digital es típicamente representado como corriente de señal de audio muestreada por tiempo. Por ejemplo, un formato de audio típico consiste de una corriente de muestra de amplitud de 16-bits de una señal de audio tomada en intervalos de tiempo regulares. Las señales de audio, imagen y vídeo digitales no comprimidas pueden consumir almacenamiento y capacidad de transmisión considerable. La codificación de transformación reduce el tamaño de audio, imágenes y vídeo digitales al transformar la representación de dominio espacial de la señal en una representación de domino por frecuencia (u otro dominio de transformación similar), y después reduce la resolución de ciertos componentes de frecuencia generalmente menos perceptibles de la representación de dominio por transformación. Esto generalmente produce degradación mucho menos perceptible de la señal digital comparado a reducir la resolución de color o espacial de imágenes o vídeo en el dominio espacial, o de audio en el dominio de tiempo. Más específicamente, un código basado en transformación de bloque típico 100 mostrado en la Figura 1 divide los pixeles de la imagen digital no comprimida en bloques bidimensionales de tamaño ajustado (X1f ... Xn), cada bloque que posiblemente se traslapa con otros bloques. Una transformación lineal 120-121 cuyo análisis de frecuencia espacial es aplicada a cada bloque, que convierte las muestras espaciadas dentro del bloque a un grupo de coeficientes de frecuencia (o transformación) que generalmente representa la fuerza de la señal digital en bandas de frecuencia correspondientes en el intervalo de bloque. Para compresión, los coeficientes de transformación pueden ser selectivamente cuantificados 130 (es decir, reducidos en resolución, tal como al liberar pedazos menos significativos de los valores de coeficiente o de otra forma delinear valores en un número de resolución más alto establecido a una resolución más baja), y también código de entropía o longitud variable 130 en una corriente de datos comprimida. En la descodificación, los coeficientes de transformación transformarán inversamente 170-171 a casi reconstruir la señal de imagen/vídeo muestreada de color-espacial original (bloques reconstruidos X-i , ... Xn). La transformación de bloque 120-121 puede ser definida como una operación matemática en un vector x de tamaño N. Más frecuentemente, la operación es una multiplicación lineal, que produce la salida de dominio de transformación = Mx, M siendo la matriz de transformación. Cuando los datos de entrada son arbitriamente largos, está segmentado en vectores de tamaño N y una transformación de bloque es aplicada a cada segmento. Para el propósito de compresión de datos, las transformaciones de bloque reversibles son elegidas. En otras palabras, la matriz M es invertlble. En dimensiones múltiples (por ejemplo, para imagen y vídeo), las transformaciones de bloque son típicamente impiementadas como operaciones separables. La multiplicación de matriz es aplicada de forma separada junto con cada dimensión de los datos (es decir, tanto flechas como columnas). Para compresión, los coeficientes de transformación (componentes de vector y) pueden ser selectivamente cuantificados (es decir, reducidos en resolución, tal como al liberar pedazos menos importantes de los valores de coeficiente o de otra forma delinear valores en un número de resolución más alto establecido a una resolución más baja), y también código de entropía o longitud variable en una corriente de datos comprimida. En la descodificación en el descodificador 150, la inversa de estas operaciones (descodificación de descuantificación/entropía 160 y transformación de bloque inversa 170-171) son aplicadas en el descodificador 150 lateral, como se muestra en la Figura 1. Mientras se reconstruyen los datos, la matriz inversa M1 (transformación inversa 170-171) es aplicada como un multiplicador para los datos de dominio de transformación. Cuando se aplica a los datos de dominio de transformación, la transformación inversa casi reconstruye los medios digitales de dominio de tiempo originales o de dominio espaciales. En muchas aplicaciones de codificación a base de transformación de bloque, la transformación es deseablemente reversible para apoyar tanto compresión con pérdida como sin pérdida dependiendo del factor de cuantificación. Con ninguna cuantif icación (generalmente representado como un factor de cuantificación de 1) por ejemplo, un código que utiliza una transformación reversible puede reproducir exactamente los datos de entrada en descodificación. Sin embargo, el requerimiento de reversibilidad en estas aplicaciones obliga a la elección de transformaciones en las que el código pueda ser diseñado. Muchos sistemas de compresión de imagen y vídeo, tal como MPEG y Windows Media, entre otros, utilizan transformaciones basados en la Transformación de Coseno Separado (DCT). La DCT es conocida por tener propiedades de compactación de energía favorable que resultan en compresión de datos casi óptima. En estos sistemas de compresión, la DCT inversa (IDCT) es empleada en los giros de reconstrucción tanto en el codificador como en el descod ¡f icador del sistema de compresión para reconstruir bloques de imagen individuales. La DCT es descrita por N.Ahmed, T. Natarajan, y K. R. Rao, "Transformación de Coseno Separado", IEEE Transacciones en Computadoras, C-23 (enero 1974), págs. 90-93. Una implementación ilustrativa de la IDCT es descrita en "Especificación Estándar de IEEE para las Implementaciones de Transformación de Coseno Separado Inverso de 8 x 8", IEEE Std. 1180-1990, Diciembre 6, 1990. Las transformaciones de datos convencionales utilizadas para implementar compresor de datos 2D reversible generalmente han sufrido una o más de las siguientes desventajas primarias, 1. Normas desiguales entre coeficientes de transformación, que requieren esquemas de codificación de entropía complicados; 2. Aproximaciones pobres a transformaciones óptimas, tal como la DCT; y 3. Alta complejidad computacional.

Implementación Convencional de Transformación 2D Una transformación 2D separable es típicamente ¡mplementada al realizar transformaciones 1D en las filas de los datos, seguidas por transformación 1D en sus columnas de datos (o viceversa). Ver, A. K. Jain, Fundamentos de Procesamiento de Imagen Digital, Prentice Hall, 1989. En la anotación de matriz, permitir T representar la matriz de transformación y X ser los datos 2D. La transformación 2D separable con T es definida por Y en la siguiente ecuación. Y = T X T (1) De hecho, las transformaciones de fenómeno de fila y fenómeno de columna pueden ser diferentes. Por ejemplo, la matriz de datos podría ser no-cuadrada (es decir de tamaño 4x8), o las transformaciones de fenómeno de fila o fenómeno de columna podrían ser la DCT y la transformación de seno separado (DST) respectivamente. En este caso, los pre y pos multiplicadores son diferentes (es decir 7? y T2) y la transformación Y es dada por Y = T1 X T'2 (2) Por ejemplo, la Figura 2 muestra una DCT de 4x4 2D ¡mplementada en dos etapas. En la primera etapa, las columnas de la matriz de datos son transformadas utilizando una DCT 1D de 4 puntos. En la segunda etapa, las DCTs 1 D de 4 puntos son aplicadas junto con las filas. Con precisión aritmética infinita, este orden puede ser cambiado sin cambio en la salida. La DCT 1D de 4 puntos puede ser implementada como una secuencia de multiplicación y operaciones de suma en los valores de datos de 4 puntos, como se representó en el gráfico de flujo de señal mostrado en la Figura 3. Los valores c y s en este diagrama son respectivamente coseno y seno de tt/8. El acercamiento de transformación separable trabaja bien para un código sin pérdida. Los códigos sin pérdida son más difíciles de realizar. Incluso con cuantificación de unidad, la DCT 2D separable descrita anteriormente en conjunto con su DCT o IDCT inversa separable no está garantizada para producir una concordancia exacta de pedazo a la entrada original. Esto es debido a los divisores en la Figura 3 dan surgimiento a errores circundantes que pueden no cancelarse entre el codificador y descodificador.

Realce Con el fin de lograr compresión sin pérdida con un código basado en transformación de bloque, es necesario reemplazar la DCT 2D de 4x4 antes descrita con una transformación sin pérdida. Una transformación separable puede ser utilizada sólo si cada transformación 1D es sin pérdida o reversible. Aunque existen múltiples elecciones para transformaciones 1D reversibles, aquellas basadas en "realce" están lejos de ser las más deseables. El realce es el procedimiento de realizar una multiplicación de vector de matriz utilizando "cortes" sucesivos". Un corte es definido como una multiplicación del vector de operando con una matriz que es una matriz de identidad más un elemento fuera de diagonal no-cero. La inversión de marca de uno o más coeficientes de vector puede ocurrir en cualquier lugar durante este procedimiento, sin pérdida de generalidad. El realce ha sido ¡mplementado a través de estructuras de filtro de escalera o reticulado en el pasado. Las técnicas basadas en realce o corte sucesivo han sido utilizadas en gráficos. Ver, A. Tanaka, M. Kameyama, S. azama, y O. Watanabe, "Un método de rotación para imagen de cuadro que utiliza transformación de oblicuidad", Proc IEEE Conf en Visión de Computadora y Reconocimiento de Patrón, páginas 272-277, Junio 1986; y A. W. Paeth, "Un algoritmo rápido para rotación de cuadro general", Procedimientos de Interfase de Gráficos '86, páginas 77-81, Mayo 1986. De hecho, se puede discutir que la eliminación de Gauss-Jordan es una manifestación de realce. Una operación de 2 puntos simple es la transformación de Hadamard, dada por la matriz de transformación H =. i (\ \\ i -i Dos acercamientos son comúnmente empleados para implementar una transformación de Hadamard 1D basada en realce (reversible). El primero es implementar la transformación de Hadamard normalizada o libre de clasificación en pasos de realce, como se muestra en la Figura 4. El segundo acercamiento es permitir a las escalas diferir entre los dos coeficientes de transformación, como se muestra en la Figura 5.

Problemas con Realce El realce no está libre de problemas. En el primer acercamiento de transformación de Hadamard mostrado en la Figura 4, los dos coeficientes de transformación son normalizados. Esto es deseable para realizar transformaciones de etapa múltiple, tal como la DCT de 4 u 8 puntos. Sin embargo, esta implementación sufre de dos desventajas mayores, primero, cada transformación Hadamard de 2 puntos requiere tres pasos de realce no triviales (es decir, calculablemente costosos), y segundo, errores circundantes en los pasos de realce causan que la energía de paso baja "salgan" en el término de frecuencia alta que llevan a eficacia de compresión reducida. En este primer acercamiento, utilizar la aproximación resulta en la función de base AC 0.7188]. Mientras la discrepancia del requerido [0.7071 0.7071] no parece demasiado grande, una señal De de amplitud 64 produce una respuesta AC de 2 unidades, que salen en la. banda de alta frecuencia de costoso de codificar. El segundo acercamiento (Figura 5) utiliza pasos de realce triviales. Sin embargo, el término de paso bajo está clasificado por un factor de ^2 mientras el término de paso alto es clasificado por (0 viceversa). La resolución de los dos coeficientes difiere por un pedazo. En dos dimensiones, el término alto-alto es menor en resolución por 2- bits comparada con el término bajo-bajo. Las etapas de transformación de cascada solo aumentan esa discrepancia. La codificación de entropía es más difícil de implementar debido a los rangos de diferenciación de los coeficientes. En resumen, los problemas con transformaciones sin pérdida basadas en realce son: 1. Clasificación desigual posible entre coeficientes de transformación, que hacen mecanismos de codificación de entropía más complejos. 2. Aproximaciones pobres para funciones de base de transformación deseada que puede causar efectos indeseables tal como filtración de DC en bandas AC. 3. Complejidad computacional potencialmente alta, especialmente si la implementacion basada en realce está diseñada para aproximar bien la transformación deseada.

COMPENDIO DE LA INVENCION Un sistema de codificador/descodificador de medios digitales está basado en una transformación de bloque 2D separable que tiene varias implementaciones descritas aquí que se dirigen a los problemas y desventajas antes indicados de transformaciones de técnica anterior. En particular, una implementacion descrita del par de una transformación 2D separable y su inversa tiene una secuencia de pasos de realce ordenados para complejidad computacional reducida (es decir, reducir un número de operaciones no triviales). Este par de transformación tiene propiedades de compactación de energía similares a la DCT, y también es sin pérdida y libre de clasificación. El término "sin pérdida" significa que el entero original saca a la transformación puede ser recuperado sin error por la transformación inversa, de sus coeficientes de transformación de entero, asumiendo ninguna cuantif icación. "Libre de clasificación" se refiere a las funciones de base de par de transformación siendo igualmente clasificadas, que también significa que la matriz de transformación resultante es ortogonal. Una implementación descrita de este par de transformación es como una transformación de 4x4, pero puede ser extendida a otros tamaños también (por ejemplo, 8x8, etc.). Además, las cascadas del par de transformación pueden ser utilizadas para realizar pirámides jerárquicas y transformaciones más grandes. Por ejemplo, una implementación descrita utiliza una cascada de dos niveles de la transformación. En la segunda etapa de transformación, la transformación es aplicada a los coeficientes DC 16 generados dentro de un macro bloque. Ya que la transformación es similar a la DCT, puede ser utilizada para realizar un código de medios digitales sin pérdida a con pérdida (es decir, un código cuyo parámetro de cuantif icación puede ser variado de un establecimiento sin pérdida a establecimientos con pérdida) con desempeño de distorsión de clasificación superior y eficacia de compresión. Características y ventajas adicionales de la invención serán evidentes a partir de la siguiente descripción detallada de modalidades que procede con referencia a los dibujos acompañantes.

BREVE DESCRIPCION DE LOS DIBUJOS La Figura 1 es un diagrama de bloque de un código basado en transformación de bloque convencional en la técnica anterior. La Figura 2 es un diagrama de bloque de una DCT de 4x4 2D implementada en dos etapas, también en la técnica anterior. La Figura 3 es un gráfico de flujo de señal de una DCT de 4x4 1D, también en la técnica anterior. La Figura 4 es un gráfico de flujo de señal de una transformación de Hadamard de 2 puntos normalizada que utiliza realce, también en la técnica anterior. La Figura 5 es un gráfico de flujo de señal de una transformación de Hadamard de 2 puntos trivial, también en la técnica anterior. La Figura 6 es un diagrama de flujo de un codificador basado en una transformación 2D reversible mejorada. La Figura 7 es un diagrama de flujo de un descodif icador basado en la transformación 2D reversible implementada. La Figura 8 es un gráfico de flujo de señal de una implementación basada en realce normalizada de la transformación de Hadamard 2x2 reversible. La Figura 9 es una lista de programa en el lenguaje de programación C para realizar la transformación de Hadamard de 2x2 reversible normalizada de la Figura 8. La Figura 10 es un gráfico de flujo de señal de una inversa de la transformación de Hadamard de 2x2 reversible normalizada de la Figura 8. La Figura 11 es un gráfico de flujo de señal de una implementacion basada en realce normalizada de la transformación Tposibjüdac] . La Figura 12 es una lista de programa en el lenguaje de programación C para realizar la transformación Tp0Sjb¡]¡dad normalizada de la Figura 11. La Figura 13 es un gráfico de flujo de señal de una versión basada en realce normalizada de la inversa de la transformación posi iiidad de la Figura 1. La Figura 14 es un gráfico de flujo de señal de una implementacion basada en realce normalizada de la transformación Tposibilidad-posibilidad- La Figura 15 es una lista de programa en el lenguaje de programación C para realizar la transformación TPosib¡i¡dad-Posibiiidad normalizada de la Figura 14. La Figura 16 es un gráfico de flujo de señal de una versión basada en realce normalizada de la inversa de la transformación posibiüdad-posibiiidad de la Figura 14. La Figura 17 es un diagrama que ilustra el orden de datos de 2x2 en las ilustraciones aquí de transformaciones y operaciones de transformación inversa. La Figura 18 es un gráfico de flujo de señal que ilustra una DCT 2D implementada de forma separada como un DCT vertical 1D y una DCT horizontal 1D aplicada a columnas y filas, respectivamente, de una entrada de datos de 4x4. La Figura 19 es un gráfico de flujo de señal que ilustra la transformación 2D libre de escala, reversible implementada al dar intervalos a operaciones de transformación horizontales y verticales en dos etapas. La Figura 20 es un diagrama que ilustra los puntos de un bloque de datos de 4x4 al que la transformación de Hadamard de 2x2 de la Figura 8 es aplicada en una primera etapa de una implementación de la transformación 2D reversible, mejorada en el codificador de la Figura 6. La Figura 21 es un diagrama que ilustra los puntos del bloque de datos de 4x4 al que la transformación Hadamard de 2x2 de la Figura 8, la transformación Tposibi|idad de la Figura 11, y la transformación Tp0S¡b¡iidad.p0Sibi|¡dad de la Figura 14 son aplicadas en una segunda etapa de la implementación de la transformación 2D reversible, mejorada en el codificador de la Figura 6. La Figura 22 es un diagrama que ¡lustra los puntos del bloque de coeficientes de transformación de 4x4 al que la transformación de Hadamard de 2x2 de la Figura 8, la transformación Tp0S¡b¡iidad de la Figura 11, y la transformación Tposibmdad-pOSibiiidad de la Figura 14 son aplicadas en una primera etapa de la implementación de la transformación 2D inversa en el descodificador de la Figura 7. La Figura 23 es un diagrama que ilustra el orden de coeficientes de transformación para la transformación 2D directa e inversa en el codificador de la Figura 6 y descodificador de la Figura 7. La Figura 24 es un diagrama de bloque que ilustra un ambiente de cómputo adecuado para implementar el código basado en transformación de bloque con transformación traslapada de dominio espacial mejorada de las Figuras 6 y 7. La Figura 25 es un gráfico de flujo de señal de una estructura de la implementación basada en realce normalizada de las transformaciones de 2x2 reversible mostradas en las Figura 11 y 14.

DESCRIPCION DETALLADA La siguiente descripción se refiere a sistema o código de compresión de medios digitales, que utiliza una transformación 2D libre de clasificación reversible, mejorada. Para propósitos de ilustración, una modalidad de un sistema de compresión que incorpora la transformación mejorada es un sistema de compresión de imagen o video. Alternativamente, la transformación mejorada también puede ser incorporada en sistemas de compresión o códigos para otros datos 2D. La transformación no requiere que el sistema de compresión de medios digitales codifique los datos de medios digitales comprimidos en un formato de codificación particular. 1. Codif icador/Descodif icador Las Figuras 6 y 7 son un diagrama generalizado de los procedimientos empleados en un codificador de datos bidimensional (2D) representativo 600 y descodificador 700 basado en la transformación 2D libre de escala reversible, mejorada 650 detallada más adelante. Los diagramas presentan una ilustración generalizada o simplificada del uso y aplicación de esa transformación en un sistema de compresión que incorpora el codificador y descodificador de datos 2D. En codificadores alternativos basados en esta transformación, los procedimientos adicionales o menos procedimientos que aquellos ilustrados en este codificador y descodificador representativos pueden ser utilizados para la compresión de datos 2D. Por ejemplo, algunos codificadores/decodificadores también pueden incluir conversión de color, formatos de color, codificación clasificable, codificación sin pérdida, modos de macro bloques, etc. La transformación 2D mejorada permite al sistema de compresión (codificador y descodificador) proporcionar compresión sin pérdida y/o con pérdidas de los datos 2D, dependiendo en la cuantificación que puede estar basada en un parámetro de cuantificación que varía de sin pérdida a con pérdida. El codificador de datos 2D 600 produce una corriente de bit comprimida 620 que es una representación más compacta (para entrada típica) de datos 2D 610 presentados como entrada al codificador. Por ejemplo, la entrada de datos 2D puede ser una imagen, un cuadro de una secuencia de vídeo, u otros datos que tienen dos dimensiones. El codificador de datos 2D separa 630 los datos de entrada en macro bloques, que son píxeles de 16x16 en tamaño en su codificador representativo. El codificador de datos 2D además separa- cada macro bloque en bloques de 4x4 632. Un operador de "traslape hacia delante" 640 es aplicado a cada borde entre los bloques, después de que cada bloque de 4x4 es transformado utilizando la transformación libre de escala reversible 650. Subsecuentemente, el coeficiente DC 660 de cada bloque de transformación de 4x4 está sujeto a una cadena de procesamiento similar (separación, traslape hacia delante, seguido por transformación de bloque de 4x4). Los coeficientes de transformación DC resultantes y los coeficientes de transformación AC son cuantificados 670, codificados de entropía 680 y empacados 690. El descodificador realiza los procedimientos inversos. El descodificador lateral, los recortes de coeficiente de transformación son extraídos 710 de sus paquetes respectivos, de los que los coeficientes son ellos mismos decodificados 720 y descuantificados 730. Los coeficientes DC 740 son regenerados al aplicar una transformación inversa, y el plano de coeficientes DC es "traslapado inverso" utilizando un operador de alisamiento adecuado aplicado a través de los bordes de bloque DC. Subsecuentemente, los datos completos son regenerados al aplicar la transformación inversa de 4x4 750 a los coeficientes DC, y los coeficientes AC 742 decodificados de la corriente de bit. Finalmente, los bordes de bloque en los planos de imagen resultantes son filtrados de traslape inverso 760. Esto produce una salida de datos 2D reconstruida. 2. Implementación de la Transformación Libre de Clasificación Reversible, Mejorada Como se describió por, por ejemplo, A. K. Jain, Fundamentos de Procesamiento de Imagen Digital, Prentice Hall, 1989, una transformación 2D separable puede ser implementada como una transformación 1D que opera en los datos ordenados en 1D, produciendo un resultado de vector ordenado de forma similar. La matriz de transformación equivalente es generada por el producto Kronecher de los pre- y post- multiplicadores utilizados en el caso separable. Si x y x denotan los vectores de datos y transformación reordenados de su representación 2D en (2), su relación es dada por lo siguiente Y = Tx (3) en donde T = Kron (?,, T2). Aunque la implementación separable de una transformación 2D mostrada en la ecuación (2) es calculablemente más eficiente (en un sentido asintótico) que en la ecuación (3), existen ciertos casos en donde la última presentación lleva a propiedades deseables. Por ejemplo, una implementación basada en la ecuación (3) tiene latencia inferior que en la ecuación (2), debido a un múltiplo de matriz de etapa individual (que es una operación soportada nativamente en diferentes procesadores de señal digital (DSPs)). Para la transformación libre de clasificación reversible, mejorada aquí descrita, la representación 1D de pasos de 2x2 lleva a una estructura reversible libre de clasificación. Además, una transformación 2D separable puede ser ¡mplementada como una cascada de transformaciones 1D más simples. Se asume que las matrices de transformación ?? y T2 pueden ser descompuestas como sigue Ti - TIATIB T2 = T2AT2B (4) La capacidad de asociación de la operación de múltiplo de matriz puede ser utilizada para reordenar la transformación 2D (2) como sigue Y = Ti X T'2 = TIA (T1B X T'2B)T'2A (5) que lleva a la implementación 1D en cascada y= Kron (T1A, T2A). Kron(7ÍS T2B).x (6) Las transformaciones tal como la DCT pueden ser formuladas como una cascada de operaciones de rotación de 2 puntos elementales. La DCT 2D puede ser formulada utilizando la estructura de (6) para poseer ciertas propiedades deseables, que serán descritas en más detalle más adelante.

A. Transformación de Hadamard 2D La transformación de Hadamard 2D, ¡mplementada como una operación 1D es generada por el producto de Kronecker, De forma interesante, es posible realizar una transformación reversible libre de clasificación que corresponde a la ecuación (7), que utiliza sólo pasos de realce triviales. Una implementación de esta forma es mostrada como el gráfico de flujo de señal 800 en la Figura 8. El código C++ que elimina algunas operaciones redundantes es mostrado en la Figura 9. En esta lista de código 900, "cambio(x,y)" es una función que intercambia los valores de sus argumentos. A partir de lo anterior, se puede ver que la transformación de Hadamard 2D reversible normalizada puede ser formulada utilizando sólo pasos de realce triviales, aunque esto no es posible para el caso Hadamard 1D discutiblemente "más simple". Aunque la misma matriz de transformación es involuntaria (es decir, TH es su propia inversa), una reconstrucción sin pérdida requiere que los pasos de realce sean cuidadosamente revertidos para que reproduzcan precisamente cualquiera de los efectos circundantes. La inversa 1000 de la estructura 800 en la Figura 8 si se presenta en la Figura 10, la estructura 1000 es idéntica a la transformación directa en este caso. Se debe notar que ios coeficientes de transformación B y C son cambiados en los gráficos de flujo de señal. La transformación 2D libre de clasificación, reversible 650 en el codificador 600 de la Figura 6 utiliza una aproximación a la DCT de 4x4. La siguiente descripción demuestra el procedimiento de la transformación completo de la transformación 650 puede ser realizado como la cascada de las operaciones de transformación de 2x2 elementales, que son la transformación Hadamard de 2x2, y lo siguiente: Rotación de posibilidad: Y = TR X ?? Rotación de posibilidad-posibilidad: Y = TR X T'R (8) en donde la matriz de rotación de punto TR es dada por Las implementaciones 1D de la ecuación (8) son obtenidas al calcular el producto Kronecker de la pre y pos matrices de transformación (aproximado a cuatro lugares decimales) (10) (11) El signo de intercalación ? indica la matriz de transformación deseada. Las aproximaciones resultantes de las implementaciones reales no transportan el signo de intercalación. Para la transformación de Hadamard de 2x2, la matriz de transformación deseada y su aproximación son idénticas. Por lo tanto, TH es utilizada para denotar la transformación Hadamard de 2x2 implementada en 1D, sin ninguna ambigüedad. Después, observamos en la implementación de realce de Tposi iiidad y TPos¡b¡ndad-posrbü¡dad- B. Implementación de Tpos¡b¡Mdad Una implementación basada en realce, libre de clasificación de la transformación Tpos¡b¡i¡dad 1100 es mostrada como un gráfico de flujo de señal en la Figura 11, y en una lista de programa de código C + + 1200 en la Figura 12. Se puede observar que la primera y última etapas de realce son idénticas al caso de transformación de Hadamard. Además de los recortes triviales, las rotaciones de realce no triviales son aplicadas en las etapas intermedias. Cada rotación no trivial es implementada en tres pasos, con un múltiplo por 3 y un cambio de bit por 3 o 4 bits. Por lo tanto, la Tposi iiidad puede ser realizada en una forma libre de clasificación, reversible al utilizar 6 pasos de realce no triviales. La p0s¡ ii¡dad de matriz de transformación 1D resultante es mostrada más abajo (12), que está en conformidad cercana con la formulación original de Tposibmdad en (10). Se puede observar que la segunda y cuarta filas de la matriz de transformación resultante suman cero, lo que significa que no existe filtración de DC en las bandas AC. Esta propiedad deseable es lograda aunque las rotaciones 2D requeridas son solamente aproximadas en la estructura. (0.6458 0.6458 0.2839 0.2839 N _ 0.6523 - 0.6523 0.2773 - 0.2773 oda ~ 0.2773 0.2773 - 0.6523 - 0.6523 ^0.2839 -0.2839 -0.6458 0.6458 J ^ Aunque la Tpos¡ büídad de matriz de transformación es involuntaria (es decir, es su propia inversa), los errores circundantes no cancelan en dos aplicaciones sucesivas del gráfico de flujo de señal o código. La inversa sin pérdida de Tpos¡b¡i¡dad es derivada al revertir los pasos de realce, ya sea en el gráfico de flujo de señal o en el código C + + , para repetir los errores circundantes laterales de transformación directa. El gráfico de flujo de señal de la inversa 1300 de Tp0sib¡iidad es mostrado en la Figura 13, el código puede ser derivado de forma similar.

C. Implementación de Tposibmdad.pOSibmdad La transformación de Tpos¡biiiciad-pos¡bii¡daci 1400 está compuesta de dos rotaciones, de las cuales ninguna es una transformación de Hadamard. De forma interesante, TpOS¡b¡i¡dad-Posibii¡dad puede ser realizada con menos pasos de realce no triviales que Tpos¡b¡i¡dad- Esto es debido a las propiedades de simetría del producto de Kronecker de TR con el mismo. El gráfico de flujo de señal de la transformación posibiüdad.posibiüdad 1400 y la lista de programa 1500 de su realización de código C++ son mostradas en las Figura 14 y 15, respectivamente. Se puede observar que sólo una rotación no trivial, implementada por medio de tres pasos de realce no triviales es requerida para realizar Tposibnidad-pc,si5mdad. Esta rotación corresponde a la transformación de Hadamard de 2 puntos 1D libre de clasificación. ?.8594 0.3223 0.3223 0.1406 ^ _ 0.3750 -0.8594 0.1406 -0.3750 odd-odd - 0 750 0 1406 _08594 _0.3750 ?.1406 -0.3223 -0.3223 0.8594 J ^ Como con las otras transformaciones consideradas aquí, posibiiidad-posibiiidad como se representa en la ecuación (13) es involuntaria, aunque ninguna inversa exacta de bit de ella misma. La inversa sin pérdida 1600 de Tp0S¡b¡|jdad_p0S¡b¡i¡dad es obtenida al revertir el gráfico de flujo de señal utilizado para la transformación directa, como se muestra en la Figura 16.

D. Anotación para y Derivación de Implementaciones de Transformación de 2x2 Anteriores En las ilustraciones aquí de la transformación 2D libre de clasificación, reversible que utiliza estas tres transformaciones libres de clasificación reversibles, aplican los siguientes puntos. Primero, el orden 1700 de los datos de 2x2 resultantes en los gráficos de flujo de señal anteriores y código C++ como se muestra en la Figura 17. Los puntos de dominio espacial son mostrados a la izquierda, y los puntos de dominio de frecuencia correspondiente a la derecha. El código de color que utiliza cuatro niveles grises para indicar los cuatro puntos de datos es presentado aquí, para facilitar la descripción de transformación 2D libre de clasificación, reversible que sigue. Frecuentemente, las transformaciones de 2 puntos o rotaciones son definidas como la siguiente operación osO señé? y = -señé? cosí? (14) en vez de la forma involuntaria cosí? señé? N ^sen T — eos T J (15) Estas dos formas son esencialmente idénticas, ya que sólo difieren en marcar el segundo coeficiente de transformación. La última representación (15) es utilizada aquí, aunque la derivación completa en este documento es igualmente aplicable a la forma anterior (14). La estructura de las transformaciones de 2x2 básicas, TH, T posibilidad posíbilidad-posibilidadi definidas anteriormente son construidas al notar que cada transformación de dos puntos es una rotación. Además, el producto de Kronecker de rotaciones de 2 puntos es dada como sigue: cosa sena eos ß sen ß T = Kron (16) -señor cosa -sen ß eos ß Después definimos un operador H como sigue: H representa una operación de mariposa doble no normalizada puede ser eficientemente implementada utilizando realce. La siguiente factorización sostiene: Basándose en esto, un producto de Kronecker del tipo 7 puede ser implementado como una cascada de 3 etapas: A. Una operación de , mariposa doble definida por H que utiliza pasos de realce. B. Rotaciones de 2 puntos entre el primer par de componentes, y entre el segundo par de componentes, y C. La opuesta de la mariposa doble realizada en el paso a. Para TH de caso especial, existe una descomposición incluso más simple, que es mostrada como el gráfico de flujo de señal 800 en la Figura 8 y descrita anteriormente. Para los otros casos (por ejemplo, Tp0Sib¡iidad y Tp0Sibmdad_p0Sibmdad), la estructura resultante puede ser generalizada como el gráfico de flujo 2500 mostrado en la Figura 25. Observando los tres gráficos de flujo de señal de las transformaciones descritas anteriormente (y también sus inversas), se observa una similitud fundamental en su estructura. La primera etapa de la transformación es una operación de realce entre los coeficientes a-d y b-c. De forma similar, la última etapa es el procedimiento de realce de inversa (señal de descuento e intercambios de coeficiente). De forma correspondiente, la primera etapa de la transformación inversa es una operación de realce entre A y D, y también entre B y C, con la operación opuesta en la última etapa. Los pasos de realce entre los elementos diagonales es una característica de distinción de la transformación de 2x2 2D aquí presentada. La siguiente sección discute la construcción de una transformación libre de clasificación, sin pérdida, que aproxima la DCT/IDCT de 4x4. Aunque una modalidad ilustrativa de la transformación es presentada en esta discusión técnica detallada, el mismo procedimiento, con la definición adicional de otras transformaciones basadas en realce reversible elemental de 2x2, puede ser utilizado para generar modalidades de transformación reversible dimensional superior con propiedades deseables.

E. Transformación Libre de Clasificación, Sin Pérdida La DCT de 4 puntos puede ser reducida a una secuencia de cuatro operaciones de mariposa como se muestra en el gráfico de flujo de señal de la Figura 3. La primera etapa consiste de dos mariposas que realizan operaciones Hadamard de 2 puntos en los datos de entrada (es decir, un Hadamard de 2 puntos de índices de datos de entrada 0 y 3; y un segundo de índices de entrada 1 y 2). La segunda etapa comprende una operación de Hadamard de 2 puntos en los resultados de paso inferior de la primera etapa para generar los componentes de frecuencia de constante (índices 0 y 2), y una rotación de 2 puntos por 77/8 para generar los componentes de frecuencia de posibilidad (índices 1 y 3). En dos dimensiones, la DCT puede ser implementada de forma separada; una DCT de 4 puntos 1D vertical de cada columna de los datos de entrada de 4x4; seguido por una DCT de 4 puntos 1D horizontal de las filas (o viceversa). Esto es ¡lustrado como una implementación de DCT separable 1800 en la Figura 18. Alternativamente, las dos etapas DCT 1D descritas anteriormente pueden ser espaciadas entre la horizontal y vertical, que utilizan la teoría de ecuación (5), como se muestra como una implementación de DCT con intervalo 1900 en la Figura 19. Además, cuando se sigue el acercamiento anterior, las etapas horizontales y verticales correspondientes además pueden ser combinadas. Por ejemplo, la primera etapa es una transformación Hadamard de 2 puntos en los elementos de entrada "interiores" y "exteriores". Las etapas horizontales y verticales pueden ser fusionadas en 4 aplicaciones de la transformación Hadamard 2D de 2x2 en los elementos de datos de entrada 16, cada transformación siendo aplicada a un grupo simétrico de puntos de entrada. De forma similar, los pasos de la horizontal y vertical de la segunda etapa pueden ser unidos en una transformación Hadamard de 2x2 y tres transformaciones de 2x2, dos de las cuales son transposiciones. Se observa que las últimas tres transformaciones de 2x2 de hecho son redelineados 2D de Tpos¡b¡[¡dad y Tpos¡b¡i¡dad-pos¡b¡i¡daci definidas anteriormente. Más particularmente, la transformación 2D libre de clasificación reversible 650 (Figura 6) es implementada al reordenar las operaciones de transformación en un orden de las transformaciones Hadamard de 2x2, Tpos¡bii¡dad y Tp0sibj|idad. posibilidad- Las dos etapas de esta transformación 650 son realizadas como se muestra en las Figuras 20 y 21, respectivamente. Cada etapa consiste de cuatro transformaciones de 2x2 que pueden ser hechas en cualquier secuencia arbitraria, o concurrentemente, dentro de la etapa. Para la transformación 2D inversa 750 (Figura 7), las etapas son revertidas en orden, y los pasos dentro de cada etapa de transformación utilizan la inversa de los pasos en el procedimiento de transformación directa. Como se notó anteriormente, la transformación Hadamard de 2x2 TH es su propia inversa, en un bit exacto o sentido sin pérdida. Por lo tanto, la segunda etapa de la transformación de Fotón inversa es solamente la primera etapa de la transformación de Fotón directa, como se muestra en la Figura 20. La primera etapa 2200 de la transformación de Fotón inversa es ilustrada en la Figura 22. Los cuatro pasos dentro de esta etapa (que, como para el caso de transformación directa, pueden ser ejecutados en orden arbitrario o concurrentemente) aplican las inversas de ??, pos¡b¡|jdad y p0s¡biiidad-posib¡iidad como se definió anteriormente, y redelineados a un espacio de 2x2 2D. Al seguir los pasos de la transformación 2D mejorada directa mostrada en las Figura 20 y 21, los coeficientes de transformación resultantes son reordenados como se muestra en la Figura 23. El mismo orden 2300 es asumido para los coeficientes siendo transformados de inversa utilizando pasos en las Figuras 22 y 20, en ese orden. La implementación mejorada antes descrita de la transformación 2D directa 650 consiste de cinco aplicaciones de,TH, dos aplicaciones de Tpos¡b¡i¡dad y una aplicación de Tp0Sibnidad-posibmdad a cada bloque de 4x4. El mismo número de aplicaciones de estas transformaciones está involucrado en la implementación desde la transformación 2D inversa 750. Por consiguiente, el número total de pasos de realce no triviales es 5x0 + 2x6 + 1x3=15 para cada bloque, para realizar la transformación directa sin pérdida o 2D inversa. Esto es sobre 1 paso no trivial por píxel. Un paso no trivial es una operación de la forma (3 x x+r)>>k, en donde x es el operando, r y k son constantes que determinan cambio circundante y de bit. El valor de k es ya sea 2, 3 o 4. De forma similar, existen cambios derechos de lugar individual 17 (es decir x>>1) por bloque. Las sumas, restas y negaciones no son contadas en esta revisión. En comparación, se considera la implementación separable 1800 de la DCT 2D ¡lustrada en la Figura 18. Se asume que cada DCT de 4 puntos es implementada utilizando tres operaciones Hadamard normalizadas de 2 puntos como se muestra en la Figura 3, y la rotación por p/8 es implementada utilizando tres pasos de realce no triviales. El número total de operaciones de realce no triviales por bloque de 4x4 ya sea para la transformación directa o inversa es 2x4x3 = 24. El número total de cambios derechos de lugar individual también es 24. Estos números son aproximadamente 50% más altos que las implementaciones de transformación directa mejorada 650 y transformación inversa 750, sin contar el hecho que la transformación resultante produce funciones de base con normas en el rango ¼ hasta 2 (o hasta 4 si se evitan funciones de base de rango irracional). En contraste, todas las funciones de base de la transformación mejorada 650 son norma de unidad.

F. Transformación Mejorada para Espacio de Color 4:2:0 En una implementación ilustrativa del codificador 600 (Figura 6) y descodificador 700 (Figura 7), el espacio de color 4:2.0 de YUV es utilizado para representar el color de pixeles en una imagen (o cuadro de video). En este código ilustrativo), un macro bloque en el espacio de color 4:2:0 de YUV es definido como una separación de 16x16 de pixeles en el canal de iuminancia (Y), y separaciones de 8x8 en los canales de crominancia (U y V). Estos son además divididos en bloques de 4x4 que son codificados de transformación que utilizan la transformación antes descrita 650. La transformación de 4x4 650 es aplicada a los coeficientes DC de los canales de Iuminancia. Sin embargo, sólo muestras de 2x2 de crominancia están disponibles dentro de un macro bloque. El código ilustrativo después aplica TH, como se describió anteriormente es una transformación de Hadamard de 2x2 libre de clasificación reversible, a los valores de crominancia DC dentro de cada macro bloque. De esa forma, la estructura de macro bloque del formato de código ilustrativo es preservada, y ninguna de las transformaciones adicionales necesitan ser introducidas en el código para controlar el formato 4:2:0.

G. Minimizar Errores Circundantes Los errores circundantes son presentados en los pasos de realce de las transformaciones TH, Tp03ibmdad y Tp0sib¡iidad-posibiiidad que involucran un cambio de bit derecho. Estos errores circundantes tienen propensión conocida, y pueden construirse en el curso de la transformación. Por ejemplo, se conoce que un paso de la forma x+= (y>>1) lleva a una propensión de -¼. Los errores circundantes no son evitables en transformaciones de entero a entero que involucran realce, pero sería deseable minimizar la propensión en el sistema total. Las fórmulas de ??, Tpositimciad Y Tpos¡b¡i¡dad-pos¡bii¡dad mostradas anteriormente como recortes de código C + + agregan factores variantes a operandos siendo divididos o cambiados de bit derecho. Estos factores son elegidos para minimizar la propensión. En particular, la propensión en los cuatro coeficientes de transformación después de la operación de primera etapa de TH (para una entrada no propensa) que utiliza la lista de código C++ 900 en la Figura 9 puede ser mostrada para ser [¼ -¼ - ¼ -¼]. La aplicación de segunda etapa de TH en la transformación 2D mejorada 650 (Figura 6) opera en los valores DC de la primera etapa, es decir, en coeficientes que ya son propensos a ¼. El resultado de la operación de segunda etapa produce una propensión de [¾ -¼ - ¼- ¼]. Ya que el primer coeficiente es el DC de DC, se espera que sea grande y la propensión relativamente alta de ¾ no afecta el desempeño de codificación. Los pasos de realce no triviales en TpoSibmdad y Tpos¡b¡]¡dad-posibilidad proporcionan libertad de elegir factores circundantes para minimizar propensión de transformación. La lista de código C + + 1500 (Figura 15) para TpOSjbnidad-posibjMdad muestra que algunas veces las reglas circundantes fuera de centro (tal como a + = (3b+5)>>3) lleva a una propensión total menor, especialmente cuando los datos de entrada ya están propensos. Para los pasos de transformación Tposibiiidad y Tposibiiidad-posibiüdad, todas las entradas son propensas a - Típicamente, la definición de un código está restringida a una definición del descodificador de corriente de bit. Una excepción a esta regla es hecha para códigos sin pérdida, ya que el codificador y descodificador deben estar en perfecta concordancia para los datos de entrada a ser reconstruidos sin pérdida. En el caso de un código con pérdida a sin pérdida, se define tanto los laterales de codificador como descodificador. Sin embargo, cuando el codificador es operado en un modo puramente con pérdida, algunos atajos o aumentos pueden ser posibles que pueden proporcionar un mejor desempeño (en términos de distorsión de clasificación, o cuenta de ciclo computacional) que el desempeño de línea base como se definió en la especificación de código. Un medio de mejorar desempeño de codificador se refiere a propensión de coeficiente de transformación. Es posible reducir el efecto de propensión en algunas modalidades del codificador 600/descodificador 700 al sacar el siguiente procedimiento para cada bloque de 4x4: 1. Clasificar el bloque de 4x4 al multiplicar por m = 2k (típicamente m = 4 trabaja bien). 2. Realizar la transformación 2D mejorada 650 en el bloque. 3. Cuantificar el bloque utilizando una cua ntif icador que en m veces el parámetro de cuantificación deseado original (por ejemplo, utilizar un factor de cuantificación (QP) de 32 si el QP deseado es 8 y m = 4 en el paso 1). No existe cambio en el lateral de descodificador 700, incluso mejores números de PSNR son posibles en la misma clasificación de bit, Por supuesto, esto no trabaja para codificación sin pérdida. 3. Ambiente de Cómputo El código antes descrito con transformación 2D libre de clasificación, reversible puede ser realizado en cualquiera de una variedad de dispositivos en el que el procesamiento de señal de medios digitales es realizado, incluyendo entre otros ejemplos, computadoras; grabación de imagen y vídeo, equipo de transmisión y recepción; reproductores de vídeo portátiles; conferencia por vídeo; y etc. Las técnicas de codificación de medios digitales pueden ser implementadas en circuitos de hardware, así como en software de procesamiento de medios digitales que se ejecutan dentro de una computadora u otro ambiente de cómputo, tal como se muestra en la Figura 24. La Figura 24 ilustra un ejemplo generalizado de un ambiente de cómputo adecuado (2400) en el que las modalidades descritas pueden ser implementadas. El ambiente de cómputo (2400) no pretende sugerir cualquier limitación al alcance de uso o funcionalidad de la invención, mientras la presente invención puede ser implementada en diversos ambientes de cómputo de propósito general o propósito especial. Con referencia a la Figura 24, el ambiente de cómputo (2400) incluye al menos una unidad de procesamiento (2410) y memoria (2420). En la Figura 24, esta configuración más básica (2430) está incluida dentro de una línea punteada. La unidad de procesamiento (2410) ejecuta instrucciones ejecutables por computadora y puede ser un procesador real o virtual. En un sistema de multiprocesamiento, las unidades de procesamiento múltiples ejecutan instrucciones ejecutables por computadora para aumentar la energía de procesamiento. La memoria (2420) puede ser memoria volátil (por ejemplo, registradores, memoria caché, RAM), memoria no volátil (por ejemplo, ROM, EEPROM, memoria instantánea, etc.), o alguna combinación de las dos. La memoria (2420) almacena software (2480) que implementa el codificador/descodificador y las transformaciones descritas. Un ambiente de cómputo puede tener características adicionales. Por ejemplo, el ambiente de cómputo (2400) incluye almacenamiento (2440),· uno o más dispositivos de entrada (2450), uno o más dispositivos de salida (2460), y uno o más conexiones de comunicación (2470). Un mecanismo de interconexión (no mostrado) tal como un conductor común, controlador, o red que interconecte los componentes del ambiente de cómputo (2400). Típicamente, el software de sistema operativo (no mostrado) proporciona un ambiente operativo para otro software que se ejecuta en el ambiente de cómputo (2400), y coordina actividades de los componentes del ambiente de cómputo (2400). El almacenamiento (2440) puede ser removible o no removible, e incluye discos magnéticos, cintas magnéticas o casetes magnéticos, CD-ROMs, CD-RWs, DVDs, o cualquier otro medio que puede ser utilizado para almacenar información y que puede ser accedido dentro del ambiente de cómputo (2400). El almacenamiento (2440) almacena Instrucciones . para el software (2480) que implementa el código con SDLT mejorada El dispositivo(s) de entrada (2450) puede ser un dispositivo de entrada por tacto tal como un teclado, ratón, pluma o seguibola, un dispositivo de entrada por voz, un dispositivo de escaneo, o cualquier otro dispositivo que proporcione entrada al ambiente de cómputo (2400). Para el audio, el dispositivo(s) de entrada (2450) puede ser una tarjeta de sonido o dispositivo similar que acepta entrada de audio en forma análoga o digital, un lector de CD-ROM que proporciona muestras de audio al ambiente de cómputo. El dispositivo(s) de salida (2460) puede ser una presentación, impresora, bocina, CD-writer u otro dispositivo que proporciona salida del ambiente de cómputo (2400). La conexión(es) de comunicación (2470) permiten comunicación en un medio de comunicación a otra entidad de cómputo. El medio de comunicación transporta información tal como instrucciones ejecutables por computadora, audio comprimido o información de vídeo, u otros datos en una señal de datos modulada. Una señal de datos modulada es una señal que tiene una o más de sus características establecidas o cambiadas de tal forma para codificar información en la señal. A manera de ejemplo, y no de limitación, los medios de comunicación incluyen técnicas alámbricas o inalámbricas implementadas con un transportador eléctrico, óptico, de RF, infrarrojo, acústico, u otro transportador. Las técnicas de procesamiento de medio digital aquí pueden ser descritas en el contexto general de medios legibles por computadora. Los medios legibles por computadora con cualquier medio disponible que puede ser accedido dentro de un ambiente de cómputo. A manera de ejemplo, y no de limitación, con el ambiente de cómputo (2400), los medios legibles por computadora incluyen memoria (2420), almacenamiento (2440), medios de comunicación, y combinaciones de cualquiera de los anteriores. Las técnicas de procesamiento de medios digitales aquí pueden ser descritas en el contexto general de instrucciones ejecutables por computadora, tal como aquellas incluidas en módulos de programa, siendo ejecutados en un ambiente de cómputo en un procesador real o virtual de objetivo. Generalmente, los módulos de programa incluyen rutinas, programas, bibliotecas, objetos, clases, componentes, estructuras de datos, etc., que realizan tareas particulares o implementas tipos de datos abstractos particulares. La funcionalidad de los módulos de programa puede ser combinada o dividida entre módulos de programa como se ha deseado en varias modalidades. Las instrucciones ejecutables por computadora para módulos de programa pueden ser ejecutadas dentro de un ambiente de cómputo local o distribuido. Para la búsqueda de presentación, la descripción detallada utiliza términos como "determinar", "generar", "ajustar", y "aplicar" para describir operaciones de computadora en un ambiente de cómputo. Estos términos son abstracciones de nivel superior para operaciones, realizadas por una computadora, y no deben ser consumidas con actos realizados por un ser humano. Las operaciones de computadora reales que corresponden a estos términos varían dependiendo en la implementación. En vista de las muchas modalidades posibles a las que los principios de nuestra invención pueden ser aplicados, reclamamos como nuestra invención tales modalidades que pueden venir dentro del alcance y espíritu de las siguientes reivindicaciones equivalentes a las mismas.

Claims

REIVINDICACIONES 1. - Un método para realizar una transformación de bloque bidimensional libre de clasificación, reversible definido como una transformación de 1 dimensión aplicada horizontalmente y verticalmente en un bloque bidimensional de datos de medios digitales, el método comprende: en cada una de dos o más etapas de operaciones de intervalo de las transformaciones de 1 dimensión horizontales y verticales, aplicar las operaciones en la etapa respectiva reordenada como un grupo de transformaciones elementales implementadas como pasos de realces a subgrupos independientes de valores en el bloque bidimensional. 2. - El método de acuerdo con la reivindicación 1, que además comprende en una primera de las etapas, aplicar una transformación de Hadamard de 2x2 a subgrupos de 4 valores independientes en el bloque bidimensional de valores. 3. - El método de acuerdo con la reivindicación 3, en donde los subgrupos de 4 valores comprenden: un grupo de cuatro valores en esquinas del bloque bidimensional; un grupo de cuatro valores en un centro del bloque bidimensional; un grupo de cuatro valores en centros de borde horizontal del bloque bidimensional; y un grupo de cuatro valores en centros de borde vertical del bloque bidimensional. 4.- El método de acuerdo con la reivindicación 1, que además comprende en una segunda de las etapas, aplicar un grupo de transformación a subgrupos de 4 valores independientes en el bloque bidimensional de valores, al menos uno del grupo de transformaciones siendo implementado en la forma de una cascada de tres etapas, que comprende: una operación de mariposa doble definida por el operador H que utiliza pasos de realce, en donde rotaciones de dos puntos entre un primer par de valores de componente, y entre un segundo par de valores de componente, respectivamente; y una reversa de la operación de mariposa doble. 5.- El método de acuerdo con la reivindicación 1, que además comprende en una segunda de las etapas, aplicar un grupo de transformaciones a subgrupos de 4 valores independientes en el bloque bidimensional de valores, el grupo de transformaciones incluyendo una transformación Hadamard de 2x2, una transformación de rotación de posibilidad de 2x2 derivada como un producto Kronecher de una transformación Hadamard de 2 puntos y una matriz de rotación de dos puntos, y una transformación de rotación de posibilidad-posibilidad de 2x2 derivada como un producto Kronecher de las matrices de rotación de dos puntos. 6. - El método de acuerdo con la reivindicación 1 , con reducción de propensión de error circundante, el método además comprende: para una operación de mariposa que involucra una división o cambio de pedazo derecho, agregar un factor de variante para operandos siendo divididos o cambiados de pedazo derecho antes de la operación de mariposa respectiva. 7. - El método de acuerdo con la reivindicación 1, con reducción de propensión de error circundante para compresión con pérdida, el método además comprende: antes de la transformación, clasificar el bloque bidimensional al multiplicar por un factor; realizar la transformación; y cuantificar los coeficientes de transformación resultantes por un cuantificador igual a un cuantificador deseado multiplicado por el factor. 8.- Un método para realizar una inversa de la transformación bidimensional de acuerdo con la reivindicación 1, el método para realizar la inversa comprende, en cada una de dos o más etapas dar intervalos a operaciones de las transformaciones de una dimensión horizontales y verticales, aplicar las operaciones en la etapa respectiva reordenada como un grupo de transformaciones elementales implementadas como pasos de realce a subgrupos independientes de valores en el bloque bidimensional. 9. - El método de acuerdo con la reivindicación 8, que además comprende en una primera de las etapas, aplicar un grupo de transformaciones a subgrupos de 4 valores independientes en el bloque bidimensional de valores, el grupo de transformaciones incluyendo una transformación de Hadamard de 2x2, una transformación de rotación de posibilidad de 2x2 derivada como un producto de Kronecher de una transformación Hadamard de 2 puntos y una matriz de rotación de dos puntos, y una transformación de rotación de posibilidad-posibilidad de 2x2 derivada como un producto de Kronecher de las matrices de rotación de dos puntos. 10. - El método de acuerdo con la reivindicación 9, en donde los subgrupos de 4 valores comprenden grupos de cuatro valores en el superior izquierdo, superior derecho, inferior izquierdo e inferior derecho del bloque bidimensional. 11. - El método de acuerdo con la reivindicación 9, en donde la transformación de Hadamard de 2x2, la transformación de rotación de posibilidad de 2x2, y la transformación de rotación de posibilidad-posibilidad de 2x2 son proporcionadas por las siguientes ecuaciones, aproximadas a cuatro lugares de decimales: 0.6458 0.6458 0.2839 0.2839 0.6523 -0.6523 0.2773 - 0.2773 0.2773 0.2773 -0.6523 -0.6523 0.2839 -0.2839 -0.6458 0.6458 ( 0.8594 0.3223 0.3223 0.1406 ^ 0.3750 -0.8594 0.1406 -0.3750 X odd-odd 0.3750 0.1406 -0.8594 -0.3750 0.1406 V -0.3223 -0.3223 0.8594 j 12. - El método de acuerdo con la reivindicación 8, que además comprende en una segunda de las etapas, aplicar una transformación de Hadamard de 2x2 a subgrupos de 4 valores independientes en el bloque bidimensional de valores. 13. - Un codificador de un sistema de compresión con périda/sin pérdida para realizar compresión con pérdida/sin pérdida de datos de medios digitales bidimensionales con codificación a base de transformación de bloque que utiliza una transformación bidimensional libre de clasificación, reversible definida como una transformación de 4 puntos aplicada verticalmente y horizontalmente a bloques bidimensionales de los datos de medios digitales, el codificador comprende: una memoria intermedia para guardar en la memoria intermedia datos de medios digitales bidimensionales para ser codificados; un procesador para aplicar la transformación a bloques bidimensionales de los datos de medios digitales, en cada una de dos o más etapas de operaciones de intervalo de la transformación de 4 puntos de una dimensión horizontal y vertical, al aplicar las operaciones en la etapa respectiva reordenada como un grupo de transformaciones de 2x2 elementales implementadas como pasos de realce a subgrupos de 4 valores independientes en el bloque bidimensional. 14. - El codificador de acuerdo con la reivindicación 13, en donde las transformaciones elementales comprenden una transformación de Hadamard de 2x2, una transformación de rotación de posibilidad de 2x2 derivada como un producto de Kronecher de una transformación de Hadamard de 2 puntos y una matiz de rotación de dos puntos, y una transformación de rotación de posibilidad-posibilidad de 2x2 derivada como un producto de Kronecher de las matrices de rotación de dos puntos. 15. - El codificador de acuerdo con la reivindicación 13, en donde el procesador en una primera etapa aplica una transformación de Hadamard de 2x2 a subgrupos de 4 valores del bloque de medios digitales respectivo incluyendo grupos de 4 valores en esquinas, bordes superiores/inferiores, y bordes izquierdos-derechos del bloque de medios digitales. 16.- El codificador de acuerdo con la reivindicación 13, en donde el procesador en una segunda etapa aplica una transformación de Hadamard de 2x2 a un subgrupo de 4 valores en el superior izquierdo del bloque de medios digitales respectivo, una transformación de Hadamard de 2x2, una transformación de rotación de posibilidad de 2x2 derivada como un producto de Kronecher de la transformación de Hadamard de 2x2 y una matriz de rotación de dos puntos para subgrupos de 4 valores en el superior derecho e inferior izquierdo del bloque de medios digitales respectivo, y una transformación de rotación de posibilidad-posibilidad de 2x2 derivada como un producto de Kronecher de la matriz de rotación de dos puntos consigo mismo a un subgrupo de 4 valores en el inferior derecho del bloque de medios digitales respectivo. 17.- Un descodificador del sistema de compresión con pérdida/sin pérdida de acuerdo con la reivindicación 13 para realizar descompresión con pérdida/sin pérdida de los datos de medios digitales bidimensionales comprimidos con descodificación a base de transformación de bloque que utiliza una inversa de la transformación bidimensional libre de clasificación, reversible, el descodificador comprende: una memoria intermedia para guardar en la memoria intermedia coeficientes de transformaciones de bloques de los datos de medios digitales bidimensionales comprimidos; un procesador para aplicar la transformación inversa a bloques bidimensionales de los datos de medios digitales, en cada una de dos o más etapas de operaciones de intervalo de la transformación inversa de 4 puntos de una dimensión horizontal y vertical, al aplicar las operaciones el la etapa respectiva reordenada como un grupo de transformaciones de 2x2 elementales implementadas como pasos de realce a subgrupos de 4 valores independientes en el bloque bidimensional. 18. - El descodificador de acuerdo con la reivindicación 17, en donde las transformaciones elementales comprenden una transformación de Hadamard de 2x2, una transformación de rotación de posibilidad de 2x2 derivada como un producto de Kronecher de una transformación de Hadamard de 2 puntos y una matriz de rotación de dos puntos, y una transformación de rotación de posibilidad-posibilidad de 2x2 derivada como un producto de Kronecher de las matrices de rotación de dos puntos. 19. - El descodificador de acuerdo con la reivindicación 18, en donde el procesador en una primera etapa aplica una transformación de Hadamard de 2x2 a un subgrupo de 4 valores en el superior izquierdo del bloque de medios digitales respectivo, una transformación de Hadamard de 2x2, una transformación de rotación de posibilidad 2x2 derivada como un producto de Kronecher de una transformación de Hadamard de dos puntos y una matriz de rotación de dos puntos para subgrupos de 4 valores en el superior derecho e inferior izquierdo del bloque de medios digitales respectivo, y una transformación de rotación de posibilidad-posibilidad de 2x2 derivada como un producto de Kronecher de las matrices de rotación de dos puntos para un subgrupo de 4 valores en el inferior derecho del bloque de medios digitales respectivo. 20. - El descodificador de acuerdo con la reivindicación 18, en donde el procesador en una segunda etapa aplica una transformación de Hadamard de 2x2 a subgrupos de 4 valores del bloque de medios digitales respectivo incluyendo grupos de 4 valores en esquinas, centro, bordes superiores/inferiores, y bordes izquierdos-derechos del bloque de medios digitales.