We help IT Professionals succeed at work.

Algorithm for shape recognition

goldrian
goldrian asked
on
2,100 Views
Last Modified: 2013-11-12
It seems a so simple task, but I have many doubts on how to approch the problem.
All I need is, starting from a 2-colored bitmap showing a plane and a fulfilled circle, to find the starting x,y, width and height of the minimal square which inscribe that circle.
Dear Experts, any idea on the algorithm that may solve this problem?
Comment
Watch Question

ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
couldn't you just find the leftmost, rightmost, uppermost, and bottommost points in the circle?

Author

Commented:
Ok... I said simple, but not SO simple :)
The input is a bitmap image, I don't have leftmost, rightmost, uppermost and bottommost points of the circle.
It may vary, since the circle will be randomly placed in the image. And also its size may vary.
Ok, the quest could be to find those 4 points instead of a square. But how?
For calculating those 4 points:

uppermost:
for each row, progressing from top to bottom,  run through the pixels you hit a shaded pixel on the row.  Take the coordinate of the centremost shaded pixel on that row to find the uppermost point of the circle.

bottom:
as for uppermost except scan rows from bottom to top

leftmost:
for each column, starting from the left, cycle through the pixels in it, stopping when you hit a shaded one.   Again use the coordinate of the centremost shaded pixel as the leftmost point of the circle.

rightmost:
as fo leftmost, but start from the right

Author

Commented:
if noone has a more optimized method I'll accept that :)
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Author

Commented:
Quite smart.
However, if the image is very big, the scanning of every pixel can take a long time.
I keep the question open for now :)
ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
If you know that the object is a circle, then any 3 points on the edge would give you the centre and radius.
Given a point inside and a point outside, you can binary search between them to find an edge.
A point inside a large circle can be found in an average of sizeofimage/sizeofcircle probes.
Scanning in steps in a Golden Ratio can give fairly even coverage at increasing resolutiom.

Author

Commented:
Could it be a good idea to look for a point inside the circle using a random function?

>Scanning in steps in a Golden Ratio

I think I need more explanation on this point :)

Author

Commented:
Ozo, what do you mean with "Scanning in steps in a Golden Ratio"?
Thanks.

Commented:
If you have only one circle it must be not so complicated. The easy way is scan the image lines.
If circe is filled with the other color you can use "binary search" - I think ozo call it "Golder Ratio". You divide you scan on the middle and check where is the filled/unfilled area. When you find it you can divide you interval by 2 and find it again. After some iteration steps you can find the "switch" point exactly.
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.