Transformation block optimization method

• US 5,825,929 A
• Filed: 06/04/1996
• Issued: 10/20/1998
• 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): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/659,309
• Time in Patent Office: 868 Days
• Field of Search: 382/232, 382/236, 382/238, 382/292, 348/180, 348/193
• US Class Current: 382/236
• 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 transformation block optimization method provides transformation blocks of variable size for video compression processes. The method includes defining a transformation block of multiple pixels in an image frame and determining a peak signal-to-noise ratio for the transformation block. The transformation block is tentatively subdivided into subcomponents for which a signal-to-noise ratio is also obtained. The subcomponents are adopted as transformation blocks whenever the signal-to-noise ratios of the subcomponents are greater than the signal-to-noise ratio of the transformation block by more than a predetermined threshold.

Claims

1. In a method of encoding in a compressed format video information within a video image frame sequence having first and second video image frames, a method of defining a transformation image frame component having video information in the first video image frame for transformation to the second video image frame, comprising:

defining the image frame component in the first video image frame and determining a signal-to-noise ratio for the video information within the image frame component;

tentatively subdividing the image frame component into plural image frame subcomponents and determining a signal-to-noise ratio for the video information within the image frame subcomponents; and

adopting the image frame subcomponents as image frame components whenever the signal-to-noise ratio for the image frame subcomponents is greater than the signal-to-noise ratio for the image frame component by more than a predetermined threshold.

2. The method of claim 1 in which the image frame subcomponents are adopted as image frame components and the method further comprises:

tentatively subdividing each adopted image frame component into plural subsequent image frame subcomponents and determining a signal-to-noise ratio for the video information within the subsequent image frame subcomponents; and

adopting the subsequent image frame subcomponents as image frame components whenever the signal-to-noise ratio for the subsequent image frame subcomponents is greater than the signal-to-noise ratio of the adopted image frame component by more than the predetermined threshold.

3. The method of claim 1 in which each video image frame is formed of multiple pixels with color component values and the signal-to-noise ratios are determined with respect to variances of the color component values of the pixels in the image frame components and subcomponents.

4. The method of claim 1 in which the image frame component is a right regular block of multiple pixels.

5. The method of claim 4 in which the image frame component has user-defined dimensions.

6. The method of claim 1 in which the image frame component and the image frame subcomponents are right regular blocks of multiple pixels.

7. The method of claim 1 in which each video image frame is formed of a foreground and a background portion and in which the background portion is different in each frame.

8. A method of encoding in a compressed format video information within an image frame component of a video image frame, comprising:

determining an estimated image component corresponding to the image frame component;

identifying an estimated error between the estimated image component and the image frame component;

determining a signal-to-noise ratio between the video information within the image frame component and the estimated image component;

tentatively subdividing the image frame component into plural image frame subcomponents and determining a signal-to-noise ratio for the video information within the image frame subcomponents; and

adopting the image frame subcomponents as image frame components whenever the signal-to-noise ratio for the image frame subcomponents is greater than the signal-to-noise ratio of the image frame component by more than a predetermined threshold.

9. The method of claim 8 in which the image frame subcomponents are adopted as image frame components and the method further comprises:

tentatively subdividing each adopted image frame component into plural subsequent image frame subcomponents and determining a signal-to-noise ratio for the video information within the subsequent image frame subcomponents; and

adopting the subsequent image frame subcomponents as image frame components whenever the signal-to-noise ratio for the subsequent image frame subcomponents is greater than the signal-to-noise ratio of the adopted image frame component by more than the predetermined threshold.

10. The method of claim 8 in which each video image frame is formed of multiple pixels with color component values and the signal-to-noise ratios are determined with respect to variances of the color component values of the pixels in the image frame components and the estimated image component.

11. The method of claim 8 in which the image frame component is a right regular block of multiple pixels.

12. The method of claim 8 in which the video image frame is included in a video image frame sequence having another video image frame that precedes the video image frame and includes the image frame component, and in which determining the estimated image component includes applying an affine transformation to a representation of the image frame component in the other video image frame.

13. The method of claim 8 further comprising:

determining estimated image subcomponents corresponding to the image frame subcomponents;

identifying estimated errors between the estimated image subcomponents and the image frame subcomponents; and

determining signal-to-noise ratios between the video information within the image frame subcomponents and the estimated image subcomponents.

14. The method of claim 12 in which the video image frame is included in a video image frame sequence having another video image frame that precedes the video image frame and includes the image frame component, and in which determining the estimated image subcomponents includes applying affine transformations to a representation of the image frame component in the other video image frame.

15. A computer-readable medium storing computer-executable programming for defining a transformation image frame component having video information in a first video image frame for transformation to a second video image frame, the medium comprising:

programming for defining the image frame component in the first video image frame and determining a signal-to-noise ratio for the video information within the image frame component;

programming for tentatively subdividing the image frame component into plural image frame subcomponents and determining a signal-to-noise ratio for the video information within the image frame subcomponents; and

programming for adopting the image frame subcomponents as image frame components whenever the signal-to-noise ratio for the image frame subcomponents is greater than the signal-to-noise ratio of the image frame component by more than a predetermined threshold.

16. The medium of claim 15 in which the image frame subcomponents are adopted as image frame components and the medium further comprises:

programming for tentatively subdividing each adopted image frame component into plural subsequent image frame subcomponents and determining a signal-to-noise ratio for the video information within the subsequent image frame subcomponents; and

programming for adopting the subsequent image frame subcomponents as image frame components whenever the signal-to-noise ratio for the subsequent image frame subcomponents is greater than the signal-to-noise ratio of the adopted image frame component by more than the predetermined threshold.

17. The medium of claim 15 in which each video image frame is formed of multiple pixels with color component values and the signal-to-noise ratios are determined with respect to variances of the color component values of the pixels in the image frame components and subcomponents.