This algorithm analyzes statistics in small local regions of an image to try and separate the foreground from the background. This is an active contour segmentation technique, meaning a curve (or surface) is deformed over time to iteratively improve the segmentation until an optimum is reached.
One of the main aspects of computer vision is finding the appropriate outline of shapes in images. This is useful for analyzing â€œnatural imagesâ€ like the ones taken from a camera or medical images such as 3D MRI scans of the brain. This project began by trying to define the boundary of a particularly tricky structure in the brain called the putamen.
I first developed a solution that worked, then analyzed it to figure out the mathematical principles behind what I was doing. In the end, a very nice technique was discovered that is both highly effective and mathematically sound. This idea was first submitted to a conference in August 2006. It was subsequently published in March 2007.
Shawn Lankton, Delphine Nain, Anthony Yezzi, Allen Tannenbaum. Hybrid Geodesic Region-Based Curve Evolutions for Image Segmentation. In Proceedings of SPIE Medical Imaging, San Diego, 2007. [pdf]
(Poster presented at conference.)
Below is a very high-level summary of the paper along with some results and a code demo.
This paper presents a novel segmentation technique (Segmentation is the process of detecting the boundary of an object in an image. This can be 2D or 3D images). This technique is based off of two well known classes of techniques, but combines the two in a clever way that allows it to capture benefits of both methods. These two methods are: gradient-based active contours, and region-based active contours. The mechanism of our solution is to start from a naive initial curve, and then move each point on the curve based on analysis of the statistics of the local interior and exterior regions.
Level Set Active Contours
Active contour methods begin with an initial curve and define some cost for that curve based on its geometric properties and the associated image data. Cost based on the geometry is provided to keep the curve smooth, and cost based on the image data are intended to attract the contour to object boundaries. This curve is then deformed in the way needed to decrease the cost thus moving the curve toward a position where cost is locally minimized. Presumably this occurs when the curve is correctly situated on the object.
Essentially what we are doing is combining the ideas of â€œEdge-basedâ€ flows and â€œRegion-basedâ€ flows.
Edge-based flows use an edge detector to find edges, then try to fit a curve nicely on those detected edges. The problem is that these methods only look at very local image information. That means that it is very susceptible to noise, and the initial placement of the curve. For a reference, check this paper: Geodesic Active Contours by Caselles, et al.
Region-based flows take an alternate approach. They try to model the global characteristics of entire regions of the image. This approach is nice because its very robust to initialization and noise, but sometimes images can’t be modeled well in terms of global rules and erroneous segmentations occur. For a reference, check this paper: Active Contours Without Edges by Chan and Vese
The Hybrid Flow
The hybrid flow aims to blend the benefits of the geodesic active contours and the region based active contours. This is accomplished by forming a cost based on a shortest weighted path. The weights at each point along the path are determined from local regions around the curve. The resulting flow is more robust to initial curve placement and image noise like region-based flows, but also capable of finding significant local minima and partitioning the image without making global assumptions about its makeup.
The key assumption that we make about ob jects to be segmented by this technique is this: At each point on the true edge of an object, nearby points inside and outside the ob ject will be modeled well by the mean intensities of the local regions. The result is an energy that is more global in nature than edge-based flows.
The cost of the entire curve is often called an ‘energy.’ In the definition of this hybrid energy we use several notations. I represents the image, and x and s represent independent spatial variables. Omega and Omega-bar represent the interior and exterior of the curve respectively. Chi, in the equations below, represents a ball centered at the point s that specifies the local region being examined.
We define the ul and vl functions:
in terms of local sums (SIl and SEl) and local areas (AIl, AEl). Based on these notations, we can define the hybrid energy:
In this energy we use an outer integral over s to cover the points along the curve. Then, in the inner integrals we use x to inspect the entire domain restricted by the Chi function so that the only contribution in from image information in the local neighborhood around the point s. The energy around each point s is a function of how well the interior and exterior are modeled by their means, ul and vl. The total energy is the sum of the contribution of energy from every point around the curve.
Using the calculus of variations, it is possible to take the derivative of this energy with respect to the shape of the curve itself. Hence, we find the way to deform the curve such that this energy is always decreasing. By decreasing the energy in an iterative fashion, we continuously refine our guess at the correct answer until we finally converge on the local minimum solution.
Here are two experiments run with this flow. In each set, you see the initial contour (in red), and then the result of three different techniques: a typical region-based technique, an edge-based technique, and the presented hybrid technique. In all cases, the hybrid method outperforms all others.
First a synthetic image designed specifically to foil the other algorithms.
The next experiment is an MRI image of the putamen. This is a small structure in the sub-cortex of the brain.
As you can see, there is significant improvement with the hybrid method.
The presented technique combines the ideas of geodesic and region-based active contours and as a result produces a segmentation algorithm which has benefits of both. Like other geodesic models, this approach is capable of looking locally for correct solutions while only making weak assumptions about global image properties. Also, as with region based models, our method has increased robustness to noise and reduced dependence on initial curve placement as a result of taking image data from local regions. The algorithm has proven to be more versatile than either of the two standard techniques presented, even in its simplest form.
Despite its benefits, this method still has some drawbacks. As with all geometric-based energies, initial curve placement is still important. Although this algorithm is less dependent than some, it is still necessary to initialize the contour nearby the object to be segmented or risk that the final segmentation result will converge at an incorrect local minima. Additionally, the key assumption made about image makeup is not ideal for all images. There are cases where the ideal border of an ob ject is not characterized by a separation of image intensities at that border.
The method presented here is merely the first application of a new class of energy functionals based around combining local and global flows. The ability to define a geodesic energy with respect to local regions of image data has many possible applications. Extension of the implementation to accommodate higher order statistics, vector valued images, and images of higher dimensionality will improve performance and open the door to other potential applications.
Many of these improvements will be addressed in my future publications.
Check out this Matlab code to see an example of this technique in action.
Feel free to contact me with any questions, comments, or improvements on the code!