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.

Introduction

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.

Hybrid Seg, Figure 1

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.

Abstract

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.

Related Work

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.

Hybrid Seg, Figure 2

We define the ul and vl functions:

Equation 2
Equation 3
,

in terms of local sums (SIl and SEl) and local areas (AIl, AEl). Based on these notations, we can define the hybrid energy:

Equation 1
.

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.

Results

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.

Hybrid Seg, Figure 3

The next experiment is an MRI image of the putamen. This is a small structure in the sub-cortex of the brain.

Hybrid Seg, Figure 4

As you can see, there is significant improvement with the hybrid method.

Conclusion

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.

Demo

Check out this Matlab code to see an example of this technique in action.

localized_seg.zip

Feel free to contact me with any questions, comments, or improvements on the code!

20 thoughts on “Hybrid Segmentation

  1. Very cool of you to release your code.

    If I use it in my research, then I will make sure to credit you.

    What is your official citation for your released code? Do you have a page with this info?

    Regards,
    Joseph

  2. Citations for this and all of my papers can be found on the publications page

    Citations and acknowledgments are appreciated, but also be sure to leave a comment or drop me an email and let me know what worked, what didn’t and how it could be improved!

  3. Excellent coding style, easy to read and understand. It is quite useful for my research.

  4. Thanks!
    But there is a problem when i excute this programme.It display Undefined function or variable ‘isfloat’ On line 183 ==> if(isfloat(img)) % image is a double.How can i cope with this problem?

  5. I think it is a general way to produce a loacl mask based on the local information around the evolution curve.This way would be suit for any nature images and can cope with image segmentation with intensity inhomogeneity.
    Now i am researching this adaptive mask and its local energy function to drive the evolution of a contour.

  6. @wu jimig Your Matlab version may not support isfloat. This line is a check to ensure that the image is a double. You can remove this ‘if’ statement and instead write ==> img = double(img);

  7. Does this algorithm work with 3D data? I want to use your algorithm to gradually deform a surface (x,y,z) to another surface (x’,y’,z’). Can I do that with your algorithm? If yes can you elaborate a little bit? If not, are you familiar with any code that can do that? Thank you! Keep up the good work!

  8. {i have {seen|read} many so called gurus {sharing|telling} their tips and tricks,but {rarely|very rarely} some are good.I can say very {confidently|prodly|easily} that this post was really {good|awesome|informative}|i would definately {love|like} to see some {good|great} {tips|info} from you to {make|earn} money from adsense.as i {feel|really feel} you can help us. and i really do not believe the other online guru’s. They {freeze|cheat} us by {saying|telling} we will make money but instead they make more money.|{good|great} informative {posarticle}.I think i {will need to|should} read some other {post|articles} of your’s too.By the way frankly speaking i like the way you appraoch the visitors.Definately {attractive post|innovative post} | This is really interesting to read.hope to see some more like this in future.keep it up the researching and great task.cool|I?m really one of those {people|webmsters} earning next to {nothing|no mopney} or rather $1 a day. {Getting|having} good {traffic|vistors} is really a {big|bit} challenge.|I {luv|like} you lol. You have no idea how helpful {that|this} was, this {site|post} rocks man, ROCKS! WOOO.|I?ve been looking into {information|info} on this {very|particular} topic for quite a while and this really covers it! this is a great blog!}

  9. {i have {seen|read} many so called gurus {sharing|telling} their tips and tricks,but {rarely|very rarely} some are good.I can say very {confidently|prodly|easily} that this post was really {good|awesome|informative}|i would definately {love|like} to see some {good|great} {tips|info} from you to {make|earn} money from adsense.as i {feel|really feel} you can help us. and i really do not believe the other online guru’s. They {freeze|cheat} us by {saying|telling} we will make money but instead they make more money.|{good|great} informative {posarticle}.I think i {will need to|should} read some other {post|articles} of your’s too.By the way frankly speaking i like the way you appraoch the visitors.Definately {attractive post|innovative post} | This is really interesting to read.hope to see some more like this in future.keep it up the researching and great task.cool|I?m really one of those {people|webmsters} earning next to {nothing|no mopney} or rather $1 a day. {Getting|having} good {traffic|vistors} is really a {big|bit} challenge.|I {luv|like} you lol. You have no idea how helpful {that|this} was, this {site|post} rocks man, ROCKS! WOOO.|I?ve been looking into {information|info} on this {very|particular} topic for quite a while and this really covers it! this is a great blog!}

  10. Hi Shawn,

    I appreciate you sharing the codes.

    I am wondering whether your localized region-based active contours segmentation (localized_seg.zip) could perform a multi-object segmentation ( like the elephant example in your paper), please?

  11. Sir,
    I have gone through the code, I learned well. But i found that code is sensitive to parameter selection like mu, lambda etc. So any method , that select the parameter automatically or update the parameter.

  12. Hi,I’ve read your papers“Active Contours Without Edges,”and I have some doubts.

    In the paper of MS Energy part Eq(17)
    It looks as:
    [(I-u)^2 / Au] – [(I-v)^2 / Av]

    And in your matlab code it shows
    F = -((u-v).*((I(idx)-u)./Ain+(I(idx)-v)./Aout))
    just like
    [(I-u)*(v-u) / Au] – [(I-v)*(u-v)] / Av]

    I cannot understand it.
    I look forward your relpy.
    Thanks in advance!

  13. Hi,I’ve read your paper Localising region based active contours,”and have some doubts.

    In the paper of MS Energy part Eq(17)
    It looks as:
    [(I-u)^2 / Au] – [(I-v)^2 / Av]

    And in your matlab code it shows
    F = -((u-v).*((I(idx)-u)./Ain+(I(idx)-v)./Aout))
    just like
    [(I-u)*(v-u) / Au] – [(I-v)*(u-v)] / Av]

    I cannot understand how it came like that.
    I look forward your relpy.
    Thanks in advance!

  14. Hi,Shawn
    I have just read the paper “Hybrid Geodesic Region-Based Curve Evolutions for Image Segmentation.” I’m wondering whether it’s an error that the operator before the second term is “+” in eq(15) or “-” in eq(16). In eq(14), I think you dropped “-” before the integration.

Leave a Reply

Your email address will not be published.