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