Abstract

We prove that the scale map of the zero crossings of almost all signals filtered by a Gaussian filter of variable size determines the signal uniquely, up to a constant scaling. The proof assumes that the filtered signal can be represented as a polynomial of finite, albeit possibly high, order. The result applies to zero and level crossings of linear differential operators of Gaussian filters. In this case the signal is determined uniquely, modulus the null space of the linear operator. The theorem can be extended to two-dimensional functions. These results are reminiscent of Logan’s theorem [ Bell Syst. Tech. J.56, 487 ( 1977)]. They imply that extrema of derivatives at different scales are a complete representation of a signal. They are especially relevant for computational vision in the case of the Laplacian operator acting on image intensities, and they suggest rigorous foundations for the primal sketch.

© 1985 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. Marr, Vision, A Computational Investigation into the Human Representation and Processing of Visual Information (Freeman, San Francisco, Calif., 1982).
  2. B. F. Logan, “Information in the zero crossings of bandpass signals,” Bell Syst. Tech. J. 56, 487–510 (1977).
  3. T. Poggio, H. K. Nishihara, K. R. K. Nielsen, “Zero-crossings and spatiotemporal interpolation in vision: aliasing and electrical coupling between sensors,” Artificial Intelligence Memo 675 (Massachusetts Institute of Technology, Cambridge, Mass., May1982).
  4. D. Marr, T. Poggio, S. Ullman, “Bandpass channels, zero-crossings and early visual information processing,”J. Opt. Soc. Am. 70, 868–870 (1979).
    [CrossRef]
  5. W. E. L. Grimson, From Images to Surfaces (MIT Press, Cambridge, Mass., 1981).
  6. D. Marr, E. Hildreth, “Theory of edge detection,” Proc.R. Soc. London Ser. B, 207, 187–217 (1980).
    [CrossRef]
  7. J. L. Crowley, “A representation for visual information,” (Robotics Institute, Carnegie-Mellon University, Pittsburgh, Pa., 1982).
  8. A. Rosenfeld, “Quadtrees and pyramids: hyerarchical representation of images,” (University of Maryland, College Park, Md., 1982).
  9. F. W. Campbell, J. G. Robson, “Applications of Fourier analysis to the visibility of gratings,”J. Physiol. (London) 197, 551–556 (1968).
  10. C. Enroth-Cugell, J. G. Robson, “The contrast sensitivity of retinal ganglion cells of the cat,”J. Physiol. London 187, 517–552 (1966).
    [PubMed]
  11. A. Witkin, “Scale-space filtering,” presented at the International Joint Conference on Artificial Intelligence, Karlsruhe, Federal Republic of Germany, 1983.
  12. J. L. Stansfield, “Conclusions from the commodity expert project,” Artificial Intelligence Memo 601 (Massachusetts Institute of Technology, Cambridge, Mass., 1980).
  13. J. Babaud, A. Witkin, R. Duda, “Uniqueness of the Gaussian kernel for scale-space filtering,” (Fairchild Artificial Intelligence Laboratory, Palo Alto, Calif., 1983).
  14. A. L. Yuille, T. Poggio, “Scaling theorems for zero-crossings,” Artificial Intelligence Memo 722 (Massachusetts Institute of Technology, Cambridge, Mass., June1983).
  15. A. L. Yuille, T. Poggio, “Fingerprints theorems for zero-crossings,” Artificial Intelligence Memo 730 (Massachusetts Institute of Technology, Cambridge, Mass., October1983).
  16. J. Koenderink, University of Utrecht, Utrecht, The Netherlands (personal communication, 1984).
  17. H. K. Nishihara, “Intensity, visible-surface, and volumetric representations,” Art. Intell. 17, 265–284 (1981).
    [CrossRef]
  18. Clearly, the scale-map fingerprint cannot always be a more compact description of the signal than the signal itself, unless the signal is redundant in precisely the way that the fingerprint representation can exploit. We expect this to be the case for images, if an appropriate differential operator is used, because images are not a purely random array of numbers. Usually images consist of rather homogeneous regions that do not change much over significant scale intervals.
  19. H. Asada, M. Brady, “The curvature primal sketch,” Artificial Intelligence Memo 758 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).
  20. A. L. Yuille, T. Poggio, “Fingerprints and the psychophysics of gratings,” Artificial Intelligence Memo 751 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).
  21. A. L. Yuille, T. Poggio, “Fingerprints theorems,” presented at the Conference on Artificial Intelligence, Austin, Texas, 1984.
  22. S. W. Zucker, R. A. Hummel, “Receptive fields and the reconstruction of visual information,” (Courant Institute, New York, N.Y., 1983).
  23. This argument cannot be applied when all zero-crossing contours are vertical straight lines: It is impossible to reconstruct the signal.20 In this case the matrices in Eqs. (3.3.1) and (3.3.2) take simple forms.
  24. A. Albert, Regression and the Moore–Penrose Pseudoinverse (Academic, New York, 1982).
  25. W. E. L. Grimson, “Surface consistency constants in vision,” Comput. Vision Graph. Inf. Process, 24, 28–51 (1983).
    [CrossRef]
  26. A. L. Yuille, “Zero-crossings and lines of curvature,” Artificial Intelligence Memo 718 (Massachusetts Institute of Technology, Cambridge, Mass., 1983).
  27. R. A. Hummel, Courant Institute, New York, N.Y. (personal communication).
  28. A. L. Yuille, T. Poggio, “Fingerprints and their slope,” Artificial Intelligence Memo 752 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).
  29. D. Marr, “Early processing of visual information,” Phil. Trans. R. Soc. London Ser. B 275, 483–524 (1976).
    [CrossRef]

