448,652 Members | 1,756 Online Need help? Post your question and get tips & solutions from a community of 448,652 IT Pros & Developers. It's quick & easy.

# Slow Python - what can be done?

 P: n/a Hey, I'm an experience programmer but new to Python. I'm doing a simple implementation of a field morphing techinique due to Beier and Neely (1992) and I have the simple case working in Python 2.3 - but it's REALLY slow. Basically, you specify two directed line segments in the coordinate system of a raster image and use the difference between those two lines to transform the image. for a 400 x 600 image, python takes about 30 seconds to run the algorithm. This seems way to slow - I would expect it to run in a matter of a few seconds. Here's the code: what should I do to speed things up? I know I'm going to get a "do it in C/make a C extension" but that defeats the purpose: I'd like to know what Python can do here. Thanks for your help. from Tkinter import * import Image import ImageTk from sys import exit from math import sqrt 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 - 1 or pt.y > self.data.size - 1: return 0 else: return 1 def warp(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 - 1): for y in range(0, self.data.size - 1): xy = line1.transformPoint(line2, Point(x,y)).to_tuple() if self.in_bounds(Point(xy, xy)): dest[x + y*self.data.size] = src[xy + xy*self.data.size] else: dest[x + y*self.data.size] = 0 self.data.putdata(dest) def show(self): # show the image root = Tk() canvas = Canvas(root, width=self.data.size, height=self.data.size) canvas.pack() photo = ImageTk.PhotoImage(self.data) disp = canvas.create_image(0, 0, anchor=NW, image=photo) mainloop() Jul 18 '05 #1
