Randomized low-rank Dynamic Mode Decomposition for motion detection

Fast and robust decomposition of a matrix representing a spatial grid through time.Rapid approximation for robust principal component analysis.Competitive performance in terms of recall and precision for motion detection.GPU accelerated implementation allows faster computation. This paper introduces a fast algorithm for randomized computation of a low-rank Dynamic Mode Decomposition (DMD) of a matrix. Here we consider this matrix to represent the development of a spatial grid through time e.g. data from a static video source. DMD was originally introduced in the fluid mechanics community, but is also suitable for motion detection in video streams and its use for background subtraction has received little previous investigation. In this study we present a comprehensive evaluation of background subtraction, using the randomized DMD and compare the results with leading robust principal component analysis algorithms. The results are convincing and show the random DMD is an efficient and powerful approach for background modeling, allowing processing of high resolution videos in real-time. Supplementary materials include implementations of the algorithms in Python.

• Publication year

  2015

• Venue

  Computer Vision and Image Understanding

• Publication date

  2015-12-11

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1016/j.cviu.2016.02.005arXiv 1512.03526
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An Efficient Gauss-Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations

  2015cited by this paper
• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset

  2015cited by this paper
• RSVDPACK: An implementation of randomized algorithms for computing the singular value, interpolative, and CUR decompositions of matrices on multi-core and GPU architectures

  2015cited by this paper
• Multi-Resolution Analysis of Dynamical Systems using Dynamic Mode Decomposition

  2015cited by this paper
• RSVDPACK: Subroutines for computing partial singular value decompositions via randomized sampling on single core, multi core, and GPU architectures

  2015cited by this paper
• Multiresolution Dynamic Mode Decomposition

  2015cited by this paper
• A Self-Adjusting Approach to Change Detection Based on Background Word Consensus

  2015cited by this paper
• Subspace Iteration Randomization and Singular Value Problems

  2014cited by this paper
• A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos

  2014cited by this paper
• Dynamic Mode Decomposition for Real-Time Background/Foreground Separation in Video

  2014influential reference
• CDnet 2014: An Expanded Change Detection Benchmark Dataset

  2014cited by this paper
• Robust PCA via Principal Component Pursuit: A review for a comparative evaluation in video surveillance

  2014cited by this paper
• Traditional and recent approaches in background modeling for foreground detection: An overview

  2014cited by this paper
• Static and Moving Object Detection Using Flux Tensor with Split Gaussian Models

  2014cited by this paper
• Limited Memory Block Krylov Subspace Optimization for Computing Dominant Singular Value Decompositions

  2013cited by this paper
• Data-Driven Modeling & Scientific Computation: Methods for Complex Systems & Big Data

  2013cited by this paper
• On dynamic mode decomposition: Theory and applications

  2013cited by this paper
• A Benchmark Dataset for Outdoor Foreground/Background Extraction

  2012cited by this paper
• Moving Object Detection by Robust PCA Solved via a Linearized Symmetric Alternating Direction Method

  2012cited by this paper
• Low-rank and sparse dynamic mode decomposition

  2012cited by this paper
• GoDec: Randomized Lowrank & Sparse Matrix Decomposition in Noisy Case

  2011cited by this paper
• Comparative study of background subtraction algorithms

  2010cited by this paper
• CULA: hybrid GPU accelerated linear algebra routines

  2010cited by this paper
• Stable Principal Component Pursuit

  2010cited by this paper
• Invited articles section foreword

  2010cited by this paper
• Templates for convex cone problems with applications to sparse signal recovery

  2010cited by this paper
• Fast alternating linearization methods for minimizing the sum of two convex functions

  2009cited by this paper
• Spectral analysis of nonlinear flows

  2009cited by this paper
• Robust principal component analysis?

  2009cited by this paper
• Subspace Learning for Background Modeling: A Survey

  2009influential reference
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

  2009influential reference
• Scalable parallel programming

  2008cited by this paper
• Dynamic mode decomposition of numerical and experimental data

  2008influential reference
• Calculating the singular values and pseudo-inverse of a matrix

  2007cited by this paper
• A fast randomized algorithm for the approximation of matrices ✩

  2007cited by this paper
• An introduction to ROC analysis

  2006cited by this paper
• A randomized algorithm for the approximation of matrices

  2006cited by this paper
