1
`
`Google Inc.
`GOOG 1027
`IPR of US Pat. No. 7,974,339
`
`

`
`
`
`DATA AND IMAGE
`
`COMPRESSION
`
`Tools and Techniques
`
`FOLE|'lZh Eclitien
`
`
`
`Gilbert Held
`
`4-Degree Consulting,
`Macon, Georgia, USA
`
`and
`
`Thomas R. Marshall
`
`(Software Author, Second
`and Third Editions)
`
`JOHN WILEY & SONS LTD
`Chichester » New York - Brisbane - Toronto - Singapore
`
`2
`
`2
`
`

`
`11
`
`Copyright © 1996 by John Wiley & Sons Ltd.
`Baffins Lane, Chichester
`West Sussex P0 19 IUD. England
`
`All rights reserved.
`
`No part of this book may be reproduced by any means,
`or transmitted, or translated into a machine language
`without the written permission of the publisher.
`
`Other Wiley Editorial Qtfzces
`
`John Wiley 8: Sons, Inc., 605 Third Avenue,
`New York. NY 10158-0012, USA
`
`Jacaranda Wiley Ltd. G.P.O. Box 859, Brisbane,
`Queensland 4001, Australia
`
`John Wiley 8: Sons [Canada] Ltd, 22 Worcester Road,
`Rexdale, Ontario M9W 1L1, Canada
`
`John Wiley & Sons (SEA) Pte Ltd, 2 Clementi Loop #02-01,
`Jin Xirgg Distripark, Singapore 0512
`
`Library of Congress Cataloging-in-Publication Data:
`Held, Gilbert. 1943-
`Data and image compression : tools and techniques / Gilbert Held
`and Thomas R. Marshall — 4th ed.
`p.
`cm.
`Previous eds. pub. under title: Data compression.
`includes bibliographical references and index.
`ISBN 0 471 952478 (alk. paper)
`2. Image processing-
`1. Data compression (Computer science)
`Digital techniques.
`1. Marshall, Thomas (Thomas R.)
`11. Held,
`Gilbert, 1943- Data compression.
`III. Title.
`QA76.9.D33H473
`1996
`0O5.74'6—dc2O
`
`95-4196 1CIP
`
`British Library Cataloguing in Publication Data
`A catalogue record for this book is available from the British Library
`ISBN 0 471 95247 8
`
`Typeset by Photo-graphics, Honiton, Devon
`Printed in Great Britain by Bookcraft (Bath) Ltd
`
`3
`
`34
`
`
`
`

`
`
`
`
`
`CONTENTS
`
`Preface
`Acknowledgements
`
`1 Rationale and Utilization
`1.1 Logical compression
`1.2 Physical compression
`1.3 Compression benefits
`1.4 Terminology
`Compression efficiency
`Compression methods
`1.5 Communications applications
`1.6 Data storage applications
`1.7 Other applications
`1.8 Data compression and information transfer
`BISYNC communications
`
`2 Data Codes and Compression-indicating Characters
`2.1 Data codes
`Boudot code
`BCD and EBCDIC codes
`The ASCII code
`2.2 Selecting compression—indicating characters
`Logical compression—indicating characters
`Physical compression-indicating characters
`
`3 Ciharacter-oriented Compression Techniques
`3.1 Null suppression
`Technique overview
`Programming examples
`File naming conventions
`Compression program
`Decompression program
`Technique Variations
`
`xi
`xiii
`
`1
`2
`3
`4
`5
`6
`7
`12
`16
`17
`18
`19
`
`34
`35
`35
`35
`39
`39
`41
`43
`
`47
`48
`48
`50
`50
`52
`53
`59
`
`4
`4
`.
`
`

