Method to improve accuracy and reliability of motion estimated with phase correlation

1. A system for performing phase correlation to eliminate sub-pixel motion bias programmed in a memory in a device comprising:

a. a first pass module for performing a first pass of phase correlation;

b. an offset module for offsetting a window in a reference picture using an offset according to motion determined in the first pass;

c. a second pass module for performing a second pass of the phase correlation using an original current window and the offset reference window to generate a second phase correlation surface, wherein the second pass module further comprises:

i. an offset window function module for applying an offset window function to the window of a reference frame to obtain an offset frame result;

ii. a third Fast Fourier Transform module for applying the Fast Fourier Transform to the offset frame result yielding a third set of complex values;

iii. normalizing a product of the third set of complex values and a complex conjugate of a first set of complex values; and

iv. a second inverse Fast Fourier Transform module for computing the inverse Fast Fourier Transform to yield a second phase correlation surface;

d. a sub-pixel module for computing sub-pixel motion estimates based on the second phase correlation surface; and

e. a final motion module for computing a final motion estimate by summing the offset and sub-pixel estimates.

2. The system of claim 1 wherein the first pass module further comprises:

a. a first window function module for applying a window function to a window of a current frame to obtain a current frame result;

b. a first Fast Fourier Transform module for applying a Fast Fourier Transform to the current frame result yielding the first set of complex values;

c. a second window function module for applying the window function to the window of a reference frame to obtain a reference frame result;

d. a second Fast Fourier Transform module for applying the Fast Fourier Transform to the reference frame result yielding a second set of complex values;

e. a normalizing module for normalizing a product of the second set of complex values and a complex conjugate of the first set of complex values;

f. an inverse Fast Fourier Transform module for computing an inverse Fast Fourier Transform to yield a phase correlation surface; and

g. a peak identification module for identifying one or more peaks from the phase correlation surface, wherein indices of the peaks correspond to possible motions.

3. The system of claim 1 further comprising a reliability module for implementing a reliability measure.

4. The system of claim 1 wherein the device is selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPhone, an iPod®, a video player, a DVD writer/player, a Blu-ray® writer/player, a television and a home entertainment system.

5. A camera device comprising:

a. a video acquisition component for acquiring a video;

b. an encoder for encoding the video, including phase correlation motion estimation, by:

i. performing a first pass of phase correlation;

ii. offsetting a window in a reference picture using an offset according to motion determined in the first pass;

iii. performing a second pass of the phase correlation using an original current window and the offset reference window to generate a second phase correlation surface, wherein performing the second pass of phase correlation further comprises:

1) applying an offset window function to the window of a reference frame to obtain an offset frame result;

2) applying a Fast Fourier Transform to the offset frame result yielding a third set of complex values;

3) normalizing a product of the third set of complex values and a complex conjugate of a first set of complex values; and

4) computing an inverse Fast Fourier Transform to yield a second phase correlation surface;

iv. computing sub-pixel motion estimates based on the second phase correlation surface; and

v. computing a final motion estimate by summing the offset and sub-pixel estimates; and

c. a memory for storing the encoded video.

6. The camera device of claim 5 wherein performing the first pass of phase correlation further comprises:

a. applying a window function to a window of a current frame to obtain a current frame result;

b. applying a Fast Fourier Transform to the current frame result yielding the first set of complex values;

c. applying the window function to the window of a reference frame to obtain a reference frame result;

d. applying the Fast Fourier Transform to the reference frame result yielding a second set of complex values;

e. normalizing a product of the second set of complex values and a complex conjugate of the first set of complex values;

f. computing an inverse Fast Fourier Transform to yield a phase correlation surface; and

g. identifying one or more peaks from the phase correlation surface, wherein indices of the peaks correspond to possible motions.