Entropía de una imagen

Question

¿Cuál es la forma más correcta desde un punto de vista de la información/física-teórica para calcular la entropía de una imagen? No me importa la eficiencia computacional en este momento, quiero que sea teóricamente lo más correcta posible.

Empecemos con una imagen en escala de grises. Un enfoque intuitivo es considerar la imagen como un conjunto de píxeles y calcular $$ H = - \sum_k p_k log_2(p_k) $$ donde $K$ es el número de niveles de grises y $p_k$ es la probabilidad asociada con el nivel de gris $k$.

Hay dos problemas con esta definición:

1. Funciona para una banda (es decir, escala de grises), pero ¿cómo se debería extender de manera estadísticamente correcta a múltiples bandas? Por ejemplo, para 2 bandas, ¿debería uno basarse en $(X_1,X_2)$ y por lo tanto en la FMP usando $P(X_1=x_1,X_2=x_2)$? Si uno tiene muchas ($B$>>2) bandas, entonces $P(X_1=x_1, ..., X_B=x_B) \sim 1/N^B \rightarrow H_{MAX}$, lo cual parece incorrecto.
2. La información espacial no se tiene en cuenta. Por ejemplo, las imágenes a continuación (propiedad de John Loomis) tienen la misma $H$, aunque claramente no transmiten la misma información.

¿Alguien se anima a explicar o dar consejo, o referirme a algún material de referencia decente sobre el tema? Estoy principalmente interesado en un enfoque teóricamente correcto del segundo problema (es decir, la información espacial).

Answer 1

“¿Cuál es la forma más correcta desde el punto de vista de la física teórica de calcular la entropía de una imagen?”

Una pregunta excelente y oportuna.

Contrariamente a la creencia popular, es posible definir de manera intuitiva (y teóricamente) natural la entropía de información de una imagen.

Considera la siguiente figura:

Podemos ver que la imagen diferencial tiene un histograma más compacto, por lo tanto, su entropía de información de Shannon es más baja. Por lo tanto, podemos obtener una menor redundancia utilizando la entropía de segundo orden de Shannon (es decir, entropía derivada de datos diferenciales). Si podemos extender esta idea isotrópicamente a 2D, entonces podríamos esperar buenas estimaciones para la entropía de información de la imagen.

Un histograma bidimensional de gradientes permite la extensión a 2D.

Podemos formalizar los argumentos y, de hecho, esto se ha completado recientemente. Recapitulando brevemente:

La observación de que la definición simple (ver, por ejemplo, la definición de entropía de imagen de MATLAB) ignora la estructura espacial es crucial. Para entender lo que está sucediendo, vale la pena regresar brevemente al caso de 1D. Desde hace mucho tiempo se sabe que utilizar el histograma de una señal para calcular su entropía de información/entropía de Shannon ignora la estructura temporal o espacial y da una estimación pobre de la compresibilidad o redundancia inherentes de la señal. La solución ya estaba disponible en el texto clásico de Shannon; utilizar las propiedades de segundo orden de la señal, es decir, las probabilidades de transición. La observación en 1971 (Rice & Plaunt) de que el mejor predictor de un valor de píxel en un escaneo de trama es el valor del píxel anterior lleva directamente a un predictor diferencial y a una entropía de Shannon de segundo orden que se alinea con ideas simples de compresión como la codificación por ejecución de longitud. Estas ideas se refinaron a finales de los años 80 dando lugar a algunas técnicas clásicas de codificación de imagen sin pérdida (diferencial) que aún se utilizan (PNG, JPG sin pérdidas, GIF, JPG2000 sin pérdidas) mientras que las wavelets y las DCT solo se utilizan para la codificación con pérdida.

Avanzando ahora a 2D; los investigadores encontraron muy difícil extender las ideas de Shannon a dimensiones superiores sin introducir una dependencia de orientación. Intuitivamente podríamos esperar que la entropía de información de Shannon de una imagen sea independiente de su orientación. También esperamos que las imágenes con estructura espacial complicada (como el ejemplo de ruido aleatorio del preguntante) tengan una entropía de información más alta que las imágenes con estructura espacial simple (como el ejemplo de escala de grises suave del preguntante). Resulta que la razón por la que fue tan difícil extender las ideas de Shannon de 1D a 2D es que hay una asimetría (unilateral) en la formulación original de Shannon que impide una formulación simétrica (isotrópica) en 2D. Una vez corregida la asimetría de 1D, la extensión a 2D puede proceder de forma fácil y natural.

