Abstract

This paper describes some previously invented optical means for performing convolutions (i.e., correlations) of designs in two dimensions and teaches through optics the physical meaning of these functions. The paper also discusses how these operations can be used for pattern recognition and also for measuring the similarity of two patterns. It is shown how the well-known cross-correlations function,

A(uv)=1ab0a0bρ(x,y)ρ(x+u,y+v)dxdy,

is a part of a new function we call here the “similarity” function,

S(ρρ)=1ab0a0bA2(uv)dudv.

This function (having the highest value for identical patterns and lower values for dissimilar patterns) can, like the correlation function, be performed by optical means without any computation whatsoever. The mathematical discussion of the characteristics of S(ρρ′) are given. The possible role of these methods in information retrieval are suggested, and some of the limitations mentioned.

© 1962 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A complete bibliography on information retrieval and translation of languages may be obtained by writing Charles P. Bourne, Stanford Research Institute, Menlo Park, California.
  2. David O. Woodbury, Let Erma Do It (Harcourt, Brace and Company, Inc., New York, 1956).
  3. These functions are discussed in many books on Fourier analysis and on statistics. In crystallography they were introduced by Patterson and subsequently called “Patterson functions.” See A. L. Patterson, Z. Krist. 90, 517 (1935); or Dan McLachlan, X-Ray Crystal Structure (McGraw-Hill Book Company, Inc., New York, 1957), pp. 228–232.
  4. J. M. Robertson, Phil. Mag. 13, 413 (1932).
  5. W. R. Philips and D. McLachlan, Rev. Sci. Instr. 25, 123 (1954).
    [Crossref]
  6. W. Meyer-Eppler and G. Darius, Information Theory, edited by Colin Cherry (Academic Press, New York, 1956), pp. 34–36.
  7. Lawrence Bragg, Nature 154, 69 (1944).
    [Crossref]
  8. F. B. Burger, U. S. Patent2,787,188, April2, 1957.
  9. Otis M. Minot, “Automatic devices for recognition of visible two-dimensional patterns, a survey of the field,” Technical Memorandum 364 (U. S. Navy Electronics Laboratory, San Diego, California, June25, 1959).
  10. R. V. Churchill, Fourier Series and Boundary Value Problems (McGraw-Hill Book Company, Inc., New York, 1941).
  11. W. L. Bragg, Z. Krist A70, 475 (1929).
  12. M. L. Huggins, J. Am. Chem. Soc. 63, 66 (1941).
    [Crossref]
  13. Dan McLachlan and R. H. Woolley, Rev. Sci. Instr. 22, 423 (1951).
    [Crossref]

1954 (1)

W. R. Philips and D. McLachlan, Rev. Sci. Instr. 25, 123 (1954).
[Crossref]

1951 (1)

Dan McLachlan and R. H. Woolley, Rev. Sci. Instr. 22, 423 (1951).
[Crossref]

1944 (1)

Lawrence Bragg, Nature 154, 69 (1944).
[Crossref]

1941 (1)

M. L. Huggins, J. Am. Chem. Soc. 63, 66 (1941).
[Crossref]

1935 (1)

These functions are discussed in many books on Fourier analysis and on statistics. In crystallography they were introduced by Patterson and subsequently called “Patterson functions.” See A. L. Patterson, Z. Krist. 90, 517 (1935); or Dan McLachlan, X-Ray Crystal Structure (McGraw-Hill Book Company, Inc., New York, 1957), pp. 228–232.

1932 (1)

J. M. Robertson, Phil. Mag. 13, 413 (1932).

1929 (1)

W. L. Bragg, Z. Krist A70, 475 (1929).

Bragg, Lawrence

Lawrence Bragg, Nature 154, 69 (1944).
[Crossref]

Bragg, W. L.

W. L. Bragg, Z. Krist A70, 475 (1929).

Burger, F. B.

F. B. Burger, U. S. Patent2,787,188, April2, 1957.

Churchill, R. V.

R. V. Churchill, Fourier Series and Boundary Value Problems (McGraw-Hill Book Company, Inc., New York, 1941).

Darius, G.

W. Meyer-Eppler and G. Darius, Information Theory, edited by Colin Cherry (Academic Press, New York, 1956), pp. 34–36.

Huggins, M. L.

M. L. Huggins, J. Am. Chem. Soc. 63, 66 (1941).
[Crossref]

McLachlan, D.

W. R. Philips and D. McLachlan, Rev. Sci. Instr. 25, 123 (1954).
[Crossref]

McLachlan, Dan

Dan McLachlan and R. H. Woolley, Rev. Sci. Instr. 22, 423 (1951).
[Crossref]

Meyer-Eppler, W.

W. Meyer-Eppler and G. Darius, Information Theory, edited by Colin Cherry (Academic Press, New York, 1956), pp. 34–36.

Minot, Otis M.

Otis M. Minot, “Automatic devices for recognition of visible two-dimensional patterns, a survey of the field,” Technical Memorandum 364 (U. S. Navy Electronics Laboratory, San Diego, California, June25, 1959).

Patterson, A. L.

These functions are discussed in many books on Fourier analysis and on statistics. In crystallography they were introduced by Patterson and subsequently called “Patterson functions.” See A. L. Patterson, Z. Krist. 90, 517 (1935); or Dan McLachlan, X-Ray Crystal Structure (McGraw-Hill Book Company, Inc., New York, 1957), pp. 228–232.

Philips, W. R.

