writing robust (color and size invariant) circle d

Question

I wrote the following very simple python code to find circles in an image:

import cv
import numpy as np

WAITKEY_DELAY_MS = 10
STOP_KEY = 'q'

cv.NamedWindow("image - press 'q' to quit", cv.CV_WINDOW_AUTOSIZE);
cv.NamedWindow("post-process", cv.CV_WINDOW_AUTOSIZE);

key_pressed = False
while key_pressed != STOP_KEY:

    # grab image
    orig = cv.LoadImage('circles3.jpg')

    # create tmp images
    grey_scale = cv.CreateImage(cv.GetSize(orig), 8, 1)
    processed = cv.CreateImage(cv.GetSize(orig), 8, 1)


    cv.Smooth(orig, orig, cv.CV_GAUSSIAN, 3, 3)

    cv.CvtColor(orig, grey_scale, cv.CV_RGB2GRAY)

    # do some processing on the grey scale image
    cv.Erode(grey_scale, processed, None, 10)
    cv.Dilate(processed, processed, None, 10)
    cv.Canny(processed, processed, 5, 70, 3)
    cv.Smooth(processed, processed, cv.CV_GAUSSIAN, 15, 15)

    storage = cv.CreateMat(orig.width, 1, cv.CV_32FC3)

    # these parameters need to be adjusted for every single image
    HIGH = 50
    LOW = 140

    try: 
        # extract circles
        cv.HoughCircles(processed, storage, cv.CV_HOUGH_GRADIENT, 2, 32.0, HIGH, LOW)

        for i in range(0, len(np.asarray(storage))):
            print "circle #%d" %i
            Radius = int(np.asarray(storage)[i][0][2])
            x = int(np.asarray(storage)[i][0][0])
            y = int(np.asarray(storage)[i][0][1])
            center = (x, y)

            # green dot on center and red circle around
            cv.Circle(orig, center, 1, cv.CV_RGB(0, 255, 0), -1, 8, 0)
            cv.Circle(orig, center, Radius, cv.CV_RGB(255, 0, 0), 3, 8, 0)

            cv.Circle(processed, center, 1, cv.CV_RGB(0, 255, 0), -1, 8, 0)
            cv.Circle(processed, center, Radius, cv.CV_RGB(255, 0, 0), 3, 8, 0)

    except:
        print "nothing found"
        pass

    # show images
    cv.ShowImage("image - press 'q' to quit", orig)
    cv.ShowImage("post-process", processed)

    cv_key = cv.WaitKey(WAITKEY_DELAY_MS)
    key_pressed = chr(cv_key & 255)

As you can see from the following two examples, the 'circle finding quality' varies quite a lot:

CASE1:

CASE2:

Case1 and Case2 are basically the same image, but still the algorithm detects different circles. If I present the algorithm an image with differently sized circles, the circle detection might even fail completely. This is mostly due to the HIGH and LOW parameters which need to be adjusted individually for each new picture.

Therefore my question: what are the various possibilities of making this algorithm more robust? It should be size and color invariant so that different circles with different colors and in different sizes are detected. Maybe using the Hough transform is not the best way of doing things? Are there better approaches?

Answer 1

This is a great modelling problem. I have the following recommendations/ ideas:

1. Split the image to RGB then process.
2. pre-processing.
3. Dynamic parameter search.
4. Add constraints.
5. Be sure about what you are trying to detect.

In more detail:

1: As noted in other answers, converting straight to grayscale discards too much information - any circles with a similar brightness to the background will be lost. Much better to consider the colour channels either in isolation or in a different colour space. There are pretty much two ways to go here: perform HoughCircles on each pre-processed channel in isolation, then combine results, or, process the channels, then combine them, then operate HoughCircles. In my attempt below, I've tried the second method, splitting to RGB channels, processing, then combining. Be wary of over saturating the image when combining, I use cv.And to avoid this issue (at this stage my circles are always black rings/discs on white background).

2: Pre-processing is quite tricky, and something its often best to play around with. I've made use of AdaptiveThreshold which is a really powerful convolution method that can enhance edges in an image by thresholding pixels based on their local average (similar processes also occur in the early pathway of the mammalian visual system). This is also useful as it reduces some noise. I've used dilate/erode with only one pass. And I've kept the other parameters how you had them. It seems using Canny before HoughCircles does help a lot with finding 'filled circles', so probably best to keep it in. This pre-processing is quite heavy and can lead to false positives with somewhat more 'blobby circles', but in our case this is perhaps desirable?

3: As you've noted HoughCircles parameter param2 (your parameter LOW) needs to be adjusted for each image in order to get an optimal solution, in fact from the docs:

The smaller it is, the more false circles may be detected.

Trouble is the sweet spot is going to be different for every image. I think the best approach here is to make set a condition and do a search through different param2 values until this condition is met. Your images show non-overlapping circles, and when param2 is too low we typically get loads of overlapping circles. So I suggest searching for the:

maximum number of non-overlapping, and non-contained circles

So we keep calling HoughCircles with different values of param2 until this is met. I do this in my example below, just by incrementing param2 until it reaches the threshold assumption. It would be way faster (and fairly easy to do) if you perform a binary search to find when this is met, but you need to be careful with exception handling as opencv often throws a errors for innocent looking values of param2 (at least on my installation). A different condition that would we very useful to match against would be the number of circles.

4: Are there any more constraints we can add to the model? The more stuff we can tell our model the easy a task we can make it to detect circles. For example, do we know:

• The number of circles. - even an upper or lower bound is helpful.
• Possible colours of the circles, or of the background, or of 'non-circles'.
• Their sizes.
• Where they can be in an image.

5: Some of the blobs in your images could only loosely be called circles! Consider the two 'non-circular blobs' in your second image, my code can't find them (good!), but... if I 'photoshop' them so they are more circular, my code can find them... Maybe if you want to detect things that are not circles, a different approach such as Tim Lukins may be better.

Problems

