Dynamic Mode Decomposition for Real-Time Background/Foreground Separation in Video

• Real-time video surveillance requires separation methods that remain accurate and robust under illumination changes, location changes, and cluttered backgrounds.Source: §1 · p. 1
• The task can be formulated as separating video data into low-rank background and sparse foreground components, following the RPCA viewpoint.Source: §1 · p. 1
• DMD applies a time-Fourier interpretation of dynamical-system data, using near-zero modes for stationary background and modes bounded away from zero for foreground motion.Source: §1 · pp. 1–2
• Compared with RPCA, DMD performs approximate separation using one singular-value decomposition and one linear solve, without RPCA's exact-recovery guarantees.Source: §1 · pp. 1–2
• The paper evaluates DMD on dynamical-system noise removal, realistic surveillance videos, and a constructed video for error analysis.Source: §1 · p. 2

2.1 RPCA Algorithm

• 2.1 RPCA Algorithm: The L1 norm reduces the influence of sparse outliers and promotes sparsity, improving on L2-based PCA for corrupted data.Source: §2 · p. 2
• 2.1 RPCA Algorithm: Principal component pursuit minimizes a weighted nuclear-norm and L1-norm objective subject to the exact decomposition X = L + S.Source: §2.1 · p. 3
• 2.1 RPCA Algorithm: Under incoherence assumptions, RPCA has high probability of recovering the correct low-rank and sparse components, although tuning λ may slightly improve results.Source: §2.1 · p. 3
• 2.1 RPCA Algorithm: Exact ALM is stable and accurate, while inexact ALM converges in fewer iterations but has weaker convergence guarantees.Source: §2.1 · p. 3

2.2 Video Interpretation of the RPCA Method

• 2.2 Video Interpretation of the RPCA Method: Video frames are vectorized into a data matrix X, whose low-rank component represents background and sparse component represents moving foreground.Source: §2.2 · p. 3
• 2.2 Video Interpretation of the RPCA Method: With λ near (√n)^−1, RPCA achieves quality comparable to DMD, while decreasing or increasing λ introduces stationary pixels or removes foreground pixels.Source: §2.2 · p. 3

3.1 DMD Algorithm

• DMD analyzes snapshot data through a reduced representation of the Koopman dynamics, using SVD-based dimensionality reduction and an eigenvalue problem to obtain modes and temporal frequencies.The algorithm estimates a linear operator mapping each snapshot to the next, then computes eigenvalues, eigenvectors, and Fourier modes from the reduced system.Source: §3.1 · pp. 4–5
• The method assumes regularly spaced sampling and may model some dynamics poorly when irregular-time behavior is transformed into an apparently evenly sampled sequence.This limitation follows from DMD treating the supplied observations as regularly spaced without independently verifying their timing.Source: §3.1 · pp. 5–6

3.2 Video Interpretation of the DMD Method

• Video is suitable for DMD because frames are equally spaced in time and their pixel data can be vectorized into snapshot vectors, although reconstruction quality depends on the sequence meeting DMD assumptions.The method can reconstruct observed or potentially future frames from the sampled video data.Source: §3.2 · p. 6
• The DMD reconstruction expresses video frames as spatial modes multiplied by time-dependent exponentials and initial amplitudes, allowing the first frame to generate subsequent frames.The time vector indexes regularly sampled frames, and the diagonal temporal factor controls how the initial frame evolves.Source: §3.1 · p. 5, §3.2 · p. 6
• Modes near zero frequency represent slowly changing background, while modes bounded away from zero represent foreground motion on O(1) timescales or faster.This frequency-based distinction is the central principle for approximating low-rank background and sparse foreground components.Source: §3.2 · p. 6
• DMD handles complex modal terms by forming real-valued low-rank and sparse reconstructions, correcting negative sparse values through a residual added back to the low-rank component.The correction preserves nonnegative pixel intensities while retaining real-valued approximate reconstructions.Source: §3.2 · pp. 6–7

4.1 Surveillance Video Application

• DMD and RPCA produce comparably good surveillance-video separations, although their relative quality varies with the scene and method assumptions.In the Parked Vehicle video, DMD appears to remove more potentially stationary-background pixels; in Abandoned Bag, DMD depicts more movement trails while RPCA is more conservative.Source: §4.1 · p. 7

4.2 Timing Performance

• DMD is about 2–3 orders of magnitude faster than exact ALM RPCA and about 1 order faster than inexact ALM RPCA, enabling real-time processing without downsampling.For high- and low-resolution images, DMD processes video segments in about 0.1–0.01 seconds, while typical cameras operate at 20–30 frames per second.Source: §4.2 · p. 8, Figure 4 · p. 10

4.3 DMD and Dimensionality Reduction

• Dimensionality reduction preserves reasonably good separation even at ℓ = 1, while blurring motion and increasing sparsity; it may reduce separation costs further.The authors caution that the favorable low-dimensional result may partly reflect the limited movement of vehicles in the example.Source: §4.3 · p. 9, Figure 5 · p. 11

4.4 DMD Error Analysis

• Low-intensity objects can be confused with zero entries in the sparse component, producing spurious pixels and forward/backward movement trails.The constructed video includes a pure-black object that is absent from the DMD foreground results, while analogous trails appear in the Abandoned Bag footage.Source: §4.4 · pp. 10–11
• The measured sparse-background intensity is on the order of 10^-3 versus a true background intensity near 0.5, and thresholding can reduce spurious pixels.The error is computed on the first m − 1 frames because the final frame accumulates DMD error.Source: §4.4 · p. 11
• In the constructed 300-frame video, longer segments provide more information but also lengthen erroneous movement trails, while reducing their pixel intensity.DMD timing grows quadratically with segment size, whereas RPCA perfectly reconstructs videos for segment sizes greater than 10 frames under the tested setting.Source: §4.4 · p. 11, Figure 6 · p. 12
• DMD reconstruction error increases for larger objects relative to the frame and for fewer snapshots representing the same movement; stopped objects are not reconstructed well.High-speed and accelerating motion can still be handled fairly well when enough snapshots capture the movement.Source: §4.4 · p. 12

4.5 Iterative Application of DMD

• Applying DMD iteratively to its previous sparse output empirically decreases separation error and moves more data into the low-rank structure.The authors identify the convergence rate and theoretical basis of this behavior as future work.Source: §4.5 · p. 13, Figure 7 · p. 13

• DMD produces separation quality on par with RPCA for realistic videos while operating orders of magnitude faster.The authors report that DMD is viable for real-time foreground/background separation on laptop-level computing platforms.Source: §5 · p. 13
• DMD remains efficient enough for processing times below typical camera frame-acquisition intervals, although high-resolution images or many frames can reduce speed and available memory.The paper recommends segments large enough for adequate separation but small enough to keep processing faster than data acquisition.Source: §5 · p. 13
• Unlike RPCA, the DMD analysis lacks a proof of convergence to low-rank and sparse structures.Future work is proposed to establish rigorous results under suitable conditions and potentially combine DMD initialization with RPCA’s exact reconstruction.Source: §5 · p. 13