Entropía de una imagen.

21

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

Comencemos con una imagen en escala de grises. Un enfoque intuitivo es considerar la imagen como una bolsa de píxeles y calcular donde es el número de niveles de gris y es la probabilidad asociada con el nivel de gris .

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

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

K

$K$

p_{k}

$p_k$

k

$k$

Hay dos problemas con esta definición:

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

¿A alguien le importa explicar o dar consejos, 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, información espacial).

spatial entropy image-processing Davor Josipovic
fuente

2

Creo que debería mirar los campos aleatorios de Markov, por ejemplo, files.is.tue.mpg.de/chwang/papers/CVIU2013_MRFSurvey.pdf

seanv507

1

también matrices de

concordancia de graylevel

@ seanv507, sí, de hecho. Los modelos gráficos no dirigidos o los campos aleatorios de Markov es lo que estoy estudiando ahora. Volveré a publicar cuando sepa más.

Davor Josipovic

17

"¿Cuál es la forma correcta más teórica de información / física para calcular la entropía de una imagen?"

Una excelente y oportuna pregunta.

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

Considere 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 menor. Por lo tanto, podemos obtener una menor redundancia mediante el uso de entropía de Shannon de segundo orden (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 información-entropía de la imagen.

Un histograma bidimensional de gradientes permite la extensión 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 MATLAB de entropía de imágenes) ignora la estructura espacial es crucial. Para comprender lo que está sucediendo, vale la pena volver brevemente al caso 1D. Desde hace tiempo se sabe que el uso del histograma de una señal para calcular su información / entropía de Shannon ignora la estructura temporal o espacial y proporciona una estimación pobre de la compresibilidad o redundancia inherente de la señal. La solución ya estaba disponible en el texto clásico de Shannon; use las propiedades de segundo orden de la señal, es decir, las probabilidades de transición. La observación en 1971 (Rice & Plaunt) que el mejor predictor de un valor de píxel en una exploración de trama es el valor del píxel anterior que conduce inmediatamente a un predictor diferencial y una entropía de Shannon de segundo orden que se alinea con ideas de compresión simples, como la codificación de longitud de ejecución. Estas ideas se refinaron a fines de los años 80, lo que resultó en algunas técnicas clásicas de codificación de imagen sin pérdida (diferencial) que todavía están en uso (PNG, JPG sin pérdida, GIF, JPG2000 sin pérdida) mientras que las wavelets y DCT solo se usan para la codificación con pérdida.

Pasando 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 información-entropía de Shannon de una imagen sea independiente de su orientación. También esperamos que las imágenes con una estructura espacial complicada (como el ejemplo de ruido aleatorio del interlocutor) tengan una mayor entropía de información que las imágenes con estructura espacial simple (como el ejemplo de escala de grises suave del interrogador). 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 que se corrige la asimetría 1D, la extensión 2D puede proceder de manera fácil y natural.

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

Primero, el pdf 2D se calcula agrupando las estimaciones de las imágenes derivadas x e y. Esto se asemeja a la operación de agrupamiento utilizada para generar el histograma de intensidad más común en 1D. Las derivadas se pueden estimar mediante diferencias finitas de 2 píxeles calculadas en las direcciones horizontal y vertical. Para una imagen cuadrada de NxN f (x, y) calculamos los valores de NxN de derivada parcial fx y los valores de NxN de fy. Escaneamos la imagen diferencial y por cada píxel que usamos (fx, fy) para ubicar un contenedor discreto en la matriz de destino (PDF en 2D) que luego se incrementa en uno. Repetimos para todos los píxeles NxN. El pdf 2D resultante debe normalizarse para tener una probabilidad de unidad general (simplemente dividiendo por NxN logra esto). El PDF 2D ahora está listo para la siguiente etapa.

El cálculo de la entropía de información de Shannon en 2D a partir del PDF de gradiente en 2D es simple. La fórmula de suma logarítmica clásica de Shannon se aplica directamente, excepto por un factor crucial de la mitad que se origina a partir de consideraciones especiales de muestreo de banda ilimitada para una imagen de gradiente (consulte el artículo de arXiv para más detalles). El medio factor hace que la entropía 2D calculada sea aún más baja 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 de preimpresión. Los cálculos son directos (no iterativos) y la complejidad computacional es de orden (el número de píxeles) NxN. La entropía informática de Shannon final es independiente de la rotación y corresponde precisamente con el número 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 (intuitivamente agradable) 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.

Kieran Larkin
fuente

1

Trabajo interesante. Ahora, Razlighi ha hecho una comparación de varios algoritmos de entropía en este artículo . Me pregunto cómo se compararía la suya, especialmente en la imagen sintética que usa allí. Podría valer la pena investigarlo.

Davor Josipovic

Gracias por mencionar el papel de Razlighi's. Los resultados cruciales de la prueba se muestran en la Fig. 2. Creo que mi medida de delentropía 2D tendría una entropía normalizada unitaria para la correlación 0.0 y luego caería a una entropía normalizada casi cero para la correlación 1.0. Realmente no he calculado estos valores, pero se deduce directamente de la sección 3.2 de mi preimpresión arXiv porque la alta correlación corresponde a un ancho de banda espectral bajo, por lo tanto, baja entropía.

Kieran Larkin

