Tai / Lie / Chan Image Processing Based on Partial Differential Equations

Proceedings of the International Conference on PDE-Based Image Processing and Related Inverse Problems, CMA, Oslo, August 8-12, 2005
1. Auflage 2006
ISBN: 978-3-540-33267-1
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 440 Seiten

Reihe: Mathematics and Visualization

This book publishes a collection of original scientific research articles that address the state-of-art in using partial differential equations for image and signal processing. Coverage includes: level set methods for image segmentation and construction, denoising techniques, digital image inpainting, image dejittering, image registration, and fast numerical algorithms for solving these problems.

Autoren/Hrsg.

Tai, Xue-Cheng

Lie, Knut-Andreas

Osher, Stanley

Chan, Tony F.

Inhaltsverzeichnis

1;Preface;5
2;Contents;7
3;Part I Digital Image Inpainting, Image Dejittering, and Optical Flow Estimation;11
3.1;Image Inpainting Using a TV-Stokes Equation;12
3.1.1;1 Introduction;12
3.1.2;2 The Mathematical Principles;14
3.1.3;3 Numerical Experiments;19
3.1.4;4 Conclusion;29
3.1.5;References;30
3.2;Error Analysis for H1 Based Wavelet Interpolations;32
3.2.1;1 Introduction;32
3.2.2;2 Variational Wavelet Interpolation Models;34
3.2.3;3 Recovery Bound for the H1 Model;36
3.2.4;4 A Numerical Example;40
3.2.5;References;41
3.3;Image Dejittering Based on Slicing Moments;44
3.3.1;1 Introduction;44
3.3.2;2 Slicing Moments of BV Functions;46
3.3.3;3 Moments Regularization for Image Dejittering;50
3.3.4;4 Application to Image Dejittering and Examples;57
3.3.5;5 Conclusion;61
3.3.6;References;62
3.4;CLG Method for Optical Flow Estimation Based on Gradient Constancy Assumption;66
3.4.1;1 Introduction;66
3.4.2;2 Review of the CLG Method;67
3.4.3;3 Formulation of the CLG(H) Method;69
3.4.4;4 Algorithmic Realization;70
3.4.5;5 Comparison Between Methods;71
3.4.6;6 Summary;74
3.4.7;References;74
4;Part II Denoising and Total Variation Methods;77
4.1;On Multigrids for Solving a Class of Improved Total Variation Based Staircasing Reduction Models;78
4.1.1;1 Introduction;78
4.1.2;2 An Overview of Staircasing Reduction Models;82
4.1.3;3 Algorithms for the Combined TV and H1 Models;86
4.1.4;4 A Modifed Staircasing Reduction Model;98
4.1.5;5 Conclusion;101
4.1.6;References;101
4.2;A Method for Total Variation-based Reconstruction of Noisy and Blurred Images;104
4.2.1;1 Introduction;104
4.2.2;2 Idea and New Method;106
4.2.3;3 Algorithms for Solving the Nonlinear System of Equations;108
4.2.4;4 Models and Blur Operators;111
4.2.5;5 Numerical Experiments and Discussions;112
4.2.6;References;115
4.3;Minimization of an Edge-Preserving Regularization Functional by Conjugate Gradient Type Methods;118
4.3.1;1 Introduction;118
4.3.2;2 Review of Two Phase Methods;119
4.3.3;3 Our Method;121
4.3.4;4 Convergence of the Method;122
4.3.5;5 Simulation;127
4.3.6;6 Conclusion;128
4.3.7;References;129
4.4;A Newton-type Total Variation Diminishing Flow;132
4.4.1;1 Introduction;132
4.4.2;2 A Newton-type Flow for the Minimization of the Area of Level- Sets;139
4.4.3;3 Geometric Properties;143
4.4.4;4 Numerical Examples;149
4.4.5;5 Conclusion;152
4.4.6;References;155
4.5;Chromaticity Denoising using Solution to the Skorokhod Problem;158
4.5.1;1 Introduction;158
4.5.2;2 Mathematical Preliminaries;159
4.5.3;3 Stochastic Representation of Solution to the Heat Equation;161
4.5.4;4 Image Denoising;164
4.5.5;5 A Numerical Scheme;168
4.5.6;References;168
4.6;Improved 3D Reconstruction of Interphase Chromosomes Based on Nonlinear Di . usion Filtering;172
4.6.1;1 Introduction;172
4.6.2;2 Improved Reconstruction of Interphase Chromosomes;174
4.6.3;3 Conclusion;180
4.6.4;Acknowledgment;180
4.6.5;References;180
5;Part III Image Segmentation;183
5.1;Some Recent Developments in Variational Image Segmentation;184
5.1.1;1 Introduction;185
5.1.2;2 Active Contours Methods;186
5.1.3;3 Multi-Channel Extensions in Chan–Vese Model;191
5.1.4;4 Multi-Phase Extensions;208
5.1.5;5 Fast Algorithms;213
5.1.6;6 Acknowledgment;216
5.1.7;References;216
5.2;Application of Non-Convex BV Regularization for Image Segmentation;220
5.2.1;1 Introduction;220
5.2.2;2 Review on the Mathematical Analysis of Evolution Processes;222
5.2.3;3 Variational Level Set Model for Image Segmentation;223
5.2.4;4 Relaxation;225
5.2.5;5 Numerical Simulations;232
5.2.6;6 Conclusion;235
5.2.7;References;236
5.3;Region-Based Variational Problems and Normal Alignment – Geometric Interpretation of Descent PDEs;238
5.3.1;1 Introduction;238
5.3.2;2 Background;239
5.3.3;3 Descent Directions;243
5.3.4;4 Region-Based Functionals;244
5.3.5;5 Quadratic Normal Alignment;251
5.3.6;6 Computing Gˆ ateaux Derivatives using Shape Gradients;254
5.3.7;7 Conclusions;256
5.3.8;References;256
5.4;Fast PCLSM with Newton Updating Algorithm;258
5.4.1;1 Introduction;258
5.4.2;2 PCLSM for Image Segmentation;259
5.4.3;3 Newton Updating;262
5.4.4;4 Numerical Examples;264
5.4.5;5 Conclusion;270
5.4.6;References;270
6;Part IV Fast Numerical Methods;273
6.1;Nonlinear Multilevel Schemes for Solving the Total Variation Image Minimization Problem;274
6.1.1;1 Introduction;274
6.1.2;2 Review of Unilevel Methods for the TV Formulation;276
6.1.3;3 Review of a Class of Multigrid Methods;280
6.1.4;4 NSSC Method for Equation (1);284
6.1.5;5 Numerical Experiments;290
6.1.6;6 Conclusions;291
6.1.7;Acknowledgements;293
6.1.8;References;293
6.2;Fast Implementation of Piecewise Constant Level Set Methods;298
6.2.1;1 Introduction;298
6.2.2;2 Piecewise Constant Level Set Formulation;300
6.2.3;3 Operator Splitting Scheme;301
6.2.4;4 Operator Splitting and Newton Methods for Image Segmentation;303
6.2.5;5 The Algorithm;306
6.2.6;6 Numerical Experiments;309
6.2.7;7 Conclusion;314
6.2.8;References;316
6.3;The Multigrid Image Transform;318
6.3.1;1 Introduction;318
6.3.2;2 Recapitulation on Multigrid;319
6.3.3;3 The Multigrid Image Transform;322
6.3.4;4 Comparative Results;327
6.3.5;5 Concluding Remarks;328
6.3.6;References;332
6.4;Minimally Stochastic Schemes for Singular Di . usion Equations;334
6.4.1;1 Introduction;334
6.4.2;2 Schemes Based on Two Pixel Interaction;336
6.4.3;3 Numerical Experiments;341
6.4.4;4 Conclusion;342
6.4.5;References;347
7;Part V Image Registration;350
7.1;Total Variation Based Image Registration;352
7.1.1;1 Introduction.;352
7.1.2;2 Continuous Total Variation Minimization.;355
7.1.3;3 Numerical Minimization;358
7.1.4;4 Results;361
7.1.5;5 Summary and Conclusion;364
7.1.6;References;364
7.2;Variational Image Registration Allowing for Discontinuities in the Displacement Field;372
7.2.1;1 Introduction;373
7.2.2;2 Variational Approach;374
7.2.3;3 Variable Regularizer;378
7.2.4;4 Numerical Results;382
7.2.5;5 Conclusion and Outlook;384
7.2.6;References;386
8;Part VI Inverse Problems;388
8.1;Shape Reconstruction from Two-Phase Incompressible Flow Data using Level Sets;390
8.1.1;Summary;390
8.1.2;1 Introduction;390
8.1.3;2 The Reservoir Model;393
8.1.4;3 The Forward Problem;395
8.1.5;4 The Shape Reconstruction Problem;396
8.1.6;5 Formal Derivation of the Shape Evolution Algorithm;397
8.1.7;6 The Adjoint Technique for Calculating Sensitivities;399
8.1.8;7 The Algorithm;401
8.1.9;8 Numerical Examples;402
8.1.10;9 Conclusions and Future Work;406
8.1.11;Acknowledgments;408
8.1.12;References;408
8.2;Reservoir Description Using a Binary Level Set Approach with Additional Prior Information About the Reservoir Model;412
8.2.1;1 Introduction;412
8.2.2;2 The Inverse Problem;414
8.2.3;3 The Binary Level Set Approach;416
8.2.4;4 The Binary Level Set Method for the Inverse Problem;418
8.2.5;5 Numerical Optimisation;419
8.2.6;6 Numerical Results;420
8.2.7;7 Summary and Conclusions;431
8.2.8;8 Acknowledgements;432
8.2.9;9 Nomenclature;432
8.2.10;References;433
9;A Color Figures;436
9.1;From Image Inpainting Using a TV-Stokes Equation,” by Tai, Osher, and Holm;436
9.2;From Image Dejittering Based on Slicing Moments,” by Kang and Shen;444
9.3;From Chromaticity Denoising using Solution to the Skorokhod Problem,” by Borkowski;445
9.4;From Some Recent Developments in Variational Image Segmentation,” by Chan, Moelich, and Sandberg;446

