Motion Compensated Frequency Selective Extrapolation for Error Concealment in Video Coding

Due to modern video codecs and increased computational power, the transmission and processing of video signals in wireless environments or IP-based access to videos became more and more usual in the past years. Unfortunately, in these cases the risk of data lost in transmission or erroneously received is omnipresent. To cope with this risk, modern video codecs such as H.264/AVC use two strategies. According to [1], the first one is error resilience by protecting the coded video against transmission errors and by minimizing the potential damage produced by incorrectly received bits. In the case that an error occurs, the second strategy has to take place, the concealment of block losses. Although the concealment is not part of the actual video standard, error concealment is widely used in many decoders in order to display a pleasant video and to reduce error propagation. A good overview over this area can be found in [2].

For concealing a lost block, most existent techniques use either spatial or temporal information for extrapolating the signal into the area of the lost block. The spatial methods only use information from the neighborhood of the lost block in the actual frame to extrapolate the signal into the area of the lost block. Two algorithms out of this group are e. g. the Projections onto Convex Sets from [3] and the Sequential Error-Concealment from [4]. On the other hand, the temporal methods extrapolate the signal into the lost area only by means of information from previous or following already correctly received frames. In most cases, these methods try to estimate the motion in a sequence and replace the lost block with one from another frame, shifted according to the estimated motion. Two powerful temporal concealment algorithms are e. g. the Extended Boundary Matching Algorithm from [5] or the Decoder Motion-Vector Estimation from [6]. Unlike these two groups, spatio-temporal algorithms use spatial as well as temporal information for concealing the errors. One state of the art spatio-temporal concealment algorithm is the Three-Dimensional Frequency Selective Extrapolation (3D-FSE) introduced by [7]. This algorithm aims at generating a model of the signal for a data volume centered by the erroneous block. The 3D-FSE is able to implicitly compensate small motion inside the volume, leading to very good objective and subjective extrapolation results.

Now, we propose a new concealment technique, the Motion Compensated Frequency Selective Extrapolation (MC-FSE). It is based on the 3D-FSE but uses an explicit motion estimation and compensation prior to the model generation. By explicitly estimating the motion and aligning the extrapolation volume, significantly better extrapolation results can be obtained compared to 3D-FSE.

Fig. 1 shows three consecutive frames of a possible video sequence $v\left[x,y,t\right]$ depicted by the two spatial coordinates $x$ and $y$ and the temporal coordinate $t$. In the frame at time instance $t=\tau$ an isolated block loss occurs with the top left corner at $\left(x_{0},y_{0}\right)$. Although isolated block losses are considered for the illustration of the algorithm, the algorithm easily can be adapted to other loss scenarios as well. In order to conceal the lost block, surrounding pixels in the actual frames and pixels in one or more previous and following frames are used. The number of used previous frames is indicated by $N_{\mathrm{p}}$, of used following frames by $N_{\mathrm{f}}$. In the case that the considered sequence is not a static one, the areas in the previous or following frame that correspond to the block loss may have been moved. Based on the frame at $t=\tau$, the movement relative to the frame at $t=\tau+\kappa$ is described by the motion vector

whereas each motion vector includes the displacement in horizontal direction $x_{\mathrm{d}}^{\left(\kappa\right)}$ and in vertical direction $y_{\mathrm{d}}^{\left(\kappa\right)}$. For the actual concealment the motion has to be revoked in order to generate an aligned three-dimensional data set, the so called extrapolation volume $\mathcal{L}$. The volume $\mathcal{L}$ is depicted by the spatial coordinates $m$ and $n$ and the temporal coordinate $p$. All in all, it is of size $M\times N\times P$. Further, it contains the lost block subsumed in area $\mathcal{B}$ and all the pixels used to extrapolate the signal into this area. These pixels are subsumed in volume $\mathcal{A}$, called support volume.

The block diagram in Fig. 2 shows the different steps of the MC-FSE that will be carried out in detail in the subsequent subsections. Starting with the lost block, the motion of the sequence around this block is estimated. As this estimation may be inaccurate, the motion estimation’s reliability is checked. If the motion estimation is reliable, the extrapolation volume is aligned according to the estimated motion. Afterwards, the Three-Dimensional Frequency Selective Extrapolation [7] enhanced by the fast orthogonality deficiency compensation proposed in [8] is applied to the extrapolation volume. Finally, the area corresponding to the lost block is cut out of the generated model and is used for replacing the lost block.

In order to demonstrate the extrapolation quality of the MC-FSE, the concealment of block losses in the CIF sequences “City”, “Foreman”, and “Vimto” is evaluated. Therefore, for all regarded sequences, in the frames number $17,47,77,107,$ and $137$ blocks of size $16\times 16$ pixels are cut out according to the loss pattern showed on the left side of Fig. 5. Then, for the luminance component these blocks are extrapolated and the extrapolation results are compared to the original blocks in terms of $\mathrm{PSNR}$.

