Loading…
Thumbnail Image

Theoretical analysis of image separation and image inpainting: a compressed sensing approach

Do, Van Tiep

In image processing, problems of separation and reconstruction of missing pixels from incomplete digital images have been far more advanced in past decades. Many empirical results have produced very good results, however, providing a theoretical analysis for the success of algorithms is not an easy task, especially, for inpainting and separating multi-component signals. In this thesis, our primary goal is to develop a framework for these two problems. In the first part of this thesis, we present a theoretical analysis of separating images consisting of pointlike and curvelike structures. Our approach is based on l1-minimization, in which the sparsity of the desired solution is exploited by two sparse representation systems. It is well known that for such components wavelets provide an optimally sparse representation for point singularities, whereas a-shearlet type with flexible scaling might be best adapted to the curvilinear singularities. In our analysis, we first propose a reconstruction framework with theoretical guarantee on convergence, which is extended to use general frames instead of Parseval frames. We construct a dual pair of bandlimited a-shearlets which possesses a good time and frequency localization. We then apply the result to derive an asymptotic accuracy of the reconstructions. In addition, we show that it is possible to separate these two components as long as a < 2, i.e., bandlimited a-shearlets which range from wavelet to shearlet type do not coincide with wavelets in the sense of isotropic fashion. Next, we present a theoretical analysis of recovering missing content in texture images. Our reconstruction algorithm is based on a modified basic pursuit denoising model. The success of this method relies on a compressed sensing technique that texture can be sparsely represented by Gabor frames. Different from papers in the literature which used a multi-scale approach to obtain asymptotic results, we propose a framework with recovery performance guarantees for the whole signal. Our analysis shows that if the region to be inpainted is sufficiently small we can then prove the success of the method by deriving a normalized L2 error estimate of the reconstruction. In the second part of this thesis, we introduce a comprehensive analysis showing that we can use two different representation systems to separate geometric components and fill-in the missing part of the original image simultaneously by utilizing the concept of clustered sparsity. Consequently, our theory shows that it is possible to inpaint or remove texture from an image that is the superposition of two distinct geometric components. We then extend our theory for separating N distinct geometric components and simultaneously filling-in the missing part of the observed image by two main algorithms, one is based on l1 constrained and the other is based on unconstrained minimization. We present a theoretical guarantee for these algorithms using compressed sensing technique, which is based on a principle that each component can be sparsely represented by a suitably chosen dictionary. Those sparsifying systems are also extended to the case of general frames instead of Parseval frames which have been typically used in the past. We finally prove that the method does indeed succeed in separating point singularities from curvilinear singularities and texture as well as inpainting the missing band contained in curvilinear singularities and texture. Finally, some numerical experiments are performed to illustrate our theoretical results.
In der Bildverarbeitung sind die Ansätze zur Trennung und Rekonstruktion von fehlenden Pixeln aus unvollständigen digitalen Bildern in den letzten Jahrzehnten weit fortgeschritten. Viele empirische Ergebnisse haben sehr gute Resultate erbracht, aber eine theoretische Analyse für den Erfolg der Algorithmen ist keine leichte Aufgabe, insbesondere bei dem Inpainting und der Separation von Mehrkomponentensignale. In dieser Arbeit ist unser primäres Ziel die Entwicklung eines Rahmens für diese beiden Probleme. Im ersten Teil dieser Arbeit präsentieren wir eine theoretische Analyse der Trennung von Bildern, die aus punktförmigen und kurvenförmigen Strukturen bestehen. Unser Ansatz basiert auf der l1-Minimierung, bei der die Spärlichkeit der gewünschten Lösung durch zwei spärliche Darstellungssysteme ausgenutzt wird. Es ist bekannt, dass Wavelets für solche Komponenten eine optimal spärliche Darstellung für Punktsingularitäten bieten, während ein Shearlet-Typ mit flexibler Skalierung möglicherweise am besten für die krummlinigen Singularitäten geeignet ist. In unserer Analyse schlagen wir zunächst einen Rekonstruktionsrahmen mit theoretischer Konvergenzgarantie vor, der erweitert wird auf allgemeine Rahmen anstelle von Parseval-Rahmen. Wir konstruieren ein duales Paar von bandbegrenzten a-Shearlets, das eine gute Zeit- und Frequenzlokalisierung besitzt. Anschließend wenden wir das Ergebnis an, um eine asymptotische Genauigkeit der Rekonstruktionen abzuleiten. Darüber hinaus zeigen wir die Möglichkeit der Trennung beider Komponenten, solange a < 2 ist, d. h., bandbegrenzte a-Shearlets, die vom Wavelet- zum Shearlet-Typ reichen, stimmen nicht mit Wavelets im Sinne einer isotropen Mode überein. Als nächstes stellen wir eine theoretische Analyse derWiederherstellung fehlender Inhalte in Texturbildern vor. Unser Rekonstruktionsalgorithmus basiert auf einem modifizierten Basic pursuit-Entrauschungsmodell. Der Erfolg dieser Methode beruht auf einer Compressed-Sensing-Technik, bei der die Textur durch Gabor-Frames spärlich dargestellt werden kann. Im Gegensatz zu Arbeiten in der Literatur, die einen mehrskaligen Ansatz zur Erzielung asymptotischer Ergebnisse verwenden, schlagen wir einen Rahmen vor, der dieWiederherstellungsleistung für das gesamte Signal garantiert. Unsere Analyse zeigt, dass wir den Erfolg der Methode nachweisen können, wenn die zu übermalende Region ausreichend klein ist. Im zweiten Teil dieser Arbeit stellen wir eine umfassende Analyse vor, die zeigt, dass wir zwei verschiedene Darstellungssysteme verwenden können, um geometrische Komponenten zu trennen und den fehlenden Teil des Originalbildes gleichzeitig aufzufüllen, indem wir das Konzept der geclusterten Sparsamkeit anwenden. Folglich zeigt unsere Theorie, dass es möglich ist, ein Bild, das aus der Überlagerung zweier unterschiedlicher geometrischer Komponenten besteht, zu übermalen oder Textur zu entfernen. Anschließend erweitern wir unsere Theorie für die Trennung vonNverschiedenen geometrischen Komponenten und gleichzeitiges Auffüllen des fehlenden Teils des beobachteten Bildes durch zwei Hauptalgorithmen, einer basiert auf l1-gebundener und der andere auf ungebundener Minimierung.Wir stellen eine theoretische Garantie für diese Algorithmen vor, indem wir die Technik der komprimierten Abtastung verwenden, die auf dem Prinzip basiert, dass jede Komponente spärlich durch ein geeignetes Wörterbuch dargestellt werden kann. Diese Sparsifizierungssysteme werden auch auf den Fall allgemeiner Rahmen anstelle von Parseval-Rahmen, die in der Vergangenheit üblicherweise verwendet wurden, erweitert.Wir zeigen schließlich, dass die Methode tatsächlich erfolgreich Punktsingularitäten von krummlinigen Singularitäten und Textur trennt und das fehlende Band in kurvilinearen Singularitäten und Textur. Schließlich werden einige numerische Experimente durchgeführt, um unsere theoretischen Ergebnisse zu illustrieren.