Instagram Engineering Challenge: The Unshredder

http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder

by mikeyk • 15 years ago

156 65 15 years ago

instagram-engineering.tumblr.com

icki• 15 years ago

Interestingly enough, DARPA is running a similar challenge (their prize is a lot better): http://www.darpa.mil/shredder_splash.aspx#Splash

jakubw2• 15 years ago

My first thought was that not only they were inspired by that one but they're trying to parody it.

asharp4• 15 years ago

Now that, my friend, seems to be an actual challenge.

InclinedPlane• 15 years ago

This is already a solved problem, but the existing processes are hugely expensive, darpa is looking to see if anyone has a good idea on making it cheap enough to be routine.

hopeless• 15 years ago

I knew I'd heard of a similar challenge. If I was a cynic, I'd say instagram would take the winning solution and enter it in the DARPA challenge. Crowd-sourced competition entries!

jvandenbroeck• 15 years ago

The DARPA challenge is much more complicated, the Instagram challenge (which is accompanied by a solution!) is child's play.

snotrockets• 15 years ago

There's a famous anecdote about human unshredding: when the Iranian revolutionary took over the US embassy in 1979, they captured the shredded remains of secret documents. They took those shredding to the carpet weavers Iran is so famous of, who manually rewoven the shreds into the original documents (See http://en.wikisource.org/wiki/Documents_seized_from_the_U.S....)

systrom• 15 years ago

This is a pretty amazing story. Thanks for sharing! I wasn't inspired by this when I wrote it up, but it looks like it's not the first time it's crossed someone's mind.

blumentopf• 15 years ago

The German government is funding a project to algorithmically unshred the files that the Stasi (East Germany's secret police) destroyed in 1989 when the Berlin wall came down and protesters started to occupy their buildings:

http://news.bbc.co.uk/2/hi/6692895.stm

ppk• 15 years ago

Yeah it was fascinating, there's a whole article on it from Wired:

http://www.wired.com/politics/security/magazine/16-02/ff_sta...

nikcub2• 15 years ago

I thought the point of this exercise was going to be to produce an Instagram filter that creates that awesome 'shredded' effect as seen in those real shredded documents.

Turns out they are just splitting images up and rearranging them - not as interesting.

(see for eg. http://en.wikisource.org/wiki/File:Espionage_den02_79.png)

asharp4• 15 years ago

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?

Luyt4• 15 years ago

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

webfuel3• 15 years ago

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.

japhyr• 15 years ago

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.

asharp4• 15 years ago

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.

______• 15 years ago

I find it strange that they don't provide an interface that the desired program should implement. For example, "provide the input image as a command line parameter to the script / binary, write the output to out.jpg"

Because of this, is someone going to actually take the time to understand what assumptions people make to run the program? If there was an interface, they could just run a script to test submissions...

uniclaude3• 15 years ago

I thought it would be a fun thing to do tonight until I saw all the tips given at the end of the article. They basically give the solution, it's not funny anymore :(.

stevelosh• 15 years ago

So make it more fun:

* Support crosscut shredders (shredded in both directions).

* Make it work even if the shreds aren't all the same size.

* Make it work when there are some pieces missing.

* Show where those missing pieces would probably go.

* Make it work when two images' shreds are mixed together.

* (with missing pieces)

* (generalized to N images)

* Predict what the missing pieces might look like (this one is much tougher).

* Think of ways you could cheat (like searching Tineye for the fragments to find the original image, if it was originally online somewhere).

You can keep going as long as you want. If it's too easy, just make it harder.

Edited because HN doesn't support Markdown or linebreaks. :(

bfung• 15 years ago

* write a plugin for photoshop or gimp that will select the arbitrary shreds.

Does that exist already?

emmelaich• 15 years ago

Another idea: combine it with a file recovery or computer forensic program to stitch jpeg file fragments together.

mnutt• 15 years ago

Also: make it work for shreds at any angle and overlapping, as if you dumped the pieces on a flatbed scanner and hit 'scan'.

gerggerg• 15 years ago

Implement zoom and enhance so we can see what all the people in those buildings are up to.

uniclaude3• 15 years ago

If it's too easy, just make it harder.

Absolutely.

Wa can make it harder in many creative ways, and that would be fun, but I wrote this comment to express the feeling of disappointment I had when I saw the post. I felt a little bit like someone showed me a candy but already ate half of it.

Terretta• 15 years ago

Agreed. Showing how to use PIL, fine. But if they really intended to use this as a gate, then showing the key to a solution -- what's the point?

patio11• 15 years ago

It is still Fizzbuzz++: they're not looking for computer vision researchers. They're looking for programmers who are competent enough to be worth their time interviewing. If you can go from hints in the direction of the solution to a) reading library documentation, b) coming up with an innovative solution to an only-partially specified problem, and c) actually producing functioning code which implements your solution, you are heads and tails above the hiring pool.

dabent• 15 years ago

