Group testing for image compression

Abstract

This thesis studies the application of group testing to image compression. Group testing is a technique used for identifying a few significant items out of a large set. Image compression studies techniques for making image data take up less storage space. We first explain the many interesting and deep connections between image compression and group testing, and then demonstrate the effectiveness of group testing techniques for image compression, from both practical and theoretical points of view.In particular, we show that group testing is a generalization of the zerotree coding method widely used in wavelet-based image compression. We also show the equivalence of elementary Golomb codes and the binary splitting procedure used in Hwang's generalized group testing method. Next, we present new image coding techniques based on transform coding which apply group testing to the output of different transforms. We present one new image coder for each type of transform we study, namely: the wavelet transform; the wavelet packet transform; and block transforms such as the discrete cosine transform and lapped transforms. Group testing's flexibility and usefulness is shown in its applicability to many different transforms. In terms of compression performance, these new algorithms are competitive with many recent state-of-the-art image coders that use the same transforms on a wide variety of images.We also present a study on the theoretical performance of group testing on correlated Markov sources. We show how images can be modeled by these Markov sources, and relate these theoretical performance results to the performance of group testing on image compression.