Dynamic Mode Decomposition for Robust PCA with Applications to Foreground/Background Subtraction in Video Streams

Authors: J. Grosek (University of Washington, USA), Xing Fu (University of Washington, USA), S. Brunton (University of Washington, USA), J. Nathan Kutz (Air Force Research Laboratories, USA)

[Project Page][Publications]

Chapter Description

One potential viewpoint of background/foreground separation is a matrix separation problem into low-rank (background) and sparse (foreground) components. Recently, this viewpoint has been advocated by Candes et al. in the framework of robust principal component analysis (RPCA). By weighting a combination of the nuclear and the l₁ norms, a convenient convex optimization problem (principal component pursuit) was demonstrated, under suitable assumptions, to recover the low-rank and sparse components exactly of a given data-matrix or video for background/foreground separation. It was also compared to the state-of-the-art computer vision procedure developed by De La Torre and Black. We advocate a similar matrix separation approach, but by using the method of dynamic mode decomposition (DMD). This method, which essentially implements a Fourier decomposition of correlated spatial activity of the video frames in time, distinguishes the stationary background from the dynamic foreground by differentiating between the nearzero Fourier modes and the remaining modes bounded away from the origin, respectively. In the application of video surveillance, the video frames can be thought of as snapshots of some underlying complex/nonlinear dynamics. The DMD decomposition yields oscillatory time components of the video frames that have contextual implications. Namely, those modes that are near the origin represent dynamics that are unchanging, or changing slowly, and can be interpreted as stationary background pixels, or low-rank components of the data matrix. By simply applying the dynamical systems DMD interpretation to video frames, an approximate RPCA technique can be enacted at a fixed cost of a singular-value decomposition and a linear equation solve. The additional innovation of multi-resolution DMD (MRDMD) allows for further separation of dynamic content in the video, thus allowing for the separation of components that are happening on different time scales.