Compressed Image File Formats JPEG, PNG, GIF, XBM, BMP Your guide to graphics files on the Web John Miano www.vsofts.net oldroad Compressed Image File Formats www.vsofts.net oldroad Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial capital letters or all capital letters. The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. The publisher offers discounts on this book when ordered in quantity for special sales. For more information, please contact: Corporate, Government, and Special Sales Group Addison Wesley Longman, Inc. One Jacob Way Reading, Massachusetts 01867 Library of Congress Cataloging-in-Publication Data Miano, John, 1961- Compressed image file formats : JPEG, PNG, GIF, XBM, BMP / by John Miano p. cm. Includes bibliographical references. ISBN 0-201-60443-4. — ISBN 0-201-61657-2 (CD-ROM) 1. Image processing—Computer programs. 2. Data compression (Computer science) 3. Computer programming. 4. File organization (Computer science) I. Title TA1637.M53 1999 005.74'6—dc21 99-15179 CIP Copyright © 1999 by the ACM Press, a division of the Association for Computing Machinery, Inc. (ACM). 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, electronic, mechanical, photocopying, recording, or otherwise, without the prior consent of the publisher. Printed in the United States of America. Published simultaneously in Canada. ISBN 0-201-60443-4 Text printed on recycled and acid-free paper. 1 2 3 4 5 6 7 8 9—MA—04 03 02 01 00 99 First printing, July 1999 oldroad Contents Preface ix Acknowledgments xi Chapter 1 Introduction 1 The Representation of Images 1 Vector and Bitmap Graphics 3 Color Models 5 True Color versus Palette 9 Compression 10 Byte and Bit Ordering 13 Color Quantization 16 A Common Image Format 18 Conclusion 21 Chapter 2 Windows BMP 23 Data Ordering 23 File Structure 24 Compression 28 Conclusion 29 Chapter 3 XBM 31 File Format 31 Reading and Writing XBM Files 33 Conclusion 34 Chapter 4 Introduction to JPEG 35 JPEG Compression Modes 36 What Part of JPEG Will Be Covered in This Book? 39 What are JPEG Files? 40 SPIFF File Format 40 Byte Ordering 41 V www.vsofts.net oldroad VI Contents Sampling Frequency 41 JPEG Operation 44 Interleaved and Noninterleaved Scans 45 Conclusion 46 Chapter 5 JPEG File Format 47 Markers 47 Compressed Data 49 Marker Types 49 JFIF Format 55 Conclusion 57 Chapter 6 JPEG Human Coding 61 Usage Frequencies 61 Huffman Coding Example 63 Huffman Coding Using Code Lengths 65 Huffman Coding in JPEG 71 Limiting Code Lengths 72 Decoding Huffman Codes 73 Conclusion 75 Chapter 7 The Discrete Cosine Transform 77 DCT in One Dimension 78 DCT in Two Dimensions 84 Basic Matrix Operations 85 Using the 2-D Forward DCT 87 Quantization 88 Zigzag Ordering 89 Conclusion 90 Chapter 8 Decoding Sequential-Mode JPEG Images 91 MCU Dimensions 91 Decoding Data Units 94 Decoding Example 97 Processing DCT Coefficients 98 Up-Sampling 99 Restart Marker Processing 99 Overview of JPEG Decoding 100 Conclusion 100 Chapter 9 Creating Sequential JPEG Files 105 Compression Parameters 105 Output File Structure 111 Doing the Encoding 111 Down-Sampling 112 Interleaving 113 Data Unit Encoding 115 Huffman Table Generation 117 Conclusion 119 www.vsofts.net oldroad Contents VII Chapter 10 Optimizing the DCT 121 Factoring the DCT Matrix 121 Scaled Integer Arithmetic 137 Merging Quantization and the DCT 138 Conclusion 148 Chapter 11 Progressive JPEG 149 Component Division in Progressive JPEG 149 Processing Progressive JPEG Files 151 Processing Progressive Scans 152 MCUs in Progressive Scans 153 Huffman Tables in Progressive Scans 153 Data Unit Decoding 154 Preparing to Create Progressive JPEG Files 160 Encoding Progressive Scans 162 Huffman Coding 162 Data Unit Encoding 162 Conclusion 169 Chapter 12 GIF 171 Byte Ordering 172 File Structure 172 Interlacing 178 Compressed Data Format 178 Animated GIF 186 Legal Problems 187 Uncompressed GIF 188 Conclusion 188 Chapter 13 PNG 189 History 190 Byte Ordering 190 File Format 190 File Organization 195 Color Representation in PNG 195 Device-Independent Color 197 Gamma 201 Interlacing 202 Critical Chunks 203 Noncritical Chunks 206 Conclusion 212 Chapter 14 Decompressing PNG Image Data 215 Decompressing the Image Data 215 Huffman Coding in Deflate 221 Compressed Data Format 222 Compressed Data Blocks 223 Writing the Decompressed Data to the Image 227 Conclusion 231 www.vsofts.net viii Contents Chapter 15 Creating PNG Files 233 Overview 233 Deflate Compression Process 234 Huffman Table Generation 238 Filtering 241 Conclusion 243 Glossary 245 Bibliography 249 Index 253 www.vsofts.net oldroad Preface The purpose of this book is to instruct the reader on how to write software that can read and write files using various 2-D image formats. I wanted to write a book that explains the most frequently used file formats with enough depth for the reader to implement them, as opposed to one that covered many different for- mats at a high level or one that avoided the more difficult image formats. As a result, I chose to cover the image file formats that are associated with Web browsers. Those covered in this book (BMP, XBM, JPEG, GIF, and PNG) repre- sent the vast majority of image files that can be found on the Internet. They employ a wide range of encoding techniques and range in implementation diffi- culty from simple to very complex. The inspiration for this book was my own frustration resulting from the lack of information on how to implement encoders and decoders for the more com- plex file formats. Most of the information available was at too high a level, left major gaps, or was very difficult to decipher. I have tried to create a bridge between the programmer and the standards documents. One issue I faced at the start of this project was which programming lan- guage to use for the examples. The intention was to create a book on graphics file formats rather than one on how to write programs to read and write graph- ics files in a particular language. Therefore, I debated using a language that is easy to read (e.g., Pascal or Ada) or the one most people are likely to use (C++). In the end I felt that its widespread use made C++ the best choice. To make the examples more understandable for non-C++ programmers, I have carefully avoided certain C++ language constructs (e.g., expressions with side effects and integer/boolean interchangeability) that would make the code difficult for them to understand. IX www.vsofts.net oldroad x Preface In order to make the encoding and decoding processes as clear as possible, I have used a Pascal-like pseudo-code. C++ is used for complete function implementations and pseudo-code for illustrative fragments. These fragments generally contain no error checking. Because of their generally large size, it was not possible to include work- ing source code for the formats in the book itself. Instead, the accompanying CD-ROM contains the complete source code for encoders and decoders for almost all of the image formats covered.1 The reader should use the pseudo- code in the text to learn how processes work and the C++ examples on the CD to see how to implement them. Generally, the decoders implement more features than to the encoders. In the decoders I have implemented all of the features needed to decode files that a reader will have any likelihood of encountering on the Internet. For the sake of clarity, the encoders generally implement a smaller feature subset. In writing the programming examples I have given clarity precedence over execution efficiency and instant portability. The source examples will compile, without modifications, on Microsoft Windows using both Borland C++Builder V3.0 and Microsoft Visual C++ V5.0. Other compilers generally require some modifications to the code. The descriptions of the encoders and decoders for the various file for- mats frequently employ the term "user" to describe the source of certain input parameters to the encoding or decoding process. By this I mean the user of the encoder or decoder, not necessarily the person typing at the keyboard. Since image encoders and decoders are incorporated into other applications, such as image viewers and editors, the user in this case would most likely be another piece of software. However, in many situations the "user" application may get some of these parameters directly from a human. Just as this is not intended to be a book on C++ programming, it is also not intended to be a book on programming in a specific environment. For that information readers will need a book for their particular system. 1The unfortunate exception is GIF because of legal issues. www.vsofts.net oldroad Acknowledgments A project as large as producing a book requires the involvement of many peo- ple. Mike Bailey, Eric Haines, Tom Lane, Shawn Neely, and Glenn Randers- Pehrson reviewed the manuscript and provided many invaluable suggestions. Glenn also arranged for me to get the latest proposed PNG standards for the CD. My fellow aviator, Charlie Baumann, was kind enough to provide sev- eral of the photographs. Ralph Miano and Margaret Miano assisted with preparing the manuscript. Jean-Loup Gailley answered all my questions on ZLIB. Albert "The Chipster" Copper compiled examples on systems I did not have access to. Most important, Helen Goldstein at AWL guided the process from start to finish. John M. Miano Summit, New Jersey miano@colosseumbuilders. com XI www.vsofts.net oldroad