Comparing bitmap images for differences?

[lanwrangler]

I know it's a long shot but does anyone have any pointers to generic
algorithms - or, even better, Python code - for comparing images and
computing a value for the "difference" between them?

What I want to do is to compare two bitmap images (taken from a
webcam, so I'll likely be using PIL) and get some idea of the
"difference" between them so I can tell if something in the image has
changed, eg, a person has entered the field of view. I've had a look
at the PIL documentation and all it really told me was how little I
knew about image processing and I couldn't see any recipes in the
Python Cookbook that are aimed at this problem area. In a perfect
world I'd love a method such as CompareImage(Img1, Img2) which would
give a result of 255 if they're identical and 0 if not one pixel
matches with a sliding scale inbetween but I know I'm probably asking
for a lot there...

Some ideas I've had is, maybe, increasing the contrast on both images
(to take out variation in lighting etc), then compressing the results
to get a hash value and comparing the hash, but that sounds likely to
produce a lot of false positives. I note that PIL provides a
histogram function for counting pixel colour values which sounds
potentially useful and if no-one's got any better ideas I'll probably
start working in that direction. Or, maybe, dump the bitmap data into
a numpy array and do some kind of FFT on that but that feels very CPU-
intensive.

Those are my ideas so far but I thought it would be worth asking here
first in case there are some known-good algorithms for doing this kind
of thing rather than me trying to re-invent a wheel that ends up
triangular...

Thanks!
Matthew.

 

[Diez B. Roggisch]

I know it's a long shot but does anyone have any pointers to generic
algorithms - or, even better, Python code - for comparing images and
computing a value for the "difference" between them?

What I want to do is to compare two bitmap images (taken from a
webcam, so I'll likely be using PIL) and get some idea of the
"difference" between them so I can tell if something in the image has
changed, eg, a person has entered the field of view. I've had a look
at the PIL documentation and all it really told me was how little I
knew about image processing and I couldn't see any recipes in the
Python Cookbook that are aimed at this problem area. In a perfect
world I'd love a method such as CompareImage(Img1, Img2) which would
give a result of 255 if they're identical and 0 if not one pixel
matches with a sliding scale inbetween but I know I'm probably asking
for a lot there...

Some ideas I've had is, maybe, increasing the contrast on both images
(to take out variation in lighting etc), then compressing the results
to get a hash value and comparing the hash, but that sounds likely to
produce a lot of false positives. I note that PIL provides a
histogram function for counting pixel colour values which sounds
potentially useful and if no-one's got any better ideas I'll probably
start working in that direction. Or, maybe, dump the bitmap data into
a numpy array and do some kind of FFT on that but that feels very CPU-
intensive.

Those are my ideas so far but I thought it would be worth asking here
first in case there are some known-good algorithms for doing this kind
of thing rather than me trying to re-invent a wheel that ends up
triangular...

There is the excellent OpenCV-library from intel which is FOSS and has a
python-binding. Either using swig, or a ctypes-version:

http://wwwx.cs.unc.edu/~gb/wp/blog/2007/02/04/python-opencv-wrapper-using-ctypes/

With that, you can approach your problem. What is usually done is that a
sequence of background images is sampled & an average is built. Then the
actual image is subtracted from that image, with an epsilon to account
for noise.

The result is then converted to a binary image for further processing.
There are some blob-detection-recipes out there.

Another approach is to use the motion-detection parts of the lib.

Diez

 

[3c273]

Those are my ideas so far but I thought it would be worth asking here

first in case there are some known-good algorithms for doing this kind
of thing rather than me trying to re-invent a wheel that ends up
triangular...

Thanks!
Matthew.

This might get you started.
http://tinyurl.com/7qexl
Louis

 

[Terry Reedy]

|I know it's a long shot but does anyone have any pointers to generic
| algorithms - or, even better, Python code - for comparing images and
| computing a value for the "difference" between them?

If PIL and the other posted ideas are not enough, another approach is to
convert the image from PIL format to NumPy array format. (pygame has
functions to do this, I believe, since it uses NumPy (actually the older
Numerical Python at present) for its surface arrays.) You can then do most
any calculation you want.

tjr

 

[lanwrangler]

With that, you can approach your problem. What is usually done is that a
sequence of background images is sampled & an average is built. Then the
actual image is subtracted from that image, with an epsilon to account
for noise.

Thanks for the tip for an algorithm - I can see how that could work
really nicely (and it gives me some ideas for other things, too!)
Thanks also for the link to the OpenCV bindings. I'll give 'em a try
and see what happens.

Regards,
Matthew.

 

[lanwrangler]

This might get you started.http://tinyurl.com/7qexl

Wow, I thought briefly along those lines but then thought "No, it
can't possibly be that easy" It looks like the approach given in
that link could benefit hugely from using numpy to treat the bitmaps
as arrays to speed up processing but that should be pretty
straightforward. I'll give it a try as-is and then look at
optimisation if required. Saying that, and thinking about the itch
I'm trying to scratch here, I think I could also safely ignore the
borders of the image so that would reduce the processing requirements
anyway. Add in a FIFO file buffer so I can do pre/post-event image
capture plus a spot of SMTP mail alerting and the job's done!

Thanks again.
Matthew.

 

[Dave Johnston]

Thanks for the tip for an algorithm - I can see how that could work
really nicely (and it gives me some ideas for other things, too!)
Thanks also for the link to the OpenCV bindings. I'll give 'em a try
and see what happens.

I did similar stuff for a project at Uni, but for tracking
pedestrians... in (eurgh) Java.
Tad boring, but might help a little bit: http://uni.johnsto.co.uk/crowd/

Unfortunately it only got tested on pre-recorded feeds, not live ones.
The background removal was fun. I think I ended up getting the
background by converting every 5th frame to grayscale, and calculating
the median for each pixel position across the sample. A couple filters
to remove tiny 1 or 2 pixel specks of noise, and then went onto blob
detection for identifying people and tracking their movement across
the entire video.

The same filtering in numpy should be really quite fast indeed!