Positional, rotational and scale invariant optical correlation method and apparatus

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
32Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. A method for correlating two functions f_{1} (x,y) and f_{2} (x,y) which are scaled and rotated versions of each other, comprising the steps ofobtaining F_{1} (ω

_{x},ω
_{y}), and F_{2} (ω
_{x},ω
_{y}), the magnitudes of the Fourier transforms of these functions;
performing a polar coordinate conversion on F_{1} (ω
_{x},ω
_{y}) and F_{2} (ω
_{x},ω
_{y}) thereby to obtain the functions F_{1} (r,θ
) and F_{2} (r,θ
);
logarithmically scaling the coordinate r in the functions F_{1} (r,θ
) and F_{2} (r,θ
) thereby to obtain the functions F_{1} (e.sup.ρ
,θ
) and F_{2} (e.sup.ρ
,θ
);
Fourier transforming F_{1} (e.sup.ρ
,θ
) and F_{2} (e.sup.ρ
,θ
) thereby to obtain the Mellin transforms M_{1} (ω
.sub.ρ
,ω
.sub.θ
) and M_{2} (ω
.sub.ρ
,ω
.sub.θ
);
obtaining the conjugate Mellin transform M_{1} *(ω
.sub.ρ
,ω
.sub.θ
);
producing the product M_{1} *M_{2} ;
Fourier transforming said product, all of the aforementioned steps being performed by optical or electrooptical means; and
recording on film the results of said lastmentioned Fourier transformation.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and electrooptical apparatus for correlating two functions, f_{1} (x,y) and f_{2} (x,y) which are shifted, scaled and rotated versions of each other without loss of signaltonoise and signaltoclutter ratios as compared to the autocorrelation case. The coordinates of two correlation peaks provide an indication of the scale and orientation differences between the two functions. In performing the method, the magnitudes of the Fourier transforms of the functions are obtained, F_{1} (ω_{x}, ω_{y}) and F_{2} (ω_{x},ω_{y}) and then a polar coordinate conversion is performed, and the resultant functions F_{1} (r,θ) and F_{2} (r,θ) are logarithmically scaled in the r coordinate. The functions thus produced F_{1} (e.sup.ρ,θ) and F_{2} (e.sup.ρ,θ) are Fourier transformed to produce the Mellin transforms M_{1} (ω.sub.ρ, ω.sub.θ) and M_{2} (ω.sub.ρ,ω.sub.θ). The conjugate of one of these Mellin transforms is obtained, and the product of this conjugate with the other Mellin transform is produced and, subsequently, Fourier transformed to complete the correlation process.
39 Citations
View as Search Results
Speculative address translation for processor using segmentation and optional paging  
Patent #
US 7,831,799 B1
Filed 11/01/2004

Current Assignee
Intellectual Ventures Funding LLC

Sponsoring Entity
Intellectual Ventures Funding LLC

Authentication system and method  
Patent #
US 7,317,814 B2
Filed 11/28/2003

Current Assignee
Physical Optics Corporation

Sponsoring Entity
Physical Optics Corporation

Method and computer program for detecting rotation and magnification of images  
Patent #
US 6,711,303 B1
Filed 12/01/1999

Current Assignee
Intellectual Ventures Fund 83 LLC

Sponsoring Entity
Eastman Kodak Company

Authentication system and method  
Patent #
US 6,744,909 B1
Filed 08/19/1999

Current Assignee
Intellisense Systems Inc.

Sponsoring Entity
Physical Optics Corporation

Magnetic resonance image correction method and magnetic resonance imaging apparatus using the same  
Patent #
US 6,076,004 A
Filed 09/05/1996

Current Assignee
Toshiba Medical Systems Corporation

Sponsoring Entity
Toshiba Corporation

Adaptive or a priori filtering for detection of signals corrupted by noise  
Patent #
US 5,943,170 A
Filed 08/24/1995

Current Assignee
Hanni Inbar, Emanuel Marom

Sponsoring Entity
Hanni Inbar, Emanuel Marom

Method of and apparatus for improved image correlation  
Patent #
US 5,703,970 A
Filed 06/07/1995

Current Assignee
Laser Signals LLC

