Medición de entropía / información / patrones de una matriz binaria 2D

Quiero medir la entropía / densidad de información / similitud de patrón de una matriz binaria bidimensional. Déjame mostrarte algunas fotos para aclarar:

Esta pantalla debería tener una entropía bastante alta:

UNA)

Esto debería tener una entropía media:

SI)

Estas imágenes, finalmente, deberían tener una entropía cercana a cero:

C)

RE)

MI)

¿Hay algún índice que capture la entropía, resp. la "similitud de patrón" de estas pantallas?

Por supuesto, cada algoritmo (por ejemplo, algoritmos de compresión; o el algoritmo de rotación propuesto por ttnphns ) es sensible a otras características de la pantalla. Estoy buscando un algoritmo que intente capturar las siguientes propiedades:

• Simetría rotacional y axial
• La cantidad de agrupamiento
• Repeticiones

Quizás más complicado, el algoritmo podría ser sensible a las propiedades del " principio Gestalt " psicológico , en particular:

• La ley de proximidad:
• La ley de la simetría: las imágenes simétricas se perciben colectivamente, incluso a pesar de la distancia:

A las pantallas con estas propiedades se les debe asignar un "valor de entropía bajo"; las pantallas con puntos bastante aleatorios / no estructurados deberían recibir un "valor de entropía alto".

Soy consciente de que lo más probable es que ningún algoritmo capturará todas estas características; por lo tanto, las sugerencias de algoritmos que aborden solo algunas o incluso una sola característica también son muy bienvenidas.

En particular, estoy buscando algoritmos concretos existentes o ideas específicas implementables (y otorgaré la recompensa de acuerdo con estos criterios).

Hay un procedimiento simple que captura toda la intuición, incluidos los elementos psicológicos y geométricos. Se basa en el uso de la proximidad espacial , que es la base de nuestra percepción y proporciona una forma intrínseca de capturar lo que solo se mide imperfectamente por simetrías.

Para hacer esto, necesitamos medir la "complejidad" de estos arreglos a diferentes escalas locales. Aunque tenemos mucha flexibilidad para elegir esas escalas y elegir el sentido en que medimos la "proximidad", es lo suficientemente simple y efectivo como para usar vecindarios cuadrados pequeños y observar promedios (o, de manera equivalente, sumas) dentro de ellos. Para este fin, se puede derivar una secuencia de matrices de cualquier matriz de por formando sumas de vecindad móviles usando por vecindades, luego por , etc., hasta por (aunque para entonces generalmente hay muy pocos valores para proporcionar algo confiable).$m$$n$$k=2$$2$$3$$3$$\min(n,m)$$\min(n,m)$

Para ver cómo funciona esto, hagamos los cálculos para las matrices en la pregunta, que llamaré de a , de arriba a abajo. Aquí hay gráficas de las sumas móviles para ( es la matriz original, por supuesto) aplicada a .$a_1$$a_5$$k=1,2,3,4$$k=1$$a_1$

En el sentido de las agujas del reloj desde la esquina superior izquierda, es igual a , , y . Las matrices son por , luego por , por y por , respectivamente. Todos parecen algo "al azar". Midamos esta aleatoriedad con su entropía de base 2. Para , la secuencia de estas entropías es . Llamemos a esto el "perfil" de .$k$$1$$2$$4$$3$$5$$5$$4$$4$$2$$2$$3$$3$$a_1$$(0.97, 0.99, 0.92, 1.5)$$a_1$

Aquí, en contraste, están las sumas móviles de :$a_4$

Para hay poca variación, por lo tanto, baja entropía. El perfil es . Sus valores son consistentemente más bajos que los valores para , lo que confirma la sensación intuitiva de que hay un "patrón" fuerte presente en .$k=2, 3, 4$$(1.00, 0, 0.99, 0)$$a_1$$a_4$

Necesitamos un marco de referencia para interpretar estos perfiles. Una matriz perfectamente aleatoria de valores binarios tendrá aproximadamente la mitad de sus valores iguales a y la otra mitad igual a , para una entropía de . Las sumas móviles dentro de los vecindarios por tenderán a tener distribuciones binomiales, dándoles entropías predecibles (al menos para matrices grandes) que pueden aproximarse por :$0$$1$$1$$k$$k$$1 + \log_2(k)$

Estos resultados se confirman mediante simulación con matrices de hasta . Sin embargo, se desglosan para matrices pequeñas (como las matrices de por aquí) debido a la correlación entre las ventanas vecinas (una vez que el tamaño de la ventana es aproximadamente la mitad de las dimensiones de la matriz) y debido a la pequeña cantidad de datos. Aquí hay un perfil de referencia de matrices aleatorias de por generadas por simulación junto con gráficos de algunos perfiles reales:$m=n=100$$5$$5$$5$$5$

En esta gráfica, el perfil de referencia es azul sólido. Los perfiles de matriz corresponden a : rojo, : oro, : verde, : azul claro. (La inclusión de oscurecería la imagen porque está cerca del perfil de .) En general, los perfiles corresponden al orden en la pregunta: se reducen en la mayoría de los valores de medida que aumenta el orden aparente. La excepción es : hasta el final, para , sus sumas móviles tienden a tener una de las entropías más bajas . Esto revela una regularidad sorprendente: cada barrio de por en$a_1$$a_2$$a_3$$a_4$$a_5$$a_4$$k$$a_1$$k=4$$2$$2$$a_1$ tiene exactamente o cuadrados negros, nunca más o menos. Es mucho menos "aleatorio" de lo que uno podría pensar. (Esto se debe en parte a la pérdida de información que acompaña a la suma de los valores en cada vecindario, un procedimiento que condensa posibles configuraciones de vecindario en solo diferentes sumas posibles. Si quisiéramos tener en cuenta específicamente para la agrupación y orientación dentro de cada vecindario, entonces, en lugar de usar sumas móviles, usaríamos concatenaciones móviles, es decir, cada vecindario por tiene$1$$2$$2^{k^2}$$k^2+1$$k$$k$$2^{k^2}$posibles configuraciones diferentes; al distinguirlos a todos, podemos obtener una medida más fina de la entropía. Sospecho que tal medida elevaría el perfil de comparación con las otras imágenes).$a_1$

Esta técnica de crear un perfil de entropías en un rango controlado de escalas, mediante la suma (o concatenación o combinación) de valores dentro de vecindarios en movimiento, se ha utilizado en el análisis de imágenes. Es una generalización bidimensional de la conocida idea de analizar el texto primero como una serie de letras, luego como una serie de dígrafos (secuencias de dos letras), luego como trigráficos, etc. También tiene algunas relaciones evidentes con el fractal. análisis (que explora las propiedades de la imagen a escalas cada vez más finas). Si tenemos cuidado de usar una suma de bloques en movimiento o una concatenación de bloques (para que no haya superposiciones entre ventanas), se pueden derivar relaciones matemáticas simples entre las entropías sucesivas; sin embargo,

Varias extensiones son posibles. Por ejemplo, para un perfil rotacionalmente invariante, use vecindarios circulares en lugar de cuadrados. Todo se generaliza más allá de las matrices binarias, por supuesto. Con matrices suficientemente grandes, incluso se pueden calcular perfiles de entropía que varían localmente para detectar la no estacionariedad.

Si se desea un solo número, en lugar de un perfil completo, elija la escala a la que le interese la aleatoriedad espacial (o la falta de ella). En estos ejemplos, esa escala correspondería mejor a un vecindario móvil de por o por , porque para su patrón todos ellos dependen de agrupaciones que abarcan de tres a cinco celdas (y un vecindario de por solo promedia todas las variaciones en el matriz y por lo tanto es inútil). En la última escala, las entropías para hasta son , , , y3 4 4 5 5 a 1 a 5 1.50 0.81 0 0 0 1.34 a 1 a 3 a 4 a 5 0 3 3 1.39 0.99 0.92 $3$$3$$4$$4$$5$$5$$a_1$$a_5$$1.50$$0.81$$0$$0$$0$ ; La entropía esperada en esta escala (para una matriz uniformemente aleatoria) es . Esto justifica la sensación de que "debería tener una entropía bastante alta". Para distinguir , y , que están vinculados con entropía en esta escala, observe la siguiente resolución más fina ( vecindarios por ): sus entropías son , , , respectivamente (mientras que se espera una cuadrícula aleatoria para tener un valor de ). Con estas medidas, la pregunta original coloca las matrices exactamente en el orden correcto.$1.34$$a_1$$a_3$$a_4$$a_5$$0$$3$$3$$1.39$$0.99$$0.92$$1.77$

