Ask Your Question
2

Open CV's HoughCircles() is ~1000 times faster than my version

asked 2014-04-01 19:12:10 -0600

Y Simson gravatar image

updated 2014-05-06 01:00:13 -0600

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:

https://bitbucket.org/YontanSimson/opencv-projects/src/e504c2a4bd4043003456c63a44e440b96ae86050/HoughCircle/?at=master

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?

edit retag flag offensive close merge delete

Comments

Sorry, may I ask you a question: is Chan-Vese Segmentation algorithm finished :-P?

albertofernandez gravatar imagealbertofernandez ( 2014-04-02 06:35:53 -0600 )edit
2

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

Y Simson gravatar imageY Simson ( 2014-04-05 12:48:37 -0600 )edit

3 answers

Sort by ยป oldest newest most voted
5

answered 2014-04-02 02:58:02 -0600

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.

edit flag offensive delete link more

Comments

I have considered going down the path of Multi threading. However seeing that I only have 8 cores I still won't achieve the same speed as Open CV. I think they achieved the speed up with Hierarchical transform.

Y Simson gravatar imageY Simson ( 2014-04-05 12:50:18 -0600 )edit
1

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!

StevenPuttemans gravatar imageStevenPuttemans ( 2014-04-07 02:37:24 -0600 )edit
0

answered 2017-10-10 12:36:46 -0600

mfisher gravatar image

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.

edit flag offensive delete link more

Comments

@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.

StevenPuttemans gravatar imageStevenPuttemans ( 2017-10-11 04:49:30 -0600 )edit
1

@StevenPuttermans Yeah, sorry. I didn't see how old the question was until after I posted.

mfisher gravatar imagemfisher ( 2017-10-11 10:46:57 -0600 )edit
0

answered 2014-05-10 10:03:02 -0600

Y Simson gravatar image

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.

edit flag offensive delete link more

Question Tools

Stats

Asked: 2014-04-01 19:12:10 -0600

Seen: 4,339 times

Last updated: Oct 10 '17