Memory Efficient Quadtree Wavelet Coding for Compound Images - eScholarship
Pamela C. Cosman, Tama´s Frajka, D. Schilling, K. Zeger · 1999
Memory Efficient Quadtree Wavelet Coding for Compound Images * Pamela Cosman, Tamhs Frajka, Dirck Schilling, and Kenneth Zeger Department of Electrical and Computer Engineering, University of California at San Diego 9500 Gilman Drive, San Diego, CA 92093-0407 email: { pcosman, frajka, dschilli, zeger) @code.ucsd.edu Abstract Wavelet-based image coders generally perform well on natural images, which are typically characterized by slowly varying image intensities. Their performance suffers, how- ever; on compound images containing both text and im- age data. We modify a quadtree wavelet coder to perform well on text image data by treating text blocks differently from nen-text blocks. We combine wavelet domain process- ing of non-,text blocks with spatial domain processing of text blocks, and achieve improved performance over purely wavelet domain techniques for compound images. 1. Introduction Text in an image can be far more visually important to a human viewer than might be deduced from summing the energy of the text pixels themselves. Distortion in the edges of text characters, caused by lossy compression of the im- age, can be more annoying than the same type of distortion in other areas of the image. Unfortunately, wavelet-based image coders suffer from just this deficiency when used on compound images. They often focus on improving low fre- queniy information while allowing high frequency edges, such as the sharp edges of text characters, to blur. In this paper, we present two variations on a quadtree wavelet-based coder designed for improved performance on compound images. We segment the image to identify blocks containing text, which are then treated specially. One coder operates entirely in the wavelet domain, apply- ing separate coding parameters to text and non-text blocks. In the second variation, the coder combines wavelet-domain processing of non-text blocks with spatial domain process- ing of text blocks. Both variations provide improved per- formance over standard wavelet methods when applied to compound images. This paper is organized as follows. In Section 2 we de- 'This work wils supported in part by the Hewlett Packard Co. scribe the text segmentation methods used with both coding approaches. In Section 3 we describe the first coder varia- tion, which operates entirely in the wavelet domain. The second variation, combining wavelet and spatial-domain coding, is discussed in Section 4. We present concluding remarks in Section 5 . 2 Text Segmentation Each of the coder variations we describe in this paper be- gins its processing by segmenting the input image into text and non-text blocks. Any block-based segmenter may be used for this purpose. Our implementation uses a relatively simple procedure based on decision trees. Training images are divided into 8 x 8 blocks. For each block, 11 parameters are computed from the 64 pixels in the block. Among these are the row variance, column variance, 3rd and 4th moments, and DCT coefficient energy. The CART (Classification and Regression Trees) algorithm [ I ] is then used to construct a binary decision tree based on the parameters computed from the training images. Each leaf node of the tree represents either a text or non-text outcome. At each stage in growing the tree, CART considers which node to split next by considering every parameter at each of the current leaf nodes. The node, parameter, and parameter decision threshold which yield the most accurate partition of the training data are determined, and that leaf node is split. CART grows a large tree, then employs optimal prun- ing to reduce it to the desired size. During segmentation, the necessary parameters are com- puted for an image block. The values are compared with the thresholds in the tree, starting at the top and progress- ing downward until a leaf node is reached. The resulting texthon-text decision is recorded, and the procedure is re- peated on the next block. Given the 8 x 8 block size, one bit per 64 pixels would be required to describe the segmentation map. This informa- tion is arithmetically encoded using a causal context of four neighbor blocks; it typically adds less than 0.01 bpp to the overall compressed bit rate. 0-7803-5700-0/99/$10.000 1999 IEEE