Me gusta este enfoque. Me parece intuitivo. El paso adicional de calcular el gradiente antes de calcular la entropía parece codificar la información espacial intuitivamente. Traté de jugar y calcularlo con Python aquí . Pero luché por reproducir los cáusticos de su papel (ver código, último ejemplo). ¡Solo puedo reproducirlos con carrozas! Esto se debe a que con los enteros los gradientes están en [-6,6] para mi imagen de prueba, incluso cuando utilizo 16 bits, lo que resulta en solo 49 contenedores distintos de cero para el histograma.

mxmlnkn

¿Alguna vez se publicó su artículo? ¿Tú o alguien más continuaron el trabajo?

Andrei

Un código de muestra de Matlab sería genial.

Pedro77

8

No hay ninguno, todo depende del contexto y su información previa. La entropía tiene muchas interpretaciones, como "medición del orden" o "medición de la información", pero en lugar de mirar las interpretaciones, podría ver lo que realmente es. La entropía es solo 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.

Usted y el artículo al que se vincula: declara que las dos imágenes tienen la misma entropía. Esto no es correcto (para mí).

El artículo calcula correctamente la entropía es.

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

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

Para la primera imagen, cualquier píxel puede tener cualquier valor de gris,

p_{k} = \frac{1}{M} = 2^{- n}

$p_k = \frac{1}{M} = 2^{-n}$

Por lo tanto, la entropía es:

H = - \sum_{k} p_{k} l o g_{2} (p_{k}) = - \sum_{k} 2^{- n} l o g_{2} (2^{- n}) = - l o g_{2} (2^{- n}) = n

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

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

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

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

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

pero no puede decir simplemente , porque cuando ha encontrado que es un valor, sabe que es El mismo valor. $p_k = \frac{1}{M} = 2^{-n}$ $p_1$ $p_2, p_3, p_4 \ldots p_{many}$

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

Puede parecer contrario a la intuición que la entropía depende de cómo se mire el problema. Sin embargo, probablemente lo sepa por compresión. La máxima compresión de un archivo está dictada por el teorema de codificación de fuente de Shannon, que establece un límite superior de qué tan bien un algoritmo de compresión puede comprimir un archivo. Este límite depende de la entropía del archivo. Todos los compresores modernos comprimirán un archivo cercano a este límite.

Sin embargo, si sabe que el archivo es un archivo de audio, puede comprimirlo usando FLAC en lugar de algún compresor genérico. FLAC no tiene pérdidas, por lo que se conserva toda la información. FLAC no puede sortear el teorema de codificación de fuente de Shannon, eso es matemático, pero puede ver el archivo de una manera que reduce la entropía del archivo, por lo tanto, hace una mejor compresión.

De manera idéntica, cuando miro su segunda imagen, veo que los píxeles están ordenados por valor de gris y, por lo tanto, no tiene la misma entropía que la imagen con ruido aleatorio.

bottiger
fuente

Creo que el OP sabe si esto, está pidiendo modelos probabilísticos que incluyen información espacial

seanv507 el

@ seanv507 Releyé la pregunta. No estoy seguro si estoy de acuerdo contigo o no. Creo que OP está buscando algo que no existe.

bottiger

@bottiger, gracias por tu respuesta. Creo que todos estamos de acuerdo en que las 2 imágenes deberían / no tener la misma entropía. Lo que quiero saber es una forma correcta (conceptual / teórica) de calcularlo. La fórmula simple dada para no parece tener en cuenta la información espacial. Entonces la pregunta es sobre cómo extenderlo correctamente. Volveré cuando sepa más.

H

$H$

Davor Josipovic

@bottiger FLAC no puede reducir la entropía de un archivo de audio, ya que, por definición, sería una compresión con pérdida Se logra la compresión al eliminar la redundancia.

Paul Uszak

¿Quizás es correcto decir que la fórmula clásica de entropía es correcta solo si los valores de los píxeles son estáticamente independientes?

volperossa

2

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

$p[\,I,h\,]$ $I$ $p[\,h\mid I\,]$

$h$ $I$

GeoMatt22
fuente

1

H = - \sum_{k} p_{k} l o g_{2} (p_{k})

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

no no funciona en la práctica, por la sencilla razón de que es casi imposible determinar Pk. Cree que puede hacerlo, como lo ha hecho al considerar la cantidad de niveles de gris. Pk no es eso. Pk es todas las combinaciones posibles de niveles de gris. Por lo tanto, debe crear un árbol de probabilidad multidimensional considerando 1, 2, 3 ... combinaciones de píxeles. Si lees el trabajo de Shannon, lo ves hacer este cálculo para inglés simple considerando una profundidad de árbol de 3 letras. Luego se vuelve difícil de manejar sin una computadora.

Usted mismo lo probó con la declaración 2. Es por eso que su cálculo de entropía devuelve el mismo nivel de entropía para las dos imágenes, aunque una es claramente menos ordenada que la otra.

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

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

Entonces. Su imagen aleatoria contiene aproximadamente 114 KBytes, y su imagen ordenada contiene aproximadamente 2.2 KBytes. Esto es lo que esperaría, pero ya lo sabía porque vio que los tamaños de los archivos 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 asintótica a un verdadero valor subyacente.

PD: Por interés, Shakespeare solo produjo 1 MByte de entropía en el trabajo de toda su vida, calculado por esta técnica. Sin embargo, la mayor parte es bastante buena.

Paul Uszak
fuente

Entropía de una imagen.

Respuestas: