Autoregressive fractionally integrated moving average

2013-11-06T18:44:31Z

109.154.36.13: revert to last version by Duoduoduo

'''Active contour model''', also called '''snakes''', is a framework for delineating an object outline from a possibly [[image noise|noisy]] 2D [[image]].

This framework attempts to [[graph cuts in computer vision|minimize an energy]] associated to the current contour as a sum of an internal and external energy:

*The ''external energy'' is supposed to be minimal when the snake is at the object boundary position. The most straightforward approach consists in giving low values when the regularized [[gradient]] around the contour position reaches its peak value.
*The ''internal energy'' is supposed to be minimal when the snake has a shape which is supposed to be relevant considering the [[shape]] of the sought object. The most straightforward approach grants high energy to elongated contours (elastic force) and to bended/high [[curvature]] contours (rigid force), considering the shape should be as regular and smooth as possible.

The snakes model is popular in [[computer vision]], and led to several developments in 2D and 3D. In two dimensions, the [[active shape model]] represents a discrete version of this approach, taking advantage of the [[point distribution model]] to restrict the shape range to an explicit domain learned from a training set.

[[File:Snake-contour-example.jpg|thumb|500px|Snakes – active deformable models]]

==Introduction==

Snake is an energy minimizing, deformable [[Spline (mathematics)|spline]] influenced by constraint and image forces that pull it towards object contours. Snakes are greatly used in applications like object tracking, shape recognition, segmentation, edge detection, stereo matching. Snakes may be understood as a special case of general technique of matching a deformable model to an image by means of energy minimization.<ref>Snakes: Active Contour Models, M Kass, A Witkin, D Terzopoulos, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124.5318&rep=rep1&type=pdf</ref>
Snake is an “active” model as it always minimizes its energy functional and therefore exhibits dynamic behavior.

A simple elastic snake is thus defined by
*a set of n points
*an internal elastic energy term
*an external edge based energy term

One may visualize the snake as a rubber band of arbitrary shape that is deforming with time trying to get as close as possible to the object contour. Snakes do not solve the entire problem of finding contours in images, but rather, they depend on other mechanisms like interaction with a user, interaction with some higher level image understanding process, or information from image data adjacent in time or space. In general, Snake is placed near the object contour. It will dynamically move towards object contour by minimizing its energy iteratively.

==Energy function==

In Snakes, we use the technique of matching a deformable model to an image by means of energy minimization. A snake initialized near the target gets refined iteratively and is attracted towards the salient contour. A snake in the image can be represented as a set of ''n'' points.

<math> \mathbf v_i=(x_i,y_i) </math>

where <math>i=0 \ldots n-1 </math>

We can write its energy function as

<math> E_{snake}^*=\int\limits_0^1E_{snake}(\mathbf{v}(s))\,ds=\int\limits_0^1 ( E_{internal}(\mathbf{v}(s))+E_{image}(\mathbf{v}(s))+E_{con}(\mathbf{v}(s)) )\,ds</math>

<math>E_{external}=E_{image}+E_{con}</math>

where <math>E_{internal} </math> represents the internal energy of the spline (snake) due to bending, <math> E_{image} </math> denotes the image forces acting on spline and <math> E_{con} </math> serves as external constraint forces introduced by user. The combination of <math> E_{image} </math> and <math> E_{con} </math> can be represented as <math> E_{external} </math>, that denote the external energy acting on the spline.

===Internal energy===

Internal Energy of the snake is
<math>E_{internal}=E_{cont}+E_{curv}</math> <ref>Dr. George Bebis,University of Nevada,http://www.cse.unr.edu/~bebis/CS791E/Notes/DeformableContours.pdf</ref>

where <math> E_{cont} </math> denotes the energy of the snake contour and <math> E_{curv} </math> denotes the energy of the spline curvature.

<math>E_{internal}=(\alpha\,\!(s)\left | \mathbf{v}_s(s) \right \vert^2 + \beta\,\!(s)\left | \mathbf{v}_{ss}(s) \right \vert ^2)/2 </math>
<math>=\bigg(\alpha\,\!(s) \left \| \frac{d\bar v}{ds}(s) \right \Vert^2 + \beta\,\!(s) \left \| \frac{d^2\bar v}{ds^2}(s) \right \Vert ^2 \bigg) /2</math>