Sponsoring Entity
Lockheed Martin Corporation

Optical information processing apparatus and method for using computer generated hologram  
Patent #
US 5,497,433 A
Filed 05/12/1995

Current Assignee
Matsushita Electric Industrial Company Limited

Sponsoring Entity
Matsushita Electric Industrial Company Limited

Classifying faces  
Patent #
US 5,561,718 A
Filed 10/24/1994

Current Assignee
US Philips Corporation

Sponsoring Entity
US Philips Corporation

Optical information processing apparatus and method using computer generated hologram  
Patent #
US 5,386,378 A
Filed 10/28/1992

Current Assignee
Matsushita Electric Industrial Company Limited

Sponsoring Entity
Matsushita Electric Industrial Company Limited

Joint transform correlator using a 4F lens system to achieve virtual displacement along the optical axis  
Patent #
US 5,438,632 A
Filed 06/25/1993

Current Assignee
The United States of America As Represented By The Secretary of Agriculture

Sponsoring Entity
The United States of America As Represented By The Secretary of Agriculture

Logarithmic polar coordinate transforming method, vision recognizing method, and optical information processing apparatus  
Patent #
US 5,343,415 A
Filed 10/19/1992

Current Assignee
Matsushita Electric Industrial Company Limited

Sponsoring Entity
Matsushita Electric Industrial Company Limited

Method of removing spurious responses from optical joint transform correlators  
Patent #
US 5,367,579 A
Filed 06/25/1993

Current Assignee
The United States of America As Represented By The Secretary of Agriculture

Sponsoring Entity
The United States of America As Represented By The Secretary of Agriculture

Optical processor for pulse train identification  
Patent #
US 5,187,598 A
Filed 08/26/1991

Current Assignee
United Technologies Corporation

Sponsoring Entity
United Technologies Corporation

Method and apparatus for optically evaluating the conformance of unknown objects to predetermined characteristics  
Patent #
US 5,078,501 A
Filed 02/05/1990

Current Assignee
E. I. du Pont de Nemours and Company

Sponsoring Entity
E. I. du Pont de Nemours and Company

Image enhanced optical correlator system  
Patent #
US 5,107,351 A
Filed 02/16/1990

Current Assignee
Grumman Aerospace Corporation

Sponsoring Entity
Grumman Aerospace Corporation

Transform optical processing system  
Patent #
US 5,159,474 A
Filed 01/18/1990

Current Assignee
E. I. du Pont de Nemours and Company

Sponsoring Entity
E. I. du Pont de Nemours and Company

Positioning controlling device  
Patent #
US 4,992,711 A
Filed 02/12/1990

Current Assignee
Toyoda Koki Kabushiki Kaisha

Sponsoring Entity
Toyoda Koki Kabushiki Kaisha

Spatial symmetry cueing image processing method and apparatus  
Patent #
US 5,020,111 A
Filed 10/14/1988

Current Assignee
United States Of America As Represented By The Secretary Of The Army

Sponsoring Entity
United States Of America As Represented By The Secretary Of The Army

Position, rotation, and intensity invariant recognizing method  
Patent #
US 4,838,644 A
Filed 09/15/1987

Current Assignee
The United States of America As Represented By The Secretary of Agriculture

Sponsoring Entity
The United States of America As Represented By The Secretary of Agriculture

Automatic classification of images  
Patent #
US 4,881,270 A
Filed 10/28/1983

Current Assignee
The United States of America As Represented By The Secretary of Agriculture

Sponsoring Entity
The United States of America As Represented By The Secretary of Agriculture

Preprocessor for spectral pattern classification systems  
Patent #
US 4,783,754 A
Filed 07/02/1984

Current Assignee
Motorola Inc.

Sponsoring Entity
Motorola Inc.

Xray image correction apparatus  
Patent #
US 4,636,953 A
Filed 05/04/1984

Current Assignee
KABUSHIKI KAISHA TOSHIBA 72 HORIKAWACHO SAIWAIKU KAWASAKISHI JAPAN A CORP OF JAPAN

Sponsoring Entity
KABUSHIKI KAISHA TOSHIBA 72 HORIKAWACHO SAIWAIKU KAWASAKISHI JAPAN A CORP OF JAPAN

