Thursday, June 6, 2013

The fast marching method solves boundary value problems that describe how a closed curve evolves as a function of time t with a speed f(x) in the normal direction at a point x on the curve. The speed is given but the time it takes for the contour to pass the point x is calculated by the equation. Different points may have different speeds. The region grows outward from the seed of the area. The more the points considered, the better the contour. The fast marching method makes use of a stationary surface that gives the arrival information of the moving boundary. From the initial curve, build a little bit of the surface upwards, with each iteration always starting from the initial position. It's called fast because it uses a fast heap sort algorithm that can tell the proper data point to update and hence to build the surface. For each of the N points at any given height h, the next point is determined and always in the order from the priority queue. The surface grows with height h in a monotonically increasing order because previously evaluated grid points are not revisited. This is because of non-negative speed and because the heap guarantees that the grid point with the minimum distance is selected first out of the data points in the sweep of N points at any level. Hence the entire operation of determining the next contour takes NlogN time.
This is a numerical method because it tries to view the curve as a set of discrete markers. The fast marching method has applications in image processing such as for region growing.
(Courtesy: Sethian @ Berkeley)
We will revisit the fast marching method for its implementation and discuss clustering but for now let us look at the other partial differential methods in that category.
The partial differential equation (PDE) based methods solve PDE equations by a numerical scheme.  When we use PDE for curve propagation, we use a cost function and use a minimization technique to find the next data point to consider.
There are three different PDE methods. The first one that we discussed earlier was the fast marching method. In this we consider the distance function to be always positive so that the curve expands outwards from the seed. However, the distance function can be both positive and negative and so a variation of the method that takes into consideration the sign of the distance function has been proposed and that is called the generalized fast marching method.
The other two methods are the Parametric methods and the level set methods. The parametric methods are based on parameterizing the contour based on some sampling strategy and then evolve each element according to the surrounding data points and the internal terms. When the parameters involve the sum of internal and external energy associated to a current contour  and tries to minimize it, we delineate an object outline and these outlines are called snakes. The snake calculation is fast and easy and therefore valuable in video processing as well which consists of tracking the snake on the series of images in a video.
The level set method uses the contour as obtained from a height h on the stationary surface that gives arrival information. This is called the zero-level which gives the contour. As opposed to fast marching methods, the level set method can have distances that are positive or negative. The level set method does not use parameters but generalizes the approach by going to a higher dimension (third) which is the geometric properties of the evolving structure.
The PDE methods have to consider topology changes such as curve splitting or merging.
If the data points cross over each other, or if the shape breaks into two, then the curve propagation should still be able to continue.

No comments:

Post a Comment