Mesure de l'entropie / informations / motifs d'une matrice binaire 2D

Je veux mesurer l'entropie / densité d'information / ressemblance-motif d'une matrice binaire à deux dimensions. Permettez-moi de montrer quelques images pour clarification:

Cet affichage devrait avoir une entropie assez élevée:

UNE)

Cela devrait avoir une entropie moyenne:

B)

Enfin, ces images devraient toutes avoir une entropie proche de zéro:

C)

RÉ)

E)

Y at-il un index qui capture l’entropie, resp. la "ressemblance de motif" de ces affichages?

Bien entendu, chaque algorithme (par exemple, un algorithme de compression ou l' algorithme de rotation proposé par ttnphns ) est sensible aux autres caractéristiques de l'affichage. Je cherche un algorithme qui tente de capturer les propriétés suivantes:

• Symétrie rotationnelle et axiale
• La quantité de clustering
• Répétitions

Peut-être plus compliqué, l'algorithme pourrait être sensible aux propriétés du " principe de Gestalt " psychologique , en particulier:

• La loi de proximité:
• La loi de symétrie: les images symétriques sont perçues collectivement, même en dépit de la distance:

Les affichages avec ces propriétés doivent recevoir une "valeur d'entropie faible"; les affichages avec des points plutôt aléatoires / non structurés doivent se voir attribuer une "valeur d'entropie élevée".

Je suis conscient que probablement aucun algorithme ne capturera toutes ces caractéristiques; par conséquent, les suggestions d’algorithmes qui ne traitent que certaines ou même une seule fonctionnalité sont également les bienvenues.

En particulier, je recherche des algorithmes concrets existants ou des idées spécifiques pouvant être mises en œuvre (et j'attribuerai la prime en fonction de ces critères).

Il existe une procédure simple qui capture toute l’intuition, y compris les éléments psychologiques et géométriques. Il s'appuie sur la proximité spatiale , qui est la base de notre perception et fournit un moyen intrinsèque de capturer ce qui n'est qu'imparfaitement mesuré par des symétries.

Pour ce faire, nous devons mesurer la "complexité" de ces tableaux à différentes échelles locales. Bien que nous ayons beaucoup de flexibilité pour choisir ces échelles et choisir le sens dans lequel nous mesurons la "proximité", il est suffisamment simple et efficace pour utiliser des quartiers de petite taille et examiner les moyennes (ou, de façon équivalente, les sommes) qu’ils contiennent. À cette fin, une séquence de tableaux peut être dérivée à partir de n’importe quel tableau par en formant des sommes de voisinage mobiles en utilisant par voisin, puis par , etc., jusqu’à par (même si à ce moment-là, il y a généralement trop peu de valeurs pour fournir quelque chose de fiable).n k = 2 2 3 3 min ( n , m ) min ( n , m $m$$n$$k=2$$2$$3$$3$$\min(n,m)$$\min(n,m)$

Pour voir comment cela fonctionne, calculons les tableaux de la question, que j'appellerai de à , de haut en bas. Voici les tracés des sommes en mouvement pour ( est le tableau d'origine, bien sûr) appliqué à .a 5 k = 1 , 2 , 3 , 4 k = 1 a $a_1$$a_5$$k=1,2,3,4$$k=1$$a_1$

Dans le sens des aiguilles d'une montre, en haut à gauche, est égal à , , et . Les tableaux sont par , puis par , par et par , respectivement. Ils ont tous l'air un peu "aléatoire". Mesurons ce caractère aléatoire avec leur entropie en base 2. Pour , la séquence de ces entropies est la suivante . Appelons cela le "profil" de .1 2 4 3 5 5 4 4 2 2 3 3 a 1 ( 0,97 , 0,99 , 0,92 , 1,5 ) a $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$

Voici, en revanche, les sommes en mouvement de :$a_4$

Pour il y a peu de variation, d'où une faible entropie. Le profil est . Ses valeurs sont systématiquement inférieures à celles de , confirmant ainsi le sentiment intuitif qu'il existe un "motif" puissant présent dans .$k=2, 3, 4$$(1.00, 0, 0.99, 0)$$a_1$$a_4$

Nous avons besoin d'un cadre de référence pour interpréter ces profils. Un tableau parfaitement aléatoire de valeurs binaires aura à peu près la moitié de ses valeurs égales à et l’autre moitié à , pour une entropie de . Les sommes en mouvement dans par voisin auront tendance à avoir des distributions binomiales, ce qui leur donnera des entropies prévisibles (au moins pour les grands tableaux) pouvant être approchées par :$0$$1$$1$$k$$k$$1 + \log_2(k)$

Ces résultats sont corroborés par simulation avec des matrices jusqu’à . Cependant, ils se décomposent pour les petits tableaux (tels que les tableaux de sur ici) en raison de la corrélation entre les fenêtres voisines (une fois que la taille de la fenêtre est environ la moitié de la taille de la matrice) et en raison de la petite quantité de données. Voici un profil de référence de tableaux aléatoires de sur générés par simulation ainsi que des tracés de certains profils réels:$m=n=100$$5$$5$$5$$5$

Dans ce graphique, le profil de référence est bleu continu. Les profils de tableau correspondent à : rouge, : or, : vert, : bleu clair. (L'inclusion de obscurcirait l'image car elle est proche du profil de .) Globalement, les profils correspondent à l'ordre dans la question: ils diminuent au maximum de lorsque l'ordre apparent augmente. L'exception est : jusqu'à la fin, pour , ses sommes en mouvement ont tendance à avoir des entropies parmi les plus basses . Cela révèle une régularité surprenante: tous par quartiera 2 a 3 a 4 a 5 a 4 k a 1 k = 4 2 2 a 1 1 2 2 k 2 k 2 + 1 $a_1$$a_2$$a_3$$a_4$$a_5$$a_4$$k$$a_1$$k=4$$2$$2$$a_1$ a exactement ou carrés noirs, jamais plus ni moins. C'est beaucoup moins "aléatoire" qu'on pourrait le penser. (Ceci est en partie dû à la perte d'informations qui accompagne la somme des valeurs dans chaque voisinage, une procédure qui condense configurations de voisinage possibles en seulement différentes sommes possibles. Si nous voulions rendre compte spécifiquement pour le regroupement et l'orientation dans chaque voisinage, alors, au lieu d'utiliser des sommes en mouvement, nous utiliserions des concaténations en mouvement, c'est-à-dire que chaque voisinage de sur a$1$$2$$2^{k^2}$$k^2+1$$k$$k$$2^{k^2}$différentes configurations possibles; en les distinguant tous, nous pouvons obtenir une mesure plus fine de l'entropie. Je soupçonne qu'une telle mesure augmenterait le profil de par rapport aux autres images.)$a_1$

Cette technique de création d'un profil d'entropies sur une plage d'échelles contrôlée, en sommant (ou en concaténant ou en combinant autrement) des valeurs dans des quartiers en mouvement, a été utilisée dans l'analyse d'images. Il s’agit d’une généralisation en deux dimensions de l’idée bien connue d’analyser le texte en une série de lettres, puis en une série de digrammes (séquences de deux lettres), puis en tant que trigraphes, etc. l'analyse (qui explore les propriétés de l'image à des échelles de plus en plus fines). Si nous prenons soin d'utiliser une somme ou une concaténation de blocs en mouvement (afin d'éviter tout chevauchement de fenêtres), on peut déduire des relations mathématiques simples entre les entropies successives; cependant,

Diverses extensions sont possibles. Par exemple, pour un profil invariant en rotation, utilisez des quartiers circulaires plutôt que des carrés. Tout se généralise au-delà des tableaux binaires, bien sûr. Avec des tableaux suffisamment grands, on peut même calculer des profils d'entropie variant localement pour détecter la non-stationnarité.

Si vous souhaitez un seul numéro au lieu d'un profil complet, choisissez l'échelle à laquelle le caractère aléatoire de l'espace (ou son absence) présente un intérêt. Dans ces exemples, cette échelle correspondrait le mieux à un quartier en mouvement de sur ou sur , car pour leur structuration, ils reposent tous sur des groupes de trois à cinq cellules (et un quartier de sur élimine en moyenne toute variation de la tableau et est donc inutile). À cette dernière échelle, les entropies pour à sont , , , et3 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$ ; l'entropie attendue à cette échelle (pour un tableau uniformément aléatoire) est . Cela justifie le sens que "devrait avoir une entropie plutôt élevée". Pour distinguer , et , qui sont à égalité avec entropie à cette échelle, regard à la prochaine résolution plus fine ( par quartiers): leurs entropies sont , , , respectivement (alors qu'une grille aléatoire devrait avoir une valeur de ). Par ces mesures, la question initiale met les tableaux dans le bon ordre.$1.34$$a_1$$a_3$$a_4$$a_5$$0$$3$$3$$1.39$$0.99$$0.92$$1.77$

Premièrement, ma suggestion est purement intuitive: je ne sais rien en matière de reconnaissance de formes. Deuxièmement, des dizaines de suggestions alternatives comme la mienne pourraient être faites.

Je commence par l'idée qu'une configuration régulière (c'est-à-dire avec une entropie faible) devrait être symétrique, isomorphe à telle ou telle de ses transformations. Par exemple, dans les rotations.

Vous pouvez faire pivoter (basculer à 90 degrés, que 180 degrés, etc.) votre matrice jusqu'à ce que la configuration concorde avec celle d'origine . Il sera toujours conforme à 4 rotations (360 degrés), mais parfois, il peut concourir plus tôt (comme la matrice E sur la photo).

À chaque rotation, comptez le nombre de cellules avec des valeurs non identiques entre la configuration d'origine et celle qui a subi la rotation. Par exemple, si vous comparez la matrice A d' origine avec sa rotation de 90 degrés, vous découvrez 10 cellules où il y a des taches dans une matrice et des blancs dans l'autre matrice. Comparez ensuite la matrice d'origine avec sa rotation de 180 degrés: 11 cellules de ce type seront trouvées. 10 cellules correspond à la différence entre la matrice A d'origine et sa rotation à 270 degrés. + 11 + 10 = 10 31 est le " l' entropie" globale de la matrice A .

Pour la matrice B, "l'entropie" est égale à 20 et pour la matrice E, elle n'est que 12. Pour les matrices C et D, "entropie" est égale à 0, car les rotations s'arrêtent après 90 degrés: l'isomorphisme est déjà atteint.

Les informations sont généralement définies comme suit: . Il existe une théorie intéressante qui explique que est la quantité de bits dont vous avez besoin pour coder utilisant . Si vous voulez en savoir plus sur cette lecture, lisez le code arithmétique .log 2 p ( x ) x $h(x) = \log p(x)$$\log_2 p(x)$$x$$p$

Alors, comment cela peut-il résoudre votre problème? Facile. Trouvez quelques qui représentent vos données et utilisez où est un nouvel échantillon servant à mesurer la surprise ou les informations permettant de le rencontrer.$p$$-\log p(x)$$x$

La difficulté est de trouver un modèle pour et de générer vos données. Peut-être pouvez-vous trouver un algorithme qui génère des matrices que vous jugez «probables».$p$

Quelques idées pour un ajustement .$p$

1. Si vous ne regardez que des matrices 5x5, il vous suffit de bits pour stocker toutes les matrices possibles. Vous pouvez donc toutes les énumérer et leur attribuer une certaine probabilité.$2^{25}$
2. Utilisez une machine restreinte de Boltzmann pour adapter vos données (vous devrez alors utiliser l'énergie gratuite comme substitut d'informations, mais ce n'est pas grave),
3. Utilisez zip comme substitut de et ne vous souciez pas de l’ensemble de la probabilité ci-dessus. C'est même formellement bon, parce que vous utilisez zip comme une approximation de la complexité de Kolmogorov et que cela a été fait par les théoriciens de l'information conduisant également à la distance de compression normalisée ,$-\log p(x)$
4. Peut-être utiliser un modèle graphique pour inclure les croyances antérieures spatiales et utiliser les variables de Bernoulli localement.
5. Pour coder une invariance traductionnelle, vous pouvez utiliser un modèle basé sur l'énergie utilisant un réseau convolutionnel .

Certaines des idées ci-dessus sont assez lourdes et proviennent de l'apprentissage automatique. Si vous souhaitez obtenir des conseils supplémentaires, utilisez simplement les commentaires.

Ma proposition suivante est plutôt éclairée que déduite, je ne peux donc pas le prouver, mais je peux au moins donner une justification. La procédure d'évaluation de "l'entropie" de la configuration des taches comprend:

1. Numériser des spots.
2. Effectuez la comparaison de la configuration avec elle-même permutée plusieurs fois par analyse orthogonale de Procrustes .
3. Résultats de la parcelle des comparaisons (coefficient d'identité) et évaluer l'irrégularité de la parcelle.

Numériser des spots , c'est-à-dire prendre leurs coordonnées. Par exemple, vous trouverez ci-dessous votre configuration D avec des emplacements numérotés (l’ordre de numérotation peut être arbitraire) et leurs coordonnées.

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

Faites des permutations et effectuez une analyse Procrustes. Taches de permutation (lignes dans les données) de manière aléatoire et effectuer une comparaison Procrustes des données d'origine (non permutées) avec celles permutées; enregistrer le coefficient d'identité (mesure de la similarité des deux configurations, sortie de l'analyse). Répéter la permutation - Procrustes - en enregistrant le coefficient plusieurs fois (par exemple 1000 fois ou plus).

Que pouvons-nous attendre des coefficients d’identité (IDc) obtenus après l’opération ci-dessus sur une structure régulière ?Considérons par exemple la configuration D ci-dessus. Si nous comparons le jeu de coordonnées d'origine à lui-même, nous aurons IDc = 1, bien sûr. Mais si nous permutons quelques points, l'IDc entre l'ensemble d'origine et le permuté sera une valeur inférieure à 1. Permutons, juste par exemple, une paire de points, étiquetés 1 et 4. IDc = 0,964. Maintenant, au lieu de cela, permutez les taches 3 et 5. Fait intéressant, IDc sera à nouveau de 0,964. La même valeur, pourquoi? Les points 3 et 5 sont symétriques par rapport aux points 1 et 4, de sorte qu'une rotation à 90 degrés les superpose. La comparaison procrustes est insensible à la rotation ou à la réflexion et, par conséquent, la permutation dans la paire 1-4 est "identique" à la permutation dans la paire 5-3. Pour ajouter d'autres exemples, si vous permutez seulement les points 4 et 7, IDc sera à nouveau 0,964! Il semble que pour Procrustes, la permutation dans la paire 4-7 soit la même chose comme ci-dessus deux dans le sens où il donne le même degré de similitude (tel que mesuré par IDc). Évidemment, tout cela est dû au fait que la configuration D est régulière.Pour une configuration régulière, nous nous attendons à obtenir des valeurs discrètes de IDc dans notre expérience de permutation / comparaison; tandis que pour une configuration irrégulière, nous nous attendons à ce que les valeurs tendent à être continues.

Tracer les valeurs IDc enregistrées. Par exemple, triez les valeurs et créez un tracé linéaire. J'ai fait l'expérience - 5000 permutations - avec chacune de vos configurations A, B (les deux assez irrégulières), D, E (les deux normales) et voici le tracé de la ligne:

Notez combien les lignes D et E sont plus irrégulières (D en particulier). C'est à cause de la discrétion des valeurs. Les valeurs pour A et B sont beaucoup plus continues. Vous pouvez choisir vous-même une statistique qui estime le degré de discrétion / de continuité au lieu de tracer. A ne semble pas plus continu que B (pour vous, la configuration A est un peu moins régulière, mais mon tracé de ligne ne semble pas le démontrer) ou, sinon, montre peut-être un autre motif de valeurs IDc. Quel autre motif? Ceci dépasse le cadre de ma réponse pour le moment. La grande question de savoir si A est en effet moins régulier que B: cela peut être pour votre œil, mais pas nécessairement pour l’analyse de Procrustes ou l’œil d’une autre personne.

À propos, toute l'expérience de permutation / Procrustes que j'ai faite très rapidement. J'ai utilisé ma propre macro d'analyse Procrustes pour SPSS (disponible sur ma page Web) et ajouté quelques lignes de code pour effectuer des permutations.

Les informations mutuelles, considérant chaque dimension comme une variable aléatoire, et donc chaque matrice comme un ensemble de paires de nombres, devraient aider dans tous les cas, sauf pour C, où je ne suis pas sûr du résultat.

Voir la discussion autour de la figure 8 (à partir de la p24) sur l’analyse de performance de régression dans le manuel TMVA ou l’entrée arxiv correspondante .

$s$

Si les pierres ont été jetées au hasard, la distribution des voisins est où est la densité des pierres. Le nombre de places dépend de la présence d'une pierre à l'intérieur ( ), sur le bord ( ) ou sur le coin .

Il est clairement visible que la distribution des voisins en C) , D) et E) est loin d'être aléatoire. Par exemple, pour D), toutes les pierres intérieures ont exactement voisins (opposées à la distribution aléatoire, ce qui donne un rendement au lieu des valeurs mesurées ).$4$$\approx (0\%,2\%,9\%,20\%,27\%,24\%,13\%,4\%,0\%)$$(0\%,0\%,0\%,0\%,100\%,0\%,0\%,0\%,0\%)$

Donc, pour quantifier si un motif est aléatoire, vous devez comparer sa distribution de voisins et la comparer à une distribution aléatoire . Par exemple, vous pouvez comparer leurs moyennes et leurs variances.$P_{measured}(k|n)$$P_{rand,p}(k|n)$

Alternativement, on peut mesurer leurs distances dans les espaces de fonction, par exemple: où est le rapport mesuré des points avec espaces adjacents et est le prédit pour un motif aléatoire, c'est-à-dire , et .

Il existe un moyen très simple de conceptualiser le contenu de l’information qui renvoie à l’idée de Shannon (certes unidimensionnelle) en utilisant des probabilités et des probabilités de transition pour trouver la représentation la moins redondante d’une chaîne de texte. Pour une image (dans ce cas particulier, une image binaire définie sur une matrice carrée), nous pouvons reconstruire uniquement à partir d'une connaissance des dérivées x et y (-1,0, + 1). Nous pouvons définir une probabilité de transition 3x3 et une fonction de densité de probabilité globale, également 3x3. Les informations de Shannon sont ensuite obtenues à partir de la formule de sommation logarithmique classique appliquée sur 3x3. Il s’agit d’une mesure d’information de Shannon de second ordre qui capture bien la structure spatiale dans le fichier PDF 3x3.

Cette approche est plus intuitive lorsqu'elle est appliquée aux images en niveaux de gris comportant plus de 2 niveaux (binaires). Pour plus de détails , voir https://arxiv.org/abs/1609.01117 .

En lisant ceci, deux choses me viennent à l’esprit. La première est que beaucoup de propriétés de gestalt sont assez difficiles à prévoir, et beaucoup de travaux de doctorat consistent à essayer de trouver des modèles pour la façon dont les groupements se produisent. Mon instinct est que les règles les plus simples auxquelles vous pourriez penser aboutiront avec des contre-exemples.

Si vous pouvez mettre de côté la description des groupes de gestalt pour le moment, je pense qu’une abstraction utile consiste à considérer votre contribution comme un cas particulier d’une image. Il existe de nombreux algorithmes en vision par ordinateur qui visent à attribuer une signature à une image en fonction d'un ensemble de caractéristiques invariantes en termes d'échelle et d'invariants. Je pense que les plus connues sont les fonctionnalités SIFT:

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

Fondamentalement, votre sortie sera un nouveau vecteur qui donne les poids pour ces entités. Vous pouvez utiliser ce vecteur et y appliquer une heuristique (trouver la norme, peut-être) et espérer qu'il décrit ce que vous recherchez. Vous pouvez également former un classificateur à prendre le vecteur de caractéristiques en entrée et à lui indiquer votre impression de son «entropie». L'avantage de ceci est qu'il utilisera les fonctionnalités SIFT appropriées (qui sont définitivement excessives pour votre problème) et construira une sorte de mappage qui pourrait très bien être approprié. L'inconvénient est que vous devez faire beaucoup d'étiquetage vous-même, et ce que vous obtenez peut être plus difficile à interpréter, selon le classificateur que vous utilisez.

J'espère que ceci est utile! De nombreux algorithmes traditionnels de vision par ordinateur peuvent également vous convenir ici. Un survol rapide de wikipedia dans ce portail peut vous donner des informations supplémentaires.

Vos exemples me rappellent les tables de vérité de l’algèbre booléenne et des circuits numériques. Dans ce domaine, les cartes Karnaugh (http://en.wikipedia.org/wiki/Karnaugh_map) peuvent être utilisées comme un outil permettant de fournir la fonction booléenne minimale permettant d'exprimer la grille entière. Alternativement, utiliser des identités d'algèbre booléenne peut aider à réduire la fonction à sa forme minimale. Compter le nombre de termes dans la fonction booléenne réduite pourrait être utilisé comme mesure d'entropie. Cela vous donne une symétrie verticale et horizontale ainsi que la compression des voisins adjacents, mais manque de symétrie diagonale.

En utilisant l'algèbre booléenne, les deux axes sont étiquetés à partir de AE ​​en commençant par le coin supérieur gauche. De cette manière, l'exemple C correspondrait à la fonction booléenne (! A &! E). Pour d'autres exemples, les axes devraient être étiquetés séparément (c.-à-d. AE, FJ).

Je soulignerais le rang de la matrice utilisée dans la factorisation matricielle binaire comme indicateur de l'entropie. Bien que le calcul exact soit NP-difficile , le rang peut être estimé en temps O (log2n) .

Je voudrais aussi simplement souligner que la comparaison avec la méthode des 3 rotations et des 4 réflexions a un réel défaut.

Pour une matrice avec un nombre impair de lignes / colonnes, il y aura une ligne ou une colonne centrale qui chevauchera les données d'origine en rotations / réflexions, ce qui entraînera une diminution de la quantité d'entropie.

De plus, pour la réflexion aux positions à 90 et 270 degrés, toutes les diagonales se chevaucheront, abaissant ainsi l'entropie. Donc, cette perte devrait tous être pris en compte.