Measuring entropy/ information/ patterns of a 2d binary matrix

Question

I want to measure the entropy/ information density/ pattern-likeness of a two-dimensional binary matrix. Let me show some pictures for clarification:

This display should have a rather high entropy:

A)

This should have medium entropy:

B)

These pictures, finally, should all have near-zero-entropy:

C)

D)

E)

Is there some index that captures the entropy, resp. the "pattern-likeness" of these displays?

Of course, each algorithm (e.g., compression algorithms; or the rotation algorithm proposed by ttnphns) is sensitive to other features of the display. I am looking for an algorithm that tries to capture following properties:

• Rotational and axial symmetry
• The amount of clustering
• Repetitions

Maybe more complicated, the algorith could be sensitive to properties of the psychological "Gestalt principle", in particular:

• The law of proximity:
• The law of symmetry: Symmetrical images are perceived collectively, even in spite of distance:

Displays with these properties should get assigned a "low entropy value"; displays with rather random / unstructured points should get assigned a "high entropy value".

I am aware that most probably no single algorithm will capture all of these features; therefore suggestions for algorithms which address only some or even only a single feature are highly welcome as well.

In particular, I am looking for concrete, existing algorithms or for specific, implementable ideas (and I will award the bounty according to these criteria).

Answer 1

There is a simple procedure that captures all the intuition, including the psychological and geometrical elements. It relies on using spatial proximity, which is the basis of our perception and provides an intrinsic way to capture what is only imperfectly measured by symmetries.

To do this, we need to measure the "complexity" of these arrays at varying local scales. Although we have much flexibility to choose those scales and choose the sense in which we measure "proximity," it is simple enough and effective enough to use small square neighborhoods and to look at averages (or, equivalently, sums) within them. To this end, a sequence of arrays can be derived from any $m$ by $n$ array by forming moving neighborhood sums using $k=2$ by $2$ neighborhoods, then $3$ by $3$, etc, up to $\min(n,m)$ by $\min(n,m)$ (although by then there are usually too few values to provide anything reliable).

To see how this works, let's do the calculations for the arrays in the question, which I will call $a_1$ through $a_5$, from top to bottom. Here are plots of the moving sums for $k=1,2,3,4$ ($k=1$ is the original array, of course) applied to $a_1$.

Clockwise from the upper left, $k$ equals $1$, $2$, $4$, and $3$. The arrays are $5$ by $5$, then $4$ by $4$, $2$ by $2$, and $3$ by $3$, respectively. They all look sort of "random." Let's measure this randomness with their base-2 entropy. When an array $a$ contains various distinct values with proportions $p_1,$ $p_2,$ etc., its entropy (by definition) is

$$H(a) = -p_1\log_2(p_1) - p_2\log_2(p_2) - \cdots$$

For instance, array $a_1$ has ten black cells and 15 white cells, whence they are in proportions of $10/25$ and $15/25,$ respectively. Its entropy therefore is $$H(a_1) = -(10/25)\log_2(10/25) - (15/25)\log_2(15/25) \approx 0.970951.$$

For $a_1$, the sequence of these entropies for $k=1,2,3,4$ is $(0.97, 0.99, 0.92, 1.5)$. Let's call this the "profile" of $a_1$.

Here, in contrast, are the moving sums of $a_4$:

For $k=2, 3, 4$ there is little variation, whence low entropy. The profile is $(1.00, 0, 0.99, 0)$. Its values are consistently close to or lower than the values for $a_1$, confirming the intuitive sense that there is a strong "pattern" present in $a_4$.

We need a frame of reference for interpreting these profiles. A perfectly random array of binary values will have just about half its values equal to $0$ and the other half equal to $1$, for an entropy close to $1$. The moving sums within $k$ by $k$ neighborhoods will tend to have binomial distributions, giving them predictable entropies (at least for large arrays) that can be approximated by $1 + \log_2(k)$:

These results are borne out by simulation with arrays up to $m=n=100$. However, they break down for small arrays (such as the $5$ by $5$ arrays here) due to correlation among neighboring windows (once the window size is about half the dimensions of the array) and due to the small amount of data. Here is a reference profile of random $5$ by $5$ arrays generated by simulation along with plots of some actual profiles:

In this plot the reference profile is solid blue. The array profiles correspond to $a_1$: red, $a_2$: gold, $a_3$: green, $a_4$: light blue. (Including $a_5$ would obscure the picture because it is close to the profile of $a_4$.) Overall the profiles correspond to the ordering in the question: they get lower at most values of $k$ as the apparent ordering increases. The exception is $a_1$: until the end, for $k=4$, its moving sums tend to have among the lowest entropies. This reveals a surprising regularity: every $2$ by $2$ neighborhood in $a_1$ has exactly $1$ or $2$ black squares, never any more or less. It's much less "random" than one might think. (This is partly due to the loss of information that accompanies summing the values in each neighborhood, a procedure that condenses $2^{k^2}$ possible neighborhood configurations into just $k^2+1$ different possible sums. If we wanted to account specifically for the clustering and orientation within each neighborhood, then instead of using moving sums we would use moving concatenations. That is, each $k$ by $k$ neighborhood has $2^{k^2}$ possible different configurations; by distinguishing them all, we can obtain a finer measure of entropy. I suspect that such a measure would elevate the profile of $a_1$ compared to the other images.)

This technique of creating a profile of entropies over a controlled range of scales, by summing (or concatenating or otherwise combining) values within moving neighborhoods, has been used in analysis of images. It is a two-dimensional generalization of the well-known idea of analyzing text first as a series of letters, then as a series of digraphs (two-letter sequences), then as trigraphs, etc. It also has some evident relations to fractal analysis (which explores properties of the image at finer and finer scales). If we take some care to use a block moving sum or block concatenation (so there are no overlaps between windows), one can derive simple mathematical relationships among the successive entropies; however, I suspect that using the moving window approach may be more powerful and is a little less arbitrary (because it does not depend on precisely how the image is divided into blocks).

Various extensions are possible. For instance, for a rotationally invariant profile, use circular neighborhoods rather than square ones. Everything generalizes beyond binary arrays, of course. With sufficiently large arrays one can even compute locally varying entropy profiles to detect non-stationarity.

If a single number is desired, instead of an entire profile, choose the scale at which the spatial randomness (or lack thereof) is of interest. In these examples, that scale would correspond best to a $3$ by $3$ or $4$ by $4$ moving neighborhood, because for their patterning they all rely on groupings that span three to five cells (and a $5$ by $5$ neighborhood just averages away all variation in the array and so is useless). At the latter scale, the entropies for $a_1$ through $a_5$ are $1.50$, $0.81$, $0$, $0$, and $0$; the expected entropy at this scale (for a uniformly random array) is $1.34$. This justifies the sense that $a_1$ "should have rather high entropy." To distinguish $a_3$, $a_4$, and $a_5$, which are tied with $0$ entropy at this scale, look at the next finer resolution ($3$ by $3$ neighborhoods): their entropies are $1.39$, $0.99$, $0.92$, respectively (whereas a random grid is expected to have a value of $1.77$). By these measures, the original question puts the arrays in exactly the right order.

Answer 2

First, my suggestion is purely intuitive: I know nothing in pattern recognition field. Second, alternative dozens suggestions like mine could be made.

I start with idea that a regular configuration (that is, with low entropy) should be somehow symmetric, isomorphic to this or that its tranformants. For example, in rotations.

You could rotate (flip to 90 degrees, than 180 degrees, etc) your matrix until the configuration concur with the original one. It will always concur upon 4 rotations (360 degrees), but sometimes it can concur earlier (like matrix E in the picture).

At each rotation, count the number of cells with not identical values between the original configuration and the rotated one. For example, if you compare original matrix A with its 90-degree rotation you'll discover 10 cells where there is spot in one matrix and blank in the other matrix. Then compare the original matrix with its 180-degree rotation: 11 such cells will be found. 10 cells is the discrepancy between the original matrix A and its 270-degrees rotation. 10+11+10=31 is the overall "entropy" of matrix A.

For matrix B the "entropy" is 20, and for matrix E it is only 12. For matrices C and D "entropy" is 0 because rotations stop after 90 degrees: isomorphism attained already.

Answer 3

The information is commonly defined as $h(x) = \log p(x)$. There is some nice theory explaining that $\log_2 p(x)$ is the amount of bits you need to code $x$ using $p$. If you want to know more about this read up on arithmetic coding.

So how can that solve your problem? Easy. Find some $p$ that represents your data and use $-\log p(x)$ where $x$ is a new sample as a measure of surprise or information of encountering it.

The hard thing is to find some model for $p$ and to generate your data. Maybe you can come up with an algorithm that generates matrices which you deem 'probable'.