1983 (1)

W. E. L. Grimson, “Surface consistency constants in vision,” Comput. Vision Graph. Inf. Process, 24, 28–51 (1983).
[CrossRef]

1981 (1)

H. K. Nishihara, “Intensity, visible-surface, and volumetric representations,” Art. Intell. 17, 265–284 (1981).
[CrossRef]

1980 (1)

D. Marr, E. Hildreth, “Theory of edge detection,” Proc.R. Soc. London Ser. B, 207, 187–217 (1980).
[CrossRef]

1979 (1)

1977 (1)

B. F. Logan, “Information in the zero crossings of bandpass signals,” Bell Syst. Tech. J. 56, 487–510 (1977).

1976 (1)

D. Marr, “Early processing of visual information,” Phil. Trans. R. Soc. London Ser. B 275, 483–524 (1976).
[CrossRef]

1968 (1)

F. W. Campbell, J. G. Robson, “Applications of Fourier analysis to the visibility of gratings,”J. Physiol. (London) 197, 551–556 (1968).

1966 (1)

C. Enroth-Cugell, J. G. Robson, “The contrast sensitivity of retinal ganglion cells of the cat,”J. Physiol. London 187, 517–552 (1966).
[PubMed]

Albert, A.

A. Albert, Regression and the Moore–Penrose Pseudoinverse (Academic, New York, 1982).

Asada, H.

H. Asada, M. Brady, “The curvature primal sketch,” Artificial Intelligence Memo 758 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

Babaud, J.

J. Babaud, A. Witkin, R. Duda, “Uniqueness of the Gaussian kernel for scale-space filtering,” (Fairchild Artificial Intelligence Laboratory, Palo Alto, Calif., 1983).

Brady, M.

H. Asada, M. Brady, “The curvature primal sketch,” Artificial Intelligence Memo 758 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

Campbell, F. W.

F. W. Campbell, J. G. Robson, “Applications of Fourier analysis to the visibility of gratings,”J. Physiol. (London) 197, 551–556 (1968).

Crowley, J. L.

J. L. Crowley, “A representation for visual information,” (Robotics Institute, Carnegie-Mellon University, Pittsburgh, Pa., 1982).

Duda, R.

J. Babaud, A. Witkin, R. Duda, “Uniqueness of the Gaussian kernel for scale-space filtering,” (Fairchild Artificial Intelligence Laboratory, Palo Alto, Calif., 1983).

Enroth-Cugell, C.

C. Enroth-Cugell, J. G. Robson, “The contrast sensitivity of retinal ganglion cells of the cat,”J. Physiol. London 187, 517–552 (1966).
[PubMed]

Grimson, W. E. L.

W. E. L. Grimson, “Surface consistency constants in vision,” Comput. Vision Graph. Inf. Process, 24, 28–51 (1983).
[CrossRef]

W. E. L. Grimson, From Images to Surfaces (MIT Press, Cambridge, Mass., 1981).

Hildreth, E.

D. Marr, E. Hildreth, “Theory of edge detection,” Proc.R. Soc. London Ser. B, 207, 187–217 (1980).
[CrossRef]

Hummel, R. A.

R. A. Hummel, Courant Institute, New York, N.Y. (personal communication).

S. W. Zucker, R. A. Hummel, “Receptive fields and the reconstruction of visual information,” (Courant Institute, New York, N.Y., 1983).

Koenderink, J.

J. Koenderink, University of Utrecht, Utrecht, The Netherlands (personal communication, 1984).

Logan, B. F.

B. F. Logan, “Information in the zero crossings of bandpass signals,” Bell Syst. Tech. J. 56, 487–510 (1977).

Marr, D.

D. Marr, E. Hildreth, “Theory of edge detection,” Proc.R. Soc. London Ser. B, 207, 187–217 (1980).
[CrossRef]

D. Marr, T. Poggio, S. Ullman, “Bandpass channels, zero-crossings and early visual information processing,”J. Opt. Soc. Am. 70, 868–870 (1979).
[CrossRef]

