Abstract

Natural scenes, like most all natural data sets, show considerable redundancy. Although many forms of redundancy have been investigated (e.g., pixel distributions, power spectra, contour relationships, etc.), estimates of the true entropy of natural scenes have been largely considered intractable. We describe a technique for estimating the entropy and relative dimensionality of image patches based on a function we call the proximity distribution (a nearest-neighbor technique). The advantage of this function over simple statistics such as the power spectrum is that the proximity distribution is dependent on all forms of redundancy. We demonstrate that this function can be used to estimate the entropy (redundancy) of 3×3 patches of known entropy as well as 8×8 patches of Gaussian white noise, natural scenes, and noise with the same power spectrum as natural scenes. The techniques are based on assumptions regarding the intrinsic dimensionality of the data, and although the estimates depend on an extrapolation model for images larger than 3×3, we argue that this approach provides the best current estimates of the entropy and compressibility of natural-scene patches and that it provides insights into the efficiency of any coding strategy that aims to reduce redundancy. We show that the sample of 8×8 patches of natural scenes used in this study has less than half the entropy of 8×8 white noise and less than 60% of the entropy of noise with the same power spectrum. In addition, given a finite number of samples (<220) drawn randomly from the space of 8×8 patches, the subspace of 8×8 natural-scene patches shows a dimensionality that depends on the sampling density and that for low densities is significantly lower dimensional than the space of 8×8 patches of white noise and noise with the same power spectrum.

© 2007 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. J. Field, "Relations between the statistics of natural images and the response properties of cortical cells," J. Opt. Soc. Am. A 4, 2379-2394 (1987).
    [CrossRef] [PubMed]
  2. J. J. Atick, "Could information theory provide an ecological theory of sensory processing?" Network 3, 213-251 (1992).
    [CrossRef]
  3. D. Kersten, "Predictability and redundancy of natural images," J. Opt. Soc. Am. A 4, 2395-2400 (1987).
    [CrossRef]
  4. O. Schwartz and E. P. Simoncelli, "Natural signal statistics and sensory gain control," Nat. Neurosci. 4, 819-825 (2001).
    [CrossRef]
  5. E. P. Simoncelli and B. A. Olshausen, "Natural image statistics and neural representation," Annu. Rev. Neurosci. 24, 1193-1216 (2001).
    [CrossRef]
  6. W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
    [CrossRef]
  7. D. J. Field, "Scale-invariance and self-similar 'Wavelet' transforms: an analysis of natural scenes and mammalian visual systems," in Wavelets, Fractals and Fourier Transforms: New Developments and New Applications (Oxford U. Press, 1993), pp. 151-193.
  8. Y. Petrov and L. Zhoaping, "Local correlations, information redundancy, and the sufficient pixel depth in natural images," J. Opt. Soc. Am. A 20, 56-66 (2003).
    [CrossRef]
  9. T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
    [CrossRef] [PubMed]
  10. B. A. Olshausen and D. J. Field, "Sparse coding with an overcomplete basis set: a strategy employed by V1?" Vision Res. 37, 3311-3325 (1996).
    [CrossRef]
  11. A. J. Bell and T. J. Sejnowski, "The independent components of natural scenes are edge filters," Vision Res. 37, 3327-3338 (1997).
    [CrossRef]
  12. W. B. Pennebaker and J. L. Mitchell, The JPEG Still Image Data Compression Standard (Van Nostrand Reinhold, 1993).
  13. International Organization for Standardization, "Information technology--JPEG 2000 image coding system: core coding system," Tech. Rep. ISO/IEC FDIS15444-1:2000 (International Organization for Standardization, 2000).
  14. N. G. Deriugin, "The power spectrum and the correlation function of the television signal," Telecommun. 1, 1-12 (1957).
  15. D. L. Ruderman and W. Bialek, "Statistics of natural images: scaling in the woods," Phys. Rev. Lett. 73, 814-817 (1994).
    [CrossRef] [PubMed]
  16. J. Minguillon and J. Pujol, "Uniform quantization error for Laplacian sources with applications to JPEG standard," in Mathematics of Data/Image Coding, Compression, and Encryption, M.S.Schmalz, ed., Proc. SPIE 3456, 77-88 (1998).
  17. M. Wainwright, E. P. Simoncelli, and A. Willsky, "Random cascades on wavelet trees and their use in modeling and analyzing natural imagery," Appl. Comput. Harmon. Anal. 11, 89-123 (2001).
    [CrossRef]
  18. L. F. Kozachenko and N. N. Leonenko, "A statistical estimate for the entropy of a random vector," Probl. Inf. Transm. 23, 9-16 (1987).
  19. J. D. Victor, "Binless strategies for estimation of information from neural data," Phys. Rev. E 66, 051903 (2002).
    [CrossRef]
  20. A. Kraskov, H. Stgbauer, and P. Grassberger, "Estimating mutual information," Phys. Rev. E 69, 066138 (2004).
    [CrossRef]
  21. C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 623-656 (1948).
  22. T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications (Wiley, 1991).
    [CrossRef]
  23. S. Verdu and T. Han, "The role of the asymptotic equipartition property in noiseless source coding," IEEE Trans. Inf. Theory 43, 847-857 (1997).
    [CrossRef]
  24. E. W. Weisstein, "Birthday problem," from MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/BirthdayProblem.html.
  25. I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck, "Entropy and information in neural spike trains: progress on the sampling problem," Phys. Rev. E 69, 056111 (2004).
    [CrossRef]
  26. Z. E. Schnabel, "The estimation of total fish population of a lake," Am. Math. Monthly 45, 348-352 (1938).
    [CrossRef]
  27. I. Nemenman, F. Shafee, and W. Bialek, "Entropy and inference, revisited," in Advances in Neural Information Processing Systems, Vol. 14, T.G.Dietterich, S.Becker, and Z.Ghahramani, eds. (MIT Press, 2002).
  28. J. Guckenheimer and G. Buzyna, "Dimension measurements for geostrophic turbulence," Phys. Rev. Lett. 51, 1438-1441 (1983).
    [CrossRef]
  29. R. Badii and A. Politi, "Statistical description of chaotic attractors: the dimension function," J. Stat. Phys. 40, 725-750 (1985).
    [CrossRef]
  30. P. Grassberger, "Generalizations of the Hausdorff dimension of fractal measures," Phys. Lett. A 107, 101-105 (1985).
    [CrossRef]
  31. K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
    [CrossRef] [PubMed]
  32. W. van de Water and P. Schram, "Generalized dimensions from near-neighbor information," Phys. Rev. A 37, 3118-3125 (1988).
    [CrossRef] [PubMed]
  33. J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science 290, 2319-2323 (2000).
    [CrossRef] [PubMed]
  34. S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science 290, 2323-2326 (2000).
    [CrossRef] [PubMed]
  35. J. Theiler, "Estimating fractal dimension," J. Opt. Soc. Am. A 7, 1055-1073 (1990).
    [CrossRef]
  36. K. L. Clarkson, "Nearest neighbor searching and metric space dimensions," in Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, G.Shakhnarovich, T.Darrell, and P.Indyk, eds. (MIT Press, 2006), Chap. 2, pp. 15-59.
  37. In this paper, we estimate differential entropy assuming that the original images are drawn from an underlying continuous distribution. Under high-rate quantization, the discrete entropy H is related to the differential entropy h by H?h+log?, where ? is the quantization step size (here ?=1, log?=0); see Refs. .
  38. J. H. van Hateren and A. van der Schaaf, "Independent component filters of natural images compared with simple cells in primary visual cortex," Proc. R. Soc. London, Ser. B 265, 359-366 (1998).
    [CrossRef]
  39. R. M. Gray and D. L. Neuhoff, "Quantization," IEEE Trans. Inf. Theory 44, 2325-2384 (1998).
    [CrossRef]
  40. see http://redwood.psych.cornell.edu/proximity/.
  41. J. Kybic, "High-dimensional mutual information estimation for image registration," in Proceedings of IEEE International Conference on Image Processing (IEEE, 2004), pp. 1779-1782.
  42. As long as the means are identical, the distance between two patches does not depend on the (common) mean of the underlying Gaussian from which the pixels are drawn.
  43. E. W. Weisstein, "Chi-squared distribution," from MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/Chi-SquaredDistribution.html.
  44. Although the pixel values of the spectrum-equalized noise patches were correlated (and were therefore statistically dependent), the real and imaginary components of the DFT coefficients of each block were independent. Accordingly, the entropy of the spectrum-equalized noise was computed by summing the individual entropies of the real and imaginary part of each DFT coefficient; the individual entropies were computed via Eq. (9).
  45. J. A. Nelder and R. Mead, "A simplex method for function minimization," J. Comput. 7, 308-313 (1965).
  46. D. J. Field, "What is the goal of sensory coding?" Neural Comput. 6, 559-601 (1994).
    [CrossRef]
  47. J. R. Parks, "Prediction and entropy of half-tone pictures," Behav. Sci. 10, 436-445 (1965).
    [CrossRef] [PubMed]
  48. N. S. Tzannes, R. V. Spencer, and A. Kaplan, "On estimating the entropy of random fields," Inf. Control. 16, 1-6 (1970).
    [CrossRef]
  49. A. B. Lee, K. S. Pedersen, and D. Mumford, "The nonlinear statistics of high-contrast patches in natural images," Int. J. Comput. Vis. 54, 83-103 (2003).
    [CrossRef]
  50. J. Costa and A. O. Hero, "Geodesic entropic graphs for dimension and entropy estimation in manifold learning," IEEE Trans. Signal Process. 52, 2210-2221 (2004).
    [CrossRef]
  51. B. V. Dasarathy, Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques (IEEE, 1973).
  52. G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (MIT Press, 2006).

