Abstract:
A temporal sequence of images is acquired of a dynamic scene. Spatial gradients are determined using filters. By taking advantage of the sparseness of outputs of the filters, an intrinsic background image is generated as median filtered gradients. The intrinsic background image is then divided into the original sequence of images to yield intrinsic foreground images. The intrinsic foreground images can be thresholded to obtain a detection mask.

Description:
FIELD OF THE INVENTION  
       [0001]     This invention relates generally to image processing, and more particularly to detecting foregrounds in a sequence of images.  
       BACKGROUND OF THE INVENTION  
     Foreground Detection  
       [0002]     In many computer vision applications, e.g., surveillance, tracking, and recognition applications, a necessary first step is to detect foreground objects in a scene. Typically, this is done by a background subtraction method  100 , as shown in  FIG. 1A . A sequence of input images  110  acquired of a scene is processed  120  to generate a background image  130 . The background image is then subtracted  140  from the images  110  to yield foreground images  150 .  
         [0003]     Prior art foreground detection methods either makes strict assumptions about the composition of the scene, or fail to handle abrupt illumination changes, or are computationally complex and time consuming.  
         [0004]     Prior art foreground detection methods can generally be classified as single-layer or multi-layer. Single-layer methods develop a single dynamical model based on the past observations.  
         [0005]     The simplest way to construct a single-layer background image is to measure a mean or variance of the pixel intensities. The intensities can be measured on a per (RGB) channel basis, to characterize color variations. Then, the intensities can be used as a threshold to detect foreground regions. However, such an averaging operation usually produces ‘ghost’ regions that are neither the true background nor true foreground.  
         [0006]     One method models statistical distributions of background pixels with a Gaussian function and alpha-blending, C. R. Wren, A. Azarbayejani, T. J. Darrell, and A. P. Pentland “Pfinder: Real-time tracking of the human body,”  PAMI,  19(7), pp. 780-785, July 1997. A background image B t  is updated according to a current image I t  using a preset blending weight α, such that B t =(1−α)B t−1 +αI t .  
         [0007]     The blending weight α adjusts how fast the background should blend with the current image. That averaging method is very sensitive to the selection of the blending weight. Depending to the value of α, the foreground objects can be subsumed into the background, or illumination changes are not accommodated.  
         [0008]     An alternative ‘voting’ method selects intensity values based on frequency of occurrence. That ‘voting’ approach has advantages over averaging. It does not blur the background and allows sudden illumination changes. The major drawback for the voting approach is its computational complexity. Quantization can be applied to decrease the number of candidate values and the number of operations. However, quantization decreases the ability to separate the foreground from the background.  
         [0009]     Kalman filters can also be used for background detection, K. Karmann, A. Brand, “Time-varying image processing and moving object recognition,”  Elsevier Science Publish.,  1990, C. Ridder, O. Munkelt, and H. Kirchner, “Adaptive background estimation and foreground detection using Kalman filtering,”  Proc. ICAM,  1995, and K. Toyama, J. Krumm, B. Brumitt, B. Meyers, “Wallflower: Principles and Practice of Background Maintenance,”  Proc. of Int&#39;l Conf on Computer Vision , pp. 255-261, 1999. A version of the Kalman filter that operates directly on the data subspace is described by J. Zhong and S. Sclaroff, in “Segmenting foreground objects from a dynamic, textured background via a robust Kalman filter,”  Proc. of IEEE Int&#39;l Conf. on Computer Vision , pp. 44-50, 2003.  
         [0010]     A similar autoregressive model acquires properties of dynamic scenes, A. Monnet, A. Mittal, N. Paragios, and V. Ramesh, “Background modeling and subtraction of dynamic scenes,”  Proc. of IEEE Int&#39;l Conf on Computer Vision , pp. 1305-1312, 2003.  
         [0011]     The Kalman filter provides optimal estimates for the state of a discrete-time process that obeys a linear stochastic difference equation, e.g., the intensities of the background. The various parameters of the Kalman filter, such as a transition matrix, a process noise covariance, and a measurement noise covariance can change at each time step. By using larger covariance values, the background adapts quicker to illumination changes. However, the filter becomes more sensitive to noise and objects in the scene. Another drawback of the Kalman filter is its inability to distinguish multimodal distribution i.e., moving leaves or grass, or waves on water. The Kalman filter gives poor performance in the presence of large non-linearities.  
         [0012]     Another method models the background in an image with a mixture of Gaussian distribution functions, C. Stauffer and W. Grimson, “Adaptive background mixture models for real-time tracking,”  Proc. of IEEE Int&#39;l Conf. on Computer Vision and Pattern Recognition,  1999. Rather than explicitly modeling the values of all the pixels as one particular type of distribution, the background is modeled by a pixel-wise mixture of Gaussian distribution functions to support multimodal backgrounds. Based on the persistence and the variance of each Gaussian function in the mixture, the Gaussian models that correspond to background regions are determined. Pixel values that do not fit the background distributions are considered foreground, until there is a Gaussian model that includes them in the background with sufficient and consistent supporting evidence. That method includes a learning constant and a parameter that controls the proportion of the pixels that should be accounted for by the background. The mixture-of-Gaussians method is the basis for a large number of related methods, O. Javed, K. Shafique, and M. Shah, “A hierarchical approach to robust background subtraction using color and gradient information,”  MVC , pp. 22-27, 2002.  
         [0013]     The mixture methods are adaptable to illumination changes and do not cause ghost effect. Furthermore, the mixture methods can handle multimodal backgrounds. However, their performance deteriorates when the scene is dynamic and exhibits non-stationary properties in time. Another drawback of the mixture model based solutions is the computational load of constructing and updating the background models. For a large number of models in the mixture, such methods become computationally too demanding to be practical.  
         [0014]     A non-parametric method uses Gaussian kernels for modeling the density at a particular pixel, A. Elgammal, D. Harwood, and L. Davis, “Non-parametric model for background subtraction,”  Proc. of European Conf. on Computer Vision , pp. II:751767, 2000.  
         [0015]     Another method integrates optical flow in the modeling of the dynamic characteristics, A. Mittal and N. Paragios, “Motion-Based background subtraction using adaptive kernel density estimation,”  Proc. Int&#39;l Conf. on Computer Vision and Pattern Recognition,  2004.  
         [0016]     Statistical methods can use color, global and dynamic features to enhance object detection features, C. Jiang and M. O. Ward, “Shadow identification”,  Proc. of IEEE Int&#39;l Conf. on Computer Vision and Pattern Recognition , pp. 606-612, 1992, and Stauder, R. Mech, and J. Ostermann, “Detection of moving cast shadows for object segmentation”,  IEEE Transactions on Multimedia , vol. 1, no. 1, pp. 65-76, March 1999.  
         [0017]     Therefore, it is desired to improve over prior art foreground detection methods.  
         [0018]     Intrinsic Images  
         [0019]     One interpretation of a scene states that every image is the product of characteristics of the scene. Then, an ‘intrinsic’ image is a decomposition of an image that reflects one of the characteristics in the scene, H. G. Barrow and J. M. Tenenbaum, “Recovering intrinsic scene characteristics from images,”  Computer Vision Systems, Academic Press , pp. 3-26, 1978.  
         [0020]     The decomposition of input images I t  of a scene into a reflectance image R and illumination images L t  can be expressed as the product 
 
 I   t   =R·L   t .  (1) 
 
         [0021]     The reflectance image R contains the reflectance values of the scene, and the illumination images L t  contain the illumination intensities. Because the illumination images L t  represent the distribution of incident lighting in the scene, while the reflectance image R depict the surface reflectance properties of the scene, this representation becomes useful to analyze and manipulate the reflectance and lighting properties of the scene as acquired in the input images.  
         [0022]     In the prior art, intrinsic images deal with spatial characteristics within a single image of a scene, such as illumination, and reflectance as visible in image texture, and not the temporal evolution of foreground objects in the scene itself.  
         [0023]     As shown in  FIG. 1B , one decomposition method estimates a maximum likelihood to produce reflectance images  102  and illumination images  103  from a sequence of input images  101  acquired from a fixed point under significant variations in lighting conditions, Y. Weiss, “Deriving intrinsic images from image sequences,” Proc. of  IEEE Int&#39;l Conf. on Computer Vision , pp. 68-75, July, 2001. Note, that lighting from the right (R) and left (L) is clearly visible in the illumination image  
         [0024]     That method has been extended to derive varying reflectance images and corresponding illumination images from a sequence of images. Y. Matsushita, K. Nishino, K. Ikeuchi, and S. Masao, “Illumination normalization with time-dependent intrinsic images for video surveillance,”  Proc. of IEEE Int&#39;l Conf. on Computer Vision and Pattern Recognition,  2004. Matsushita et al. also describe an illumination eigenspace, which captures the illumination variations. In that method, the scene is static, the only thing that is detected are variation of external factors of the scene, such as lighting conditions. The motion of foreground objects is not considered.  
         [0025]     Another method recovers an illumination invariant image, which is similar to a reflectance image, from a single color image, G. D. Finlayson, S. D. Hordley and M. S. Drew, “Removing Shadows from Images,”  Proc. of European Conf. on Computer Vision  Vol. 4, pp. 823-836, 2002. Finlayson et al. assume the input image contains both non-shadowed surfaces and shadows cast on those surfaces. They calculate an angle for an ‘invariant direction’ in a log-chromaticity space by minimizing an entropy of the color distribution.  
         [0026]     Another method uses multiple cues to recover shading and reflectance images from a single image, M. Tappen, W. Freeman, E. Adelson, “Recovering Shading and Reflectance from a single image,” NIPS, 2002 Tappen et al., use both color information and a classifier trained to recognize gray-scale patterns. Each intrinsic image is classified as being caused by shading or a change in the surfaces reflectance. Note, that method also does not consider the motion of foreground objects in a scene.  
         [0027]     Another deterministic method uses gray levels, and local and static features, M. Kilger, “A shadow handler in a video-based real-time traffic monitoring system,”  Proc. of IEEE Workshop on Applications of Computer Vision , pp. 11-18, 1992, and D. Koller, K. Danilidis, and H. Nagel, “Model-based object tracking in monocular image sequences of road traffic scenes,”  Int&#39;l Journal of Computer Vision , vol. 10, pp. 257-281, 1993.  
         [0028]     In general, prior art intrinsic images do not consider motion of foreground objects in a scene. Therefore, it is desired to provide improved intrinsic images that do reflect motion variations in the scene itself.  
         [0029]     Furthermore, it is desired to use the improved intrinsic images to improve foreground detection.  
       SUMMARY OF THE INVENTION  
       [0030]     Instead of conventional foreground detection by way of background subtraction, the invention decomposes images of a dynamic scene into time-varying intrinsic background and foreground images. A product of these intrinsic images characterizes the scene.  
         [0031]     A temporal sequence of images is acquired of the scene. Spatial gradients are determined using filters. By taking advantage of the sparseness of outputs of the filters, an intrinsic background image is generated as median filtered gradients. The intrinsic background image is then divided into the original sequence of images to yield intrinsic foreground images.  
         [0032]     The invention also provides a robust method for thresholding intrinsic foreground images to obtain a detection mask. The invention can also detect static and moving lines.  
         [0033]     The method is computationally efficient and effectiveness even under abrupt and severe illumination changes. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0034]      FIG. 1A  shows a prior art method for detecting foregrounds in scenes;  
         [0035]      FIG. 1B  shows prior art intrinsic images;  
         [0036]      FIG. 2  shows a method for detecting foregrounds in scenes according to the invention;  
         [0037]      FIG. 3  shows detailed steps of the method of  FIG. 2 ; and  
         [0038]      FIG. 4  shows intrinsic images if a road scene according to the invention; and  
         [0039]      FIG. 5  shows intrinsic images if a golf scene according to the invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
     Intrinsic Background Image  
       [0040]     As shown in  FIG. 2 , the invention provides a method  200  for detecting foreground regions in images. The foreground regions typically represent moving objects in the scene. A sequence of input images  210  acquired of a scene is processed  300  to generate an intrinsic background image  230 . Each of the input images  210  is divided  240  by the intrinsic background image to yield a sequence of intrinsic foreground images  250 . In a preferred embodiment, the intrinsic background image is updated as each current image in the sequence  210  is processed.  
         [0041]     The invention characterizes a scene as a product of the foreground and background characteristics, i.e., 
 
 I   t   =B·F   t ,  (2) 
 
 where the background image B t    230  is relatively static, and the foreground images F t    250  characterizes dynamic characteristics of the scene, e.g., moving objects. It should be noted that the background image can vary, but over a much longer time-scale as the foreground images. Therefore, according to the invention, a division  240  of the input images by the intrinsic background image determines the intrinsic foreground images  
         F   t     =         I   t     B     .         
 
 Note that this definition is in stark contrast with the prior art, which expresses the background and foreground characteristics as an additive inference, i.e., I t =B+F t , and the foreground image is F t =I t −B. 
 
         [0042]     In real-world scenes, the static and dynamic characteristics change over time, although the ‘static’ characteristics change substantially slower than the dynamic characteristics. For example, in a ‘static’ outdoor scene, the movement of building shadows is relatively slow, and in an indoor scene, a bag is eventually subsumed into the background when it is left unattended.  
         [0043]     Therefore, the notion that a single time invariant static image can represent a background is wrong. While the time invariant background image B(x, y) reasonably describes the static scene without moving objects, the estimated foreground images F(x, y, t) tend to contain considerable amount of texture and shadows, especially if global illumination varies. Therefore, unlike the method according to Weiss, which implicitly assumes the reflectance images are time invariant of the illumination images, the invention uses time variant intrinsic images, i.e., both the background and foreground images are updated over time.  
         [0044]     As shown in detail in  FIG. 3 , The invention acquires a sequence of N input images  210 , {I t−N , . . . , I t−1 , I t }, of a scene. The image  211  is a current input image. A rate at which the images are acquired can depend on a speed of moving objects in the scene. If overlap between appearances of moving objects in consecutive images is minimized, the derived statistics of the objects are less likely to contaminate the background images  230 .  
         [0045]     Therefore, a support set of images is {I t−kN , . . . , I t−k , I t }, where k is a sampling period. Although it is reasonable to select a longer sampling period, a short sampling period is used for scenes where objects move fast. In any case, the sampling period k is not a critical decision. It should also be noted that images can be acquired at varying rates dependent on an average motion in the scene, over time.  
         [0046]     Next, determine  310  the logarithm (log) of the intensity values of each input image I t    210 . This produces ‘log’ images  311 - 312 , where log image  312  is for the current input image  211 .  
         [0047]     Next, spatial derivative filters s n    320  are applied to the log images i t    311 - 312  to determine intensity gradients according to 
 
