- Mading Li
martinli0822@pku.edu.cn - Jiaying Liu
liujiaying@pku.edu.cn - Chong Ruan
ruanchong_ruby@163.com - LuLiu
liulu@staff.cntv.cn - Zongming Guo
guozongming@pku.edu.cn
Published on APSIPA, December 2014.
Introduction
With the rapid development of social network and multimedia technology, a huge number of digital image and video resources are being transmitted on the Internet everyday. However, practical communication channels are not error free. There are many loss mechanisms that may cause the data corruption, including network congestion, all kinds of noises, signal fades, etc. Moreover, since the transmitted signals are always highly compressed, the loss of one single bit is likely to bring about the loss of a whole block, which seriously affects the visual quality of the decoded images/videos. The error concealment method takes advantages of the correlation within images and tends to recover the loss parts of the corrupted images. A good error concealment method should be able to hide the fact that the image is corrupted and make the image comfortable and natural to be looked at.
In this paper, we propose a novel block-based multiscale error concealment method using low-rank completion aiming at isolated block loss situations. The input loss image is first down-sampled into lower levels. Then, for each block containing one pixel width loss, its similar blocks can be collected in all levels. After that, the similar blocks are clustered into a matrix, whose rank should be low. Finally, the matrix is processed by the low-rank completion and the missing pixels can be recovered. For each iteration, the boundaries of missing blocks are recovered. Progressively, the whole missing block can be recovered from boundaries to the center.
Problem Formulation
According to the availability of the neighboring blocks, block-loss situations can be classified into two types [1]: the isolated block loss and the consecutive block loss. In this paper, we mainly focus on the former situation.
The image block that contains one or more missing pixels is regarded as the reference block. For a $\sqrt{n} \times \sqrt{n}$ reference block $b_l$ at location $l$, a set of its similar blocks is defined as follows, \begin{equation} \label{indices} I_l = \{l\mid\|b_l-b_{l'}\|_2\leq T,l'\in\Omega_n(l)\}, \end{equation} where $I_l$ is the indices of the similar blocks. The threshold $T$ controls the similarity between the block $b_{l'}$ and $b_l$. $\Omega_n(l)$ defines the neighborhood of location $l$. When computing the similarity between two blocks, only the available pixels are included in order to prevent the similarity from being damaged by the missing pixels. Assuming that $m$ similar blocks are found, we can use them to define a matrix $M$, which is \begin{equation} \label{matrix} M = (\textbf{b}_{I_l(1)}, \textbf{b}_{I_l(2)}, ..., \textbf{b}_{I_l(k)}, ..., \textbf{b}_{I_l(m)}), k=1,...,m, \end{equation} where $\textbf{b}_{I_l(k)}$ is an $n \times 1$ vector containing all the columns of the image block $b_{I_l(k)}$. As described above, matrix $M$ should have a low-rank structure. Given the incomplete matrix $M \in\mathbb{R}^{n \times m}$, the low-rank completion problem can be formulated as follows, \begin{equation} \label{rank minimization} \begin{split} \min_X \quad& rank(X), \\ s.t. \quad& X_{ij} = M_{ij}, (i,j)\in\Omega_a, \end{split} \end{equation} where $X \in\mathbb{R}^{n \times m}$ and $\Omega_a$ is the set of locations corresponding to the available pixels.
Unfortunately, the above rank minimization problem is NP-hard and cannot be solved efficiently so far. Recently, the nuclear norm is utilized to solve the rank minimization problem since it is proved to be the tightest convex lower bound of the rank function of matrices. Thus, the rank minimization problem (3) can be solved by approximating rank function using the nuclear norm: \begin{equation} \label{nuclear norm} \begin{split} \min_X \quad& \|X\|_*, \\ s.t. \quad& X_{ij} = M_{ij}, (i,j)\in\Omega_a, \end{split} \end{equation} where $\|X\|_* = \sum_{i=1}^{min(m,n)}\sigma_i(X)$ is the nuclear norm and $\sigma_i(X)$ is the $i$th largest singular value of $X$. In this paper, the truncated nuclear norm [3] is applied because of its efficiency.
Fig. 1 The proposed image pyramid. The red block represents the reference block. The blue blocks in dash lines represent the searching neighborhood. The yellow blocks in dash lines represent the similar blocks. Level 0 is the original scale of the image.
The Multiscale Error Concealment Method
The Image Pyramid
In practice, we find that the toughest issues of similar blocks is that they are not that similar. In fact, the top-ranking similar blocks are indeed reliable while the bottom-ranking blocks are not. As illustrated in Fig. 2(c), the most unlike block in the similar block set found in the original level may be significantly different from the reference block. To address this problem, we need a wider searching neighborhood for the reference block, while not introducing extra prior knowledge. Thus, we come up with the image pyramid.
Fig. 2 (a) The original block; (b) The reference block; (c) The most unlike block in the similar block set found in the original level; (d) The most unlike block in the similar block set collected from all the levels.
As in Fig. 1, the input corrupted image is down-sampled to several levels. The nearest neighbor interpolation is adopted for down-sampling, since other interpolation methods may pollute the available pixels with missing pixels. For simplicity, the corrupted image in each level (except for the Level 0) is recovered based on its own information. The searching neighborhood of the reference block remains the same in each level, which introduces more information at the lower levels. The image pyramid helps to find more similar blocks. As shown in Fig. 2(d), the most unlike block in the similar block set collected from all the levels is much more similar to the reference block.
Unlike the DCT pyramid, the multiscale information is utilized more efficiently in the proposed image pyramid. The reference block is not bounded to a single block in the lower level. On the contrary, the similar blocks can be found in every level. There can be several similar blocks in each level. If none of the image blocks in a image level match with the reference block, there will be no similar blocks in that level.
The Ringlike Iterative Process
The ringlike iterative process specific to the isolated block loss situation is presented in this section. Apparently, the center pixels of the missing block is harder to be recovered than the pixels on the boundaries. The reason is that the missing pixels on the boundaries of the missing blocks have much more available neighbors. Thus, the recovery should be more reliable if the pixels on the boundaries are recovered first.
The basic idea of the ringlike iterative process is to recover the boundaries of the missing block on each iteration. In that case, the recovered pixels can be regarded as available pixels on the next iteration. The progressive process can make the recovery of the center pixels more natural. Fig. 3 gives some examples of the reference blocks. All reference blocks contains only one pixel width loss. After processing all the reference blocks, the pixels on the boundaries of the missing block can be obtained by averaging the recovered part of all the reference blocks. As can be observed in Fig. 3(b), the recovered pixels are used as available pixels for the next iteration.
Fig. 3 Examples of reference blocks of the first iteration (blocks in green dash lines) and the second iteration (blocks in blue dash lines). The white dots represent the available pixels. The black dots represent the missing pixels. The gray dots are the recovered pixels after the first iteration, which are used as available pixels in the following iterations.
Since the boundaries of the missing block is obtained after all the reference blocks are processed, the processing order of the reference blocks does not affect the result. The averaging may alleviate some of the artifacts, but the recovered pixels are not utilized until the current iteration is finished. In order to utilize the recovered pixels at once, three kinds of processing schemes are proposed (Fig. 4):
- Raster scanning (Fig. 4(a)): This scheme processes the input image by a raster scanning order. There is only one pixel missing in the reference block. The missing pixel in every reference block has the same location. The missing pixel recovered by last reference block is used as an available pixel in the next reference block. This sequential scheme is somewhat similar to that of [1]. Yet the proposed scheme uses an image block perform the raster scanning and preserves the correlation between the missing pixel and the available pixels. However, this scheme also need a linear merge strategy to alleviate the error propagated by the sequential recovery.
- Bilateral-direction (Fig. 4(b)): The bilateral-direction scheme intends to solve the error propagation problem by performing the scanning from both directions. The scheme simultaneously processes the upper (lower) boundary of the missing block from left to right and from right to left. The left (right) boundary is processed simultaneously from top to down and from down to top. Such measurement can properly deal with the situation that the missing block sits on the boundary of two different areas.
- Double-block (Fig. 4(c)): For every missing pixel, two reference blocks are used for recovery in this scheme. The two reference blocks contains different neighborhood for the missing pixels on different directions. The comprehensive information avoids the negative influence of the one-sided neighborhood and helps to recover the missing pixel more precisely. Compared with the bilateral-direction scheme, the double-block scheme can handle more complicated situations.
Fig. 4 Three kinds of processing schemes. The white dots represent the available pixels. The black dots represent the missing pixels.
Although these schemes may produce relatively precise result, they have a major drawback - the pixel they recovered are not natural. This is because these schemes recover pixels one by one and do not consider the correlation between missing pixels. The proposed averaging scheme, by contrast, produces less artifacts and more natural results. Thus, the averaging scheme is applied in our experiments.
Experimental results
The recovery results of the proposed block-based multiscale error concealment method (BMEC) are evaluated by concealing missing blocks in natural images. The proposed method is implemented on MATLAB 7.10 platform. The isolated blocks of size $16 \times 16$ pixels are cut out of the test images House, Lena, Barbara and Pepper. The size of the reference block is set to be $16 \times 16$. In our experiment, the image pyramid has 11 levels, including the original level. The image size of the bottom level is half of the original image. The proposed method is compared with the Novel Sequential Error Concealment method (NSEC) proposed by Li and Orchard [1], the Frequency Selective Extrapolation (FSE) proposed by Seiler and Kaup [2] and the Low-Rank Tensor Completion (LRTC) proposed by Liu et al. [4].
The quality of the recovered images are compared via two aspects: the objective quality and the subjective visual quality. The objective quality is evaluated by the Peak Signal-to-Noise Ratio (PSNR) and the structural similarity (SSIM) index. Since the recovered image and the original image are different only in the missing blocks, PSNR is computed only in these areas. As mentioned before, error concealment methods aim at recovering natural and comfortable images. In this respect, SSIM is a better objective evaluation criterion. Compared to PSNR, SSIM index is more consistent relative to visual perception. The PSNR and SSIM results of the proposed method and other methods are shown in Table I.
Table I PSNR and SSIM results of different methods. The largest values are marked in bold.
As shown in Table I, the PSNR results of the proposed BMEC method is much better than NSEC and LRTC, and comparable to FSE. In respect to SSIM, the proposed BMEC presents the best results, which means that the visual quality is rather good. Such consequence can be easily observed in the comparison of the subjective quality. As illustrated in Fig. 5, there are distinct boundaries on the recovered blocks produced by NSEC and LRTC. FSE presents rather impressive recovery, yet there are still some ghosting in the results. The proposed method presents the most natural recovery results without generating any boundaries and ghosting artifacts.
References
[1] X. Li and M.T. Orchard, "Novel Sequential Error-Eoncealment Techniques Using Orientation Adaptive Interpolation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 10, pp. 857-864, October 2002.
[2] J. Seiler and A. Kaup, "Fast Orthogonality Deficiency Compensation for Improved Frequency Selective Image Extrapolation," Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 781-784, April 2008.
[3] Y. Hu, D. Zhang, J. Ye, X. Li, and X. He, "Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 9, pp. 2117-2130, September 2013.
[4] J. Liu, P. Musialski, P. Wonka, and J. Ye, "Tensor Completion for Estimating Missing Values in Visual Data," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 1, pp. 208-220, January 2013.