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.

Unshred

Take 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 unshreddedImage.

  map path, (p, i) -> draw unshreddedImage, shreds[p], i * shredWidth, 0
  unshreddedImage

Finding the optimal path

Given 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 current path defaults to a path of zero length and zero cost.

  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, A, where A[i][j] is fn(xs[i], xs[j]). In other words, it enumerates every combination of two elements from xs (with replacement), and maps a function over each pair, returning the corresponding 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 type is simply the type of the element to construct, such as 'div', and any options passed will be set as attributes on the element.

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:

1. To copy and translate:
   draw tgt, src, dx, dy

2. To copy and scale:
   draw tgt, src, dx, dy, dw, dh

3. To copy, crop, and scale:
   draw tgt, src, sx, sy, sw, sh, dx, dy, dw, dh
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 width wide. It returns a list of new canvas objects that are the strips from canvas.

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