29
$\begingroup$

What is the most information/physics-theoretical correct way to compute the entropy of an image? I don't care about computational efficiency right now - I want it theoretically as correct as possible.

Lets start with a gray-scale image. One intuitive approach is to consider the image as a bag of pixels and compute $$ H = - \sum_k p_k log_2(p_k) $$ where $K$ is the number of gray levels and $p_k$ is the probability associated with gray level $k$.

There are two problems with this definition:

  1. It works for one band (i.e. gray-scale), but how should one extend it in a statistically correct way to multiple bands? For example, for 2 bands, should one base oneself on $(X_1,X_2)$ and thus on PMF using $P(X_1=x_1,X_2=x_2)$? If one has many ($B$>>2) bands then $P(X_1=x_1, ..., X_B=x_B) \sim 1/N^B \rightarrow H_{MAX}$, which seems wrong.
  2. Spatial information is not taken into account. For example, the images below (custody of John Loomis) have the same $H$, although clearly they do not convey the same information.

enter image description hereenter image description here

Anyone care to explain or give advice, or refer me to some decent reference material about the subject? I am mainly interested in a theoretically correct approach of the second problem (i.e. spatial information).

$\endgroup$
  • 2
    $\begingroup$ I think you should look at markov random fields eg files.is.tue.mpg.de/chwang/papers/CVIU2013_MRFSurvey.pdf $\endgroup$ – seanv507 Sep 16 '16 at 11:15
  • 1
    $\begingroup$ also graylevel cooccurrence matrices $\endgroup$ – seanv507 Sep 16 '16 at 15:17
  • $\begingroup$ @seanv507, yes indeed. Undirected graphical models or Markov random fields is what I am studying now. Will post back when I know more. $\endgroup$ – Davor Josipovic Sep 16 '16 at 17:30
25
$\begingroup$

“What is the most information/physics-theoretical correct way to compute the entropy of an image?“

An excellent and timely question.

Contrary to popular belief, it is indeed possible to define an intuitively (and theoretically) natural information-entropy for an image.

Consider the following figure:

enter image description here

We can see that the differential image has a more compact histogram, therefore its Shannon information-entropy is lower. So we can get lower redundancy by using second order Shannon entropy (i.e. entropy derived from differential data). If we can extend this idea isotropically into 2D, then we might expect good estimates for image information-entropy.

A two dimensional histogram of gradients allows the 2D extension.

We can formalise the arguments and, indeed, this has been completed recently. Recapping briefly:

The observation that the simple definition (see for example MATLAB’s definition of image entropy) ignores spatial structure is crucial. To understand what is going on it is worth returning to the 1D case briefly. It has been long known that using the histogram of a signal to compute its Shannon information/entropy ignores the temporal or spatial structure and gives a poor estimate of the signal’s inherent compressibility or redundancy. The solution was already available in Shannon’s classic text; use the second order properties of the signal, i.e. transition probabilities. The observation in 1971 (Rice & Plaunt) that the best predictor of a pixel value in a raster scan is the value of the preceding pixel immediately leads to a differential predictor and a second order Shannon entropy that aligns with simple compression ideas such as run length encoding. These ideas were refined in the late 80s resulting in some classic lossless image (differential) coding techniques that are still in use (PNG, lossless JPG, GIF, lossless JPG2000) whilst wavelets and DCTs are only used for lossy encoding.

Moving now to 2D; researchers found it very hard to extend Shannon’s ideas to higher dimensions without introducing an orientation dependence. Intuitively we might expect the Shannon information-entropy of an image to be independent of its orientation. We also expect images with complicated spatial structure (like the questioner’s random noise example) to have higher information-entropy than images with simple spatial structure (like the questioner’s smooth gray-scale example). It turns out that the reason it was so hard to extend Shannon’s ideas from 1D to 2D is that there is a (one-sided) asymmetry in Shannon’s original formulation that prevents a symmetric (isotropic) formulation in 2D. Once the 1D asymmetry is corrected the 2D extension can proceed easily and naturally.

