PaperlayerView exact revision on arXiv

Source-linked AI summary

A Low-Complexity Algorithm for Static Background Estimation from Cluttered Image Sequences in Surveillance Contexts

Vikas Reddy, Conrad Sanderson, Brian C. Lovell

arXiv:1303.2465v1cs.CV

TL;DR

Cluttered sequences often leave the true background unavailable, so the paper estimates static backgrounds through sequential block-based MRF processing. The method obtains better background estimates than median filtering and stable-intensity intervals, and Wallflower foreground segmentation improves when initialized with its estimates.

  • Problem

    Background models are difficult to obtain from sequences where foreground objects occlude the static background, a situation common in uncontrolled environments.

    Source: §I · p. 1

  • Method

    The method processes frames sequentially, maintaining distinct block representatives and using MRF clique potentials based on candidate and neighborhood frequency responses.

    Source: §I · p. 1, §III · pp. 2–3, A. Overview of the Algorithm · p. 3

  • Results

    The method obtains considerably better background estimates than median filtering and intervals of stable intensity, while Wallflower foreground segmentation improves when it initializes a single-Gaussian background model.

    Source: §V · p. 12

  • Takeaways & Limitations

    The estimated background can initialize foreground segmentation, with improved segmentation reported on the Wallflower dataset.

    Source: §V · p. 12

    The approach is confined to static backgrounds; extending it to non-static backgrounds is future work.

    Source: §I · p. 1, §V · p. 12

Abstract

from arXiv · show

For the purposes of foreground estimation, the true background model is unavailable in many practical circumstances and needs to be estimated from cluttered image sequences. We propose a sequential technique for static background estimation in such conditions, with low computational and memory requirements. Image sequences are analysed on a block-by-block basis. For each block location a representative set is maintained which contains distinct blocks obtained along its temporal line. The background estimation is carried out in a Markov Random Field framework, where the optimal labelling solution is computed using iterated conditional modes. The clique potentials are computed based on the combined frequency response of the candidate block and its neighbourhood. It is assumed that the most appropriate block results in the smoothest response, indirectly enforcing the spatial continuity of structures within a scene. Experiments on real-life surveillance videos demonstrate that the proposed method obtains considerably better background estimates (both qualitatively and quantitatively) than median filtering and the recently proposed "intervals of stable intensity" method. Further experiments on the Wallflower dataset suggest that the combination of the proposed method with a foreground segmentation algorithm results in improved foreground segmentation.

I. INTRODUCTION

Background subtraction supports foreground detection, but clean training sequences are often unavailable in uncontrolled environments, motivating background estimation from cluttered sequences. Earlier pixel-level approaches use temporal intensity patterns, yet can fail when the background is exposed less often than the foreground.

I. INTRODUCTION

  • Background subtraction supports foreground detection, but clean training sequences are often unavailable in uncontrolled sites, motivating estimation from persistently occluded, static scenes.Strong illumination changes can also make an existing background model ineffective.Source: §I · p. 1

A. Pixel-level Processing

  • Pixel-level approaches include median filtering, stable-intensity intervals, Bayesian estimation, interval objectives, codewords, and temporal pixel clustering.Median filtering is correct only when the background is exposed for more than 50% of the time.Source: A. Pixel-level Processing · p. 2
  • Pixel-based techniques can fail when background exposure is shorter than foreground exposure.This limits their reliability when foreground objects occupy a pixel location for longer than the background does.Source: A. Pixel-level Processing · p. 2

B. Region-level Processing

Region-level methods exploit blocks but can miss spatial context or incur high computational cost. The proposed algorithm uses MRF labelling and sequential frame processing, with clique potentials designed to favor smooth frequency responses.

B. Region-level Processing

  • Farin et al. classify blocks using temporal SAD and apply median filtering to those deemed background, but omit neighboring-background correlation, risking errors with quasi-stationary objects.Colombari et al. incorporate spatial correlations during iterative block selection, but can blend foreground and background for slow or quasi-stationary objects and may not run in real time.Source: B. Region-level Processing · p. 2

