System and method for encoding video data using computationally efficient adaptive spline wavelets

• US 6,587,507 B1
• Filed: 03/24/2000
• Issued: 07/01/2003
• Est. Priority Date: 06/02/1997
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Picsurf, Inc.
• Inventors: Zhong, Lefan, Chui, Charles K.
• Primary Examiner(s): Diep, Nhon
• Application Number:
  US09/445,100
• Time in Patent Office: 1,194 Days
• Field of Search: H04/N.712, H04/N.730, 348/384.1, 348/390.1, 348/403.1, 348/404.1, 382/232, 382/248, 375/240, 375/240.02, 375/240.18, 375/240.19
• US Class Current: 375/240.19
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• 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

Abstract

A system and method for encoding a two dimensional array of data utilizes a library having entries corresponding to a set of predefined two dimensional adaptive spline wavelet waveforms. Each predefined two dimensional adaptive spline wavelet waveform is formed by the superposition of one or more B-splines. The data encoding method identifies a set of best matches between the array of data and the predefined two dimensional adaptive spline wavelet waveforms by generating the inner product of the array of data and each of the predefined two dimensional adaptive spline wavelet waveforms. Each inner product is generated by FIR filtering the data with a corresponding set of FIR filter coefficients, and then determining which of the inner products have largest values. Once a set of best matches has been found, the data encoding method generates data representing the identified set of best matches. The generated data indicates for each match: one of the library entries, a position within the array of data at which the match was found, and a magnitude of the match. The data encoding method is computationally efficient because inner products are computed by FIR filtering.

Claims

1. A method of encoding a two dimensional array of data, comprising the steps of:

accessing a library having entries corresponding to a set of predefined two dimensional adaptive spline wavelet waveforms, each predefined two dimensional adaptive spline wavelet waveforms being formed by the superposition of one or more B-splines;

identifying a set of best matches between the array of data and the predefined two dimensional adaptive spline wavelet waveforms by generating the inner product of the array of data and each of the predefined two dimensional adaptive spline wavelet waveforms, each inner product being generated by FIR filtering the data with a corresponding set of FIR filter coefficients, and then determining which of the inner products have largest values; and

generating data representing the identified set of best matches, the generated data indicating for each match;

one of the library entries, a position within the array of data at which the match was found, and a magnitude of the match.

2. The method of claim 1, wherein the inner product between the array of data and some of the predefined two dimensional adaptive spline wavelet waveforms are generated by FIR filtering another one of the inner products using FIR filter coefficients specified by the library.

3. The method of claim 1, wherein the inner product between the array of data and a first one of the predefined two dimensional adaptive spline wavelet waveforms having a low resolution level is generated by FIR filtering the inner product of the array of data and a second one of the predefined two dimensional adaptive spline wavelet waveforms having a higher resolution level, using a predefined set of resolution modifying FIR filter coefficients.

4. The method of claim 1, including:

generating the array of data by encoding a sequence of video frames into a primary data frame and a plurality of residual data frames, the array of data comprising one of the residual frames.

5. A computer program product for use in conjunction with a computer controlled system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a library having entries corresponding to a set of predefined two dimensional adaptive spline wavelet waveforms, each predefined two dimensional adaptive spline wavelet waveforms being formed by the superposition of one or more B-splines;

instructions for identifying a set of best matches between the array of data and the predefined two dimensional adaptive spline wavelet waveforms, represented by the entries in the library, including instructions for generating the inner product of the array of data and each of the predefined two dimensional adaptive spline wavelet waveforms, each inner product being generated by FIR filtering the data with a corresponding set of FIR filter coefficients, and then determining which of the inner products have largest values; and

instructions for generating data representing the identified set of best matches, the generated data indicating for each match;

one of the library entries, a position within the array of data at which the match was found, and a magnitude of the match.

6. The computer program product of claim 5, wherein the inner product between the array of data and some of the predefined two dimensional adaptive spline wavelet waveforms are generated by FIR filtering another one of the inner products using FIR filter coefficients specified by the library.

7. The computer program product of claim 5, wherein the inner product between the array of data and a first one of the predefined two dimensional adaptive spline wavelet waveforms having a low resolution level is generated by FIR filtering the inner product of the array of data and a second one of the predefined two dimensional adaptive spline wavelet waveforms having a higher resolution level, using predefined set of resolution modifying FIR filter coefficients.

8. The computer program product of claim 5, including instructions for generating the array of data by encoding a sequence of video frames into a primary data frame and a plurality of residual data frames, the array of data comprising one of the residual data frames.

9. Image data processing apparatus, comprising:

memory storing a library having entries corresponding to a set of predefined two dimensional adaptive spline wavelet waveforms, each predefined two dimensional adaptive spline wavelet waveforms being formed by the superposition of one or more B-splines;

a processing unit for executing instructions in procedures;

one or more image processing modules, stored in the memory and containing instructions executable by the processing unit, the one or more processing modules including;

instructions for identifying a set of best matches between the array of data and the predefined two dimensional adaptive spline wavelet waveforms, represented by the entries in the library, including instructions for generating the inner product of the array of data and each of the predefined two dimensional adaptive spline wavelet waveforms, each inner product being generated by FIR filtering the data with a corresponding set of FIR filter coefficients, and then determining which of the inner products have largest values; and

instructions for generating data representing the identified set of best matches, the generated data indicating for each match;

one of the library entries, a position within the array of data at which the match was found, and a magnitude of the match.

10. The image data processing apparatus of claim 9, wherein the instructions for generating the inner product of the array of data and some of the predefined two dimensional adaptive spline wavelet waveforms include instructions for FIR filtering another one of the inner products using FIR filter coefficients specified by the library.

11. The image data processing apparatus of claim 9, wherein the instructions for generating the inner product between the array of data and a first one of the predefined two dimensional adaptive spline wavelet waveforms having a low resolution level includes instructions for FIR filtering the inner product of the array of data and a second one of the predefined two dimensional adaptive spline wavelet waveforms having a higher resolution level, using a predefined set of resolution modifying FIR filter coefficients.

12. The image data processing apparatus of claim 9, including instructions for generating the array of data by encoding a sequence of video frames into a primary data frame and plurality of residual data frames, the array of data comprising one of the residual data frames.