Entropy estimation in bidimensional sequences

We investigate the performance of entropy estimation methods, based either on block entropies or compression approaches, in the case of bidimensional sequences. We introduce a validation data set made of images produced by a large number of different natural systems, in the vast majority characterized by long-range correlations, which produce a large spectrum of entropies. Results show that the framework based on lossless compressors applied to the one-dimensional projection of the considered data set leads to poor estimates. This is because higher dimensional correlations are lost in the projection operation. The adoption of compression methods which do not introduce dimensionality reduction improves the performance of this approach. By far, the best estimation of the asymptotic entropy is generated by the faster convergence of the traditional block-entropies method. As a by-product of our analysis, we show how a specific compressor method can be used as a potentially interesting technique for automatic detection of symmetries in textures and images.

Figure 1

Top: Some exemplar maps of urban sections in downtown areas. Bottom: The binary version of five different Brodatz textures.

Figure 2

Scattering plot of the entropies of the urban sections evaluated using the lossless compression algorithms vs the block-entropies algorithm. Each figure represents the entropy pairs obtained using a different compressor. Continuous lines represent the linear fitting of the points. In the inset, the histogram of the relative differences [Eq. (4)] between the two considered methods.

Figure 3

Scattering plot of the entropy of the Brodatz textures evaluated using the compression algorithms vs the block-entropies algorithm. Continuous lines represent the linear fitting of the points. In the inset, the histogram of the relative differences.

Figure 4

$\tilde{r}$ values displayed in dependence of the order of the block-entropies method used in the comparison with the compression method implemented by using the gzip (red points) and jpeg-ls algorithms (black points) for the urban sections (circles) and Brodatz's textures (squares).

Figure 5

Scattering plot of the entropies evaluated using the compression algorithm vs the block-entropies algorithm. Red points represent data of Brodatz's textures, and black points show those of the urban sections. The blue point is the result of a perfectly random image. In the inset is the histogram of the relative differences between the two considered methods. The dashed line is the $x=y$ equation. Top: The gzip compression algorithm is used. The continuous line is a guide for the eyes (generated by a fourth order polynomial fitting). Bottom: Results for the jpeg-ls compression algorithm.

Figure 6

Top: On the left, the relative difference between the entropy estimated from the original and rotated Brodatz's textures using the jpeg-ls compressor method. The textures with $|r_R|>0.2$ are indicated with their symbols. In the inset, the same data encompassing also the extreme statistics. On the right, eight textures presenting large differences. Bottom: Distribution of the $r_R$ values for the jpeg-ls compressor (on the left) and the block entropy method (on the right). The first distribution presents a standard deviation of 0.646 and the second one of only 0.028.

Figure 7

This figure represents the block of size 15 for estimating $H_{15}$. $X$ is the target cell and numbers indicate the scan order for general blocks up to order 15. These blocks have been clearly defined and described by Feldman et al. in Ref. [1].