OSA's Digital Library

Virtual Journal for Biomedical Optics

Virtual Journal for Biomedical Optics

| EXPLORING THE INTERFACE OF LIGHT AND BIOMEDICINE

  • Editor: Gregory W. Faris
  • Vol. 2, Iss. 5 — May. 17, 2007

Estimates of the information content and dimensionality of natural scenes from proximity distributions

Damon M. Chandler and David J. Field  »View Author Affiliations


JOSA A, Vol. 24, Issue 4, pp. 922-941 (2007)
http://dx.doi.org/10.1364/JOSAA.24.000922


View Full Text Article

Enhanced HTML    Acrobat PDF (2597 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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 ( < 2 20 ) 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

OCIS Codes
(100.7410) Image processing : Wavelets
(330.1800) Vision, color, and visual optics : Vision - contrast sensitivity
(330.1880) Vision, color, and visual optics : Detection
(330.5020) Vision, color, and visual optics : Perception psychology
(330.5510) Vision, color, and visual optics : Psychophysics

ToC Category:
Vision and color

History
Original Manuscript: May 30, 2006
Manuscript Accepted: September 29, 2006
Published: March 14, 2007

Virtual Issues
Vol. 2, Iss. 5 Virtual Journal for Biomedical Optics

Citation
Damon M. Chandler and David J. Field, "Estimates of the information content and dimensionality of natural scenes from proximity distributions," J. Opt. Soc. Am. A 24, 922-941 (2007)
http://www.opticsinfobase.org/vjbo/abstract.cfm?URI=josaa-24-4-922


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  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).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited