Circular Hough Transform Improvements

Question

I'm working on an iris recognition algorithm that processes these kind of images into unique codes for identification and authentication purposes.

After filtering, intelligently thresholding, then finding edges in the image, the next step is obviously to fit circles to the pupil and iris. I've looked around the the technique to use is the circular Hough Transform. Here is the code for my implementation. Sorry about the cryptic variable names.

print "Populating Accumulator..."
# Loop over image rows
for x in range(w):
    # Loop over image columns
    for y in range(h):
        # Only process black pixels
        if inp[x,y] == 0:
            # px,py = 0 means pupil, otherwise pupil center
            if px == 0:
                ra = r_min
                rb = r_max
            else:
                rr = sqrt((px-x)*(px-x)+(py-y)*(py-y))
                ra = int(rr-3)
                rb = int(rr+3)
            # a is the width of the image, b is the height
            for _a in range(a):
                for _b in range(b):
                    for _r in range(rb-ra):
                        s1 = x - (_a + a_min)
                        s2 = y - (_b + b_min)
                        r1 = _r + ra
                        if (s1 * s1 + s2 * s2 == r1 * r1):
                            new = acc[_a][_b][_r]
                            if new >= maxVotes:
                                maxVotes = new
print "Done"

# Average all circles with the most votes
for _a in range(a):
    for _b in range(b):
        for _r in range(r):
            if acc[_a][_b][_r] >= maxVotes-1:
                total_a += _a + a_min
                total_b += _b + b_min
                total_r += _r + r_min
                amount += 1
top_a = total_a / amount
top_b = total_b / amount
top_r = total_r / amount
print top_a,top_b,top_r

This is written in python and uses the Python Imaging Library to do image processing. As you can see, this is a very naive brute force method of finding circles. It works, but takes several minutes. The basic idea is to draw circles from rmin to rmax wherever there is a black pixel (from thresholding and edge-detection), the build an accumulator array of the number of times a location on the image is "voted" on. Whichever x, y, and r has the most votes is the circle of interest. I tried to use the fact that the iris and pupil have about the same center (variables ra and rb) to reduce some of the complexity of the r loop, but the pupil detection takes so long that it doesn't matter.

Now, obviously my implementation is very naive. It uses a three dimensional parameter space (x, y, and r), which unfortunately makes it run slower than is acceptable. What kind of improvements can I make? Is there any way to reduce this to a two-dimensional parameter space? Is there a more efficient way of accessing and setting pixels that I'm not aware of?

On a side note, are there any other techniques for improving the overall runtime of this algorithm that I'm not aware of? Such as methods to approximate the maximum radius of the pupil or iris?

Note: I've tried to use OpenCV for this as well, but I could not tune the parameters enough to be consistently accurate.

Let me know if there's any other information that you need.

NOTE: Once again I misinterpreted my own code. It is technically 5-dimensional, but the 3-dimensional x,y,r loop only operates on black pixels.

Answer 1

Assuming you want the position of the circle rather than a measure of R.

If you have a decent estimate of the possible range of R then a common technique is to run the algorithm for a first guess of fixed R, adjust it and try again.