Contents Foreword vii Preface to the Second Edition xi Preface to the First Edition xv Guide to the Main Mathematical Concepts and Their Application xxv Notation and Symbols xxvii 1 Introduction 1 1.1 The Image Society.....................1 1.2 What Is a Digital Image?..................3 1.3 About Partial Di?erential Equations(PDEs) .......5 1.4 Detailed Plan........................5 2 Mathematical Preliminaries 29 How to Read This Chapter....................29 2.1 The Direct Method in the Calculus of Variations.....30 2.1.1 Topologies on Banach Spaces...........30 2.1.2 Convexity and Lower Semicontinuity.......32 2.1.3 Relaxation......................37 2.1.4 AboutΓ-Convergence................40 2.2 The Space of Functions of Bounded Variation......42xx Contents 2.2.1 Basic Definitions on Measures...........43 2.2.2 Definition of BV(?)................45 2.2.3 Properties of BV(?)................46 2.2.4 Convex Functions of Measures...........50 2.3 Viscosity Solutions in PDEs................50 2.3.1 About the Eikonal Equation............50 2.3.2 Definition of Viscosity Solutions..........52 2.3.3 About the Existence................54 2.3.4 About the Uniqueness...............55 2.4 Elements of Di?erential Geometry:Curvature......57 2.4.1 Parametrized Curves................58 2.4.2 Curves as Isolevel of a Function u.........58 2.4.3 Images as Surfaces.................59 2.5 Other Classical Results Used in This Book........60 2.5.1 Inequalities.....................60 2.5.2 Calculus Facts....................62 2.5.3 About Convolution and Smoothing........62 2.5.4 Uniform Convergence................63 2.5.5 Dominated Convergence Theorem.........64 2.5.6 Well-Posed Problems................64 3 Image Restoration 65 How to Read This Chapter....................65 3.1 Image Degradation.....................66 3.2 The Energy Method.....................68 3.2.1 An Inverse Problem.................68 3.2.2 Regularization of the Problem...........69 3.2.3 Existence and Uniqueness of a Solution for the Minimization Problem.............72 3.2.4 Toward the Numerical Approximation......76 The Projection Approach..............76 The Half-Quadratic Minimization Approach...79 3.2.5 Some Invariances and the Role ofλ........87 3.2.6 Some Remarks on the Nonconvex Case......90 3.3 PDE-Based Methods....................94 3.3.1 Smoothing PDEs..................95 The Heat Equation.................95 Nonlinear Di?usion.................98 The Alvarez–Guichard–Lions–Morel Scale Space Theory.................107 Weickert’s Approach................113 Surface Based Approaches.............117 3.3.2 Smoothing–Enhancing PDEs............121 The Perona and Malik Model...........121Contents xxi Regularization of the Perona and Malik Model: Catt′e et al......................123 3.3.3 Enhancing PDEs..................128 The Osher and Rudin Shock Filters........128 A Case Study:Construction of a Solution by the Method of Characteristics...........130 Comments on the Shock-Filter Equation.....134 3.3.4 Neighborhood Filters,Nonlocal Means Algorithm, and PDEs......................137 Neighborhood Filters................138 How to Suppress the Staircase E?ect?......143 Nonlocal Means Filter(NL-Means)........146 4 The Segmentation Problem 149 How to Read This Chapter....................149 4.1 Definition and Objectives..................150 4.2 The Mumford and Shah Functional............153 4.2.1 A Minimization Problem..............153 4.2.2 The Mathematical Framework for the Existence of a Solution...............154 4.2.3 Regularity of the Edge Set.............162 4.2.4 Approximations of the Mumford and Shah Functional......................166 4.2.5 Experimental Results................171 4.3 Geodesic Active Contours and the Level-Set Method...173 4.3.1 The Kass–Witkin–Terzopoulos model.......173 4.3.2 The Geodesic Active Contours Model.......175 4.3.3 The Level-Set Method...............182 4.3.4 The Reinitialization Equation...........194 Characterization of the Distance Function....195 Existence and Uniqueness.............198 4.3.5 Experimental Results................206 4.3.6 About Some Recent Advances...........208 Global Stopping Criterion.............208 Toward More General Shape Representation...211 5 Other Challenging Applications 213 How to Read This Chapter....................213 5.1 Reinventing Some Image Parts by Inpainting.......215 5.1.1 Introduction.....................215 5.1.2 Variational Models.................216 The Masnou and Morel Approach.........216 The Ballester et al.Approach...........218 The Chan and Shen Total Variation Minimization Approach.................220xxii Contents 5.1.3 PDE-Based Approaches..............222 The Bertalmio et al.Approach...........223 The Chan and Shen Curvature-Driven Di?usion Approach.................224 5.1.4 Discussion......................225 5.2 Decomposing an Image into Geometry and Texture...228 5.2.1 Introduction.....................228 5.2.2 A Space for Modeling Oscillating Patterns....229 5.2.3 Meyer’s Model....................232 5.2.4 An Algorithm to Solve Meyer’s Model......233 Prior Numerical Contribution...........234 The Aujol et al.Approach.............234 Study of the Asymptotic Case...........241 Back to Meyer’s Model...............242 5.2.5 Experimental Results................245 Denoising Capabilities...............245 Dealing With Texture...............248 5.2.6 About Some Recent Advances...........248 5.3 Sequence Analysis......................249 5.3.1 Introduction.....................249 5.3.2 The Optical Flow:An Apparent Motion.....250 The Optical Flow Constraint(OFC).......252 Solving the Aperture Problem...........253 Overview of a Discontinuity-Preserving Variational Approach................256 Alternatives to the OFC..............260 5.3.3 Sequence Segmentation...............261 Introduction.....................261 A Variational Formulation.............264 Mathematical Study of the Time-Sampled Energy...............265 Experiments.....................269 5.3.4 Sequence Restoration................271 Principles of Video Inpainting...........276 Total Variation(TV)Minimization Approach..277 Motion Compensated(MC)Inpainting......277 5.4 Image Classification.....................281 5.4.1 Introduction.....................281 5.4.2 A Level-Set Approach for Image Classification.................282 5.4.3 A Variational Model for Image Classification and Restoration.....................290 5.5 Vector-Valued Images....................299 5.5.1 Introduction.....................299 5.5.2 An Extended Notion of Gradient.........300Contents xxiii 5.5.3 The Energy Method................300 5.5.4 PDE-Based Methods................302 A Introduction to Finite Di?erence Methods 307 How to Read This Chapter....................307 A.1 Definitions and Theoretical Considerations Illustrated by the 1-D Parabolic Heat Equation............308 A.1.1 Getting Started...................308 A.1.2 Convergence.....................311 A.1.3 The Lax Theorem..................313 A.1.4 Consistency.....................313 A.1.5 Stability.......................315 A.2 Hyperbolic Equations....................320 A.3 Di?erence Schemes in Image Analysis...........329 A.3.1 Getting Started...................329 A.3.2 Image Restoration by Energy Minimization...333 A.3.3 Image Enhancement by the Osher and Rudin Shock Filters....................336 A.3.4 Curve Evolution with the Level-Set Method...338 Mean Curvature Motion..............339 Constant Speed Evolution.............340 The Pure Advection Equation...........341 Image Segmentation by the Geodesic Active Contour Model...............342 B Experiment Yourself!343 How to Read This Chapter....................343 B.1 The CImg Library......................344 B.2 What Is Available Online?.................344 References 349 Index 373 .......5 1.4 Detailed Plan........................5 2 Mathematical Preliminaries 29 How to Read This Chapter....................29 2.1 The Direct Method in the Calculus of Variations.....30 2.1.1 Topologies on Banach Spaces...........30 2.1.2 Convexity and Lower Semicontinuity.......32 2.1.3 Relaxation......................37 2.1.4 AboutΓ-Convergence................40 2.2 The Space of Functions of Bounded Variation......42xx Contents 2.2.1 Basic Definitions on Measures...........43 2.2.2 Definition of BV(?)................45 2.2.3 Properties of BV(?)................46 2.2.4 Convex Functions of Measures...........50 2.3 Viscosity Solutions in PDEs................50 2.3.1 About the Eikonal Equation............50 2.3.2 Definition of Viscosity Solutions..........52 2.3.3 About the Existence................54 2.3.4 About the Uniqueness...............55 2.4 Elements of Di?erential Geometry:Curvature......57 2.4.1 Parametrized Curves................58 2.4.2 Curves as Isolevel of a Function u.........58 2.4.3 Images as Surfaces.................59 2.5 Other Classical Results Used in This Book........60 2.5.1 Inequalities.....................60 2.5.2 Calculus Facts....................62 2.5.3 About Convolution and Smoothing........62 2.5.4 Uniform Convergence................63 2.5.5 Dominated Convergence Theorem.........64 2.5.6 Well-Posed Problems................64 3 Image Restoration 65 How to Read This Chapter....................65 3.1 Image Degradation.....................66 3.2 The Energy Method.....................68 3.2.1 An Inverse Problem.................68 3.2.2 Regularization of the Problem...........69 3.2.3 Existence and Uniqueness of a Solution for the Minimization Problem.............72 3.2.4 Toward the Numerical Approximation......76 The Projection Approach..............76 The Half-Quadratic Minimization Approach...79 3.2.5 Some Invariances and the Role ofλ........87 3.2.6 Some Remarks on the Nonconvex Case......90 3.3 PDE-Based Methods....................94 3.3.1 Smoothing PDEs..................95 The Heat Equation.................95 Nonlinear Di?usion.................98 The Alvarez–Guichard–Lions–Morel Scale Space Theory.................107 Weickert’s Approach................113 Surface Based Approaches.............117 3.3.2 Smoothing–Enhancing PDEs............121 The Perona and Malik Model...........121Contents xxi Regularization of the Perona and Malik Model: Catt′e et al......................123 3.3.3 Enhancing PDEs..................128 The Osher and Rudin Shock Filters........128 A Case Study:Construction of a Solution by the Method of Characteristics...........130 Comments on the Shock-Filter Equation.....134 3.3.4 Neighborhood Filters,Nonlocal Means Algorithm, and PDEs......................137 Neighborhood Filters................138 How to Suppress the Staircase E?ect?......143 Nonlocal Means Filter(NL-Means)........146 4 The Segmentation Problem 149 How to Read This Chapter....................149 4.1 Definition and Objectives..................150 4.2 The Mumford and Shah Functional............153 4.2.1 A Minimization Problem..............153 4.2.2 The Mathematical Framework for the Existence of a Solution...............154 4.2.3 Regularity of the Edge Set.............162 4.2.4 Approximations of the Mumford and Shah Functional......................166 4.2.5 Experimental Results................171 4.3 Geodesic Active Contours and the Level-Set Method...173 4.3.1 The Kass–Witkin–Terzopoulos model.......173 4.3.2 The Geodesic Active Contours Model.......175 4.3.3 The Level-Set Method...............182 4.3.4 The Reinitialization Equation...........194 Characterization of the Distance Function....195 Existence and Uniqueness.............198 4.3.5 Experimental Results................206 4.3.6 About Some Recent Advances...........208 Global Stopping Criterion.............208 Toward More General Shape Representation...211 5 Other Challenging Applications 213 How to Read This Chapter....................213 5.1 Reinventing Some Image Parts by Inpainting.......215 5.1.1 Introduction.....................215 5.1.2 Variational Models.................216 The Masnou and Morel Approach.........216 The Ballester et al.Approach...........218 The Chan and Shen Total Variation Minimization Approach.................220xxii Contents 5.1.3 PDE-Based Approaches..............222 The Bertalmio et al.Approach...........223 The Chan and Shen Curvature-Driven Di?usion Approach.................224 5.1.4 Discussion......................225 5.2 Decomposing an Image into Geometry and Texture...228 5.2.1 Introduction.....................228 5.2.2 A Space for Modeling Oscillating Patterns....229 5.2.3 Meyer’s Model....................232 5.2.4 An Algorithm to Solve Meyer’s Model......233 Prior Numerical Contribution...........234 The Aujol et al.Approach.............234 Study of the Asymptotic Case...........241 Back to Meyer’s Model...............242 5.2.5 Experimental Results................245 Denoising Capabilities...............245 Dealing With Texture...............248 5.2.6 About Some Recent Advances...........248 5.3 Sequence Analysis......................249 5.3.1 Introduction.....................249 5.3.2 The Optical Flow:An Apparent Motion.....250 The Optical Flow Constraint(OFC).......252 Solving the Aperture Problem...........253 Overview of a Discontinuity-Preserving Variational Approach................256 Alternatives to the OFC..............260 5.3.3 Sequence Segmentation...............261 Introduction.....................261 A Variational Formulation.............264 Mathematical Study of the Time-Sampled Energy...............265 Experiments.....................269 5.3.4 Sequence Restoration................271 Principles of Video Inpainting...........276 Total Variation(TV)Minimization Approach..277 Motion Compensated(MC)Inpainting......277 5.4 Image Classification.....................281 5.4.1 Introduction.....................281 5.4.2 A Level-Set Approach for Image Classification.................282 5.4.3 A Variational Model for Image Classification and Restoration.....................290 5.5 Vector-Valued Images....................299 5.5.1 Introduction.....................299 5.5.2 An Extended Notion of Gradient.........300Contents xxiii 5.5.3 The Energy Method................300 5.5.4 PDE-Based Methods................302 A Introduction to Finite Di?erence Methods 307 How to Read This Chapter....................307 A.1 Definitions and Theoretical Considerations Illustrated by the 1-D Parabolic Heat Equation............308 A.1.1 Getting Started...................308 A.1.2 Convergence.....................311 A.1.3 The Lax Theorem..................313 A.1.4 Consistency.....................313 A.1.5 Stability.......................315 A.2 Hyperbolic Equations....................320 A.3 Di?erence Schemes in Image Analysis...........329 A.3.1 Getting Started...................329 A.3.2 Image Restoration by Energy Minimization...333 A.3.3 Image Enhancement by the Osher and Rudin Shock Filters....................336 A.3.4 Curve Evolution with the Level-Set Method...338 Mean Curvature Motion..............339 Constant Speed Evolution.............340 The Pure Advection Equation...........341 Image Segmentation by the Geodesic Active Contour Model...............342 B Experiment Yourself!343 How to Read This Chapter....................343 B.1 The CImg Library......................344 B.2 What Is Available Online?.................344 References 349 Index 373