• FAST MONTE CARLO ALGORITHMS FOR MATRICES II: COMPUTING A LOW-RANK APPROXIMATION TO A MATRIX∗

  2004cited by this paper
• Fast Monte-Carlo algorithms for finding low-rank approximations

  1998cited by this paper
• Applied Numerical Linear Algebra

  1997cited by this paper
• Fundamentals of matrix computations

  1991cited by this paper
• Submitted to Ieee Transactions on Pattern Analysis and Machine Intelligence. Special Section on Video Surveillance and Monitoring a Bayesian Computer Vision System for Modeling Human Interactions

  year unknowncited by this paper
• Article in Press Applied and Computational Harmonic Analysis a Randomized Algorithm for the Decomposition of Matrices

  year unknowncited by this paper
• Stat260/cs294: Randomized Algorithms for Matrices and Data

  year unknowncited by this paper

• A hybrid dynamic mode decomposition algorithm combining random and sparsity promoting and its application to viscoelastic flow around circular cylinder

  2025cites this paper
• Foreground-background separation and video reconstruction using moment matching

  2025cites this paper
• Reduced Order Data-driven Twin Models for Nonlinear PDEs by Randomized Koopman Orthogonal Decomposition and Explainable Deep Learning

  2025cites this paper
• Koopman-inspired data-driven quantification of fluid–structure energy transfers

  2024cites this paper
• Separating urban heat island circulation and convective cells through dynamic mode decomposition

  2024cites this paper
• Automatic detection and assessment of crack development in ultra-high performance concrete in the spatial and Fourier domains

  2024cites this paper
• A Pump Fault Warning Algorithm Based on Improved PCA-KNN

  2024cites this paper
• Full Decoupling High-Order Dynamic Mode Decomposition for Advanced Static and Dynamic Synergetic Fault Detection and Isolation

  2024cites this paper
• Optimizing Dynamic Mode Decomposition for Video Denoising via Plug-and-Play Alternating Direction Method of Multipliers

  2024cites this paper
• Koopman analysis by the dynamic mode decomposition in wind engineering

  2023cites this paper
• Tensor BM‐Decomposition for Compression and Analysis of Video Data

  2023cites this paper
• A surrogate non-intrusive reduced order model of quasi-geostrophic turbulence dynamics based on a combination of LSTM and different approaches of DMD

  2023cites this paper
• Density field reconstruction from time-series schlieren images via extended phase-consistent dynamic mode decomposition

  2023cites this paper
• Tensor BM-Decomposition for Compression and Analysis of Spatio-Temporal Third-order Data

  2023cites this paper
• A Data-Driven Hybrid Methodology Using Randomized Low-Rank DMD Approximation and Flat-Top FIR Filter for Voltage Fluctuations Monitoring in Grid-Connected Distributed Generation Systems

  2023cites this paper
• Extended-Phase-Consistent-Dynamic-Mode-Decomposition-based Density Reconstruction of Schlieren Images in Low-Density Wind Tunnel Tests

  2023cites this paper
• Efficient and Robust Background Modeling with Dynamic Mode Decomposition

  2022cites this paper
• Sketching Methods for Dynamic Mode Decomposition in Spherical Shallow Water Equations

  2022cites this paper
• Digital Twin Data Modelling by Randomized Orthogonal Decomposition and Deep Learning

  2022cites this paper
• Urban Design Storm Hyetograph Analysis Based on a New Method Considering Spatiotemporal Variations

  2022cites this paper
• Concept of Hybrid Models in Background Subtraction: A Review of Recent Trends

  2021cites this paper
• The linear-time-invariance notion to the Koopman Analysis: the architecture, pedagogical rendering, and fluid-structure association

  2021cites this paper
• Cross-View Gait Recognition with Deep Universal Linear Embeddings

  2021cites this paper
• On Some Modal Implications of the Dynamic Mode Decomposition Through the Lens of a Subcritical Prism Wake

  2021influential citation
• Noise Removal for Dynamic Mode Decomposition Based on Plug-and-Play ADMM

  2021cites this paper
• RETRACTED ARTICLE: Moving object detection based on unified model

  2020cites this paper
• 7 Data-driven methods for reduced-order modeling

  2020cites this paper
• Moving target extraction and background reconstruction algorithm

  2020cites this paper
