The world’s leading publication for data science, AI, and ML professionals.

A bonsai and an ellipse

Fitting an elliptical shape in an image

Andromeda galaxy by Bryan Goff on Unsplash
Andromeda galaxy by Bryan Goff on Unsplash

I recently had to dive into the details of identifying ellipses in images. I must confess that I naively thought it would be straightforward. In various Computer Vision projects I worked on, I had to find circles and disks in images. An ellipse is a squashed circle, right? How hard can it be to go from a circle to a squashed circle? It turns out that conic sections (the family of objects an ellipse is an instance of) have some intricacies that we can ignore in the degenerate case of a circle.

I invite you to follow me in the process of fitting an elliptical shape in an image. You can find the code and the input image in this repository.

The task that we will have to accomplish is to locate the elliptical shape of the edge of the flower pot in this image:

The bonsai in its pot. Image by the author. Bonsai lovingly cared for by the author's wife.
The bonsai in its pot. Image by the author. Bonsai lovingly cared for by the author’s wife.

Creating the mask

Whenever we want to locate a shape in an image, be it a line, polynomial, circle, or Ellipse, we first need to create a mask (i.e. a binary image) of the candidate pixels that are part of the target shape.

In our case, the pot rim appears as a bright edge as compared to the background. Our go-to tool in such a situation is the Canny edge detector, preceded by some blurring to ignore the high-frequency texture that we see in the moss surface and the grass in the background.

The result of this operation is this mask:

Canny mask. Image by the author.
Canny mask. Image by the author.

We have candidate points covering about 75% of the pot edge, in addition to a large number of unrelated pixels from the foliage. We can filter a good proportion of the outliers by observing that the foliage is green, while our points of interest are white. We’ll create a mask of non-green dominated pixels, and keep only the candidate points that also belong to this mask.

We obtain the following mask:

Canny mask after getting rid of green-dominated pixels. Image by the author.
Canny mask after getting rid of green-dominated pixels. Image by the author.

The operation deprived us of ~25% of the candidate points on the rim but got rid of ~90% of the outliers. That is a good deal. Our goal is to increase the proportion of the points of interest in the mask, but we don’t have to eliminate all outliers. Separating the inliers from the outliers will be our mission for the next step.

Modeling an ellipse with RANSAC

An ellipse is an instance of the general class of objects called _conic sections_. Conic sections (so-called because they are the intersection of a cone and a plane) are the solution to the following quadratic equation in two variables:

… which has the equivalent matrix form:

The relative values of the parameters A, B, and C will determine the type of conic section. Specifically, if the discriminant B²–4AC is negative, the conic section will be an ellipse. Otherwise, the conic section could be a parabola (null discriminant) or a hyperbola (positive discriminant). For the rest of the discussion, we will assume that equation (1) represents an ellipse.

Rewriting equation (1) in the form Mz=0:

Equation (3) is a homogeneous linear equation in 6 variables, the parameters A, B, … F. We will need five such equations to solve the system up to a scaling factor.

We have six parameters to solve. Why not six linear equations?

Because it is a homogeneous system of linear equations, i.e. the right side of each equation is 0. If we added a 6th linearly independent equation to this system, we would be stuck with the trivial solution A=B=C=D=E=F=0. That doesn’t look like a very interesting ellipse.

We will solve a system of five linearly independent equations so our solution will have one degree of freedom. Five points (x, y) will allow us to create this system of five linear homogeneous equations that we can solve by eigenvalues decomposition, with numpy.linalg.eig().

Let’s assume we have a point cloud of five 2D points that belong to an ellipse. We now know how to compute the parameters of its quadratic equation by stacking equation (3) in five rows. Unfortunately, we have a point cloud of thousands of points, some of which belong to the ellipse and some do not. That is where the RANSAC algorithm comes into play. By randomly sampling quintuplets of 2D points and solving the corresponding candidate ellipse, we can find the candidate that satisfies the highest number of points in the cloud.

In the following image, the found ellipse is highlighted in blue, the inliers are marked in green and the outliers are marked in red [1]:

The ellipse found by the RANSAC algorithm, the inliers, and the outliers. Image by the author.
The ellipse found by the RANSAC algorithm, the inliers, and the outliers. Image by the author.

We found the implicit parameters for the quadratic equation of the ellipse. That’s great, but what about the parameters that actually matter to us? The ellipse center, the length of the half-axes, the inclination angle?

I wasn’t sure we would go this route, but since you ask, let’s dive in!

Computation of the ellipse parameters

First things first: the center.

Let’s define the function z(x, y):

Since A and C have the same sign (remember: B²–4AC is negative in the case of an ellipse), z(x, y) can be visualized as having the shape of a flattened glass of wine.

The ellipse is the intersection of this flattened glass of wine with the plane z=0. Radial slices of z(x, y) around its center are parabolas (the terms in equation (4) are quadratic, at most) and hence we have a radial symmetry around the extremum because parabolas are symmetric around their extremum. The extremum of z(x, y) is the center we are looking for.

The center of z(x, y), and by symmetry the center of the ellipse, can be found by solving the system of linear equations:

Solving for (xc, yc):

The half-axes and the inclination angle

Knowing the ellipse center, we can define another ellipse, translated so that its center is the origin:

Inserting (4) into (8) and solving for the parameters of the centered ellipse:

The crucial thing to note here is the fact that the terms Dc and Ec are zero. The quadratic equation for the centered ellipse can therefore be written:

… or, in matrix form:

That is reminiscent of the quadratic equation of an ellipse centered on the origin whose axes happen to coincide with the x and y axes:

Equation (17) is more complicated than equation (19) because the general ellipse has an inclination angle relative to the x-axis, which causes the term Bc to be non-zero. Equation (19) is simply a deformation of the x and y axes by their respective semi-axes, squared.

We observe that the central 2×2 matrix in equation (17) is symmetrical and therefore orthogonally diagonalizable [2]. That means its singular value decomposition A=UDVᵀ can take the form A=UDUᵀ=RᵀDR, where R is an orthogonal 2×2 matrix. I chose to call it ‘R’ because an orthogonal 2×2 matrix performs a rotation around the origin.

Rewriting (17) with the singular value decomposition of the central matrix:

We can interpret the left-hand side of equation (21) in the following way, reading from right to left:

  • Starting with an original vector (x0, y0) belonging to an inclined ellipse, we rotate it around the origin by an angle θ to align the ellipse’s principal axes with the x and y axes;
  • Now that the rotated vector belongs to an ellipse whose principal axes align with the x and y axes, we squash the axes with a diagonal matrix, just like equation (19);
  • We de-rotate the squashed vector such that the squashed ellipse has its principal axes aligned with the original ellipse’s;
  • We compute the dot product between the original vector and the de-rotated vector.

This interpretation allows us to read the last parameters that we were searching for, the inclination angle θ and the half-axes a and b, from the entries of equation (21):

Back to our bonsai image, the computed explicit parameters are very good estimates, as we can confirm by manual measurements.

Conclusion

We went through the process of fitting an elliptical shape in an image. We started with the detection of edges, and then we applied a Ransac algorithm to adjust the parameters of the ellipse with consistent points. We used the implicit parameters of the found quadratic equation to extract the explicit parameters of the ellipse.

If you have an application in mind where fitting an elliptical shape in an image would be required, please let me know. I would be glad to hear about it and help you if I can.

[1] The point cloud was randomly subsampled to 400 points to limit the computation time.

[2] https://math.emory.edu/~lchen41/teaching/2020_Fall/Section_8-2.pdf


Related Articles