Primero, mi sugerencia es puramente intuitiva: no sé nada en el campo de reconocimiento de patrones. En segundo lugar, se podrían hacer decenas de sugerencias alternativas como la mía.

Comienzo con la idea de que una configuración regular (es decir, con baja entropía) debe ser de alguna manera simétrica, isomórfica a esto o aquello que sus transformantes. Por ejemplo, en rotaciones.

Puede rotar (voltear a 90 grados, que 180 grados, etc.) su matriz hasta que la configuración coincida con la original . Siempre coincidirá con 4 rotaciones (360 grados), pero a veces puede coincidir antes (como la matriz E en la imagen).

En cada rotación, cuente el número de celdas con valores no idénticos entre la configuración original y la rotada. Por ejemplo, si compara la matriz original A con su rotación de 90 grados, descubrirá 10 celdas donde hay un punto en una matriz y un espacio en blanco en la otra matriz. Luego compare la matriz original con su rotación de 180 grados: se encontrarán 11 de estas celdas. 10 celdas es la discrepancia entre la matriz original A y su rotación de 270 grados. 10 + 11 + 10 = 31 es la "entropía" global de la matriz A .

Para la matriz B, la "entropía" es 20, y para la matriz E es solo 12. Para las matrices C y D, la "entropía" es 0 porque las rotaciones se detienen después de 90 grados: el isomorfismo ya se ha alcanzado.

La información se define comúnmente como . Hay una buena teoría que explica que es la cantidad de bits que necesita para codificar usando . Si desea saber más sobre esto, lea sobre codificación aritmética .$h(x) = \log p(x)$$\log_2 p(x)$$x$$p$

Entonces, ¿cómo puede eso resolver tu problema? Fácil. Encuentre alguna que represente sus datos y use donde es una nueva muestra como medida de sorpresa o información para encontrarla.$p$$-\log p(x)$$x$

Lo difícil es encontrar algún modelo para y generar sus datos. Tal vez pueda encontrar un algoritmo que genere matrices que considere 'probables'.$p$

Algunas ideas para encajar .$p$

1. Si solo está buscando matrices de 5x5, solo necesita bits para almacenar todas las matrices posibles, por lo que puede enumerarlas todas y asignar una cierta probabilidad a cada una.$2^{25}$
2. Use una máquina de Boltzmann restringida para ajustar sus datos (entonces tendría que usar la energía libre como sustituto de la información, pero está bien),
3. Use zip como sustituto de y no se preocupe por toda la historia de probabilidad de arriba. Incluso está formalmente bien, porque usas zip como una aproximación a la complejidad de Kolmogorov y esto ha sido hecho por teóricos de la información y también ha llevado a la distancia de compresión normalizada ,$-\log p(x)$
4. Tal vez use un modelo gráfico para incluir creencias espaciales anteriores y use variables de Bernoulli localmente.
5. Para codificar la invariancia traslacional, puede usar un modelo basado en energía usando una red convolucional .

Algunas de las ideas anteriores son bastante pesadas y provienen del aprendizaje automático. En caso de que desee tener más consejos, solo use los comentarios.

Mi siguiente propuesta es más intuitiva que deducida, por lo que no puedo probarla, pero al menos puedo ofrecer algunos fundamentos. El procedimiento de evaluación de la "entropía" de la configuración de manchas incluye:

1. Digitalizar manchas.
2. Realice la comparación de la configuración consigo misma, muchas veces, mediante análisis ortogonal de Procrustes .
3. Trace los resultados de las comparaciones (coeficiente de identidad) y evalúe la irregularidad de la trama.

Digitalizar puntos , es decir, tomar sus coordenadas. Por ejemplo, a continuación se muestra su configuración D con puntos numerados (el orden de numeración puede ser arbitrario) y sus coordenadas.

spot x   y
1   1   1
2   3   1
3   5   1
4   2   2
5   4   2
6   1   3
7   3   3
8   5   3
9   2   4
10  4   4
11  1   5
12  3   5
13  5   5