Some ideas for fitting $p$.

1. If you are only looking at 5x5 matrices, you only need $2^{25}$ bits to store all possible matrices, so you can just enumerate all of them and assign a certain probability to each.
2. Use a restricted Boltzmann machine to fit your data (then you'd have to use the free energy as a substitute for information, but that's okay),
3. Use zip as a substitute for $-\log p(x)$ and don't care about the whole probability story from above. It's even formally okay, because you use zip as an approximation to Kolmogorov complexity and this has been done by information theorists as well leading to the normalized compression distance,
4. Maybe use a graphical model to include spatial prior beliefs and use Bernoulli variables locally.
5. To encode translational invariance, you could use an energy based model using a convolutional network.

Some of the ideas above are quite heavy and come from machine learning. In case you want to have further advice, just use the comments.

Answer 4

My following proposal is rather insighted than deduced, so I cannot prove it, but can at least offer some rationale. The procedure of assessing of "entropy" of the configuration of spots includes:

1. Digitize spots.
2. Perform comparison of the configuration with itself permuted, many times, by orthogonal Procrustes analysis.
3. Plot results of comparisons (identity coefficient) and assess jaggedness of the plot.

Digitize spots, that is, take their coordinates. For example, below is your configuration D with numbered spots (numbering order may be arbitrary) and their coordinates.

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

Do permutations and perform Procrustes analysis. Permute spots (rows in the data) randomly and perform Procrustes comparison of the original (not permuted) data with the permuted one; record the identity coefficient (measure of similarity of the two configurations, output by the analysis). Repeat permutation - Procrustes - saving the coefficient, many times (e.g. 1000 times or more).

What can we await from identity coefficients (IDc) obtained after the above operation on a regular structure? Consider for example the above configuration D. If we compare the original coordinates set with itself, we will get IDc=1, of course. But if we permute some spots the IDc between the original set and the permuted will be some value below 1. Let us permute, just for example, one pair of spots, labeled 1 and 4. IDc=.964. Now, instead, permute spots 3 and 5. Interestingly, IDc will be .964 again. The same value, why? Spots 3 and 5 are symmetric to 1 and 4, so that rotation to 90 degrees superpose them. Procrustes comparison is insensitive to rotation or reflexion, and thereby permutation within pair 1-4 is the "same" as permutation within pair 5-3, for it. To add more example, if you permute just spots 4 and 7, IDc will be again .964! It appeares that for Procrustes, permutation within pair 4-7 is the "same" as the above two in the sense that it gives the same degree of similarity (as measured by IDc). Obviously, this all is because configuration D is regular. For a regular configuration we expect to obtain rather discrete values of IDc in our permutation/comparison experiment; while for irregular configuration we expect that the values will tend to be continuous.

Plot the recorded IDc values. For example, sort the values and make line-plot. I did the experiment - 5000 permutations - with each of your configurations A, B (both quite irregular), D, E (both regular) and here's the line-plot:

Note how much more jagged are lines D and E (D especially). This is because of discreteness of the values. Values for A and B are much more continuous. You can pick yourself some kind of statistic that estimates degree of discreteness/continuety, instead of plotting. A seems no more continuous than B (for you, configuration A is somewhat less regular, but my line-plot seem not to demonstrate it) or, if not, maybe shows a bit another pattern of IDc values. What another pattern? This is beyond the scope of my answer yet. The big question whether A is indeed less regular than B: it may be for your eye, but not necessarily for Procrustes analysis or another person's eye.

By the way, the whole permutation/Procrustes experiment I did very quickly. I used my own Procrustes analysis macro for SPSS (found on my web-page) and add some lines of code to do permutations.

Answer 5

Mutual information, considering each dimension as a random variable, thus each matrix as a set of pairs of numbers, should help in all cases, except for C, where I am not sure of the result.

See the discussion around Fig 8 (starting in p24) on regression performance analysis in the TMVA manual or the corresponding arxiv entry.

Answer 6

Instead of looking at global properties of the pattern (like symmetries), one can take a look at the local ones, e.g. the number of neighbors each stone (=black circle) has. Let's denote the total number of stones by $s$.

If the stones where thrown at random, the distribution of neighbors is $$P_{rand,p}(k\ \text{neighbors}|n\ \text{places} ) = {n \choose k} p^{k} (1-p)^{n-k},$$ where $p = s/25$ is the density of stones. Number of places $n$ depends if a stone is in the interior ($n=8$), on the edge ($n=5$) or on the corner $(n=3)$.

