Image Processing: Lossy Compression by Color Quantization and GCT Modeling

------------------------------------------♦----------------------------------------- 1. INTRODUCTION

In addition to raster maps, which are converted from vector databases, there is another class of scanned map images. Digitizing printed-paper maps produces these images. Scanned map imagery unintentionally combines the properties of natural imagery and converted raster maps. Edges and details on a scanned map are smooth since the image is acquired with a physical sensor of the scanner. Besides this, a scanned map image may have special patterns such as dithering. The number of paints available in typography is limited and color gradation is usually represented as a pattern of color dots. These structures are acquired by a scanner and appear in the scanned map image.One can see that the distribution does not contain clear centroids. For example, the water pixels, which are supposed to be grouped around a dominant blue color, are actually a mix of blue and white clouds due to the dithering effects. The same holds for the yellow fields. For the whole image this effect makes the distribution uniformly spread. We consider map imagery as a class of images with distinctive properties separating them from photographic, computer generated or other classes of images. Digital map images (both scanned and converted) are widely used among a great variety of users worldwide. However, general purpose algorithms rarely take the properties of this kind of imagery into account. The work in this study is motivated by the fact that better understanding of the properties of map images together with 4 designing and optimization of algorithms exploiting these features can make map image processing and compression algorithms more efficient. This study is aimed at two specific topics. The first topic of the study is layer wise map image processing for reconstruction and compression. In paper P1, lossless compression is improved by trying to reconstruct the semantic layers of the map. In paper P2, bit plane separation and binary context-based compression of natural and palette images are studied. The second topic is dedicated to context tree (CT) modeling. In paper P3, we apply highly optimized CT modeling for the progressive loss-to-lossless compression of map images. In paper P4, we propose a CT filter for improving the quality of noisy map images. In paper P5, we generalize the method for loss compression of scanned maps. Compression algorithms can be separated into two classes: lossless and loss algorithms (TIFF Revision, 1992) (ITU-T Recommendation, 1993) (Rissanen, Langdon, 1979). Lossless compression assumes that the data before and after the compression-decompression process is equal, i.e. no loss of information occurs. In contrast, lossy compression makes no such assumption, and allows distortion to happen. This is essential in those situations where some degradation of the data is tolerable for the benefit of better compression efficiency. The algorithms of the first type (lossless) are used in applications where information loss is not acceptable, e.g. compression of text, programs and executable code. In image compression, lossless compression can be used for compression of medical images, engineering drawings and circuits. The algorithms of the second type (lossy) are applied in photographic image, audio and video compression because minor degradation can be tolerated if it‟s visually

Available online at www.ignited.in Page 2

not perceptible, and because lossless methods alone are inefficient for this type of data.

The rapid evolution of advanced wireless communication systems has been driven in recent years by the growth of wireless packet data applications such as mobile multimedia and wireless streaming services. In particular, image and video applications are among those services that facilitate communication beyond the traditional voice services. The large amount of data that is needed to represent the visual content and the scarce bandwidth of the wire- less channel constitute a difficult system design framework. In addition, the largely heterogeneous network structures and the time variant fading channel make wireless networks much more unpredictable as compared to their wired counterparts. One of the major challenges with these services is therefore the design of networks that the stringent Quality of Service (QoS) requirements of wireless image and video applications. In order to monitor the quality of the wireless communication services, appropriate metrics are needed that are able to accurately quantify the end-to-end visual quality as perceived by the user. Traditional link layer metrics such as signal-to-noise ratio (SNR) and bit error rate (BER) have been shown to be unable to reflect the subjectively perceived quality (J. Ziv, A. Lempel, 1977). Considering the above, new paradigms in metric design for wireless image and video quality assessment need to be established. This study aims at contributing to this goal by developing objective perceptual quality metrics that are able to accurately quantify end-to-end visual quality of wireless communication services. The metrics are based on spatial feature extraction algorithms that may be applied to images and also to videos on a frame-by-frame basis. The resulting metrics can then be utilized to perform efficient link adaptation and resource management techniques to fulfill the aforementioned QoS requirements. This introduction aims to briefly familiarize the reader with the field of visual quality assessment and provide an overview of the scope of this study as follows. Section 1 gives a general overview of visual quality assessment. In The visual system may be considered the most eminent human sense to gain information from the outside world (Ziv, Lempel, 1978). Without our sight we would live in darkness and would not be able to appreciate the beauty of the world around us. During all phases of human evolution our eyes were adapted to observing a natural environment. This has changed only during the last decades with the deployment of many visual technologies, such as television, computer screens, and most recently personal digital assistants (PDA) and mobile phones. These technologies now strongly influence our everyday work and private life. Hence, we are not only used to just looking at the natural

