主动轮廓模型介绍：EVERYTHING_YOU_ALWAYS_WANTED_TO_KNOW_ABOUT_SNAKES_(BUT_WERE_AFRAID_TO_ASK)

EVERYTHING YOU ALWAYS WANTED TO KNOW ABOUT SNAKES (BUT WERE AFRAID TO ASK) Jim Ivins† & John Porrill AIVRU Technical Memo #86, July 1993 (Revised June 1995; March 2000) Artificial Intelligence Vision Research Unit University Of Sheffield England S10 2TP “Reeling and Writhing, of course, to begin with,” the Mock Turtle replied; “and then the different branches of Arithmetic – Ambition, Distraction, Uglification, and Derision.” Alice’s Adventures In Wonderland, by Lewis Carroll † Please send feedback and corrections regarding this document to Jim Ivins. E-mail: ivinsj@cs.curtin.edu.au. ABSTRACT Active contour models – known colloquially as snakes – are energy-minimising curves that deform to fit image features. Snakes lock on to nearby minima in the potential energy gener- ated by processing an image. (This energy is minimised by iterative gradient descent accord- ing to forces derived using variational calculus and Euler-Lagrange Theory.) In addition, internal (smoothing) forces produce tension and stiffness that constrain the behaviour of the models; external forces may be specified by a supervising process or a human user. As is characteristic of gradient descent, the energy minimisation process is unfortunately prone to oscillation unless precautions – typically the use of small time steps – are taken. Active contour models provide a unified solution to several image processing problems such as the detection of light and dark lines, edges, and terminations; they can also be used in stereo matching, and for segmenting spatial and temporal image sequences. Snakes have often been used in medical research applications; for example, in reconstructing three- dimensional features from planar slices of volume data such as NMR or CT images. In addition, many motion tracking systems use snakes to model moving objects. The main limitations of the models are (i) that they usually only incorporate edge information (ignoring other image characteristics) possibly combined with some prior expectation of shape; and (ii) that they must be initialised close to the feature of interest if they are to avoid being trapped by other local minima. KEY WORDS � Calculus Of Variations � Euler-Lagrange Theory � Gradient Descent � Snakes: Active Contour Models LICENSE Copyright (C) 1993–2000 Jim Ivins & John Porrill AIVRU, University of Sheffield, England S10 2TP. Verbatim copying and distribution of this entire document is permitted in any medium, provided this notice is preserved, but changing it is not allowed. Everything You Always Wanted To Know About Snakes… Page 2 Zhang Hannan 高亮 Zhang Hannan 高亮 Zhang Hannan 高亮 1 INTRODUCTION Low-level visual tasks such as edge detection and stereo matching are often treated as autono- mous bottom-up processes. However, this sequential approach propagates mistakes to higher processes without providing opportunities for correction. A more attainable goal for low-level processing is to provide several interpretations of the image data, from which higher processes† or a human user may choose. Active contour models – first described by Kass et al (1987; 1988) – provide one possible method for generating these alternative interpretations. Active contour models are often called snakes because they appear to slither across images (a phenomenon known as hysteresis); they are one example of the general technique of matching a deformable model to an image using energy minimisation. From any starting point, subject to certain constraints, a snake will deform into alignment with the nearest salient feature in a suitably processed image; such features correspond to local minima in the energy generated by processing the image. Snakes thus provide a low-level mechanism that seeks appropriate local minima rather than searching for a global solution. In addition, high-level mechanisms can interact with snakes – for example, to guide them towards features of interest. Unlike most other techniques for finding image features, snakes are always minimis- ing their energy. Changes in high-level interpretation can therefore affect a snake during the minimisation process, and even in the absence of such changes the model will still exhibit hysteresis in response to a moving stimulus. Snakes do not try to solve the entire problem of finding salient image features; they rely on other mechanisms to place them somewhere near a desired solution. For example, automatic initialisation procedures can use standard image processing techniques to locate features of interest that are then refined using snakes. Even in cases where automatic initiali- sation is not possible, however, active contour models can still be used for image interpreta- tion. An expert user need only push a snake towards an image feature, and the energy minimi- sation process will fit the model to the data. This behaviour has been exploited in numerous interactive image processing systems – for example, see Kass et al (1987; 1988); Hill et al (1992); Porrill and Ivins (1994). A snake is typically driven by a potential energy generated by processing the underly- ing image data. For example, Gaussian smoothing followed by convolution with a Everything You Always Wanted To Know About Snakes… Page 3 † Scott (1987) is critical of this philosophy because the unspecified high-level process rarely materialise except in human form! Zhang Hannan 高亮 Zhang Hannan 高亮 Zhang Hannan 高亮 Zhang Hannan Underline gradient-squared operator generates a potential in which extrema correspond to edges in the original image. Over a series of iterations the force generated by this energy drives the snake into alignment with the nearest salient edge. However, the snake must also satisfy some inter- nal constraints – for example, it must be smooth and continuous in outline. Sometimes the user imposes additional external constraints such as attraction or repulsion. Edge: New Snake (Time t+1): Current Snake (Time t): Movement: Figure 1: A Closed Active Contour Model. This diagram shows a snake with its ends joined so that it forms a closed loop. Over a series of time steps the snake moves into alignment with the nearest salient feature (in this case an edge). Both internal and external energy constraints are discussed in Section 2; potential energy is discussed in Section 3. Section 4 uses these energy terms to derive explicit forces that can be used to drive active contour models to minimise their energy by iterative gradient descent. The original (semi-implicit) method proposed by Kass et al (1987), which is related to the explicit use of forces, is then described in the next two sections. First, the calculus of varia- tions is used to derive the Euler-Lagrange equation in Section 5; this equation is then used to find the minimum energy condition for an active contour model. Section 6 explains how to solve the minimum energy equation using a semi-implicit relaxation method based on a fast matrix inversion algorithm. (Both the explicit and semi-implicit methods use finite differences to compute derivatives as described in Appendix A; Appendix B contains six mathematical notes that provide simple background information.) Oscillation, the main drawback of relaxa- tion methods, is discussed in Section 7. Finally, Section 8 considers the use of inter-snake energy terms in three of the most common applications – stereo matching, and segmentation of spatial and temporal image sequences. Everything You Always Wanted To Know About Snakes… Page 4 Zhang Hannan Highlight Zhang Hannan Underline Zhang Hannan Underline Zhang Hannan Underline 2 SNAKE ENERGY FUNCTIONALS A snake is a parametric contour that deforms over a series of iterations (time steps). Each element x along the contour therefore depends on two parameters: x(s, t)    s = space (curve) parameter t = time (iteration) parameter The contour is influenced by internal and external constraints, and by image forces, as outlined below. � Internal forces. Internal constraints give the model tension and stiffness. � External forces. External constraints come from high-level sources such as human operators or automatic initialisation procedures. � Image forces. Image energy is used to drive the model towards salient features such as light and dark regions, edges, and terminations. Representing a snake parametrically as explained in Mathematical Note 1, x(s) = ( x(s), y(s) ) where s is usually taken to vary between 0 and 1. The total energy of the model Esnake is given by the sum of the energy for the individual snake elements:† (2.1)Esnake = �0 1 Eelement( x(s) ) ds The integral notation used in this section implies an open-ended snake; however, joining the first and last elements makes the snake into a closed loop as shown in Figure 1. Equation 2.1 can be rewritten in terms of three basic energy functionals:†† (2.2)Esnake = �0 1 Eintern(x) ds + �0 1 Eextern(x) ds + �0 1 Eimage(x) ds The curve parameter s is omitted where no ambiguity arises. The gradients of the three energy functionals in Equation 2.2 correspond to the three forces listed above. The internal and exter- nal energy functionals are considered in more detail below; image (potential) energy is dealt with in the next section. Everything You Always Wanted To Know About Snakes… Page 5 †† A functional is a function of one or more functions, giving a scalar result. † To implement an active contour model in computer software the continuous represen- tation is approximated discretely by N snake elements; however, continuous notation is used wherever possible because of its greater mathematical elegance. 2.1 INTERNAL (INTRA-SNAKE) ENERGY Using subscripts to indicate derivatives, the internal energy of a snake element is defined as: (2.3)Eintern(x) = Tension �(s) xs(s) 2 + Stiffness �(s) xss(s) 2 This energy contains a first-order term controlled by α(s), and a second-order term controlled by β(s). The first-order term makes the snake contract like an elastic band by introducing tension; the second-order term makes it resist bending by producing stiffness. In other words, the parametric curve is predisposed to have constant (preferably zero) ‘velocity’ and ‘accelera- tion’ with respect to its parameter. In the absence of other constraints, an active contour model simply collapses to a point like a strip of infinitely-elastic material; however, if the ends of the model are anchored then it forms a straight line along which the elements are evenly spaced. Adjusting the weights α(s) and β(s) controls the relative importance of the tension and stiffness terms. For example, setting β(s) = 0 in one part of the model allows it to become second-order discontinuous and develop a corner. For simplicity, the tension and stiffness weightings are assumed to be uniform throughout the remainder of this document, so that α(s) = α and β(s) = β. 2.2 EXTERNAL (EXTRA-SNAKE) ENERGY Both automatic and manual supervision can be used to control attraction and repulsion forces that drive active contour models to or from specified features. For example, a spring-like attractive force can be generated between a snake element and a point i in an image using the following external energy term: (2.4)Eextern(x) = k i − x 2 This energy is minimal (zero) when x = i, and it takes the value of k when i – x = ±1 as shown in Figure 2. Mathematical Note 2 reviews the properties of extrema in functions. An external energy term Eextern can also be used to make part of an image repel an active contour model: (2.5)Eextern(x) = ki − x 2 This energy is maximal (infinite) when x = i; it is unity when i – x = ± k. Because of the singularity, the repulsion term must be clipped as the denominator approaches zero. Everything You Always Wanted To Know About Snakes… Page 6 Negating the (positive) constant k in these equations converts attraction to pseudo- repulsion, and repulsion to pseudo-attraction; however, these pseudo energy terms are unusable because their minima are infinite. (During energy minimisation, the singularities completely dominate the behaviour of an active contour model, at the expense of all other energy terms.) The forces produced by these energy terms are easily found by differentiation. ∞ ∞ ∞ (a) Attractive Energy (b) Repulsive Energy E E k +k– k 1 +1–1 i–xi–x 0 0 Figure 2: Attraction And Repulsion Energy. These graphs show the attractive and repulsive energy terms. Both functionals have maximal values that are infinite; the minima are zero. Everything You Always Wanted To Know About Snakes… Page 7 3 IMAGE (POTENTIAL) ENERGY FUNCTIONALS The potential energy P generated by processing an image I(x, y) produces a force that can be used to drive snakes towards features of interest. Three different potential (image) energy functionals are described below; these attract snakes to lines, edges, and terminations. The total potential energy can be expressed as a weighted combination of these functionals: (3.1)P = Eimage = wlineEline + wedgeEedge + wtermEterm The nearest local minimum the potential energy can be found using gradient descent as described in Section 4: (3.2)x � x + �x The image forces δx produced by each of the terms in Equation 3.1 are derived below, in advance of the main discussion of energy minimisation and forces in Sections 4–6. If just a small portion of an active contour model finds a low-energy image feature then the internal constraints will pull neighbouring elements towards that feature. This effect can be enhanced by spatially smoothing the potential energy field. Typically, a snake is first allowed to reach equilibrium on a very smooth potential; the blurring is then gradually reduced – see Witkin et al (1986). At very coarse scales the snake does a poor job of localis- ing features, and fine detail is lost; however, it is attracted to local minima from far away. Reducing the amount of blurring allows the snake to form a more accurate model of the underlying image. 3.1 REGION FUNCTIONAL The simplest potential energy is the unprocessed image intensity so that P(x) = I(x): (3.3)Eline = �0 1 I( x(s) ) ds According to the sign of wline in Equation 3.1, the snake will be attracted either to light or dark regions of the image. Using ∇ to indicate image gradient, the corresponding image force δx is given by: �x � − �P�x = − �I �x = − �I(x) Local minima in the image intensity can therefore be found by taking small steps in x: (3.4)x � x − � �I(x) The positive time step τ is chosen to suit the problem domain; however, it is almost invariably one or two orders of magnitude less than unity to prevent oscillation (see Section 7). For an Everything You Always Wanted To Know About Snakes… Page 8 extension of this idea for segmenting textures and colours see the work on active region models by Ivins and Porrill (1995). 3.2 EDGE FUNCTIONAL By far the most common use for active contour models is as semi-global edge-detectors that minimise a potential energy in which minima correspond to strong edges – see Figure 3. (a) Unprocessed Image (b) Potential (Edge) Energy Figure 3: Potential (Edge) Energy. (a) An unprocessed 256-by-256 pixel NMR image. (b) The potential energy generated by smoothing the image, convolving it with a simple gradi- ent operator, and negating the result (the image has been re-scaled for display). Strong edges produce correspondingly low (dark) local minima; however, fine detail is lost during the smoothing process, which is necessary to eliminate noise and spread out legitimate edges. Edges can be found with a gradient-based potential energy functional such as: (3.5)Eedge = − �0 1 �I �x 2 ds For example, consider a snake element x = (x, y) with potential energy P(x) = –| ∇I(x) |2; the image force acting on this element is given by: �x � − �P�x = � �x ( �I 2 ) = 2 ��I(x) �I(x) The term ∇∇I(x) is the Hessian matrix of second-order image derivatives. Strong edges can therefore be found using: (3.6)x � x + � ��I(x) �I(x) Everything You Always Wanted To Know About Snakes… Page 9 3.3 TERMINATION FUNCTIONAL The ends of line segments, and therefore corners, can be found using an energy term based on the curvature of lines in a slightly smoothed image C(x, y) = Gσ(x, y) * I(x, y). If the gradient direction is given by θ = tan−1(Cy / Cx) then the unit vectors along, and perpendicular to, the image gradient are given by: Tangent: n = cos � sin� Normal: nz = − sin� cos � The curvature of a contour in C(x, y) can be written: (3.7)Eterm = �0 1 �� �n z ds = �0 1 �2C/�n z 2 �C/�n ds Expanding the derivatives: (3.8)Eterm = �0 1 CyyCx2 + CxxCy2 − 2CxyCxCy Cx2 + Cy2 3/2 ds This energy formula provides a simple means for attracting snakes towards corners and terminations. Everything You Always Wanted To Know About Snakes… Page 10 4 GRADIENT DESCENT USING FORCES The previous two sections can be summarised by stating that, at its simplest, the energy E of an active contour model x(s) is defined as:† (4.1)E( x(s) ) = Potential � 0 1 P(x(s)) ds + Tension � 2 �0 1 �x(s) �s 2 ds + Stiffness � 2 �0 1 �2x(s) �s2 2 ds This section considers the task of minimising these energy functionals. First, the general technique of minimisation by iterative gradient descent is introduced; an equation is then derived to describe the energy changes that occur when an active contour model is moved, and this equation is used to calculate forces for energy minimisation by gradient descent. 4.1 CONJUGATE GRADIENT DESCENT In general, an energy function E(x) can be minimised by altering each variable according some small quantity δx that is guaranteed to reduce the value of the function: (4.2)x � x + �x Local linear approximation gives an expression for the new energy: (4.3)E(x + �x) � E(x) + �E�x � �x Clearly, δx must be chosen so that the energy decreases at each iteration. The gradient descent rule is based on the fact that steps down an energy hypersurface (see Figure 4) can be guaran- teed by making small changes in the direction of the negated gradient: (4.4)�x � − �E�x The new value of the energy function is given by: (4.5)E(x + �x) � E(x) − � �E�x 2 The negative sign and square power (dot product) in this equation guarantee that E will decrease at each iteration until the minimum is reached; however, the (small) time step τ must be chosen carefully to avoid oscillation (see Section 7) and is almost invariable less than unity. Conjugate gradient descent, as illustrated in Figure 4, finds the nearest local minimum in an energy hypersuface, with no consideration of global properties. Unfortunately, this Everything You Always Wanted To Know About Snakes… Page 11 † For simplicity, external constraints are omitted from the remainder of this document. lenovo 自由文本工具 设计一个 simplicity can lead to problems when there are several minima close together because a snake can be attracted to a feature (energy minimum) other than that intended by the user. High Energy Low Energy (b) Energy Contours x2 x1 (a) Energy Hypersurface x 2 x1 E Figure 4: Conjugate Gradient Descent. This figure shows four alternative paths down a three-dimensional energy surface. At each iteration the gradient descent algorithm moves the energy value towards the nearest local minimum by making a small change in the direction given by the negated energy gradient (orthogonal to the local energy contours). The process is repeated until this gradient (force) is zero, at which point none of the variables can be altered without increasing the energy. 4.2 ENERGY GRADIENT FOR AN ACTIVE CONTOUR MODEL Before gradient descent can be used to minimise the energy of an active contour model it is necessary to obtain an expression for the corresponding energy gradient which determines the changes t