1.

Introduction

In the last few years, a variety of mobile multimedia devices have been developed and become popular. The end-users would like to capture various scenes and to send those through up-link channels. Usually, the capability of the mobile devices that the end-users have is constrained with low-power and low-CPU speed. In this circumstance, the conventional video codecs, such as MPEG-2, H.264/AVC, and MPEG-4, are not appropriate for the portable devices because those codecs need the high power to encode video sequences. Thus, demand for simple and low-power video encoder has been continuously increasing. Distributed video codec (DVC) is one of the solutions to encode video sequence with low complexity on the encoder side. The complexity of DVC encoder is significantly lower than those of the conventional encoders. DVC codec is regarded as an advanced codec that is appropriate for low power applications such as wireless surveillance, sensor network, and mobile camera phones.

DVC had been developed based on Slepian–Wolf¹ and the Wyner–Ziv² theorems which had proved that two signals can be decoded with prediction on the decoder side after those signals have been encoded without prediction between them on the encoder side. A theoretical method for lossless coding with side information (SI) was performed in Ref. 1. This method is referred to as Slepian–Wolf coding and is used with a channel-coding scheme. Slepian–Wolf coding was extended to a lossy compression by Wyner and Ziv.^2,3 The Wyner–Ziv codec consists of a quantization module, channel coding module, such as turbo code and low-density parity-check accumulator, punctured matrix, and SI generator. Most DVC codecs have been developed based on the models^4,5 which Stanford University and University of California Berkeley have provided. The model of UC Berkeley is named power-efficient robust, high-compression, syndrome-based multimedia (PRISM) coding.⁵ In Ref. 6, a project, which is called distributed coding for video services (DISCOVER), had been performed to construct the low-power video codec based on Slepian–Wolf and Wyner–Ziv theorems. In DISCOVER codec, key frames were encoded with the conventional intra-coding technique (intra-mode of H.264/AVC). On the other hand, the Wyner–Ziv frames were split to nonoverlapped blocks and then the blocks were transformed and quantized. The quantized coefficients were ordered bit plane by bit plane. Those coefficients were fed into a systematic channel encoder.

Recently, practical coding techniques using Slepian–Wolf and Wyner–Ziv codecs have been further studied.^7–11 Qing et al.⁷ proposed a model for the correlation of noise statistics, which was utilized to increase coding performance. Coding performances of various DVC codecs were analyzed in Ref. 8, where motion vectors (MVs) were estimated with subpixel resolution to generate SI. In Refs. 910.–11, enhanced SI was generated using various algorithms. Petrazzuoli et al.⁹ proposed a method to generate the SI, where more than two intra-decoded frames are used to estimate the position of the current MC block. A bilateral ME-based scheme to generate SI was described in Ref. 10. In Ref. 11, SI was generated using a side matching algorithm. Among the tools to increase the performance of the DVC codec, an efficient scheme to generate the SI frame is one of the most important techniques because it dominantly affects the quality of the picture in the DVC decoder and the encoding rate. In this paper, we propose a scheme to generate the SI frame using block boundary matching after analyzing the coding blocks in the initial SI frame.

The main functions of the SI generation module are motion estimation (ME) and motion compensation (MC). Thus, it is important to estimate MVs efficiently in DVC decoder. Because this topic is crucial also in a variety of video codecs,^12–17 for several decades, the related researches have been performed by various researchers to increase the accuracy of MVs,^12–14 and to speed up the ME process.^15–17 In this paper, we propose an efficient scheme to estimate MVs while the specific properties of MVs in DVC decoder are considering.

This paper is organized as follows. In Sec. 2, the model for DVC codec is formulated. The proposed scheme is explained in Sec. 3. Simulation results are presented in Sec. 4. Section 5 concludes this paper.

2.

Wyner–Ziv Codec Model

