Procedimiento y dispositivo de codificación y descodificación aritméticas utilizando varias tablas de consulta.

Un dispositivo para codificar aritméticamente un símbolo que hay que codificar que tiene un estado binario basadoen una anchura de intervalo actual R y representando una probabilidad una estimación de probabilidad para elsímbolo que hay que codificar,

en el que la probabilidad del símbolo menos probable PLPS está representada por uníndice de probabilidad para asignar un estado de probabilidad entre una pluralidad de Nmax estados de probabilidadrepresentativos Pn, en el que el dispositivo se caracteriza por:

medios para codificar el símbolo que hay que codificar, que comprende los siguientes medios:

medios para cartografiar la anchura de intervalo actual R con un índice de cuantización de entre una pluralidad de Kíndices de cuantización representativos asociados a anchuras de anchuras de intervalo respectivas Qk; y

medios para realizar la subdivisión de intervalo mediante el acceso a una tabla de división de intervalo compuesta deK*Nmax valores de producto Qk*Pn utilizando el índice de cuantización y el índice de probabilidad para obtener unvalor de la anchura de intervalo parcial.

Procedimiento y dispositivo de codificación y descodificación aritméticas utilizando varias tablas de consulta [0001] La invención se refiere a un procedimiento y a un dispositivo para codificar aritméticamente y descodificar estados binarios y a un programa informático correspondiente y un medio de almacenamiento legible por ordenador correspondiente que puede en particular ser utilizado en la compresión de datos digitales.

La presente invención describe un nuevo procedimiento eficiente para la codificación aritmética binaria. Existe una demanda para la codificación aritmética binaria en la mayoría de áreas de aplicación diferentes de compresión de datos digitales; aquí, en particular, son especialmente interesantes las aplicaciones en los sectores de la compresión de imágenes digitales. En numerosas normas para la codificación de imágenes, como por ejemplo, JPEG, JPEG -2000, JPEG -LS y JPIG, se definieron procedimientos para una codificación aritmética binaria. Las actividades de normalización más nuevas también prevén de manera obvia el uso futuro de estas tecnologías de codificación en el campo de la codificación video (CABAC en H. 264/AVC) [1].

Las ventajas de la codificación aritmética (CA) en contraste con la codificación de Huffman [2] que hasta ahora se había utilizado en la práctica, se pueden caracterizar básicamente por tres características:

1. Mediante el uso de la codificación aritmética, por mecanismos de adaptación simples se puede obtener una adaptación dinámica a la presente estadística de fuente (adaptabilidad) .

2. La codificación aritmética permite la asignación de un número de bits no entero por símbolo que va a codificarse y es por lo tanto adecuada para lograr resultados de codificación que ilustran una aproximación de la entropía como límite inferior dado teóricamente (aproximación de entropía) [3].

3. Se pueden utilizar enlaces estadísticas de modelos de contexto adecuados entre símbolos para una reducción adicional de datos con la codificación aritmética (redundancia entre símbolos) [4].

Como desventaja de una aplicación de la codificación aritmética, se considera en general el aumento del esfuerzo de cálculo en comparación con la codificación de Huffman.

El concepto de la codificación aritmética se remonta a la documentación básica para la teoría de información por Shannon [5]. Los primeros procedimientos de construcción conceptuales fueron publicados primeramente por Elias [6]. Una primera variante LIFO (last-in-first-out) de la codificación aritmética fue diseñada por Rissanen [7] y más tarde modificada [8] [9] [10] por diferentes autores de las implementaciones FIFO (first-in-first-out) .

Todos estos documentos tienen como principio básico común la descomposición de intervalo parcial recursiva. En correspondencia con las probabilidades dadas P (“0”) y P (“1”) de dos resultados {“0”, “1”} de un alfabeto binario un intervalo dado principalmente, por ejemplo el intervalo [0, 1) , se descompone de forma recursiva en intervalos parciales dependiendo de la ocurrencia de eventos individuales. Aquí, el tamaño del intervalo parcial resultante como el producto de las probabilidades individuales de los eventos que ocurren es proporcional a la probabilidad de la secuencia de eventos individuales. Como cada evento Si añade una contribución de H (Si) = log (P (Si) ) del contenido de información teórica H (Si) de Si a la tasa global por la probabilidad P (Si) , una relación entre el número NBit de bits para ilustrar el intervalo parcial y la entropía de la secuencia de los resultados de los eventos individuales, que viene dada por el término derecho de la ecuación siguiente:

