Abstract

Brownian motion is a random process that finds application in many fields, and its relation to certain color perception phenomena has recently been observed. On this ground, Marini and Rizzi developed a retinex algorithm based on Brownian motion paths. However, while their approach has several advantages and delivers interesting results, it has a high computational complexity. We propose an efficient algorithm that generates pseudo-Brownian paths with a very important constraint: we can guarantee a lower bound to the number of visits to each pixel, as well as its average. Despite these constraints, we show that the paths generated have certain statistical similarities to random walk and Brownian motion. Finally, we present a retinex implementation that exploits the paths generated with our algorithm, and we compare some images it generates with those obtained with the McCann99 and Frankle and McCann’s algorithms (two multiscale retinex implementations that have a low computational complexity). We find that our approach causes fewer artifacts and tends to require a smaller number of pixel comparisons to achieve similar results, thus compensating for the slightly higher computational complexity.

© 2011 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. Durret, Brownian Motion and Martingales in Analysis (Wadsworth, 1984).
  2. D. Freedman, Brownian Motion and Diffusion (Holden-Day, 1971).
  3. R. Engbert and R. Kliegl, “Microsaccades keep the eyes’ balance during fixation,” Psychol Sci. 15, 431–436 (2004).
    [CrossRef] [PubMed]
  4. M. Shelhamer, “Sequence of predictive saccades are correlated over a span of ∼2 s and produce a fractal time series,” J. Neurophysiol. 93, 2002–2011 (2005).
    [CrossRef]
  5. S. Zeki, A Vision of the Brain (Blackwell Science, 1993).
  6. D. Marini and A. Rizzi, “A computational approach to color adaptation effects,” Image Vis. Comput. 18, 1005–1014 (2000).
    [CrossRef]
  7. E. Provenzi, L. De Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. Opt. Soc. Am. A 22, 2613–2621 (2005).
    [CrossRef]
  8. K. Barnard and B. V. Funt, “Analysis and improvement of multi-scale retinex,” in Proceedings of the Fifth Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1997), pp. 221–226.
  9. Z. Rahman, D. J. Jobson, and G. A. Woodell, “Retinex processing for automatic image enhancement,” J. Electron. Imaging 13, 100–110 (2004).
    [CrossRef]
  10. D. Gadia, A. Rizzi, and D. Marini, “Tuning retinex for HDR images visualization,” in Proceedings of the Second European Conference on Color in Graphics, Imaging and Vision (Society for Imaging Sciences and Technology, 2004), pp. 326–331.
  11. L. Meylan and S. Süsstrunk, “High dynamic range image rendering with a retinex-based adaptive filter,” IEEE Trans. Image Process. 15, 2820–2830 (2006).
    [CrossRef] [PubMed]
  12. R. Sobol, “Improving the Retinex algorithm for rendering wide dynamic range photographs,” J. Electron. Imaging 13, 65–74(2004).
    [CrossRef]
  13. J. A. Frankle and J. J. McCann, “Method and apparatus for lightness imaging,” U.S. patent 4,384,336 (17 May 1983).
  14. B. V. Funt, F. Ciurea, and J. J. McCann, “Retinex in MATLAB,” J. Electron. Imaging 13, 48–57 (2004).
    [CrossRef]
  15. J. J. McCann, “Lessons learned from Mondrians applied to real images and color gamuts,” in Proceedings of the Seventh Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1999), pp. 1–8.
  16. J. M. Morel, A. B. Petro, and C. Sbert, “A PDE formalization of retinex theory,” IEEE Trans. Image Process. 19, 2825–2837(2010).
    [CrossRef]
  17. D. H. Brainard and B. A. Wandell, “Analysis of the retinex theory of color vision,” J. Opt. Soc. Am. 3, 1651–1661 (1986).
    [CrossRef]
  18. C. Fredembach and G. D. Finlayson, “Hamiltonian path-based shadow removal,” in Proceedings of the 16th British Machine Vision Conference (British Machine Vision Association, 2005), Vol.  2, pp. 502–511.
  19. C. Fredembach and G. D. Finlayson, “The 1.5D sieve algorithm,” Pattern Recogn. Lett. 29, 629–636 (2008).
    [CrossRef]
  20. J. Rudnick and G. Gaspari, Elements of the Random Walk(Cambridge University, 2004).
    [CrossRef]
  21. G. F. Lawler and L. N. Coyle, Lectures on Contemporary Probability, Student Mathematical Library (American Mathematical Society, 2000).
  22. B. B. Mandelbrot, The Fractal Geometry of Nature (Freeman, 1983).
  23. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).
  24. S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput. 28, 1293–1305 (2002).
    [CrossRef]
  25. R. Dafner, D. Cohen-Or, and Y. Matias, “Context-based space filling curves,” Comput. Graph. Forum 19, 209–218 (2000).
    [CrossRef]
  26. D. R. Karger, P. N. Klein, and R. E. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees,” J. Assoc. Comput. Mach. 42, 321–328 (1995).
    [CrossRef]
  27. R. Gould, Graph Theory (Benjamin/Cummins, 1988).
  28. G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” J. Stat. Software 5, 1–7 (2000).
  29. Kodak, “Kodak lossless true color image suite,” 2004, retrieved 23 October 2010, http://r0k.us/graphics/kodak/.
  30. E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
    [CrossRef] [PubMed]