Figure 1 shows a video communication system that incorporates the Wyner–Ziv (WZ) codec. In this system, the odd frames $\{X_{2i-1},i=1,2,3,\dots \}$ are encoded using the intra-coding mode of the H.264/AVC standard,¹⁸ while the even frames $\{X_{2i},i=1,2,3,\dots \}$ are encoded using the WZ codec which consists of a Slepian–Wolf coding module and an outer quantizer-reconstruction pair. The data generated from encoding intra-frame $X_{2i-1}$ and WZ frame $X_{2i}$ are transmitted separately over independent channels. We assume that the channel for intra-frame is robust enough to prevent channel errors. $\{X_{2i-1}^{\prime },i=1,2,3,\dots \}$ and $\{X_{2i}^{\prime },i=1,2,3,\dots \}$ are the decoded frames on the decoder side.

Fig. 1

The video communication system using DVC codec.

When a WZ frame is encoded on the encoder side, the frame is split to nonoverlapped $8\times 8$ blocks and the blocks are transformed by discrete cosine transform (DCT). The transformed frame is denoted by $T_{2i}$. The DCT transformed frame is quantized by a scalar quantizer. The quantized frame is denoted by $Q_{2i}$, where a quantized datum is represented by a binary index. The binary indexes are encoded using a turbo coder to protect it from channel error. The turbo encoder changes each binary index to another binary vector which consists of information and redundant bits. Among the resulted bits, only the redundant bits are transmitted to the decoder, whereas the information bits are not sent. The set of binary vectors which turbo encoder generates is denoted by $P_{2i}$.

On the decoder side, while the odd frames $\{X_{2i-1}^{\prime },i=1,2,3,\dots \}$ are reconstructed by the H.264/AVC decoder with the intra-mode, the even frames $\{X_{2i}^{\prime },i=1,2,3,\dots \}$ are made by WZ decoder. In decoding WZ frames, when the quantized frame $Q_{2i}^{\prime }$ is generated by the turbo decoder both redundant and information bits are needed. But because the information bits have not been sent from the encoder, the turbo decoder should use the prediction values for the information bits. In Fig. 1, $QT(Y_{2i})$ is used instead of the information bits, where $Y_{2i}$ is SI frame. $Y_{2i}$ is constructed using ME and MC for the previous and next intra-frames, $X_{2i-1}^{\prime }$ and $X_{2i+1}^{\prime }$, that have been reconstructed by H.264/AVC decoder. $QT(Y_{2i})$ is resulted from quantizing after DCT transforming $Y_{2i}$. After the turbo decoder has generated $Q_{2i}^{\prime }$, the decoded WZ frame $X_{2i}^{\prime }$ is reconstructed by applying inverse DCT after inverse quantizing the $Q_{2i}^{\prime }$.

Because the $X_{2i}^{\prime }$ is made using $QT(Y_{2i})$, the quality of $X_{2i}^{\prime }$ depends on the quality of $Y_{2i}$. Therefore, various research^9–11 has been performed to increase the quality of the SI frame. Petrazzuoli et al.⁹ proposed a method to generate the SI where more than two intra-decoded frames are used to estimate the position of the current MC block. In the first step of Ref. 9, temporary MVs are estimated from $X_{2i+1}^{\prime }$ to $X_{2i-1}^{\prime }$. Then, the half-sized vectors of the temporary MVs are used as MVs for the corresponding blocks in the SI frame. This step provides a temporary SI frame. In the next step, new forward and backward MVs are estimated from $Y_{2i}$ to $X_{2i+1}^{\prime }$ and $X_{2i-1}^{\prime }$, respectively. Based on the forward and backward MVs, the SI frame is refined. In Ref. 10, a bilateral ME-based scheme to generate SI frame had been proposed, where side matching distortion was used in the ME process. In the initial step of Ref. 10, seed blocks were selected to increase the performance of ME process, which increases the quality of SI frame. Ko et al.¹¹ had proposed an algorithm to generate SI frame using a side matching algorithm, where blocks in SI frame were refined considering the mismatch error between the template of the current blocks and the corresponding pixels in the intra-frames $X_{2i+1}^{\prime }$ and $X_{2i-1}^{\prime }$.

In this paper, we make an initial SI frame by using ME and MC processes where these procedures are not constrained by a specific algorithm. One of the conventional ME and MC schemes can be used in this step. Because the qualities of some blocks in the initial SI frame may be very low, the blocks are refined according to the reliabilities of the blocks. The reliability of each block is calculated using the concentration ratio of MVs of the neighbor blocks.

