Increasing Web Bandwidth through Image Compression: An Overview of GIF, JPEG and Fractal Compression Techniques

Adrian Vanzyl, Unit of Medical Informatics, Monash University, 867 Centre Road, East Bentleigh, 3165. Email: adrian.vanzyl@med.monash.edu.au. Web: http://www.monash.edu.au/informatics/Default.html. 61-3-579-3188 Voice. 61-3-570-1382 Fax

Keywords: Image compression, Bandwidth, WWW, GIF, JPEG, Fractal

Introduction

The need to improve effective bandwidth is motivated by the explosive growth of users and service providers using the web, which is currently severely straining the available bandwidth.

Whilst in the past most net traffic has been text based, with file sizes measured in hundreds of kilobytes, the use of the html protocol to serve multimedia documents has increased file sizes to megabytes. This encroachment of bandwidth results in long delays in accessing documents, limits information availability to less users in a given time, and negatively affects net traffic using other protocols such as mail and news.

We do not examine the role of motion picture/video compression standards such as MPEG, nor that of textual compressors, but acknowledge their importance in achieving the overall goal of improving network throughput.

In November 1994, the total amount of net traffic on NSFNET alone was 17,781 billion bytes. The traffic due to WWW was 3,126 billion bytes (second largest, and 14% of total traffic). FTP ranked first, and news and mail third and fourth respectively [13]. This compares to 3,602,330 bytes (580th largest and 0.0004% of total traffic) for the WWW in June 1990 [13]. This incredible increase is continuing at almost the same hyperexponential rate.

The following comparisons of file sizes show the magnitude of the problem being faced by the increassed use of images.

A standard 80 x 24 screen full of text requires just under 2 K to store. A similar sized full colour image requires just over 900 K to store (a ratio of 450:1). For comparison (rounded figures, no compression):

300K - a two hundred and fifty page novel
300K - a 640x480, 8 bit/256 colour image
900K - a 640x480, 24 bit/16 million colour image
128K - a 1024x1024 1 bit/black and white image
1024K - a 1024x1024 , 8 bit/256 colour image
3072K - a 1024x1024 , 24 bit/16 million colour image

Compression Strategies

We discuss three types of compression techniques, namely the two current standards used (JPEG and GIF), and the newly emerging technique of fractal compression.

For each scheme we consider current status, compression strategy, degree of compression achievable, and strengths and weaknesses.

Lossless compression schemes are those in which no information is lost in the compression cycle. Lossy schemes compress an image by permanently discarding certain information.

In general terms, GIF is suited to lossless compression of smaller, 8 bit images. JPEG and Fractal compression are suited to lossy compression of large, full 24 bit images.

JPEG