2010 (1)

J. M. Morel, A. B. Petro, and C. Sbert, “A PDE formalization of retinex theory,” IEEE Trans. Image Process. 19, 2825–2837(2010).
[CrossRef]

2008 (1)

C. Fredembach and G. D. Finlayson, “The 1.5D sieve algorithm,” Pattern Recogn. Lett. 29, 629–636 (2008).
[CrossRef]

2007 (1)

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

2006 (1)

L. Meylan and S. Süsstrunk, “High dynamic range image rendering with a retinex-based adaptive filter,” IEEE Trans. Image Process. 15, 2820–2830 (2006).
[CrossRef] [PubMed]

2005 (2)

M. Shelhamer, “Sequence of predictive saccades are correlated over a span of ∼2 s and produce a fractal time series,” J. Neurophysiol. 93, 2002–2011 (2005).
[CrossRef]

E. Provenzi, L. De Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. Opt. Soc. Am. A 22, 2613–2621 (2005).
[CrossRef]

2004 (4)

Z. Rahman, D. J. Jobson, and G. A. Woodell, “Retinex processing for automatic image enhancement,” J. Electron. Imaging 13, 100–110 (2004).
[CrossRef]

R. Sobol, “Improving the Retinex algorithm for rendering wide dynamic range photographs,” J. Electron. Imaging 13, 65–74(2004).
[CrossRef]

B. V. Funt, F. Ciurea, and J. J. McCann, “Retinex in MATLAB,” J. Electron. Imaging 13, 48–57 (2004).
[CrossRef]

R. Engbert and R. Kliegl, “Microsaccades keep the eyes’ balance during fixation,” Psychol Sci. 15, 431–436 (2004).
[CrossRef] [PubMed]

2002 (1)

S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput. 28, 1293–1305 (2002).
[CrossRef]

2000 (3)

R. Dafner, D. Cohen-Or, and Y. Matias, “Context-based space filling curves,” Comput. Graph. Forum 19, 209–218 (2000).
[CrossRef]

G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” J. Stat. Software 5, 1–7 (2000).

D. Marini and A. Rizzi, “A computational approach to color adaptation effects,” Image Vis. Comput. 18, 1005–1014 (2000).
[CrossRef]

1995 (1)

D. R. Karger, P. N. Klein, and R. E. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees,” J. Assoc. Comput. Mach. 42, 321–328 (1995).
[CrossRef]

1986 (1)

D. H. Brainard and B. A. Wandell, “Analysis of the retinex theory of color vision,” J. Opt. Soc. Am. 3, 1651–1661 (1986).
[CrossRef]

Barnard, K.

K. Barnard and B. V. Funt, “Analysis and improvement of multi-scale retinex,” in Proceedings of the Fifth Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1997), pp. 221–226.

Brainard, D. H.

D. H. Brainard and B. A. Wandell, “Analysis of the retinex theory of color vision,” J. Opt. Soc. Am. 3, 1651–1661 (1986).
[CrossRef]

Chen, S. D.

S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput. 28, 1293–1305 (2002).
[CrossRef]

