PaperlayerView exact revision on arXiv

Source-linked AI summary

Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation

Xiaowei Zhou, Can Yang, Weichuan Yu

arXiv:1109.0882v2cs.CV

TL;DR

The paper asks how to separate moving foreground objects from background automatically without separate training, despite nonrigid motion and dynamic scenes. It proposes DECOLOR, a unified low-rank outlier-detection framework that jointly estimates object support and background, and reports better object-detection and background-estimation accuracy than RPCA.

  • Problem

    The paper addresses automatic foreground-background separation without separate training in videos containing nonrigid motion or complex, dynamic backgrounds.

  • Method

    DECOLOR detects contiguous moving-object outliers in a low-rank representation while jointly estimating background through an alternating optimization algorithm.

  • Results

    DECOLOR achieves better object-detection and background-estimation accuracy than the state-of-the-art RPCA algorithm.

  • Takeaways & Limitations

    The framework can segment moving objects while learning the background without training sequences.

  • Takeaways & Limitations

    DECOLOR works poorly when the background is a 3D scene with a large depth variation.

Abstract

from arXiv · show

Object detection is a fundamental step for automated video analysis in many vision applications. Object detection in a video is usually performed by object detectors or background subtraction techniques. Often, an object detector requires manually labeled examples to train a binary classifier, while background subtraction needs a training sequence that contains no objects to build a background model. To automate the analysis, object detection without a separate training phase becomes a critical task. People have tried to tackle this task by using motion information. But existing motion-based methods are usually limited when coping with complex scenarios such as nonrigid motion and dynamic background. In this paper, we show that above challenges can be addressed in a unified framework named DEtecting Contiguous Outliers in the LOw-rank Representation (DECOLOR). This formulation integrates object detection and background learning into a single process of optimization, which can be solved by an alternating algorithm efficiently. We explain the relations between DECOLOR and other sparsity-based methods. Experiments on both simulated data and real sequences demonstrate that DECOLOR outperforms the state-of-the-art approaches and it can work effectively on a wide range of complex scenarios.

I. INTRODUCTION

The paper targets automatic moving-object segmentation without separate training, especially when foreground motion, camera motion, or background dynamics complicate motion-based methods. DECOLOR jointly detects objects and estimates background through contiguous outliers in a low-rank representation.

  • Problem: Training-based detectors and background subtraction require labeled examples or object-free sequences, limiting their applicability to automated video analysis.Motion-only methods avoid training but face additional assumptions in complex scenes.
  • Problem: Motion segmentation can handle large camera motion, but assumes rigid or smooth motion that may fail with nonrigid foreground shape changes.Foreground motion may be complicated by nonrigid shape changes.
  • Problem: Dynamic backgrounds, such as moving escalators, waving trees, and sea waves, challenge methods that assume static backgrounds.The airport example treats an operating escalator as background while targeting people.
  • DECOLOR: DECOLOR models vectorized video frames with a low-rank background and detects moving objects as outliers, reducing assumptions about foreground behavior.Low-rank background representations accommodate global background variations.
  • DECOLOR: The unified framework performs object detection and background estimation without training sequences and compensates for camera motion within batch processing.The optimization is solved by an effective algorithm despite a non-convex energy.
  • DECOLOR: DECOLOR jointly estimates outlier support and the low-rank matrix, incorporating spatial contiguity through Markov Random Fields.The formulation explicitly models outlier support rather than leaving spatial distribution implicit.

II. RELATED WORK

Prior video object-detection methods use supervised detectors, motion segmentation, or background subtraction, but each relies on assumptions or inputs that limit complex continuous-object scenes.

  • Motion segmentation methods address continuously present moving objects but face aperture problems, occlusion, and video noise.
  • Dense optical-flow methods decompose videos into smooth motion layers with changes concentrated at layer boundaries, but require accurate motion analysis.
  • Trajectory-based methods can handle large camera motion, but require tracked point trajectories and produce only sparse-point segmentation before postprocessing.
  • Standard background subtraction generally requires object-free training data, while initialization methods assume static backgrounds and are limited by dynamic backgrounds or moving cameras.
  • Background-subtraction models capture global background variations such as illumination changes and dynamic textures through correlations between video frames.