Hacer permutaciones y realizar análisis de Procrustes. Permute los puntos (filas en los datos) al azar y realice la comparación de Procrustes de los datos originales (no permutados) con los permutados; registre el coeficiente de identidad (medida de similitud de las dos configuraciones, salida del análisis). Repita la permutación - Procrustes - guardando el coeficiente, muchas veces (por ejemplo, 1000 veces o más).

¿Qué podemos esperar de los coeficientes de identidad (IDc) obtenidos después de la operación anterior en una estructura regular ?Considere, por ejemplo, la configuración anterior D. Si comparamos las coordenadas originales establecidas consigo mismo, obtendremos IDc = 1, por supuesto. Pero si permutamos algunos puntos, el IDc entre el conjunto original y el permutado tendrá un valor inferior a 1. Permutamos, por ejemplo, un par de puntos, etiquetados 1 y 4. IDc = .964. Ahora, en cambio, permute los puntos 3 y 5. Curiosamente, IDc volverá a ser .964. El mismo valor, ¿por qué? Los puntos 3 y 5 son simétricos a 1 y 4, de modo que la rotación a 90 grados los superpone. La comparación de Procrustes es insensible a la rotación o la reflexión, y por lo tanto, la permutación dentro del par 1-4 es "igual" que la permutación dentro del par 5-3, para ello. Para agregar más ejemplos, si permutas solo los puntos 4 y 7, IDc volverá a ser .964. Parece que para Procrustes, la permutación dentro del par 4-7 es la "misma" como los dos anteriores en el sentido de que da el mismo grado de similitud (medido por IDc). Obviamente, todo esto se debe a que la configuración D es regular.Para una configuración regular, esperamos obtener valores bastante discretos de IDc en nuestro experimento de permutación / comparación; mientras que para la configuración irregular esperamos que los valores tiendan a ser continuos.

Trace los valores IDc registrados. Por ejemplo, ordene los valores y haga un diagrama de línea. Hice el experimento - 5000 permutaciones - con cada una de sus configuraciones A, B (ambas bastante irregulares), D, E (ambas regulares) y aquí está el diagrama de línea:

Tenga en cuenta cuánto más irregulares son las líneas D y E (D especialmente). Esto se debe a la discreción de los valores. Los valores para A y B son mucho más continuos. Puede elegir algún tipo de estadística que calcule el grado de discreción / continuidad, en lugar de trazar. A parece no más continuo que B (para usted, la configuración A es algo menos regular, pero mi diagrama de líneas parece no demostrarlo) o, si no, tal vez muestra un poco otro patrón de valores IDc. ¿Qué otro patrón? Esto está más allá del alcance de mi respuesta todavía. La gran pregunta es si A es de hecho menos regular que B: puede ser para su ojo, pero no necesariamente para el análisis de Procrustes o el ojo de otra persona.

Por cierto, todo el experimento de permutación / Procrustes lo hice muy rápidamente. Utilicé mi propia macro de análisis Procrustes para SPSS (que se encuentra en mi página web) y agregué algunas líneas de código para hacer permutaciones.

La información mutua, considerando cada dimensión como una variable aleatoria, por lo tanto, cada matriz como un conjunto de pares de números, debería ayudar en todos los casos, excepto en C, donde no estoy seguro del resultado.

Vea la discusión sobre la Fig. 8 (comenzando en p24) sobre el análisis de rendimiento de regresión en el manual de TMVA o la entrada correspondiente de arxiv .

En lugar de mirar las propiedades globales del patrón (como las simetrías), uno puede mirar las locales, por ejemplo, el número de vecinos que tiene cada piedra (= círculo negro). Denotemos el número total de piedras por .$s$

Si las piedras fueron arrojadas al azar, la distribución de vecinos es donde es la densidad de las piedras. El número de lugares depende si una piedra está en el interior ( ), en el borde ( ) o en la esquina .

Es claramente visible, que la distribución de vecinos en C) , D) y E) está lejos de ser aleatoria. Por ejemplo, para D) todas las piedras interiores tienen exactamente vecinos (lo que se opone a la distribución aleatoria, que rinde en lugar de la medida ).$4$$\approx (0\%,2\%,9\%,20\%,27\%,24\%,13\%,4\%,0\%)$$(0\%,0\%,0\%,0\%,100\%,0\%,0\%,0\%,0\%)$