NEll =− log∏l P (Sl) = −I logP (Sl)

l

El principio básico, sin embargo, requiere en primer lugar de una precisión ilimitada (teóricamente) en la ilustración del intervalo parcial resultante y aparte de esto, tiene la desventaja de que sólo después de la codificación de los últimos resultados pueden darse como salida los bits para una representación de intervalo parcial resultante. A los efectos de aplicación práctica, fue decisivo por lo tanto desarrollar mecanismos para una salida gradual de bits con una representación simultánea con números con una precisión fija predeterminada. Estos mecanismos se introdujeron por primera vez en los documentos [3] [7] [11].

En la figura 1, se indican las operaciones básicas para una codificación aritmética binaria. En la implementación ilustrada el intervalo parcial actual está representado por los dos valores L y R, donde L indica el punto de desplazamiento y R el tamaño (anchura) del intervalo parcial, donde ambas cantidades se ilustran, utilizando números b bits enteros respectivamente. La codificación de un bit ∈ {0, 1} se lleva a cabo de este modo, básicamente, en cinco subetapas: En la primera etapa se determina el valor del símbolo menos probable utilizando la estimación de probabilidad. Para este símbolo, también llamado LPS (Least Probable Symbol- símbolo menos probable) , en contraste con el MPS (Most Probable Symbol- símbolo más probable) , se utiliza la estimación de probabilidad PLPS en la segunda etapa para calcular la anchura RLPS del intervalo parcial correspondiente.

Dependiendo del valor del bit que hay que codificar L y R se actualizan en la tercera etapa. En la cuarta etapa se actualiza la estimación de probabilidad en función del valor del bit que se acaba de codificar y finalmente el intervalo de código R se somete a la así llamada renormalización en la última etapa, es decir R se reescala por ejemplo para que se satisfaga la condición R∈[2b-2, 2b-1]. Aquí, se da como salida un bit en cada operación de escalado. Para más detalles, consulte [10].

La principal desventaja de una implementación, tal como se indica más arriba, reside ahora en el hecho de que el cálculo de la anchura de intervalo RLPS requiere una multiplicación para cada símbolo que hay que codificar. En general, las operaciones de multiplicación, en particular cuando se realizan en hardware, son costosas y requieren mucho tiempo. En varios documentos de investigación se examinaron los procedimientos para sustituir esta operación de multiplicación por una aproximación adecuada [11] [12] [13] [14]. Por la presente, los procedimientos publicados con referencia a este tema se pueden separar generalmente en tres categorías.

El primer grupo de propuestas para una codificación aritmética binaria libre de multiplicaciones, se basa en el enfoque de la aproximación de las probabilidades estimadas PLPS para que la multiplicación en la segunda etapa de La figura 1 podrá sustituirse por una o varias operaciones de suma y desplazamiento [11] [14]. Para esto, en el caso más simple las probabilidades PLPS se aproximan por valores en la forma 2-q con el entero q > 0.

En la segunda categoría de procedimientos aproximativos se propone aproximar el rango de valores de R por valores discretos en la forma (1/2 – r) , donde se selecciona r ∈ {0} ∪ {2-k I k > 0, k entero} [15] [16].