Topographic feature extraction using sensor array system  
Patent #
US 4,590,608 A
Filed 05/30/1980

Current Assignee
United States Of America As Represented By The Secretary Of The Army

Sponsoring Entity
United States Of America As Represented By The Secretary Of The Army

Method and apparatus for determining conformity of a predetermined shape related characteristics of an object or stream of objects by shape analysis  
Patent #
US 4,624,367 A
Filed 04/20/1984

Current Assignee
Exxon Research and Engineering Company

Sponsoring Entity
Exxon Research and Engineering Company

Image comparison system  
Patent #
US 4,513,441 A
Filed 08/02/1983

Current Assignee
SPARTA Inc.

Sponsoring Entity
SPARTA Inc.

Apparatus for correcting image distortions automatically by interimage processing  
Patent #
US 4,558,462 A
Filed 08/31/1983

Current Assignee
Hitachi Medical Corporation

Sponsoring Entity
Hitachi Medical Corporation

Machine vision system utilizing programmable optical parallel processing  
Patent #
US 4,462,046 A
Filed 07/02/1982

Current Assignee
Robert L. Jones Jr

Sponsoring Entity
AMAF INDUSTRIES INCORPORATED

Method of multivariant intraclass pattern recognition  
Patent #
US 4,487,476 A
Filed 04/28/1981

Current Assignee
The United States of America As Represented By The Secretary of Agriculture

Sponsoring Entity
The United States of America As Represented By The Secretary of Agriculture

Apparatus for correlating successive images of a scene  
Patent #
US 4,368,456 A
Filed 01/09/1980

Current Assignee
EMI

Sponsoring Entity
EMI

Image processing system  
Patent #
US 4,267,573 A
Filed 06/14/1978

Current Assignee
Old Dominion University Research Foundation

Sponsoring Entity
Old Dominion University Research Foundation

Multipleinvariant spacevariant optical processing  
Patent #
US 4,308,521 A
Filed 02/12/1979

Current Assignee
United States Of America As Represented By The Secretary Of The Air Force

Sponsoring Entity
United States Of America As Represented By The Secretary Of The Air Force

Coherent optical processor apparatus with improved fourier transform plane spatial filter  
Patent #
US 3,891,968 A
Filed 04/04/1974

Current Assignee
Sperry Rand Corporation

Sponsoring Entity
Sperry Rand Corporation

Method for correlating frequencymodulated signals  
Patent #
US 3,903,407 A
Filed 12/11/1963

Current Assignee
the united states of america as represented by the secretary of the navy

Sponsoring Entity
the united states of america as represented by the secretary of the navy

MULTIDIMENSIONAL FOURIER TRANSFORM OPTICAL PROCESSOR  
Patent #
US 3,872,293 A
Filed 07/30/1973

Current Assignee
the united states of america as represented by the secretary of the navy

Sponsoring Entity
the united states of america as represented by the secretary of the navy

VECTOR GENERATOR UTILIZING AN EXPONENTIAL ANALOGUE OUTPUT SIGNAL  
Patent #
US 3,772,563 A
Filed 11/09/1972

Current Assignee
National Computer Services Limited

Sponsoring Entity
Vector General Inc. Canoga Park CA

COHERENT OPTICAL MULTICHANNEL CORRELATOR  
Patent #
US 3,776,616 A
Filed 10/10/1972

Current Assignee
Siemens AG

Sponsoring Entity
Siemens AG

PATTERN RECOGNITION APPARATUS AND METHODS INVARIANT TO TRANSLATION, SCALE CHANGE AND ROTATION  
Patent #
US 3,614,736 A
Filed 05/21/1968

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

METHOD OF AND APPARATUS FOR OPTICAL MULTIPLE FILTERING  
Patent #
US 3,794,406 A
Filed 09/11/1972

Current Assignee
US Philips Corporation

Sponsoring Entity
US Philips Corporation

10 Claims
 1. A method for correlating two functions f_{1} (x,y) and f_{2} (x,y) which are scaled and rotated versions of each other, comprising the steps of
