Search code examples
delphiimage-processingpixelshapes

Detecting multiple shapes in a picture and calculate the middle

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.

Solution

  • 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.