Dictionary design for text image compression with JBIG2

The JBIG2 standard for lossy and lossless bilevel image coding is a very flexible encoding strategy based on pattern matching techniques. This paper addresses the problem of compressing text images with JBIG2. For text image compression, JBIG2 allows two encoding strategies: SPM and PM&S. We compare in detail the lossless and lossy coding performance using the SPM-based and PM&S-based JBIG2, including their coding efficiency, reconstructed image quality and system complexity. For the SPM-based JBIG2, we discuss the bit rate tradeoff associated with symbol dictionary design. We propose two symbol dictionary design techniques: the class-based and tree-based techniques. Experiments show that the SPM-based JBIG2 is a more efficient lossless system, leading to 8% higher compression ratios on average. It also provides better control over the reconstructed image quality in lossy compression. However, SPM's advantages come at the price of higher encoder complexity. The proposed class-based and tree-based symbol dictionary designs outperform simpler dictionary formation techniques by 8% for lossless and 16-18% for lossy compression     

A chip set for lossless image compression

The authors describe two chips which form the basis of a high-speed lossless image compression/decompression system. They present the transform and coding algorithms and the main architectural features of the chips and outline some performance specifications. Lossless compression can be achieved by a transformation process followed by entropy coding. The two application-specific integrated circuits (ASICs) perform S-transform image decomposition and the Lempel-Ziv (L-Z) type of entropy coding. The S-transform, besides decorrelating the image, provides a convenient method of hierarchical image decomposition. The data compressor/decompressor IC is a fast and efficient implementation of the L-Z algorithm. The chips can be used independently or together for image compression     

Simple universal lossy data compression schemes derived from theLempel-Ziv algorithm

Two universal lossy data compression schemes, one with fixed rate and the other with fixed distortion, are presented, based on the well-known Lempel-Ziv algorithm. In the case of fixed rate R, the universal lossy data compression scheme works as follows: first pick a codebook B_n consisting of all reproduction sequences of length n whose Lempel-Ziv codeword length is ⩽nR, and then use B_n to encode the entire source sequence n-block by n-block. This fixed-rate data compression scheme is universal in the sense that for any stationary, ergodic source or for any individual sequence, the sample distortion performance as n→∞ is given almost surely by the distortion rate function. A similar result is shown in the context of fixed distortion lossy source coding     

Source coding, large deviations, and approximate pattern matching

We present a development of parts of rate-distortion theory and pattern-matching algorithms for lossy data compression, centered around a lossy version of the asymptotic equipartition property (AEP). This treatment closely parallels the corresponding development in lossless compression, a point of view that was advanced in an important paper of Wyner and Ziv in 1989. In the lossless case, we review how the AEP underlies the analysis of the Lempel-Ziv algorithm by viewing it as a random code and reducing it to the idealized Shannon code. This also provides information about the redundancy of the Lempel-Ziv algorithm and about the asymptotic behavior of several relevant quantities. In the lossy case, we give various versions of the statement of the generalized AEP and we outline the general methodology of its proof via large deviations. Its relationship with Barron (1985) and Orey's (1985, 1986) generalized AEP is also discussed. The lossy AEP is applied to (i) prove strengthened versions, of Shannon's(1948, 1974) direct source-coding theorem and universal coding theorems; (ii) characterize the performance of "mismatched" codebooks in lossy data compression; ( iii) analyze the performance of pattern-matching algorithms for lossy compression (including Lempel-Ziv schemes); and (iv) determine the first-order asymptotic of waiting times between stationary processes. A refinement to the lossy AEP is then presented, and it is used to (i) prove second-order (direct and converse) lossy source-coding theorems, including universal coding theorems; (ii) characterize which sources are quantitatively easier to compress; (iii) determine the second-order asymptotic of waiting times between stationary processes; and (iv) determine the precise asymptotic behavior of longest match-lengths between stationary processes. Finally, we discuss extensions of the above framework and results to random fields     

On the performance of data compression algorithms based upon stringmatching

Lossless and lossy data compression algorithms based on string matching are considered. In the lossless case, a result of Wyner and Ziv (1989) is extended. In the lossy case, a data compression algorithm based on approximate string matching is analyzed in the following two frameworks: (1) the database and the source together form a Markov chain of finite order; (2) the database and the source are independent with the database coming from a Markov model and the source from a general stationary, ergodic model. In either framework, it is shown that the resulting compression rate converges with probability one to a quantity computable as the infimum of an information theoretic functional over a set of auxiliary random variables; the quantity is strictly greater than the rate distortion function of the source except in some symmetric cases. In particular, this result implies that the lossy algorithm proposed by Steinberg and Gutman (1993) is not optimal, even for memoryless or Markov sources     

