Ph.D Thesis

Ph.D StudentDar Yehuda
SubjectNew Methods for Signal Compression and Their Relations to
Restoration Problems
DepartmentDepartment of Computer Science
Supervisors PROF. Alfred Bruckstein
PROF. Michael Elad
Full Thesis textFull thesis text - English Version


Compression and restoration are two fundamental data processing tasks. Lossy compression represents the given data using a binary description that trades off the reconstructed signal quality with the representation bit-cost to satisfy storage or transmission constraints. Restoration methods estimate an unknown signal from its degraded version resulting from inevitable imperfections of practical devices. Since typical systems involve various degradations and also require data storage and transmission, the restoration and compression problems have various interesting connections of great importance. This thesis examines several challenging problems at the intersection of the compression and restoration topics.

In the main part of this thesis we propose a compression framework for rate-distortion optimizations that are intricate due to unusual distortion metrics. Using the alternating direction method of multipliers (ADMM) technique we develop an optimization approach addressing the difficult problem by iterative solution of easier tasks, including standard compression applications. We believe that the general iterative optimization framework proposed here entails a great potential for a variety of challenging compression problems associated with unusual distortion metrics. The usefulness of our general design is established here using a thorough study of its implications to problems connecting compression, degradation operators, and restoration processes.

We study a typical system structure where a signal is first acquired, then compressed for transmission or storage, and eventually rendered using an imperfect device. While the resulting quality of the system output signal may severely be affected by the acquisition and rendering processes, these degradations are usually ignored in the compression stage, leading to an overall sub-optimal system performance. Using our ADMM-based compression methodology we optimize the system's performance with respect to end-to-end reconstruction error versus the compression bit-cost, showing that the design of the new globally-optimized compression reduces to a standard compression of a "system adjusted" signal. Essentially, we propose a new practical framework for the information-theoretic problem of remote source coding. The main ideas of our method are further illustrated using rate-distortion theory for Gaussian signals. We experimentally demonstrate our framework for image and video compression using the state-of-the-art HEVC standard, adjusted to several system layouts including acquisition and rendering models. The experiments establish our method as the best approach for optimizing the system performance at high bit-rates from the compression standpoint.

Moreover, we explore the topic of signal restoration using complexity regularization, quantifying the compression bit-cost of the signal estimate. Based on our ADMM-based approach, we present new restoration methods relying on repeated applications of standard compression techniques. Thus, we restore signals by leveraging state-of-the-art models designed for compression. Our approach utilizes a new shift-invariant complexity regularizer, measuring the bit-cost of all the shifted forms of the estimate, promoting restoration using averaging of decompressed outputs gathered from compression of shifted signals. On the theoretical side, we present a rate-distortion theoretic analysis for restoration of a Gaussian signal. The presented experiments show good results for image deblurring and inpainting using the JPEG2000 and HEVC compression standards.