Ciurea, F.

B. V. Funt, F. Ciurea, and J. J. McCann, “Retinex in MATLAB,” J. Electron. Imaging 13, 48–57 (2004).
[CrossRef]

Cohen-Or, D.

R. Dafner, D. Cohen-Or, and Y. Matias, “Context-based space filling curves,” Comput. Graph. Forum 19, 209–218 (2000).
[CrossRef]

Cormen, T. H.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).

Coyle, L. N.

G. F. Lawler and L. N. Coyle, Lectures on Contemporary Probability, Student Mathematical Library (American Mathematical Society, 2000).

Dafner, R.

R. Dafner, D. Cohen-Or, and Y. Matias, “Context-based space filling curves,” Comput. Graph. Forum 19, 209–218 (2000).
[CrossRef]

De Carli, L.

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

E. Provenzi, L. De Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. Opt. Soc. Am. A 22, 2613–2621 (2005).
[CrossRef]

Durret, R.

R. Durret, Brownian Motion and Martingales in Analysis (Wadsworth, 1984).

Engbert, R.

R. Engbert and R. Kliegl, “Microsaccades keep the eyes’ balance during fixation,” Psychol Sci. 15, 431–436 (2004).
[CrossRef] [PubMed]

Fierro, M.

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

Finlayson, G. D.

C. Fredembach and G. D. Finlayson, “The 1.5D sieve algorithm,” Pattern Recogn. Lett. 29, 629–636 (2008).
[CrossRef]

C. Fredembach and G. D. Finlayson, “Hamiltonian path-based shadow removal,” in Proceedings of the 16th British Machine Vision Conference (British Machine Vision Association, 2005), Vol.  2, pp. 502–511.

Frankle, J. A.

J. A. Frankle and J. J. McCann, “Method and apparatus for lightness imaging,” U.S. patent 4,384,336 (17 May 1983).

Fredembach, C.

C. Fredembach and G. D. Finlayson, “The 1.5D sieve algorithm,” Pattern Recogn. Lett. 29, 629–636 (2008).
[CrossRef]

C. Fredembach and G. D. Finlayson, “Hamiltonian path-based shadow removal,” in Proceedings of the 16th British Machine Vision Conference (British Machine Vision Association, 2005), Vol.  2, pp. 502–511.

Freedman, D.

D. Freedman, Brownian Motion and Diffusion (Holden-Day, 1971).

Funt, B. V.

B. V. Funt, F. Ciurea, and J. J. McCann, “Retinex in MATLAB,” J. Electron. Imaging 13, 48–57 (2004).
[CrossRef]

K. Barnard and B. V. Funt, “Analysis and improvement of multi-scale retinex,” in Proceedings of the Fifth Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1997), pp. 221–226.

Gadia, D.

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

D. Gadia, A. Rizzi, and D. Marini, “Tuning retinex for HDR images visualization,” in Proceedings of the Second European Conference on Color in Graphics, Imaging and Vision (Society for Imaging Sciences and Technology, 2004), pp. 326–331.

Gaspari, G.

J. Rudnick and G. Gaspari, Elements of the Random Walk(Cambridge University, 2004).
[CrossRef]

Gould, R.

R. Gould, Graph Theory (Benjamin/Cummins, 1988).

Jobson, D. J.

Z. Rahman, D. J. Jobson, and G. A. Woodell, “Retinex processing for automatic image enhancement,” J. Electron. Imaging 13, 100–110 (2004).
[CrossRef]

Karger, D. R.

D. R. Karger, P. N. Klein, and R. E. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees,” J. Assoc. Comput. Mach. 42, 321–328 (1995).
[CrossRef]

Klein, P. N.

D. R. Karger, P. N. Klein, and R. E. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees,” J. Assoc. Comput. Mach. 42, 321–328 (1995).
[CrossRef]

Kliegl, R.

R. Engbert and R. Kliegl, “Microsaccades keep the eyes’ balance during fixation,” Psychol Sci. 15, 431–436 (2004).
[CrossRef] [PubMed]

Lawler, G. F.

G. F. Lawler and L. N. Coyle, Lectures on Contemporary Probability, Student Mathematical Library (American Mathematical Society, 2000).

Leiserson, C. E.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).

