Method for generating sprites for object-based coding sytems using masks and rounding average

• US 6,037,988 A
• Filed: 06/23/1997
• Issued: 03/14/2000
• Est. Priority Date: 03/22/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Ming-Chieh, Gu, Chuang, Chen, Wei-ge
• Primary Examiner(s): BRITTON, HOWARD W
• Application Number:
  US08/881,901
• Time in Patent Office: 995 Days
• Field of Search: 348/699, 348/384, 348/390, 348/400, 348/401, 348/402, 348/409, 348/413, 348/415, 348/416, 382/190, 382/203, 382/232, 382/236, 382/238, 382/241, 382/243
• US Class Current: 375/240.16
• 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/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/649 the transform being applied to non rectangular image segments

Abstract

A sprite generation method used in video coding generates a sprite from the video objects in the frames of a video sequence. The method estimates the motion between a video object in a current frame and a sprite constructed from video objects for previous frames. Specifically, the method computes motion coefficients of a 2D transform that minimizes the intensity errors between pixels in the video object and corresponding pixels inside the sprite. The method uses the motion coefficients from the previous frame as a starting point to minimizing the intensity errors. After estimating the motion parameters for an object in the current frame, the method transforms the video object to the coordinate system of the sprite. The method blends the warped pixels of the video object with the pixels at corresponding positions in the sprite using rounding average such that each video object in the video sequence provides substantially the same contribution to the sprite.

Claims

1. A method used in object-based video coding for generating sprites from video objects in a video sequence, the method comprising:

computing motion parameters that estimate motion of a video object in a current frame relative to a previously constructed sprite;

warping the video object into the previously constructed sprite using the motion parameters; and

incrementally blending the warped video object with the previously constructed sprite by weighting the previously constructed sprite in proportion to the number of times that the sprite has been updated with a warped video object of a previous frame such that each warped video object in the video sequence provides substantially the same contribution to a final sprite representing the video object throughout a video sequence.

2. The method of claim 1 wherein the motion parameters are a set of motion coefficients and the step of computing motion parameters includes attempting to find a set of motion coefficients that minimizes error between pixel values in the video object for a current frame with pixel values at corresponding pixel positions in the previously constructed sprite, where the corresponding pixel positions are determined by warping pixel coordinates of pixels in the video object to the coordinate space of the sprite.

3. The method of claim 2 wherein the step of computing motion parameters includes minimizing the sum of squared intensity errors between pixel values in the video object for a current frame with corresponding pixel values in the previously constructed sprite.

4. The method of claim 2 wherein the video object and the previously constructed sprite each have a mask to specify which pixel positions are located within the video object and sprite, respectively,

and wherein the minimizing step includes using the masks to ensure that that the error is computed only for cases where a pixel in the video object has a corresponding pixel inside the mask of the previously constructed sprite.

5. The method of claim 1 wherein the step of computing the motion parameters includes using the motion parameters computed for a previous frame as a starting point for computing the motion parameters for a current frame.

6. The method of claim 1 wherein the blending step comprises blending the warped video object for the current frame with a previously constructed sprite using the following expression:

space="preserve" listing-type="equation">S.sub.i =(i*S.sub.i-1 +W.sub.i)/(i+1)

where S_i is the sprite for the current frame, i is a weighting factor proportional to the number of video objects from which the previously constructed sprite S_i-1 has been constructed, and W_i is the warped object for the current frame; and

repeating the blending step to combine warped objects from each subsequent frame with a sprite constructed from each previous frame.

7. A computer-readable medium having computer executable instructions for performing the steps of claim 1.

8. A method used in object-based video coding for generating sprites from video objects in a video sequence, the method comprising:

computing motion parameters that estimate motion of a video object in a current frame relative to a previously constructed sprite by finding a set of motion parameters that minimizes intensity errors between pixels within a mask of the video object and corresponding pixels within a mask of the sprite;

warping the video object into the previously constructed sprite using the motion parameters; and

incrementally blending the warped video object with the previously constructed sprite.

9. The method of claim 8 wherein the blending step comprises:

weighting the previously constructed sprite in proportion to the number of times that the sprite has been updated with a warped video object of a previous frame such that each warped video object in the video sequence provides substantially the same contribution to a final sprite representing the video object throughout a video sequence.

10. The method of claim 8 wherein the step of computing the motion parameters includes using the motion parameters of a previous frame as a starting point to finding the set of motion parameters that minimizes the intensity errors.

11. A computer-readable medium having computer executable instructions for performing the steps of claim 8.

12. A method used in object-based video coding for generating sprites from video objects in a video sequence, the method comprising:

computing motion coefficients of a 2D transform that estimate motion of a video object in a current frame relative to a previously constructed sprite by finding a set of motion coefficients that minimizes intensity errors between pixels within a mask of the video object and corresponding pixels within a mask of the sprite, where location of the corresponding pixels in the sprite are computed by warping the pixels in the video object with the set of motion coefficients;

warping the video object into the previously constructed sprite using the motion parameters; and

incrementally blending the warped video object with the previously constructed sprite by weighting the previously constructed sprite in proportion to the number of times that the sprite has been updated with a warped video object of a previous frame such that each warped video object in the video sequence provides substantially the same contribution to a final sprite representing the video object throughout a video sequence.

13. The method of claim 12 wherein the 2D transform is a perspective transform.

14. The method of claim 12 wherein the blending step comprises blending the warped video object for the current frame with a previously constructed sprite using the following expression:

space="preserve" listing-type="equation">S.sub.i =(i*S.sub.i-1 +W.sub.i)/(i+1)

where S_i is the sprite for the current frame, i is a weighting factor proportional to the number of video objects from which the previously constructed sprite S_i-1 has been constructed, and W_i is the warped object for the current frame; and

repeating the blending step to combine warped objects from each subsequent frame with a sprite constructed from each previous frame.

15. A computer-readable medium having computer executable instructions for performing the steps of claim 12.

16. A sprite generator comprising:

means for computing motion parameters that map a video object in a current frame into a previously constructed sprite;

means for warping the video object into the previously constructed sprite using the motion parameters; and

means for incrementally blending the warped video object with the previously constructed sprite by weighting the previously constructed sprite in proportion to the number of times that the sprite has been updated with a warped video object of a previous frame such that each warped video object in the video sequence provides substantially the same contribution to a final sprite representing the video object throughout a video sequence.

17. The sprite generator of claim 16 further including frame memory for storing a sprite constructed from the warped video object and the previously constructed sprite;

wherein the frame memory is in communication with the means for computing motion parameters and the means for incrementally blending.

18. The sprite generator of claim 16 wherein the motion parameters are a set of motion coefficients and the means for computing the motion parameters includes means for attempting to find a set of motion coefficients that minimizes error between pixel values in the video object for a current frame with corresponding pixel values in the previously constructed sprite.

19. The sprite generator of claim 18 wherein means for attempting to find a set of motion coefficients includes means for minimizing the sum of squared intensity errors between pixel values in the video object for a current frame with corresponding pixel values in the previously constructed sprite.

20. The sprite generator of claim 18 wherein the video object and the previously constructed sprite each have a mask to specify pixels located within the video object and sprite, respectively,

and wherein the means for minimizing includes means for checking whether a pixel location is inside a mask to ensure that that the error is computed only for cases where a pixel in the video object has a corresponding pixel inside the mask of the previously constructed sprite.

21. The sprite generator of claim 18 wherein the means for computing the motion parameters includes means for using the motion parameters computed for a previous frame as a starting point for computing the motion parameters for a current frame.

22. A method of encoding in a compressed format information within a video image frame sequence having first and second video frames that include general arbitrary image objects with arbitrary configurations, the image objects undergoing changes between, and having different attributes in, the first and second video image frames, at least one of the image objects being a sprite-defined image object defined initially by a sprite and a trajectory, wherein the sprite-defined object includes a single instance of pixel information used to construct the object in at least two frames of the video sequence, and where one or more trajectories are used to compute the position of the pixel information in the frames of the video sequence, the method comprising:

for the general image objects, determining estimated image objects in the second video image frame;

identifying differences between the estimated image objects in the second video image frame and the image objects in the second video image frame to determine transform errors for the image objects; and

encoding the transform error in a first compressed format; and

for the sprite-defined object, encoding the sprite and the trajectory.

23. The method of claim 22 further comprising encoding the sprite by a lossy encoding process and the trajectory by a lossless encoding process.

24. The method of claim 23 in which encoding the trajectory comprises differentially encoding x and y components of feature points of the sprite-defined object for each frame in the video image sequence.

25. The method of claim 24 in which encoding the trajectory comprises encoding the x and y components of the feature points with QM-coding.

26. The method of claim 22 in which the sprite corresponds to an image background in the video image frame sequence.

27. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 22.

28. The method of claim 22 wherein the sprite-defined object defines objects in each frame of a sequence, the sequence being more than two frames, and wherein the sprite-defined object and the one or more trajectories are used to construct the object in each of the frames in the sequence.

29. The method of claim 28 wherein the sprite-defined image object includes trajectories for each of the frames in the sequence and the trajectories are used to compute the position of pixels in the sprite in each of the frames.

30. The method of claim 22 wherein the trajectories include two-dimensional image transforms.

31. A method of encoding in a compressed format information within a video image frame sequence having first and second video image frames that include general arbitrary image objects with arbitrary configurations, the image objects undergoing changes between, and having different attributes in, the first and second video image frames, the method comprising:

encoding at least one of the image objects as a sprite-defined image object defined initially by a sprite and a predefined trajectory, wherein the encoded sprite-defined object includes a single instance of pixel information used to construct the object in at least two frames of the video sequence, and one or more trajectories used to compute the position of the pixel information in the frames of the video sequence; and

encoding the general image objects other than the sprite-defined image object with respect to changes between the first and second video image frames other than predefined trajectories.

32. The method of claim 31 in which encoding the general image objects other than the sprite-defined image object comprises determining estimated changes in the general image objects between the first and second video image frames and feedback correcting the estimated changes.

33. The method of claim 31 in which encoding the general image objects other than the sprite-defined image object comprises determining estimated general image objects in the second video image frame;

identifying differences between the estimated general image objects in the second video image frame and the general image objects in the second video image frame to determine transform errors; and

encoding the transform errors.

34. The method of claim 31 further comprising encoding the sprite by a lossy encoding process and the trajectory by a lossless encoding process.

35. The method of claim 34 in which encoding the trajectory comprises differentially encoding x and y components of feature points of the sprite-defined object for each frame in the video image sequence.

36. The method of claim 35 in which encoding the trajectory comprises encoding the x and y components of the feature points with QM-coding.

37. The method of claim 31 in which the sprite corresponds to an image background in the video image frame sequence.

38. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 31.

39. A computer-readable medium having stored thereon a data structure representing in a compressed format information within a video image frame sequence having first and second video image frames that include general arbitrary image objects with arbitrary configurations, the image objects undergoing changes between, and having different attributes in, the first and second video image frames, the data structure comprising:

an encoded sprite-defined image object representing at least one of the general arbitrary image objects by an encoded sprite and predefined trajectory, wherein the sprite-defined object includes a single instance of pixel information used to construct the object in at least two frames of the video sequence, and wherein one or more trajectories used to compute the position of the pixel information in the frames of the video sequence are encoded in coordinates of feature points located in the frames; and

plural encoded general image objects other than the sprite-defined image object represented by encoded changes between the first and second video image frames other than predefined trajectories.

40. The memory of claim 39 in which the encoded sprite-defined image object comprises an encoded sprite and an encoded trajectory that are encoded in respective first and second encoding formats.

41. The memory of claim 39 in which the encoded sprite-defined image object comprises a lossy encoded sprite.

42. The memory of claim 39 in which the encoded sprite-defined image object comprises a lossless encoded trajectory.

43. The memory of claim 39 in which the encoded general image objects other than the sprite-defined image object comprise representations of encoded feedback corrections of estimated changes in the general image objects between the first and second video image frames.