`
`
`
`TK 668a "
`
`.5
`
`.M69
`1996
`
`
`Digital
`uiflrnescna
`
`'; £r1dards
`
`
`
`
`
`
`
`
`
`
`MPEG VIDEO
`:2 MPHESSIDN
`QTANDAHD
`
`Joan L. Mitchell,
`
`William B. Pennebaker,
`
`Chad E. Fogg, and
`Didier J. LeGaII
`
`Page 1 of 498
`
`GOOGLE EXHIBIT 1018
`
`Page 1 of 498
`
`GOOGLE EXHIBIT 1018
`
`

`

`
`
`Digital systcnisIElcctrical engineering
`
` MF’EG
`
`
`VIDEO
`
`
`COMPRESSION
`STANDARD
`
`*1 '
`
`l
`
`
`
`
`
`
`LIBRARY OF CONGRESS:
`
`
`
`
`
`
`
`
`
`
`
`
`0 006139749? _.
`
`
`
`
`
`
`
`,-
`
`
`
`
`
`.
`
`
`
`
`
`
`
`
`For all those interested in high definition television,
`
`
`
`
`
`
`multimedia. and image compression, this unique
`
`
`
`
`
`
`
`
`reference will be an essential tool.
`It provides
`
`
`
`
`
`
`
`the first comprehensive introduction to this field.
`
`
`
`
`
`incorporating material ranging from basic concerns
`
`
`
`
`
`
`
`of newcomers to the field through sophisticated
`
`
`
`
`
`
`reviews of cutting edge technical issues.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Written by acknowledged experts In the field. MPEG
`
`
`
`
`
`Video Compression Standard offers important bene—
`
`
`
`
`fits to readers Including:
`
`
`
`
`
`
`
`
`
`
`
`Detailed information on MPEG modes of operation. signaling conven-
`
`
`
`
`
`
`
`tions. and structure of MPEG compressed data
`
`
`
`
`
`
`
`
`
`
`
`
`0 Each section of the book is labeled by level of technical difficulty.
`
`
`
`
`
`
`
`
`
`
`
`
`allowing less technical readers to skip higher level sections and still gain
`
`
`
`
`
`
`
`
`
`
`
`a broad understanding of the subject while guiding advanced readers to
`
`
`
`
`
`the in-depth coverage they require
`
`
`
`
`
`
`
`
`
`
`With its comprehensive coverage of MPEG video compression. this impor-
`
`
`
`
`
`
`
`
`
`
`
`
`
`tant book meets the needs of those working to develop the standard as
`
`
`
`
`
`
`
`
`
`
`
`well as those who use MPEG in their work. Electrical engineers. multimedia
`producers. computer scientists. as well as all those interested in this fast
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`growing field will find MPEG Video Compression Standard essential in
`their work.
`
`
`
`
`
`
`
`
`ABOUT THE AUTHORS
`
`
`
`
`
`
`
`
`
`
`
`
`loan 1.. Mitchell is a Research Staff Member at the IBM Thomas J. Watson
`Research Center.
`
`
`
`
`
`
`
`
`
`
`
`
`nsultant and former Research Staff Member,
`William ll. Pennebaker is a
`
`
`
`
`
`IBM Thomas J. Watson Research Center.
`
`
`
`
`
`
`Chad E. fogg. Cascade Design Automation
`
`
`
`Didier I. LeGall is Vice President of Research and Development. C-cube
`
`
`
`
`
`
`
`Microsystems.
`
`
`
`
`
`
`
`
`
`
`
`
`Chapman 8. Hall
`
`
`
`
`
`
`
`
`
`
`“5 filth Avenue. NewYork. NY 10003
`2—6 Boundary Row. London SE1 BHN
`
`
`
`
`
`
`Printed In USA.
`
`
`
`
`
`
`jOlN US ON THE INTERNET WWW: httprfhvwwlhomsoncom
`
`
`
`
`
`
`
`Visit Chapman ti. Hall's lnternet Rmource Center-for Information on
`
`
`
`
`
`
`
`
`
`
`our new publications. links to useful sites on the World Wide Web and
`
`
`
`
`
`
`
`
`
`
`
`
`
`an opportunity to join our e-mall mailing list.
`
`
`
`
`
`
`
`
`Point your browser to: htip:flwwwmhaphal|.com/chaphall.html or
`
`
`
`
`
`http://Www.chaphall.com/chaphall/electeng.htrnl for Electrical
`
`
`
`Engineering
`
`
`
`A service of I®P.
`
`
`
`
`
`
`
`
`
`
`ISBN III-ll LE—DB??L-5
`
`9 D g 0 0
`
`
`
`
`9 ?80412 087714
`
`' -
`
`
`
`_
`
`—____«la
`
`Page 2 of 498
`
`
`
`
`
`Page 2 of 498
`
`

`

`I®P‘
`
`Mitchell
`
`
`
`
`
`
`
`
`
`050mSEdW
`
`F n
`
`a g 1
`
`1
`J]
`m
`;m
`fl
`
`
`
`u .
`
`2 f
`
`l
`
`53>
`:2
`-u
`,>
`11
`.IU
`
`
`
`
`
`
`
`
`
`
`
`Page 3 of 498
`
`
`
`Page 3 of 498
`
`