Mandelbrot, B. B.

B. B. Mandelbrot, The Fractal Geometry of Nature (Freeman, 1983).

Marini, D.

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

E. Provenzi, L. De Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. Opt. Soc. Am. A 22, 2613–2621 (2005).
[CrossRef]

D. Marini and A. Rizzi, “A computational approach to color adaptation effects,” Image Vis. Comput. 18, 1005–1014 (2000).
[CrossRef]

D. Gadia, A. Rizzi, and D. Marini, “Tuning retinex for HDR images visualization,” in Proceedings of the Second European Conference on Color in Graphics, Imaging and Vision (Society for Imaging Sciences and Technology, 2004), pp. 326–331.

Marsaglia, G.

G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” J. Stat. Software 5, 1–7 (2000).

Matias, Y.

R. Dafner, D. Cohen-Or, and Y. Matias, “Context-based space filling curves,” Comput. Graph. Forum 19, 209–218 (2000).
[CrossRef]

McCann, J. J.

B. V. Funt, F. Ciurea, and J. J. McCann, “Retinex in MATLAB,” J. Electron. Imaging 13, 48–57 (2004).
[CrossRef]

J. J. McCann, “Lessons learned from Mondrians applied to real images and color gamuts,” in Proceedings of the Seventh Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1999), pp. 1–8.

J. A. Frankle and J. J. McCann, “Method and apparatus for lightness imaging,” U.S. patent 4,384,336 (17 May 1983).

Meylan, L.

L. Meylan and S. Süsstrunk, “High dynamic range image rendering with a retinex-based adaptive filter,” IEEE Trans. Image Process. 15, 2820–2830 (2006).
[CrossRef] [PubMed]

Morel, J. M.

J. M. Morel, A. B. Petro, and C. Sbert, “A PDE formalization of retinex theory,” IEEE Trans. Image Process. 19, 2825–2837(2010).
[CrossRef]

Petro, A. B.

J. M. Morel, A. B. Petro, and C. Sbert, “A PDE formalization of retinex theory,” IEEE Trans. Image Process. 19, 2825–2837(2010).
[CrossRef]

Provenzi, E.

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

E. Provenzi, L. De Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. Opt. Soc. Am. A 22, 2613–2621 (2005).
[CrossRef]

Rahman, Z.

Z. Rahman, D. J. Jobson, and G. A. Woodell, “Retinex processing for automatic image enhancement,” J. Electron. Imaging 13, 100–110 (2004).
[CrossRef]

Rivest, R. L.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).

Rizzi, A.

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

E. Provenzi, L. De Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. Opt. Soc. Am. A 22, 2613–2621 (2005).
[CrossRef]

D. Marini and A. Rizzi, “A computational approach to color adaptation effects,” Image Vis. Comput. 18, 1005–1014 (2000).
[CrossRef]

D. Gadia, A. Rizzi, and D. Marini, “Tuning retinex for HDR images visualization,” in Proceedings of the Second European Conference on Color in Graphics, Imaging and Vision (Society for Imaging Sciences and Technology, 2004), pp. 326–331.

Rudnick, J.

J. Rudnick and G. Gaspari, Elements of the Random Walk(Cambridge University, 2004).
[CrossRef]

Sbert, C.

J. M. Morel, A. B. Petro, and C. Sbert, “A PDE formalization of retinex theory,” IEEE Trans. Image Process. 19, 2825–2837(2010).
[CrossRef]

Shelhamer, M.

M. Shelhamer, “Sequence of predictive saccades are correlated over a span of ∼2 s and produce a fractal time series,” J. Neurophysiol. 93, 2002–2011 (2005).
[CrossRef]

Shen, H.

S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput. 28, 1293–1305 (2002).
[CrossRef]

Sobol, R.

R. Sobol, “Improving the Retinex algorithm for rendering wide dynamic range photographs,” J. Electron. Imaging 13, 65–74(2004).
[CrossRef]

Stein, C.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).

Süsstrunk, S.

L. Meylan and S. Süsstrunk, “High dynamic range image rendering with a retinex-based adaptive filter,” IEEE Trans. Image Process. 15, 2820–2830 (2006).
[CrossRef] [PubMed]

Tarjan, R. E.

