Slow Python - what can be done? LONG, CODE

Jason Sewall me at me.com
Wed Mar 24 16:32:42 CET 2004


WARNING: Long post, contains code
Hey everyone -

I've found time to make a few different versions of that slow image 
processing app that I was working on. I chucked abstraction out the 
window and made a built-in-type-only implementation that was ugly as sin 
(reminded me of assembly code, if you can believe it) but it was about 
5-6x faster.

That still wasn't enough for me so I figured out how to do C extensions 
and wrote a module in C for the transforms. That's noticably faster, but 
I'm sad to say that there's a bit of overhead in the argument grabs and 
returns that slows it down. Anyway, it's not too bad.

For the hell of it, here's the app, without much in the way of comments 
or info. Sorry, too bad. The algorithm is due to Beier and Neely 1992 
but the code is mine.


from Tkinter import *
import Image
import ImageTk
from math import sqrt
import _warp
import psyco
psyco.full()

class WarpGUI(Frame):
     def __init__(self, parent=None):
         Frame.__init__(self, parent)
         self.pack()
         self.lines = list()
         self.lcanv = WarpCanvas(self, "", 0)
        # self.mcanv = WarpCanvas(self, "")
         self.rcanv = WarpCanvas(self, "", 1)
         self.alpha = Scale(self, label='a',
               from_=0.01,
               to=2.0,
               orient='horizontal',
               tickinterval=0.05,
               resolution=0.01,
               length=1200,
               showvalue=YES)
         self.alpha.pack(side=TOP)
         self.beta = Scale(self, label='b',
               from_=0.0,
               to=5.0,
               orient='horizontal',
               tickinterval=0.1,
               resolution=0.1,
               length=1200,
               showvalue=YES)
         self.beta.pack(side=TOP)
         self.rho = Scale(self, label='rho',
               from_=0.0,
               to=5.0,
               orient='horizontal',
               tickinterval=0.1,
               resolution=0.1,
               length=1200,
               showvalue=YES)
         self.rho.pack(side=TOP)

         self.lcanv.pack(side=LEFT)
        # self.mcanv.pack(side=LEFT)
         self.rcanv.pack(side=LEFT)
         self.bind_all('<Button-2>', lambda event: 
self.lcanv.warp(self.rcanv, self.lines, self.alpha.get(), 
self.beta.get(), self.rho.get()))
     def add_lines(self, x0, y0, x1, y1):
         id1 = self.lcanv.add_line(x0, y0, x1, y1)
         id2 = self.rcanv.add_line(x0, y0, x1, y1)
         self.lines.append(( [float(x0), float(y0), float(x1), 
float(y1), id1], [float(x0), float(y0), float(x1), float(y1), id2]))
         self.lcanv.make_bindings()
         self.rcanv.make_bindings()
     def highlight_line(self, lineID):
         self.lcanv.highlight_line(lineID)
         self.rcanv.highlight_line(lineID)
     def unhighlight_line(self, lineID):
         self.lcanv.unhighlight_line(lineID)
         self.rcanv.unhighlight_line(lineID)
     def get_line(self, lineID, side):
         for item in self.lines:
             if item[side][4] == lineID:
                 return item[side]