2006 (2)

K. L. Clarkson, "Nearest neighbor searching and metric space dimensions," in Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, G.Shakhnarovich, T.Darrell, and P.Indyk, eds. (MIT Press, 2006), Chap. 2, pp. 15-59.

G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (MIT Press, 2006).

2004 (4)

J. Costa and A. O. Hero, "Geodesic entropic graphs for dimension and entropy estimation in manifold learning," IEEE Trans. Signal Process. 52, 2210-2221 (2004).
[CrossRef]

J. Kybic, "High-dimensional mutual information estimation for image registration," in Proceedings of IEEE International Conference on Image Processing (IEEE, 2004), pp. 1779-1782.

A. Kraskov, H. Stgbauer, and P. Grassberger, "Estimating mutual information," Phys. Rev. E 69, 066138 (2004).
[CrossRef]

I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck, "Entropy and information in neural spike trains: progress on the sampling problem," Phys. Rev. E 69, 056111 (2004).
[CrossRef]

2003 (2)

A. B. Lee, K. S. Pedersen, and D. Mumford, "The nonlinear statistics of high-contrast patches in natural images," Int. J. Comput. Vis. 54, 83-103 (2003).
[CrossRef]

Y. Petrov and L. Zhoaping, "Local correlations, information redundancy, and the sufficient pixel depth in natural images," J. Opt. Soc. Am. A 20, 56-66 (2003).
[CrossRef]

2002 (2)

I. Nemenman, F. Shafee, and W. Bialek, "Entropy and inference, revisited," in Advances in Neural Information Processing Systems, Vol. 14, T.G.Dietterich, S.Becker, and Z.Ghahramani, eds. (MIT Press, 2002).

J. D. Victor, "Binless strategies for estimation of information from neural data," Phys. Rev. E 66, 051903 (2002).
[CrossRef]

2001 (4)

M. Wainwright, E. P. Simoncelli, and A. Willsky, "Random cascades on wavelet trees and their use in modeling and analyzing natural imagery," Appl. Comput. Harmon. Anal. 11, 89-123 (2001).
[CrossRef]

O. Schwartz and E. P. Simoncelli, "Natural signal statistics and sensory gain control," Nat. Neurosci. 4, 819-825 (2001).
[CrossRef]

E. P. Simoncelli and B. A. Olshausen, "Natural image statistics and neural representation," Annu. Rev. Neurosci. 24, 1193-1216 (2001).
[CrossRef]

W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
[CrossRef]

2000 (3)

International Organization for Standardization, "Information technology--JPEG 2000 image coding system: core coding system," Tech. Rep. ISO/IEC FDIS15444-1:2000 (International Organization for Standardization, 2000).

J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science 290, 2319-2323 (2000).
[CrossRef] [PubMed]

S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science 290, 2323-2326 (2000).
[CrossRef] [PubMed]

1998 (4)

J. H. van Hateren and A. van der Schaaf, "Independent component filters of natural images compared with simple cells in primary visual cortex," Proc. R. Soc. London, Ser. B 265, 359-366 (1998).
[CrossRef]

R. M. Gray and D. L. Neuhoff, "Quantization," IEEE Trans. Inf. Theory 44, 2325-2384 (1998).
[CrossRef]

J. Minguillon and J. Pujol, "Uniform quantization error for Laplacian sources with applications to JPEG standard," in Mathematics of Data/Image Coding, Compression, and Encryption, M.S.Schmalz, ed., Proc. SPIE 3456, 77-88 (1998).

