Transform coding of dense motion vector fields for frame and object based video coding applications

• US 5,959,673 A
• Filed: 06/04/1996
• Issued: 09/28/1999
• Est. Priority Date: 10/05/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Ming-Chieh, Chen, Wei-ge
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): LEE, Y YOUNG
• Application Number:
  US08/657,282
• Time in Patent Office: 1,211 Days
• Field of Search: 348/420, 348/401, 348/402, 348/409, 348/412, 348/413, 348/415, 348/416, 348/699, 382/236, 382/238, 382/243, 382/246, 382/244
• US Class Current: 375/240.16
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• 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/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/563 Motion estimation with padding, i.e. with filling of non-object values in an arbitrarily shaped picture block or region for estimation purposes
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• 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 video compression encoding process compresses or encodes dense motion vector fields to provide and improved compression ratio. In accordance with this method, a dense motion vector field is obtained for an object or a portion of an object between a pair of video image frames. The dense motion vector field may correspond, for example, to an object or other image portion of arbitrary configuration or size. The configuration of the dense motion vector field is extrapolated to a regular, preferably rectangular, configuration to facilitate encoding or compression. The dense motion vector field with its extrapolated regular configuration is encoded or compressed according to conventional encoding transformations such as, for example, discrete cosine transformation (DCT) or lattice wavelet compression.

Claims

1. A compression method of representing changes between corresponding pixels in first and second video image frames, comprising:

determining motion vectors for all pixel locations in each region in a set of regions of the first video image frame by estimating the motion of all of the pixels in each region relative to pixels in the second video image frame;

wherein the regions correspond to regions of a first image feature having a non-rectangular boundary in the first image frame and the motion vectors for at least one of the regions represent a motion vector field having a non-rectangular shape corresponding to the boundary of the first image feature;

transforming the motion vector field having a non-rectangular shape to a motion vector field of rectangular configuration for encoding in the first compressed format, where the rectangular configuration comprises a two dimensional array of motion vectors, and transforming the motion vector field includes assigning motion vectors to pixel locations within the rectangular configuration but not overlapping the non-rectangular shape of the motion vector field; and

encoding the motion vectors for each of the regions in a first compressed format to produce compressed motion vectors for each region, including transforming the motion vectors for each region into spatial frequency components and transforming the motion vectors for each pixel location in the rectangular configuration into spatial frequency components.

2. The method of claim 1 in which the regions correspond to regions of a first image feature in the first image frame and determining the motion vectors includes determining a dense motion vector field between pixels of each of the regions in the first image feature and pixels of a corresponding image feature in the second video image frame, where the first image feature is coded separately from other image features in the first image frame.

3. The method of claim 1 in which determining the motion vectors includes:

identifying a first arrangement of multiple first pixels and a corresponding second arrangement of multiple second pixels in the first and second video image frames, respectively; and

identifying plural corresponding pairs of pixels in the first and second arrangements of multiple pixels and determining a motion vector for each corresponding pair of pixels.

4. The method of claim 3 in which the first and second arrangements of pixels represent first and second image features in the first and second video image frames, respectively, and the first and second image features comprise a non-rectangular video object segmented from the first and second frames.

5. The method of claim 1 in which the first compressed format includes lossy compression.

6. The method of claim 1 in which the first compressed format includes a discrete cosine transformation or lattice wavelet compression.

7. The method of claim 1 in which the first compressed format includes lossy compression and the method further comprises encoding in a second compressed format that includes lossless compression the motion vectors encoded in the first compressed format.

8. A computer-readable medium storing computer-executable programming for compressing changes between corresponding pixels in first and second video image frames, the medium comprising:

programming for determining motion vectors for all pixel locations in each region in a set of regions of the first video image frame by estimating the motion of all of the pixels in each region relative to pixels in the second video image frame; and

programming for encoding all of the motion vectors for each of the regions in a first compressed format to produce compressed motion vectors for each region, including transforming the motion vectors for each region into spatial frequency components and quantizing the spatial frequency components;

wherein the regions correspond to regions of a first image feature having a non-rectangular boundary in the first image frame and the motion vectors for at least one of the regions represent a motion vector field having a non-rectangular shape corresponding to the boundary of the first image feature, the medium further comprising programming for transforming the motion vector field having a non-rectangular shape to a motion vector field of rectangular configuration for encoding in the first compressed format, where the rectangular configuration comprises a two dimensional array of motion vectors, and the programming for transforming the motion vector field includes programming for assigning motion vectors to pixel locations within the rectangular configuration but not overlapping the non-rectangular shape of the motion vector field; and

programming for transforming the motion vectors for each pixel location in the rectangular configuration into spatial frequency components.

9. The medium of claim 8 in which the regions correspond to regions of a first image feature in the first image frame and the medium further comprises programming for determining the motion vectors as a dense motion vector field between each of the regions in the first image feature and pixels of a corresponding image feature in the second video image frame.

10. The medium of claim 8 in which the first compressed format includes lossy compression.

11. The medium of claim 8 in which the first compressed format includes lossy compression and the medium further comprises programming for encoding in a second compressed format that includes lossless compression the motion vectors encoded in the first compressed format.