Preview

PDF, English Download (2MB) | Terms of use

Abstract

We investigate theoretical and numerical results that guarantee the exact reconstruction of piecewise constant images from insufficient projections in Discrete Tomography. This is often the case in non-destructive quality inspection of industrial objects, made of few homogeneous materials, where fast scanning times do not allow for full sampling. As a consequence, this low number of projections presents us with an underdetermined linear system of equations. We restrict the solution space by requiring that solutions (a) must possess a sparse image gradient, and (b) have constrained pixel values.

To that end, we develop an lower bound, using compressed sensing theory, on the number of measurements required to uniquely recover, by convex programming, an image in our constrained setting. We also develop a second bound, in the non-convex setting, whose novelty is to use the number of connected components when bounding the number of linear measurements for unique reconstruction.

Having established theoretical lower bounds on the number of required measurements, we then examine several optimization models that enforce sparse gradients or restrict the image domain. We provide a novel convex relaxation that is provably tighter than existing models, assuming the target image to be gradient sparse and integer-valued. Given that the number of connected components in an image is critical for unique reconstruction, we provide an integer program model that restricts the maximum number of connected components in the reconstructed image. When solving the convex models, we view the image domain as a manifold and use tools from differential geometry and optimization on manifolds to develop a first-order multilevel optimization algorithm. The developed multilevel algorithm exhibits fast convergence and enables us to recover images of higher resolution.

Translation of abstract (German)

Im Rahmen der vorliegenden Dissertation werden theoretische und numerische Ergebnisse hergeleitet, welche die exakte Rekonstruktion von stückweise konstanten Bildern aus unzureichenden Messungen in der diskreten Tomographie garantieren. Dies ist häufig der Fall bei der zerstörungsfreien Qualitätsprüfung von Industriebauteilen, die aus wenigen homogenen Materialien bestehen und bei denen aufgrund von schnellen Prüfzeiten keine vollständige Messung möglich ist. Die geringe Anzahl an Messungen führt schließlich zu einen unterbestimmten linearen Gleichungssystem. Es wird ein beschränkter Lösungsraum betrachtet, in welchem die Lösungen (a) dünnbesetzte (sparse) Bildgradienten aufweisen und (b) beschränkte Pixelwerte besitzen.

Auf der Grundlage der Compressed Sensing-Theorie wird eine untere Schranke für die Anzahl der Messungen bestimmt, die erforderlich sind, um unter den gegebenen Bedingungen, mittels konvexer Optimierung ein Bild eindeutig zu rekonstruieren. Darüber hinaus wird auch für den nicht-konvexen Fall eine untere Schranke bestimmt. Deren Besonderheit darin besteht, dass sie auf der Anzahl der Zusammenhangskomponenten beruht.

Auf diesen Ergebnissen aufbauend werden verschiedene Optimierungsmodelle untersucht, welche Lösungen mit sparsen Bildgradienten liefern oder den Bereich der Pixelwerte einschränken. In diesem Zusammenhang wird eine neuartige konvexe Relaxierung vorgestellt, die nachweislich genauer ist als alle bestehenden Ansätze. Hierbei wird davon ausgegangen, dass das Lösungsbild einen sparsen Gradienten aufweist und ganzzahlig ist. Da die Anzahl der Zusammenhangskomponenten in einem Bild für dessen eindeutige Rekonstruktion entscheidend ist, wird ein ganzzahliges Programm entwickelt, welches die maximale Anzahl der Zusammenhangskomponenten im rekonstruierten Bild beschränkt. Ferner wird beim Lösen konvexer Modelle der Bildbereich als Mannigfaltigkeit aufgefasst. Basierend auf Ergebnissen aus der Differentialgeometrie und der Optimierung auf Mannigfaltigkeiten wird ein Optimierungsverfahren erster Ordnung, welches mehrere Ebenen nutzt, hergeleitet. Der entwickelte Mehrebenen-Algorithmus weist eine schnelle Konvergenz auf und ermöglicht die Rekonstruktion von hochauflösenden Bildern.