class WarpCanvas(Canvas):
     def __init__(self, parent=None, file=None, side=None):
         Canvas.__init__(self, parent)
         self.parent = parent
         self.current_line = list()
         self.side = side
         self.make_bindings()
         if not file == None:
             self.image_data = Image.open(file)
             self.config(width=self.image_data.size[0], 
height=self.image_data.size[1])
             self.image_tk = ImageTk.PhotoImage(self.image_data)
             self.image_id = self.create_image(0, 0, 
image=self.image_tk, anchor=NW)
     def make_bindings(self):
         self.bind('<Double-1>', self.get_line1)
         self.unbind('<Motion>')
         self.unbind('<ButtonRelease-1>')
         if len(self.parent.lines) > 0:
             self.bind('<Button-1>', self.move_line)
     def get_line1(self, event):
         self.bind('<Button-1>', self.get_line2)
         self.cand1 = (event.x, event.y)
     def add_line(self, x0, y0, x1, y1):
         return self.create_line(x0, y0, x1, y1, arrow=LAST)
     def highlight_line(self, lineID):
         self.itemconfig(lineID, fill='yellow')
     def unhighlight_line(self, lineID):
         self.itemconfig(lineID, fill='black')
     def get_line2(self, event):
         self.parent.add_lines(self.cand1[0], self.cand1[1], event.x, 
event.y)
     def move_line(self, event):
         lineID = self.find_closest(event.x, event.y, halo= 5)
         if lineID[0] > 1:
             self.parent.highlight_line(lineID[0])
             self.current_line = self.parent.get_line(lineID[0], self.side)
             dist1 = (self.current_line[0] - 
event.x)**2+(self.current_line[1] - event.y)**2
             dist2 = (self.current_line[2] - 
event.x)**2+(self.current_line[3] - event.y)**2
             if dist1 <= dist2:
                 self.bind('<Motion>', self.adjust_point1)
             else:
                 self.bind('<Motion>', self.adjust_point2)
             self.bind('<ButtonRelease-1>', lambda event: 
self.parent.unhighlight_line(lineID) or self.make_bindings())

         else :
             self.bind('<ButtonRelease-1>', lambda event: 
self.make_bindings())
     def adjust_point1(self, event):
         self.coords(self.current_line[4], event.x, event.y, 
self.current_line[2], self.current_line[3])
         self.current_line[0] = float(event.x)
         self.current_line[1] = float(event.y)
     def adjust_point2(self, event):
         self.coords(self.current_line[4], self.current_line[0], 
self.current_line[1], event.x, event.y,)
         self.current_line[2] = float(event.x)
         self.current_line[3] = float(event.y)
     def update_image(self):
         self.image_tk = ImageTk.PhotoImage(self.image_data)
         self.itemconfigure(self.image_id, image=self.image_tk)
     def warp(self, source, all_lines, alpha, beta, rho):
     # Do transformPoint on each pixel, save results
     # This is the slow part of the program
         dest = list(self.image_data.getdata())
         src = list(source.image_data.getdata())
         newdata = _warp.warp(dest, src, self.image_data.size[0], 
self.image_data.size[1], all_lines, len(all_lines), 0, alpha, beta, rho)
         self.image_data.putdata(newdata)
         self.update_image()

if __name__ == '__main__':
     WarpGUI().mainloop()

Here's the code for the _warp module:

#include "python.h"
#include "math.h"
#include "stdio.h"

typedef struct warp_line {
	float x0;
	float y0;
	float x1;
	float y1;
} warp_line;

// a testing function for the passing of lists into C arrays and back 
out again