JPEG stands for Joint Photographics Experts Group [1]. It is a compression standard aimed at still images, in colour or grey scale, and having some degree of complexity (for example, photographs of the `real' world). For moving images, MPEG (Motion Pictures Expert Group) is more appropriate [7, 11], and for simple images (highly geometric or stylised) GIF is more appropriate. For scanned text images TIFF (Tagged Image File Format), or JBIF (Joint Bi-level Image Experts Group, for black and white images) [7] are more appropriate.

Developers and Status

JPEG is an international standard, developed jointly by CCITT and ISO. Public domain viewers are available for all major platforms. A list of archive sites is available [1]. C source code is also available [2]. JFIF (JPEG File Interchange Format) is the current de facto interchange format for JPEG compressed images.

Compression Strategy

JPEG is a lossy compression scheme. The greater the compression, the greater the degree of information loss. This can be user determined, to optimise the trade-off between resultant image size and image quality. The algorithm exploits some of the ways in which the human eye perceives and analyses images, so that compressed images still appear to be of high quality when looked at by human eyes [7]. Times for compression/decompression are symmetric - they take roughly the same amount of time.

The algorithm is based on the forward discrete cosine transform (DCT), as applied to a block breakdown of the original image into 8 by 8 blocks, quantised down to a finite set of possible values, and then further transformed (run length encoding) and finally entropy encoded using Huffman or arithmetic coding [7, 8].

Degree of Compression

The following table compares the compression ratios with the observed quality. A 20:1 ratio means that an image originally 900K will be compressed to 45K, which is one twentieth its original size.

10:1 to 20:1 - High quality, with little or no observable loss in image quality to the human viewer.
30:1 to 50:1 - Moderate quality.
60:1 to 100:1 - Poor quality, suitable for thumbnails and previews. Marked blockiness and Gibb's effects occur (see weaknesses below).

In comparison with GIF compressed images, high quality JPEG compression produces an image 4 to 5 times smaller.

In comparison with Fractally compressed images, the degree of compression is roughly equivalent.

Strengths

JPEG compression offers the following advantages and strengths:

it provides support for full 24 bit colour images. In contrast, GIF only support 8 bit images.
the compressed image size and image quality tradeof can be user determined.
it is ideally suited to images of real world scenes, or computer generated images which are complex.
it is platform independent for displaying 24 bit images. It is currently the most widely adhered to standard, with the algorithm, source code implementations and public domain viewers readily available [1,2].
it provides fast compression speed compared to fractal compression [15].

Weaknesses

The weaknesses and disadvantages of JPEG are:

JPEG compression is a tradeof between degree of compression, resultant image quality and time required for compression/decompression. Blockiness results at high image compression ratios.
it produces poor image quality when compressing text or images containing sharp edges or lines. Gibb's effect is the name given to this phenomenon where disturbances/ripples may be seen at the margins of objects with sharp borders.
it is not suitable for 2 bit black and white images.
the degree of compression is greater for full colour images then it is for grey scale images.
it is not suitable as a strategy for images that are still being edited, because every compression/decompression cycle continues to lose information.
it is not intended for moving images/video.
it is not resolution independent. Does not provide for scalability, where the image is displayed optimally depending on the resolution of the viewing device. [14]

GIF

The Graphics Interchange Format is a lossless 8 bit/256 colour protocol for "on-line transmission and interchange of raster graphic data in a way that is independent of the hardware used in their creation or display" [3].

Developers and Status

Developed and copyrighted by CompuServe, who provide a royalty free licence for use of the GIF standard. The standard, and licensing information is available from [3].

Compression Strategy

GIF is a lossless compression strategy, based on LZW compression (Lempel-Ziv-Welch algorithm) [4,5,6]. There is however significant colour loss in quantisation of 24 bit images to 8 bits. The LZW technique was originally developed for compression of textual material, and compresses files by substituting commonly occurring character sequences with a reference to the first occurrence of that sequence.

Degree of Compression

For fullscreen, 8 bit images of moderate complexity, 4:1 compression is the average. Since this is a lossless scheme, the compression ratio can not be increased by trading off quality.

Strengths

GIF compression offers the following advantages and strengths:

it is lossless for 8 bit images (since no image degradation occurs, repeated compression/decompression cycles are possible, also suitable for images where information loss can not be tolerated).
it is ideally suited to stylised images such as line drawings, or those which contain only a limited number of colours (for these images it can produce good compression ratios, and no Gibb's phenomena).
it is widely used and supported, with no runtime licence required.

Weaknesses

The weaknesses and disadvantages of GIF compression are:

it is not suitable for 24 bit images. When compressing such images, much of the colour information is lost during the quantisation process which reduces this to 8 bits. Good algorithms can however optimise this process so that the resultant image still has good quality from a human point of view.
the compression ratios are low. These can not be traded off against compression times or degree of loss of quality.
it is not intended for moving images/video.
it is not resolution independent.

As display devices become capable of higher bit depths (number of colours), GIF will become superseded.

There has been a recent (January 1994) development that throws the continued use of GIF as a standard into turmoil. Unisys has been awarded a patent for LZW compression. Since GIF uses LZW compression, Compuserve may be obliged to pay for its use of GIF images. In turn, general users who have been using GIF compression may also be liable for royalty payments. This issue is yet to be resolved.

FRACTAL Compression

Fractal compression has generated much discussion, hyperbole, promise and criticism. The emergence of a de facto solution (though proprietary), and the availability of hardware assisted compression, is providing the basis for a valid future alternative image compression technique. It is particularly suited (and is currently aimed at) solutions where images need to be compressed once and then delivered in maximally compressed form for rapid and repeated decompression.

Developers and Status

A commercial compressor and decompressor is being licensed by Iterated Systems [10]. It is based on the work and patent held by Barnsley [8], the inventor of the fractal transform.

The decompressor software is available as a Windows DLL, and can be licensed from Iterated Systems.

Compression Strategy

In simple terms, the aim of fractal compression is to find a small finite set of mathematical equations that describe the image [14].

Fractal compression is based on IFS Iterated Function Systems. The technique is based on the presence of `affine redundancy' in an image. This is present when part of an image is the same as another part of the image, providing an arbitrary number of transformations can be applied to the original part (such as rotations, contractions, skews and moves) [15]. To achieve such an affine mapping requires significant mathematical processing, and the commercially available solution is based on the work of Barnsley [8,14]. The use of human chosen templates to assist in this process can significantly improve the decompressed image quality for a given compression ratio.

Degree of Compression

This table compares compression ratio with observed image quality.

20:1 to 50:1 - High quality, with little or no observable loss to the human viewer.
50:1 to 90:1 - Moderate quality.
100:1 and greater - Poor quality, suitable for thumbnails and previews.

Strengths

Fractal compression offers the following advantages and strengths:

it is aimed at compression of full 24 bit colour images.
it is ideally suited to real world image compression, due to the inherent fractal nature of many natural images [16].
the degree of compression can be traded off against compression time (ideal for creation of archives).
it provides a high degree of compression. Compressed image size does not generally increase strictly linearly as the image size increases, it increases at a lower rate (ie better effective compression for larger and larger images). JPEG compressed file size increases purely linearly.
compresion is non symmetrical. Decompression takes significantly less time than compression. Decompression can also be significantly faster than JPEG.
it provides scalability/resolution independence - because the image is defined by a set of equations, these can be arbitrarily scaled. It is of course not possible to create more information in the image as it is enlarged, so at a certain point during this process, image quality starts being sacrificed for size. This point is however always significantly higher than it is for JPEG or bitmapped images.
it can be used as a component in live video compression.

Weaknesses

The weaknesses and disadvantages of fractal compression are:

it is not standard.
the compression scheme is not documented in the public domain. This situation is currently being reviewed by Iterated Systems [10], and in the near future it is foreseen that the decompressor at least will be in the public domain. For general adoption however it is essential for source code to become widely available.
the software compression times are very long, unless hardware assisted.
it is not suited for repeated compression/decompression cycles due to its lossy nature.

Conclusion

The current preferred solutions for delivering images on the web are GIF and JPEG. This observation is based on an overview of the major web sites (and also ftp picture archive sites). The current state is derived from both historical precedent (especially for GIF), and the availability of the protocols in the public domain. JPEG is becoming more widely accepted, and due to its better compression ratios and support for full 24 bit images, we recommend it. Since it offers on average a four times greater compression ratio than GIF, its wider adoption will significantly improve the effective bandwidth. Fractal compression is a technology standing on a threshold - keeping it proprietary is likely to stop it from taking the step into mainstream use.

It is hoped that this overview of the current state will raise awareness sufficiently for wide adoption by all webmasters of JPEG image compression.

References

[0] Fractal web site at http://legendre.ucsd.edu/Research/Fisher/fractal.html

[1] JPEGFAQ - The FAQ for JPEG image compression. FTP access from ftp://rtfm.mit.edu/pub/usenet/news-answers/jpeg-faq.

[2] JPEG source code - Available from the Independent JPEG Group via ftp from ftp://ftp.uu.net/graphics/jpeg.

[3] GIF 89a - Graphics Interchange Format, Programming Reference, Version 89a, Compuserve Incorporated, Graphics Technology Department, 5000 Arlington Center Boulevard, Columbus, Ohio, 43220.

[4] Nelson, M.R. : "LZW Data Compression", Dr. Dobb's Journal, October 1989.

[5] Ziv, J. and Lempel, A. : "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, May 1977.

[6] Welch, T. : "A Technique for High-Performance Data Compression", Computer, June 1984.

[7] COMPFAQ - The FAQ for the comp.compression and comp.compression.research groups. FTP access from ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq.

[8] M. F. Barnsley, L. P. Hurd, "Fractal Image Compression", AK Peters Ltd, 1993.

[9] JPEG standard description - "Digital Compression and Coding of Continuous-tone Still Images, Part 1: Requirements and guidelines", Number: ISO/IEC CD 10918-1.

[10] Iterated Systems Inc, 5550A Peachtree Parkway, Suite 650, Norcross, GA 30092.

[11] The MPEG FAQ available on the web at http://www.crs4.it/HTML/LUIGI/MPEG/mpegfaq.html.

[12] Standard CCITT test image set ftp://ipl.rpi.edu/image-archive/bitmap/ccitt.

[13] Network statistics, available from ftp://nic.merit.edu/statistics/nsfnet.

[14] Marini, D., Image files comparing JPEG and Fractal compression, available from ftp://ftp.dsi.unimi.it/pub/imaging/fractal_compression/images

[15] Simon, B, "How Lossy Compression Shrinks Image Files", PC Magazine, July 1993.

[16] Mandelbrot, B. B., "Fractal Geometry of Nature", W. H. Freeman and Co, New York, 1982.

Copyright

© Southern Cross University, 1995. Permission is hereby granted to use this document for personal use and in courses of instruction at educational institutions provided that the article is used in full and this copyright statement is reproduced. Permission is also given to mirror this document on WorldWideWeb servers. Any other usage is expressly prohibited without the express permission of Southern Cross University.

Return to the AusWeb95 Table of Contents

AusWeb95 The First Australian WorldWideWeb Conference