Slow Python - what can be done?

[Peter Otten]

Jason wrote:

> My uber-abstraction is due to recently fleeing from C (abstraction
> made hard) and Lisp (no workable GUI stuff) so I'm stuck in the
> middle. Anyway, I appreciate the comments.

Not so fast. I think abstraction is *good* - only not well suited for the
inner loop of an image transformation algorithm.

Your warping seems to boil down to an affine transform, so whatever fancy
stuff you do as a preparation - with points, lines and all that nice
object-oriented stuff - you always end up with two equations

u = ax + by + c
v = dx + ey + f

and that's the only thing you should calculate repeatedly if you want
efficiency.
Using that recipe reduced calculation time for a small 350x223 pixel image
from 10 to 0.33 (0.2 with psyco) seconds. Here's the code, and I'm
confident you'll recognize it :-)

(no testing performed, but the images *do* look similar)

<warp.py>
""" call with
    --psyco to use psyco
    --old to use the original algorithm
    an image file as the *last* parameter
"""
from Tkinter import *
import Image
import ImageTk
from sys import exit
from math import sqrt

if "--psyco" in sys.argv:
    import psyco
    psyco.full()

class Point:
# A Point in the plane
    def __init__(self, int1, int2):
    # Constructor
        self.x = float(int1)
        self.y = float(int2)
    def __add__(self, other):
    # Add two points
        return Point(self.x + other.x, self.y + other.y)
    def __sub__(self, other):
    # Sub two points
        return Point(self.x - other.x, self.y - other.y)
    def __mul__(self, other):
    # Either mult by a constant or dot product
        if type(other) == float or type(other) == int:
            return Point(self.x*other, self.y*other)
        else:
            return self.x*other.x + self.y*other.y
    def __div__(self,other):
    # division by a constant
        if type(other) == float or type(other) == int:
            return Point(self.x/other, self.y/other)
    def __rmul__(self, other):
    # multiplication by a constant
        return Point(self.x*other, self.y*other)
    def __rdiv__(self, other):
    # division by a constant
        return Point(other/self.x, other/self.y)
    def __str__(self):
    # printing represenation
        return '(%s, %s)' % (self.x, self.y)
    def length(self):
    # regular length
        return sqrt(pow(self.x, 2) + pow(self.y, 2))
    def perpindicular(self):
    # 90 deg rotation
        return Point(self.y, -self.x)
    def to_tuple(self):
    # makes a tuple of ints
        return (int(self.x), int(self.y))


class WarpLine:
# The lines used to warp the image
    def __init__(self, x0, y0, x1, y1, id):
    # Constructor - just two points - id not used yet.
        self.id = 0
        self.point1 = Point(x0, y0)
        self.point2 = Point(x1, y1)
    def __str__(self):
    # Printing
        return '%s->%s' % (self.point1, self.point2)
    def length(self):
    # Segment length
        return sqrt(pow(self.point2.x-self.point1.x, 2) +
pow(self.point2.y-self.point1.y, 2))
    def getUV(self, point):
    # v = shortest distance of  point to line
    # u = the parameterization of the closest point from v
        diff = (self.point2 - self.point1)
        u = ((point - self.point1) * diff) / (diff * diff)

        v = ((point - self.point1) * diff.perpindicular()) / sqrt(diff *
diff)

        return u, v
    def transformPoint(self, line, point):
    # finds transform of point based on self and line
        diff = (line.point2 - line.point1)
        u, v = self.getUV(point)
        return line.point1 + u * diff  + (v * diff.perpindicular())
/sqrt(diff * diff)

class Picture:
    # A simple image class
    def __init__(self, file):
    # Load up an image
        self.data = Image.open(file)
    def in_bounds(self, pt):
    # is point in our bounds?
        if pt.x < 0 or pt.y < 0 or pt.x > self.data.size[0] - 1 or pt.y >
self.data.size[1] - 1:
            return 0
        else:
            return 1

    def coefficients(self, transform=None):
        orig = transform(Point(0, 0))
        p = transform(Point(1, 0)) - orig
        q = transform(Point(0, 1)) - orig
        a, b, c = p.x, q.x, orig.x
        d, e, f = p.y, q.y, orig.y
        return a, b, c, d, e, f

    def warp_new(self, source, line1, line2):
        """ psyco doesn't like lambdas, so I had to factor it out.
            Does anybody know why?
        """
        self._warp(source,
            *self.coefficients(lambda p: line1.transformPoint(line2, p)))

    def _warp(self, source, a, b, c, d, e, f):
        width, height = self.data.size
        dest = [0] * (width*height)
        src = source.data.getdata()
        yoff = 0
        for y in range(height):
            for x in range(width):
                u = int(a*x+b*y+c)
                v = int(d*x+e*y+f)
                if u >= 0 and u < width and v >= 0 and v < height:
                    dest[x + yoff] = src[u + v*width]
            yoff += width
        self.data.putdata(dest)

    def warp_old(self, source, line1, line2):
    # Do transformPoint on each pixel, save results
    # This is the slow part of the program
        dest = list(self.data.getdata())
        src = source.data.getdata()
        for x in range(0, self.data.size[0] - 1):
            for y in range(0, self.data.size[1] - 1):
                xy = line1.transformPoint(line2,Point(x,y)).to_tuple()

                if self.in_bounds(Point(xy[0], xy[1])):
                    dest[x + y*self.data.size[0]] = src[xy[0] +
xy[1]*self.data.size[0]]

                else:
                    dest[x + y*self.data.size[0]] = 0

        self.data.putdata(dest)
    def show(self):
    # show the image
        root = Tk()
        canvas = Canvas(root,
width=self.data.size[0],height=self.data.size[1])
        canvas.pack()
        photo = ImageTk.PhotoImage(self.data)
        disp = canvas.create_image(0, 0, anchor=NW, image=photo)
        mainloop()

if __name__ == "__main__":
    import time
    p1 = Picture(sys.argv[-1])
    line1 = WarpLine(0, 0, 200, 50, None)
    line2 = WarpLine(-100, 0, 150, 0, None)
    start = time.time()
    if "--old" in sys.argv:
        p1.warp_old(p1, line1, line2)
    else:
        p1.warp_new(p1, line1, line2)
    print time.time() - start
    p1.show()
</warp.py>

I'm sure there's room for improvement. E. g., you could devise a clipping
algorithm to not calculate all the black points. By the way, the Python
Imaging Library (PIL) has such a transform built in - but that might spoil
the fun.

Peter