Overcomplete basis transform-based motion residual frame coding method and apparatus for video compression

• US 20090103602A1
• Filed: 03/29/2004
• Published: 04/23/2009
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: Etiip Holdings Incorporated
• Original Assignee: Digital Accelerator Corporation (Even Technologies, Inc.)
• Inventors: Xiong, Yi, Sauer, Mark, Wang, Meng, Koat, Peter
• Granted Patent: US 8,204,109 B2
• Time in Patent Office: Days
• US Class Current: 375/240.10
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

The present invention provides a method to compress digital moving pictures or video signals based on an overcomplete basis transform using a modified Matching Pursuit algorithm. More particularly, this invention focuses on the efficient coding of the motion residual image, which is generated by the process of motion estimation and compensation. A residual energy segmentation algorithm (RESA) can be used to obtain an initial estimate of the shape and position of high-energy regions in the residual image. A progressive elimination algorithm (PEA) can be used to reduce the number of matching evaluations in the matching pursuits process. RESA and PEA can speed up the encoder by many times for finding the matched basis from the pre-specified overcomplete basis dictionary. Three parameters of the matched pattern form an atom, which defines the index into the dictionary and the position of the selected basis, as well as the inner product between the chosen basis pattern and the residual signal. The present invention provides a new atom position coding method using quad tree like techniques and a new atom modulus quantization scheme. A simple and efficient adaptive mechanism is provided for the quantization and position coding design to allow a system according to the present invention to operate properly in low, medium and high bit rate situations. These new algorithm components can result in a faster encoding process and improved compression performance over previous matching pursuit based video coders.

Claims

1. A method for encoding a residual image using basis functions from an overcomplete library, said method comprising the steps of:

a) obtaining the residual image, said residual image having a size and an energy; and

b) decomposing said residual image into a list of one or more atoms, each atom representing a basis function from the overcomplete library, said step of decomposing said residual image including the steps of;

i) identifying a replacement region in the residual image for representation by an atom using a residual energy segmentation algorithm;

ii) creating a subset of basis functions from the overcomplete library, each basis function in the subset matching with the replacement region within a predetermined threshold;

iii) identifying an atom within the subset of basis functions, said atom for representing the replacement region and said atom having parameters;

iv) quantizing said atom and modifying the parameters of the atom into a form suited for encoding;

v) encoding said quantized atom, subtracting said atom from the replacement region in the residual image thereby reducing the energy of the residual image and using a quadtree-based atom coder to reduce the size of the residual image; and

vi) comparing the reduced size of the residual image or the reduced energy of the residual image with a predetermined criteria and repeating steps (i) to (vi) until the predetermined criteria is achieved;

thereby encoding said residual image and reducing the size thereof to a predetermined level.

2. The method according to claim 1, wherein the step of identifying an atom within the subset of basis functions is performed using a progressive elimination algorithm.

3. The method according to claim 1, wherein the step of identifying a replacement region comprises the generation of a RESA rectangle.

4. The method according to claim 3, wherein the step of identifying a replacement region comprises identification of an initial region within the residual image having a highest energy, and growing the RESA rectangle therefrom.

5. The method according to claim 1, wherein the step of identifying an atom within the subset of basis functions comprises determining an inner product between a basis function and the replacement region, wherein a maximum absolute value of the inner product indicates a best match.

6. The method according to claim 3, wherein the RESA rectangle is compared to the basis functions within the overcomplete library and the basis functions that are sufficiently match the RESA rectangle are placed in the subset of basis functions.

7. The method according to claim 2, wherein the progressive elimination algorithm removes basis functions from the subset of basis functions by comparing a basis function currently being evaluated with a previously evaluated basis function.

8. The method according to claim 1, wherein the step of quantizing the atom comprises determining a quantizer based on a comparison between the atom and the replacement region.

9. The method according to claim 1, wherein the predetermined criteria is determined based on a desired bit stream size.

10. An apparatus for encoding a residual image using basis functions from an overcomplete library, said apparatus comprising:

a) means for obtaining the residual image, said residual image having a size and an energy; and

b) means for decomposing said residual image into a list of one or more atoms, each atom representing a basis function from the overcomplete library, said means for decomposing said residual image including;

i) means for identifying a replacement region in the residual image for representation by an atom using a residual energy segmentation algorithm;

ii) means for creating a subset of basis functions from the overcomplete library, each basis function in the subset matching with the replacement region within a predetermined threshold;

iii) means for identifying an atom within the subset of basis functions, said atom for representing the replacement region and said atom having parameters;

iv) means for quantizing said atom and modifying the parameters of the atom into a form suited for encoding;

v) means for encoding said quantized atom, subtracting said atom from the replacement region in the residual image thereby reducing the energy of the residual image and using a quadtree-based atom coder to reduce the size of the residual image; and

vi) means for comparing the reduced size of the residual image or the reduced energy of the residual image with a predetermined criteria;

thereby encoding said residual image and reducing the size thereof to a predetermined level.

11. A computer program product comprising a computer readable medium having a computer program recorded thereon for performing a method for encoding a residual image using basis functions from an overcomplete library comprising the steps of:

a) obtaining the residual image, said residual image having a size and an energy; and

b) decomposing said residual image into a list of one or more atoms, each atom representing a basis function from the overcomplete library, said step of decomposing said residual image including the steps of;

i) identifying a replacement region in the residual image for representation by an atom using a residual energy segmentation algorithm;

ii) creating a subset of basis functions from the overcomplete library, each basis function in the subset matching with the replacement region within a predetermined threshold;

iii) identifying an atom within the subset of basis functions, said atom for representing the replacement region and said atom having parameters;

iv) quantizing said atom and modifying the parameters of the atom into a form suited for encoding;

v) encoding said quantized atom, subtracting said atom from the replacement region in the residual image thereby reducing the energy of the residual image and using a quadtree-based atom coder to reduce the size of the residual image; and

vi) comparing the reduced size of the residual image or the reduced energy of the residual image with a predetermined criteria and repeating steps (i) to (vi) until the predetermined criteria is achieved;

thereby encoding said residual image and reducing the size thereof to a predetermined level.