T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
[CrossRef] [PubMed]

1997 (2)

A. J. Bell and T. J. Sejnowski, "The independent components of natural scenes are edge filters," Vision Res. 37, 3327-3338 (1997).
[CrossRef]

S. Verdu and T. Han, "The role of the asymptotic equipartition property in noiseless source coding," IEEE Trans. Inf. Theory 43, 847-857 (1997).
[CrossRef]

1996 (1)

B. A. Olshausen and D. J. Field, "Sparse coding with an overcomplete basis set: a strategy employed by V1?" Vision Res. 37, 3311-3325 (1996).
[CrossRef]

1994 (2)

D. L. Ruderman and W. Bialek, "Statistics of natural images: scaling in the woods," Phys. Rev. Lett. 73, 814-817 (1994).
[CrossRef] [PubMed]

D. J. Field, "What is the goal of sensory coding?" Neural Comput. 6, 559-601 (1994).
[CrossRef]

1993 (2)

W. B. Pennebaker and J. L. Mitchell, The JPEG Still Image Data Compression Standard (Van Nostrand Reinhold, 1993).

D. J. Field, "Scale-invariance and self-similar 'Wavelet' transforms: an analysis of natural scenes and mammalian visual systems," in Wavelets, Fractals and Fourier Transforms: New Developments and New Applications (Oxford U. Press, 1993), pp. 151-193.

1992 (1)

J. J. Atick, "Could information theory provide an ecological theory of sensory processing?" Network 3, 213-251 (1992).
[CrossRef]

1991 (1)

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications (Wiley, 1991).
[CrossRef]

1990 (1)

1988 (1)

W. van de Water and P. Schram, "Generalized dimensions from near-neighbor information," Phys. Rev. A 37, 3118-3125 (1988).
[CrossRef] [PubMed]

1987 (3)

1985 (2)

R. Badii and A. Politi, "Statistical description of chaotic attractors: the dimension function," J. Stat. Phys. 40, 725-750 (1985).
[CrossRef]

P. Grassberger, "Generalizations of the Hausdorff dimension of fractal measures," Phys. Lett. A 107, 101-105 (1985).
[CrossRef]

1983 (1)

J. Guckenheimer and G. Buzyna, "Dimension measurements for geostrophic turbulence," Phys. Rev. Lett. 51, 1438-1441 (1983).
[CrossRef]

1979 (1)

K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
[CrossRef] [PubMed]

1973 (1)

B. V. Dasarathy, Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques (IEEE, 1973).

1970 (1)

N. S. Tzannes, R. V. Spencer, and A. Kaplan, "On estimating the entropy of random fields," Inf. Control. 16, 1-6 (1970).
[CrossRef]

1965 (2)

J. R. Parks, "Prediction and entropy of half-tone pictures," Behav. Sci. 10, 436-445 (1965).
[CrossRef] [PubMed]

J. A. Nelder and R. Mead, "A simplex method for function minimization," J. Comput. 7, 308-313 (1965).

1957 (1)

N. G. Deriugin, "The power spectrum and the correlation function of the television signal," Telecommun. 1, 1-12 (1957).

1948 (1)

C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 623-656 (1948).

1938 (1)

Z. E. Schnabel, "The estimation of total fish population of a lake," Am. Math. Monthly 45, 348-352 (1938).
[CrossRef]

Atick, J. J.

J. J. Atick, "Could information theory provide an ecological theory of sensory processing?" Network 3, 213-251 (1992).
[CrossRef]

Badii, R.

R. Badii and A. Politi, "Statistical description of chaotic attractors: the dimension function," J. Stat. Phys. 40, 725-750 (1985).
[CrossRef]

Bailey, T.

K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
[CrossRef] [PubMed]

Bell, A. J.

A. J. Bell and T. J. Sejnowski, "The independent components of natural scenes are edge filters," Vision Res. 37, 3327-3338 (1997).
[CrossRef]

Bialek, W.

I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck, "Entropy and information in neural spike trains: progress on the sampling problem," Phys. Rev. E 69, 056111 (2004).
[CrossRef]

I. Nemenman, F. Shafee, and W. Bialek, "Entropy and inference, revisited," in Advances in Neural Information Processing Systems, Vol. 14, T.G.Dietterich, S.Becker, and Z.Ghahramani, eds. (MIT Press, 2002).

D. L. Ruderman and W. Bialek, "Statistics of natural images: scaling in the woods," Phys. Rev. Lett. 73, 814-817 (1994).
[CrossRef] [PubMed]

Buzyna, G.

J. Guckenheimer and G. Buzyna, "Dimension measurements for geostrophic turbulence," Phys. Rev. Lett. 51, 1438-1441 (1983).
[CrossRef]

Clarkson, K. L.

K. L. Clarkson, "Nearest neighbor searching and metric space dimensions," in Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, G.Shakhnarovich, T.Darrell, and P.Indyk, eds. (MIT Press, 2006), Chap. 2, pp. 15-59.

Costa, J.

J. Costa and A. O. Hero, "Geodesic entropic graphs for dimension and entropy estimation in manifold learning," IEEE Trans. Signal Process. 52, 2210-2221 (2004).
[CrossRef]

Cover, T. M.

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications (Wiley, 1991).
[CrossRef]

Darrell, T.

G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (MIT Press, 2006).

Dasarathy, B. V.

B. V. Dasarathy, Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques (IEEE, 1973).

de Ruyter van Steveninck, R.

I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck, "Entropy and information in neural spike trains: progress on the sampling problem," Phys. Rev. E 69, 056111 (2004).
[CrossRef]

de Silva, V.

J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science 290, 2319-2323 (2000).
[CrossRef] [PubMed]

Deriugin, N. G.

N. G. Deriugin, "The power spectrum and the correlation function of the television signal," Telecommun. 1, 1-12 (1957).

Dubes, R.

K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
[CrossRef] [PubMed]

Field, D. J.

B. A. Olshausen and D. J. Field, "Sparse coding with an overcomplete basis set: a strategy employed by V1?" Vision Res. 37, 3311-3325 (1996).
[CrossRef]

D. J. Field, "What is the goal of sensory coding?" Neural Comput. 6, 559-601 (1994).
[CrossRef]

D. J. Field, "Scale-invariance and self-similar 'Wavelet' transforms: an analysis of natural scenes and mammalian visual systems," in Wavelets, Fractals and Fourier Transforms: New Developments and New Applications (Oxford U. Press, 1993), pp. 151-193.

D. J. Field, "Relations between the statistics of natural images and the response properties of cortical cells," J. Opt. Soc. Am. A 4, 2379-2394 (1987).
[CrossRef] [PubMed]

