#!/usr/bin/env python
 
import Image
import ImageEnhance
import logging
import math
 
edge_buffer=25
black_threshold=96
search_indicator=None
 
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 
class FarsideFixError(Exception): pass
class FarsideFixFindEdgeError(FarsideFixError): pass
 
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 
def PixelValue(color):
	return sum(color)/3
 
def FindEdge(pixels, start_x, start_y, inc_x, inc_y):
	x=start_x
	y=start_y
 
	for i in xrange(999):
		try:
			if PixelValue(pixels[x, y]) < black_threshold:
				return (x, y)
			if search_indicator:
				pixels[x, y]=search_indicator
		except IndexError:
			raise FarsideFixFindEdgeError
		x+=inc_x
		y+=inc_y
 
	raise FarsideFixFindEdgeError
 
def FindCorner(pixels, start_x, start_y, inc_x, inc_y, search_x, search_y):
	try:
		corner=None
		x=start_x
		y=start_y
		hit=None
		last_hit=None
		while True:
			hit=FindEdge(pixels, x, y, inc_x, inc_y)
 
			if last_hit:
				moved=( (hit[0]-last_hit[0])*inc_x, (hit[1]-last_hit[1])*inc_y )
				if moved[0]<-5 or moved[1]<-5:
					# We moved "back" too much, probably hit an errant dot,
					# ignore this hit.
					hit=last_hit
				elif moved[0]>10 or moved[1]>10:
					# We jumped "forward", so we just passed the corner.
					break
 
			last_hit=hit
			x+=search_x
			y+=search_y
	except FarsideFixFindEdgeError:
		if not last_hit:
			raise
 
	return last_hit
 
def PointDistance(a, b):
	return math.sqrt( (a[0]-b[0])**2 + (a[1]-b[1])**2 )
 
class Line(object):
	def __init__(self, lower_point, upper_point):
		self.lower_point=lower_point
		self.upper_point=upper_point
		self.angle=math.atan2(
			(upper_point[1]-lower_point[1]),
			(upper_point[0]-lower_point[0])
			)
 
	def x_at_y(self, y):
		width=float(self.lower_point[0]-self.upper_point[0])
		height=float(self.lower_point[1]-self.upper_point[1])
		rise_rate=float(width)/height
		return self.lower_point[0] + ( rise_rate * (y-self.lower_point[1]) )
 
	def extend_by(self, distance):
		return (
			int(self.lower_point[0] - math.cos(self.angle)*distance),
			int(self.lower_point[1] - math.sin(self.angle)*distance))
 
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 
def FixImage(filename_in):
	global search_indicator
 
	try:
		image=Image.open(filename_in)
		pixels=image.load()
		(width, height)=image.size
 
		# Chop off the non-comic space on the right.
		top_right=FindCorner(pixels, width/2, 0, 1, 1, 1, 0)
		right=top_right[0]+edge_buffer*3
		image=image.crop( (0, 0, right, height) )
 
		pixels=image.load()
		(width, height)=image.size
 
		# Find the other edges of the comic.
		left=width
		for y in xrange(0, height, height/50):
			try:
				point=FindEdge(pixels, 0, y, 1, 0)
				if point[0]<left: left=point[0]
			except FarsideFixError:
				pass
		top=height
		for x in xrange(left, width, width/50):
			try:
				point=FindEdge(pixels, x, 0, 0, 1)
				if point[1]<top: top=point[1]
			except FarsideFixError:
				pass
		bottom=0
		for x in xrange(left, width, width/50):
			try:
				point=FindEdge(pixels, x, height-2, 0, -1)
				if point[1]>bottom: bottom=point[1]
			except FarsideFixError:
				pass
 
		# Add some buffer space to these edges.
		left=max(0, left-edge_buffer)
		top=max(0, top-edge_buffer)
		bottom=min(height-2, bottom+edge_buffer)
 
		# Crop off the chaff.
		image=image.crop( (left, top, width, bottom) )
 
		pixels=image.load()
		(width, height)=image.size
 
		# Paste this cropped image into a blank one (guaranteed border space).
		matte=Image.new(
			"RGB",
			(width+edge_buffer*2, height+edge_buffer*2),
			(255, 255, 255))
		matte.paste(image, (edge_buffer, edge_buffer))
		image=matte
 
		pixels=image.load()
		(width, height)=image.size
 
		# Find the corners of the box.
		top_left=FindCorner(pixels, width/3, 0, -1, 1, -1, 0)
		top_right=FindCorner(pixels, width*2/3, 0, 1, 1, 1, 0)
		bottom_left=FindCorner(pixels, 0, height/2, 1, 1, 0, 1)
		bottom_right=FindCorner(pixels, width-1, height*2/3, -1, 1, 0, 1)
 
		# Add a buffer from these found edges, within the image.
		top_left=(top_left[0]-edge_buffer, top_left[1]-edge_buffer)
		top_right=(top_right[0]+edge_buffer, top_right[1]-edge_buffer)
		bottom_left=(bottom_left[0]-edge_buffer, bottom_left[1]+edge_buffer)
		bottom_right=(bottom_right[0]+edge_buffer, bottom_right[1]+edge_buffer)
 
		# Extend them down to include the caption.
		left_line=Line(bottom_left, top_left)
		right_line=Line(bottom_right, top_right)
 
		# Find which side is lower, extend that side's line down to the bottom,
		# then extend the other side by the same distance.
		if bottom_right[1]>bottom_left[1]:
			intersect=right_line.x_at_y(height-2)
			bottom_right_extra=(intersect, height-2)
			distance=PointDistance(bottom_right, bottom_right_extra)
			bottom_left_extra=left_line.extend_by(distance)
		else:
			intersect=left_line.x_at_y(height-2)
			bottom_left_extra=(intersect, height-2)
			distance=PointDistance(bottom_left, bottom_left_extra)
			bottom_right_extra=right_line.extend_by(distance)
 
		# Transform these corner points into a straight rectangle.
		new_size=(int(PointDistance(top_left, top_right)),
			int(PointDistance(top_left, bottom_left_extra)))
		matte=Image.new("RGB", new_size, (255, 255, 255))
		image=image.convert("RGBA").transform(
			new_size,
			Image.QUAD,
			top_left+bottom_left_extra+bottom_right_extra+top_right,
			Image.BICUBIC)
		matte.paste(image, image)
		image=matte
 
		pixels=image.load()
		(width, height)=image.size
 
		# Find the real bottom.  Many samples, because it is likely sparse text.
		bottom=0
		for x in xrange(100, width, width/30):
			try:
				(unused, bottom_tmp)=FindEdge(pixels, x, height-2, 0, -1)
				bottom=max(bottom, bottom_tmp)
			except FarsideFixFindEdgeError:
				pass
		bottom=min(height-1, bottom+edge_buffer)
		image=image.crop((0, 0, width-1, bottom))
	except FarsideFixError, e:
		return (False, e)
 
	image.load()
	return (True, image)
 
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 
if __name__=="__main__":
	from glob import glob
	import os
	import sys
 
	if len(sys.argv)>1:
		filenames=sys.argv[1:]
	else:
		filenames=glob('in/*.jpg')
		filenames.sort()
 
	for filename_in in filenames:
		filename_out='out'+filename_in[2:]
 
		if os.path.exists(filename_out):
			continue
 
		print "Processing %s ..." % filename_in,
 
		result=FixImage(filename_in)
		if result[0]:
			result[1].save(filename_out)
			print "OK!"
		else:
			print "Fail! ", result[1]