Approximate binary shape with a set of ellipses?

Software G'MIC
1

Hello there.
I’ve an idea for a new image filter, but I am a bit stuck with one of the main step, that is:

Finding the largest ellipse (allowed to have an arbitrary orientation) within a binary shape.

1. A simpler problem:

I’ve tried a few things, and found out that solving this problem when considering circles (instead of ellipses) is relatively easy, and can be done with the following code (taking advantage of the distance function):

# Approximate a binary shape with a set of circles.
approx_circles :
  shape_cupid 400 # Input binary shape
  is0:=is
  100%,100%
  do
    +distance[0] 0 x,y,r:=xM,yM,iM rm.
    circle[1] $x,$y,$r,1,{1+$>}
    circle[0] $x,$y,$r,1,0
  while is#0>0.05*$is0
  k. map lines,2

This script transforms the following binary shape:

approx_circles0

into this set of circles :

approx_circles

2. Solving it with ellipses?

Now, the question : how to do the same thing with a (ideally optimal) set of ellipses ?
Currently, I know how to “approximate” a binary shape with an ellipse, by computing a covariance matrix and get the corresponding eigenvalues/eigenvectors that are related to the ellipse radii/orientation.
But that’s not what I want, because the approximated ellipse will most of the time contain background pixels, while an inscribed ellipse will obviously only cover white pixels of the binary shape.

So, how would you solve this, dear smart people of pixlsus ?
Any idea ?

2

Do I understand correctly: the idea would be to fill the most space possible - enclosed within the shape - with a single arbitrary ellipse, then repeat with remaining space until it’s completely filled (or an equivalent method)? That’s probably too difficult for me, but will think about it anyway…

3

I have been having severe back pain recently, so I may not be thinking clearly. Here are random thoughts that could be too expense or silly:

Have you tried other shapes such has lines or rectangles? Rotating the base shape? Sorting pixels? Scaffolding distance or the skeleton? Geodesic dilation or erosion?

4

Yes you do :slight_smile:

Lines is actually a good example of an ellipse with one radius being 0 and the other being max.
What I’m looking for is to fill the shapes with ellipses with maximal possible area each time.
My intuition tells me that probably, these ellipses will be sometimes circle-shaped (if I want to maximize the area), so maybe a good idea would be to start from the best fitting circle and try to elongate it to get a bit more area covered.

5

OK, so here is the result of my filter when considering only circles :

gmic_test
gmic_test1476×520 230 KB

Input image on the left, set of circles on the middle (with multiple scales), and shape-average blending on the right.
Makes a sort of painting look. Could be so nice with oriented ellipses :slight_smile:

6

I think I have a idea, but might not be that great. What if you can find perpendicular lines associated with binary shape and use that to find orientation of ellipse, and scale based on that? It’s like distance, but with the catch where average orientation is there.

Yeah, I don’t know how to explain it nor I expect this to help.

7

Can the ellipses be aligned at any angle, or must the major and minor axes be parallel to the image x and y axes?

In either case, I can’t see a solution other than trial-and-error.

1 Like
8

Do I understand correctly: the idea would be to fill the most space possible - enclosed within the shape - with a single arbitrary ellipse, …

Suppose the space happens to be in the shape of two overlapping ellipses. One has semi-axes 50 and 50 (it is a circle), the other has 550 and 5. The ellipse is slightly larger than the circle.

x
x1200×200 11 KB

The pixel that is furthest from any edge of the shape is in the centre of the circle. But if we fill the space with an ellipse centred there, we haven’t filled the most space possible. For that, we should choose the centre of the thin ellipse, even though that location is close to the edge of the shape.

EDIT to add:

Filling with circles works well because the distance from each point in the shape to the nearest edge(s) is the largest radius of circle that can be drawn centred at that point.

We could represent the shape in a 3-dimensional figure. The third axis is the possible range of ellipse aspect ratios. Put this another way: we have one basic 2D image of the shape. Another image has the same shape slightly squished (reduced) in the x-dimension, and increased in the same proportion in the y-dimension. Then another image, squished a bit more. And so on. In the other direction from the basic image, we reduce the y-dimension and increase the x-dimension. So a circle in any of these squished images represents an ellipse with a known aspect ratio in the basic image.

In my shape above, one of the squished images would have a tall thin ellipse on the left, and a large circle almost beneath it.

In each of those images (or all along the third dimension), at each pixel, find the distance from the nearest edge(s). The pixel in the 3 dimensional shape with the greatest distance is the one we want. From its 3D coordinates, we know the aspect ratio of the ellipse, and its (circular) radius with this squishing, and hence the major and minor axes, and we know its location.

I don’t claim this would be fast. It is effectively trial-and-error.

EDIT again: The above assumes the ellipse axes are constrained to be parallel to the Cartesian axes. If that is not the case, and ellipses at arbitrary angles are allowed, the solution is to represent the shape in four dimensions. The fourth dimension is the angle.

G’MIC has 4D images, right?

1 Like
9

You can actually have 5D+ representation as a 1D array when creating 1D representation of Cartesian product of each dimensions. G’MIC images are 3D + fixed size array which can be 4D, but with Cartesian Product trick, you can treat 1D array of fixed size array as 5D to any arbitrary dimensions.

10

Sounds like a question for a mathematician. I’m no mathematician, so I can only offer my ideas as a programmer.

If the ellipse’s eccentricity and angle are known, the problem reduces to the circle problem. I assume you know how to perform this reduction (if not, see @snibgo’s comment). Then it’s a matter of finding the optimal eccentricity and angle. We can describe the area of the optimal ellipse as a function of eccentricity and angle. I imagine it will be a 3 dimensional version of a piecewise function. The trick is developing an algorithm, perhaps taking inspiration from gradient descent, to find a reasonable local maximum, tuning the parameters to balance speed and accuracy. Once you have the eccentricity and angle, turn it into a convincing solution by finding the best size and position via the circle problem.

That last part may give you another idea. If your eigenvector algorithm yields ellipses with reasonable eccentricity and angle, use those and refine the size and position.

1 Like
11

Yes, that’s why trial and error is getting costly. I’ve tried that and while you end up with reasonnable ellipses after a few (hundreds of) trials, they are still far from being optimal.

12

A multi-scale approach may help. For example: resize the input to 50% in each direction. Find the best ellipse (position and semi-major axes and angle) at that scale. Parameters of that ellipse, scaled up, are probably close to parameters of the best ellipse at the larger scale. So that greatly limits the search space we need to examine at the larger scale.

We can do this recursively, within some limit. More recursion will increase speed but also increase the probability of finding a sub-optimal solution.

1 Like
13

Would this point you in the right direction? https://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf

1 Like