REAL-TIME
`VIDEO
`COMPRESSION
`Techniques and Algorithms
`
`Hammond Wean der
`itorkrb Furht
`
`Comcast - Exhibit 1009, page 1
`
`

`

`Page i
`Page i
`
`Real-Time Video Compression
`Real-Time Video Compression
`
`
`
`Comcast - Exhibit 1009, page 2
`
`

`

`Page ii
`
`TEM ICLDIVERDOWONAL BRADS
`THE KLUWER INTERNATIONAL SERIES
`IN RAGDIEDDING AND cam:arrest WIDER
`IN ENGINEERING AND COMPUTER SCIENCE
`
`MULTIMEDIA SYSTEMS AND APPLICATIONS
`MULTDCEDIASYSTEMS AND APPLICArA7N9
`
`Commiagatir
`Consulting Editor
`
`X17iO3 RAM
`Borko Furht
`;Turbo MIcislc Ilikwyrtiy
`Florida Atlantic University
`
`Earn* /14614441714444
`Recently Published Titles:
`
`VIDEO AND IMAGE PROCESSING IN MULTIMEDIA SYSTEMS, by
`VIDEO AND MACE P3113CEJESD4C D7 5137LITMEDIA131812113. by
`Borko Furht, Stephen W. Smoliar, HongJiang Zhang
`Bodco P041:4, Stereo W. Scuola; Noogrion VAN
`ISBN: 0-7923-9604-9
`ISBN 0-7923-9604-9
`
`MULTIMEDIA SYSTEMS AND TECHNIQUES, edited by Borko Furht
`51:01.TDORIIIA 811311043 AND TECHNIQ0154. eclizad by Bodco Arbt
`ISBN: 0-7923-9683-9
`ISBN 0-7923-96E3-9
`
`MULTIMEDIA TOOLS AND APPLICATIONS, edited by Borko Furht
`MULTIMEDIA TO018 AND APPLICATIONS eclItal by Borto RIAU
`ISBN: 0-7923-9721-5
`ISBN 0-7923-9721-5
`
`MULTIMEDIA DATABASE MANAGEMENT SYSTEMS, by B. Prabhakaran
`MULTIKED It DAMME?. MANAGEMENT 13115130115. by & Pabbleno
`ISBN: 0-7923-9784-3
`ISM 0-7923-97E4-3
`
`r.
`
`4
`
`vs
`
`MULTIMEDIA SYSTEMS AND APPLICATIONS
`Advanced Book Series
`
`‘Ct
`
`
`
`Comcast - Exhibit 1009, page 3
`
`

`

`Page iii
`Page iii
`
`Real-Time Video Compression
`Real-Time Video Compression
`
`Techniques and Algorithms
`Techniques and Algorithms
`
`by
`by
`
`Raymond Westwater
`Raymond Westwater
`Borko Furht
`Borko Furht
`
`Florida Atlantic University
`Florida Atlantic University
`
`KLUWER ACADEMIC FLIBLk511-1ERS
`Boston / Dordrecht I London
`
`
`
`Comcast - Exhibit 1009, page 4
`
`

`

`Page iv
`Page iv
`
`Distributors for North America:
`Distributors for North America:
`Kluwer Academic Publishers
`Kluwer Academic Publishers
`101 Philip Drive
`101 Philip Drive
`Assinippi Park
`Assinippi Park
`Norwell, Massachusetts 02061 USA
`Norwell, Massachusetts 02061 USA
`
`Distributors for all other countries:
`Distributors for all other countries:
`Kluwer Academic Publishers Group
`Kluwer Academic Publishers Group
`Distribution Centre
`Distribution Centre
`Post Office Box 322
`Post Office Box 322
`3300 AH Dordrecht, THE NETHERLANDS
`3300 AH Dordrecht, THE NETHERLANDS
`
`Library of Congress Cataloging-in-Publication Data
`Library of Congress Cataloging-in-Publication Data
`
`A C.I.P. Catalogue record for this book is available
`A C.I.P. Catalogue record for this book is available
`from the Library of Congress.
`from the Library of Congress.
`
`Copyright © 1997 by Kluwer Academic Publishers
`Copyright © 1997 by Kluwer Academic Publishers
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or
`transmitted in any form or by any means, mechanical, photocopying, recording, or otherwise, without
`transmitted in any form or by any means, mechanical, photocopying, recording, or otherwise, without
`the prior written permission of the publisher, Kluwer Academic Publishers, 101 Philip Drive,
`the prior written permission of the publisher, Kluwer Academic Publishers, 101 Philip Drive,
`Assinippi Park, Norwell, Massachusetts 02061
`Assinippi Park, Norwell, Massachusetts 02061
`
`Printed on acid-free paper.
`Printed on acid free paper.
`
`Printed in the United States of America
`Printed in the United States of America
`
`
`
`Comcast - Exhibit 1009, page 5
`
`

`

