Instagram Unshredder Challenge

unshred.rb

require 'RMagick'

# Reads the images specified by filename and returns an RMagick Image
# object
def read filename
  Magick::Image.read(filename).first
end

# Splits the input image into n vertical strips each with width equal
# to the input size (default 32). Returns an array of RMagick images
# each of which is a strip.
def split image, size = 32
  draw = Magick::Draw.new
  (0..image.columns-1).step(size).map{|x|
    image.crop(x, 0, size, image.rows)
  }
end

# Combines an array of images into one single image by laying them
# next to each other. Returns an RMagick image.
def combine images
  il = Magick::ImageList.new
  images.each{|i| il << i}
  il.append(false)
end

# Computes the difference between two images assuming they were laid
# next to each other with img1 on the left and img2 on the
# right. Computes difference as the sum of squares of the difference
# between each component of each pixel. Returns an integer
# representing the difference.
def difference img1, img2
  col1 = img1.export_pixels(img1.columns-1, 0, 1, img1.rows, "RGB")
  col2 = img2.export_pixels(0, 0, 1, img2.rows, "RGB")

  raise "images must have same height" if col1.size != col2.size

  col1.zip(col2).map{|cs|
    c1, c2 = cs
    (c1 - c2) ** 2
  }.reduce(:+)
end

# Computes the adjacency matrix for a complete asymetric graph between
# the input images, where m[i][j] is the distance between strips i and
# j if i is laid to the left of j. Returns the matrix.
def difference_matrix images
  a = []
  images.each_index{|i|
    a[i] = []
    images.each_index{|j|
      a[i][j] = difference(images[i], images[j])
    }
  }
  a
end

# Attempts to find the right edge of the unshredded image by finding
# the strip that is closest on the right (according to the
# distance metric above) to each strip. By the pigeonhole principle,
# there must be at least two strips that claim the same strip. It then
# finds the strip that is closest to its choice, and decides the other
# strip that claims that one is the right edge. This does not work
# universally, but seems the most effective strategy in the corpus of
# images I've tried. Returns the index of the supposed right edge.
def find_right_edge matrix
  gs = (0..matrix.size-1).map{|i|
    j = find_closest matrix, i, [], :right
    [i, j, matrix[i][j]]
  }.group_by{|g| g[1]}

  most_certain = gs.reject{|i, a| a.size == 1}
   .map{|i, a| a.min_by{|x| x[2]}}
   .min_by{|x| x[2]}

  most_certain[1]
end

# Finds the closest image to col on the left if dir == :left or the
# right if dir == :right without considering those in the
# used. Returns the index of the closest match.
def find_closest matrix, col, used, dir = :left
  (0..matrix.size-1).min_by{|i|
    if used.include? i
      1/0.0 #infinity
    elsif dir == :right
      matrix[col][i]
    elsif dir == :left
      matrix[i][col]
    end
  }
end

# Takes in a list of images and attempts to reorder them into their
# original ordering. Returns a permutation of images.
def order images
  matrix = difference_matrix images
  ordering = [find_right_edge(matrix)]
  1.upto(matrix.size-1){|i|
    r = find_closest matrix, ordering[0], ordering, :left
    ordering.insert(0, r)
  }
  ordering.map{|i| images[i]}
end

# Takes in an input filename and output filename, which should point
# to images. Reads in the input image, splits it assuming 32px strips,
# and attempts to recombine it into the original image.
def unshred input, output
  (combine order split read input).write output
end

# Takes in an input filename and ouput filename, which should point to
# images. Reads in the input image, splits it into 32px strips,
# randomly reorders those strips and outputs the newly shredded image.
def shred input, output
  (combine (split read input).shuffle).write output
end

if $0 == __FILE__
  unshred ARGV[0], ARGV[1]
end