Fast fourier transform correlation tracking algorithm with background correction

• US 7,251,345 B1
• Filed: 06/10/2005
• Issued: 07/31/2007
• 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): Mehta; Bhavesh M
• Assistant Examiner(s): KIM, CHONG R
• Application Number:
  US11/149,549
• Publication Number:
  US 20070165906A1
• Time in Patent Office: 781 Days
• Field of Search: None
• 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:

determining a background correction for a varying background in the image based on a representation of the background correction that includes a product in the frequency domain of a squared function of the image with a 2-dimension sinc function, wherein the determining a background correction comprises;

squaring pixel values of a search window and performing a 2-dimension Fast Fourier Transform of the squared pixel values, and

multiplying the transform of the squared pixel values with the 2-dimension sinc function to obtain the background correction in the frequency domain; and

tracking the object based on the background correction and a cross-correlation between a search window image function and a reference window image function.

2. The method of claim 1, wherein tracking the object comprises:

zero-padding a reference window to a size of the search window, performing a 2-dimension Fast Fourier Transform of the zero-padded reference window, and taking a complex conjugate of the transformed zero-padded reference window to obtain the reference window image function;

performing a 2-dimension Fast Fourier Transform of the search window to obtain the search window image function;

performing a complex multiplication of the reference window image function and the search window image function, and multiplying the result of the complex multiplication by a factor to obtain the cross-correlation in the frequency domain;

summing the background correction and the cross-correlation in the frequency domain;

performing a 2-dimension inverse Fast Fourier Transform of the sum to obtain a spatial-domain correlation surface; and

searching for a minimum of the correlation surface to identify a location of the object in the search window.

3. A method for tracking an object in an image based on a mean-square-error function having a background correction term and a cross-correlation term, the method comprising the steps of:

transforming the background correction and cross-correlation terms into the frequency domain;

computing the background correction term in real time based on a representation of the background correction term that includes a product of a squared function of the image with a 2-dimension sinc function;

computing the cross-correlation term;

transforming the computed background correction and cross-correlation terms out of the frequency domain to form a correlation surface; and

determining a minimum of the correlation surface, wherein a location of the minimum corresponds to a location of the object being tracked.

4. The method of claim 3, wherein the mean-square-error function is defined as:

$C<br><br>\left(s,t\right)=\frac{1}{N}<br><br>\underset{N}{\sum <br><br>}<br><br>f^2<br><br>\left(x,y\right)+\frac{1}{N}<br><br>\underset{N}{\sum <br><br>}<br><br>g^2<br><br>\left(x-s,y-t\right)-2·<br><br>\frac{1}{N}<br><br>\underset{N}{\sum <br><br>}<br><br>\left[f<br><br>\left(x,y\right)·<br><br>g<br><br>\left(x-s,y-t\right)\right],$

wherein the background correction term is defined as;

$\frac{1}{N}<br><br>\underset{N}{\sum <br><br>}<br><br>f^2<br><br>\left(x,y\right),$

and wherein the cross-correlation term is defined as;

$-2·<br><br>\frac{1}{N}<br><br>\underset{N}{\sum <br><br>}<br><br>\left[f<br><br>\left(x,y\right)·<br><br>g<br><br>\left(x-s,y-t\right)\right].$

5. The method of claim 3, wherein the background correction and cross-correlation terms comprise non-constant terms of the mean-square-error function.

6. A Fast Fourier Transform correlation tracker for tracking an object in an image, comprising:

means for determining a background correction for a varying background in the image based on a representation of the background correction that includes a product in the frequency domain of a squared function of the image with a 2-dimension sinc function, wherein the background correction means is configured to;

square pixel values of a search window and perform a 2-dimension Fast Fourier Transform of the squared pixel values, and

multiply the transform of the squared pixel values with the 2-dimension sinc function to obtain the background correction in the frequency domain; and

means for tracking the object based on the background correction and a cross-correlation between a search window image function and a reference window image function.

7. The tracker of claim 6, wherein the tracking means is configured to:

zero-pad a reference window to a size of the search window, perform a 2-dimension Fast Fourier Transform of the zero-padded reference window, and take a complex conjugate of the transformed zero-padded reference window to obtain the reference window image function;

perform a 2-dimension Fast Fourier Transform of the search window to obtain the search window image function;

perform a complex multiplication of the reference window image function and the search window image function, and multiply the result of the complex multiplication by a factor to obtain the cross-correlation in the frequency domain;

sum the background correction and the cross-correlation in the frequency domain;

perform a 2-dimension inverse Fast Fourier Transform of the sum to obtain a spatial-domain correlation surface; and

search for a minimum of the correlation surface to identify a location of the object in the search window.