Methods for PDE-based image reconstruction

Abstract

This thesis addresses scattered data interpolation and image approximation, focusing on reconstructions via partial differential equations (PDEs). While classical methods like JPEG and JPEG2000 are widely used, PDE-based inpainting often yields better results for images with low to medium texture content. We extend PDE-based approaches by incorporating diverse features - colours, derivatives, and local integrals - into the reconstruction process. Experiments show that these features can reduce the MSE by more than 60% without increasing the data budget. The framework also supports nonlinear operators and features. Since PDE-based methods are computationally demanding, we develop fast inpainting techniques using adaptive finite elements on the CPU, and multigrid solvers on the GPU. The latter enables real-time inpainting of 4K images. Beyond efficiency, we tackle data selection for low-error reconstructions through spatial and tonal optimisation. We propose greedy algorithms for spatial selection and fast solvers for large-scale tonal optimisation problems. We also explore the link between denoising and inpainting, showing their connection through probabilistic theory. Finally, we present perceptual optimisation techniques for Monte Carlo rendering, aiming for blue-noise error distributions that decay under low-pass filtering.

Diese Arbeit behandelt die Scattered Data Interpolation und Bildapproximation mit partiellen Differentialgleichungen (PDEs). Klassische Verfahren wie JPEG und JPEG2000 sind verbreitet, doch PDE-basiertes Inpainting liefert oft bessere Ergebnisse bei Bildern mit geringer bis mittlerer Textur. Wir erweitern PDE-Ansätze durch Einbindung von Farben, Ableitungen und lokalen Integralen. Experimente zeigen, dass diese Merkmale den mittleren quadratischen Fehler (MSE) um mehr als 60% senken können – ohne zusätzlichen Datenbedarf. Unser Ansatz unterstützt auch nichtlineare Operatoren. Da PDE-Methoden rechenintensiv sind, entwickeln wir schnelle Inpainting-Techniken mit adaptiven finiten Elementen (CPU) und Mehrgitterlösern für Grafikprozessoren (GPUs). So wird Echtzeit-Inpainting von 4K-Bildern möglich. Zur Fehlerreduktion optimieren wir die Datenauswahl räumlich und tonal. Wir schlagen Greedy-Algorithmen für die räumliche Auswahl und schnelle Löser für große tonale Optimierungsprobleme vor. Zudem etablieren wir einen Zusammenhang zwischen Entrauschen und Inpainting, der auf einer wahrscheinlichkeitstheoretischen Beziehung basiert. Abschließend präsentieren wir perzeptuelle Optimierungstechniken für Monte-Carlo-Rendering mit blauem Rauschen, das unter Tiefpassfilterung abklingt.