The first-order term makes the snake act like a membrane and second-order term makes it act like a thin plate. Large values of <math> \alpha (s) </math> will increase the internal energy of the snake as it stretches more and more, whereas small values of <math> \alpha (s) </math> will make the energy function insensitive to the amount of stretch. Similarly, large values of <math> \beta (s) </math> will increase the internal energy of the snake as it develops more curves, whereas small values of <math> \beta (s) </math> will make the energy function insensitive to curves in the snake. Smaller values of both <math> \alpha (s) </math> and <math> \beta (s) </math> will place fewer constraints on the size and shape of the snake.

===Image forces===

Further, <math> E_{image} </math> has three components:
* Lines
* Edges
* Terminations

The energies can be represented as follows:

<math>E_{image}=w_{line}E_{line}+w_{edge}E_{edge}+w_{term}E_{term}</math>

Adjusting the weights in the image will determine salient features in the image which will be considered by the snake.

====Line functional====

A line functional is nothing but the intensity of the image, which can be represented as

<math>E_{line}= I(x,y)</math>

Depending on the sign of <math>w_{line}</math>, the line will be attracted to either dark lines or light lines.

====Edge functional====

=====Image gradient=====
Edges in the image can be found by the following energy function which will make the snake attract towards contours with large image gradients.

<math>E_{edge}=-\left | \nabla I(x,y)\right \vert ^2</math>

=====Scale space=====

It is rather common that a snake started far from the object converges to the desired object contour. If a part of the snake finds a low energy feature, it pulls the other parts of the snake to continue to the contour. Scale Space continuation can be used in order to achieve desired results. One can allow the snake to come to equilibrium on a blurry energy edge functional and reduce the blurring as the calculation progresses. The energy functional is

<math>E_{edge}=-\left | G_{\sigma} * \nabla ^2 I \right \vert ^2</math>

Where <math> G_{\sigma} </math> is a Gaussian standard deviation <math> \sigma </math> minima of this functional lie on [[Zero crossing|zero-crossings]] of
<math> G_{\sigma} \nabla ^2 I </math> which define edges in [[Marr-Hildreth algorithm|Marr-Hildreth]] Theory. Thus the snake gets attracted towards zero-crossing constrained by its own smoothness.

====Termination functional====

Curvature of level lines in a slightly smoothed image is used to detect corners and terminations in an image. Let <math> C(x,y)= G_{\sigma}*I(x,y) </math> be a slightly smoothed version of the image.Let <math> \theta = \arctan ( \frac {C_y}{C_x})</math> be the gradient angle.

And let
<math> \mathbf n = (\cos \theta,\sin \theta)</math> and <math>\mathbf n_{\perp}= (-\sin \theta,\cos \theta) </math> be unit vectors along and perpendicular to the gradient direction. The termination functional of energy can be represented as

<math> E_{term}={\partial \theta\over\partial n_{\perp}} = {\partial^2 C / \partial^2 n_{\perp} \over \partial C / \partial n} = {{C_{yy}C_x^2-2C_{xy}C_xC_y+C_{xx}C_y^2}\over(C_x^2+C_y^2)^{3/2}}</math>

=== Constraint energy ===

Some systems, including the original snakes implementation, allowed for user interaction to guide the snakes, not only in initial placement but also in their energy terms. Such constraint energy <math> E_{con} </math> can be used to interactively guide the snakes towards or away from particular features.

==Implementation==

Gradient-descent minimization <ref>Image Understanding,Bryan S. Morse,Brigham Young University,1998-2000 http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MORSE/iu.pdf</ref> is one of the simple optimizations which can be used to minimize snake energy. For example, let’s consider a function of only one variable. If we have a starting guess at the value of the solution, we can look at the slope at that point and decide to increment our solution (negative slope) or decrement our solution (positive slope). Notice the negation there: if the slope is positive, downhill is backwards; and if the slope is negative, downhill is forwards. We can thus implement gradient-descent minimization as

<math>x_{t+1}=x_t+\gamma\frac{df}{dx}(x_t)</math> and
<math>y_{t+1}=y_t+\gamma\frac{df}{dy}(y_t)</math>

Where <math> \gamma </math> controls the size of the step at each iteration.

Vector representation: <math>\bar x_{t+1}=\bar x_t+\gamma \nabla f(\bar x_t)</math>

We can approximate the energy function of the snake by using the discrete points on the snake.

<math>E_{snake}^*\approx \displaystyle \sum_1^n E_{snake}(\bar v_i)</math>

The derivative of above sum is nothing but the sum of derivatives.

