Browse Prior Art Database

A NOVEL APPROACH TO COMPRESSING BI-LEVEL IMAGES

IP.com Disclosure Number: IPCOM000007608D
Original Publication Date: 1996-May-01
Included in the Prior Art Database: 2002-Apr-09
Document File: 7 page(s) / 486K

Publishing Venue

Motorola

Related People

Zaffer Merchant: AUTHOR

Abstract

One area ofgrowing interest is the ability to send a printed document containing dithered (half-tone) images, such as in newspaper articles and reports, from a fax machine to a wireless device equipped with a monochrome or color LCD screen. A major goal ofportable wireless communications is to reduce the tile size for transmission and storage of such services. This paper describes a novel method for compressing bi-level images beyond that achievable by standard techniques, Continuous-tone grey-level images are commonly used in computers and included in newspapers, arti- cles, reports and documents. In computers equipped with LCD screens it is relatively common to be able to display up to 256 shades of grey color. However, most printed media do not render the image using colors that are shades ofgrey but instead use a tech- nique called half-toning. In half-toning a grey pixel is represented using a block ofpixels where the vis- ual perception of various shades of grey is achieved by different distributions of only black and white pixels (no grey) in the block.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 37% of the total text.

Page 1 of 7

M-ROLA Technical Developments

A NOVEL APPROACH TO COMPRESSING BI-LEVEL IMAGES

by Zaffer Merchant

ABSTRACT

  One area ofgrowing interest is the ability to send a printed document containing dithered (half-tone) images, such as in newspaper articles and reports, from a fax machine to a wireless device equipped with a monochrome or color LCD screen. A major goal ofportable wireless communications is to reduce the tile size for transmission and storage of such services. This paper describes a novel method for compressing bi-level images beyond that achievable by standard techniques,

INTRODUCTION

  Continuous-tone grey-level images are commonly used in computers and included in newspapers, arti- cles, reports and documents. In computers equipped with LCD screens it is relatively common to be able to display up to 256 shades of grey color. However, most printed media do not render the image using colors that are shades ofgrey but instead use a tech- nique called half-toning. In half-toning a grey pixel is represented using a block ofpixels where the vis- ual perception of various shades of grey is achieved by different distributions of only black and white pixels (no grey) in the block.

  Most compression techniques for bi-level images are lossless: that is they render the image exactly. The most common technique for lossless coding of images, and one that is used in fax transmission, is Hutlinan coding ofthe runs of black and white pixels. Hufhnan coding takes advantage of the statistical properties of the message and generates variable- length codewords where the length of the code associated with a message is related to the message probability; messages with high probability have short codewords and messages with low probability have long codewords. A Huffman code can be designed such that the average bit-rate is minimized and can get arbitrarily close to the signal entropy. The entropy is the theoretically minimum possible average bit

rate required in coding a message.

  Figure 3a is a dithered bi-level image of size 480x512 pels. The entropy was calculated to be 0.74 bits/pixel (bpp). A Huffman code can be designed to approach this value, but it is obvious that not much can be gained, since the uncoded rate for this image is 1 bpp.

  As mentioned earlier, bi-level images in docu- ments and faxes, are mostly dithered versions of multi-level grey and color images. FurthermoreY most applications using multi-level images, including fax, do not require that they be rendered exactly, and in fact commonly use lossy compression algorithms such as JPEG and Subband coding. Lossy compres- sion algorithms can achieve significant reduction in bit rate over lossless compression and can be expected to be in the range of 0.3-0.5 bpp for continuous tone images. Since bi-level images are derived from multi- level images, it seems reasonable to assume that it is not essential that bi-level images be rendered exactly either. The method being proposed is a gen-...