The Effect of Compression on Text Legibility in
Document Images

Chris McDonald

Abstract
Document images are proliferating across the Internet, and are useful in many domains, especially marketing and historical research.   The defining characteristic of document images is that they are images which contain text.  By performing experiments with several different metrics of legibility and several different compression methods, this paper seeks to answer how much lossy compression one can afford to do on such an image while still retaining legible text.  

1. Introduction
Many textual documents are best represented as images.  Examples include manuscripts of  historical importance, and official documents (such as a birth certificate).  Still more documents contain both text and images, such as advertisements and software screenshots.  In such cases simply extracting and digitizing the pure text using optical character recognition (OCR) does not preserve the essential characteristics of the document.  There is a substantial 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 solution taken by Adobe Acrobat is to extract fonts from the text and use these to recreate it, thus allowing it to be compressed as text rather than an image.  This is very effective but has a significant drawback, in that it requires a dedicated reader with a substantial overhead in memory and processing time.  If one takes the approach of compressing the document images as pure images, using standard techniques - such as wavelet compression or the DCT-based JPEG compression, it would be useful to know how much legibility will be incurred on the text at a given level of compression.  Then one can make an informed decision about how much to compress the document images you are serving based on you priorities.  An online archive of historical documents would be more sensitive to text legibility loss than a site showing computer game screenshots, for example.  

In order to learn how compression affects text legibility, I took a number of different document images and compressed them at various ratios, using both JPEG compression and a wavelet-based compression technique.  The implementations of both techniques are optimized to preserve text quality over image quality when compressing.  I then tested the text in the image using several different metrics for legibility.

2. Methods
All of the metrics I used are based primarily on luminance levels.  A strong, sharp contrast of luminance levels between text and background makes text readable.  Thus black text on a white background or white text on a black background is highly readable, while yellow text on a white background or blue text on a black background is not.  Compressing text tends to smear out this sharp contrast, bringing the luminance of background and text closer to the middle luminance levels, while creating a spread of luminance levels inbetween.  

I used a standard formula for luminance - given the R, G and B values of a given pixel, its luminance is 

		0.3R + 0.59G + 0.11B.  					(1)

This represents the fact that green appears substantially brighter than red, which in turn is much brighter than blue.  Since R, G and B are each 8 bit values, the final result is a floating point number between 0 and 255.  In all cases I only consider rectangular regions of the document image that were pure text; since I am only interested in text legibility and considering other regions would skew my legibility metrics.

The first metric tried was the total contrast range of the image.  If the maximum luminance in the region under considerition is maxL, the minimum is minL, and the total possible range is ΔL (i.e. 255), the total contrast is 

		(Lmax - Lmin)/ΔL    					(2)

This is an extremely simple metric, and a totally ineffective one.  A single stray black pixel and a single stray white pixel will give a contrast of 1.0 regardless of the rest of the image.

The second metric used was the entropy of the image.  This is a straightforward application of Shannon's entropy theorem to the image domain.  The first step is quantization, sorting the luminance values found in the region under consideration into 256 bins.  Thus if there are 100 pixels with luminance in the range [5, 6), the 5th bin will be set to 100.   Then the probability of a given luminance level L can be taken as the frequency with which L appears in the region, that is, the size of bin L over the total number of pixels.  The entropy is then defined as 
		         255
		H = - Σ p(Li) ln(p(Li))			(3)
		         i = 1
In the realm of image compression, entropy is generally used to measure loss of information - an image with lower entropy contains less information than one with higher information.  In the case of text legibility, however, low entropy can be seen as a good thing - crisp text contains only 2 luminance values, one for the text and one for the background.  Intermediate luminance values will be created by compression, which will increase the entropy of the region.