<math>\nabla E_{snake}^*\approx \displaystyle \sum_1^n \nabla E_{snake} (\bar v_i) </math>

Now we should iteratively adjust the points vector <math> \mathbf v_i </math> by using gradient descent minimization.

<math>\bar v_i \leftarrow \bar v_i-\nabla E_{snake}(\bar v_i)</math>

Applying the derivative to energy function gives

<math>\nabla E_{snake} (\bar v_i) = w_{internal} \nabla E_{internal} (\bar v_i)+w_{external} \nabla E_{external} (\bar v_i) </math>

Derivative of internal Energy of the image can be solved as

<math>\nabla E_{internal}(s)=\nabla \bigg[(\alpha\,\!(s)\left \| \mathbf{v}_s(s) \right \Vert^2 + \beta\,\!(s)\left \| \mathbf{v}_{ss}(s) \right \Vert ^2)/2 \bigg] </math>

<math>\nabla E_{internal} (s)= \Bigg[ \bigg(\alpha\,\!(s) \nabla \left \| \frac{d\bar v}{ds}(s) \right \Vert^2 + \beta\,\!(s) \nabla \left \| \frac{d^2\bar v}{ds^2}(s) \right \Vert ^2 \bigg) /2 \Bigg]</math>
<math>=\alpha \frac{\partial ^2 \bar v}{\partial s^2}+\beta \frac{\partial ^4 \bar v}{\partial s^4}</math>

These can be approximated using [[finite difference]]s—the second derivative w.r.t. ''s'' can be calculated using three
adjacent points on the snake, and the fourth derivative w.r.t. ''s'' can be calculated using five adjacent points. It also helps
to separate the x and y components.

Final equations are

<math>\bar v_i= \leftarrow \bar v_i - \gamma \Bigg\{ w_{internal} \bigg[ \alpha \frac{\partial ^2 \bar v}{\partial s^2} (\bar v_i)+\beta \frac{\partial ^4 \bar v}{\partial s^4} (\bar v_i) \bigg]</math>
<math>+ \nabla E_{ext} (\bar v_i) \Bigg\} </math>

<math>\bar x_i= \leftarrow x_i - \gamma \Bigg\{ w_{internal} \bigg[ \alpha \frac{\partial ^2 x}{\partial s^2} (\bar v_i)+\beta \frac{\partial ^4 x}{\partial s^4} (\bar v_i) \bigg]</math>
<math>+ \frac{\partial}{\partial x} E_{ext} (\bar v_i) \Bigg\} </math>

<math>\bar y_i= \leftarrow y_i - \gamma \Bigg\{ w_{internal} \bigg[ \alpha \frac{\partial ^2 y}{\partial s^2} (\bar v_i)+\beta \frac{\partial ^4 y}{\partial s^4} (\bar v_i) \bigg]</math>
<math>+ \frac{\partial}{\partial y} E_{ext} (\bar v_i) \Bigg\} </math>

Where

<math> E_{external}=E_{image}+E_{con}</math>

===Pseudo code===

# Before entering the iteration calculate <math>E_{ext} (\bar v_i) </math>and the derivatives of this w.r.t. x and y separately.
# At the start of the iteration, calculate <math>\frac{\partial ^2 x}{\partial s^2}(\bar v_i) </math>and <math>\frac{\partial ^2 y}{\partial s^2} (\bar v_i) </math> using the three adjacent points and <math> \frac{\partial ^4 y}{\partial s^4} (\bar v_i),\frac{\partial ^4 x}{\partial s^4} (\bar v_i)</math> using five adjacent points.
# Then, calculate change in x and y for each point in <math> \bar v_i </math> Use the precalculated <math>E_{ext} (\bar v_i) </math>.

==Advantages and drawbacks==

Snakes have multiple advantages over classical feature attraction techniques.
# Snakes are autonomous and self-adapting in their search for a minimal energy state.
# They can be easily manipulated using external image forces.
# They can be made sensitive to image scale by incorporating Gaussian smoothing in the image energy function.
# They can be used to track dynamic objects in temporal as well as the spatial dimensions.

The key drawbacks of the traditional snakes are

# They can often get stuck in local minima states; this may be overcome by using simulated annealing techniques at the expense of longer computation times.
# They often overlook minute features in the process of minimizing the energy over the entire path of their contours.
# Their accuracy is governed by the convergence criteria used in the energy minimization technique; higher accuracies require tighter convergence criteria and hence, longer computation times.<ref>Snakes: an active model,Ramani Pichumani,http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RAMANI1/node31.html</ref>