3.

Proposed Algorithm

The proposed scheme consists of three steps to generate the SI frame. The initial SI frame is constructed by using forward, backward, and bidirectional ME and MC between $X_{2i-1}^{\prime }$ and $X_{2i+1}^{\prime }$ in the first step. Then, the blocks in SI frame are analyzed in the second step. Finally, in the third step, the SI frame is refined using the information generated in the second step.

3.1.

First Step: Generating the Initial SI

In the first step, a temporary SI frame is constructed by ME and MC for $X_{2i-1}^{\prime }$ and $X_{2i+1}^{\prime }$. After temporary backward and forward MVs are estimated from $X_{2i+1}^{\prime }$ to $X_{2i-1}^{\prime }$ and $X_{2i-1}^{\prime }$ to $X_{2i+1}^{\prime }$, respectively, the first temporary SI frame is constructed by MC based on the temporary MVs. Then, new forward and backward MVs are estimated from the first temporary SI frame to $X_{2i+1}^{\prime }$ and $X_{2i-1}^{\prime }$, respectively. By using the MC based on the new forward and backward MVs, the second temporary SI frame is constructed.

Figure 2 shows the relationship between the two key frames ($X_{2i-1}^{\prime }$, $X_{2i+1}^{\prime }$) and the second temporary SI frame ($Y_{2i}$). In $Y_{2i}$, a block $B_{s,t}$ whose size is $N\times N$ is constructed by ME and MC. $s$ and $t$ denote the horizontal and vertical indexes of the block in $Y_{2i}$. ${\mathrm{MV}}_{s,t}^0$ and ${\mathrm{MV}}_{s,t}^1$ are the MVs estimated for $X_{2i-1}^{\prime }$ and $X_{2i+1}^{\prime }$, respectively, to reconstruct $B_{s,t}$. The superscript 0 and 1 imply the backward and forward data, respectively. The horizontal and vertical components of ${\mathrm{MV}}_{s,t}^l$ are denoted by ${\mathrm{MV}}_{s,t}^l(x)$ and ${\mathrm{MV}}_{s,t}^l(y)$, respectively, where the superscript $l$ is 0 or 1. As can be seen from other researches,^9–11 it is difficult for the temporary SI frame to demonstrate high quality because the ME and MC modules generate some poor quality blocks.

Fig. 2

The initial side information (SI) frame is generated through forward, backward, and bidirectional ME and MC.

3.3.

Third Step: Refinement of Blocks

In this step, if $J_{s,t}$’s of some blocks are $<1$, then the blocks are classified as unreliable and remade. On the other hand, if $J_{s,t}$’s of some blocks are not $<1$, then the blocks are classified as reliable. After the unreliable blocks are sorted in a decreasing order of their $J_{s,t}$‘s, those are remade in the order by ME/MC procedure using block boundary matching (BBM). Figure 3 shows that an SI frame consists of reliable and unreliable blocks. Because the neighbor reliable blocks can be used to remake the unreliable block $B_{s,t}$, the MV of $B_{s,t}$ is re-estimated with templates $T_U(s,t)$, $T_B(s,t)$, $T_L(s,t)$, and $T_R(s,t)$ which are the upper, bottom, left, and right templates, respectively. Note that those templates consist of pixels in neighbor reliable blocks. If some neighbor blocks around the current unreliable block $B_{s,t}$ are unreliable, then the corresponding templates are not used. The MV of $B_{s,t}$ is estimated by minimizing the following cost function:

Eq. (12)

$$\text{COST}({\mathrm{MV}}_{s,t})=\frac{1}{Z}\sum _{l=0,1}\{w_U\times D[T_U(s,t),R_U^l({\mathrm{MV}}_{s,t}^l)]+w_B\times D[T_B(s,t),R_B^l({\mathrm{MV}}_{s,t}^l)]+w_L\times D[T_L(s,t),R_L^l({\mathrm{MV}}_{s,t}^l)]+w_R\times D[T_R(s,t),R_R^l({\mathrm{MV}}_{s,t}^l)]\},$$

