Method of and apparatus for improved image correlation

• US 5,703,970 A
• Filed: 06/07/1995
• Issued: 12/30/1997
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Laser Signals LLC (Intellectual Ventures LLC)
• Original Assignee: Martin Marietta Corporation
• Inventors: Atashroo, M. Ali
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/487,832
• Time in Patent Office: 937 Days
• Field of Search: 382/278, 382/276, 382/218, 382/280, 382/277, 364/726, 364/728.03, 364/728.05
• US Class Current: 382/278
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation

Abstract

A method of and apparatus for computing correlating images using the one dimensional Fast Fourier Transform (FFT) and the symmetry property of the Fourier Transform. In one aspect, the invention is a method of correlating images in the form of a pair of real number arrays. Apparatus for carrying the method out is also disclosed and claimed.

Claims

1. A method of correlating a first image and a second image, said first image being in the form of a first real array having a size M by N and said second image being in the form of a second real array having a size M by N, M and N being positive integers, the method comprising the computer implemented steps of:

(a) performing a first domain transform on said first real array to produce a first complex array having a size M by (N/2+1);

(b) performing a second domain transform on said second real array to produce a second complex array having a size M by (N/2+1);

(c) multiplying a conjugate of said first complex array by said second complex array to produce an intermediate complex array having a size M by (N/2 +1);

(d) performing a first inverse domain transform on each of the columns of the intermediate complex array to produce an inverse transformed intermediate complex array;

(e) producing an supplemented complex array having size M by N from said inverse transformed intermediate complex array by determining elements for additional columns by symmetry for each row;

(f) performing a second inverse domain transform on each of the M rows of said supplemented complex array to produce a real correlation matrix having a size M by N; and

(g) correlating said first image and said second image on the basis of said real correlation matrix.

2. A method of correlating a first image and a second image as claimed in claim 1, wherein said first and second domain transforms are performed concurrently.

3. A method of correlating a first image and a second image as claimed in claim 1, wherein said first and second domain transforms are performed successively.

4. A method of correlating a first image and a second image as claimed in claim 1, wherein said first and second domain transforms are real two dimensional fast fourier transforms.

5. A method of correlating a first image and a second image as claimed in claim 4, wherein said first and second inverse domain transforms are inverse fast fourier transforms.

6. A method of correlating a first image and a second image as claimed in claim 1, wherein said first image is an image of a scene and said second image is an image of said scene at a later time, comprising additional steps before said step (a) of:

acquiring said first image at a first time; and

acquiring said second image at a second time later than said first time, and wherein said step (g) comprises tracking an object in said scene on the basis of said real correlation matrix.

7. A method of correlating a first image and a second image as claimed in claim 1, wherein said first image is a predetermined reference image and said second image is an acquired image of a scene, comprising additional steps before said step (a) of:

storing said first image at a first time; and

acquiring said second image at a second time later than said first time, and wherein said step (g) comprises recognizing an object in said scene on the basis of said real correlation matrix.

8. A method of correlating a first image and a second image as claimed in claim 1, comprising an additional step after said step (g) of displaying results of said correlating.

9. A method of correlating a first image and a second image as claimed in claim 1, comprising an additional step after said step (g) of storing said real correlation matrix.

10. Apparatus for correlating a first image and a second image, said first image being in the form of a first real array having a size M by N and said second image being in the form of a second real array having a size M by N, M and N being positive integers, the apparatus comprising:

a first domain transformer for performing a first domain transform on said first real array to produce a first complex array having a size M by (N/2+1);

a second domain transformer for performing a second domain transform on said second real array to produce a second complex array having a size M by (N/2 +1);

a multiplier, responsive to said first domain transformer and said second domain transformer, for multiplying a conjugate of said first complex array by said second complex array to produce an intermediate complex array having a size M by (N/2+1);

first inverse domain transform means, responsive to the multiplier, for performing a first inverse domain transform on each of the columns of the intermediate complex array to produce an inverse transformed intermediate complex array;

supplementing means, responsive to the first inverse domain transform means, for producing a supplemented complex array having size M by N from said inverse transformed intermediate complex array by determining elements for additional columns by symmetry for each row;

second inverse domain transform means, responsive to the supplementing means, for performing a second inverse domain transform on each of the M rows of the completed complex array to produce a real correlation matrix having a size M by N; and

correlating means, responsive to the second inverse transform means, for correlating said first image and said second image on the basis of said real correlation matrix.

11. Apparatus as claimed in claim 10, wherein said first and second domain transformers perform real two dimensional fast fourier transforms.

12. Apparatus as claimed in claim 11, wherein said first and second inverse domain transformers perform inverse fast fourier transforms.

13. Apparatus as claimed in claim 10, wherein said first image is an image of a scene and said second image is an image of said scene at a later time, wherein said apparatus further comprises means for acquiring said first image and said second image at successive times, and wherein said correlating means comprises means for tracking an object in said scene on the basis of results of said real correlation matrix.

14. Apparatus as claimed in claim 10, wherein said first image is a predetermined reference image and said second image is an acquired image of a scene, wherein said apparatus further comprises means for storing said first image at a first time and means for acquiring said second image at a second time later than said first time, and wherein said correlating means comprises means for recognizing an object in said scene on the basis of results of said real correlation matrix.

15. Apparatus as claimed in claim 10, further comprising means, responsive to said correlating means, for displaying results of said correlating.

16. Apparatus as claimed in claim 10, further comprising means, responsive to said correlating means, for storing said real correlation matrix.