III. CONTIGUOUS OUTLIER DETECTION IN THE LOW-RANK REPRESENTATION

DECOLOR models video frames as a low-rank background plus foreground support, using outlier detection and spatial-temporal structure to identify contiguous moving objects.

  • DECOLOR estimates the foreground support S and background images B directly from a sequence D without requiring a separate object-free training sequence.
  • Foreground motion creates intensity changes that cannot fit the low-rank background model, so those changes are detected as outliers.
  • An MRF models spatially or temporally neighboring foreground-support labels so contiguous foreground pieces are preferred.
  • The signal model fits background-region observations with i.i.d. Gaussian noise while leaving foreground intensities unconstrained.
  • The formulation imposes a low-rank background constraint, relaxes rank with the nuclear norm, and uses parameters α, β, and γ to control model complexity and support regularization.

C. Algorithm

DECOLOR alternates between estimating the low-rank background and foreground support, solving the respective subproblems efficiently with SOFT-IMPUTE and graph cuts.

  • Joint optimization over B and S is difficult, so DECOLOR alternates between a convex B-step and a combinatorial S-step.
  • The optimal solutions of both alternating subproblems can be computed efficiently.
  • The B-step is a matrix-completion problem solved efficiently by SOFT-IMPUTE using singular-value thresholding.
  • The S-step forms a binary first-order MRF that can be solved exactly with graph cuts when the background estimate is fixed.
  • Using only spatial-neighbor connections separates the graph into image-specific subgraphs, substantially reducing computational cost.

3) Parameter tuning:

DECOLOR tunes its background-complexity and spatial-smoothness parameters through sequential threshold updates, and its fixed-parameter energy decreases toward a local minimum.

  • 3) Parameter tuning:: The algorithm starts with a large α and decreases it while the estimated background rank remains at most K, using warm starts for efficiency.
  • 3) Parameter tuning:: The outlier sparsity parameter β is tied to image noise, typically set to β = 4.5σ̂^2 using an online residual-variance estimate.
  • 3) Parameter tuning:: β is reduced by a factor η_2 = 0.5 after each iteration until it reaches 4.5σ̂^2, allowing progressively more outliers as the model improves.
  • 3) Parameter tuning:: For fixed parameters, the energy decreases monotonically because the adaptive coefficients α, β, and γ keep decreasing.
  • 3) Parameter tuning:: 20 iterations are typically sufficient for convergence precision 10^-5, although the algorithm converges to a local minimum.
  • Unlike PCP, DECOLOR retains the ℓ0 penalty, explicitly estimates outlier support S, and uses MRF continuity to detect contiguous outliers.

2) Sparse signal recovery:

DECOLOR extends sparse signal recovery by jointly learning the background representation and foreground outlier support from a batch of test images. Unlike prior fixed-basis methods, it targets moving-object segmentation over short sequences.

  • Sparse signal recovery: Sparse signal recovery models each testing image as previous-frame combinations plus sparse foreground and Gaussian-noise terms.The background is represented by Φw, while e captures foreground outliers and ϵ captures noise.
  • Limitations of prior methods: Prior methods use fixed bases from training sequences or previous frames, limiting the representation available during testing.DECOLOR instead treats the basis as unknown and learns it from the test-image batch.
  • DECOLOR: DECOLOR factorizes the low-rank background B into basis Φ and coefficients W while estimating both jointly with the outlier support.The factorization uses Φ ∈ Rm×r and W ∈ Rr×n, where r is the rank of B.
  • DECOLOR: DECOLOR jointly estimates foreground and background by outlier detection during a short sequence in which objects continuously appear.This setting is more challenging than detecting new objects using a training sequence without those objects.

IV. EXTENSION TO MOVING BACKGROUND