`

`
`
`
` A,“AVA.e.._e*.__JV
`
`p.1«Worm;MMW._44«M4,‘44,“A.”
`
`
`
`i
`‘
`
`.
`
`5
`
`f
`
`_,
`
`
`
`
`
`
`
`
`Join ,Us onthe Internet.
`
`
`
`W: http2/ /Www.thomson.com
`EMAIL:
`findit@kiosk.thomson.com
`
`
`
`.
`
`
`
`
`
`
`
`
`
`
`
`thomsonmm is the on—line portal for the products, services and
`
`
`
`
`
`
`
`resources available from International Thomson Publishing (ITP).
`
`
`
`
`
`
`
`
`
`
`
`This Internet kiosk gives users immediate access to more than 34 ITP
`
`
`
`
`
`
`
`
`publishers and over 20,000 products. Through thomsonmm Internet
`
`
`
`
`
`
`
`
`users can search catalogs, examine subject-specific resource centers
`
`
`
`
`
`
`
`
`
`
`and subscribe to electronic discussion lists. You can purchase ITP
`
`
`
`
`
`
`
`
`
`products from your local bookseller, or directly through thomson.com.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`apman 8: Hall’s Internet Resource Center for information on our new publications,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to useful sites on the World Wide Web and an opportunity to join our e—mail
`
`
`
`
`
`
`
`
`
`,' mailing list. Point your browser to: http://www.chaphall.com/chaphall.html or
`
`
`
`
`’ http:7/w'ww.chaphall.com/chaphall/electeng.html for Electrical Engineering
`
`
`
`A service of I®P
`
`
`
`
`®
`
`
`
`
`
`
`
`Page 4 of 498
`
`Page 4 of 498
`
`

`

`
`
`
`
`{If m CHAPMAN ax HALL
`
`I®P INTERNATIONAL THOMSON PUBLISHING
`
`
`
`
`
`
`
`
`
`
`
`
`New York - Albany - Bonn * Boston - Cincinnati - Detroit - London - Madnd - Melbourne
`
`
`
`
`
`
`
`
`
`
`Mexico City ' Pacific Grove ' Paris - San Francisco ~ Singapore - Tokyo - Toronto - Washington
`
`
`
`
`
`
`
`‘0,
`
`’
`
`®
`
`Page 5 of 498
`
`
`
`
`
`Page 5 of 498
`
`

`