D. Marr, “Early processing of visual information,” Phil. Trans. R. Soc. London Ser. B 275, 483–524 (1976).
[CrossRef]

D. Marr, Vision, A Computational Investigation into the Human Representation and Processing of Visual Information (Freeman, San Francisco, Calif., 1982).

Nielsen, K. R. K.

T. Poggio, H. K. Nishihara, K. R. K. Nielsen, “Zero-crossings and spatiotemporal interpolation in vision: aliasing and electrical coupling between sensors,” Artificial Intelligence Memo 675 (Massachusetts Institute of Technology, Cambridge, Mass., May1982).

Nishihara, H. K.

H. K. Nishihara, “Intensity, visible-surface, and volumetric representations,” Art. Intell. 17, 265–284 (1981).
[CrossRef]

T. Poggio, H. K. Nishihara, K. R. K. Nielsen, “Zero-crossings and spatiotemporal interpolation in vision: aliasing and electrical coupling between sensors,” Artificial Intelligence Memo 675 (Massachusetts Institute of Technology, Cambridge, Mass., May1982).

Poggio, T.

D. Marr, T. Poggio, S. Ullman, “Bandpass channels, zero-crossings and early visual information processing,”J. Opt. Soc. Am. 70, 868–870 (1979).
[CrossRef]

A. L. Yuille, T. Poggio, “Fingerprints theorems,” presented at the Conference on Artificial Intelligence, Austin, Texas, 1984.

A. L. Yuille, T. Poggio, “Fingerprints theorems for zero-crossings,” Artificial Intelligence Memo 730 (Massachusetts Institute of Technology, Cambridge, Mass., October1983).

A. L. Yuille, T. Poggio, “Fingerprints and the psychophysics of gratings,” Artificial Intelligence Memo 751 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

T. Poggio, H. K. Nishihara, K. R. K. Nielsen, “Zero-crossings and spatiotemporal interpolation in vision: aliasing and electrical coupling between sensors,” Artificial Intelligence Memo 675 (Massachusetts Institute of Technology, Cambridge, Mass., May1982).

A. L. Yuille, T. Poggio, “Scaling theorems for zero-crossings,” Artificial Intelligence Memo 722 (Massachusetts Institute of Technology, Cambridge, Mass., June1983).

A. L. Yuille, T. Poggio, “Fingerprints and their slope,” Artificial Intelligence Memo 752 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

Robson, J. G.

F. W. Campbell, J. G. Robson, “Applications of Fourier analysis to the visibility of gratings,”J. Physiol. (London) 197, 551–556 (1968).

C. Enroth-Cugell, J. G. Robson, “The contrast sensitivity of retinal ganglion cells of the cat,”J. Physiol. London 187, 517–552 (1966).
[PubMed]

Rosenfeld, A.

A. Rosenfeld, “Quadtrees and pyramids: hyerarchical representation of images,” (University of Maryland, College Park, Md., 1982).

Stansfield, J. L.

J. L. Stansfield, “Conclusions from the commodity expert project,” Artificial Intelligence Memo 601 (Massachusetts Institute of Technology, Cambridge, Mass., 1980).

Ullman, S.

Witkin, A.

A. Witkin, “Scale-space filtering,” presented at the International Joint Conference on Artificial Intelligence, Karlsruhe, Federal Republic of Germany, 1983.

J. Babaud, A. Witkin, R. Duda, “Uniqueness of the Gaussian kernel for scale-space filtering,” (Fairchild Artificial Intelligence Laboratory, Palo Alto, Calif., 1983).

Yuille, A. L.

A. L. Yuille, T. Poggio, “Fingerprints and their slope,” Artificial Intelligence Memo 752 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

A. L. Yuille, T. Poggio, “Scaling theorems for zero-crossings,” Artificial Intelligence Memo 722 (Massachusetts Institute of Technology, Cambridge, Mass., June1983).

A. L. Yuille, T. Poggio, “Fingerprints and the psychophysics of gratings,” Artificial Intelligence Memo 751 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

A. L. Yuille, “Zero-crossings and lines of curvature,” Artificial Intelligence Memo 718 (Massachusetts Institute of Technology, Cambridge, Mass., 1983).

A. L. Yuille, T. Poggio, “Fingerprints theorems for zero-crossings,” Artificial Intelligence Memo 730 (Massachusetts Institute of Technology, Cambridge, Mass., October1983).

A. L. Yuille, T. Poggio, “Fingerprints theorems,” presented at the Conference on Artificial Intelligence, Austin, Texas, 1984.

Zucker, S. W.

S. W. Zucker, R. A. Hummel, “Receptive fields and the reconstruction of visual information,” (Courant Institute, New York, N.Y., 1983).

Art. Intell. (1)