== Other implementations of snakes ==

=== GVF active contours ===

The snake is developed based on new type of external field, called Gradient Vector Flow, or GVF. This computation causes diffuse forces to exist far from the object, and crisp force vectors near the edges. Combining these forces with the usual internal forces yields a powerful computational object: the GVF snake (2D), or the GVF deformable model (N-D). Even though this snake is started far from the object, it still gets attracted towards the object.<ref name="gvf">Chenyang Xu and Jerry L. Prince,IACL,http://www.iacl.ece.jhu.edu/static/gvf/</ref> Especially, GVF active contours can handle broken object edges and subjective contours.<ref name="gvf"/>

=== Balloon snake===

In this case, the snake behaves like a balloon which is blown up. When it passes by edges, it is stopped if the contour is strong,or passes through if the contour is too weak. Thus, the initial snake need not be too close to the solution(object) to converge. This approach modifies the definition external forces (derived from gradient of the image) presented in traditional snake (Kass ''et al''). A new pressure force is introduced which makes the curve behave like a balloon.<ref>On Active Contour Models, Laurent D. COHEN,http://hal.archives-ouvertes.fr/docs/00/07/54/84/PDF/RR-1075.pdf</ref>

===Diffusion snakes===

The diffusion snake is a modification of the [[Mumford-Shah Functional|Mumford-Shah functional]] for spline contours. A modification of the Mumford-Shah functional and its cartoon limit is used to incorporate statistical prior on the shape of the segmenting contour. By minimizing a single energy functional, we obtain a segmentation process which maximizes both the Grey value homogeneity in the separated regions and the similarity of the contour with respect to a set of training shapes.<ref>Diffusion Snakes: Statistical Shape Knowledge in Mumford-Shah Based Segmentation,Daniel Cremers, Christoph Schnörr and Joachim Weickert http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/CREMERS2/</ref>

===Geometric Active Contours===

This class of snake models employs ideas from Euclidean curve shortening evolution which defines the gradient direction
in which the Euclidean perimeter is shrinking as fast as possible. One therefore notes that
new active contour models may be derived by multiplying the Euclidean arc-length by a conformal factor tailored to the features of interest that one wants to capture, then writing down the resulting gradient
evolution equations. The latter becomes a curve shortening equation with respect to the new conformally Euclidean metric.
These models may be implemented using [[level sets]], and have been extensively employed in [[medical image computing]].
They have been called geodesic snakes <ref>Geodesic Active Contours, V. Caselles, R. Kimmel, G. Sapiro http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.2196</ref> and conformal active contours.<ref>Conformal curvature flows: From phase transitions to active vision, Satyanad Kichenassamy, Arun Kumar, Peter Olver, Allen Tannenbaum and Anthony Yezzi http://www.springerlink.com/content/u457157212872201/</ref> Statistical models combining local and global features
have been formulated in.<ref>Localizing region-based active contours, Shawn Lankton and Allen Tannenbaum http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.178.2796/</ref>

==Sample code==

#[http://www.icaen.uiowa.edu/~image/Prince-snakes/ Practical examples of different snakes developed by Prince and Xu]
#[http://www.isbe.man.ac.uk/~bim/software/qsnake_demo/qsnake_demo.html Basic tool to play with snakes (active contour models) from Tim Cootes,University of Manchester]
#[http://www.mathworks.com/matlabcentral/fileexchange/28149 Matlab implementation of 2D and 3D snake including GVF and balloon force]
#[http://www.slaney.org/malcolm/pubs.html Matlab Snake Demo] by Chris Bregler and Malcolm Slaney, Interval Research Corporation.
#[http://www.markschulze.net/snakes/ A Demonstration Using Java]

==See also==

#[http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/YOUNG/vision7.html David Young, March 1995]
# [http://homepages.inf.ed.ac.uk/cgi/rbf/CVONLINE/entries.pl?TAG709 Snakes: Active Contours, CVOnline]
# [http://www.isbe.man.ac.uk/courses/Computer_Vision/downloads/L11_Snakes.pdf ICBE,University of Manchester]

==References==
{{reflist|2}}

{{DEFAULTSORT:Active Contour Model}}
[[Category:Computer vision]]

formulasearchengine - User contributions [en]

Autoregressive fractionally integrated moving average