#!/usr/bin/python

from optparse import OptionParser
from os.path import splitext
from math import pow
from math import sqrt
from PIL import Image
from PIL import ImageChops

parser = OptionParser()
(options, args) = parser.parse_args()

if len(args) != 1:
  print "requires one image file as input"
  exit()

inputfile = args[0]
outputfile = splitext(args[0])[0] + "_unshredded" + splitext(args[0])[1]

image = Image.open(inputfile)
unshredded = Image.new("RGBA", image.size)

width, height = image.size

def calc_distance_avg(diff_image):
  sum = 0
  diff_data = diff_image.getdata()
  for pixel in diff_data:
    distance = sqrt(pow(pixel[0], 2) + pow(pixel[1], 2) + pow(pixel[2], 2))
    sum += distance
  return sum / len(diff_data)

def find_shred_width():
  found = False
  index = 1
  column1 = image.crop((index - 1, 0, index, height))
  column2 = image.crop((index, 0, index + 1, height))
  diff = ImageChops.difference(column1, column2)
  avg1 = 0
  avg2 = calc_distance_avg(diff)
  threshold = 20

  while found == False:
    index += 1
    column1 = column2
    column2 = image.crop((index, 0, index + 1, height))
    diff = ImageChops.difference(column1, column2)
    avg1 = avg2
    avg2 = calc_distance_avg(diff)

    if avg1 < avg2 - threshold:
      found = True
      #print index, avg1, avg2

  return index

shred_width = find_shred_width()
shreds = width / shred_width

shredded_list = range(0, shreds)
unshredded_list = [0]
#print unshredded_list

def find_matching_shreds():
  left_distance_avg, right_distance_avg = 100000000, 100000000
  left_shred, right_shred = unshredded_list[0], unshredded_list[len(unshredded_list) - 1]
  left_x, right_x = left_shred * shred_width, right_shred * shred_width + shred_width - 1
  left_edge = image.crop((left_x, 0, left_x + 1, height))
  right_edge = image.crop((right_x, 0, right_x + 1, height))

  #for shred in shredded_list:
  for shred in range(0, shreds):
    shred_right_x = shred * shred_width + shred_width - 1
    shred_right_edge = image.crop((shred_right_x, 0, shred_right_x + 1, height))
    diff_image = ImageChops.difference(shred_right_edge, left_edge)
    distance_avg = calc_distance_avg(diff_image)
    if distance_avg < left_distance_avg:
      left_shred = shred
      left_distance_avg = distance_avg

    shred_left_x = shred * shred_width
    shred_left_edge = image.crop((shred_left_x, 0, shred_left_x + 1, height))
    diff_image = ImageChops.difference(right_edge, shred_left_edge)
    distance_avg = calc_distance_avg(diff_image)
    if distance_avg < right_distance_avg:
      right_shred = shred
      right_distance_avg = distance_avg

  return (left_shred, right_shred)

while len(unshredded_list) < shreds:
  matching_shreds = find_matching_shreds()
  if matching_shreds[0] != unshredded_list[0]:
    unshredded_list.insert(0, matching_shreds[0])
  if matching_shreds[1] != unshredded_list[len(unshredded_list) - 1]:
    unshredded_list.append(matching_shreds[1])
  #print unshredded_list

for i, shred_index in enumerate(unshredded_list):
  shred_x1, shred_y1 = shred_width * shred_index, 0
  shred_x2, shred_y2 = shred_x1 + shred_width, height
  region = image.crop((shred_x1, shred_y1, shred_x2, shred_y2))
  unshredded.paste(region, (shred_width * i, 0))

unshredded.save(outputfile)