# US 5,703,970 A · Method of and apparatus for improved image correlation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,703,970 A
- Document ID: US5703970A
- Status: Granted
- Kind: A
- Application number: 08/487,832
- Filed: 1995-06-07
- Granted: 1997-12-30
- Earliest claimed: 1995-06-07
- Assignees: Martin Marietta Corporation
- Inventors: M. Ali Atashroo
- Web page: https://patentgrep.com/patent/US5703970A

## CPC

- G06F 17/153: {Multidimensional correlation or convolution}
- G06V 10/431: {Frequency domain transformation; Autocorrelation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 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.

### Claim 11 (depends on 10)

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

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 10)

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.

### Claim 14 (depends on 10)

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.

### Claim 15 (depends on 10)

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

### Claim 16 (depends on 10)

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