A Hybrid Lossless-Lossy Binary Image Compression Scheme

A Hybrid Lossless-Lossy Binary Image Compression Scheme

Saif alZahir (Department of Computer Science, University of North British Columbia, Prince George, Canada) and Syed M. Naqvi (Department of Computer Science, University of North British Columbia, Prince George, Canada)
Copyright: © 2013 |Pages: 14
DOI: 10.4018/ijcvip.2013100103
OnDemand PDF Download:
List Price: $37.50


In this paper, the authors present a binary image compression scheme that can be used either for lossless or lossy compression requirements. This scheme contains five new contributions. The lossless component of the scheme partitions the input image into a number of non-overlapping rectangles using a new line-by-line method. The upper-left and the lower-right vertices of each rectangle are identified and the coordinates of which are efficiently encoded using three methods of representation and compression. The lossy component, on the other hand, provides higher compression through two techniques. 1) It reduces the number of rectangles from the input image using our mathematical regression models. These mathematical models guarantees image quality so that rectangular reduction should not produce visual distortion in the image. The mathematical models have been obtained through subjective tests and regression analysis on a large set of binary images. 2) Further compression gain is achieved through discarding isolated pixels and 1-pixel rectangles from the image. Simulation results show that the proposed schemes provide significant improvements over previously published work for both the lossy and the lossless components.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 7: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2015)
Volume 4: 2 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing