News for hackers. Stuff that matters.
Re:Instagram Engineering Challenge: The Unshredder by asharp on Friday November 11, 2011 @03:32PM (#3226040)
Warning, spoiler?

My first take on it was the following: Take the average of the differences between each pixel and the pixel adjacent to it over each column and store that as, say, X[]. Find some maximum number such that the sum of every nth column of X - the sum of all other rows of X is maximised. That's the column width. Split into a series of columns, use stable matching to match columns based on the sum of differences between rightmost male pixel and leftmost female pixel over all rows. Use stable marrage to give you a partial ordering, turn into a complete ordering and unscramble the image.

Any better/more elegant solutions?

Re:Instagram Engineering Challenge: The Unshredder by Luyt on Saturday November 12, 2011 @10:56AM (#3228024)
"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...

Re:Instagram Engineering Challenge: The Unshredder by japhyr on Monday November 14, 2011 @05:07AM (#3233509)
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.
Re:Instagram Engineering Challenge: The Unshredder by webfuel on Saturday November 12, 2011 @11:43AM (#3228137)
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.

Re:Instagram Engineering Challenge: The Unshredder by Luyt on Saturday November 12, 2011 @12:00PM (#3228186)
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 ;-(

Re:Instagram Engineering Challenge: The Unshredder by webfuel on Saturday November 12, 2011 @12:21PM (#3228250)
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.

Re:Instagram Engineering Challenge: The Unshredder by asharp on Monday November 14, 2011 @04:46AM (#3233472)
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?

Re:Instagram Engineering Challenge: The Unshredder by Luyt on Saturday November 12, 2011 @01:50PM (#3228513)
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)

Re:Instagram Engineering Challenge: The Unshredder by webfuel on Saturday November 12, 2011 @02:42PM (#3228683)
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

Re:Instagram Engineering Challenge: The Unshredder by s3ththompson on Saturday November 12, 2011 @04:23PM (#3228954)
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.
Re:Instagram Engineering Challenge: The Unshredder by asharp on Monday November 14, 2011 @06:21AM (#3233623)
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.