A multigrid method for elastic image registration with additional structural constraints [Elektronische Ressource] / vorgelegt von Lars Hömke

Sujets

• Informatik
• Mathematics

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2006
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

A multigrid method for elastic image
registration with additional structural
constraints
Inaugural-Dissertation
zur
Erlangung des Doktorgrades der
Mathematisch-Naturwissenschaftlichen Fakultat¤
der Heinrich-Heine Universitat¤ Dusseldorf¤
vorgelegt von
Lars Homk¤ e
aus Dusseldorf¤
August 2006Aus dem Mathematischen Institut
¤ ¤der Heinrich-Heine Universitat Dusseldorf
Gedruckt mit der Genehmigung der
Mathematisch-Naturwissenschaftlichen Fakultat¤ der Heinrich-Heine
¤ ¤Universitat Dusseldorf
Referent: Prof. Dr. rer. nat. Kristian Witsch
Koreferent: Prof. Dr. rer. nat. Bernd Fischer (Universitat¤ zu Lubeck)¤
Tag der mundlichen¤ Prufung:¤ 08.12.2006c 2006
Lars Homk¤ e
All Rights ReservedAbstract
This thesis deals with the solution of a nonlinear inverse problem arising in digital
image registration. In image registration one seeks to compute a transformation
between two images such that they become more similar in some sense.
In the rst part, we de ne the problem as the minimization of a regularized non-
linear least-squares functional, which measures the image difference and smooth-
ness of the transformation. The nonlinear functional is linearized around a current
approximation in order to obtain well-posed linear subproblems. The Hessian is
replaced by an approximation that leads to an inexact Newton-type method, specif-
ically a regularized Gauss-Newton method. A related gradient descent method is
derived in the same framework for the purpose of comparison.
In the next part of this thesis we study geometric multigrid methods for the
solution of the linear subproblems (inner iteration). The type of regularization em-
ployed leads to a system of elliptic partial differential equations. For the regularized
Gauss-Newton method the differential operator contains jumping coef cients that
cannot be adequately dealt with by standard geometric multigrid methods. Modi -
cations of the multigrid components that improve multigrid convergence and allow
for fast and ef cient computation are proposed. In the outer iteration a trust region
strategy is used and the whole procedure is embedded in a multiresolution frame-
work. Extensive numerical results for the multigrid (inner iteration), outer iteration,
and multiresolution framework are given.
In the last part a framework for the incorporation of additional structural con-
straints in the presented registration procedure is proposed. This framework is
based on implicit representation of shapes via level sets. Representations for differ-
ent types of shapes are discussed. Distance functionals of least-square type that can
be easily plugged into the existing registration procedure are introduced. Examples
for the different representations and the combination with image data are given.Contents
Abstract i
Contents ii
List of Figures v
List of Tables vii
List of Algorithms viii
1 Introduction 1
2 Elastic image registration 4
3 Two optimization strategies for image registration 7
3.1 Regularized gradient descent method . . . . . . . . . . . . . . . . 9
3.2 Re Gauss-Newton method . . . . . . . . . . . . . . . . . 10
3.3 Trust region approach . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3.1 Choice of the trust-region parameter . . . . . . . . . . . 11
3.3.2 Choice of the trust region topology . . . . . . . . . . . . . 12
4 Numerical Implementation 16
4.1 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Multigrid (inner iteration) . . . . . . . . . . . . . . . . . . . . . . 24
4.2.1 The principles . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.2 Two-grid cycle . . . . . . . . . . . . . . . . . . . . . . . 25
4.2.3 Multigrid cycle . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.4 Restriction and prolongation operators . . . . . . . . . . . 28
4.2.5 Multigrid components . . . . . . . . . . . . . . . . . . . 30
4.3 A multigrid method for anisotropic coef cients . . . . . . . . . . 30
4.3.1 Coarse grid operator . . . . . . . . . . . . . . . . . . . . 31
4.3.2 Smoother . . . . . . . . . . . . . . . . . . . . . . . . . . 31Contents iii
4.3.3 Operator dependent interpolation . . . . . . . . . . . . . . 35
4.3.4 correction step . . . . . . . . . . . . . 36
4.4 Outer iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5 Multiresolution framework . . . . . . . . . . . . . . . . . . . . . 37
5 Numerical results 40
5.1 Multigrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.1.1 h-independence . . . . . . . . . . . . . . . . . . . . . . . 41
5.1.2 Convergence rates . . . . . . . . . . . . . . . . . . . . . . 42
5.1.3 In uence of noise . . . . . . . . . . . . . . . . . . . . . . 44
5.2 Outer iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2.1 Effect of the number of multigrid cycles . . . . . . . . . . 47
5.2.2 Trust region topology . . . . . . . . . . . . . . . . . . . . 49
5.2.3 Trust region control strategy . . . . . . . . . . . . . . . . 50
5.2.4 Comparison of gradient descent and Gauss-Newton approach 54
5.3 Multiresolution framework . . . . . . . . . . . . . . . . . . . . . 66
6 Shape constraints 70
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.1.1 Motivational example . . . . . . . . . . . . . . . . . . . . 71
6.2 Representation of shape constraints . . . . . . . . . . . . . . . . . 73
6.2.1 Parametric representations . . . . . . . . . . . . . . . . . 74
6.2.2 Implicit . . . . . . . . . . . . . . . . . . . 74
6.2.3 Weighing the pros and cons . . . . . . . . . . . . . . . . . 76
6.3 Implicit representations via Level Sets . . . . . . . . . . . . . . . 78
6.3.1 Level sets and the implicit function theorem . . . . . . . . 78
6.3.2 Implicit representations for closed shapes . . . . . . . . . 80
6.3.3 for shapes of arbitrary codimension 83
6.3.4 Implicit representations for non-closed shapes . . . . . . . 87
6.3.5 A uni ed implicit representation . . . . . . . . . . . . . . 87
6.4 Distance functions . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4.1 Distance function for closed shapes . . . . . . . . . . . . 89
6.4.2 for shapes of arbitrary codimension . . . 91
6.4.3 Distance function for non-closed shapes . . . . . . . . . . 92
6.4.4 for the uni ed approach . . . . . . . . . 93
6.4.5 Approximations forH and . . . . . . . . . . . . . . . . 94
6.5 Integration into the registration process . . . . . . . . . . . . . . . 96iv Contents
7 Results for shape constraints 98
7.1 Shapes of arbitrary codimension . . . . . . . . . . . . . . . . . . 98
7.2 In uence of the approximation parametera . . . . . . . . . . . . 100
7.3 Non-closed shapes . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.4 Combination of different shape constraints . . . . . . . . . . . . . 105
7.5 of image data and shape constraints . . . . . . . . . 107
8 Conclusion 111
A Abbreviations and acronyms 113
B Nomenclature 114
Bibliography 116
Statement of originality 121List of Figures
4.1 Stencil representation ofM u =f . . . . . . . . . . . . . . . . . . 18h h h
[2]4.2 Sparsity pattern forM . . . . . . . . . . . . . . . . . . . . . . . . 21
h
[3]4.3 pattern forM . . . . . . . . . . . . . . . . . . . . . . . . 23h
4.4 Common multigrid cycle types . . . . . . . . . . . . . . . . . . . . . 27
4.5 Sparsity patterns for the matrixQ (line relaxation) . . . . . . . . . . . 33
4.6 Operator dependent interpolation for the two dimensional case . . . . 36
5.1 Simple model problem (square and circle) . . . . . . . . . . . . . . . 40
5.2 Convergence for pointwise relaxation . . . . . . . . . . . . . . . . . 43
5.3 Convergence for small~s . . . . . . . . . . . . . . . . . . . . . . . . 44
5.4 Effect of noise on multigrid convergence . . . . . . . . . . . . . . . . 46
5.5 Comparison of two trust region topologies . . . . . . . . . . . . . . . 49
5.6 Gauss-Newton: Convergence in dependence on