search

inspirit / jsfeat

JavaScript Computer Vision library.
MIT License
2.74k stars 372 forks source link

Hough Transforms? #27

Closed lancejpollard closed 6 years ago

lancejpollard commented 10 years ago

Do you guys have any plans to implement Hough Transforms? Or is there another approach to doing line/shape detection (without training data like with haar classifiers) in jsfeat?

Thanks man, really excited to start using this, there's so much stuff in here!

inspirit commented 10 years ago

Hough wasnt in my head at the moment since its quite computation expensive. but i think it shouldnt be hard to port it from OpenCV for example, it looks pretty straight forward there.

lancejpollard commented 10 years ago

Ah that makes sense. Are there ways to optimize the hough transform? I am just starting to learn about it but it seems that the algorithm basically iterates 360 times for each pixel in the image (if you divide the circle into 360 degrees rather than more fine-grained), so the larger the image the more it has to do. So a 600x600 image means ~130 million iterations? That seems kinda crazy, maybe I'm way off. That would be pretty slow for sure. Probably would take like a second at least, but it could be run in web workers.

But, if there was some way to segment an image, and only divide the circle into chunks smaller than 360 in some intelligent way, maybe it could be sped up. Is there anything you know in relation to that? This paper has some suggestions for "optimized hough transforms", such as implicit shape kernel and a few others:

http://link.springer.com/chapter/10.1007%2F978-3-642-41181-6_6#page-1

Thoughts?

inspirit commented 10 years ago

i recommend to look at OpenCV implementation. as far as i know it has some rotation related optimizations.

lancejpollard commented 10 years ago

Cool, sounds good.

literalpie commented 6 years ago

This issue should be closed.