The class of scanned raster map images is commonly used in navigational applications in cases when vector map is not available. A scanned map image combines the properties of both the natural class and artificial imagery class. They originally contain only a few colors, sharp edges and small details. After the scanning, however, this image is corrupted by noise caused by the acquisition sensor imposing blurring and other inconsistencies. Therefore, neither traditional lossy image compression algorithms like JPEG and JPEG2000, nor lossless image compression techniques like PNG are well suited for scanned maps. In P5, we propose an algorithm for lossy map image compression based on Median Cut (CCITT, 1984) color quantization and generalized context tree modeling (GCT); the overall scheme. Samples representing the quality provided by the proposed technique are presented in Figure 10. The upper row represents 0.72 bit per pixel compression results, and the artifacts and blurring imposed by JPEG2000 along the edges are clearly seen. The corresponding image provided by the proposed algorithm is free from these artifacts. The lower row represents a higher quality level for the proposed technique using 256 colors. Although any difference with JPEG2000 is hardly visible, the objective measurement shows one advantage of the proposed algorithm. In general, when comparing images at a similar objective quality level the proposed algorithm provides up to 50% better compression efficiency than JPEG2000.

Available online at www.ignited.in Page 3

Although any difference with JPEG2000 is hardly visible, the objective measurement shows one advantage of the proposed algorithm. In general, when comparing images at a similar objective quality level the proposed algorithm provides up to 50% better compression efficiency than JPEG2000.