La tercera categoría de procedimientos sólo se conoce por el hecho de que aquí cualquier operación aritmética se sustituye por accesos a tabla. La tercera categoría de procedimientos sólo se conoce por el hecho de que aquí cualquier operación aritmética se sustituye por accesos a tabla. A este grupo de procedimientos pertenecen, por un lado el codificador Q utilizado en los procedimientos JPEG estándar y los relacionados, tales como los codificadores QM - y MQ - [12], y por otro lado el codificador cuasi aritmético [13]. Mientras que este último procedimiento realiza una limitación drástica del número b de bits utilizados para la representación de R con el fin de obtener tablas aceptablemente dimensionadas, en el codificador Q la renormalización de R se implementa de manera que R puede al menos aproximadamente ser aproximado por 1. De esta manera se evita la multiplicación para determinar RLPS. Además, se realiza la estimación de probabilidad mediante una tabla en la forma de una máquina de estado finito. Además, se realiza la estimación de probabilidad mediante una tabla en la forma de una máquina de estado finito [12].

El documento de patente US5592162 describe un procedimiento de realización de codificación aritmética, estando el número de posibles intervalos de anchuras restringido. Mediante el uso de un índice relativo a dichas anchuras de intervalo, la codificación aritmética libre de multiplicaciones se puede lograr con una sobrecarga reducida en términos de almacenamiento.

Esta invención se refiere... [Seguir leyendo]

1. Un dispositivo para codificar aritméticamente un símbolo que hay que codificar que tiene un estado binario basado en una anchura de intervalo actual R y representando una probabilidad una estimación de probabilidad para el símbolo que hay que codificar, en el que la probabilidad del símbolo menos probable PLPS está representada por un índice de probabilidad para asignar un estado de probabilidad entre una pluralidad de Nmax estados de probabilidad representativos Pn, en el que el dispositivo se caracteriza por:

medios para codificar el símbolo que hay que codificar, que comprende los siguientes medios:

medios para cartografiar la anchura de intervalo actual R con un índice de cuantización de entre una pluralidad de K índices de cuantización representativos asociados a anchuras de anchuras de intervalo respectivas Qk; y

medios para realizar la subdivisión de intervalo mediante el acceso a una tabla de división de intervalo compuesta de K*Nmax valores de producto Qk*Pn utilizando el índice de cuantización y el índice de probabilidad para obtener un valor de la anchura de intervalo parcial.

2. Un dispositivo para descodificar aritméticamente un símbolo codificado que tiene un estado binario basado en una anchura de intervalo actual R y representando una probabilidad una estimación de probabilidad para el símbolo codificado, en el que la probabilidad del símbolo menos probable está representada por un índice de probabilidad para asignar un estado de probabilidad entre una pluralidad de Nmax estados de probabilidad representativos Pn, en el que el dispositivo comprende:

medios para descodificar el símbolo codificado, que comprende los siguientes medios:

medios para cartografiar la anchura de intervalo actual con un índice de cuantización de entre una pluralidad de K = 2…8 índices de cuantización representativos asociados a anchuras de anchuras de intervalo respectivas Qk; y

medios para realizar la subdivisión de intervalo mediante el acceso a una tabla de división de intervalo compuesta de K*Nmax valores de producto Qk*Pn utilizando el índice de cuantización y el índice de probabilidad para obtener un valor de la anchura de intervalo parcial.

3. El dispositivo según la reivindicación 2, en el que los medios para descodificar también comprenden medios para actualizar la anchura de intervalo actual utilizando el valor de la anchura de intervalo parcial para obtener una nueva y actualizada anchura de intervalo.

4. El dispositivo según cualquiera de las reivindicaciones 2 a 3, en el que los medios para actualizar están configurados de modo que la actualización de la anchura de intervalo actual se realiza además en función de un valor dentro de un nuevo intervalo parcial caracterizado por la anchura de intervalo parcial actual y el valor dentro de un nuevo intervalo parcial.

5. El dispositivo según la reivindicación 4, en el que los medios para descodificar también comprenden medios para igualar el estado binario del símbolo codificado con uno de un estado menos probable y un estado más probable en función de si el valor dentro del nuevo intervalo parcial es mayor que o igual a, o menor que una diferencia del valor de la anchura de intervalo actual y el valor de la anchura de intervalo parcial.

6. El dispositivo según cualquiera de las reivindicaciones 4 o 5, en el que los medios para codificar también comprenden medios para actualizar el valor dentro del nuevo intervalo parcial con un siguiente bit a leer.