DECOLOR is extended to videos with moving backgrounds by introducing domain transformations and jointly estimating transformed frames, background, foreground errors, and motion parameters. The motion updates use incremental refinement and can be performed efficiently per frame.

  • Moving-background model: The moving-background extension introduces domain transformations to compensate for background motion caused by moving cameras.The model uses 2D parametric transforms for translation, rotation, and planar deformation.
  • Moving-background model: Each transformed frame participates in the decomposition D ◦τ = B + E + ϵ, with τ collecting the frame-specific motion parameters.Affine motion uses p = 6 parameters, while projective motion uses p = 8.
  • Optimization: DECOLOR estimates motion parameters together with B and S by iteratively minimizing the transformed low-rank decomposition energy.The energy includes nuclear-, entrywise sparsity-, and structured-sparsity penalties.
  • Optimization: Incremental refinement linearizes the transformed data after small motion updates, reducing each motion subproblem to weighted least squares with a closed-form solution.Framewise transformations allow the updates of τ1, …, τn to be performed separately.
  • Implementation: The algorithm is initialized by roughly aligning each frame to the middle frame before the main DECOLOR loops.A robust multiresolution method performs the pre-alignment.

V. EXPERIMENTS

Experiments evaluate DECOLOR on synthesized low-rank videos with moving foreground occlusions, using qualitative comparisons and quantitative measures of detection and background recovery. The simulations vary object width, noise, and model parameters.

  • Qualitative comparison: DECOLOR produces fewer false detections and a less corrupted recovered background than PCP in the qualitative comparison.Unlike PCP, DECOLOR directly outputs the foreground support without postprocessing.
  • Evaluation: Detection accuracy is evaluated against the true foreground support using precision, recall, and their combined F-measure.Higher F-measure indicates better detection accuracy.
  • Quantitative evaluation: Fig. 3 evaluates F-measure and RMSE as functions of object width and SNR, and examines the effects of K and γ over 50 random trials.The parameter study uses W = 25 and SNR = 10.
  • Evaluation: Background recovery is evaluated with RMSE measuring the difference between the estimated and true background matrices.The metric is defined from ˆB and B0.

1) Comparison to PCP:

DECOLOR is more robust than PCP to contiguous and relatively dense moving foregrounds in the reported simulations, while its performance depends on noise, rank selection, motion continuity, and foreground texture. Large static or textureless regions can become inseparable from the low-rank background.

  • Comparison to PCP: DECOLOR yields fewer false detections and a less corrupted recovered background than PCP in the synthesized qualitative comparison.The comparison concerns the estimated foreground support and recovered low-rank background.
  • Comparison to PCP: As foreground width increases, PCP degrades significantly while DECOLOR remains less affected, demonstrating greater robustness to less-sparse outliers.Both methods perform well when W = 10, when outliers are very sparse.
  • Comparison to PCP: DECOLOR maintains better performance than PCP at relatively high SNR but drops dramatically when SNR < 2.The reported interpretation attributes this behavior to non-convex penalties being robust to gross errors but sensitive to entrywise perturbations.
  • Effects of parameters: With true rank(B0) = 3, the optimal result occurs at K = 3, while accuracy decreases smoothly for larger K.The nuclear-norm shrinkage helps prevent rapid overfitting when K exceeds the true rank.
  • Effects of parameters: DECOLOR’s detection remains stable across γ ∈ [β, 10β], underscoring the role of the contiguity prior.The γ = 0 result lies between PCP and DECOLOR with γ = β and has larger variance.
  • Inseparable cases: DECOLOR detects foregrounds accurately over a wide range of texture and width conditions, except for large, textureless foregrounds.The difficult case arises because undetectable interior motion can leave regions unchanged long enough to fit the low-rank model.
  • Inseparable cases: When foreground interiors remain unchanged, parts of the foreground may be absorbed into the low-rank background and cannot be separated correctly.This establishes a scope boundary for scenes with large or slowly moving textureless objects.

B. Real Sequences