Gallogly, D. P.

W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
[CrossRef]

Geisler, W. S.

W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
[CrossRef]

Grassberger, P.

A. Kraskov, H. Stgbauer, and P. Grassberger, "Estimating mutual information," Phys. Rev. E 69, 066138 (2004).
[CrossRef]

P. Grassberger, "Generalizations of the Hausdorff dimension of fractal measures," Phys. Lett. A 107, 101-105 (1985).
[CrossRef]

Gray, R. M.

R. M. Gray and D. L. Neuhoff, "Quantization," IEEE Trans. Inf. Theory 44, 2325-2384 (1998).
[CrossRef]

Guckenheimer, J.

J. Guckenheimer and G. Buzyna, "Dimension measurements for geostrophic turbulence," Phys. Rev. Lett. 51, 1438-1441 (1983).
[CrossRef]

Han, T.

S. Verdu and T. Han, "The role of the asymptotic equipartition property in noiseless source coding," IEEE Trans. Inf. Theory 43, 847-857 (1997).
[CrossRef]

Hero, A. O.

J. Costa and A. O. Hero, "Geodesic entropic graphs for dimension and entropy estimation in manifold learning," IEEE Trans. Signal Process. 52, 2210-2221 (2004).
[CrossRef]

Indyk, P.

G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (MIT Press, 2006).

Jain, A. K.

K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
[CrossRef] [PubMed]

Kaplan, A.

N. S. Tzannes, R. V. Spencer, and A. Kaplan, "On estimating the entropy of random fields," Inf. Control. 16, 1-6 (1970).
[CrossRef]

Kersten, D.

Kozachenko, L. F.

L. F. Kozachenko and N. N. Leonenko, "A statistical estimate for the entropy of a random vector," Probl. Inf. Transm. 23, 9-16 (1987).

Kraskov, A.

A. Kraskov, H. Stgbauer, and P. Grassberger, "Estimating mutual information," Phys. Rev. E 69, 066138 (2004).
[CrossRef]

Kybic, J.

J. Kybic, "High-dimensional mutual information estimation for image registration," in Proceedings of IEEE International Conference on Image Processing (IEEE, 2004), pp. 1779-1782.

Lamme, V. A. F.

T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
[CrossRef] [PubMed]

Langford, J. C.

J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science 290, 2319-2323 (2000).
[CrossRef] [PubMed]

Lee, A. B.

A. B. Lee, K. S. Pedersen, and D. Mumford, "The nonlinear statistics of high-contrast patches in natural images," Int. J. Comput. Vis. 54, 83-103 (2003).
[CrossRef]

Lee, T. S.

T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
[CrossRef] [PubMed]

Leonenko, N. N.

L. F. Kozachenko and N. N. Leonenko, "A statistical estimate for the entropy of a random vector," Probl. Inf. Transm. 23, 9-16 (1987).

Mead, R.

J. A. Nelder and R. Mead, "A simplex method for function minimization," J. Comput. 7, 308-313 (1965).

Minguillon, J.

J. Minguillon and J. Pujol, "Uniform quantization error for Laplacian sources with applications to JPEG standard," in Mathematics of Data/Image Coding, Compression, and Encryption, M.S.Schmalz, ed., Proc. SPIE 3456, 77-88 (1998).

Mitchell, J. L.

W. B. Pennebaker and J. L. Mitchell, The JPEG Still Image Data Compression Standard (Van Nostrand Reinhold, 1993).

Mumford, D.

A. B. Lee, K. S. Pedersen, and D. Mumford, "The nonlinear statistics of high-contrast patches in natural images," Int. J. Comput. Vis. 54, 83-103 (2003).
[CrossRef]

T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
[CrossRef] [PubMed]

Nelder, J. A.

J. A. Nelder and R. Mead, "A simplex method for function minimization," J. Comput. 7, 308-313 (1965).

Nemenman, I.

I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck, "Entropy and information in neural spike trains: progress on the sampling problem," Phys. Rev. E 69, 056111 (2004).
[CrossRef]

I. Nemenman, F. Shafee, and W. Bialek, "Entropy and inference, revisited," in Advances in Neural Information Processing Systems, Vol. 14, T.G.Dietterich, S.Becker, and Z.Ghahramani, eds. (MIT Press, 2002).

Neuhoff, D. L.

R. M. Gray and D. L. Neuhoff, "Quantization," IEEE Trans. Inf. Theory 44, 2325-2384 (1998).
[CrossRef]

Olshausen, B. A.

E. P. Simoncelli and B. A. Olshausen, "Natural image statistics and neural representation," Annu. Rev. Neurosci. 24, 1193-1216 (2001).
[CrossRef]

B. A. Olshausen and D. J. Field, "Sparse coding with an overcomplete basis set: a strategy employed by V1?" Vision Res. 37, 3311-3325 (1996).
[CrossRef]

Parks, J. R.

J. R. Parks, "Prediction and entropy of half-tone pictures," Behav. Sci. 10, 436-445 (1965).
[CrossRef] [PubMed]

Pedersen, K. S.

A. B. Lee, K. S. Pedersen, and D. Mumford, "The nonlinear statistics of high-contrast patches in natural images," Int. J. Comput. Vis. 54, 83-103 (2003).
[CrossRef]

Pennebaker, W. B.

W. B. Pennebaker and J. L. Mitchell, The JPEG Still Image Data Compression Standard (Van Nostrand Reinhold, 1993).

Perry, J. S.

W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
[CrossRef]

Petrov, Y.

Pettis, K.

K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
[CrossRef] [PubMed]

Politi, A.

R. Badii and A. Politi, "Statistical description of chaotic attractors: the dimension function," J. Stat. Phys. 40, 725-750 (1985).
[CrossRef]

Pujol, J.

J. Minguillon and J. Pujol, "Uniform quantization error for Laplacian sources with applications to JPEG standard," in Mathematics of Data/Image Coding, Compression, and Encryption, M.S.Schmalz, ed., Proc. SPIE 3456, 77-88 (1998).

Romero, R.

T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
[CrossRef] [PubMed]

Roweis, S. T.

S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science 290, 2323-2326 (2000).
[CrossRef] [PubMed]

Ruderman, D. L.

D. L. Ruderman and W. Bialek, "Statistics of natural images: scaling in the woods," Phys. Rev. Lett. 73, 814-817 (1994).
[CrossRef] [PubMed]

Saul, L. K.

S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science 290, 2323-2326 (2000).
[CrossRef] [PubMed]

Schnabel, Z. E.

Z. E. Schnabel, "The estimation of total fish population of a lake," Am. Math. Monthly 45, 348-352 (1938).
[CrossRef]

