Image Processing Based on Partial Differential Equations (eBook)

Preface 5
Contents 7
Part I Digital Image Inpainting, Image Dejittering, and Optical Flow Estimation 11
Image Inpainting Using a TV-Stokes Equation 12
1 Introduction 12
2 The Mathematical Principles 14
3 Numerical Experiments 19
4 Conclusion 29
References 30
Error Analysis for H1 Based Wavelet Interpolations 32
1 Introduction 32
2 Variational Wavelet Interpolation Models 34
3 Recovery Bound for the H1 Model 36
4 A Numerical Example 40
References 41
Image Dejittering Based on Slicing Moments 44
1 Introduction 44
2 Slicing Moments of BV Functions 46
3 Moments Regularization for Image Dejittering 50
4 Application to Image Dejittering and Examples 57
5 Conclusion 61
References 62
CLG Method for Optical Flow Estimation Based on Gradient Constancy Assumption 66
1 Introduction 66
2 Review of the CLG Method 67
3 Formulation of the CLG(H) Method 69
4 Algorithmic Realization 70
5 Comparison Between Methods 71
6 Summary 74
References 74
Part II Denoising and Total Variation Methods 77
On Multigrids for Solving a Class of Improved Total Variation Based Staircasing Reduction Models 78
1 Introduction 78
2 An Overview of Staircasing Reduction Models 82
3 Algorithms for the Combined TV and H1 Models 86
4 A Modifed Staircasing Reduction Model 98
5 Conclusion 101
References 101
A Method for Total Variation-based Reconstruction of Noisy and Blurred Images 104
1 Introduction 104
2 Idea and New Method 106
3 Algorithms for Solving the Nonlinear System of Equations 108
4 Models and Blur Operators 111
5 Numerical Experiments and Discussions 112
References 115
Minimization of an Edge-Preserving Regularization Functional by Conjugate Gradient Type Methods 118
1 Introduction 118
2 Review of Two Phase Methods 119
3 Our Method 121
4 Convergence of the Method 122
5 Simulation 127
6 Conclusion 128
References 129
A Newton-type Total Variation Diminishing Flow 132
1 Introduction 132
2 A Newton-type Flow for the Minimization of the Area of Level- Sets 139
3 Geometric Properties 143
4 Numerical Examples 149
5 Conclusion 152
References 155
Chromaticity Denoising using Solution to the Skorokhod Problem 158
1 Introduction 158
2 Mathematical Preliminaries 159
3 Stochastic Representation of Solution to the Heat Equation 161
4 Image Denoising 164
5 A Numerical Scheme 168
References 168
Improved 3D Reconstruction of Interphase Chromosomes Based on Nonlinear Di . usion Filtering 172
1 Introduction 172
2 Improved Reconstruction of Interphase Chromosomes 174
3 Conclusion 180
Acknowledgment 180
References 180
Part III Image Segmentation 183
Some Recent Developments in Variational Image Segmentation 184
1 Introduction 185
2 Active Contours Methods 186
3 Multi-Channel Extensions in Chan–Vese Model 191
4 Multi-Phase Extensions 208
5 Fast Algorithms 213
6 Acknowledgment 216
References 216
Application of Non-Convex BV Regularization for Image Segmentation 220
1 Introduction 220
2 Review on the Mathematical Analysis of Evolution Processes 222
3 Variational Level Set Model for Image Segmentation 223
4 Relaxation 225
5 Numerical Simulations 232
6 Conclusion 235
References 236
Region-Based Variational Problems and Normal Alignment – Geometric Interpretation of Descent PDEs 238
1 Introduction 238
2 Background 239
3 Descent Directions 243
4 Region-Based Functionals 244
5 Quadratic Normal Alignment 251
6 Computing Gˆ ateaux Derivatives using Shape Gradients 254
7 Conclusions 256
References 256
Fast PCLSM with Newton Updating Algorithm 258
1 Introduction 258
2 PCLSM for Image Segmentation 259
3 Newton Updating 262
4 Numerical Examples 264
5 Conclusion 270
References 270
Part IV Fast Numerical Methods 273
Nonlinear Multilevel Schemes for Solving the Total Variation Image Minimization Problem 274
1 Introduction 274
2 Review of Unilevel Methods for the TV Formulation 276
3 Review of a Class of Multigrid Methods 280
4 NSSC Method for Equation (1) 284
5 Numerical Experiments 290
6 Conclusions 291
Acknowledgements 293
References 293
Fast Implementation of Piecewise Constant Level Set Methods 298
1 Introduction 298
2 Piecewise Constant Level Set Formulation 300
3 Operator Splitting Scheme 301
4 Operator Splitting and Newton Methods for Image Segmentation 303
5 The Algorithm 306
6 Numerical Experiments 309
7 Conclusion 314
References 316
The Multigrid Image Transform 318
1 Introduction 318
2 Recapitulation on Multigrid 319
3 The Multigrid Image Transform 322
4 Comparative Results 327
5 Concluding Remarks 328
References 332
Minimally Stochastic Schemes for Singular Di . usion Equations 334
1 Introduction 334
2 Schemes Based on Two Pixel Interaction 336
3 Numerical Experiments 341
4 Conclusion 342
References 347
Part V Image Registration 350
Total Variation Based Image Registration 352
1 Introduction. 352
2 Continuous Total Variation Minimization. 355
3 Numerical Minimization 358
4 Results 361
5 Summary and Conclusion 364
References 364
Variational Image Registration Allowing for Discontinuities in the Displacement Field 372
1 Introduction 373
2 Variational Approach 374
3 Variable Regularizer 378
4 Numerical Results 382
5 Conclusion and Outlook 384
References 386
Part VI Inverse Problems 388
Shape Reconstruction from Two-Phase Incompressible Flow Data using Level Sets 390
Summary 390
1 Introduction 390
2 The Reservoir Model 393
3 The Forward Problem 395
4 The Shape Reconstruction Problem 396
5 Formal Derivation of the Shape Evolution Algorithm 397
6 The Adjoint Technique for Calculating Sensitivities 399
7 The Algorithm 401
8 Numerical Examples 402
9 Conclusions and Future Work 406
Acknowledgments 408
References 408
Reservoir Description Using a Binary Level Set Approach with Additional Prior Information About the Reservoir Model 412
1 Introduction 412
2 The Inverse Problem 414
3 The Binary Level Set Approach 416
4 The Binary Level Set Method for the Inverse Problem 418
5 Numerical Optimisation 419
6 Numerical Results 420
7 Summary and Conclusions 431
8 Acknowledgements 432
9 Nomenclature 432
References 433
A Color Figures 436
From Image Inpainting Using a TV-Stokes Equation,” by Tai, Osher, and Holm 436
From Image Dejittering Based on Slicing Moments,” by Kang and Shen 444
From Chromaticity Denoising using Solution to the Skorokhod Problem,” by Borkowski 445
From Some Recent Developments in Variational Image Segmentation,” by Chan, Moelich, and Sandberg 446

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).