Article Preview
Top1. Introduction
Digital image compression is concerned with reducing the amount of bits in a digital image either for transmission or storage requirements. These requirements are becoming imperative due to the advent and rapid spread of the Internet. There have been developed several standards for image compression to standardize compression/decompression process (AlZahir, 2011; Sikora, 2005). A class of image compression techniques is concerned with the storage and transmission of two-tone, binary images. The importance of binary image compression is becoming indispensable due to the enormous amount of images that are being processed and stored in a wide range of applications such as in digital libraries, e-learning, fingerprints, cartography, banking, insurance companies, e-government just to name a few. These binary images are encountered in different formats and extensions.
Most of binary image compression techniques are lossless. Lossless compression results in reproducing exactly the same as the original data with low compression ratio. Lossless coding techniques are also called reversible coding. These techniques are usually applied in such an environment where even a slight loss in the original data cannot be tolerated. Huffman codes, Lempel-Ziv codes, and arithmetic codes are some examples of lossless compression. These compression techniques exploit redundancies that are present in the form of a single tone (or color) on most part of the image, and high correlation of adjacent pixels (Algazi, Phillip, & Robert, 1990). Source coding techniques exploit these redundancies either along with single scan line (1-D) or many scan lines (2-D) (Witten, Moffat, & Bell, 1999).
Lossy binary image compression techniques provide higher compression ratios at the expense of some distortion of the original data. In these techniques, some information is discarded permanently from the image. Lossy compression techniques are also called irreversible coding techniques, because the discarded data can never be reproduced again. Differential pulse code modulation, vector quantization, and block truncation coding are some examples of lossy compression techniques.
The edges or boundary points between the black and the white areas (objects) of a binary image contain the entire information about the image (Cederberg, 1979). For example, if the boundary points are known, we can fill inside the boundaries with black or white pixels and reconstruct the image. Therefore, some of the binary image compression techniques achieve compression through reducing the redundant boundary points and then efficiently encoding the coordinates of the selected boundary points. A method that can be used to reduce the boundary points is to cover a region with geometrical shapes where the objective is to best fit the region with these parameterized shapes (Bucklew & Sethares, 1994; AlZahir, El-Maleh, & Khan, 2001). One method of covering is to partition a region with the minimum number of rectangles (AlZahir & Naqvi, 2005). After having partitioned the matrix into rectangles, the redundant boundary points can be discarded keeping only two opposite diagonal vertices of each rectangle to reconstruct the whole rectangle again as shown in Figure 1.
Figure 1. (left) Binary image; (right) labeled vertices for each rectangle, and isolated pixel with unique symbols
The resultant rectangles can be overlapping or non-overlapping rectangles. The rectangles produced in non-overlapping partitioning schemes have the characteristic that each rectangle has its upper-left and lower-right vertices closest to each other column-wise, if scanned in a raster scan format (Mohamed & Fahmy, 1995). The proposed scheme is based on rectangular shapes representation of images.