Fastest Way To Loop Through Every Pixel

[nikie]

Chaos wrote:

> nikie wrote:
> > Chaos wrote:
> >
> > > 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
> >
> > Milliseconds don't mean much unless we knew how big your images are and
> > what hardware you're using.
> >
> > Have you considered using NumPy? Assuming you can get the image into a
> > numpy array efficiently, the actual algorithm boils down to something
> > like this:
> >
> >     grey = r*0.3 +
>
>  g*0.59 + b*0.11
> >     index = grey.argmin()
> >     x,y = index%step, index/step
> >     v = grey[x,y]
> >
> > where r,g,b and grey are numpy.ndarray objects; The arithmetic
> > operators and the argmin-function are implemented in C, so you can
> > expect decent performance. (the 4 lines above take about 80 ms for a
> > 1000x1000 image on my PC)
> >
> > If that's not enough, you might want to use some specially optimized C
> > library for this purpose. (I'd suggest Intel's IPP, but there are
> > others).
>
> I really do not understand the code. Where did you get the varibales r,
> g, b and step and what does v produce?

Sorry, I should have commented it better. The idea is that r,g,b are
numpy-arrays containig the r, g, b-pixel-values in the image:

  import numpy, Image
  img = Image.open("Image1.jpg")
  r = numpy.array(img.getdata(0))
  g = numpy.array(img.getdata(1))
  b = numpy.array(img.getdata(2))
  w,h = img.size

The "step" is the length of one line of pixels, that is, the offset to
a pixel (x,y) is x+y*step. (This is usually called "step" or "stride"
in literature)

  step = w

Now, I can use numpy's overridden arithmetic operators to do the
per-pixel calculations (Note that numpy also overrides sin, cos, max,
..., but you'll have to use from numpy import * to get these overrides
in your namespace):

  grey = r*0.3 + g*0.59 + b*0.11

The multiplication-operator is overridden, so that "r*0.3" multiplies
each value in the array "r" with "0.3" and returns the multiplied
array, same for "g*0.59", "b*0.11". Adding the arrays adds them up
value by value, and returns the sum array. This generally works quite
well and intuitively if you perform only per-pixel operations. If you
need a neighborhood, use slicing.
The function "argmin" searches for the index of the minimum value in
the array:

  index = grey.argmin()

But since we want coordinates instead of indices, we'll have to
transform these back using the step value:

  x,y = index % step, index / step

Result:

  print x,y,r[index],g[index],b[index]

Works for my image.

Notes:
- I'm _not_ sure if this is the fastest way to get an image into a
numpy array. It's convenient, but if you need speed, digging into the
numpy docs/newsgroup archive, and doing a few benchmarks for yourself
would be a good idea
- numpy does have 2d-Arrays, but I'm not that much of a numpy expert to
tell you how to use that to get rid of the index/step-calculations.
Again, numpy-docs/newsgroup might help
- a general advice: using integer multiplications instead for
floating-point may help with performance, too.
- you said something about 10 ms, so I'm guessing your image doesn't
come from a harddrive at all (because reading it alone will usually
take longer than 10 ms). Numpy arrays have a C-Interface you might want
to use to get data from a framegrabber/digital camera into a numpy
array.