Searching for patterns on the screen

[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/Cookbook/Python/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