Yendo al grano (los lectores interesados pueden consultar la exposición detallada en el preimpreso de arXiv enhttps://arxiv.org/abs/1609.01117) donde se calcula la entropía de imagen a partir de un histograma 2D de gradientes (función de densidad de probabilidad de gradientes).

Primero se calcula la función de densidad de probabilidad 2D mediante estimaciones de celdas de las derivadas x e y de las imágenes. Esto se asemeja a la operación de agrupamiento utilizada para generar el histograma de intensidad más común en 1D. Las derivadas pueden ser estimadas mediante diferencias finitas de 2 píxeles computadas en las direcciones horizontal y vertical. Para una imagen cuadrada NxN f (x, y) calculamos NxN valores de la derivada parcial fx y NxN valores de fy. Recorremos la imagen diferencial y para cada píxel usamos (fx,fy) para localizar una celda discreta en el array de destino (pdf 2D) que luego se incrementa en uno. Repetimos para todos los píxeles de NxN. El pdf 2D resultante debe normalizarse para tener una probabilidad unitaria total (simplemente dividiendo por NxN se logra esto). El pdf 2D está listo ahora para la siguiente etapa.

El cálculo de la entropía de información 2D de Shannon a partir del pdf de gradientes 2D es simple. La fórmula clásica de suma logarítmica de Shannon se aplica directamente excepto por un factor crucial de la mitad que proviene de consideraciones especiales de muestreo limitado en banda para una imagen de gradiente (ver el artículo de arXiv para más detalles). El factor de la mitad hace que la entropía 2D calculada sea aún menor en comparación con otros métodos (más redundantes) para estimar la entropía 2D o la compresión sin pérdidas.

Lamento no haber escrito las ecuaciones necesarias aquí, pero todo está disponible en el texto preimpreso. Los cálculos son directos (no iterativos) y la complejidad computacional es del orden de (el número de píxeles) NxN. La entropía de información de Shannon finalmente calculada es independiente de la rotación y corresponde precisamente con la cantidad de bits necesarios para codificar la imagen en una representación de gradiente no redundante.

Por cierto, la nueva medida de entropía 2D predice una entropía de 8 bits por píxel para la imagen aleatoria y 0.000 bits por píxel para la imagen de gradiente suave en la pregunta original.

Answer 2

No hay una respuesta definitiva, todo depende del contexto y de tu información previa. La entropía tiene muchas interpretaciones, como "medida de orden" o "medida de información", pero en lugar de enfocarte en las interpretaciones podrías simplemente ver qué es en realidad. La entropía es simplemente una forma de expresar el número de estados de un sistema. Un sistema con muchos estados tiene una entropía alta, y un sistema con pocos estados tiene una entropía baja.

Tú, y el artículo al que enlazas, afirman que las dos imágenes tienen la misma entropía. Esto no es correcto (para mí).

El artículo calcula correctamente cuál es la entropía.

$$ H = - \sum_k p_k log_2(p_k) $$

Para la primera imagen, cualquier píxel puede tener cualquier valor de escala de grises, $$p_k = \frac{1}{M} = 2^{-n}$$

Por lo tanto, la entropía es:

$$ H = - \sum_k p_k log_2(p_k) = - \sum_k 2^{-n} log_2(2^{-n}) = - log_2(2^{-n}) = n $$

Sin embargo, esto no es el caso para la segunda imagen.

La entropía aún se puede calcular como:

$$ H = - \sum_k p_k log_2(p_k) $$

pero no puedes simplemente decir que $p_k = \frac{1}{M} = 2^{-n}$, porque cuando has encontrado que $p_1$ tiene un valor, sabes que $p_2, p_3, p_4 \ldots p_{muchos}$ tienen el mismo valor.

Por lo tanto, las dos imágenes no tienen la misma entropía.

Puede sonar contradictorio que la entropía dependa de cómo se mira el problema. Sin embargo, probablemente lo sepas por la compresión. La compresión máxima de un archivo está dictada por el teorema de codificación de fuente de Shannon, que establece un límite superior para cuán bien puede comprimir un algoritmo un archivo. Este límite depende de la entropía del archivo. Todos los compresores modernos comprimirán un archivo cerca de este límite.

Sin embargo, si sabes que el archivo es un archivo de audio, puedes comprimirlo usando FLAC en lugar de un compresor genérico. FLAC es sin pérdida, por lo que toda la información se conserva. FLAC no puede evitar el teorema de codificación de fuente de Shannon, eso es matemática, pero puede analizar el archivo de una manera que reduzca la entropía del archivo, logrando así una mejor compresión.

De manera similar, cuando veo tu segunda imagen y observo que los píxeles están ordenados por valor de escala de grises, no tiene la misma entropía para mí como la imagen con ruido aleatorio.

Answer 3

$$ H = - \sum_k p_k log_2(p_k) $$ no funciona en la práctica, por la simple razón de que es casi imposible determinar $P_k$. Piensas que puedes hacerlo, como lo hiciste al considerar el número de niveles de gris. Pk no es eso. Pk son todas las combinaciones posibles de niveles de gris. Así que tienes que crear un árbol de probabilidad multidimensional considerando 1, 2, 3... combinaciones de píxeles. Si lees el trabajo de Shannon verás que él hace este cálculo para el inglés simple considerando una profundidad de árbol de 3 letras. Luego se vuelve complicado sin un ordenador.

Lo demostraste tú mismo con la declaración 2. Por eso tu cálculo de entropía devuelve el mismo nivel de entropía para las dos imágenes, incluso aunque una claramente tiene menos orden que la otra.

Tampoco existe tal concepto de distribución espacial dentro del cálculo de entropía. Si lo hubiera, también tendrías que calcular la entropía de forma diferente para muestras distribuidas temporalmente. ¿Y qué harías con un array de datos de 11 dimensiones? Para la entropía informacional; se mide en bytes.

Simplemente comprime las imágenes usando un algoritmo de compresión. Te dará una estimación de la entropía en bytes. Lo hará para cualquier imagen o literalmente cualquier cosa que pueda ser digitalizada, como música o obras de Shakespeare.

Así que. Tu imagen aleatoria contiene aproximadamente 114 KBytes, y tu imagen ordenada contiene aproximadamente 2.2 KBytes. Esto es lo que esperarías, pero ya lo sabías un poco porque viste que los tamaños de archivo de imagen eran de este tamaño. He reducido el tamaño comprimido en un 33% para permitir futuras mejoras en los algoritmos de compresión. No puedo ver que mejoren más allá de esto, ya que la curva de mejora se está volviendo asíntota a un valor verdadero subyacente.

P.D. Por si te interesa, Shakespeare solo produjo 1 MByte de entropía en toda su obra de vida, calculado por esta técnica. Aunque la mayor parte es bastante buena.

Answer 4

Esencialmente, la idea de entropía es algo así como "número de microestados consistentes con el macroestado".

Creo que el comentario de sean507 y la respuesta de bottiger apuntan a un marco común. Si representas el espacio de la imagen por un modelo generativo, $p[\,I,h\,]$, entonces para una imagen dada $I$ puedes (en principio) calcular un posterior sobre los estados ocultos $p[\,h\mid I\,]$ (ver también aquí). Luego puedes (en principio) calcular la entropía del posterior.

Así que estaría de acuerdo en que cualquier "entropía", incluso en el "sentido más teóricamente correcto", parecería depender tanto de la representación utilizada, como del modelo generativo que conecta "microestados" ($h$) con "macroestados" ($I$).

Answer 5

La entropía de una imagen se puede calcular generalizando los métodos clásicos 1D al caso 2D. Obviamente, se debe tener en cuenta la "información espacial", no solo los niveles de gris.

Los enfoques clásicos utilizados en sistemas 1D tienen en cuenta, al menos potencialmente, configuraciones en todas las escalas (todos los n-gramos, también para n muy grandes). El hecho de que la entropía de Shannon correcta (de una secuencia o de una imagen) solo se pueda estimar considerando todos los posibles "n-gramos" es un punto clave que no permeó suficientemente la literatura de procesamiento de imágenes. Esta idea fundamental se puede encontrar en el artículo seminal "Predicción y entropía del inglés impreso" de Shannon (1952), y está en la base de los métodos clásicos utilizados para sistemas 1D, que se pueden encontrar en: T. Schürmann and P. Grassberger, "Entropy estimation of symbol sequences", Chaos 6, 414 (1996). Un análisis reciente de las generalizaciones 2D de estos métodos se puede encontrar en: F.N.M. de Sousa Filho, V. G. Pereira de Sa, and E. Brigatti, "Entropy estimation in bidimensional sequences", Phys. Rev E, 105, 054116 (2022):

https://www.researchgate.net/publication/361742112_Entropy_estimation_in_bidimensional_sequences

donde se tiene en cuenta el método de entropías por bloque y los métodos de compresión sin pérdida.