obtaining F_{1} (ω  _{x},ω
_{y}), and F_{2} (ω
_{x},ω
_{y}), the magnitudes of the Fourier transforms of these functions;performing a polar coordinate conversion on F_{1} (ω
_{x},ω
_{y}) and F_{2} (ω
_{x},ω
_{y}) thereby to obtain the functions F_{1} (r,θ
) and F_{2} (r,θ
);logarithmically scaling the coordinate r in the functions F_{1} (r,θ
) and F_{2} (r,θ
) thereby to obtain the functions F_{1} (e.sup.ρ
,θ
) and F_{2} (e.sup.ρ
,θ
);Fourier transforming F_{1} (e.sup.ρ
,θ
) and F_{2} (e.sup.ρ
,θ
) thereby to obtain the Mellin transforms M_{1} (ω
.sub.ρ
,ω
.sub.θ
) and M_{2} (ω
.sub.ρ
,ω
.sub.θ
);obtaining the conjugate Mellin transform M_{1} *(ω
.sub.ρ
,ω
.sub.θ
);producing the product M_{1} *M_{2} ; Fourier transforming said product, all of the aforementioned steps being performed by optical or electrooptical means; and recording on film the results of said lastmentioned Fourier transformation.  View Dependent Claims (2, 3, 4, 5, 6)
 _{x},ω
 7. A method for correlating two functions f_{1} (x,y) and f_{2} (x,y) which are scaled and rotated versions of each other, comprising the steps of
producing an optical representation of F_{2} (ω  _{x},ω
_{y}), the magnitude of the Fourier transform of f_{2} (x,y);performing a polar coordinate conversion on this representation of F_{2} (ω
_{x},ω
_{y}) thereby to obtain an optical representation of the function F_{2} (r,θ
);logarithmically scaling the coordinate r in the function F_{2} (r,θ
) thereby to obtain an optical representation of the function F_{2} (e.sup.ρ
,θ
);Fourier transforming F_{2} (e.sup.ρ
,θ
) thereby to obtain a light distribution pattern corresponding to the Mellin transform M_{2} (ω
.sub.ρ
,ω
.sub.θ
);pouring a film transparency having an interference pattern recorded therein which contain a term that is proportional to the conjugate Mellin transform M_{1} *(ω
.sub.ρ
,ω
.sub.θ
);illuminating said film transparency with said light distribution pattern thereby to produce a light distribution pattern corresponding to the produce M_{1} *M_{2} ; Fourier transforming said lastmentioned light pattern; and
recording the results thereof.
 _{x},ω
 8. Apparatus for correlating two functions f_{1} (x,y) and f_{2} (x,y) which are shifted, scaled and rotated versions of each other, comprising in combination
an optical correlator having an input plane P_{0}, a frequency plane P_{1} and an output plane P_{2} ; a film transparency having an interference pattern recorded therein which contain a term proportional to the conjugate Mellin transform M_{2} *(ω
.sub.ρ
,ω
.sub.θ
), said film transparency being positioned at plane P_{1} ;means for creating a light pattern leaving plane P_{0} that corresponds to F_{1} (e.sup.ρ
,θ
),said light pattern being Fourier transformed by lens means within said correlator located between planes P_{0} and P_{1} and the illumination of said film transparency by the resultant light pattern producing a light pattern leaving plane P_{1} that corresponds to the product M_{2} *(ω
.sub.ρ
,ω
.sub.θ
) M_{1} (ω
.sub.ρ
,ω
.sub.θ
),said lastmentioned light pattern being Fourier transformed by other lens means within said correlator located between planes P_{1} and P_{2} ; and means positioned at plane P_{2} for recording the results of said lastmentioned Fourier transformation.
 9. Apparatus for correlating two functions f_{1} (x,y) and f_{2} (x,y) which are shifted, scaled and rotated versions of each other, comprising
