Fast circle drawing algorithm (Bresenham?) for Circular Hough Transform

[vekkuli]

I've been working on a Circular Hough Transform algorithm for circle detection and I'm interested in finding ways to make it a bit more efficient. On high level I'm implementing some producer/customer model queueing between data gathering and analysis/filtering but I think the circle drawing operation for the Hough accumulation could use some honing. This is where I would love some help from you, experienced LabVIEW programmers.

Earlier I was using simple trigonometry to draw pixels with certain angular resolution but I believe using a circle drawing algorithm like the Midpoint Circle Algorithm (Bresenham circle variation) is probably smarter in the end. The hidious abomination of a LabVIEW script that I created for it, though, isn't performing quite as rapidly as I hoped. I followed the C code written here: http://members.chello.at/~easyfilter/bresenham.html

You can find the VI attached. It takes in a pixel array of a binary image (0 and 255) with the edges and draws circles centered on each 255 pixel with the given radius. The "drawn" circles are simply a list of coordinates, the output array. Would anyone have any suggestions on how to improve this VI? Or maybe even some input to the whole Hough transform concept?

[ValkoA · Accepted solution]

Hi Vekkuli!

 I have but a few recommendations for this function. Mind you, this is just my take, there might be other, more beneficial solutions.

1. For calculating the pixel coordiates, you've used Formula Nodes. I think this is a bit of an overkill since it's only addition/subtraction, so you may just do that in LabVIEW.
2. When collecting coordinate values, try to avoid using shift registers and Build Array to add new elements in every iteration. Since arrays are dynamic datatypes, this causes the compiler to allocate a new, bigger memory, copy the whole array into it with the new elements, then deallocate the old memory. Doing this every iteration is quite a performance hog. A better approach would be to use indexing or concatenating tunnels.
3. Using indexing tunnels to collect data also has he added benefit of making the outer loop (the one iterating through all pixels) paralellizable, which could be a big increase in performance, assuming a multi-core PC.
4. You can get a potential speed increase by drawing octants instead of quadrants, creating 8 points in every iteration.

I also tried my hand at implementing this algorithm that creates a circle, here's the result:

Regarding the Hough transform, there are some examples of a LabVIEW implementation, made at the University of Texas. You'll find them here.

Hope this helps.

Kind regards:

Andrew Valko

NI Hungary

[vekkuli]

Thank you for your great response, Valkoa, much appreciated! For the concatenating tunnels you made me finally dig up those version 2012 installation discs. I implemented your suggestions and it seemed to help with the efficiency quite a bit. I suppose I should look into utilising the concatenating tunnels in other similar loops as well.

I used an octant technique earlier as well, but in that one I wasn't able to fix the duplicate pixels. Anyway, with the current solution I'm good for now.

Yes, the University of Texas SIVA Hough Transform material was my inspiration and template. That one was implemented for straight lines but I made one for circles. When I'm done I'm sure to be in contact with Prof. Al Bovik for their thoughts on publishing the circular one.

[ValkoA]

Dear Vekkuli,

thank you for the kind response. Best of luck with your application.

Kind regards:

Andrew Valko

NI Hungary

[vekkuli]

A little update:

In the end I sped up the calculation further by implementing a lookup table. Now the relative circle edge coordinates (according to Bresenham/Midpoint Circle algorithm) are precalculated for each radius and stored into a lookup table array. The "drawing" itself is then done by simply extracting the approriate list of coordinates corresponding to the radius from the table and placing those around the desired center points in the image array. In a 10 megapixel sample image of around 7 million various circles drawn the lookup table reduced the calculation time down to half (still totalling some 120 s including data filtering).

[DonRoth]

Have you thought about using the IMAQ Vision Function "IMAQ Find Circular Edge.vi?"  This VI outputs results that including drawing the circle.  I have had great success with this VI in my analysis of x-ray computed tomography data from cylindrical objects.   Or are you hoping to do this in straight LabVIEW?

[vekkuli]

Thank you for your input. I do have the Vision library at hand as well. However, I'm not exactly sure how you ment I could use the Find Circular Edge tool in my application. The "sur"routine in question is, indeed, related to locating circles (Circular Hough Transform) and in this topic I talk about the key subroutine of it where tons of circles are drawn at certain points in order to create a voting algorithm. Does the "IMAQ Find Circular Edge.vi" provide an efficient way to achieve this? At first, at least, it seems like a major overkill. I don't have the debugging license, though, so I can't see what's underneath.

[DonRoth]

It may not be applicable in your particular situation but I wanted to make you aware of it.  I read over your initial post again to try to understand what you are doing (draw circles around a pixel location for pixel gray value = 255).  In your case, the specific Vision VI that might be able to help you is "IMAQ Convert Annulus to ROI."  For this function, it requires that you input center coordinates, and inner and outer radius. Once you would detect the pixel, its coordinates would be the center of the circle, and the inner radius and outer radius input requirements would be satisfied by you setting them both equal to your defined radius. You feed the output of this VI into an 'ROI' property node for the Vision Container.  If you do not clear the ROI using an Invoke Node for the Vision container, I think you will be able to accumulate as many ROIs (circles) on your image as you like.

[vekkuli]

That sounds more like what I'm doing here. If the drawing wasn't such a repetative routine in the application, using high level tools, such as you suggested, would be a pretty easy way to take care of the drawing. Although, it would still require tracing the resulting ROI contours and merging/masking into an image. I appreciate your ideas but I find it hard to see how the high level functions would be more beneficial in this scenario.

If you're interested, I have attached a sample image where you can try out the ideas in context yourself. The task is to draw circles of radii 5,6,7,...,58,59,60, on every non-zero pixel in the image. If I checked right this should results in approximately 7 million circles. The drawing is done one radius at a time and by creating a grayscale image where each circle adds one to the intensity value on it's edge. Oh wow what an explanation... I hope it made some sense.

Anyway, no sweat! The solution I'm running now is actually satisfactory.

[DonRoth]

Well the IMAQ Vision functionality could be placed in a loop where you are searching for the non-zero pixesl, and the draws in Vision are pretty fast I expect.  It would be really interesting to perform the speed comparison.  Many ways to skin the cat but I know you are looking for the most efficient algorithm.

Great work on both your parts.