Context quantization for adaptive entropy coding in image compression

Context based adaptive entropy coders are used in newer compression standards to achieve rates that are asymptotically close to the source entropy: separate arithmetic coders are used for a large number of possible conditioning classes. This greatly reduces the amount of sample data available for learning. To combat this problem, which is referred as the context dilution problem in the literature, one needs to balance the benefit of using high-order context modeling and the learning cost associated with context dilution. In the first part of this dissertation, we propose a context quantization method to attack the context dilution problem for non-binary source. It begins with a large number of conditioning classes and then uses a clustering procedure to reduce the number of contexts into a desired size. The main operational difficulty in practice is how to describe the complex partition of the context space. To deal with this problem, we present two novel methods, coarse context quantization (CCQ) and entropy coded state sequence (ECSS), for efficiently describing the context book, which completely specifies the context quantizer mappings information. The second part of this dissertation considers binarization of non-binary sources. Same as non- binary source, the cost of sending the complex context description as side information is very high. Up to now, all the context quantizers are designed off-line and being optimized with respect to the statistics of the training set. The problem of handling the mismatch between the training set and an input image has remained largely untreated. We propose three novel schemes, minimum description length, image dependent and minimum adaptive code length, to deal with this problem. The experimental results show that our approach outperforms the JBIG and JBIG2 standard with peak compression improvement of 24% and 11% separately on the chosen set of halftone images. In the third part of this dissertation, we extend our study to the joint design of both quantizers and entropy coders. We propose a context-based classification and adaptive quantization scheme, which essentially produce a finite state quantizer and entropy coder with the same procedure.