|
Hi.
Do you know any algorithms for detecting a shape in an image ?
thanks in advance.
|
|
|
|
|
hough transform : for curve responses
harris coner and sobel edge detectors : for macro or constellation features
this kind of problem is studied within computer vision.
|
|
|
|
|
Hough transform can help you in simple shape detection like line circle etc.. You better look PDM(Probability density models ), these can detect shapes. PDM need to be initialized with a training set , after that it will calculate PCA . PDM is not that difficult.. have a look.
If u can Dream... U can do it
|
|
|
|
|
|
Great, thanks
Alan Balkany wrote: If you could describe the task you're trying to accomplish, maybe I could make some more specific recommendations.
Actually , I'm going to detect some shapes (likes circle or rectangles or complex shapes ) in an AVI file or a stream video from WebCam with C# .
Do you have any advices ?
|
|
|
|
|
Once you get your image into a bitmap, morphology provides operations you can use to simplify the image, so it's easier to detect the shape you're looking for. For example, to detect circles with diameter d, doing an erosion by a diameter d circle should result in a single point for every circle in the image.
Many systems have morphological operations built in, which is the easiest way to do it. You can also implement your own, but this is harder and requires specialized knowledge. I found a better link for morphology: http://en.wikipedia.org/wiki/Morphological_image_processing[^]. This includes links to free function libraries that do this.
|
|
|
|
|
|
Yes, that looks excellent. It has morphology and much more.
|
|
|
|
|
Thanks a lot Alan Balkany for answers.
|
|
|
|
|
|
Assuming that these are simple geometric shapes on relatively simple backgrounds (as opposed to real objects against cluttered backgrounds), then I'd suggest:
1. Determine which pixels are foreground (shapes) and background (everything else)
2. Identify individual blobs (connected sets of foreground pixels of the same type)
3. For each blob, extract meaningful features
4. Train a classifier, based on the extracted features
5. Test the system on new images
6. Celebrate!
In step 2, try using a flood fill.
In step 3, there are many features one might try, such as perimeter-to-area ratio.
In step 4, the classifier could be any learning algorithm: neural network, linear discriminant, etc.
-Will Dwinnell
Data Mining in MATLAB
|
|
|
|
|
Thank a lot for the reply.
I'm gonna using C# .
|
|
|
|
|
I have a rectangle(all sides are known). I want to draw X(known number) small rectangles in it.but all of sub rectangles must have same size and a predefined proportion.
This should use maximum area in main rectangle when deciding columns and rows.
i.e If my rectangle is 800x320 and i want to draw 32 sub rectangles in it.All 32 sub rectangles must have ratio (4:3)
What will be the number of columns and rows and width/height of sub rectangles?
modified on Friday, March 20, 2009 3:08 AM
|
|
|
|
|
skelet0n wrote: i.e If my rectangle is 800x320 and i want to draw 32 sub rectangles in it.All 32 sub rectangles must have ratio (4:3)
Columns 8, rows 4, dim ={100, 75}.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
. I bet that was helpful .
|
|
|
|
|
Superb reason is that this 800x320 was just an example and i put this question in algorithm section, because i want an algorithm to solve it. As every time this algorithm will get different inputs, such as rectangle size, sub controls count and sub controls ratio. and the out put will be (row x columns) and their size.
I guess some trigonometry will surely do it...but can't figure it out so far.
|
|
|
|
|
In fact I used and algorithm (no trigonometry involved). Hint: [^].
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
So can you explain that algorithm?
|
|
|
|
|
A hint on the procedure.
You should maximize the sum of the rectangle areas with some constraint (hence the use of Lagrange multipliers).
You requirements give the following constants (supposing all rectangles have the same size):
N the total number of rectanglesw and h , giving the ratio of each rectangle, i.e. ratio w:h W and H , the width and the height of the bounding rectangle
and the following variables
r the number of rows of the rectangle gridc the number of columns of the rectangle gridx defined so that x*w = rectangle width and x*h =rectangle height
You should maximize the total area, i.e. N*h*w*x , while obeying to the following constraints:
N = r*c W >= c * w * x H >= r * h * x
Using (generalized ?) Lagrange multipliers you may write the function L :
L(x,r,c,j,k,l) = N*h*w*x - (r*c - N)*j - (c*w*x - W)*l - (r*h*x -H)*k
where j,l,k are the Lagrange multipliers.
Now you've to find an extreme of it (i.e. all first derivatives with respect the parameters x,r,c,j,k,l should be zero) and verify it's a solution for your problem.
I hope I didn't make silly mistakes.
Good luck.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
No mistakes. This should give him what he wants!
|
|
|
|
|
Thank you for revising it.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
I thought I'd do the math myself. This is a useful problem for rectangle packing.
(Haven't had time to do it just yet)
|
|
|
|
|
How about if the rectangle is 750x325? Assume the material is uniform so that a 3x4 and 4x3 rectangle are equivalent. What's the optimal way to get 32 rectangles then?
|
|
|
|
|
You're a friend of skelet0n, aren't you? Given the algo [^], you can easily figure out the result (you've just to change N from constant to variable).
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
You're a friend of skelet0n, aren't you? Given the algo [^], you can easily figure out the result (you've just to change N from constant to variable).
No, I'm just me. If rotation is allowed, however, the algorithm given won't take optimal advantage of it. For example, the dimensions I gave allow 30 rectangles of size 100x75 or 75x100 to be placed, but only if some are rotated 90 degrees relative to others. What would be the optimal algorithm to deal with that?
|
|
|
|