7. El dispositivo según cualquiera de las reivindicaciones 4 a 6, que comprende además:

medios para actualizar la estimación de probabilidad, en el que actualizar la estimación de probabilidad comprende consultar, con el índice de probabilidad, en una tabla de reglas de transición LPS (Next_State_LPS) para obtener un nuevo índice de probabilidad, cuando el valor dentro del nuevo intervalo parcial es mayor que o igual a una diferencia del valor de la anchura de intervalo actual y el valor de la anchura de intervalo parcial, y consultar, con el índice de probabilidad, en una tabla de reglas de transición MPS (Next_State_MPS) para obtener un nuevo índice de probabilidad, cuando el valor dentro del nuevo intervalo parcial es menor que una diferencia del valor de la anchura de intervalo actual y el valor de la anchura de intervalo parcial.

8. El dispositivo según cualquiera de las reivindicaciones 4 a 7, que comprende además medios para ajustar un valor indicativo del estado más probable del símbolo codificado de un estado indicado inicial a un diferente estado binario, cuando el índice de probabilidad es igual a un índice de probabilidad predeterminado y el valor dentro del nuevo intervalo parcial es mayor que o igual a una diferencia del valor de la anchura de intervalo actual y el valor de la anchura de intervalo parcial.

9. El dispositivo según cualquiera de las reivindicaciones anteriores, en el que la anchura de intervalo actual está representado con una precisión de b bits, y el valor de la anchura de intervalo parcial obtenido de la tabla de división de intervalo está representado con una precisión de b-2 bits.

1. Determinación del LPS

2. Cálculo de las variables RLPS y RMPS:

RLPS = R X RLPS

RMPS = R – RLPS

3. Cálculo del nuevo intervalo parcial:

if (bit: LPS) then L L + RMPS R RLPS

else R RMPS

4. Actualización de la estimación de probabilidad PLPS

5. Dar como salida los bits y renormalizar R

Fig.1

1. Determinación del LPS

2. Cuantización de R:

q_index = Qtab[R>>q]

3. Determinación de RLPS y RMPS:

RLPS = Rtab [q_index, p_state] RMPS = R – RLPS

4. Cálculo del nuevo intervalo parcial:

if (bit: LPS) then

L L + RMPS

R RLPS

p_state Next_State_LPS [p_state]

else

R RMPS

p_state Next_State_MPS [p_state]

Fig.2

1. Determinación del LPS

2. Cuantización de R:

q_index = Qtab[R>>q]

3. Determinación de RLPS y RMPS:

RLPS = Rtab [q_index, p_state] R = R – RLPS

4. Determinación de bit en función de la posición del intervalo parcial:

if (V ≥ RMPS) then bit LPS

V V -RMPS

R RLPS

p_state Next_State_LPS [p_state]

else bit MPS R RMPS p_state Next_State_MPS [p_state]

5. Renormalización de R, leer un bit y actualizar V

Fig.3

Codificador:

1. Cálculo del nuevo intervalo parcial

R R >> 1

if (bit = 1) then

L L + R

2. Dar como salida los bits y renormalizar R

Descodificador:

1. Determinación de bit en función de la posición del intervalo parcial:

if (V ≥ R) then

bit 1

V V – R

else bit 0,

2. Leer un bit, renormalizar R y actualizar V

Fig.4

Codificador:

1. Cálculo del nuevo intervalo parcial

L L << 1

if (bit = 1) then

L L + R

2. Dar como salida un bit y renormalizar utilizando valores umbrales de determinación duplicados (sin duplicar R y L)

Descodificador:

1. Leer un bit y actualizar V

2. Determinación de bit en función de la posición del intervalo parcial:

if (V ≥ R) then

bit 1

V V – R

else

Fig.5

1. preState = min (max (1, ( (m * SliceQP) >>4) +n) , 126)

2. if (preState <=63) then p_state = 63 – preState valMPS = 0

else p_state = preState – 64 valMPS = 1,

Fig.6