Schram, P.

W. van de Water and P. Schram, "Generalized dimensions from near-neighbor information," Phys. Rev. A 37, 3118-3125 (1988).
[CrossRef] [PubMed]

Schwartz, O.

O. Schwartz and E. P. Simoncelli, "Natural signal statistics and sensory gain control," Nat. Neurosci. 4, 819-825 (2001).
[CrossRef]

Sejnowski, T. J.

A. J. Bell and T. J. Sejnowski, "The independent components of natural scenes are edge filters," Vision Res. 37, 3327-3338 (1997).
[CrossRef]

Shafee, F.

I. Nemenman, F. Shafee, and W. Bialek, "Entropy and inference, revisited," in Advances in Neural Information Processing Systems, Vol. 14, T.G.Dietterich, S.Becker, and Z.Ghahramani, eds. (MIT Press, 2002).

Shakhnarovich, G.

G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (MIT Press, 2006).

Shannon, C. E.

C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 623-656 (1948).

Simoncelli, E. P.

E. P. Simoncelli and B. A. Olshausen, "Natural image statistics and neural representation," Annu. Rev. Neurosci. 24, 1193-1216 (2001).
[CrossRef]

O. Schwartz and E. P. Simoncelli, "Natural signal statistics and sensory gain control," Nat. Neurosci. 4, 819-825 (2001).
[CrossRef]

M. Wainwright, E. P. Simoncelli, and A. Willsky, "Random cascades on wavelet trees and their use in modeling and analyzing natural imagery," Appl. Comput. Harmon. Anal. 11, 89-123 (2001).
[CrossRef]

Spencer, R. V.

N. S. Tzannes, R. V. Spencer, and A. Kaplan, "On estimating the entropy of random fields," Inf. Control. 16, 1-6 (1970).
[CrossRef]

Stgbauer, H.

A. Kraskov, H. Stgbauer, and P. Grassberger, "Estimating mutual information," Phys. Rev. E 69, 066138 (2004).
[CrossRef]

Super, B. J.

W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
[CrossRef]

Tenenbaum, J. B.

J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science 290, 2319-2323 (2000).
[CrossRef] [PubMed]

Theiler, J.

Thomas, J. A.

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications (Wiley, 1991).
[CrossRef]

Tzannes, N. S.

N. S. Tzannes, R. V. Spencer, and A. Kaplan, "On estimating the entropy of random fields," Inf. Control. 16, 1-6 (1970).
[CrossRef]

van de Water, W.

W. van de Water and P. Schram, "Generalized dimensions from near-neighbor information," Phys. Rev. A 37, 3118-3125 (1988).
[CrossRef] [PubMed]

van der Schaaf, A.

J. H. van Hateren and A. van der Schaaf, "Independent component filters of natural images compared with simple cells in primary visual cortex," Proc. R. Soc. London, Ser. B 265, 359-366 (1998).
[CrossRef]

van Hateren, J. H.

J. H. van Hateren and A. van der Schaaf, "Independent component filters of natural images compared with simple cells in primary visual cortex," Proc. R. Soc. London, Ser. B 265, 359-366 (1998).
[CrossRef]

Verdu, S.

S. Verdu and T. Han, "The role of the asymptotic equipartition property in noiseless source coding," IEEE Trans. Inf. Theory 43, 847-857 (1997).
[CrossRef]

Victor, J. D.

J. D. Victor, "Binless strategies for estimation of information from neural data," Phys. Rev. E 66, 051903 (2002).
[CrossRef]

Wainwright, M.

M. Wainwright, E. P. Simoncelli, and A. Willsky, "Random cascades on wavelet trees and their use in modeling and analyzing natural imagery," Appl. Comput. Harmon. Anal. 11, 89-123 (2001).
[CrossRef]

Weisstein, E. W.

E. W. Weisstein, "Chi-squared distribution," from MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/Chi-SquaredDistribution.html.

E. W. Weisstein, "Birthday problem," from MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/BirthdayProblem.html.

Willsky, A.

M. Wainwright, E. P. Simoncelli, and A. Willsky, "Random cascades on wavelet trees and their use in modeling and analyzing natural imagery," Appl. Comput. Harmon. Anal. 11, 89-123 (2001).
[CrossRef]

Zhoaping, L.

Am. Math. Monthly (1)

Z. E. Schnabel, "The estimation of total fish population of a lake," Am. Math. Monthly 45, 348-352 (1938).
[CrossRef]

Annu. Rev. Neurosci. (1)

E. P. Simoncelli and B. A. Olshausen, "Natural image statistics and neural representation," Annu. Rev. Neurosci. 24, 1193-1216 (2001).
[CrossRef]

Appl. Comput. Harmon. Anal. (1)

M. Wainwright, E. P. Simoncelli, and A. Willsky, "Random cascades on wavelet trees and their use in modeling and analyzing natural imagery," Appl. Comput. Harmon. Anal. 11, 89-123 (2001).
[CrossRef]

Behav. Sci. (1)

J. R. Parks, "Prediction and entropy of half-tone pictures," Behav. Sci. 10, 436-445 (1965).
[CrossRef] [PubMed]

Bell Syst. Tech. J. (1)

C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J. 27, 623-656 (1948).

IEEE Trans. Inf. Theory (2)

S. Verdu and T. Han, "The role of the asymptotic equipartition property in noiseless source coding," IEEE Trans. Inf. Theory 43, 847-857 (1997).
[CrossRef]

R. M. Gray and D. L. Neuhoff, "Quantization," IEEE Trans. Inf. Theory 44, 2325-2384 (1998).
[CrossRef]

IEEE Trans. Pattern Anal. Mach. Intell. (1)

K. Pettis, T. Bailey, A. K. Jain, and R. Dubes, "An intrinsic dimensionality estimator from near-neighbor information," IEEE Trans. Pattern Anal. Mach. Intell. 1, 25-36 (1979).
[CrossRef] [PubMed]

IEEE Trans. Signal Process. (1)

J. Costa and A. O. Hero, "Geodesic entropic graphs for dimension and entropy estimation in manifold learning," IEEE Trans. Signal Process. 52, 2210-2221 (2004).
[CrossRef]

Inf. Control. (1)

N. S. Tzannes, R. V. Spencer, and A. Kaplan, "On estimating the entropy of random fields," Inf. Control. 16, 1-6 (1970).
[CrossRef]

Int. J. Comput. Vis. (1)

A. B. Lee, K. S. Pedersen, and D. Mumford, "The nonlinear statistics of high-contrast patches in natural images," Int. J. Comput. Vis. 54, 83-103 (2003).
[CrossRef]

J. Comput. (1)