Lossless, near-lossless, and refinement coding of bilevel images

We present general and unified algorithms for lossy/lossless coding of bilevel images. The compression is realized by applying arithmetic coding to conditional probabilities. As in the current JBIG standard the conditioning may be specified by a template. For better compression, the more general free tree may be used. Loss may be introduced in a preprocess on the encoding side to increase compression. The primary algorithm is a rate-distortion controlled greedy flipping of pixels. Though being general, the algorithms are primarily aimed at material containing half-toned images as a supplement to the specialized soft pattern matching techniques that work better for text. Template based refinement coding is applied for lossy-to-lossless refinement. Introducing only a small amount of loss in half-toned test images, compression is increased by up to a factor of four compared with JBIG. Lossy, lossless, and refinement decoding speed and lossless encoding speed are less than a factor of two slower than JBIG. The (de)coding method is proposed as part of JBIG2, an emerging international standard for lossless/lossy compression of bilevel images.     

2D-pattern matching image and video compression: theory,algorithms, and experiments

We propose a lossy data compression framework based on an approximate two-dimensional (2D) pattern matching (2D-PMC) extension of the Lempel-Ziv (1977, 1978) lossless scheme. This framework forms the basis upon which higher level schemes relying on differential coding, frequency domain techniques, prediction, and other methods can be built. We apply our pattern matching framework to image and video compression and report on theoretical and experimental results. Theoretically, we show that the fixed database model used for video compression leads to suboptimal but computationally efficient performance. The compression ratio of this model is shown to tend to the generalized entropy. For image compression, we use a growing database model for which we provide an approximate analysis. The implementation of 2D-PMC is a challenging problem from the algorithmic point of view. We use a range of techniques and data structures such as k-d trees, generalized run length coding, adaptive arithmetic coding, and variable and adaptive maximum distortion level to achieve good compression ratios at high compression speeds. We demonstrate bit rates in the range of 0.25-0.5 bpp for high-quality images and data rates in the range of 0.15-0.5 Mbps for a baseline video compression scheme that does not use any prediction or interpolation. We also demonstrate that this asymmetric compression scheme is capable of extremely fast decompression making it particularly suitable for networked multimedia applications.     

An implementable lossy version of the Lempel-Ziv algorithm. I.Optimality for memoryless sources

A new lossy variant of the fixed-database Lempel-Ziv coding algorithm for encoding at a fixed distortion level is proposed, and its asymptotic optimality and universality for memoryless sources (with respect to bounded single-letter distortion measures) is demonstrated: as the database size m increases to infinity, the expected compression ratio approaches the rate-distortion function. The complexity and redundancy characteristics of the algorithm are comparable to those of its lossless counterpart. A heuristic argument suggests that the redundancy is of order (log log m)/log m, and this is also confirmed experimentally; simulation results are presented that agree well with this rate. Also, the complexity of the algorithm is seen to be comparable to that of the corresponding lossless scheme. We show that there is a tradeoff between compression performance and encoding complexity, and we discuss how the relevant parameters can be chosen to balance this tradeoff in practice. We also discuss the performance of the algorithm when applied to sources with memory, and extensions to the cases of unbounded distortion measures and infinite reproduction alphabets     

Lossless compression of VLSI layout image data.

We present a novel lossless compression algorithm called Context Copy Combinatorial Code (C4), which integrates the advantages of two very disparate compression techniques: context-based modeling and Lempel-Ziv (LZ) style copying. While the algorithm can be applied to many lossless compression applications, such as document image compression, our primary target application has been lossless compression of integrated circuit layout image data. These images contain a heterogeneous mix of data: dense repetitive data better suited to LZ-style coding, and less dense structured data, better suited to context-based encoding. As part of C4, we have developed a novel binary entropy coding technique called combinatorial coding which is simultaneously as efficient as arithmetic coding, and as fast as Huffman coding. Compression results show C4 outperforms JBIG, ZIP, BZIP2, and two-dimensional LZ, and achieves lossless compression ratios greater than 22 for binary layout image data, and greater than 14 for gray-pixel image data.     

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models

