Hough Transform

[poison]

Hi all,

I'm doing line detection on camera input (GPUImageCannyEdgeDetectionFilter -> GPUImageRawDataOutput) by using OpenCV's hough transform (cvHoughLines2). Unfortunately this is extremely slow, it takes up to 1,2 s and higher to do so. I was wondering if anyone implemented GPU-based fast hough transform. It's described in many papers but I don't seem to find relevant sample code. Is there anybody who achieved this on the GPU?

Best regards, Nicolas

[BradLarson]

I had contacted this group:

http://medusa.fit.vutbr.cz/pclines/

about their GPU-accelerated implementation of a Hough transform for line detection using parallel coordinates. They had a working in-house version based on Android, and I was going to see if I could adapt that to this framework. They were going to send me their code, but they got a little busy. I'll check in with them again.

[poison]

I guess there are licensing issues with their code? I'm still dreaming of in-GPU Hough :) Doing it on CPU is terribly slow unfortunately

[BradLarson]

Not at all. I had simply forgotten to remind them again about this until a couple of weeks ago. I now have their desktop implementation, but am waiting on their OpenGL ES variant. I see what they're doing now, but the desktop OpenGL code is going to require a significant rewrite to make work. If I can get the OpenGL ES version they created, it would save me a lot of time.

[poison]

Oh, this would be great! Looks promising! Thanks in advance

[BradLarson]

I finally got a working version of their PC line Hough transform in the framework. The FilterShowcase and FeatureExtractionTest sample applications show how it works. It's a little noisy and slower than it should be, but I haven't even started optimizing this yet. Still, it runs at ~15 FPS on 640x480 video on an iPhone 4S, so that's probably much better than what you can get from OpenCV.

[skovsboll]

Brad, is there a way to extract the confidence of each line? That would enable me to sort the lines and only use the strongest ones.

[BradLarson]

@skovsboll Unfortunately, not in the current implementation. You can adjust the thresholding for which lines are detected using the lineDetectionThreshold, but that thresholding and readback is performed within a shader, so strength of the lines isn't currently returned from that.

In any case, the line intensities are prone to noise because they saturate the 8-bit dynamic range for intensities pretty quickly. To overcome this, I'll need to implement some of the directional filtering that the original researchers did, but I haven't yet had the time to put this in.

[skovsboll]

Fiddling with thresholds doesn't enable me to extract exactly the lines that I expect. I find it excludes lines that look stronger and includes weaker ones. If you do find the time to output the strengths it would be awesome. Thanks for all the effort you put into GPUImage, it's really useful.

[kcraft]

Brad, firstly, thanks a ton for developing this framework. It is awesome!

I have been toying with the Houghlines filter and am definitely having issues with the noise. I'm trying to do something very similar to skovsboll. I'm running some of my own algorithms to filter out noise and and a clearer picture of where the lines in the image are actually positioned. I've had some success with it, but some of the lines I'm seeing just seem like gibberish.

I know you probably work on this in your spare time, so of course I don't have any expectations, but I'm wondering where "fixing" the houghlines filter falls on your list of priorities for this project.

Thanks again for making this great contribution to the community. :)