本篇論文藉由改變GOP（Group of Pictures）中不同畫面間的編碼相依性來重建出數種新型的GOP結構。在傳統GOP結構中，除了單獨壓縮的第一張畫面外，每張畫面（frame）與前一張均有編碼上的相依性，因此不論使用者要求存取一個GOP中的任何一張畫面，在此之前的所有畫面也必須被傳送並解碼。當觀眾進行快轉（Fast Forward Scan）或跳躍（Jump）等VCR動作時，雖然只有少數的畫面被顯示，卻仍需傳送整個GOP的畫面並解碼，且為了能讓每張被要求的畫面及時播放，傳送速度必須符合使用者所觀看的倍率。在視訊串流的環境下，如存在大量使用者同時向伺服器要求VCR動作，將造成伺服器及網路過量的負擔，而其中大部分被傳送的資訊卻是多餘的。在本篇論文中，我們重新架構整個GOP，將GOP中不同畫面間的編碼相依性重新組合，使其在進行VCR動作時，不需傳送多餘的畫面，因此使用者可以一般傳送速度來觀看各種不同倍率的播放，以達到平衡伺服器負擔及節省網路頻寬的功能。
此外，本文所提的結構亦支援錯誤回復（Error Resilience）功能，在普通播放速度的情形下，因網路狀況不佳所造成的封包遺失或損毀，我們可以在不需有任何回傳資訊（Feedback Information）的條件下，重建相似的移動（motion）及像素資訊，並防止因畫面間的相依性所造成的錯誤增值（Error Propagation）。

In this thesis, we present several novel GOP (Group of Pictures) structures by reorganizing the coding dependencies among frames in a GOP. In the conventional GOP structure, each frame except I-frame is predicted by the previous one. Once any of these frames is requested, we need to transmit not only the requested frame, but also all frames before the target frame. Therefore, when a client performs VCR operations such as Fast Forward Scan (FFS) or Jump, there may be only few frames for display, but all frames in a GOP have to be sent and decoded. Besides, the transmission rate of these frames needs corresponding to the playback rate so that every required frame can be shown on the screen in time. Consider the video streaming systems, if numerous users request for VCR operations at the same time, it may cause heavy server load. However, most of these transmitted data are redundant but inevitable. In our GOP structures, no redundant frame will be transmitted in most of cases when a VCR operation is performed. Thus even for the VCR operations with a high-speed factor, the server still sends data at normal transmission rate. The video server load and network bandwidth can significantly reduce as well.
In addition, the proposed structures also provide error resilient mechanism. Similar motion or pixel information can be reconstructed without feedback information if packet loss or packet damage occurs during transmission. And error propagation phenomenon caused by coding dependencies among frames will reduce as well.

Chapter 1. Introduction...1
Chapter 2. VCR Functionality and Video Error Resilience...3
2.1 VCR Functionality on Streaming Video...3
2.1.1 GOP-Skipping-Based Dynamic Transmission Scheme...5
2.1.2 Dual Bitstreams with Least-Cost Frame Selection...6
2.1.3 VCR Functionality in Staggered Broadcasting...7
2.1.4 The Split and Merge (SAM) Protocol...9
2.1.5 Single-Rate Multicast Double-Rate Unicast (SRMDRU) Scheme...11
2.2 Video Error Resilience...11
2.2.1 Interleaved Packetization...12
2.2.2 Independent Segment Prediction...12
2.2.3 Reference Picture Selection Based on Feedback Information (RPS)...13
Chapter 3. GOP Model of VCR Functionality...15
3.1 Playback Sequences...15
3.2 Optimal Coding Dependencies for an Allocated Playback Sequence...15
3.3 Feasibility Model of Optimality for VCR Functionality...16
3.4 Restriction of the Reference Distance...18
3.5 Proximity Approximation...19
Chapter 4. Restructuring GOP Algorithms with No Redundant Referring Information...21
4.1 A Simple Example...21
4.2 Restructuring Algorithms with Minimum Cost...22
4.2.1 Greedy Tree Structure...22
4.2.2 Double-Binary Tree Structure...25
Chapter 5. Redundant Referring Information on Conventional GOP Structure ...28
5.1 Restructuring Algorithm of Extended GOP...28
5.2 Transmit All Motion Information in Extended GOP...30
5.3 Transmit Only Conventional Motion Information in Extended GOP...32
Chapter 6. Experimental Results...33
Chapter 7. Conclusions and Future Works...39
References...41