W. R. Philips and D. McLachlan, Rev. Sci. Instr. 25, 123 (1954).
[Crossref]

Robertson, J. M.

J. M. Robertson, Phil. Mag. 13, 413 (1932).

Woodbury, David O.

David O. Woodbury, Let Erma Do It (Harcourt, Brace and Company, Inc., New York, 1956).

Woolley, R. H.

Dan McLachlan and R. H. Woolley, Rev. Sci. Instr. 22, 423 (1951).
[Crossref]

J. Am. Chem. Soc. (1)

M. L. Huggins, J. Am. Chem. Soc. 63, 66 (1941).
[Crossref]

Nature (1)

Lawrence Bragg, Nature 154, 69 (1944).
[Crossref]

Phil. Mag. (1)

J. M. Robertson, Phil. Mag. 13, 413 (1932).

Rev. Sci. Instr. (2)

W. R. Philips and D. McLachlan, Rev. Sci. Instr. 25, 123 (1954).
[Crossref]

Dan McLachlan and R. H. Woolley, Rev. Sci. Instr. 22, 423 (1951).
[Crossref]

Z. Krist (1)

W. L. Bragg, Z. Krist A70, 475 (1929).

Z. Krist. (1)

These functions are discussed in many books on Fourier analysis and on statistics. In crystallography they were introduced by Patterson and subsequently called “Patterson functions.” See A. L. Patterson, Z. Krist. 90, 517 (1935); or Dan McLachlan, X-Ray Crystal Structure (McGraw-Hill Book Company, Inc., New York, 1957), pp. 228–232.

Other (6)

W. Meyer-Eppler and G. Darius, Information Theory, edited by Colin Cherry (Academic Press, New York, 1956), pp. 34–36.

A complete bibliography on information retrieval and translation of languages may be obtained by writing Charles P. Bourne, Stanford Research Institute, Menlo Park, California.

David O. Woodbury, Let Erma Do It (Harcourt, Brace and Company, Inc., New York, 1956).

F. B. Burger, U. S. Patent2,787,188, April2, 1957.

Otis M. Minot, “Automatic devices for recognition of visible two-dimensional patterns, a survey of the field,” Technical Memorandum 364 (U. S. Navy Electronics Laboratory, San Diego, California, June25, 1959).

R. V. Churchill, Fourier Series and Boundary Value Problems (McGraw-Hill Book Company, Inc., New York, 1941).

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

Fig. 1
Fig. 1

Showing the capital letter A with variations in position, magnification, and orientation.

Fig. 2
Fig. 2

The letter A in the domain ab with the vectors aa′, bb′, and cc′ indicated. These vectors are the same length and identically oriented so that u and v are the same for all. When the products of the densities, ρ, at the termini are multiplied, only those for aa′ give a nonzero result.

Fig. 3
Fig. 3

A schematic diagram of an optical multiplier and integrator.

Fig. 4
Fig. 4

A convenient device for performing a convolution optically. (a) The light box provides illumination for the translucent sheet or ground glass GG upon which rests the film having transparency ρ(xy), while the spacers CR support the second film for ρ′(xy) and the recording plate P. (b) A schematic representation of samples of optical paths in (a).

Fig. 5
Fig. 5

A repeating function, ρ(x) and a square pulse ready for cross-convoluting.

Fig. 6
Fig. 6

Examples of convolutions obtained by optical means. See Fig. 4(a).

Fig. 7
Fig. 7

Some autocorrelations.

Fig. 8
Fig. 8

Some interesting autocorrelations.

Fig. 9
Fig. 9

When identical designs, as in (a), are brought into coincidence (u=v=0), the common area shown in hatched lines is greater than that obtained when unlike designs, as shown in (b), are brought into maximum coincidence.

Fig. 10
Fig. 10

A schematic diagram of an automatic name finder.

Fig. 11
Fig. 11

Suggesting the manner of computing the intensity of the maxima in the convolution of: (a) two extremely different patterns, (b) two identical patterns, and (c) two identical, stylized modifications of the letter A.

Equations (12)

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

A ( u v ) = 1 a b 0 a 0 b ρ ( x , y ) ρ ( x + u , y + v ) d x d y ,
S ( ρ ρ ) = 1 a b 0 a 0 b A 2 ( u v ) d u d v .
A ( u v ) = 1 a b 0 a 0 b ρ ( x y ) ρ ( x + u , y + v ) d x d y .
A ( u v ) = 1 a b 0 a 0 b ρ ( x y ) ρ ( x + u , y + v ) d x d y .
A ( u ) = 1 a 0 a ρ ( x ) S ( x + u ) d x = 1 2 w u - w u + w ρ ( x ) d x .
A ( 00 ) = 1 a b 0 a 0 b ρ ( x y ) ρ ( x y ) d x d y = 1 a b 0 a 0 b ρ 2 ( x y ) d x d y .
j = 0 n a j = k ,
j = 0 n a j = j = 0 n ( a av + Δ a j ) = n a av ,
j = 0 n Δ a j = 0.
j = 0 n a j 2 = j = 0 n ( a av + Δ a j ) 2 = n a av 2 + 2 a av j = 0 n Δ a j + j = 0 n ( Δ a j ) 2 = k 2 n + j = 0 n ( Δ a j ) 2 .
0 a A ( u ) d u = k = 0 a [ A av + Δ A ( u ) ] d u = a A av ,
0 a A 2 ( u ) d u = [ A av + Δ A ( u ) ] 2 d u = a A av 2 + 0 a [ Δ A ( u ) ] 2 d u .