Competitive image compression with linear PDEs

Abstract

In recent years, image compression methods with partial differential equations (PDEs) have become a promising alternative to standard methods like JPEG or JPEG2000. They exploit the ability of PDEs to recover an image from only a small amount of stored pixels. To do so, this information is diffused into unknown image regions. Most successful codecs rely on a sophisticated nonlinear diffusion process. In this thesis, we investigate the potential of linear PDEs for image compression. This follows up recent promising compression results with the Laplace and biharmonic operator. As a central contribution, we thoroughly study the diffusion-based image reconstruction, and establish a connection to the concept of sparsity with the help of discrete Green's functions. Apart from gaining novel theoretical insights, this offers algorithmic benefits: We obtain a fast reconstruction procedure and improved data optimisation methods. The power of linear PDEs is demonstrated by proposing three different compression approaches. Besides a designated codec for depth maps we present an algorithm for general images. The third approach aims at a fast decoding. Experiments show that linear PDEs can compete with nonlinear PDEs in a compression context, and that codecs with linear PDEs are even able to outperform standard approaches in terms of both speed and quality.

In den letzten Jahren sind Bildkompressionsmethoden basierend auf partiellen Differentialgleichungen (PDEs) eine vielversprechende Alternative zu Standardmethoden wie JPEG oder JPEG2000 geworden. Diese nutzen die Fähigkeit von PDEs aus, ein Bild von nur einer kleinen Menge an gespeicherten Pixeln rückgewinnen zu können. Die meisten erfolgreichen Codecs verwenden einen aufwändigen nichtlinearen Diffusionsprozess. In dieser Arbeit werden wir das Potential von linearen PDEs zur Bildkompression untersuchen. Dies schließt an die kürzlichen vielversprechenden Kompressionsergebnisse mit dem Laplace und biharmonischen Operator an. Als zentralen Beitrag studieren wir die PDE-basierte Bildrekonstruktion und stellen mit Hilfe von diskreten Greenschen Funktionen eine Verbindung zum Sparsity-Konzept her. Dies bietet neben neuen theoretischen Erkenntnissen auch algorithmische Vorteile: Wir erhalten ein schnelles Rekonstruktionsverfahren und verbesserte Datenoptimierungsmethoden. Die Stärke von linearen PDEs wird gezeigt, indem wir drei verschiedene Kompressionsmethoden vorschlagen. Neben eines designierten Codecs für Tiefenkarten präsentieren wir einen Algorithmus für allgemeine Bilder. Der dritte Ansatz zielt auf eine schnelle Dekodierung ab. Experimente zeigen, dass lineare PDEs mit nichtlinearen PDEs in einem Kompressionskontext konkurrieren können und dass Codecs mit linearen PDEs in Bezug auf Geschwindigkeit und Qualität sogar Standardmethoden übertreffen können.