Searching for patterns on the screen

[Jerry Hill]

Hello all,

I have a piece of code I could use some help optimizing. What I'm
attempting to do is periodically grab a screenshot, and search for 2D
patterns of black pixels in it. I don't care about any color other
than black. Here's some simple code that simulates my worst-case
scenario, scanning the whole screen for a sequence that does not
exist:

import ImageGrab # From the PIL library

def removeColor(rgb):
r, g, b = rgb
return (r == 0 and g == 0 and b == 0)

BMP = ImageGrab.grab.getdata()
x = map(removeColor, BMP)

The idea is to search for sequences of black pixels on a background
that can change colors. To that end, I transform the screengrab into
a sequence of either black or nonblack pixels as I search them. Note
that in my actual code, I use imap so I only transform pixels as I
search them, and I'm using the KnuthMorrisPratt algorithm from
http://aspn.activestate.com/ASPN/Coo.../Recipe/117214 to do
the actual searching.

>From some testing using the timeit module:

map(None, BMP) takes about 0.6 seconds on a 1600x1200 screengrab.
map(removeColor, BMP) takes about 1.5 seconds.

I'd love to speed things up, if possible. It seems like what I'm
doing would probably be a fairly well defined problem, but I don't
know enough about the field to even know where to start my research,
so even a list of keywords that would point me to discussion of
similar topics would be welcome.

This is being done in Python 2.5c2 using PIL 1.1.5

--
Jerry

[Paul McGuire]

"Jerry Hill" <ma*********@gmail.comwrote in message
news:ma**************************************@pyth on.org...

Hello all,

I have a piece of code I could use some help optimizing. What I'm
attempting to do is periodically grab a screenshot, and search for 2D
patterns of black pixels in it. I don't care about any color other
than black. Here's some simple code that simulates my worst-case
scenario, scanning the whole screen for a sequence that does not
exist:

import ImageGrab # From the PIL library

def removeColor(rgb):
r, g, b = rgb
return (r == 0 and g == 0 and b == 0)

BMP = ImageGrab.grab.getdata()
x = map(removeColor, BMP)

The idea is to search for sequences of black pixels on a background
that can change colors.

I had to do a similar thing using pywinauto to interact with a IE browser
running an embedded Flash application. To speed things up, I included psyco
to compile my functions.

As far as working just in Python, you could remove the tuple unpacking
inside removeColor, and shorten it to just:

def removeColor(rgb):
return rgb==(0,0,0)

or even better:

BLACK = (0,0,0)
def removeColor(rgb):
return rgb==BLACK

By defining BLACK once and just referring to it by name, you also avoid
dynamically constructing the (0,0,0) tuple in every call.

But you might also look at the PIL docs and see if there is a way to do this
color manipulation using the PIL API - the advantage here is that then you
would be invoking a C-compiled API routine, which will run way faster than
any optimized Python method.

-- Paul

[John Machin]

Paul McGuire wrote:

"Jerry Hill" <ma*********@gmail.comwrote in message
news:ma**************************************@pyth on.org...

Hello all,

I have a piece of code I could use some help optimizing. What I'm
attempting to do is periodically grab a screenshot, and search for 2D
patterns of black pixels in it. I don't care about any color other
than black. Here's some simple code that simulates my worst-case
scenario, scanning the whole screen for a sequence that does not
exist:

import ImageGrab # From the PIL library

def removeColor(rgb):
r, g, b = rgb
return (r == 0 and g == 0 and b == 0)

BMP = ImageGrab.grab.getdata()
x = map(removeColor, BMP)

The idea is to search for sequences of black pixels on a background
that can change colors.

I had to do a similar thing using pywinauto to interact with a IE browser
running an embedded Flash application. To speed things up, I included psyco
to compile my functions.

As far as working just in Python, you could remove the tuple unpacking
inside removeColor, and shorten it to just:

def removeColor(rgb):
return rgb==(0,0,0)

or even better:

BLACK = (0,0,0)
def removeColor(rgb):
return rgb==BLACK

By defining BLACK once and just referring to it by name, you also avoid
dynamically constructing the (0,0,0) tuple in every call.

Bzzzzzt. It's not dynamically constructed. Its a constant (in 2.4 at
least)