J. A. Nelder and R. Mead, "A simplex method for function minimization," J. Comput. 7, 308-313 (1965).

J. Opt. Soc. Am. A (4)

J. Stat. Phys. (1)

R. Badii and A. Politi, "Statistical description of chaotic attractors: the dimension function," J. Stat. Phys. 40, 725-750 (1985).
[CrossRef]

Nat. Neurosci. (1)

O. Schwartz and E. P. Simoncelli, "Natural signal statistics and sensory gain control," Nat. Neurosci. 4, 819-825 (2001).
[CrossRef]

Network (1)

J. J. Atick, "Could information theory provide an ecological theory of sensory processing?" Network 3, 213-251 (1992).
[CrossRef]

Neural Comput. (1)

D. J. Field, "What is the goal of sensory coding?" Neural Comput. 6, 559-601 (1994).
[CrossRef]

Phys. Lett. A (1)

P. Grassberger, "Generalizations of the Hausdorff dimension of fractal measures," Phys. Lett. A 107, 101-105 (1985).
[CrossRef]

Phys. Rev. A (1)

W. van de Water and P. Schram, "Generalized dimensions from near-neighbor information," Phys. Rev. A 37, 3118-3125 (1988).
[CrossRef] [PubMed]

Phys. Rev. E (3)

I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck, "Entropy and information in neural spike trains: progress on the sampling problem," Phys. Rev. E 69, 056111 (2004).
[CrossRef]

J. D. Victor, "Binless strategies for estimation of information from neural data," Phys. Rev. E 66, 051903 (2002).
[CrossRef]

A. Kraskov, H. Stgbauer, and P. Grassberger, "Estimating mutual information," Phys. Rev. E 69, 066138 (2004).
[CrossRef]

Phys. Rev. Lett. (2)

D. L. Ruderman and W. Bialek, "Statistics of natural images: scaling in the woods," Phys. Rev. Lett. 73, 814-817 (1994).
[CrossRef] [PubMed]

J. Guckenheimer and G. Buzyna, "Dimension measurements for geostrophic turbulence," Phys. Rev. Lett. 51, 1438-1441 (1983).
[CrossRef]

Probl. Inf. Transm. (1)

L. F. Kozachenko and N. N. Leonenko, "A statistical estimate for the entropy of a random vector," Probl. Inf. Transm. 23, 9-16 (1987).

Proc. R. Soc. London, Ser. B (1)

J. H. van Hateren and A. van der Schaaf, "Independent component filters of natural images compared with simple cells in primary visual cortex," Proc. R. Soc. London, Ser. B 265, 359-366 (1998).
[CrossRef]

Science (2)

J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science 290, 2319-2323 (2000).
[CrossRef] [PubMed]

S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science 290, 2323-2326 (2000).
[CrossRef] [PubMed]

Telecommun. (1)

N. G. Deriugin, "The power spectrum and the correlation function of the television signal," Telecommun. 1, 1-12 (1957).

Vision Res. (4)

T. S. Lee, D. Mumford, R. Romero, and V. A. F. Lamme, "The role of the primary visual cortex in higher level vision," Vision Res. 38, 2429-2454 (1998).
[CrossRef] [PubMed]

B. A. Olshausen and D. J. Field, "Sparse coding with an overcomplete basis set: a strategy employed by V1?" Vision Res. 37, 3311-3325 (1996).
[CrossRef]

A. J. Bell and T. J. Sejnowski, "The independent components of natural scenes are edge filters," Vision Res. 37, 3327-3338 (1997).
[CrossRef]

W. S. Geisler, J. S. Perry, B. J. Super, and D. P. Gallogly, "Edge co-occurence in natural images predicts contour grouping performance," Vision Res. 41, 711-724 (2001).
[CrossRef]

Other (16)

D. J. Field, "Scale-invariance and self-similar 'Wavelet' transforms: an analysis of natural scenes and mammalian visual systems," in Wavelets, Fractals and Fourier Transforms: New Developments and New Applications (Oxford U. Press, 1993), pp. 151-193.

B. V. Dasarathy, Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques (IEEE, 1973).

G. Shakhnarovich, T. Darrell, and P. Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (MIT Press, 2006).

W. B. Pennebaker and J. L. Mitchell, The JPEG Still Image Data Compression Standard (Van Nostrand Reinhold, 1993).

International Organization for Standardization, "Information technology--JPEG 2000 image coding system: core coding system," Tech. Rep. ISO/IEC FDIS15444-1:2000 (International Organization for Standardization, 2000).

J. Minguillon and J. Pujol, "Uniform quantization error for Laplacian sources with applications to JPEG standard," in Mathematics of Data/Image Coding, Compression, and Encryption, M.S.Schmalz, ed., Proc. SPIE 3456, 77-88 (1998).

E. W. Weisstein, "Birthday problem," from MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/BirthdayProblem.html.

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications (Wiley, 1991).
[CrossRef]

K. L. Clarkson, "Nearest neighbor searching and metric space dimensions," in Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, G.Shakhnarovich, T.Darrell, and P.Indyk, eds. (MIT Press, 2006), Chap. 2, pp. 15-59.

In this paper, we estimate differential entropy assuming that the original images are drawn from an underlying continuous distribution. Under high-rate quantization, the discrete entropy H is related to the differential entropy h by H?h+log?, where ? is the quantization step size (here ?=1, log?=0); see Refs. .

I. Nemenman, F. Shafee, and W. Bialek, "Entropy and inference, revisited," in Advances in Neural Information Processing Systems, Vol. 14, T.G.Dietterich, S.Becker, and Z.Ghahramani, eds. (MIT Press, 2002).

see http://redwood.psych.cornell.edu/proximity/.

J. Kybic, "High-dimensional mutual information estimation for image registration," in Proceedings of IEEE International Conference on Image Processing (IEEE, 2004), pp. 1779-1782.

As long as the means are identical, the distance between two patches does not depend on the (common) mean of the underlying Gaussian from which the pixels are drawn.

E. W. Weisstein, "Chi-squared distribution," from MathWorld--A Wolfram Web Resource, http://mathworld.wolfram.com/Chi-SquaredDistribution.html.

Although the pixel values of the spectrum-equalized noise patches were correlated (and were therefore statistically dependent), the real and imaginary components of the DFT coefficients of each block were independent. Accordingly, the entropy of the spectrum-equalized noise was computed by summing the individual entropies of the real and imaginary part of each DFT coefficient; the individual entropies were computed via Eq. (9).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (20)

Fig. 1
Fig. 1

