Springer Press：Geometric Curve Evolution and Image Processing PDF文件 Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V Part I The curve smoothing problem 1 Curve evolution and image processing . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Shape recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Axioms for shape recognition... . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 ... and their consequ ences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Curve smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 The linear curve scale space . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Towards an intrinsic heat equation . . . . . . . . . . . . . . . . . . . . . 10 1.3 An axiomatic approach of curve evolution . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Basic requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 First conclusions and first models . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Image and contour smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.1 Active contours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.2 Principles of a shape recognition algorithm . . . . . . . . . . . . . . 17 1.5.3 Optical character recognition . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Organization of the volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.7 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Rudimentary bases of curve geometry . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1 Jordan curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Length of a curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Euclidean parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 Motion of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 VIII Contents Part II Theoretical curve evolution 3 Geometric curve shortening flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1 What kind of equations for curve smoothing? . . . . . . . . . . . . . . . . . . 32 3.1.1 Invariant flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.2 Symmetry group of flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Differential invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.1 General form of invariant flows . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.2 The mean curvature flow is the Euclidean intrinsic heat flow 42 3.2.3 The affine invariant flow: the simplest affine invariant curve flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 General properties of second order parabolic flows: a digest . . . . . . 46 3.3.1 Existence and uniqueness for mean curvature and affine flows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.2 Short-time existence in the general case . . . . . . . . . . . . . . . . 48 3.3.3 Evolution of convex curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.4 Evolution of the length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.5 Evolution of the area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4 Smoothing staircases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 Curve evolution and level sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1 From curve operators to function operators and vice versa . . . . . . . . 57 4.1.1 Signed distance function and supporting function . . . . . . . . 57 4.1.2 Monotone and translation invariant operators . . . . . . . . . . . . 57 4.1.3 Level sets and their properties . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.1.4 Extension of sets operators to functions operators . . . . . . . . 60 4.1.5 Characterization of monotone, contrast invariant operator . 62 4.1.6 Asymptotic behavior of morphological operators . . . . . . . . . 64 4.1.7 Morphological operators yield PDEs . . . . . . . . . . . . . . . . . . . 69 4.2 Curve evolution and Scale Space theory . . . . . . . . . . . . . . . . . . . . . . . 70 4.2.1 Multiscale analysis are given by PDEs . . . . . . . . . . . . . . . . . 70 4.2.2 Morphological scale space . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 Viscosity solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.3.1 Definition of viscosity solution . . . . . . . . . . . . . . . . . . . . . . . . 76 4.3.2 Proof of uniqueness: the maximum principle . . . . . . . . . . . . 80 4.3.3 Existence of solution by Perron’s Method . . . . . . . . . . . . . . . 85 4.3.4 Contrast invariance of level sets flow . . . . . . . . . . . . . . . . . . . 88 4.3.5 Viscosity solutions shorten level lines . . . . . . . . . . . . . . . . . . 89 4.4 Morphological operators and viscosity solution. . . . . . . . . . . . . . . . . 90 4.4.1 Median filter and mean curvature motion . . . . . . . . . . . . . . . 90 4.4.2 Affine invariant schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.6 Curvature thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Contents IX 4.6.1 Viscosity approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.6.2 Opening and closing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.7 Alternative weak solutions of curve evolution . . . . . . . . . . . . . . . . . . 100 4.7.1 Brakke’s varifold solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.7.2 Reaction diffusion approximation. . . . . . . . . . . . . . . . . . . . . . 100 4.7.3 Minimal barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.8 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Part III Numerical curve evolution 5 Classical numerical methods for curve evolution . . . . . . . . . . . . . . . . 107 5.1 Parametric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.1.1 Finite difference methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.1.2 Finite element schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2 Non parametric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2.1 Sethian’s level sets methods . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2.2 Alvarez and Guichard’s finite differences scheme . . . . . . . . 109 5.2.3 A monotone and convergent finite difference schemes . . . . . 109 5.2.4 Bence, Merriman and Osher scheme for mean curvature motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.2.5 Elliptic regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6 A geometrical scheme for curve evolution . . . . . . . . . . . . . . . . . . . . . . 111 6.1 Preliminary definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2 Erosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3 Properties of the erosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4 Erosion and level sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.4.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.5 Evolution by a power of the curvature . . . . . . . . . . . . . . . . . . . . . . . . 124 6.5.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.5.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.6 A numerical implementation of the erosion . . . . . . . . . . . . . . . . . . . . 133 6.6.1 Scale covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.6.2 General algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.6.3 Eroded set and envelope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 6.6.4 Swallow tails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.7 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.7.1 Evolving circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.7.2 Convex polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.7.3 Unclosed curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.7.4 Evolving non convex curves . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.7.5 Invariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 6.7.6 Numerical maximum principle . . . . . . . . . . . . . . . . . . . . . . . . 152 X Contents 6.7.7 Image filtering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.8 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Conclusion and perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 A Proof of Thm. 4.34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 ences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Curve smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 The linear curve scale space . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Towards an intrinsic heat equation . . . . . . . . . . . . . . . . . . . . . 10 1.3 An axiomatic approach of curve evolution . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Basic requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 First conclusions and first models . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Image and contour smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.1 Active contours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.2 Principles of a shape recognition algorithm . . . . . . . . . . . . . . 17 1.5.3 Optical character recognition . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Organization of the volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.7 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Rudimentary bases of curve geometry . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1 Jordan curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Length of a curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Euclidean parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 Motion of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 VIII Contents Part II Theoretical curve evolution 3 Geometric curve shortening flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1 What kind of equations for curve smoothing? . . . . . . . . . . . . . . . . . . 32 3.1.1 Invariant flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.2 Symmetry group of flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Differential invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.1 General form of invariant flows . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.2 The mean curvature flow is the Euclidean intrinsic heat flow 42 3.2.3 The affine invariant flow: the simplest affine invariant curve flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 General properties of second order parabolic flows: a digest . . . . . . 46 3.3.1 Existence and uniqueness for mean curvature and affine flows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.2 Short-time existence in the general case . . . . . . . . . . . . . . . . 48 3.3.3 Evolution of convex curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.4 Evolution of the length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.5 Evolution of the area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4 Smoothing staircases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 Curve evolution and level sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1 From curve operators to function operators and vice versa . . . . . . . . 57 4.1.1 Signed distance function and supporting function . . . . . . . . 57 4.1.2 Monotone and translation invariant operators . . . . . . . . . . . . 57 4.1.3 Level sets and their properties . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.1.4 Extension of sets operators to functions operators . . . . . . . . 60 4.1.5 Characterization of monotone, contrast invariant operator . 62 4.1.6 Asymptotic behavior of morphological operators . . . . . . . . . 64 4.1.7 Morphological operators yield PDEs . . . . . . . . . . . . . . . . . . . 69 4.2 Curve evolution and Scale Space theory . . . . . . . . . . . . . . . . . . . . . . . 70 4.2.1 Multiscale analysis are given by PDEs . . . . . . . . . . . . . . . . . 70 4.2.2 Morphological scale space . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 Viscosity solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.3.1 Definition of viscosity solution . . . . . . . . . . . . . . . . . . . . . . . . 76 4.3.2 Proof of uniqueness: the maximum principle . . . . . . . . . . . . 80 4.3.3 Existence of solution by Perron’s Method . . . . . . . . . . . . . . . 85 4.3.4 Contrast invariance of level sets flow . . . . . . . . . . . . . . . . . . . 88 4.3.5 Viscosity solutions shorten level lines . . . . . . . . . . . . . . . . . . 89 4.4 Morphological operators and viscosity solution. . . . . . . . . . . . . . . . . 90 4.4.1 Median filter and mean curvature motion . . . . . . . . . . . . . . . 90 4.4.2 Affine invariant schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.6 Curvature thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Contents IX 4.6.1 Viscosity approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.6.2 Opening and closing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.7 Alternative weak solutions of curve evolution . . . . . . . . . . . . . . . . . . 100 4.7.1 Brakke’s varifold solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.7.2 Reaction diffusion approximation. . . . . . . . . . . . . . . . . . . . . . 100 4.7.3 Minimal barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.8 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Part III Numerical curve evolution 5 Classical numerical methods for curve evolution . . . . . . . . . . . . . . . . 107 5.1 Parametric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.1.1 Finite difference methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.1.2 Finite element schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2 Non parametric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2.1 Sethian’s level sets methods . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2.2 Alvarez and Guichard’s finite differences scheme . . . . . . . . 109 5.2.3 A monotone and convergent finite difference schemes . . . . . 109 5.2.4 Bence, Merriman and Osher scheme for mean curvature motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.2.5 Elliptic regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6 A geometrical scheme for curve evolution . . . . . . . . . . . . . . . . . . . . . . 111 6.1 Preliminary definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2 Erosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3 Properties of the erosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.4 Erosion and level sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.4.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.5 Evolution by a power of the curvature . . . . . . . . . . . . . . . . . . . . . . . . 124 6.5.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.5.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.6 A numerical implementation of the erosion . . . . . . . . . . . . . . . . . . . . 133 6.6.1 Scale covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.6.2 General algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.6.3 Eroded set and envelope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 6.6.4 Swallow tails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.7 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.7.1 Evolving circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.7.2 Convex polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.7.3 Unclosed curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.7.4 Evolving non convex curves . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.7.5 Invariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 6.7.6 Numerical maximum principle . . . . . . . . . . . . . . . . . . . . . . . . 152 X Contents 6.7.7 Image filtering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.8 Bibliographical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Conclusion and perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 A Proof of Thm. 4.34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185