Lossy data compression methods for halftoned and printed images

This dissertation describes how lossy data compression algorithms can be tailored for applications in which digital images are halftoned for bi-level printing or display. The goal is to improve the speed and efficiency of these imaging applications by reducing the amount of data needed to represent an image, without causing any serious degradation in image quality. Conceptually, there are three different strategies for adding data compression to an image processing system that includes halftoning: the compression step can occur before halftoning, after halftoning, or in combination with halftoning. The central purpose of this dissertation is to demonstrate that in all three cases, it is beneficial to design the compression algorithm based on knowledge about the halftoning algorithm that accompanies it in the processing sequence.;Because halftoning figures prominently in all of this work, a tutorial overview is provided at the outset, with explanations of popular halftoning techniques and examples of the images they produce. The remainder of the dissertation is devoted to descriptions of prototype compression and halftoning systems that represent the three possible implementation strategies mentioned above. First, the halftoning and compression operations are combined by using vector quantization with binary-valued reproduction vectors. Next, for compression of continuous-tone images prior to halftoning, a JPEG-compliant coder is developed, taking into account the characteristics of the human visual system and the bi-level rendering procedure. Finally, two new high-speed algorithms, based on the well-known principles of run-length coding and predictive coding, are proposed for compressing images that have already been halftoned. The discussion of each prototype system addresses practical implementation issues as well as theoretical motivation. Experimental results are also included to illustrate each system's performance advantages relative to competing compression schemes.