"""
Implementation of Liquid Resizing <http://www.thegedanken.com/retarget/> in Python. 

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.

Copyright (C) 2007 Yew Jin, Lim

Things needed to improve:
1. Use ImageFilter <http://www.pythonware.com/library/pil/handbook/imagefilter.htm> instead of computing intensity gradient manually
2. Do not maipulate image with PIL directly (?)
3. Use scipy.weave to write tight inner loop
"""

from PIL import Image, ImageEnhance
import numpy
import random

# geez, the things that get passed off as infinity these days
INFINITY = 99999

def createData(im, targetWidth, targetHeight):
	width,height = im.size

	height = max(height,targetHeight)
	width = max(width,targetWidth)

	working = Image.new("RGB",(width,height))
	working.paste(im, (0,0,im.size[0],im.size[1]))
	
	inten = numpy.zeros((width,height),numpy.int32)
	xgradient = numpy.zeros((width,height),numpy.int32)
	ygradient = numpy.zeros((width,height),numpy.int32)		
	energy = numpy.zeros((width,height),numpy.int32)
	xmin = numpy.zeros((width,height),numpy.int32)
	ymin = numpy.zeros((width,height),numpy.int32)

	data = {}
	data["originalImage"] = im
	data["working"] = working
	data["intensity"] = inten
	data["targetHeight"] = targetHeight
	data["targetWidth"] = targetWidth
	data["xgradient"] = xgradient
	data["ygradient"] = ygradient
	data["energy"] = energy
	data["xmin"] = xmin
	data["ymin"] = ymin
	
	return data	

def init(data, width, height):
	inten = data["intensity"]
	im = data["working"]
	
	#ImageEnhance.Sharpness(ImageEnhance.Color(im).enhance(2.0)).enhance(2.0).convert("L").show()
	pix = ImageEnhance.Sharpness(ImageEnhance.Color(im).enhance(2.0)).enhance(2.0).convert("L").load()
	for x in xrange(width): 
		for y in xrange(height): 
			inten[x,y] = pix[x,y]

	xgradient = data["xgradient"]
	xgradient[1:width-1,:height] = inten[2:width,:height] - inten[0:width-2,:height]
	
	ygradient = data["ygradient"]
	ygradient[:width,1:height-1] = inten[:width,2:height] - inten[:width,0:height-2]
	
	energy = data["energy"]
	energy[:width,:height] = numpy.abs(xgradient[:width,:height]) + numpy.abs(ygradient[:width,:height])
	
def resize(filename, targetWidth, targetHeight):
	im = Image.open(filename)
	width, height = im.size
	
	data = createData(im, targetWidth, targetHeight)
	working = data["working"]
	workingPix = working.load()
	
	while targetWidth != width or targetHeight != height:
		working.show()
		init(data, width, height)
	
		energy = data["energy"]
	
		minVal = INFINITY
		minSeam = ""
	
		if targetWidth != width:
			xmin = data["xmin"]
			xmin[1:width-1,1:height] = 0
			xmin[1:width-1,0] = energy[1:width-1,0]

			xmin[0,:height] = INFINITY
			xmin[width-1,:height] = INFINITY

			for y in xrange(height-1):
				for x in xrange(width-2):
					xmin[x+1,y+1] = energy[x+1,y+1] + numpy.min(xmin[x:x+3,y])

			minIndex = numpy.argmin(xmin[1:width-1,height-1])
			minSeam = "W"
			minVal = xmin[minIndex+1,height-1]

		if targetHeight != height:
			ymin = data["ymin"]
			ymin[1:width,1:height-1] = 0
			ymin[0,1:height-1] = energy[0,1:height-1]

			ymin[:width,0] = INFINITY
			ymin[:width,height-1] = INFINITY
			
			for x in xrange(width-1):
				for y in xrange(height-2):
					ymin[x+1,y+1] = energy[x+1,y+1] + numpy.min(ymin[x,y:y+3])

			index = numpy.argmin(ymin[width-1,1:height-1])
			val = ymin[width-1,index+1]
			
			if val < minVal:
				minSeam = "H"
				minIndex = index
				minVal = val
			
		if minSeam == "W":
			seam = [(minIndex+1,height-1)]
			val = xmin[minIndex+1,height-1] - energy[minIndex+1,height-1]
			cx = minIndex+1
			
			for y in xrange(height-1):
				cy = height-2-y
				for d in xrange(3):
					nx = cx+d-1
					if xmin[nx,cy] == val:
						cx = nx
						seam.append((cx,cy))
						val -= energy[cx,cy]
						break
						
					if d == 2:
						print "Error while computing VERTICAL seam"

			if targetWidth < width:
				width -= 1
						
				for x,y in seam:
					for i in xrange(width-x): workingPix[x+i,y] = workingPix[x+i+1,y]
			else:
				width += 1
						
				for x,y in seam:
					for i in xrange(width-x-2): workingPix[width-1-i,y] = workingPix[width-2-i,y]
					workingPix[x+1,y] = ((workingPix[x,y][0]+workingPix[x+1,y][0])/2,(workingPix[x,y][1]+workingPix[x+1,y][1])/2,(workingPix[x,y][2]+workingPix[x+1,y][2])/2)
				
		elif minSeam == "H":
			seam = [(width-1,minIndex+1)]
			val = ymin[width-1,minIndex+1] - energy[width-1,minIndex+1]
			cy = minIndex+1
			
			for x in xrange(width-1):
				cx = width-2-x
				for d in xrange(3):
					ny = cy+d-1
					if ymin[cx,ny] == val:
						cy = ny
						seam.append((cx,cy))
						val -= energy[cx,cy]
						break
						
					if d == 2:
						print "Error while computing HORIZONTAL seam"

			if targetHeight < height:
				height -= 1

				for x,y in seam:
					for i in xrange(height-y): workingPix[x,y+i] = workingPix[x,y+i+1]
			else:
				height += 1

				for x,y in seam:
					for i in xrange(height-x-2): workingPix[x,height-1-i] = workingPix[x,height-2-i]
					workingPix[x,y+1] = ((workingPix[x,y][0]+workingPix[x,y+1][0])/2,(workingPix[x,y][1]+workingPix[x,y+1][1])/2,(workingPix[x,y][2]+workingPix[x,y+1][2])/2)
		else:
			print "ERROR: No minimum seam found"
			
	return working.crop((0,0,targetWidth,targetHeight))