Subtraction

As was described above, the subtraction algorithm proceeds by warping the pixels in the key image into the reference images and comparing the color intensity values. Let:

$$\begin{array}{ll} (x,y) & \mbox{position in key image} \\ ... ...{\bf R}(x', y') & \mbox{reference image pixel} \\ \end{array}$$

We need to define a binary masking function $m({\bf K}(x, y), {\bf R}(x', y'))$ for construction of the background subtracted image. The masking function $m(\cdot,\cdot)$ determines the complexity and accuracy of the algorithm.

In its simplest form function $m({\bf K}(x, y), {\bf R}(x', y'))$ is just a set of pixels not satisfying the disparity constraint:

$$m({\bf K}(x, y), {\bf R}(x', y')) = \left\{ \begin{array}{... ...\bf R}(x', y') \\ 1 & \mbox{otherwise} \end{array} \right.$$

In reality we never get measurements good enough to comply with this this sort of screening, so we have to relax this constraint to compensate for possible errors and formulate the comparison to accept a value within some tolerance range ${\hbox{\rlap{$\epsilon$}\kern .4pt{$\epsilon$}}}$:

$$m({\bf K}(x, y), {\bf R}(x', y')) = \left\{ \begin{array}{... ...{$\epsilon$}}} \\ 1 & \mbox{otherwise} \end{array} \right.$$

Along with this straightforward method of subtraction, we have implemented a more robust, sub-sampling method which performs subtraction over a small neighborhood of a pixel. This technique introduces the least amount of interference with the normal computations, giving the advantage of being more forgiving about the precision of the disparity map. We partition the original key image into a grid of small windows and compute a mean of each window of the grid. Then we warp the pixels of each window of the key image into the reference image and compute the mean of the resulting set of generally non-contiguous points. We then compare the means by the same procedure as above. For a k x k window of pixels in the key image W_ij, the window mean images are computed as:

$$\begin{eqnarray*} {\bf\bar{K}}_{ij} & = & {1 \over k^2} \sum_{x, y \in W_{ij}... ... & = & {1 \over k^2} \sum_{x', y' \in W'_{ij}}{{\bf R}(x', y')} \end{eqnarray*}$$

where W'_ij is the set of reference image pixel locations to which the pixels in the key image window were warped. The masking function is defined as:

$$m({\bf K}(x, y), {\bf R}(x', y')) = \left\{ \begin{array}{... ...in W'_{ij} \\ 1 & \mbox{otherwise} \\ \end{array} \right.$$

which yields a blocked (or equivalently sub-sampled) background subtracted image. The proposed algorithm is simple and fast enough for real time performance. It is as fast as the normal template based background subtraction algorithm used in [4] in that each pixel is examined once. One obvious advantage is that in using disparity for identifying a candidate background, we can accommodate for changing textures and lighting conditions. The algorithm effectively removes shadows and can be modified to remove surfaces selectively.