Research Document Imaging Image Compression Previous Work

Search

Previous Work in Image Compression
Dr. Eugene Ageenko

The Compression understood as a joint process of Modeling and Coding [RL81].

The initial advancements in compression of one-dimensional signals extended to the image domain by concatenating the image pixels in a single stream in an appropriate order. Run-length encoding (RLE) replaces the runs of same-colored pixels by two numbers: color and length of the run [Cap59].

Sophisticated pixel-ordering techniques for one-dimensional sequential compression [NW80].

Statistical approaches are based on modeling the image according to the probability distribution of the pixel values. Shannon-Fano [Sh48], Huffman coding [Huf52, Vit87] and integral codes [Col66, Ric79, Will91] assign shorter codes to more frequent pixel color values and vice versa, as for example in a Morse alphabet.

The Huffman encoding process is usually very fast and not complex. However, because of the integral property, the probability distribution of the code does not necessarily match the distribution of the source. Modified Huffman (MH) algorithm applies Huffman code, not directly to the pixels, but to runs of pixels [ITU T.4, Hun80].

The following techniques have been developed to take advantage of a two-dimensional correlation between the image lines:

• Vector run-length coding [WW92] applies run-length coding two-dimensionally to m by n-sized blocks of pixels, instead of to single pixels. 
• The block coding [KJ80] divides the image into rectangular blocks of pixels. A totally white block is coded by a single 0-bit, whereas all other blocks are coded by a 1-bit as a prefix, followed by the content of the block. The process can be iterated, resulting in a hierarchical block coding algorithm. 
• This technique has been improved by encoding the bit patterns of the 2x2-blocks with Huffman codes. 
• Another improvement has been achieved using the prediction technique [NW80]. The idea is to form a so-called error image from the original one, by comparing the value of each original pixel to the value given by a prediction function. If these two are equal, the pixel of the error image is set to white, otherwise to black. The encoding is then applied to the error image instead of to the original one, and gains were achieved from the increased number of white pixels [FN95].

Another approach is to exploit the correlation between successive lines of the image. Relative element address designate (READ) method encodes the location of the boundaries of the runs (point of transitions from black to white and vice versa) relative to the corresponding positions in the previous line. If there are no such positions within three pixels in the reference line, one-dimensional run-length coding is used [ITU T.4].

An arithmetic coding invented by Rissanen and Langdon [RL79]. It represents the entire input message as a small interval in the range [0,1]. The resulting codeword is the binary code representation of the interval. Arithmetic coding is an optimal coding method as regards the model. It has no limitation of integral codes and suits for compression of binary images. It is also well suited for dynamic modeling, because there is no need to store and update complex data structures such as Huffman trees.

Rissanen and Langdon proposed to use Shannon’s context-based statistical modeling conjunction with arithmetic coding [LR81]. The idea of context-based modeling is to obtain the statistical model of the image by conditioning the probability distribution of the pixels on the context. The context is determined by the combination of the pixels in the local neighborhood, which is defined by the template. 

Context-based statistical modeling and arithmetic coding are implemented in the international standard for compression of binary images in communications JBIG (Joint Bi-level Image Experts Group) [JBIG1].

The solutions for multi-tone and grayscale image compression were presented by separating the images into bit-planes [WRA96, JKW98]. 

Another approach to deal with multi-tone images has been developed by At&T and is called "DjVu". It classifies the pixels of the image either as foreground (text, drawings) or background (pictures, photos, paper texture). The classification is compressed as a binary image, whereas a progressive, wavelet-based lossy compression technique is applied to the foreground and background images [Haf+99].

Moffat has experimented with various sizes and shapes of the context templates in order to improve the image compression [Mof91]. Although observing the limitations for the size of the context template (~14 pixels), he has demonstrated the potential of larger templates of up to 24 pixels and has proposed the two-level modeling technique using both 10- and 24-pixel templates. 

The variable-size modeling based on a context tree has been introduced by Rissanen in [Ris83]. Martins and Forchhammer have recently studied variable-size context modeling and proposed both context tree and "free tree" techniques, were they varied the number and the positions of the context pixels depending on the pixel neighborhood [MF98].

Remarkable improvements in image compression have been achieved by specializing in some known image types (e.g. text images) and exploiting global dependencies. The emerging standard JBIG2 [JBIG2] segments a page into different classes of image data, in particular, textual, halftone and generic (other) [TK99], and utilize the repetitive nature of the textual and halftone images. JBIG2 will also provide lossy image compression [MF99], and quality and content progressive coding [How+98].

For textual data, JBIG2 uses pattern matching techniques, which are based on the following works:

• Pattern matching technique to extract symbol and mark bitmaps from the image into the dictionary [AN74].
• Witten et al. expanded on this approach to address the extraction of marks, indexing their location within the image, compressing the indices, and coding the residuals left after the replacement of marks by library prototypes [IW94, WMB94].
• Soft pattern matching, compressing the original image instead of the residual, and uses the image composed of prototypes in improved context modeling [How97].

JBIG2 will also address the compression of halftone image data using either of the two following methods:

• The one similar to JBIG1, but with larger context templates (up to 16 pixels) with multiple adaptive pixels [MF98, 99]. The larger templates are intended to exploit specific types of redundancies that exist in halftone images.
• The second method involves de-screening the halftone image (converting it back to grayscale) and transmitting the grayscale values [VETK99, FJ94].

References.