C. Hybrid Approaches

  • Hybrid methods use optical flow or MRF-based energy minimization, but optical flow is computationally intensive and MRF solutions can be costly on small image sequences.A reported loopy-belief-propagation prototype took about 2.5 minutes for 10 QVGA images.Source: C. Hybrid Approaches · p. 2

III. PROPOSED ALGORITHM

  • The proposed algorithm recasts estimation as MRF labelling and processes frames sequentially; clique potentials use combined frequency responses to favor smooth candidate-neighborhood configurations while ignoring high frequencies.The authors identify ignored high-frequency DCT coefficients as a way to address image noise.Source: §III · pp. 2–3

A. Overview of the Algorithm

The algorithm processes a stationary-camera sequence of static background blocks by collecting representative labels at each location, then initializing and iteratively completing the background in an MRF framework.

A. Overview of the Algorithm

  • The method has three stages: collect block-label representatives, initialize nodes with a single representative, then estimate the remaining background iteratively using ICM.The sequence is assumed to reveal the static background briefly at each block location, and one representative is assumed to correspond to background.Source: A. Overview of the Algorithm · p. 3
  • Each block location maintains distinct labels from its temporal line, represented by cluster means with occurrence weights and recursively updated variance.A label’s weight records how often it occurs at that location.Source: A. Overview of the Algorithm · p. 3
  • Nodes with a single representative initialize the corresponding background location, while the remaining locations are filled progressively through MRF-based optimization.ICM computes the optimal labeling by considering candidate labels and local spatial context.Source: A. Overview of the Algorithm · p. 3

B. Similarity Criteria for Labels

The algorithm groups visually similar block labels into representative sets, then uses those sets to initialize and iteratively complete the background.

B. Similarity Criteria for Labels

  • For each block location, matching labels update a representative and its variance recursively; unmatched labels become new representatives with an initial weight of one.Representative weights are incremented for matches.Source: B. Similarity Criteria for Labels · p. 4
  • Singleton representative sets initialize background locations, after which the algorithm fills empty locations and iteratively updates labels with higher posterior probability.The pseudocode repeats the label-update step for a fixed number of iterations.Source: B. Similarity Criteria for Labels · p. 4
  • Label similarity requires both correlation and mean absolute difference (MAD) constraints, combining pattern agreement with closeness in the block’s pixel space.The paper notes that correlation alone can accept blocks with very different values, while MAD alone can accept a block containing a thin foreground edge.Source: B. Similarity Criteria for Labels · p. 5
  • The MAD threshold is estimated from co-located labels in successive training frames, using the middle quartiles to exclude very low and high MAD outliers.The threshold is set to 2×(µQ31 + 2σQ31).Source: B. Similarity Criteria for Labels · p. 5

C. Markov Random Field (MRF) Framework

The MRF framework combines temporal evidence for candidate blocks with spatial context to label the background. An example recovers the region hidden by a person who occupied the scene for most of the sequence.

C. Markov Random Field (MRF) Framework

  • At each node, candidate-label likelihoods from temporal observations are combined with prior spatial information represented by an MRF, and the maximum-posterior label is selected.ICM iteratively maximizes local conditional probabilities until convergence.Source: C. Markov Random Field (MRF) Framework · pp. 5–6
  • The likelihood favors labels with more occurrences, but caps their weights at five times the sequence frame rate to limit bias from exceptionally persistent foreground objects.The paper gives a parked car visible for 950 of 1,000 frames as an example of the risk without the cap.Source: C. Markov Random Field (MRF) Framework · p. 6
  • Because temporal likelihood alone can err when foreground lasts slightly longer than background, the method incorporates Gibbs-distribution spatial priors derived from clique energies.A lower energy indicates a greater probability of being the best match relative to neighboring labels.Source: C. Markov Random Field (MRF) Framework · p. 6
  • The prior receives more weight than temporal likelihood, with η empirically set to the number of neighboring nodes used for clique-potential calculation, typically three.The log-posterior combines the label likelihood and prior probability.Source: C. Markov Random Field (MRF) Framework · p. 6
  • 350 of 450 frames showed a standing person, yet the algorithm estimated the background that person occluded; pixel-level techniques are likely to fail in this case.The person walked off during the final 100 frames.Source: C. Markov Random Field (MRF) Framework · p. 6

