Hacker News Reader

Comment by webfuel | Hacker News Reader

Can you post some of your test pictures?

Re: your attempt: I think you just need to find the starting strip, looks like your algorithm is working.

The starting strip is, by definition, the strip on which no other strip has been placed left of. There is no other way of determining what the starting strip is; it's not a given. The problem is that with my current pixel matcher (sum of absolute differences) one strip is wrongly attached. That made me think I also have to take other features in consideration, like color, hue and/or line detection. But that seems outside the scope of this challenge.

The algorithm works fine for some random pictures I found on the web. It's just not working for the Tokyo picture ;-(

Minor spoiler/hint:

My algorithm, given a strip, would tell you which strip was on the right and also gave a certainty. The last strip would have a "next strip" value shared with an earlier strip (thus wrongly attached) but with less certainty.

Edit: Or (worst case) the last strip would have a high degree of uncertainty.

Currently I'm using a matrix to determine adjacency, but I'll give this graph idea a try. Thanks for the tip!

PS. Have you actually realized a succesful implementation? (Just curious)

No problem! Yes, I have this working:

http://webfuel.org/instaunshredderv2.php

It also works on the test images I created:

http://webfuel.org/a.png http://webfuel.org/b.png http://webfuel.org/c.png

This is exactly how I implemented my solution. The worst case scenario is important because some images have last strips that have a unique "next strip" value.

That's what stable marriage is for. With some reasonable heuristic it should just give you the best partial ordering, which when flattened into a total ordering should give you the most likely picture.

How do you calculate your certainty?

Reply on news.ycombinator.com