D. R. Karger, P. N. Klein, and R. E. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees,” J. Assoc. Comput. Mach. 42, 321–328 (1995).
[CrossRef]

Topor, R.

S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput. 28, 1293–1305 (2002).
[CrossRef]

Tsang, W. W.

G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” J. Stat. Software 5, 1–7 (2000).

Wandell, B. A.

D. H. Brainard and B. A. Wandell, “Analysis of the retinex theory of color vision,” J. Opt. Soc. Am. 3, 1651–1661 (1986).
[CrossRef]

Woodell, G. A.

Z. Rahman, D. J. Jobson, and G. A. Woodell, “Retinex processing for automatic image enhancement,” J. Electron. Imaging 13, 100–110 (2004).
[CrossRef]

Zeki, S.

S. Zeki, A Vision of the Brain (Blackwell Science, 1993).

Comput. Graph. Forum (1)

R. Dafner, D. Cohen-Or, and Y. Matias, “Context-based space filling curves,” Comput. Graph. Forum 19, 209–218 (2000).
[CrossRef]

IEEE Trans. Image Process. (3)

J. M. Morel, A. B. Petro, and C. Sbert, “A PDE formalization of retinex theory,” IEEE Trans. Image Process. 19, 2825–2837(2010).
[CrossRef]

E. Provenzi, M. Fierro, A. Rizzi, L. De Carli, D. Gadia, and D. Marini, “Random spray Retinex: a new retinex implementation to investigate the local properties of the model,” IEEE Trans. Image Process. 16, 162–171 (2007).
[CrossRef] [PubMed]

L. Meylan and S. Süsstrunk, “High dynamic range image rendering with a retinex-based adaptive filter,” IEEE Trans. Image Process. 15, 2820–2830 (2006).
[CrossRef] [PubMed]

Image Vis. Comput. (1)

D. Marini and A. Rizzi, “A computational approach to color adaptation effects,” Image Vis. Comput. 18, 1005–1014 (2000).
[CrossRef]

J. Assoc. Comput. Mach. (1)

D. R. Karger, P. N. Klein, and R. E. Tarjan, “A randomized linear-time algorithm to find minimum spanning trees,” J. Assoc. Comput. Mach. 42, 321–328 (1995).
[CrossRef]

J. Electron. Imaging (3)

Z. Rahman, D. J. Jobson, and G. A. Woodell, “Retinex processing for automatic image enhancement,” J. Electron. Imaging 13, 100–110 (2004).
[CrossRef]

R. Sobol, “Improving the Retinex algorithm for rendering wide dynamic range photographs,” J. Electron. Imaging 13, 65–74(2004).
[CrossRef]

B. V. Funt, F. Ciurea, and J. J. McCann, “Retinex in MATLAB,” J. Electron. Imaging 13, 48–57 (2004).
[CrossRef]

J. Neurophysiol. (1)

M. Shelhamer, “Sequence of predictive saccades are correlated over a span of ∼2 s and produce a fractal time series,” J. Neurophysiol. 93, 2002–2011 (2005).
[CrossRef]

J. Opt. Soc. Am. (1)

D. H. Brainard and B. A. Wandell, “Analysis of the retinex theory of color vision,” J. Opt. Soc. Am. 3, 1651–1661 (1986).
[CrossRef]

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

J. Stat. Software (1)

G. Marsaglia and W. W. Tsang, “The ziggurat method for generating random variables,” J. Stat. Software 5, 1–7 (2000).

Parallel Comput. (1)

S. D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput. 28, 1293–1305 (2002).
[CrossRef]

Pattern Recogn. Lett. (1)

C. Fredembach and G. D. Finlayson, “The 1.5D sieve algorithm,” Pattern Recogn. Lett. 29, 629–636 (2008).
[CrossRef]

Psychol Sci. (1)

R. Engbert and R. Kliegl, “Microsaccades keep the eyes’ balance during fixation,” Psychol Sci. 15, 431–436 (2004).
[CrossRef] [PubMed]

Other (14)

C. Fredembach and G. D. Finlayson, “Hamiltonian path-based shadow removal,” in Proceedings of the 16th British Machine Vision Conference (British Machine Vision Association, 2005), Vol.  2, pp. 502–511.

