Jump To …

## insta.coffee | |
---|---|

This is a solver for the Instagram shredder challenge. Given a url of an image that is shredded, and the width of the shreds, this code calculates a probable unshredded version of the image. The algorithm works best for natural photos and may be less accurate on highly periodic images, such as patterns. | |

## UnshredTake a canvas object of a shredded image, and the width of the shreds, and return a new canvas object with what it has determined to be the most likely original order of the shreds. | ```
unshred = (shreddedImage, shredWidth) ->
{width, height} = shreddedImage
``` |

Split the image into it's individual shreds. | ` shreds = split shreddedImage, shredWidth` |

Calculate the matrix of correlation weights for each shred against every other shred. We correlate every right edge against every left edge (or return zero when both edges are from the same shred). When correlating the edges, we unzip the rgb channels, correlate each channel independently, and then take the mean of the correlation of the 3 channels. | ```
weights = cross shreds, (x, y) ->
if x == y
0
else
mean zipWith unzip(rightEdge(x)), unzip(leftEdge(y)), correlate
``` |

This function normalizes a row of numbers and then inverts them. We do this because some shreds will naturally correlate highly with every shred, and others will naturally correlate poorly with all shreds. Instead of maximizing the raw correlation values, we seek to maximize the normalized values. This compensates for shreds that generally correlate poorly and it experimentally performs substantially better. We invert the numbers because the traveling salesman algorithm seeks to minimze the total cost, and without inverting the numbers, we'd need to maximze the cost. | ` invertNormalize = (row) -> invert normalize row` |

Calculate the best new arrangement of shreds. | ` path = optimalPath range(shreds.length), map weights, invertNormalize` |

Create a new image with the same dimensions as the shredded image, to draw the unshredded image into. | ` unshreddedImage = element 'canvas', {width, height}` |

Draw the shreds in their unshredded order and return | ```
map path, (p, i) -> draw unshreddedImage, shreds[p], i * shredWidth, 0
unshreddedImage
``` |

## Finding the optimal pathGiven a list of nodes and a matrix of the cost of traveling from one node to another, this returns the lowest weighted path that visits each node exacty once. The implementation is a simple branch-and-bound search. As a result, this is not effective with a large number of nodes. While sufficient for 20 nodes, it may not be sufficient for 40 nodes (depending on the weights of the graph). | `optimalPath = (nodes, weights) ->` |

This is updated with the best path found during the search. | ` best = path: [], weight: Number.MAX_VALUE` |

Recursively walk the nodes with a branch-and-bound algorithm. It takes a
list of unwalked nodes, as well as the current path of the
traversal. The | ` walk = (nodes, current={path: [], weight: 0}) ->` |

If there are no nodes left to walk, then the current path must be the best path. | ` return best = current if nodes.length == 0` |

Given a node, this returns the weight of the new path with the node appended to it. | ` weight = (node) -> current.weight + (weights[last current.path]?[node] ? 0)` |

Compares the weights of two paths. It's used to sort paths later on. | ` weightCmp = (x, y) -> weight(x) - weight(y)` |

We traverse the nodes from lowest to highest cost. | ` for node in sort nodes, weightCmp` |

Early out if the current path is more expensive than the best current best known path. We can get away with this because we're traversing the nodes in ascending order. | ` return if best.weight < weight node` |

Remove the node from the unwalked list, append it to the current path, and recurse. | ```
walk remove(node, nodes),
path: append(node, current.path)
weight: weight node
``` |

Find the optimal path and return it | ```
walk nodes
best.path
``` |

## Miscellaneous helpers | |

Calculates a matrix, | ```
cross = (xs, fn) ->
(fn(x1, x2) for x2 in xs for x1 in xs)
``` |

Takes two discrete signals, represented as a list of numbers, and returns a value between -1 to 1 representing a measure of how closely the two signals follow a similar trend. 1 meaning the signals are very similar, and -1 meaning there is a negative relationship between the signals. The correlation metric used is the Pearson product-moment correlation coefficient. For a more precise definition of the metric, reference that article. | ```
correlate = (xs, ys) ->
covariance(xs, ys) / (stdDev(xs) * stdDev(ys))
``` |

Calculates a measure of how much two random variables change together. See covariance on Wikipedia. | ```
covariance = (xs, ys) ->
[mx, my] = [mean(xs), mean(ys)]
mean zipWith xs, ys, (x, y) -> (x - mx) * (y - my)
``` |

Transforms a list of arbitrary numbers into a list of numbers linearly scaled between zero and one. The returned list will always contain at least one 0 and 1, unless the min value in the list is the same as the max value, in which case a list of all NaN will be returned. | ```
normalize = (xs) ->
[mn, mx] = [min(xs), max(xs)]
map xs, (x) -> (x - mn) / (mx - mn)
``` |

Takes a list of numbers and returns a new list with all of the numbers subtracted from one. | ```
invert = (xs) ->
map xs, (x) -> 1 - x
``` |

## HTML & Canvas helpers | |

Creates a new html element and returns it. The | ```
element = (type, options) ->
el = document.createElement type
for key, val of options
el[key] = val
el
``` |

Draws the source image or canvas into the target canvas. The three forms are: | ```
draw = (target, source, args...) ->
target.getContext('2d').drawImage source, args...
target
``` |

Takes a url of an image and a callback. Loads the image into a canvas and calls the callback with the new canvas as an argument once it's loaded. | ```
loadImage = (src, callback) ->
image = new Image()
image.src = src
image.onload = ->
canvas = element 'canvas', width: image.width, height: image.height
draw canvas, image, 0, 0
callback canvas
``` |

Takes a canvas and splits it into strips that are | ```
split = (canvas, width) ->
height = canvas.height
for x in range(0, canvas.width, width)
slice = element 'canvas', width: width, height: height
draw slice, canvas, x, 0, width, height, 0, 0, width, height
``` |

Given a canvas and an index, returns an array of pixel data from a column of the canvas. Each pixel is represented as an array of [r, g, b]. | ```
pixelColumn = (canvas, index) ->
context = canvas.getContext('2d')
data = (i for i in context.getImageData(index, 0, 1, canvas.height).data)
rgb = ((data[(4 * i) + j] for j in range(3)) for i in range(canvas.height))
``` |

Given a canvas, returns the right edge of pixel data. | ```
rightEdge = (canvas) ->
pixelColumn canvas, canvas.width - 1
``` |

Given a canvas, returns the left edge of pixel data. | ```
leftEdge = (canvas) ->
pixelColumn canvas, 0
``` |