hough transforms

[maestro]

So lately I have been interested in Hough transformation, and am wondering first off if any one has been successful in making one in autoit, and secondly if any one knows of any good real time method changing live media to binary so I can run the calculation on the media so i would be able to display real-time output that highlights the lines / shapes i am making it look for.

I found one thread a while back that demonstrates a script that can clone the appearance of windows using user32.dll and gdi32.dll dll calls, but I don't fully understand the mechanics behind it, and am unsure if this method would work or not for my purposes.

Thanks,

Ilmaestro.

Edited December 9, 2010 by maestro

[jchd]

All flavours of Hough transforms imply very VERY heavy computations, the more complex the shape you need to detect, the heavier computations are. There are Hough transforms for detecting straight lines, circle, elipses, parabola, hyperbola but, albeit the same principles can be applied as well to detect curves of higher degree, it's rarely done due to neverending runtimes. I happen to have written about Hough transforms at several occasions, but it looks like the links have all vanished some time ago, or have been replaced to point to more recent/detailed material. Here is a link remaining to a usenet post with short bibliography.

It's completely irrealistic to even try to code a Hough transform in AutoIt and apply it to a significant image. Real-time is a dream except if you have access to a massively parallel machine, in which case AutoIt won't make you any good.

What kind of image do you want to apply which (lines, circles, ...) Hough transform to?

What is the relationship with a Windows-looking graphics?

What is your purpose, really?

Edited December 10, 2010 by jchd

[maestro]

Well for now I was just going to use it for lines, and I was going to use it on web cam input.

I have seen some videos that demonstrate real time line detection.

And as far as my purpose behind it, its just more for my understanding / research at this point then it is for anything specific.

(later down the road might try facial recognition)

Thanks,

Ilmaestro.

[jchd]

Sincerely, I doubt Hough xform can be done in real time without specific hardware. Here's how it goes for lines:

apply suitable image filtering/transform to achieve desirable contrast

for evey point P in image

--for every point Q in image with Q <> P

----compute the parametric equation of line PQ in the form ρ = x cosθ + y sin θ

----accumulate (ρ, θ) values as Q varies (this in fact builds a large number of sinusoids)

--determine (by statistical means) if there is an "almost common" point (or rather a high density convergence area) between the sinusoids.

--If there is, it represents what could be (never 100% sure) a straight segment in the original image

continue with next P

consolidate lines found so far and filter out those which don't fit the object's chracteristics

I didn't check very recently for improvements in this domain but I'm not aware of any "simple" implementation of such algorithm and, as often, the devil is in the details. Several important parameters need to be fine-tuned depending on image resolution, contrast, and other characteristics like thickness and expected length of the objects you wish to recognize. Developping real-time _true_ Hough can only be achieved with seriously parallel architecture (multiple GPUs or a bunch of cores, or ASICs).

Hough is _not_ used AFAIK for edges recognition, which use completely distinct approaches/algorithms, let alone facial recognition.

Edited December 10, 2010 by jchd

[maestro]

Hi, thanks for the replys thus far.

I guess im having trouble understanding Hough transforms, and there limitations.

I have a high end i7 processor wich is almost always idol, so if there is a way to use more resources to give faster results, ide be more then happy to do that, as i have the 5870 graphics hard so my gpu is quite good as well.

I have come up with some ideas to get realtime 2d arrays that i can store the values of the media, however Im having trouble implimenting the hough, would you be able to give me an example of code, or a more indepth description of the inner workings / theory behind one. ( it can be a slow example, I just want to see the mechanics of it, i had trouble following your "P Q" example.

Thanks,

Ilmaestro.

[jchd]

I'm afraid I don't have spare time to drive you inside a complete implementation. Your best bet is to Google around and follow exemples given here and there, then dig in the referenced litterature if you still find Hough suited for your needs.

There are now good chances that some open source implementation exists, but I don't have pointers to it/them. Look towards Matlab (or clone) modules.

Depending on your actual problem, much more simple edge detection can work well and wih great efficiency.

[maestro]

Thanks anyways for your time jchd.

This topic is still open to any one else who might have other possible solutions to the problem.

Thanks,

Ilmaestro.

[jchd]

Ten seconds googling turned up this link to a reference implementation of a faster variant (I'd rather call it an emasculation) of the basic Hough idea.

Going to the download link, you'll find a C++ source, a Win32 binary and a Matlab wrapper.

Notice that on the example chessboard picture, there are a number of obvious lines that are simply ignored but would have been detected by the full-fledge Hough version.

Have fun.

[maestro]

The link didn't work for me, do you know any other good examples.

Also, I have been able to convert an image to line binary, with all the info stored in a 2d array ( 1 or 0 ) with this information, I was wondering if you could give me a tip on how to process this for line detection, I dont seem to be making much progress after this point.

Thanks,

Ilmaestro.

[jchd]

The link http://www.inf.ufrgs.br/~laffernandes/kht.html is _not_ dead, probably temporary slowdown somewhere in the path.

Really sorry but I don't have enough spare time to guide you towards anything close to a working implementation. Your best bet is to pick up a Hough line algorithm somewhere and implement it in AutoIt, as slow as it will be. Leave optimizations for later.