Kodak, “Kodak lossless true color image suite,” 2004, retrieved 23 October 2010, http://r0k.us/graphics/kodak/.

R. Gould, Graph Theory (Benjamin/Cummins, 1988).

J. Rudnick and G. Gaspari, Elements of the Random Walk(Cambridge University, 2004).
[CrossRef]

G. F. Lawler and L. N. Coyle, Lectures on Contemporary Probability, Student Mathematical Library (American Mathematical Society, 2000).

B. B. Mandelbrot, The Fractal Geometry of Nature (Freeman, 1983).

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).

J. J. McCann, “Lessons learned from Mondrians applied to real images and color gamuts,” in Proceedings of the Seventh Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1999), pp. 1–8.

J. A. Frankle and J. J. McCann, “Method and apparatus for lightness imaging,” U.S. patent 4,384,336 (17 May 1983).

K. Barnard and B. V. Funt, “Analysis and improvement of multi-scale retinex,” in Proceedings of the Fifth Color Imaging Conference (Society for Information Systems and Technology, Society for Information Display, 1997), pp. 221–226.

D. Gadia, A. Rizzi, and D. Marini, “Tuning retinex for HDR images visualization,” in Proceedings of the Second European Conference on Color in Graphics, Imaging and Vision (Society for Imaging Sciences and Technology, 2004), pp. 326–331.

S. Zeki, A Vision of the Brain (Blackwell Science, 1993).

R. Durret, Brownian Motion and Martingales in Analysis (Wadsworth, 1984).

D. Freedman, Brownian Motion and Diffusion (Holden-Day, 1971).

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 (13)

Fig. 1
Fig. 1

(a) Example of Brownian motion in two dimensions and (b) example of pseudo-Brownian path generated with our algorithm.

Fig. 2
Fig. 2

Hamiltonian path on the pixels of an image represented as a graph. (a) The original grid graph is (b) subsampled. (c) Then a spanning tree is computed, and after upsampling to the original resolution, it is possible to adjust the edges in order to obtain a (d) Hamiltonian path.

Fig. 3
Fig. 3

Application of our algorithm to a 3 × 3 grid graph, with parameter k = 2 . Yellow vertices are in S with multiplicity given by the inscribed number, blue edges are in T, and magenta edges are in Q. Starting from (a), in step 2 our algorithm randomly selects a node that is going to be the root r of the tree. Thus, all the edges that connect the vertices in S with the others go into Q (or become magenta). In step 3, it picks randomly an edge from Q, adds the edge to T (or it paints it blue) and adds new edges to Q. The algorithm continues this way, always picking a random edge from Q and adding it to T. Note in (b), step 6, that the first vertex reaches multiplicity 2 in S, and all of its edges become outgoing only. In (c), step 12, we see that a direct connection between two vertices disappears, since both have already multiplicity 2.

Fig. 4
Fig. 4

In (a), the algorithm keeps proceeding until all vertices are in S twice, and thus Q is empty. In step 20 we are labelling the vertices with letters from a to i so that we can see how a spanning multigraph is built. For the sake of clarity, we unroll this multigraph in (b) and show it as a tree with repeated vertices having root in b, our starting vertex in the initial graph. Even though vertices are repeated, step 20 in (a) and this tree have the same number of edges. Also, in the tree there is no need to stress the directionality of the edges, since this comes naturally in the parent–child node relation.

Fig. 5
Fig. 5

Average drifts from the origin of different type of paths. Our random path in (a) visits each pixel on average 32 times (i.e., k = 16 ). (b) The drifts of raster paths and Hilbert curves are very different from those of random walks.

Fig. 6
Fig. 6

Two instances of the probability P ( n , d ) and the measured P ˜ ( n , d ) , with (a) even and (b) odd numbers of steps and distances, shown as continuous curves for clarity. We set k = 16 for our random path.

Fig. 7
Fig. 7

(a) Grid graphs are a natural way of representing images: each vertex corresponds to a pixel, and edges connect pixels that are neighbors. Our algorithm on such a graph generates a pseudorandom walk. To obtain pseudo-Brownian motion, we discard the grid structure and (b) generate random edges having normally distributed length. This approach does not guarantee that the graph is connected, i.e., there may exist two vertices that are not connected by a path. In order to guarantee this constraint, we superimpose (a) with (b) and we obtain (c).

