5 ms·

Finding rectangles in images using Haskell

48 points by dclaysmith 15y ago

willvarfar 15y ago
please someone post the APL program to do this!
Nate75Sanders 15y ago
"Given a binary image, find the largest axis aligned that consists only of foreground pixels." I think you mean "axis-aligned rectangle", no?
Nate75Sanders 15y ago
I remember reading about this in DDJ back in the day: http://drdobbs.com/database/184410529 http://drdobbs.com/database/184410529
sinjax 15y ago
My immediate thought was to do a hough transform. The equation for rectangles has very few parameters and finding "complete" rectangles at any given point would fast, though slower than this technique in honesty the bonus of the hough transform approach is that you'd get ALL the complete rectangles. Also you could (optionally) get the biggest rectangle which is almost complete (let's say missing one or two pixels). Which is nice in the practical case when you are looking for shapes because "noise is a bitch" word.
- willvarfar 15y ago
  What jumped to my mind is that if you detect the vertical and horizontal lines - O(n) - and call those corners 'm'. You can then just run the O(n^2) bit on m rather than the whole n. Worst case n=m, but usually m will be massively smaller. http://stackoverflow.com/questions/289779/calculating-a-boundary-around-several-linked-rectangles/294549#294549 http://stackoverflow.com/questions/289779/calculating-a-boun...
wmwong 15y ago
Not necessarily on the topic of the article itself, but I found this to be a good concrete example of how to think in Haskell (and functional programming in general?). I've just started learning by reading Learn You a Haskell. Even though there are plenty of examples in the book, so far, none of them are concrete. I found this article helps with the thought process of how to approach a problem in Haskell. The code snippets are accompanied with some clear explanations, and with some effort, I could figure out what the code does. If you're a new Haskeller, I would encourage you to take the time to understand what's going on.

48 points by dclaysmith 15y ago

please someone post the APL program to do this!

"Given a binary image, find the largest axis aligned that consists only of foreground pixels." I think you mean "axis-aligned rectangle", no?

Nate75Sanders 15y ago

I remember reading about this in DDJ back in the day: http://drdobbs.com/database/184410529 http://drdobbs.com/database/184410529

sinjax 15y ago

My immediate thought was to do a hough transform. The equation for rectangles has very few parameters and finding "complete" rectangles at any given point would fast, though slower than this technique in honesty the bonus of the hough transform approach is that you'd get ALL the complete rectangles. Also you could (optionally) get the biggest rectangle which is almost complete (let's say missing one or two pixels). Which is nice in the practical case when you are looking for shapes because "noise is a bitch" word.

willvarfar 15y ago
What jumped to my mind is that if you detect the vertical and horizontal lines - O(n) - and call those corners 'm'. You can then just run the O(n^2) bit on m rather than the whole n. Worst case n=m, but usually m will be massively smaller. http://stackoverflow.com/questions/289779/calculating-a-boundary-around-several-linked-rectangles/294549#294549 http://stackoverflow.com/questions/289779/calculating-a-boun...

wmwong 15y ago

Not necessarily on the topic of the article itself, but I found this to be a good concrete example of how to think in Haskell (and functional programming in general?). I've just started learning by reading Learn You a Haskell. Even though there are plenty of examples in the book, so far, none of them are concrete. I found this article helps with the thought process of how to approach a problem in Haskell. The code snippets are accompanied with some clear explanations, and with some effort, I could figure out what the code does. If you're a new Haskeller, I would encourage you to take the time to understand what's going on.