DECOLOR is evaluated on real surveillance sequences against sparse recovery, PCP, median filtration, and MoG, including crowded and dynamic-background settings. It recovers backgrounds and foreground masks accurately, with higher F-measure than the compared approaches on the evaluated sequences.

  • 1) Comparison to sparse signal recovery:: DECOLOR recovers a clean background from continuously occluded frames, whereas ProxFlow cannot recover the background and produces inaccurate segmentation.Using DECOLOR’s learned low-rank background as ProxFlow bases improves the subsequent results.
  • 1) Comparison to sparse signal recovery:: DECOLOR jointly estimates backgrounds and foregrounds without requiring foreground-free training sequences, addressing crowded-scene conditions where such data may be unavailable.Sparse signal recovery requires background images without foreground, which is not always available in crowded surveillance scenes.
  • 2) Background estimation:: DECOLOR accurately recovers backgrounds and foreground masks for large objects that remain present in every frame, without postprocessing.The comparison includes PCP, median filtration, and mixture-of-Gaussians background models.
  • 2) Background estimation:: DECOLOR avoids PCP’s residual foreground ghosts and false detections caused by ℓ1-penalty sensitivity to contiguous occlusion.Median filtration can leave ghosts, while MoG reduces some false positives but may blend foreground intensity and increase false negatives.
  • 2) Background estimation:: DECOLOR models periodic dynamic backgrounds such as escalators and water surfaces, producing cleaner backgrounds and fewer false detections than PCP.The escalator’s repeated motion is recognized as background, and the water-surface example yields a cleaner recovered background.
  • 2) Background estimation:: DECOLOR outperforms the other approaches on all sequences in the F-measure evaluation.The evaluation uses manual annotations as ground truth for the sequences shown in Fig. 6.

3) Moving cameras:

For sequences captured by moving cameras, DECOLOR aligns images, learns a background model, and detects objects correctly. It performs better on people sequences but works poorly with substantial camera motion in deep 3D scenes.

  • 3) Moving cameras:: DECOLOR aligns images, learns a background model, and detects objects correctly in the moving-camera examples.Border regions extrapolated during transformation are constrained as background for segmentation and treated as missing when estimating the background.
  • 3) Moving cameras:: DECOLOR’s moving-camera pipeline outputs transformed images, estimated backgrounds, and foreground masks alongside Brox–Malik results and ground truth.Figure 7 compares these outputs across four sequences.
  • 3) Moving cameras:: DECOLOR avoids the complicated motion analysis used by Brox–Malik, which analyzes point trajectories and clusters them before producing dense pixel-level regions.DECOLOR directly generates the segmentation from the motion cue.
  • 3) Moving cameras:: On the people sequences, DECOLOR performs better than Brox–Malik, whose motion tracking misses the lady’s feet.Brox–Malik relies on correct motion tracking and clustering, which is difficult for small, nonrigidly moving objects.
  • 3) Moving cameras:: DECOLOR works poorly when the camera moves substantially through a 3D scene with large depth variation.Its parametric motion model compensates only for planar background motion, with cars9 and cars10 given as examples.

4) Dynamic foreground:

DECOLOR extends low-rank background modeling to dynamic and rapidly changing scenes while jointly segmenting moving objects. Its performance is satisfactory but remains limited by non-convex optimization, scope assumptions, and batch operation.

  • 4) Dynamic foreground:: DECOLOR detects fast-changing textures such as smoke even when their motion lacks periodicity and cannot be modeled as low-rank.In the smoke example, the background behind smoke cannot be recovered because it is always occluded.
  • 4) Dynamic foreground:: DECOLOR segments moving objects by formulating detection as outlier detection and using low-rank modeling for complex backgrounds.The framework avoids complicated motion computation and jointly supports object segmentation and background learning.
  • 4) Dynamic foreground:: Compared with PCP, DECOLOR uses a non-convex penalty and MRFs to detect relatively dense, contiguous outlier regions more greedily.The paper establishes a direct link between DECOLOR and PCP.
  • 4) Dynamic foreground:: DECOLOR’s alternating optimization converges to a local optimum, so results depend on initialization of the estimated foreground support.PCP instead minimizes its energy globally.
  • 4) Dynamic foreground:: DECOLOR may classify unmoved objects or large textureless regions as background because they can enter the low-rank model.The paper suggests adding object appearance or shape priors as future work.
  • 4) Dynamic foreground:: DECOLOR is currently unsuitable for real-time object detection because it operates in batch mode.The authors plan an online version that updates the low-rank model incrementally.
Loading 1109.0882v2…