AMATH482-Assignment 5 Background Subtraction in Video Streams Solved

Use the Dynamic Mode Decomposition method on the video clips ski drop.mov and monte carlo.mov containing a foreground and background object and separate the video stream to both the foreground video and a background.

The DMD spectrum of frequencies can be used to subtract background modes. Specifically, assume that ωp, where p ∈ {1,2,...,`}, satisfies kωpk ≈ 0, and that kωjk ∀ j 6= p is bounded away from zero. Thus,

                                                                 XDMD =             bpϕpeωpt                +           Xbjϕjeωjt                    (1)

  | {z }

Background Video

Foreground Video

Assuming that X ∈ Rn×m, then a proper DMD reconstruction should also produce XDMD ∈ Rn×m. However, each term of the DMD reconstruction is complex: bjϕj exp(ωjt) ∈ Cn×m ∀j, though they sum to a real-valued matrix. This poses a problem when separating the DMD terms into approximate low-rank and sparse reconstructions because real-valued outputs are desired and knowing how to handle the complex elements can make a significant difference in the accuracy of the results. Consider calculating the DMD’s approximate low-rank reconstruction according to

                                                                                        XLow-RankDMD = bpϕpeωpt.

Since it should be true that

                                                                                      X = XLow-RankDMD + XSparseDMD ,

then the DMD’s approximate sparse reconstruction,

XSparseDMD = Xbjϕjeωjt,

j6=p

can be calculated with real-valued elements only as follows...

 SparseLow-Rank

                                                                                                  XDMDXDMD                           ,

where | · | yields the modulus of each element within the matrix. However, this may result in XSparseDMD having negative values in some of its elements, which would not make sense in terms of having negative pixel intensities. These residual negative values can be put into a n×m matrix R and then be added back into XLow-RankDMD as follows:

                                                                                 XLow-RankDMD  XLow-RankDMD       

XSparseDMD ← XSparseDMD − R

This way the magnitudes of the complex values from the DMD reconstruction are accounted for, while maintaining the important constraints that

                                                                                      X = XLow-RankDMD + XSparseDMD ,

so that none of the pixel intensities are below zero, and ensuring that the approximate low-rank and sparse DMD reconstructions are real-valued. This method seems to work well empirically.