Digital Repository at the University of Maryland (DRUM)  >
Theses and Dissertations from UMD  >
UMD Theses and Dissertations 

Please use this identifier to cite or link to this item:

Title: Image representation and compression via sparse solutions of systems of linear equations
Authors: Nava Tudela, Alfredo
Advisors: Benedetto, John J
Department/Program: Applied Mathematics and Scientific Computation
Type: Dissertation
Sponsors: Digital Repository at the University of Maryland
University of Maryland (College Park, Md.)
Subjects: Applied mathematics
Keywords: Applied harmonic analysis
Discrete cosine transform
Frame theory
Haar wavelet
Image processing
Issue Date: 2012
Abstract: We are interested in finding sparse solutions to systems of linear equations $mathbf{A}mathbf{x} = mathbf{b}$, where $mathbf{A}$ is underdetermined and fully-ranked. In this thesis we examine an implementation of the {em orthogonal matching pursuit} (OMP) algorithm, an algorithm to find sparse solutions to equations like the one described above, and present a logic for its validation and corresponding validation protocol results. The implementation presented in this work improves on the performance reported in previously published work that used software from SparseLab. We also use and test OMP in the study of the compression properties of $mathbf{A}$ in the context of image processing. We follow the common technique of image blocking used in the JPEG and JPEG 2000 standards. We make a small modification in the stopping criteria of OMP that results in better compression ratio vs image quality as measured by the structural similarity (SSIM) and mean structural similarity (MSSIM) indices which capture perceptual image quality. This results in slightly better compression than when using the more common peak signal to noise ratio (PSNR). We study various matrices whose column vectors come from the concatenation of waveforms based on the discrete cosine transform (DCT), and the Haar wavelet. We try multiple linearization algorithms and characterize their performance with respect to compression. An introduction and brief historical review on the topics of information theory, quantization and coding, and the theory of rate-distortion leads us to compute the distortion $D$ properties of the image compression and representation approach presented in this work. A choice for a lossless encoder $gamma$ is left open for future work in order to obtain the complete characterization of the rate-distortion properties of the quantization/coding scheme proposed here. However, the analysis of natural image statistics is identified as a good design guideline for the eventual choice of $gamma$. The lossless encoder $gamma$ is to be understood under the terms of a quantizer $(alpha, gamma, beta)$ as introduced by Gray and Neuhoff.
Appears in Collections:Computer Science Theses and Dissertations
Mathematics Theses and Dissertations
UMD Theses and Dissertations

Files in This Item:

File Description SizeFormatNo. of Downloads
NavaTudela_umd_0117E_13138.pdf11.19 MBAdobe PDF107View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments