Week 3: Image Segmentation

Goal

The goal of the third block was to successfully implement the Chan-Vese algorithm in order to detect contours around binary and color images. This will be done by considering, as usual, a minimization problem, which we will formulate according to level set theory.

Mandatory Tasks

Implementation of explicit Chan-Vese algorithm

In 2D, the level set method amounts to representing a closed curve (such as the shape boundary) using an auxiliary function, phi (our level set function). It is initialized in the code as a circle in the center of the image of radius 50, and it is given Neumann boundary conditions.

The determination of the image boundaries is done by minimizing the functional below. We can see that the functional is composed by four main parts.

• Length parameter (µ). It is the first term of the functional, and penalizes boundaries that have higher length using the constant. The higher the , the more the boundary stretches itself to fit around the foreground with a smaller perimeter. This way, we avoid unnecessary details in the boundary for the noisy images.
• Area parameter (ν). It penalizes the boundaries that enclose bigger areas.
• Discrepancy between f and u (λ1, λ2). The first term it is related to the discrepancy between the given grayscale image (f) and the foreground. And the second term to the discrepancy between the grayscale image and the background.

We initialized the region averages c1 and c2 to 1 and -1, which will be computed by discretizing the following equations:

.

We based our numerical implementation on the semi-implicit scheme described in Gertreuer, but applied it explicitly. This consists in one Gauss-Seidel sweep from left to right, top to bottom:

Results (Binary)

circles: mu = 0.2, it = 850, dt = 0.5

circles: mu = 0.2, it = 5000, dt = 0.5

phantom17: mu = 0.5, it = 22000

phantom17: mu = 0.5, it = 22000

Results (Noise)

noisedCircles: mu = 0.05, it = 23000

noisedCircles: mu = 0.05, it = 30000

phantom18: mu = 0.3, it = 20000

phantom18: mu = 0.1, it = 22400

It might be worth noting that the closer the initialization of phi is to the shape of the contour we are looking for, the faster/better the convergence. For example, for the phantom images, if phi is initialized as a diagonal line of the form y = -ax instead of a circle, it converges significantly faster to the shape of the boundary.

As for the case of the phantom18, instead of initializing the phi function as a circle centered in the image, we chose a displaced circle for the same reason mentioned above.

Curve Evolution

Limitations of Chan-Vese

It can be seen that in image phantom19, the Chan-Vese algorithm fails to correctly find the boundary despite going through 20,000 iterations.

phantom19: mu = 0.3, it = 20000

This happens when the region averages c1 and c2 are approximately equal. These are phi’s principal guidance for where to go to separate the foreground and the background, so it stands to reason that if they both have very similar values, phi will not be able to distinguish the regions.

For phantom19, c1 =  0.5408 and c2 = 0.5401. They differ by 0.0007, whereas for circles, for example, the region averages (0.2494 and 0.1845) differ by a significantly larger 0.0651.