As wavelets inherently provide a hierarchical representation of the analyzed con- tent and also have proved very attractive for spatial and quality scalability in still image coding, an intense effort has been deployed since the late-1980s to extend these decompositions in the temporal direction. This can be done by considering the video sequence as a volume of pixels and applying the temporal transform on samples along the temporal dimension. Temporal subbands are then spatially transformed also using a wavelet transform.
5.4.1 Motion-Compensated Temporal Filtering (MCTF)
The idea of temporal extensions of subband decompositions appeared in the late 1980s, with the works of Karlsson and Vetterli [1] and Kronander [2]. In these works the classical temporal closed-loop prediction scheme was replaced by a temporal subband decomposition, which didn’t take into account any motion com- pensation. Later it was shown that motion prediction was also important in these schemes [3] in order to reduce the detail energy subbands, thus leading to much better compression performance and visual quality, and ideally the temporal trans- form should be applied along the motion trajectories.
The simplest temporal wavelet transform is the Haar transform, performing sums and differences of pairs of frames to obtain respectively approximation and detail subbands. It is illustrated in Figure 5.12 on a group of frames (GOF) of eight frames, which allows performing a maximum of three levels of dyadic de- composition. A review of various MCTF structures for scalable video coding can be found in [42].
Due to the two-tap low-pass and high-pass filters and downsampling by a factor of 2, no boundary problems appear when decomposing a GOF of size 2Linto a number of up toLresolution levels.
Moreover, if motion estimation and compensation is performed between pairs of successive frames, without overlapping, the number of operations and the num- ber of motion vector fields are the same as for coding the same number of frames in a predictive scheme (and equal to 2L−1). However, as pairs of pixels have to be processed in successive frames in order to obtain the coefficients of the ap- proximation and detail frames, the motion invertibility becomes a very important problem.
For example, in a block-based motion-compensated prediction, which is the most usual technique for temporal prediction, the same area in the reference frame
FIGURE 5.12: Temporal Haar wavelet decomposition of a GOF.
can be used to predict several areas in the current frame, while parts of the refer- ence frame are not used at all for prediction. This gives rise to multiple connected and unconnected pixels (see Figure 5.13) [3,4]. In order to avoid such problems, other motion models, such as meshes, can be employed [30].
Moreover, in order to take advantage of in-place calculations and guaranteed reversibility of the scheme even for nonlinear operations (such as the operations involving motion compensation), a lifting implementation of the wavelet filter bank was proposed [5,21]. This way, after splitting the input samples in odd and even indexed ones, theoretically any biorthogonal filter bank with finite impulse responses can be represented with a finite number of predict-update (see Fig- ure 5.14) steps, possibly followed by multiplication with a constant.
In the case of temporal decomposition of the video, motion estimation is first performed between input frames, and the motion vector fields (denoted byv in Figure 5.15) are used for motion-compensated operations in both the predict and the update steps.
An important remark is that the predict operator can use all the even indexed input frames (denoted byx2tt) to perform the motion-compensated prediction of the odd indexed frames (denoted by{x2t+1}), while the update operator can use
5.4:MOTION-COMPENSATEDWAVELETVIDEOCODECS137
FIGURE 5.13: Temporal MC Haar filtering: connected, unconnected, and multiple connected pixels.
FIGURE 5.14: Basic steps of a lifting scheme.
FIGURE 5.15: Spatiotemporal motion-compensated lifting scheme.
all the detail frames ({Htt}) thus computed to obtain the approximation subband frames ({Ltt}).The predict and update operators then also involve the motion vec- tors used to match corresponding positions. Therefore, in thet+2Dframework they actually become spatiotemporal operators:
Ht(n)=x2t+1(n)−P x2(t−k), v2t2(t+−1k)
k∈Tkp
!
, ∀n∈S, Lt(p)=x2t(p)+U Ht−k, v2t2(t−k)+1
k∈Tku
!
, ∀p∈S,
wherevij is the motion vector field used to predict the current frameifrom the reference framej, Tkp (respectivelyTku) is the support of the temporal predict (respectively update) operator, and the spatial position is denoted by n or p.
In the simplest case of the Haar multiresolution analysis, the previous relations become
Ht(n)=x2t+1(n)−x2t
n−v2t2t+1
, ∀n∈S, Lt(p)=x2t(p)+Ht
p+v2t2t+1
, ∀p∈S.
However, from the temporal prediction viewpoint, it is better to make use of longer filters. The biorthogonal 5/3 filter bank has been most studied. In this
case, both forward and backward motion vectors need to be used for a bidirec- tional prediction. The analysis equations have the form
Ht(n)=x2t+1(n)−1 2
"
x2t
n−v2t2t+1
+x2t+2
n−v2t2t++12#
, ∀n∈S, Lt(p)=x2t(p)+1
4
"
Ht−1
p+v2t2t+1 +Ht
p+v2t2t++21#
, ∀p∈S.
Due to the fact that a bidirectional prediction is used in this structure, the num- ber of motion vector fields is double compared with the Haar decomposition, and therefore the coding of this information may represent an important part of the bit stream at low bit rates. Efficient algorithms are needed to further exploit redun- dancies between motion vector fields at the same temporal decomposition level or at different levels [23].
To effectively deal with the problem of motion-compensated temporal wavelet filtering associated with fractional precision motion vectors, many-to-one map- ping for the covered areas and nonreferred pixels for the uncovered areas [31], proposes a new and general lifting structure (see Figure 5.16) that unifies all the
FIGURE 5.16: The Barbell lifting scheme.
previous works to solve this problem and enables any traditional motion compen- sation techniques in block-based motion prediction coding to be easily adopted in the MCTF framework. The core of this work is a so-called Barbell lifting scheme, in which instead of a single pixel value, a function of a set of pixel values is used as the input to the lifting step. The Barbell lifting scheme essentially moves any existing effective motion prediction schemes in traditional video coding to the MCTF frames.
A new update scheme, energy distributed update (EDU), is proposed in [32]
to avoid a second set of motion vectors or complex and inaccurate inversion of the motion information used in the traditional update step. The idea is to update where predict is made by distributing high-pass signals to the low-pass frame.
Meanwhile, it provides further coding efficiency gain.
5.4.2 Three-Dimensional (3D) Wavelet Coefficients Coding
After 3D (temporal and spatial) wavelet analysis, a video sequence will be de- composed into a certain number of 3D subbands. For example, in Figure 5.17, a three-level wavelet (motion compensated) decomposition is performed in the temporal direction, followed by a three-level 2D spatial dyadic decomposition within each of the resulting temporal bands.
The next step in 3D wavelet video coding is to encode the transformed 3D wavelet coefficients in each subband efficiently. Since the subband structure in 3D wavelet decomposition for video sequence is very similar to the subband structure
FIGURE 5.17: Separable 3D wavelet transform. Three-level dyadic temporal (motion compensated) wavelet decomposition, followed by three-level 2D spatial dyadic decomposition.
in 2D wavelet decomposition for image, it is natural to extend many existing 2D wavelet-based image coding techniques, such as SPIHT [33], EBCOT [34], and EZBC [35], to the 3D case. As a matter of fact, almost all the existing 3D wavelet coefficients coding schemes use one form of these 3D extensions, such as 3D SPIHT [38], 3D ESCOT [36,37], and 3D EZBC [38,39].
Generally speaking, after 3D (motion compensated) wavelet decomposition, there is not only spatial similarity inside each frame across the different scale, but also temporal similarity between two frames at the same temporal scale. Further- more, temporal linkages of coefficients between frames typically show more cor- relation along the motion trajectory. An efficient 3D wavelet coefficient coding scheme should exploit these properties as much as possible. Several algorithms for texture coding in 3D wavelet schemes have been developed.
5.4.2.1 3D SPIHT
3D SPIHT is an extension of the concept of SPIHT still image coding to 3D video coding. As we know, the SPIHT algorithm takes advantages of the nature of en- ergy clustering of subband/wavelet coefficients in frequency and space and ex- ploits the similarity between subbands. It utilizes three basic concepts: (1) search- ing for sets in spatial-orientation trees in a wavelet transform; (2) partitioning the wavelet transform coefficients in these trees into sets defined by the level of the highest significant bit in a bit plane representation of their magnitudes; and (3) coding and transmitting bits associated with the highest remaining bit planes first.
There is no constraint to dimensionality in the SPIHT algorithm itself, as pixels are sorted regardless of dimensionality. The 3D SPIHT scheme can be easily ex- tended from 2D SPIHT, with the following three similar characteristics: (1) par- tial ordering by magnitude of the 3D wavelet transformed video with a 3D set partitioning algorithm; (2) ordered bit plane transmission of refinement bits; and (3) exploitation of self-similarity across spatiotemporal orientation trees.
For the 3D wavelet coefficients, a new 3D spatiotemporal orientation tree and its parent–offspring relationships are defined. For pure dyadic wavelet decompo- sition with an alternate separable wavelet transform in each dimension, a straight- forward extension from the 2D case is to form a node in 3D SPIHT as a block with eight adjacent pixels, two in each dimension, hence forming a node of 2×2×2 pixels. The root nodes (at the highest level of the pyramid) have one pixel with no descendants and the other seven pointing to eight offspring in a 2×2×2 cube at corresponding locations at the same level. For nonroot and nonleaf nodes, a pixel has eight offspring in a 2×2×2 cube one level below in the pyramid. For nondyadic decomposition similar to the 2D wavelet packet decomposition case, the 2×2×2 offspring nodes are split into pixels in these smaller subbands at the corresponding orientation in the nodes at the original level. For the common
FIGURE 5.18: Parent–offspring relationship in a spatiotemporal de- composition.
t+2D type of wavelet decomposition the parent–offspring relationship is shown in Figure 5.18. With such defined 3D spatiotemporal trees, the coefficients can be compressed into a bit stream by feeding the 3D data structure to the 3D SPIHT coding kernel. The 3D SPIHT kernel will sort the data according to the magnitude along the spatiotemporal orientation trees (sorting pass) and refine the bit plane by adding necessary bits (refinement pass).
5.4.2.2 3D ESCOT
The 3D SPIHT coding scheme provides natural scalability in rate (quality). How- ever, it is difficult to provide temporal or spatial scalabilities due to the inherent spatiotemporal tree structure. Even with extra effort, it can only provide partial temporal or spatial scalabilities by modifying the decoder or encoder [35]. How- ever, 3D ESCOT [36,37] can provide full rate, temporal and spatial scalabilities by constraining the encoding of wavelet coefficients independently within each sub- band. Meanwhile, the R–D optimized bit stream truncation process after encoding guarantees a bit stream with the best video quality given a bit rate constraint.
The 3D ESCOT scheme is in principle very similar to EBCOT [34] in the JPEG- 2000 standard, which offers high compression efficiency and other functionalities
(e.g., error resilience and random access) for image coding. In extending the 2D EBCOT algorithm to 3D ESCOT, a different coding structure is used to form a new set of 3D contexts for arithmetic coding that makes the algorithm very suit- able for scalable video compression. Specifically, each of the subbands is coded independently in the extended coding structure. The advantage of doing so is that each subband can be decoded independently to achieve flexible spatial/temporal scalability. The user can mix an arbitrary number of spatiotemporal subbands in any order to obtain the desired spatial or temporal resolution.
Unlike the EBCOT encoder [34] in JPEG2000, the ESCOT encoder takes a subband as a whole entity. There are two reasons for this. (1) Normally a video frame has lower resolution than a still image. Not splitting a subband further into many small 3D blocks brings better coding efficiency of the context-based adap- tive arithmetic coder. (2) Taking a subband as a whole entity is also convenient for incorporating the possible motion model in the coding process, since within the same 3D subband, the motion vector may point from any coefficients on a temporal plane to any other coefficients on other temporal planes.
As in the 2D EBCOT case, the contexts for 3D ESCOT are also formed with immediate neighbors in the same subband. The difference is that the immediate neighbors are now in three directions instead of two: horizontal, vertical, and tem- poral (Figure 5.19). In addition, the temporal neighbors not only may be spatially collocated in different frames, but also may be neighbors pointed to by motion vectors across frames with a certain motion model [36,37].
The encoding of the 3D wavelet coefficients in the 3D ESCOT scheme is done bit plane by bit plane. For each bit plane, the coding procedure consists of three distinct passes: Significance Propagation, Magnitude Refinement, and Normal- ization, which are applied in turn. Each pass processes a “fractional bit plane.” In each pass, the scanning order is along the horizontal direction first, the vertical di- rection second, and finally the temporal direction. In the Significance Propagation pass, samples that are not yet significant but have a “preferred neighborhood” are
FIGURE 5.19: Immediate neighbors of a sample in 3D ESCOT coding.
processed. A sample has a “preferred neighborhood” if and only if the sample has at least a significant immediate diagonal neighbor for a HHH (high frequency in three directions) subband or a significant immediate horizontal, vertical, or tem- poral neighbor for the other types of subbands. In the Magnitude Refinement pass, the samples that have been significant in the previous bit planes are encoded. In the Normalization pass, those samples that have not yet been coded in the previous two passes are coded.
In the previous stage, each subband is coded separately up to a specific pre- cision and each forms an independent bit stream. The objective of optimal bit stream truncation is to construct a final bit stream that satisfies the bit rate con- straint and minimizes the overall distortion. As in the EBCOT algorithm [34], the end of each pass at each “fractional” bit plane is a candidate truncation point with a precalculated R–D value pair for that subband. A straightforward way to achieve R–D optimized truncation is to find the convex hull of the R–D pairs at the end of each fractional bit plane and truncate only at the candidate truncation points that are on the convex hull.
To achieve quality scalability, a multilayer bit stream may be formed, where each layer represents a quality level. Depending on the available bandwidth and the computational capability, the decoder can choose to decode up to the layer it can handle. The fractional bit plane coding ensures that the bit stream is finely embedded. Since each subband is independently coded, the bit stream of each subband is separable. The encoder can choose to construct a bit stream favoring spatial scalability or temporal scalability. Also, the decoder can easily extract only a few subbands and decode only these subbands. Therefore, the implementation of resolution scalability and temporal scalability is natural and easy.
5.4.2.3 3D EZBC
3D EZBC is an extension of the EZBC image coder [35] to allow coding of three- dimensional wavelet coefficients. The concept of EZBC is inspired by the success of two popular embedded image coding techniques: zero-tree/-block coding, such as SPIHT [33], and context modeling of the subband/wavelet coefficients, such as EBCOT [34]. As discussed, zero-tree/-block coding takes advantage of the natural energy clustering of subband/wavelet coefficients in frequency and in space and exploits the similarity between subbands. Moreover, instead of all pixels, only a small number of elements in the lists [33] need to be processed in individual bit plane coding passes. Thus, processing speed for this class of coders is very fast. However, in the context model based coders [34], individual samples of the wavelet coefficients are coded bit plane by bit plane using context-based arith- metic coding to effectively exploit the strong correlation of subband/wavelet coef- ficients within and across subbands. Nevertheless, unlike zero-tree/-block coders, these algorithms need to scan all subband/wavelet coefficients at least once to
FIGURE 5.20: Quad tree decomposition in 3D EZBC.
finish coding of a full bit plane, with an implied higher computation cost. The EZBC algorithm combines the advantages of these two coding techniques, that is, low computation complexity and effective exploitation of correlation of subband coefficients, using both ZeroBlocks of subband/wavelet coefficients and context modeling.
Similar to EZBC for image coding, 3D EZBC is based on quad tree represen- tation of the individual subbands and frames. The bottom quad tree level, or pixel level, consists of the magnitude of each subband coefficient. Each quad tree node of the next higher level is then set to the maximum value of its four corresponding nodes at the current level; see Figure 5.20. In the end, the top quad tree node corre- sponds to the maximum magnitude of all the coefficients from the same subband.
As in EZBC, 3D EZBC uses this quad tree-based zero-block coding approach for hierarchical set-partition of subband coefficients to exploit the strong statistical dependency in the quad tree representation of the decomposed subbands. Further- more, to code the significance of the quad tree nodes, context-based arithmetic coding is used. The context includes eight first-order neighboring nodes of the same quad tree level and the node of the parent subband at the next lower quad tree level. Experiments have shown that including a node in the parent subband in the interband context model is very helpful in predicting the current node, espe- cially at higher levels of a quad tree.
Like SPIHT and other hierarchical bit plane coders, lists are used for tracking the set-partitioning information. However, the lists in 3D-EZBC are separately maintained for nodes from different subbands and quad tree levels. Therefore, separate context models are allowed to be built up for the nodes from different subbands and quad tree levels. In this way, statistical characteristics of quad tree nodes from different orientations, subsampling factors, and amplitude distribu- tions are not mixed up. This ensures a resolution scalable bit stream while main- taining the desirable low complexity feature of this class of coders.
5.4.3 Variants and Extensions: UMCTF, 3-bands
The concept of “unconstrained MCTF” (UMCTF) [10,43] allows very useful ex- tensions of the MCTF. By selecting the temporal filter coefficients appropriately,
multiple reference frames and bidirectional prediction can be introduced, such as in H.264, in the MC-wavelet framework. No update step is used, however, which makes this scheme comparable with an open-loop multiresolution predic- tive structure. We can adaptively change the number of reference frames, the rel- ative importance attached to each reference frame, the extent of bidirectional fil- tering, and so on. Therefore, with this filter choice, the efficient compensation strategies of conventional predictive coding can be obtained by UMCTF, while preserving the advantages of conventional MCTF.
Other extensions of the temporal transform are aimed at providing nondyadic scalability factors. This can be achieved byM-band filter banks, for which a gen- eral framework was proposed in [25]. In particular, a three-band filter bank in lifting form was proposed in [24] and is illustrated in Figure 5.21. For simplicity, Figure 5.21 shows only predict and update blocks; however, as in the dyadic case, they involve motion estimation/compensation.
Following the notation in Figure 5.21, the analysis equations, which lead to one approximation and two detail subbands, are
⎧⎪
⎪⎨
⎪⎪
⎩
Ht+(n)=x3t+1(n)−P+ {x3t}t∈N
,
Ht−(n)=x3t−1(n)−P− {x3t}t∈N
,
Lt(p)=x3t(p)+U+ Ht+
t∈N
+U− Ht−
t∈N
.
Note that in this scheme all the frames indexed by multiples of three are used by the two prediction operators. For example, by choosing framesx3t andx3t+3 for the prediction of framex3t+1and likewise choosing framesx3t−3andx3t for predicting framex3t−1, a structure similar to the classical IBBP . . . structure can be obtained.
FIGURE 5.21: Three-band lifting scheme.