Fastest Way To Loop Through Every Pixel

[Chaos]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

 

[John Machin]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

OT: you don't need the 0 in the range call. Taking it out doesn't make
it run faster, though.

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

Unsuccessful because .... what?
[I wasn't aware that swig was intended to compile Python scripts]

Sticking with Python:
With the "for thisX" try
(1) using xrange instead of range.
(2) widthRange = range(thisWidth)
for thisY in range(thisHeight):
for thisX in widthrange:
and in general, hoist loop-invariants outside the loop.

Have you considered Pyrex?

It all depends on what "#Actions here for Pixel thisX, thisY" is doing.
Perhaps there is a library (PIL, pygame, ...) that does what you are
trying to do.
Perhaps if you show us what you are doing, we can give you better
advice.

HTH,
John

 

[Chaos]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

OT: you don't need the 0 in the range call. Taking it out doesn't make
it run faster, though.

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

Unsuccessful because .... what?
[I wasn't aware that swig was intended to compile Python scripts]

Sticking with Python:
With the "for thisX" try
(1) using xrange instead of range.
(2) widthRange = range(thisWidth)
for thisY in range(thisHeight):
for thisX in widthrange:
and in general, hoist loop-invariants outside the loop.

Have you considered Pyrex?

It all depends on what "#Actions here for Pixel thisX, thisY" is doing.
Perhaps there is a library (PIL, pygame, ...) that does what you are
trying to do.
Perhaps if you show us what you are doing, we can give you better
advice.

HTH,
John

Nope still same speed. I also tried pyrex but I couldnt understand how
to build pyx files. I didnt see how to set up the files using C. I
wasnt sure if you were supposed use the example or build your own.

With pypy I got a strange error trying to open py files. It said the
first character of evey py file was unknown.

I may try SWIG again becuase I fail to rememeber why I stopped using it.

 

[Nick Vatamaniuc]

Hello Chaos,

Whatever you do in "#Actions here ..." might be expressed nicely as a
ufunction for numeric. Then you might be able to convert the expression
to a numeric expression. Check out numpy/scipy.

In general, if thisHeight, thisWidth are large use xrange not range.
range() generates a list of numbers first then iterates through them.
So try that first.

Then of course if you do the whole thing many times you could just
pre-generate the indices as in:
all_indices=[]
for i in xrange(thisHeight):
for j in xrange(thisWidth):
all_indices.append( (i,j) )

Then each time you need to run '#Actions here...' you can just use
for (i,j) in all_indices:
#Actions here ... blah blah

In general, if there would be a way to significantly optimize generic
for loops, they would probably be already optimized...

Nick V.

 

[Chaos]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

OT: you don't need the 0 in the range call. Taking it out doesn't make
it run faster, though.

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

> > > I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

Unsuccessful because .... what?
[I wasn't aware that swig was intended to compile Python scripts]

Sticking with Python:
With the "for thisX" try
(1) using xrange instead of range.
(2) widthRange = range(thisWidth)
for thisY in range(thisHeight):
for thisX in widthrange:
and in general, hoist loop-invariants outside the loop.

Have you considered Pyrex?

It all depends on what "#Actions here for Pixel thisX, thisY" is doing.
Perhaps there is a library (PIL, pygame, ...) that does what you are
trying to do.
Perhaps if you show us what you are doing, we can give you better
advice.

HTH,
John

Nope still same speed. I also tried pyrex but I couldnt understand how
to build pyx files. I didnt see how to set up the files using C. I
wasnt sure if you were supposed use the example or build your own.

With pypy I got a strange error trying to open py files. It said the
first character of evey py file was unknown.

I may try SWIG again becuase I fail to rememeber why I stopped using it.

With SWIG when I tried to execute ld -shared example.o example_wrap.o
-o _example.so line in CMD I got example_wrap.o:example.o
:<.text+0x####>: undifned refrence to object

--Nick

Thank you but it didnt work, but I think I am getting somewhere because
I used your method and got 400 ms, I think that is something because I
used 2 loops

He is the code #Actions here

myCol = (0.3 * image.GetRed(thisX, thisY)) + (0.59 *
image.GetGreen(thisX, thisY)) + (0.11 * image.GetBlue(thisX, thisY))
if myCol < darkestCol:
darkestCol = myCol
possX = thisX
possY = thisY

 

[Simon Forman]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

You could try the PIL package.

From the docs at

http://www.pythonware.com/library/pil/handbook/image.htm

Image.eval(function, image) => image

Applies the function (which should take one argument) to each pixel in
the given image. If the image has more than one band, the same function
is applied to each band. Note that the function is evaluated once for
each possible pixel value, so you cannot use random components or other
generators.

HTH,
~Simon

 

[Casey Hawthorne]

Have you tried PIL? (Python Imaging Library)

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

 

[Chaos]

You could try the PIL package.

http://www.pythonware.com/library/pil/handbook/image.htm

Image.eval(function, image) => image

Applies the function (which should take one argument) to each pixel in
the given image. If the image has more than one band, the same function
is applied to each band. Note that the function is evaluated once for
each possible pixel value, so you cannot use random components or other
generators.

HTH,
~Simon

I have tried PIL. Not only that, but the Image.eval function had no
success either. I did some tests and I found out that Image.eval only
called the function a certain number of times either 250, or 255.
Unless I can find a working example for this function, its impossible
to use.

 

[Paul McGuire]

myCol = (0.3 * image.GetRed(thisX, thisY)) + (0.59 *
image.GetGreen(thisX, thisY)) + (0.11 * image.GetBlue(thisX, thisY))
if myCol < darkestCol:
darkestCol = myCol
possX = thisX
possY = thisY

Psyco may be of some help to you, especially if you extract out your myCol
expression into its own function, something like:

def darkness(img,x,y):
return (0.3 * img.GetRed(x,y)) + (0.59 * img.GetGreen(x,y)) + (0.11 *
img.GetBlue(x,y))

You may also be paying a penalty for the floating-point multiplications.
Since you are only concerned with the relative values, what if you scale up
all of your weighting coefficients, so that you only do integer multiplies?

def darkness(img,x,y):
return (30 * img.GetRed(x,y)) + (59 * img.GetGreen(x,y)) + (11 *
img.GetBlue(x,y))

You can also cut down on resolution of your GetXXX functions by saving them
to locals.

RedVal = Image.GetRed
GrnVal = Image.GetGreen
BluVal = Image.GetBlue
def darkness(img,x,y):
return (30 * RedVal(img,x,y)) + (59 * GreenVal(img,x,y)) + (11 *
BlueVal(img,x,y))

Even downer-and-dirtier, you could approximate 30 with 32, 59 with 64, and
11 with 8, and do bit-shifting instead of multiplying:

def darkness(img,x,y):
return (RedVal(img,x,y) << 5) + (GreenVal(img,x,y) << 6) +
(BlueVal(img,x,y) << 3)


-- Paul

 

[Paul McGuire]

Hello Chaos,

Then of course if you do the whole thing many times you could just
pre-generate the indices as in:
all_indices=[]
for i in xrange(thisHeight):
for j in xrange(thisWidth):
all_indices.append( (i,j) )

Or just:

all_indices = [ (i,j) for i in xrange(thisHeight) for j in
xrange(thisWidth) ]

Embrace those list comprehensions!

-- Paul

 

[Simon Forman]

I have tried PIL. Not only that, but the Image.eval function had no
success either. I did some tests and I found out that Image.eval only
called the function a certain number of times either 250, or 255.

It says "the function is evaluated once for each possible pixel value",
so if it's only calling the function 250 or 255 times it's because your
image only has 250 or 255 colors.

Obviously Image.eval() caches the results of your function for each
color/pixel-value and reuses them rather than recomputing them.

I take it that whatever you're doing to those pixels involves more
information than just the pixel values? What are you doing to the
pixels? That's probably wher you should look to improve the speed of
the loop.

Peace,
~Simon

 

[H J van Rooyen]

| Even downer-and-dirtier, you could approximate 30 with 32, 59 with 64, and
| 11 with 8, and do bit-shifting instead of multiplying:
|
| def darkness(img,x,y):
| return (RedVal(img,x,y) << 5) + (GreenVal(img,x,y) << 6) +
| (BlueVal(img,x,y) << 3)
|
|
| -- Paul

*grin* - a man after my own heart! - how do you multiply by ten? - shift, save a
copy, shift twice more and add the copy...

- Hendrik

 

[Simon Forman]

It says "the function is evaluated once for each possible pixel value",
so if it's only calling the function 250 or 255 times it's because your
image only has 250 or 255 colors.

Obviously Image.eval() caches the results of your function for each
color/pixel-value and reuses them rather than recomputing them.

I take it that whatever you're doing to those pixels involves more
information than just the pixel values? What are you doing to the
pixels? That's probably wher you should look to improve the speed of
the loop.

Peace,
~Simon

Oops, sorry. I didn't see where you had already posted the actions
you're taking on the pixels..

He is the code #Actions here

myCol = (0.3 * image.GetRed(thisX, thisY)) + (0.59 *
image.GetGreen(thisX, thisY)) + (0.11 * image.GetBlue(thisX, thisY))
if myCol < darkestCol:
darkestCol = myCol
possX = thisX
possY = thisY

Hmm, if you're just trying to find the darkest color and one of it's
pixel coordinates after applying your weighting calculation, and you
don't mind if the coordinates are of the first encountered pixel of
that color, then I think you might be able to use Image.eval() after
all.

What format are the images in?


Peace,
~Simon

 

[Paul McGuire]

| Even downer-and-dirtier, you could approximate 30 with 32, 59 with 64, and
| 11 with 8, and do bit-shifting instead of multiplying:
|
| def darkness(img,x,y):
| return (RedVal(img,x,y) << 5) + (GreenVal(img,x,y) << 6) +
| (BlueVal(img,x,y) << 3)
|
|
| -- Paul

*grin* - a man after my own heart! - how do you multiply by ten? - shift, save a
copy, shift twice more and add the copy...

- Hendrik

Sadly, my timeit results show this saves only a little time, and
shift-copy-shiftsomemore-and-add is even slower then just doing the original
floating point multiply. The biggest win is in prelookup of Image.GetXXX
functions.

-- Paul

 

[Ben Sizer]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

The main question is: why do you want to do this? I ask because with
performance requirements like that, you almost certainly need another
approach, one which I may be able to suggest.

 

[c d saunter]

Chaos ([email protected]) wrote:

: He is the code #Actions here

: myCol = (0.3 * image.GetRed(thisX, thisY)) + (0.59 *
: image.GetGreen(thisX, thisY)) + (0.11 * image.GetBlue(thisX, thisY))
: if myCol < darkestCol:
: darkestCol = myCol
: possX = thisX
: possY = thisY

You really don't want to do this in interpreted Python code. Way to slow.
I don't know PIL but probably you can do it their.

Another aproach is to use one of the array/maths libraries e.g. Numeric or
NumPy.

You'll need to move the image data between PIL and the array package with
the data being a (y,x,3) array for input array and (y,x) for the output
array. .tostirng() methods and fromstring() can be usefull here.

Then...

1. Colour map it
newImage = 0.3 * image[:,:,0] + 0.59 * image[:,:,1] + 0.11 * image[:,:,2]

2. Mask of pixels less than your threshold

newImage = clip(newImage, myCol, MAX_COLOUR)

3. Find the coordinates of the last minimum colour - possX, possY (do you
really need/mean to do this?)

hth
cds

 

[H J van Rooyen]

| | >
| > | Even downer-and-dirtier, you could approximate 30 with 32, 59 with 64,
| and
| > | 11 with 8, and do bit-shifting instead of multiplying:
| > |
| > | def darkness(img,x,y):
| > | return (RedVal(img,x,y) << 5) + (GreenVal(img,x,y) << 6) +
| > | (BlueVal(img,x,y) << 3)
| > |
| > |
| > | -- Paul
| >
| > *grin* - a man after my own heart! - how do you multiply by ten? - shift,
| save a
| > copy, shift twice more and add the copy...
| >
| > - Hendrik
| >
| Sadly, my timeit results show this saves only a little time, and
| shift-copy-shiftsomemore-and-add is even slower then just doing the original
| floating point multiply. The biggest win is in prelookup of Image.GetXXX
| functions.
|
| -- Paul

I was not seriously suggesting this for use in python on a pc - its the sort of
rubbish you do on a small embedded machine that has a reduced instruction set
and no multiplier...

- Hendrik

 

[jay graves]

As my first attempt to loop through every pixel of an image, I used

for thisY in range(0, thisHeight):
for thisX in range(0, thisWidth):
#Actions here for Pixel thisX, thisY

But it takes 450-1000 milliseconds

I want speeds less than 10 milliseconds

I have tried using SWIG, and pypy but they all are unsuccessfull in
compiling my files.

I think you are using PIL but I don't know what version.

Check out this page.
http://effbot.org/zone/image-histogram-optimization.htm

HTH...
jay

 

[Terry Reedy]

Besides other suggestions, you might also take a look at Pygame which both
wraps a C graphics library and has an interface to numeric.

 

[John Machin]

Besides other suggestions, you might also take a look at Pygame which both
wraps a C graphics library and has an interface to numeric.

Could your check_earlier_responses() gizmoid be made case-insensitive?
(-: