Ask Your Question

Writting robust (size invariant) circle detection (Watershed)

asked 2018-09-13 06:39:31 -0500

christian gravatar image

updated 2018-09-19 11:54:33 -0500

I want to detect circles with different sizes. The use case is to detect coins on an image and to extract them solely. Quick Summary so far: I use the watershed algorithm but I have probably a problem with threshold. It didn't detect the brighter circles.

It's probably not ideal but I already have described it in a stackoverflow thread and I would be really happy if I could get any more advices:

I used this watershed algorithm:

Edit: Example image of my problem. image description

Edit 2:I tried the radial symmetry transform by kbarni. I used [this] ( implementation but unfortunately I only get a just black output. I have already tried to modify every parameter but it didn't help.

Implementation of fast radial symmetry transform in pure Python using OpenCV and numpy.

Adapted from:

Which is itself adapted from:
Loy, G., & Zelinsky, A. (2002). A fast radial symmetry transform for detecting points of interest. Computer         
Vision, ECCV 2002.

import cv2
import numpy as np

def gradx(img):
    img = img.astype('int')
    rows, cols = img.shape
    # Use hstack to add back in the columns that were dropped as zeros
    return np.hstack((np.zeros((rows, 1)), (img[:, 2:] - img[:, :-2]) / 2.0, np.zeros((rows, 1))))

def grady(img):
    img = img.astype('int')
    rows, cols = img.shape
    # Use vstack to add back the rows that were dropped as zeros
    return np.vstack((np.zeros((1, cols)), (img[2:, :] - img[:-2, :]) / 2.0, np.zeros((1, cols))))

# Performs fast radial symmetry transform
# img: input image, grayscale
# radii: integer value for radius size in pixels (n in the original paper); also used to size gaussian kernel
# alpha: Strictness of symmetry transform (higher=more strict; 2 is good place to start)
# beta: gradient threshold parameter, float in [0,1]
# stdFactor: Standard deviation factor for gaussian kernel
# mode: BRIGHT, DARK, or BOTH
def frst(img, radii, alpha, beta, stdFactor, mode='BOTH'):
    mode = mode.upper()
    assert mode in ['BRIGHT', 'DARK', 'BOTH']
    dark = (mode == 'DARK' or mode == 'BOTH')
    bright = (mode == 'BRIGHT' or mode == 'BOTH')

    workingDims = tuple((e + 2 * radii) for e in img.shape)

    # Set up output and M and O working matrices
    output = np.zeros(img.shape, np.uint8)
    O_n = np.zeros(workingDims, np.int16)
    M_n = np.zeros(workingDims, np.int16)

    # Calculate gradients
    gx = gradx(img)
    gy = grady(img)

    # Find gradient vector magnitude
    gnorms = np.sqrt(np.add(np.multiply(gx, gx), np.multiply(gy, gy)))

    # Use beta to set threshold - speeds up transform significantly
    gthresh = np.amax(gnorms) * beta

    # Find x/y distance to affected pixels
    gpx = np.multiply(np.divide(gx, gnorms, out=np.zeros(gx.shape), where=gnorms != 0),         
    gpy = np.multiply(np.divide(gy, gnorms, out=np.zeros(gy.shape), where=gnorms != 0),     

    # Iterate over all pixels (w/ gradient above threshold)
    for coords, gnorm in np ...
edit retag flag offensive close merge delete


Use the Circular Hough transform on the gradient magnitude image.

(...and generally, an example image you are using would be helpful)

kbarni gravatar imagekbarni ( 2018-09-13 10:49:59 -0500 )edit

Thank you for your advice. I already tried Hough Transform but it is to size sensitive as I would have to change the parameters for every image (which is not possible, the coins are photographed from different heights). Or is it something different on the gradient magnitude image?

christian gravatar imagechristian ( 2018-09-13 11:05:11 -0500 )edit

There are two parameters for the min/max radius. You can define them so it detects the very small/very large coins. Otherwise use the symmetrical transform (I will write an answer on that below).

kbarni gravatar imagekbarni ( 2018-09-14 03:15:43 -0500 )edit

What I proposed was a slightly modified version of the Radial Symmetry Transform; try to follow the algorithm I described.

In the code, use just the if bright: part; and instead of changing only O_n[ppve] += 1, increment every pixel between coord and ppve (draw a line).

The ppve has to be computed a bit differently; so that the distance between coord and ppve is constant D (60 pixels should work in the example image).

kbarni gravatar imagekbarni ( 2018-09-17 05:27:22 -0500 )edit

I didn't get it right to follow and implement your algorithm :( I'm very new to python and have some problems.

Maybe you could tell me how I can draw a line with a constant?

I tried this changes but it din't work (I added an image in the question)

# Iterate over all pixels (w/ gradient above threshold) for coords, gnorm in np.ndenumerate(gnorms): if gnorm > gthresh: i, j = coords # Positively affected pixel ppve = (i + gpx[i, j], j + gpy[i, j]) O_n[ppve] += 1 M_n[ppve] += gnorm output = cv2.line(output, coords, ppve, (255, 255, 255), 1)

christian gravatar imagechristian ( 2018-09-17 16:36:30 -0500 )edit

Don't use cv2.line, rather a lineiterator. As I see, it's not a part of the Python API, but here is a solution:

I suggest to learn a bit Python and OpenCV, then try to implement the algorithm I described in the answer yourself, instead of trying to find the solution online, and then try to make some modifications.

kbarni gravatar imagekbarni ( 2018-09-18 05:07:56 -0500 )edit

I tried your apporach again and the results are in my questions. Your suggestion is absolutely right and I want to learn that. But, I'm really under a lot of (time) pressure to get this done :( It's probably not how it this forum is supposed to be, but: Could you may share your code with me, please? I have to get this right :/

christian gravatar imagechristian ( 2018-09-18 16:55:03 -0500 )edit

I added my code, it's C++; but it shouldn't be hard to rewrite it in Python (but you still need to know Python)...

...and you still need to write your algorithm for local maximum detection.

kbarni gravatar imagekbarni ( 2018-09-19 04:41:26 -0500 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2018-09-14 03:23:43 -0500

kbarni gravatar image

updated 2018-09-19 04:39:52 -0500

To quickly detect circles with very large diameter variation, you can use the radial symmetry transform (as they are radially symmetric) (Loy&Zelinsky 2002). This is a very robust and proven algorithm for circular object detection for any radius. It's not part of OpenCV, but it's easy to implement.

The algorithm is the following:

  • define an accumulator image (same size as the original)
  • detect the gradients in the image (magnitude/angle).
  • For every point where the gradient magnitude is over a certain threshold, draw a line in the gradient direction in the accumulator image (in fact, as it's an accumulator, you have to increment by 1 the value of the pixels along the line). The length of the line should be equal to the maximum radius you want to detect.
  • Detect the local maxima in the accumulator image. They will indicate the center of the coins.

Here is the result of the radial symmetry transform (the accumulator space) for the image above and a detection length of 60 pixels. The center of all the coins is clearly visible, for any radius.

image description

Here is the C++ code for the proposed algorithm. It takes the X and Y gradients and the detection radius (ray). minval and maxval are low and high thresholds for the gradient.

void RadSymTransform(InputArray gradx,InputArray grady,OutputArray result,int ray,double minval=0,double maxval=255)
Mat gxMat=gradx.getMat();
Mat gyMat=grady.getMat();
result.create(gradx.size(), CV_16UC1);
Mat resMat=result.getMat();
resMat=Mat::zeros(resMat.size(), resMat.type());
int x,y,i,H,W;
double tx,ty,gx,gy,ampl,max;
    for (x = 0; x < W; x++)
            for (i = 0; i < ray; ++i)
edit flag offensive delete link more


Thank you for your help! I tried this implementation: but only get a just black output. Do you have any idea why? (I also edited my question with the version I use)

christian gravatar imagechristian ( 2018-09-16 16:40:11 -0500 )edit

Thank you very much!

Can I use gradx and grady from above as Input here?

christian gravatar imagechristian ( 2018-09-19 09:19:33 -0500 )edit

Just do a Sobel operation. I have no idea what does the python code.

kbarni gravatar imagekbarni ( 2018-09-19 10:24:53 -0500 )edit

I just get a complete white image. Maybe you have experienced something similar or have any idea what could cause that?

(The "if tx < width and ty < height:" is because I had out of bound errors (in the width) before)

christian gravatar imagechristian ( 2018-09-19 11:55:33 -0500 )edit

You have to debug the code.

Maybe you have to normalize the image and also set the minval to a higher value.

kbarni gravatar imagekbarni ( 2018-09-19 14:49:34 -0500 )edit
Login/Signup to Answer

Question Tools

1 follower


Asked: 2018-09-13 06:38:31 -0500

Seen: 587 times

Last updated: Sep 19 '18