Description
Introduction
In the first part of the assignment, it is your task to implement the Snakes: Active Contour model by (1).
It was already introduced in class, but the most important details will be reiterated. The method uses an
energy-minimizing discrete curve, which adapts to a contour in an image. It is guided by internal forces
that change the behavior of the curve and image forces to pull it towards features like lines and edges.
E
∗
snake =
Z 1
0
Esnake(v(s))ds =
Z 1
0
Einternal(v(s))ds +
Z 1
0
Eexternal(v(s))ds (1)
Using an approximate discrete representation, the energy calculation can be simplified to:
E
∗
snake =
Xn
i
Esnake(i) = Xn
i
Einternal(i) +Xn
i
Eexternal(i) (2)
In this assignment, you will implement this method from scratch. A framework is provided along with this
document, which will help you implement the method and run experiments on different images. In the
following, different parts of the assignment and their respective grading are explained
Part 1: Initialization (2 pts)
In the main.py file, There is a code which opens an image and gives the user the ability to select the initial
points of the contour. However, to increase accuracy, you should write a code that interpolates between the
user-selected initial points with n evenly spaced fine points. Here, n is a parameter which can affect the
quality of the final output.
CMPT 732 A1-1
Part 2: External energies (12 pts)
As we discussed in class, External energies are used to drive the contour towards the salient features of the
image like edges, corners, and lines. For this part, you should complete the file external_energy.py which
contains four functions:
1. Eline: This energy is equal to the intensity of the image.
2. Eedge: This energy pulls the contour toward the edges of the image and it is equal to the magnitude
of the gradient of the image.
3. Eterm: This energy pulls the contour toward corners and it is calculated as follows:
Eterm =
CxxC
2
y − 2CxyCxCy + CyyC
2
x
(C2
x + C2
y
)
3
2
(3)
In this equation, Cx and Cy are the first order derivatives of the image in the x and y directions, and
Cxx, Cyy, and Cxy are the second order derivatives of the image.
bonus question (2 pts): prove that image curvature can be calculated with the equation
above, and write it in your report.
4. Eexternal: The external energy is a weighted sum of all the above energies.
Eexternal = wlineEline + wedgeEedge + wtermEterm (4)
the weights specify the importance of each feature, and can vary based on application. The output of
all the functions in this part are matrices in the size of the original image.
1 Part 3: Internal energy (8 pts)
The internal energy’s job in the active contours’ framework is to control the characteristics of the curve, by
controlling the first and second derivatives of the curve. This control is further handled with two parameters
α and β. The former, is related to the first order derivative of the curve and forces the curve to act like an
elastic band. The latter, controls the smoothness of the curve and forces it to act like a metal sheet. As
mentioned in the class, the optimization of the internal energy can be done using a pentadiagonal matrix A.
In this part you should complete the file internal_energy_matrix.py which contains a function that takes
α, β, and the changing step size γ, and returns the matrix M = (A + γI)
−1, where, I is the identity matrix.
CMPT 732 A1-1
2 Part 4: Optimization loop (8 pts)
Back in the main.py file, you should finally complete the optimization loop. As discussed before, the
optimization is done separately for x coordinates and y coordinates as follows:
xt = M(γxt−1−κfx)
yt = M(γyt−1−κfy)
Here, κ is an extra parameter that controls the importance of the external energy, compared to the internal
energy. fx and fy are the gradients of the external energy in the x and y directions. Notice that because
the external energy is computed on the image grid, it is only defined on integer coordinates. Thus, you have
to do bilinear interpolation in order to get fx and fy. Furthermore, blurring the image at the beginning,
might help with the quality of the output.
3 Report
For the demo session, please prepare parameters that work for each example image in the images folder.
Additionally, you should submit a written report that includes:
1. visual results on the provided images. include at least the following scenarios:
• For the binary images (circle, square, star, shape) and the vase, segment the objects
• For the dental image, segment the row of teeth
• For the brain image, segment the outer layer of the skull, the inner contour of the brain matter
• The right eye hole
2. proof of the bonus question (optional).
References
[1] Michael Kass, Andrew Witkin, and Demetri Terzopoulos. Snakes: Active contour models. International
journal of computer vision, page 1(4):321–331, 1988.
