#Copyright 2008 Sean Colyer
# This is Distributed under GPL V2.0
# Terms: http://www.gnu.org/licenses/gpl-2.0.html

import Image

MULTIPLIER = 2

#Passed in the image to work with and the number of columns already moved and shifted.
def findEnergy(img,shifted):
    imgSize = img.size
    imgOut = Image.new("L",(imgSize[0],imgSize[1]))
    pix = img.load()
    pixOut = imgOut.load()
    for x in range(imgSize[0]-shifted):
        for y in range(imgSize[1]):
            pixOut[x,y] = 0
            #calculate a simple derivative. look at points to the left and above and calculate pixel difference
            if(x > 0):
                pixOut[x,y] = pixOut[x,y] + abs((pix[x,y][0]-pix[x-1,y][0]))
                pixOut[x,y] = pixOut[x,y] + abs((pix[x,y][1]-pix[x-1,y][1]))
                pixOut[x,y] = pixOut[x,y] + abs((pix[x,y][2]-pix[x-1,y][2]))
            if(y > 0):
                pixOut[x,y] = pixOut[x,y] + abs((pix[x,y][0]-pix[x,y-1][0]))
                pixOut[x,y] = pixOut[x,y] + abs((pix[x,y][1]-pix[x,y-1][1]))
                pixOut[x,y] = pixOut[x,y] + abs((pix[x,y][2]-pix[x,y-1][2]))
            pixOut[x,y] *= MULTIPLIER
    return imgOut,pixOut

#pix is input "energy" picture and size is [x,y]
def findPaths(pix,size,shifted):
    global path
    global INFINITY
    #Use two for loops to calculate the values for each point. Since value for x,y depends on values in y-1 row, make sure y is calculated from 0 up
    for y in range(size[1]):
        for x in range(size[0]-shifted):
            if y > 0:
                total0,total1,total2 = INFINITY,INFINITY,INFINITY
                ##pass by reference issue in total?
                if x > 0:
                    total0 = path[x-1][y-1][1]
                if x < size[0] - 1 - shifted:
                    total1 = path[x+1][y-1][1]
                total2 = path[x][y-1][1]

                ## Below is loops to determine which is the minimum for a given point. This can be made more efficient                
                if total0 is not INFINITY and total0 <= total1 and total0 <= total2:
                    path[x][y] = -1,pix[x,y]+total0
                elif total1 is not INFINITY and total1 <= total0 and total1 <= total2:
                    path[x][y] = 1,pix[x,y]+total1
                elif total2 is not INFINITY and total2 <= total1 and total2 <= total0:
                    path[x][y] = 0,pix[x,y]+total2
            else:
                ##Top row, beginning of path
                path[x][y] = 99,pix[x,y]

def findRemoval(path,size):
    minVal = INFINITY
    minPos = -1
    for x in range(size[0]):
        if path[x][size[1]-1][1] < minVal:
            #print x
            minVal = path[x][size[1]-1][1]
            minPos = x
    return minPos

def remove(img,pos,path):
    nextX = pos
    for n in range(sizeY):
        img[nextX,sizeY-n-1] = (255,255,255)
        shift(nextX,sizeY-n-1,img)
        nextShift = path[nextX][sizeY-n-1][0]
        path[nextX][sizeY-n-1] = path[nextX][sizeY-n-1][0],INFINITY
        shift(nextX,sizeY-n-1)
        nextX = nextX + nextShift
    return img, path

#shift can be used to shift any array. Point (x,y) is shifted to the end of its row (sizeX,y)
def shift(x,y,img = -1):
    if img is -1:
        global path
        global INFINITY
        for n in range(len(path) - x - 1):
            path[n+x][y] = path[n+x+1][y]
        path[n+x+1][y] = path[n+x+1][y][0],INFINITY
    else:
        initVal = img[x,y]
        for n in range (len(path)-x-1):
            img[n+x,y] = img[n+x+1,y]
        img[sizeX-1,y] = initVal
        return img

INFINITY = 999999999

imgFile = raw_input("Input Picture: ")
factor = input("Factor to remove? 2 would be 1/2 the picture, 4 would remove 1/4, etc..: ")
img = Image.open(imgFile)
pixMatrix = img.load()
path = [ [-1 for y in range(img.size[1])] for x in range(img.size[0])]
#img.show()
pixEnergy = img.load()
sizeX,sizeY = img.size[0],img.size[1]
for shifted in range(int(sizeX/factor)):
    print "Calculating and removing path: " +str(shifted+1) + "/" + str(sizeX/factor)
    imgEnergy,pixEnergy = findEnergy(img,shifted)
    findPaths(pixEnergy,imgEnergy.size,shifted)
    pos = findRemoval(path,imgEnergy.size)
    pixMatrix, path = remove(pixMatrix,pos,path)
img.save("out"+imgFile,quality=99)