I have to echo patio11 below. The point here isn't to find PhD-level image analysts, it's to find some relatively solid (Python) developers in fairly short order, while handing out advertising to people in the form of shirts. The problem isn't hard for people who end up reading Hacker News on a Friday night (and Veteran's Day in the US, when some folks are off work altogether), but this is just the kind of people they're looking for in a tight tech labor market.

I noticed they did remove on of the functions they had listed in the hints at the bottom, possibly to make things a bit more challenging.

username3• 15 years ago

Seems like they're trying to fix the rolling shutter effect on iPhones or shredded photos the iPhone takes sometimes.

wallflower• 15 years ago

Interesting. A 90 degree phase change makes a huge difference

> For maximum security, documents should be shredded so that the words of the document go through the shredder horizontally (i.e. perpendicular to the blades). Many of the documents in the Enron Accounting scandals were fed through the shredder the wrong way, making them easier to reassemble.

joshmlewis• 15 years ago

Isn't this like the bunny slope of Darpas shredder challenge?

dasil003• 15 years ago

Some of those Instagram filters look like they make the job easier.

fferen2• 15 years ago

Isn't this extremely obvious? Couldn't you just take the first slice, calculate the total color difference between its right edge pixels and the corresponding left edge pixels of each of the other slices, and stick it next to the one with least difference, then repeat?

I mean, you'd need to specify some threshold to handle slices on the ends, and maybe use sum of (difference^2) instead of just the sum, but it shouldn't be hard at all. Am I missing something?

lunaru2• 15 years ago

That would be slow if you didn't know the slice size (the bonus part of the question), but no, you're not missing anything for the basic solution. That said, it would be O(n^2) since you're comparing every slice to every other slice.

bermanoid2• 15 years ago

The general problem is fairly easily isomorphic to traveling salesman, so if you can get even O(n^2) you're already making simplifying assumptions that mean you can't solve the general case. Further, with n=20, I wouldn't usually worry too much about asymptotic performance unless you're in exponential territory.

jakubw2• 15 years ago

While this problem is indeed easy, what you described is a greedy algorithm and won't give you the most optimal solution and, specifically, could give you a different solution if you shuffled the shreds, which shouldn't be happening.

Hint: very often, when you think "isn't it extremely obvious?", you've come up with a greedy algorithm and it's not the right one. :)

nikcub2• 15 years ago

In terms of optimization, it is always better to put a solution together in pieces rather than all at once.

fferen2• 15 years ago

Yes, I meant that after combining two, treat them as a new slice, and repeat until there is only one slice.

Luyt4• 15 years ago

I did just that, but the algorithm fails on the provided Tokyo picture. It works on other pictures, tho.

lunaru2• 15 years ago

The tips seem to be just a crude pixel matcher. Seems much more elegant to transfer the image into the frequency domain via FFT and find edges that way.

jamesjyu2• 15 years ago

No way! You'd lose all spatial information in the frequency domain.

fooandbarify2• 15 years ago

That is false. (No information is lost in the Fourier Transform.) However, I'm not sure how Fourier analysis would help in this case - image processing is not my forte. Perhaps there would be a spike at the spatial frequency where the discontinuities occur (given that the discontinuities are evenly spaced)?

EDIT: Given the slices, is it possible to order them properly entirely in the frequency domain?

vedran• 15 years ago

For anyone who's thinking of using Ruby I recommend OilyPNG instead of RMagick. It's a c extension to ChunkyPNG and is much faster if you don't need all of the fancy filters that come with ImageMagick.

https://github.com/wvanbergen/oily_png

st3fan• 15 years ago

Doesn't DARPA have a similar challange?

razzaj• 15 years ago

in the sample they provided shreds seem to be 25 pix and not 32

eCa• 15 years ago

You want to use the linked image [1], not the one they show in the post.

[1] http://instagram-static.s3.amazonaws.com/images/TokyoPanoram...

stuyguy• 15 years ago

You know you're done if you understand what this image means (and how it was made): http://i.imgur.com/Kn7Za.png

tucaz• 15 years ago

Looks like I was able to do it. I'm not sure if they will be happy to get a result in C#, though.

Also, not as easy as I thought it would be. A friend had to give me some help with the math to match the stripes.

Edit: How long did you guys take to figure this out? I took nearly 4 hours.

weka• 15 years ago

and this is why I need to start learning python.........

vidoss2• 15 years ago

Did anyone manage to match the 12th shred next to 6th ? (zero index). That white and black building is really messing it up.

vidoss2• 15 years ago

Ok. Got it working... See demo http://vidoss.github.com/

zx2c42• 15 years ago

It works! Here's a demo: http://www.youtube.com/watch?v=hILm9oojA48

zx2c42• 15 years ago

Oh, and here's the source: http://git.zx2c4.com/instagram-unshredder/tree/unshred.py

BarkMore• 15 years ago

Although Instagram promised a brand-spankin’ new Instagram shirt if you complete the challenge correctly, they are only sending out stickers.

I hope they are not another Zynga :).

Instagram Engineering Challenge: The Unshredder

Related Stories