Image filtering aims at reconstructing the original image before degradation (Pennebaker, Mitchell, 1988) [G. G. Langdon and J. Rissanen (1981) (Rissanen, 1983) (ITU-T Recommendation, 2000). As a rule, the reconstruction involves a criterion for measuring the quality of the desired result. There are two different approaches for the quality measurement: objective and subjective. Objective quality measurement assumes that it is possible to establish an objective metric. The most common examples of these metrics are MSE and peak signal-to-noise ratio (PSNR). The objective measurement measures a „distance‟ between the original image and the result of reconstruction. This is possible when the original image is available for measurement, which is not always the case. Another approach is subjective quality estimation. In the case when the uncorrupted image is not available, one can estimate the restoration quality by subjective observations of the reconstructed image. This approach is less analytical than the first one and, therefore, less popular. Besides the two above-mentioned approaches, different performance evaluation methods can be defined. For example, in P1 we use image compressibility as a quality evaluation criterion. Linear filtering is an approach that has been widely used since the beginning of the computer era. The filter replaces a pixel with a linear combination of its neighbors combining the simplicity of implementation with robustness to various tasks from smoothing to edge detection. Linear filters, however, are not well suited for filtering of map images since the imposed smoothing is not (always) tolerable. Linear filters homogeneously process all pixels, which is another drawback for a filtering of images consisting of complex structures. Later, a great variety of more general non-linear filtering algorithms were considered. In the early sixties, the investigations of Matheron and Serra led to a new quantitative approach in image analysis, now known as mathematical morphology (Howard et. al., 1998) (Wu, Memon, 1997) (Wu, 2000). The central idea of mathematical morphology is to examine the geometrical structure of an image by matching it with small patterns at various locations in the image. By varying the size and shape of the matching pattern, called structuring element, one can obtain useful information about the shape of the different parts of the image and their interrelations. Flexibility of the concept allows various filters to be designed (ISO/IEC, 1998) (Ajay Babu Sriramoju, 2011)] (Weinberger (2000) (Golomb, 1966). Mathematical morphology is widely applied in various disciplines such as mineralogy, medical diagnostics, machine vision, pattern recognition, granulometry and others. There exists a great variety of heuristically filtering approaches, which exploit knowledge about the noise. For example, edge preserving filters are trying to smooth uniform areas while keeping the edges untouched. One of the most popular edge preserving filtering methods is vector median filter (VM), which is a non-linear operator. The filter replaces the current pixel value with a value called vector median defined in a local neighborhood. An attempt to design a filter that would be invariant to the features of the particular image was made in (Golomb, 1966). The filter is called rank-conditioned vector median filter or adaptive vector median filter (AVM), and it uses a noise detector before applying VM. An overview of weighted median filters can be found in (Ajay Babu Sriramoju, 2011).

Ajay Babu Sriramoju (2011). “Analysis on Lossless Image Compression in Image Processing”, International Journal of Information Technology and Management, vol. I, Issue No. I, ISSN 2249-4510 D. Huffman (1952). “A method for the construction of minimum-redundancy codes”, Proceedings of the I.R.E., pp. 1098-1102. G. G. Langdon and J. Rissanen (1981). “Compression of black-white images with arithmetic coding,” IEEE Trans. on Communications, vol. 29, no. 6, pp. 858-867. International Telegraph and Telephone Consultative Committee (CCITT) (1984) . “Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus,” Recommendation T.6.

Available online at www.ignited.in Page 4

ISO/IEC JTC1/SC29/WG1 (1998). “JPEG-LS part-2 WD.” ISO/IEC JTC1/SC29/WG1 N938. ITU-T recommendation T. 82 (1993). “Information technology – coded representation of picture and audio information – progressive bi-level image compression”. ITU-T recommendation T.88 (2000). “Information technology – coded representation of picture and audio information – lossy/lossless coding of bi-level images”. J. J. Rissanen, Langdon G. G. (1979). “Arithmetic coding”, IBM Journal of Research, Development 23: 146-162. J. Rissanen (1983). “A universal data compression system”, IEEE Trans. on Information Theory, vol. 29 (5), pp. 656–664. J. Ziv, A. Lempel (1977). “A universal algorithm for sequential data compression”, IEEE Trans. on Information Theory, vol. 23(6), pp. 337-343. J. Ziv, A. Lempel (1978). “Compression of individual sequences via variable rate coding”, IEEE Trans. on Information Theory, vol. 24(5), pp. 530-536. M. Weinberger, G. Seroussi, G. Shapiro (2000). “The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS”, IEEE Trans. on Image Processing, vol. 9 (8), pp. 1309–1324. P. Howard, F. Consenting, B. Martins, S. Forchhammer, W. Rucklidge (1998). “The emerging JBIG2 standard”, IEEE Trans. On Circuits and Systems for video technology, vol. 8(7), pp. 838-848. S.W. Golomb (1966). “Run-length encodings”, IEEE Transactions on Information Theory, vol. 12(3), pp. 399-401. TIFF Revision 6.0 (1992). Adobe Developers Association, Adobe System Incorporated. http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf. W. Pennebaker, J. Mitchell (1988). “Probability estimation for the Q-coder”, IBM Journal of Research, Development 32(6), pp. 737-759. X. Wu, N. Memon (1997). “Context-based, adaptive, lossless image coding”, IEEE Trans. on communications, 45(4), pp. 437-444. X.Wu (2000). “L–constrained high fidelity image compression via adaptive context modelling”, IEEE Trans. on Image Processing, 9, 536-542.