Method and device to estimate motion in a sequence of moving pictures

• US 4,853,775 A
• Filed: 03/22/1988
• Issued: 08/01/1989
• Est. Priority Date: 03/23/1987
• Status: Expired due to Term

• Current Assignee: Thomson-CSF (Thales SA)
• Original Assignee: Thomson-CSF (Thales SA)
• Inventors: Rouvrais, Bernard, Robert, Philippe, Kerdranvat, Michel
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): Kostak, Victor R.
• Application Number:
  US07/171,835
• Time in Patent Office: 497 Days
• Field of Search: 358/105, 358/138, 358/136, 358/133, 358/137, 358/135
• US Class Current: 348/699
• CPC Class Codes: G06T 7/269 using gradient-based methods
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 7/014 involving the use of motion vectors motion estimation and compensation in video coding H04N19/51

Abstract

The method consists in estimating motion by performing a gradient algorithm which minimalizes the mean square deviation of local luminance variations of the present pel of the picture with the pel that is homologous with it in the prior picture, in initializing the execution of the algorithm by displacement values estimated along several directions within the close causal neighborhood of the present pel and in propagating each estimate in the scanning direction if the picture lines.

Claims

1. A method to estimate motion in a sequence of television type moving pictures, where each picture is formed by a determined number of light spots located at intersections of lines and columns, said method of the type where motion is estimated by performing a gradient algorithm which minimizes a mean square deviation between local variations in luminance of a current pel of the picture and those of a pel in a similar position to the current pel in the prior image, said method comprising the steps of:

initializing an algorithm by displacement values estimated according to several directions within a close causal neighborhood of the current pel and of the propagation of each estimate in a scanning direction of picture lines,

choosing a propagating direction for the algorithm depending on a position, in the picture, of a line to which the current pel belongs,

calculating a modulus of a gradient of the current pel and comparing the result with a pre-determined threshold value,

choosing a displacement for the present pel in the causal neighborhood of this pel when the modulus of the gradient obtained is below the pre-determined threshold value, and

choosing the displacement that gives the smallest displaced frame difference, or estimating a new displacement when the gradient modulus obtained is above the predetermined threshold.

2. A method according to claim 1 wherein the scanning direction alternates every other line.

3. A method according to claim 1 further comprising the steps when the gradient modulus obtained is above the pre-determined threshold,

computing a simultaneous estimating computation for a determined number N of displacements, from N initial displacement values, and choosing the displacement value D_i (O<

i<

_MAX) which gives a convergence with the smallest displaced frame difference DFD(Di).

4. A motion-estimating method according to claim 1 wherein a field of motion is determined between two successive frames (Ta, Tb) of a sequence of pictures, in the form of a vector field assigned to a fictitious picture frame (Tj) located in the vicinity of the two frames (Ta, Tb).

5. A method according to claim 4 wherein the scanning direction of the fictitious frame lines is alternated at every other line.

6. A method according to claim 4 wherein the motion of each pel in the fictitious frame Tj is estimated in the form of a motion vector D(Z,Tj), corresponding to the displacement of the pel P(Z,Tj) between the instants Ta and Tb frames, this vector passing through the present pel P(Z,Tj) and respectively having its endpoints on the instants Ta and Tb picture frames, the estimation taking place by the performance of a computation through the iteration of displacement vectors Di(Z,Tj), according to a gradient algorithm which minimizes the mean square deviation of the local luminance variations of the present pel in the instant Tj fictitious frame.

7. A method according to claim 6 wherein each displacement vector Di(Z,Tj) of an iteration i is obtained from the displacement vector Di-1(Z,Tj) obtained at the preceding iteration i-1 by the relationship:

space="preserve" listing-type="equation">Di(Z,Tj)=Di-1(Z,Tj)-(DFD(Z,Di-1).grad

L(Z,Di-1))).(2.(grad L(Z,Di-1))²)1.

where;

Z designates the spatial coordinates of the present pel P(Z,Tj) for which the motion vector D(Z,Tj) is estimated;

DFD(Z,Di-1) designates the computed displaced frame difference between the instants Ta and Tb frames;

and grad L (Z,Di-1) designates the spatial gradient which is the half-sum of the spatial gradients at the endpoints of the displacement vector Di-1 on the instants Ta and Tb frames.

8. A method according to claim 7 wherein the estimation of the motion vector D(Z,Tj) for the pel P(Z,Tj) is computed from the four initializing shift vectors corresponding to the motion vectors already estimated for four neighbouring pels in the causal neighbourhood of the present pel and, with the four initializing shift vectors giving rise to four estimated motion vectors, only that motion vector is chosen, out of these four estimated vectors, which gives a convergence of the gradient algorithm with the smallest frame difference.

9. A method according to claim 8 wherein the displaced frame difference DFD (Z,Di-1) is obtained by taking the temporal difference in the displacement direction Di-1 of the luminance values of the present pel P(Z,Tj) displaced in the instants Ta and Tb frames.

10. A method according to claim 9 wherein the luminance values LA and LB of the displaced pel in the instants Ta and Tb frames respectively, are obtained by the bilinear interpolation of the luminance values Ln of the four pels surrounding the pel, at the endpoint of the vector considered, in Ta and Tb respectively.

11. A method according to claim 10 wherein each displacement vector Di is obtained by subtracting the displacement vector Di-1, calculated at the preceding iteration, from a correcting term equal to the product of the displaced frame difference DFD(Z,Di-1), firstly, by the spatial gradient of luminance grad L(Z,Di-1) and, secondly, by the converse of the half-sum of the spatial gradients at the endpoints of the displacement vector Di-1 on the instants Ta and Tb frames.

