ellipse detection out of set of points

Programming Questions

clankill3r

ellipse detection out of set of points

in Programming Questions • 2 months ago

I'm working on a knob detector to use with a webcam.

Based on the green dots in the image i want to create an ellipse.

One dot is missing, on the right.

The other dot is to much off (on the control line of the knob).

Here are the coordinates:

int[][] coords = {{189, 78}, {296, 35}, {285, 209}, {189, 206}, {134, 167}, {118, 128}, {128, 82}};
void setup() {
size(400, 400);
background(0);
fill(255, 0, 0);
noStroke();
for(int i = 0; i < coords.length; i++) {
ellipse(coords[i][0], coords[i][1], 5, 5);
}
}

Is there any algoritme to figure out where it could be?

Replies(8)

PhiLho

Re: ellipse detection out of set of points

2 months ago

I don't understand the rules you want to use to make your ellipse.

Chrisir

Re: ellipse detection out of set of points

2 months ago

the middle is $(x_0|y_0)$

$\begin{pmatrix} x\\ y \end{pmatrix}=\begin{pmatrix} x_0+a\cos t\\ y_0+b\sin t \end{pmatrix} \quad \text{mit} \quad 0\le t< 2\pi.$

see
http://en.wikipedia.org/wiki/Ellipse#Parametric_form_in_canonical_position
etc.

Greetings, Chrisir

If you need an answer, please send me a personal message since this forum doesn't notify.

Chrisir

Re: ellipse detection out of set of points

2 months ago

so this is the idea

// ellipse
void setup() {
size( 600, 600 );
background(0);
}
void draw () {
background(0);
stroke(244);
// diameters
float a = 90; // in x
float b = 30; // in y
// b=mouseY;
// center
float centerX=100;
float centerY=100;
// loop
for (int i=0; i<360;i+=10) {
float x=centerX+a*cos(radians(i));
float y=centerY+b*sin(radians(i));
println (x+","+y);
point(x, y);
} // for
} // func
//

Greetings, Chrisir

If you need an answer, please send me a personal message since this forum doesn't notify.

PhiLho

Re: ellipse detection out of set of points

2 months ago

Chrisir, I think he wants to make an ellipse enclosing all the points of a list, probably the smallest possible, but I am not sure, hence my request for clarification (and what is the current implementation and the exact problem it has).

Chrisir

Re: ellipse detection out of set of points

2 months ago

hello,

well my program could help with his problem

either he wants to improve the list he has (I think that's his wish and my program is pretty good for that)
or as you say he wants to make an ellipse enclosing all the points of a list : then he could play with a and b and make the program make a and b smaller until he can't go smaller without touching them

Greetings, Chrisir

clankill3r

Re: ellipse detection out of set of points

2 months ago

thanks for the speculating :)

Let me try to reformulate my question in a more abstract matter.

Let's say i have the following points:

Then with the eye we can see that there is an ellipse shape in it.

What i want to know is how to write a algoritme that can detect if there could be an ellipse shape.

It can be that some points are off like in the next image:

I could imagine that multiple ellipses get created for testing and that the one with the most hits is picked as best result.

Chrisir

Re: ellipse detection out of set of points

2 months ago

hm...
starting of with my code

you could resolve the formula in a way that you could derive centerX and / or a but I don't have the math for it

the proceding:

make a class with the properties of the ellipse (center, a, b) and the similarity score
make an arraylist of the class and all tests fill in the arraylist
when tests are all done search the object in the arraylist with the highest score, that's your ellipse

the tests:

average all of your points x and y, you have a potential center
you could move the center in a square around the average
you could for all of those centers try different a and b
to check the points you have with those from the formula you need to allow for an offset of + or - 2 or so I guess

Greetings, Chrisir

mbraendle

Re: ellipse detection out of set of points

2 months ago

Simple, approximate solution:

You have n points (xi,yi), i being a counter.

First you calculate the average of the points in x and y direction, which gives you the mid-point

x0 = 1/n sum xi

y0 = 1/n sum yi

Then you calculate the maximum distance from your points to the mid point, in x and y direction separately --> a, b

a = max ( | xi - x0 | )

b = max ( | yi - y0 | )

Then you can draw

ellipseMode(RADIUS);

ellipse(x0,y0,a,b);

This should give an ellipse which encloses all points.

Complicated solution:

You need to minimize the following function:

R = sum((y - yi)^2 + (x-xi)2)

where y = y0 + b sin t , x = x0 + a cos t

R is a hypersurface that depends on the parameters (x0,y0,a,b)

You need an algorithm such as Simplex to find the minimum of R.

As start parameters I would feed in the x0,y0, a, and b from the first solution.

For each yi,xi you need to calculate an approximate t solving the formula (yi - y0) / (xi - x0) = b / a * tan t with the current parameters you have in each optimization step.

This can be iterative as well: After you have found an optimized set of parameters, you can find the point (yi,xi) which has the largest distance to the ellipse. You eliminate this point and repeat the optimization.

Top Reply