math/algorithm to find a rectangle and a circle in a picture

im not sure i am posting on the correct forum but this is the only one i though suitable.

i am trying to think of the best (fastest) way to search for a rectangle in a picture frame taken from a webcam . and also circle (seperatly)
the "problem" is that the rectangle can be turned cw and ccw .

and when i say "way" , i mean algorithm using math.
and as for the webcam, i got all the code for it, so thats not what i will be talking about. i will talk about single frame of picture

it is known that the efficiency with these things is as less pixel scanning and more math calculations , is faster , because pixel scanning takes much longer time and resources.

so i came up with some idea and would like to hear your opinion and suggestions

ok first rectangle - refer to first attached picture
i have many colored points (pixels) which i will mention
2 red ; 2 purple ; 4 blue ; 4 green ; and 4 yellow

so my idea is like this
to start with from the 2 red dots and go vertically up and down untill i meet a black dot (which is the rectangle) . this will give me the 4 blue dots (2 up and 2 down)
from these 2 sets of dots i can calculate the y=ax+b (or also known as y=mx+n, same thing) which is the linear equation, of the upper and lower lines of the rectangle.
so now i will have 2 equations of y=ax+b
next i will do the same horizontally , start from the purple dots and horizontally left and right untill i meet a black dot (which is the rectangle). this will give me the 4 green dots (2 left and 2 right)
from these 2 sets of dots i can caluclate the y=ax+b of the left and right lines of the rectangle.

all this will give me total of 4 equations of y=ax+b, 1 for each line.
now i can take 2 crossing lines equations and find the intercross dot which is the edge of the rectangle. i'll have to do it for each edge, total of 4 times.
and done.

the problem with this method, as i see it, is what if the rectangle will be turned too much , and the green or blue dots will not be found on the correct line. that will destroy everything for me.
refer to the second picture attachment , look at the red arrow.
if i will come upon this black dot it will mess up my y=ax+b for the right side line of the rectangle.



now circle is easier
refer to the 3rd picture attached

i'll start with the purple dot
and scan pixels vertically up and down untill i find a black pixel which is the circle its self. this will give me the 2 green dots and from that it will be easy to calculate the Y center of the circle (orange/brown dot)
i'll do the same horizontally which will give me the 2 yellow dots and from that it will be easy to calculate the X center of the circle (orange/brown dot)
combining the center X and the Y will give me the complete center point of the circle (black dot)

then i can scan pixels from the center in the up direction ( or down or left right , doesn't matter) untill i meet the circle. this will give me the RADIUS.
and done!

now , if the circle is infact elliptical, then not big deal, in addition of scanning from the center up , i will have to scan from the center towards right (or left, doesnt matter) this will give me the SECOND RADIUS.


the circle is easy, but the rectangle can be a problem.

so ?
what do you think?
is this a good idea?
do you think its possible to implement?
do you have better ideas?

any thoughts will be appreciated
and thanks for reading this silly post :)

To start I'm just looking at your rectangle case. One particularly nasty case for your algorithm is a perfect diamond, with the red and purple points placed in such a way that the blue and green overlap each other. Your algorithm would detect a square instead of a diamond. I say this is particularly nasty, because you could try a "fix" where you check to make sure none of the green dots are colinear with pairs of blue dots.

I don't think this algorithm can be easily saved. There are too many edge cases. Once you reach a side, can you scan around to see how that side is tilted? If so you could use only 1 red and 1 purple point, perhaps even making them the same point, scan in all 4 directions out from that point, and at the worst I think you'd only hit 3 out of 4 sides of the rectangle. Finding the 4th would take one more scan.


For the circle, your algorithm will work fine--unless the ellipse can be rotated. You could probably do it with one fewer scan and more math. Any 3 points on a circle give enough information to find the equation of that circle (slog through the algebra if you want to prove it rigorously), which gives you the radius without having to scan from the center. You should be able to do the same with the ellipse.

wow, im impressed you actually read all that :) thanks !

Quote:

---

To start I'm just looking at your rectangle case. One particularly nasty case for your algorithm is a perfect diamond, with the red and purple points placed in such a way that the blue and green overlap each other. Your algorithm would detect a square instead of a diamond. I say this is particularly nasty, because you could try a "fix" where you check to make sure none of the green dots are colinear with pairs of blue dots.

---

it wont be a perfect diamond... i'm doing this for something specific...
i have an iphone , and im playing pool there, and i wanted to see if i can write something that will help me "cheat" in it, for my program to show me where should i hit the ball to get it in to the pocket. for me to create something like that would be a great challenge. now its more for the challenge of making it work then to really have it for the pure ability to "cheat".
i have a webcam above the iphone and i'm analyzing the frames.
the iphone is rectangle, and yes ofcourse i can place it in such way that i wont have to really deal with rotated rectangle. but again , this developed into a challenge and the "how cool it would be if it will trace the iphone rectangle screen on my computer screen with a webcam" factor. :)

Quote:

---

I don't think this algorithm can be easily saved. There are too many edge cases. Once you reach a side, can you scan around to see how that side is tilted? If so you could use only 1 red and 1 purple point, perhaps even making them the same point, scan in all 4 directions out from that point, and at the worst I think you'd only hit 3 out of 4 sides of the rectangle. Finding the 4th would take one more scan.

---

i actually started in my mind with exactly what your suggesting, but the webcam gives me 30 fps, and i knew that scanning this way will be slower, so i tried to think of quicker ways, and the only solution is math.

do you still think i should try the scan method ?

Quote:

---

For the circle, your algorithm will work fine--unless the ellipse can be rotated. You could probably do it with one fewer scan and more math. Any 3 points on a circle give enough information to find the equation of that circle (slog through the algebra if you want to prove it rigorously), which gives you the radius without having to scan from the center. You should be able to do the same with the ellipse.

---

the circle is actually the balls , so it wont be rotated elliptical shape...

I would imagine that, after colliding with a black spot, scanning around to determine the slope of the line you hit wouldn't take too long for your computer. You could always ignore most of the frames; 30 is probably overkill, depending on exactly what you want to do.

The only other fool-proof solution I can think of is to scan along a larger number of lines, using more complex reasoning that doesn't seem worth it.

ok , i'll try both, see how it goes, but little later, i dont have time now...

thanks for responding!!

i'll keep u informed and post the full project when im done