s n *i t , 
 
         [0048]     where ‘*’ represents a convolution. The derivative filters can be s 0 =[1 −1], s 1 =[1 −1] T .  
         [0049]     Instead of using derivative filters, a line detector of the for f line  =[−1 2 −1] can also be used. The output of this filter is also sparse. This filter can capture static and moving edges in a scene, which is essential for the shape extraction.  
         [0050]     Because the filter outputs are Laplacian distributed and independent over space and time, a maximum likelihood estimate of the filtered background image {circumflex over (b)} tn  is a median image  330  given by 
 
{circumflex over (b)} tn =median t {s n *i t }.  (3) 
 
 Note, the median image  330  is the result of filtering over a ‘window’ of n previous log input images  311  and the current log input image  312 . By updating for each new input image, the intrinsic background image is always correct. This is a direct result of the fact that when derivative filters  320  are applied to images of natural scenes, the outputs of the filters tend to be sparse. 
 
         [0051]     The intrinsic foreground images f tn    250  are then determined by using estimated filtered background images {circumflex over (b)} tn  according to 
 
 {circumflex over (f)}   tn =( s   n   *i   t )− {circumflex over (b)}   tn .  (4) 
 
         [0052]     The median image  330  is now ‘reverse’ filtered by solving a systems of linear equations  
                   b   ^     t     =     g   ⋆     (       ∑   n     ⁢       s   n   r     ⋆       b   ^     tn         )         ,   and           (   5   )                     f   ^     t     =     g   ⋆     (       ∑   n     ⁢       s   n   r     ⋆       f   ^     tn         )         ,           (   6   )             
 
         [0053]     where s n   r    340  is the reversed filter of s n , and the filter g  350  is the filter which satisfies the Fourier equation 
 
 G =( S   n   ·S   n   r ) −1 .  (7) 
 
         [0054]     The filter g  350  is independent of the input image sequence  210 , and can be predetermined.  
         [0055]     Still in the logarithmic domain, the output  351  of the filter  350 , which is the log of intrinsic background image, is then subtracted from the log of the current image  310 . In the log domain this corresponds to the division  240 .  
         [0056]     The final intrinsic foreground images  250  and intrinsic background images  230  are then obtained by applying inverse logarithms  361 - 362  according to B t =e b     t   , F t =e f     t   .  
         [0057]     A mask image M t  can also used. The mask image M t  represents the foreground pixels in the current input image I t  based on intensity statistics of a difference between the current intrinsic background and foreground images D t (x, y)=B t (x, y)−Ft(x, y).  
         [0058]     The distribution of this difference can be approximated by a Gaussian function. Thus, the mean μ t  and variance σ 2   t  of the distribution are determined, and the 95% percentile is assigned as the threshold τ=2.5 σ. The mask image M t  is given by  
                 M   t     ⁡     (     x   ,   y     )       =     {         1             ⁢              D   ⁡     (     x   ,   y     )       -     μ   1            &gt;     2.5   ⁢           ⁢     σ   t                   0             ⁢   otherwise                     (   8   )             
 
         [0059]     For a sequence of input images  401  of a traffic scene,  FIG. 4  shows corresponding intrinsic background images  402 , intrinsic foreground images  403 , and mask images  404 , according to the invention. It is clear that the mask image tracks the moving vehicles. The scene contains moving bushes and clouds in the distance and diffuse shadows under the vehicles. Note that the foreground images  402  are accurate and do not contain these artifacts. It is also seen that the diffuse shadows are eliminated in the mask images  404 .  
         [0060]      FIG. 5  shows an input image  501  of a golf scene, the corresponding intrinsic background image  502 , intrinsic foreground image  503 , and mask image  504 . In this scene sky color changes and shadows are more eminent. The method according to the invention accurately decomposes the input image into background and foreground images.  
       Effect of the Invention  
       [0061]     The invention detects foreground regions, such as moving objects from a sequence of input images acquired by a stationary camera. As opposed to the additive background/foreground scenario of the prior art, the invention decompose a sequence into a product of time-varying multiplicative intrinsic background and foregrounds images. There are several advantages of the proposed method. A product has a higher gain than a sum, and therefore the invention is less sensitive to sudden and severe illumination changes. The method is not model based, thus model fitting is not required. The method is computationally efficient and can be implement into a real-time system. The method does not require a fine-tuning of parameters. The invention can also estimate a static edge map of a scene. Most importantly, the multiplicative background/foreground characterization yields better performance than the prior art additive scenario.  
         [0062]     Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.