`
`vi
`
`CONTENTS
`
`cc
`
`'1»
`
`3.2 Bit mapping
`Encoding process
`Hardware considerations
`
`Suppression efficiency
`Bitmap variations
`Technique constraints
`3.3 Run length
`Operation
`Encoding process
`Decoding
`Utilization
`
`Programming examples
`Decompression
`3.4 Half—byte packing
`Encoding format and technique efficiency
`Encoding process
`Decoding
`Programming examples
`Encoding
`Decompression
`Extended ha1f—byte
`BASIC compression program
`BASIC decompression program
`Encoding variations and efficiency considerations
`3.5 Diatomic encoding
`Operation
`Air frequency of occurrence
`Communications hardware implementation
`Programming examples
`Decompression
`Encoding considerations
`3.6 Byte pair encoding
`Expansion
`Efficiency
`3.7 Pattern substitution
`
`The pattern table
`Encoding process
`Patterns in programming Languages
`3.8 Forms—mode operation
`Transmission
`Modified forms-mode method
`
`4 Statistical Encoding
`4.1 Information theory
`Entropy examples
`4.2 Huffman coding
`Prefix property of code
`Code construction considerations
`
`Information requirements
`HUFF1.C
`
`60
`60
`61
`
`61
`65
`66
`68
`68
`69
`7 1
`72
`
`77
`83
`90
`92
`96
`99
`99
`100
`107
`109
`109
`1 18
`125
`128
`128
`129
`133
`137
`143
`148
`150
`156
`157
`157
`
`159
`1 59
`161
`163
`165
`167
`
`170
`170
`173
`176
`176
`181
`
`184
`186
`
`5
`
`5
`
`

`
`CONTENTS
`
`DHUFF.C
`4.3 Shannon—Fa_no coding
`Code ambiguity
`Efficiency comparison
`4.4 Comma codes
`4.5 Arithmetic coding
`Overview
`Operation
`Decoding
`Computer models
`4.6 Adaptive compression
`The fixed compression table
`Adaptive compression
`Coded example
`Sixpack program
`Finite window compression
`Circular buffer array
`Hash table
`Doubly linked lists
`Adoptive Huffman coding
`Bit packing
`4.7 MNP compression
`MNP Class 5
`MNP Class 7 enhanced data compression
`
`5 Facsimile Compression
`5.1 Group 3 fax operational overview
`5.2 Relative encoding
`Telemetry compression
`Facsimile techniques
`5.3 Modified Huffman codes
`5.4 Modified read coding
`
`6 Dictionary Based String Compression
`6.1 String compression efficiencies
`6.2 LZ77 compression
`Encoding
`Decoding
`Coding problems
`6.3 LZSS compression
`LZSS modifications
`6.4 LZ78 compression
`Operation
`Coding tradeoffs
`6.5 LZW compression
`Operation
`Decoding
`Implementation issues
`
`vii
`
`194
`195
`200
`201
`206
`208
`209
`209
`214
`214
`217
`218
`222
`224
`229
`230
`231
`231
`231
`240
`241
`241
`241
`245
`
`248
`248
`250
`250
`252
`255
`259
`
`265
`266
`269
`269
`270
`272
`272
`273
`274
`274
`275
`280
`280
`282
`283
`
`6
`
`6
`
`

`
`viii
`
`CONTENTS
`
`6.6 BTLZ (V.42 bis) compression
`Dictionary pruning
`Decoding algorithm
`Cofiguration and negotiation parameters
`Efficiency limitations
`LZ Variations
`6.7 Multilevel coding and other efficienoy improvements
`LZH compression
`The AR archive program
`LZARI compression
`
`7 Image Compression
`7.1 Graphics overview
`Raster programs
`Vector programs
`Value of image compression
`7.2 Image compression techniques
`Character based
`Statistical
`Dictionary based coding
`Binary graphics
`Predictive coding
`Adaptive Bilevel Image Compression
`JPEG
`
`Object model
`Pattern matching
`Fractal coding
`7.3 GIF file formats
`GIF Signature
`Screen Descriptor
`Global Color Map
`Image Descriptor
`Local Color Map/Table
`Raster Data
`
`LZW algorithm
`GIF89 extensions
`
`Proposed GIF speficication modules
`7.4 JPEG file formats
`
`7.5 Image tools
`GIF coding
`JPEG4.ZIP
`
`GIF2JPG/JPG2GIF
`Image Alchemy
`PRINTGF
`
`8 Communications Software-linkage Considerations
`8.1 Compression routine placement
`Software considerations
`
`284
`287
`288
`288
`289
`289
`290
`290
`291
`292
`
`311
`312
`312
`312
`313
`314
`314
`315
`315
`316
`316
`316
`317
`
`318
`318
`319
`319
`320
`321
`322
`323
`324
`324
`
`324
`326
`
`327
`330
`
`331
`331
`338
`
`341
`342
`343
`
`344
`344
`345
`
`7
`
`7:
`
`
`
`

