Source-linked AI summary
Compressed Dynamic Mode Decomposition for Background Modeling
N. Benjamin Erichson, Steven L. Brunton, J. Nathan Kutz
TL;DR
Background modeling for high-resolution video must address costly processing and challenging scene changes. The paper applies compressed DMD with sparse mode selection to reduce computation, reporting competitive speed and detection accuracy relative to leading methods, with limitations in some scenes.
Problem
High-resolution video processing is costly, while background modeling must handle unknown backgrounds and scene changes such as camera jitter, illumination changes, shadows, and dynamic backgrounds.
Source: §1 · p. 1Method
Compressed DMD decomposes a compressed video representation, with background-mode selection formulated as sparse coding and approximated using orthogonal matching pursuit.
Source: §1 · pp. 1–2Results
Frame rate is highly competitive with Gaussian mixture-based algorithms, speed gains over RPCA-based algorithms are more substantial, and F-measure is competitive with leading RPCA methods but below highly specialized Gaussian-mixture methods.
Source: §5 · p. 12Takeaways & Limitations
The reported trade-off between speed and accuracy is compelling, and GPU acceleration further improves computational time.
Source: §5 · p. 12As a batch algorithm, cDMD has difficulty detecting sleeping foreground objects and has limited capability with non-periodic dynamic backgrounds; crowded or non-periodic scenes are also identified as difficult.
Source: §4.1 · p. 10, §5 · p. 12
Abstract
from arXiv · showhide
We introduce the method of compressed dynamic mode decomposition (cDMD) for background modeling. The dynamic mode decomposition (DMD) is a regression technique that integrates two of the leading data analysis methods in use today: Fourier transforms and singular value decomposition. Borrowing ideas from compressed sensing and matrix sketching, cDMD eases the computational workload of high resolution video processing. The key principal of cDMD is to obtain the decomposition on a (small) compressed matrix representation of the video feed. Hence, the cDMD algorithm scales with the intrinsic rank of the matrix, rather then the size of the actual video (data) matrix. Selection of the optimal modes characterizing the background is formulated as a sparsity-constrained sparse coding problem. Our results show, that the quality of the resulting background model is competitive, quantified by the F-measure, Recall and Precision. A GPU (graphics processing unit) accelerated implementation is also presented which further boosts the computational efficiency of the algorithm.
1 Introduction
Background modeling must handle unknown and changing scenes while processing high-resolution video efficiently. The paper introduces compressed DMD to reduce computation and reports competitive computational performance and detection accuracy.
1 Introduction
- High-resolution video processing remains challenging alongside camera jitter, illumination changes, shadows, and dynamic backgrounds, with no single real-time method handling all challenges without performance failures.Source: §1 · p. 1
- Compressed DMD computes an accurate decomposition from a compressed video representation in a fraction of the time, addressing the costs dominated by DMD’s singular value decomposition.Source: §1 · p. 1
- Sparse mode selection is formulated as a sparsity-constrained coding problem approximated by orthogonal matching pursuit; computation is competitive with Gaussian mixtures and detection accuracy with leading RPCA algorithms.Source: §1 · p. 2
2 DMD for Video Processing
DMD models video as a sequence of snapshots and separates slowly changing background structure from foreground dynamics. For background modeling, the paper describes sparse mode selection to form a static background from the decomposition.
2.1 The Dynamic Mode Decomposition
- DMD treats successive video frames as snapshots linked by an approximately linear map, then estimates a lower-dimensional operator to avoid analyzing the full high-dimensional matrix.The frames are flattened into time-ordered columns; the reduced operator is k × k, with k no greater than the smaller matrix dimension.Source: §2.1 · p. 2
- DMD modes encode spatial structure, while their eigenvalues describe temporal evolution and their amplitudes weight each mode.The decomposition can reconstruct frames or estimate future frames, depending on how well the video meets the method’s assumptions.Source: §2.1 · p. 2, §2.2 · p. 3
2.2 DMD for Foreground/Background Separation
- Modes with continuous-time eigenvalues near zero, or discrete eigenvalue magnitudes near one, represent slowly changing content associated with the background.In the canoe sequence, the zero mode captures static background content, while modes capture the canoe and other dynamics such as waves.Source: §2.2 · p. 3, Figure 2 · p. 4
- DMD frames video separation as low-rank background and sparse foreground components, with a computational advantage over RPCA optimization methods.The paper notes that only the real part of the complex DMD reconstruction is used because original pixel intensities are real-valued.Source: §2.2 · p. 4
2.3 DMD for Real-Time Background Modeling
- Standard DMD is costly for high-resolution video because it reconstructs the full sequence, while a static background model can suffice for background subtraction.Selecting only the zero mode can underfit, whereas selecting many modes can overfit.Source: §2.3 · pp. 4–5
- The paper selects background modes through sparsity-constrained coding and uses orthogonal matching pursuit to approximate the resulting mode-selection problem.OMP iteratively selects the mode most correlated with the residual, projects the initial frame onto selected modes, and repeats until K nonzero entries are obtained; cross-validation can determine K when priors are unavailable.Source: §2.3 · p. 5
3 Compressed DMD (cDMD)
cDMD reduces the computational burden of video DMD by performing expensive calculations on compressed data while using full-state data to recover the full DMD modes. The section develops this approach through measurement-matrix choices and a GPU implementation.
3.1 Compressed Sensing and Matrix Sketching
- Compressed sensing motivates low-dimensional measurements of compressible video frames, while matrix sketching extends the compressed representation to low-rank data matrices.For low-rank X, matrix sketching can approximate its singular values and right singular vectors from a compressed representation.Source: §3.1 · pp. 5–6
3.2 Algorithm
- The algorithm assumes low-rank video data and sufficiently many incoherent measurements, then uses a truncated SVD and a low-dimensional eigendecomposition to estimate DMD modes.The truncated SVD is performed on the compressed matrix, while full modes are recovered using full-state data.Source: §3.2 · pp. 6–7
3 Compressed DMD (cDMD)
- For full-image video, cDMD performs the expensive SVD on compressed data and combines those transformations with full-state data to recover full DMD modes.The method targets reduced runtime when full image data is available.Source: §3 · p. 5, §3.2 · p. 7
3.3 Measurement Matrices
- Single-pixel measurements avoid storing a sensing matrix and its matrix multiplication, while sparse random projections offer another practical measurement-matrix option.Sparse matrix packages allow rapid execution of the compressed-data multiplication.Source: §3.3 · p. 7, §3.2 · p. 7
3.4 GPU Accelerated Implementation
- The GPU-accelerated DMD implementation is substantially faster than the MKL-accelerated routine, although CPU–GPU memory bandwidth remains a limitation.The authors identify random-number generation, dot products, SVD, eigenvalue decomposition, and least-squares solving as GPU-suitable computations; asynchronous memory operations can mitigate the bandwidth overhead.Source: §3.4 · pp. 8–9
4 Results
The evaluation measures foreground detection with recall, precision, and F-measure across real-video benchmarks, then examines computational performance and sensing-matrix trade-offs. cDMD is competitive with RPCA methods on BMC and improves on zero-mode modeling in most tested CD sequences, while compressed and GPU implementations reduce computation.
4 Results
- Detection is evaluated by thresholding the difference between a frame and its reconstructed background, then comparing the foreground mask with ground truth using recall, precision, and F-measure.Recall measures detection of moving-object pixels, precision measures correctness of predicted foreground pixels, and F-measure is their harmonic mean.Source: §4 · p. 9
4.1 Evaluation on Real Videos
- In five of six CD sequences, sparse-coding cDMD dominates zero-mode modeling; gains are substantial for Canoe and Fountain02, while Park tends to over-fit.Compressed DMD is slightly better than exact DMD overall, which the authors attribute to randomized algorithms’ implicit regularization.Source: §4.1 · pp. 9–10, Figure 8 · p. 10
- On BMC, cDMD’s average F-value is about 0.648, slightly better than GoDec, nearly as good as LSADM, and lower than RSL.The evaluation uses individual thresholds for each of the nine videos.Source: §4.1 · p. 10
- The batch method struggles with sleeping foreground objects and non-periodic dynamic backgrounds; incremental background maintenance can better address sleeping objects, and median filtering or morphology can reduce false positives.The reported weak cases include non-periodic motion in videos 001, 005, 008, and 009.Source: §4.1 · pp. 10–11
4.2 Computational Performance
- For HD 1280 × 720 video, GPU cDMD is about 4× faster than CPU cDMD and 21× faster than exact DMD.Compression avoids the expensive SVD and reduces time complexity from O(knm) to O(kpm); computing the full modes remains costly but parallelizable.Source: §4.2 · p. 11
- Gaussian measurements give the best F-measure but become more expensive; single-pixel measurements are most efficient, while sparse sensing offers the best time–accuracy trade-off.Single-pixel measurements are memory-efficient and simple to implement; sparse sensing requires sparse-matrix packages.Source: §4.2 · p. 11
- Sparse measurements show lower bootstrap dispersion than single-pixel measurements, whose greater information loss is given as the explanation.Randomized sensing matrices can cause fluctuations in background-model quality.Source: §4.2 · p. 11
5 Conclusion and Outlook
The conclusion presents cDMD as a candidate for fast high-definition video background modeling, reporting competitive speed and accuracy with clear scene-specific limitations.
5 Conclusion and Outlook
- Runtime excluding foreground-mask computation and accuracy are evaluated as sample count varies; F-measure confidence intervals compare sparse and single-pixel measurements.Table 1 covers nine real BMC videos and results for three robust PCA algorithms adapted from [12].Source: Figure 10 · p. 11, Figure 11 · p. 11, Table 1 · p. 12
- cDMD's frame rate is highly competitive with Gaussian mixture-based algorithms, while its speed increase over RPCA-based algorithms is even more substantial.Fig. 12 reports CPU/GPU runtime including foreground-mask computation across resolutions (200 frames), with automatically selected target rank and p=1000 samples.Source: §5 · p. 12, Figure 12 · p. 12
- F-measure is competitive with leading RPCA algorithms [12] but not optimized Gaussian mixture-based algorithms [2], especially on crowded or non-periodic dynamic scenes.Source: §5 · p. 12
- Future work aims to improve background subtraction quality and integrate multi-resolution ideas with cDMD to separate foreground video into dynamic targets when needed.Source: §5 · p. 12
A Notation
The notation appendix catalogs symbols for scalar quantities, vectors, and matrices used in the paper.
A Notation
- Scalars include k for target rank, p for measurements, s for sparse samples, K for non-zero amplitudes, and n and m for pixels and frames.Source: A Notation · p. 13
- Vectors include x for a flattened video frame, y for a compressed frame, φ for DMD modes, and β for sparsity-constrained amplitudes.Source: A Notation · p. 13
- Matrices include X and X′ for snapshot sequences, Y and Y′ for compressed sequences, and Φ and ΦY for DMD modes and compressed DMD modes.The appendix also lists rank-reduced operators and eigenvectors, amplitudes, Vandermonde matrices, and truncated compressed SVD factors.Source: A Notation · p. 13