Boundary detection in images using the “Color Snakes” algorithm and its improvements.

One of the basic problems in image analysis is segmentation of objects in pictures.

Abstract
One of the basic problems in image analysis is segmentation of objects in pictures. This problem was partially solved for “easy” pictures. The meaning of “easy” is: smoothness of the picture and without much noise.

What we dealt with in our project, is to find an algorithm that will find well boundaries in noised pictures or boundaries between different textures, such as in Ultrasound and MRI images.

We will review few known algorithms, starting with the classical method. We will focus on the “Color snakes” algorithm. We will change and improve the last one to reach better results.

Note. We use the word “color” to refer to general multi-valued images.
 
Classical snakes algorithm
This is the basic algorithm for boundaries detection.

This algorithm is based on defining an initial contour, and deforming it toward the boundary that we would like to find. We define an energy function for the picture, thus the deforming contour will converge to the local minimum of this function, where the boundary is located. The contour saves its smoothness and does not split easily.

1
 
where g is a function that fulfill , x?? leads g(x)?0, I is the intensity and C is the curve.

The most popular g function Is 2(p=1,2).
 
Geodesic snakes algorithm
The geodesic snakes method gives a solution in a different way. The solution is given by a geodesic curve in the Riemannian space, which derived by the image.
 
Color snakes algorithm
Here, the calculation of the e function, which we converge the contour to (previously it was called g), is being in a different way. We don’t use only the information about the intensity in each pixel in the image, but also different kinds of information, such as the variance of the image. The e function weights all those factors.
 
The algorithm improvements
In order to deal with images like Ultrasound and MRI, which have textures and much noise, we added to the weights the information of the variance and the mean of the image in a window around the pixel. (The window size, and the weights of the factors are parameters in this algorithm).

We also added a little smoothing to the image before the algorithm starts its work, and we changed the e function with a specific LUT.
 
Experimental results
We’ve tested the algorithm on several kind of images.

  • A binary image of 2 circles

    • 3
     

  • MRI image of a knee

    • 4
     

  • 2 Brodatz images (of textures)

    • 5 6
     

  • 2 Ultrasound images

    • 7 8
     
    First thing we did is, showing that when we have a good e function, the contour is converged to it well.

    We tested it on several examples. Here is one of them (a simple example of convergence to the e function of the “2 circles” image.

    This is the U function (that the curve is a zero level of it) :

    9 10 11 12
    The initial U after 500 iterations after 1500 iterations after 2500 iterations

    13 14 15 16
    after 4000 iterations after 5000 iterations after 6500 iterations after 8000 iterations

    We saw that the part of convergence to the e function goes as well as the quality of the e function. That is why we have referred from now only to the quality of e.

    Here are the results of all the 6 images, using the classical algorithm against the results using the new color snakes algorithm with the improvements that we’ve added:

    (Click on a picture to see it on a full screen).

    win
    k1
    k2
    		 Using the new
    “color snakes”     algorithm    		 Using Classical
    algorithm
    3
    1
    1000
    17
    18
    3-11
    1
    1000
    		 19 20
    11
    1000
    1000
    21
    22
    11
    1000
    1000
    23
    24
    3
    0.001
    0.1
    25
    26
    11
    1
    1000
    27
    28

     
    k1–the variance coefficient. (in a window around the pixel).

    k2–the mean coefficient. (in a window around the pixel).

    win – the window size that we take.
     
    Conclusions

    • We saw that for images that are close to binaric, without noise and with loud and clear boundaries, our new algorithm do not help, and even damage the results, because of the window size, that spread the boundary
    • For images with a much noise, the algorithm helped a lot, cleaned the noise and found only the relevant boundaries. Yet, this is not a magical algorithm and when the noise is too big the algorithm can not deal with this satisfactorily
    • The algorithm distinguish between different textures very well. This is a great improvement of the new algorithm. Yet, the algorithm have much difficulty when the image has many textures in it

     
    Credits
    We want to thank all those who gave their help and support:
    Chen Sagiv – project mentor, who helped and guided us through the whole project.
    Johanan Erez – the lab engineer, who helped us with all the administrative things etc.