Geometric partial differential equations and image analysis (Q2704788)

This book is an introduction to the use of geometric partial differential equations (PDE) in image processing and computer vision. NEWLINENEWLINENEWLINEThe basic background material required to read the rest of the book is provided in Chapter~1. This includes some differential geometry (curves and surfaces in Euclidean space, affine differential geometry, Lie groups and differential invariants), some PDE topics (the maximum principle, hyperbolic conservation laws, viscosity solutions, the calculus of variations), and some facts from numerical analysis (finite difference approximations, stability, the Courant-Friedrichs-Lewy condition). NEWLINENEWLINENEWLINEIn Chapter 2 the basic concepts of curve and surface evolution are introduced, including the well-known level set formulation, which plays a central role in the book for a number of reasons: it is independent of the curve (or surface) parametrization, it automatically handles changes in topology, and there is a well-developed existence and uniqueness theory for viscosity solutions of very general level set flows. Two curve evolutions are emphasized: the Euclidean invariant flow NEWLINE\[NEWLINE {{\partial{\mathcal C}}\over{\partial t}} = \kappa {\mathcal N} \tag{1}NEWLINE\]NEWLINE and the affine invariant flow, which modulo reparametrization is given by NEWLINE\[NEWLINE {{\partial{\mathcal C}}\over{\partial t}} = \kappa^{1/3} {\mathcal N}. \tag{2}NEWLINE\]NEWLINE Here at each time \(t\) the curve \({\mathcal C}\) is given as an embedding (or possibly just an immersion) of an interval or of \({\mathbf S}^1\), and \(\kappa\) and \({\mathcal N}\) are the curvature and (inner) unit normal vector field respectively. The corresponding level set flows are NEWLINE\[NEWLINE {{\partial u}\over{\partial t}} = \kappa|\nabla u|\tag{3}NEWLINE\]NEWLINE and NEWLINE\[NEWLINE {{\partial u}\over{\partial t}} = \kappa^{1/3}|\nabla u|, \tag{4}NEWLINE\]NEWLINE where NEWLINE\[NEWLINE \kappa = \text{div}\left( {{\nabla u}\over|{\nabla u|}} \right) \tag{5}NEWLINE\]NEWLINE is the curvature of the level sets of \(u\), which is a function on \({\mathbb R}^2\times [0,T)\) for some \(T>0\). In (3) and (4) each nondegenerate level set of \(u\) moves according to the flows (1) and (2) respectively. A brief discussion of numerical implementations is also given. A large part of the chapter is concerned with proving that under the affine invariant flow (2) closed convex curves evolve to ellipses after rescaling to make the enclosed area constant. This parallels the well-known result of Gage and Hamilton for the flow (1). Higher-dimensional flows, such as the mean curvature flow, as well as area and volume preserving flows, are also discussed briefly. The chapter concludes with the classification of flows of planar curves, invariant under a subgroup of the projective group \(SL({\mathbb R},3)\). NEWLINENEWLINENEWLINEIn Chapter 3 the problem of edge detection in an image is discussed. An image is a function \(I:[0,a]\times[0,b] \rightarrow {\mathbb R}^+\). A basic problem then is to devise algorithms to detect the boundaries of objects in the image, that is, sets where \(|\nabla I|\) is large. The classical variational approach of energy-based active contours (snakes) is formulated and its disadvantages are discussed. This is then reformulated, with the help of Maupertuis' principle from dynamical systems, as the problem of finding geodesics in \([0,a]\times[0,b]\) equipped with a Riemannian metric determined by the image \(I\). This problem can then be studied by means of a geometric PDE (in the level set formulation) of the form NEWLINE\[NEWLINE {{\partial u}\over{\partial t}} = |\nabla u|\text{div} \left( g(|\nabla I|) {{\nabla u}\over|{\nabla u|}} \right) \tag{6}NEWLINE\]NEWLINE where \(g\) is an edge-stopping function: it is strictly decreasing and \(g(r)\rightarrow 0\) as \(r\rightarrow\infty\). Higher-dimensional analogues are also discussed (one then seeks minimal surfaces in a Riemannian manifold determined by the image), as are extensions to the case of vector-valued (colour) images. Affine invariant versions of the above problems are also discussed. NEWLINENEWLINENEWLINEChapters 4 and 5 deal with the problem of smoothing (or denoising) an image. The simplest way to do this is to use a Gaussian filter, which is the same as evolving the image \(I\) by the standard heat equation NEWLINE\[NEWLINE {{\partial I}\over{\partial t}} =\text{div}(\nabla I). \tag{7}NEWLINE\]NEWLINE This certainly smoothes the image, but it also blurs it. One therefore needs more refined techniques of removing noise without blurring edges. Perona and Malik proposed using the diffusion equation NEWLINE\[NEWLINE {{\partial I}\over{\partial t}} = \text{div} \left[ g(|\nabla I|)\nabla I \right] \tag{8}NEWLINE\]NEWLINE where \(g\) is an edge-stopping function. This diffusion equation is interpreted from the point of view of robust statistics. Several different choices of \(g\) are thus motivated, and their effectiveness is compared. Further techniques, and in particular, an affine invariant version of (8), are also discussed. Chapter 5 is concerned mainly with the extension of the results of Chapter 4 to vector-valued images. NEWLINENEWLINENEWLINEIn certain applications the image to be smoothed may be a mapping between two Riemannian manifolds rather than between two Euclidean spaces. It may, for example, take values in the unit sphere \({\mathbf S}^n\). The smoothing then needs to take this constraint into account. Corresponding to the heat equation (7) for scalar-valued images, one is then led to consider the harmonic map heat flow, and more generally, to handle anisotropic diffusion, the \(p\)-harmonic map heat flow with \(1\leq p < 2\). The analogue of (3) is the \(p\)-harmonic map equation with \(p=1\). These topics together with applications and numerical implementations are discussed in Chapter 6. NEWLINENEWLINENEWLINEChapter 7 is concerned with contrast enhancement, or histogram (pixel value distribution) modification. It is shown that this can be done using a suitable evolution equation for the image. A variational interpretation of the flow is also given, which also makes it clear how to formulate a local version of the flow. It is also shown how to combine the histogram flow with previously discussed smoothing techniques to simultaneously achieve smoothing and contrast enhancement. NEWLINENEWLINENEWLINEThe final chapter deals with interpolation, or the filling in of regions that are missing in an image. This has obvious applications: restoring damaged photographs and films, removing unwanted features such as red eyes, etc. A digital inpainting algorithm for achieving these goals is described. Some related topics are also discussed briefly. NEWLINENEWLINENEWLINEThe author's intention was to provide an introduction to the diverse uses of geometric PDE to image processing. He does this quite successfully. The reader may need to consult other sources for more detailed expositions of certain topics that are discussed only briefly. Suitable references for this are provided throughout the book. The effectiveness of the various techniques presented is illustrated with numerous pictures, as one would expect in a book on image processing. As the bibliography of 430 items shows, image processing is a large and rapidly developing field. This book is a useful introduction to the subject.