Chris McDonald
									CS 641
									9/29/02

	Project Proposal:  The Effect of Document Image Compression 
				on Text Legibility

Problem

Textual documents often need to be treated as a images when digitized.  We refer to these as document images or text images.  Examples include manuscripts of  historical importance, signed documents (such as birth certificates) and poster advertisements.  In such cases simply extracting and digitizing the pure text using optical character recognition (OCR) does not preserve some essential characteristics of the document.  There is a qualitative difference between seeing the U.S. Constitution in plain text and seeing it in its original form.  

In an application such as a digital library one wishes to serve such documents to users over a network with limited bandwith.  Thus the issue of compression becomes important - uncompressed images can be quite large and so we want to achieve as much compression as possible.  The question I wish to pursue is what effect various compression schemes have on the legibility of document images.  Setting aside lossless schemes, which will obviously incur no cost in legibility, I will experiment several different compression algorithms and determine how much each algorithm degrades legibility at various levels of compression.

Previous Work
I have so far been unable to find any paper which describes a quantitaive analysis of the effect of image compression on text legibility.  That certainly doesn't mean that no such work exist, and I will continue to look as I begin my experiments.  There is however considerable work on compression techniques for document images, and it is an active field of research.  

Work in the area began with compression for fax machines, but it is driven today mostly by the needs of digital library applications.  These applications have many document images, and standard image compression techniques, which tend to assume a certain degree of coherence between neighboring pixels, don't work very well on high-contrast text.  The general sentiment in the community is that the solution to this problem is to somehow split the text from the images and compress each seperately, then recombine the results.  Thus the techniques that are very effective on images can be used in that domain, without destroying
the readability of the text.    

Proposed Solution
Each paper on the subject of document compression presents its own algorithmic twists and tweaks, an exhaustive test of published methods would be impossible.  Instead I will attempt to select a representative sample - disregarding lossless methods, which obviously have no affect on image quality.  I have already found a number of likely candidates.  The baseline is JPEG, which is based on the discrete cosine transform (DCT) and is one of the most common image compression standards on the World Wide Web.  The second method is JPEG-based Mixed Raster Content (MRC) compression, as discussed in [3].  This method divides the image into foreground and background and uses seperate JPEG compression on each component.   Third is the JBIG-2 standard, for compression of bi-level images [6].  This scheme will naturally not be applicable to any color or grayscale images in the experimental data set.  Finally I will use wavelet-based compression with a sampling of different filters, similar to the experiment described in  [4].

Each method will be used at various levels of compression to compress a variety of input document images - some in color and some in black and white, some pure text and some with images and text intermingled, some with large text and some with small text, and so forth.  The resulting images, as well as baseline uncompressed images, will be shown to test subjects.  They will be asked to transcribe the text and provide a qualitative rating of the text legibility on a 1-100 scale.  No single subject will be shown any two images from the same original image, to prevent knowledge of one contaminating the evaluation of the other.  The qualitative rating as well as the accuracy of the text transcription should provide a useful assessment of the quality of the tested compression schemes. 

Once I have the data I will analyze it and hopefully find some interesting patterns.  At what point does legibility break down completely under each method?  Do certain method perform better under certain input conditions?  Which methods are rated best in qualitative  terms at a given level of compression?  How well does qualitative perception of legibility correspond to accuracy of transcription?  These are the sorts of questions I hope to answer.  

Schedule
The first phase of my project will be to acquire implementations of each of the algorithms I intend to test.  I will likely  also need to adapt them to better suit my needs or to add needed functionality.  Simultaneously, I need to find a number
of test subjects willing to volunteer a bit of their time for my experiments.  This should take no more than 3 weeks (by Oct. 21) Once this is done, I need to find and/or create the document images I wish to use and generate a nice range of output images at various compression levels to use for my experiments. This will require some trial and error, but should take no more than 2 weeks (Nov 4).  Next I need to actually perform the experiments.  How long this takes will mostly be determined by the availability of my test subjects, but I can comfortably allow 2 weeks (Nov. 18).  This leaves me 3-4 weeks to analyze the results, draw conclusions and write my report.  

References
[1]  S. Battiato, M. Mancuso, A. Bosco, "Psychovisual and Statistical Optimization of Quantization Tables for DCT Compression Engines," 11th International Conference on Image Analysis and Processing, 2001, pp. 602-606
[2]  F. Le Bourgeois, H. Emptoz, E. Trinh, "Networking Digital Document Images," Sixth International Conference on Document Analysis and Recognition, 2001, pp. 379-383
[3]  D. Mukherjee, N. Memon, A. Said, "JPEG-Matched MRC Compression of Compound Documents," International Conference on Image Processing, 2001, vol. 2,  pp. 434-437.
[4]  S. Saha, R. Vemuri, "Adaptive Wavelet Coding of Multimedia Images," Proceedings of the Seventh ACM International Conference on Multimedia (part 2), 1999, pp. 71-74.
[5] I. H. Witten, A. Moffat, T. C. Bell, Managing Gigabytes : Compressing and Indexing Documents and Images, Van Nostrand Reinhold, New York, 1994
[6]  Yan Ye, P. Cosman, "Fast and Memory efficient JBIG2 encoder," IEEE International Conference on Acoustics, Speech, and Signal Processing, 2001, vol. 3, pp. 1753-1756.
.