Active contours theory

 

Table of content:

Active Contours (Snakes):............................................................................................. 1

Geometric Active Contours:........................................................................................ 2

Level Sets approach......................................................................................................... 2

Geodesic Active Contours:........................................................................................... 4

Conclusions:........................................................................................................................ 5

 

Active Contours (Snakes):

 

Given an input image, the objective is to produce complete and accurate contour lines of a specific object in the image. A simple pixel-based identification is not enough since a full mathematical and analytical describing of the contour lines is desired.

 

We describe a line “L” using the analytical model as the mapping:

Where:

 

Active Snakes is an iterative algorithm that can produce a better contour-line description in each step. It receives as input the previous contour line and using some balancing constant factors (which will be explained below) to produce a new contour line representation.

 

The basic problem can be reduced to following fundamental questions:

1.          How to produce a better description of the contour line – what is a “better” line?

2.          Can we utilize the properties of the object we are trying to find?

 

One can try to answer these questions by:

1.          We should shrink the line to make it cover only the desired object – but how can we know were to stop?

2.          There are many object properties that can be harness from the image itself, some of them deals with the intensity variations, other with the density of the particles of the object.

 

Note that if we’re looking for analytical function it has to be “smooth” in some extent – so we must prefer a smooth function to a sharp one.

 

Calculating the integral of the line function seems to be a good start since the integral actually measures the “length” of the line (*provided q is geometric).

The first derivative measure the length and the second one measure the smoothness of the line that C describes.

Putting it all together, we’ll get the following:

 

This is a “functional” that will represent a measurable property for the quality of the contour. Our objective is now to minimize this functional. The phrase “External” comes the remind us that this functional is affected only from “forces” (expressions) that procedure lower values if the line is smoother and shorter – i.e. they are similar to external forces that push the contour line inside and towards the center of the object.

 

Besides from the problem of minimizing the functional, we still need to find some balancing factor to be used as “internal force” - i.e. to push the contour line out side the object that we are looking for. The best balance of the “external” and “internal” forces will be on the real contour

 

We must also use the input image properties to identifying the desired object. For instance the intensity of the colors of the desired object may be different from its surroundings. In this case we can use the gradient operator on the image pixels intensity, to create a function that generates a major change in output values for input values (pixels) in coordinates that are closer to the edges of the desired object. Hence creating a balancing factor to the external forces:

Note that in the general case, any image property may be used  (or combination of those) so we should relate to a general “g-function” that has the property of internal-force (naturally it is based on some sort of an edge detector).

A common example of gradient-based function is:

 

 

To solve the minimization of the functional we must find extreme-values – i.e. to solve a differential equation:  

Geometric Active Contours:

 

There are many miscalculations and hazards caused by the fact that the contour “C” parameter – “q”, doesn’t have to be geometric. It could be any mapping – for example: “q” is the angle and C(q) is the intersection between the vector in the direction “q” with the relevant line. Non-geometric parameter can cause the absence of a minimum value, or dual values in other cases. The arc “length” which is the base of all the above calculations also requires “geometric parameter”. So, instead of using any mapping parameter “q” we’ll use “s” which is a geometric parameter and:

 

Now we may use the Level-Set approach to solve our initial problem:

 

Level Sets approach

The Minimization problem can be approached using the Level-Sets model. In this model we’ll describe the contour “C(s)” using an implicit function f(x,y,t).

In addition we’ll see f as a 3-dmentional-function subset. The 3rd dimension is the “level” of f. This model frees us from the need to handle each and every special case of joining and separating contour lines as we iterate through the different contours towards the real one. It overcomes all the topological hazards because now, all contours are always connected in the 3rd dimension and thus they are continues function. The connection between f and C(s) is defined by the additional requirement that f happens to be identical to C(s) on the 0 level:

 

f(x,y,0) = C(s).

 

So now minimizing the functional becomes minimizing f.

 

What we actually have here is a 3-dimentional function that f is implicitly describing specific levels from it – i.e. ft = {all the points that are the intersection of the function and the plane parallel to the (x,y) plane that contains the point (0,0,t) }

 

 

The derivative of f by t is a scalar function. The amount of “change” needed to be added to the current value of f(x,y,t) to become f(x’,y’,t+1) is :

 

 

 

 

Each f(t) defines a new [C(s)](t) because:

 

 

Where:  

 

 

A better understanding of this Vn can be using the curvature-flow:

 

We define the curvature K by:

 

So now [Vn --> K(s)] and we’ll have:

 

 

We know that “s” (or “q”) depends of the coordinate (x,y) , so:

 

 , Becomes: 

 

However, we didn’t include yet the “internal force” factor that is needed to actually reach the right contour (now we’ll use the “g-function” representation):

 

 

 

Or, in the level-sets formulation:

(Where “v” is just a constant stabilizer for the convergence speed)

Geodesic Active Contours:

 

We came a long way, however, although we have a level-set description of the function, we still don’t have a meaningful analytical solution – we need to know from what functional the above equation comes from. In essence we are going to join the above 2 approaches into a single concept.

 

We’ll start with a general representation of the functional (note that “s” is a geometric parameterization):

 

As before:

 

 

Or, in the level-sets formulation:

 

 

Or simply:

 

As before a acceleration factor “v(t)” may be added (v(t) is decreased as we approach the real contour line – i.e. as t advances):

 

A typically v(t) value is :


 

Conclusions:

 

After this theoretical review of the Active-Contours algorithms, It's obvious that we are looking at the evolution of the Active Contours concept: from the early stages of the energy-like description, towards the geometric model, and on to the geodesic generalization.

This model is clearly robust and generic enough to answer our needs in this laboratory project. Thus, we'll implement our solution based on this model, and we will integrate additional numerical optimizations to the model, in order to achieve a practical solution.