By doing heavy pre-processing AdaptiveThresholding and `Canny' there can be a lot of distortion to features in an image, which may lead to false circle detection, or incorrect radius reporting. For example a large solid disc after processing can appear a ring, so HughesCircles may find the inner ring. Furthermore even the docs note that:

...usually the function detects the circles’ centers well, however it may fail to find the correct radii.

If you need more accurate radii detection, I suggest the following approach (not implemented):

• On the original image, ray-trace from reported centre of circle, in an expanding cross (4 rays: up/down/left/right)
• Do this seperately in each RGB channel
• Combine this info for each channel for each ray in a sensible fashion (ie. flip, offset, scale, etc as necessary)
• take the average for the first few pixels on each ray, use this to detect where a significant deviation on the ray occurs.
• These 4 points are estimates of points on the circumference.
• Use these four estimates to determine a more accurate radius, and centre position(!).
• This could be generalised by using an expanding ring instead of four rays.

Results

The code at end does pretty good quite a lot of the time, these examples were done with code as shown:

Detects all circles in your first image:

How the pre-processed image looks before canny filter is applied (different colour circles are highly visible):

Detects all but two (blobs) in second image:

Altered second image (blobs are circle-afied, and large oval made more circular, thus improving detection), all detected:

Does pretty well in detecting centres in this Kandinsky painting (I cannot find concentric rings due to he boundary condition).

Code:

import cv
import numpy as np

output = cv.LoadImage('case1.jpg')
orig = cv.LoadImage('case1.jpg')

# create tmp images
rrr=cv.CreateImage((orig.width,orig.height), cv.IPL_DEPTH_8U, 1)
ggg=cv.CreateImage((orig.width,orig.height), cv.IPL_DEPTH_8U, 1)
bbb=cv.CreateImage((orig.width,orig.height), cv.IPL_DEPTH_8U, 1)
processed = cv.CreateImage((orig.width,orig.height), cv.IPL_DEPTH_8U, 1)
storage = cv.CreateMat(orig.width, 1, cv.CV_32FC3)

def channel_processing(channel):
    pass
    cv.AdaptiveThreshold(channel, channel, 255, adaptive_method=cv.CV_ADAPTIVE_THRESH_MEAN_C, thresholdType=cv.CV_THRESH_BINARY, blockSize=55, param1=7)
    #mop up the dirt
    cv.Dilate(channel, channel, None, 1)
    cv.Erode(channel, channel, None, 1)

def inter_centre_distance(x1,y1,x2,y2):
    return ((x1-x2)**2 + (y1-y2)**2)**0.5

def colliding_circles(circles):
    for index1, circle1 in enumerate(circles):
        for circle2 in circles[index1+1:]:
            x1, y1, Radius1 = circle1[0]
            x2, y2, Radius2 = circle2[0]
            #collision or containment:
            if inter_centre_distance(x1,y1,x2,y2) < Radius1 + Radius2:
                return True

def find_circles(processed, storage, LOW):
    try:
        cv.HoughCircles(processed, storage, cv.CV_HOUGH_GRADIENT, 2, 32.0, 30, LOW)#, 0, 100) great to add circle constraint sizes.
    except:
        LOW += 1
        print 'try'
        find_circles(processed, storage, LOW)
    circles = np.asarray(storage)
    print 'number of circles:', len(circles)
    if colliding_circles(circles):
        LOW += 1
        storage = find_circles(processed, storage, LOW)
    print 'c', LOW
    return storage

def draw_circles(storage, output):
    circles = np.asarray(storage)
    print len(circles), 'circles found'
    for circle in circles:
        Radius, x, y = int(circle[0][2]), int(circle[0][0]), int(circle[0][1])
        cv.Circle(output, (x, y), 1, cv.CV_RGB(0, 255, 0), -1, 8, 0)
        cv.Circle(output, (x, y), Radius, cv.CV_RGB(255, 0, 0), 3, 8, 0)

#split image into RGB components
cv.Split(orig,rrr,ggg,bbb,None)
#process each component
channel_processing(rrr)
channel_processing(ggg)
channel_processing(bbb)
#combine images using logical 'And' to avoid saturation
cv.And(rrr, ggg, rrr)
cv.And(rrr, bbb, processed)
cv.ShowImage('before canny', processed)
# cv.SaveImage('case3_processed.jpg',processed)
#use canny, as HoughCircles seems to prefer ring like circles to filled ones.
cv.Canny(processed, processed, 5, 70, 3)
#smooth to reduce noise a bit more
cv.Smooth(processed, processed, cv.CV_GAUSSIAN, 7, 7)
cv.ShowImage('processed', processed)
#find circles, with parameter search
storage = find_circles(processed, storage, 100)
draw_circles(storage, output)
# show images
cv.ShowImage("original with circles", output)
cv.SaveImage('case1.jpg',output)

cv.WaitKey(0)

Answer 2

Looking through your code, I noticed the following:

• Greyscale conversion. I understand why you're doing it, but realize that you're throwing away information there. As you see in the "post-process" images, your yellow circles are the same intensity as the background, just in a different color.

• Edge detection after noise removal (erae/dilate). This shouldn't be necessary; Canny ought to take care of this.

• Canny edge detection. Your "open" circles have two edges, an inner and outer edge. Since they're fairly close, the Canny gauss filter might add them together. If it doesn't, you'll have two edges close together. I.e. before Canny, you have open and filled circles. Afterwards, you have 0/2 and 1 edge, respectively. Since Hough calls Canny again, in the first case the two edges might be smoothed together (depending on the initial width), which is why the core Hough algorithm can treat open and filled circles the same.

So, my first recommendation would be to change the grayscale mapping. Don't use intensity, but use hue/saturation/value. Also, use a differential approach - you're looking for edges. So, compute a HSV transform, smooth a copy, and then take the difference between the original and smoothed copy. This will get you dH, dS, dV values (local variation in Hue, Saturation, Value) for each point. Square and add to get a one-dimensional image, with peaks near all edges (inner and outer).

My second recommendation would be local normalization, but I'm not sure if that's even necessary. The idea is that you don't care particularly much about the exact value of the edge signal you got out, it should really be binary anyway (edge or not). Therefore, you can normalize each value by dividing by a local average (where local is in the order of magnitude of your edge size).

Answer 3

The Hough transform uses a "model" to find certain features in a (typically) edge-detected image, as you may know. In the case of HoughCircles that model is a perfect circle. This means there probably doesn't exist a combination of parameters that will make it detect the more erratically and ellipse shaped circles in your picture without increasing the number of false positives. On the other hand, due to the underlying voting mechanism, a non-closed perfect circle or a perfect circle with a "dent" might consistently show up. So depending on your expected output you may or may not want to use this method.

That said, there are a few things I see which might help you on your way with this function:

1. HoughCircles calls Canny internally, so I guess you can leave that call out.
2. param1 (which you call HIGH) is typically initialised around a value of 200. It is used as a parameter to the internal call to Canny: cv.Canny(processed, cannied, HIGH, HIGH/2). It might help to run Canny yourself like this to see how setting HIGH affects the image being worked with by the Hough transform.
3. param2 (which you call LOW) is typically initialised around a value 100. It is the voting threshold for the Hough transform's accumulators. Setting it higher means more false negatives, lower more false positives. I believe this is the first one you want to start fiddling around with.

Ref: http://docs.opencv.org/3.0-beta/modules/imgproc/doc/feature_detection.html#houghcircles

Update re: filled circles: After you've found the circle shapes with the Hough transform you can test if they are filled by sampling the boundary colour and comparing it to one or more points inside the supposed circle. Alternatively you can compare one or more points inside the supposed circle to a given background colour. The circle is filled if the former comparison succeeds, or in the case of the alternative comparison if it fails.

Answer 4

The following is based on my experience as a vision researcher. From your question you seem to be interested in possible algorithms and methods rather only a working piece of code. First I give a quick and dirty Python script for your sample images and some results are shown to prove it could possibly solve your problem. After getting these out of the way, I try to answer your questions regarding robust detection algorithms.

Quick Results

Some sample images (all the images apart from yours are downloaded from flickr.com and are CC licensed) with the detected circles (without changing/tuning any parameters, exactly the following code is used to extract the circles in all the images):

Code (based on the MSER Blob Detector)

And here is the code:

import cv2
import math
import numpy as np

d_red = cv2.cv.RGB(150, 55, 65)
l_red = cv2.cv.RGB(250, 200, 200)

orig = cv2.imread("c.jpg")
img = orig.copy()
img2 = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

detector = cv2.FeatureDetector_create('MSER')
fs = detector.detect(img2)
fs.sort(key = lambda x: -x.size)

def supress(x):
        for f in fs:
                distx = f.pt[0] - x.pt[0]
                disty = f.pt[1] - x.pt[1]
                dist = math.sqrt(distx*distx + disty*disty)
                if (f.size > x.size) and (dist<f.size/2):
                        return True

sfs = [x for x in fs if not supress(x)]

for f in sfs:
        cv2.circle(img, (int(f.pt[0]), int(f.pt[1])), int(f.size/2), d_red, 2, cv2.CV_AA)
        cv2.circle(img, (int(f.pt[0]), int(f.pt[1])), int(f.size/2), l_red, 1, cv2.CV_AA)

h, w = orig.shape[:2]
vis = np.zeros((h, w*2+5), np.uint8)
vis = cv2.cvtColor(vis, cv2.COLOR_GRAY2BGR)
vis[:h, :w] = orig
vis[:h, w+5:w*2+5] = img

cv2.imshow("image", vis)
cv2.imwrite("c_o.jpg", vis)
cv2.waitKey()
cv2.destroyAllWindows()

As you can see it's based on the MSER blob detector. The code doesn't preprocess the image apart from the simple mapping into grayscale. Thus missing those faint yellow blobs in your images is expected.

Theory

In short: you don't tell us what you know about the problem apart from giving only two sample images with no description of them. Here I explain why I in my humble opinion it is important to have more information about the problem before asking what are efficient methods to attack the problem.

Back to the main question: what is the best method for this problem? Let's look at this as a search problem. To simplify the discussion assume we are looking for circles with a given size/radius. Thus, the problem boils down to finding the centers. Every pixel is a candidate center, therefore, the search space contains all the pixels.

P = {p1, ..., pn} 
P: search space
p1...pn: pixels

To solve this search problem two other functions should be defined:

E(P) : enumerates the search space
V(p) : checks whether the item/pixel has the desirable properties, the items passing the check are added to the output list

Assuming the complexity of the algorithm doesn't matter, the exhaustive or brute-force search can be used in which E takes every pixel and passes to V. In real-time applications it's important to reduce the search space and optimize computational efficiency of V.

We are getting closer to the main question. How we could define V, to be more precise what properties of the candidates should be measures and how should make solve the dichotomy problem of splitting them into desirable and undesirable. The most common approach is to find some properties which can be used to define simple decision rules based on the measurement of the properties. This is what you're doing by trial and error. You're programming a classifier by learning from positive and negative examples. This is because the methods you're using have no idea what you want to do. You have to adjust / tune the parameters of the decision rule and/or preprocess the data such that the variation in the properties (of the desirable candidates) used by the method for the dichotomy problem are reduced. You could use a machine learning algorithm to find the optimal parameter values for a given set of examples. There's a whole host of learning algorithms from decision trees to genetic programming you can use for this problem. You could also use a learning algorithm to find the optimal parameter values for several circle detection algorithms and see which one gives a better accuracy. This takes the main burden on the learning algorithm you just need to collect sample images.

The other approach to improve robustness which is often overlooked is to utilize extra readily available information. If you know the color of the circles with virtually zero extra effort you could improve the accuracy of the detector significantly. If you knew the position of the circles on the plane and you wanted to detect the imaged circles, you should remember the transformation between these two sets of positions is described by a 2D homography. And the homography can be estimated using only four points. Then you could improve the robustness to have a rock solid method. The value of domain-specific knowledge is often underestimated. Look at it this way, in the first approach we try to approximate some decision rules based on a limited number of sample. In the second approach we know the decision rules and only need to find a way to effectively utilize them in an algorithm.

Summary

To summarize, there are two approaches to improve the accuracy / robustness of the solution:

1. Tool-based: finding an easier to use algorithm / with fewer number of parameters / tweaking the algorithm / automating this process by using machine learning algorithms
2. Information-based: are you using all the readily available information? In the question you don't mention what you know about the problem.

For these two images you have shared I would use a blob detector not the HT method. For background subtraction I would suggest to try to estimate the color of the background as in the two images it is not varying while the color of the circles vary. And the most of the area is bare.

Answer 5

Ah, yes… the old colour/size invariants for circles problem (AKA the Hough transform is too specific and not robust)...

In the past I have relied much more on the structural and shape analysis functions of OpenCV instead. You can get a very good idea of from "samples" folder of what is possible - particularly fitellipse.py and squares.py.

For your elucidation, I present a hybrid version of these examples and based on your original source. The contours detected are in green and the fitted ellipses in red.

It's not quite there yet:

• The pre-processing steps need a bit of tweaking to detect the more faint circles.
• You could test the contour further to determine if it is a circle or not...

Good luck!

import cv
import numpy as np

# grab image
orig = cv.LoadImage('circles3.jpg')

# create tmp images
grey_scale = cv.CreateImage(cv.GetSize(orig), 8, 1)
processed = cv.CreateImage(cv.GetSize(orig), 8, 1)

cv.Smooth(orig, orig, cv.CV_GAUSSIAN, 3, 3)

cv.CvtColor(orig, grey_scale, cv.CV_RGB2GRAY)

# do some processing on the grey scale image
cv.Erode(grey_scale, processed, None, 10)
cv.Dilate(processed, processed, None, 10)
cv.Canny(processed, processed, 5, 70, 3)
cv.Smooth(processed, processed, cv.CV_GAUSSIAN, 15, 15)

#storage = cv.CreateMat(orig.width, 1, cv.CV_32FC3)
storage = cv.CreateMemStorage(0)

contours = cv.FindContours(processed, storage, cv.CV_RETR_EXTERNAL)
# N.B. 'processed' image is modified by this!

#contours = cv.ApproxPoly (contours, storage, cv.CV_POLY_APPROX_DP, 3, 1) 
# If you wanted to reduce the number of points...

cv.DrawContours (orig, contours, cv.RGB(0,255,0), cv.RGB(255,0,0), 2, 3, cv.CV_AA, (0, 0)) 

def contour_iterator(contour):
  while contour:
    yield contour
    contour = contour.h_next()

for c in contour_iterator(contours):
  # Number of points must be more than or equal to 6 for cv.FitEllipse2
  if len(c) >= 6:
    # Copy the contour into an array of (x,y)s
    PointArray2D32f = cv.CreateMat(1, len(c), cv.CV_32FC2)

    for (i, (x, y)) in enumerate(c):
      PointArray2D32f[0, i] = (x, y)

    # Fits ellipse to current contour.
    (center, size, angle) = cv.FitEllipse2(PointArray2D32f)

    # Convert ellipse data from float to integer representation.
    center = (cv.Round(center[0]), cv.Round(center[1]))
    size = (cv.Round(size[0] * 0.5), cv.Round(size[1] * 0.5))

    # Draw ellipse
    cv.Ellipse(orig, center, size, angle, 0, 360, cv.RGB(255,0,0), 2,cv.CV_AA, 0)

# show images
cv.ShowImage("image - press 'q' to quit", orig)
#cv.ShowImage("post-process", processed)
cv.WaitKey(-1)

EDIT:

Just an update to say that I believe a major theme to all these answers is that there are a host of further assumptions and constraints that can be applied to what you seek to recognise as circular. My own answer makes no pretences at this - neither in the low-level pre-processing or the high-level geometric fitting. The fact that many of the circles are not really that round due to the way they are drawn or the non-affine/projective transforms of the image, and with the other properties in how they are rendered/captured (colour, noise, lighting, edge thickness) - all result in any number of possible candidate circles within just one image.

There are much more sophisticated techniques. But they will cost you. Personally I like @fraxel idea of using the addaptive threshold. That is fast, reliable and reasonably robust. You can then test further the final contours (e.g. use Hu moments) or fittings with a simple ratio test of the ellipse axis - e.g. if ((min(size)/max(size))>0.7).

As ever with Computer Vision there is the tension between pragmatism, principle, and parsomony. As I am fond of telling people who think that CV is easy, it is not - it is in fact famously an AI complete problem. The best you can often hope for outside of this is something that works most of the time.

Answer 6

Ok looking at the images. I suggest using **Active Contours**

• Active Contours The good thing about active contours is that they almost perfectly fit into the any given shape. Be it squares or triangle and in your case they are the perfect candidates.
• If you are able to extract the centre of the circles, that is great. Active contours always need a point to start from which they can either grow or shrink to fit. Not necessary that the centres are always aligned to the centre. A little offset will still be ok.
• And in your case, if you let the contours to grow from the centre outwards, they shall rest a the circle boundaries.
• Note that active contours that grow or shrink use balloon energy which means you can set the direction of contours, inwards or outwards.
• You would probably need to use the gradient image in grey scale. But still you can try in colour as well. If it works!
• And if you do not provide centres, throw in lots of active contours, make then grow/shrink. Contours that settle down are kept, unsettled ones are thrown away. This is a brute force approach. Will CPU intensive. But will require more careful work to make sure you leave correct contours and throw out the bad ones.

I hope this way you can solve the problem.