`
`CONTENTS
`
`8.2 Timing considerations
`Total time
`Flow control
`Routine linkage
`
`9 Compression-perfonning Hardware and Software Product
`Overview
`9.1 Hardware products
`Asynchronous data compressors
`V.42 bis modems
`Synchronous data compressors
`Compression DSU
`The Time Machine
`Multifunctional compression devices
`9.2 Software products
`Teleprocessing monitor compression products
`Database compression
`Personal computer file compression
`Archive utility programs
`
`APPENDIX A DATANALYSIS Program Descriptions and
`Listings
`A.1 FORTRAN program: operational description
`A.2 Main routine
`A.3 Program transferability
`A.4 Variable assignments
`A.5 BASIC program: operational description
`A.6 Main routine
`A.7 Variable assignments
`A.8 FORTRAN DATANALYSIS program listing
`A.9 BASIC language DATANALYSIS program listing
`
`B SHRINK Program Descriptions and
`
`Listings
`B. 1 MERGEC.BAS and MERGED.BAS
`52 Program operations
`
`References
`Further Reading
`Index
`
`8
`
`ix
`
`348
`349
`350
`351
`
`352
`353
`353
`356
`356
`357
`358
`358
`362
`360
`364
`366
`366
`
`389
`389
`389
`393
`394
`395
`397
`400
`401
`410
`
`417
`417
`424
`
`427
`429
`432
`
`

`
`7 I
`
`MAGE COMPRESSION
`
`
`
`New versions ofWord _Perfect, Microsoft’s Word, and a number of elec-
`tronic spreadsheet and database programs routinely provide the
`capability to integrate images into a variety of application programs.
`Although this is a relatively recent phenomenon, in actuality the use
`of images as well as the application of compression techniques to
`reduce the data storage and transmission requirements of images is
`far from being a recent phenomenon.
`In Chapter 5 we examined the use of modified Huffman coding to
`compress fax transmission. Since fax represents images and the use
`of modified Huffman coding is over 20 years old, this technique can
`be considered as one of the earliest applications of compression to
`images. If you ever used a TIFF file or downloaded a GIF file from a
`bulletin board, you experienced the use of image compression.
`Although data compression produces image compression, we will use
`the term image compression to denote data compression techniques
`specifically applied to images. Such techniques can include lossless
`as well as lossy compression techniques, with an example of the for-
`mer being an image stored using the GIF specification, while an exam-
`ple of the latter can be an image stored using the JPEG specifications.
`Since a discussion of image compression requires an understand-
`ing of graphic images and how they are stored, we will first focus our
`attention upon this area to obtain an overview of image storage
`requirements. Next, we will take a short tour of image compression
`techniques. This tour will provide us with additional infofination con-
`cerning the application of a variety of compression techniques to the
`compression of images. This will be followed by an examination of
`several specific graphic file formats as well as compression tech-
`niques supported by each graphic file format. In concluding this
`chapter, we will focus our attention upon a few tools that can assist
`us ir1 either developing graphic files or converting images from one
`graphic format to another.
`
`9
`
`
`

`
`312
`
`IMAGE COMPRESSION
`
`7.1 GRAPHICS OVERVIEW
`
`Graphic file formats are based upon the method by which graphic
`programs create, store and display images. Graphic programs and
`their resulting file formats can be subdivided into one of two categor-
`ies—raster and Vector.
`
`Raster programs
`
`A raster format program works with a series of picture elements,
`referred to as pels or pixels, and the resulting file format is commonly
`referred to as bitmapped. A raster format program divides the image
`area into very small points, typically 1/300 of an inch square, and
`stores the data for each point. Thus, one square inch at a resolution
`of 300 dots per inch (dpi) would require 90000 points.
`Each point in a bitmapped or raster image can have two or more
`states. If the image is black-and-white, each point can be represented
`by one bit. If the image is gray scale or color, two or more bits will be
`required to represent each point.
`Common gray scale images have either 16 or 256 shades of gray,
`requiring either four or eight bits to represent the possible gray shad-
`ing of each point. Color images can range from 16 colors, or four bits
`per point, up to 16.7 million colors, requiring 24 bits per point.
`The number of bits used to represent the gray scale or color of a
`point
`commonly referred to as the color depth of an image.
`Although more than 24 bits can be used to represent the color of each
`point, that is a practical maximum as any range of colors beyond that
`afforded by the use of 24 bits normally cannot be detected by the
`human eye.
`
`Vector programs
`
`A second type of graphic image program and resulting file format are
`vector programs which produce vector files. A vector graphics pro-
`gram generates shapes that are made up of line segments. Examples
`of vector graphics programs include computer aided design (CAD) and
`map generation and manipulations programs.
`
`Raster versus vector
`
`Raster images are shape independent and permit the input, manipu-
`lation and output of images that would be difficult, if not impossible,
`when using a vector image program. For this reason scanners, digital
`cameras and digitizer pads provide bitmapped or raster image input.
`
`10
`10
`
`‘
`
`

