Video encoding method using a wavelet transform

• US 20010046326A1
• Filed: 03/29/2001
• Published: 11/29/2001
• Est. Priority Date: 04/04/2000
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Pesquet-Popescu, Beatrice, Felts, Boris
• Granted Patent: US 6,735,342 B2
• Time in Patent Office: Days
• US Class Current: 382/240
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/62 by frequency transforming in three dimensions H04N19/63 takes precedence
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]

Abstract

The invention relates to an encoding method for the compression of a video sequence divided in flames decomposed by means of a wavelet transform. Said method, based on the hierarchical subband encoding process called “set partitioning in hierarchical trees” (SPIHT), leads from the original set of picture elements of the video sequence to wavelet transform coefficients encoded with a binary format. These coefficients are organized in trees and ordered into partitioning sets respectively corresponding to levels of significance, by means of magnitude tests leading to a classification into three ordered lists called list of insignificant sets (LIS), list of insignificant pixels (LIP) and list of significant pixels (LSP). According to the invention, a specific initialization order of the LIS is proposed. Moreover, the orientation trees defining the relationship in the hierarchical pyramid of the wavelet decomposition are explored from the lowest resolution level to the highest one, while keeping neighboring pixels together and taking account of the orientation of the details.

Claims

1. An encoding method for the compression of a video sequence including successive frames, each frame being decomposed by means of a two dimensional (2D) wavelet transform leading to a given number of successive resolution levels corresponding to the decomposition levels of said transform, said encoding method being based on the hierarchical subband encoding process called “

set partitioning in hierarchical trees”

(SPIHT) and leading from the original set of picture elements of the video sequence to wavelet transform coefficients encoded with a binary format, said coefficients being organized into spatial orientation trees rooted in the lowest frequency, or spatial approximation, subband and completed by an offspring in the higher frequency subbands, the coefficients of said trees being further ordered into partitioning sets corresponding to respective levels of significance and defined by means of magnitude tests leading to a classification of the significance information in three ordered lists called list of insignificant sets (LIS), list of insignificant pixels (LIP) and list of significant pixels (LSP), said tests being carried out in order to divide said original set of picture elements into said partitioning sets according to a division process that continues until each significant coefficient is encoded within said binary representation, said method being further characterized in that it comprises the following steps;

(A) an initialization step, in which, each pixel having coordinates (x,y) varying from 0 to size_x and from 0 to size_y respectively, said list LIS is then initialized with the coefficients of said spatial approximation subband, excepting the coefficient having the coordinates x=0(mod

     2) and y=0(mod

     2), the initialization order of the LIS being the following;

(a) put in the list all the pixels that verify x=1(mod.2) and y=0(mod.2), for the luminance component Y and then for the chrominance components U and V;

(b) put in the list all the pixels that verify x=1(mod.2) and y=1(mod.2), for Y and then for U and V;

(c) put in the list all the pixels that verify x=0(mod.2) and y=1(mod.2), for Y and then for U and V;

(B) an exploration step, in which the spatial orientation trees defining the spatial relationship in the hierarchical subband pyramid of the wavelet decomposition are explored from the lowest resolution level to the highest one, while keeping neighboring pixels together and taking account of the orientation of the details, said exploration of the offspring coefficients being implemented thanks to a zig-zag scanning order of the offspring coefficients that is shown in FIG. 7, in the case of horizontal and diagonal detail subbands, for a group of four offspring and the passage of said group to the next one in the horizontal direction, in FIG. 8 for a group of four offspring and the passage of said group to the next one in the vertical direction, and in FIGS. 9 and 10 respectively for the lowest resolution level and for the finer resolution levels.

3. Computer executable process steps provided to encode a video sequence including successive frames, said process steps being stored on a computer-readable medium and being provided in order to carry out an encoding method according to

claim 1

.

4. A computer-readable medium containing one or more software programs provided in order to carry out an encoding method according to

claim 1

.

2. An encoding method for the compression of a video sequence including successive groups of frames, each group of frames being decomposed by means of a three-dimensional (3D) wavelet transform leading to a given number of successive resolution levels corresponding to the decomposition levels of said transform, said encoding method being based on the hierarchical subband encoding process called “

set partitioning in hierarchical trees”

(SPIHT) and leading from the original set of picture elements of the video sequence to wavelet transform coefficients encoded with a binary format, said coefficients being organized into spatio-temporal orientation trees rooted in the lowest frequency, or spatio-temporal approximation, subband and completed by an offspring in the higher frequency subbands, the coefficients of said trees being further ordered into partitioning sets corresponding to respective levels of significance and defined by means of magnitude tests leading to a classification of the significance information in three ordered lists called list of insignificant sets (LIS), list of insignificant pixels (LIP) and list of significant pixels (LSP), said tests being carried out in order to divide said original set of picture elements into said partitioning sets according to a division process that continues until each significant coefficient is encoded within said binary representation, said method being further characterized in that it comprises the following steps;

(A) an initialization step, in which the spatio-temporal approximation subband that results from the 3D wavelet transform contains the spatial approximation subbands of the two frames in the temporal approximation subband, indexed by z=0 and z=1, and, each pixel having coordinates (x,y,z) varying for x and y from 0 to size_x and from 0 to size_y respectively, said list LIS is then initialized with the coefficients of said spatio-temporal approximation subband, excepting the coefficient having the coordinates of the form z=0(mod

     2), x=0(mod

     2) and y=0(mod

     2), the initialization order of the LIS being the following;

(a) put in the list all the pixels that verify x=0(mod.2) and y=0(mod.2) and z=1, for the luminance component Y and then for the chrominance components U and V;

(b) put in the list all the pixels that verify x=1(mod.2) and y=0(mod.2) and z=0, for Y and then for U and V;

(c) put in the list all the pixels that verify x=1(mod.2) and y=1(mod.2) and z=0, for Y and then for U and V;

(d) put in the list all the pixels that verify x=0(mod.2) and y=1(mod.2) and z=0, for Y and then for U and V;

(B) an exploration step, in which the spatio-temporal orientation trees defining the spatio-temporal relationship in the hierarchical subband pyramid of the wavelet decomposition are explored from the lowest resolution level to the highest one, while keeping neighboring pixels together and taking account of the orientation of the details, said exploration of the offspring coefficients being implemented thanks to a scanning order of the offspring coefficients that is shown in FIG. 7, in the case of horizontal and diagonal detail subbands, for a group of four offspring and the passage of said group to the next one in the horizontal direction, in FIG. 8 for a group of four offspring and the passage of said group to the next one in the vertical direction, and in FIGS. 9 and 10 respectively for the lowest resolution level and for the finer resolution levels.

5. Computer-executable process steps provided to encode a video sequence including successive frames, said process steps being stored on a computer-readable medium and being provided in order to carry out an encoding method according to

claim 2

.

6. A computer-readable medium containing one or more software programs provided in order to carry out an encoding method according to

claim 2

.