H. K. Nishihara, “Intensity, visible-surface, and volumetric representations,” Art. Intell. 17, 265–284 (1981).
[CrossRef]

Bell Syst. Tech. J. (1)

B. F. Logan, “Information in the zero crossings of bandpass signals,” Bell Syst. Tech. J. 56, 487–510 (1977).

Comput. Vision Graph. Inf. Process (1)

W. E. L. Grimson, “Surface consistency constants in vision,” Comput. Vision Graph. Inf. Process, 24, 28–51 (1983).
[CrossRef]

J. Opt. Soc. Am. (1)

J. Physiol. (London) (1)

F. W. Campbell, J. G. Robson, “Applications of Fourier analysis to the visibility of gratings,”J. Physiol. (London) 197, 551–556 (1968).

J. Physiol. London (1)

C. Enroth-Cugell, J. G. Robson, “The contrast sensitivity of retinal ganglion cells of the cat,”J. Physiol. London 187, 517–552 (1966).
[PubMed]

Phil. Trans. R. Soc. London Ser. B (1)

D. Marr, “Early processing of visual information,” Phil. Trans. R. Soc. London Ser. B 275, 483–524 (1976).
[CrossRef]

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

D. Marr, E. Hildreth, “Theory of edge detection,” Proc.R. Soc. London Ser. B, 207, 187–217 (1980).
[CrossRef]

Other (21)

J. L. Crowley, “A representation for visual information,” (Robotics Institute, Carnegie-Mellon University, Pittsburgh, Pa., 1982).

A. Rosenfeld, “Quadtrees and pyramids: hyerarchical representation of images,” (University of Maryland, College Park, Md., 1982).

D. Marr, Vision, A Computational Investigation into the Human Representation and Processing of Visual Information (Freeman, San Francisco, Calif., 1982).

A. L. Yuille, “Zero-crossings and lines of curvature,” Artificial Intelligence Memo 718 (Massachusetts Institute of Technology, Cambridge, Mass., 1983).

R. A. Hummel, Courant Institute, New York, N.Y. (personal communication).

A. L. Yuille, T. Poggio, “Fingerprints and their slope,” Artificial Intelligence Memo 752 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

W. E. L. Grimson, From Images to Surfaces (MIT Press, Cambridge, Mass., 1981).

T. Poggio, H. K. Nishihara, K. R. K. Nielsen, “Zero-crossings and spatiotemporal interpolation in vision: aliasing and electrical coupling between sensors,” Artificial Intelligence Memo 675 (Massachusetts Institute of Technology, Cambridge, Mass., May1982).

A. Witkin, “Scale-space filtering,” presented at the International Joint Conference on Artificial Intelligence, Karlsruhe, Federal Republic of Germany, 1983.

J. L. Stansfield, “Conclusions from the commodity expert project,” Artificial Intelligence Memo 601 (Massachusetts Institute of Technology, Cambridge, Mass., 1980).

J. Babaud, A. Witkin, R. Duda, “Uniqueness of the Gaussian kernel for scale-space filtering,” (Fairchild Artificial Intelligence Laboratory, Palo Alto, Calif., 1983).

A. L. Yuille, T. Poggio, “Scaling theorems for zero-crossings,” Artificial Intelligence Memo 722 (Massachusetts Institute of Technology, Cambridge, Mass., June1983).

A. L. Yuille, T. Poggio, “Fingerprints theorems for zero-crossings,” Artificial Intelligence Memo 730 (Massachusetts Institute of Technology, Cambridge, Mass., October1983).

J. Koenderink, University of Utrecht, Utrecht, The Netherlands (personal communication, 1984).

Clearly, the scale-map fingerprint cannot always be a more compact description of the signal than the signal itself, unless the signal is redundant in precisely the way that the fingerprint representation can exploit. We expect this to be the case for images, if an appropriate differential operator is used, because images are not a purely random array of numbers. Usually images consist of rather homogeneous regions that do not change much over significant scale intervals.

H. Asada, M. Brady, “The curvature primal sketch,” Artificial Intelligence Memo 758 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

A. L. Yuille, T. Poggio, “Fingerprints and the psychophysics of gratings,” Artificial Intelligence Memo 751 (Massachusetts Institute of Technology, Cambridge, Mass., 1984).

A. L. Yuille, T. Poggio, “Fingerprints theorems,” presented at the Conference on Artificial Intelligence, Austin, Texas, 1984.

S. W. Zucker, R. A. Hummel, “Receptive fields and the reconstruction of visual information,” (Courant Institute, New York, N.Y., 1983).

This argument cannot be applied when all zero-crossing contours are vertical straight lines: It is impossible to reconstruct the signal.20 In this case the matrices in Eqs. (3.3.1) and (3.3.2) take simple forms.

A. Albert, Regression and the Moore–Penrose Pseudoinverse (Academic, New York, 1982).

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.


Metrics