16 Replies

 P: n/a In article <48**************************@posting.google.com >, Jason wrote: Basically, you specify two directed line segments in the coordinate system of a raster image and use the difference between those two lines to transform the image. # 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 - 1): for y in range(0, self.data.size - 1): "For loops" are evil ;-) Though I'm not familiar with your algorithm, you should investigate the Numeric/numarray package, which is designed to do lots of number crunching fast. If you can cast your problem into good Numeric form, you'll see a speedup of a factor of hundreds. Mike -- Dr. Michael Ressler Research Scientist, Astrophysics Research Element, Jet Propulsion Laboratory Email: re*****@cheetah.jpl.nasa.gov Phone: (818)354-5576 "A bad night at the telescope is still better than the best day at the office." Jul 18 '05 #2

 P: n/a On 18 Mar 2004 09:43:19 -0800, se******@rocknroll.umcs.maine.edu (Jason) wrote: Hey,I'm an experience programmer but new to Python. I'm doing a simpleimplementation of a field morphing techinique due to Beier and Neely(1992) and I have the simple case working in Python 2.3 - but it'sREALLY slow. My impression is that you should avoid the Point class. It's a pretty trivial class, but each time it is instantiated or an instance destroyed you get some overhead. Do that enough times and you get speed issues. If you can live with tuples and non-member functions, that may be some help. Also, for the picture data itself, possibly you should look at the numarray library. I haven't used it myself, but I suspect that it will have lower overheads than a standard Python list. http://www.pfdubois.com/numpy/ You also seem to be doing too much avoidable work in your inner loop. For instance, you could swap your x and y loops, and calculate things like y*self.data.size once per row (rather than for every single pixel). I imagine there are also aspects of the transform calculation that could be done once per row to save time, though I haven't looked that closely at what you are doing. -- Steve Horne steve at ninereeds dot fsnet dot co dot uk Jul 18 '05 #3

 P: n/a On Thu, 18 Mar 2004 09:43:19 -0800, Jason wrote: Hey, I'm an experience programmer but new to Python. I'm doing a simple implementation of a field morphing techinique due to Beier and Neely (1992) and I have the simple case working in Python 2.3 - but it's REALLY slow. Basically, you specify two directed line segments in the coordinate system of a raster image and use the difference between those two lines to transform the image. for a 400 x 600 image, python takes about 30 seconds to run the algorithm. This seems way to slow - I would expect it to run in a matter of a few seconds. Here's the code: what should I do to speed things up? I know I'm going to get a "do it in C/make a C extension" but that defeats the purpose: I'd like to know what Python can do here. Thanks for your help. [SNIP] I can't try your prog because I have not Tkinter, but I think this app would gain a lot in performances using psyco. http://psyco.sourceforge.net/ <-- home http://psyco.sourceforge.net/psycoguide/index.html <-- doc The simplest way to use psyco is putting import psyco psyco.full() after your imports. Ciao, Riccardo -- -=Riccardo Galli=- _,e. s~ `` ~@. ideralis Programs .. ol `**~ http://www.sideralis.net Jul 18 '05 #5

 P: n/a Jason> Here's the code: what should I do to speed things up? Without considering your code, two suggestions come to mind. One, look at PIL or Numeric. Perhaps one of them has a more efficient C-based Image class or array class will will help. Two, if you're running on an Intel Pentium-type processor (Windows or Linux), take a look at psyco. http://www.pythonware.com/products/pil/ http://psyco.sourceforge.net/ If you don't have Intel hardware, you might consider PyInline or SciPy's weave tool to easily inline bits of C code into your Python. A quick look at your code suggests that you use a fair amount of abstraction (nothing wrong with that), then throw it away: xy = line1.transformPoint(line2, Point(x,y)).to_tuple() if self.in_bounds(Point(xy, xy)): ... In the above, you instantiate a Point using x and y, then pass it to transformPoint() which returns new Point. You immediately discard that point by calling .to_tuple(), then in the next statement create yet another Point with those same coordinates. Why not just have transformPoint accept a tuple and return a tuple or at least save the transformed Point for later use? Skip Jul 18 '05 #6

 P: n/a Hello Jason, I'm an experience programmer but new to Python. I'm doing a simple implementation of a field morphing techinique due to Beier and Neely (1992) and I have the simple case working in Python 2.3 - but it's REALLY slow. Did you use hotshot to find *where* you spend the time? class Point: ... I've found out the Python's faster with native types. One thing is to use a tuple for the point and have functions like point_sub(p1, p2) You can try and use Psyco, in several cases it gives a very big speedup. HTH. Miki Jul 18 '05 #7

 P: n/a Thanks for the help - I wasn't aware of the profilers avilable for Python. 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. Jason Jul 18 '05 #8

 P: n/a se******@rocknroll.umcs.maine.edu (Jason) wrote in message news:<48**************************@posting.google. com>... Hey, I'm an experience programmer but new to Python. I'm doing a simple implementation of a field morphing techinique due to Beier and Neely (1992) and I have the simple case working in Python 2.3 - but it's REALLY slow. Basically, you specify two directed line segments in the coordinate system of a raster image and use the difference between those two lines to transform the image. for a 400 x 600 image, python takes about 30 seconds to run the algorithm. This seems way to slow - I would expect it to run in a matter of a few seconds. Here's the code: what should I do to speed things up? I know I'm going to get a "do it in C/make a C extension" but that defeats the purpose: I'd like to know what Python can do here. If you can't go with the mentioned compilers (psycho) or libraries there is nothing else then writing C. Python is best at glueing code together. Writing numerical or highly mathematical algorithms in python will always result in 10000% overhead. Maybe you want to look at GNU eiffel (smarteiffel). Remember there is no silver bullet ! Jul 18 '05 #9

 P: n/a se******@rocknroll.umcs.maine.edu (Jason) writes: Thanks for the help - I wasn't aware of the profilers avilable for Python. You might abuse complex numbers for points (the lisp faq recommends doing this), maybe it speeds things up. You might even save time (I did not try this, but hardware operations might be cheaper than Python procedure calls) by doing complex products and ignoring the imaginary part of the result just to get quickly at stuff like p1.x*p2.x-p1.y*p2.y. If you come from the lisp world anyway, you might try STk or stklos (schemes with OO and Tk (or GTK) bindings). Ralf -- GS d->? s:++>+++ a+ C++++ UL+++ UH++ P++ L++ E+++ W- N++ o-- K- w--- !O M- V- PS+>++ PE Y+>++ PGP+ !t !5 !X !R !tv b+++ DI+++ D? G+ e++++ h+ r? y? Jul 18 '05 #10

 P: n/a 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) """ 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 - 1 or pt.y > self.data.size - 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 =  * (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 - 1): for y in range(0, self.data.size - 1): xy = line1.transformPoint(line2,Point(x,y)).to_tuple() if self.in_bounds(Point(xy, xy)): dest[x + y*self.data.size] = src[xy + xy*self.data.size] else: dest[x + y*self.data.size] = 0 self.data.putdata(dest) def show(self): # show the image root = Tk() canvas = Canvas(root, width=self.data.size,height=self.data.size) 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() 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 Jul 18 '05 #11

 P: n/a It's affine for the one-line-pair case, but the full algorithm actually uses n line pairs to describe a nonlinear transformation. Since the transformations are weighted for each pair, the matrix solution doesn't cut it for the general case. Of course, since I didn't mention it, you wouldn't have known that - sorry. It should be obvious now why I want the speed tho - doing that transformation n times and then adding in some extra sums and a division will only make things slower. Jason Jul 18 '05 #12

 P: n/a Jason Sewall wrote: It's affine for the one-line-pair case, but the full algorithm actually uses n line pairs to describe a nonlinear transformation. Since the Would you care to post a small driver program (if feasible)? I'd like to try the "complex numbers as points" approach on it. transformations are weighted for each pair, the matrix solution doesn't cut it for the general case. Of course, since I didn't mention it, you wouldn't have known that - sorry. No problem. Peter Jul 18 '05 #13

 P: n/a Riccardo Galli wrote: I can't try your prog because I have not Tkinter, Isn't Tkinter a standard module? Jul 18 '05 #14

 P: n/a I was out of town for a few days and thus had to rely on Google's only okay support for news. When I get a moment, I'll be working on a real-deal version of the algorithm and worry about optimization. I understand your suggestion about the complex number. It's probably a good idea and it is reminiscent of quaternions (although in the plane). I'll let you know, Jason Peter Otten wrote: Jason Sewall wrote:It's affine for the one-line-pair case, but the full algorithm actuallyuses n line pairs to describe a nonlinear transformation. Since the Would you care to post a small driver program (if feasible)? I'd like to try the "complex numbers as points" approach on it.transformations are weighted for each pair, the matrix solution doesn'tcut it for the general case.Of course, since I didn't mention it, you wouldn't have known that -sorry. No problem. Peter Jul 18 '05 #15 