where superscripts “$l=0$” and “$l=1$” imply that the data are related to $X_{2i-1}^{\prime }$ and $X_{2i+1}^{\prime }$, respectively. $R_U^l({\mathrm{MV}}_{s,t}^l)$, $R_B^l({\mathrm{MV}}_{s,t}^l)$, $R_L^l({\mathrm{MV}}_{s,t}^l)$, and $R_R^l({\mathrm{MV}}_{s,t}^l)$ are sets of pixels in reference frames whose pixels are overlapped with templates $T_U(s,t)$, $T_B(s,t)$, $T_L(s,t)$, and $T_R(s,t)$ displaced by ${\mathrm{MV}}_{s,t}^l$, respectively. $D[T_q(s,t),R_q^l({\mathrm{MV}}_{s,t}^l)]$ denotes the mean-squared difference between $T_q(s,t)$ and $R_q^l({\mathrm{MV}}_{s,t}^l)$, where $q$ is one of the $\{U,B,L,R\}$. If $T_q(s,t)$ is used because it is included in the reliable neighbor block, then $w_q$ is set to 1, otherwise, it is set to 0. If ME/MC is performed with forward or backward only, then the corresponding one in $\{l=0,1\}$ is used in Eq. (12). The variable $Z$ is the number of pixels used to calculate the cost function of Eq. (12).

Fig. 3

The SI frame is updated through ME and MC using block boundary matching.

4.

Simulation Results

In this section, the gain of the proposed scheme is represented by Bjøntegaard delta (BD) rate reduction.¹⁹ The intra-frames are encoded with the intra-mode of JM18.0. The number of frames to be encoded is 300. The GOP structure is “IWIWI…,” where “I” and “W” denote the intra- and WZ frames, respectively. When the intra- and WZ frames are encoded, the QPs are set to {27, 31, 35, 39} which are used in the calculation of BD rate reduction.¹⁹ Note that the quantization module of H.264/AVC is used for both intra- and WZ frames. In the decoders of DVC codecs, the MVs were estimated with $1/4$ pixel resolution.

In Figs. 4 and 5, and Tables 1 and 2, the DVC codec incorporating the proposed scheme (BBM) is compared with DVC codecs using the conventional algorithms,^9–11 where the size $N\times N$ of $B_{s,t}$ is set to $8\times 8$ or $16\times 16$. Figures 4 and 5 show that the rate-distortion (RD) curves of the DVC codecs using the proposed scheme are higher than those incorporating the conventional methods. It implies that the proposed scheme outperforms the conventional schemes in the viewpoint of RD. In Tables 1 and 2, the proposed algorithm has gains of $-5.9\%$, $-5.3\%$, $-8.1\%$ and $-6.3\%$, $-5.7\%$, $-8.1\%$ on average BD rates against the conventional schemes. Note that the negative number of BD rate implies that the proposed scheme reduces the total number of the bits generated from encoding the video sequence while the image quality resulted from the proposed scheme is equal to those of the conventional schemes. The gains of the case of $N\times N=16\times 16$ are larger than that of $N\times N=8\times 8$ because the template of $N\times N=16\times 16$ block contains the more useful information to construct the SI frame than that of $N\times N=8\times 8$ block.

Fig. 4

Comparison between rate-distortion (RD) curves of the conventional and the proposed algorithms, where the BBM is performed with $N\times N=8\times 8$. (a) Foreman, (b) mobile, (c) hall, (d) silent.

Fig. 5

Comparison between RD curves of the conventional and the proposed algorithms, where the BBM is performed with $N\times N=16\times 16$. (a) Foreman, (b) mobile, (c) hall, (d) silent.

Table 1

Bjøntegaard delta (BD) rate gains and the relative complexity of the proposed DVC codec. N×N=8×8.

Table 2

BD rate gains and the relative complexity of the proposed DVC codec. N×N=16×16.

