Slow Python - what can be done? LONG, CODE
Jason Sewall
me at me.com
Wed Mar 24 10:32:42 EST 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