Diagram of the procedure used in the experiments. Images from a given class were randomly divided into two groups: Group T containing the to-be-matched “target” samples, and group N containing the samples from the population. Patches of size r × r pixels were then extracted from the images in a nonoverlapping fashion. For each target patch in group T , an exhaustive, brute-force search procedure was performed to find the patch in group N with the minimum Euclidean distance to the target patch (minimum L 2 -norm of the difference). The average log nearest-neighbor distance was then estimated by computing the sample mean of the minimum Euclidean distances over all target patches; this process was then repeated for increasing numbers of samples to compute the average log nearest-neighbor distance as a function of the number of samples (the proximity distribution). See Figs. 5, 6, 9, 10 later in this paper for examples of proximity distribution functions.

Fig. 2
Fig. 2

(a) Swiss roll data to which Gaussian white noise has been added (here, showing 3200 samples), (b) eight random samples of the noisy Swiss roll data; here, there are too few samples to discern any particular geometry ( RD = 3 ) , (c) 80 random samples of the noisy Swiss roll data; here, there are enough samples to begin to see a two-dimensional Swiss roll manifold ( RD = 2 ) , (d) 800 random samples of the noisy Swiss roll data; here, there are enough samples to see that the roll actually has a thickness ( RD = 3 ) .

Fig. 3
Fig. 3

(a) Unrolled version of the noisy Swiss roll data in Fig. 2. (b) Eight random samples of the unrolled data; here, there are too few samples to clearly expose the third dimension ( RD = 2 ) ; (c) 80 random samples of the unrolled data; here, there are still too few samples to clearly expose the third dimension ( RD = 2 ) ; (d) 800 random samples of the unrolled data; here, there are enough samples to see that the plane has a thickness ( RD = 3 ) .

Fig. 4
Fig. 4

Example stimuli used in the experiments ( R × R = 1024 × 1024 ) : (a) Gaussian white noise; (b) 1 f noise; (c) 1 f 2 noise; (d) spectrum-equalized noise with r × r = 8 × 8 ; (e) natural scene cropped from image i m k 04103 of the van Hateren database [note that to promote visibility, the intensities of these images have been adjusted and (d) depicts only the top-left 256 × 256 section].

Fig. 5
Fig. 5

Proximity distribution functions for iid Gaussian data computed via Eq. (10) (solid curves) and measured experimentally (circles). In each graph, the horizontal axis denotes the number of samples N; the vertical axis denotes the corresponding E { log 2 D N * } computed via Eq. (10). (a) Proximity distribution functions for a fixed dimensionality ( k = 64 ) and various values of standard deviation σ; (b) proximity distribution functions for a fixed standard deviation ( σ = 0.77 ) and various values of dimensionality k.

Fig. 6
Fig. 6

Proximity distribution functions for 3 × 3 patches of Gaussian white noise, spectrum-equalized noise, and natural scenes. The horizontal axis denotes the number of samples N; the vertical axis denotes the corresponding E { log 2 D N * } estimated via a sample mean over all target patches. Black circles, Gaussian white noise; light-gray circles, spectrum-equalized noise; stars, natural scenes. The solid lines represent a slope of 1 9 th ; notice that all three curves eventually converge on this slope.

Fig. 7
Fig. 7

RD curves for 3 × 3 patches of Gaussian white noise, spectrum-equalized noise, and natural scenes. The horizontal axis denotes the number of samples N; the vertical axis denotes the corresponding RD. Black circles, Gaussian white noise; light-gray circles, spectrum-equalized noise; stars, natural scenes. The solid gray line denotes the intrinsic dimensionality of k = 9 for all three data sets (the natural scenes possess an intrinsic dimensionality of k = 9 owing to photon noise).

Fig. 8
Fig. 8

Entropy estimates for 3 × 3 patches of Gaussian white noise, spectrum-equalized noise, and natural scenes. The horizontal axis denotes the number of samples N; the vertical axis denotes the entropy computed via Eq. (8) using the corresponding value of N. Black circles, Gaussian white noise ( 7.0   bits pixel ) ; light-gray circles, spectrum-equalized noise ( 5.5   bits pixel ) ; stars, natural scenes ( 3.9   bits pixel ) . The solid gray lines indicate the actual entropies of Gaussian white noise and spectrum-equalized noise (7.0 and 5.5   bits pixel , respectively) as computed via Eq. (9); the dashed line denotes the entropy estimate of 3.9   bits pixel for natural scenes.

Fig. 9
Fig. 9

(a) Proximity distribution and (b) RD curves for 8 × 8 patches. In both graphs, the horizontal axis denotes the number of samples N. The vertical axis in (a) denotes the corresponding E { log 2 D N * } estimated via a sample mean over all target patches; the vertical axis in (b) denotes the corresponding RD. Black circles, Gaussian white noise; gray circles, 1 f noise; light-gray circles, spectrum-equalized noise; white circles, 1 f 2 noise; stars, natural scenes. The solid gray line in (b) denotes the intrinsic dimensionality of k = 64 for all data sets.

Fig. 10
Fig. 10

(a) Proximity distribution and (b) RD curves for mean-and contrast-normalized 8 × 8 patches. The horizontal axis in both graphs denotes the number of samples N. The vertical axis in (a) denotes the corresponding E { log 2 D N * } estimated via a sample mean over all target patches; the vertical axis in (b) denotes the corresponding RD. Black circles, Gaussian white noise; gray circles, 1 f noise; light-gray circles, spectrum-equalized noise; white circles, 1 f 2 noise; stars, natural scenes. The solid gray line in (b) denotes the intrinsic dimensionality of k = 62 for all data sets.

Fig. 11
Fig. 11

(a) Proximity distribution and (b) RD curves for mean- and contrast-normalized 8 × 8 patches of whitened natural scenes and of Gaussian white noise, spectrum-equalized noise, and natural scenes (replotted from Fig. 10). In both graphs, the horizontal axis denotes the number of samples N; the vertical axis in (a) denotes the corresponding E { log 2 D N * } estimated via a sample mean over all target patches; and the vertical axis in (b) denotes the corresponding RD. Black circles, Gaussian white noise; light-gray circles, 1 f noise; black stars, natural scenes; white stars, whitened natural scenes. The solid gray line in (b) denotes the intrinsic dimensionality of k = 62 for all data sets.

Fig. 12
Fig. 12

RD curves for 8 × 8 Gaussian white noise (black curve), spectrum-equalized noise (light-gray circles), and natural scenes (stars). The RD curve for the Gaussian white noise was computed at values of N [ 1 , 2 50 ] via Eq. (10), and the remainder of the curve was fitted with relativedimensionality ( N ) = ( log N + b 0 ) 2 ( a 2 [ log N ] 2 + 2 a 2 b 0 log N + a 1 b 0 a 0 ) , where a 2 = 1 64 , a 1 = 4.13 , a 0 = 65.05 , and b 0 = 13.02 were computed via the Nelder–Mead simplex method. The data for the spectrum-equalized noise and natural scenes are replotted from Fig. 9b. The solid gray line denotes the intrinsic dimensionality of k = 64 for all data sets.

