Multi-Frame Motion-Compensated Prediction for Video Transmission THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE MULTI-FRAME MOTION COMPENSATED PREDICTION FOR VIDEO TRANSMISSION THOMAS WIEGAND Heinrich Hertz Institute BERNDGIROD Stanford University ., SPRINGER SCIENCE+BUSINESS MEDIA, LLC Library of Congress Cataloging-in-Publication Data Wiegand, Thomas. Multi-frame motion-compensated prediction for video transmission / Thomas Wiegand, Bernd Girod. p.cm.-(Kluwer international series in engineering and computer science; SECS 636) Includes bibliographical references and index. ISBN 978-1-4613-5578-6 ISBN 978-1-4615-1487-9 (eBook) DOI 10.1007/978-1-4615-1487-9 1. Digital video. 2. Video compression. 3. Coding theory. I. Girod, Bernd. 11. Tide. III. Series. TK6680.5 .W54 2001 621.388-dc21 2001046191 Copyright © 2001 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 2001 Softcover reprint of the hardcover 1s t edition 2001 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any me ans, mechanical, photo copying, recording, or otherwise, without the prior written permission of the publisher, Springer Science+Business Media, LLC. Printed on acid-free paper. Contents Preface xiii Introduction xvii 1.1 Main Contributions xviii 1.2 Practical Importance xx 1.3 Organization of the Book xxi 1. STATE-OF-THE-ART VIDEO TRANSMISSION 1 1.1 Video Transmission System 2 1.2 Basic Components of a Video Codec 3 1.3 ITU-T Recommendation H.263 7 1.4 Effectiveness of Motion Compensation Techniques in Hybrid Video Coding 8 1.5 Advanced Motion Compensation Techniques 10 1.5.1 Exploitation of Long-Term Statistical Dependencies 11 1.5.2 Efficient Modeling of the Motion Vector Field 13 1.5.3 Multi-Hypothesis Prediction 15 1.6 Video Transmission Over Error Prone Channels 16 1.7 Chapter Summary 19 2. RATE-CONSTRAINED CODER CONTROL 21 2.1 Optimization Using Lagrangian Techniques 22 2.2 Lagrangian Optimization in Video Coding 23 2.3 Coder Control for ITU-T Recommendation H.263 25 2.4 Choosing the Coder Control Parameters 26 2.4.1 Experimental Determination of the Coder Control Parameters 27 2.4.2 Interpretation of the Lagrange Parameter 29 2.4.3 Efficiency Evaluation for the Parameter Choice 33 2.5 Comparison to Other Encoding Strategies 34 2.6 Chapter Summary 35 VI MULTI-FRAME MOTION-COMPENSATED PREDICTION 3. LONG-TERM MEMORY MOTION-COMPENSATED PREDICTION 37 3.1 Long-Term Memory Motion Compensation 38 3.2 Prediction Performance 41 3.2.1 Scene Cuts 41 3.2.2 Uncovered Background 43 3.2.3 Texture with Aliasing 44 3.2.4 Similar Realizations of a Noisy Image Sequence 45 3.2.5 Relationship to other Prediction Methods 45 3.3 Statistical Model for the Prediction Gain 46 3.4 Integration into ITU-T Recommendation H.263 52 3.4.1 Rate-Constrained Long-Term Memory Prediction 53 3.4.2 Rate-Distortion Performance 55 3.5 Discussion and Outlook 58 3.6 Chapter Summary 59 4. AFFINE MULTI-FRAME MOTION-COMPENSATED PREDICTION 61 4.1 Affine Multi-Frame Motion Compensation 62 4.1.1 Syntax of the Video Codec 63 4.1.2 Affine Motion Model 65 4.2 Rate-Constrained Coder Control 66 4.2.1 Affine Motion Parameter Estimation 66 4.2.2 Reference Picture Warping 71 4.2.3 Rate-Constrained Multi-Frame Hybrid Video Encoding 71 4.2.4 Determination of the Number of Efficient Reference Frames 72 4.3 Experiments 73 4.3.1 Affine Motion Compensation 73 4.3.2 Combination of Affine and Long-Term Memory Motion Compensation 76 4.4 Assessment of the Rate-Distortion Performance of Multi-Frame Prediction 80 4.5 Discussion and Outlook 81 4.6 Chapter Summary 81 5. FAST MOTION ESTIMATION FOR MULTI-FRAME PREDICTION 83 5.1 Lossless Fast Motion Estimation 84 5.1.1 Triangle Inequalities for Distortion Approximation 85 5.1.2 Search Order 86 5.1.3 Search Space 87 5.2 Lossy Fast Motion Estimation 88 5.2.1 Sub-Sampling of the Search Space 88 5.2.2 Sub-Sampling of the Block 89 5.3 Experiments 90 5.3.1 Results for Lossless Methods 90 5.3.2 Results for Lossy Methods 94 5.4 Discussion and Outlook 98 5.5 Chapter Summary 99 Contents vii 6. ERROR RESILIENT VIDEO TRANSMISSION 101 6.1 Error Resilient Extensions of the Decoder 102 6.2 Error-Resilient Coder Control 103 6.2.1 Inter-Frame Error Propagation 104 6.2.2 Estimation of the Expected Transmission Error Distortion 105 6.2.3 Incorporation into Lagrangian Coder Control 109 6.3 Experiments 111 6.3.1 Channel Model and Modulation 111 6.3.2 Channel Coding and Error Control 112 6.3.3 Results without Feedback 114 6.3.4 Experimental Results with Feedback 119 6.4 Discussion and Outlook 122 6.5 Chapter Summary 122 7. CONCLUSIONS 125 Appendices 129 A- Simulation Conditions 129 A.l Distortion Measures 129 A.2 Test Sequences 130 B- Computation of Expected Values 131 References 133 Index 147 Foreword This body of work by Thomas Wiegand and Bernd Girod has already proved to have an exceptional degree of influence in the video technology community, and I have personally been in a position to proudly witness much of that influence. I have been participating heavily in the video coding standardization com munity for some years - recently as the primary chairman ("rapporteur") of the video coding work in both of the major organizations in that area (the ITU-T VCEG and ISO/IEC MPEG organizations). The supporters of such efforts look for meritorious research ideas that can move smoothly from step to step in the process found there: • generation of strong proposal descriptions, • tests of effectiveness, • adjustments for practicality and general flexibility, and • precise description in a final approved design specification. The ultimate hope in the standardization community is that the specifications written there and the other contributions developed there will prove to provide all the benefits of the best such efforts: • enabling the growth of markets for products that work well together, • maximizing the quality of these products in widespread use, and • progressing the technical understanding of the general community. The most well-known example of such a successful effort in the video coding community is the MPEG-2 video standard (formally identified as ITU-T Rec ommendation H.262 or as ISOIIEC International Standard 13818-2). MPEG-2 video is now used for DVD Video disks, direct-broadcast satellite services, terrestrial broadcast television for conventional and high-definition services, x MULTI-FRAME MOTION-COMPENSATED PREDICTION digital cable television, and more. The MPEG-2 story owes some of its success to lessons learned in earlier standardization efforts - including the first digi tal video coding standard known as ITU-T Recommendation H.120, the first truly practical success known as ITU-T Recommendation H.261 (a standard that enabled the growth of the new industry of videoconferencing), and the MPEG-I video standard (formally ISOIIEC 11172-2, which enabled the stor age of movies onto inexpensive compact disks). Each generation of technology has benefited from lessons learned in previous efforts. The next generation of video coding standard after MPEG-2 is represented by ITU-T Recommendation H.263 (a standard primarily used today for video conferencing, although showing strong potential for use in a variety of other applications), and it was the "H.263++" project for enhancing that standard that provided a key forum for Wiegand and Girod's work. At the end of 1997, Thomas Wiegand, Xiaozheng Zhang, Bernd Girod, and Barry Andrews brought a fateful contribution (contribution Q15-C-11) to the Eibsee, Germany meeting of the ITU-T Video Coding Experts Group (VCEG). In it they proposed their design for using long-term memory motion compensated prediction to improve the fidelity of compressed digital video. The use of long-term memory had already begun to appear in video coding with the recent adoption of the error/loss resilience feature known as reference picture selection or as "NEWPRED" (adopted into H.263 Annex N with final approval in January of 1998 and also adopted about two years later into the most recent ISO/IEC video standard, MPEG-4). But the demonstration of a way to use long-term memory as an effective means of improving coded video quality for reliable channels was clearly new and exciting. Part of the analysis in that contribution was a discussion of the importance of using good rate-distortion optimization techniques in any video encoding process. The authors pointed out that the reference encoding method then in use by VCEG (called the group's test model number 8) could be significantly improved by incorporating better rate-distortion optimization. It was highly admirable that, in the interest of fairness, part of the proposal contribution was a description of a method to improve the quality of the reference competition against which their proposal would be evaluated. It was in this contribution that I first saw the simple equation = .AMOTION V.AMODE . A few months later (in VCEG contribution Q15-D-13), Wiegand and Andrews followed up with the extremely elegant simplification .AMODE = 0.85 . Q2 . For years (starting with the publication of a paper by Yair Shoham and Allen Gersho in 1988), the principles of rate-distortion optimization had become xi an increasingly-familiar concept in the video compression community. Many members of the community (myself included, starting in 1991) had published work on the topic - work that was all governed by a frustrating little parameter known as A. But figuring out what value to use for A had long been a serious annoyance. It took keen insight and strong analysis to sort out the proper relationship between a good choice for A and Q, the parameter governing the coarseness of the quantization. Wiegand, working under the tutelage of Girod and in collaboration with others at the University of Erlangen-Nuremberg and at 8x8, Inc. (now Netergy Networks), demonstrated that insight and analytical strength. The ITU-T VCEG adopted the rate-distortion optimization method into its test model immediately (in April of 1998), and has used that method ever since. It is now preparing to adopt a description of it as an appendix to the H.263 standard to aid those interested in using the standard. I personally liked the technique so much that I persuaded Thomas Wiegand to co-author a paper with me for the November, 1998 issue of the IEEE Signal Processing Magazine and include a description of the method. And at the time of this writing, the ISO/IEC Moving Picture Experts Group (MPEG) is preparing to to conduct some tests against a reference level of quality produced by its recent MPEG-4 video standard (ISOIIEC International Standard 14496-2) - and it appears very likely that MPEG will also join the movement by choosing a reference that operates using that same rate-distortion optimization method. But long-term memory motion compensation was the real subject of that 1997 contribution, while the rate-distortion optimization was only a side note. The main topic has fared even better than the aside. The initial reaction in the community was not one of unanimous enthusiasm - in fact some thought that the idea of increasing the memory and search requirements of video encoders and decoders was highly ill-advised. But diligence, strong demonstrations of results, and perhaps more iteration of Moore's Law soon persuaded the ITU-T VCEG to adopt the long-term memory feature as Annex U to Recommenda tion H.263. After good cross-verified core experiment results were shown in February of 1999, the proposal was adopted as draft Annex U. Additional good work described in this text in regard to fast search methods helped in convincing the skeptics of the practicality of using long-term memory. Ultimately, draft Annex U was adopted as a work item and evolved to preliminary approval in February of 2000 and then final approval in November of 2000. A remarkable event took place in Osaka in May of 2000, when Michael Horowitz of Polycom, Inc. demonstrated an actual real-time implementation of Annex U in a prototype of a full videoconferencing product (VCEG con tribution Q1S-J-11). Real-time efficacy demonstrations of preliminary draft video coding standards has been an exceedingly rare thing in recent years. The obvious improvement in quality that was demonstrated by Horowitz's system