En mi explicación, usaré el concepto de entropía de una variable aleatoria. El método al que se hace referencia en la pregunta, la codificación de Huffman, es demostrablemente imbatible siempre que conozca la función de densidad de probabilidad completa de la señal que desea comprimir. El número de bits de información en una señal [matemática] X [/ matemática], dada su función de densidad de probabilidad se mide por su entropía teórica de la información (Entropía (teoría de la información)), y la codificación de Huffman logra esto asintóticamente:
[matemáticas] H (X) = – \ sum_x p_X (x) log_2 p_X (x) [/ matemáticas]
Ilustraré el problema continuando con el ejemplo que usó en su pregunta. Cuando tiene un histograma, no, digamos, una función de densidad de probabilidad * verdadera * de valores de color, puede representar un píxel individual con el menor número absoluto de bytes posible. Pero presumiblemente quiere hacer más que comprimir un solo píxel de color. Quizás quieras comprimir una imagen.
Pero una imagen es solo una colección de píxeles. ¿Por qué importa cuántos píxeles quieres enviar? Para ilustrar, digamos que tiene una señal [matemática] Z = [Z_1, Z_2] [/ matemática] que consta de dos bits, y es 1,0 o 0,1 con probabilidad 0,5. Entonces, si codifica cualquier bit [matemático] Z_i [/ matemático] de esta señal, encontrará que su entropía de ese bit es exactamente 1 bit. Es decir, la señal no se puede comprimir en absoluto. Pero si codifica la señal como un todo, verá que [matemática] P (Z = 01) = P (Z = 10) = 0.5 [/ matemática] y así [matemática] H (Z) = 0.5 + 0.5 bits = 1 bit [/ math], que es una ganancia total del 50% sobre el método de codificación de un solo bit.
¿Cómo pasó esto? Porque hay dependencias entre [math] Z_1 [/ math] y [math] Z_2 [/ math]. De hecho, [math] Z_1 [/ math] determina completamente [math] Z_2 [/ math]. Si almacenó esa [matemática] Z_1 = 1 [/ matemática], no necesitaría almacenar [matemática] Z_2 = 0 [/ matemática]. Lo obtienes gratis. Es por eso que la señal tiene solo un bit de información. Volviendo a la definición de entropía anterior, la entropía de una señal vectorial es estrictamente menor que la suma de las entropías de sus componentes individuales a menos que todos los componentes sean independientes.
- ¿Por qué TeXmacs aún no ha reemplazado a TeX o LaTeX?
- ¿Puede la programación en objetivos ser una alternativa a la definición de API (de la charla de B. Victor 'El futuro de la programación)?
- ¿La entropía de la web es de solo 22 bits?
- Voy a ir a la universidad pronto y tengo muchas ganas de hacer una investigación de pregrado de CS, pero todos los trabajos de investigación que he intentado leer están muy por encima de mi cabeza. ¿Esto es normal?
- ¿Quiénes son los mejores académicos y practicantes del aprendizaje automático?
[matemáticas] H ([X]) = H (X_1) + [/ matemáticas] [matemáticas] H (X_2 | X_1) +… + H (X_n | X_1, .. X_n) [/ matemáticas]
[matemática] H (A | B) [/ matemática] es una medida de la información adicional en A después de saber B. En el ejemplo anterior [matemática] H (Z_2 | Z_1) = 0 [/ matemática].
Ahora, vamos a las señales del mundo real. Suponga que desea comprimir una imagen fotográfica [matemática] I [/ matemática]. Todos los píxeles de una imagen tienen dependencias, por lo que no puede trabajar con probabilidades de píxeles individuales. Eso sería como trabajar con los bits individuales de nuestra señal de juguete [matemática] Z [/ matemática] anterior. Debe conocer la función de densidad de probabilidad conjunta de la imagen [matemáticas] I [/ matemáticas]. No puede simplemente almacenar histogramas de imágenes para representar el pdf conjunto, como lo hizo para los valores de color. Incluso para una imagen de 640 × 480 píxeles, este histograma tendría 307200 dimensiones, y si cada píxel pudiera tomar 255 valores (digamos que es una imagen en escala de grises), entonces estaría mirando un histograma con [matemáticas] 255 ^ {307200 } [/ math] entradas! E incluso si estuviera dispuesto a almacenar esta información en algún lugar, la cantidad de imágenes que tendría que escanear para construir un histograma confiable de ese tamaño sería un orden de magnitud mayor que el tamaño del histograma.
Esto es cuando sabe que es hora de que comience a hacer cosas inteligentes para acercarse al mejor rendimiento posible haciendo * mucho * menos de lo que requeriría el mejor rendimiento absoluto. Empiezas a construir un modelo económico inteligente para un pdf conjunto. En el nivel más bajo, los valores de píxeles adyacentes generalmente están muy cerca uno del otro, pero esta dependencia desaparece rápidamente para píxeles más separados. Entonces, tal vez diga que estaría satisfecho con un pdf conjunto que solo codifica las dependencias en vecindarios de 3 × 3 píxeles. Entonces tu trabajo se volvió mucho más fácil. Ahora tiene [math] 255 ^ 9 [/ math] entradas en su histograma. Todavía es un número muy grande, pero observa que hay simetrías dentro del pdf (digamos que el píxel superior e inferior dependen de la misma manera del resto) y, por lo tanto, solo necesita almacenar [matemáticas] 255 ^ 5 [/ matemáticas ] píxeles. Esto es algo que quizás pueda lograr, pero es posible que tenga que aprender un modelo funcional para su histograma después de haberlo construido, para que su programa de compresión no necesite [matemáticas] 4 ^ {12} [/ matemáticas ] bytes (suponiendo entradas flotantes).
El principal algoritmo de compresión de imágenes sin pérdida de hoy en día, JPEG-LS (ver http://www.hpl.hp.com/loco/), hace algo en este sentido y ha sido difícil de superar durante mucho tiempo. Sin embargo, teóricamente, podrías encontrar otras formas de aproximar el pdf conjunto y quizás hacerlo mejor. Tal vez, por ejemplo, explota dependencias de mayor nivel, como decir que si hay un automóvil en la imagen, ¡es probable que también haya una carretera en él! Siempre es posible superar todos los métodos de compresión existentes, simplemente utilizando unos pocos recursos más que cualquiera de ellos. A medida que aumenta la potencia de cálculo y las capacidades de almacenamiento, los algoritmos de compresión cada vez más complicados pueden volverse viables. Por lo tanto, siempre hay margen de mejora.
Solo he tratado hasta ahora con la compresión sin pérdidas. Supongamos que se vuelve aún más inteligente y dice que no le importa el pdf conjunto de la imagen en sí, sino solo la percepción de esa imagen por parte de los espectadores humanos. Como ejemplo de juguete, digamos que descubres que a la mayoría de los humanos les resulta difícil notar el cambio cuando se eliminan todos los bordes de una imagen. Luego dejas de molestarte para codificar los bordes. Claro, en un sentido absoluto, no podrá reproducir la imagen original, pero sus estudios muestran que la mayoría de las personas no notan la diferencia, y usted sabe que los únicos consumidores de su imagen son * personas *, por lo que puede salirse con la suya haciendo esto. Esta es la compresión “con pérdida”. Para las imágenes, por ejemplo, los esquemas de compresión de imágenes fijas con pérdida como JPEG pueden producir imágenes comprimidas “excelentes” (según lo juzgado por observadores humanos) utilizando aproximadamente un orden de magnitud menos bytes que los mejores métodos sin pérdida. Por lo tanto, el progreso en el difícil problema de comprender la percepción visual humana es otra fuente importante de nuevas ideas que han permitido consistentemente mejoras sobre el estado de la técnica para la compresión de imagen / video con pérdida.
Imágenes cortesía: wikipedia, galerías jmg y blog del consorcio de la comunidad informática
