ES2376540T3

ES2376540T3 - Compresión de imagen por dct de tamaño de bloque adaptativo en base a la varianza.

Info

Publication number: ES2376540T3
Application number: ES00977131T
Authority: ES
Inventors: Kadayam Thyagarajan; Michael J. Merritt
Original assignee: Qualcomm Inc
Current assignee: Qualcomm Inc
Priority date: 1999-11-08
Filing date: 2000-11-08
Publication date: 2012-03-14
Anticipated expiration: 2020-11-08
Also published as: US6529634B1; EP1230804B1; CN1186942C; AR033655A1; KR20030036129A; IL149455A; IL149455A0; RU2273112C2; CA2389410A1; MXPA02004577A; JP2012199963A; TW517500B; WO2001035673A1; ATE538598T1; JP5384696B2; CA2389410C; ZA200203276B; JP5289659B2; AU1481101A; JP2003523652A

Abstract

Un procedimiento para la determinación de una asignación de tamaño de bloque para un bloque entrante de píxeles de imagen que va a ser utilizado en la compresión de dicho bloque entrante, que comprende las etapas de: la lectura de un boque de datos de píxeles; la generación de una asignación de tamaño de bloque para el bloque de datos de píxeles en base a las varianzas de los valores de píxeles de dicho bloque de datos de píxeles y de bloques subdivididos de dicho bloque de datos de píxeles, en el que dicha etapa de generación comprende así mismo las etapas de: la determinación de una varianza de valores de píxeles para dicho bloque de datos de píxeles, en el que la varianza se calcula sobre todos los píxeles del bloque; la comparación de dicha varianza con un umbral, en el quel dicho umbral es una función del valor de píxel medio del bloque que está siendo evaluado; la toma de una decisión para subdividir dicho bloque si dicha varianza es mayor que dicho umbral; si dicha decisión es la de subdividir dicho bloque, entonces la repetición de las etapas de determinación, comparación y toma de decisión para cada bloque subdividido hasta que se satisfaga un criterio predeterminado; y la designación como dicha asignación de tamaño de bloque a cada bloque que no está más subdividido; y la provisión de una estructura de datos que contenga la información acerca de dicha asignación de tamaño de bloque.

Description

Compresion de imagen por DCT de tamaro de bloque adaptativo en base a la varianza

Antecedentes de la invención

I. Campo de la invención

La presente invencion se refiere al campo del procesamiento de imagen. Mas concretamente, la presente invencion se refiere a un esquema de compresion para serales de imagen que utiliza unos bloques y subbloques dimensionados de manera adaptativa de los datos de coeficientes codificados de la transformada de coseno discreta.

II. Descripción de la técnica relacionada

En el campo de la transmision y recepcion de serales de video tal y como se utilizan para la proyeccion de "filmes"

o "peliculas", se han realizado diversas mejoras respecto de las tecnicas de compresion de imagen. Muchos de los sistemas de video actuales y propuestos hacen uso de tecnicas de codificacion digital. La codificacion digital proporciona una robustez en el enlace de comunicaciones la cual ofrece resistencia a problemas tales como el desvanecimiento por multitrayectoria y la perturbacion o la transferencia de la seral, cada una de las cuales podria en otro caso provocar una seria degradacion de la calidad de la imagen. Asi mismo, las tecnicas digitales facilitan el uso de tecnicas de encriptacion de la seral, las cuales han resultado utiles o incluso necesarias en aplicaciones gubernamentales y en otras muchas de difusion comercial recientemente desarrolladas.