Fig. 13
Fig. 13

(a) RD curves and (b) proximity distribution functions for 8 × 8 Gaussian white noise (black curve), and (a) extrapolated RD and (b) proximity distribution curves for spectrum-equalized noise (gray circles) and natural scenes (stars) by assuming form A of the RD curves. Under from A, the RD curves follow a straight line (in log N ) until they hit the dimensionality value of 64.

Fig. 14
Fig. 14

Entropy estimate for Gaussian white noise and extrapolated entropy estimates (XEn curves) assuming form A of the RD curves (XEntropy A) for spectrum-equalized noise and natural scenes. The entropy estimates computed by using Eq. (8) with k = 64 and N = 2 300 are 5.4   bits pixel and 3.3   bits pixel for spectrum-equalized noise and natural scenes, respectively; the true entropy of spectrum-equalized noise computed via Eq. (9) is 5.1   bits pixel .

Fig. 15
Fig. 15

(a) RD curves and (b) proximity distribution functions for 8 × 8 Gaussian white noise (black curve), and (a) extrapolated RD and (b) proximity distribution curves for spectrum-equalized noise (gray circles) and natural scenes (stars) by assuming form B of the RD curves. Under form B, the RD curves follow a straight line until they intersect with the RD curve for Gaussian white noise, whereupon all subsequent RD values are equivalent to the RD values for Gaussian white noise.

Fig. 16
Fig. 16

Entropy estimate for Gaussian white noise and extrapolated entropy estimates (XEn curves) assuming form B of the RD curves (XEntropy B) for spectrum-equalized noise and natural scenes. The entropy estimates computed by using Eq. (8) with k = 64 and N = 2 300 are 5.3   bits pixel and 3.2   bits pixel for spectrum-equalized noise and natural scenes, respectively; the true entropy of spectrum-equalized noise computed via Eq. (9) is 5.1   bits pixel .

Fig. 17
Fig. 17

(a) RD curves and (b) proximity distribution functions for 8 × 8 Gaussian white noise (black curve), and (a) extrapolated RD and (b) proximity distribution curves for spectrum-equalized noise (gray circles) and natural scenes (stars) by assuming form C of the RD curves. Under form C, the RD curves assume the same functional form as the RD curve for Gaussian white noise [Eq. (12)], where a 2 = 1 64 , a 1 = 4.13 , a 0 = 65.05 , and the parameter b 0 was adjusted to fit the measured data ( b 0 = 10.88 for spectrum-equalized noise, b 0 = 8.10 for natural scenes).

Fig. 18
Fig. 18

Entropy estimate for Gaussian white noise and extrapolated entropy estimates (XEn curves) assuming form C of the RD curves (XEntropy C) for spectrum-equalized noise and natural scenes. The entropy estimates computed by using Eq. (8) with k = 64 and N = 2 300 are 5.1   bits pixel and 2.9   bits pixel for spectrum-equalized noise and natural scenes, respectively; the true entropy of spectrum-equalized noise computed via Eq. (9) is 5.1   bits pixel .

Fig. 19
Fig. 19

Proximity distribution functions for patches of size 8 × 8 (black circles) and 16 × 16 (white circles). (a) Data for Gaussian white noise; (b) data for natural scenes. The solid black curves in each graph denote the proximity distribution functions that would result if the 8 × 8 subpatches were statistically independent (thus requiring 4 times the entropy of 8 × 8 patches to describe a 16 × 16 patch). Note that the predicted curves have been vertically offset to match their corresponding data.

Fig. 20
Fig. 20

Proximity distribution functions for patches of size 8 × 8 (black circles) and 16 × 16 (white circles) in which each patch was mean and contrast normalized as described in Subsection 3B. (a) Data for Gaussian white noise; (b) data for natural scenes. The solid black curves in each graph denote the proximity distribution functions that would result if the 8 × 8 subpatches were statistically independent (thus requiring 4 times the entropy of 8 × 8 patches to describe a 16 × 16 patch). Note that the predicted curves have been vertically offset to match their corresponding data.

Equations (11)

Equations on this page are rendered with MathJax. Learn more.

f ( x ) = 1 σ 2 π e [ ( x μ ) 2 2 σ 2 ] ,
H ( u , v ) = { 1 u = v = 0 1 u 2 + v 2 else } ,
H ( u , v ) = { 1 u = v = 0 1 u 2 + v 2 else } ,
H ( u , v ) = σ R 2 ( u , v ) + σ I 2 ( u , v ) ,
D N , t * = min n [ 1 , N ] X ( J t ) X ( N n ) L 2 = ( min n [ 1 , N ] { i = 1 k ( X i ( J t ) X i ( N n ) ) 2 } ) 1 2 ,
h ( X ) x A f X ( x ) log 2 f X ( x ) d x = x A f X ( x ) i X ( x ) d x = E { i X ( x ) } 1 M m = 1 M i ̂ X ( x m ) ,
i ̂ X ( x ) = k E { log 2 D N * } + log 2 ( A k N k ) + γ ln 2 ,
h ( X ) k M m = 1 M log 2 D N , m * + log 2 ( A k N k ) + γ ln 2 ,
h ( X ) = 1 2 log 2 ( 2 π e σ 2 ) bits ,
E { log 2 D N * } = 1 2 log 2 ( 2 σ 2 ) + 1 2 E { log 2 D ̃ N * } = 1 2 log 2 ( 2 σ 2 ) + 1 2 0 f D ̃ N * ( ζ ) log 2 ( ζ ) d ζ = 1 2 log 2 ( 2 σ 2 ) + N 2 0 ( 1 F D ̃ ( ζ ) ) N 1 f D ̃ ( ζ ) log 2 ( ζ ) d ζ = 1 2 log 2 ( 2 σ 2 ) + N 2 0 ( Γ ( k 2 , ζ 2 2 ) Γ ( k 2 ) ) N 1 1 2 k 2 Γ ( k 2 ) ζ k 2 1 e ζ 2 log 2 ( ζ ) d ζ = 1 2 log 2 ( 2 σ 2 ) + N 2 k 2 + 1 Γ ( k 2 ) N 0 Γ ( k 2 , ζ 2 2 ) N 1 ζ k 2 1 e ζ 2 log 2 ( ζ ) d ζ .
H ( u , v ) = ( u 2 + v 2 ) 1.38 ,

Metrics