Instagram Challenge - The Unshredder
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.
Without further ado, je vous présente le code:
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')
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.
$${√{({r_{c1}-r_{c2}})^2+({g_{c1}-g_{c2}})^2+({b_{c1}-b_{c2}})^2}}/{√{255^2*3}}$$
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.
Related stuff
This challenge got into about CV algorithms in general, so I searched for some code algorithms around the web using ChunkyPNG and Ruby:
- Content-aware image cropping with ChunkyPNG
- Pixelizing images with ChunkyPNG
- Line detections with Hough Transformation
- Edge detection with the Sobel operator in Ruby
- Comparing images and creating image diffs
And finally this awesome solution for the Instagram challenge in MATLAB by wpalfi:
ws=32;
img=im2double(imread('sample.png'));
hsv=rgb2hsv(img); %convert to hsv
h=size(img,1);
w=size(img,2);
n=w/ws;
%linearize and normalize columns
v=hsv(:,:,1:3);
v=permute(v,[1 3 2]);
v=reshape(v,[h*size(v,2) w]);
m=mean(v,1);
v=v-m(ones(1,size(v,1)),:,:);
v=normc(v);
%multiply first and last columns (correlation matrix)
m=v(:,ws:ws:end)'*v(:,1:ws:end);
m(logical(eye(size(m))))=0; %no self-reference
%find best correlations
[ms ix]=sort(m,2);
next=ix(:,end)'; %index
nextp=ms(:,end)'; %correlation
%min correlation is last slice (no next slice)
[dummy ind]=min(nextp);
ord(n)=ind;
for i=n-1:-1:1
ord(i)=find(next==ord(i+1),1);
end
%repair image
sl=reshape(img,[h ws n 3]);
slo=sl(:,:,ord,:);
imgr=reshape(slo,size(img));
imwrite(imgr,'sample_unshredded.png');