El video de alta definicion es un area que aprovecha las tecnicas mejoradas de compresion de imagenes. Cuando se propuso por primera vez, la transmision por las ondas del video de alta definicion (o incluso la transmision cableada o por fibra optica parecio escasamente practica debido a los excesivos condicionamientos del ancho de banda. Los sistemas de transmision inalambricos tipicos, o de otro tipo que se estaban diserando no se ajustaban con facilidad en la medida suficiente al ancho de banda. Sin embargo, se ha llegado al convencimiento de que la compresion de serales de video digitales puede conseguirse hasta un nivel que permita la transmision utilizando anchos de banda razonables. Dichos niveles de compresion de la seral, acoplados con la transmision digital de la seral, permitira un sistema de video que transmita con menor potencia y con una mayor inmunidad respecto de las perturbaciones del canal ocupando al tiempo un ancho de banda mas conveniente y util.

Una tecnica de compresion capaz de ofrecer niveles significativos de compresion preservando al tiempo el nivel de calidad deseado de las serales de video utiliza un bloque y unos subbloques dimensionados de forma adaptativa de los datos de coeficientes codificados de la Transformada de Coseno Discreta (DCT). Esta tecnica se designara en lo sucesivo como el procedimiento de la Transformada de Coseno Diferencial del Tamaro de Bloque Adaptativo (ABSDCT). Esta tecnica se divulga en la Patente estadounidense No. 5,021,891, titulada "Procedimiento y Sistema de Compresión de Imágenes del Tamaño de Bloque Adaptativo” ["Adaptative Block Size Image Compression Method And System”1 transferida al cesionario de la presente invencion. Las tecnicas de DCT se divulgan, asi mismo, en la Patente estadounidense No. 5,107,345, titulada "Procedimiento Y Sistema de Compresión de Imágenes del tamaño de Bloque Adaptativo” ["Adaptative Block Size Image Compression Method And System”1 transferida al cesionario de la presente invencion. Asi mismo, el uso de la tecnica ABSDCT en combinacion con la tecnica de la Transformada de Arbol Cuaternario Diferencial se analiza en la Patente estadounidense No. 5,452,104, titulada "Procedimiento Y Sistema de Compresión de Imágenes del tamaño de Bloque Adaptativo” ["Adaptative Block Size Image Compression Image Method And System”1, transferido, tambien al cesionario de la presente invencion. Los sistemas divulgados en estas patentes utilizan lo que se designa como una codificacion "intertramass", en la que cada trama de los datos de imagen es codificada sin consideracion al contenido de cualquier otra trama. Al utilizar la tecnica ABSDCT, puede ser reducida la tasa de transmision de datos obtenible desde alrededor de 1,5 miles de millones de bits por segundo hasta aproximadamente 50 millones de bits por segundo sin una degradacion apreciable de la calidad de la imagen.

La tecnica ABSDCT puede ser utilizada para comprimir una imagen o seral ya sea en blanco o negro o en color que represente la imagen. La seral entrante de color puede concretarse en un formato YIQ, siendo Y la luminancia, o el brillo, la muestra, y siendo I y Q la crominancia o el color, las muestras para cada bloque de pixeles de 4 x 4. Pueden, asi mismo, ser utilizados otros formatos conocidos como por ejemplo los formatos YUV o RGB. Debido a la baja sensibilidad espacial del ojo al color, la mayor parte de la investigacion ha mostrado que una submuestra de los componentes de color mediante un factor de cuatro en las direcciones horizontal y vertical es razonable. De acuerdo con ello, una seral de video puede ser representada por cuatro componentes de luminancia y dos componentes de crominancia.

Utilizando la ABSDCT, una seral de video resultara segmentada, en terminos generales, en bloques de pixeles para su procesamiento. Para cada bloque, los componentes de luminancia y crominancia son transferidos a un intercalador de bloques. Por ejemplo, un bloque de 16 x 16 (pixeles) puede ser presentado al intercalador de bloques, el cual ordena y organiza las muestras de imagenes dentro de cada bloque de 16 x 16 para producir bloques y subbloques compuestos de datos para el analisis de la transformada de coseno discreta (DCT). El operador de la DCT es un procedimiento de conversion de una seral muestreada en funcion del tiempo en una representacion frecuencial de la misma seral. Mediante la conversion en una representacion frecuencial, las tecnicas de la DCT se ha demostrado que permiten muy elevados niveles de compresion, en cuanto unos cuantificadores pueden ser diserados para aprovechar las caracteristicas de distribucion de frecuencias de una imagen. En una forma de realizacion, DCT de 16 x 16 es aplicada en una primera ordenacion, cuatro DCTs de 8 x 8 son aplicadas en una segunda ordenacion. 16 DCTs de 4 x 4 son aplicadas en una tercera ordenacion y 64 DCTs de 2 x 2 son aplicadas en una cuarta ordenacion.

La operacion de la DCT reduce la redundancia espacialinherente en la fuente de video. Despues de que se ha llevado a cabo la DCT, la mayoria de la energia de las serales de video tiende a concentrarse en unos pocos coeficientes de la DCT. Una transformada adicional, la Transformada de Arbol Cuaternario Diferencial (DQT), puede ser utilizada para reducir la redundancia entre dos coeficientes de la DCT.

Para el bloque de 16 x 16 y para cada subbloque, los valores de los coeficientes de la DCT y el valor de la DQT (si se ut iliza l a D QT) so n anal izados para d eterminar el numero d e bi ts r equerido par a co dificar el bloque o el subbloque. A continuacion, el bloque o la combinacion de subbloques que requiera la codificacion del menor numero posible de bits, es elegido para representar el segmento de imagen. Por ejemplo, dos subbloques de 8 x 8, seis subbloques de 4 x 4 y ocho subbloque de 2 x 2 pueden ser elegidos para representar el segmento de imagen.

El bloque o combinacion de subbloques elegido es, a continuacion, adecuadamente dispuesto por orden en un bloque de 16 x 16. Los valores de los coeficientes de las DCT / DQT pueden a continuacion ser sometidas a una ponderacion de frecuencias, a una codificacion y a una cuantificacion (como por ejemplo una codificacion de longitud variable) como preparacion para la transmision.

Aunque la tecnica ABSDCT descrita con anterioridad funciona sorprendentemente bien, es intensiva desde el punto de vista computacional. Asi, puede resultar dificil la implementacion de la tecnica con un hardware compacto. Se desea una tecnica alternativa que consiga una implementacion del hardware mas eficiente. Un procedimiento y un sistema de compresion de imagen que es mas eficiente desde el punto de vista computacional se proporciona mediante la presente invencion de la manera descrita en las lineas que siguen.

El trabajo "Compresion de Imagen Segmentacion de Tamaros de Bloque Variables" ["Image Compression with Variable Block Size Segmentation"1, de Vaisey J. et al., IEEE Transactions on SignalProcessing, vol. 40, No. 8 agosto de 1 992, p aginas 2040 - 2060 descr ibe un pr ocedimiento d e co mpresion de i magen m ediante la segmentacion de una imagen en zonas de tamaros diferentes.

Divulga un procedimiento para la determinacion de una asignacion de tamaro de bloque para un bloque de entrada de l os pixeles de imagen q ue va n a se r ut ilizados en l a co mpresion del b loque entrante, co mprendiendo e l procedimiento las etapas de lectura de un bloque de datos de pixeles, la generacion de una asignacion de tamaro de bloque para los bloques de los datos de pixeles basados en las varianzas de los valores de los pixeles de dichos bloque de datos de pixeles y de los bloques subdivididos de dicho bloque de datos de pixeles, en el que la etapa de generacion adicional comprende las etapas de la determinacion de una varianza de valores de pixeles para dicho bloque de datos de pixeles en el que la varianza se calcula sobre todos los pixeles del bloque; la comparacion de dicha varianza con un umbral; la toma de una decision para subdividir dicho bloque si dicha varianza es mayor que dicho um bral; si dicha decision es l a s ubdividir d icho bl oque, l a r epeticion e ntonces de l as etapas d e l a determinacion, la comparacion y la toma de decision para cada bloque subdividido hasta que se satisfaga un criterio predeterminado; y la designacion como asignacion del tamaro del bloque de cada bloque que no se subdivide mas; y la provision de una informacion que contiene una estructura de datos sobre dicha asignacion del tamaro del bloque.

Sumario de la invención

La presente invencion se refiere a un procedimiento para la determinacion de la asignacion del tamaro del bloque para un bloque entrante de pixeles de imagen de acuerdo con lo definido en la reivindicacion 1, y a un sistema de compresion de imagen de acuerdo con lo definido en la reivindicacion 12.

La presente invencion es un sistema y un procedimiento de compresion de imagen que utiliza unos bloques y unos subbloques dimensionados de manera adaptativa de unos datos de coeficientes de la Transformada de Coseno Discreta. E n u na f orma de r ealizacion, el bloque d e pi xeles de 16 x 16 es introducido e n un co dificador. E l codificador comprende un elemento de asignacion del tamaro del bloque, el cual segmenta el bloque de pixeles entrante para su procesamiento. La asignacion del tamaro del bloque se basa en las varianzas del bloque entrante y de los bloques subdivididos. En general, las areas con mayores varianzas seran subdivididas en bloques mas pequeros, mientras que las areas con varianzas menores no seran subdivididas, con tal de que los valores medios de los bloques y de los subbloques se incluyan en unos margenes diferentes predeterminados.

De esta manera, en primera lugar, el umbral de la varianza de un bloque es modificado a partir de su valor nominal, dependiendo de su valor medio y, a continuacion, la varianza del bloque es comparada con un umbral, y si la varianza es mayor que el umbral, entonces el bloque se subdivide.

La asignacion del tamaro del bloque se proporciona a un elemento de la transformada, el cual transforma los datos de pixeles en datos en el dominio secuencial. La transformada se lleva a cabo solo sobre el bloque y los subbloques seleccionados mediante la asignacion del tamaro del bloque. Los datos de la transformada, a continuacion, son sometidos a una cuantificacion y a una serializacion. Por ejemplo, puede ser utilizado un escaneo en zigzag para serializar los datos para producir un flujo de datos. El flujo de datos puede, a continuacion, ser codificado mediante un codificador de longitud variable como preparacion para la transmision. Los datos codificados son enviados a

5 traves de un canal de transmision hasta un descodificador, donde los datos de pixeles son reconstruidos como preparacion para su representacion.

Breve descripción de los dibujos

Las caracteristicas distintivas, los objetivos y las ventajas de la presente invencion se pondran de manifiesto de forma mas acabada a partir de la descripcion detallada expuesta en las lineas que siguen tomada en combinacion

10 con los dibujos, en los cuales los mismos caracteres de referencia identifican los correspondientes elementos a lo largo de todos los dibujos, y en los que:

La FIG. 1 es un diagrama de bloques de un sistema de procesamiento de imagen que incorpora el sistema y el procedimiento de la presente invencion de asignacion del tamaro del bloque en base a la varianza;

la FIG. 2 es un diagrama de flujo que ilustra las etapas de procesamiento implicadas en la asignacion del 15 tamaro del bloque en base a la varianza;

las FIGS. 3a, 3b y 3c ilustran u na asi gnacion del tamaro d el bloque ej emplar, l a co rrespondiente descomposicion de arbol cuaternario, y los correspondientes datos de PQR.

Descripción detallada de las formas de realización preferentes

Con el fin de facilitar la transmision digital de serales digitalesydisfrutar de los correspondientes beneficios,es

20 necesario, e n terminos generales, em plear al guna f orma de co mpresion de la seral. P ara co nseguir un a a lta definicion en la imagen resultante es, asi mismo, de importancia que se mantenga la alta calidad de la imagen. Asi mismo, se desea una eficiencia computacional para una implementacion con un hardware compacto, lo que es importante en muchas aplicaciones.

La presente invencion proporciona un sistema o un aparato y un procedimiento de compresion de imagen que toma

25 en cuenta tanto la calidad de la imagen como la eficiencia computacional en la ejecucion de la compresion de la imagen. La compresion de la imagen de la presente invencion se basa en tecnicas de la Transformada de Coseno Discreta (DCT). En general, una imagen que va a ser procesada en el dominio digital estaria compuesta por unos datos de pixeles en un conjunto de bloques no superpuestos, de tamaro N x N. Una DCT de dos dimensiones puede ejecutarse sobre cada bloque. La DCT de dos dimensiones se define mediante la siguiente relacion:

35 donde

40 x(m, n) es la localizacion de los pixeles (m, n) dentro de un bloque N x M, y

X (k, l) es el correspondiente coeficiente de la DCT.

Dado que los valores de los pixeles son no negativos, el componente x (0, 0) de la DCT es siempre positivo, y generalmente tiene la mayor energia. De hecho, para imagenes tipicas, la mayoria de la energia de la transformada se concentra alrededor del componente X (0, 0). Esta propiedad de compactacion de la energia hace que la tecnica

45 de la DCT sea un procedimiento de compresion tan atractivo.

La tecnica de compresion de la imagen de la presente invencion utiliza una codificacion adaptativa de contraste para conseguir una reduccion adicional de latasa de transmision de bits. Se ha observado que las imagenes mas naturales estan compuestas por unas areas planas de variacion relativamente lenta, y unas areas activas como por ejemplo en los limites del objeto y con una textura de gran contraste. Los esquemas de codificacion adaptativos de contraste utilizan este factor mediante la asignacion de mas bits a las areas activas y menos bits a las areas menos activas.

La codificacion ada ptativa de co ntraste, asi m ismo, es util par a l a r educcion de l ef ecto de bl oqueo. E n l a implementacion de otras tecnicas de codificacion de la DCT, el efecto de bloqueo es quizas la perturbacion mas importante para la calidad de la imagen. Asi mismo, el efecto de bloqueo tiende a ser mas perceptible enareas activas de la imagen. Sin embargo, se ha llegado a comprender que el efecto de bloqueo se reduce cuando se utiliza una DCT de menor tamaro. El efecto de bloqueo resulta virtualmente invisible cuando se utiliza una DCT de 2 x 2, aunque pueden resentirse las prestaciones de bit por pixel. De esta manera, la codificacion adaptativa de contraste puede reducir el efecto de bloqueo mediante la asignacion de tamaros de bloque mas pequeros (y con ello de mas bits) hacia las areas activas y tamaros de bloque mayores hacia las areas relativamente vacias.

�tra caracteristica distintivade la presente invencion es que utiliza una codificacion intertramas(procesamiento espacial) en lugar de la codificacion intertramas (procesamiento espacio temporal). Una razon para la adopcion de la codificacion intertramas es la gran complejidad del receptor requerida para procesar las serales de codificacion intertramas. La codificacion intertramas requiere de forma inherente multiples memorias intermedias de trama ademas de unos circuitos de procesamiento mas complejos. En muchas aplicaciones, se necesita una reduccion de la complejidad para la implementacion efectiva.

Una segunda razon para la utilizacion de la codificacion intertramas es que puede existir una situacion,o un material de programa, que pueda provocar que el esquema de codificacion espacio -temporal se estropee y lleve a cabo un rendimiento defectuoso. Por ejemplo, las peliculas de 24 tramas por segundo pueden incluirse dentro de esta categoria dado que el tiempo de integracion, debido al obturador mecanico es relativamente corto. El corto periodo de tiempo de integracion hace posible un grado mas alto de solapamiento temporal. La asuncion de la correlacion de trama a trama se rompe en el caso de un movimiento rapido en cuanto resulta entrecortado.

Una razon adicional para la utilizacion de la codificacion intertramas es un esquema de codificacion espacio temporal es mas dificil de estandarizar cuando estan implicadas frecuencias tanto a 50 �z como a 60 �z de la linea de transporte de energia. La televisionen la actualidad transmite serales ya sea a 50 �z o 60 �z. El uso de un esquema de intertramass, al ser un sistema digital, puede adaptar tanto el funcionamiento a 50 �z como a 60 �z, o incluso para peliculas de 24 tramas por segundo mediante la transaccion entre la tasa de tramas y la resolucion espacial.

A los fines del procesamiento de imagen, la operacion de la DCT se lleva a cabo sobre unos datos depixeles que son divididos en un conjunto de bloques no superpuestos. Notese que, aunque los tamaros de los bloques son analizados en la presente memoria teniendo un tamaro de N x N, se contempla que pueden ser utilizados tamaros de bloques diferentes. Por ejemplo, un tamaro de bloque N x M puede ser utilizado cuando tanto N como M sean numeros enteros, siendo M o bien mayor o menor que N. �tro importante aspecto es que el bloque es divisible en al menos un nivel de subbloques, como por ejemplo N /ixN /i, N / ixN/j , N/ixM/j, etc., cuando i y j sean numeros enteros. Asi mismo, el tamaro de bloque ejemplar, tal y como se analizaen la presente memoria es un bloque de pixeles de 16 x 16 con unos correspondientes bloques y subbloques de coeficientes de la DCT. Se contempla, asi mismo, que pueden ser utilizados otros distintos numeros enteros, como por ejemplo tanto valores de numeros pares como impares, por ejemplo, de 9 x 9.

Con referencia ahora a la FIG. 1, en ella se muestra un sistema 100 de procesamiento de imagen, el cual incorpora el sistema de compresion de la presente invencion. El sistema 100 d e procesamiento de i magen comprende un codificador 102 que comprime una seral de video recibida. La seral comprimida es transmitida por medio de un canal de transmision 104, y es recibida por un descodificador 106. El descodificador 106 descodifica la seral recibida en muestras de la imagen, las cuales pueden a continuacion se representadas.

En general, una imagen es dividida en bloques de pixeles para su procesamiento. Una seral de color puede ser convertida desde el espacio RGB hasta el espacio YC1 C2, siendo Y el componente de luminancia, o de brillo, y siendo C1 y C2 los componentes de la crominancia o el color. Debido a la baja sensibilidad espacial del ojo al color, muchos sistemas submuestrean los componentes C1 y C2 mediante un factor de cuatro en las direcciones horizontal y vertical. Sin embargo, el submuestreo no es necesario. Una imagen de resolucion total, conocida como el formato

4: 4: 4, puede ser o bien muy util o bien necesario en algunas aplicaciones, como por ejemplo las designadas como englobadoras del " cine digital". D os posibles representaciones de Y C1C2 son l a representacion Y IQ y l a representacion YUV, las dos bien conocidas en la tecnica. Asi mismo, es posible emplear una variante de la representacion YUV conocida como YCbCr.

En una forma de realizacion preferente, cada uno de los componentes Y, Cb y Cr es procesado sin submuestreo. De esta manera, se suministra una entrada de un bloque de pixeles de 16 x 16 al codificador 102. El codificador 102 comprende un elemento 108 de asignacion de tamaro de bloque, el cual efectua la asignacion del tamaro del bloque para la preparacion para la compresion del video. El elemento 108 de asignacion del tamaro del bloque determina la descomposicion del bloque del bloque de 16 x 16 en base a las caracteristicas preceptuales de la imagen del bloque. La asi gnacion del tamaro del bloque subdivide cada bloque de 16 x 16 en bloques mas pequeros en una forma de arbol cuaternario dependiendo de la actividad existente dentro de un bloque de 16 x 16. El elemento 108 de asignacion del tamaro del bloque genera unos datos de arbol cuaternario llamados los datos de PQR, cuya longitud puede oscilar entre 1 y 21 bits. De esta manera, si la asignacion del tamaro del bloque determina que un bloque de 16 x 16 va a ser dividido, se establece el bit R de los datos de PQR, seguidos por cuatro bits adicionales de datos P correspondientes a los cuatro bloquesdivididos de 8 x 8. Si la asignacion del tamaro del bloque determina que ninguno de los bloques de 8 x 8 va a ser subdividido, entonces se araden cuatro bits adicionales de los datos Q para cada bloque de 8 x 8.

Con referencia ahora a la FIG. 2, se ofrece un diagrama de flujo que muestra detalles de la interaccion del elemento 108 de asignacion del tamaro del bloque. El algoritmo utiliza la varianza de un bloque como una metrica en la decision de subdividir un bloque. Comenzando en la etapa 202, se lee un bloque de pixeles de 16 x 16. En la etapa 204, se computa la varianza, v16, del bloque de 16 x 16. La varianza se computa como sigue:

donde N = 16, y xij es el pixel de la fila iesima, la columna jotaesima dentro del bloque N x N. En la etapa 206, en primer lugar, se modifica el umbral de varianza T16 para proporcionar un nuevo umbral T'16 si el valor medio del bloque se situa entre dos valores predeterminados, a continuacion la varianza del bloque es comparada con el nuevo umbral, T'16.

Si la varianza v16 no es mayor que el umbral T16, entonces, en la etapa 208, se escribe la direccion de comienzo del bloque de 16 x 16, y el bit R de los datos de PQR se establece en 0 para indicar que el bloque de 16 x 16 no esta subdividido. El algoritmo a continuacion lee el siguiente bloque de pixeles de 16 x 16. Si la varianza v16 es mayor que el umbral T16, entonces, en la etapa 210, el bit R de los datos de PQR se establece en 1, para indicar que el bloque de 16 x 16 va a ser subdividido en cuatro bloques de 8 x 8.

Los cuatro bloques de 8 x 8 , i = 1: 4, son considerados de forma secuencial para una division ulterior, tal y como se muestra en la etapa 212. Para cada bloque de 8 x 8, la varianza, v8i, es computada, enla etapa 214. En la etapa 216, el primer umbral de varianza T8 es modificado para proporcionar un nuevoumbral T'8 si el valor medio del bloque se situa entre dos valores predeterminados, entonces la varianza del bloque se compara con este nuveo umbral.

Si la varianza v81no es mayor que el umbral T8 entonces, en la etapa 218 se escribe la direccion de inicio del bloque de 8 x 8, y el correspondiente bit Q, Qi se fija en 0. El siguiente bloque de 8 x 8 es entonces procesado. Si la varianza v8i es mayor que el umbral T8, entonces, en la etapa 220, el correspondiente bit Q, Qi, se establece en 1 para indicar que el bloque de 8 x 8 va a ser subdivido en cuatro bloques de 4 x 4.

Los cuatro bloques 4 x 4, ji = 1 : 4, son considerados de forma secuencial para una ulterior division, tal y como se muestra en la etapa 222. Para cada bloque de 4 x 4, la varianza, v4ij, es computada, en la etapa 224. En la etapa 226, en primer lugar el umbral de varianza T4 es modificada para proporcionar un nuevo umbral T'4 si el valor medio del bloque se situa entre dos valores predeterminados, a continuacion la varianza del bloque es comparada con este nuevo umbral.

Si la varianza v4ij no es mayor que el umbral T4, entonces, en la etapa 228, se escribe la direccion del bloque de 4 x 4, y el correspondiente bit P, Pij, se establece en 0. El siguiente bloque de 4 x 4 es a continuacion procesado. Si la varianza v4ij es mayor que el umbral T4, entonces, en la etapa 230, el correspondiente bit P, Pij, se establece en 0 para indicar que el bloque de 4 x 4 va a ser subdividido en 4 bloques de 2 x 2. Asi mismo, se escribe la direccion de los 4 bloques de 2 x 2.

Los umbrales T16, T8 y T4 pueden serunas constantes predeterminadas. Esto es conocido como decision dura. Como alternativa, puede ser implementada una decision adaptativa o suave. La decision suave varia los umbrales de las varianzas dependiendo del valor medio de los pixeles de los bloques 2N x 2N, donde N puede ser 8, 4 o 2. De esta manera, las funciones de los valores medios de los pixeles pueden ser utilizadas como umbrales.

Con fines ilustrativos, considerese el siguiente ejemplo. Supongase que los umbrales de varianza predeterminados del componente Y sean 50, 1100 y 880, respectivamente, para los bloques de 16 x 16, 8 x 8 y 4 x 4. En otras palabras, T16 = 50, T8 = 1100 yT14 = 880. Supongase que el rango de los valores medios sea de 80 y 100. Supongase que la varianza computada para el bloque de 16 x 16 es 60. Dado que 60 y su valor medio 90 es mayor que T16, el bloque de 16 x 16 es subdividido en cuatro subbloques de 8 x 8. Supongase que las varianzas computadas para los bloques de 8 x 8 son 1180, 935, 980, y 1210. Dado que dos de los bloques de 8 x 8 presentan unas varianzas que exceden de T8, estos dos bloques se dividen a su vez para obtener un total de ocho subbloques de 4 x 4. Finalmente, supongase que las varianzas de los ocho bloques de 4 x 4 son 620, 630, 670, 610, 590, 525, 930 y 690, con unos correspondientes valores medios de 90, 120, 110, 115. Dado que el valor medio del primer bloque de 4 x 4 cae en el rango (80, 100), su umbral se reducira hasta T''4 = 200 que es menor de 880. De esta manera, este bloque de 4 x 4 sera subdivido asi como el septimo bloque de 4 x 4. La asignacion de tamaros de bloques resultantes se muestra en la FIG. 3a. La correspondiente descomposicion de arbol cuaternario se muestra en la FIG. 3b. Asi mismo, los datos de PQR generados por esta asignacion de tamaros de bloques se muestra en la FIG. 3c.

Notese que un procedimiento similar es utilizado para asignar tamaros de bloques para los componentes de color C1 y C2. Los componentes de color pueden ser decimados horizontal, verticalmente, o en ambos sentidos.

Asi mismo, notese que, aunque la asignacion de tamaros de bloques ha sido descrita como un sistema de arriba abajo, en el cual el bloque de mayor tamaro (de 16 x 16 en el presente ejemplo), es utilizado en primer termino, puede utilizarse en su lugar un sistema de abajo arriba. El sistema de abajo arriba evaluara en primer termino los bloques mas pequeros, (de 2 x 2 en el presente ejemplo).

Con referencia de nuevo a la FIG. 1, se describira el resto del sistema 110 de procesamiento de imagen. Los datos de PQR, junto con las direcciones de los bloques seleccionados, se suministran a un elemento 110 de DCT de la DCT. El elemento 110 de la DCT utiliza los datos de PQR para llevar a cabo las transformadas de coseno discretas de l os tamaros apropiados so bre l os bloques seleccionados. S olo los bloques seleccionados necesitan se r sometidos al procesamiento de la DCT.

El sistema 100 de procesamiento de imagen puede de manera opcional comprender el elemento DCT 112 para la reduccion de la redundancia entre los coeficientes de DC de las DCTs. Un coeficiente de DC se encuentra en la esquina superior izquierda de cada bloque de la DCT. Los coeficientes de la DCT son, en general, de gran tamaro en comparacion con los coeficientes de AC. La discrepancia en cuanto a los tamaros hace dificil diserar un codificador d e l ongitud v ariable ef iciente. De acuerdo c on ello, es ve ntajoso r educir l a r edundancia entre los coeficientes DC.

El elemento 112 de la DQTlleva a cabounas DCTsde 2 -D sobre los coeficientesde DC, tomados 2 x 2 a un tiempo. Empezando por los bloques de 2 x 2 dentro de los bloques de 4 x 4 se lleva a cabo una DCT de 2 -D sobre cuatro coeficientes de DC. Esta DCT de 2 x 2 se denomina la transformada de arbol cuaternario diferencial, o DQT, de cuatro coeficientes de DC. A continuacion, el coeficiente de DC de la DQT junto con los tres coeficientes de DC con un bloqueo de 8 x 8 son utilizados para compactar la DQT del nivel siguiente. Finalmente, los coeficientes de DC de los cuatro bloques de 8 x 8 dentro de un bloque de 16 x 16 son utilizados para computar la DQT. De esta manera, en un bloque de 16 x 16, hay un autentico coeficiente de DC y el resto son coeficientes de AC correspondientes a la DCT y a la DQT.

Los coeficientes de la transformada ( tanto de la DCT como de la DQT), son suministrados a un cuantificador 114 para su c uantificacion. E n u na f orma d e r ealizacion preferente, los co eficientes de la D CT so n c uantificados utilizando unas mascaras de ponderacion de frecuencias (FWMs) y un factor de cuantificacion de escala. Una FWM es una tabla de ponderaciones de frecuencias de las mismas dimensiones que el bloque de los coeficientes de entrada de la DCT. Las ponderaciones de frecuencias aplican diferentes ponderaciones a los diferentes coeficientes de la DCT. Las ponderaciones estan diseradas para otorgar importancia a las muestras entrantes que presentan un contenido de frecuencias respecto de las cuales el sistema visual humano es mas sensible y para quitar importancia a las muestras que presentan un contenido de frecuencias a las que el sistema visual es menos sensible. Las ponderaciones pueden, asi mismo, ser diseradas en base a factores tales como las distancias de visualizacion, etc.

Las ponderaciones son seleccionadas en base a datos empiricos. Un procedimiento para diserar las mascaras de ponderacion para los coeficientes de la DCT de 8 x 8 se divulga en el documento IS� / IEC JTCA CD 10918 "Compresion y codificacion Digital de imagenes fijas de tono continuo -parte 1: Condiciones y directrices" ["Digital Compression and Encoding of Continuus - tone still images - part 1: Requirements and guidelines"1 International Standards �rganization, 1994. En general. Se diseran dos FWMs, una para el componente de luminancia y otra para los componentes de crominancia. Las tablas de FWM para los tamaros de bloques de 2 x 2 , 4 x 4 se obtienen por decimacion y el de 16 x 16 por interpolacion para el del bloque de 8 x 8. El factor de escala controla la calidad y la tasa de transmision de datos de los coeficientes cuantificados.

De esta manera, cada coeficiente de la DCT es cuantificado de acuerdo con la relacion: donde DTC (i, j) es el coeficiente de la DTC entrante , fwm (i, j) es la mascara de ponderacion de frecuencias, q es el factor de escala yDCTq (i,j) es el coeficiente cuantificado. Notese que, dependiendo del signo del coeficiente de la DCT, el primer termino situado dentro de los corchetes es redondeado arriba o abajo. Los coeficientes de la DQT son, asi mismo, cuantificados utilizando una mascara de ponderacion apropiada. Sin embargo, pueden ser utilizadas multiples tablas o mascaras, y aplicadas a cada uno de los componentes Y, Cb y Cr.

Los coeficientes cuantificados son suministrados a un serializador 116 de escaneo en zigzag. El serializador 116 escanea los bloques de los coeficientes cuantificados de una forma en zigzag para producir un flujo serializado de coeficientes cuantificados. Asi mismo puede ser escogida una pluralidad de pautas de escaneo en zigzag diferentes, asi como de pautas en zigzag distintas. Una tecnica preferente, emplea unos tamaros de bloque de 8 x 8 para el escaneo en zigzag aunque pueden ser empleados otros tamaros.

Notese que e l se rializador 116 de escaneo e n zi gzag pue de s er si tuado o bien antes o bi en despues del cuantificador 114. Los resultados netos son los mismos.

En cualquier caso, el flujo de coeficientes cuantificados es suministrado a un codificador 118 de longitud variable. El codificador 118 de longitud variable puede hacer uso de una codificacion de ceros de longitud de recorrido seguida por una codificacion de �uffman. Esta tecnica se analiza con detalle en las Patentes estadounidenses anteriormente mencionadas 5,021,891, 5,107,345 y 5,452,104, y ahora se expone de forma resumida en la presente memoria. Un codificador de longitud de recorrido tomaria los coeficientes cuantificados y separaria los coeficientes nulos de los no nulos. Los valores nulos son designados como valores de longitud de recorrido y son codificados mediante el sistema de �uffman. Los valores no nulos son codificados por el sistema �uffman de forma separada.

Una codificacion de �uffman modificada de los coeficientes cuantificados es, asi mismo, posible, y es utilizada en la forma de realizacion preferente. Aqui, despues del escaneo en zigzag, un codificador de longitud de recorrido determinara los pares de longitud de recorrido / tamaro dentro de cada bloque de 8 x 8. Estos pares de longitud de recorrido / tamaro son a continuacion codificados por el sistema de �uffman.

Los codigos de �uffman estan diserados a partir de estadisticas ya sea medidas o ya sea teoricas de una imagen. Se ha observado que las imagenes mas naturales estan compuestas por areas en blanco o por areas de variacion relativamente l enta, y p or ar eas ocupadas, co mo p or e jemplo los limites de dos ob jetos y l a t extura d e gr an contraste. Los codificadores de �uffman con transformadas en el dominio frecuencial, por ejemplo, la DCT, explotan estas caracteristicas mediante la asignacion de mas bits a las areas mas ocupadas y de menos bits a las areas en blanco. En general, los codificadores de �uffman hacen uso de tablas de consulta para codificar los valores de longitud de recorrido y los no nulos. En general se utilizan multiples tablas, siendo 3 tablas preferentes en la presente invencion, aunque, si se desea, pueden ser empleadas 1 o 2.

La seral de imagen comprimida generada por el codificador 102 es transmitida al descodificador 106 por medio del canal de transmision 104. Los datos de PQR, los cuales contienen la informacion de la asignacion de los tamaros de los bloques es, asi mismo, suministrada al descodificador 106. El descodificador 106 comprende un descodificador 120 de longitud variable, el cual descodifica los valores de longitud de recorrido y los valores no nulos.

La salida del descodificador 120 de longitud variable se suministra a un serializador inverso 122 de escaneo en zigzag que ordena los coeficientes de acuerdo con el esquema de escaneo empleado. El serializador inverso 122 de escaneo en zigzag recibe los datos de PQR para ayudar a la ordenacion adecuada de los coeficientes para obtener un bloque de coeficientes compuesto.

El bloque compuesto es suministrado a un codificador inverso 124 para deshacer el procesamiento debido al uso de las mascaras de ponderacion de frecuencias.

El bloque de coeficientes es a continuacion suministrado a un elemento 126 de la IDQT, seguido por un elemento 128 de la IDCT, si se ha aplicado la transformada de Arbol Cuaternario Diferencial. En otro caso, el bloque de coeficientes es suministrado directamente al elemento 128 de la IDCT. El elemento 126 de la IDQT y el elemento 128 de la IDCT efectuan una transformacion inversa de los coeficientes para producir un bloque de datos de pixeles . Los datos de pixeles , pueden, a continuacion, tener que ser interpolados,convertidos enformade RGB y, a continuacion, almacenados para su representacion futura.

De acuerdo con ello, se presenta un sistema y un procedimiento para la compresion de imagen que lleva a cabo una asignacion del tamaro de los bloques en base a una varianza de pixeles. La asignacion del tamaro de los bloques en base a la varianza ofrece diversas ventajas. Debido a que la Transformada de Coseno Discreta selleva a cabo despues de que los tamaros de los bloques son determinados, se consigue una computacion eficiente. La transformada intensiva de forma computacional solo necesita llevarse a cabo sobre los bloques seleccionados. Asi mismo, el procedimiento de seleccion de bloques es eficiente, en cuanto la varianza de los valores de los pixeles es matematicamente sencilla de calcular. �tra ventaja adicional de la asignacion del tamaro de los bloques en base a la varianza es que esta basada de forma perceptual. La varianza de los pixeles es una medida de la actividad existente en un bloque y, proporciona una indicacion de la presencia de los bordes, las texturas, etc. Tiende a captar los detalles de un bloque mucho mejor que mediciones tales como la media de los valores de los pixeles. De esta manera, el esquema en base a la varianza de la presente invencion asigna bloques mas pequeros a zonas con mas bordes y bloques de mayor tamaro a las zonas mas planas. Como resultado de ello, puede conseguirse una calidad sobresaliente de las imagenes reconstruidas.

�tra ventaja importante adicional es que, dado que la asignacion del tamaro de los bloques se efectua antes de la cuantificacion, se obtiene una flexibilidad mayor en el control de la tasa de transmision de bits y de la calidad. Dado 5 que el umbral de la varianza esta adaptado a la media local, se asignan bloques pequeros incluso en areas relativamente oscuras. Esto preserva los detalles en todas las areas que estan por encima exactamente del umbral de visibilidad perceptible. Asi mismo, la compresion de imagen en base a la varianza proporciona una degradacion vistosa de la calidad de la imagen cuando el factor de cuantificacion de escala se modifica de valores bajos a valores altos, a diferencia de procedimientos tales como el MPEG. Esto es especialmente critico en aplicaciones tales como

10 en el area del cine digital.

Dada la gran demanda de video digital, la pirateria es una serie amenaza. El marcado con agua digital es un requisito importante para disuadir la violacion de los derechos de autor y de la perdida de ingresos. El marcaje con agua se lleva a cabo en areas de una imagen que son perceptiblemente significativas, la asignacion de tamaros de bloques en base a la varianza es un candidato para el marcaje con agua.

Claims

REIVINDICACIONES

1.- Un procedimiento para la determinacion de una asignacion de tamaro de bloquepara un bloque entrante de pixeles de imagen que va a ser utilizado en la compresion de dicho bloque entrante, que comprende las etapas de:

la lectura de un boque de datos de pixeles; la generacion de una asignacion de tamaro de bloque para el bloque de datos de pixeles en base a las varianzas de los valores de pixeles de dicho bloque de datos de pixeles y de bloques subdivididos de dicho bloque de datos de pixeles, en el que dicha etapa de generacion comprende asi mismo las etapas de:

la determinacion de una varianza de valores de pixeles para dicho bloque de datos de pixeles, en

el que la varianza se calcula sobre todos los pixeles del bloque; la comparacion de dicha varianza con un umbral, en el quel dicho umbral es una funcion del valor de pixel medio del bloque que esta siendo evaluado;

la toma de una decision para subdividir dicho bloque si dicha varianza es mayor que dicho umbral; si di cha d ecision es la de subdividir di cho bl oque, ent onces la r epeticion de l as etapas de

determinacion, co mparacion y t oma de decision p ara c ada bloque s ubdividido has ta que s e satisfaga un criterio predeterminado; y la designacion como dicha asignacion de tamaro de bloque a cada bloque que no esta mas

subdividido; y la provision de una estructura de datos que contenga la informacion acerca de dicha asignacion de tamaro de bloque. 2.- Un procedimiento para la compresionde un bloque de datos de pixeles de una imagen, que comprende las etapas de:

la determinacion de una asignacion de tamaro de bloque para el bloque de datos de pixeles de acuerdo con el procedimiento de la reivindicacion 1; la transformacion de dichos datos de pixeles de bloques seleccionados de acuerdo con lo indicado por

dicha estructura de datos en una representacion en el dominio frecuencial; la cuantificacion de dichos datos en el dominio frecuencial; el escaneo de dichos datos cuantificados para obtener un flujo serializado de datos; y la codificacion de dicho flujo serializado de datos en preparacion para una transmision.
3.- El procedimiento de la reivindicacion 2, en el que la Transformada de Coseno Discreta se lleva a cabo seguida

por una Transformada de Arbol Cuaternario Diferencial durante dicha etapa de transformacion. 4.- El procedimiento de la reivindicacion 2, en el que una Transformada de Coseno Discreta se lleva a cabo seguida por una Transformada de Arbol Cuaternario Diferencial durante dicha etapa de transformacion.
5.- El procedimiento de la reivindicacion 2, en el que se lleva a cabo un escaneo en zigzag durante dicha etapa de

escaneo. 6.- El procedimiento de la reivindicacion 5, en el que el escaneo en zigzag se lleva a cabo utilizando un tamaro de bloque de 8 x 8.
7.- El procedimiento de la reivindicacion 2, en el que se lleva a cabo una codificacion de �uffman durante dicha

etapa de codificacion. 8.- El procedimiento de la reivindicacion 7, en el que dicha codificacion de �uffman emplea multiples tablas de consulta para codificar valores de longitud de recorrido y no nulos.
9.- El procedimiento de la reivindicacion 8, en el que hay tres tablas de consulta. 10.- El procedimiento de las reivindicaciones 1 o 2, en el que dicho umbral cambia para cada nivel de subdivision. 11.- El procedimiento de las reivindicaciones 1 o 2, en el que dicho criterio predeterminado para no seguir repitiendo

las etapas de det erminacion, co mparacion y t oma d e deci siones, se basa en u n tamaro de b loque m inimo preseleccionado de datos de pixeles.
12.- Un sistema de compresion de imagen para comprimir un bloque de datos de pixeles, que comprende:

un medio de asignacion detamaro de bloque para la seleccion de dicho bloque o de dichos bloques subdivididos de dicho bloque que va a ser comprimido en base a las varianzas de los valores de pixeles de dicho bloque de datos de pixeles y de bloques subdivididos de dicho bloque de datos de pixeles, en el que dicho medio de asignacion de tamaro de bloque:

determina una varianza de valores de pixeles para dicho bloque de datos de pixeles, en el que la varianza se calcula sobre todos los pixeles del bloque, compara dicha varianza con un umbral, en el que dicho umbral es una funcion del valor de pixel medio del bloque que esta siendo evaluado;

la toma de una decision para subdividir dicho bloque si dicha varianza es mayor que dicho umbral, si dicha decision es la de subdividir dicho bloque, a continuacion repite la determinacion de la varianza, la comparacion con un umbral, y la decision de subdividir para cada bloque subdivido hasta que satisfaga un criterio predeterminado; y

designa como dicha asignacion de tamaro de bloque cada bloque que no se subdivide mas

un medio de transformacion para la transformacion del tamaro de pixeles de dicho bloque seleccionado o de dichos bloques subdivididos en datos en el dominio frecuencial;

un medio cuantificado para la cuantificacion de dichos datos en el dominio frecuencial;

un medio de serializador para escanear dichos datos cuantificados para obtener un flujo serializado de datos; y

un medio de codificacion de longitud variable para la codificacion de dicho flujo de datos serializado en preparacion para la transmision.
13.- El sistema de la reivindicacion 12, en el que dicho umbral cambia para cada nivel de subdivision.
14.- El sistema de la reivindicacion 12, en el que dicho criterio predeterminado para no seguir subdividendo se basa en un tamaro de bloque minimo preseleccionado de los datos de pixeles que estan siendo conseguidos.
15.- El sistema de la reivindicacion 12, en el que dicho medio de transformacion lleva a cabo una Transformada de Coseno Discreta.
16.- El sistema de la reivindicacion 12, en el que dicho medio de transformacion lleva a cabo una Transformada de Coseno Discreta seguida por una Transformada de Arbol Cuaternario Diferencial.
17.- El sistema de la reivindicacion 12, en el que dicho medio serializador comprende un escaneador en zigzag.
18.- El sistema de la reivindicacion 17, en el que el escaneador en zigzag emplea un tamaro de bloque de 8 x 8 para el escaneo en zigzag.
19.- El sistema de la reivindicacion 12, en el que dicho medio de codificacion de longitud variable comprende un codificador de �uffman,
20.- El sistema de la reivindicacion 19, en el que dicho codificador de �uffman emplea multiples tablas de consulta para codificar valores de longitud de recorrido y valores no nulos.
21.- El sistema de la reivindicacion 20, en el que hay tres tablas de consulta.