ES2316749T3 - Procedimiento y disposicion para la codificacion y la descodificacion aritmetica de estados binarios asi como programa informatico correspondiente y medio de almacenamiento legible por ordenador correspondiente. - Google Patents
Procedimiento y disposicion para la codificacion y la descodificacion aritmetica de estados binarios asi como programa informatico correspondiente y medio de almacenamiento legible por ordenador correspondiente. Download PDFInfo
- Publication number
- ES2316749T3 ES2316749T3 ES03725141T ES03725141T ES2316749T3 ES 2316749 T3 ES2316749 T3 ES 2316749T3 ES 03725141 T ES03725141 T ES 03725141T ES 03725141 T ES03725141 T ES 03725141T ES 2316749 T3 ES2316749 T3 ES 2316749T3
- Authority
- ES
- Spain
- Prior art keywords
- probability
- interval
- width
- index
- current
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/005—Statistical coding, e.g. Huffman, run length coding
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M7/4006—Conversion to or from arithmetic code
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
- Signal Processing For Digital Recording And Reproducing (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Hardware Redundancy (AREA)
Abstract
Procedimiento para la codificación aritmética de un símbolo que va a codificarse con estado binario basándose en una anchura de intervalo R actual y una probabilidad que representa una estimación de probabilidad para el símbolo que va a codificarse, estando representada la probabilidad por un índice de probabilidad para el direccionamiento de un estado de probabilidad a partir de una pluralidad de estados de probabilidad representativos, presentando el procedimiento la siguiente etapa: codificar el símbolo que va a codificarse, llevando a cabo las siguientes subetapas: mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y realizar la subdivisión de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo, presentando la subetapa de mapeo la aplicación de una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index = (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
Description
Procedimiento y disposición para la codificación
y la descodificación aritmética de estados binarios así como
programa informático correspondiente y medio de almacenamiento
legible por ordenador correspondiente.
La invención se refiere a un procedimiento y a
una disposición para la codificación y la descodificación aritmética
de estados binarios así como a un programa informático
correspondiente y a un medio de almacenamiento legible por
ordenador correspondiente, que pueden utilizarse especialmente en la
compresión de datos digital.
La presente invención describe un nuevo
procedimiento eficaz para la codificación aritmética binaria. La
necesidad de codificación aritmética binaria surge en los más
diversos campos de aplicación de la compresión de datos digital; a
este respecto son interesantes a modo de ejemplo sobre todo
aplicaciones en los campos de la compresión de imagen digital. En
numerosas normas para la codificación de imagen, como por ejemplo
JPEG, JPEG-2000, JPEG-LS y JBIG se
han definido procedimientos para la codificación aritmética binaria.
Nuevas actividades de normalización permiten reconocer también el
futuro uso de este tipo de técnicas de codificación en el campo de
la codificación de vídeo (CABAC en H.264/AVC) [1].
Las ventajas de la codificación aritmética (AK)
frente a la codificación Huffman [2] empleada hasta ahora con
frecuencia en la práctica pueden caracterizarse esencialmente por
tres características:
1. Mediante el uso de la codificación aritmética
puede conseguirse mediante mecanismos de adaptación sencillos una
adaptación dinámica a la estadística de fuente existente
(adaptividad).
2. La codificación aritmética permite la
asignación de un número no entero de bits por cada símbolo que va a
codificarse y de este modo es adecuada para conseguir resultados de
codificación que representan una aproximación de la entropía como
el límite inferior teóricamente dado (aproximación de entropía)
[3].
3. Con ayuda de modelos de contexto adecuados
pueden aprovecharse con la codificación aritmética combinaciones
estadísticas entre símbolos para la reducción de datos adicional
(redundancia entre símbolos) [4].
Como desventaja de una aplicación de la
codificación aritmética se considera el gran esfuerzo de cálculo en
general en comparación con la codificación Huffman.
El concepto de la codificación aritmética se
basa en los trabajos básicos con respecto a la teoría de información
de Shannon [5]. Se publicaron los primeros métodos de construcción
conceptuales en [6] por primera vez por Elias. Rissanen [7] diseñó
una primera variante LIFO
(last-in-first-out)
de la codificación aritmética y se modificó posteriormente por
diferentes autores para obtener configuraciones FIFO
(first-in-first-out)
[8] [9] [10].
Todos estos trabajos tienen en común que se
basan en el principio de la división de subintervalos recursiva: de
manera correspondiente a las probabilidades P("0") y
P("1") dadas de dos eventos {"0", "1"} de un alfabeto
binario se divide de manera recursiva en subintervalos un intervalo
dado inicialmente, por ejemplo el intervalo [0, 1), según la
aparición de eventos individuales. A este respecto el tamaño del
subintervalo resultante como producto de las probabilidades
individuales de los eventos aparecidos es proporcional a la
probabilidad de la secuencia de los eventos individuales. Puesto
que cada evento S_{i} con la probabilidad P(S_{i})
aporta una contribución de H(S_{i}) = -log
(P(S_{i})) del contenido de información teórico
H(S_{i}) de S_{i} a la tasa compuesta, se obtiene una
relación entre el número N_{Bit} de bits para la representación
del subintervalo y la entropía de la secuencia de eventos
individuales que se indica mediante el lado derecho de la siguiente
ecuación
\vskip1.000000\baselineskip
\vskip1.000000\baselineskip
Sin embargo, el principio básico requiere en
primer lugar una precisión ilimitada (teóricamente) en la
representación del subintervalo resultante y tiene además la
desventaja de que sólo tras la codificación del último evento
pueden salir los bits para la representación del subintervalo
resultante. Para fines de aplicación prácticos fue decisivo por
tanto desarrollar mecanismos para una salida incremental de bits con
representación simultánea con números de precisión fija
preestablecida. Éstos se presentaron por primera vez en los trabajos
[3] [7] [11].
En la figura 1 están esbozadas las operaciones
esenciales para la codificación aritmética binaria. En la
implementación representada se representa el subintervalo actual
mediante los dos valores L y R, designando L el punto de partida y
R el tamaño (anchura) del subintervalo y representándose ambas
magnitudes en cada caso con números enteros de b bits. La
codificación de un bit \in {0, 1} se realiza a este respecto
esencialmente en cinco subetapas: en la primera etapa se determina
mediante la estimación de probabilidad el valor del símbolo menos
probable. Para este símbolo, también denominado LPS (least
probable symbol, símbolo menos probable) en contraposición a
MPS (most probable symbol, símbolo más probable), se recurre
a la estimación de probabilidad P_{LPS} en la segunda etapa para
calcular la anchura R_{LPS} del subintervalo correspondiente.
Según el valor del bit, bit, que va a codificarse se actualizan L y
R en la tercera etapa. En la cuarta etapa se actualiza la
estimación de probabilidad según el valor del bit que acaba de
codificarse y finalmente el intervalo de código R se somete en la
última etapa a una denominada renormalización, es decir, R se
reajusta a escala por ejemplo de modo que se cumple la condición
R\in[2^{b-2}, 2^{b-1}).
A este respecto sale en cada operación de ajuste a escala un bit.
Para más detalles se hace referencia a [10].
La desventaja esencial de una implementación,
tal como se ha esbozado anteriormente, consiste ahora en que el
cálculo de la anchura de intervalo R_{LPS} requiere una
multiplicación por cada símbolo que va a codificarse. Habitualmente
las operaciones de multiplicación son complicadas y caras,
especialmente cuando se realizan en hardware. En varios trabajos de
investigación se analizaron por tanto procedimientos para sustituir
esta operación de multiplicación por una aproximación adecuada [11]
[12] [13] [14]. A este respecto los procedimientos publicados con
respecto a este tema pueden clasificarse de manera aproximada en
tres categorías.
El primer grupo de propuestas con respecto a una
codificación aritmética binaria sin multiplicación se basa en el
planteamiento de aproximar las probabilidades P_{LPS} estimadas de
modo que la multiplicación en la 2ª etapa de la figura 1 puede
sustituirse por una (o varias) operación (operaciones) de
desplazamiento y suma [11] [14]. Para ello se aproximan en el caso
más sencillo las probabilidades P_{LPS} mediante valores en la
forma 2^{-q} con q > 0 entero.
En la segunda categoría de procedimientos
aproximativos se propone aproximar el rango de valores de R mediante
valores discretos en la forma (1/2 - r), eligiéndose
r\in{0}\cup{2^{-k} | k>0, k entero} [15] [16].
La tercera categoría de procedimientos se
caracteriza finalmente porque en la misma se sustituyen todas las
operaciones aritméticas por accesos a tablas. A este grupo de
procedimientos pertenecen por un lado el codificador Q utilizado en
la norma JPEG y procedimientos relacionados, como el codificador QM
y MQ [12], y por otro lado el codificador casi aritmético [13].
Mientras que el procedimiento mencionado en último lugar efectúa una
limitación drástica del número b de bits utilizado para la
representación de R para llegar a tablas dimensionadas de manera
aceptable, en el codificador Q la renormalización de R se diseña de
modo que R puede aproximarse al menos de manera aproximada mediante
1. De este modo se evita la multiplicación para la determinación de
R_{LPS}. Adicionalmente se lleva a cabo la estimación de
probabilidad mediante una tabla en forma de una máquina de estados
finita. Para detalles adicionales a este respecto se hace referencia
a [12].
El documento US5592162 describe un procedimiento
para llevar a cabo una codificación aritmética, limitándose el
número de las posibles anchuras de intervalo. Mediante el uso de un
índice que se refiere a estas anchuras de intervalo puede
conseguirse una codificación aritmética sin multiplicación con un
esfuerzo de almacenamiento reducido.
Un procedimiento para la codificación y la
descodificación aritmética de estados binarios se realiza de manera
ventajosa de modo que en una primera etapa se subdivide un rango de
valores que puede preestablecerse para la especificación de la
anchura de intervalo R en K anchuras de intervalo {Q_{1},...,
Q_{K}} representativas, un rango de valores que puede
preestablecerse para la especificación de las probabilidades en N
estados de probabilidad {P_{1},..., P_{N}} representativos y se
indican reglas de asignación que a cada anchura de intervalo R
asignan una Q_{k} (1 \leq k \leq K) y a cada probabilidad una
P_{n} (1 \leq n \leq N), en una segunda etapa se realiza la
codificación o descodificación de los estados binarios, realizándose
el cálculo de la nueva anchura de intervalo que va a derivarse en
el proceso de codificación o descodificación utilizando una anchura
de intervalo Q_{k} (1 \leq k \leq K) representativa y un
estado de probabilidad P_{n} (1 \leq n \leq N) representativo
mediante operaciones aritméticas diferentes de multiplicación y
división, determinándose la anchura de intervalo Q_{k}
representativa mediante el intervalo básico que se toma como base
de la anchura R y el estado de probabilidad P_{n} representativo
mediante la estimación de probabilidad en que se basa el símbolo
que va a codificarse o descodificarse según las reglas de asignación
indicadas.
Otra forma de realización preferida del
procedimiento está caracterizada porque, partiendo del intervalo que
va a evaluarse actualmente con anchura R para la determinación de
la anchura de intervalo Q_{k} asignada, se determina un índice
q_index mediante una operación de enmascaramiento de bits y
desplazamiento aplicada a la representación binaria/interna del
ordenador de R.
También resulta ventajoso si, partiendo del
intervalo que va a evaluarse actualmente con anchura R para la
determinación de la anchura de intervalo Q_{k} asignada, se
determina un índice q_index mediante una operación de
desplazamiento aplicada a la representación binaria/interna del
ordenador de R y un acceso aguas abajo a una tabla Qtab,
conteniendo la tabla Qtab los índices de anchuras de intervalo que
corresponden a los valores de R precuantificados mediante operación
de desplazamiento.
Especialmente resulta ventajoso cuando la
estimación de probabilidad en que se basa el símbolo que va a
codificarse o descodificarse se asigna con ayuda de un índice
p_state a un estado de probabilidad P_{n}.
También es ventajoso cuando la determinación de
la anchura de intervalo R_{LPS} que corresponde al LPS se realiza
mediante un acceso a una tabla Rtab, conteniendo la tabla Rtab los
valores de la anchura de intervalo R_{LPS} correspondientes a
todos los K valores cuantificados de R y los N estados de
probabilidad diferentes como valores de producto (Q_{k} *
P_{n}). El esfuerzo de cálculo se reduce especialmente cuando la
determinación de la anchura de intervalo R_{LPS} que corresponde
al LPS se realiza mediante un acceso a la tabla Rtab, utilizándose
para la evaluación de la tabla el índice de cuantificación q_index y
el índice del estado de probabilidad p_state.
Está previsto además que para los N estados de
probabilidad representativos diferentes se preestablezcan reglas de
transición, indicando las reglas de transición qué nuevo estado se
utiliza partiendo del símbolo actualmente codificado o
descodificado para el siguiente símbolo que va a codificarse o
descodificarse. A este respecto resulta ventajoso cuando se
establece una tabla Next_State_LPS que, con respecto al índice n del
estado de probabilidad P_{n} actualmente dado, contiene el índice
m del nuevo estado de probabilidad P_{m} al aparecer un símbolo
menos probable (LPS), y/o se establece una tabla Next_State_MPS que,
con respecto al índice n del estado de probabilidad P_{n}
actualmente dado, contiene el índice m del nuevo estado de
probabilidad P_{m} al aparecer un símbolo más probable (MPS).
Una optimización del procedimiento para la
codificación y descodificación aritmética binaria basada en tablas
se consigue especialmente porque los valores de la anchura de
intervalo R_{LPS} correspondientes a todas las K anchuras de
intervalo y a todos los N estados de probabilidad diferentes se
depositan como valores de producto (Q_{k} * P_{n}) en una tabla
Rtab.
Una optimización adicional se consigue cuando el
número K de valores de cuantificación y/o el número N de estados
representativos se eligen en función de la precisión preestablecida
de la codificación y/o en función del espacio de memoria
disponible.
\vskip1.000000\baselineskip
Una forma de realización especial de la
codificación comprende las siguientes etapas:
1. Determinación del LPS
2. Cuantificación de R:
\hskip0,3cm1
3. Determinación de R_{LPS} y R:
\hskip0,4cm2
4. Cálculo del nuevo subintervalo:
\hskip0,3cm3
5. Renormalización de L y R, escritura de
bits,
describiendo
q_index, el índice de un valor de cuantificación
extraído mediante lectura de Qtab,
p_state, el estado actual,
R_{LPS}, la anchura de intervalo que
corresponde al LPS y
ValMPS, el bit que corresponde al MPS.
\vskip1.000000\baselineskip
La descodificación en una forma de realización
especial comprende las siguientes etapas:
1. Determinación del LPS
2. Cuantificación de R:
\hskip0,3cm4
3. Determinación de R_{LPS} y R:
\hskip0,3cm5
4. Determinación del bit, según la posición del
subintervalo:
\hskip0,3cm6
5. Renormalización de R, extracción mediante
lectura de un bit y actualización de V,
describiendo
q_index, el índice de un valor de cuantificación
extraído mediante lectura de Qtab,
p_state, el estado actual,
R_{LPS}, la anchura de intervalo que
corresponde al LPS,
valMPS, el bit que corresponde al MPS y
V, un valor del interior del subintervalo
actual.
\vskip1.000000\baselineskip
En una forma de realización del procedimiento
según la invención está previsto que en la codificación y/o
descodificación se realice el cálculo del índice de cuantificación
q_index en la segunda subetapa según la regla de cálculo:
q_index = (R >> q) & Qmask
representando Qmask una máscara de bits elegida
de manera adecuada en función de K.
Además resulta ventajoso cuando la
inicialización de los modelos de probabilidad se realiza en función
de un parámetro de cuantificación SliceQP y parámetros de modelo m
y n preestablecidos, describiendo SliceQP el parámetro de
cuantificación preestablecido en el inicio de un sector y m y n los
parámetros de modelo.
\newpage
Asimismo es ventajoso cuando la inicialización
de los modelos de probabilidad comprende las siguientes etapas:
\hskip0,3cm7
describiendo valMPS el bit que
corresponde al MPS, SliceQP el parámetro de cuantificación
preestablecido en el inicio de un sector y m y n los parámetros de
modelo.
Una disposición para la codificación y la
descodificación aritmética de estados binarios comprende al menos
un procesador que está(n) configurado(s) de modo que puede
realizarse un procedimiento para la codificación y descodificación
aritmética, subdividiéndose en una primera etapa un rango de valores
que puede preestablecerse para la especificación de la anchura de
intervalo R en K anchuras de intervalo {Q_{1},..., Q_{k}}
representativas, un rango de valores que puede preestablecerse para
la especificación de las probabilidades en N estados de
probabilidad {P_{1},..., P_{N}} representativos e indicándose
reglas de asignación que a cada anchura de intervalo R asignan una
Q_{k} (1 \leq k \leq K) y a cada probabilidad una P_{n} (1
\leq n \leq N), en una segunda etapa se realiza la codificación
o descodificación de los estados binarios, realizándose el cálculo
de la nueva anchura de intervalo que va a derivarse en el proceso de
codificación o descodificación utilizando una anchura de intervalo
Q_{k} (1 \leq k \leq K) representativa y un estado de
probabilidad P_{n} (1 \leq n \leq N) representativo mediante
operaciones aritméticas diferentes de multiplicación y división,
determinándose la anchura de intervalo Q_{k} representativa
mediante el intervalo básico que se toma como base de la anchura R
y el estado de probabilidad P_{n} representativo mediante la
estimación de probabilidad en que se basa el símbolo que va a
codificarse o descodificarse según las reglas de asignación
indicadas.
Un programa informático para la codificación y
la descodificación aritmética de estados binarios posibilita a un
ordenador, una vez cargado en la memoria del ordenador, realizar un
procedimiento para la codificación y la descodificación aritmética,
subdividiéndose en una primera etapa un rango de valores que puede
preestablecerse para la especificación de la anchura de intervalo R
en K anchuras de intervalo representativas {Q_{1},..., Q_{K}},
un rango de valores que puede preestablecerse para la especificación
de las probabilidades en N estados de probabilidad representativos
{P_{1},..., P_{N}} e indicándose reglas de asignación, que
asignan a cada anchura de intervalo R una Q_{k} (1 \leq k
\leq K) y a cada probabilidad una P_{n} (1 \leq n \leq N),
produciéndose en una segunda etapa la codificación o descodificación
de los estados binarios, realizándose el cálculo de la nueva
anchura de intervalo que va a derivarse en el proceso de
codificación o descodificación utilizando una anchura de intervalo
Q_{k} representativa (1 \leq k \leq K) y un estado de
probabilidad P_{n} representativo (1 \leq n \leq N) mediante
operaciones aritméticas diferentes de multiplicación y división,
determinándose la anchura de intervalo Q_{k} representativa
mediante el intervalo básico que se toma como base de la anchura R
y el estado de probabilidad P_{n} representativo mediante la
estimación de probabilidad en la que se basa el símbolo que va a
codificarse o a descodificarse según las reglas de asignación
indicadas.
Por ejemplo, tales programas informáticos
(pagando tasas o de forma gratuita, con libre acceso o protegidos
con contraseña) pueden proporcionarse con posibilidad de descarga en
una red de datos o de comunicación. Los programas informáticos así
proporcionados pueden hacerse útiles entonces mediante un
procedimiento, en el que un programa informático se descarga desde
una red para la transmisión de datos como por ejemplo desde
Internet a un medio de procesamiento de datos conectado a la
red.
Para la realización de un procedimiento para la
codificación y la descodificación aritmética de estados binarios se
utiliza ventajosamente un medio de almacenamiento legible por
ordenador, en el que está almacenado un programa, que posibilita a
un ordenador, una vez cargado en la memoria del ordenador, realizar
un procedimiento para la codificación y la descodificación
aritmética, subdividiéndose en una primera etapa un rango de valores
que puede preestablecerse para la especificación de la anchura de
intervalo R en K anchuras de intervalo {Q_{1},..., Q_{k}}
representativas, un rango de valores que puede preestablecerse para
la especificación de las probabilidades en N estados de
probabilidad {P_{1},..., P_{N}} representativos e indicándose
reglas de asignación, que a cada anchura de intervalo R asignan una
Q_{k} (1 \leq k \leq K) y a cada probabilidad una P_{n} (1
\leq n \leq N), produciéndose en una segunda etapa la
codificación o descodificación de los estados binarios,
realizándose el cálculo de la nueva anchura de intervalo que va a
derivarse en el proceso de codificación o descodificación
utilizando una anchura de intervalo Q_{k} (1 \leq k \leq K)
representativa y un estado de probabilidad P_{n} (1 \leq n
\leq N) representativo mediante operaciones aritméticas diferentes
de multiplicación y división, determinándose la anchura de
intervalo Q_{k} representativa mediante el intervalo básico que
se toma como base de la anchura R y el estado de probabilidad
P_{n} representativo mediante la estimación de probabilidad en la
que se basa el símbolo que va a codificarse o a descodificarse según
las reglas de asignación indicadas.
\newpage
El nuevo procedimiento se caracteriza por la
combinación de tres características. En primer lugar, de manera
similar al codificador Q se produce la estimación de probabilidad
mediante una máquina de estados finita (FSM: finite state
machine), produciéndose la generación de los N estados
representativos de la FSM fuera de línea. Las reglas de transición
correspondientes se depositan a este respecto en forma de
tablas.
La segunda característica de la invención es una
precuantificación de la anchura de intervalo R hasta un número de K
valores de cuantificación previamente definidos. Esto permite, con
un dimensionamiento adecuado de K y N la elaboración de una tabla,
que contiene todas las combinaciones K x N de valores de producto R
x P_{LPS} calculados previamente para una determinación sin
multiplicación de R_{LPS}.
Para el uso de la presente invención en un
entorno, en el que se utilizan diferentes modelos de contexto,
entre los que se encuentran también aquéllos con una distribución de
probabilidades (casi) uniforme, se prevé como elemento adicional
(opcional) una rama separada en la máquina de codificación, en la
que suponiendo una distribución uniforme se reduce claramente otra
vez la determinación de las magnitudes L y R así como la
renormalización con respecto al esfuerzo de cálculo.
Muestran:
la figura 1 una representación de las
operaciones esenciales para la codificación aritmética binaria;
la figura 2 un esquema modificado para la
codificación aritmética basada en tablas;
la figura 3 el principio de la descodificación
aritmética basada en tablas;
la figura 4 el principio de la codificación o
descodificación para datos binarios con distribución uniforme;
la figura 5 una realización alternativa de la
codificación o descodificación para datos binarios con distribución
uniforme.
La figura 6 la inicialización de los modelos de
probabilidad en función de un parámetro de cuantificación SliceQP y
los parámetros de modelo m y n preestablecidos
Sin embargo, en primer lugar se explicará la
base teórica de forma algo más detallada:
Estimación de probabilidad basada en tablas
Como ya se explicó con más detalle
anteriormente, el modo de acción de la codificación aritmética se
basa en una estimación lo mejor posible de la probabilidad de
aparición de los símbolos que van a codificarse. Para posibilitar
una adaptación a estadísticas de fuente no estacionarias debe
actualizarse esta estimación a lo largo del proceso de
codificación. Por regla general se utilizan para ello habitualmente
procedimientos, que operan con ayuda de contadores de frecuencia
ajustados a escala de los eventos codificados [17]. Si C_{LPS} y
C_{MPS} designan contadores para las frecuencias de aparición de
LPS y MPS, entonces mediante estos contadores puede llevarse a cabo
la estimación
y así realizar la operación
esbozada en la figura 1 de la subdivisión de intervalo. Desventajosa
para fines prácticos es la división necesaria en la ecuación (1).
Sin embargo, con frecuencia es conveniente y necesario, al superar
un valor umbral C_{max} preestablecido del contador total
C_{Total} = C_{MPS} + C_{LPS} llevar a cabo un reajuste a
escala de los estados del contador. (En este contexto se considerará
que en una representación de b bits de L y R la menor probabilidad,
que aún puede representarse correctamente, asciende a 2^{-b+2},
de modo que para evitar quedar por debajo de este límite inferior
dado el caso es necesario un reajuste a escala de los estados del
contador). Con una elección adecuada de C_{max} pueden presentarse
en forma de tabla los valores recíprocos de C_{Total}, de modo
que la división necesaria en la ecuación (1) puede sustituirse por
un acceso a la tabla así como una operación de multiplicación y
desplazamiento. Sin embargo, para evitar también estas operaciones
aritméticas, en la presente invención se utiliza un procedimiento
basado completamente en tablas para la estimación de
probabilidad.
Para este fin se eligen previamente en una fase
de entrenamiento estados de probabilidad representativos {P_{k}|0
\leq k < N_{max}}, dependiendo la elección de los estados por
un lado de la estadística de los datos que van a codificarse y por
otro lado de la condición secundaria del número máximo N_{max}
preestablecido de estados. Adicionalmente se definen reglas de
transición, que indican qué nuevo estado ha de utilizarse partiendo
del símbolo actualmente codificado para el siguiente símbolo que va
a codificarse. Estas reglas de transición se proporcionan en forma
de dos tablas: {Next_State_LPS_{k} | 0 \leq k < N_{max}}
y {Next_State_MPS_{k} | 0 \leq k < N_{max}},
proporcionando las tablas para el índice n del estado de
probabilidad P_{n} dado actualmente el índice m del nuevo estado
de probabilidad P_{m} al aparecer un LPS o MPS. En este punto
cabe destacar que para la estimación de probabilidad en el
codificador o descodificador aritmético tal como se propone en este
caso, no se requiere una presentación explícita en forma de tabla de
los estados de probabilidad. Más bien se direccionan los estados
sólo mediante sus índices correspondientes de manera implícita, tal
como se describe en el párrafo siguiente. Adicionalmente a las
reglas de transición debe especificarse en qué estados de
probabilidad debe cambiarse el valor del LPS y MPS. Por regla
general sólo habrá un estado marcado tal, que a continuación puede
identificarse mediante su índice p_state.
La figura 2 muestra el esquema modificado para
la codificación aritmética basada en tablas, tal como se propone en
este caso. Tras determinar el LPS se mapea en primer lugar la
anchura de intervalo R dada mediante un mapeo Qtab presentado en
forma de tabla y una operación de desplazamiento adecuada (por q
bit) con un valor Q cuantificado. Alternativamente, la
cuantificación también puede realizarse en casos especiales sin
recurrir a un mapeo Qtab presentado en forma de tabla sólo con
ayuda de una combinación de operaciones de desplazamiento y
enmascaramiento. Por regla general se realiza en este caso una
cuantificación relativamente aproximada hasta K = 2...8 valores
representativos. Tampoco en este caso, de manera similar al caso de
la estimación de probabilidad, se produce una determinación
explícita de Q; más bien se transmite sólo un índice q_index a Q.
Este índice se utiliza ahora junto con el índice p_state para
caracterizar el estado de probabilidad actual para determinar la
anchura de intervalo R_{LPS}. Para ello se utiliza la entrada
correspondiente de la tabla Rtab. En ésta están depositados los K
\cdot N_{max} valores de producto R x P_{LPS} correspondientes
a todos los K valores cuantificados de R y N_{max} estados de
probabilidad diferentes como valores de número entero con una
exactitud de en general b-2 bits. Para
implementaciones prácticas se da en este caso una posibilidad de
sopesar entre la necesidad de memoria para el tamaño de la tabla y
la exactitud aritmética, que en última instancia determina también
la eficiencia de la codificación. Ambas magnitudes objetivo se
determinan mediante la granularidad de la representación de R y
P_{LPS}.
En la cuarta etapa de la figura 2 se muestra
cómo se lleva a cabo la actualización del estado de probabilidad
p_state en función del evento bit recién codificado. En este caso se
utilizan las tablas de transición Next_State_LPS y Next_State_MPS
ya mencionadas en el párrafo anterior "Estimación de probabilidad
basada en tablas". Estas operaciones corresponden al proceso de
actualización indicado en la figura 1 en la 4ª etapa, aunque no
especificado con más detalle.
La figura 3 muestra el esquema de desarrollo
correspondiente de la descodificación aritmética basada en tablas.
Para caracterizar el subintervalo actual se utiliza en el
descodificador la anchura de intervalo R y un valor V. Éste último
se encuentra dentro del subintervalo y se afina sucesivamente con
cada bit leído. Tal como se deduce de la figura 3, las operaciones
para la estimación de probabilidad y la determinación de la anchura
de intervalo R se corrigen correspondientemente a las del
codificador.
En aplicaciones en las que deben codificarse por
ejemplo valores con signo, cuya distribución de probabilidades está
dispuesta simétricamente respecto al cero, se podrá partir para la
codificación de la información de signo por regla general de una
distribución uniforme. Puesto que esta información debe introducirse
por un lado en el flujo de bits aritmético, aunque por otro lado no
es útil para el caso de una probabilidad de P \approx 0,5
utilizar el aparato aún relativamente complejo de la estimación de
probabilidad y subdivisión de intervalo basadas en tablas, se
propone para este caso especial utilizar opcionalmente un
procedimiento de codificador/descodificador separado que se
representa de la siguiente manera.
En el codificador puede determinarse para este
caso especial la anchura de intervalo del nuevo subintervalo
mediante una operación de desplazamiento sencilla
correspondientemente a una división por la mitad de la anchura del
intervalo de partida R. Según el valor del bit que va a codificarse
se elige entonces la mitad superior o inferior de R como nuevo
subintervalo (véase la figura 4). La renormalización y salida
posterior de bits se realiza como en el caso anterior de la solución
basada en tablas.
En el descodificador correspondiente se reducen
las operaciones necesarias a determinar el bit que va a
descodificarse mediante el valor de V respecto a la anchura de
intervalo R actual mediante una operación de comparación sencilla.
En caso de establecer el bit descodificado, se reducirá V por la
cantidad de R. Tal como representa la figura 4, se termina la
descodificación mediante la renormalización y la actualización de V
con el siguiente bit que va a introducirse mediante lectura.
Una realización alternativa de la codificación
de eventos con distribución de probabilidades uniforme se representa
en la figura 5. En esta implementación a modo de ejemplo no se
modifica la anchura de intervalo R actual. En su lugar se duplica
en el codificador en primer lugar V mediante una operación de
desplazamiento. Según el valor del bit que va a codificarse, de
manera similar al ejemplo anterior, se elige entonces la mitad
superior o inferior de R como nuevo subintervalo (véase la figura
5). La renormalización y salida posterior de bits se produce como
en el caso anterior de la solución basada en tablas con la
diferencia de que no se lleva a cabo la duplicación de R y L y se
llevan a cabo las operaciones de comparación correspondientes con
valores umbral duplicados.
\newpage
En el descodificador correspondiente de la
realización alternativa en primer lugar se extrae un bit mediante
lectura y se actualiza V. La segunda etapa se lleva a cabo de la
misma manera que la etapa 1 en la figura 4, es decir, el bit que va
a descodificarse se determina mediante el valor de V respecto a la
anchura de intervalo R actual mediante una operación de comparación
sencilla y en caso de que se establezca el bit descodificado, se
reducirá V por la cantidad de R (véase la figura 5).
Cada modelo de probabilidad, tal como se utiliza
en la presente invención, se caracteriza con ayuda de dos
parámetros: 1) el índice p_state, que caracteriza el estado de
probabilidad del LPS, y 2) el valor valMPS del MPS. Cada una de
estas magnitudes debe inicializarse al inicio de la codificación o
descodificación de una unidad de codificación terminada (en
aplicaciones de la codificación de vídeo aproximadamente un sector).
Los valores de inicialización pueden derivarse a este respecto a
partir de información de control, como el parámetro de
cuantificación (de un sector), tal como se representa a modo de
ejemplo en la figura 6.
Otra posibilidad de adaptación de las
distribuciones de inicio de los modelos se proporciona mediante el
siguiente método. Para garantizar una mejor adaptación de las
inicializaciones de los modelos puede proporcionarse en el
codificador una elección de valores de inicio preestablecidos de los
modelos. Estos modelos pueden agruparse en grupos de distribuciones
de inicio y direccionarse con índices, de modo que en el codificador
se produce la elección adaptiva de un grupo de valores de inicio y
se transmite al descodificador en forma de un índice como
información lateral. Este método se denomina proceso de
inicialización controlado hacia delante.
[1] T. Wiegand, G. Sullivan,
"Draft Text of Final Draft International Standard (FDIS) of Joint
Video Specification (ITUT Rec. H.264 | ISO/IEC
14496-10 AVC)", JVT-G050, marzo
de 2003.
[2] D. A. Huffman, "A Method for
Construction of Minimum Redundancy code", Proc. IRE, Vol.
40, págs. 1098-1101, 1952.
[3] I. H. Witten, R. M. Neal, J.
G. Cleary, "Arithmetic Coding for Data Compression",
Communication of the ACM, Vol. 30, No. 6, págs.
520-540, 1987.
[4] G. G. Langdon, J. Rissanen,
"A Simple General Binary Source code", IEEE Transactions on
Information Theory, Vol. 28, págs. 800-803,
1982.
[5] C. E. Shannon, "A Mathematical
Theory of Communication", Bell Syst. Tech. Journal, vol.
27, págs. 379-423, 623-656,
1948.
[6] P. Elias, "in information Theory
and Coding", N. Abramson (Ed.), New York,
MC-Crawl-Hill,
1963.
[7] J. Rissanen, "Generalizad Kraft
Inequality and Arithmetic Coding", IBM J. Res. Develop.,
Vol. 20, págs. 198-203. 1976.
[8] R. C. Pasco, "Source Coding and
Algorithms for Fast Data Compression", Ph. D.
Dissertation, Stanford University, EE.UU., 1976.
[9] G. G. Langdon, "An Introduction to
Arithmetic Coding", IBM J. Res. Develop., Vol. 28, págs.
135-149, 1984.
[10] A. Moffat, R. M. Neal, I. H.
Witten, "Arithmetic Coding Revisited", Proc. IEEE Data
Compression Conference, Snowbird (USA), págs.
202-211, 1996.
[11] J. Rissanen, K. M. Mohiuddin,
"A Multiplication-Free Multialphabet Arithmetic
Arithmetic Code", IEEE Trans. on Communication, Vol. 37,
págs. 93-98, 1989.
[12] W. B. Pennebaker, J. L.
Mitchell, G. G. Langdon, R. B. Arps, "An
Overview of the Basic Principles of the QCoder Adaptive Binary
Arithmetic Coder", IBM J. Res. Develop., Vol. 32, págs.
717-726, 1988.
[13] P. G. Howard, J. S. Vitter,
"Practical Implementations of Arithmetic Coding", in "Image
and Text Compression", J. Storer (Ed.), Norwell (EE.UU.),
Kluwer, 1992.
[14] L. Huynh, A. Moffat, "A
Probability-Ratio Approach to Approximate Binary
Arithmetic Coding", IEEE Trans. on Information Theory,
Vol. 43, págs. 1658-1662, 1997.
[15] D. Chevion, E. D. Karnin, E.
Walach, "High-Efficiency, Multiplication
Free Approximation of Arithmetic Coding", Proc. IEEE Data
Compression Conference, Snowbird (USA), págs.
43-52, 1991.
[16] G. Feygin, P. G. Gulak, P.
Chow, "Minimizing Excess Code Length and VLSI Complexity in
the Multiplication Free Approximation of Arithmetic Coding",
Inform. Proc. Manag., vol. 30, págs. 805-816,
1994.
[17] D. L. Duttweiler, Ch.
Chamzas, "Probability Estimation in Arithmetic and
Adaptive-Huffman Entropy Coders", IEEE Trans.
on Image Processing, Vol. 4, págs. 237-246,
1995.
Claims (38)
1. Procedimiento para la codificación aritmética
de un símbolo que va a codificarse con estado binario basándose en
una anchura de intervalo R actual y una probabilidad que representa
una estimación de probabilidad para el símbolo que va a
codificarse, estando representada la probabilidad por un índice de
probabilidad para el direccionamiento de un estado de probabilidad
a partir de una pluralidad de estados de probabilidad
representativos, presentando el procedimiento la siguiente
etapa:
- codificar el símbolo que va a codificarse, llevando a cabo las siguientes subetapas:
- mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- realizar la subdivisión de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo,
presentando la subetapa de mapeo la aplicación
de una operación de enmascaramiento de bits y desplazamiento a una
representación binaria/interna del ordenador de la anchura de
intervalo actual, concretamente según la siguiente regla de cálculo
q_index = (R >> q) & Qmask, representando Qmask una
máscara de bits elegida de manera adecuada en función del número de
índices de cuantificación representativos, R la anchura de intervalo
actual y q un número de bits.
2. Procedimiento según la reivindicación 1, en
el que la codificación tiene lugar además mediante la siguiente
etapa:
- actualizar la anchura de intervalo actual utilizando el valor de anchura de intervalo, para obtener una nueva anchura de intervalo actualizada.
3. Procedimiento según la reivindicación 1 ó 2,
en el que el valor de anchura de subintervalo indica una anchura de
un subintervalo para un símbolo que va a codificarse con un estado
menos probable a partir de un intervalo actual con la anchura de
intervalo actual.
4. Procedimiento según una de las
reivindicaciones 1 a 3, en el que la actualización de la anchura de
intervalo actual se realiza además en función del estado binario
del símbolo que va a codificarse.
5. Procedimiento según una de las
reivindicaciones anteriores, que presenta además la siguiente
etapa:
- adaptar la estimación de probabilidad, presentando la adaptación de la estimación de probabilidad la consulta, con el índice de probabilidad, en una tabla de regla de transición LPS (Next_State_LPS), para obtener un nuevo índice de probabilidad, si el símbolo que va a codificarse presenta un estado menos probable, y la consulta, con el índice de probabilidad, en una tabla de regla de transición MPS (Next_State_MPS), para obtener un nuevo índice de probabilidad, si el símbolo que va a codificarse presenta un estado más probable.
6. Procedimiento según la reivindicación 5, que
presenta además el cambio de un valor que indica el estado más
probable de un estado indicado originalmente al estado binario del
símbolo que va a codificarse, si el índice de probabilidad es
similar a un índice de probabilidad predeterminado y el símbolo que
va a codificarse presenta un estado binario diferente del estado
indicado originalmente.
7. Procedimiento según una de las
reivindicaciones 1 a 6, en el que la subetapa de la actualización de
la anchura de intervalo actual presenta las siguientes etapas:
- igualar la nueva anchura de intervalo con la diferencia de la anchura de intervalo actual menos el valor de anchura de subintervalo; y
- a continuación, en caso de que el símbolo que va a codificarse presente un estado menos probable, igualar la nueva anchura de intervalo con el valor de anchura de subintervalo.
8. Procedimiento según una de las
reivindicaciones anteriores, en el que un intervalo actual está
representado por la anchura de intervalo actual y un punto de
partida actual, y la codificación se realiza además mediante la
siguiente subetapa:
- sumar el punto de partida actual y una diferencia de anchura de intervalo actual y valor de anchura de subintervalo, para obtener un nuevo punto de partida actualizado, si el símbolo que va a codificarse presenta un estado menos probable.
\newpage
9. Procedimiento para la descodificación
aritmética de un símbolo codificado con estado binario basándose en
una anchura de intervalo R actual y una probabilidad que representa
una estimación de probabilidad para el símbolo codificado, estando
representada la probabilidad por un índice de probabilidad de un
estado de probabilidad a partir de una pluralidad de estados de
probabilidad representativos, presentando el procedimiento la
siguiente etapa:
- descodificar el símbolo codificado, llevándose a cabo las siguientes subetapas:
- mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- realizar la división de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo,
presentando la subetapa de mapeo la aplicación
de una operación de enmascaramiento de bits y desplazamiento a una
representación binaria/interna del ordenador de la anchura de
intervalo actual, concretamente según la siguiente regla de cálculo
q_index = (R >> q) & Qmask, representando Qmask una
máscara de bits elegida de manera adecuada en función del número de
índices de cuantificación representativos, R la anchura de intervalo
actual y q un número de bits.
10. Procedimiento según la reivindicación 9, en
el que la descodificación tiene lugar además mediante la siguiente
etapa:
- actualizar la anchura de intervalo actual utilizando el valor de anchura de subintervalo, para obtener una nueva anchura de intervalo actualizada.
11. Procedimiento según la reivindicación 9 ó
10, en el que el valor de anchura de subintervalo indica una anchura
de un subintervalo para un símbolo codificado con un estado menos
probable a partir de un intervalo actual con la anchura de intervalo
actual.
12. Procedimiento según una de las
reivindicaciones 9 a 11, en el que la actualización de la anchura de
intervalo actual se realiza además en función de un valor situado
dentro de un nuevo subintervalo, que está caracterizado por
la anchura de subintervalo actual y el valor situado dentro de un
nuevo subintervalo.
13. Procedimiento según la reivindicación 12, en
el que la descodificación se realiza además mediante la siguiente
subetapa:
- igualar el estado binario del símbolo codificado con uno de entre un estado no más probable y uno más probable en función de si el valor situado dentro del nuevo subintervalo es mayor o menor que una diferencia de la anchura de intervalo actual y el valor de anchura de subintervalo.
14. Procedimiento según una de las
reivindicaciones 12 ó 13, en el que la codificación se realiza
además mediante una actualización del valor situado dentro del
nuevo subintervalo con un siguiente bit que va a introducirse
mediante lectura.
15. Procedimiento según una de las
reivindicaciones 12 a 14, que presenta además la siguiente
etapa:
actualizar la estimación de probabilidad,
presentando la actualización de la estimación de probabilidad la
consulta, con el índice de probabilidad, en una tabla de regla de
transición LPS (Next_State_LPS), para obtener un nuevo índice de
probabilidad, si el valor situado dentro del nuevo subintervalo es
mayor que una diferencia de la anchura de intervalo actual y el
valor de anchura de subintervalo, y la consulta, con el índice de
probabilidad, en una tabla de regla de transición MPS
(Next_State_MPS), para obtener un nuevo índice de probabilidad, si
el valor situado dentro del nuevo subintervalo es menor que una
diferencia de la anchura de intervalo actual y el valor de anchura
de subintervalo.
16. Procedimiento según una de las
reivindicaciones 12 a 15, que presenta además el cambio de un valor
que indica el estado más probable del símbolo codificado de un
estado indicado originalmente a un estado binario diferente, si el
índice de probabilidad es similar a un índice de probabilidad
predeterminado y el valor situado dentro del nuevo subintervalo es
mayor que una diferencia de la anchura de intervalo actual y el
valor de anchura de subintervalo.
17. Procedimiento según una de las
reivindicaciones anteriores, en el que la anchura de intervalo
actual está representada con una precisión de b bits y el valor de
anchura de subintervalo obtenido de la tabla de división de
intervalo con una precisión de b-2 bits.
18. Procedimiento según una de las
reivindicaciones anteriores, en el que la subetapa de mapeo presenta
la aplicación de una operación de desplazamiento a una
representación binaria/interna del ordenador de la anchura de
intervalo actual, para obtener un valor cuantificado para la
anchura de intervalo actual, y presenta un acceso aguas abajo a una
tabla (Qtab), para obtener el índice de cuantificación.
\newpage
19. Procedimiento según una de las
reivindicaciones anteriores, en el que en la tabla de división de
intervalo están depositados valores para la anchura de intervalo
actual correspondientes a todos los índices de cuantificación
posibles y a todos los índices de probabilidad como valores de
producto entre índice de cuantificación, y en una tabla Rtab.
20. Procedimiento según una de las
reivindicaciones anteriores, que presenta además la siguiente
etapa:
- actualizar la estimación de probabilidad, realizándose la actualización de la estimación de probabilidad mediante reglas de transición, indicando las reglas de transición, qué nuevo estado de probabilidad de la pluralidad de estados de probabilidad se utiliza, partiendo del símbolo que va a codificarse o codificado, para un siguiente símbolo que va a codificarse o codificado.
21. Procedimiento según una de las
reivindicaciones anteriores, que presenta además la siguiente
etapa:
- actualizar la estimación de probabilidad, presentando la actualización de la estimación de probabilidad la consulta, con el índice de probabilidad, en una tabla de regla de transición (Next_State_LPS), para obtener un nuevo índice de probabilidad.
22. Procedimiento según una de las
reivindicaciones anteriores, en el que el número de posibles índices
de cuantificación y/o el número de estados de probabilidad se
eligen en función de la precisión preestablecida de la codificación
y/o en función del espacio de memoria disponible.
23. Procedimiento según una de las
reivindicaciones anteriores, que presenta además la siguiente
subetapa:
- renormalizar el nuevo punto de partida actualizado y la nueva anchura de intervalo actualizada.
24. Procedimiento según una de las
reivindicaciones anteriores, en el que en caso de existir una
distribución de probabilidades uniforme
- -
- en la codificación se realiza la siguiente regla de cálculo:
\hskip1cm9
- o se realiza la siguiente regla de cálculo:
\hskip1cm10
- y como última alternativa se realiza una renormalización con valores umbral de decisión duplicados y no se efectúa ningún duplicado de L y R,
- -
- en la descodificación según la reivindicación 13 se realiza la siguiente regla de cálculo:
\hskip0,5cm11
- o la siguiente regla de cálculo:
- 3.
- extraer mediante lectura un bit y actualizar V
\newpage
- 4.
- determinar el bit, según la posición del subintervalo:
\hskip0,5cm12
25. Procedimiento según una de las
reivindicaciones anteriores, en el que la inicialización de los
modelos de probabilidad se realiza en función de un parámetro de
cuantificación SliceQP y parámetros de modelo preestablecidos m y
n, describiendo SliceQP el parámetro de cuantificación
preestablecido al inicio de un sector y m y n los parámetros de
modelo.
26. Procedimiento según una de las
reivindicaciones anteriores, en el que la inicialización de los
modelos de probabilidad comprende las siguientes etapas:
\hskip0,3cm13
describiendo valMPS el bit
correspondiente al MPS, SliceQP el parámetro de cuantificación
preestablecido al inicio de un sector y m y n los parámetros de
modelo.
27. Procedimiento según una de las
reivindicaciones anteriores, en el que la estimación de probabilidad
de los estados se realiza mediante una máquina de estados finita
(finite state machine; FSM).
28. Procedimiento según una de las
reivindicaciones anteriores, en el que la generación de los estados
de probabilidad se realiza fuera de línea.
29. Procedimiento según una de las
reivindicaciones anteriores, en el que la elección de los estados
depende de la estadística de los datos que van a codificarse y/o
del número de los estados.
30. Disposición para la codificación aritmética
de un símbolo que va a codificarse con estado binario basándose en
una anchura de intervalo R actual y una probabilidad que representa
una estimación de probabilidad para el símbolo que va a
codificarse, estando representada la probabilidad por un índice de
probabilidad para el direccionamiento de un estado de probabilidad
a partir de una pluralidad de estados de probabilidad
representativos, presentando el dispositivo la siguiente
característica:
- un medio para la codificación del símbolo que va a codificarse, que presenta los siguientes medios:
- un medio para el mapeo de la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- un medio para realizar la subdivisión de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo, estando configurado el medio de mapeo para aplicar una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index = (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
31. Disposición para la descodificación
aritmética de un símbolo codificado con estado binario basándose en
una anchura de intervalo R actual y una probabilidad que representa
una estimación de probabilidad para el símbolo codificado, estando
representada la probabilidad por un índice de probabilidad para el
direccionamiento de un estado de probabilidad a partir de una
pluralidad de estados de probabilidad representativos, presentando
el dispositivo la siguiente característica:
- un medio para la descodificación del símbolo codificado, que presenta los siguientes medios:
- un medio para el mapeo de la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos: y
- un medio para realizar la subdivisión de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo, estando configurado el medio de mapeo para aplicar una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index = (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
32. Programa informático, que permite a un
ordenador, una vez cargado en la memoria del ordenador, llevar a
cabo un procedimiento para la codificación aritmética de un símbolo
que va a codificarse con estado binario basándose en una anchura de
intervalo R actual y una probabilidad que representa una estimación
de probabilidad para el símbolo que va a codificarse, estando
representada la probabilidad por un índice de probabilidad para el
direccionamiento de un estado de probabilidad a partir de una
pluralidad de estados de probabilidad representativos, presentando
el procedimiento la siguiente etapa:
- codificar el símbolo que va a codificarse, llevándose a cabo las siguientes subetapas:
- mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- realizar la subdivisión de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo,
- presentando la subetapa de mapeo la aplicación de una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index = (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
33. Programa informático, que permite a un
ordenador, una vez cargado en la memoria del ordenador, realizar un
procedimiento para la descodificación aritmética de un símbolo
codificado con estado binario basándose en una anchura de intervalo
R actual y una probabilidad que representa una estimación de
probabilidad para el símbolo codificado, estando representada la
probabilidad por un índice de probabilidad de un estado de
probabilidad a partir de una pluralidad de estados de probabilidad
representativos, presentando el procedimiento la siguiente
etapa:
- descodificar el símbolo codificado, llevándose a cabo las siguientes subetapas:
- mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- realizar la división de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo, presentando la subetapa de mapeo la aplicación de una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index = (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
34. Medio de almacenamiento legible por
ordenador, en el que está almacenado un programa, que permite a un
ordenador, una vez cargado en la memoria del ordenador, realizar un
procedimiento para la codificación aritmética de un símbolo que va
a codificarse con estado binario basándose en una anchura de
intervalo R actual y una probabilidad que representa una estimación
de probabilidad para el símbolo que va a codificarse, estando
representada la probabilidad por un índice de probabilidad para el
direccionamiento de un estado de probabilidad a partir de una
pluralidad de estados de probabilidad representativos, presentando
el procedimiento la siguiente etapa:
- codificar el símbolo que va a codificarse, llevándose a cabo las siguientes subetapas:
- mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- realizar la subdivisión de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo, presentando la subetapa de mapeo la aplicación de una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index= (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
35. Medio de almacenamiento legible por
ordenador, en el que está almacenado un programa, que permite a un
ordenador, una vez cargado en la memoria del ordenador, realizar un
procedimiento para la descodificación aritmética de un símbolo
codificado con estado binario basándose en una anchura de intervalo
R actual y una probabilidad que representa una estimación de
probabilidad para el símbolo codificado, estando representada la
probabilidad por un índice de probabilidad de un estado de
probabilidad a partir de una pluralidad de estados de probabilidad
representativos, presentando el procedimiento la siguiente
etapa:
- descodificar el símbolo codificado, llevándose a cabo las siguientes subetapas:
- mapear la anchura de intervalo actual con un índice de cuantificación a partir de una pluralidad de índices de cuantificación representativos; y
- realizar la división de intervalo mediante el acceso, utilizando el índice de cuantificación y el índice de probabilidad, a una tabla de división de intervalo, para obtener un valor de anchura de subintervalo, presentando la subetapa de mapeo la aplicación de una operación de enmascaramiento de bits y desplazamiento a una representación binaria/interna del ordenador de la anchura de intervalo actual, concretamente según la siguiente regla de cálculo q_index = (R >> q) & Qmask, representando Qmask una máscara de bits elegida de manera adecuada en función del número de índices de cuantificación representativos, R la anchura de intervalo actual y q un número de bits.
36. Medio de almacenamiento legible por
ordenador, en el que está almacenado un programa, que permite a un
ordenador, una vez cargado en la memoria del ordenador, realizar un
procedimiento según una de las reivindicaciones 32 y 33.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE10220962 | 2002-05-02 | ||
| DE10220962 | 2002-05-02 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2316749T3 true ES2316749T3 (es) | 2009-04-16 |
Family
ID=29285283
Family Applications (6)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES03725141T Expired - Lifetime ES2316749T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y disposicion para la codificacion y la descodificacion aritmetica de estados binarios asi como programa informatico correspondiente y medio de almacenamiento legible por ordenador correspondiente. |
| ES08020010.8T Expired - Lifetime ES2442215T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas de estados binarios y programa informático correspondiente y soporte de almacenamiento correspondiente legible por ordenador |
| ES10185209.3T Expired - Lifetime ES2442190T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas utilizando una pluralidad de tablas de consulta |
| ES08020113.0T Expired - Lifetime ES2442173T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas con utilización de varias tablas |
| ES10185219.2T Expired - Lifetime ES2439996T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas de estados binarios y programa informático correspondiente y soporte de almacenamiento correspondiente legible por ordenador |
| ES10185215.0T Expired - Lifetime ES2442174T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas utilizando varias tablas de consulta |
Family Applications After (5)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES08020010.8T Expired - Lifetime ES2442215T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas de estados binarios y programa informático correspondiente y soporte de almacenamiento correspondiente legible por ordenador |
| ES10185209.3T Expired - Lifetime ES2442190T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas utilizando una pluralidad de tablas de consulta |
| ES08020113.0T Expired - Lifetime ES2442173T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas con utilización de varias tablas |
| ES10185219.2T Expired - Lifetime ES2439996T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas de estados binarios y programa informático correspondiente y soporte de almacenamiento correspondiente legible por ordenador |
| ES10185215.0T Expired - Lifetime ES2442174T3 (es) | 2002-05-02 | 2003-05-02 | Procedimiento y dispositivo de codificación y descodificación aritméticas utilizando varias tablas de consulta |
Country Status (12)
| Country | Link |
|---|---|
| US (1) | US6943710B2 (es) |
| EP (7) | EP2037412B1 (es) |
| JP (3) | JP3989485B2 (es) |
| KR (1) | KR100733795B1 (es) |
| AT (1) | ATE421802T1 (es) |
| DE (1) | DE50311129D1 (es) |
| DK (6) | DK2068448T3 (es) |
| ES (6) | ES2316749T3 (es) |
| HK (5) | HK1127525A1 (es) |
| PT (6) | PT2037412E (es) |
| SI (1) | SI1550219T1 (es) |
| WO (1) | WO2003094355A2 (es) |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7408486B2 (en) * | 2003-04-21 | 2008-08-05 | Qbit Corporation | System and method for using a microlet-based modem |
| GB2398191B (en) * | 2004-03-10 | 2004-12-22 | David Asher Jaffa | Adaptive quantiser |
| KR100694098B1 (ko) * | 2005-04-04 | 2007-03-12 | 한국과학기술원 | 산술 복호 방법 및 그 장치 |
| US8572018B2 (en) * | 2005-06-20 | 2013-10-29 | New York University | Method, system and software arrangement for reconstructing formal descriptive models of processes from functional/modal data using suitable ontology |
| JP4547503B2 (ja) * | 2006-03-07 | 2010-09-22 | 国立大学法人徳島大学 | 算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体 |
| US7262722B1 (en) * | 2006-06-26 | 2007-08-28 | Intel Corporation | Hardware-based CABAC decoder with parallel binary arithmetic decoding |
| JP4865509B2 (ja) * | 2006-11-01 | 2012-02-01 | キヤノン株式会社 | 復号装置及び復号方法 |
| JP4717780B2 (ja) | 2006-11-01 | 2011-07-06 | キヤノン株式会社 | 符号化装置及びその制御方法 |
| JP4785706B2 (ja) * | 2006-11-01 | 2011-10-05 | キヤノン株式会社 | 復号装置及び復号方法 |
| US7443318B2 (en) * | 2007-03-30 | 2008-10-28 | Hong Kong Applied Science And Technology Research Institute Co. Ltd. | High speed context memory implementation for H.264 |
| TWI330006B (en) * | 2007-07-27 | 2010-09-01 | Lite On It Corp | Encoding method and encoder for generating balanced code or constant weighted code |
| JP4382840B2 (ja) * | 2007-08-20 | 2009-12-16 | Ｎｔｔエレクトロニクス株式会社 | ２値算術符号化装置 |
| US20090231173A1 (en) * | 2008-03-14 | 2009-09-17 | Daniel Kilbank | System and method for using a microlet-based modem |
| JP5133950B2 (ja) * | 2009-07-16 | 2013-01-30 | 日本電信電話株式会社 | コンテクスト適応エントロピ符号化方法および装置，コンテクスト適応エントロピ復号方法および装置，並びにそれらのプログラム |
| JP5047244B2 (ja) * | 2009-09-01 | 2012-10-10 | 日本電信電話株式会社 | コンテクスト適応エントロピ符号化方法および装置，コンテクスト適応エントロピ復号方法および装置，並びにそれらのプログラム |
| KR101615384B1 (ko) * | 2010-04-05 | 2016-04-25 | 삼성전자주식회사 | 통신 시스템에서의 채널 부호화 장치 및 방법 |
| PL2559166T3 (pl) | 2010-04-13 | 2018-04-30 | Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. | Koder i dekoder dzielący interwał prawdopodobieństwa |
| JP4936574B2 (ja) * | 2011-03-02 | 2012-05-23 | キヤノン株式会社 | 符号化装置及びその制御方法 |
| JP5925884B2 (ja) | 2011-06-16 | 2016-05-25 | ジーイー ビデオ コンプレッション エルエルシー | エントロピー符号化におけるコンテキスト初期化 |
| UA114674C2 (uk) | 2011-07-15 | 2017-07-10 | ДЖ.І. ВІДІЕУ КЕМПРЕШН, ЛЛСі | Ініціалізація контексту в ентропійному кодуванні |
| US9871537B2 (en) | 2011-10-27 | 2018-01-16 | Qualcomm Incorporated | Mapping states in binary arithmetic coder for video coding |
| EP2810371B1 (en) * | 2012-01-30 | 2017-12-20 | Fraunhofer Gesellschaft zur Förderung der angewandten Forschung e.V. | Binary arithmetic coding scheme |
| KR101910376B1 (ko) | 2014-06-29 | 2019-01-04 | 엘지전자 주식회사 | 연결된 rom-ram 테이블에 기초하여 산술 코딩을 수행하는 방법 및 장치 |
| US10757412B2 (en) * | 2017-01-03 | 2020-08-25 | Avago Technologies International Sales Pte. Limited | Architecture flexible binary arithmetic coding system |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4891643A (en) * | 1986-09-15 | 1990-01-02 | International Business Machines Corporation | Arithmetic coding data compression/de-compression by selectively employed, diverse arithmetic coding encoders and decoders |
| US5475388A (en) * | 1992-08-17 | 1995-12-12 | Ricoh Corporation | Method and apparatus for using finite state machines to perform channel modulation and error correction and entropy coding |
| US5272478A (en) * | 1992-08-17 | 1993-12-21 | Ricoh Corporation | Method and apparatus for entropy coding |
| FR2703483B1 (fr) * | 1993-03-29 | 1995-06-02 | Digital Equipment Int | Dispositif de mise à jour de la valeur de code dans la méthode du codage arithmétique. |
| US5912636A (en) * | 1996-09-26 | 1999-06-15 | Ricoh Company, Ltd. | Apparatus and method for performing m-ary finite state machine entropy coding |
| JP3367370B2 (ja) * | 1997-03-14 | 2003-01-14 | 三菱電機株式会社 | 適応符号化方法 |
| US6757436B2 (en) * | 1997-06-19 | 2004-06-29 | Electroncs For Imaging, Inc. | Methods and apparatus for data compression based on modeling schemes |
| US5970174A (en) * | 1997-06-19 | 1999-10-19 | Electronics For Imaging | Method and apparatus for data compression and gray value estimation |
| US5973626A (en) * | 1998-03-17 | 1999-10-26 | Cornell Research Foundation, Inc. | Byte-based prefix encoding |
| EP1465349A1 (en) * | 2003-03-31 | 2004-10-06 | Interuniversitair Microelektronica Centrum Vzw | Embedded multiple description scalar quantizers for progressive image transmission |
| US6894628B2 (en) * | 2003-07-17 | 2005-05-17 | Fraunhofer-Gesellschaft Zur Forderung Der Angewandten Forschung E.V. | Apparatus and methods for entropy-encoding or entropy-decoding using an initialization of context variables |
-
2003
- 2003-05-02 WO PCT/EP2003/004654 patent/WO2003094355A2/de active Application Filing
- 2003-05-02 PT PT80200108T patent/PT2037412E/pt unknown
- 2003-05-02 PT PT80201130T patent/PT2068448E/pt unknown
- 2003-05-02 DK DK08020113.0T patent/DK2068448T3/da active
- 2003-05-02 PT PT03725141T patent/PT1550219E/pt unknown
- 2003-05-02 EP EP08020010.8A patent/EP2037412B1/de not_active Expired - Lifetime
- 2003-05-02 ES ES03725141T patent/ES2316749T3/es not_active Expired - Lifetime
- 2003-05-02 EP EP03725141A patent/EP1550219B1/de not_active Expired - Lifetime
- 2003-05-02 DK DK08020010.8T patent/DK2037412T3/da active
- 2003-05-02 ES ES08020010.8T patent/ES2442215T3/es not_active Expired - Lifetime
- 2003-05-02 PT PT101852150T patent/PT2296282E/pt unknown
- 2003-05-02 EP EP05009246A patent/EP1571755A3/de not_active Withdrawn
- 2003-05-02 ES ES10185209.3T patent/ES2442190T3/es not_active Expired - Lifetime
- 2003-05-02 EP EP08020113.0A patent/EP2068448B1/de not_active Expired - Lifetime
- 2003-05-02 EP EP10185209.3A patent/EP2326013B1/de not_active Expired - Lifetime
- 2003-05-02 KR KR1020047017090A patent/KR100733795B1/ko active IP Right Grant
- 2003-05-02 EP EP10185215.0A patent/EP2296282B1/de not_active Expired - Lifetime
- 2003-05-02 PT PT101852093T patent/PT2326013E/pt unknown
- 2003-05-02 DK DK10185215.0T patent/DK2296282T3/da active
- 2003-05-02 PT PT101852192T patent/PT2290612E/pt unknown
- 2003-05-02 ES ES08020113.0T patent/ES2442173T3/es not_active Expired - Lifetime
- 2003-05-02 SI SI200331516T patent/SI1550219T1/sl unknown
- 2003-05-02 ES ES10185219.2T patent/ES2439996T3/es not_active Expired - Lifetime
- 2003-05-02 DK DK10185219.2T patent/DK2290612T3/da active
- 2003-05-02 DK DK03725141T patent/DK1550219T3/da active
- 2003-05-02 AT AT03725141T patent/ATE421802T1/de active
- 2003-05-02 JP JP2004502472A patent/JP3989485B2/ja not_active Expired - Lifetime
- 2003-05-02 ES ES10185215.0T patent/ES2442174T3/es not_active Expired - Lifetime
- 2003-05-02 DK DK10185209.3T patent/DK2326013T3/da active
- 2003-05-02 EP EP10185219.2A patent/EP2290612B1/de not_active Expired - Lifetime
- 2003-05-02 DE DE50311129T patent/DE50311129D1/de not_active Expired - Lifetime
- 2003-12-04 US US10/727,801 patent/US6943710B2/en not_active Expired - Lifetime
-
2005
- 2005-07-25 JP JP2005213727A patent/JP4054345B2/ja not_active Expired - Lifetime
-
2007
- 2007-11-01 JP JP2007284653A patent/JP4709821B2/ja not_active Expired - Lifetime
-
2009
- 2009-06-10 HK HK09105184.6A patent/HK1127525A1/xx not_active IP Right Cessation
- 2009-06-10 HK HK11108764.4A patent/HK1155000A1/xx not_active IP Right Cessation
- 2009-10-02 HK HK09109109.0A patent/HK1130372A1/xx not_active IP Right Cessation
-
2011
- 2011-08-15 HK HK11108520.9A patent/HK1154430A1/xx not_active IP Right Cessation
- 2011-11-08 HK HK11112033.1A patent/HK1157948A1/xx not_active IP Right Cessation
Also Published As
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| ES2316749T3 (es) | Procedimiento y disposicion para la codificacion y la descodificacion aritmetica de estados binarios asi como programa informatico correspondiente y medio de almacenamiento legible por ordenador correspondiente. | |
| Núñez et al. | Gbit/s lossless data compression hardware | |
| KR102588145B1 (ko) | 엔트로피 인코딩 및 디코딩 방식 | |
| Salomon | Variable-length codes for data compression | |
| US5973626A (en) | Byte-based prefix encoding | |
| US9094039B2 (en) | Efficient deflate decompression | |
| JP4179640B2 (ja) | 情報信号の算術符号化及び復号 | |
| US20110128167A1 (en) | Unicode-compatible dictionary compression | |
| US5708430A (en) | High speed variable length code decoding apparatus | |
| Hsieh et al. | An adaptive multialphabet arithmetic coding for video compression | |
| Li et al. | Lossless compression algorithms | |
| Sun et al. | Lossless Coders | |
| Bloom | New Techniques in Context Modeling and Arithmetic Encoding. | |
| Aulí-Llinàs | Fast and efficient entropy coding architectures for massive data compression. Technologies 2023, 1, 0 | |
| Mahapatra et al. | Parallel implementation of a multialphabet arithmetic coding algorithm | |
| Ribeiro | Data Compression Algorithms in FPGAs | |
| Kasera et al. | A survey of lossless data compression techniques | |
| Salomon et al. | Dictionary methods | |
| Reddy et al. | LosslessGrayscaleImage Compression Using Intra Pixel Redundancy | |
| Srivastava et al. | Data Compression Algorithms and Techniques | |
| Lelewer | Data compression on machines with limited memory | |
| JPH11163737A (ja) | 情報源の符号化及び復号化の高速化装置 | |
| KR20050037307A (ko) | Ｎ-트리 검색에 기초한 허프만 디코딩 방법 및 장치 | |
| KR20060116384A (ko) | 균형 이진 검색 트리를 이용한 허프만 디코딩 방법 및디코딩 장치 |