Spectrally Efficient Partitioning of MPEG Video Streams for Robust Transmission over Multiple Channels
Wen Xu, Sheila
Hemami
Abstract
Reliable transmission of video over wireless networks must address both the limited bandwidth and the possibility of loss. When bandwidth sufficient to transmit the video is unavailable on a single channel, the video can be partitioned over multiple channels with possibly unequal bandwidths and error characteristics at the expense of more complex channel coding (error correction). This paper addresses the problem of efficiently partitioning forward error protected, pre-encoded video data for transmission over multiple channels. The assumption of pre-encoding precludes adjustment of source rates to the channels, since it is assumed that channel characteristics are not known until immediately prior to the start of transmission. The proposed partitioning exploits the structure of MPEG video, and frames in each group-of-pictures are reordered based on their decoding dependence and assigned to the channels to maximize the decodable frame rate. To be spectrally efficient, the frames are unequally error protected based on both frame types and channel packet loss rates. This technique is also applicable to scalable coding techniques. Simulation results demonstrate that the approach is effective under a variety of channel conditions and for a broad range of source material.
The
Transmission Model
The partitioning problem and solution are illustrated using the MPEG compression standard [1], though they could easily be applied to other video coding algorithms in which encoded data has different importance in terms of decoding quality and consists of independent coded units.
Assume that there are N (N ³ 2) channels having various characteristics (bandwidth, latency, packet loss rate (PLR)) available for transmitting one video sequence. Forward error correction (FEC) across packets is applied to each coded frame in order to recover lost packets. Because the multiple channels have different PLRs, data transmitted over each channel requires a different protection level. Because the MPEG frames have priorities in terms of group-of-picture (GOP) decoding, unequal error protection (UEP) is applied at the frame-level. After FEC protection the channel reliabilities are assumed to be approximately the same for a given frame type, though they vary for different frame types. In a UEP encoding scheme higher redundancy (expressed as redundancy factors) is given to more important frames. Furthermore, the same frame would assume different sizes after FEC encoding if allocated to channels with different PLRs.
The FEC-encoded video data for each GOP is thereafter partitioned as a group. The transmission process is thus described in discrete time with step size of the duration of a GOP, denoted as T. Bandwidth, PLR and redundancy factors are taken to be a constant within a step time T though they can vary throughout the duration of the entire video sequence. Partitioning is performed when the sender buffer has one GOP (assume it has Q frames) to be transmitted and is completed within T seconds.
Problem
Formulation
In the frame-level video partitioning problem a GOP consisting of Q frames is to be transmitted over N channels with differing bandwidths, PLRs, and latencies. It is assumed that the total available bandwidth is insufficient to transmit the entire coded GOP, so frames have to be dropped by the sender; the partitioning is performed to maximize the decodable frame rate. In order to effectively use the bandwidths, there is no need to deliver a frame if any one of the frames required to decode it is not delivered; the transmitted frames must be decodable without the dropped frames. At playback the missing frames can be replaced by replaying the latest decoded one, or by using a more sophisticated frame reconstruction technique (e.g. [5]).
The frames in a GOP are therefore reordered based on their encoding dependencies. The reordering occurs prior to the partitioning process. In the reordered sequence the j-th (1<j £ Q) frame is decodable on the condition that all frames from 1 to j-1 are transmitted. Therefore, frames from the end of the reordered sequence can be removed without affecting the decodability of remaining frames. The problem is thus formulated to maximize the number of frames in the reordered sequence within the bandwidth-time product constraints. The proposed formulation is general and can be extended to work with other coding techniques.
The delay is defined as the time interval between the start of a partitioned GOP transmission and the moment when all delivered frames of the GOP arrive, which mainly consists of transmission delay and propagation delay. Using T in the formulation constraints without worrying about the influence of propagation delay is justified when the processing time associated with partitioning a GOP and performing the FEC encoding is negligible. If the variation in propagation delays is large, however, it results in an overestimated solution for these channels. More accurate but more complex constraints can be applied. Therefore, it is preferable that the propagation delays have small variations if possible.
Algorithms
Two algorithms are considered and each provides desirable performance under certain circumstances. A fast solution is to use greedy algorithm, which allocates frames beginning with the best channel and ending with the worst. However, it doesn't guarantee the optimal solution due to the discrete unit (frame) and variable frame sizes. An alternative is to use a Pruned-Tree-Search (PTS) algorithm. A tree structure is employed, in which tree depth corresponds to number of frames and branches represent channel assignment. Bandwidth constraints in the formulation are associated with each node. Impossible sub-trees (searching subspaces) are pruned by evaluating constraints starting from the root.
Selected
Results
§ Comparison of PTS-reorder
and Greedy Algorithm with/without Frame Reordering
|
Table 1-- Frame rate difference between PTS and greedy partitions with channel bandwidth varying over [70%, 150%] of video average bit rate. Positive numbers indicate that PTS-reorder achieves a higher average frame rate. B-frames are sorted in ascending order of frame sizes in frame reordering. Frame rates are averaged over 100 GOPs for each bandwidth; minimum/ maximum are then taken over the bandwidth range. |
|
Video Clips (bits/s) |
Max Average Difference (frames/GOP) |
Min Average Difference (frames/GOP) |
||
|
Without Reorder |
With Reorder |
Without Reorder |
With Reorder |
|
|
Star Wars (233k) |
0.51 |
0.38 |
-0.1 |
0.04 |
|
Soccer (678k) |
0.70 |
0.27 |
0.0 |
0.12 |
|
MTV (615k) |
0.58 |
0.32 |
-0.09 |
0.0 |
|
News (517k) |
0.70 |
0.21 |
0.0 |
0.0 |
The frame rate difference is small between the two candidate algorithms. There are GOPs where a simple greedy scheme achieves a slightly higher frame rate than the PTS-reorder scheme, as indicated by the negative numbers in Table 1. This occurs when the channel bandwidths are lower and P-frame sizes happen to be larger. In the reordering scheme, frames with larger sizes (I- or P-) are reordered to early positions. At lower channel bandwidths, the greedy algorithm may achieve a higher frame rate as shown by IBBP compared with IPP, for example. However, PTS-reorder provides an evenly distributed spacing of frames within a GOP due to the delivery of P-frames, especially at lower frame rate. An even spacing can reduce the effect of time aliasing when frame rate up-conversion is performed at the receiver.
§ Performance Effects of
Channel Parameter Mismatch
|
Table 2-- Differences between expected frame rate and actual frame rate at -5% bandwidth mismatch for various video traces. The total bandwidth is 130% of video average bit rate. Results are provided for 100 GOPs using PTS-reorder scheme. (-5% indicates that the actual bandwidth is lower than the assumed by -5%.) |
|
Video Clips (bits/s) |
Ave. Difference (frames/GOP) |
Max Difference (frames/GOP) |
Standard Deviation (frames/GOP) |
|
Star Wars (233k) |
3.67 |
12 |
3.96 |
|
Soccer (678k) |
2.21 |
12 |
2.97 |
|
MTV (615k) |
1.26 |
11 |
2.44 |
|
News (517k) |
3.28 |
11 |
4.05 |
§ Effects of Differing Video
Content
Figure 1 -- Average
frame rate (frames/GOP) over 100 GOPs using PTS-reorder algorithm vs.
total
channel bandwidths (normalized with respect to video bit
rate)
for various video traces. The three
channels have equal bandwidth.
Conclusions
A framework has been proposed to efficiently partition pre-encoded video sequences for transmission over multiple channels with various qualities. The available bandwidths of the channels are the primary constraints in the partitioning process. The maximum decodable frame rate is achieved after the partition. The formulation is independent of the FEC mechanisms and can adapt to varying channel conditions.
The PTS algorithm guarantees the optimality of the partition solution for a given frame order, and along with the proposed frame reordering scheme it achieves a better average performance than a simple greedy approach. However, its exponential running time discourages its use for increased number of channels or frames in a GOP.
In the situations with tight timing constraints the greedy algorithm is a fast approximation algorithm. The bandwidth distributions among multiple channels have little influence on the partitioning performance, but do affect the computational complexity. Parameter mismatch analysis demonstrates that if mismatch is common, modifications to the algorithm can be made at the expense of lower frame rate and bandwidth utilization.
The partitioning formulation demonstrated in this paper is basic, on which more complex video transmission schemes can be developed. It is invoked whenever the current available resource (bandwidth) drops below the current requirement (video data rate), despite the efforts of possibly limited adjustments of resource assignment (e.g. channel rate control). Exploiting the a priori knowledge associated with pre-encoded video sources allows multiple GOPs to be processed in advance of their transmission times when the channel parameters are relatively stable or can be pre-estimated using accurate channel models. This is expected to further improve the channel bandwidth utilization, and can facilitate multiple channel video streaming with dynamic partitioning.
[2] P.H. Fredette, “The past, present, and
future of inverse multiplexing,” IEEE
Comm. Magazine, vol. 32, no. 4, pp. 42-6, April 1994.
[3] Y. Wang and Q. Zhu, “Error control and
concealment for video communication: a review,” Proc. IEEE, vol. 86, no. 5, pp. 974-97, May 1998
[4] E. W. Biersack, “Performance evaluation
of forward error correction in an ATM environment,” IEEE JSAC, vol. 11, no. 4, pp. 631-640, May 1993
[6] U. Horn et al., “Robust
Internet video transmission based on scalable coding and unequal error
protection,” Signal Processing: Image
Comm., vol. 15, no. 1-2, pp. 77-94, Sept. 1999
[7] Q. Zhang et al. “Resource
allocation with adaptive QoS for multimedia transmission over W-CDMA channels,”
in Proc. WCNC, Chicago, IL, Sept. 2000, vol. 1, pp. 179-84
[8] A. R. Reibman and B. G.
Haskell, “Constraints on variable bit rate video for ATM networks,” IEEE Trans. CSVT, vol. 2, no.4, pp.
361-72, Dec. 1992
[9] O. Rose, “Statistical
properties of MPEG video traffic and their impact on traffic modeling in ATM
systems,” in Proc. Of the 20th Conf. On Local Computer Networks,
Minneapolis, MN, Oct 1995, pp. 397-406
[10] M. Gallant and F.
Kossentini, “Rate-distortion optimized layered coding with unequal error
protection for robust internet video,”
IEEE Trans. CSVT, vol. 11, no. 3, pp. 357-372, Mar. 2001