For pt. I see ibid., vol.46, p.755-88 (2000). The concept of context-free grammar (CFG)-based coding is extended to the case of countable-context models, yielding context-dependent grammar (CDG)-based coding. Given a countable-context model, a greedy CDG transform is proposed. Based on this greedy CDG transform, two universal lossless data compression algorithms, an improved sequential context-dependent algorithm and a hierarchical context-dependent algorithm, are then developed. It is shown that these algorithms are all universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet. Moreover, it is proved that these algorithms' worst case redundancies among all individual sequences of length n from a finite alphabet are upper-bounded by d log log n/log n, as long as the number of distinct contexts grows with the sequence length n in the order of O(n/sup a/), where 0 < /spl alpha/ < 1 and d are positive constants. It is further shown that for some nonstationary sources, the proposed context-dependent algorithms can achieve better expected redundancies than any existing CFG-based codes, including the Lempel-Ziv (1978) algorithm, the multilevel pattern matching algorithm, and the context-free algorithms in Part I of this series of papers.     

Embedded image coding using zerotrees of wavelet coefficients

The embedded zerotree wavelet algorithm (EZW) is a simple, yet remarkably effective, image compression algorithm, having the property that the bits in the bit stream are generated in order of importance, yielding a fully embedded code. The embedded code represents a sequence of binary decisions that distinguish an image from the “null” image. Using an embedded coding algorithm, an encoder can terminate the encoding at any point thereby allowing a target rate or target distortion metric to be met exactly. Also, given a bit stream, the decoder can cease decoding at any point in the bit stream and still produce exactly the same image that would have been encoded at the bit rate corresponding to the truncated bit stream. In addition to producing a fully embedded bit stream, the EZW consistently produces compression results that are competitive with virtually all known compression algorithms on standard test images. Yet this performance is achieved with a technique that requires absolutely no training, no pre-stored tables or codebooks, and requires no prior knowledge of the image source. The EZW algorithm is based on four key concepts: (1) a discrete wavelet transform or hierarchical subband decomposition, (2) prediction of the absence of significant information across scales by exploiting the self-similarity inherent in images, (3) entropy-coded successive-approximation quantization, and (4) universal lossless data compression which is achieved via adaptive arithmetic coding     

A lossless image compression algorithm using variable block sizesegmentation

The redundancy in digital image representation can be classified into two categories: local and global. In this paper, we present an analysis of two image characteristics that give rise to local and global redundancy in image representation. Based on this study, we propose a lossless image compression scheme that exploits redundancy both at local and global levels in order to obtain maximum compression efficiency. The proposed algorithm segments the image into variable size blocks and encodes them depending on the characteristics exhibited by the pixels within the block. The proposed algorithm is implemented in software and its performance is better than other lossless compression schemes such as the Huffman, the arithmetic, the Lempel-Ziv and the JPEG.     

超光谱图像的分布式压缩

针对超光谱图像压缩进行了研究,提出了一种有效的基于分布式信源编码(Distributed Source Coding, DSC)的有损压缩算法。该算法利用多元陪集码和标量量化的方式实现超光谱图像的分布式有损压缩,针对分布式信源编码,利用多波段预测的方式为每个编码块构造边信息,然后采用标量量化的方式对编码块和其边信息同时进行量化处理。根据分布式信源编码原理,给出了各编码块量化后的编码码率。为了减少标量量化带来的信息丢失,算法引入了跳跃策越。部分均方误差意义上损失较大的编码块将由其边信息直接代替。实验结果表明,所提出的算法性能与基于小波变换的算法性能相当;此外,该算法复杂度较低,适合星载超光谱图像的压缩。     

A suboptimal lossy data compression based on approximate patternmatching

A practical suboptimal (variable source coding) algorithm for lossy data compression is presented. This scheme is based on approximate string matching, and it naturally extends the lossless Lempel-Ziv (1977) data compression scheme. Among others we consider the typical length of an approximately repeated pattern within the first n positions of a stationary mixing sequence where D percent of mismatches is allowed. We prove that there exists a constant r₀(D) such that the length of such an approximately repeated pattern converges in probability to 1/r₀(D) log n (pr.) but it almost surely oscillates between 1/r_-∞(D) log n and 2/r₁(D) log n, where r _-∞(D)>r₀(D)>r₁(D)/2 are some constants. These constants are natural generalizations of Renyi entropies to the lossy environment. More importantly, we show that the compression ratio of a lossy data compression scheme based on such an approximate pattern matching is asymptotically equal to r₀(D). We also establish the asymptotic behavior of the so-called approximate waiting time N_l which is defined as the time until a pattern of length C repeats approximately for the first time. We prove that log N_l/l→r₀(D) (pr.) as l→∞. In general, r₀(D)>R(D) where R(D) is the rate distortion function. Thus for stationary mixing sequences we settle in the negative the problem investigated by Steinberg and Gutman by showing that a lossy extension of the Wyner-Ziv (1989) scheme cannot be optimal     