PyObject * warp(PyObject * source1, PyObject * source2, int w, int h, 
PyObject * lines, int nlines, double alpha, double a, double b, double p)
{
	int i,j,k;
	double weightsum;
	double dsumx, dsumy;
	double u, v;
	double q_px, q_py;
	double x_px, x_py;
	double q_p_primex, q_p_primey;
	double dot_primex, dot_primey;
	double x_primex, x_primey;
	double d_ix, d_iy;
	double weight;
	double temp;
	double dist;
	
	unsigned char * s1;
	unsigned char * s2;
	unsigned char * s3;
	warp_line * lines1;
	warp_line * lines2;
	
	// we have two sources in the forms of lists of 3-tuples of integers
	// the lists are w*h in length
	// we have two sources, so we allocate...
	
	// I realize that I'm missing error checking here; oh well - it's not 
the problem
	s1 = (unsigned char *) malloc(w*h*3*sizeof(unsigned char));
	s2 = (unsigned char *) malloc(w*h*3*sizeof(unsigned char));
	s3 = (unsigned char *) malloc(w*h*3*sizeof(unsigned char));
	
	lines1 = (warp_line *) malloc(nlines*sizeof(warp_line));
	lines2 = (warp_line *) malloc(nlines*sizeof(warp_line));
	
	// some pointer holders
	PyObject * returnval;
	PyObject * innerlist;
	PyObject * pychar;
	
	// loop over all data
	for(i = 0; i < w*h*3; i+=3)
	{
		// get tuple
		innerlist = PyList_GetItem(source1, i/3);

		// write out tuple to array
		s1[i] = PyInt_AsLong(PyTuple_GetItem(innerlist, 0));
		s1[i+1] = PyInt_AsLong(PyTuple_GetItem(innerlist, 1));
		s1[i+2] = PyInt_AsLong(PyTuple_GetItem(innerlist, 2));
		
		// ditto for list 2
		innerlist = PyList_GetItem(source2, i/3);
		s2[i] = PyInt_AsLong(PyTuple_GetItem(innerlist, 0));
		s2[i+1] = PyInt_AsLong(PyTuple_GetItem(innerlist, 1));
		s2[i+2] = PyInt_AsLong(PyTuple_GetItem(innerlist, 2));
	}
	
	for(i = 0; i < nlines ; i++)
	{
		innerlist = PyList_GetItem(lines, i);
		pychar = PyTuple_GetItem(innerlist, 0);
		lines1[i].x0 = PyFloat_AsDouble(PyList_GetItem(pychar, 0));
		lines1[i].y0 = PyFloat_AsDouble(PyList_GetItem(pychar, 1));		
		lines1[i].x1 = PyFloat_AsDouble(PyList_GetItem(pychar, 2));
		lines1[i].y1 = PyFloat_AsDouble(PyList_GetItem(pychar, 3));
		
		pychar = PyTuple_GetItem(innerlist, 1);
		lines2[i].x0 = PyFloat_AsDouble(PyList_GetItem(pychar, 0));
		lines2[i].y0 = PyFloat_AsDouble(PyList_GetItem(pychar, 1));		
		lines2[i].x1 = PyFloat_AsDouble(PyList_GetItem(pychar, 2));
		lines2[i].y1 = PyFloat_AsDouble(PyList_GetItem(pychar, 3));
	}
	
	for(i = 0; i < w; i++)
	{
		for(j = 0; j < h; j++)
		{			
                 dsumx = 0.0;
                 dsumy = 0.0;
                 weightsum = 0.0;

                 for(k = 0; k < nlines; k++)
                 {
                     x_px = i - lines1[k].x0;
                     x_py = j - lines1[k].y0;
                     q_px = lines1[k].x1 - lines1[k].x0;
                     q_py = lines1[k].y1 - lines1[k].y0;

                     u = (x_px * q_px + x_py * q_py) / (q_px*q_px + 
q_py*q_py);
                     v = (x_px * q_py - x_py * q_px) / sqrt(q_px*q_px + 
q_py*q_py);

                     q_p_primex = lines2[k].x1 - lines2[k].x0;
                     q_p_primey = lines2[k].y1 - lines2[k].y0;

                     temp = v / sqrt(q_p_primex * q_p_primex + 
q_p_primey * q_p_primey);
                     dot_primex = temp * q_p_primey;
                     dot_primey = - temp * q_p_primex;

                     x_primex = lines2[k].x0 + u * q_p_primex + dot_primex;
                     x_primey = lines2[k].y0 + u * q_p_primey + dot_primey;

                     d_ix = x_primex - i;
                     d_iy = x_primey - j;

                     if ((0.0 <= u) && (u <= 1.0))
                     {
                         dist = abs(v);
                     }
                     else if (u < 0.0)
                     {
                         dist = sqrt(pow((i - lines1[k].x0), 2.0) + 
pow((j - lines1[k].y0), 2.0));
                     }
                     else if (u > 1.0)
                     {
                         dist = sqrt(pow((i - lines1[k].x1),2.0) + 
pow((j - lines1[k].y1), 2.0));
                     }

                     weight = 
pow(pow(sqrt(pow(lines1[k].y1-lines1[k].y0, 
2.0)+pow(lines1[k].x1-lines1[k].x0, 2.0)), p)/(a + dist), b);
                     dsumx = dsumx + d_ix * weight;
                     dsumy = dsumy + d_iy * weight;
                     weightsum += weight;
                 }

                 x_primex = (int) (i + dsumx / weightsum);
                 x_primey = (int) (j + dsumy / weightsum);

                 if ((0 <= x_primex) && (x_primex < w ) && (0 <= 
x_primey) && (x_primey < h))
                 {
                     s3[(i + j*w)*3] = s2[(int) (x_primex + x_primey*w)*3];
                     s3[(i + j*w)*3+1] = s2[(int) (x_primex + 
x_primey*w)*3+1];
                     s3[(i + j*w)*3+2] = s2[(int) (x_primex + 
x_primey*w)*3+2];
                 }
                 else
                 {
                     s3[(i + j*w)*3] = 0;
                     s3[(i + j*w)*3+1] = 0;
                     s3[(i + j*w)*3+2] = 0;
                 }
		}
     }

	// prepare return list
	returnval = PyList_New(w*h);
	
	// fill list	
	for(i = 0; i < w*h*3; i+=3)
	{
		// make a tuple
		innerlist = PyTuple_New(3);
		
		// fill tuple with 3 values		
		pychar = PyInt_FromLong((long)s3[i]);	
		
		PyTuple_SetItem(innerlist, 0, pychar);
		
		pychar = PyInt_FromLong((long)s3[i+1]);

		PyTuple_SetItem(innerlist, 1, pychar);
		
		pychar = PyInt_FromLong((long)s3[i+2]);

		PyTuple_SetItem(innerlist, 2, pychar);
		
		// store tuple in list
		PyList_SetItem(returnval, i/3, innerlist);
		
		// manually get rid of list
	//	Py_DECREF(innerlist);

	}
	
	//free storage
	free(s1);
	free(s2);
	free(s3);
	free(lines1);
	free(lines2);
	
	// done
	return returnval;
	
}






More information about the Python-list mailing list