Dynamic sprites for encoding video data

• US 5,943,445 A
• Filed: 12/19/1996
• Issued: 08/24/1999
• Est. Priority Date: 12/19/1996
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Dufaux, Frederic A.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tadayon, Bijan
• Application Number:
  US08/769,559
• Time in Patent Office: 978 Days
• Field of Search: 348/699, 348/700, 348/208, 348/416, 348/113, 358/261.2, 358/428, 358/430, 358/432, 382/100, 382/190, 382/215, 382/107, 382/236, 382/282, 382/283, 382/106, 382/171, 382/173, 382/174, 382/180, 382/181, 382/192, 382/195, 382/197, 382/199, 382/201, 382/202 , 382/203, 382/204, 382/207, 382/209, 382/210, 382/217, 382/224, 382/225, 382/232, 382/235, 382/238, 382/239, 382/240, 382/241, 382/242, 382/243, 382/244, 382/248 , 382/251, 382/308, 701/28, 701/200, 901/47
• US Class Current: 382/236
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/58 Motion compensation with long-term prediction, i.e. the reference frame for a current frame not being the temporally closest one H04N19/23 takes precedence

Abstract

Video data representing a scene are processed to improve encoding efficiencies. The video data are segmented into rigidly and non-rigidly moving video objects. The segmentation is preformed by estimating local motion vectors for the video data of a sequence of frames. The local motion vectors are clustered to determine dominant motions, and video data having motion vectors similar to the dominant motions are segmented out as rigidly moving video objects. For these objects, motion parameters are robustly estimated. Using the motion parameters, the rigid video objects of the frames are integrated in one or more corresponding sprites stored in a long-term memory. The sprites can be used in a two-way motion compensated prediction technique for encoding video data where blocks of video data are encoded either from sprites based on rigid motion parameters, or from a previous frame based on local motion parameters. In addition, the sprites can be used to construct a high resolution panoramic view of the background of a scene.

Claims

1. A computer implemented method for processing video data representing a scene, comprising the steps of:

segmenting the video data into rigidly and non-rigidly moving video objects;

estimating motion information for the rigidly moving objects; and

integrating the rigidly moving objects, using the motion information, incrementally into corresponding dynamic sprites stored in memory.

2. The method of claim 1 further comprising:

estimating local motion vectors for the video data;

clustering the local motion vectors to determine dominant motions; and

segmenting the video data having local motion vectors substantially similar to the dominant motions as the rigidly moving video objects.

3. The method of claim 2 further comprising:

determining first residual information present in a prediction error of the dominant motions;

determining second residual information present in a prediction error of the local motion vectors;

segmenting the video data as the rigidly moving video objects if the first residual information are substantially similar to the second residual information, otherwise, segmenting the video data as non-rigidly moving video objects.

4. The method of claim 1 further comprising:

estimating the dominant motions using a parametric motion model.

5. The method of claim 4 wherein the parametric motion model is a perspective motion model.

6. The method of claim 2 wherein there is one video object and a corresponding sprite for each dominant motion.

7. The method of claim 1 wherein the video data are organized as a temporal sequence of frames, and further comprising:

aligning the frames with respect to a coordinate system.

8. The method of claim 7 further comprising:

aligning the frames with respect to a first frame of the temporal sequence of frames to establish a fixed reference coordinate system for the sprites.

9. The method of claim 8 wherein each frame and each sprite includes a plurality of pixels, each pixel representing a light intensity value of the scene, and further comprising:

warping pixels of a current frame of the temporal sequence of frames to the fixed reference coordinate system of the sprites using a backward transform prior to integrating.

10. The method of claim 7 further comprising:

aligning the sprites with respect to a current frame of the temporal sequence of frames to establish a time-varying coordinate system for the sprites.

11. The method of claim 10 wherein each frame and each sprite includes a plurality of pixels, each pixel representing a light intensity value of the scene, and further comprising:

warping pixels of the, sprites to a current frame of the temporal sequence of frames using a forward transform prior to integrating.

12. The method of claim 1 further comprising:

encoding the video data, and motion and shape information as encoded data using an encoder of a first processing system;

decoding the encoded data using a first decoder to build a first sprite in a first memory of the first processing system;

transmitting the encoded data to a second processing system;

decoding the encoded data using a second decoder to build a second sprite in a second memory of the second processing system, the first and second sprites being substantially identical.

13. The method of claim 12 wherein the video data are organized as a temporal sequence of frames, and each frame includes a plurality of block of pixels, and further comprising:

selecting a particular block of pixels of a current frame of the temporal sequence of frames for encoding from the first sprite or from a previous frame of the temporal sequence of frames.

14. The method of claim 13 further comprising:

encoding the particular block using the motion information if the particular block is selected for encoding from the first sprite; and

encoding the particular block using the local motion vectors if the particular block is selected for encoding from the previous frame.

15. The method of claim 13 further comprising:

determining a first prediction error for the particular block based on encoding the particular block from the first sprite;

determining a second prediction error for the particular block based on encoding the particular block from the previous frame; and

selecting the particular block for encoding from the first sprite if the first prediction error is less than the second prediction error, otherwise selecting the particular block for encoding from the previous frame.

16. The method of claim 8 further comprising:

selecting one of the sprites having the fixed reference coordinate system to construct a panoramic view of a background portion of the scene represented by the video data, the panoramic view only including rigidly moving video objects.

17. An apparatus for processing video data representing a scene, comprising:

a camera acquiring video data representing light intensity values of a scene;

means for segmenting the video data into rigidly and non-rigidly moving video objects;

means for estimating motion information for the rigidly moving objects; and

a memory incrementally storing an integration of the rigidly moving objects as dynamic sprites.

18. A computer-implemented method for processing video data representing a scene comprising the steps of:

segmenting the video data into rigidly and non-rigidly moving video objects;

estimating motion information for the rigidly moving objects;

integrating the rigidly moving objects, using the motion information into at least one corresponding sprite in a memory;

wherein the video data are organized as a temporal sequence of frames, each frame includes a plurality of blocks of pixels, and a particular block of pixels of a first of the temporal sequence of frames is selected for encoding from one of the sprite and a second of the temporal sequence of frames which occurs prior to the first of the temporal sequence of frames.

19. The method of claim 18, wherein, if the particular block of pixels is selected from the sprite, the encoding uses the motion information and, if the particular block is selected from the second of the temporal sequence of frames, the encoding uses other motion information different than the motion information.

20. An apparatus for processing video data representing a scene comprising:

a processor configured to receive the video data, to segment the video data into rigidly and non-rigidly moving objects, and to estimate motion information for the rigidly moving objects;

a memory configured to incrementally store an integration of the rigidly moving objects as at least one dynamic sprite; and

an encoder configured to encode the video data using the at least one dynamic sprite.

21. The apparatus of claim 20, wherein the processor is further configured to organize the video data as a temporal sequence of frames, each frame including a plurality of blocks of pixels, and to select a particular block of pixels of a first of the temporal sequence of frames for the encoder to encode from one of the at least one sprite and a second of the temporal sequence of frames which occurs prior to the first frame.

22. A computer-implemented method for processing video data representing a scene comprising the steps of:

estimating motion information for a rigidly moving object within the scene; and

building at least one dynamic sprite by incrementally integrating the rigidly moving object using the motion information.

23. The method of claim 22, further comprising the step of:

encoding the video data using the at least one sprite.