Finding rectangles in images using Haskell

twanvl.nl

48 points·dclaysmith··6 comments

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.

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.

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

I remember reading about this in DDJ back in the day:

http://drdobbs.com/database/184410529

"Given a binary image, find the largest axis aligned that consists only of foreground pixels."

I think you mean "axis-aligned rectangle", no?

please someone post the APL program to do this!

Reply on news.ycombinator.com