I tried to write my own version of Hough Transform for circles.
Even after a few cycles of optimization I could not get close the performance of OpenCV.
The code can be found here:
My CPU is an Intel 8 core i7-3770 CUP @ 3.4GHz My Display Adapter is an Intel HD Graphics 4000
How do they manage to get good results so fast?
I think you are wrong. As far as I know there is a CPU implementation and a GPU implementation of the HoughCircles algorithm. However OpenCV uses tons of internal optimizations like NEON codes, parallelization, TBB framework, ... to reach higher performance. It is quite impossible for a basic software programmer to get equal results, unless you know how to do these specific optimizations.
Hmm do not underestimate the benefit of 8 cores. It could increase the speedup already quite drastically, especially if you can increase the load on each core!
You are probably iterating over each of your edge points and incrementing at each of the respective accumulator pixels. Profile your code. Consider the number of edge points you have versus the relative size of the images and circles.
If cache misses are a problem, try thinking backwards. Consider hashing the edge points in such a manner that you can iterate over each pixel p in the accumulator, quickly find the edges that contribute to p, and move to the next pixel in the accumulator.
@mfisher, I do like the fact you try to help people, but reviving topics of 2014 might be a bit overkill. Those guys are long gone and the fact is that other topics get pushed down in the list.
To best of my understanding after looking at the code I found under opencv\sources\modules\imgproc\src\hough.cpp ->icvHoughCirclesGradient OpenCV uses gradient information to reduce voting a full cirlce to only two votes for each edges points. This explains part of the speed up.
After implementing my own version that uses gradient information I am "only" 100 times slower than OpenCVs version.
Asked: 2014-04-01 19:12:10 -0600
Seen: 4,301 times
Last updated: Oct 10 '17
Sorry, may I ask you a question: is Chan-Vese Segmentation algorithm finished :-P?
Still working on it. I can refer you to an example written in Matlab from Matlab Central written by Yue Wu: http://www.mathworks.com/matlabcentral/fileexchange/23445-chan-vese-active-contours-without-edges
I hope this helps