12. A device for the application of the method according to claim 11 comprising a line memory coupled to a frame memory to store, respectively, luminance values of a determined number of pels surrounding the pels homologous with the present pel P(Z,Tj) and the pels that surround it in the instants Ta and Tb frames, a displacement estimating device coupled with the line memory, with the frame memory and with a decision element to compute, from the luminance values of the pels contained in the line memory and the frame memory and from at least one initial displacement value contained in an initializing block, a displacement vector for each present pel P(Z,Tj) of the picture.

13. A device according to claim 12 wherein the displacement estimating device comprises at least one convergence-testing block, one correcting-term computing block and one new displacement computing block.

14. A device according to claim 13 wherein a convergence-testing block comprises, firstly, a first interpolation circuit to determine the luminance of the present pel displaced in the instant Ta frame, a second interpolation circuit to determine the luminance of the current pel displaced in the instant Tb frame and a computing device coupled to the first and second interpolation circuits to compute, according to the luminance values computed by the first and second interpolation circuits, the absolute value of the displaced frame difference, the output of the computing device being coupled with the decision element through a first switch and a second switch;

said convergence-testing device comprising, secondly, first and second gradient computing devices coupled to a third device for computing the mean of the gradients formed by the first and second computing devices, the third computing device being coupled to a fourth device to compute the sum of the squares of the displaced mean gradients.

15. A device according to claim 14 wherein a correcting-terms computing block comprises a fifth device to compute an "epsilon" value equal to the converse, divided by two, of the sum of the squares of the displaced mean gradients given by the fourth computing device coupled, through an increment computing device, to a correction computing device coupled, firstly to the third computing device, and secondly, to the second switch to compute correcting terms depending on the absolute value of the displaced frame difference given by the computing device and on the "epsilon" value, as well as at least one comparator circuit to limit the value of the correcting terms obtained from the correction computing device.

16. A device according to claim 15 wherein a new displacements computing block comprises subtractor circuits to subtract the correcting terms, at each new iteration commanded by the increment computing device, from the displacement value calculated at the preceding iteration and stored in the initialization block to obtain the new dispacement values at each new iteration and store them in the initialization block.

17. A device for implementation of a method to estimate motion in a sequence of television type moving pictures, where each picture is formed by a determined number of light spots located at intersections of lines and columns, of the type where motion is estimated by performing a gradient algorithm which minimizes a mean square deviation between local variations in luminance of a current pel of the picture and those of a pel which is homologous to it in the prior image, where the method includes the steps of initializing an algorithm by displacement values estimated according to several directions within a close causal neighborhood of the current pel and of the propagation of each estimate in a scanning direction of picture lines, choosing a propagating direction for the algorithm depending on a position, in the picture, of a line to which the current pel belongs, calculating a modulus of the gradient of the current pel and comparing the result with a pre-determined threshold value, choosing a displacement for the present pel in the causal neighborhood of this pel when the modulus of the gradient obtained is below the pre-determined threshold value, and choosing the displacement that gives the smallest displaced frame difference, or estimating a new displacement when the gradient modulus obtained is above the pre-determined threshold, said device comprising:

a picture memory to store the luminance values of a determined number of pels surrounding the pel of P(z,t-1) of a coordinate z in the picture homologous with the current pel P(z,t) in the picture frame IMS.sub.(t-1) preceding the current pel frame IMS.sub.(t),

a device to compute the modulus of the luminance gradient of the current pel,

a first decision element and a second decision element,

a displacement estimating device, and a switching device, the outputs of the two decision elements being coupled to elements of the switching device controlled by the gradient modulus computing device,

said switching device controlled such that if the value of the current gradient modulus is smaller than or equal to a pre-determined threshold value, the displacement chosen is the one coming from the second decision element, otherwise, the displacement chosen is the one coming from the first decision element.

18. A device according to claim 17 wherein the displacement estimating device comprises an initializing block to store the initial displacement along several directions, coupled to a computing unit to compute, from initial displacement values, displacement values for which the gradient algorithm converges.

19. A device according to claim 18 wherein the computing unit is coupled to the decision element to select the displacement value that gives the fastest algorithm convergence.

20. A device according to claim 19 wherein the computing unit comprises, for each estimated displacement value D_i (O<

i<

i_MAX), a convergence-testing block coupled with a correcting-terms computing block and a new displacements computing device.

21. A device according to claim 20 wherein the convergence-testing block comprises, firstly, an interpolation circuit coupled with a device for computing the absolute value of the displaced frame difference and, secondly, a gradient computing device coupled with a device for computing the sum of the squares of the displaced gradients, obtained along both the horizontal and the vertical picture-scanning directions.

22. A device according to claim 21 wherein the correcting-terms computing block comprises a device to compute the gain of the gradient algorithm, coupled with a device to compute increment and correction values.

23. A device according to claim 22 wherein the new displacements computing device has subtractor circuits to compute displacement values according to the correcting terms computed by the correcting-terms computing block.

24. A device according to claim 23 wherein each correcting term (TC) given by the correcting-terms computing block is equal to the product of the displaced frame difference DFD(Z,D) by the value of the displaced pel gradient P(Z-D,T-1) and by the gain of an algorithm epsilon, D being an estimated displacement at the current pel.