Progressive Image Transmission  
Capability (PROTRAC) on the 
World Wide Web
Vojislav Lalich-Petrich,
Center for Automation Research (CfAR)
University of Maryland, College Park 20742, USA
lpv@umiacs.umd.edu
http://www.umiacs.umd.edu/users/lpv/HTML/voja.html

Gaurav Bhatia,
Computer Science Department
University of Maryland, College Park 20742, USA
bhatia@eng.umd.edu

Larry Davis,
Computer Science Department
University of Maryland, College Park 20742, USA
lsd@umiacs.umd.edu
http://www.cs.umd.edu/users/lsd/

Abstract
This paper describes a method that allows progressive and scalable image transfer over the World Wide Web (WWW or W3). Images are converted into the appropriate format - sliced and compressed - on the server's side. At the client's request, with the desired image quality specified, the server sends chunks of data through the network. The client cumulatively builds the image while applying additional image enhancement operations on the data obtained so far. The ability to specify desired image quality allows a client to satisfy constraints imposed by line bandwidth and response time. This method is illustrated with 8 bit gray scale and true color (24 bit) images.

Keywords
Progressive, Image, Transmission, World Wide Web, HTTP, GIF, LZW, JPEG 
  
         Plane 1                 Planes 1+2                  Planes 1+2+3

Introduction

Small bandwidth lines and long waits for image transfer over the network are all too familiar. Recognizing the fact that a 500KB file can be the text of someone's PhD thesis or only the color image for the cover of the same, clearly reflects the fact that image transfer is taking orders of magnitude more bandwidth than any other data type on the WWW today. However, image data is inherently suitable for processing that results in reduction of its size at the expense of image quality, which can still remain satisfactory for many applications. There is very little that has been done to take advantage of this property of images. This suggests that the WWW and the tools used to utilize it, in their current incarnation, are not sufficiently scalable.

High speed lines, improved protocols [Spec94a, Spec94b] and other hardware enhancements are not likely to solve the problem. Our appetite for rapid data transfer will grow as more and more speed is available from processing hardware, while today's communication bottleneck will remain.

We present an approach that addresses this issue. A progressive image transmission capability (PROTRAC) has been developed to provide scalable image transfer, in which the quality of the image passed to the client can be adjusted.

It is important to note that the method discussed allows for a complete and non lossy image transfer with a negligible overhead, while the stateless nature of the HTTP protocol is preserved.

Overview of the PROTRAC Procedure

The subject of progressive transmission is well studied in a literature (see the references). We have developed a method that performs efficient progressive image transmission and can combine image coding of spatial and color resolution. The method developed takes into account both the constraints and the advantages of the WWW environment which makes it a novel approach in the field of progressive image transmission.

Procedure

The PROTRAC procedure is based on the idea that only partial information from the original image is provided to the client at each iteration. The client will use the limited information it has obtained, perform enhancement if desired or necessary, and display the image. In the next iteration, additional information about the image will be sent to the client. The new data, together with data already on the client side, is used to build a new and more complete image at the client, achieving a better image representation. As the procedure is iterated at the user's request, the client gathers more image data so that eventually it is able to recreate the image in its original form. 

     The Algorithm.	Processing steps at the server.

Server

The PROTRAC procedure will slice the original image by partitioning it along its bit planes. This can occur in response to several situations that we discuss in the Data Management section of this paper. For an 8 bit gray scale image this will amount to 8 planes. In the case of true color (24 bit) image the same procedure is applied for each of the three bands (RGB) producing 24 such slices. Naturally, each plane will consist of zeros (0) and ones (1) only. To reduce the size of raw image data, we have chosen the Lempel-Ziv-Wellsh (LZW) compression to be applied to the planes after 8 consecutive bits of one plane are packed in a byte.

This procedure is in its core identical to the compression procedure applied in the case of GIF images. There, LZW compression is used to compress regular pixels from image data after which color map and image header information is tacked to it. Knowing this, we can be certain that converting image file to PROTRAC format will result in file sizes virtually identical to the ones obtained from GIF compression. The fact that image bit planes are made out of bilevel data may further improve compression rates by applying packbit compression techniques often used in fax technology. 

 Image plane concatenation.	 Bits loading into pixel (8 bit).
Optionally, the original image can be averaged (i.e. over regions of size SxS ) before the slicing procedure is applied to it. This will further reduce the amount of data to be transferred, but will make the image transfer lossy.

Client

When a chunk of data reaches the client it is added to the existing image data (if available) on the client side. Since chunks arrive in the form of compressed image bit planes, they are decompressed and pasted on "top" of the planes currently defining an image. The additional bit plane provides a better color or gray scale resolution as resolution gets increased by a factor of two. Maintenance of the order in which bit planes are composed to represent an image is controlled by the client.

If the image was averaged prior to the transfer, the composite image will be blurred (some kernel applied) to compensate for the loss in the spatial resolution due to the averaging performed on the server side.

Advantages

The power of this method comes from the ability to control the amount of data to be transferred. In some cases, the first iteration can prove sufficient for a given application, considering constraints of bandwidth and response time.

Notably, we can compare this to sending a true color image by fax. In many cases, the low quality of the received image can be satisfactory. The advantage here is that if it is not, the client can ask for more image data and combine it with what it has received previously. The crucial point is that the client assembles data received in a previous iterations with a data from the most recent one to produce a higher quality image.

Also worth mention is that by transferring images in this way we are not introducing any overhead in data transmission. No image data is sent twice through the network. Repeated client requests for more data, if needed, are the only overhead which is, for all practical purposes, negligible.

It is important to note that the stateless nature of the HTTP server and client is preserved. We find this to be important as this will provide for seamless software transition and smooth upgrade path. It will be the client's responsibility to maintain the information on the amount and sequence of data received, relieving the server of any bookkeeping.

In addition to this, the technique we propose could be applied not only to the in-line images contained in a document, but also to the image files pointed to from the document. In a similar manner as described above, clients would receive a reduced quality image from the server and spawn an external viewer to display it. Depending on the PROTRAC implementation at the client, external viewer does not have to be PROTRAC aware.

Data Management

A data management heuristic is proposed: The method we propose leaves room for various other data management algorithms to be used in order to satisfy other specific needs.

Experiments and the Demo

Generally, a gray scale image compressed to a GIF format will be about 40% to 60% of its original size. As expected, slicing the original image and applying the LZW to each respective plane provides compression rates the same as the rates obtained from GIF. Consequently, if images are converted to this format and transferred in full to the client, the bandwidth used will remain virtually identical to the bandwidth used to transfer images in conventional format.

Currently, we have a demo based on a CGI script that performs the processing as described in this paper. This simulation was meant to be an efficient and effective presentation of a proposed method in a close to real world environment.

Other Considerations

Color images with 256 colors (8 bits per pixel)
The progressive transmission of color images with 256 colors is currently unresolved by this method. The issue of color map adjustment as transmission progresses is still an open problem. Due to the fact that color map entrees can contain random values from the color three-space, the best way to perform color quantization as image bit planes are added to the final image is unclear.
We will try to address this problem in our future work. A possible solution would be application of wavelet compression instead of image bit plane partitioning.

CPU Load vs Storage Requirements
Based on a data management model used, the server could experience significant increases in the load on its CPU. Ideally, images will be stored in the PROTRAC format, which will have no impact on the amount of storage space required at the server compared to the presently used image formats. PROTRAC format will also insure very light CPU activity in respond to client requests, as no image processing operations will be performed on the fly.
Nevertheless, if existence of conventional formats is required for historical, compatibility or upgrade path reasons, we feel that current workstations are sufficiently fast and are able to perform proposed transformations on the fly, as those operations are computationally inexpensive and are of no more than O(n) complexity.

Future work

Some Results

  • Gray scale
  • Color I
  • Color II

    • Acknowledgment

    The authors thanks Pedja Bogdanovich for helpful discussions about progressive image transmission and system staff at UMIACS for their help in setting up the CGI demo.

    References

    [Digi92]
    RamaChellappa (1992) Digital Image Processing, IEEE Computer Society Press.
    [FDFH92]
    Foley, vanDam, Feiner, Hughes (1992) Computer Graphics, Addison-Wesley.
    [Hana90]
    Hanan Samet (1990). The Design and Analysis of Spatial Data Structures, Addison-Wesley.
    [Know80]
    Ken Knowlton (1980) Progressive Transmission of Gray-Scale and Binary Pictures by Simple, Efficient, and Lossless Encoding Schemes. Proceedings of the IEEE, VOL. 68, NO. 7, July 1980, 885-896.
    [Sloa79]
    K. R. Sloan Jr. and S. L. Tanimoto (1979) Progressive Refinement of Raster Images. IEEE Transactions on Computers, VOL. c-28, NO. 11, November 1979, 871-874 .
    [Spec94a]
    James Lane (1994) ATM knits voice, data on any net. IEEE Spectrum, February 1994, 42-45.
    [Spec94b]
    Dragos Ruiu (1994) Testing ATM systems. IEEE Spectrum, June 1994, 25-27.
    [Tani75]
    S. L. Tanimoto and T. Pavlidis (1975) A Hierarchical Data Structure for Picture Processing. Computer Graphics and Image Processing, June 1975, 104-119 .
    [Yunm92]
    H. Yunming, H. M. Driezen, N. P. Galatsanos (1992) Prioritized DCT for Compression and Progressive Transmission of Images. IEEE Transactions on Image Processing, VOL. 1, NO. 4, October 1992, 477-487.
    Vojislav Lalich-Petrich, Gaurav Bhatia and Larry Davis.

    Last update: March 15, 1995.
    URL: http://www.umiacs.umd.edu/users/lpv/HTML/PROTRAC/protrac.html