| >>BLACK=(0,0,0)
| >>def func1(rgb):
| ... return rgb==BLACK
| ...
| >>def func2(rgb):
| ... return rgb==(0,0,0)
| ...
| >>import dis
| >>dis.dis(func1)
| 2 0 LOAD_FAST 0 (rgb)
| 3 LOAD_GLOBAL 1 (BLACK)
| 6 COMPARE_OP 2 (==)
| 9 RETURN_VALUE
| >>dis.dis(func2)
| 2 0 LOAD_FAST 0 (rgb)
| 3 LOAD_CONST 2 ((0, 0, 0))
| 6 COMPARE_OP 2 (==)
| 9 RETURN_VALUE
| >>>
C:\junk>python -mtimeit -s"BLACK=(0,0,0);rgb=(1,1,1)" "rgb==BLACK"
1000000 loops, best of 3: 0.129 usec per loop

C:\junk>python -mtimeit -s"rgb=(1,1,1)" "rgb==(0,0,0)"
1000000 loops, best of 3: 0.127 usec per loop

[Claudio Grondi]

Jerry Hill wrote:

Hello all,

I have a piece of code I could use some help optimizing. What I'm
attempting to do is periodically grab a screenshot, and search for 2D
patterns of black pixels in it. I don't care about any color other
than black. Here's some simple code that simulates my worst-case
scenario, scanning the whole screen for a sequence that does not
exist:

import ImageGrab # From the PIL library

def removeColor(rgb):
r, g, b = rgb
return (r == 0 and g == 0 and b == 0)

BMP = ImageGrab.grab.getdata()
x = map(removeColor, BMP)

The idea is to search for sequences of black pixels on a background
that can change colors. To that end, I transform the screengrab into
a sequence of either black or nonblack pixels as I search them. Note
that in my actual code, I use imap so I only transform pixels as I
search them, and I'm using the KnuthMorrisPratt algorithm from
http://aspn.activestate.com/ASPN/Coo.../Recipe/117214 to do
the actual searching.

>From some testing using the timeit module:

map(None, BMP) takes about 0.6 seconds on a 1600x1200 screengrab.
map(removeColor, BMP) takes about 1.5 seconds.

I'd love to speed things up, if possible. It seems like what I'm
doing would probably be a fairly well defined problem, but I don't
know enough about the field to even know where to start my research,
so even a list of keywords that would point me to discussion of
similar topics would be welcome.

This is being done in Python 2.5c2 using PIL 1.1.5

Use PIL for grabbing the screenshot and numarray for processing the
image. See
http://groups.google.com.vc/group/co...5646969d59102e
for some further helpful hints towards speeding things up.

Claudio Grondi

[Jerry Hill]

On 15 Sep 2006 08:16:41 -0700, John Machin <sj******@lexicon.netwrote:

C:\junk>python -mtimeit -s"BLACK=(0,0,0);rgb=(1,1,1)" "rgb==BLACK"
1000000 loops, best of 3: 0.129 usec per loop

C:\junk>python -mtimeit -s"rgb=(1,1,1)" "rgb==(0,0,0)"
1000000 loops, best of 3: 0.127 usec per loop

Surprisingly (to me), hand splitting the tuple and doing short circuit
comparisons is slightly faster than either of those:

C:\Python25>python -mtimeit -s"BLACK=(0,0,0);rgb=(1,1,1)" "rgb==BLACK"
10000000 loops, best of 3: 0.18 usec per loop

C:\Python25>python -mtimeit -s"rgb = (1,1,1)" "rgb == (0,0,0)"
10000000 loops, best of 3: 0.169 usec per loop

C:\Python25>python -mtimeit -s"rgb = (1,1,1)" "rgb[0] == 0 and rgb[1]
== 0 and rgb[2] == 0"
10000000 loops, best of 3: 0.158 usec per loop

It probably has to do with not needing to find the len of the tuple
each time you compare.

I agree with Paul's earlier statement that there's probably a better
way to do this through PIL. I've read through the PIL docs, but I'm
afraid I'm running into problems caused by my own ignorance. It seems
like I should be able to do something with Image.eval(), the point()
method or one of the PIL filters, but I don't understand them well
enough. I'll take a look through the source, and if that doesn't help
I'll take this to the PIL list to get some further feedback on how
those work.

--
Jerry

[Filip Wasilewski]

Jerry Hill wrote:

Hello all,

