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 prefijo óptimo , [1] lo que hace que la codificación 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 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 ; La "codificación de Rice" 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 M para dividir un valor de entrada x en dos partes: q , el resultado de una división por M , y r , 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 de ejemplo muestra la posición qy el desplazamiento r para la codificación del entero x usando el parámetro de Golomb-Rice M = 3 , con probabilidades de origen siguiendo una distribución geométrica con p (0) = 0.2 .
Formalmente, las dos partes vienen dadas por la siguiente expresión, donde es el entero no negativo que se codifica:
y
- .
Tanto q y r se codifican utilizando un número variable de bits de: q por un código unario, y r por b bits para código de Rice, o la elección entre b y b + 1 bits para el código Golomb (es decir, M no es una potencia de 2 ), con. Si, luego use b bits para codificar r ; de lo contrario, utilice b + 1 bits para codificar r . Claramente,si M es una potencia de 2 y podemos codificar todos los valores de r con b bits.
El entero x tratado por Golomb fue la longitud de ejecución de un proceso de Bernoulli , que tiene una distribución geométrica que comienza en 0. La mejor elección del parámetro M es una función del proceso de Bernoulli correspondiente, que está parametrizado porla probabilidad de éxito en un ensayo de Bernoulli dado . M es la mediana de la distribución o la mediana +/− 1. Puede determinarse mediante estas desigualdades:
que son resueltos por
- .
Para el ejemplo con p (0) = 0.2 :
- .
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.
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 se puede expresar 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 = piso ( 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 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 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
- Tenga en cuenta que p y 1 - p están invertidos en la sección en comparación con el 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 ≥ 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 de 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 adaptativa de Golomb-Rice de longitud de ejecución
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 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 adaptable hacia atrás. El código de longitud de ejecución 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 altos y más bajos 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 el gráfico de relación de compresión que se muestra.
El esquema JPEG-LS utiliza Rice-Golomb para codificar los residuos de predicción.
La versión adaptativa Golomb-Rice (RLGR) de ejecución 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 Adaptive run-length / 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.