Gradient based motion estimation

• US 6,381,285 B1
• Filed: 09/03/1998
• Issued: 04/30/2002
• Est. Priority Date: 03/13/1996
• Status: Expired due to Term

• Current Assignee: HBC Solutions Incorporated (AEG Holdings, Inc.)
• Original Assignee: Leitch Europe Limited
• Inventors: Borer, Timothy John
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): VO, TUNG T
• Application Number:
  US09/142,229
• Time in Patent Office: 1,335 Days
• Field of Search: H04/B.166, 375/240.18, 375/240.01, 375/240.12, 375/240.15, 375/240.16, 375/240.17, 348/400, 348/413.1, 348/414.1, 348/415.1, 348/416.1, 348/42, 348/620, 348/581, 348/699, 382/232, 382/236, 382/238
• US Class Current: 375/260
• CPC Class Codes: G06T 7/269 using gradient-based methods
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51
• CPC Class Codes: H04N 7/014 involving the use of motion vectors motion estimation and compensation in video coding H04N19/51

Abstract

A technique for generating motion vectors for applications is requiring field of frame rate interpolation and especially in standards conversion. The image gradients on the same standard as the input video or film signal and then vertical/temporal interpolators are used to convert to the output standard before determining the motion vectors. This allows motion vectors to be easily calculated on the output standard.

Claims

1. A motion vector estimation apparatus for use in video signal processing which is adapted to generate motion vector sampled on an output sampling lattice, comprising:

a first means for spatially filtering an input signal sampled on an input lattice;

a second means for means operating on said input signal for calculating image gradients sampled on said input lattice;

a third means for converting the signal sampled on said input lattice to a signal sample on said output sampling lattice said first, second and third means operating on said input signal in any order and having a plurality of image gradients sampled on said output lattice as an output; and

a fourth means for calculating motion vectors,

wherein said fourth means for calculating motion vectors has as an input said plurality of image gradients sampled on said output sampling lattice.

2. A motion vector estimation apparatus as claimed in claim 1, wherein said first means for spatially filtering the signal includes spatial low pass filters.

3. A motion vector estimation apparatus as claimed in claim 1, wherein said second means for calculating the image gradients includes temporal and spatial differentiators.

4. A motion vector estimation apparatus as claimed in claim 1, wherein said third means for converting the input signal includes a vertical/temporal interpolator.

5. A motion vector estimation apparatus as claimed in claim 1, and further comprising a multiplier array for calculating image gradient products from a plurality of said image gradients generated on the output standard, filters for summing said plurality of image gradient products, wherein said second means for calculating the motion vectors utilizes the sums of a plurality of image gradient products to generate the best fit motion vector.

6. A motion vector estimation apparatus as claimed in claim 5 wherein said best fit motion vector is determined in accordance with 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>}}_2^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}{\mathrm{\sigma <br><br>}}_{\mathrm{xt}}^2\\ {\mathrm{\sigma <br><br>}}_{\mathrm{yt}}^2\end{array}\right]$

where [u₀ v₀] is the best fitting motion vector, σ

represents the roots of sums of products of image gradients the subscript signifying the particular image gradients, and e and λ

are the eigen vectors and eigen values of M, where $M=\left[\begin{array}{cc}{\mathrm{\sigma <br><br>}}_{\mathrm{xx}}^2& {\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2\\ {\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2& {\mathrm{\sigma <br><br>}}_{\mathrm{yy}}^2\end{array}\right]$

7. A motion vector estimation apparatus as claimed in claim 1, and further comprising means for calculating from a plurality of image gradients generated on said output sampling lattice, the spatial image gradient (|∇

I|), the angle between the spatial image gradient and the horizontal (θ

) and the motion speed (vn) in the direction of the image gradient vector.

8. A motion vector estimation apparatus as claimed in claim 7, wherein said means for calculating motion vectors calculates the best fitting motion vector in accordance with 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>}}_2^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>v<br><br>\text{\hspace{1em}<br><br>}<br><br>n·<br><br>\cos <br><br>\left(\mathrm{\theta <br><br>}\right)\\ \sum <br><br>v<br><br>\text{\hspace{1em}<br><br>}<br><br>n·<br><br>\sin <br><br>\left(\mathrm{\theta <br><br>}\right)\end{array}\right]$

where e and λ

are the eigen vectors and eigen values of;

$<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]$

9. A method of estimating motion vectors on an output sampling lattice for use in video-signal processing, comprising the following steps:

(a) spatially filtering a video signal,

(b) converting the signal from an input sampling lattice to said output sampling lattice,

(c) calculating a plurality of image gradients;

wherein steps a to c are carried out in any order, and calculating motion vectors on said output sampling lattice from said image gradients generated on said output sampling lattice.

10. A method of motion vector estimation as claimed in claim 9, wherein said step of spatially filtering the input signal includes filtering by spatial low pass filters.

11. A method of motion vector estimation as claimed in claim 9, wherein calculating said plurality of image gradients includes temporally and spatially differentiating the spatially filtered signal.

12. A method of motion vector estimation as claimed in claim 9, wherein converting the signal includes vertical and temporal interpolation.

13. A method of motion vector estimation as claimed in claim 9 and further comprising calculating image gradient products from a plurality of said image gradients generated on the output standard, summing said plurality of image gradient products, wherein calculating the motion vectors comprises utilizing the sums of a plurality of image gradient products to generate the best fit motion vector.

14. A method of motion vector estimation as claimed in claim 13, wherein said best fit motion vector is determined in accordance with 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>}}_2^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}{\mathrm{\sigma <br><br>}}_{\mathrm{xt}}^2\\ {\mathrm{\sigma <br><br>}}_{\mathrm{yt}}^2\end{array}\right]$

where [u₀ v₀] is the best fitting motion vector, σ

represents the roots of sums of products of image gradients the subscript signifying the particular image gradients, and e and λ

are the eigen vectors and eigen values of M, where $M=\left[\begin{array}{cc}{\mathrm{\sigma <br><br>}}_{\mathrm{xx}}^2& {\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2\\ {\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2& {\mathrm{\sigma <br><br>}}_{\mathrm{yy}}^2\end{array}\right]$

15. A method of motion vector estimation as claimed in claim 9, and further comprising calculating from a plurality of image gradients generated on said output sampling lattice, the spatial image gradient (|∇

I|), the angle between the spatial image gradient and the horizontal (θ

) and the motion speed (vn) in the direction of the image gradient vector.

16. A method of motion vector estimation as claimed in claim 15, wherein said means for calculating motion vectors calculates the best fitting motion vector in accordance with 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>}}_2^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>v<br><br>\text{\hspace{1em}<br><br>}<br><br>n·<br><br>\cos <br><br>\left(\mathrm{\theta <br><br>}\right)\\ \sum <br><br>v<br><br>\text{\hspace{1em}<br><br>}<br><br>n·<br><br>\sin <br><br>\left(\mathrm{\theta <br><br>}\right)\end{array}\right]$

where e and λ

are the eigen vectors and eigen values of;

$<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]$