`Printed in the United States of America Chapman ti: Hall
`
`
`
`
`
`Cover design: Curtis Tow Graphics
`
`
`
`
`
`
`
`
`Copyright 0 1996 by Chapman 8: Hail
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`115 Fifth Avenue
`New York, N? 10003
`
`
`
`
`
`
`
`
`
`
`
`Chapman a Hall
`
`
`
`2«6 Boundary Row
`
`
`
`London SE] BHN
`
`England
`
`Thomas Nelson Australia
`
`
`102 Dodds Street
`
`
`
`
`
`South Melbourne, 3205
`
`
`Victoria, Australia
`
`
`
`
`
`
`
`
`
`
`Chapman 5: Hall GmbH
`
`
`
`Postiach 100 263
`
`069442 Weinheim
`
`Germany
`
`
`
`
`
`International Thomson Editores
`
`
`
`
`
`
`Campos Eliseos 385, Piso 7
`Col. Polanco
`
`
`
`
`11560 Mexico D.F
`
`Mexico
`
`
`
`
`
`International Thomson Publishing—Japan
`
`
`
`
`Hirakawacho-cho Kyowa Building, 3F
`
`
`1-2-1 Hirakawacho—cho
`
`
`
`Chiyoda-ku, 102 Tokyo
`
`Japan
`
`
`
`
`
`
`International Thomson Publishing Asia
`21 Henderson Road #05—10
`
`
`
`
`
`
`Henderson Building
`
`
`Singapore 0315
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`All rights reserved. No part of this book covered by the copyright hereon may be reproduced or
`
`
`
`
`
`
`
`
`
`
`
`
`
`used in any form or by any means—graphic, electronic, or mechanical, including photocopying,
`
`
`
`
`
`
`
`
`
`
`
`
`recording, taping, or information storage and retrieval systems—without the written permission ot
`
`
`the publisher.
`
`2345673910XXX0100999897
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Library of Congress Cataloging-in-Publicat‘ion Data
`
`
`
`.
`. [et all.
`
`
`
`
`
`
`
`MPEG video : compression standard I loan 1.. Mitchell .
`
`
`
`
`
`
`
`cm.
`p.
`
`
`Includes bibliographical references and index.
`
`
`
`
`
`
`
`
`ISBN 0-412-08771-5 (alk. paper)
`3. Sound -
`1. Digital video. Z Video compression — Standards.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`— Recording and reproducing - Digital techniques - Standards.
`
`
`
`
`
`
`
`4. Coding theory.
`1. Mitchell, loan 1..
`mama 1996
`
`
`621.388—dc20
`
`
`
`96-31124
`
`CIP
`
`
`
`British Library Cataloguing in Publication Data available
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`To order this or any other Chapman 8: Hall book, please contact International Thomson
`
`
`
`
`
`
`
`
`
`
`
`Publishing, 7625 Empire Drive, Florence, KY 41042. Phone: {606) 525-6600 or 1—300-342'3536‘
`
`
`
`
`
`Fax: (606) 525-7778. email: order®chaphall.corn.
`
`
`
`For acornplete listing of Chapman 6: Hall titles, send your request to Chapman 3‘ “311' Dept- BC!
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`115 Fifth Avenue, New York, NY 10003.
`
`
`
`Page 6 of 498
`
`Page 6 of 498
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`To
`
`
`
`
`
`
`
`Nancy, Don, and Sandy
`
`
`
`
`Margaret, Betsy, Patty, and Erik
`
`
`
`Lori and John.
`
`
`
`Dedication
`
`
`
`
`
`
`
`Page 7 of 498
`
`Page 7 of 498
`
`

`

`
`
`
`Series Preface
`
`
`
`
`
`
`
`
`
`
`
`
`
`This book initiates a new digital multimedia standards series. The purpose
`
`
`
`
`
`
`
`
`
`
`of the series is to make information about digital multimedia standards
`
`
`
`
`
`
`
`
`
`
`
`readily available. Both tutorial and advanced topics will be covered in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`series, often in one book. Our hope is that users will find the series helpful
`
`
`
`
`
`
`
`
`
`
`
`in deciding what standards to support and use while implementors will dis-
`
`
`
`
`
`
`
`
`
`
`cover a wealth of technical: details that help them implement those standards
`
`correctly.
`
`
`
`
`
`
`
`
`In today’s global economy standards are increasingly important. Yet
`
`
`
`
`
`
`
`
`
`
`
`
`until a standard is widely used, most of the benefits of standardization are
`
`
`
`
`
`
`
`
`
`not realized. We hope that standards committee chairpeople will organize
`
`
`
`
`
`
`
`
`
`
`
`
`and encourage a book in this series devoted to their new standard. This can
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`be a forum to share and preserve some of the “why” and “how” that went
`
`
`
`
`
`
`
`
`
`
`
`
`
`into the development of the standard and, in the process, assist in the rapid
`
`
`
`
`adoption of the standard.
`V
`
`
`
`
`
`
`
`
`
`
`
`Already in production for this series are books titled Digital Video: In—
`
`
`
`
`
`
`
`
`troduction to MPEG-2 and Data Compression in Systems.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5
`
`3’
`,
`
`i
`
`
`
`vii
`
`
`
`
`
`Page 8 of 498
`
`Page 8 of 498
`
`

`

`Foreword
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The reduction of bitrate of digitised television signals has been an R&D
`
`
`
`
`
`
`
`
`
`
`
`
`
`topic in research centres and academia for more than 30 years. Many were
`
`
`
`
`
`
`
`
`
`
`
`
`the purposes for which research was funded, but all shared the basic ra—
`
`
`
`
`
`
`
`
`
`
`
`
`
`tionale. If you had a digital or digitised delivery medium and could bring
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the more than 200 Mbit/s bitrate of PCM television down to a value that
`
`
`
`
`
`
`
`
`
`
`could be handled economically by signal processing technology then you
`
`
`
`
`
`
`
`
`
`would achieve the goal of substantially improving existing products/ services
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`or even creating new ones. The bitrate of up to 1.5 Mbit/s was the value
`around which three industries shared a common interest towards the end of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the ’80s: consumer electronics with compact disc, broadcasting with digi—
`tal radio and telecommunications with Narrowband ISDN and ASDL. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`merit of MPEG was its ability to identify the opportunity and to bring
`
`
`
`
`
`
`
`
`
`disparate industries to work together. The unprecedented degree of interna-
`
`
`
`
`
`
`
`
`tional collaboration involving hundreds of researchers produced a standard -
`
`
`
`
`
`
`
`
`
`
`
`
`MPEG-l - of very high technical quality. Even today, after several years and
`
`
`
`
`
`
`
`
`
`
`
`countless implementations not a single error was found in the specification.
`
`
`
`
`
`
`
`
`
`
`
`
`MPEG—l devices are now counted by the millions in all continents. MPEG—l
`
`
`
`
`
`
`
`
`
`
`
`
`encoded content can be found everywhere and is the first implementation of
`
`
`
`
`
`
`
`
`
`
`
`delivery media independence of content. The beginning of the ’90s provided
`
`
`
`
`
`
`
`
`
`
`
`the next opportunity with a general interest in a new standard— MPEG—2 ‘.
`
`
`
`
`
`
`
`
`- for applications spanning all industries: broadcasting over satellite, ter—
`
`
`
`
`
`
`
`
`
`
`
`restrial and CATV networks, Broadband ISDN, digital discs and tapes etc.
`
`
`
`
`
`
`
`
`
`
`The availability of another MPEG standards promised — and delivered — as
`
`
`
`
`
`
`
`
`
`
`
`
`scheduled was not a small contribution to the multimedia revolution we are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`living today. The book by Drs. Le Gall, Fogg, Mitchell and Pennebaker is a
`
`
`
`
`
`
`
`
`
`
`recommended reading for those who want to have a thorough understanding
`
`
`
`
`
`
`
`
`
`
`
`
`of the Video parts of MPEG—1 and MPEG-2. The concepts that were devel—
`
`
`
`
`
`
`
`
`
`
`
`
`oped in those standards and presented in the book are a necessary reading
`
`
`
`
`
`
`
`
`
`
`
`
`for anybody who needs to work on them or go beyond them;
`
`
`
`
`
`
`
`
`Leonardo Chiariglione
`
`
`
`Convenor, ISO/IEC JTCl/SCQQ/WGll (MPEG)
`
`
`
`ix
`
`
`
`
`
`Page 9 of 498
`
`
`
`
`
`
`
`Page 9 of 498
`
`

`

`
`
`Acknowledgments
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Several hundred technical experts worked hard, attended meetings all over
`
`
`
`
`
`
`
`
`
`
`
`the world, and spent many, many hours of personal and professional time
`
`
`
`
`
`
`
`
`
`
`
`before reaching a consensus on the MPEG—1 standard. We want to specifi—
`
`
`
`
`
`
`
`
`
`
`cally acknowledge their dedicated work even though they are too numerous
`
`
`
`
`
`to be listed by name.
`.
`
`
`
`
`
`
`
`
`
`
`JM wishes to thank a former manager, Cesar Gonzales, for permission
`
`
`
`
`
`
`
`
`
`
`
`
`
`to start work on this book. She wishes to thank her current IBM manage—
`
`
`
`
`
`
`
`
`
`
`
`ment and in particular, Fred Mintzer and- Howard Sachar, for giving her
`
`
`
`
`
`
`
`
`
`
`
`permission to take a two-year leave of absence from IBM. Her participation
`
`
`
`
`
`
`
`
`
`
`
`
`in writing this book would have been much more diflicult without this extra
`
`
`
`
`
`
`
`
`
`
`freedom. She also acknowledges the support of the Computer and Electri-
`
`
`
`
`
`
`
`
`
`cal Engineering Department and the Beckman Institute at the University
`
`
`
`
`
`
`
`
`
`
`
`of Illinois, Urbana, 111., for their 1996 part—time Visiting Professor and Vis—
`
`
`
`
`
`
`
`
`
`
`
`
`iting Scientist positions which she held during the final stages of finishing
`
`
`
`
`
`
`
`
`
`
`
`
`this book. She also wants to thank Christiana Creighton; Sandy and David
`
`
`
`
`
`
`
`
`
`
`Creighton; Anne Gilligan; Sandy Grover and Dorothy Cullinan of the Cut—
`
`
`
`
`
`
`
`
`
`
`
`
`leaf Maples Motel, Arlington, VT; Jackie and Bruce Kelman; Joan and Don
`
`
`
`
`
`
`
`
`
`
`
`Lucas; Sherri and Peter McCormick; Doris, Bill, and Carol Mitchell; Nancy
`
`
`
`
`
`
`
`
`
`
`and Don Mitchell; Margaret and Bill Pennebaker; Ruth Redden; Frances
`
`
`
`
`
`
`
`
`
`
`
`and Charles Riggs; and Norma and Don Vance for encouragement, meals,
`
`
`
`
`
`
`
`
`and lodging during the writing of this book.
`
`
`
`
`
`
`
`
`
`
`
`
`WP wishes to thank his wife, Margaret, for her patience and active
`
`
`
`
`
`
`
`
`
`
`
`
`support during the preparation of this book and the implementation of a
`
`
`
`
`
`
`
`
`
`
`
`MPEG—1 video encoder and decoder. Acknowledgment is also given to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`neighbors who took the subjective quality tests, results of which are in this
`book.
`
`
`
`
`
`
`
`
`
`
`
`
`
`We also want to thank the vendors who supplied information for this
`
`
`
`
`
`
`
`
`
`
`
`
`book; Cliff Reader, who contributed the IPR chapter; our many editors at
`
`
`
`
`
`
`
`
`
`
`
`Van Nostrand Reinhold and later at Chapman and Hall; Nancy Mitchell,
`
`
`
`
`
`
`
`
`
`
`
`
`
`who reviewed this book for consistency at the easiest technical level; and all
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`of the other people who reviewed this book and helped us correct our errors
`
`
`before publication.
`
`Xi
`
`
`
`Page 10 of 498
`
`
`
`
`
`
`
`
`
`
`
`Page 10 of 498
`
`

`

`
`
`
`
`SifiQaEzw..
`‘E
`L;%‘
`
`“a
`
`4
`
`
`
`
`
`
`
`Contents
`
`
`
`
`
`DedicatiOn
`
`
`Series Preface
`
`Foreword
`Acknowledgments
`
`
`
`List of Figures
`
`
`
`List of Tables
`
`Trademarks
`
`
`
`
`
`vii
`
`ix
`
`
`
`
`
`xi
`xxiii
`xxxi
`xxxvii
`
`1
`
`
`
`'
`
`1
`
`2
`3
`4
`4
`5
`
`
`Introduction
`
`
`
`
`
`
`.......................
`1.1 Why compress? O
`
`
`
`
`
`
`1.2 Why standardize video compression? 0
`...........
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1.3 VocabularyO
`..........................
`
`
`
`
`
`
`Sequences, pictures, and samplesO
`1.3.1
`.........
`
`
`
`
`Frames and fieldsO
`..................
`1.3.2
`
`
`
`
`
`
`
`6
`1.3.3
`Pels and pixelsO ...... ‘ ..............
`
`
`
`
`7
`1.3.4 Compression vocabularyO
`..............
`
`
`
`
`7
`.Standards vocabularyO
`1.3.5
`................
`
`
`
`
`8
`.................
`1.3.6 MPEG vocabularyO
`
`
`
`
`
`
`
`
`8
`..... ' .......
`1.4 A quick look at MPEG compressionO
`
`
`
`
`
`
`
`, 12
`1.5 Compact pseudocode notation in MPEGO
`.
`.
`.
`.
`.
`: ~.
`.‘
`.
`
`
`
`
`. 1.6 MPEG applicationsO
`..................... 12
`
`
`
`
`
`
`1.7 Organization of the bookO
`.................. 13
`
`
`
`
`
`1.8 Level of difficultyO
`...................... 14
`
`
`
`
`1.9 An international collaborationO
`............... 14
`
`
`
`
`
`
`1.10 An evolving standardO
`.................... 15
`
`
`
`
`
`
`2 Overview of MPEG
`
`
`
`
`
`
`.
`.
`.
`_, ................. 17
`2.1 MPEG system layerO
`
`
`
`
`System/target decoderO
`2.1.1
`............... 19
`
`
`
`
`
`2.1.2
`System layer syntaxO .' .......... '.
`20
`.
`.
`.
`.
`.
`
`
`
`
`
`2.2 MPEG audioO .......................... 20
`
`
`
`
`
`2.3 MPEG videoO
`......................... 21
`
`
`
`
`
`2.3.1 MPEG video layersO
`................. 22
`
`17
`
`xiii
`
`
`
`
`
`
`
`
`
`Page 11 of 498
`
`Page 11 of 498
`
`

`

`
`
`K iv
`
`
`
`
`
`
`
`
`
`2.3.2 Display and coding orderO
`.............. 23
`
`
`
`
`2.3.3 MacroblockO
`..................... 23
`
`
`
`
`2.3.4
`SliceO
`......................... 23
`
`
`
`
`
`
`
`
`2.3.5 The discrete cosine transform in MPEGO
`25
`.
`.
`.
`.
`.
`2.3.6 QuantizationO ..................... 27
`
`
`
`
`
`
`
`2.3.7 Motion con'lpensationO
`................ 28
`
`
`
`
`
`2.3.8 MPEG coding InodelsO ................ 29
`
`
`
`
`
`2.3.9 Encoder decision strategieso
`............. 30
`
`
`2.4 MPEG-2O
`........................... 30
`
`
`
`
`ReiPEG—LIO
`2.5
`
`........................... 31
`
`
`
`
`
`
`
`33
`3 The Discrete Cosine Transform
`
`
`
`
`
`
`3.1 The one—dimensional cosine transformO ........... 33
`
`
`
`
`
`
`
`3.2
`1—D discrete cosine transform (DCT)O
`........... 37
`
`
`
`
`
`2-D DCTO ........................... 42
`3.3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3.4 Why use the DCT?O
`..................... 44
`
`
`
`
`
`
`....... 44
`3.4.1 Decorrelation and energy compactionO
`
`
`
`
`
`3.4.2
`Efficient DCT algoritlnnsO .............. 45
`
`
`
`
`
`
`3.5 Precision of the DCTO
`.................... 45
`
`
`
`
`
`
`
`3.6 Quantization of the DCTO .................. 46
`
`
`
`
`
`
`3.6.1 Rounding conventions for quantizationO
`...... 46
`
`
`
`
`
`
`
`Scaling of quai'ltizer tablesO
`............. 48
`3.6.2
`
`
`
`
`
`
`3.6.2.1 Quantization of the FDCTO ........ 48
`
`
`
`
`
`
`3.6.2.2 Dequantization of the IDCTO ....... 49
`
`
`
`
`
`3.7 Mismatch of IDCTsO
`..................... 49
`
`
`4.1.5
`
`
`
`
`
`
`
`51
`4 Aspects of Visual Perception
`
`
`
`
`.................... 52
`4.1 Color representationsO
`
`
`
`
`4.1.1 Tricln‘oniatic theoryO ................. 52
`
`
`
`
`
`4.1.2 Luminance and ChrominanceO
`............ 54
`
`
`
`
`4.1.3 Brightness perceptionO ................ 54
`
`
`
`4.1.4 Gamma correctionO .................. 55
`
`
`
`
`
`
`
`Luma and gamma—corrected luminanceO
`...... 58
`
`
`
`
`
`
`
`
`
`58
`.
`.
`.
`4.1.6 YUV and YCbCr color systems and chromaO
`
`
`
`
`
`
`
`4.1.? Opponent model of human visionO
`......... 60
`
`
`
`
`4.1.8 Cln‘omaticity coordinatesO
`.............. 61
`
`
`
`
`
`4.1.9 Center of gravityo
`.................. 62
`
`
`
`4.1.10 Coordinate transforniationso
`............ 63
`
`
`
`
`
`4.1.11 CIE primaries.
`.................... 64
`
`
`
`
`
`4.1.12 CIELUV color space.
`................ 66
`
`
`
`
`
`4.2 Resolving spatial detailO
`................... 67
`
`
`
`
`
`4.2.1 MPEG cln‘ominance samplingO
`........... 68
`
`
`
`
`
`4.2.2 Varying precisionO
`.................. 69
`
`'
`
`g
`
`.
`
`
`
`
`
`_
`i
`
`.
`
`.,
`
`Page 12 of 498
`
`

`

`
`
`
`
`
`
`
`
`
`
`4.2.3
`Frequency weighting and quantizationO ....... 69
`
`
`
`
`
`
`4.2.4 Activity masking and facilitationO
`......... 70
`
`
`
`
`
`
`4.3 Perception of motionO
`.................... 72
`
`
`
`
`
`4.3.1 Critical flicker frequencyO
`.............. 72
`
`
`
`
`
`
`
`Spatial resolution of time—varying scenesO
`..... 74
`4.3.2
`
`
`
`
`
`
`
`
`4.3.3 Motion sensingO
`................... 75
`
`
`
`
`4.3.4 Temporal maskingO. .................. 76
`
`
`
`
`
`
`4.3.5 Tracking of moving objectsO ............. 78
`
`
`
`
`
`4.3.6 Coding time-varying scenesO ............. 78
`
`
`
`
`
`
`81
`5 MPEG' Coding Principles
`
`
`
`
`
`
`
`
`
`
`
`
`.................. 81
`5.1 Coding system structureO
`
`
`
`
`
`
`
`
`
`
`
`................. 82
`Isolating the modelO
`5.1.1
`
`
`
`
`
`
`5.1.2
`Symbols and statistical modelingO
`......... 83
`
`
`
`
`
`
`
`
`
`
`
`
`
`5.2 Entropy codingO
`....................... 84
`
`
`
`
`
`
`Principles of entropy codingO
`............ 84
`5.2.1
`
`
`
`
`
`
`5.2.2 Mathematics of entropy codingO
`.......... 85
`
`
`
`
`5.2.3 Huffman codingO
`................... 86
`
`
`
`
`
`
`. 5.2.4 Assigning Huffman codesO
`.............. 86
`
`
`
`
`
`5.2.5 Adaptive entropy codingO
`.............. 87
`
`
`
`
`Symbol probabilitiesO ......... . ........ 88
`5.2.6
`
`
`
`
`
`
`
`
`
`5.3 Statistical modelsO
`...................... 88
`
`
`
`
`
`
`
`
`
`
`
`5.4 Coding modelsO ........................ 89
`
`
`
`
`
`
`I—, P—, and B-picturesO
`................ 90
`5.4.1
`
`
`
`
`
`5.4.2 MPEG coding modelsO ................ 90
`
`
`
`
`
`5.4.3 Quantization in MPEG-1O .............. 91
`
`
`
`
`
`
`5.4.4 Coding of I—picturesO
`................. 91
`
`
`
`
`
`
`
`Coding DC coefficients in I—picturesO
`92
`5.4.4.1
`.
`.
`.
`
`
`
`
`
`
`
`5.4.4.2 Coding AC coefficients in I—picturesO
`94
`.
`.
`.
`
`
`
`
`
`
`5.4.5 Coding of P— and B—picturesO
`......... ' .
`99 «‘
`. '.
`.
`
`
`
`
`
`
`
`5.5 Encoder and decoder block diagramsO
`........... 100
`
`
`
`
`5.5.1 Reconstruction moduleO
`............... 100
`
`
`
`
`
`5.5.2 Encoder block diagranfo
`............... 100
`
`
`
`
`
`5.5.3 Decoder block diagramO
`............... 102
`
`
`
`105
`-................. 106
`
`.
`
`
`
`
`
`
`6 Pseudocode and Flowcharts
`
`
`
`
`
`6.1 Pseudocode presentationO
`
`
`
`
`6.2 Flowchart primitivesO
`
`
`
`6.2.1 Decision notationO
`
`
`
`
`. ...... '.
`.
`. .'. .
`.
`.~ ..... 108
`>
`6.2.2 Test notationO
`
`
`
`
`.7 .................... 110
`.
`6.3 Operator notationO
`
`
`
`
`
`................. 111‘
`6.3.1 Branches and loopsO
`
`
`
`
`
`.................. 113
`6.4 Data element proceduresO
`
`.................... 106
`
`.................. 108
`
`
`
`
`
`Page 13 of 498
`
`Page 13 of 498
`
`

`

`>11.
`1
`.
`1
`:21
`1 a1
`1 1'
`1
`11
`
`
`
`111
`.1
`
`‘1
`2.
`
`i
`
`§
`
`11
`1
`1
`1
`1
`‘1
`
`7
`.
`
`11
`
`
`1'
`I
`
`1
`, 1
`,1
`11
`fi 11
`1
`1
`1,
`
`'15!
`__
`-
`
`1
`. 1
`
`1
`
`11'
`
`1
`I1
`_
`1
`3;"
`3
`
`.
`
`'
`
`-
`
`1
`
`
`
`
`
`
`135
`8 MPEG-1 Video Syntax
`
`
`
`
`
`.................. 135
`I 8.1 Video sequence overvieWO
`
`
`
`
`..... 1..................... 137
`8.2 Start codesO
`
`
`
`
`
`8.3 Video sequence layerO
`.................... 138
`
`
`
`
`
`
`8.4 Group of pictures layerO
`...... .............. 145
`
`
`
`
`48.5 Picture layerO
`.
`.
`.
`.‘ ............. 1 ........ 147
`
`
`
`
`
`
`
`.......................... 150
`‘ V
`Slice layerO
`
`...................... 151
`Macroblock layerO
`
`
`
`
`
`
`Skipping macroblocksO
`................ 160
`8.7.1
`
`
`
`
`
`
`.......................... 160
`- 8.8- Block layerO
`
`
`
`
`
`
`
`
`'1 3.8.9 ‘ Summary of data element syntaXO
`............. 165
`
`
`
`
`
`
`81.10 MPEG-1 video data stream example.
`~
`........... 166
`
`
`171
`9- MPEG-2 Overview
`
`
`
`
`
`
`
`
`
`
`9.1 Advantages of MPEG—2 over MPEG-1O ........... 171
`
`
`
`
`9.2 MPEG—2 applicationsO
`.................... 172
`
`
`
`
`
`9.3
`Joint development With ITU—TO
`............... 173
`
`
`
`
`
`9.4 MPEG—2 systemsO
`...... '............ ..... 173
`
`
`
`
`
`
`9.5 Fields, frames, and picturesO ................. 174
`
`
`
`
`9.6 Chrominance samplingO
`.
`.
`.
`. ................ 175
`9.7 Video formatsO
`........................ 175
`
`
`
`
`
`
`
`.......................... 177
`9 .8 ScalabilityO
`
`
`
`
`................... 177
`SNR scalabilityO
`9.8.1
`
`
`
`
`9.8.2 Spatial scalabilityO
`.
`.
`.
`.
`.
`.
`.
`. ......... 178
`
`
`
`
`9.8.3 " Temporal scalabilityO ................. 178
`
`
`
`
`
`............ 178
`9.8.4 Data partitioning extensionO
`
`
`
`9.9 Profiles 0
`............................ 1 78
`
`
`
`
`xvi
`'
`
`
`6.5 NextbitsO procedureO
`.................... 114
`
`
`
`
`
`
`
`
`
`............. 115
`6.6 Encoder versus decoder operationO
`
`
`
`
`6.7 Other low-level proceduresO
`................. 115
`
`
`
`
`
`
`
`
`
`
`117
`7 MPEG System Syntax
`
`
`
`
`.......................... 117
`7.1 Start codesO
`
`
`
`
`7.1.1 Next_start_code() functionO
`............. 117
`
`
`
`
`
`
`7.1.2
`System and video start codeso
`........... 119
`
`
`
`
`
`7.2 System overvieWO
`....................... 119
`7.3
`ISO/IEC 11172 streamo
`.
`.
`.
`'......... 1. ...... 121
`
`
`
`
`
`
`
`
`
`
`7.4 Pack layerO
`.......................... 121
`System headerO
`7.4.1
`.................... 123
`
`
`
`
`
`
`
`
`7.5 Packet layerO
`......................... 127
`
`
`
`
`
`
`7.6 Summary of system data elementsO
`............. 131
`
`
`
`
`
`
`7.7 SCR calculation examples.
`................. 133
`
`.
`
`'1
`
`
`"
`
`
`
`
`
`
`
`
`Page 14 of 498
`
`Page 14 of 498
`
`

`

`xvii
`
`
`
`
`
`
`
`
`9.10 LevelsO ............. ' ................ 179
`
`
`
`
`
`
`
`
`
`
`
`
`
`9.11 Main profile video sequence overviewO
`........... 183
`
`
`
`
`
`
`
`
`9.12 Differences between MPEG—1 and MPEG—2 videoO
`.
`.
`.
`. 185
`
`
`
`
`
`
`
`187
`10 MPEG-2 Main Profile Syntax
`
`
`
`
`
`10.1 MPEG-2 start codesO ..................... 187
`
`
`
`
`
`.................. 189
`10.2 MPEG—2 video sequence.
`
`
`
`
`
`10.2.1 MPEG-2 sequence header.
`............. 189
`
`
`
`
`
`............ 192
`10.2.2 MPEG—2 sequence extension.
`
`
`
`
`
`
`110.2.3 MPEG—2 optional sequence extensions.
`...... 195
`
`
`
`
`
`
`
`
`
`
`
`
`
`10.2.4 MPEG—2 user data.
`...... ............ 196
`
`
`
`
`
`
`10.2.5 MPEG—2 sequence display extension.
`........ 196
`10.3 MPEG—2 GOP header.
`.................... 198
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.......... 202
`10.4 MPEG—2 picture header and extensions.
`
`
`
`
`
`
`10.4.1 MPEG-2 picture coding extension.
`......... 203
`
`
`
`
`
`
`
`
`.
`.
`.
`10.4.2 MPEG-2 picture extensions and user data.
`. 212
`
`
`
`
`
`
`10.4.3 MPEG—2 quant matrix extension.
`......... 212
`
`
`
`
`
`
`10.4.4 MPEG—2 picture display extension.
`......... 213
`
`
`
`
`
`10.4.5 MPEG-2 copyright extension.
`............ 215
`
`
`
`
`
`
`10.4.6 MPEG-2 picture data function.
`........... 215
`
`
`
`
`
`10.5 MPEG—2 slice header.
`................... 216
`
`
`
`
`
`10.6 MPEG-2 macroblock header.
`................ 217
`
`10.6.1 Macroblock modes.
`................. 220
`
`
`
`10.6.2 M’otion vectors. .................... 222
`
`
`
`
`
`
`
`
`
`
`10.6.3 MPEG-2 coded block pattern.
`........... 224
`
`
`
`
`
`
`
`
`
`
`10.7 MPEG-2 block(i) function.
`................. 225
`10.8 MPEG—2 MP@ML and SP@ML additional restrictions.
`. 227
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10.9 MPEG—2 MP@ML video‘ data elements.
`.......... 227
`
`
`
`
`
`237
`11 Motion Compensation
`
`
`
`
`
`
`
`
`............l ..
`.‘ 237
`11.1 Motion in sequences of picturesO
`
`
`
`
`
`
`............. 240
`11.2 Motion compensation in MPEG-1O
`
`
`
`
`
`11.3 P—picture motion—compensated predictionO ......... 241
`
`
`
`
`
`11.4 B~picture motion-compensated predictionO ......... 242
`
`
`
`
`
`11.5 Generic motion displacementsO
`............... 245
`
`
`
`
`
`
`11.6 Displacement principal and residualO
`............ 245
`
`
`
`
`
`
`11.7 Wraparound of motion displacementsO
`........... 248
`
`
`
`
`
`
`
`
`11.8 Coding and decoding of motion vectorsO
`.......... 250
`
`
`
`
`
`11.8.1 Decoding motion displacements O.
`.......... 251
`11.8.2 Forward motion vectorsO ............... 251
`
`
`
`
`
`
`
`
`
`
`11.8.3 Backward motion vectors. ......... ’ ..... 253 ‘
`
`
`
`
`
`
`11.8.4 P- and B-picture motion vectorsO
`.......... 253
`
`
`
`
`
`
`
`
`11.8.5 Calculating displacements for Y and CO
`...... 253
`
`n
`
`I
`
`'
`
`Page 15 of 498
`
`
`
`
`
`‘1
`
`'
`
`:
`"
`'
`
`,
`.‘1
`
`Page 15 of 498
`
`

`

`
`
`Ll
`
`xviii
`
`
`
`
`
`
`
`
`11.9 Strategies for determining motion vectorsO
`
`
`
`
`11.10Motion compensation in MPEG—2O
`...............
`11.10.1 MPEG—2 motion vectors.
`
`
`
`
`..........
`
`
`
`11.10.2MPEG-2 dual—prime prediction.
`
`
`1 1.10.3 Motion-compensated predictions .
`
`
`
`
`
`254
`
`256
`
`256
`
`260
`
`
`
`263
`
`..............
`............
`
`...........
`
`
`
`
`
`12 Pel Reconstruction
`263
`
`
`
`
`
`12.1 Intra—coded block dequantizationo
`265
`
`
`
`
`
`
`
`12.2 DC prediction in intra macroblocksO
`268
`
`
`
`
`
`12.3 Nonintra—coded block dequantizationO
`269
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`12.4 IDCT mismatchO
`.......................
`......
`269
`
`
`
`
`
`
`
`12.4.1 IEEE Standard Specification for IDCTO
`272
`
`
`
`
`
`12.5 Limiting error propagationO
`272
`
`
`
`
`
`12.6 H.261 and H.263 oddificationO
`
`272
`
`
`
`
`
`12.7 MPEG-2 pel reconstructiono .................
`. 274
`
`
`
`
`
`12.7.1 MPEG-2 intra—coded block reconstructionO
`.
`.
`.
`
`. 275
`
`
`
`
`
`12.7.2 MPEG—2 nonintra—coded block reconstructionO
`
`275
`
`
`
`
`
`
`12.8 IDCT mismatch control. ...................
`............
`277
`
`
`
`
`
`
`12.8.1 Review of Katayama’s paper.
`279
`
`
`
`
`
`
`' 12.8.2 Review of Yagasaki’s paper.
`
`................
`
`.
`
`.............
`
`I
`
`
`
`
`
`13 Motion Estimation
`
`284
`
`
`
`
`
`
`
`
`
`
`
`
`................
`3.1 Criterion for block matchingO
`
`
`
`
`
`
`
`
`
`
`
`
`
`286
`1 3.2 The search reference pictureO ‘ ................
`
`286
`
`
`
`
`
`
`
`
`
`
`""133 How large should the search range be? 0
`..........
`
`290
`
`
`
`
`
`
`
`
`
`
`
`' «13.4 Fractional pel searchesO
`...................
`.
`292
`
`
`
`
`
`
`
`' 13.5 Correlation between motion vectorsO
`............
`292
`
`
`
`
`
`
`
`
`13.5.1 Adding chroma to the distortion measureO .....
`295
`
`
`
`
`
`
`
`
`
`
`
`
`13.5.2 Tiebreakingo
`.....................
`296
`
`
`
`
`
`
`
`
`
`
`
`
`13.5.3 Search failureO
`....................
`...........
`297
`
`
`
`
`
`
`
`13.5.4 Search failure at scene changesO
`297
`
`
`
`
`
`
`13.6 Motion displacement search algorithmsO
`300
`
`
`
`
`
`
`
`13.7 Fast algorithms for motion estimationO ...........
`301
`
`
`
`
`
`
`
`
`13.8 A survey of fast search algorithmsO
`.............
`. 304
`
`
`
`
`
`
`
`
`
`13.8.1 Fast search algorithms based on sparse samplingO
`
`
`
`
`
`
`13.8.2 Variable resolutiOn search techniquesO
`304
`
`
`
`
`
`13.8.3 Statistically sparse searchesO
`............
`305
`
`
`
`
`
`
`
`13.8.4 Searches dependent on spatial continuityO
`305
`
`
`
`
`
`
`
`
`
`
`
`
`13.8.5 Telescopic searchO
`..................
`.........
`306
`
`
`
`
`
`13.8.6 3—D (spatial/temporal) estimationO
`
`
`
`
`
`13.8.7 Phase correlation searchO
`..............
`307
`
`
`
`
`
`........... ‘.
`13.8.8 Other search techniquesO
`.
`.
`..307
`
`
`
`
`
`
`
`13.8.9 Improving the motion displacement estimateo
`
`283
`
`304
`
`306
`
`
`
`
`
`
`Page 16 of 498
`
`Page 16 of 498
`
`

`

`
`
`
`
`
`
`
`13.9 Comparison of fast search algorithmsO
`
`
`
`........... 307
`
`
`
`
`
`
`
`
`
`
`
`313
`14 Variable Quantization
`...................... 314
`14.1 Literature reviewO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`14.1.1 Still-picture codingO
`................. 315
`
`
`
`
`
`
`
`
`14.1.2 Masking functions based on spatial derivativeO
`.
`. 315
`
`
`
`
`
`
`
`
`
`
`
`
`14.1.2.1 Spatial derivative errorO .......... 316
`
`
`
`
`
`14.1.2.2 Vertical/horizontal spatial derivativeO
`.
`. 317
`
`
`
`
`
`14.1.2.3 Spatial derivative classificationO
`..... 320
`
`
`
`
`
`
`
`
`14.1.3 Masking functions based on block varianceO
`.
`.
`.
`. 321
`14.1.3.1 Global varianceO
`.............. 321
`
`
`
`
`
`
`
`
`14.1.3.2 Scene complexityO
`...... . ....... 321
`
`............... 322
`14.1.3.3 Bit allocationO
`
`
`
`
`
`
`
`
`14.1.3.4 Coding artifact classificationO .
`.
`.'
`.
`.
`.
`. 322
`
`
`
`
`14.1.3.5 Perceptual qualityO
`............ 322
`
`
`
`
`
`14.1.3.6 Statistical activity classesO ’ ........ 322
`
`
`
`
`
`14.1.4 DCT—based masking functionsO
`........... 323
`
`
`
`
`
`14.1.4.1 AC energyO ................. 323
`
`
`
`
`
`14.1.4.2 Minimax DCT coefiicientO
`........ 323
`
`
`
`
`
`.......... 324
`14.1.4.3 Coefficient energy sumo
`
`
`
`
`
`
`
`14.1.4.4 Macroblock classification using the DCTO
`325
`
`
`
`
`
`
`14.1.5 Overhead in switching quantizenscaleo
`..... 327
`
`
`
`
`
`14.1.6 MPEG-2 Test Model 50
`..... ' .......... 327
`
`
`14.1.7 Coded bitsO
`...................... 328
`
`
`
`
`
`
`
`
`14.2 Perceptual studiesO ...................... 328
`
`
`
`
`
`
`14.3 Variable quantization and motionO
`............. 331
`
`
`
`
`14.3.1 Temporal maskingO .................. 331
`
`
`
`
`
`
`
`14.3.2 Relative motion between adjacent macroblocksO .
`. 331
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`14.4 SummaryO .
`._ ............. ‘ ....... 332
`
`.
`
`.
`
`.
`
`..
`
`.
`
`
`
`
`
`
`
`
`‘
`'
`i 333 "
`15‘ Rate Control in MPEG
`
`
`
`
`
`...................... 333
`15.1 Literature reviewO
`
`
`
`
`
`
`................... 334
`15.1.1 The rate bufferO
`
`
`
`
`
`
`
`15.1.2 p><64 reference model and generalizationsO ..... 334
`
`
`
`
`
`15.1.2.1 S-shaped control characteristicO
`..... 335
`
`
`
`
`
`
`
`15.1.3 MPEG-2 Test Model 50
`- ....... ~ ....... 335
`.
`
`
`
`
`
`
`
`
`15.1.3.1 Rate control with DOT minimax activityO 336
`
`
`
`
`
`
`
`15.1.4 Rate control based on recodingO ’ .......... 336
`
`
`
`
`
`
`15.1.5 VBR rate controlO
`.................. 337
`
`
`
`
`
`
`.
`.
`.
`.
`., .
`.
`. 337
`15.1.6 Recursive prediction withrecodingO
`
`
`
`
`
`15.1.7