Quality-fluctuation-constrained rate allocation for MCTF-based video

Quality-fluctuation-constrained rate allocation for MCTF-based videocodingYihua Chen*a, Jizheng Xu b, Feng Wu b, Hongkai Xiong aa Dept. of Electrical Engineering, Shanghai Jiaotong Univ., Shanghai 200030, China;b Microsoft Research Asia, 49 Zhichun Rd., Beijing 100080, ChinaABSTRACTThis paper presents a new rate allocation algorithm for MCTF-based video coding with the aim to control quality fluctuation. Distortion analysis is conducted for MCTF using a simplified signal model. Based on the analysis, the aim to control quality fluctuation is posed as a quadratic programming problem and its solution forms the basis for our proposed algorithm. After discussions on some extensions of the proposed rate allocation method, we verify it on MPEG SVC reference software and the experimental results demonstrate that the proposed rate allocation scheme can reduce quality fluctuation significantly.Keywords: Motion-compensated temporal filtering, constant quality, rate allocation, scalable video coding1.INTRODUCTIONMotion-compensated temporal filtering (MCTF) has proved to be one of the key technologies for highly efficient scalable video coding. Lifting-based MCTF applies discrete wavelet transform along motion trajectories using lifting scheme.1 Due to the inherent flexibility of lifting scheme, lifting-based MCTF can ensure perfect reconstruction even for complex motion models, provided there are no quantization errors. By considering the different weight of each temporal subband resulting from nonorthogonal wavelet transform, the popular rate allocation approach using Lagrange multiplier for traditional hybrid video coding can be easily extended to MCTF-based video coding in order to minimize the total distortion given a fixed rate budget. Since the optimization objective is the total distortion, such rate allocation scheme will cause quality fluctuation. This phenomenon is observed in our investigation and has also been reported in related literature.2, 3 For some sequences, a PSNR difference of 3 dB or even more can be observed between two successive frames. The reason for this quality fluctuation lies inherently in the nonorthogonal wavelet transform and such phenomenon becomes visually objectionable at low bit-rates. Therefore, a rate allocation algorithm to control quality fluctuation, or equally, distortion variation, is highly desirable. The solution offered by A. Munteanu et al.2 for unconstrained MCTF (UMCTF) only applies to lifting without update step, while for lifting with update step, which is more often the case, their solution can no longer be used. Lin Luo et al.3 presented a rate control method to smooth distortion in the temporal direction, but their approach lacks strict theoretical support.In this paper, a new rate allocation scheme is proposed to control quality fluctuation by choosing the appropriate quantizer for each temporal subband in a group of pictures (GOP). First, we analyze the relationship between the distortion in reconstructed frames and that in temporal subbands introduced by lossy source coding. Based on the analysis, we explain the quality fluctuation phenomenon when rate allocation scheme to minimize overall distortion is used. Then the objective to reduce distortion variation is formulated as a quadratic programming problem and the proposed rate allocation scheme is given based on the solution. Some extensions of the proposed method are also discussed. Last, experimental results are shown to verify the effectiveness of our approach.2.DISTORTION ANALYSIS FOR MCTFHere we investigate two-band motion-compensated lifting and consider decomposing a GOP containing N (= 2k, k∈Z+) frames into the same number of temporal subbands. However, the analysis can be easily extended to more general * This work was done when the author was with Microsoft Research Asia.Visual Communications and Image Processing 2006, edited by John G. Apostolopoulos, Amir Said,Proc. of SPIE-IS&T Electronic Imaging, SPIE Vol. 6077, 60771G, © 2005 SPIE-IS&T · 0277-786X/05/$15MCTF frameworks, e.g., three-band MCTF4 and UMCTF.5 Motion-compensated lifting is first performed on theoriginal frames and then recursively on the temporal low-pass frames obtained at the previous decomposition level.Thus,k stages of decomposition will yieldNtemporal subbands and there will be only one low-pass frame left. Atypical example for N= 4 is illustrated in Fig. 1 and the resulting four temporal subbands are marked gray. In theprediction step, which is identical to traditional motion-compensated prediction, the mode decision procedure willchoose between Haar wavelet (unidirectional prediction) and 5/3 wavelet (bidirectional prediction) for each macroblockor sub-macroblock. In the following update step, optimized update coefficients 6, 7 other than the standard ones for Haar and 5/3 wavelets can also be used.Figure 1. Two-band motion-compensated lifting structure for a GOP containing four framesIn order to simplify the analysis, we assume that one prediction mode, e.g. 5/3 wavelet, is dominant and the motion fieldestimated in the prediction step is nearly uniform. We also assume that the update coefficients are fixed for each high-pass frame. With these assumptions we employ a one-dimensional signal model instead of regarding each pixel as arandom variable. In this model, each frame or temporal subband is treated as a single random variable. We denote by X n ,n = 1, …, N the original frames and S n , n = 1, …, N the resulting temporal subbands. Here S N represents the only low-pass frame remaining after k stages of decomposition. The N original frames and N resulting subbands can be expressedby vector x = [X 1, …, X N ]T and vector s = [S 1, …, S N ]T , respectively. We assume that both prediction and update stepsinvolve exclusively linear operations; hence, the synthesis process for lifting structure is simply a linear transformationof the reconstructed temporal subbands s %, i.e.,,=xAs %% (1) where x% is the reconstructed frames. The matrix A is solely determined by the prediction mode and the update coefficients used. Take the structure illustrated in Fig. 1 as an example. Here T 1,11,22,12,1[,,,]H H H L =s and we have23123123414111111.1111()122201αααααααααααα−−−⎡⎤⎢⎥−−−⎢⎥=⎢⎥−−+−⎢⎥⎢⎥−−⎢⎥⎣⎦A (2) The relationship between the quantization errors of temporal subbands ∆S and the reconstruction errors of originalframes ∆X can thus be expressed as.X S =∆A ∆ (3)Then the total distortion of a GOP, measured by mean square error, isTT T T {}{()}()(),X X X X S S D E E tr tr tr ====∆∆∆∆AR A A AR (4) where T {}S S S E =R ∆∆ is the autocorrelation matrix of ∆S . Since each temporal subband is quantized independently, it is reasonable to assume that the quantization errors are uncorrelated, i.e. R S is a diagonal matrix. Then we have1,N i Si i D k D ==∑ (5) where22,i i k =a (6) and2{}.Si i D E S =∆ (7) Here in (6), a i represents the i -th column of A , and ║•║2 is the L 2-norm of a vector. In (7), ∆S i , which is the i -th elementof ∆S , denotes the quantization error of the i -th subband. Eq. (5) reveals that the total distortion is simply a linearcombination of the distortions of all the temporal subbands. Based on this relationship, the budget-constrained bitallocation problem 8 for MCTF can be solved with Lagrange multiplier. We repeat the definition of this problem here,i.e.,121min (,,,),..,N N i T i D R R R s t R R =≤∑L (8)where R i is the rate allocated to the i -th subband and R T is the rate budget for a GOP. By means of Lagrange multiplier,the objective function to minimize becomes11()().N N i Si i i T i i J k D R R R λ===+−∑∑ (9)When the above cost reaches its minimum, the slope of each subband, defined as(),1,,,Si i i i dD R i N dR λ=−=L (10) has the following relationship 1212111::::::.N Nk k k λλλ=L L (11) By substituting (11) for the constant slope criterion,8 the Lagrangian method to solve the budget-constrained bitallocation problem for traditional hybrid video coding can be easily extended here.If we further adopt the exponential rate-distortion model 9 by assuming for each subband that(),1,,,i i R Si i Si D R E e i N β−==L (12) the ratio of the distortion of the i -th subband to that of the N -th one, denoted by,1,,1,Si i SN D r i N D ==−L (13) can be derived from (11) and (12) as ,,1,, 1.N N i opt i ik r i N k ββ==−L (14)Thus the vector r = [r 1, …, r N –1]T , representing the ratio of subband distortions, takes the value r opt = [r 1, opt , …, r N–1, opt ]Twhen the minimal total distortion of reconstructed frames is achieved given a fixed bit budget.Now we examine the distortion of each frame inside a GOP. Since the quantization errors of temporal subbands areassumed to be uncorrelated, the distortion of reconstructed frames d X = [D X 1, …, D XN ]T is easily found from (3) to be alinear transformation of that of temporal subbands and thus we have,X S =d Bd (15)where d S = [D S 1, …., D SN ]T . Each element of B is the square of the element of A at the same position, i.e. 2ij ij b a =. Byutilizing (13), the distortion of each frame can be further express asT (),1,,,Xi i i SN D p D i N =+=h r L (16) where h i = [b i 1, …, b iN –1]T , p i = b iN . With optimal budget-constrained bit allocation, the ratio of the distortion of the i -thframe to that of the j -th one is T T.i opt i Xi Xj j opt jp D D p +=+h r h r (17) For a typical GOP size 16 with a constant value of βi = 2ln2,9 the maximal ratio between two successive frames reaches2.88; when converted to PSNR, the difference is 4.59 dB. Therefore, in the situation of nonorthogonal wavelettransform along motion trajectories, the optimal budget-constrained bit allocation will inherently cause qualityfluctuation. This characteristic makes it impossible in the framework of MCTF to achieve constant quality and minimaloverall distortion simultaneously as might be done in traditional video coding.103. DISTORTION-VARIATION-CONSTRAINED RATE ALLOCATION FOR MCTFSevere quality fluctuation can hardly be a pleasant user experience. Therefore, it is necessary to design a rate allocationscheme to reduce distortion variation, or sometimes, even to achieve constant quality. Here we consider achieving bitallocation through a given set of admissible quantizers. A well-known result concerning uniform scalar quantizer withstep size Q is that the distortion can be approximated by Q 2/12. This result, supported by high resolution quantizationtheory, implies that as long as the ratio between distortions of temporal subbands is set, it can be used to guide theselection of appropriate quantization steps for the corresponding subbands. Suppose the quantizer for the N -th subbandQ N is determined. Then given r i , i = 1, …, N –1, the quantization step for the i -the subband should be.i N Q = (18) The most straightforward way to derive vector r under constant quality constraint is to set all the elements of d X to 1,which leads to D X 1 = D X 2 = … = D XN , and solve (15). However, in most cases, the matrix B is ill-conditioned (alsoreported in 3), which means the solution is unstable. Thus, in order to reduce quality fluctuation, we choose the samplevariance of the distortions of reconstructed frames as the objective function to minimize, i.e.,211(),N Xi X i V D D N ==−∑ (19) where11.N X Xi i D D N ==∑ (20) By substituting (16) into (19), the variance becomes T T 212().2SN V q D =++r Hr g r (21) The expressions of H , g , and q are given in Appendix A. From (21) we know that given a fixed D SN , our goal to reducedistortion variation can be mapped to a quadratic programming problem. It is stated as follows,1T T 1min (),2..||||.N opt opt f s t θ−∈=+−≤−r R r r Hr g r r r r 1 (22) The inequality constraint in (22) is intended to confine the solution to a neighborhood of r opt and to ensure that for eachr i , i = 1, …, N –1, there is,,|||1|.i i opt i opt r r r θ−≤− (23) Here θ∈[0, 1] is a parameter to control the tradeoff between overall distortion and distortion variation. As θ increasesfrom 0 to 1, the solution r will deviate from r opt increasingly but the distortion variation will on the contrary decrease.When θ reaches 1, a heuristic restriction for r is still satisfied, i.e. r i ≥ 1, i = 1, …, N –1. Regarding the fact that for eitherHaar or 5/3 wavelet, the weight of the low-pass frame k N is always the largest, we ensure by this heuristic restriction thatthe quantization step chosen for the low-pass frame will never be larger than that used for any high-pass frame.Based on the solution of (22), we propose the following bit allocation algorithm for a GOP given a bit budget R T :Step 1: Choose an appropriate value from [0, 1] for θ according to the requirements.Step 2: Solve the quadratic programming problem (22) and obtain the solution r .Step 3: Choose an initial quantization step (0)NQand set the initial quantizers for the GOP as (0)(0)(0)(0),,,}N N N Q Q =L . Use Q (0) to quantize the N temporal subbands and get rate R (0).Step 4: Q (i ) ← Q (0) and R (i ) ← R (0). If R (0) ≤ R T , go to Step 5; otherwise, go to Step 7.Step 5: (1)()1i i N N Q Q +←+(here we assume the adjustment unit is 1) and get (1)(1)(1)(1),,,}i i i i N N N Q Q ++++=L . UseQ (i +1) to quantize the N temporal subbands and get rate R (i +1).Step 6: If R (i +1) > R T , go to Step 9; otherwise, Q (i ) ← Q (i +1), R (i ) ← R (i +1), and go to Step 5.Step 7: ()()1i i N N Q Q ←−(here we assume the adjustment unit is 1) and get ()()()(),,,}i i i i N N N Q Q =L . Use Q (i )to quantize the N temporal subbands and get R (i ).Step 8: If R (i ) ≤ R T , go to Step 9; otherwise, go to Step 7.Step 9:The quantizers chosen for the GOP are ()()()(),,}i i i i N N N Q Q =L and the rate achieved is R (i ). The quadratic programming problem can be solved by many existing mathematical tools. The efficiency of the proposedalgorithm relies heavily on the value of (0)NQ , and sophisticated R-D models can be used to estimate a good initial value. Fast search algorithms, e.g. binary search, can also be used to accelerate the proposed algorithm.4. FURTHER EXTENSIONSTo quantize the temporal subbands directly is not a common method in state-of-the-art video coding technologies. Moreoften, the temporal subbands will be quantized after spatial transform. For most spatial transforms, especially DCT andits integer approximation,11 the distortion of transform coefficients is proportional to that of original signals. Therefore,it is safe to use the quantizers obtained by the proposed algorithm to quantize the transform coefficients of temporalsubbands.Since the essence of the proposed algorithm is to determine the ratio of subband distortions by solving a quadraticprogramming problem, it can be extended to other coding methods as long as the ratio of subband distortions ispreserved. Bit-plane coding is a common technique to realize fine-granular scalability (FGS) in scalable video coding.Because adding each bit-plane is equal to reducing the quantization step to half of the original one, the consequentdistortion is expected to decrease to a quarter of the original distortion and thus the ratio remains unchanged. Now it isclear that after meeting the target rate budget for the base layer with the quantizers obtained by the proposed algorithm,by adding bit-planes upon the base layer one by one, our algorithm still works for the FGS enhancement layers.Sometimes the FGS enhancement layers need to be truncated to meet the target bit-rate. Here we point out that as longas the truncation follows the rule detailed in Appendix B, the distortion variation is still controlled to the specified level.5. EXPERIMENTAL RESULTSIn this section, we verify the proposed rate allocation algorithm on MPEG SVC reference software JSVM1.12 The update operator proposed in 7 are used due to its improved performance over the original one in JSVM1. We solve the quadratic programming problem with the optimization toolbox of MATLAB. Four CIF sequences (“Bus,” “Coastguard,” “Foreman,” and “Mobile”) at 30 fps are encoded with GOP size 16. For each sequence, a base layer is encoded at 256 kbps and the other three rate points (384, 512 and 1024 kbps) are reached by truncating the FGS enhancement layers. For simplicity, a constant quantization parameter is used throughout each sequence for low-pass frames. The coding efficiency and distortion variation for different values of θ are shown in Table 1. Distortion variation here is measured by the standard deviation of PSNR values. Table 1 also shows the performance of the unmodified JSVM1. Moreover, two fragments of per-frame PSNR curves are displayed in Fig. 2 and Fig. 3. Because the rate allocation scheme in JSVM1 has already taken (14) into account, the improvement in coding efficiency and quality fluctuation gained by our optimal budget-constrained bit allocation (θ = 0.0) is mainly due to the improved update operator 7 we use. However, the data and curves here clearly show that we can achieve tradeoff between coding efficiency and quality fluctuation with different values of θ, which is consistent with our analysis. Table 1. Luma PSNR mean (M [dB]) and standard deviation (S [dB]) for different values of θ 256 kbps 384 kbps 512 kbps 1024 kbpsM S M S M S M S JSVM1 27.94 0.61 29.38 0.77 30.88 0.95 33.95 1.26 θ = 0.0 28.18 0.43 29.65 0.53 31.13 0.63 34.17 0.83 θ = 0.7 27.91 0.38 29.35 0.44 30.91 0.50 33.93 0.57 “Bus” θ = 1.0 27.36 0.22 28.72 0.23 30.45 0.28 32.92 0.27 JSVM1 30.47 0.77 31.47 0.81 32.62 0.88 35.11 1.02θ = 0.0 30.51 0.59 31.72 0.62 33.12 0.70 35.50 0.74 θ = 0.7 30.24 0.55 31.51 0.55 32.89 0.58 35.10 0.54“Coastguard” θ = 1.0 30.13 0.36 31.03 0.36 32.03 0.34 34.59 0.33JSVM1 34.44 0.65 36.06 0.79 37.25 0.91 39.69 1.18θ =0.0 34.65 0.54 36.18 0.62 37.45 0.69 39.85 0.84 θ = 0.7 34.38 0.52 36.05 0.58 37.25 0.60 39.72 0.66“Foreman” θ = 1.0 34.15 0.39 35.51 0.40 37.10 0.42 38.87 0.39JSVM1 26.20 0.32 27.90 0.52 29.42 0.72 32.35 1.15θ =0.0 26.68 0.26 28.26 0.37 29.81 0.48 32.66 0.76 θ = 0.7 26.27 0.20 28.09 0.29 29.63 0.35 32.53 0.51“Mobile” θ = 1.0 25.94 0.18 27.57 0.22 29.20 0.24 31.46 0.23Figure 2. Comparison of the PSNR fluctuation for different values of θ on “Bus”Figure 3. Comparison of the PSNR fluctuation for different values of θ on “Foreman”6.CONCLUSIONIn this paper, we have studied the problem of controlling quality fluctuation for MCTF-based video coding through rate allocation. A simplified model of MCTF is introduced first as the basis for distortion analysis. Through distortionanalysis, we reveal the cause of quality fluctuation phenomenon in MCTF-based video coding. The major contribution of this paper is to formulate the problem of controlling distortion variation as a quadratic programming problem. And based on the solution, we propose a rate allocation algorithm to reduce quality fluctuation to a specified level and some extensions are also discussed. The experimental results provided in the previous section have demonstrated the effectiveness of our proposed algorithm. However, the one-dimensional signal model we use for MCTF is clearly an oversimplification; more accurate yet controllable model deserves further investigation.APPENDIX ABefore we give the expressions of H , g and q , we must introduce a few notations first. First, we defineT ,1,,,i i i i N ==H h h L (24) and.i i i p =g h (25) Then we define0,=H hh (26) where11.N i i N ==∑h h (27) Last we define0,p =g h (28) where11.N i i p p N ==∑ (29) Now we have011,N i i N ==−∑H H H (30) and011,N i i N ==−∑g g g (31) and 22111().2N i i q pp N ==−∑ (32)APPENDIX BWe denote by R i , j and D i , j the rate and distortion of the i -th temporal subband after including the j -th bit-plane upon the base layer. Particularly, R i , 0 and D i , 0 represent the rate and distortion of the base layer of the i -th subband. We further define,,,1i j i j i j R R R −∆=− (33)as the rate increase from one bit-plane to another. Suppose the target rate budget R T meets,1,11,N Ni j T i j i i R R R −==<<∑∑ (34)then after ensuring including all the bit-planes below the j -th one for each subband, we still have the remaining rate budget,11NT T i j i R R R −=∆=−∑ (35)to be allocated among the j -th bit-planes of all the temporal subbands. Suppose the quantizers for the base layer are obtained by the proposed algorithm, in order to ensure that we still control the distortion variation to the specified level, the rate allocated to the j -th FGS enhancement layer of the i -th subbband should be ,,1.i ji T k jk R R R R=∆∆=∆∆∑ (36) Finally, the total rate allocated to the i -th temporal subband is,1.i i j i R R R −=+∆ (37) It is known that the R-D curve for FGS coding can be well approximated by a piecewise linear function 10 and eachsegment represents the R-D information of a bit-plane. Based on this fact, we prove the effectiveness of (36) as follows.Figure 4. R-D curves of the i -th and N -th subbands for FGS codingFirst, we know from our discussions in Sec. 4 that we have ,1,,1,,1,,1,i j i j i N j N j D D r i N D D −−===−L (38)where r i is the solution of (22). Then we get from the R-D curves shown in Fig. 4 that,1,1,,(),1,,.i Si i j i j i j i j R D D D D i N R −−∆=−−=∆L (39) Since (36) ensures that,,,i N i j N j R R R R ∆∆=∆∆ (40) it is easy to find that ,1,, 1.Si i SND r i N D ==−L (41)As long as (41) holds, the distortion variation is still controlled to the specified level and this ends the proof.ACKNOWLEDGEMENTYihua Chen would like to thank Dr. Nikola Bozinovic for his valuable comments on an early version of this paper. He is also grateful to Mr. Ruiqin Xiong for many helpful discussions on scalable video coding.REFERENCES1.W. Sweldens, “The lifting scheme: a construction of second generation wavelets,” SIAM J. Math. Anal., vol. 29, no.2, pp. 512-546, 1997.2. A. Munteanu, et al., “Control of the distortion variation in video coding systems based on motion compensatedtemporal filtering,” Proc. IEEE Int. Conf. Image Process. (ICIP 2003), Barcelona, Sept. 2003.3.Lin Luo, Jizheng Xu, Shipeng Li, and Zhenquan Zhuang, “Rate control with smoothed temporal distortion for a 3Dembedded wavelet video coder,” Proc. IEEE Int. Conf. Info., Commu. & Sig. Process. (ICICS 2001), Singapore, Oct. 2001.4. C. Tillier and B. Pesquet-Popescu, “3D, 3-band, 3-tap temporal lifting for scalable video coding,” Proc. IEEE Int.Conf. Image Process. (ICIP 2003), Barcelona, Sept. 2003.5. D. S. Turage, et al., “Unconstrained motion compensated temporal filtering (UMCTF) for efficient and flexibleinterframe wavelet video coding,” Signal Processing: Image Communication, vol. 20, no. 1, pp. 1-19, Jan. 2005. 6. B. Girod and S. Han, “Optimum update for motion-compensated lifting,” IEEE Sig. Process. Lett., vol. 12, no. 2,pp. 150-153, Feb. 2005.7.Yihua Chen, Jizheng Xu, Feng Wu, and Hongkai Xiong, “An improved update operator for H.264 scalableextension,” Proc. IEEE Int. Workshop Multimedia Sig. Process. (MMSP 2005), Shanghai, China, Nov. 2005.8.Kai Wang and John W. Woods, “MPEG motion picture coding with long-term constraint on distortion variation,”Proc. SPIE Image Video Commu. Process., vol. 5685, pp. 284-296, March 2005.9.Hsueh-Ming Hang and Jiann-Jone Chen, “Source model for transform video coder and its application – part I:Fundamental theory,” IEEE Trans. Circuits Syst. Video Technol., vol. 7, no. 2, pp. 287-298, April 1997.10.Xi Min Zhang, A. Vetro, Yun Q. Shi, and Huifang Sun, “Constant quality constrained rate allocation for FGS-coded video,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 2, pp. 121-130, Feb. 2003.11.H. S. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, “Low-complexity transform and quantization inH.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13. no. 7, pp. 598-603, July 2003.12.“JSVM 1.0 Software,” ISO/IEC JTC1/SC29/WG11/N6900, Hong Kong, China, Jan. 2005.。