`Contents
`Contents
`
`Preface
`Preface
`
`1. The Problem of Video Compression
`1. The Problem of Video Compression
`
`1.1 Overview of Video Compression Techniques
`1.1 Overview of Video Compression Techniques
`
`1.2 Applications of Compressed Video
`1.2 Applications of Compressed Video
`
`1.3 Image and Video Formats
`1.3 Image and Video Formats
`
`1.4 Overview of the Book
`1.4 Overview of the Book
`
`2. The MPEG Video Compression Standard
`2. The MPEG Video Compression Standard
`
`2.1 MPEG Encoder and Decoder
`2.1 MPEG Encoder and Decoder
`
`2.2 MPEG Data Stream
`2.2 MPEG Data Stream
`
`3. The H.261/H.263 Compression Standard for Video Telecommunications
`3. The H.261/H.263 Compression Standard for Video Telecommunications
`
`3.1 Picture Formats for H.261/H.263 Video Codecs
`3.1 Picture Formats for H.261/H.263 Video Codecs
`
`3.2 H.261/H.263 Video Encoder
`3.2 H.261/H.263 Video Encoder
`
`3.3 H.261/H.263 Video Decoder
`3.3 H.261/H.263 Video Decoder
`
`4. The XYZ Video Compression Algorithm
`4. The XYZ Video Compression Algorithm
`
`4.1 XYZ Compression Algorithm
`4.1 XYZ Compression Algorithm
`
`4.2 XYZ Decompression Algorithm
`4.2 XYZ Decompression Algorithm
`
`5. The Discrete Cosine Transform
`5. The Discrete Cosine Transform
`
`5.1 Behavior of the DCT
`5.1 Behavior of the DCT
`
`5.2 Fast One-dimensional DCT Algorithms
`5.2 Fast One-dimensional DCT Algorithms
`
`5.3 Two-dimensional DCT Algorithms
`5.3 Two-dimensional DCT Algorithms
`
`5.4 Inverse DCT Algorithms
`5.4 Inverse DCT Algorithms
`
`
`
`Page v
`Page v
`
`vii
`vii
`
`1
`1
`
`3
`3
`
`6
`6
`
`8
`8
`
`12
`12
`
`15
`15
`
`15
`15
`
`18
`18
`
`23
`23
`
`24
`24
`
`25
`25
`
`28
`28
`
`29
`29
`
`29
`29
`
`32
`32
`
`37
`37
`
`37
`37
`
`40
`40
`
`47
`47
`
`50
`50
`
`Comcast - Exhibit 1009, page 6
`
`

`

`5.5 Three-dimensional DCT Algorithms
`5.5 Three-dimensional DCT Algorithms
`
`6. Quantization
`6. Quantization
`
`6.1 Defining an Invariant Measure of Error
`6.1 Defining an Invariant Measure of Error
`
`6.2 Calculation of Transform Variances
`6.2 Calculation of Transform Variances
`
`6.3 Generating Quantizer Factors
`6.3 Generating Quantizer Factors
`
`6.4 Adding Human Visual Factors
`6.4 Adding Human Visual Factors
`
`7. Entropy Coding
`7. Entropy Coding
`
`7.1 Huffman Coding
`7.1 Huffman Coding
`
`7.2 Use of Entropy Coding in JPEG and MPEG
`7.2 Use of Entropy Coding in JPEG and MPEG
`
`7.3 Adaptive Huffman Coding
`7.3 Adaptive Huffman Coding
`
`8. VLSI Architectures of the XYZ Video Codec
`8. VLSI Architectures of the XYZ Video Codec
`
`8.1 Complexity of the Video Compression Algorithms
`8.1 Complexity of the Video Compression Algorithms
`
`8.2 From Algorithms to VLSI Architectures
`8.2 From Algorithms to VLSI Architectures
`
`8.3 Classification of Video Codec VLSI Architectures
`8.3 Classification of Video Codec VLSI Architectures
`
`8.4 Implementation of the XYZ Video Compression Algorithm
`8.4 Implementation of the XYZ Video Compression Algorithm
`
`8.5 Adaptive XYZ Codec Using Mesh Architecture
`8.5 Adaptive XYZ Codec Using Mesh Architecture
`
`8.6 XYZ Codec Based on Fast 3D DCT Coprocessor
`8.6 XYZ Codec Based on Fast 3D DCT Coprocessor
`
`9. Experimental Results Using XYZ Compression
`9. Experimental Results Using XYZ Compression
`
`9.1 PC Implementation
`9.1 PC Implementation
`
`9.2 MasPar Implementation
`9.2 MasPar Implementation
`
`9.3 Non-adaptive XYZ Compression
`9.3 Non-adaptive XYZ Compression
`
`10. Conclusion
`10. Conclusion
`
`Bibliography
`Bibliography
`
`Index
`Index
`
`
`
`Page vi
`Page vi
`
`51
`51
`
`57
`57
`
`58
`58
`
`62
`62
`
`65
`65
`
`67
`67
`
`73
`73
`
`73
`73
`
`76
`76
`
`78
`78
`
`83
`83
`
`83
`83
`
`86
`86
`
`87
`87
`
`90
`90
`
`103
`103
`
`111
`111
`
`123
`123
`
`124
`124
`
`138
`138
`
`144
`144
`
`151
`151
`
`155
`155
`
`163
`163
`
`Comcast - Exhibit 1009, page 7
`
`

