Optimal interpolation data for image reconstructions

Abstract

This work analyses several approaches for determining optimal sparse data sets for image reconstructions by means of linear homogeneous diffusion. Two optimisation strategies for finding optimal data locations are presented. The first one impresses through its simplicity and is based on results from spline interpolation theory. However, this approach can only be applied to one dimensional strictly convex and differentiable functions. Due to these restrictions we derive an alternative approach which uses findings from optimal control theory. This new algorithm can be applied on arbitrary signals. Both approaches are analysed for their convergence behaviour. Further, we discuss the problem of selecting good data values for fixed data positions. This problem can be analysed as a least squares problem. An important relationship between the optimal data locations and the data values is derived and we present efficient numerical schemes to obtain these values. Finally, we present a image compression approach based on the findings from this work. Experiments show that is possible to outperform popular compression algorithms.

Diese Arbeit untersucht mehrere Ansätze zur Bestimmung optimaler dünn besetzter Datensätze für Bildrekonstruktionen mittels linearer homogener Diffusion. Es werden zwei Optimierungsverfahren zur Bestimmung der Position der Datenpunkte präsentiert. Das Erste besticht durch seine Einfachheit und basiert auf Resultaten aus der Spline Interpolationstheorie. Dieses Verfahren kann jedoch nur auf eindimensionale streng konvexe und stetig differenzierbare Signale angewendet werden. Wegen dieser Einschränkungen wird ein alternativer Ansatz hergeleitet der auf Erkenntnissen aus der Theorie der optimalen Steuerung beruht. Dieser neue Algorithmus kann auf beliebige Signale angewendet werden. Beide Methoden werden auf ihre Konvergenzeigenschaften untersucht. Des Weiteren untersuchen wird das Problem zur Bestimmung guter Datenwerte für feste Positionen, welches im Rahmen der Methode der kleinsten Quadrate untersucht werden kann. Ein wesentlicher Zusammenhang zwischen optimalen Datenpositionen und Datenwerten wird hergeleitet und wir stellen effiziente numerische Verfahren zur Bestimmung dieser Datenwerte dar. Abschließend präsentieren wir ein Bildkompressionsverfahren das auf den Resultaten aus dieser Arbeit basiert. Experimente beweisen, dass es möglich ist gängige Kompressionsalgorithmen zu schlagen.