Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-08-06
2004-08-24
Diep, Nhon (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240110, C375S240180
Reexamination Certificate
active
06782051
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an encoding method applied to a video sequence subdivided into groups of frames (GOFs) and based on an on-line procedure that comprises the steps of:
an initializing step, provided for defining for the encoding process its input parameters;
a motion estimation/compensation step, provided for performing a motion estimation and compensation between pairs of successive frames;
a spatio-temporal decomposition step, provided for carrying out a three-dimensional (3D) wavelet decomposition using a biorthogonal filter bank in a so-called lifting scheme itself using weighting constants defined in the initialization step;
an encoding step, provided for encoding the transform coefficients thus obtained, by means of an encoding method adapted to 3D decompositions.
BACKGROUND OF THE INVENTION
In video compression schemes, the reduction of temporal redundancy is mainly achieved by two types of approaches. In the first one, the so-called “hybrid” or predictive approach, a prediction of the current frame is computed based on the previously transmitted frames, and only the prediction error is intra-coded and transmitted. In the second one, the temporal redundancy is exploited by means of a temporal transform, the 3D (or 2D+t) approach, which is similar to spatial techniques for removing redundancies. According to this last approach, the sequence of frames is processed as a 3D volume, and the classical subband decomposition often used in image coding can thus be extended to 3D spatio-temporal data by using separable transforms (for example, wavelet or wavelet packets transforms implemented by means of filter banks). Obviously, there is, in the 3D structure, an anisotropy, which can however be taken into account by using different filter banks in the temporal and spatial directions (usually, Haar filters are used for temporal filtering since the added delay of using longer filters is undesirable; furthermore, they are two-tap filters and are the only perfect reconstruction orthogonal filters which do not present the boundaries effect).
The coding efficiency of this 3D coding scheme can be improved by performing motion estimation/compensation in the low temporal subbands, at each level of the temporal decomposition. The 3D subband decomposition is applied on the compensated group of frames (this group of frames must contain a power of two number of frames, usually 16), and, at the last temporal decomposition level, there are two frames in the lowest temporal subband. In each frame of the temporal subbands, a spatial decomposition is performed.
Subband coding the three-dimensional structure of data can be realized as an extension of the spatial subband coding techniques. One of the most effective wavelet-based scheme for image compression is based on the 2D SPIHT algorithm, described in a detailed manner in “A new, fast, and efficient image codec based on set partitioning in hierarchical trees (=SPIHT)”, by A. Said and W. A. Pearlman, IEEE Transactions on Circuits and Systems for Video Technology, vol.6, June 1996, pp.243-250, and recently extended to the 3D structures. The basic concepts used in the 3D coding technique are the following: spatio-temporal trees corresponding to the same location are formed in the wavelet domain, then the wavelet transform coefficients in these trees are partitioned into sets defined by the level of the highest significant bit in a bit-plane representation of their magnitudes, and, finally, the highest remaining bit planes are coded and the resulting bits are transmitted.
The original SPIHT algorithm is based on the hypothesis of an orthogonal decomposition, according to which the reconstruction error is equal to the quantization error measured as the sum of subband distorsions (that is why it is possible to distribute the bit budget based on the energy of each subband). It has also been shown that the best results in image and video coding are not achieved using orthogonal filters, but biorthogonal ones (this is due to the fact that the symmetry of biorthogonal filters yields wavelet coefficients at the same spatial location as their parents). However, as biorthogonal filters do not preserve the L
2
norm of the quantization error, the bit repartition deduced for an orthogonal transform would not lead to the minimum reconstruction error.
Moreover, biorthogonal filters are determined up to a multiplicative constant and therefore an infinity of filter banks may be designed when only the perfect reconstruction condition is imposed. If a lifting implementation of the filter bank is used, it is known that the polyphase matrix P(z) can always be decomposed into factors
P
(
z
)
=
∏
i
=
1
m
[
1
s
i
(
z
)
0
1
]
[
1
0
t
i
(
z
)
1
]
[
K
0
0
1
/
K
]
,
where t
i
and s
i
are Laurent polynomials and K is a real constant. The dual polyphase matrix, corresponding to the synthesis part, is given in this case by:
P
~
(
z
)
=
∏
i
=
1
m
[
1
0
-
s
i
(
z
-
1
)
1
]
[
1
-
t
i
(
z
-
1
)
0
1
]
[
1
/
K
0
0
K
]
.
The perfect reconstruction is insured for all K, since:
P
(
z
)
{tilde over (P)}
(
z
−1
)
t
=I
This decomposition is implemented through the dual schemes illustrated in
FIGS. 1 and 2
. There exists therefore an infinity of implementations, corresponding to different factorizations and different values of the constant K. From the coding point of view, these filter banks are not all equivalent. A usual criterion for choosing this multiplicative constant is to impose the determinant of the polyphase matrix to be equal to 1, but this choice may not be the best for coding performances (that is why most of the usual algorithms are based on biorthogonal transforms that are nearly orthogonal).
SUMMARY OF THE INVENTION
It is therefore an object of the invention to propose a technique for improving the applicability of highly non-orthogonal wavelet transforms for video coding schemes, based on a 3D wavelet decomposition and an automatic bit allocation mechanism.
To this end, the invention relates to an encoding method such as defined in the introductory part of the description and which is moreover characterized in that it also comprises an off-line procedure that consists of off-line computations including the sub-steps of:
defining for these off-line computations the same type of input parameters, with the exception of the weighting constants;
carrying out a random GOF generation sub-step, the generated GOF containing a white, Gaussian noise of mean and standard deviation adapted to the representation of the original sequence;
implementing a 3D wavelet decomposition based on said lifting scheme and using the same filter bank without any weighting constants;
computing the standard deviations of the spatio-temporal sub-bands resulting from said 3D decomposition;
dividing said standard deviations by the standard deviation of the noise, optimal weighting constants being available at the output of said division sub-step and sent towards said filter bank in order to allow to weight the output of the spatio-temporal sub-bands.
Based on the energy repartition in subbands, the optimal weights for the biorthogonal filters in a 3D decomposition are thus determined. Some complicated methods based on relaxation algorithms are already used in the literature for choosing these constants in the framework of image coding, for instance the method described in “A multiscale relaxation algorithm for SNR maximization in non-orthogonal subband coding”, by P. Moulin, IEEE Transactions on Image Processing, vol.4, n°9, September 1995, pp.1269-1281. Techniques exploiting the human visual system in order to make the reconstruction error subjectively more acceptable also exist, such as the one described in “Signal-adapted multiresolution transform for image coding”, by P. Desarte and al, IEEE Transactions on Information Theory, vol.38, n°2, March 1992, pp.897-904. However, all these existing algorithms refer to image coding, while the
Diep Nhon
Koninklijke Philips Electronics , N.V.
LandOfFree
Video encoding method based on a wavelet decomposition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video encoding method based on a wavelet decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video encoding method based on a wavelet decomposition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3341686