optical means for Fourier transforming f_{1} (x,y) so as to obtain F_{1} (ω  _{x},ω
_{y}), the magnitude of the Fourier transform of this function;means for performing a polar coordinate conversion on F_{1} (ω
_{x},ω
_{y}) so as to obtain the function F_{1} (r,θ
);
means for logarithmically scaling the r coordinate in the function F_{1} (r,θ
) so as to obtain F_{1} (e.sup.ρ
,θ
), F_{1} (ω
_{x},ω
_{y}), F_{1} (r,θ
) and F_{1} (e.sup.ρ
,θ
) occurring as optical images;optical means for Fourier transforming F_{1} (e.sup.ρ
,θ
) so as to obtain a light pattern corresponding to the Mellin transform M_{1} (ω
.sub.ρ
,ω
.sub.θ
);a film transparency having an interference pattern recorded therein which contains an optical representation of the conjugate Mellin transform M_{2} *(ω
.sub.ρ
,ω
.sub.θ
);means for illuminating said film transparency with said light pattern so as to obtain a light pattern corresponding to M_{1} M_{2} *; optical means for Fourier transforming said lastmentioned light pattern; and means for recording the results thereof.  View Dependent Claims (10)
 _{x},ω
1 Specification
The present invention relates generally to optical pattern recognition systems, and, more particularly, to optical correlation apparatus and methods utilizing transformations that are shift, scale and rotationally invariant.
In the correlation of 2D information, the signaltonoise ratio of the correlation peak decreases significantly when there are scale and rotational differences in the data being compared. For example, in one case of a 35 mm transparency of an aerial image with about 5 to 10 lines/mm resolution, this ratio decreased from 30 db to 3 db with a 2 percent scale change and a similar amount with a 3.5° rotation.
Several methods have been advanced for overcoming the signal losses associated with the scale, shift and rotational discrepancies encountered in optical comparison systems. One proposed solution involves the storage of a plurality of multiplexed holographic spatial filters of the object at various scale changes and rotational angles. Although theoretically feasible, this approach suffers from a severe loss in diffraction efficiency which is proportional to the square of the number of stored filters. In addition, a precise synthesis system is required to fabricate the filter bank, and a high storage density recording medium is needed.
A second proposed solution involves positioning the input behind the transform lens. As the input is moved along the optic axis the transform is scaled. Although useful in laboratory situations, this method is only appropriate for comparatively small scale changes, i.e., 20 percent or less. Also, since this method involves mechanical movement of components, it cannot be employed in those applications where the optical processor must possess a real time capability.
Mechanical rotation of the input can, of course, be performed to compensate for orientation errors in the data being compared. However, the undesirable consequences of having to intervene in the optical system are again present.
In applicants'"'"' copending application, Ser. No. 707,977, filed July 23 1976, there are disclosed correlation methods and apparatus which use Mellin transforms that are scale and shift invariant to compensate for scale differences in the data being compared. The systems therein disclosed, however, do not compensate for orientation errors in this data.
It is, accordingly, an object of the present invention to provide a transformation which is invariant to shift, scale and orientational changes in the input.
Another object of the present invention is to provide an optical correlation method and apparatus for use with 2D data having shift, scale and rotational differences.
Another object of the present invention is to provide a method of crosscorrelating two functions which are scale and rotated versions of one another where the correlation peak has the same signaltonoise ratio as the autocorrelation peak.
Another object of the present invention is to provide an electrooptic correlator whose performance is not degraded by scale and orientational differences in the data being compared and which provides information indicative of the magnitudes of these differences.
Other objects, advantages and novel features of the invention will become apparent from the following detailed description of the invention when considered in conjunction with the accompanying drawings wherein:
FIG. 1 is a block diagram illustrating a positional, rotational and scale invariant transformation system;
FIG. 2 is a block diagram illustrating the real time implementation of the transformation of FIG. 1;
FIG. 3 shows the sequence of operations carried out in the crosscorrelation method of the present invention;
FIG. 4 shows a correlation configuration for practicing the method of FIG. 3; and
FIG. 5 shows the correlation peaks appearing in the output plane of the correlator of FIG. 4.
The present invention provides a solution for the shift, scale and rotational differences between the input and reference data by utilizing a transformation which is itself invariant to shift, scale and orientational changes in the input. As shown in FIG. 1, the first step in the synthesis of such a transformation is to form the magnitude of the Fourier transform F(ω_{x},ω_{y}) of the input function f(x,y). This eliminates the effects of any shifts in the input and centers the resultant light distribution on the optical axis of the system.
Any rotation of f(x,y) rotates F (ω_{x},ω_{y}) by the same angle. However, a scale change in f(x,y) by "a" scales F(ω_{x},ω_{y}) by 1/a.
The effects of rotation and scale changes in the light distribution resulting from the Fourier transform of f (x,y) can be separated by performing a polar transformation on F(ω_{x},ω_{y}) from (ω_{x},ω_{y}) coordinates to (r,θ) coordinates. Since θ = tan^{1} (ω_{y} /ω_{x}) and r = (ω_{x}^{2} +ω_{y}^{2})^{1/2}, a scale change in F by "a" does not affect the θ coordinate and scales the r coordinate directly to r = ar. Consequently, a 2D scaling of the input function is reduced to a scaling in only one dimension, the r coordinate, in this transformed F(r,θ) function.
If a 1D Mellin transform in r is now performed on F'"'"'(r, θ), a completely scale invariant transformation results. This is due to the scale invariant property of the Mellin transform.
The 1D Mellin transform of F(r, θ) in r is given by ##EQU1## where ρ = ln r. The Mellin transform of the scaled function F" = F(ar,θ) is then
M'"'"' (ω.sub.ρ,θ) = a.sup.jω ρM(ω.sub.ρ,θ)
from which the magnitudes of the two transforms are seen to be identical. One arrangement for optically implementing the Mellin transform is disclosed in applicants'"'"' copending application, aboveidentified, and there it is shown that ##EQU2## where ρ = ln r. From equation (3), it can be seen that the realization of the required optical Mellin transform simply requires a logarithmic scaling of the r coordinate followed by a 1D Fourier transform in r. This follows from equation (3) since M(ω.sub.ρ,θ) is the Fourier transform of F(expρ,θ).
The rotation of the input function f(x,y) by an angle θ_{0} will not affect the r coordinate in the (r,θ) plane. If, for example, the input F(ω_{x},ω_{y}) is partitioned into two sections F_{1} (ω_{x},ω_{y}), F_{2} (ω_{x},ω_{y}) where F_{2} is a segment of F that subtends an angle θ_{0}, the effects of a rotation by θ_{0} is an upward shift in F_{1} (r,θ) by θ_{0} and a downward shift in F_{2} (r,θ) by 2π  θ_{0}. Thus, while the polar transformation has converted a rotation in the input to a shift in the transform space, the shift is not the same for all parts of the function.
These shifts in F(r,θ) space due to a rotation in the input can be converted to phase factors by performing a 1D Fourier transform on F(r,θ).
The final Fourier transform shown in FIG. 1 is a 2D transform in which the Fourier transform in ρ is accomplished to effect scale invariance by the Mellin transform and the Fourier transform in θ is used to convert the shifts due to θ_{0} to phase terms. The resultant function is, thus, a Mellin transform in r, and, hence, it is denoted by M in FIG. 1.
If the complete transformation of f(x,y) is represented by
M (ω.sub.ρ,ω.sub.θ) = m_{1} (ω.sub.ρ,ω.sub.θ) + m_{2} (ω.sub.ρ,ω.sub.θ) (4)
the transformation of the function f'"'"'(x,y), which is scaled by "a" and rotated by θ_{0} is given by
M'"'"'(ω.sub.ρ,ω.sub.θ) = M.sub.1 (ω.sub.ρ,ω.sub.θ) exp[j(ω.sub.ρ lna+ω.sub.ρ θ.sub.0)] (5)
+ M_{2} (ω.sub.ρ,ω.sub.θ) exp{j[ω.sub.ρ lnaω.sub.θ (2πθ_{0})]}
The positional, rotational and scale invariant (PRSI) correlation is based on the form of equations (4) and (5). If the product M*M'"'"' is formed, we obtain
M*M'"'"' = M*M.sub.1 exp[j(ω.sub.ρ lna+ω.sub.θ θ.sub.0)] (6)
+M*M_{2} exp{j[ω.sub.ρ lnaω.sub.θ (2πθ_{0})]}
The Fourier transform of equation (6) is
f.sub.1 * f * δ(ρ'"'"'lna) * δ(θ'"'"'θ.sub.0) + f * f.sub.2 * δ(ρ'"'"'lna) * δ(θ'"'"'+2πθ.sub.0) (7)
The δ functions in equation (7) identify the locations of the correlation peaks, one at ρ'"'"' = ln a, θ'"'"' = θ_{0} ; the other at ρ'"'"' = ln a, θ'"'"' = (2π+θ_{0}). Consequently, the ρ'"'"' coordinate of the peaks is proportional to the scale change "a" and the θ'"'"' coordinate is porportional to the rotational angle θ_{0}.
The Fourier transform of equation (6) thus consists of two terms:
(a) the crosscorrelation F_{1} (expρ,θ) * F(expρ,θ) located, as indicated above, at ρ'"'"' = ln a and θ'"'"' = θ_{0} ;
(b) the crosscorrelation F_{2} (expρ,θ) F(expρ,θ) located at ρ'"'"' = ln a and θ'"'"' = (2π+θ_{0}), where the coordinates of this output Fourier transform plane are (ρ'"'"',θ'"'"').
If the intensities of these two crosscorrelation peaks are summed, the result is the autocorrelation of F(expρ,θ). Therefore, the crosscorrelation of two functions that are scaled and rotated versions of one another can be obtained. Most important, the amplitude of this crosscorrelation will be equal to the amplitude of the autocorrelation function itself.
Referring now to FIG. 2, which illustrates one electrooptical arrangement for implementing the positional, rotational and shift invariant transformation, the input f(x,y), which may be recorded on a suitable transparency 20 or available in the form of an appropriate transmittance pattern on the target of an electronbeamaddressed spatial light modulator of the type described in the article, "Dielectric and Optical Properties of ElectronBeamAddressed KD_{2} PO_{4} " by David Casasent and William Keicher which appeared in the December 1974 issue of the Journal of the Optical Society of America, Volume 64, Number 12, is here illuminated with a coherent light beam from a suitable laser not shown and Fourier transformed by a spherical lens 21. A TV camera 22 is positioned in the back focal plane of this lens and arranged such that the magnitude of the Fourier transform [F(ω_{x},ω_{y})] constitutes the input image to this camera. As is well known, camera 22 has internal control circuits which generate the horizontal and vertical sweep voltages needed for the electron beam scanning, and these waveforms are extracted at a pair of output terminals as signals ω_{x} and ω_{y}. The video signal developed by sanning the input image is also available at a third output terminal.
Horizontal and vertical sweep voltages ω_{x} and ω_{y} are subject to signal processing in the appropriate circuits 23 and 24 to yield the quantities (1/2) ln (ω_{x}^{2} +ω_{y}^{2}) and tan^{1} (ω_{x} /ω_{y}), respectively. It will be recalled that the results of this signal processing, which may be performed in an analog or digital manner, is the polar coordinate transformation of the magnitude of the Fourier transform of the input function and its subsequent log scaling in r.
The function F(e.sup.ρ,θ) is formed on the target of an EALM tube of the type hereinbefore referred to. In this regard, the video signal from camera 22 modulates the beam current of this tube while the voltages from circuits 23 and 24 control the deflection of the electron beam. Instead of utilizing an electronbeamaddressed spatial light modulator, an optically addressed device may be used wherein the video signal modulates the intensity of the laser beam while deflection system 25 controls its scanning motion. It would also be mentioned that the transformation can also be accomplished by means of computer generated holograms.
The function M(ω.sub.ρ,ω.sub.θ) is obtained by Fourier transforming F(e.sup.ρ,θ) and this may be accomplished by illuminating the target of the EALM tube with a coherent light beam and performing a 2D Fourier transform of the image pattern.
FIG. 3 shows the sequence of steps involved in correlating two functions f_{1} (x,y) and f_{2} (x,y) that differ in position, scale and rotation. It would be mentioned that this method may be implemented by optical or digital means. Thus, all of the operations hereinafter set forth may be performed with a digital computer. However, the following description covers the optical process since it has greater utility in real time optical pattern recognition systems.
The first step of a method is to form the magnitude of the Fourier transform of both functions F_{1} (ω_{x},ω_{y})} and F_{2} (ω_{x},ω_{y})}. This may be readily accomplished, as is well known, with a suitable lens and an intensity recorder with γ = 1. Next, a polar coordinate conversion of these magnitudes is performed to produce F_{1} (r,θ) and F_{2} (r,θ). The r coordinate of these functions is now logarithmically scaled to form F_{1} (expρ,θ) and F_{2} (expρ,θ). A second Fourier transform is carried out to produce the Mellin transform of F(r,θ) in r and the Fourier transform in θ. The resultant functions being M_{1} (ω.sub.ρ,ω.sub.θ) and M_{2} (ω.sub.ρ,ω.sub.θ). The conjugate Mellin transform of F(r,θ) which is M_{1} *(ω.sub.ρ,ω.sub.θ) is formed and, for example, recorded as a suitable transparency. This can be readily accomplished by conventional holographic spatial filter synthesis methods which involve Fourier transforming F_{1} (expρ,θ) and recording the light distribution pattern produced when a plane wave interferes with this transformation.
The correlation operation involves locating the function F_{2} (expρ,θ) at the input plane of a conventional frequency plane correlator and positioning the conjugate Mellin transform recording M_{1} *(ω.sub.ρ,ω.sub.θ) at the frequency plane. The light distribution pattern leaving the frequency plane when the input plane is illuminated with a coherent light beam has as one of its terms M_{1} *M_{2} and this product when Fourier transformed completes the crosscorrelation process. The correlation of the two input functions in this method appears as two crosscorrelation peaks, and the sum of their intensities is equal to the autocorrelation peak. Thus, the correlation is performed without loss in the signaltonoise ratio. As mentioned hereinbefore, the coordinates of these crosscorrelation peaks, as shown in FIG. 5, provides an indication of the scale difference, "a", and amount of rotation between the two functions θ_{0}.
FIG. 4 shows a frequency plane correlator for forming the conjugate Mellin transform M_{1} * (ω.sub.ρ,ω.sub.θ) and for performing a crosscorrelation operation utilizing a recording of this transform. In applicants'"'"' copending application, identified hereinbefore, there is disclosed a procedure for producing a hologram corresponding to this conjugate Mellin transform, and, as noted therein, the process involves producing at the input plane P_{0}, an image corresponding to the function F_{1} (expρ,θ). This image may be present on the target of an EALM tube as an appropriate transmittance pattern. Alternatively, it may be available as a suitable transparency. In any event, the input function is illuminated with a coherent light beam from a laser source, not shown, and Fourier transformed by lens L_{1}. Its transform M_{1} (ω.sub.ρ,ω.sub.θ) is interferred with a plane reference wave which is incident at an angle Ψ and the resultant light distribution pattern is recorded. One of the four terms recorded at plane P_{1} will be proportional to M_{1} *(ω.sub.ρ,ω.sub.θ).
In carrying out the correlation, the reference beam is blocked out of the system. The hologram corresponding to the conjugate Mellin transform M_{1} *(ω.sub.ρ,ω.sub.θ) is positioned in the back focal plane of lens L_{1} at plane P_{1}. The input image present at plane P_{0} now corresponds to the function F_{2} (expρ,θ) which again may be the transmittance pattern on an EALM tube or suitable transparency. When the coherent light beam illuminates the input plane P_{0}, the light distribution incident on plane P_{1} is M_{2} (ω.sub.ρ,ω.sub.θ). One term in the distribution leaving plane P_{1} will, therefore, be M_{2} M_{1},* and the Fourier transform of this product is accomplished by lens L_{2}. In the output plane P_{2}, as shown in FIG. 5, two crosscorrelation peaks occur. Two photodetectors spaced by 2π may be utilized to detect these peaks and, as indicated hereinbefore, the sum of their amplitudes will be equal to the autocorrelation peak produced when the two images being compared have the same position, scale and orientation.
In the correlation method depicted in FIG. 3, the conjugate Mellin transform M_{1} *(ω.sub.ρ,ω.sub.θ) was produced and utilized in the frequency plane of the correlator of FIG. 4. However, it should be understood that the method can also be practiced by utilizing the conjugate Mellin transform M_{2} *(ω.sub.ρ,ω.sub.θ) at P_{1} forming the product M_{1} M_{2} * and Fourier transforming it to complete the crosscorrelation process.