• Recommendations for evaluating the performance of background subtraction algorithms for surveillance systems

  2020cites this paper
• A greedy non-intrusive reduced order model for shallow water equations

  2020cites this paper
• Reducing the amount of out‐of‐core data access for GPU‐accelerated randomized SVD

  2020cites this paper
• A literature survey of matrix methods for data science

  2019cites this paper
• Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction

  2019cites this paper
• Automatic Delineation of Kidney Region in DCE-MRI

  2019cites this paper
• Methods for data-driven multiscale model discovery for materials

  2019cites this paper
• Randomized methods to characterize large-scale vortical flow networks

  2019cites this paper
• Randomized linear algebra for model reduction—part II: minimal residual methods and dictionary-based approximation

  2019cites this paper
• A Fault Diagnosis Method for One-Dimensional Vibration Signal Based on Multiresolution tlsDMD and Approximate Entropy

  2019cites this paper
• Topological Labelling of Scene using Background/Foreground Separation and Epipolar Geometry

  2019cites this paper
• Processing epidemiological data using dynamic mode decomposition method

  2019cites this paper
• Randomized Dynamic Mode Decomposition | SIAM Journal on Applied Dynamical Systems | Vol. 18, No. 4 | Society for Industrial and Applied Mathematics

  2019cites this paper
• An Improved Two-steps Saliency Detection Algorithm based on Binarized Normed Gradients and Nuclear Norm Model in Video Sequences

  2018cites this paper
• Numerical Computation of Detonation Stability

  2018cites this paper
• Background Subtraction Techniques Evaluation based on Sigma = delta Algorithm for Motion Detection

  2018cites this paper
• An integrated data-driven computational pipeline with model order reduction for industrial and applied mathematics

  2018cites this paper
• Dynamic Mode Decomposition for Multi-dimensional Time Series Analysis

  2018cites this paper
• Efficiency of randomised dynamic mode decomposition for reduced order modelling

  2018cites this paper
• Structure preserving reduced order modeling for gradient systems

  2018cites this paper
• Unsupervised deep context prediction for background estimation and foreground segmentation

  2018cites this paper
• Improved Dynamic Mode Decomposition and Its Application to Fault Diagnosis of Rolling Bearing

  2018cites this paper
• Unsupervised Deep Context Prediction for Background Foreground Separation

  2018cites this paper
• Optimized Dynamic Mode Decomposition via Non-Convex Regularization and Multiscale Permutation Entropy

  2018cites this paper
• Dynamic mode decomposition for interconnected control systems

  2017cites this paper
• Online dynamic mode decomposition for time-varying systems

  2017cites this paper
• Randomized Dynamic Mode Decomposition

  2017cites this paper
• Dynamic Mode Decomposition for Background Modeling

  2017cites this paper
• Background–Foreground Modeling Based on Spatiotemporal Sparse Subspace Clustering

  2017cites this paper
• Reduced-order modeling of fluids systems, with applications in unsteady aerodynamics

  2017cites this paper
• MoSense: An RF-Based Motion Detection System via Off-the-Shelf WiFi Devices

  2017cites this paper
• Scalable Extended Dynamic Mode Decomposition Using Random Kernel Approximation

  2017cites this paper
• Modal Analysis of Fluid Flows: An Overview

  2017cites this paper
• Dynamic Mode Decomposition for Univariate Time Series: Analysing Trends and Forecasting

  2017cites this paper
• Dynamic mode decomposition for computer vision and signal processing

  2017cites this paper
• Variable Projection Methods for an Optimized Dynamic Mode Decomposition

  2017cites this paper
• Energy preserving model order reduction of the nonlinear Schrödinger equation

  2017cites this paper
• Randomized Matrix Decompositions using R

  2016cites this paper
• Streaming GPU Singular Value and Dynamic Mode Decompositions

  2016cites this paper
• Randomized dynamic mode decomposition for nonintrusive reduced order modelling

  2016influential citation
• Compressed dynamic mode decomposition for background modeling

  2015influential citation
• Compressed Dynamic Mode Decomposition for Real-Time Object Detection

  2015cites this paper
• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset

  2015influential citation
• S CALING D YNAMIC M ODE D ECOMPOSITION FOR R EAL T IME A NALYSIS OF I NFANT M OVEMENTS

  year unknowncites this paper