Discrete tomography by convex concave regularization using linear and quadratic optimization [Elektronische Ressource] / vorgelegt von Stefan Weber

Stefan

Sujets

• Mathematics

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2009
• Nombre de lectures: 6
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Inaugural-Dissertation
zur
Erlangung der Doktorwürde
der
Naturwissenschaftlich–MathematischenGesamtfakultät
der
Ruprecht–Karls–Universität
Heidelberg
vorgelegt von
Dipl.-Inf. Stefan Weber
aus Heidelberg
Tag der mündlichen Prüfung: 20. März 2009iiDiscrete Tomography by
Convex-Concave Regularization using
Linear and Quadratic Optimization
1. Gutachter: Prof. Dr. Christoph Schnörr
2. Gutachter: Prof. Dr. Joachim Horneggeriv1 2To Pauline and Attila .
1Pauline Weber (stillborn 21.12.2006).
2Prof. Attila Kuba (1953-2006),
Dept. of Image Processing and Computer Graphics, University of Szeged, Hungary.
vvi1Quidquid agis, prudenter agas et respice finem.
1trans. “Whatever you do, do prudently, and be aware of the consequences.”
viiviiiAbstract
Tomography in its broadest sense concerns the reconstruction of cross section images which
permits the visualization of the interior of objects. From the medical application, computerized
tomography (CT) and magnetic resonance imaging (MRI) are well-known for delivering high
quality images from inside the human body and, thus, support physicians at their diagnosis.
Generally speaking, tomographic images depict the spatially varying density of objects; in the
medical case for instance different sorts of tissue are distinguishable because of their diverse
densities. Nevertheless, the values that density attains must not be constant, not even in the
same class of tissue. Instead, it might continuously vary and therefore this type of tomography
is referred to as continuous tomography.
In contrast to continuous tomography, discrete tomography concerns the reconstruction of ob-
jects that are made up from a few different materials, each of which comprising a homogeneous
density distribution. Consequently, the involved densities can only embrace a certain set of
discrete values. Such reconstruction scenarios arise for instance in quality protection by non-
destructive testing where manufacturers seek for involvements or cracks inside their cast or
metal parts. The reconstruction process assigns a single value from the discrete set to each
spatial position which in the simplest case, single material and air (environment), yields a binary
image with 0 corresponding to air (environment) and 1 to material. In fact the binary case is
mostly studied in the relevant literature. There, it is typically also assumed that the discrete
values are either known in advance and are, thus, directly accessible as a priori knowledge or
that at least a reasonably good estimate can be provided. Similarly as continuous functions
generalize discrete functions, discrete tomography can be perceived as a special case of contin-
uous tomography. This, however, poses the question why to deal with a special case while there
already exists a solution to the more general case? The answer is that algorithms which are
specialized to the discrete problem have many advantages if both assumptions, (i) discreteness
of the solution and (ii) discrete values are a priori known, hold for the underlying reconstruction
ixAbstract
problem. If they are met then specialized algorithms typically need a significant smaller amount
of projection data since they explore the a priori knowledge in order to reduce the space of
possible solutions. Further, due to the construction of the scanning device it might not be
◦possible to perform a scan over a range of 180 which is, however, mandatory in order to apply
the transform-based methods among the continuous reconstruction approaches. Specialized
algorithms, conversely, do not underlie any restrictions on the scanning range and are, thus,
applicable to limited angle tomography. Another advantage is that many discrete approaches
allow to actively include additional a priori knowledge, e.g. the smoothness of the solution, into
the reconstruction process which in turn makes even less projections necessary. Nonetheless,
the restriction to a discrete set also entails some difficulties as it renders the reconstruction
task into a combinatorial problem, in fact its NP-completeness can be proven for more than
two projections. As a result stochastic approaches, like simulated annealing, are frequently
employed which can be applied straightforwardly due to their flexibility concerning objective
criteria. It is known, however, that these approaches converge slowly if applied properly and
their results cannot be reproduced due to their non-deterministic procedure.
This work addresses the development of new and theoretically sound algorithms which are suit-
able for reconstruction problems as they appear in discrete tomography. At this, we pursue a
pure deterministic approach and our principal strategy is to solve a relaxation of the original
problem at first. This part equals the minimization of a convex optimization problem which is
good natured from a mathematical point of view and is efficiently solvable by linear or quadratic
programminginourcase. Subsequently, therelaxation isgradually releasedandasolutioninthe
sense of the original problem is enforced. The non-linear subproblems which accrue during that
process are rendered to sequences of convex optimization problems by means of an optimization
approach based on d.c. (∼ difference of convex functions) programming. This provably assures
the convergence of our algorithms which is not obvious for this type of optimization strategy.
In order to numerically demonstrate the performance of our algorithms we solve several recon-
struction problems setup from different phantom images and a varying number of projections.
At first, we consider reconstructions of binary images only but eventually extend our approach
to the general discrete reconstruction problem such that it can be successfully applied to the
non-binary case.
x