autocratic for the people.

How Hard Could It Be, Part 3.

(Also see parts 1 and 2.)

We're now at the point where we understand the problem, and are starting to think about solutions. Unfortunately, the simplest and most straightforward attempt at a solution has failed. By comparing each pixel of the background image to each pixel of the background-and-foreground image we hoped to figure out whether the pixel was background (the pixels are the same) or foreground (the pixels are different). What we didn't realize is that webcam images tend to be noisy, and the noise prevents that approach from working: because the noise causes each image we look at to have a slightly different color value for each pixel, a direct comparison doesn't work. What we really need is a way to compare pixels that:

1. Knows background pixels can vary a little bit but still be "just about the same," and
   
2. Also knows that too big a difference means the pixel has probably changed.
   

Put another way, we want to know when a pixel has changed enough that it can't possibly be part of the background anymore. Fortunately, there's a relatively easy way to figure that out. What we need to do is collect a bunch of different empty-background images, and then look at how much each pixel changes in each image. If we do that for a number of different images, we can get a good idea of how much the pixel's color is affected by noise.


Color of the same pixel in sequential images


Those look like pretty different colors, but if we assume that those colors represent the extremes of how much the color can vary, we can figure out how much variation in color should be considered acceptable for the pixel to still be part of the background. We do this by calculating the standard deviation. In essence, the standard deviation says:

• If this pixel is between green and brown, it's probably still part of the background.
  

We can also then turn that statement inside out to say:

• If this pixel isn't between green and brown, it's probably not part of the background.
  

That answers our question! Remember, we wanted to know when a pixel has changed enough that it shouldn't be considered part of the background anymore. Using the standard deviation*, we can tell when a pixel has changed enough that it's unlikely noise alone caused the change. Problem solved, right?

Well, let's try it. Here's what we get when we capture ten empty background images, calculate the standard deviation of each pixel based on those ten images, and then use that to determine whether each pixel in a live image is part of the foreground or the background:


Finding background pixels in a noisy image using the standard deviation


Hey, that's not bad! It doesn't get all of the pixels, but it gets most of 'em. Note that a big clump of the missed pixels are in the bottom-right corner of the image; that's because that corner is black in the image, and noise tends to be worse in darker areas of images because very little light hits the camera to tell it what color that area is.

Things are looking pretty good, so let's press on. What happens if we stick a foreground object into the scene?


Background subtraction using the standard deviation


Hmm, that doesn't look nearly as good. My hand is certainly visible, but there are all sorts of holes in my fingers, and the railing in the background is clearly visible through my arm. Looks like my skin color is so close to the color of the railing that the standard deviation thinks it sees background!

Tomorrow we'll look at ways to make the background and foreground more uniform, and see if we can't clean up that image.




* Well, three times the standard deviation, to be precise.

posted by avixe @ 8:55 PM