D. Node Initialisation

The algorithm seeds the background from unambiguous locations and expands into empty nodes only when neighboring labels provide sufficient spatial context.

D. Node Initialisation

  • Nodes whose representative sets contain one label are initialized directly; if all sets are ambiguous, the largest-weight label at a corner node supplies a heuristic seed.This fallback assumes at least one corner region is static in the video frames.Source: D. Node Initialisation · p. 6
  • An empty node is labeled when three neighboring nodes provide background labels in three different directions, allowing edge continuity to be assessed across orientations.When three such neighbors are unavailable, an already labeled four-connected neighbor can be used, with the clique reduced to two adjacent nodes.Source: D. Node Initialisation · p. 7
  • ICM addresses incorrect initial assignments that could propagate to neighboring nodes by revisiting labels where an eight-connected neighbor changed in the previous iteration.This is contrasted with the authors’ previous algorithm [10].Source: D. Node Initialisation · p. 7

E. Calculation of the Energy Potential

The method scores candidate blocks by the spectral response of their cliques in a DCT-based MRF energy calculation. It favors the candidate producing the smoothest response, using only the lower 75% of frequency components.

E. Calculation of the Energy Potential

  • Candidate labels for an unknown node are evaluated through the spectral response of each possible clique, using the DCT for decorrelation and ease of hardware implementation.The clique's 2D DCT coefficients are stored in an M × M matrix, with the DC coefficient set to zero to focus on spatial variation.Source: E. Calculation of the Energy Potential · p. 7
  • The preferred candidate is the one whose clique yields a smoother spectral distribution, reflecting the assumption that nearby pixels have similar intensities.Figure 5 illustrates four candidate labels; candidate 3 has the smoother distribution in the example.Source: Figure 5 · p. 7, E. Calculation of the Energy Potential · p. 8
  • The energy calculation uses only the lower 75% of frequency components after a zig-zag scan, excluding higher components associated with image noise.Source: E. Calculation of the Energy Potential · p. 8
  • The resulting energy potential is computed for each candidate label and corresponding local configuration, with potentials also calculated for the other three cliques.Source: E. Calculation of the Energy Potential · p. 8

IV. EXPERIMENTS

Experiments tested the method on greyscale sequences using 16 × 16 nodes. A Matlab prototype ran at 17 fps, and backgrounds were estimated after a single labelling pass.

  • The experiments used greyscale sequences with 16 × 16 nodes; T1 was empirically set to 0.8 and automatically determined T2 ranged from 1 to 4.T1 was selected in preliminary experiments, while T2 was measured on several image sequences.Source: §IV · p. 8
  • A Matlab prototype on a 1.6 GHz dual-core processor yielded 17 fps, with background estimates produced after labelling nodes once and without subsequent iterations.The authors expected higher performance from a C++ implementation, but did not report that performance as measured.Source: §IV · p. 8
  • The experiments separately evaluated background-estimation quality and the effect of the method on a foreground-segmentation algorithm.Source: §IV · p. 8

A. Standalone Performance

Standalone performance was compared with median filtering and the ISI method on 20 surveillance videos. The evaluation combined background-quality comparisons with sensitivity testing of T1.

  • The evaluation compared the proposed method with median filtering and the ISI method on 20 videos from CAVIAR, CANDELA, and a Brisbane railway station.Source: A. Standalone Performance · p. 8
  • CANDELA sequences were selected using four criteria: at least 700 frames, significant background occlusions, a true background available in at least one frame, and largely static backgrounds.Sequences were resized to 320×240 pixels.Source: A. Standalone Performance · p. 8
  • The standalone evaluation included qualitative and quantitative assessments, plus a separate study of sensitivity to T1.Source: A. Standalone Performance · p. 8

