Progressive Source Coding by Matching Pursuit: Application in Image and Gaussian Data Compression - Shoa, Alireza (My University, 2009)
Conventional image compression algorithms use transform coding to achieve a compact representation of the image. Most transforms used in image compression algorithms map image data to a complete set of transform basis functions which can decorrelate image information and represent data in a more compact form. This technique has proven to be very efficient and is used in most state of the art compression algorithms. However, if an over-complete set of basis functions is available, the image information can be captured by fewer basis functions. This results in a more compact image representation and can potentially yield a better compression performance. In this thesis, we study the use of over-complete image representation as an alternative to transform coding techniques used in image compression. The matching pursuit (MP) algorithm is used to map the image to an over-complete dictionary. We develop new quantization and encoding algorithms for matching pursuit image coding and compare the proposed MP image encoder with state of the art image codecs that use transform coding techniques. Additionally, the iterative nature of the matching pursuit algorithm can be used to design progressive encoders. We also study progressive coding by matching pursuit and design new progressive MP encoders and show how they outperform existing solutions.
We start by study of progressive coding by matching pursuit and design a progressive encoder for i.i.d. Gaussian sources. The choice of Gaussian sources is motivated by the fact that theoretical bounds on progressive coding of Gaussian sources are known and therefore can be used to determine the efficiency of matching pursuit in progressive coding. Our proposed MP progressive encoder outperforms all existing progressive encoders designed for Gaussian sources. However, redundancies in the MP algorithm prevents us from closing the gap that exists between progressive and non-progressive Gaussian source coding. Therefore, we design another progressive encoder based on lattice quantization and address some of the issues associated with our proposed MP encoder.
In the second part of this thesis we study the application of matching pursuit m image compression. We start our study by developing a new adaptive quantization technique that can outperform existing quantization techniques designed for matching pursuit image coding. We continue our study by designing an optimal encoding algorithm for encoding MP coefficients and atom positions. The proposed encoding algorithm results in significant rate distortion improvement over existing encoding techniques. The use of our proposed encoding technique enables comparison of matching pursuit image coding with state of the art compression algorithms that use transform coding such as JPEG2000. Our proposed MP image encoder outperforms JPEG2000 at low bit rates and results in better visual quality at moderate bit rates. We show that the flexibility offered by the over-complete dictionary can result in superior performance compared to image compression using transform coding techniques.
Keywords: electrical and computer engineering, progressive coding, matching pursuit, Gaussian