Method and apparatus for providing motion estimation signals for communicating image sequences

• US 4,661,849 A
• Filed: 06/03/1985
• Issued: 04/28/1987
• Est. Priority Date: 06/03/1985
• Status: Expired due to Term

• Current Assignee: Polycom Incorporated (Plantronics, Inc.)
• Original Assignee: Pictel Corporation
• Inventors: Hinman, Brian L.
• Primary Examiner(s): Hartary, Joseph W.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/740,900
• Time in Patent Office: 694 Days
• Field of Search: 358/105, 358/133, 358/135, 358/136, 358/138, 375/27
• US Class Current: 375/240.16
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search

Abstract

An image sequence transmission method and apparatus transmit a sequence of successive images over a bandwidth limited channel. The transmitter has a motion estimator for estimating the motion displacement between successive image frames of the sequence. The motion estimator divides each image into nonoverlapping blocks, each block including a plurality of picture elements. The apparatus then successively selects, in accordance with a steepest descent estimation technique, an initial value of a motion vector displacement for each successive block. Thereafter, an iterative process determines using the steepest descent approach, successive values of the motion displacement vector for a block and the iteration process is terminated when an iteration error measure, which is associated with the steepest descent method, is less than a predetermined threshold value. In particular embodiments of the invention, an adaptive approach is used wherein the step size parameter is incremented in accordance with a gradient error used in the steepest descent technique. In addition, methods and apparatus for determining an initial motion vector field value based upon of the motion displacements in adjacent blocks advantageously determine the initial displacement vector for a block.

Claims

1. In an image sequence transmission method for transmitting a sequence of images over a bandwidth limited channel, a motion estimation method for estimating for successive image frames, a measure of motion displacement between successive images comprising the steps of

dividing each said image into non-overlapping blocks, each block having a plurality of picture elements,

selecting an initial value of a motion vector displacement for each successive block,

iteratively determining, using a steepest descent method, succession values of said motion vector displacement for successive blocks of an image, and

terminating said iteration step for a block when an iteration error measure, associated with said steepest descent method, is less than a predetermined threshold value.

2. The motion estimation method of claim 1 wherein said selecting step comprises the step of

generating said initial value of the motion vector displacement for a block from a weighted average of previously determined motion vector displacements for adjacent blocks.

3. The motion estimation method of claim 2 wherein said selecting step further comprises

selecting, for said adjacent blocks, a previous block on the same block scan line and a previous, a corresponding, and a future block on a previous block scan line.

4. The motion estimation method of claim 3 wherein said weighting factors are respectively 0.3, 0, 0.4 , and 0.3 for said previous block on said same block scan line and said previous, corresponding, and future blocks of the previous block scan line.

5. The motion estimation method of claim 1 wherein said iteratively determining step comprises the steps of

modifying, for each iteration, a previous motion vector displacement in accordance with a multiplicative product of an incremental step value and an error gradient, and

said terminating step terminates said iteration process when said multiplicative product is less than said predetermined threshold value.

6. The motion estimation method of claim 1 wherein said iteratively determining step comprises the step of

modifying, for each iteration, a previous motion vector displacement in accordance with a multiplicative product of an incremental step value and an error gradient, and

adaptively modifying an initial incremental step value in accordance with said error gradient value.

7. The motion estimation method of claim 6 wherein said modifying step comprises

multiplying a step value for a previous iteration by a constant having a value dependent upon the error gradients for at least the last two iterations of said determining step.

8. The motion estimation method of claim 7 wherein

said terminating step terminates said iteration process when said error gradient is less than said predetermined threshold.

9. The motion estimation method of claim 6 further comprising the step of

limiting the maximum motion vector displacement to be less than a selected maximum displacement threshold value.

10. The motion estimation method of claim 6 further comprising the step of

limiting the maximum value of the multiplicative product to be less than a selected maximum update threshold step size.

