4 ms·
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 a
by asharp 15y 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?
- deleted 15y ago[deleted]
- Luyt 15y 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/TokyoPanoramaUnshredded18.png http://www.michielovertoom.com/incoming/TokyoPanoramaUnshred...
- webfuel 15y agoCan 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.
- Luyt 15y agoThe 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 ;-(
- webfuel 15y agoMinor 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.
- Luyt 15y agoCurrently 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)
- webfuel 15y agoNo problem! Yes, I have this working: http://webfuel.org/instaunshredderv2.php http://webfuel.org/instaunshredderv2.php It also works on the test images I created: http://webfuel.org/a.png http://webfuel.org/a.png http://webfuel.org/b.png http://webfuel.org/b.png http://webfuel.org/c.png http://webfuel.org/c.png
- s3ththompson 15y agoThis 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.
- asharp 15y agoThat'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?
- japhyr 15y agoI 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.
- asharp 15y agoYeah, there are a whole bunch of things you could try, but i think a standard Gaussian blur on the edges would solve your problem.