Codificación en Golomb

La codificación Golomb es un método de compresión de datos sin pérdidas que utiliza una familia de códigos de compresión de datos inventados por Solomon W. Golomb en la década de 1960. Los alfabetos que siguen una distribución geométrica tendrán un código Golomb como código de prefijo óptimo , ^{[ 1 ]} lo que hace que la codificación Golomb sea muy adecuada para situaciones en las que la aparición de valores pequeños en el flujo de entrada es significativamente más probable que la de valores grandes.

Codificación de arroz

La codificación Rice (inventada por Robert F. Rice ) consiste en utilizar un subconjunto de la familia de códigos Golomb para generar un código de prefijo más simple (aunque posiblemente subóptimo). Rice empleó este conjunto de códigos en un esquema de codificación adaptativa ; el término "codificación Rice" puede referirse tanto a dicho esquema adaptativo como al uso de ese subconjunto de códigos Golomb. Mientras que un código Golomb tiene un parámetro ajustable que puede ser cualquier valor entero positivo, los códigos Rice son aquellos cuyo parámetro ajustable es una potencia de dos. Esto facilita su uso en computadoras, ya que la multiplicación y la división por 2 se pueden implementar de forma más eficiente en aritmética binaria .

Rice se sintió motivado a proponer este subconjunto más simple debido a que las distribuciones geométricas a menudo varían con el tiempo, no se conocen con precisión, o ambas cosas, por lo que seleccionar el código aparentemente óptimo podría no ser muy ventajoso.

La codificación Rice se utiliza como etapa de codificación entrópica en varios métodos de compresión de imágenes sin pérdidas y de datos de audio .

Descripción general

Construcción de códigos

Golomb coding uses a tunable parameter $M$ to divide an input value $x$ into two parts: $q$ , the result of a division by $M$ , and $r$ , the remainder. The quotient is sent in unary coding, followed by the remainder in truncated binary encoding. When $M=1$ , Golomb coding is equivalent to unary coding.

Golomb–Rice codes can be thought of as codes that indicate a number by the position of the bin ( $q$ ), and the offset within the bin ( $r$ ). The example figure shows the position $q$ and offset $r$ for the encoding of integer $x$ using Golomb–Rice parameter $M = 3$ , with source probabilities following a geometric distribution with $p (0) = 0.2$ .

Formally, the two parts are given by the following expression, where $x$ is the nonnegative integer being encoded:

$q=\left\lfloor {\frac {x}{M}}\right\rfloor$

and

$r=x-qM.$

This image shows the redundancy, in bits, of the Golomb code, when $M$ is chosen optimally, for $1 - p (0) \geq 0.45$

Both $q$ and $r$ will be encoded using variable numbers of bits: $q$ by a unary code, and $r$ by $b$ bits for Rice code, or a choice between $b$ and $b +1$ bits for Golomb code (i.e. $M$ is not a power of 2), with $b=\lfloor \log _{2}(M)\rfloor$ . If $r<2^{b+1}-M$ , then use $b$ bits to encode $r$ ; otherwise, use $b$ +1 bits to encode $r$ . Clearly, $b=\log _{2}(M)$ if $M$ is a power of 2 and we can encode all values of $r$ with $b$ bits.