Leseproben

Error Analysis for H1 Based Wavelet Interpolations (p. 23)

Tony F. Chan, Hao-Min Zhou, and Tie Zhou

Summary.

We rigorously study the error bound for the H1 wavelet interpolation problem, which aims to recover missing wavelet coe.cients based on minimizing the H1 norm in physical space. Our analysis shows that the interpolation error is bounded by the second order of the local sizes of the interpolation regions in the wavelet domain.

1 Introduction

In this paper, we investigate the theoretical error estimates for variational wavelet interpolation models. The wavelet interpolation problem is to calculate unknown wavelet coe.- cients from given coeficients. It is similar to the standard function interpolations except the interpolation regions are defined in the wavelet domain. This is because many images are represented and stored by their wavelet coeficients due to the new image compression standard JPEG2000.

The wavelet interpolation is one of the essential problems of image processing and closely related to many tasks such as image compression, restoration, zooming, inpainting, and error concealment, even though the term "interpolation" does not appear very often in those applications. For instance, wavelet inpainting and error concealment are to fill in (interpolate) damaged wavelet coe.cients in given regions in the wavelet domain.

Wavelet zooming is to predict (extrapolate) wavelet coeficients on a finer scale from a given coarser scale coeficients. A major difference between wavelet interpolations and the standard function interpolations is that the applications of wavelet interpolations often impose regularity requirements of the interpolated images in the pixel domain, rather than the wavelet domain.

