Method for the determination of motion vector fields from digital image sequences

• US 4,924,310 A
• Filed: 08/22/1989
• Issued: 05/08/1990
• Est. Priority Date: 06/02/1987
• Status: Expired due to Term

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: von Brandt, Achim
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US07/397,049
• Time in Patent Office: 259 Days
• Field of Search: 358/133, 358/135, 358/136, 358/105, 375/27, 375/122
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/238 using non-full search, e.g. three-step search
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures

Abstract

A method for the determination of motion vector fields from digital image sequences derives a motion vector field from two successive image frames, with the motion vector field relating a picture element of the other image frame to every picture element of the one image frame, whereby the relation is defined by a motion vector which reproduces the displacement of the picture elements relative to one another and whereby respectively all picture elements in a square or rectangular block of picture elements receive the same motion vector. The determination of the motion vectors is carried out by minimization of a composite objective function which, first, takes into consideration the difference in the luminance values of the mutually allocated picture elements of the two established frames, and, then evaluates or weights the differences between adjacent or neighboring motion vectors, evaluating or weighting these with the assistance of a smoothing measure. The minimization of this objective function is carried out in such fashion that, first, the motion vectors minimizing the objective function are determined, given the restriction that the motion vectors in blocks larger than the blocks ultimately desired are constant, and that, subsequently, each of these blocks (16×6) is subdivided into smaller, preferably equal-sized blocks until the desired block size (4×4) is achieved.

Claims

1. A method for the determination of motion vector fields from digital image sequences that determines a motion vector field from respectively two successive image frames, said motion vector field relating a picture element of the other image frame to every picture element of the one image frame, whereby the relation is respectively defined by a motion vector that reproduces the displacement of the picture elements relative to one another and, whereby respectively all picture elements contained in a square or rectangular block of picture elements receive the same motion vector, comprising the steps of minimizing a composite objective function (Z) which is designed to take the differences in the luminance values of the picture elements of the two given frames allocated to one another into consideration and which weights the differences between neighboring motion vectors whose coordinates are adjacent, with the assistance of a smoothing measure (P);

said minimization step being carried out by determining the motion vectors that minimize the objective function using constant motion vectors in blocks that are larger than the blocks ultimately desired;

subsequently subdividing each of these blocks (16×

16) into smaller, preferably equal-sized blocks until the desired block size (4×

4) is achieved, whereby the objective function is again minimized by variation of the motion vectors after each diminution of the blocks.

2. The method according to claim 1, including, in the case of an insertion of an intermediate image between the two frames, allocating two picture elements to every picture element of this intermediate image, namely, one of said two picture elements from the first frame and one from the second frame.

3. The method according to claim 1, including the steps of identifying not only the differences between neighboring motion vectors in the motion vector field to be calculated, but also the differences between the motion vectors of the current motion vector field and those of the motion vector field calculated immediately before from a preceding pair of successive frames and using said identified differences in the smoothness measure, for the purpose of smoothing the motion vector field in the direction of the time axis, i.e. for assimilating successive motion vector fields.

4. The method according to claim 1, including the step of determining motion vector fields, for the purpose of inserting intermediate images, from two respective, successive frames transmitted with data compression from a coder via a channel to a decoder, and using corresponding motion vector fields that had already been previously transmitted for the initialization of the method.

5. The method according to claim 1, including the steps of subdividing the blocks by halving the side lengths of the blocks.

6. The method according to claim 5, including the step of optimizing every individual motion vector in every stage of the block-sub-division, in the case of the maximum block size and, following thereupon, after every block sub-division that is preferably carried out down to a block size of 4×

4 picture elements, such optimization taking place by variation in an appertaining value range in sequence until a smaller value of the objective function can no longer be found for any motion vector in this way.

7. The method according to claim 6, including the step of ignoring some motion vectors of the appertaining value range in the optimization of a defined motion vector;

whereby only a sub-set of the motion vectors are taken into consideration based on a predetermined pattern.

8. The method according to claim 1, including the step of weighting the differences in the luminance values of mutually corresponding picture elements of the two successive frames within a block of picture elements with the sum of the absolute values of the differences in the luminance values and using said weighted values as addends in the objective function to be minimized, whereby these addends form a first component of the objective function.

9. The method according to claim 1, including the step of weighting the differences in the luminance values of mutually corresponding picture elements of the two successive frames within a block of picture elements with the sum of the squares of the differences of the luminance values, and using said weighted values as addends in the objective function to be minimized, whereby these addends form a first component of the objective function.

10. The method according to claim 8 or 9, including the step of forming the absolute value norms of differences between neighboring motion vectors, whereby the sum of these absolute value norms forms a second component of the objective function and is used as smoothing measure.

11. The method according to claim 10, including the step of multiplying at least one of the two components by a weighting factor;

and summing the corresponding products to form the objective function, whereby the objective function preferably has the form Z=Z1+α

Z2, whereby Z1 is the first component, Z2 is the second component and α

is the weighting factor.

12. The method according to claim 10, including the step of using only those four neighboring motion vectors of every motion vector whose coordinates are horizontally and vertically adjacent to the motion vector, i.e. that the coordinates thereof differ from the coordinates of the motion vector by (0, 1), (0,-1), (1,0) or (-1,0).

13. The method according to claim 10, including the step of initializing the motion vector field with large blocks (preferably 16×

16 picture elements), before a motion vector is calculated at least once for every block, by modifying the smoothing measure so that, instead of the absolute values of the differences between neighboring motion vectors, the absolute value norms of the motion vectors to be optimized are multiplied by a weighting factor, and by employing of the products thus formed in the objective function by means of the smoothing measure.

14. The method according to any of claims 1-9, including the step of deriving the value range of the motion vectors within which the individual motion vectors are varied in order to minimize the objective function in dependence on the values of the motion vectors in the motion vector field that has already been calculated, so that the value range for the optimization of the motion vector field is small when neighboring motion vectors are the same or similar and is only larger when neighboring motion vectors exhibit great differences compared to one another.

15. The method according to any of claims 1-9, including the step of providing a logging system optimizing only those motion vectors, in view of a possible minimization of the value of the objective function, whose neighboring motion vectors have changed since the last optimization of the motion vector, so that the smoothness function may also have varied, whereby the logging system contains a logging field comprising a memory location per block for storing a control information for the optimization execution.