|
I fixed a HTML problem in my previous post.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Can anyone guide me how to write the Hough circular transform?
|
|
|
|
|
This is used to recognize a circle in an image with incomplete data and/or noise. Every white pixel (assuming a black background) is evidence for a circle that goes through it. You go through all the white pixels and accumulate evidence for all the possible circles. The circle with the most evidence is the result of the Hough transform.
When you find a white pixel, it could be on many circles of radius r. In fact, every point that's distance r away from the white pixel COULD be the center of the circle. In other words, a white pixel is evidence for the center of the circle at all points r away from the pixel, i.e. a new circle with center at the white pixel and radius r.
So you start with an array with all cells set to zero. For every white pixel, increment all array cells at distance r from the white pixel. When you're done, the cell with the highest score is probably the center of the circle.
|
|
|
|
|
Great explanation. What would you suggest for finding circles of arbitrary size though, so radius r is unknown?
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
In that case, you have a three-dimensional space for the circle parameters: center X, center Y, and r.
So instead of a two-dimensional array, you have a three-dimensional array where the extra dimension is for the radius.
When you hit a white pixel, you increment the cells in a circle at EACH level in the r dimension (with the radius given by the r level). As in the two-dimensional case, the cell with the highest score gives the parameters for the circle with the most evidence. But here the r level also gives you the radius.
|
|
|
|
|
I understand that, however now you are using a lot of memory (it has one more dimension than the original image) and incrementing a huge number of counters. Seems like it will take forever, I would hope there is something with better performance...
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
This is a bit of a hack, but it worked fine for me and was quicker then a hough trans.
I was suppose to detect black framed circles in a microscopy image.
What I did was generatin a circle template, starting with 4 pixel in diameter and increase to the width of the image. At each step I correlated my circle template with the image. The highest scoring correlation output was stored. So in the end you know where and which size the circles are.
I did this in Matlab where it was actually easy to do and it was quicker then the hough trans detection and normally more accurate as well.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
These days memory is cheap, and it's possible to draw a circle quickly using only fast integer operations: http://en.wikipedia.org/wiki/Midpoint_circle_algorithm[^].
If you have bounds on the circle's radius, there are a couple of optimizations:
1. It limits the size of the 3D array in the r dimension, and
2. You can preprocess the image to remove convex blobs with radius greater than the minimum radius. These blobs are just noise, and eliminate lots of white pixels which reduces processing time.
|
|
|
|
|
Yep. Actually we did the circle algorithm once in hardware, eons ago, using simple TTL logic. A priority encoder (74148 IIRC) works wonders here (today I would use FPGAs, not TTL).
And another reply hinted on radius estimation. So things start to look better and better.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Luc,
That was also my immediate question. What might be done is to just scan the image for the white (or black) pixels and set the array values just to a 1 for the pixel position itself. Once done, look for adjacent pixels in the first array (horizontally, vertically, or diagnally), either immediately adjacent or separated by 1 pixel (or two or three or ... if a very sparse image). Once such a pair is found, walk the adjacent pixels at both ends to extend the string, then create the equation of a line through the endpoints (a chord), and more importantly, the equation of the perpendicular bisector of the chord, saving this bisector's equation (y = mx+b, slope intercept form). Watch out for a joined line (a complete circular arc - on a clear disk you can seek forever), if found, take the lowest (or highest) 1/4 of the pixels as one arc, and the leftmost (or rightmost) 1/4 of the pixels as the other arc (saving these two arcs in a special array of pairs). Erase the found points in the array, and look for other arcs (connected or not). Now for the fun. Calculate the intersections of the bisectors, starting with the circular pairs (giving the center of the circle and the distance from the center to all ends, averaged, as the radius), then on to the disjointed arcs. For the disjointed arcs, calculate a possible center for all combinations, and choose the closest groupings as a center, eliminate these arcs and repeat (maybe more than 1 circle in the image). Caution, since this is an image, the image of a circular disk could appear as an ellipse and not a circle.
Think this might work?
Dave.
Edit: all of the other answers came in while I was writing this up!
modified on Wednesday, September 16, 2009 11:29 AM
|
|
|
|
|
For one full or partial circle, lots of schemes would work.
Things become interesting when only some small fractions of a circle are visible, and/or multiple circles are intersecting, making "walk the circle" rather tricky; one would need some restraints to the walk and split the chords when in doubt.
Maybe your walking should be used to put some limits on the radius, before applying Hough transform on those pixels.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Hi,,,Thanks for your reply...I will try as per your suggestion and get back..
|
|
|
|
|
Hi,
I need to count the no of circles in the image...
Can anyone help ne regarding the same...
I am developing the application in .Net...
It is very urgent requirment for me...
|
|
|
|
|
See my reply (above) to your following question. This is how to find the clearest circle in the image.
To count the circles, apply the above algorithm, then increment your counter and delete the clearest circle from the image. Repeat until the circle evidence is too low to indicate any more circles remaining. (Some experimentation will suggest a threshold for this.)
|
|
|
|
|
You can also see mine from above. I don't know if it helps but it worked for me.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
Hello ! I'm making cut optimization software, and have problem with the cut optimization algorithm.
I have one big rectangle, and x smaller rectangles (that may and may not be of the same size). Now I need way to calculate optimum position of these rectangles, so that as many as it is possible can fit into big one ... Also I need to draw that positions somehow ...
Can anybody help ?
Thanks
|
|
|
|
|
It depends. Do you know more about the possible sizes of the small rectangles? For some combinations of sizes a simple greedy approach would be optimal.
Also, are the rectangles allowed to be turned 90 degrees?
|
|
|
|
|
Yes, rectangles are allowed to be turned 90 degrees. I don't know possible sizes, they can be anything.
Is there any way to somehow calculate coordinates of rectangles inside big rectangle?
What do you mean by greedy approach ? Is there any kind of already made algorithm that could help me ?
|
|
|
|
|
Greedy is when a series of optimal local choices will always lead to a global optimum
Which is not the case here. It would have been for some sizes of small rectangles.
But basically, this sucks. Does it absolutely have to be actually optimal?
Also, are the coordinates not-too-big integers?
If they are, what you could try (but I don't guarantee it's the best way) is a limited form of Branch&Bound combined with a heuristic to determine which choice to test first (to test "probable" cases first) and bound the subtree when you can determine that due to earlier choices it would be completely impossible to find a solution in that subtree (such as when the biggest open space is not big enough to place the biggest unplaced small-rectangle in it)
It will still suck for any but tiny instances of the problem. There would be an enormous number of choices at each node - the total number of possible placements of all rectangles that were not yet placed. The heuristic might be something like "try the biggest rectangle first" combined with a sane way to place it (eg near the edge).
I don't even see a way to do real B&B on this..
It's stupid though, there are many overlapping subproblems (you could use memoization but you'd get a Huge lookup table - maybe try something like "memoization only for the first k levels of recursion") and this algorithm would likely take longer than the estimated age of the universe to run on any interesting instance of the problem.
If a non-optimal (but "good") result is also OK, you could use basically the same algorithm but with far less choices (eg use an heuristic to do only the k "probably best" choices at each node) - you can still expect major suckage.
I hope this helped anyway.. though I don't think that's likely.. sorry
Note: I apologize for all errors and falsities in this post, there can't be none but I don't know what they are yet.
|
|
|
|
|
Yeah, you're helping and thanks for that 
Anyway, I don't think that coordinates will be bigger than 32000 (maybe not bigger than 10 000). I've thought of similar approach with recursion and memoization, but I'm not sure how to do it (I think I'll run into memory problems).
And yeah, non-optimal but "good" result should be OK. I'm not familiar with Branch&Bound, but I'll research it and try to learn something 
And one more thought ... Should I try placing every rectangle two times(normal and 90 degrees rotated) in the big rectangle and use memoization? Then I can determine how must small rectangles can there be for that algorithm to be executing in about 10 seconds ?
And I also have one more problem ... What's the best way to remember what parts of big rectangle I've already used ? I don't know how to do it ... Should I try with some custom class or ?? Please tell me if you have any ideas
And one more time, thanks for your big help !
|
|
|
|
|
xx77abs wrote: And one more thought ... Should I try placing every rectangle two times(normal and 90 degrees rotated) in the big rectangle and use memoization? Then I can determine how must small rectangles can there be for that algorithm to be executing in about 10 seconds ?
I don't really know what you mean by that - could you explain it in more detail?
xx77abs wrote: And I also have one more problem ... What's the best way to remember what parts of big rectangle I've already used ? I don't know how to do it ... Should I try with some custom class or ?? Please tell me if you have any ideas
I have a couple of idea, but none of them are really good:
1) directly use the positions of the rectangles to calculate intersections (slow)
2) use a bitarray (too much memory)
3) hybrid: store big rectangles as rectangles, but use bitarrays to store the small rectangles (justification: in general the small rectangles will end up close to each other since using small rectangles leaves small gaps) Very complex though, and it may not be worth the effort
You're welcome, but I have the nagging feeling that there is a better solution - I just don't know what it is.
|
|
|
|
|
harold aptroot wrote: I don't really know what you mean by that - could you explain it in more detail?
I meant that I'll try and make recursive function that will implement memoization and try to find best possible solution. Then I'll run it with various number of elements and determine what's the case in which recursive function works OK(not too slow). And if that's OK for the person that has requested the program from me - problem solver
harold aptroot wrote: I have a couple of idea, but none of them are really good:
1) directly use the positions of the rectangles to calculate intersections (slow)
2) use a bitarray (too much memory)
3) hybrid: store big rectangles as rectangles, but use bitarrays to store the small rectangles (justification: in general the small rectangles will end up close to each other since using small rectangles leaves small gaps) Very complex though, and it may not be worth the effort
You're welcome, but I have the nagging feeling that there is a better solution - I just don't know what it is.
1. Yes, I think that would be too slow
2. Yes, it would take too much memory if big rectangles maximum size if 32000x32000. But if it is 10000x10000, then memory consumption would be about 100 MB (that I can spare). So this is maybe good solution (I have to contact the person that has requested the program ...)
3. Well, I'm not even sure how to implement this
Yeah, I too have feeling that there's a better solution - maybe already completed algorithm ...
|
|
|
|
|
Ok, then, I don't have much to add.. I hope someone else knows a better way
|
|
|
|
|
I've worked on a similar problem before but not exactly like your issue. I would suggest that you google "rectangle packing problem" and read some of the papers in the google links. Maybe you can modify the algorithm to work for your case.
|
|
|
|
|
Thanks, I'll read that
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