Simplistic universal coding

A conceptually simple coding method may be described as follows. The source sequence is parsed into fixed-length blocks and a list of these blocks is placed in a dictionary. In the lossless case, the dictionary is transmitted and each successive block is encoded by giving its dictionary location. In the lossy case, the smallest collection of blocks such that every member of the dictionary is within distortion δ of the collection is determined, this codebook is transmitted, and each successive block is encoded by giving the location of a member of the code within δ of it. We show that by optimizing on the block length, this method is universal, that is, for any ergodic process it achieves entropy in the limit in the lossless case and the rate-distortion function R(δ) in the lossy case     

Wavelet-based lossy-to-lossless ECG compression in a unified vector quantization framework

In a prior work, a wavelet-based vector quantization (VQ) approach was proposed to perform lossy compression of electrocardiogram (ECG) signals. In this paper, we investigate and fix its coding inefficiency problem in lossless compression and extend it to allow both lossy and lossless compression in a unified coding framework. The well-known 9/7 filters and 5/3 integer filters are used to implement the wavelet transform (WT) for lossy and lossless compression, respectively. The codebook updating mechanism, originally designed for lossy compression, is modified to allow lossless compression as well. In addition, a new and cost-effective coding strategy is proposed to enhance the coding efficiency of set partitioning in hierarchical tree (SPIHT) at the less significant bit representation of a WT coefficient. ECG records from the MIT/BIH Arrhythmia and European ST-T Databases are selected as test data. In terms of the coding efficiency for lossless compression, experimental results show that the proposed codec improves the direct SPIHT approach and the prior work by about 33% and 26%, respectively.     

Adaptive lossy LZW algorithm for palettised image compression

An adaptive lossy LZW algorithm is proposed for palettised image compression, that is a generalised algorithm of the conventional lossless LZW algorithm. The new algorithm employs an adaptive thresholding mechanism with human visual characteristics to constrain the distortion. With this distortion control, the compression efficiency is increased by ~40% for natural colour images, while maintaining good subjective quality on the reconstructed image. In addition, the encoded image file format is compatible with the original GIF decoder     

An improved wavelet-based image coder for embedded greyscale and colour image compression

The embedded zero-tree wavelet (EZW) coding algorithm is a very effective technique for low bitrate still image compression. In this paper, an improved EZW algorithm is proposed to achieve a high compression performance in terms of PSNR and bitrate for lossy and lossless image compression, respectively. To reduce the number of zerotrees, the scanning and symbol redundancy of the existing EZW; the proposed method is based on the use of a new significant symbol map which is represented in a more efficient way. Furthermore, we develop a new EZW-based schemes for achieving a scalable colour image coding by exploiting efficiently the interdependency of colour planes. Numerical results demonstrate a significant superiority of our scheme over the conventional EZW and other improved EZW schemes with respect to both objective and subjective criteria for lossy and lossless compression applications of greyscale and colour images.     

Wavelet coding of volumetric medical datasets

Several techniques based on the three-dimensional (3-D) discrete cosine transform (DCT) have been proposed for volumetric data coding. These techniques fail to provide lossless coding coupled with quality and resolution scalability, which is a significant drawback for medical applications. This paper gives an overview of several state-of-the-art 3-D wavelet coders that do meet these requirements and proposes new compression methods exploiting the quadtree and block-based coding concepts, layered zero-coding principles, and context-based arithmetic coding. Additionally, a new 3-D DCT-based coding scheme is designed and used for benchmarking. The proposed wavelet-based coding algorithms produce embedded data streams that can be decoded up to the lossless level and support the desired set of functionality constraints. Moreover, objective and subjective quality evaluation on various medical volumetric datasets shows that the proposed algorithms provide competitive lossy and lossless compression results when compared with the state-of-the-art.