LOSS AWARE RATE ALLOCATIONS IN H.263 CODED VIDEO TRANSMISSIONS
Journal of Circuits,Systems,and Computers
Vol.14,No.6(2005)1157–1171
c Worl
d Scienti?c Publishing Company
LOSS A W ARE RATE ALLOCATIONS IN H.263CODED
VIDEO TRANSMISSIONS
XIAO SU
Computer Engineering Department,San Jose State University,
One Washington Square,San Jose,CA95192,USA
BENJAMIN W.W AH
Coordinated Science Laboratory,
Department of Electrical and Computer Engineering,
University of Illinois at Urbana-Champaign,
Urbana,IL61801,USA
Revised6August2005
For packet video,information loss and bandwidth limitation are two factors that a?ect
video playback quality.Traditional rate allocation approaches have focused on optimizing
video quality under bandwidth constraint alone.However,in the best-e?ort Internet,
packets carrying video data are susceptible to losses,which need to be reconstructed at
the receiver side.In this paper,we propose loss aware rate allocations in both group-
of-block(GOB)level and macroblock level,given that certain packets are lost during
transmissions and reconstructed using simple interpolation methods at the receiver side.
Experimental results show that our proposed algorithms can produce videos of higher
quality when sent over lossy Internet.
Keywords:Error concealment;interpolation-based reconstruction;multi-description
coding(MDC);real-time multimedia in the Internet;rate allocation.
1.Introduction
Although video coding and transmission have attracted much attention from research community,it remains to be a challenging topic.Two di?cult issues involved are bandwidth constraints and information loss.In the literature,schemes can be found to address either of the two problems.
For information loss,there are sender-based,1–6receiver-based,7–11or sender–receiver-based schemes to recover from losses.12–14In particular,multiple-description coding(MDC)is an attractive approach for video streaming on the Internet because it greatly improves the error-resilience of coded bit streams.It divides video data into equally important streams such that the decoding quality using any subset is acceptable,and better quality is obtained by more descriptions. However,such schemes normally assume bandwidth is in?nitely available.
1157
1158X.Su&B.W.Wah
For bandwidth constraints,there are rate allocation and adaptation schemes to optimize video quality within a limited rate budget.15–22Again,such techniques work best for error free environment.
Di?erent from existing schemes that deal with rate allocations under lossless conditions,we study rate allocations for lossy transmissions in which parts of a bit stream may get lost and need to be reconstructed.To our best knowledge,no e?orts have been made to tackle the problem when sender employs certain robust coding algorithms,such as MDC.The proposed work?lls in this gap.In such a setting,the design of rate allocation schemes is closely related to those of multiple-description coding at a sender and the reconstruction algorithm employed at a receiver.
To facilitate discussions,let us?rst list the notations to be used in the paper in Table1.The general problem to be studied is as follows:given the available bandwidth R,how do we design an MDC in order to minimize reconstruction E r, subject to the rate constraint:r≤R?In the above statement,r is the actual rate (in bit per second)that the video signals are coded,and the reconstruction error E r refers to the distortion between the original video signals before applying MDC and the recovered signals after decoding and reconstruction.One wide-adopted metric to measure E r is Mean Squared Error(MSE)that calculates the average error between the original and the reconstructed pixel values.
Figure1illustrates the basic building blocks of the encoding and decoding descriptions in MDC.Among the steps,Transform T and Quantizer Q are two very important components that can greatly a?ect video playback quality.How-ever,in lossy situations,the original Transform T and Quantizer Q are not designed
Table1.Notations to be used in the paper.
Notation De?nition
E r Reconstruction error,i.e.,di?erence between the original and the
reconstructed videos
R Rate budget,i.e.,available video coding rate(in bit per second)
r Actual video coding rate(in bit per second)
Q i Quantization factor for the i th frame
q i Quantization factor for the i th GOB in a frame
s i Quantization factor for the i th coe?cient in a block
D(·)Rate-distortion function.D i(x i)represents distortion when video coding rate is x i X Vector of pixels in an original block
X Vector of pixels in a reconstructed block
Y Vector of original transformed coe?cients in a block
Y Vector of reconstructed transformed coe?cients in a block(after quantization)
d i Quantization error for th
e i th coe?cient in a block
σ2i Variance of the i th coe?cient in a block
c i The i th coe?cient in a block
R o The bit rate resulted from the original quantization method
R s The bit rate resulted from the scaled quantization method
P SNR o Peak-Signal-to-Noise-Ratio of the original quantization method
P SNR s Peak-Signal-to-Noise-Ratio of the scaled quantization method
Loss Aware Rate Allocations in H.263Coded Video Transmissions1159
Decoder
(a)Optimized Reconstruction-Based DCT
(ORB-DCT).
(b)H.263codec with modi?ed transform T and Quantizer Q.
Fig.1.Modi?ed H.263codec for reconstruction purpose.
for optimal reconstruction performance.In Ref.23,we have proposed Optimized Reconstruction-Based DCT(ORB-DCT)that modi?ed only Transform T,but not Quantizer Q,as illustrated in Fig.1(a).To add rate constraints,we need to modify both T and Q,as illustrated in Fig.1(b).However,such a formulation involving quantization module Q is a constrained integer optimization problem and is not solvable in a closed-form.Therefore,in this paper,we discuss heuristic approaches to address this problem.
Modifying Quantizer Q results in di?erent rate allocations in the frame,group-of-block(GOB),and macroblock levels.Figure2shows how rate control and allo-cations can be done in each layer.At the top frame level,rate allocations can be achieved by assigning distinct Q i’s to frames.At the GOB level,rate allocations can be done by assigning di?erent q i’s to blocks within the GOB.The assignment of q i’s overrides the default quantization choice set at the frame level.At the macroblock level,rate allocations can be done by applying di?erent s i’s to coe?cients within a macroblock.Again,the value of s i overrides the quantization choice set at the
GOB:
Block:
Coeff:
Fig.2.Rate allocation and control problems in H.263.
1160X.Su &B.W.Wah
GOB level.In this paper,we focused on two spatial domain schemes implemented in GOB-and macroblock-levels.
The paper is organized as follows.In Sec.2,we discuss reconstruction-based rate allocation among macroblocks in GOB-level.In Sec.3,we proposed loss aware quantization schemes for individual coe?cients within a macroblock.Section 4con-cludes the paper.
2.Reconstruction-Based Rate Allocation Among Blocks in a GOB
As a GOB consists of a sequence of macroblocks,and if the total rate allocated to this GOB is constrained by a budget R ,the question is how to choose quantization factors among macroblocks within the GOB in order to maximize reconstruction performance,subject to the rate constraint.To facilitate future discussions,we de?ne notations to be used in Table 1.
Let us start by reviewing the solution to this problem,without considering the fact that video signals may get lost and need to be reconstructed.The classical solution to this problem is based on the following theorem.
Theorem 1.18Given that the rate-distortion functions of macroblocks,D i (x i ),i =1,2,...,n ,are convex,the rate allocation vector (r 1,r 2,...,r n )is the solution to :min i D i (x i )
s.t.
i x i ≤R
if and only if the following condition satis?es: ?D 1?x 1 r 1= ?D 2?x 2 r 2=···= ?D n ?x n r n
.The proof can be found in Ref.18,and the discrete version of the theorem can be found in Ref.21.Essentially,the derivatives (?D i /?x i )r i ,i =1,2,...,n ,are the slopes of lines tangent to the rate-distortion (R-D)curves of the macroblocks coded at rates r i ,i =1,2,...,n .For this reason,the algorithm implementing the theorem is normally referred to as “constant slope optimization”.The intuitive idea behind the algorithm is very simple.At those points with constant slope,all the macroblocks operate at the same marginal return for an extra bit in the rate-distortion trade-o?.In other words,if we reduce one bit for macroblock i ,and spend it on another macroblock j (to maintain the same bit rate),then the reduction in distortion of macroblock j would be equal to the increase in distortion of macroblock i .For this reason,there is no allocation that is more e?cient for this rate budget.
This theorem establishes the necessary and su?cient conditions for optimal rate allocations among macroblocks.To apply the theorem,one needs to verify an important assumption,i.e.,the R-D curve for each individual block is convex.It has
Loss Aware Rate Allocations in H.263Coded Video Transmissions1161 been found that conventional single description coders(SDC)generate convex R-D curves,but no results have been reported about MDC coders with reconstructions. Next,we empirically establish the properties of the R-D curves for MDC coders with reconstruction.Please note that in MDC setting,the distortion is calculated between the decompressed and reconstructed signals and the original signals.
To this end,we?rst modi?ed the MDC-based H.263codec in such a way that the reconstruction quality after interpolation and the corresponding bit rate spent on each macroblock were saved for each description,for a given quantization choice. Then,we iterated through all possible quantization choices,i.e.,2,3,...,31,and obtained30rate-distortion pairs,that resulted in a rate-distortion(R-D)curve for each macroblock.
From the experiments,we have found that all the intra-coded macroblocks and a majority of the inter-coded macroblocks have convex R-D curves.Some inter-coded macroblocks have nonconvex R-D curves due to their complex dependencies on the R-D curves of their reference macroblocks.To save space,we only show the R-D curves of four randomly chosen intra-coded macroblocks and four inter-coded macroblocks from three test video sequences:missa,football,and akiyo.In Fig.3, the?rst row shows the R-D curves of intra-blocks from missa,and the second row shows the curves of inter-blocks from missa,followed by those of intra-and inter-blocks from football and akiyo.In these plots,rate is measured in bytes,and distortion is calculated in terms of mean squared error.Although for some video sequences,their curves are not convex in certain small local regions,convexity is still observed in most parts of all the R-D curves.We can observe the same trend in the R-D curves of other test sequences that are not included here due to space constraints.As a result,we conclude that the R-D relationship for reconstructed macroblocks in MDC is approximately convex;therefore,previous approaches that address optimal allocations among macroblocks can still be applied in MDC with reconstruction.18,21,24
3.Design of Quantization Matrices for MDC
H.263uniformly quantizes every coe?cient in a block by applying the same quan-tization factor q.Intuitively,this simple scheme is not optimal because it does not exploit the characteristics of individual coe?cients.The objective of our work is to improve its performance for MDC by assigning proper quantization factors to di?erent coe?cients.
As quantization is done in the coe?cient domain after DCT transform,we need to?rst relate errors introduced in the coe?cient domain to those observed in the pixel domain.Let X and X denote the original and the reconstructed blocks of pixels,and Y and Y be the corresponding original and reconstructed blocks of transformed coe?cients,we have the following relationship between the errors in
1162
X.Su &B.W.Wah 020*********
1201400295887116145174D i s t o r t i o n Rate Rate Distortion 204060801001201400295887
116145174D i s t o r t i o n
Rate Rate Distortion 2040
60801001201401600336699132165198D i s t o r t i o n Rate Rate Distortion 01020
30
40
5060
708090023466992115138
D i s t o r t i o n Rate Rate Distortion 33.053.13.153.23.253.3
3.353.4
0123456D i s t o r t i o n
Rate rate distortion 2.42.62.8
3
3.23.43.60123456789D i s t o r t i o n Rate
rate distortion 44.5
55.566.577.5036
91215D i s t o r t i o n Rate rate distortion 2.52.552.6
2.65
2.72.752.8
2.8501234D i s t o r t i o n Rate rate distortion
050100150
200250
30035004692138184230276D i s t o r t i o n Rate Rate Distortion 05010015020025030004182123
164205D i s t o r t i o n
Rate Rate Distortion 020
40
6080100120140160180200
03570105140175210D i s t o r t i o n Rate Rate Distortion 01020
30
405060
70020406080100120
D i s t o r t i o n Rate Rate Distortion
050100150200
25030003468102
136170204D i s t o r t i o n
Rate rate distortion 020
406080100120140160180
022446688110132D i s t o r t i o n Rate rate distortion 0204060
80100120140023466992115D i s t o r t i o n Rate rate distortion 0102030
40
506070
80
90100
021*********
D i s t o r t i o n Rate rate distortion 6080100
120140160180200
220240260
04080120
160200240D i s t o r t i o n Rate Rate Distortion 050
10015020025030035004080120160200D i s t o r t i o n
Rate Rate Distortion 0510
15
202530
3561218243036D i s t o r t i o n Rate Rate Distortion 0510152025303540455055091827364554
D i s t o r t i o n Rate Rate Distortion 05101520
2500.51 1.52
2.53
3.54D i s t o r t i o n Rate rate distortion 010
203040
50607000.51 1.52D i s t o r t i o n
Rate rate distortion 80100120
140160180200220240260
01234567D i s t o r t i o n Rate
rate distortion 0510
15
20253000.20.40.60.81D i s t o r t i o n Rate rate distortion Fig.3.Rate-distortion curves of four randomly chosen macroblocks from a I-frame of missa ,P-frame of missa ,I-frame of football ,P-frame of football ,I-frame of akiyo ,and P-frame of akiyo .
Loss Aware Rate Allocations in H.263Coded Video Transmissions1163 these two domains:
Y?Y 2= T X?T X 2(1)
=(X?X )T T T T(X?X )(2)
=(X?X )T(X?X )if and only if T T T=I(3)
= X?X 2.(4) Equations(2)and(3)hold if and only if T is an orthonormal matrix.It is easy to verify that DCT is an orthonormal transform;therefore,the energy of quantization errors in DCT transform coe?cients is equal to that of image pixels.This is a useful property because it implies that our e?orts to reduce quantization errors are equally re?ected in the pixel domain as well.
To?nd the quantization factor for each coe?cient in a block,we need to?rst ?nd the number of bits to be allocated to each coe?cient and then map this rate budget to quantization factor.For the?rst step,we can formulate the block-level rate allocation as a constrained optimization problem as follows25:
min E r=1
n
n
i=1
d2i,(5)
s.t.
n
i=1
R i=R.(6)
In the above formulation,we assume that i th coe?cient is quantized to R i bits,and the resulting quantization error is d i.There are n coe?cients in a block.In H.263, n is equal to64since each block is8by8.The optimal solution can be obtained in terms of the rate budget,R,the number of coe?cients within the macroblock,n, and coe?cient variances25:σi,i=1,2,...,n:
R i=R
n
+
1
2
log2
σ2i
n
σ21σ22 (2)
,i=1,2,...,n.(7)
The equation indicates that bit allocation should be done based on coe?cient variances.If all the coe?cients have equal variances,i.e.,σ21=σ22=···=σ2n,then, the best way is to assign R/n bits to each coe?cient.On the other hand,if the variance of a certain coe?cient i,σ2i,is greater(or smaller)than the geometrical average of the variances,then,the number of bits allocated to this coe?cient should be greater(or smaller)than R/n,the average number of bits for each coe?cient.
Although mathematically elegant,it is di?cult to directly apply this closed-form solution in practice.First,real-time estimations of the variance for each coe?cient results in an increase in both memory requirement and computational time.We need to set aside a frame bu?er to facilitate variance estimation,and this doubles the memory requirement in encoding.To understand its computational overhead,let us do a rough analysis on the number of computations needed to estimate coe?cient variance.Suppose there are m blocks in each frame,then,we need to estimate the
1164X.Su&B.W.Wah
variances for64coe?cient bands,c i,i=1,2,...,64among the m blocks as follows:
ˉc=1
m
m
i=1
c i,(8)
σ2i=1
m
m
i=1
c i?ˉc 2.(9)
To calculate the average coe?cient value,we need to perform m additions and one division.To calculate the coe?cient variance for a single coe?cient,σ2i,we need m additions,m subtractions,m multiplications and one division.Therefore, we need4m+2computations to estimate the variance for a single coe?cient,and 64(4m+2)to calculate all the variances.For a small CIF video sequence where the frame dimension is352×288,m is equal to1584=(352/8×288/8).This results in a total number of405632computations to be performed to estimate coe?cient variance!Compared to the original quantization method that needs just one division to quantize each coe?cient and101376computations to quantize all the coe?cients,this results in a four-fold increase in computational time.
Second,due to the nonstationarity of video frames,the variance of a coe?cient changes from frame to frame;hence,a quantization matrix needs to be sent for each frame,leading to additional bit overhead that may not justify the bit savings resulted from this approach.
Third,the largest obstacle to the application of this formula is that the rela-tionship between rate and quantization factors cannot be derived in advance due to the zigzag ordering and variable length coding employed.As both of them have large impact on the resulted bit rate but cannot be formulated in closed-form,it is di?cult to?nd the optimal quantization choices given the knowledge of this optimal bit allocation vector.
Equation(7),however,still provides guidelines for designing macroblock-level quantization schemes.Basically,it suggests that coe?cients should be quantized according to their variances in the way that if the variance of a certain coe?cient,σ2i,is greater(or smaller)than the geometrical average of the variances,then the number of bits allocated to this coe?cient should be greater(or smaller)than R/n, the average number of bits for each coe?cient.To develop practical MDC-based quantization schemes,our?rst step is to study how the MDC process changes the variances of individual coe?cients.For this purpose,we group coe?cients from a video frame into64bands by putting coe?cients with the same coordinate(i,j) in a transformed block,i,j=1,2,...,8,into the same band,and calculate the variances of coe?cients within each band.We do this separately for intra-coded and inter-coded frames because they have di?erent inputs:intra-coded frames code the original pixel values,whereas inter-coded frames code the residual signals computed from the current and its reference frames.
Table2shows the ratio of coe?cient variances of a horizontally-interleaved MDC system as compared to those of a SDC system,for three CIF format sequences
Loss Aware Rate Allocations in H.263Coded Video Transmissions 1165
Table 2.Ratio of coe?cient variances of a horizontally-interleaved MDC system compared to those of a SDC system,for intra-coded and inter-coded blocks from missa ,football ,boxing ,akiyo ,and coastguard ,respectively.
Intra-coded block Inter-coded block missa ￡￠ ?0.95 2.01 3.35 4.14 4.09 2.85 2.56 1.61 1.88 1.51 1.44 2.00 2.59 1.54 2.60 1.39￡￠ ?0.84 1.15 2.43 3.39 2.62 2.62 2.59 1.38 1.25 1.30 1.46 1.65 2.31 2.07 1.51 1.21￡￠ ?0.68 1.50 1.16 1.58 2.08 1.99 2.87 1.36 1.20 1.14 1.37 1.80 2.16 1.63 1.87 1.29￡￠ ?0.60 1.27 1.11 1.91 1.34 1.75 1.89 1.22￡￠ ?0.87 1.03 1.20 2.05 1.19 1.73 1.66 1.41￡￠ ?0.58 1.12 1.18 1.22 1.34 1.13 2.32 1.05￡￠ ?0.73 1.50 1.45 1.38 1.03 1.39 1.79 1.06￡￠ ?0.51 1.46 1.26 1.34 1.24 1.22 1.73 1.02￡￠ ?0.71 1.05 1.10 1.29￡￠ ?0.97￡￠ ?0.93 1.62 1.30￡￠ ?0.06￡￠ ?0.87 1.18￡￠ ?0.78 1.27￡￠ ?0.33￡￠ ?0.80 1.16￡￠ ?0.05￡￠ ?0.91￡￠ ?0.88 1.04 1.460.41￡￠ ?0.89 5.23￡￠ ?0.08￡￠ ?0.86 1.48 1.03 1.14￡￠ ?0.46 1.07 1.23￡￠ ?0.06￡￠ ?0.90 1.35 1.33 1.30￡￠ ?0.49 1.01 3.27football ￡￠ ?0.92 2.50 2.64 1.91 2.16 2.62 5.379.41 1.50 1.69 2.12 2.25 1.88 4.06 5.569.51￡￠ ?0.79 1.21 2.07 1.77 2.85 3.61 5.198.26 1.00 1.13 1.32 1.68 2.34 4.368.8113.85￡￠ ?0.66 1.02 1.45 2.25 2.93 3.94 4.637.67￡￠ ?0.83 1.02 1.06 1.64 2.65 4.209.0114.18￡￠ ?0.59￡￠ ?0.81 1.45 1.98 3.51 4.42 5.16 6.56￡￠ ?0.73￡￠ ?0.91 1.14 1.64 2.17 3.739.4314.76￡￠ ?0.66￡￠ ?0.91 1.76 1.91 3.10 5.09 6.157.47￡￠ ?0.85￡￠ ?0.88 1.35 1.36 2.85 6.128.6813.24￡￠ ?0.66￡￠ ?0.99 2.01 2.52 3.83 5.27 6.947.87￡￠ ?0.67 1.24 1.64 1.83 2.94 5.868.6414.54￡￠ ?0.65 1.11 1.49 2.48 4.15 6.367.1112.12￡￠ ?0.62 1.38 1.35 1.22 3.629.5210.9710.20￡￠ ?0.59￡￠ ?0.96 1.41 1.62 3.478.0911.6413.29￡￠ ?0.69￡￠ ?0.87 1.12 1.16 2.22 5.3510.1817.76boxing ￡￠ ?0.93 1.71 1.81 2.38 4.14 4.29 6.8712.06 1.03 2.40 2.46 2.00 1.95 4.84 5.8014.38￡￠ ?0.86 1.33 1.41 1.48 2.19 2.9312.5326.26￡￠ ?0.80 1.39 1.67 1.54 2.03 4.707.5514.99￡￠ ?0.85 1.41 1.14 1.23 2.11 3.439.6521.26￡￠ ?0.76￡￠ ?0.57 1.04 1.76 1.79 3.70 6.7919.15￡￠ ?0.75 1.26 1.21 1.29 1.81 4.327.5120.18 1.13￡￠ ?0.41￡￠ ?0.88 1.06 1.48 3.13 5.2423.38￡￠ ?0.77 1.37￡￠ ?0.88￡￠ ?0.81 2.16 3.5110.3122.09 1.05￡￠ ?0.98 1.28￡￠ ?0.86 1.49 2.79 6.3415.59￡￠ ?0.74 1.09 1.06 1.29 1.73 3.28 6.3812.34￡￠ ?0.71￡￠ ?0.93 1.02 1.14 1.37 2.36 5.4011.11￡￠ ?0.67￡￠ ?0.93￡￠ ?0.80 1.58 1.69 4.07 3.007.12￡￠ ?0.79￡￠ ?0.85 1.04 1.18 1.20 2.51 4.219.12￡￠ ?0.71￡￠ ?0.88￡￠ ?0.97￡￠ ?0.76￡￠ ?0.52 2.97 3.09 6.60￡￠ ?0.73￡￠ ?0.16￡￠ ?0.22￡￠ ?0.36￡￠ ?0.55 2.12 4.597.69akiyo ￡￠ ?0.94 1.62 2.15 1.65 2.28 3.65 6.5716.70￡￠ ?0.95 1.06￡￠ ?0.85 1.18 1.72 1.73 2.01 3.97￡￠ ?0.76 1.38￡￠ ?0.81￡￠ ?0.65 2.06 2.45 4.9120.84 1.14 1.08 1.13 1.37 1.69 1.70 1.81 2.66￡￠ ?0.69 1.12￡￠ ?0.98￡￠ ?0.75 1.03 1.87 4.4516.49￡￠ ?0.99 1.04 1.06 1.16 1.19 1.44 1.58 3.53￡￠ ?0.62￡￠ ?0.74 1.30 1.28 1.88 1.30 2.39 6.22 1.12 1.41￡￠ ?0.96￡￠ ?0.79 1.23 1.45 1.50 2.93￡￠ ?0.38￡￠ ?0.82￡￠ ?0.95 1.92 1.25 2.00 2.97 4.93 1.10 1.13 1.05￡￠ ?0.82 1.10 1.48 1.85 2.91￡￠ ?0.55￡￠ ?0.31￡￠ ?0.74 1.25 3.12 2.69 3.547.67 1.03￡￠ ?0.88￡￠ ?0.76￡￠ ?0.91 2.10 1.78 2.54 4.73￡￠ ?0.56￡￠ ?0.40￡￠ ?0.30 1.09 2.58 6.88 2.87 5.98￡￠ ?0.96￡￠ ?0.84 1.23￡￠ ?0.80 1.57 2.84 2.61 6.63￡￠ ?0.43￡￠ ?0.55￡￠ ?0.40 1.21￡￠ ?0.91 4.64￡￠ ?0.9319.92￡￠ ?0.88￡￠ ?0.55￡￠ ?0.49 1.08 1.63 5.81 3.3816.56￡￠ ?0.92 2.43 1.24 2.67 5.63 1.3115.6220.19￡￠ ?0.87 1.51 1.17 1.40 1.85 3.23 2.377.20￡￠ ?0.90 1.35 1.36 1.60 1.60 4.19 5.6414.89￡￠ ?0.88 1.07 1.12 1.42 1.88 2.72 6.1818.12coast-￡￠ ?0.79 1.37 1.71 1.52 2.52 2.94 5.8913.51￡￠ ?0.91 1.04 1.28 1.38 1.99 1.89 4.369.09guard ￡￠ ?0.86 1.07￡￠ ?0.97 1.04 1.64 3.079.4221.87￡￠ ?0.96 1.19￡￠ ?0.97 1.38 1.85 2.35 6.2713.06￡￠ ?0.81 1.03￡￠ ?0.92 2.06 1.39 2.99 4.2212.83￡￠ ?0.91￡￠ ?0.88 1.25 1.42 1.50 2.03 4.2419.45￡￠ ?0.70 1.10 1.29 1.14 1.16 2.76 6.4323.45￡￠ ?0.83 1.12 1.30￡￠ ?0.93 1.79 2.48 5.6619.75￡￠ ?0.73￡￠ ?0.86 1.18 1.29 2.12 2.31 6.2213.45￡￠ ?0.81￡￠ ?0.94 1.30 1.10 2.09 2.37 4.9917.76
￡￠ ?0.70 1.05￡￠ ?0.95 1.57 1.70 2.66 3.6019.49￡￠ ?0.81 1.26 1.08 1.67 1.59
2.45 5.5515.39(missa ,football ,and boxing )and two QCIF format sequences (akiyo and coastguard ).The coe?cients having smaller variances after MDC are circled in ovalboxes.
The results tell us that the variances in the upper right part of a coe?cient block tend to increase after MDC,and those in the lower left tend to decrease after MDC.
1166X.Su&B.W.Wah
This is not surprising because horizontal(resp.vertical)frequency components are likely to increase(resp.decrease)after horizontal partitioning,and the coe?cients in the upper right(resp.lower left)triangle are the ones that capture horizontal (resp.vertical)frequencies.As we know that coe?cients with large variances need to be quantized more?nely than those with smaller variances,our observation motivates the following quantization scheme for MDC:
Q i,j=
αQ i≥j
βQ i α≥1,β≤1, where Q i,j is the quantization factor to be used for the coe?cient of row i and column j,αandβare scaling parameters,and Q is the original quantization choice for this block.To choose suitableαandβ,we have evaluated the following com-bination of choices:α=1.0,1.05,...,1.2andβ=0.7,0.75,...,1,for each video sequence. The best results along with the parameters and the comparisons with the orig-inal quantization scheme can be found in Table3.Here,R s(resp.R o)represents the bit rate resulted from the scaled(resp.original)quantization,measured in bytes,and PSNR s(resp.PSNR o)denotes PSNR values for the scaled(resp.orig-inal)approach.From the results on?PSNR(=PSNR s?PSNR o)and?R/R (=(R s?R o)/R o),we can see that the modi?ed quantization scheme lead to better PSNRs and1–10%savings in bit rates for missa,football,boxing,akiyo,and river, and comparable R-D results for coastguard. In our approach,since the same scaling factors are used throughout a video sequence,there is no overhead in bit rate when compared to approaches that need to send frame-based quantization matrices to decoders.Furthermore,the estimations of variances and scaling factors,αandβ,do not add much extra complexity in real-time encoding because they can be done o?ine. A natural question arises as to how our proposed quantization algorithm increases computational time in real-time encoding and decoding,since the quan-tization and de-quantization processes become?oating point operations after scal-ing.To this end,we computed encoding time with the original quantization(enct o), encoding time with the proposed quantization(enct s),decoding time with the orig-inal quantization(dect o),and decoding time with the proposed quantization(dect s) and reported them in Table4.These numbers were calculated as the averages of100 experimental runs.In each run,we recorded time to encode and decode90frames of each sequence,respectively.The experiments were done on a Pentium-III PC with1.8GHz CPU and512M B memory. In Table4,we can see that the increase in computational time due to?oating number operations in quantization and dequantization is negligible,less than2%. This can be partly explained by the fact that both quantization and dequantiza-tion only take a very small fraction of time in the encoding and decoding pro-cesses.In the literature,people have reported time pro?ling results of MPEG-2and H.263coding26,27:in encoding,around85%time is spent on motion estimation and Loss Aware Rate Allocations in H.263Coded Video Transmissions 1167 Table https://www.wendangku.net/doc/fb16991954.html,parisons of bit rates and PSNRs of scaled quantization and original quantization for missa ,football ,boxing ,akiyo ,coastguard and river ,respectively. Quant factor R o P SNR o R s P SNR s ?R/R o ?P SNR (a)missa :one description received (α=0.9,β=1.0)4 52014239.3050581439.37￡￠ ??2.75%￡￠ ?0.078 15599237.8714094337.93￡￠ ??9.65%￡￠ ?0.0612 8149436.747916236.89￡￠ ??4.01%￡￠ ?0.1516 5263835.965128536.01￡￠ ??1.27%￡￠ ?0.0520 3824435.223781435.26￡￠ ??1.09%￡￠ ?0.04(b)missa :two descriptions received (α=0.9,β=1.0)4 104143139.70100759439.83￡￠ ??3.25%￡￠ ?0.138 31273937.9428340538.04￡￠ ??9.38%￡￠ ?0.1012 16144536.7915829836.93￡￠ ??1.95%￡￠ ?0.1416 10489635.9410258936.00￡￠ ??2.20%￡￠ ?0.0620 7570735.217519035.22￡￠ ??0.68%￡￠ ?0.01(c)football :one description received (α=0.95,β=1.05)4 137041034.021********.08￡￠ ??4.18%￡￠ ?0.068 68630931.8066448931.83￡￠ ??3.18%￡￠ ?0.0312 42906930.1441763830.15￡￠ ??2.66%￡￠ ?0.0116 29743528.9429265928.96￡￠ ??1.61%￡￠ ?0.0220 22229028.022*******.05￡￠ ??1.27%￡￠ ?0.03(d)football:two descriptions received (α=0.95,β=1.05)4 273918135.60262467235.73￡￠ ??4.18%￡￠ ?0.138 137183632.25132821632.32￡￠ ??3.18%￡￠ ?0.0712 85721330.2383497730.28￡￠ ??2.59%￡￠ ?0.0516 59446928.8858593828.93￡￠ ??1.44%￡￠ ?0.0520 44359227.9143829827.96￡￠ ??1.19%￡￠ ?0.05(e)boxing :one description received (α=0.95,β=1.05)4 643350532.96620290832.99￡￠ ??3.58%￡￠ ?0.038 337270731.37329983131.40￡￠ ??2.16%￡￠ ?0.0312 224801429.99221569130.05￡￠ ??1.44%￡￠ ?0.0616 166004028.86165355128.90￡￠ ??0.39%￡￠ ?0.0420 130204827.93130109827.96￡￠ ??0.07%￡￠ ?0.03(f)boxing :two description received (α=0.95,β=1.05)4 1287388735.161240881135.32￡￠ ??3.61%￡￠ ?0.168 674404832.30659990332.42￡￠ ??2.14%￡￠ ?0.1212 449324130.37442894330.47￡￠ ??1.43%￡￠ ?0.1016 331608628.98330363229.07￡￠ ??0.38%￡￠ ?0.09202600602 27.90259868127.97￡￠ ??0.07%￡￠ ?0.07 1168X.Su &B.W.Wah Table 3.(Continued ) Quant factor R o P SNR o R s P SNR s ?R/R o ?P SNR (g)akiyo :one description received (α=0.9,β=1.0)4 16676633.1814817333.24￡￠ ??11.2%￡￠ ?0.068 8490732.088165332.23￡￠ ??3.83%￡￠ ?0.1512 4961231.094769331.26￡￠ ??3.87%￡￠ ?0.1716 3953630.253572030.46￡￠ ??9.65%￡￠ ?0.2120 2913829.482707529.58￡￠ ??7.08%￡￠ ?0.10(h)akiyo :two descriptions received (α=0.9,β=1.0)4 33815036.0929785236.26￡￠ ??11.9%￡￠ ?0.178 16690933.7816472634.04￡￠ ??1.31%￡￠ ?0.2612 9981032.109473332.38￡￠ ??5.09%￡￠ ?0.2816 7801230.877086731.20￡￠ ??9.16%￡￠ ?0.3320 5850629.875289030.05￡￠ ??9.60%￡￠ ?0.18(i)coastguard :one description received (α=0.95,β=1.05)4 87036832.7483890932.71￡￠ ??3.61%?0.038 43439730.8542156930.89￡￠ ??2.95%￡￠ ?0.0412 26897729.3426955829.400.02%￡￠ ?0.0616 18271528.2218042328.17￡￠ ??1.25%?0.0520 13337927.3413124727.31￡￠ ??1.60%?0.03(j)coastguard :two descriptions received (α=0.95,β=1.05)4 173226934.70167050534.71￡￠ ??3.57%￡￠ ?0.018 86409831.6283787831.62￡￠ ??3.03%0.0012 53467729.6552374929.63￡￠ ??2.04%?0.0216 36312128.3535871928.31￡￠ ??1.21%?0.0420 26474827.3726141927.35￡￠ ??1.26%?0.02(k)river :one description received (α=0.95,β=1.0)4 137041034.021********.08￡￠ ??4.18%￡￠ ?0.068 68630931.8066448931.83￡￠ ??3.18%￡￠ ?0.0312 42906930.1441763830.15￡￠ ??2.66%￡￠ ?0.0116 29743528.9429265928.96￡￠ ??1.61%￡￠ ?0.0220 22229028.022*******.05￡￠ ??1.27%￡￠ ?0.03(l)river :two descriptions received (α=0.95,β=1.0)4 178137533.99177342434.10￡￠ ??0.04%￡￠ ?0.118 84546031.6383859631.75￡￠ ??0.08%￡￠ ?0.1212 50512430.1850013530.29￡￠ ??0.10%￡￠ ?0.1116 33981729.2133655029.27￡￠ ??0.10%￡￠ ?0.0620250665 28.5024895028.54￡￠ ??0.07%￡￠ ?0.04 Loss Aware Rate Allocations in H.263Coded Video Transmissions1169 https://www.wendangku.net/doc/fb16991954.html,parison of computational time of the original and the proposed quantization algorithms.Time is measured in seconds. Sequence enct o(s)enct s(s)dect o(s)dect s(s) Missa(352×288)20.4420.810.290.30 Football(352×288)24.4224.740.470.48 Boxing(352×288)24.7025.100.510.51 Akiyo(176×144) 3.00 3.050.080.08 Coastguard(176×144) 5.26 5.370.120.12 River(176×144) 5.90 6.010.120.12 compensation,8%time on quantization,variable length coding and rate control, and7%on transform coding;in decoding,around20%is spent on transform coding, 40%on motion compensation,25%on variable length decoding,and around15% on dequantization. To further understand the results in Table4,we did an experiment to compare the time to calculate10000integer operations(e.g.,multiplications and divisions) and10000?oating point operations,respectively.We found that?oating point operations result in approximately10%increase in computational time than inte-ger ones.This implies that if the time spent on quantization dominates the encoding procedure and the time spent on dequantization dominates the decoding procedure, then we will see10%increase in encoding and https://www.wendangku.net/doc/fb16991954.html,bined with the obser-vation that quantization takes only8%time in encoding and dequantization takes only15%in decoding,it is easy to understand why the introduction of?oating point quantization and dequantization in the proposed algorithms does not incur much penalty in computational time. 4.Conclusions In this paper,we have studied reconstruction-based rate control schemes with the objective to minimize?nal reconstruction error when packet losses happen. In general,rate control can be formulated as integer programming problems. Since it is di?cult to derive signal-independent closed-form solutions to such prob-lems,we have developed heuristic approaches to do rate control in two levels.First, for rate control among blocks within a GOB,we have studied schemes based on the“constant slope theorem”,which basically states that the optimal rate alloca-tion vector can be found at points with constant slopes in rate-distortion curves. To apply this theorem,one needs to verify an important assumption,i.e.,the R-D relationship for each individual block is convex.It has been found that conventional SDC generates convex R-D curves,but no results have been reported about MDC coders with reconstructions.Our work has?lled this gap by verifying empirically the convexity of R-D curves for MDC coders with reconstructions.As a result,con-ventional approaches based on the“constant slope theorem”can still be used for MDC coders.Second,for rate control among coe?cients within a block,we have ?rst investigated the property of coe?cient variances for MDC coders.Then,based 1170X.Su&B.W.Wah on the observations about the change of variances,we have proposed a scaled quan-tization scheme that produce videos with higher PSNRs using smaller bandwith. References 1. A.Albanese,J.Bloemer and J.Edmonds,Priority encoding transmission,Proc.Foun- dations of Computer Sciences(1994),pp.604–612. 2.R.Aravind,M.R.Civanlar and A.R.Reibman,Packet loss resilience of MPEG-2 scalable video coding algorithms,IEEE Trans.Circuits Syst.Video Technol.6(1996) 426–435. 3.V.Parthasarathy,J.W.Modestino and K.S.Vastola,Design of a transport coding scheme for high quality video over ATM networks,IEEE Trans.Circuits Syst.Video Technol.7(1997)358–376. 4.S.D.Servetto,K.Ramchandran,V.A.Vaishampayan and K.Nahrstedt,Multi- ple description wavelet based image coding,IEEE Trans.Image Processing9(2000) 813–826. 5.V.A.Vaishampayan,Design of multiple description scalar quantizers,IEEE Trans. Infor.Theor.39(1993)821–834. 6.Y.Wang,M.T.Orchard and A.R.Reibman,Multiple description image coding for noisy channels by pairing transform coe?cients,Proc.IEEE First Workshop Multi-media Signal Processing(1997),pp.419–424. 7.S.S.Hemami and T.H.-Y.Meng,Transform coded image reconstruction exploiting interblock correlation,IEEE Trans.Image Processing4(1995)1023–1027. 8.S.S.Hemami and R.M.Gray,Subband coded image reconstruction for lossy packet networks,IEEE Trans.Image Processing6(1997)523–539. 9.W.Kwok and H.Sun,Multi-directional interpolation for spatial error concealment, IEEE Trans.Consumer Electron.39(1993)455–460. 10.J.Suh and Y.Ho,Error concealment based on directional interpolation,IEEE Trans. Consumer Electron.43(1997)295–302. 11.W.Zeng and B.Liu,Geometric-structure-based error concealment with novel appli- cations in block-based low-bit-rate coding,IEEE Trans.Circuits Syst.Video Technol. 9(1999)648–665. 12.M.Ghanbari,Postprocessing of late cells for packet video,IEEE Trans.Circuits Syst. Video Technol.6(1996)669–678. 13.S.H.Lee,P.J.Lee and R.Ansari,Cell loss detection and recovery in variable rate video Proc.3rd Int.Workshop on Packet Video(1990). 14.I.Rhee,Error control techniques for interactive low-bit rate video transmission over the Internet,Proc.of ACM SIGCOMM(1998). 15.W.Ding and B.Liu,Rate control of MPEG video coding and recording by rate- quantization modeling,IEEE Trans.Circuits Syst.Video Technol.6(1996)12–20. 16. C.-Y.Hsu,A.Ortega and M.Khansari,Rate control for robust video transmission over burst-error wireless channels,IEEE Trans.Circuits Syst.Video Technol.17(1999) 756–773. 17.L.-J.Lin and A.Ortega,Bit-rate control using piecewise approximated rate-distortion characteristics,IEEE Trans.Circuits Syst.Video Technol.8(1998)446–459. 18. A.Ortego and K.Ramchandran,Rate-distortion methods for image and video com- pression,IEEE Signal Processing Magazine15(1998)23–50. 19.J.Ribas-Corbera and S.Lei,Rate control in DCT video coding for low-delay com- munications,IEEE Trans.Circuits Syst.Video Technol.9(1999)172–185. Loss Aware Rate Allocations in H.263Coded Video Transmissions1171 20.J.I.Ronda,M.Eckert,F.Jaureguizar and N.Garcia,Rate control and bit allocation for MPEG-4,IEEE Trans.Circuits Syst.Video Technol.8(1999)1243–1258. 21.Y.Shoham and A.Gersho,E?cient bit allocation for an arbitrary set of quantizers, IEEE Trans.Acoustics,Speech,and Signal Processing36(1988)1445–1453. 22.H.Sun,W.Kwok,M.Chien and C.H.J.Ju,MPEG coding performance improvement by jointly optimizing coding mode decisions and rate control,IEEE Trans.Circuits Syst.Video Technol.7(1997)449–458. 23.X.Su and B.W.Wah,Streaming real-time video data with optimized reconstruction- based DCT and neural-network reconstructions,IEEE Trans.Multimedia3(2001) 123–131. 24.K.Ramchandran and M.Vetterli,Best wavelet packet bases in a rate-distortion sense, IEEE Trans.Image Processing2(1993)160–175. 25.N.Jayant and P.Noll,Digital Coding of Waveforms:Principles and Applications to Speech and Video(Englewood Cli?s,Prentice-Hall,1984). 26. A.Hallapuro,https://www.wendangku.net/doc/fb16991954.html,ppalainen and T.D.Hamalainen,Performance analysis of low bit rate h.26l video encoder,Proc.IEEE Int.Conf.Acoustics,Speech,and Signal Processing(2001). 27. E.Iwata and K.Ohikotun,Exploiting coarse-grain parallelism in the MPEG-2algo- rithm,Technical Report CSL-TR-98-771,Stanford University,September1998.