`

`Page vii
`Page vii
`
`Preface
`Preface
`
`This book is on real-time video compression. Specifically, the book introduces the XYZ video
`This book is on real-time video compression. Specifically, the book introduces the XYZ video
`compression technique, that operates in three dimensions, eliminating the overhead of motion
`compression technique, that operates in three dimensions, eliminating the overhead of motion
`estimation. First, video compression standards, MPEG and H.261/H.263, are described. They both
`estimation. First, video compression standards, MPEG and H.261/H.263, are described. They both
`use asymmetric compression algorithms, based on motion estimation. Their encoders are much more
`use asymmetric compression algorithms, based on motion estimation. Their encoders are much more
`complex than decoders. The XYZ technique uses a symmetric algorithm, based on the Three-
`complex than decoders. The XYZ technique uses a symmetric algorithm, based on the Three-
`Dimensional Discrete Cosine Transform (3D-DCT). 3D-DCT was originally suggested for
`Dimensional Discrete Cosine Transform (3D-DCT). 3D-DCT was originally suggested for
`compression about twenty years ago, however at that time the computational complexity of the
`compression about twenty years ago, however at that time the computational complexity of the
`algorithm was to high, it required large buffer memory, and was not as effective as motion
`algorithm was to high, it required large buffer memory, and was not as effective as motion
`estimation. We have resurrected the 3D-DCT based video compression algorithm by developing
`estimation. We have resurrected the 3D-DCT based video compression algorithm by developing
`several enhancements to the original algorithm. These enhancements made the algorithm feasible for
`several enhancements to the original algorithm. These enhancements made the algorithm feasible for
`real-time video compression in applications such as video-on-demand, interactive multimedia, and
`real-time video compression in applications such as video-on-demand, interactive multimedia, and
`videoconferencing. The demonstrated results, presented in the book, suggest that the XYZ video
`videoconferencing. The demonstrated results, presented in the book, suggest that the XYZ video
`compression technique is not only a fast algorithm, but also provides superior compression ratios and
`compression technique is not only a fast algorithm, but also provides superior compression ratios and
`high quality of the video compared to existing standard techniques, such as MPEG and H.261/H.263.
`high quality of the video compared to existing standard techniques, such as MPEG and H.261/H.263.
`The elegance of the XYZ technique is in its simplicity, which leads to inexpensive VLSI
`The elegance of the XYZ technique is in its simplicity, which leads to inexpensive VLSI
`implementation of a XYZ codec.
`implementation of a XYZ codec.
`
`We would like to thank Jim Prince for conducting experiments in developing visually weighted
`We would like to thank Jim Prince for conducting experiments in developing visually weighted
`quantizers for the XYZ algorithm, as well as a number of students from Florida Atlantic University,
`quantizers for the XYZ algorithm, as well as a number of students from Florida Atlantic University,
`who participated in these experiments. We also want to thank Drs. Roy Levow, K. Genesan, and
`who participated in these experiments. We also want to thank Drs. Roy Levow, K. Genesan, and
`Matthew Evett, professors from Florida Atlantic University, Dr. Steve Rosenbaum from Cylex
`Matthew Evett, professors from Florida Atlantic University, Dr. Steve Rosenbaum from Cylex
`Systems, and Joshua Greenberg for constructive discussions during this project.
`Systems, and Joshua Greenberg for constructive discussions during this project.
`
`RAYMOND WESTWATER AND BORKO FURHT
`RAYMOND WESTWATER AND BORKO FURHT
`BOCA RATON, JULY 1996.
`BOCA RATON, JULY 1996.
`
`
`
`Comcast - Exhibit 1009, page 8
`
`