`
`7.1 GRAPHICS OVERVIEW
`
`313
`
`The output of raster image programs can be accomplished easier and
`faster to a computer monitor or graphics printer than a vector image
`program since no vector to raster conversion is necessary. In this
`chapter we will focus our attention upon raster images.
`
`Value of image compression
`
`To obtain an appreciation for the value of image compression, con-
`sider the storage requirements of a 3" x 5"co1or picture scanned using
`a scanner capable of recognizing 256 colors at 300 dpi.
`3”x 5"
`color picture consists of 15 square inches, with 90 000 points per
`inch. Thus, 90000 x 15 or 1 350000 bits are required to represent
`the picture without considering its color depth. Since eight bits (or
`one byte) are required to obtain a color depth of 256, this results in a
`minimum data storage requirement of 1.35 Mbytes for the previously
`mentioned 3'’ x 5" color image. The reason the term ‘minimum’ was
`used is that the image file must contain a heading which enables the
`program to denote the type of image stored as well as information
`about its size, resolution, and color depth. Thus, the actual file would
`require a few additional bytes of storage, although additional storage
`would be relatively small in comparison to the total amount of storage
`required. Without compression we are
`able to store one 3" x 5"
`image on a 1.44 Mbyte 3% inch diskette. If you are fortunate enough
`to have a 200 Mbyte hard drive, the storage of less than 150 3" x 5"
`images would require the entire storage capacity of your drive. Simi-
`larly, the transmission time required to send or receive non-com-
`pressed images can be lengthy. For example, at 9600 bps (1200
`characters or bytes per second) the 3" x 5" color image would require
`1125 seconds or over 18 minutes to transmit or receive. For these
`
`reasons, compression can be considered as a necessity when working
`with images. Fortunately, the file formats associated with many popu-
`lar graphic images define the use of one or more types of compression
`which permit many types of images to be stored and transmitted in
`a compressed form.
`Table 7.1 lists nine popular types of image files, their file extension
`and color support. Readers should note that the documentation that
`provides a detailed overview of each of the image file formats listed in
`Table 7.1 cumulatively exceeds the page count of many comprehen-
`sive dictionaries. Thus, it should come as no surprise that We will
`limit our exarninaéon of image file formats to those formats that sup-
`port compression and are primarily used to transport images between
`computers. Similarly, our description and review of image com-
`pression tools will be limited to those that work with the image for-
`mats We will examine in detail.
`
`I
`
`11
`ll
`
`

`
`314 IMAGE COMPRESSION
`
`Table 7.1
`
`Popular image file formats
`
`Description
`
`File extension
`
`Colors
`
`OS/2 bit map
`Windows bit map
`Windows Clipboard
`Paint Brush
`GEM environment
`Dr. Halo
`
`Graphics Interchange Format
`Tag Image File Format
`Joint Photographic Experts Group
`
`BMP
`
`CLF’
`PCX/PCC
`IMG
`PIC
`
`GIF
`TIF
`JPG
`
`B&W/Color
`B&W/Color
`B&W/Co!or
`B&W/Color
`B&W/Color
`Color
`
`B&W/Grayscale/Color
`B&W/Grayscale/Color
`Grayscale/Color
`
`Table 7.2
`
`Image coiaipression techniques
`
`Lossless
`Character based
`
`Statistical/entropy
`Dictionary based
`
`Lossy
`Binary graphics
`Object model
`
`7.2 HVIAGE COEEPRESSION TECHNIQUES
`
`A wide variety of compression techniques have been developed over
`the past 20 years to reduce the size of bitmapped image files. Some
`techniques represent the application of modified lossless compression
`algorithms, While other techniques represent
`the application of
`lossy algorithms.
`We can classify image compression techniques into a minimum of
`five general categories which are listed in Table 7.2. Readers should
`note that this classification scheme represents the views of the author
`of this book and other classification schemes can be developed to
`group compression techniques applied to images. In examining the
`entries
`Table 7.2, note that the categories are subdivided based
`upon whether or not they provide a fully recoverable (lossless) image.
`
`Character based
`
`Character based compression techniques operate upon the grouping
`of pixels as a byte entity. Thus, solid backgrounds in which pixel pat-
`
`jxev
`
`12
`12
`
`I
`
`

`
`7.2 IMAGE COEilPRESS¥0N TECHNIQUES
`
`315
`
`terns repeat for several byte groupings would be suitable for reduction
`from a character based compression technique.
`
`Statistical
`
`Figure 7.1a illustrates a poorly drawn image of a house assumed to
`be located in an area where most of the background represents either
`blue sky or green earth, except for a road leading to the house.
`Assume zeros are used to denote the background of the uniform sky
`included within a block of pixels while ls are used to represent a
`block of pixels that cover a uniform green lawn. Then, Figure 7.1b can
`be considered to represent the subdévision of the image into blocks of
`pixels that have the same or similar pixel characteristics. If the blocks
`have the same pixel characteristics, with each pixel exactly the same
`as the other pixels to include their color depth sequence, then the
`repeating sequence may not occur on a byte basis. lnstead, groups
`of bytes to include the pixels‘ color depth may repeat for a sequence.
`Thus, a statistical or entropy based compression method, such as
`Huffman coding or arithmetic coding, could be applied to the image
`and would more than likely produce better results.
`
`Dictionary based coding
`
`Since most images consist of repeating sequences of pixels a diction-
`ary based coding method, such as any of the Lempel-Ziv algorithms
`or derivatives, can be appEed to an image file. In fact, one of the most
`popular image file formats, CompuServe’s GIF specification, uses a
`rnodéfied form of LZW compression to reduce the size of the resulting
`
`40
`
`(b)
`
`(a)
`
`(c) Considering block: to be similar even when they vary
`
`(3) Initial image
`(b) Subdivision into blocks based upon c;:an'espondence
`ofpixel composition between blocks
`
`Figure 7.1 Examining an image
`
`13
`13
`
`

`
`316
`
`IMAGE COMPRESSION
`
`-,
`
`stored image. In applying LZW compression, the GIF specification
`first causes the separation of the color depth from the pixel values
`representing the image prior to applying compression to the pixels.
`Later in this chapter we will examine the GIF specification in detail.
`
`Binary graphics
`
`There are a large number of compression techniques specifically
`developed to operate upon images. Some of those techniques, such
`as the CCITI‘ Group 3 modified Huffman code, run-length coding and
`relative address coding, can be considered to represent lossless
`binary graphics compression techniques. Other compression tech-
`niques that fall into a binary graphics category are lossy. Examples
`of the latter include predictive coding, Adaptéve Bilevel Image Com-
`pression (ABIC), and the Joint Photographic Experts Group [JPEG)
`image compression technique.
`
`Predictive coding
`
`Predictive coding uses previously encoded parts of an image to predict
`the composition of future parts, resulting in lossy compresséon. This
`scheme was first described
`1976 (Preuss, 1976) and was applied
`to facsimile encoding of binary data.
`Under predictive coding, data
`scanned in raster format and at
`each pixel position a prediction is made based upon the composétion
`of neighboring previously processed pixels. If the prediction can be
`done ‘perfectly’, such as in a background area, then the pixel is coded
`as a zero. Otherwise, the actual value of the pixel is coded. The result
`of the prediction process is clusters of zero coded pixels for homo-
`geneous areas. Those pixels can then be reduced through the use of
`another compression technique, such as run-length coding or relatéve
`address coding.
`
`Aéaptive Bilevel Image Compression
`
`Adaptive Bilevel Image Compression (ABIC) refers to a class of com-
`pression techniques developed at IBM (Mitchell and Pennebaken,
`1988) and is currently being standardized by the Joint Binary Image
`Group (JBIG). ABIC uses a tWo—dimensional predictive coder to deter-
`mine the relaéve probabilities of a O or a 1 in the next scanned pixel.
`The conditional probability is then used by an arithmetic coder to
`minimize the size and transmission rate of an image to near the
`entropy of the source. The probability estimator and arithmetic coder
`was patented by IBM and is referred to as a Q-coder. JBIG expands
`
`14
`14
`
`I
`
`

`
`7.2 IMAGE COMPRESSION TECHNIQUES— 317
`
`I
`
`JPEG
`
`upon the work of IBM by introducing adaptive templates. Here the
`template represents the composition of a group of pixels that can be
`used to define a relationship to the current pixel being modeled. For
`example, a template could represent the composition of three pixels
`on the same line preceding the pixel being modeled and five pixels
`centered above that pixel on the preceding line. At the time this book
`was written, the JBIG standard was being developed based upon
`IBM’s original research efforts for the transmission of binary or bilevel
`documents between workstations.
`
`The JPEG compression and decompression algorithm represents a
`linked series of steps whéch are described in a comprehensive stan-
`dards document available from the American National Standards
`Institute (ANSI). Figure 7.2 summarizes the major functions associ-
`ated with the basic JPEG algorithm.
`The basic JPEG algorithm can be considered as a baselaie for which
`a number of extensions exist. Two examples of JPEG extensions
`énclude progressive coding which results in the gradual construction
`or decomposition of an image and the use of arithmetic coding to
`replace Huffman coding specified in the baseline algorithm.
`Initially JPEG groups pixels into 8 x 8 blocks, organized as chrorni—
`nance (color) and luminance (intenséty or brightness) components.
`When appEed to a standard computer monitor image composed of
`red, green and blue (RGBI pixels, this results in a YUV transform-
`ation, where Y represents intensity and U and V represent color
`values. In a YUV form the same picture image requires less storage
`than in RGB form; however, there is no perceptible loss of image qual-
`
`ity.
`After the pixels in an image are grouped into blocks, a discrete
`cosine transformation (DCT) process converts blocks of YUV pixels
`into sets of coefficients representing the isolated frequency compo-
`nents of the colors and intensities of the block. During the DCT pro-
`cess, each block is converted into a set of 64 coefficients—one dc coef-
`ficient and 63 ac coefficients. This action shifts the pixel block from
`the spatial domain to the frequency domain, resulting in most of the
`transformed block's energy being concentrated in the lower fre-
`quencies. Prior to the quantization step the dc coefficient is differen-
`tially encoded with respect to the prior block.
`The quantization step results in the use of a table of 64 quantization
`
`l"'33° l
`
`Pixel
`blocking
`
`=
`.
`Discremcoeinel
`-—)- Quantization
`transformation ll
`
`__ Runlength
`coding
`
`
`
`ll-[um-nan
`—)-I
`| coding
`
`Data
`packing
`
`Figure 7.2 The basic JPEG compression algorithm
`
`15
`15
`
`
`

`
`318
`
`IMAGE COMPRESSION
`
`values which the 63 ac block coefficients are compared against. Since
`most matches are not exact but are approidmaéons, this action
`results in the lossy component of JPEG. For example, consider the
`composition of the two subblocks illustrated in Figure 7.1c. During
`the quantization process small differences between blocks may not
`result m the use of a different quantization value being assigned to
`each block. Thus, the two subblocks could have the same coded
`value; however, in this example decompression would result in the
`loss of one pixel's correct value. In addition, since quantization is
`applied to the frequency matrix generated by the CDT operation, the
`quantization process can be Varied to reduce the size of the resulting
`data stream. For example, since human vision is less sensitive to
`color than to intensity, the number of quantization values or steps
`used to represent color may be reduced, resulting in a higher degree
`of compression for color components While limiting visually percep-
`tible image degradation. Similarly, since human vision is less sensi—
`tive to high frequency details than to low frequency details, the steps
`used to represent high frequency Values can be encreased which
`enhances the compressilsility of the image.
`The use of run-length and Huffman coding further reduces the size
`of the image. Both a static predefined Huffman table and a two-pass
`Huffman table created to represent the specific image are supported
`by JPEG.
`final step in the JPEG process is data packing, in which
`bit sequences produced by the Huffman coder are grouped into bytes.
`
`Object model
`
`The ability of an image to be modeled can significantly reduce redun-
`dancies. Examples of object model compression techniques include
`pattern match coding and fractal based coding.
`
`Pattern matching
`
`Pattern match coding results in the subdsvision of an image into
`blocks that have similar patterns or shapes. Then, only a block iden-
`tifier and block position of blocks whose composition match a prior
`identified block requires encoding. For example, consider Figure 7.1b.
`Here the image was broken into 25 blocks and conveniently, for
`illustrative purposes, 19 represent sequences of pixels that were rep-
`licated in a similar manner in other blocks. A PMC technique would
`‘store the contents of one block numbered 0 and one block numbered
`1. Then, to encode block (0,3) the sequence 0,0,3 could be used, with
`the first number denoting the fact that the block at position 0,3
`matches the contents of block 0.
`A comparison of the pixel contents between blocks results in an
`
`16
`16
`
`I
`
`

`
`7.3 GIF FILE FORMATS
`
`
`
`319
`
`increase in block size, lowering the probability of an exact match of
`the composition of pixels. Thus,
`there is a tradeoff between
`attempting to match larger blocks and the ability to do so. One
`method which partéally alleviates this tradeoff is to assume the pixel
`contents of blocks match even when they physically do not whenever
`the difference between blocks is under a certain threshold. For exam-
`ple, Figure 7 .1c illustrates the composition of two adjacent image
`blocks. Although they do not exactly match, the PMC algorithm can
`be configured to consider the blocks to match. While this method
`results in an inability to fully replicate the pixel content of the image,
`it increases the ability of the algorithm to obtain a more effective com-
`pression ratio.
`
`Fractal coding
`
`Fractal coding of images is based upon the work of the Frenchman,
`Benoit Mandelbrot, whose classic book The Fractal Geometry of Nat-
`ure (Mandelbrot, 1982) can be considered as opening a new branch
`of mathematics. Mandelbrot coined the word ‘fractal’ to describe
`objects that are ‘fractured’ for which mathematical formulas can be
`used to represent an image.
`Based upon the work of Mandelbrot, a firm based in Atlanta, Geor-
`gia, Iterated Systems, developed software that can be used to com-
`press images achieving compression ratios up to or higher than
`10000: 1. The technique used by Iterated Systems commences with
`breaking a digitized image into blocks or segments. Each segment
`is compared to a library of iterated function system (IFS) codes that
`reproduce corresponding fractals, significantly reducing the size of
`the library. The IFS codes generate fractals that are compared to the
`pixel composition of a block. When the fractal provides a close
`approximate of the contents of the block the code replaces the block.
`Although this compression technique can achieve a compression rateo
`several orders of magnitude or greater than other techniques, the
`computational time required to encode an image can exceed 100
`hours or more. Thus, this technique is impractical for on-the-fly com-
`pression applications; however, decompression can occur relatévely
`fast, which makes this technique suétable for encoding and distribut-
`ing large numbers of images or images associated with a large databa-
`se.
`
`7.3 GIF FILE FORMATS
`
`There are two GIF formats presently defined—GIF87 based upon the
`CompuServe standard proposed in 1987, and GIF89 which rep-
`resents a modification to the original standard. The latter is more for-
`
`17
`17
`
`
`

`
`320____m IMAGE COMPRESSION
`
`mally referred to as GlF89a, referencing GIF Version 89a. Both GIF
`and ‘Graphics Interchange Format’ are trademarks of CompuServe,
`Inc., an H&R Block company.
`The original GIF specification was developed in 1987 when the
`ability to display more than 16 colors on a monitor was considered
`to be in the distant future. Due to this, the 1987 standard, as well
`
`as its 1989 revision, are limited to 256 colors out of a palette of 16
`million. While this limits the ability of GIF to represent truly stunning
`graphics, it also limits the size of a file required to store an image. This
`in turn reduces the time required to transmit GIF encoded images.
`A modified form of LZW compression is buflt into both GIF stan-
`dards. This provides a lossless or reversible compression method. In
`comparison, JPEG, a technique described later in this chapter, sup-
`ports a lossy compression process. Although this results in degrading
`the image quality, it also enables file sizes to be considerably reduced.
`The actual image quality degradation is controlled by the user and a
`significant reduction in the size of a stored image can be achieved
`with little to no visually perceptible image distortion. However, if a
`user tends to be greedy and requires an additional reduction in the
`size of the stored image, the ability to Visually recognize the image
`may be impaired as we will note later in this chapter. Figure 7.3 illus-
`trates the general GIF file format essentially applicable to both
`GIF87a and GIF89a. As we examine each field in the file format illus-
`
`trated in Figure 7.3, we will note the differences between the two stan-
`dards.
`
`GIF Signature
`
`Under the GIF87a standard the GIF Signature field consists of the
`entry GIF87a in the first six bytes of the file. Under the GIF89a stan-
`dard the GIF Signature field was renamed as the Header; however,
`
`GIF signature
`
`Screen descriptor
`
`Global color map
`
`0
`
`0
`Image descriptor i
`mm mm mm
`Raster data
`
`__I
`
`Figure 7.3 General GIF file format
`
`18
`18
`
`.
`
`

`
`7.3 GIF FILE FORMATS _j_ 321
`
`six bytes are still used to identify the context of the GIF data stream.
`Bytes 0 to 2 continue to contain the fixed value GIF, while bytes 3
`through 5 identify the Version number used to format the data
`stream. Thus, the GlF87a standard is limited to supporting one data
`stream format While the GIF89a standard can support different data
`stream formats.
`
`Screen Descriptor
`
`The screen description field consists of eight bytes which define the
`parameters of GIF images included in the file. Those parameters
`include the raster width and height of the GIF image, an indicator
`concerning whether or not a global color map follows the screen
`descriptor field, the number of bits of color resolution, the number of
`bits per pixel in the image and the color index associated with the
`screen background. Figure 7 .4 illustrates the format of the Screen
`Descriptor field.
`Under the GIF87a standard the value of pixel represents the
`maximum number of colors used to represent an image. Since tiriree
`bits are used for cr, the range of Values of O to 7 represents one to
`eight bits which supports two (black and white) to 256 colors. Also
`under the GIF87a standard, bit 3 of word 4 as well as all bits in word
`6 were reserved for future use. Under the GIF‘89a standard, bit 3 of
`
`Word 4 becomes a sort flag. When set to 1, it indicates that a following
`Global Color Table is ordered by decreasing importance, with the
`most important color appearing first in the table. When the sort flag
`is set to 0, it indicates the Global Color Table is not sorted. A second
`change under the GIF89a standard concerns the use of word 6, which
`Was reserved for future use under the GIF87a standard. Under the
`
`Position
`Byte
`number 76543210
`
`0 1—-—-—-T4-—.
`S
`1
`creenwidth
`.
`h
`Cree“ eight
`
`2
`
`S
`
`Raster width in pixels
`(least significantbit first)
`Raster height in pixels
`(least significant bit first)
`M = Global Color Map follows
`Crt E = number ofbits ofcolor resolution
`pixel + 1 = number bits/pixel in image
`
`In
`
`01'
`
`0
`
`Pixel
`
`1
`d
`B“
`an
`
`
`Background = color index of screen
`background
`
`0 0 0 0 0 0 0 0
`
`3
`
`4
`
`5
`
`6
`
`Figure 7.4 Screen Descriptor field
`
`19
`19
`
`
`

`
`322
`
`IMAGE COESPRESSION
`
`GIF89a standard word 6 contains the pixel aspect ratio which rep-
`resents a factor used to compute an approx1'mation of the aspect ratio
`of the pixel if; the original image. When the Value of the field is not
`zero the approximation of the aspect ratio is obtained from the follow-
`ing formula:
`
`_
`Pixel aspect ratio + 15
`Aspect ratio = — - 64
`
`where the pixel aspect ratio is the quotient of the pixels width over
`its height. The value range of this field permits specification of the
`widest pixel of 4: 1 to the tallest pixel of 1:4 in increments of 1 /64th.
`
`Global Color Map
`
`The Global Color Map, which was renamed flee Global Color Table
`under the GIF89a standard, contains a sequence of bytes rep-
`resenting red—green—b1ue color triplets. Figu