seam carvin'

convolve.py

from math import sqrt
import random,time
import profile

random.seed(1)

def bellman_ford(edges):

        numRows = len(edges)
	numCols = len(edges[0])
        OPT = dict(( (len(edges)-1,x),edges[-1][x]) for x in xrange(len(edges[-1])))
        opt = dict(( (len(edges)-1,x),None) for x in xrange(len(edges[-1])))
        for y in xrange(numRows-2,-1,-1):
                for x in xrange(numCols):
                        optNbr = None
                        optPath = [(y,x)]
                        optVal = float("inf")
                        nbrs = [(y+1,x2) for x2 in xrange(x-1,x+2) if x2<numCols and x2>=0 ]
                        for nbr in nbrs:
                                if OPT[nbr] < optVal:
                                        optVal = OPT[nbr]
                                        optNbr = nbr
                        OPT[(y,x)] = optVal+edges[y][x]
                        opt[(y,x)]=optNbr

        minKey = min([key for key in OPT if key[0]==0],key=OPT.get)
        path = []
        conductor = minKey
        while(conductor):
                path.append(conductor)
                conductor = opt[conductor]
        return path,OPT[minKey]                      

def doubleConvolve2DOriginal(matrix,kernel1,kernel2):

        numRows = len(matrix)
        numCols = len(matrix[0])
        numKernelRows = len(kernel1)
        numKernelCols = len(kernel1[0])
        
        yradius = (len(kernel1)-1)/2
        xradius = (len(kernel1[0])-1)/2
        
        padded = padMatrix(matrix,xradius,yradius)
        convolvedRows = []
        for row in xrange(yradius,numRows+yradius):
                convolvedRow = []
                for col in xrange(xradius,numCols+xradius):
                        totalSum1 = 0
                        totalSum2 = 0
                        for kernelRow in xrange(numKernelRows):
                                for kernelCol in xrange(numKernelCols):
                                        totalSum1+= kernel1[kernelRow][kernelCol] * padded[row+kernelRow-yradius][col+kernelCol-xradius]
                                        totalSum2+= kernel2[kernelRow][kernelCol] * padded[row+kernelRow-yradius][col+kernelCol-xradius]
                        sobeled_pixel = ((totalSum1*totalSum1+totalSum2*totalSum2)**(0.5))
                        convolvedRow.append(sobeled_pixel)
                convolvedRows.append(convolvedRow)

        convolved = [row for row in convolvedRows]
        
        del padded
        return convolved

def doubleConvolve2D(matrix,kernel1,kernel2):

        numRows = len(matrix)
        numCols = len(matrix[0])
        numKernelRows = len(kernel1)
        numKernelCols = len(kernel1[0])
        
        yradius = (len(kernel1)-1)/2
        xradius = (len(kernel1[0])-1)/2
        
        padded = padMatrix(matrix,xradius,yradius)
        def getPixelInRow(row,xradius,padwidth):
                while xradius < padwidth:
                        col = xradius
                        xradius += 1
                        totalSum1 = 0
                        totalSum2 = 0
                        for kernelRow in xrange(numKernelRows):
                                for kernelCol in xrange(numKernelCols):
                                        totalSum1+= kernel1[kernelRow][kernelCol] * padded[row+kernelRow-yradius][col+kernelCol-xradius]
                                        totalSum2+= kernel2[kernelRow][kernelCol] * padded[row+kernelRow-yradius][col+kernelCol-xradius]
                        sobeled_pixel = ((totalSum1*totalSum1+totalSum2*totalSum2)**(0.5))
                        yield sobeled_pixel

        def getConvolvedRow(yradius,padheight):
                while yradius < padheight:
                        row = yradius
                        yradius += 1
                        # i think ths guy can be converted to a generator comprehension and then it'll get rid
                        # of the last memory overhead, but i don't know how to write the test to ensure equality
                        convolvedRow = [pixel for pixel in getPixelInRow(row,xradius,numCols+xradius)]
                        # the matrix should be still be consumable by iteration, 
                        # it just wouldn't exist as a structure with lookups anymore
                        yield convolvedRow

        convolvedRows = (col for col in getConvolvedRow(yradius,numRows+yradius))
        convolved = [row for row in convolvedRows]
        
        return convolved

def sobel(matrix):      
        xKernel = [[-1,0,1],[-2,0,2],[-1,0,1]]
        yKernel = [[-1,-2,-1],[0,0,0],[1,2,1]]
        edges = doubleConvolve2D(matrix,xKernel,yKernel)
        #assert edges == doubleConvolve2DOriginal(matrix,xKernel,yKernel)
        return edges



def Matrix(numRows,numCols,val=0,rand=False):
        if not rand:
                return [ [val for j in xrange(numCols)] for i in range(numRows)]
        else:
                return [ [random.randint(0,3) for j in xrange(numCols)] for i in range(numRows)]

def padMatrix(matrix,xpad,ypad):

        padded = []
        topRow = [matrix[0][0] for i in xrange(xpad)]+matrix[0]+[matrix[0][-1] for i in range(xpad)]
        for i in xrange(ypad):
                padded.append(topRow)
        for row in matrix:
                paddedRow = [row[0] for i in xrange(xpad)]+row+[row[-1] for i in range(xpad)]
                padded.append(paddedRow)
        bottomRow = [matrix[-1][0] for i in xrange(xpad)]+matrix[-1]+[matrix[-1][-1] for i in range(xpad)]
        for i in xrange(ypad):
                padded.append(bottomRow)
        return padded


def bellman_ford_test():
	
        m1 = Matrix(640,480)
        #m1 = Matrix(160,120)
        t1 = time.time()
	#m2 = sobel(m1)
	profile.runctx("sobel(m1)",globals(),{"m1":m1})
	t2 = time.time()
        #profile.runctx("bellman_ford(m1)",globals(),{"m1":m1})
#	bellman_ford(m2)
	t3 = time.time()

	print "Sobel:",t2-t1,"s"
	print "Bellman-Ford:",t3-t2,"s"

if __name__=="__main__":
        bellman_ford_test()