Entonces, para cuantificar si un patrón es aleatorio, debe comparar su distribución de vecinos y compararlo con uno aleatorio . Por ejemplo, puede comparar sus medias y variaciones.$P_{measured}(k|n)$$P_{rand,p}(k|n)$

Alternativamente, uno puede medir sus distancias en los espacios de funciones, por ejemplo: donde es la relación medida de puntos con espacios adyacentes y es el predicho para un patrón aleatorio, es decir, , y .

Hay una manera realmente simple de conceptualizar el contenido de la información que se remonta a la idea de Shannon (ciertamente unidimensional) utilizando probabilidades y probabilidades de transición para encontrar una representación menos redundante de una cadena de texto. Para una imagen (en este caso particular, una imagen binaria definida en una matriz cuadrada) podemos reconstruir únicamente a partir de un conocimiento de las derivadas x e y (-1,0, + 1). Podemos definir una probabilidad de transición 3x3 y una función de densidad de probabilidad global, también 3x3. La información de Shannon se obtiene de la clásica fórmula de suma logarítmica aplicada en 3x3. Esta es una medida de información de Shannon de segundo orden y captura muy bien la estructura espacial en el pdf 3x3.

Este enfoque es más intuitivo cuando se aplica a imágenes en escala de grises con más de 2 niveles (binarios), consulte https://arxiv.org/abs/1609.01117 para obtener más detalles.

Al leer esto, se me ocurren dos cosas. La primera es que muchas de las propiedades de gestalt son bastante difíciles de predecir, y una gran cantidad de trabajo de nivel de doctorado se dedica a tratar de descubrir modelos sobre cómo se llevan a cabo las agrupaciones. Mi instinto es que las reglas más fáciles que se te ocurran terminarán con ejemplos contrarios.

Si puede dejar de lado la descripción de las agrupaciones de gestalt por ahora, creo que una abstracción útil es pensar en su entrada como un caso especial de una imagen. Hay muchos algoritmos en visión por computadora que tienen como objetivo asignar una firma a una imagen en función de un conjunto de características que son invariantes de escala e invariantes de características. Creo que las más conocidas son las características de SIFT:

http://en.wikipedia.org/wiki/Scale-invariant_feature_transform

Básicamente, su salida será un nuevo vector que proporciona los pesos para estas características. Puede usar este vector y aplicarle una heurística (encontrar la norma, tal vez) y esperar que describa lo que está buscando. Alternativamente, podría entrenar a un clasificador para tomar el vector de características como entrada y simplemente decirle cuál es su impresión de su 'entropía'. La ventaja de esto es que usará las características SIFT apropiadas (que definitivamente son excesivas para su problema) y construirá algún tipo de mapeo que bien podría ser apropiado. La desventaja es que tienes que hacer mucho de ese etiquetado tú mismo, y lo que obtienes puede ser más difícil de interpretar, dependiendo del clasificador que uses.

¡Espero que esto sea útil! Muchos de los algoritmos tradicionales de visión por computadora también pueden ser apropiados para usted aquí: una exploración rápida a través de wikipedia en ese portal puede brindarle información adicional.

Sus ejemplos me recuerdan las tablas de verdad del álgebra booleana y los circuitos digitales. En este ámbito, los mapas de Karnaugh (http://en.wikipedia.org/wiki/Karnaugh_map) se pueden usar como una herramienta para proporcionar la función booleana mínima para expresar toda la cuadrícula. Alternativamente, el uso de identidades de álgebra booleana puede ayudar a reducir la función a su forma mínima. Contar el número de términos en la función booleana minimizada podría usarse como medida de entropía. Esto le brinda simetría vertical y horizontal junto con la compresión de los vecinos adyacentes, pero carece de simetría diagonal.

Usando álgebra booleana, ambos ejes se etiquetan desde AE ​​comenzando en la esquina superior izquierda. De esta manera, el ejemplo C se correlacionaría con la función booleana (! A y! E). Para otros ejemplos, los ejes tendrían que etiquetarse por separado (es decir, AE, FJ).