The integer $x$ treated by Golomb was the run length of a Bernoulli process, which has a geometric distribution starting at 0. The best choice of parameter $M$ is a function of the corresponding Bernoulli process, which is parameterized by $p=P(x=0)$ the probability of success in a given Bernoulli trial. $M$ is either the median of the distribution or the median ±1. It can be determined by these inequalities: $(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$ which are solved by $M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil .$

For the example with $p (0) = 0.2$ : $M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3.$

El código de Golomb para esta distribución es equivalente al código de Huffman para las mismas probabilidades, si fuera posible calcular el código de Huffman para el conjunto infinito de valores fuente.

Utilizar con números enteros con signo.

El esquema de Golomb fue diseñado para codificar secuencias de números no negativos. Sin embargo, se puede extender fácilmente para aceptar secuencias que contengan números negativos utilizando un esquema de superposición e intercalación , en el que todos los valores se reasignan a algún número positivo de una manera única y reversible. La secuencia comienza: 0, −1, 1, −2, 2, −3, 3, −4, 4, ... El n -ésimo valor negativo (es decir, ⁠ $-n$ ⁠ ) se asigna al n ^-ésimo número impar ( ⁠ $2n-1$ ⁠ ), y el m ^-ésimo valor positivo se asigna al m -ésimo número par ( ⁠ $2m$ ⁠ ). Esto se puede expresar matemáticamente de la siguiente manera: un valor positivo $x$ se asigna a ( $x'=2|x|=2x,\ x\geq 0$ ), y un valor negativo $y$ se asigna a ( $y'=2|y|-1=-2y-1,\ y<0$ Dicho código puede utilizarse por simplicidad, aunque sea subóptimo. Los códigos verdaderamente óptimos para distribuciones geométricas bilaterales incluyen múltiples variantes del código de Golomb, dependiendo de los parámetros de la distribución, incluido este. ^{[ 2 ]}

Algoritmo simple

A continuación se muestra la codificación Rice-Golomb, donde el código de resto utiliza una codificación binaria truncada simple, también llamada "codificación Rice" (otras codificaciones binarias de longitud variable, como las aritméticas o las de Huffman, son posibles para los códigos de resto, si la distribución estadística de los códigos de resto no es plana, y en particular cuando no se utilizan todos los restos posibles después de la división). En este algoritmo, si el parámetro M es una potencia de 2, se vuelve equivalente a la codificación Rice más simple:

Fije el parámetro M a un valor entero.
Para N , el número que se va a codificar, encuentre
1. cociente = q = piso( N / M )
2. resto = r = N módulo M
Generar palabra clave
1. El formato del código : <Código del cociente><Código del resto>, donde
2. Código cociente (en codificación unaria )
  1. Escribe una cadena de longitud q de 1 bit (o de 0 bits).
  2. Escriba un bit 0 (o un bit 1, respectivamente).
3. Código restante (en codificación binaria truncada )
  1. Dejar $b=\lfloor \log _{2}(M)\rfloor$ $b=\lfloor \log _{2}(M)\rfloor$
    1. Si $r<2^{b+1}-M$ codificar r en representación binaria usando b bits.
    2. Si $r\geq 2^{b+1}-M$ codifica el número $r+2^{b+1}-M$ en representación binaria usando b + 1 bits.

Descodificación:

Decodifica la representación unaria de q (cuenta el número de 1 al principio del código).
Omitir el delimitador 0
Dejar $b=\lfloor \log _{2}(M)\rfloor$ $b=\lfloor \log _{2}(M)\rfloor$
1. Interpreta los siguientes b bits como un número binario r' . Si $r'<2^{b+1}-M$ se mantiene, luego el resto $r=r'$
2. De lo contrario, interprete b + 1 bits como un número binario r' , el resto viene dado por $r=r'-2^{b+1}+M$
Calcular $N=q*M+r$

Ejemplo

Establezca $M = 10.$ Por lo tanto $b=\lfloor \log _{2}(10)\rfloor =3$ . El límite es $2^{b+1}-M=16-10=6$ .

Por ejemplo, con una codificación Rice-Golomb usando el parámetro $M = 10$ , el número decimal 42 se dividiría primero en $q$ = 4 y $r$ = 2, y se codificaría como qcode( $q$ ),rcode( $r$ ) = qcode(4),rcode(2) = 11110,010 (no es necesario codificar la coma separadora en el flujo de salida, porque el 0 al final del código $q$ es suficiente para indicar cuándo termina $q y comienza$ $r$ ; tanto el código q como el código r están autodelimitados).

Uso para codificación de longitud de ejecución

Tenga en cuenta que $p$ y $1 - p$ están invertidos en esta sección en comparación con su uso en secciones anteriores.

Dado un alfabeto de dos símbolos, o un conjunto de dos eventos, P y Q , con probabilidades p y ( $1 - p$ ) respectivamente, donde $p \geq 1/2$ , la codificación de Golomb se puede utilizar para codificar secuencias de cero o más P ' separadas por Q ' individuales . En esta aplicación, la mejor configuración del parámetro M es el entero más cercano a $-{\frac {1}{\log _{2}p}}$ Cuando p = 1/2, M = 1, y el código de Golomb corresponde a unario ( $n \geq 0$ P ′ seguido de una Q se codifica como n unos seguidos de un cero). Si se desea un código más simple, se puede asignar el parámetro de Golomb-Rice $b$ (es decir, el parámetro de Golomb). $M=2^{b}$ ) al entero más cercano a $-\log _{2}(-\log _{2}p)$ Aunque no siempre es el mejor parámetro, suele ser el mejor parámetro de Rice y su rendimiento de compresión es bastante similar al del código Golomb óptimo. (El propio Rice propuso utilizar varios códigos para los mismos datos con el fin de determinar cuál era el mejor. Posteriormente, un investigador del JPL propuso varios métodos para optimizar o estimar el parámetro del código. ^{[ 3 ]} )

Considere usar un código Rice con una porción binaria que tenga $b$ bits para codificar secuencias de longitud variable donde P tiene una probabilidad $p$ . Si $\mathbb {P} [{\text{bit es parte de }}k{\text{-run}}]$ es la probabilidad de que un bit forme parte de una secuencia $de k$ bits ( $k-1$ P s y una Q ) y $({\text{relación de compresión de }}k{\text{-carrera}})$ es la relación de compresión de esa ejecución, entonces la relación de compresión esperada es ${\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}$

La compresión se expresa a menudo en términos de $1-\mathbb {E} [{\text{compression ratio}}]$ , la proporción comprimida. Para $p\approx 1$ El enfoque de codificación de longitud de ejecución da como resultado índices de compresión cercanos a la entropía . Por ejemplo, utilizando el código Rice. $b=6$ para $p=0.99$ rendimientos91,89% de compresión, mientras que el límite de entropía es91,92% .

Codificación adaptativa de Golomb-Rice de longitud variable

Cuando se desconoce la distribución de probabilidad de los números enteros, no es posible determinar el parámetro óptimo para un codificador de Golomb-Rice. Por lo tanto, en muchas aplicaciones se utiliza un enfoque de dos pasos: primero, se analiza el bloque de datos para estimar su función de densidad de probabilidad (FDP). A partir de esta FDP estimada, se determina el parámetro de Golomb-Rice. Una variante más sencilla consiste en asumir que la FDP pertenece a una familia parametrizada, estimar sus parámetros a partir de los datos y, posteriormente, calcular el parámetro óptimo de Golomb-Rice. Este es el enfoque utilizado en la mayoría de las aplicaciones que se describen a continuación.

Un enfoque alternativo para codificar eficientemente datos enteros cuya función de densidad de probabilidad (PDF) se desconoce o varía, es utilizar un codificador adaptativo hacia atrás. El codificador RLGREsto se logra mediante un algoritmo muy simple que ajusta el parámetro de Golomb-Rice hacia arriba o hacia abajo, según el último símbolo codificado. Un decodificador puede seguir la misma regla para rastrear la variación de los parámetros de codificación, por lo que no es necesario transmitir información adicional, solo los datos codificados. Suponiendo una función de densidad de probabilidad gaussiana generalizada, que abarca un amplio rango de estadísticas presentes en datos como errores de predicción o coeficientes de transformación en códecs multimedia, el algoritmo de codificación RLGR puede tener un rendimiento excelente en este tipo de aplicaciones.

Aplicaciones

Numerosos códecs de señal utilizan un código Rice para predecir residuos. En los algoritmos predictivos, estos residuos tienden a seguir una distribución geométrica bilateral , donde los residuos pequeños son más frecuentes que los grandes. El código Rice se aproxima bastante al código Huffman para dicha distribución sin la sobrecarga de tener que transmitir la tabla Huffman. Una señal que no se ajusta a una distribución geométrica es una onda sinusoidal , ya que los residuos diferenciales crean una señal sinusoidal cuyos valores no forman una distribución geométrica (los valores de residuo más alto y más bajo tienen frecuencias de aparición altas similares; solo los residuos positivos y negativos medianos aparecen con menos frecuencia).

Varios códecs de audio sin pérdidas , como Shorten , ^{[ 4 ]} FLAC , ^{[ 5 ]} Apple Lossless y MPEG-4 ALS , utilizan un código Rice después del paso de predicción lineal (llamado "filtro FIR adaptativo" en Apple Lossless). La codificación Rice también se utiliza en el códec de imagen sin pérdidas FELICS .

El codificador Golomb-Rice se utiliza en la etapa de codificación de entropía de los códecs de imagen sin pérdida basados en el algoritmo Rice . Un experimento de este tipo produce el gráfico de relación de compresión que se muestra.

El esquema JPEG-LS utiliza Rice-Golomb para codificar los residuos de la predicción.

La versión adaptativa RLGR de la codificación Golomb-Rice mencionada anteriormenteSe utiliza para codificar el contenido de la pantalla en máquinas virtuales en el componente RemoteFX del Protocolo de Escritorio Remoto de Microsoft. También se utiliza en el reciente estándar G-PCC MPEG ISO/IEC 23090-9 para la compresión de atributos de nubes de puntos.

Véase también

Referencias

↑ Gallager, RG; van Voorhis, DC (1975). "Códigos fuente óptimos para alfabetos enteros distribuidos geométricamente". IEEE Transactions on Information Theory . 21 (2): 228– 230. doi : 10.1109/tit.1975.1055357 .
↑ Merhav, N.; Seroussi, G.; Weinberger, MJ (2000). "Codificación de fuentes con distribuciones geométricas bilaterales y parámetros desconocidos". IEEE Transactions on Information Theory . 46 (1): 229– 236. Bibcode : 2000ITIT...46..229M . doi : 10.1109/18.817520 .
↑ Kiely, A. (2004). Selección del parámetro de Golomb en la codificación Rice (Informe técnico). Laboratorio de Propulsión a Chorro . 42-159.
↑ "man shorten" . Archivado del original el 30-01-2014 . Recuperado el 07-12-2008 .
↑ "FLAC - Descripción general del formato" . xiph.org .

Lecturas adicionales

Golomb, Solomon W. (1966). Codificaciones de longitud de ejecución. IEEE Transactions on Information Theory, IT--12(3):399--401
Rice, Robert F.; Plaunt, R. (1971). "Codificación adaptativa de longitud variable para la compresión eficiente de datos de televisión de naves espaciales". IEEE Transactions on Communications . 16 (9): 889– 897. Bibcode : 1971ITCoT..19..889R . doi : 10.1109/TCOM.1971.1090789 .
Robert F. Rice (1979), " Algunas técnicas prácticas de codificación universal sin ruido ", Laboratorio de Propulsión a Chorro, Pasadena, California, Publicación JPL 79-22, marzo de 1979.
Witten, Ian Moffat, Alistair Bell, Timothy. «Gestión de gigabytes: compresión e indexación de documentos e imágenes». Segunda edición. Morgan Kaufmann Publishers, San Francisco, CA. 1999 ISBN 1-55860-570-3
David Salomon. "Compresión de datos", ISBN 0-387-95045-1.
HS Malvar, Codificación adaptativa de longitud de ejecución/Golomb-Rice de fuentes gaussianas generalizadas cuantificadas con estadísticas desconocidas , Actas de la Conferencia de Compresión de Datos, 2006.
Codificación de entropía RLGR , especificación abierta Microsoft MS-RDPRFX, códec RemoteFX para el protocolo de escritorio remoto.
S. Büttcher, CLA Clarke y GV Cormack. Recuperación de información: implementación y evaluación de motores de búsqueda. Archivado el 5 de octubre de 2020 en Wayback Machine . MIT Press, Cambridge, MA, 2010.