1) Qualitative Evaluation:

Across the reported comparisons, the proposed method produced better-quality backgrounds than median filtering and ISI. The qualitative examples include dynamic and quasi-stationary foreground objects, while the quantitative evaluation reports AGE and CEPs across different input lengths.

1) Qualitative Evaluation:

  • The qualitative examples cover four videos with foreground objects that were dynamic or quasi-stationary for much of the sequence.Source: 1) Qualitative Evaluation · p. 8
  • Median filtering and ISI leave traces of long-stationary foreground objects, while the proposed method looks visually improved but can absorb a stationary person into the background.Source: 1) Qualitative Evaluation · p. 8

2) Quantitative Evaluation:

3) Sensitivity of T1:

The minimum AGE for T1 was obtained at 0.8, and MRF-based background initialization improved foreground segmentation on Wallflower, with the largest reported gain on Bootstrap.

3) Sensitivity of T1:

  • T1 = 0.8 produced the minimum averaged AGE between estimated and true backgrounds on the sampled CAVIAR sequences.The value was selected by comparing AGE across several T1 settings.Source: 3) Sensitivity of T1 · p. 11

B. Evaluation by Foreground Segmentation

  • Wallflower includes both static and dynamic backgrounds, although the proposed method is primarily designed for static-background estimation, making this evaluation potentially non-optimal for its intended domain.The authors characterize the results as suggestive across conditions.Source: B. Evaluation by Foreground Segmentation · p. 11
  • Foreground segmentation used a Gaussian background-subtraction model initialized either from training frames or from the MRF-estimated background and its variances.Median filtering and ISI were excluded because they do not specify pixel variances for their estimated backgrounds.Source: B. Evaluation by Foreground Segmentation · p. 11
  • Over 62% improvement on Bootstrap and 16.67% average improvement across six Wallflower sequences were reported; TimeOfDay degraded.The authors attribute the TimeOfDay degradation to lighting changes that made identical labels appear unique, understating background variance and increasing false positives.Source: B. Evaluation by Foreground Segmentation · p. 11, Table III · p. 11

C. Additional Observations

The method outperformed median filtering and intervals of stable intensity on real-life surveillance videos, and improved Wallflower foreground segmentation when used for background initialization. Its reported scope and behavior include static scenes, reduced memory use, and specific failure conditions.

C. Additional Observations

  • When foreground objects remain in motion and the background is visible longer, all tested approaches performed reasonably well and median filtering may suffice; the proposed method was better when this condition did not hold.Source: C. Additional Observations · p. 11
  • The algorithm sometimes mis-estimates backgrounds with strong edges when a smooth, similar-intensity foreground occluder yields a smoother spectral response.Source: C. Additional Observations · p. 12
  • The state space required on average 5% of the memory needed to store all frames.The authors contrast this with methods that typically store all frames before processing.Source: C. Additional Observations · p. 12
  • RGB and YUV experiments were marginally better than grayscale, which the authors conjecture reflects grayscale's representation of scene spatial continuity.Source: C. Additional Observations · p. 12

V. MAIN FINDINGS AND FUTURE WORK

  • The method estimates static backgrounds from cluttered, noisy surveillance videos, including scenes where foreground objects are not always moving or occlude the background much of the time.Source: §V · p. 12
  • Moderate illumination changes leave performance invariant because the energy potential uses only AC DCT coefficients; duplicate representatives for visually identical blocks remain an issue, and non-static backgrounds are future work.Source: §V · p. 12
  • Real-life surveillance experiments found considerably better background estimates than median filtering and intervals of stable intensity, while Wallflower foreground segmentation also improved with MRF-based initialization.The Wallflower experiment initialized a single-Gaussian background model.Source: §V · p. 12
Loading 1303.2465v1…