It is clearly visible, that distribution of neighbors in C), D) and E) are far from random. For example, for D) all interior stones have exactly $4$ neighbors (opposing to random distribution, which yields in $\approx (0\%,2\%,9\%,20\%,27\%,24\%,13\%,4\%,0\%)$ instead of the measured $(0\%,0\%,0\%,0\%,100\%,0\%,0\%,0\%,0\%)$).

So to quantify if a pattern is random you need to compare its distribution of neighbors $P_{measured}(k|n)$ and compare it with a random one $P_{rand,p}(k|n)$. For example you can compare their means and variances.

Alternatively, one can measure their distances in the function spaces, e.g.: $$\sum_{n=\{3,5,8\}} \sum_{k=0}^n\left[P_{measured}(k|n)P_{measured}(n) -P_{rand,p}(k|n)P_{rand,p}(n)\right]^2,$$ where $P_{measured}(n)$ is the measured ratio of points with $n$ adjacent spaces and $P_{rand,p}(n)$ is the predicted for a random pattern, i.e. $P_{rand,p}(3) = 4/25$, $P_{rand,p}(5) = 12/25$ and $P_{rand,p}(8) = 9/25$.

Answer 7

There is a really simple way to conceptualize the information content that harks back to Shannon's (admittedly one dimensional) idea using probabilities and transition probabilities to find a least redundant representation of a text string. For an image (in this particular case a binary image defined on a square matrix) we can uniquely reconstruct from a knowledge of the x and y derivatives (-1,0,+1). We can define a 3x3 transition probability and a global probability density function, also 3x3. The Shannon information is then obtained from the classic logarithmic summation formula applied over 3x3. This is a second order Shannon information measure and nicely captures the spatial structure in the 3x3 pdf.

This approach is more intuitive when applied to grayscale images with more than 2 (binary) levels, see https://arxiv.org/abs/1609.01117 for more details.

Answer 8

In reading this, two things come to mind. The first is that a lot of the gestalt properties are quite challenging to predict, and a lot of PhD level work goes into trying to figure out models for how groupings take place. My instinct is that most easy rules that you could think of will end up with counter examples.

If you can put aside the description of gestalt groupings for now, I think a helpful abstraction is to think of your input as a special case of an image. There are a lot of algorithms in computer vision that aim to assign a signature to an image based on a set of features that are scale invariant and feature invariant. I think the most well known are the SIFT features:

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

Basically your output will be a new vector which gives the weights for these features. You could use this vector and either apply a heuristic to it (find the norm, perhaps) and hope that it describes what you're looking for. Alternatively, you could train a classifier to take the feature vector as input and just tell it what your impression of its 'entropy' is. The upside of this is that it will use the appropriate SIFT features (which are definitely overkill for your problem) and construct some sort of mapping that may very well be appropriate. The downside is that you have to do a lot of that labeling yourself, and what you get may be tougher to interpret, depending on the classifier that you use.

I hope this is helpful! A lot of traditional computer vision algorithms may also be appropriate for you here - a quick browse through wikipedia in that portal may give you some additional insight.

Answer 9

Your examples remind me of truth tables from boolean algebra and digital circuits. In this realm, Karnaugh maps (http://en.wikipedia.org/wiki/Karnaugh_map) can be used as a tool to provide the minimal boolean function to express the entire grid. Alternatively, using boolean algebra identities can help to reduce the function to its minimal form. Counting the number of terms in the minimized boolean function could be used as your entropy measure. This gives you vertical and horizontal symmetry along with compressing adjacent neighbors, but lacks diagonal symmetry.

Using boolean algebra, both axes are labelled from A-E starting at the upper left corner. In this manner, example C would map to the boolean function (!A & !E). For other examples, the axes would need to be be labelled separately (i.e. A-E, F-J).

Answer 10

I would point out the rank of the matrix used in binary matrix factorization as an indicator of the entropy. Although exact computation is NP-hard, the rank can be estimated in O(log2n) time.

I would also merely point out that comparison with 3 rotations and 4 reflections method has a real flaw.

For a matrix with an odd number of rows/columns, there will be a center row or column which will overlap with the original data in rotations/reflections which will cause the entropy amount to be lowered.

Additionally, for the reflection at the 90 and 270 degree position, all of the diagonals will be overlapping also lowering the entropy. So this loss should all be accounted for.