[1]Te-Chou Su and Jia-Shung Wang, “On-demand Multicast Routing Scheme and Its Algorithms,” in International Symposium on Parallel and Distributed Processing, pp. 212-217, 1999.
[2]Zhi-Li Zhang; Yuewei Wang; Du, D.H.C. and Dongli Su, "Video Staging: A Proxy-Server-Based Approach to End-to-End Video Delivery over Wide-Area Networks," IEEE/ACM Transactions on Networking, Vol. 8, No. 4, pp. 429-442, Aug. 2000.
[3]The NTHU streaming platform, http://vod.cs.nthu.edu.tw.
[4]Wilson Wing-Fai Poon and Kwok-Tung Lo, “Design of Multicast Delivery for Providing VCR Functionality in Interactive Video-on-Demand Systems,” IEEE Transactions on Broadcasting, Vol. 45, No. 1, pp. 141-148, Mar. 1999.
[5]Wanjiun Liao and Victor O. K. Li, "Split-and Merge (SAM) Protocol for Interactive Video-on-Demand Systems," IEEE Multimedia, Vol. 4, No. 4, pp. 51-62, Oct.-Dec., 1997.
[6]Jung-Min Choi, Seung-Won Lee, and Ki-Dong Chung, “A Multicast Delivery Scheme for VCR Operations in A Large VOD System,” International Parallel and Distributed Symposium 2001, pp. 555 -561, 2001.
[7]Kwon, J.B. and Yeom, H.Y., “Providing VCR Functionality in Staggered Video Broadcasting,” IEEE Transactions on Consumer Electronics, Vol. 48, No. 1,pp. 41-48, Feb 2002.
[8]J. M. McManus, and K. W. Ross, “Video-on-Demand Over ATM: Constant-Rate Transmission and Transport,” IEEE Journal on Selected Areas in Communication, Vol. 14, No. 6, pp. 1087-1098, Aug. 1996.
[9]J. H. Lee, and S. S. Lee, “A GOP-Skipping-Based Dynamic Transmission Scheme for Supporting Fast Scan Functions of a Stored Video,” in Proc. IEEE 1999 TENCON, pp. 919-922, 1999.
[10]C. W. Lin, J. Zhou, J. Youn, and M. T. Sun, “MPEG Video Streaming with VCR Functionality,” IEEE Transaction on Circuit and System for Video Technology, Vol. 11, No. 3, pp. 415-425, Mar. 2001.
[11]R. Talluri, “Error-Resilient Video Coding in ISO MPEG-4 Standard,” IEEE Communication. Magazine, Vol. 36, No. 6, pp. 112—119, July 1998.
[12]S. Wenger, “Video Redundancy Coding in H.263+,” in Proc. AVSPN 97, Aberdeen, U.K., 1997.
[13]Wenger, S., G. Knorr, J. Ott, and F. Kossentini, “Error Resilience Support in H.263+”, IEEE Transaction on Circuit and System for Video Technology, Vol. 8, pp. 867-87, Nov. 1998.
[14]Y. Wang, J. Ostermann, and Y.-Q. Zhang, Video Processing and Communications, Prentice Hall, 2002.
[15]Q.-F. Zhu, Y. Wang, and L. Shaw, “Coding and Cell-Loss Recovery in DCT-Based Packet Video,” IEEE Transactions on circuits and systems for video technology, Vol. 3, No. 3, 1993.
[16]B. Girod, and N. Farber, “Feedback-Based Error Control for Mobile Video Transmission,” Proceedings of the IEEE, Vol. 87, No. 10, Oct 1999.