My solution to the Instagram Engineering challenge - The Unshredder

readme.md

The challenge

The challenge was to write a short script in a scripting language of choice that takes in an image of mixed up uniform sized shreds and pieces them back into the unshredded and reconstituted image. That means the original image was divided into an even number of columns of same size and than those columns were shuffled randomly. Additionally the script should auto-detecting how wide the uniform strips are.

The solution

Before I started on my solution, I made some quick assumptions to simplify things:

• I wanted to code it in Ruby, simply because it's a great language and I'm quite productive in it.
• I wanted to define a simple distance measure which can be used for auto-detecting the column size and putting the shredded image back into its original state.
• I used ChunkyPNG, a pure ruby library for read/write access to PNG images.
• This solution was only tested with a few pictures. It is by now means perfect, but just a quick hack, which I had fun on. Feel free to improve or suggest improvements to it.

Distance measure

Key to my solution is a simple distance measure slightly based on ΔE, which simply is a metric for the difference or distance between two colors. But instead of using LAB color space I adapted the measure for the RGB color space. My distance measure takes two 1px wide columns end compares pixel to pixel from top to bottom. The sum of different pixels for a certain pair of columns is the distance between these two. To ease the result a little bit, a threshold is used. This threshold was obtained by trial and error using a few test pictures, like every good programmer would obtain it (^_^). However, please note, taking this measure makes it difficult to unshred images which are not very saturized. It could be improved by increasing the width of the 1px wide columns for comparison.

Obtaining shred-width

This distance measure is used in shred_with function, which compares 2 neighboring columns until two columns are found, which distance is greater than $0.6$ of the picture's height. Again to get the number of $0.6$ I used trial and error using a few test pictures. The column count of the last compared column is the returned shred width.

Unshredding

Finally the unshred function crops the image into equally sized shreds. For each shred the first and last column of pixels are stored into respective arrays. Then every last column is compared with every first column in terms of their distance. The pair with the least distance are combined first. Then the best matching next shred is either appended to the left or to the right until no shreds are left.

theunshredder.rb

require 'chunky_png'
include ChunkyPNG::Color

module ChunkyPNG  
  class Image

    # return first column, which distance to neighbour is not "within range" (=shred width)
    def shred_width(t=0.05)
      (1..(width/2).ceil).each { |sw|
        if (distance(crop(sw,0,1,height).pixels,crop(sw+1,0,1,height).pixels, t)) > (height*0.6)
          return sw+1;
        end
      }
    end

    # distance measure for 2 columns of same height (width=1px)
    # calc color difference (ΔE, with RGB instead of LAB) of 2 pixel of same height
    # use treshold for color difference to ease results
    # sum of different pixel = distance
    def distance(c1, c2, t=0.05)
      d = 0
      (0..height-1).each_with_index { |c,i|
        score = Math.sqrt(
          (r(c1[i]) - r(c2[i])) ** 2 +
          (g(c1[i]) - g(c2[i])) ** 2 +
          (b(c1[i]) - b(c2[i])) ** 2
        ) / Math.sqrt(MAX ** 2 * 3)
        (score > t) ? d = d+1 : d
      }
      return d
    end

    # unshred image, takes shred_with as argument
    def unshred(sw=32)
      n = (width/sw) # number of shreds      
      cfs = Array.new # array for 1st columns
      cls = Array.new # array for last columns
      us = Array.new # array of already used shreds
      u = ChunkyPNG::Image.new(sw*2, height, ChunkyPNG::Color::TRANSPARENT)

      # crop 1st and last columns of a shred & add them to arrays for comparison
      (1..width).find_all{ |c| c % sw == 0 && c-1 > 0 }.each do |x|
        cls << crop(x-1,0,1,height).pixels
      end
      (0..width).find_all{ |c| c % sw == 0 && c != width }.each do |x|
        cfs << crop(x,0,1,height).pixels
      end

      # search for the pair with the smallest distance
      cd=height; bd=height; icl=-1; icf=-1;
      cls.each_with_index do |cl, i_cl|
        cfs.each_with_index do |cf, i_cf|
          if i_cl != i_cf
            cd = distance(cl, cf)
          end
          if cd < bd
            bd = cd; icf = i_cf; icl = i_cl;
          end
        end
      end
      u.replace!(crop(icl*sw, 0, sw, height), offset_x = 0)
      u.replace!(crop(icf*sw, 0, sw, height), offset_x = sw)
      us.push(icf, icl)

      # iterate over shreds for next best fitting pair
       until us.length == n
         r = ChunkyPNG::Image.new((sw*us.length)+sw, height, ChunkyPNG::Color::TRANSPARENT)
         dsr = Array.new; dsl = Array.new

         # search to the right for shred
         cfs.each_with_index do |cf, i_cf|
           if icl != i_cf and !us.include?(i_cf)
             dsr << [distance(cls[icl],cf),i_cf]
           end
         end
         nsr = dsr.sort_by{ |d| d[0] }.min

         # search to the left for shred
         cls.each_with_index do |cl, i_cl|
           if i_cl != icf and !us.include?(i_cl)
             dsl << [distance(cfs[icf],cl),i_cl]
           end
         end
         nsl = dsl.sort_by{ |d| d[0] }.min

         # add to the left or to the right??
         if nsl[0] < nsr[0]
           icf = nsl[1]
           r.replace!(crop(icf*sw, 0, sw, height), offset_x = 0)
           r.replace!(u.crop(0, 0, sw*us.length, height), offset_x = sw)
           u = r; us.push(nsl[1]);
         else
           icl = nsr[1]
           r.replace!(crop(icl*sw, 0, sw, height), offset_x = us.length*sw)
           r.replace!(u.crop(0, 0, sw*us.length, height), offset_x = 0)
           u = r; us.push(nsr[1]);
         end         
       end

      return r
    end

  end
end

# usage
image = ChunkyPNG::Image.from_file('sample_shredded.png')
image.unshred(image.shred_width).save('sample_unshredded.png')