Detecting multiple shapes in a picture and calculate the middle

6
votes

This question can be answered with any type of programming language, cause I would like some help with algorithms, but I prefer Delphi. I have a the task to detect and count multiple shapes (between 1 and N - mostly circular or a Elipse) of random pictures and calculate their middle and return them as coordinates of a picture. The middle of each shape can have a filling (but it doesn't matter). The shapes are at least 1+ pixel away from each other. None of the shapes will like blend in with another or the corner of a picture. The background of the picture has always the same background color, which actually doesn't matter, cause the borders/frames of the shapes are always a different color compared to the background. This makes it easy to detect the shapes. I was thinking about going pixel by pixel and collect the coordinates and then draw like an invisible rectangle/square around every shape to calculate the middle. Then I also heard about scanline, but I don't think it would be faster in this case. So my question is, how can I calculate:

  1. How many shapes are in the picture.
  2. How can I calculate (more or less) the exact middle of them.

A few pictures to visualize the task:

This is a picture with random shapes (mostly close circles) As you can see they are apart from each other just fine.

Shapes in a picture

Then I could easily draw/calculate an imaginary rectangle/square around every shape and calculate the middle of it like that: Shapes in a picture with rectangles/squares around them

After I have the rectangles/squares. I can easily calculate the middle. How do I start?

PS.: I've drawn some circles in mspaint. I have to add that all shapes are CLOSED, which makes it possible to flood fill EVERY shape in the picture with no problems!

Thank you for your help.

1
delphiimage-processingpixelpixelsshapes
What you want to find is called centroid. You don't need to a bounding rectangle to calculate it, only the points belonging to the exterior of the object. I notice some of your hand-drawn objects are not closed, is that intentional (based on your final comment it was purely coincidence -- they are all closed actually) ? – mmgp
After you flood fill your objects, you can keep only the borders and calculate the centroid of each shape. I've put such code at stackoverflow.com/questions/14263050/… which doesn't depend on any library for these tasks, I believe you won't have much trouble converting Python to Pascal-like language. If there is any doubt regarding that code, feel free to ask. – mmgp
I think that is not clear that you wish the centroid and not the center of the shapes. Because you was trying to bound them in rectangles. Also, second image in second row is not circular/ellipse. You need to find the centroid of that shape too? – EMBarbosa
@BenjaminWeiss there is some confusion over there, because the link you mentioned is about flood fill. It doesn't matter if you actually fill each pixel or not; you are performing the same operations as flood fill, except that, as you say, no pixel is filled. But if actually flood fill, in the sense of eliminating interior holes, each component, the task gets easier. – mmgp
@BenjaminWeiss in the code right below the comment "# Keep only border points" it does what you are saying (I think). It goes scanning every pixel in the image, if it finds a background pixel (assumed to be 255 there) then nothing is done. On the other hand, if we find a black pixel, we look around the four neighbors. If one of these neighbors is a white pixel, then this black pixel is on the border and we keep it black, otherwise we set it to white. This has to be done in an auxiliary image, it wouldn't work for inplace modifications. – mmgp

1 Answers

0
votes

Calculate MSER (Maximally stable extremal regions) for the image. I can't explain that algorithm here. You can refer to the Maximally stable extremal regions article for more information about the algorithm.

That will give you centroid too.

This algorithm is implemented as inbuilt functions in OpenCv tool and Matlab 2012b.

Another method which i can think of and possibly simple than previous method is to apply connected components algorithm and count number of objects.More information of this can be found in book by Gonzalez and Woods on Digital Image Processing.