Finally I used a metric which I call bimodal contrast, which attempts to solve the problems of the total contrast measurement.   Plotting the frequency of each luminance level in a region of text on a curve, one would expect to see two modes, two strong local maxima, representing the text and the background.  As the text is blurred by compression, the strength of these modes is decreaesed, and they move closer together, reducing the contrast of the text.  The first problem is how to measure these modes.  I first bin the luminance into 255 bins, as in the entropy method above.  Simply taking the two highest local maxima in the luminance frequency bins fails due to local fluctuations.  So I first find the highest local maximum, and then consider that to be the center of a mode which stretches along the bins in both directions until the size of the bins falls below the average size (which is simply #pixels / #bins). [see Figure 1]  

	        Figure 1: How the modes are determined.

The second mode is then the highest local maximum that doesn't fall within the first mode.  The contrast is then simply 

		| Lmode1 - Lmode2 | / 255					(4)

Note that it is possible for there to be only one mode - the most degenerate case being if all the pixels fall within one luminance level.  In this case, the bimodal contrast is considered to be 0.0.  The contrast is then weighted by percentage of the pixels in the region contained in the area under both modes.  This prevents very small regions of intense dark and light from producing good contrast values for the whole region. 

3. Results
I performed my legibility metrics on rectangles of representative text from 8 different document images representing several different document image types - computer game screenshots, historical documents, and a book cover.  I collected results without compression, and for both wavelet and JPEG compression at 10:1, 20:1, 30:1, 50:1, 75:1 and 100:1 compression levels.

The results for total contrast, as mentioned above, proved meaningless.  The entropy of the text regions increased somewhat with higher compression rations in most cases using wavelet compression, but stayed steady or decreased under JPEG compression, as shown in Table 1.  This is likely due to the blocky nature of the images JPEG produces – large chunks of the same color will reduce entropy.  So entropy by itself does not appear to provide a useful measurement of legibility.

Compression Ratio	Avg. entropy under JPEG compression	Avg. entropy under wavelet compression	
 1 : 1	         4.289	          4.289	
 10 : 1	         4.702	          4.337	
 20 : 1	         4.676	          4.400	
 30 : 1	         4.605	          4.499	
 50 : 1	         4.557	          4.644	
 75 : 1	         4.354	          4.722	
 100 : 1	         4.088	          4.732	
     Table 1: The effect of compression on entropy

Bimodal contrast, on the other hand, shows promise.  The average results for that method are shown in Table 2.

Compression Ratio	 Avg. bimodal contrast under JPEG compression	Avg. bimodal contrast under wavelet compression	
 1: 1	          0.443	          0.443	
 10 : 1	          0.294	          0.365	
 20 : 1	          0.288	          0.338	
 30 : 1	          0.251	          0.269	
 50 : 1	          0.038	          0.265	
 75 : 1	          0.037	          0.198	
100 : 1	          0.035	          0.190	
      Table 2: The effect of compression on bimodal contrast

So within a given region, at different levels of compression with the same compression algorithm, the bimodal contrast decreases as compression increases, which implies that it decreases as legibility decreases, if we accept that increased compression decreases legibility.  Unfortunately bimodal contrast does not provide a general measure of legibility across images.  This can be seen in figure 2 below.    The image on the left has a bimodal contrast of 0.14, while the one on the right is 0.10, despite being far more legibile.

       Figure 2: A legibility comparison

This problem is due to differences in the size, color and shape of the original text.  In this case a greenish text and a yellowish background reduce the apparent contrast of the iamge on the right to the bimodal contrast algorithm, despite the text being quite legibile to the human eye. 

4. Conclusions and Future Work
The bimodal contrast metric for text legibility is by far the most promising of the three metrics used, but it still needs substanial improvement before it can be used as a general method for testing text legibility.  Normalizing for the size, shape and color of the original text, and taking into account a more accurate model of how the human eye functions (rather than the simplistic notion that legibility degrades linearly from high luminance contrast to low luminance contrast) will improve the metric’s performance.

To show that the method does indeed provide some general notion of legibility, it will need to be validated, relating it to a concrete and accepted notion of text legibility.  This could be done either via a human study - comparing perceived legibility to each of the metrics - or with OCR - comparing the error rate of an OCR algorithm with the legibility metrics.  If a linear relationship exists between a legibility metric and OCR error rate or human legibility perception, than that metric is definitely a useful one.  Further experiments could also be done to test the effect of other compression techniques on legibility, as well experiments with other legibility metrics.  One simple variant that would likely improve the bimodal contrast metric would be to add a notion of sharpness - weighting a tall, narrow mode higher than a short, wide mode.  

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] M. Eckert, A. Bradley, "Perceptual Models Applied to Still Image Compression," Signal Processing, Vol. 70, Issue 3, Pages 177--200, November 1998. 
[4] L. Leung, B. King, V. Vohara, "Comparison of Image Data Fusion Techniques Using Entropy and INI", 22nd Asian Conference for Remote Sensing, 2001, pp. 5-9
[5]  D. Mukherjee, N. Memon, A. Said, "JPEG-Matched MRC Compression of Compound Documents," International Conference on Image Processing, 2001, vol. 2,  pp. 434-437.
[6]  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.
[7] I. H. Witten, A. Moffat, T. C. Bell, Managing Gigabytes : Compressing and Indexing Documents and Images, Van Nostrand Reinhold, New York, 1994
[8]  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.