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 de Golomb como código de prefijo óptimo , [1] haciendo que la codificación de Golomb sea muy adecuada para situaciones en las que la ocurrencia de valores pequeños en el flujo de entrada es significativamente más probable que los valores grandes.
Codificación de arroz
La codificación de Rice (inventada por Robert F. Rice ) denota el uso de un subconjunto de la familia de códigos de Golomb para producir un código de prefijo más simple (pero posiblemente subóptimo). Rice utilizó este conjunto de códigos en un esquema de codificación adaptativa ; "Codificación de arroz" puede referirse a ese esquema adaptativo o al uso de ese subconjunto de códigos de 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 en los que el parámetro ajustable es una potencia de dos. Esto hace que los códigos de Rice sean convenientes para su uso en una computadora, ya que la multiplicación y división por 2 se pueden implementar de manera más eficiente en aritmética binaria .
Rice estaba motivado para proponer este subconjunto más simple debido al hecho de que las distribuciones geométricas a menudo varían con el tiempo, no se conocen con precisión, o ambos, 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 de entropía en varios métodos de compresión de imágenes sin pérdida y de datos de audio .
Descripción general
Construcción de códigos
La codificación de Golomb utiliza un parámetro ajustable dividir un valor de entrada en dos partes: , el resultado de una división por , y , el resto. El cociente se envía en codificación unaria , seguido del resto en codificación binaria truncada . Cuándo La codificación de Golomb es equivalente a la codificación unaria.
Los códigos de Golomb-Rice se pueden considerar como códigos que indican un número por la posición del contenedor ( q ) y el desplazamiento dentro del contenedor ( r ). La figura anterior muestra la posición qy el desplazamiento r para la codificación del entero N usando el parámetro M de Golomb-Rice .
Formalmente, las dos partes vienen dadas por la siguiente expresión, donde es el número que se codifica:
y
- .
El resultado final se ve así: .
Tenga en cuenta que puede ser de un número variable de bits. Específicamente,es solo b bits para el código Rice y cambia entre b -1 y b bits para el código Golomb (es decir, M no es una potencia de 2). Dejar. Si, luego use b -1 bits para codificar r . Si, luego use b bits para codificar r . Claramente,si M es una potencia de 2 y podemos codificar todos los valores de r con b bits.
El parámetro M es una función del correspondiente proceso de Bernoulli , que está parametrizado porla probabilidad de éxito en un ensayo de Bernoulli dado . es la mediana de la distribución o la mediana +/− 1. Puede determinarse mediante estas desigualdades:
que son resueltos por
- .
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.
Usar con enteros con signo
El esquema de Golomb fue diseñado para codificar secuencias de números no negativos. Sin embargo, se amplía fácilmente para aceptar secuencias que contienen 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 (2 m). Esto puede expresarse matemáticamente de la siguiente manera: un valor positivo está mapeado a () y un valor negativo está mapeado a (). Dicho código se puede utilizar para simplificar, incluso si es subóptimo. Los códigos verdaderamente óptimos para distribuciones geométricas de dos lados incluyen múltiples variantes del código Golomb, dependiendo de los parámetros de distribución, incluido este. [2]
Algoritmo simple
Observe a continuación que esta es la codificación Rice-Golomb, donde el código restante usa codificación binaria truncada simple, también llamada "codificación Rice" (otras codificaciones binarias de longitud variable, como codificaciones aritméticas o Huffman, son posibles para los códigos restantes, si el 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 a codificar, encuentre
- cociente = q = int [ N / M ]
- resto = r = N módulo M
- Generar palabra en clave
- El formato del código:
, donde ódigo> - Código de cociente (en codificación unaria )
- Escriba una cadena de longitud q de 1 bits (alternativamente, de 0 bits)
- Escribe un bit 0 (respectivamente, un bit 1)
- Código restante (en codificación binaria truncada )
- DEJAR
- Si código r en representación binaria usando b bits.
- Si codificar el número en representación binaria usando b + 1 bits.
- DEJAR
- El formato del código:
Ejemplo
Establezca M = 10. Por lo tanto. El corte es
|
|
Por ejemplo, con una codificación Rice-Golomb del parámetro M = 10, el número decimal 42 se dividiría primero en q = 4, r = 2 y se codificaría como qcode ( q ), rcode ( r ) = qcode (4 ), rcode (2) = 11110,010 (no necesita codificar la coma de separación en el flujo de salida, porque el 0 al final del código q es suficiente para decir cuándo termina q y comienza r ; tanto el código q y rcode están autodelimitados).
Usar para codificación de longitud de ejecución
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 ≥ 1/2, la codificación de Golomb se puede utilizar para codificar ejecuciones de cero o más P ' s separados por Q simples . En esta aplicación, la mejor configuración del parámetro M es el entero más cercano a. Cuando p = 1/2, M = 1, y el código de Golomb corresponde a unario ( n ≥ 0 P ' s 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 Golomb-Rice (es decir, parámetro de Golomb ) al entero más cercano a ; aunque no siempre es el mejor parámetro, suele ser el mejor parámetro de Rice y su rendimiento de compresión está bastante cerca del código Golomb óptimo. (El propio Rice propuso usar varios códigos para los mismos datos para determinar cuál era el mejor. Un investigador posterior 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 bits para codificar secuencias de longitud de ejecución donde P tiene una probabilidad. Si es la probabilidad de que un bit forme parte de un -bit ejecutar P s y una Q ) y es la relación de compresión de esa ejecución, entonces la relación de compresión esperada es
La compresión se expresa a menudo en términos de , la proporción comprimida. Para, el enfoque de codificación de longitud de ejecución da como resultado relaciones de compresión cercanas a la entropía . Por ejemplo, usando el código de Rice por rendimientos compresión, mientras que el límite de entropía es .
Codificación adaptable de longitud de ejecución Golomb-Rice
Cuando no se conoce una distribución de probabilidad para números enteros, no se puede determinar el parámetro óptimo para un codificador Golomb-Rice. Por lo tanto, en muchas aplicaciones, se usa un enfoque de dos pasos: primero, el bloque de datos se escanea para estimar una función de densidad de probabilidad (PDF) para los datos. A continuación, se determina el parámetro de Golomb-Rice a partir de esa PDF estimada. Una variación más simple de ese enfoque es asumir que la PDF pertenece a una familia parametrizada, estimar los parámetros de la PDF a partir de los datos y luego determinar calcular el parámetro óptimo de Golomb-Rice. Ese es el enfoque utilizado en la mayoría de las aplicaciones que se analizan a continuación.
Un enfoque alternativo para codificar de manera eficiente datos enteros cuyo PDF no se conoce o varía es utilizar un codificador adaptativo hacia atrás. El Run-Length Golomb-Rice (RLGR) logra eso usando un algoritmo muy simple que ajusta el parámetro Golomb-Rice hacia arriba o hacia abajo, dependiendo del ú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 un PDF gaussiano generalizado, que cubre una amplia gama de estadísticas observadas en datos como errores de predicción o coeficientes de transformación en códecs multimedia, el algoritmo de codificación RLGR puede funcionar muy bien en tales aplicaciones.
Aplicaciones
Numerosos códecs de señales utilizan un código de Rice para los residuos de predicción . En los algoritmos predictivos, tales residuos tienden a caer en una distribución geométrica de dos lados , siendo los residuos pequeños más frecuentes que los residuos grandes, y el código de Rice se aproxima mucho al código de Huffman para tal distribución sin la sobrecarga de tener que transmitir la tabla de Huffman. . Una señal que no coincide con una distribución geométrica es una onda sinusoidal , porque los residuos diferenciales crean una señal sinusoidal cuyos valores no crean una distribución geométrica (los valores de residuos más alto y más bajo tienen una frecuencia alta similar de ocurrencias, solo la mediana positiva y negativa los residuos ocurren 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 de Rice . Uno de esos experimentos produce un gráfico de relación de compresión que se muestra a continuación. Vea otras entradas en esta categoría al final de esta página. En esa compresión, los datos del diferencial de espacio progresivo producen un conjunto alterno de valores positivos y negativos alrededor de 0, que se reasignan a enteros solo positivos (al duplicar el valor absoluto y agregar uno si la entrada es negativa), y luego Rice-Golomb La codificación se aplica variando el divisor que permanece pequeño. [ cita requerida ]
En esos resultados, la codificación de Rice puede crear secuencias muy largas de un bit para el cociente; por razones prácticas, a menudo es necesario limitar la longitud total de ejecución de un bit, por lo que una versión modificada de la codificación Rice-Golomb consiste en reemplazar la cadena larga de un bit codificando su longitud con un Rice-Golomb recursivo codificación esto requiere reservar algunos valores además del divisor inicial k para permitir la distinción necesaria.
El esquema JPEG-LS utiliza Rice-Golomb para codificar los residuos de predicción.
La versión adaptativa Run-Length Golomb-Rice (RLGR) de la codificación Golomb-Rice, mencionada anteriormente, se utiliza para codificar el contenido de la pantalla en máquinas virtuales en el componente RemoteFX del Protocolo de escritorio remoto de Microsoft.
Ver también
Referencias
- ^ Gallager, RG; van Voorhis, DC (1975). "Códigos fuente óptimos para alfabetos enteros distribuidos geométricamente". Transacciones IEEE sobre teoría de la información . 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 de dos caras y parámetros desconocidos". Transacciones IEEE sobre teoría de la información . 46 (1): 229-236. doi : 10.1109 / 18.817520 .
- ^ Kiely, A. (2004). Selección del parámetro de Golomb en la codificación de arroz (informe técnico). Laboratorio de propulsión a chorro . 42-159.
- ^ "hombre acortar" . Archivado desde el original el 30 de enero de 2014 . Consultado el 7 de diciembre de 2008 .
- ^ Documentación FLAC: descripción general del formato
Otras lecturas
- Golomb, Solomon W. (1966). Codificaciones de longitud de ejecución. Transacciones IEEE sobre teoría de la información, IT - 12 (3): 399--401
- Rice, Robert F .; Plaunt, R. (1971). "Codificación adaptable de longitud variable para una compresión eficiente de los datos de televisión de la nave espacial". Transacciones IEEE sobre comunicaciones . 16 (9): 889–897. doi : 10.1109 / TCOM.1971.1090789 .
- Robert F. Rice (1979), "Some Practical Universal Uniseless Coding Techniques", Jet Propulsion Laboratory, 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 edicion. Editorial Morgan Kaufmann, 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 , Proc. 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 . Prensa del MIT, Cambridge MA, 2010.
enlaces externos
- página web con un breve ejemplo elaborado de codificación y decodificación de Golomb.