I have a piece of code I could use some help optimizing. What I'm
attempting to do is periodically grab a screenshot, and search for 2D
patterns of black pixels in it. I don't care about any color other
than black. Here's some simple code that simulates my worst-case
scenario, scanning the whole screen for a sequence that does not
exist:

import ImageGrab # From the PIL library

def removeColor(rgb):
r, g, b = rgb
return (r == 0 and g == 0 and b == 0)

BMP = ImageGrab.grab.getdata()
x = map(removeColor, BMP)

The idea is to search for sequences of black pixels on a background
that can change colors. To that end, I transform the screengrab into
a sequence of either black or nonblack pixels as I search them. Note
that in my actual code, I use imap so I only transform pixels as I
search them, and I'm using the KnuthMorrisPratt algorithm from
http://aspn.activestate.com/ASPN/Coo.../Recipe/117214 to do
the actual searching.

From some testing using the timeit module:

map(None, BMP) takes about 0.6 seconds on a 1600x1200 screengrab.
map(removeColor, BMP) takes about 1.5 seconds.

I'd love to speed things up, if possible. It seems like what I'm
doing would probably be a fairly well defined problem, but I don't
know enough about the field to even know where to start my research,
so even a list of keywords that would point me to discussion of
similar topics would be welcome.

This is being done in Python 2.5c2 using PIL 1.1.5

--
Jerry

Calling Python function for every pixel results in significant
overhead. Instead of that you can use numpy to do the preprocesing.

im = ImageGrab.grab()
a = numpy.fromstring(im.tostring(), dtype=[('r','|u1'), ('g','|u1'),
('b','|u1')])
a.shape = im.size[::-1]
black = (a['r'] == 0) & (a['g'] == 0) & (a['b'] == 0)

s = black.tostring() # sequence of '\x00' and '\x01'

You can also take a look at scipy ndimage
(http://www.scipy.org/doc/api_docs/scipy.ndimage.html) if in need of
more specific routines.

cheers,
fw

[Paul McGuire]

"John Machin" <sj******@lexicon.netwrote in message
news:11**********************@b28g2000cwb.googlegr oups.com...

>
Paul McGuire wrote:

>"Jerry Hill" <ma*********@gmail.comwrote in message
news:ma**************************************@pyt hon.org...

Hello all,

As far as working just in Python, you could remove the tuple unpacking
inside removeColor, and shorten it to just:

def removeColor(rgb):
return rgb==(0,0,0)

or even better:

BLACK = (0,0,0)
def removeColor(rgb):
return rgb==BLACK

By defining BLACK once and just referring to it by name, you also avoid
dynamically constructing the (0,0,0) tuple in every call.

Bzzzzzt. It's not dynamically constructed. Its a constant (in 2.4 at
least)

| >>BLACK=(0,0,0)
| >>def func1(rgb):
| ... return rgb==BLACK
| ...
| >>def func2(rgb):
| ... return rgb==(0,0,0)
| ...
| >>import dis
| >>dis.dis(func1)
| 2 0 LOAD_FAST 0 (rgb)
| 3 LOAD_GLOBAL 1 (BLACK)
| 6 COMPARE_OP 2 (==)
| 9 RETURN_VALUE
| >>dis.dis(func2)
| 2 0 LOAD_FAST 0 (rgb)
| 3 LOAD_CONST 2 ((0, 0, 0))
| 6 COMPARE_OP 2 (==)
| 9 RETURN_VALUE
| >>>
C:\junk>python -mtimeit -s"BLACK=(0,0,0);rgb=(1,1,1)" "rgb==BLACK"
1000000 loops, best of 3: 0.129 usec per loop

C:\junk>python -mtimeit -s"rgb=(1,1,1)" "rgb==(0,0,0)"
1000000 loops, best of 3: 0.127 usec per loop

Hunh! It sure seems like I recently had to do something like this, and the
value was rebuilt every time. Perhaps I was building a "constant" list
instead of a tuple...

>>def fn(lst):

.... return lst == [1,1,1]
....

>>import dis
dis.dis(fn)

2 0 LOAD_FAST 0 (lst)
3 LOAD_CONST 1 (1)
6 LOAD_CONST 1 (1)
9 LOAD_CONST 1 (1)
12 BUILD_LIST 3
15 COMPARE_OP 2 (==)
18 RETURN_VALUE

>>>

So tuples can be inlined as constants, but lists will be built on the fly.

-- Paul