Gradient based motion estimation

• US 6,345,106 B1
• Filed: 09/14/1998
• Issued: 02/05/2002
• Est. Priority Date: 03/13/1996
• Status: Expired due to Term

• Current Assignee: HBC Solutions Incorporated (AEG Holdings, Inc.)
• Original Assignee: Innovision Ltd. (L3Harris Technologies, Inc.)
• Inventors: Borer, Timothy John
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Choobin, Mahmood
• Application Number:
  US09/142,763
• Time in Patent Office: 1,240 Days
• Field of Search: 348/140, 348/97, 348/154, 348/155, 382/107, 382/100, 356/2.F, 734/88, 375/240.17
• US Class Current: 382/107
• CPC Class Codes: G06T 7/269 using gradient-based methods

Abstract

A technique for generating motion vectors in video and film signal processing uses constraint equation based motion estimation. Simplifications of the processing and hardware are made possible by generating motion vectors based on the normalized constraint equation. The temporal and spatial image gradients are calculated using temporal and spatial differentiators (16, 17, 18). An angle (θ) corresponding to the orientation of the spatial image gradient vector and the motion speed (vn) in the direction of the vector are calculated using apparatus including a rectangular to polar coordinate converter (32). θ and vn are the parameters of the normalized constraint equation.

Claims

1. A motion vector estimation apparatus for use in video signal processing comprising:

a means for calculating a set of image gradients for each of a plurality of pixels;

a means for calculating for each said set of image gradients an angle corresponding to an orientation of a spatial image gradient vector;

a means for calculating from each said set of image gradients a motion speed in a direction of the spatial image gradient vector; and

a means for generating motion vectors from a plurality of values of said angle and said motion speed;

wherein said means for generating motion vectors calculates a best fitting motion vector for a region of a picture based on normalized constraint equations corresponding to said sets of image gradients for said plurality of pixels.

2. The motion vector estimation apparatus as claimed in claim 1, wherein the means for calculating the image gradients comprises temporal and spatial differentiators.

3. The motion vector estimation apparatus as claimed in claim 1, wherein each of the means for calculating an angle and the means for calculating a motion speed comprises a rectangular to polar coordinate converter.

4. A motion vector estimation apparatus for use in video signal processing wherein motion vectors are generated for a region of a picture based on normalized constraint equations corresponding to image gradients for a plurality of pixels, comprising:

a means for calculating a set of said image gradients for each of said plurality of pixels;

a means for calculating for each said set of image gradients an angle corresponding to an orientation of a spatial image gradient vector;

a means for calculating from each said set of image gradients a motion speed in a direction of the spatial image gradient vector; and

a means for generating motion vectors from a plurality of values of said angle and said motion speed;

wherein the means for generating motion vectors calculates the motion vectors using the equation;

$\left[\begin{array}{c}{u}_0\\ v_0\end{array}\right]=\left(\frac{{\mathrm{\lambda <br><br>}}_1}{{\mathrm{\lambda <br><br>}}_1^2+n_1^2}<br><br>\text{\hspace{1em}<br><br>}<br><br>e_1<br><br>e_1^t+\frac{{\mathrm{\lambda <br><br>}}_2}{{\mathrm{\lambda <br><br>}}_1^2+n_2^2}<br><br>\text{\hspace{1em}<br><br>}<br><br>e_2<br><br>e_2^t\right)·<br><br>\left[\begin{array}{c}\sum <br><br>\mathrm{vn}·<br><br>\cos <br><br>\left(\mathrm{\Theta <br><br>}\right)\\ \sum <br><br>\mathrm{vn}·<br><br>\sin <br><br>\left(\mathrm{\Theta <br><br>}\right)\end{array}\right]$

where now e and λ

are eigenvectors and eigenvalues of a matrix given by;

$\left[\begin{array}{cc}\sum <br><br>{\cos }^2<br><br>\left(\mathrm{\theta <br><br>}\right)& \sum <br><br>\cos <br><br>\left(\mathrm{\theta <br><br>}\right)·<br><br>\sin <br><br>\left(\mathrm{\theta <br><br>}\right)\\ \sum <br><br>\cos <br><br>\left(\mathrm{\theta <br><br>}\right)·<br><br>\sin <br><br>\left(\mathrm{\theta <br><br>}\right)& \sum <br><br>{\sin }^2<br><br>\left(\mathrm{\theta <br><br>}\right)\end{array}\right]<br><br>$

where θ

is an angle between the spatial image gradient vector and horizontal.

5. The motion vector estimation apparatus as claimed in claim 4, wherein said means for generating motion vectors comprises three look-up tables, each of said look-up tables having two inputs and containing pre-calculated values of a matrix defined by:

$Z=\left(\frac{{\mathrm{\lambda <br><br>}}_1}{{\mathrm{\lambda <br><br>}}_1^2+n_1^2}<br><br>e_1<br><br>e_1^t+\frac{{\mathrm{\lambda <br><br>}}_2}{{\mathrm{\lambda <br><br>}}_1^2+n_2^2}<br><br>e_2<br><br>e_2^t\right).$

6. The motion vector estimation apparatus as claimed in claim 4, wherein said means for generating motion vectors comprises three look-up tables, each said look-table having two inputs and containing pre-calculated values of φ

<sup>−

1</sup> where;

$\mathrm{\Phi <br><br>}=\left[\begin{array}{cc}\sum <br><br>{\cos }^2<br><br>\left(\mathrm{\Theta <br><br>}\right)& \sum <br><br>\cos <br><br>\left(\mathrm{\Theta <br><br>}\right)·<br><br>\sin <br><br>\left(\mathrm{\Theta <br><br>}\right)\\ \sum <br><br>\cos <br><br>\left(\mathrm{\Theta <br><br>}\right)·<br><br>\sin <br><br>\left(\mathrm{\Theta <br><br>}\right)& \sum <br><br>{\sin }^2<br><br>\left(\mathrm{\Theta <br><br>}\right)\end{array}\right].$

7. A method of motion estimation in video or film signal processing wherein motion vectors are generated for a region of a picture based on normalized constraint equations corresponding to image gradients for a plurality of pixels, comprisng the steps of:

calculating a set of temporal and spatial image gradients for each of a plurality of said pixels,

calculating from each said set of image gradients an angle corresponding to an orientation of a spatial image gradient vector,

calculating from each said set of image gradients a motion speed in a direction of the spatial image gradient vector, and

generating motion vectors from a plurality of values of said angle and said motion speed;

wherein the motion vectors are calculated on the basis of the following equation;

$\left[\begin{array}{c}{u}_0\\ v_0\end{array}\right]=\left(\frac{{\mathrm{\lambda <br><br>}}_1}{{\mathrm{\lambda <br><br>}}_1^2+n_1^2}<br><br>\text{\hspace{1em}<br><br>}<br><br>e_1<br><br>e_1^t+\frac{{\mathrm{\lambda <br><br>}}_2}{{\mathrm{\lambda <br><br>}}_1^2+n_2^2}<br><br>\text{\hspace{1em}<br><br>}<br><br>e_2<br><br>e_2^t\right)·<br><br>\left[\begin{array}{c}\sum <br><br>\mathrm{vn}·<br><br>\cos <br><br>\left(\mathrm{\Theta <br><br>}\right)\\ \sum <br><br>\mathrm{vn}·<br><br>\sin <br><br>\left(\mathrm{\Theta <br><br>}\right)\end{array}\right]$

where now e and λ

are eigenvectors and eigenvalues of a matrix given by;

$\left[\begin{array}{cc}\sum <br><br>{\cos }^2<br><br>\left(\mathrm{\Theta <br><br>}\right)& \sum <br><br>\cos <br><br>\left(\mathrm{\Theta <br><br>}\right)·<br><br>\sin <br><br>\left(\mathrm{\Theta <br><br>}\right)\\ \sum <br><br>\cos <br><br>\left(\mathrm{\Theta <br><br>}\right)·<br><br>\sin <br><br>\left(\mathrm{\Theta <br><br>}\right)& \sum <br><br>{\sin }^2<br><br>\left(\mathrm{\Theta <br><br>}\right)\end{array}\right]<br><br>$

and where θ

is an angle between the spatial image gradient vector and horizontal.

8. A motion vector estimation apparatus for use in video signal processing wherein motion vectors are generated for a region of a picture based on normalized constraint equations corresponding to image gradients for a plurality of pixels, comprising:

a means for calculating a set of said image gradients for each of said plurality of pixels;

a means for calculating for each said set of image gradients an angle corresponding to an orientation of a spatial image gradient vector;

a means for calculating from each said set of image gradients a motion speed in a direction of the spatial image gradient vector; and

a means for generating motion vectors from a plurality of values of said angle and said motion speed using the following equation;