Search code examples
matlabimage-processingcomputer-visioncomputer-sciencehough-transform

Finding the centers of overlapping circles in a low resolution grayscale image

I am currently taking my first steps in the field of computer vision and image processing.

One of the tasks I'm working on is finding the center coordinates of (overlapping and occluded) circles.

Here is a sample image:

enter image description here

Here is another sample image showing two overlapping circles:

Sample image

Further information about the problem:

  • Always a monochrome, grayscale image
  • Rather low resolution images
  • Radii of the circles are unknown
  • Number of circles in a given image is unknown
  • Center of circle is to be determined, preferably with sub-pixel accuracy
  • Radii do not have to be determined
  • Relative low overhead of the algorithm is of importance; the processing is supposed to be carried out with real-time camera images

For the first sample image, it is relatively easy to calculate the center of the circle by finding the center of mass. Unfortunately, this is not going to work for the second image.

Things I tried are mainly based on the Circle Hough Transform and the Distance Transform.

The Circle Hough Transform seemed relatively computationally expensive due to the fact that I have no information about the radii and the range of possible radii is large. Furthermore, it seems hard to identify the (appropriate) pixels along the edge because of the low resolution of the image.

As for the Distance Transform, I have trouble identifying the centers of the circles and the fact that the image needs to be binarized implies a certain loss of information.

Now I am looking for viable alternatives to the aforementioned algorithms.

Some more sample images (images like the two samples above are extracted from images like the following):

Full sample 1 Full sample 2

Solution

  • Just thinking aloud to try and get the ball rolling for you... I would be thinking of a Blob, or Connected Component analysis to separate out your blobs.

    enter image description here

    Then I would start looking at each blob individually. First thing is to see how square the bounding box is for each blob. If it is pretty square AND the centroid of the blob is central within the square, then you have a single circle. If it is not square, or the centroid is not central, you have more than one circle.

    enter image description here

    Now I am going to start looking at where the white areas touch the edges of the bounding box for some clues as to where the centres are...