The basis functions used for the extrapolation are the functions of the three-dimensional discrete Fourier transform. According to [7], this set of basis functions is especially suited for concealment of errors in natural images, since flat as well as noise like areas and edges can be reconstructed well. Additionally, an efficient implementation operating in the Fourier domain is possible [8]. For the actual extrapolation, $N_{\mathrm{p}}=2$ previous and $N_{\mathrm{f}}=2$ following frames are used. The support area in the actual frame is a band of $16$ pixels width around the lost block. This results in an extrapolation volume with an overall size of $48\times 48\times 5$ pixels. The decision area $\mathcal{M}$ for motion estimation is of $4$ pixels width and the search range is $d_{\mathrm{max}}=16$ pixels in each direction at fullpel accuracy. As the efficient implementation operates in the Fourier domain, the extrapolation volume has to be transformed into this domain. Therefore, a FFT of size $64\times 64\times 16$ is used. As mentioned before, the weighting function is generated by an isotropic model. Regarding the variable $\hat{\rho}$ of the isotropic model, a value of $0.8$ has lead to good extrapolation results. For controlling the orthogonality deficiency compensation, the factor $\gamma$ is chosen to $0.6$ as this value is a good tradeoff between compensation quality and the number of iterations needed for achieving the maximum $\mathrm{PSNR}$. The two thresholds for evaluating the motion estimation quality are chosen to $T_{\mathrm{rel}}=3$ and $T_{\mathrm{abs}}=100$. Fortunately, these two thresholds as well as the values given before are not very critical and can be varied in a relatively wide range without affecting the extrapolation result very much.

In Fig. 4, for the mentioned sequences the obtainable $\mathrm{PSNR}$ is shown with respect to the number of iterations used for the model generation. For illustrating the gain of MC-FSE over 3D-FSE the graph also shows the $\mathrm{PSNR}$ for the 3D-FSE that performs the extrapolation on the non-aligned extrapolation volume. Except for the motion compensation, all other parameters are chosen in the same way for 3D-FSE as for MC-FSE. Thus, the orthogonality deficiency compensation from [8] is also applied to the 3D-FSE, although originally not used in [7]. Obviously, by applying an explicit motion compensation and alignment of the extrapolation volume prior to the Frequency Selective Extrapolation the extrapolation quality can be increased significantly. For the considered sequences a maximum increment in $\mathrm{PSNR}$ of up to $1.4\,\mathrm{dB}$ is possible. Furthermore, most of the maximum gain already is existent at low numbers of iterations. Although the difference in $\mathrm{PSNR}$ depends on the sequence, for all tested sequences the explicit motion compensation leads to better extrapolation results.

Additionally, the MC-FSE is compared to several existent concealment techniques. As, according to [9], in general temporal concealment algorithms are superior to spatial ones, the comparison is carried out to temporal methods only. The simplest temporal method for concealing a block loss is the Temporal Replacement (TR). Thereby, the lost block is replaced by the block from the previous frame that has the same position. A more sophisticated approach is the Extended Boundary Matching Algorithm (EBMA) from [5] that replaces the lost block with a block from the previous frame that minimizes the boundary error between the correctly received neighboring blocks and the candidate block. Another method for concealing lost blocks is the Decoder Motion-Vector Estimation (DMVE) from [6] that already served as basis for the motion estimation in Section 2.1. The search range for EBMA and DMVE is set to $d_{\mathrm{max}}=16$ pixels as well. In Table 1 the obtainable $\mathrm{PSNR}$ is listed for the mentioned reference algorithms, the 3D-FSE [7], and the proposed Motion Compensated Frequency Selective Extrapolation (MC-FSE). For 3D-FSE and MC-FSE the number of previous and following frames is chosen to $N_{\mathrm{p}}=2,N_{\mathrm{f}}=2$. In addition, for 3D-FSE and MC-FSE Table 2 shows the concealment quality when different numbers of previous and following frames are used for the model generation. Apparently, due to making use of the spatial information as well, the 3D-FSE and the MC-FSE outperform the pure temporal concealment techniques. But, as already shown in Fig. 4, the explicit motion compensation of the extrapolation volume leads to better extrapolation results for the proposed algorithm.

Besides the objective evaluation of the extrapolation quality in terms of $\mathrm{PSNR}$, the subjective visual extrapolation quality is important. Although the 3D-FSE is able to conceal the losses without almost any visible artifacts, in some rare cases, the original signal cannot be reconstructed sufficiently. As already indicated by the $\mathrm{PSNR}$, the MC-FSE is superior to the 3D-FSE and additionally is able to conceal these critic losses better. Fig. 5 is used to illustrate such a case. The middle image is concealed with 3D-FSE and shows some minor artifacts, e. g. at the top of the “t” or the bottom of the “m”. On the right side the same image is concealed with MC-FSE. With this new technique, the block losses can be concealed very good, and no artifacts are visible any more.

The proposed algorithm is an enhancement to the already existent Three-Dimensional Frequency Selective Extrapolation. By explicitly compensating the motion of a sequence prior to the actual extrapolation, the potential of this powerful algorithm can better be tapped. With that, a very high subjective as well as objective extrapolation quality can be achieved. Demonstrated for concealment of isolated block losses, the proposed Motion Compensated Frequency Selective Extrapolation leads to an almost perfect reconstruction of the signal in the lost areas. Nevertheless, further work will focus on performing the motion estimation with fractional-pel accuracy and on reducing the complexity of the algorithm by selecting several basis functions in an iteration step. In addition to that, an implementation into a state-of-the-art video decoder is planned in order to evaluate the performance of the proposed algorithm in combination with more complex loss patterns in a realistic scenario. Although the MC-FSE is introduced for concealment of block losses it can as well be used for other signal extrapolation tasks as e. g.  the prediction in video coding.