For example, natural images (not including textures) are often viewed as piecewise smooth functions in the pixel domain. This makes the wavelet interpolations more challenging as one usually cannot directly use wavelet coeficients to ensure the required regularity in the pixel domain. To overcome the difficulty, it seems natural that one can use optimization frameworks, such as variational principles, to combine the pixel domain regularity requirements together with the popular wavelet representations to accomplish wavelet interpolations.

A different reason for using variational based wavelet interpolations is from the recent success of partial differential equation (PDE) techniques in image processing, such as anisotropic difusion for image denoising (25), total variation (TV) restoration (26), Mumford-Shah and related active contour segmentation (23, 10), PDE or TV image inpainting (1, 8, 7), and many more that we do not list here. Very often these PDE techniques are derived from variational principles to ensure the regularity requirements in the pixel domain, which also motive the study of variational wavelet interpolation problems.

Many variational or PDE based wavelet models have been proposed. For instance, Laplace equations, derived from H1 semi-norm, has been used for wavelet error concealment (24), TV based models are used for compression (5, 12), noise removal (19), post-processing to remove Gibbs’ oscillations (16), zooming (22), wavelet thresholding (11), wavelet inpainting (9), l1 norm optimization for sparse signal recovery (3, 4), anisotropic wavelet filters for denoising (14), variational image decomposition (27).