Fast fourier transform correlation tracking algorithm with background correction

• US 6,970,577 B2
• Filed: 12/19/2000
• Issued: 11/29/2005
• Est. Priority Date: 12/19/2000
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Han, Ruey-Yuan
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): Kim, Charles
• Application Number:
  US09/739,002
• Publication Number:
  US 20050163341A1
• Time in Patent Office: 1,806 Days
• Field of Search: 382/103, 382/236, 382/248, 382/280, 382/278, 244/3.15, 244/3.17, 375/240.16, 348/169, 348/699
• US Class Current: 382/103
• CPC Class Codes: G06T 7/262 using transform domain methods, e.g. Fourier domain methods
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking

Abstract

An FFT correlation tracker that is capable of effectively tracking targets against non-uniform backgrounds in realtime, includes a background correction implemented using a FFT with the 2-dimension sinc function. The tracker tracks an object by effectively computing the first and third terms of the mean-square-error function C(s,t) defined as $C\left(s,t\right)=\frac{1}{N}\sum _N{f}^2\left(x,y\right)+\frac{1}{N}\sum _N{g}^2\left(x-s,y-t\right)-2·\frac{1}{N}\sum _N\left[f\left(x,y\right)·g\left(x-s,y-t\right)\right]$
This is done by first transforming the first and third terms into the frequency domain, where the first term, the background correction term, can be computed much more efficiently in real-time by using the 2-dimension sinc function. Multiplications and additions necessary to carry out the computations in the frequency domain are then performed. Next, the resulting frequency-domain function is transformed back into the spatial domain to form a correlation surface. Finally, a minimum of the resulting correlation surface is found. The location of the minimum corresponds to the location of the object being tracked.

Claims

1. A method for tracking an object in an image using Fast Fourier Transforms, comprising:

identifying a background correction term for a Fast Fourier Transform correlation tracker; and

tracking the object based on a representation of the background correction term that includes a frequency domain sinc function;

wherein the tracking includes zero-padding a reference window to a size of a search window, performing a 2 dimension Fast Fourier Transform of the zero-padded reference window into the frequency domain, and taking a complex conjugate of the transformed zero-padded reference window, performing a 2 dimension Fast Fourier Transform of a search window, performing a complex multiplication of the complex conjugate of the transformed zero-padded reference window and the transformed search window, and multiplying the result by a first factor to obtain a first result in the frequency domain, squaring pixel values of the search window and performing a 2 dimension Fast Fourier Transform of the squared pixel values into the frequency domain, multiplying the transform of the squared pixel values with a sinc function to obtain a second result in the frequency domain, summing the first and second results to form a third result in the frequency domain, performing a 2 dimension inverse Fast Fourier Transform of the third result to obtain a spatial-domain correlation surface, and searching for a minimum of the correlation surface.

2. The method of claim 1, wherein the first factor is −

2.

3. The method of claim 1, wherein the sinc function is a 2 dimension sinc function.

4. The method of claim 3, wherein the sinc function is pre-stored.

5. The method of claim 1, wherein in the step of searching for a minimum of the correlation surface, border areas which have edge effect caused by window operation, are excluded.

6. A method for tracking an object in an image using Fast Fourier Transforms, comprising:

identifying a background correction term for a Fast Fourier Transform correlation tracker; and

tracking the object based on a representation of the background correction term that includes a frequency domain sinc function;

wherein the tracking includes zero-padding a reference window to a size of a search window, performing a 2 dimension Fast Fourier Transform of the zero-padded reference window into the frequency domain, and taking a complex conjugate of the transformed zero-padded reference window, performing a 2 dimension Fast Fourier Transform of a search window, performing a complex multiplication of the complex conjugate of the transformed zero-padded reference window and the transformed search window, and multiplying the result by a first factor to obtain a first result in the frequency domain, obtaining a search window function by squaring pixel values of the search window, performing a 2 dimension Fast Fourier Transform of the search window function into the frequency domain, multiplying the transform of the search window function with a sinc function to obtain a second result in the frequency domain, summing the first and second results to form a third result in the frequency domain, performing a 2 dimension inverse Fast Fourier Transform of the third result to obtain a spatial-domain correlation surface, and searching for a minimum of the correlation surface.

7. A Fast Fourier Transform correlation tracker, comprising:

a computing device with inputs for receiving an input search window image and receiving a reference window image, wherein the computing device tracks the reference window image in the input search window image based on a frequency domain background correction term that includes a 2 dimension sinc function, wherein the tracker;

zero-pads a reference window to a size of a search window, performs a 2 dimension Fast Fourier Transform of the zero-padded reference window into the frequency domain, and takes a complex conjugate of the transformed zero-padded reference window;

performs a 2 dimension Fast Fourier Transform of a search window;

performs a complex multiplication of the complex conjugate of the transformed zero-padded reference window and the transformed search window, and multiplies the result by a first factor to obtain a first result in the frequency domain;

squares pixel values of the search window and performs a 2 dimension Fast Fourier Transform of the squared pixel values into the frequency domain;

multiplies the transform of the squared pixel values with a sinc function to obtain a second result in the frequency domain;

sums the first and second results to form a third result in the frequency domain;

performs a 2 dimension inverse Fast Fourier Transform of the third result to obtain a spatial-domain correlation surface; and

searches for a minimum of the correlation surface.

8. A Fast Fourier Transform correlation tracker, comprising:

a computing device with inputs for receiving an input search window image and receiving a reference window image, wherein the computing device tracks the reference window image in the input search window image based on a frequency domain background correction term that includes a 2 dimension sinc function, wherein the tracker;

zero-pads a reference window to a size of a search window, performs a 2 dimension Fast Fourier Transform of the zero-padded reference window into the frequency domain, and takes a complex conjugate of the transformed zero-padded reference window;

performs a 2 dimension Fast Fourier Transform of a search window;

performs a complex multiplication of the complex conjugate of the transformed zero-padded reference window and the transformed search window, and multiplies the result by a first factor to obtain a first result in the frequency domain;

obtains a search window function by squaring pixel values of the search window;

performs a 2 dimension Fast Fourier Transform of the search window function into the frequency domain;

multiplies the transform of the search window function with a sinc function to obtain a second result in the frequency domain;

sums the first and second results to form a third result in the frequency domain;

performs a 2 dimension inverse Fast Fourier Transform of the third result to obtain a spatial-domain correlation surface; and

searches for a minimum of the correlation surface.