To understand the tendency of gains according to the block size, we show the relationship between the BD rate gain and the block size $N\times N$ in Fig. 6, where the DVC codec incorporating BBM is compared with the DVC codec using the conventional algorithm.⁹ Although the performance depends on the test sequences, the overall gains show that the case of $N\times N=16\times 16$ provides the best performance among three cases of the block size. The boundary template of $N\times N=8\times 8$ is less useful to update the unreliable blocks than that of $N\times N=16\times 16$, because the number of pixels in the template of $N\times N=8\times 8$ is smaller than that of $N\times N=16\times 16$. On the other hand, because in the case of $N\times N=32\times 32$, the correlation between pixels in a block and templates of the block is lower than that of the case of $N\times N=16\times 16$, the case of $N\times N=16\times 16$ gives more gain than that of $N\times N=32\times 32$.

Fig. 6

Bjøntegaard delta rate gains of the DVC codec incorporating BBM according to the block sizes against the DVC codec using the conventional algorithm (Ref. 9).

In Tables 1 and 2, the complexity of the DVC codec using the proposed scheme is between 97% and 105% of those using the conventional schemes. Note that 100% implies the complexity of the proposed scheme is equal to that of the conventional scheme. The complexities represented in the tables show that the complexity of the proposed scheme is approximately equal to those of the conventional schemes.

Validity of the reconstructed SI has been checked in Table 3 where the averaged PSNRs of SI reconstructed in DVC decoder were measured. Even though it is not allowed in DVC scenario, it is helpful to check the accuracy of SI generation algorithms. As we can see from this table, the PSNRs of SI generated by the proposed BBM are higher than those resulting from the conventional algorithms. It implies that the proposed scheme outperforms the conventional algorithms in increasing the quality of the generated SI frame.

Table 3

Averaged PSNRs of the SI’s reconstructed in the DVC decoder. N×N=16×16.

To analyze the performances of the steps of the proposed algorithm, the percentage of the blocks regarded as unreliable in the proposed scheme is shown in Table 4, where the percentages of the unreliable blocks are $<3\%$. Although the portion is small, the gains resulted by updating the unreliable blocks are significant. In this table, we measure BD rate gains of the third step against the first step of the proposed scheme. This table shows that the third step of the proposed algorithm increase the coding efficiency significantly.

Table 4

Percentage of the unreliable blocks in the proposed scheme. BD rate gains of the third step against the first step in the proposed scheme. N×N=16×16.

The second and third steps of the proposed scheme described in Sec. 3 can be used to enhance the performance of the conventional algorithms,^9–11 because the steps increase the quality of the SI frame by updating those that have been made by the conventional algorithms. To demonstrate it, the performance comparisons between DVC codecs using the combined techniques (conventional schemes + second and third steps of BBM) and the conventional schemes are represented in Table 5, where $N\times N=16\times 16$. In the DVC codec using the combined techniques, instead of the first step of the proposed algorithm, one of the conventional schemes is used to make the temporary SI frame. The temporary SI frame is updated by the second and third steps of the proposed algorithm. The DVC codecs using the combined techniques are more efficient than codecs using the conventional schemes. As for the results related to Ref. 9 in Table 5, the gains of the combined method are insignificant. Because SI frame constructed by Petrazzuoli et al.⁹ includes a lot of unreliable blocks, the number of reliable neighbor blocks that the BBM scheme can utilize is small. Note that BBM is useful when a lot of reliable neighbor blocks are included in the temporary SI frame.

Table 5

BD rate gains and the relative complexity of the DVC codec using the combined techniques. N×N=16×16.

In DVC codec, the complexity of the channel decoder (turbo decoder) decreases as the quality of the SI frame increases, because the number of operations sending more parity bits which are requested by the decoder is reduced as the quality of the SI frame increases. Therefore, in Table 5, because the quality of SI frame generated from the combined techniques is higher than those resulting from the conventional schemes, the complexity of the DVC codec using the combined techniques may be smaller than the conventional codecs. This table shows that the proposed scheme (BBM) can be used to increase the performances of the conventional schemes.

5.

Conclusions

This paper proposes an efficient method to reconstruct the SI frame in a DVC decoder. In the proposed algorithm, the blocks in the SI frame are classified to reliable and unreliable blocks, and then the unreliable blocks are remade using a BBM scheme. Simulation results show that the proposed scheme outperforms the conventional methods. The proposed scheme can be combined with the conventional schemes to increase the coding performance further.