Fig. 8
Fig. 8

Normal probability plots of the displacements (a) without and (b) with grid structure in the graph. The dashed line represents a normal distribution and the black crosses the measured displacements. The deviation from the line in (b) shows that the tails of the measured data are longer than those of a normal distribution with the same mean and standard deviation as the data. These plots are only for the displacements in the y direction, as the plots for x are almost identical.

Fig. 9
Fig. 9

Normal distribution overlapped to the displacement histogram. If we do not force the grid structure in (a), the histogram and the normal distribution match almost perfectly, as shown already in Fig. 8a. (b) If we force the grid structure instead, the histogram has a peak on steps of length 1 , 0, and 1, as we would expect. The normal distribution in (b) has the same standard deviation as the random steps introduced by the algorithm. These plots are only for the displacements in the y direction, as the plots for x are almost identical.

Fig. 10
Fig. 10

Image for displaying the point spread function[14]. Applying 32 visits per pixel (b) with McCann99, and 16 on average (d) with our approach, our method delivers a much more plausible resulting image. In (d) we can see that the halo artifact around the white square is not biased in any particular direction, whereas in (b) even with 32 visits per pixel in McCann99 the halo is clearly biased toward the top-right corner of the image. (c) With an average of 32 visits per pixel, Frankle and McCann’s algorithm causes an even stronger bias toward the top-left corner of the image.

Fig. 11
Fig. 11

Image from the Kodak data set [29], processed with four McCann99 iterations (32 visits per pixel), 16 Frankle and McCann iterations (32 visits per pixel), and k = 16 with our approach (32 visits per pixel on average).

Fig. 12
Fig. 12

Photo of the interior of Ely cathedral (England), provided by the authors. Here it was processed with (c) McCann99 retinex with 128 visits per pixel and then compared with (b) 32 visits per pixel of Frankle and McCann and (d) our approach.

Fig. 13
Fig. 13

Image from the Kodak data set [29], processed with a multiscale iteration scheme, i.e., the smaller the scale, the more iterations are performed. With nine scales, the McCann99 algorithm compares each pixel 256 × 2 s times with its neighbors, with s the number of the scale ( s = 1 is the full image). Our algorithm and Frankle and McCann’s obtain this result with 16 × 2 s comparisons only.

Tables (3)

Tables Icon

Table 1 Mean and Standard Deviation of the SSDs from the Input Image over the Kodak Data Set

Tables Icon

Table 2 Mean and Standard Deviation of the SSDs from Our Approach with 32 Visits per Pixel over the Kodak Data Set

Tables Icon

Table 3 Computational Complexities of Retinex Implementations

Equations (10)

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

D ( A , B ) = | a x b x | + | a y b y | .
E [ S n 2 ] = n ,
P ( n , d ) = ( 1 2 ) n n ! ( ( n + d 2 ) ! ( n d 2 ) ! ) 1 ,
w i , j n = 1 4 w i 1 , j n 1 + 1 4 w i + 1 , j n 1 + 1 4 w i , j 1 n 1 + 1 4 w i , j + 1 n 1 .
M = 0 1 4 0 1 4 0 1 4 0 1 4 0 .
W 0 = 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 , W 1 = 0 0 0 0 0 0 0 1 4 0 0 0 1 4 0 1 4 0 0 0 1 4 0 0 0 0 0 0 0 , W 2 = 0 0 1 16 0 0 0 1 8 0 1 8 0 1 16 0 1 4 0 1 16 0 1 8 0 1 8 0 0 0 1 16 0 0 .
log IP ( x i ) = log NP ( x i 1 ) + log x i log x i 1 ,
log NP ( x i ) = 1 2 ( log OP ( x i ) + min { log IP ( x i ) , 0 } ) .
m = 0 s 1 4 m N log ( 1 4 m N ) + m = 0 s 1 4 m N ,
= N m = 0 s 1 4 m ( log N m log 4 ) + m = 0 s 1 4 m N = = N log N m = 0 s 1 4 m N ( log 4 m = 0 s m 4 m m = 0 s 1 4 m ) = C N log N C N ,

Metrics