11. In an image sequence transmission method for transmitting a sequence of images over a bandwidth limited channel, a motion estimation method for estimating for successive image frames, a measure of motion displacement between successive images comprising the steps of

dividing each said image into non-overlapping blocks, each block having a plurality of picture elements,

generating an initial value of the motion vector displacement for a block from a weighted average of previously determined motion vector displacements for adjacent blocks,

iteratively determining, using a steepest descent method, succession values of said motion vector displacement for successive blocks of an image,

modifying, for each iteration, a previous motion vector displacement in accordance with a multiplicative product of an incremental step value and an error gradient,

adaptively modifying an initial step value in accordance with said error gradient value, and

terminating said iteration step for a block when a multiplicative product of said initial step value and said error gradient is less than a predetermined threshold value.

12. In an image sequence transmission system for transmitting a sequence of images over a bandwidth limited channel, a motion estimation apparatus for estimating, for successive image frames, a measure of motion displacement between successive images comprising

means for dividing each said image into non-overlapping blocks, each block having a plurality of picture elements,

means for selecting an initial value of a motion vector displacement for each successive block,

means for iteratively determining, using a steepest descent approach, successive values of said motion vector displacement for successive blocks for an image, and

means for terminating said iteration for a block when an iteration error measure associated with said steepest descent, is less than a predetermined threshold value.

13. The motion estimation apparatus of claim 12 wherein said selecting means comprises

means for generating said initial value of the motion vector displacement for a block from a weighted average of previously determined motion vector displacements for adjacent blocks.

14. The motion estimation apparatus of claim 13 wherein said selecting means further comprises

means for selecting, for said adjacent blocks, a previous block on the same block scan line and a previous, a corresponding, and a future block on a previous block scan line.

15. The motion estimation apparatus of claim 14 wherein said weighting factors are respectively 0.3, 0, 0.4, and 0.3 for said previous block on said same block scan line, and said previous, corresponding, and future blocks of the previous block scan line.

16. The motion estimation apparatus of claim 12 wherein said iteratively determining means comprises

means for modifying, for each iteration, a previous motion vector displacement in accordance with a multiplicative product of an incremental step value and an error gradient, and

said terminating means terminates said iteration means when said multiplicative product is less than said predetermined threshold value.

17. The motion estimation apparatus of claim 12 further wherein said determining means comprises

means for modifying, for each iteration, a previous motion vector displacement in accordance with a multiplicative product of an incremental step value and an error gradient, and

means for adaptively modifying an initial incremental step value in accordance with said error gradient value.

18. The motion estimation apparatus of claim 17 wherein said modifying means further comprises

means for multiplying a step value for a previous iteration by a constant having a value dependent upon the error gradients of at least the last two iterations.

19. The motion estimation apparatus of claim 18 wherein

said terminating means terminates said iteration means when said error gradient is less than said predetermined threshold.

20. The motion estimation apparatus of claim 17 further comprising

means for limiting the maximum motion vector displacement to be less than a selected maximum displacement threshold value.

21. The motion estimation apparatus of claim 17 further comprising

means for limiting the maximum value of the multiplicative product to be less than a selected update threshold step size.

22. In an image sequence transmission system for transmitting a sequence of images over a bandwidth limited channel, a motion estimation apparatus for estimating, for successive image frames, a measure of motion displacement between successive images comprising

means for dividing each said image into non-overlapping blocks, each block having a plurality of picture elements,

means for generating an initial value of the motion vector displacement for a block from a weighted average of previously determined motion vector displacements for adjacent blocks,

means for iteratively determining, using a steepest descent approach, successive values of said motion vector displacement for successive blocks for an image,

means for modifying, for each iteration, a previous motion vector displacement in accordance with a multiplicative product of an incremental step value and an error gradient,

means for adaptively modifying an initial step value in accordance with said error gradient value, and

means for terminating said iteration for a block when a multiplicative product of the initial step value and said error gradient is less than a predetermined threshold value.