Encoding method for the compression of a video sequence

• US 6,519,284 B1
• Filed: 07/14/2000
• Issued: 02/11/2003
• Est. Priority Date: 07/20/1999
• Status: Expired due to Term

• Current Assignee: Funai Electric Co., Ltd. (Funai Electric Holdings Company Limited)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Pesquet-Popescu, Beatrice, Benetiere, Marion
• Primary Examiner(s): DIEP, NHON THANH
• Application Number:
  US09/616,730
• Time in Patent Office: 942 Days
• Field of Search: H04/N.712, 375/240.03, 375/240.11, 375/240.08, 375/240.19, 375/240.22, 348/398.1, 348/399.1, 382/232, 382/233, 382/234, 382/240, 382/238
• US Class Current: 375/240.11
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/615 using motion compensated temporal filtering [MCTF]
• 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]
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression

Abstract

The invention relates to an encoding method for the compression of a video sequence divided into groups of frames decomposed by means of a tridimensional wavelet transform. According to this method, based on the hierarchical subband encoding process SPIHT and applied to the band-pass subbands of a spatio-temporal orientation tree defining the spatio-temporal relationship within the hierarchical pyramid of the obtained transform coefficients, a vectorial DPCM, using either constant prediction coefficients or adaptive ones for taking into account scene changes, is used to separately encode the lowest frequency spatio-temporal subband, and the quantification of the prediction error observed when constructing a spatio-temporal predictor for each vector of transform coefficients having components in each frame of said subband is carried out by means of a scalar or vectorial quantization. The final binary stream resulting from these modulation and quantification steps is encoded by a lossless technique minimizing the entropy of the whole message.

Claims

1. An encoding method for the compression of a video sequence divided in groups of frames decomposed by means of a tridimensional (3D) wavelet transform leading to a given number of successive resolution levels, said method being based on a hierarchical subband encoding process called “

set partitioning in hierarchical trees”

(SPIHT) and leading from the original set of picture elements (pixels) of each group of frames to transform coefficients encoded with a binary format and constituting a hierarchical pyramid, said coefficients being ordered by means of magnitude tests involving the pixels represented by 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 partitioning subsets according to a division process that continues until each significant coefficient is encoded within said binary representation, and a spatio-temporal orientation tree—

in which the roots are formed with the pixels of the approximation subband resulting from the 3D wavelet transform and the offspring of each of these pixels is formed with the pixels of the higher subbands corresponding to the image volume defined by these root pixels—

defining the spatio-temporal relationship inside said hierarchical pyramid, said method, applied to the band-pass subbands of the spatio-temporal tree, being further characterized in that;

(A) a vectorial differential pulse code modulation (DPCM) is used to separately encode the lowest frequency spatio-temporal subband, or approximation subband, according to the following conditions;

(a) a spatio-temporal predictor, using not only values at the same location in past frames of the video sequence but also neighbouring values in the current frame, is constructed for each vector of coefficients having components in each frame of the approximation subband, said vectorial coding feature coming from the fact that the lowest frequency subband contains spatial low frequency subbands from at least two frames;

(b) said DPCM uses constant prediction coefficients;

(B) the quantification of the prediction error is carried out by means of a scalar quantization of the two vector components, followed by an assignment of a unique binary code associated to the probability computed for each given couple of quantized values;

(C) the binary stream resulting from the steps (A) and (B) is encoded by a lossless process minimizing the entropy of the whole message.

3. An encoding method according to claim 1, in which said DPCM becomes adaptive, the coefficients of the spatio-temporal predictor now taking into account scene changes by means of a least means squares estimation of these coefficients for each group of frames.

4. An encoding method according to claim 3, in which a decision is taken about the fact that the predictor is most influenced by the spatial prediction or by the temporal one.

5. An encoding method according to claim 1, in which said lossless process is based on arithmetic encoding.

6. An encoding method according to claim 1, in which said lossless process is based on a Huffmann encoding.

2. An encoding method for the compression of a video sequence divided in groups of frames decomposed by means of a tridimensional (3D) wavelet transform leading to a given number of successive resolution levels, said method being based on a hierarchical subband encoding process called “

set partitioning in hierarchical trees”

(SPIHT) and leading from the original set of picture elements (pixels) of each group of frames to transform coefficients encoded with a binary format and constituting a hierarchical pyramid, said coefficients being ordered by means of magnitude tests involving the pixels represented by 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 partitioning subsets according to a division process that continues until each significant coefficient is encoded within said binary representation, and a spatio-temporal orientation tree—

in which the roots are formed with the pixels of the approximation subband resulting from the 3D wavelet transform and the offspring of each of these pixels is formed with the pixels of the higher subbands corresponding to the image volume defined by these root pixels—

defining the spatio-temporal relationship inside said hierarchical pyramid, said method, applied to the band-pass subbands of the spatio-temporal tree, being further characterized in that;

(A) a vectorial differential pulse code modulation (DPCM) is used to separately encode the lowest frequency spatio-temporal subband, or approximation subband, according to the following conditions;

(a) a spatio-temporal predictor, using not only values at the same location in past frames of the video sequence but also neighbouring values in the current frame, is constructed for each vector of coefficients having components in each frame of the approximation subband, said vectorial coding feature coming from the fact that the lowest frequency subband contains spatial low frequency subbands from at least two frames;

(b) said DPCM uses constant prediction coefficients;

(B) the quantification of the prediction error is carried out by means of a vectorial quantization using an optimal quantizer based on a generalized Lloyd-Max algorithm, a joint Laplacian probability density function for the two components of the quantized prediction error vector being considered for said optimization;

(C) the binary stream resulting from the steps (A) and (B) is encoded by a lossless process minimizing the entropy of the whole message.