Cutting to the chase (interested readers can check out the detailed exposition in the arXiv preprint at https://arxiv.org/abs/1609.01117 ) where the image entropy is computed from a 2D histogram of gradients (gradient probability density function).

First the 2D pdf is computed by binning estimates of the images x and y derivatives. This resembles the binning operation used to generate the more common intensity histogram in 1D. The derivatives can be estimated by 2-pixel finite differences computed in the horizontal and vertical directions. For an NxN square image f(x,y) we compute NxN values of partial derivative fx and NxN values of fy. We scan through the differential image and for every pixel we use (fx,fy) to locate a discrete bin in the destination (2D pdf) array that is then incremented by one. We repeat for all NxN pixels. The resulting 2D pdf must be normalised to have overall unit probability (simply dividing by NxN achieves this). The 2D pdf is now ready for the next stage.

The computation of the 2D Shannon information entropy from the 2D gradient pdf is simple. Shannon’s classic logarithmic summation formula applies directly except for a crucial factor of one half which originates from special bandlimited sampling considerations for a gradient image (see arXiv paper for details). The half factor makes the computed 2D entropy even lower compared to other (more redundant) methods for estimating 2D entropy or lossless compression.

I’m sorry I haven’t written the necessary equations down here but everything is available in the preprint text. The computations are direct (non-iterative) and the computational complexity is of order (the number of pixels) NxN . The final computed Shannon information-entropy is rotation independent and corresponds precisely with the number of bits required to encode the image in a non-redundant gradient representation.

By the way, the new 2D entropy measure predicts an (intuitively pleasing) entropy of 8 bits per pixel for the random image and 0.000 bits per pixel for the smooth gradient image in the original question.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting work. Now, Razlighi has made a comparison of several entropy algorithms in this paper. I wonder how yours would compare, especially on the synthetic image that he uses there. Might be worth investigating. $\endgroup$ – Davor Josipovic Dec 11 '16 at 9:40
  • $\begingroup$ Thank you for mentioning the paper of Razlighi's. The crucial test results are shown in Fig 2. I believe that my 2D delentropy measure would have unit normalized entropy for correlation 0.0 and then drop to near zero normalized entropy for correlation 1.0. I have not actually computed these values but it follows directly from section 3.2 of my arXiv preprint because high correlation corresponds to low spectral bandwidth, hence low entropy. $\endgroup$ – Kieran Larkin Dec 20 '16 at 4:05
  • $\begingroup$ I like this approach. It seems intuitive for me. The additional step of calculating the gradient before calculating the entropy seems to encode the spatial information intuitively. I tried to play around and calculate it with Python here. But I struggled to reproduce the caustics from your paper (see code, last example). I can only reproduce them with floats! That's because with integers the gradients are in [-6,6] for my test image, even when using 16 bits resulting in only 49 non-zero bins for the histogram. $\endgroup$ – mxmlnkn Jul 13 '18 at 11:38
  • $\begingroup$ did your paper ever got published? Did you or someone else continue the work? $\endgroup$ – Andrei Jun 27 '19 at 15:31
  • $\begingroup$ A Matlab sample code would be great. $\endgroup$ – Pedro77 Jul 12 '19 at 11:24
9
$\begingroup$

There is none, it all depends on the context and your prior information. Entropy has many interpretations such as "measurement of order" or "measurement of information", but instead of looking at the interpretations you could just look at what it actually is. Entropy is just a way of expressing the number of states of a system. A system with many states has a high entropy, and a system with few states has a low entropy.

You, and the article you link to - states that the two images have the same entropy. This is not correct (for me).

The article correctly calculates the entropy is.

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

For the first image any pixel can have any gray value, $$p_k = \frac{1}{M} = 2^{-n}$$

Therefore the entropy is:

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

However, This is not the case for the second image.

The entropy can still be calculated as:

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

but you can not simple say $p_k = \frac{1}{M} = 2^{-n}$, because when you have found $p_1$ to be a value, you know that $p_2, p_3, p_4 \ldots p_{many}$ is the same value.

Therefore, the two images do not have the same entropy.

It might sound counter intuitive that entropy depends on how you look at the problem. However, you probably know it from compression. The maximum compression of a file is dictated by the Shannon's source coding theorem which sets an upper limit for how well a compression algorithm can compress a file. This limit depends on the entropy of the file. All modern compressors will compress a file close to this limit.

However, if you know the file is an audio file you can compress it using FLAC instead of some generic compressor. FLAC is lossless so all information is preserved. FLAC can not get around the Shannon's source coding theorem, that's math, but it can look at the file in a way which reduces the entropy of the file, thus do a better compression.

Identically, when I look at you second image I see that the pixels are sorted by gray value, and therefore it doesn't have the same entropy to me as the image with random noise.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the OP is aware if this - he is asking for probabilistic models that include spatial information $\endgroup$ – seanv507 Sep 16 '16 at 13:27
  • $\begingroup$ @seanv507 I re-read the question. I'm unsure if I agree with you or not. I believe OP is looking for something which doesn't exist. $\endgroup$ – bottiger Sep 16 '16 at 13:35
  • $\begingroup$ @bottiger, I thank you for your answer. I think we all agree that the 2 images should/do not have the same entropy. What I want to know, is a correct (conceptually/theoretically) way to calculate it. The simple formula given for $H$ doesn't seem to account for spatial information. So the question is about how to extend it correctly. I'll come back when I know more. $\endgroup$ – Davor Josipovic Sep 16 '16 at 17:40
  • $\begingroup$ @bottiger FLAC can't reduce the entropy of an audio file as that would by definition be lossy compression It's achieves compression by eliminating redundancy. $\endgroup$ – Paul Uszak Oct 16 '16 at 2:09
  • $\begingroup$ Maybe is correct to say that the classic entropy formula is correct only if the pixel values are stastically independent? $\endgroup$ – volperossa May 20 '18 at 23:58
2
$\begingroup$

Essentially the idea of entropy is something like "number of micro-states consistent with the macrostate".

I think the comment by sean507 and the answer by bottiger both point to a common framework. If you represent the image space by a generative model, $p[\,I,h\,]$, then for a given image $I$ you can (in principle) compute a posterior over the hidden states $p[\,h\mid I\,]$ (see also here). Then you can (in principle) compute the entropy of the posterior.

So I would agree that any "entropy", even in the "most theoretically correct sense", would seem to depend on both the representation used, and the generative model linking "microstates" ($h$) to "macrostates" ($I$).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

does NOT work in practice, for the simple reason that it's almost impossible to determine Pk. You think that you can do it, as you've done by considering the number of grey levels. Pk is not that. Pk is all possible combinations of grey levels. So you have to create a multi dimensional probability tree considering 1, 2, 3... combinations of pixels. If you read Shannon's work you see him do this calculation for plain English considering a tree depth of 3 letters. It then gets unwieldy without a computer.

You proved this yourself with statement 2. That's why your entropy calculation returns the same level of entropy for the two images, even though one is clearly less ordered than the other.

There is also no such concept of spacial distribution within entropy calculation. If there was, you'd also have to calculate entropy differently for temporally distributed samples. And what would you do for an 11 dimensional data array? For informational entropy; it is measured in bytes.

Just simply compress the images using a compression algorithm. It will output an estimate of the entropy in bytes. It will do this for any image or literally anything else that can be digitised, such as music or Shakespearean plays.

So. Your random image contains approximately 114 KBytes, and your ordered image contains approximately 2.2 KBytes. This is what you'd expect, but you already knew this kinda because you saw the image file sizes were of this size. I have reduced the compressed size by 33% to allow for future improvements in compression algorithms. I can't see them improving beyond this as the improvement curve is becoming asymptotic to a true underlying value.

P.S. For interest, Shakespeare only produced 1 MByte of entropy in his entire life's work, calculated by this technique. Most of it's quite good though.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.