Hacker News Reader

Comment by Luyt | Hacker News Reader

"sum of differences between rightmost male pixel and leftmost female pixel over all rows"

I tried this, and it worked for a few test pictures I downloaded, but it fails for the given Tokyo panorama: the dark edges and sharp corners in some buildings confuse the algorithm. The matching must be done on somewhat more than pixel values alone...

EDIT: See how my implementation fails: http://www.michielovertoom.com/incoming/TokyoPanoramaUnshred...

View on HN

I put in a sampling resolution, to only examine every nth row. For a number of pictures, n=50 was fine. One picture even allowed n=200. For the given image, n=2 would not even work; I had to sample every row.

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.

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?

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.

Yeah, there are a whole bunch of things you could try, but i think a standard Gaussian blur on the edges would solve your problem.

Reply on news.ycombinator.com