7.2.1.1Calculating a Difference Image

Referring to Figure 7.1(a), suppose the object is brighter than the background. With the help of difference image, one positive region in the front of movement and one negative region in the rear of movement can be obtained. The moving information of the object, or the shape of some parts of an object can be further obtained. If taking the differences for all adjacent two images in a series, and making the logic AND of positive regions and negative regions, respectively, the shape of an entire object can finally be found. Figure 7.1(b) illustrates this procedure, a rectangular region is gradually moved down and sequentially travel across the different parts of the oval object, combining the results of all times, a complete ellipse object is produced.

If a series of images have been collected under the relative motion between the image acquisition device and the scene being shot, then the pixels that have been changed can be determined with the help of the motion information presented in the image. Suppose the two images f(x, y, ti) and f(x, y, tj) were collected at the time ti and tj, respectively, then the difference image obtained is

$d_{ij}\left(x,y\right)=\{\begin{array}{l}1\left|f\left(x,y,t_i\right)-f\left(x,y,t_j\right)\right|>T_g\\ 0\text{ otherwise}\end{array}\left(7.1\right)$

where Tg is the gray-level threshold. The pixel with value 0 in difference image corresponds to the place where no change occurs between the time before and after the current time (for changing arising from motion). The pixel with value 1 in difference image corresponds to the place where change occurs between the time before and after the current time. This change is often caused by the motion of object. However, the pixel with value 1 may also arising from other different circumstances, such as f(x, y, ti) is a pixel belonging to the moving object while f(x, y, tj) is a pixel belonging to background, or vice versa. Other examples include that f(x, y, ti) is a pixel belonging to a moving object, while f(x, y, tj) is a pixel belonging to another moving object, or f(x, y, tj) is a pixel belonging to the same moving object but at another location (so the gray-level may be different). Example 3.4 in Volume I of this book set has shown an instance that the object moving information can be detected by using image difference.

The threshold Tg in eq. (7.1) is used to determine whether the gray-levels of two consecutive images exists obvious difference. Another method is to use the likelihood ratio to identify if there is significant difference:

$\frac{{\left[\frac{{\sigma }_i+{\sigma }_j}{2}{+\left(\frac{{\mu }_i+{\mu }_j}{2}\right)}^2\right]}^2}{{\sigma }_i\cdot {\sigma }_j}>T_s\left(7.2\right)$

where μi, μj and σi, σj are the mean and variance of two collected images at time ti and tj, respectively; Ts is the significance threshold.

In real applications, due to the influence of random noise, the places where no pixels to move could also have some nonzero difference values between two images. To distinguish the movement of pixels with the influence of noise, it is possible to use a larger threshold value for the difference image, that is, when the difference is greater than a pre-determined threshold, then the pixels would be considered as had moved. In addition, as the pixels with value 1 that caused by noise in image are generally more isolated, so these pixels can also be removed by connectivity analysis. However, such an approach could sometimes remove also those pixels belonging to smaller objects and/or belonging to slow motion objects.

7.2.1.2Calculating a Cumulative Difference Image

To overcome the above-mentioned problem with random noise, using multiple images can be considered. If the change at one location only appears occasionally, it can be judged as noise. Let a series of image be f(x, y, t1), f(x, y, t2), ..., f(x, y, tn), and the first image f(x, y, t1) be the reference image. By comparing the first image with each of subsequent image, a cumulative difference image(ADI) can be obtained. In this image, the value at each location is the sum of the number of changes in each comparison.

One example for cumulative difference image ADI is given in Figure 7.2. Figure 7.2(a) shows an image captured at time t1, there is a square object inside, which is moved horizontally to the right one pixel per unit time. Figure 7.2(b, c) represents the images captured at time t2 and t3 (after one and two time units), respectively. Figure 7.2(d, e) corresponds to cumulative difference images for the next time t2 and t3, respectively. Figure 7.2(d) is the common difference image discussed earlier, the left square marked with 1 corresponds to the gray-level difference (as a unit) between the trailing edge of the object in Figure 7.2(a) and the background in Figure 7.2(b), and the right square marked with 1 corresponds to the gray-level difference (also as a unit) between the background in Figure 7.2(a) and the leading edge of the object in Figure 7.2(b). Figure 7.2(e) can be obtained by adding Figure 7.2(d) to the gray-level difference of Figure 7.2(a, c), in which the gray difference between 0 and 1 is two units, and the gray difference between 2 and 3 is also two units.

Referring to the example above, it is shown that the cumulative difference image ADI has three functions:

In practical applications, three types of ADI can be distinguished Gonzalez (2008): absolute ADI (Ak(x, y)), positive ADI (Pk(x, y)) and negative ADI (Nk(x, y)). Assuming the gray-level of moving object is larger than that of background, then for k > 1, the three types of definitions of ADI (taking f(x, y, t1) as reference, and Tg is as above) are:

$A_k\left(x,y\right)=\{\begin{array}{l}{A}_{k-1}\left(x,y\right)+1\left|f\left(x,y,t_1\right)-f\left(x,y,t_k\right)\right|>T_g\\ A_{k-1}\left(x,y\right)\text{ otherwise}\end{array}\left(7.3\right)$

$P_k\left(x,y\right)=\{\begin{array}{l}{P}_{k-1}\left(x,y\right)+1\left|f\left(x,y,t_1\right)-f\left(x,y,t_k\right)\right|>T_g\\ P_{k-1}\left(x,y\right)\text{ otherwise}\end{array}\left(7.4\right)$

$N_k\left(x,y\right)=\{\begin{array}{l}{N}_{k-1}\left(x,y\right)+1\left|f\left(x,y,t_1\right)-f\left(x,y,t_k\right)\right|<-T_g\\ N_{k-1}\left(x,y\right)\text{ otherwise}\end{array}\left(7.5\right)$

The above three types of ADI values are all the results of the pixel counting, they are initially zero. The following information can be obtained from them:

7.3.1.1Basic Principle

Motion detection is to find the motion information in the scene. An intuitive approach is to compare the current frame to be checked with the original background without motion information, the difference in the comparison indicates the result of movement. First consider a simple case. There is a moving object in a stationary scene (background), then the difference caused by the movement of this object in adjacent two video frames would appear at the corresponding place. In this case, by computing a difference image (as above) could detect moving objects and locate their positions.

Calculating a difference image is a simple and fast method for motion detection, but the result would not be good enough in a number of cases. This is because the calculation of difference images will detect all light variations, environment ups and downs (background noise), camera shake, etc. together with the object motion. This problem is more serious especially when the first frame is taken as the reference frame. Therefore, the true motion of objects can only be detected in very tightly controlled situations (such as in the unchanged environment and background).

A reasonable idea for motion detection is not to consider that the background is entirely stationary, but to calculate and maintain a dynamic (satisfy some models) background frame. This is the basic idea of background modeling.

There is a simple background modeling method, which uses the mean or median of N frames prior to the detection of the current frame, to determine and update the value of each pixel in the N cycle frame. One particular algorithm includes the following steps:

This approach based on average values for maintaining the value of the background is relatively simple, with small amount of calculation, but the result would be not very good when there are multiple objects or slow motion objects in the scene.

7.3.1.2Typical Methods in Applications

Here, some typical and basic background modeling methods used in real situations are introduced. They divide the foreground extraction process into two steps: model training and actual detection. A mathematical model for background is established through the training, and the model is used in detection to eliminate background and to obtain the foreground.

Approach Based on Single Gaussian Model Single Gaussian model-based approach considers that the values of the pixels follow a Gaussian distribution in the video sequence. Concretely, for each fixed pixel location, the mean μ and variance σ of the position of the pixel values in N frames of training sequence are calculated, from which a unique single Gaussian background model is identified. During the motion detection, the method of background subtraction is carried out to calculate the difference between the pixel values in current frame image and the pixel values of the background of the model, then the difference is compared to the threshold value T (often take 3 times of variance), i. e. according to |μT –μ| ≤ 3σ, the pixel can be determined as belonging to foreground or background.

This model is relatively simple but requires more stringent application conditions. For example, it requires no significant changes in light intensity in a long time, while the moving foreground has small shadow in the background during the period of detection. Another disadvantage is the high sensitivity for the change of light (light intensity), which can cause the model does not hold (both mean and variance are changed). When moving foreground existing in the scene, it may cause large false alarm rate. This is because there is only one model, the moving foreground cannot be separated from stationary background.

Approach Based on Video Initialization In the case that the background of the training sequence is stationary, but moving foreground exists, if it is able to first extract out the background values of each pixel, and to separate moving foreground from background, then the background modeling can be carried out, the foregoing problem would be overcame. This process can also be seen as initializing the training video before the background modeling, so that the influence of moving foreground on the background modeling could be filtered out.

In practice, a minimum length threshold T1 is first set for N frames training images containing moving foreground, and then, this threshold is used to select the sequence of length N for each pixel location in the sequence, to obtain several sub-sequence {Lk}, k = 1,2,..., from which the sequence with longer length and smaller variance will be selected as the background sequence.

By this initialization, the case that background is stationary while moving foreground exists in the training sequence is transformed to the case that background is stationary and no moving foreground in the training sequence. In this situation, it is still possible to use the approach based on single Gaussian model (as discussed above) for background modeling.

Approach Based on Gaussian Mixture Model When the movement exists also in the background of training sequence, the result based on the method of single Gaussian model is not very suitable. In this case a more robust and effective approach is modeling each pixel by mixed Gaussian distribution, namely Gaussian mixture model(GMM). In other words, the modeling is made for each state in background. The model parameters of states are updated according to the data belonging to the state, in order to solve the problem of moving background problem under the background modeling. According to local nature, some Gaussian distributions represent foreground while others represent background. The following algorithm can distinguish these Gaussian distributions.

The basic method based on GMM is sequentially reading N frames of training images, each time the iterative modeling is carried out for every pixel. Suppose that a pixel having a gray level f(t), t = 1,2,..., at the time t, f(t) can be modeled by using K (K is the maximum number of pixels allowed for each model) Gaussian distributions $N\left({\mu }_k,{\sigma }_k^2\right)$, where k = 1,..., K. Gaussian distribution changes over time with the change of scene, so it is a function of time, and can be written as

$N_k\left(t\right)=N\left[{\mu }_k\left(t\right),{\sigma }_k^2\left(t\right)\right],k=1,\mathrm{...},K\left(7.9\right)$

The main concern for the choice of K is computational efficiency, and K is often taking values of 3–7.

At the beginning of the training, an initial standard deviation is set. When a new image is read, the pixel value of this image is used to update the original pixel values of the background model. For each Gaussian distribution a weight wk(t) is added (the sum of all weights is 1), so the probability of observing f(t) is

$P\left[f\left(t\right)\right]={\displaystyle \sum _{k=1}^K{w}_k\left(t\right)\frac{1}{\sqrt{2\pi }}\exp \left[\frac{-{\left[f\left(t\right)-{\mu }_k\left(t\right)\right]}^2}{{\sigma }_k^2\left(t\right)}\right]}\left(7.10\right)$

EM algorithm can be used to update the parameters of the Gaussian distribution, but it is computationally expensive. An easy way is to compare each pixel with the Gaussian function, if it falls within the average range of 2.5 times the variance, then it is considered to be a match, that is, it fits to the model, so it can be used to update the values of the mean and variance of the model. If the number of models for current pixel is less than K, a new model is to be established for this pixel. If there are more than one matches appearing, the best can be chosen.

If a match is found, then for a Gaussian distribution l:

$w_k\left(t\right)=\{\begin{array}{l}\left(1-\alpha \right)w_k\left(t-1\right)k\ne 1\\ w_k\left(t-1\right)k=1\end{array}\left(7.11\right)$

Then w is renormalized. In eq. (7.11), a is a learning constant, 1/a determines the rate of parameter change. The parameters to match the Gaussian function can be updated as follows:

${\mu }_k\left(t\right)=\left(1-b\right){\mu }_1\left(t-1\right)+bf\left(t\right)\left(7.12\right)$

${\sigma }_k^2\left(t\right)=\left(1-b\right){\sigma }_l^2\left(t-1\right)+b{\left[f\left(t\right)-{\mu }_k\left(t\right)\right]}^2\left(7.13\right)$

where

$b=aP\left[f\left(t\right){\mu }_l,{\sigma }_l^2\right]\left(7.14\right)$

If no match is found, the Gaussian distribution corresponding to the minimum weight can be replaced by a new Gaussian distribution with mean f(t). Compared to other K – 1 Gaussian distributions, it has a higher variance and lower weight, so it may become part of the local background. If K models have been checked and they do not meet the conditions, then the model corresponding to the smallest weight is replaced with a new model, the mean value of the new model is the pixel value, and an initial standard deviation is set. Continuous in this way until all the training images are trained.

At this moment, the Gaussian distribution the most likely to be assigned to the gray value of the current pixel can be determined. Then, it is required to make sure whether it belongs to the foreground or the background. This may be determined by means of a constant B corresponding to the whole process of observation. Suppose the ratios of background pixels in all frames are greater than B, then all Gaussian distributions can be ranked according to wk(t)/σk(t), a higher value indicates a large weight, or a small variance, or both. These cases correspond to the situations that the given pixel is likely to belong to the background.

Approach Based on Codebook In the codebook based method, each pixel is represented by a codebook, a codebook may comprise one or more code words, and each code word represents a state (Kim, 2004). The initial code is learnt by means of a group of training frame images. There are no restrictions on the content of the training frame images that can contain moving foreground or moving background. Next, a time-domain filter is used for filtering out the code words representing a motion of the foreground and keeping the code words representing background; and a spatial filter is used to recover those codewords wrongly filtered out, so as to reduce the false alarm caused by the occurrence of sporadic foreground regions in the background. Such codebook represents a compressed form of a background model in video sequence.

7.3.1.3Some Experiment Results

Background modeling is a training-testing process. It uses some earlier frame images in the beginning of a sequence to train a background model. This model is then applied to the rest frame images, and the motion is tested according to the difference between the current frame and the background model. In the simplest case, the background is stationary in the training sequence, and there is no moving foreground. Some complicated situations include: the background is stationary, but there is moving foreground in training sequence; the background is not static, but there is no moving foreground in the training sequence. The most complicated situation is that the background is not static, and there is also moving foreground in the training sequence. In the following, some experiment results obtained by using background modeling for the first three cases are illustrated (Li, 2006).

Experimental data are from three sequences of an open access, universal video library (Toyama, 1999). There are a total of 150 color images in a sequence, each of them has a resolution of 160 × 120. During the experiment, image editing software has been used to provide the binary reference results, then each of the background modeling method is used to detect the moving object in the sequence, and a binary test result is obtained. For each sequence, 10 images are selected for testing. The test results are compared with the reference results, the average detection rate (the ratio of the number of foreground pixels detected over the real number of foreground pixels) and the average false alarm rate (the ratio of the number of no-foreground pixels detected over the number of pixels detected as foreground) are collected.

Results for Stationary Background with No Moving Foreground A set of experiment results are shown in Figure 7.4. In the sequence used, the initial scene consists of only stationary background, the goal is to detect the person subsequently entered in the scene. Figure 7.4(a) is a scene after the entering of a person. Figure 7.4(b) shows the reference result. Figure 7.4(c) gives the test results obtained with a method based on a single Gaussian model. The detection rate of this method is only 0.473, while the false alarm rate is 0.0569. It is seen from Figure 7.4(c) that a lot of pixels have not been detected (in regions of low gray-level pixels), some error detected pixels on the background have be found, too.

Results for Stationary Background with Moving Foreground A set of experiment results are shown in Figure 7.5. In the sequence used, the initial scene has a person inside but was leaved later, the goal is to detect the leaved person. Figure 7.5(a) is a scene when the person has not left. Figure 7.5(b) shows the reference result. Figure 7.5(c) gives the test result obtained with a method based on video initialization. Figure 7.5(d) gives the test result obtained with a method based on codebook.

The comparison of these two methods shows that the detection ratio of the method based on codebook is higher than that of the method based on video initialization, and the false alarm rate of the method based on codebook is lower than that of the method based on video initialization. This is because the codebook method has construct many codewords for each pixel so the detection rate is improved, while the spatial filter used in detection process reduces the false alarm rate. Some statistical results are shown in Table 7.1.

Results for Moving Background Without Moving Foreground A set of experiment results are shown in Figure 7.6. In the sequence used, the initial scene has a shaking tree in the background, the goal is to detect the person getting in after then. Figure 7.6(a) is a scene after the person has entered. Figure 7.6(b) shows the reference result. Figure 7.6(c) gives the test result obtained with a method based on Gaussian mixing model. Figure 7.6(d) gives the test result obtained with a method based on codebook.

The comparison of these two methods shows that both methods have specifically designed models for moving background so that higher detection rates are achieved (The former has a little high rate than the latter). Because the former one does not have the processing steps corresponding to the spatial filter in the latter method, the false alarm rate of the former method is a little high than that of the latter. Specific statistical data are shown in Table 7.2.

Finally, it should be noted that the method based on single Gaussian model is relatively simpler, but the situations it could be used are less popular, as it can be only used for the cases of stationary background without moving foreground. Other methods have tried to overcome the limitations of single-Gaussian model-based method, but their common problem is that if the background needs to update, then the entire background model should be recalculated, rather than just updating parameters with a simple iteration.

7.3.2.1Optical Flow Equation

Let a particular image point is at (x, y) at time t, this point will move to the point (x + dx, y + dy) at time t + dt. If the time interval dt is small, it may be desirable (or assumed) that the gray level of this image point remains unchanged. In other words, there is:

$f\left(x,y,t\right)=f\left(x+dx,y+dy,t+dt\right)\left(7.15\right)$

The right-hand side may be expanded with a Taylor series, let dt → 0, taking the limit and omitting the higher order terms available will produce

$-\frac{\partial f}{\partial t}=\frac{\partial f}{\partial x}\frac{\partial x}{\partial t}+\frac{\partial f}{\partial y}\frac{\partial y}{\partial t}=\frac{\partial f}{\partial x}u=\frac{\partial f}{\partial y}v=0\left(7.16\right)$

where u and v are the moving speed of the image point in the X and Y directions, respectively, which constitutes a velocity vector. Let

$f_x=\partial f/\partial x{f}_y=\partial f/\partial y{f}_t=\partial f/\partial t\left(7.17\right)$

Then, the optical flow equation is obtained:

$\left[f_x,f_y\right]•{\left[u,v\right]}^T=-f_t\left(7.18\right)$

Optical flow equation shows that the gray level changing rate in time at a point is the product of the gray level changing rate in space at this point and the moving velocity of this point in space.

In practice, the gray-level changing rate in time can be estimated with the first-order differential average along the time axis:

$\begin{array}{l}{f}_t\approx \frac{1}{4}\left[f\left(x,y,t+1\right)+f\left(x+1,y,t+1\right)+f\left(x,y+1,t+1\right)+f\left(x+1,y+1,t+1\right)\right]\\ -\frac{1}{4}\left[f\left(x,y,t\right)+f\left(x+1,y,t\right)+f\left(x,y+1,t\right)+f\left(x+1,y+1,t\right)\right]\left(7.19\right)\end{array}$

The gray-level changing rate in space can be estimated with the first-order differential average along X and Y directions:

$\begin{array}{l}{f}_t\approx \frac{1}{4}\left[f\left(x+1,y,t\right)+f\left(x+1,y+1,t\right)+f\left(x+1,y,t+1\right)+f\left(x+1,y+1,t+1\right)\right]\\ -\frac{1}{4}\left[f\left(x,y,t\right)+f\left(x,y+1,t\right)+f\left(x,y,t+1\right)+f\left(x,y+1,t+1\right)\right]\left(7.20\right)\end{array}$

$\begin{array}{l}{f}_t\approx \frac{1}{4}\left[f\left(x,y+1,t\right)+f\left(x+1,y+1,t\right)+f\left(x,y+1,t+1\right)+f\left(x+1,y+1,t+1\right)\right]\\ -\frac{1}{4}\left[f\left(x,y,t\right)+f\left(x+1,y,t\right)+f\left(x,y,t+1\right)+f\left(x+1,y+1,t+1\right)\right]\left(7.21\right)\end{array}$

7.3.2.2Optical Flow Estimation Using Least Squares

Formulas (7.19)–(7.21), after substituting into eq. (7.18), can be used to estimate the optical flow components u and v with the help of least squares. In two adjacent images f(x, y, t) and f(x, y, t + 1), pixels with the same u and v are selected at N different positions. Let ${\widehat{f}}_t^{\left(k\right)},{\widehat{f}}_x^{\left(k\right)}$, and ${\widehat{f}}_y^{\left(k\right)}$ represent the estimations of ft,fx, and fy, at kth position (k = 1,2,..., N), respectively:

$f_t=\left[\begin{array}{c}-{\widehat{f}}_t^{\left(1\right)}\\ -{\widehat{f}}_t^{\left(2\right)}\\ ⋮\\ -{\widehat{f}}_t^{\left(N\right)}\end{array}\right]F_{xy}=\left[\begin{array}{c}-{\widehat{f}}_x^{\left(1\right)}\\ -{\widehat{f}}_x^{\left(2\right)}\\ ⋮\\ -{\widehat{f}}_x^{\left(N\right)}\end{array}\begin{array}{c}-{\widehat{f}}_y^{\left(1\right)}\\ -{\widehat{f}}_y^{\left(2\right)}\\ ⋮\\ -{\widehat{f}}_y^{\left(N\right)}\end{array}\right]\left(7.22\right)$

Then the least squares estimations for u and v are:

${\left[uv\right]}^T={\left(F_{xy}^T{F}_{xy}\right)}^{-1}{F}_{xy}^T{f}_t\left(7.23\right)$