$\lvert\deg(h_{2k}∘h_{2k+1}∘g_{n_{k+1},∞})\rvert=\lvert\deg(g_{n_{k},∞})\rvert=\lvert\deg(h_{2k}∘f_{m_{k},∞})\rvert$
and $\lvert\deg(h_{2k+1}∘g_{n_{k+1},∞})\rvert=\lvert\deg(f_{m_{k},∞})\rvert$.
There is $0<δ_{k}≤π$ such that $f_{n_{j},n_{k}}$ is $\langle
δ_{j}/2^{k-j},δ_{k}\rangle$-continuous for every $j<k$ and $h_{2k}$ is
$\langle ε_{k}/2,δ_{k}\rangle$-continuous. This finishes a half-step of the
induction. The other half-step is analogous: there is an $\mathcal{S}$-map
$h_{2k+2}\colon Y_{n_{k+1}}\leftarrow X_{m_{k+1}}$ such that
$h_{2k+1}∘h_{2k+2}≈_{δ_{k}/2}f_{m_{k},m_{k+1}}$ and so
$\lvert\deg(h_{2k+2}∘f_{m_{k+1},∞})\rvert=\lvert\deg(g_{n_{k+1},∞})\rvert$,
and there is a suitable $ε_{k+1}>0$. In the end we use Corollary 3.21. ∎

The $S$-adic pseudo-solenoid for $S=[0]$ or $[P^{∞}]$ for $P⊆Π$ is a generic
object over $\mathcal{S}$ or $\mathcal{S}_{P}$, respectively. For $S=[0]$ this
is the pseudo-arc; for $S=[P^{∞}]$ the $P$-adic pseudo-solenoid is even a
Fraïssé limit. For the other types $[s]∈\overline{ℕ}/{\sim}$ (where $0<s(p)<∞$
for infinitely many $p∈Π$) there is no corresponding subcategory of
$\mathcal{S}$. However, a certain modification of the Banach–Mazur game still
allows us to view every $S$-adic pseudo-solenoid as a generic object.

######  Definition 5.25.

For a type $S∈\overline{ℕ}/{\sim}$ we define the abstract _Banach–Mazur game
in $\mathcal{S}$ below $S$_.
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},S\rangle)$ denotes the play
scheme $\operatorname{\mathsf{BM}}(\mathcal{S})$ with the following extra
rule. Every play $f_{*}$ of the game is supposed to be a sequence of type
$≤S$. If it is not the case, the player responsible the failure loses. More
precisely, for $S=[0]$ the extra rule is vacuous, while for a positive type
$S$ we take $s∈S$ and for every $p∈Π$ we look at the maximal $n∈ω$ (if it
exists) such that $\lvert\deg(f_{0,n})\rvert(p)≤s(p)$. We blame Eve or Odd,
respectively, for the failure at $p$ depending on whether $n$ is even or odd.
The play sequence $f_{*}$ fails to have type $≤S$ if and only if there have
been failures at infinitely many primes $p$. In that case, if Eve is
responsible for infinitely many of them, she loses. Otherwise, Odd loses. Note
that the responsibility for a failure at particular $p$ depends on $s∈S$, but
the total responsibility does not. This specifies the game scheme. A fully
specified game
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},S\rangle,\mathcal{G})$ also
adds the goal class $\mathcal{G}$ for Odd as in Definition 3.1, which
determines who wins in the case that the type of the play sequence stays below
$S$.

######  Observation 5.26.

The game $\operatorname{\mathsf{BM}}(\langle\mathcal{S},[0]\rangle)$ is just
$\operatorname{\mathsf{BM}}(\mathcal{S})$, while for $P⊆Π$ the games
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},[P^{∞}]\rangle)$ and
$\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$ are equivalent in the sense that
there is a translation preserving winning strategies for both players both
ways. The translation is as follows. We build a single $\mathcal{S}$-sequence
interpreted both as a play in
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},[P^{∞}]\rangle)$ and
$\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$. As long as the moves are in
$\mathcal{S}_{P}$ there is no difference, but when a player playing
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},[P^{∞}]\rangle)$ plays a map
not in $\mathcal{S}_{P}$, this cannot be interpreted as a move in
$\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$. In this case we “reset” the
corresponding play of $\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$ – we
pretend that the play of $\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$ is just
about to start, i.e. we interpret only the tail of the sequence $f_{*}$ as the
play (in the case that the next player is Odd, we pretend Eve started with
$\operatorname{id}_{\SS}$). If this reset occurs only finitely many times, we
have a tail of the sequence corresponding to a play in both games and the full
sequence corresponding to a play in
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},[P^{∞}]\rangle)$, all three
with the same outcome. If the reset occurs infinitely many times, there is no
corresponding play of $\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$ and the
type of $f_{*}$ is not below $[P^{∞}]$ so one of the players is to blame for
the failure. But neither a winning strategy in
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},[P^{∞}]\rangle)$ nor any
strategy in $\operatorname{\mathsf{BM}}(\mathcal{S}_{P})$ can be responsible
for such failure, and translated winning strategies remain winning in the
other game.

######  Proposition 5.27.

For every type $S∈\overline{ℕ}/{\sim}$, Odd has a winning strategy in
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},S\rangle)$ for the $S$-adic
pseudo-solenoid.

###### Proof.

By Corollary 5.24 it is enough for Odd to have a winning strategy in
$\operatorname{\mathsf{BM}}(\langle\mathcal{S},S\rangle,\mathcal{G})$ where
$\mathcal{G}$ is the set of all crooked $\mathcal{S}$-sequences of type $S$.
But it is easy for Odd to force the crookedness and the right type (unless Eve
is to blame for the failure of the type condition). The case $S=0$ corresponds
to $\operatorname{\mathsf{BM}}(\mathcal{S})$, so suppose $S≠0$. Let $s∈S$ and
let $\langle p_{k}\rangle_{k∈ω}$ be an enumeration of all primes such that
each appears infinitely many times. At every step $2k+1=n∈ω$ Odd plays an
$ε_{n}$-crooked $\mathcal{S}$-map of degree $1$ for suitable $ε_{n}>0$ as in
Proposition 3.4, composed with the map $z\mapsto z^{p_{k}}$ if
$\lvert\deg(f_{0,n})\rvert(p_{k})<s(p_{k})$. ∎

In the final paragraphs let us summarize known results regarding existence of
continuous surjections between circle-like continua and in particular pseudo-
solenoids, using types and Fraïssé theory.

######  Proposition 5.28.

Let $f\colon X\to Y$ be a continuous surjection between circle-like continua
and let $P,Q⊆Π$.

  1. (i)

If $T(f)≠0$, then $T(X)≥T(Y)$, and $T(f)$ is the multiplication by $t$ with
$[t]≤T(X)$.

  2. (ii)

There is a notion of a _self-entwined_ circle-like continuum, introduced by
Rogers [40]. If $Y$ is self-entwined, then $T(f)≠0$. If $T(Y)∉\\{0,1\\}$, then
$Y$ is self-entwined. The pseudo-circle $ℙ_{∅}$ is self-entwined.

  3. (iii)

There is a continuous surjection $f\colon ℙ_{P}\to ℙ_{Q}$ if and only if
$P⊇Q$. In this case, $T(f)≠0$.

  4. (iv)

There is a continuous surjection $f\colon ℙ_{P}\to ℙ$ (necessarily with
$T(f)=0$), but no continuous surjection $ℙ\to ℙ_{P}$ for every $P⊆Π$.

###### Proof.

Claim (i) holds since for $s∈T(Y)$ we have $T(f)(s)∈T(X)$ and $T(f)(s)≥s$.
Claim (ii) follows from the results by Rogers [40, Theorem 3, 4, 5], and from
the observation that Roger’s _limit degree zero_ corresponds to our $T(f)=0$.

If $f\colon ℙ_{P}\to ℙ_{Q}$ is a continuous surjection, then $T(f)≠0$ by (ii),
and $[P^{∞}]=T(ℙ_{P})≥T(ℙ_{Q})=[Q^{∞}]$ by (i). On the other hand, if $P⊇Q$,
then $ℙ_{Q}$ is a $σ\mathcal{S}_{P}$-object and $ℙ_{P}$ is cofinal in
$σ\mathcal{S}_{P}$. There is no continuous surjection $f\colon ℙ\to ℙ_{P}$
since by (ii) we would have $T(f)≠0$, which is impossible since $T(ℙ)=0$.

As in [41, Theorem 12] we may consider two copies of an $\mathcal{I}$-sequence
$\langle X_{*},f_{*}\rangle$ with limit $ℙ$ such that $f_{n}(i)=i$ for
$i∈\\{0,1\\}$ and every $n∈ω$, and glue them at the end-points $0$, $1$. We
obtain an $\mathcal{S}$-sequence $\langle Y_{*},g_{*}\rangle$ of maps of
degree $1$ with a limit $Y_{∞}$, and a sequence of continuous surjections
$φ_{n}\colon Y_{n}\to X_{n}$, $n∈ω$, commuting with $f_{*}$ and $g_{*}$ such
that every $φ_{n}$ is the quotient $\SS\to\mathbb{I}$ gluing two halves of the
circle together. In the and we obtain a continuous surjection $φ_{∞}\colon
Y_{∞}\to ℙ$, where $T(Y_{∞})=1$, so $Y_{∞}$ is a continuous image of every
$ℙ_{P}$. ∎

######  Corollary 5.29.

The universal pseudo-solenoid $ℙ_{Π}$ admits a continuous surjection onto
every circle-like or arc-like continuum. Every continuous surjection $ℙ_{Π}\to
ℙ_{Π}$ is a near-homeomorphism. Also, for every two continuous surjections
$f,g\colon ℙ_{Π}\to Y$ onto a circle-like continuum $Y$ with $T(Y)∉\\{0,1\\}$
and every $ε>0$ there is a homeomorphism $h\colon ℙ_{Π}\to ℙ_{Π}$ such that
$f≈_{ε}g∘h$.

###### Proof.

We combine the fact that $ℙ_{Π}$ is the Fraïssé limit of $\mathcal{S}_{Π}$ in
$σ\mathcal{S}_{Π}$ with the previous proposition. $ℙ_{Π}$ continuously maps
onto every circle-like continuum of positive type, but by (iv) also onto the
pseudo-arc, which maps onto every arc-like continuum. Every continuous
surjection $ℙ_{Π}\to ℙ_{Π}$ has non-zero type by (iii), and so is a near-
homeomorphism by Observation 4.5. Similarly, for the continuous surjection
$f,g\colon ℙ_{Π}\to Y$, if $T(Y)∉\\{0,1\\}$, we know by (ii) that $f$ and $g$
are $σ\mathcal{S}_{Π}$-maps, and we may use the homogeneity. ∎

Note that (using our language) the homogeneity in
$\langle\mathcal{S}_{Π},σ\mathcal{S}_{Π}\rangle$ and the cofinality in
$σ\mathcal{S}_{Π}$ of the universal pseudo-solenoid was already proved by
Irwin [19, Theorem 4.20 and 4.22].

## References

  * [1] J. Adámek and J. Rosický, Locally presentable and accessible categories, vol. 189 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1994.
  * [2] A. Bartoš, T. Bice, K. Dasilva Barbosa, and W. Kubiś, The weak Ramsey property and extreme amenability.  [arXiv:2110.01694v1], 2021.
  * [3] D. Bartošová and A. Kwiatkowska, Lelek fan from a projective Fraïssé limit, Fund. Math., 231 (2015), pp. 57–79.
  * [4] G. Basso and R. Camerlo, Fences, their endpoints, and projective Fraïssé theory, Trans. Amer. Math. Soc., 374 (2021), pp. 4501–4535.
  * [5] R. H. Bing, Concerning hereditarily indecomposable continua, Pacific J. Math., 1 (1951), pp. 43–51.
  * [6] R. H. Bing, Higher-dimensional hereditarily indecomposable continua, Trans. Amer. Math. Soc., 71 (1951), pp. 267–273.
  * [7] R. H. Bing, Embedding circle-like continua in the plane, Canadian J. Math., 14 (1962), pp. 113–128.
  * [8] M. Brown, On the inverse limit of Euclidean $N$-spheres, Trans. Amer. Math. Soc., 96 (1960), pp. 129–134.
  * [9] M. Brown, Some applications of an approximation theorem for inverse limits, Proc. Amer. Math. Soc., 11 (1960), pp. 478–483.
  * [10] W. J. Charatonik and R. P. Roe, Projective fraïssé limits of trees.  Preprint [https://web.mst.edu/~rroe/Fraisse.pdf], 2022.
  * [11] M. Droste and R. Göbel, Universal domains and the amalgamation property, Math. Structures Comput. Sci., 3 (1993), pp. 137–159.
  * [12] L. Fearnley, The pseudo-circle is unique, Trans. Amer. Math. Soc., 149 (1970), pp. 45–64.
  * [13] L. Fearnley, Classification of all hereditarily indecomposable circularly chainable continua, Trans. Amer. Math. Soc., 168 (1972), pp. 387–401.
  * [14] L. C. Hoehn and L. G. Oversteegen, A complete classification of homogeneous plane continua, Acta Math., 216 (2016), pp. 177–216.
  * [15] T. Homma, A theorem on continuous functions, Kōdai Math. Sem. Rep., 4 (1952), pp. 13–16.
  * [16] W. T. Ingram, Concerning non-planar circle-like continua, Canadian J. Math., 19 (1967), pp. 242–250.
  * [17] W. T. Ingram and W. S. Mahavier, Inverse limits, vol. 25 of Developments in Mathematics, Springer, New York, 2012.  From continua to chaos.
  * [18] T. Irwin and S. Solecki, Projective Fraïssé limits and the pseudo-arc, Trans. Amer. Math. Soc., 358 (2006), pp. 3077–3096.
  * [19] T. L. Irwin, Fraïssé limits and colimits with applications to continua, ProQuest LLC, Ann Arbor, MI, 2007.  Thesis (Ph.D.)–Indiana University.
  * [20] K. Kawamura, Near-homeomorphisms on hereditarily indecomposable circle-like continua, Tsukuba J. Math., 13 (1989), pp. 165–173.
  * [21] A. S. Kechris, Classical descriptive set theory, vol. 156 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995.
  * [22] A. S. Kechris, V. G. Pestov, and S. Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal., 15 (2005), pp. 106–189.
  * [23] J. Krasinkiewicz, Mappings onto circle-like continua, Fund. Math., 91 (1976), pp. 39–49.
  * [24] J. Krasinkiewicz and P. Minc, Nonexistence of universal continua for certain classes of curves, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 24 (1976), pp. 733–741.
  * [25] J. Krasinkiewicz and P. Minc, Mappings onto indecomposable continua, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 25 (1977), pp. 675–680.
  * [26] A. Krawczyk and W. Kubiś, Games with finitely generated structures, Ann. Pure Appl. Logic, 172 (2021), pp. Paper No. 103016, 13.
  * [27] W. Kubiś, Metric-enriched categories and approximate Fraïssé limits.  [arXiv:1210.6506v3], 2013.
  * [28] W. Kubiś, Fraïssé sequences: category-theoretic approach to universal homogeneous structures, Ann. Pure Appl. Logic, 165 (2014), pp. 1755–1811.
  * [29] W. Kubiś, Weak Fraïssé categories, Theory Appl. Categ., 38 (2022), pp. 27–63.  [http://www.tac.mta.ca/tac/volumes/38/2/38-02.pdf].
  * [30] W. Kubiś and A. Kwiatkowska, The Lelek fan and the Poulsen simplex as Fraïssé limits, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM, 111 (2017), pp. 967–981.
  * [31] A. Kwiatkowska, Large conjugacy classes, projective Fraïssé limits and the pseudo-arc, Israel J. Math., 201 (2014), pp. 75–97.
  * [32] W. Lewis and P. Minc, Drawing the pseudo-arc, Houston J. Math., 36 (2010), pp. 905–934.
  * [33] T. Maćkowiak, A universal hereditarily indecomposable continuum, Proc. Amer. Math. Soc., 94 (1985), pp. 167–172.
  * [34] S. Mardešić, Strong shape and homology, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2000.
  * [35] S. Mardešić and J. Segal, $\varepsilon$-mappings onto polyhedra, Trans. Amer. Math. Soc., 109 (1963), pp. 146–164.
  * [36] M. C. McCord, Inverse limit sequences with covering maps, Trans. Amer. Math. Soc., 114 (1965), pp. 197–209.
  * [37] J. Mioduszewski, A functional conception of snake-like continua, Fund. Math., 51 (1962/63), pp. 179–189.
  * [38] S. B. Nadler, Jr., Continuum theory, vol. 158 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc., New York, 1992\.  An introduction.
  * [39] A. Panagiotopoulos and S. Solecki, A combinatorial model for the Menger curve, J. Topol. Anal., 14 (2022), pp. 203–229.
  * [40] J. T. Rogers, Jr., Mapping the pseudo-arc circle-like, self-entwined continua, Michigan Math. J., 17 (1970), pp. 91–96.
  * [41] J. T. Rogers, Jr., Pseudo-circles and universal circularly chainable continua, Illinois J. Math., 14 (1970), pp. 222–237.
  * [42] R. L. Russo, Universal continua, Fund. Math., 105 (1979/80), pp. 41–60.
  * [43] R. Sikorski and K. Zarankiewicz, On uniformization of functions. I, Fund. Math., 41 (1955), pp. 339–344.


∎

11institutetext: M. Mignacca 22institutetext: Department of Mathematics and
Statistics
McGill University
Montréal, QC
Canada 33institutetext: S. Brugiapaglia 44institutetext: Department of
Mathematics and Statistics
Concordia University
Montréal, QC
Canada 55institutetext: J.J. Bramburger 66institutetext: Department of
Mathematics and Statistics
Concordia University
Montréal, QC
Canada

# Real-Time Motion Detection Using Dynamic Mode Decomposition††thanks: This
research was supported by an NSERC USRA (MM) and NSERC Discovery Grants (SB
and JJB).

Marco Mignacca  Simone Brugiapaglia  Jason J. Bramburger

(Received: date / Accepted: date)

###### Abstract

Dynamic Mode Decomposition (DMD) is a numerical method that seeks to fit
timeseries data to a linear dynamical system. In doing so, DMD decomposes
dynamic data into spatially coherent modes that evolve in time according to
exponential growth/decay or with a fixed frequency of oscillation. A prolific
application of DMD has been to video, where one interprets the high-
dimensional pixel space evolving through time as the video plays. In this
work, we propose a simple and interpretable motion detection algorithm for
streaming video data rooted in DMD. Our method leverages the fact that there
exists a correspondence between the evolution of important video features,
such as foreground motion, and the eigenvalues of the matrix which results
from applying DMD to segments of video. We apply the method to a database of
test videos which emulate security footage under varying realistic conditions.
Effectiveness is analyzed using receiver operating characteristic curves,
while we use cross-validation to optimize the threshold parameter that
identifies movement.

###### Keywords:

dynamic mode decomposition motion detection background subtraction computer
vision

##  1 Introduction

Dynamic Mode Decomposition (DMD) is a method for forecasting and extracting
complicated spatio-temporal behaviour from high-dimensional datasets. First
developed by Schmid schmid2010dynamic , DMD seeks to identify a matrix $A$ so
that advancing the data forward by one timestep is equivalent to
multiplication by this matrix tu2014dmd ; DMDbook . In this way, DMD poses
complex movement over space and through time as a linear discrete dynamical
system via the matrix $A$. Since linear systems are entirely understood by
their spectrum, the eigenvectors of $A$, called the DMD modes, can be seen to
represent macroscopic patterns in the dataset that persist through time,
either oscillating, growing, or decaying at a fixed rate determined by the
associated eigenvalue. DMD has connections to the Koopman operator
rowley2009spectral ; brunton2022modern  and has proven to be a useful tool in
identifying coherent structures in fluid mechanics schmid2011applications ;
menon2020dynamic ; colbrook2023residual  and neuroscience
brunton2016extracting ; partamian2023analysis ; shiraishi2020neural , as well
as to develop financial trading strategies mann2016dynamic , among numerous
other applications; see DMDbook ; schmid2022dynamic  and the references
therein. Improvements on the method include building in known physics
baddoo2023physics ; morandin2023port , accounting for irregular timesteps and
noisy measurements lee2023optimized ; askham2018variable ; hemati2017biasing ,
and to incorporate the effect of control proctor2016dynamic ;
garcia2022extended .

The utility of DMD has also made its way into computer vision. This includes
employing DMD for edge detection in images bi2017dynamic , salient region
detection sikha2021dynamic ; sikha2018salient ; sikha2020multi , and
performing image classification rahul2019dynamic . Most important to the work
herein, DMD has been applied to separate out the background and foreground in
videos, allowing for object tracking krake2022efficient ; grosek2014dynamic ;
kutz2015multi ; erichson2019compressed ; haq2020dynamic ; han2022quaternion .
Roughly, this comes from the fact that eigenvectors of the DMD matrix $A$ with
eigenvalues having modulus near 1 represent patterns in the (vectorized) video
data that exhibit little change from frame to frame. Thus, these eigenvectors
can be seen as representing the background of the video data, while the
remaining eigenvectors fill in the foreground motion. Importantly, projecting
the video onto the background/foreground DMD modes constitutes a separation of
these distinct components of the video. The result is then two videos: one of
a nearly static background and another of just the isolated motion, as
exemplified in Figure 1.

(a) Original frame

(b) Background

(c) Foreground

Figure 1: Screenshots of DMD being be used to separate out the background and
foreground in video data. The video is taken from the Background Models
Challenge database BMC . Figure 2: A visual overview of real-time motion
detection and tacking with DMD. Sequential collections of video frames, or
windows, are fed in and compressed to reduce computational complexity. Then,
DMD is applied to identify spatio-temporal features within the windows. Spikes
in the spectrum of the DMD matrices over the windows indicate movement in the
video, thus detecting events as they occur in real-time.

Our contribution in this paper is to present a method of real-time motion
detection in streaming video data using DMD. To do this we apply DMD not to
the entire video all at once, but to short windows as they are fed in.
Precisely, we employ sliding window DMD dylewsky2019dynamic ;
bramburger2020sparse  to streaming video data to examine the dominant
timescales in each segment of the video. These timescales are revealed by
examining the modulus of the logarithm of the eigenvalues for the DMD matrix
within each window. Sudden spikes in the DMD spectrum denote fast timescale
movement in the foreground, allowing for motion detection. A visual overview
of our method can be found in Figure 2, while a proper explanation of the
method can be found in Section 3 below. Once movement has been detected, one
can then use the DMD matrix to isolate the foreground motion by subtracting
out the background. Computation time is accelerated by compressing the frames
of the video erichson2019compressed , resulting in a computationally cheap and
efficient method of real-time motion detection for streaming video data.

Motion detection is a classic problem in computer vision with many
complementary and competing methods. The simplest method identifies temporal
differences cheung2005robust ; yu2009real , amounting to searching for
significant change in the pixels from one frame to the next. This method is
sensitive to abrupt changes in illumination, shadows, and repetitive motions,
while also having the drawback that it cannot accurately extract the moving
object boundaries. Alternatively, the work tsai2008motion  transforms the
frames into Fourier space where object movement can be shown to create a non-
vertical structure in the 2D Fourier transform. While again being an effective
method, it suffers from a high cost of computation. Computation cost can be
brought down using the cosine transform oh2012real , for which graph cuts can
be employed to isolate the movement in the video. Graph cuts come with their
own well-documented limitations (see boykov2006graph  and the references
therein), including significant memory usage. Another drawback of coupling
motion detection algorithms with graph cuts is the simple fact that
identifying and isolating movement becomes a two-step task. A major advantage
of our method herein is that DMD provides the necessary tools to both identify
movement (through eigenvalues) and isolate it (through eigenvectors).

The review singh2020object  compares eight methods for real-time video
surveillance of varying complexity. It is found that while simpler methods,
such as examining temporal differences, are fast, they often fail to handle
many of the complexities encountered in real-world video data. As expected,
better performing methods come with higher computation time and a more
complicated implementation. Our DMD-based method herein offers simplicity in
its implementation, while also being backed up by dynamical systems theory to
justify its performance. Fundamentally, DMD is a method of multiresolution
analysis that accounts for spatial and temporal coherencies simultaneously. It
identifies macroscopic patterns in the data and is more robust to scale
overlap than related methods dylewsky2019dynamic , making it optimally suited
for the task of motion detection.

The paper is organized as follows. In Section 2 we provide an overview of DMD
(§ 2.1, 2.2, 2.3) and its capabilities for background subtraction (§ 2.4),
followed by a presentation of our own technique for motion detection in video
(§ 3). In Section 4, we apply this method to a dataset of videos (§ 4.1) and
discuss its performance (§ 4.2). The performance is then is evaluated through
the lens of receiver operating characteristic curves (§ 4.3), and a strategy
to optimize a key parameter involving $k$-fold cross-validation is presented
(§ 4.4), along with concluding remarks in Section 5.

##  2 Background on Dynamic Mode Decomposition

In this section we provide an overview of all the relevant aspects of DMD for
our method. We begin in § 2.1 with a presentation of DMD in its simplest form.
We then turn to a review of DMD with compression in § 2.2, sliding window DMD
in § 2.3 and background subtraction in § 2.4.

###  2.1 Dynamic Mode Decomposition

We begin with a review of DMD in its most basic form, while directing the
reader to DMDbook  and the references therein for a more complete discussion.
Assume that we have data snapshots
$\\{X_{n}\\}_{n=1}^{N+1}\subset\mathbb{C}^{M}$ for $N\geq 1$. In the coming
applications these snapshots will be vectorized greyscale video frames, and so
we make the assumption that they are arranged sequentially. Precisely, each
snapshot $X_{n}$ is generated by the same process and sampled at times $t_{n}$
that are evenly spaced, i.e. $h:=t_{n+1}-t_{n}>0$ for all $n=1,\dots,N$. DMD
then seeks to identify a matrix $A\in\mathbb{C}^{M\times M}$ so that

$X_{n+1}=AX_{n},\qquad n=1,\dots,N.$ (1)

That is, advancing from one snapshot to the next is equivalent to multiplying
the current snapshot by the DMD matrix $A$.

Identifying an appropriate DMD matrix is achieved by least squares regression.
First, arrange the snapshots into $M\times N$ dimensional data matrices

$\begin{split}X&=\begin{bmatrix}X_{1}&X_{2}&\cdots&X_{N}\end{bmatrix},\\\
Y&=\begin{bmatrix}X_{2}&X_{3}&\cdots&X_{N+1}\end{bmatrix}.\end{split}$ (2)

Notice that by definition each column of $Y$ is exactly one snapshot in the
future from the snapshot in the corresponding column of $X$. Then, the DMD
matrix $A$ is identified as the minimizer of

$\min_{A\in\mathbb{C}^{M\times M}}\|Y-AX\|^{2}_{F},$ (3)

where $\|\cdot\|_{F}$ denotes the Frobenius norm of a matrix. The minimizing
DMD matrix is known to be $A=YX^{\dagger}$, where $X^{\dagger}$ is the
Moore–Penrose pseudo-inverse of the data matrix $X$. Thus, upon arranging the
snapshots into the matrices $X$ and $Y$, we can immediately obtain the DMD
matrix through a quick and simple process of pseudo-inversion followed by
matrix multiplication.

An advantage of using DMD is that the resulting linear dynamical system (1)
can be completely understood in terms of the spectrum of the matrix $A$.
Indeed, the correspondence (1) between snapshots guarantees the eigenvector
expansion

$X_{n}\approx\sum_{m=1}^{M}c_{m}\lambda_{m}^{n}\psi_{m},$ (4)

where $(\lambda_{m},\psi_{m})\in\mathbb{C}\times\mathbb{C}^{M}$ are the $M$
eigenpairs of $A$, and the coefficients $c_{m}$ are given by $\Psi^{-1}X_{1}$,
where $\Psi=[\psi_{1}\ \psi_{2}\ \dots\ \psi_{M}]$. Expansion (4) provides a
space-time separation of variables for the data with eigenvectors describing
macroscopic patterns, or coherent structures, that can only grow, decay, or
oscillate in time according to their eigenvalue. Importantly, notice that
eigenvectors with eigenvalues $|\lambda_{m}|\approx 1$ are modes that change
little in time, giving way to the interpretation that they are the
‘background’ in the data. To better separate our background and foreground
modes we sort according to the ‘continuous-time’ eigenvalues, given by

$\omega_{m}=\log(\lambda_{m})/h,$ (5)

where we recall that $h>0$ is the temporal spacing between consecutive
snapshots. Thus, background modes have $|\omega_{m}|\approx 0$. Furthermore,
the sum (4) is equivalently written as

$X_{n}=\sum_{m=1}^{M}c_{m}\mathrm{e}^{\omega_{m}t}\psi_{m},$ (6)

where $t=nh$.

###  2.2 Compressed Dynamic Mode Decomposition

In the case where snapshots are high-dimensional ($M\gg 1$), as in the case of
high-resolution videos, applying DMD is computationally expensive due to the
pseudo-inversion required to identify $A$. This computational bottleneck can
be overcome using compressed DMD (cDMD) erichson2019compressed  which we
incorporate into our method below. Begin by fixing an integer $p\ll M$ and
generate a random measurement matrix $C\in\mathbb{C}^{p\times M}$. As
explained in erichson2019compressed , this matrix can be constructed
componentwise via sampling a uniform or Gaussian distribution, among other
choices (we employ the former, which is expressed as $C=\text{rand}(p,M)$ in
MATLAB). With this matrix we compress our data matrices (2) into $p\times N$
matrices

$X^{\prime}=CX,\qquad Y^{\prime}=CY.$ (7)

To further eliminate redundancies in our data, we can rank-reduce the data
using the singular value decomposition tu2014dmd . This is achieved through
the reduced SVD $X^{\prime}=U_{r}\Sigma_{r}V^{*}_{r}$, where
$U\in\mathbb{C}^{p\times r}$, $\Sigma\in\mathbb{C}^{r\times
r},V\in\mathbb{C}^{N\times r}$ with $r\ll N$ and $r\leq p$, and the subscript
$r$ denotes only the first $r$ columns and/or rows of each matrix in the SVD
of $X^{\prime}$. This leads to an $r\times r$ DMD matrix given by

$\tilde{A}=U^{*}_{r}Y^{\prime}V_{r}\Sigma_{r}^{\dagger}.$ (8)

Notice that computation time is significantly reduced since $r\ll M$.

Information from the compressed and rank-reduced matrix $\tilde{A}$ can be
leveraged to obtain information about the original data in $X$ and $Y$. This
comes from first letting $Q\in\mathbb{C}^{r\times r}$ be a matrix of
eigenvectors of $\tilde{A}$ with the diagonal matrix of eigenvalues $\Lambda$
satisfying $\tilde{A}Q=Q\Lambda$. Full $M$-dimensional DMD eigenvectors are
recovered through the $M\times r$ dimensional matrix

$\Phi=YV\Sigma^{-1}Q,$ (9)

where we notably use the original data matrix $Y$. The columns of $\Phi$
contain the DMD modes to construct the space-time expansion (4), with
corresponding eigenvalues on the diagonal of $\Lambda$.

Overall, cDMD proves to be much more computationally efficient due a smaller
SVD to calculate. The only additional computational costs comes from
generating the measurement matrix $C$ and computing the respective matrix
products $X^{\prime}$ and $Y^{\prime}$ as in (7). With our method of motion
detection for video surveillance, generating $C$ comes as a one-time upfront
cost that reduces numerous computations over time. This is because we will
apply DMD to incoming windows of video data, each of which is compressed
according to the same compression matrix, thus reducing computation within
each window.

###  2.3 Sliding Window DMD

This idea of applying DMD in real-time to segments of video data is inspired
by the sliding window DMD algorithm dylewsky2019dynamic , which was originally
devised to better resolve multiscale dynamics. In this framework, snapshots
are separated into overlapping, consecutive chunks and DMD is applied on each.
To be specific, the $N+1$ snapshots of the video are divided into windows of
size $T>0$ so that each window is identified with a value
$k\in\\{1,\dots,N-T\\}$. The $k$th data matrices have the form

$\begin{split}X^{(k)}&=\begin{bmatrix}X_{k}&X_{k+1}&\cdots&X_{k+T}\end{bmatrix},\\\
Y^{(k)}&=\begin{bmatrix}X_{k+1}&X_{k+2}&\cdots&X_{k+T+1}\end{bmatrix}.\end{split}$
(10)

With an eigenvector expansion as in equation (6) in hand for each window,
which we denote by $\bar{X}_{k}$ and which corresponds to the $k$th DMD matrix
$A^{(k)}=Y^{(k)}(X^{(k)})^{\dagger}$, the entire video can be reconstructed
via a linear combination of each windowed expansion weighted with Gaussians as
follows:

$X_{\text{full}}=\frac{\sum_{k=1}^{N-T}e^{-(t-\eta_{k})/\sigma^{2}}\bar{X}_{k}}{\sum_{k=1}^{N-T}e^{-(t-\eta_{k})/\sigma^{2}}},$
(11)

where $\eta_{k}$ is the midpoint of the $k$th window, $t$ is a vector
consisting of the temporal grid, and the standard deviation $\sigma$ of the
Gaussian is prescribed. Since each iteration of this method only requires
information from one of the chunks of video, this can easily be generalized to
real time streaming data. A pseudocode of the DMD procedure, combining cDMD
and sliding window DMD, is presented in Algorithm 1.

###  2.4 Background Subtraction with DMD

An impressively successful application of DMD is for performing background
separation from video han2022quaternion ; kutz2015multi ; grosek2014dynamic ;
krake2022efficient . The method takes advantage of the linearity of DMD by
separating out the fast- and slow-moving modes in (4). Recalling that the
eigenvectors of the DMD matrix correspond to coherent structures in the data,
eigenvalues with modulus near 1 are associated with components that exhibit
little change over time. In the context of a video filmed with a fixed camera
position, the portion of the video with unchanging dynamics constitutes the
background, while the remaining eigenvectors are associated with the
foreground. To this end, we are able to approximate the background by
considering (4) summed over only eigenvectors with eigenvalues near 1,
sometimes referred to as the low-rank component of the data. Summing over the
foreground constitutes the sparse component.

Figure 3: Plot of the continuous-time eigenvalues (5) in the complex plane
(corresponding to the 100th window) for the video in Figure 1 with $r=20$. The
single eigenvalue in red close to the origin constitutes the background mode,
while the remaining 19 eigenvalues in blue make up the foreground motion.

To properly separate out low-rank and sparse components from video data $W$ we
perform the following. First, define a threshold $\varepsilon>0$ that
separates out fast and slow frequencies (5). We set

$\tilde{L}=\sum_{k:\hskip
2.84544pt|\omega_{k}|\leq\varepsilon}c_{k}\psi_{k}e^{\omega_{k}t},$ (12)

and note that with real video data it is often the case that the sum defining
$\tilde{L}$ is over only a single eigenvector. This comes from a clear
distinction between frequencies with $\omega_{k}\approx 0$ and those whose
frequencies are bounded away from zero, providing a robustness with respect to
the choice of $\varepsilon$. The reader is referred to Figure 3 for a
demonstration of this. Following grosek2014dynamic , to maintain that the
sparse component is real-valued, we set

$\tilde{S}=X_{n}-|\tilde{L}|,$ (13)

where $X_{n}$ is the $n$th video frame and $|\tilde{L}|$ is the element-wise
modulus of $L$. However, this process may result in negative pixel values in
$\tilde{S}$ and so we define the residual $R$ to be a matrix of all such
negative values in $\tilde{S}$. This leads to the true background $L$ and
foreground $S$ components of the video

$L=R+|\tilde{L}|,\qquad S=\tilde{S}-R.$ (14)

We empirically observed that defining $L=|\tilde{L}|$ resulted in improved
background separation compared to defining $L$ as in (14), and so we used this
formulation. This method works well, as evidenced by Figure 1. In practice,
this procedure is applied in tandem with sliding window DMD on the
reconstruction as in (11). In this instance however, we only sum over the slow
and fast frequencies in the eigenvalue/eigenvector expansions (6) to
reconstruct the background and foreground respectively.

##  3 Motion Detection with DMD

Having now reviewed the necessary DMD-related methods, we present our method
of motion detection. This application of DMD is the main contribution of this
paper and validation of the method is left to the next section. Recall that a
visual overview of the method was presented in Figure 2 previously.

Algorithm 1 Windowed cDMD

Input: $W\in\mathbb{R}^{M\times N+1}$, $r$, $p$, $T$
Output: $\Omega$

$\text{num\\_windows}\leftarrow N+1-T$

$C\leftarrow\text{rand}(p,M)$

$W^{\prime}\leftarrow CW$

$\Omega\leftarrow\text{zeros}(r,\text{num\\_windows})$

for $j=1,\ldots,\text{num\\_windows}$ do

$Y_{1}\leftarrow W^{\prime}(:,j:j+T-1)$

$Y_{2}\leftarrow W^{\prime}(:,j+1:j+T)$

$[U,\;\Sigma,\;V]\leftarrow\text{svd}(Y_{1})$

$[U_{r},\;\Sigma_{r},\;V_{r}]\leftarrow[U(:,1:r),\;\Sigma(1:r,1:r),\;V(:,1:r)]$

$\tilde{A}\leftarrow U_{r}^{T}Y_{2}V_{r}\Sigma^{-1}$

$\lambda\leftarrow\text{eigenvalues}(\tilde{A})$

$\omega\leftarrow|\log{\lambda}|$

$\Omega(:,j)\leftarrow\omega$

end for

The method is initiated by applying cDMD to windowed subsets of the streaming
video data, which has been transformed into greyscale and vectorized into a
matrix $W\in\mathbb{R}^{M\times N+1}$. The compression matrix $C$ and target
rank $r$ are held constant over all windows, and each window is comprised of
$T>0$ consecutive frames of video. Algorithm 1 provides our windowed cDMD
method where we see that the output is the modulus of the continuous-time
eigenvalues (5) within each window. The scope of this work is primarily
limited to video data where the camera position remains fixed, meaning the
background is assumed to be relatively unchanged over the frames. This means
that if there is little or no motion in the video, the eigenvalues within the
window will all correspond approximately to the background, i.e.,
$\omega_{i}\approx 0$. However, if motion is present in a window one expects
to see this represented as at least one of the eigenvalues deviating from the
background cluster. As one sweeps across windows, motion entering the frames
is expected to be represented by a large spike in the DMD matrix spectrum, as
shown in Figure 6 below.

Motion detection from the DMD spectrum is automated by considering the sets of
eigenvalues $\\{\omega_{i}^{(k)}\\}_{i=1}^{r}$ and
$\\{\omega_{i}^{(k+1)}\\}_{i=1}^{r}$ from the consecutive $k$th and $(k+1)$st
windows. We compute the averages

$a_{k}=\frac{1}{r}\sum_{i=1}^{r}|\omega_{i}^{(k)}|,\qquad
a_{k+1}=\frac{1}{r}\sum_{i=1}^{r}|\omega_{i}^{(k+1)}|.$ (15)

Then, defining a threshold $\Delta^{*}>0$, motion is flagged in the $(k+1)$st
window if

$\bigg{|}\frac{a_{k+1}-a_{k}}{a_{k}}\bigg{|}\geq\Delta^{*}.$ (16)

By tracking the relative change in the mean of the eigenvalues over windows we
allow for the method to exclude background motion that persists over frames,
such as leaves being rustled by the wind. Note that we need only save
information from the $k$th and $(k+1)$st consecutive windows at a time, while
if no motion is detected we discard information from the $k$th window and
compare the spectrum of the $(k+1)$st and $(k+2)$nd windows. Combined with the
data reductions from cDMD, this mean that only two $r\times r$ matrices are
stored in memory to perform the method.

In practice, it was observed that foreground motion in video was sometimes
accompanied by multiple consecutive activations; that is, the moduli of the
eigenvalues would continue to increase in a few of the windows immediately
following that of the initial detection. One way this can be resolved is by
storing the (binary) results of the motion detection test for the previous few
windows, and additionally checking that no motion was already flagged in these
previous windows.

Finally, if motion is detected in a window, we apply the method of background
separation from § 2.4. This allows for the isolation of the detected motion,
again using only information from the stored $r\times r$ DMD matrix
corresponding to the window where motion is first detected. This is summarized
in the flowchart in Figure 4.

Calculate mean of eigenvalues in current windowCalculate mean of eigenvalues
in next windowCalculate the relative change in meanDoes the change exceed the
prescribed threshold?Motion detected!Proceed to the next windowYesNo Figure 4:
Flowchart demonstrating the motion detection scheme.

This method involves initializing a number of parameters that may affect its
performance. Precisely, the target rank $r$ dictates the number of eigenvalues
in each window, while the target dimension $p$ from cDMD, the window length
$T$, and most importantly, the detection threshold $\Delta^{*}$ all have
bearing on the performance. The choice of parameters that leads to optimal
performance of the method is problem-dependent and should be optimized with
simple tests. This might include designing motion to be captured by the
method, such as having someone walk into frame, while also decreasing the
sensitivity to exclude frivolous motion that might be unique to the
application. In the following section we demonstrate the method’s performance
on real video data, while also evaluating performance with receiver operating
characteristic curves and tuning the threshold detection parameter with
$k$-fold cross-validation.

##  4 Experimental Validation

In this section we demonstrate the performance of our method on real video
data. A full code repository to reproduce the results of this section is
available. This includes all files used for our tests, as well as full MATLAB
scripts to perform the method on video data and all of the coming validations:
https://github.com/marco-mig/dmd-motion-detection.

In what follows, we fix the parameters $T$, $p$, and $r$, while focusing on
the importance of the threshold parameter $\Delta^{*}$. Precisely, we take
$p=20$ and $r=5$, meaning each DMD matrix is only $5\times 5$ dimensional.
Thus, eigenvalues within each window are can be computed quickly without
presenting a bottleneck to the real-time nature of the algorithm. Window sizes
are fixed to be $T=80$, corresponding to 8/3 seconds. The random matrix $C$ is
constructed only once and applied to all videos for consistency.

###  4.1 Dataset

Figure 5: Sample frames of videos in database. Top: Background (left) and
motion (right) in a well-lit video. Bottom: Background (left) and motion
(right) with indoor lighting producing shadows.

Initial tests of the method featured free videos from the Background Models
Challenge database BMC , including the one featured in Figure 1. However, to
ensure a diversity of situations across the test set, we have opted to film
our own videos using the built-in camera on the iPhone 13. Our videos were
filmed to simulate security footage in that the camera is held still and
various individuals enter and exit the frame to be detected. These videos
include numerous variations such as the speed of entry and/or exit of the
individual, the distance of the motion from the camera, the time the
individual spends in the frame, and the actions performed by the individuals
in the frame. Our test set includes a total of 20 videos, of which 15 were
filmed in daylight and 5 with indoor lighting. Videos are of size 426 by 240
pixels and range in length from 27 seconds (810 frames) to 109 seconds (3270
frames). Each video begins and ends with a few seconds of a still background
shot to provide a baseline for the method to gauge performance. Frames from
videos in two lighting conditions are provided in Figure 5.

Figure 6: Sudden spikes in the average of the DMD spectrum represent motion
detection. Each spike is accompanied by one or more individuals entering or
exiting the frame, as demonstrated by the screenshots.

###  4.2 Performance Demonstration

Our experiments demonstrate that sudden motion from an individual entering or
exiting the video frame is accompanied by a spike in the average eigenvalues,
as measured by (16). A characteristic demonstration is provided in Figure 6
where one can clearly see the motion detection via large deviations in the DMD
spectrum. We have observed that whenever an individual enters the frame, it is
reflected in the eigenvalues at the window number corresponding closely to the
frame number minus the window length, as this is when the frame at which the
individual enters first appears in the window as the rightmost column of the
data matrix. However, when individuals exit the frame, the window number where
the change in eigenvalues is observed corresponds to the frame number itself.
This is because it is the last window in which information about the movement
is present in the data matrix, and so the change occurs after this information
(in the leftmost column of the data matrix) vanishes in the subsequent window.
To summarize, there is a temporal delay of length $T$, the window size, in
detecting when an object has left the frame. Thus, a distinction is made
between objects entering and exiting the frame, and the frame numbers which
are supplied to the algorithm which calculates the error score in the
following subsection have been adjusted accordingly.

###  4.3 Performance Evaluation

The task of identifying motion in windowed subsets of the video can be
interpreted as a binary classification problem, since there are two distinct
classification outcomes: either the window contains motion, or it does not. In
what follows, we refer to the event of motion being present in a window as a
positive event, and the lack thereof as a negative event. To this end, there
are two possible errors that can be observed: either the algorithm classifies
a negative event as positive, a false positive (FP), or it classifies a
positive event as negative, a false negative (FN). We also denote a
successfully classified positive as a true positive (TP) and a successfully
classified negative as a true negative (TN).

To display the relationship between the true positive rate (TPR) and false
positive rate (FPR) we will use a receiver operating characteristic (ROC)
curve (see, e.g., stat ). The TPR can be thought of the rate at which the
algorithm successfully classifies positive events as positive, while the FPR
is the rate at which the algorithm classifies negative events as positive. A
perfect classifier necessarily has a TPR of 1 and an FPR of 0, and the ROC
curve for such a classifier is the graph of the indicator function of the
interval $(0,1]$. Our ROC curve is traced out by recording the TPR and FPR of
the algorithm over threshold values $\Delta^{*}$ ranging from $10^{-10}$ to
$10^{10}$. In this section, we do not implement the fix for consecutive
activations as described in § 3 as this interferes with the expected behaviour
of the algorithm at threshold values close to zero. That is, for these values,
activations at nearly every (if not every) window containing motion is
expected. Finally, a half-second tolerance (forward and backward) in detecting
each event is imposed.

We calculated ROC curves for all 20 of the videos in our database using our
motion detection method. The mean of all the ROC curves is presented in Figure
7. The performance of the classifier is quantified by the area under the ROC
curve, which for the averaged ROC curve in Figure 7 is $0.9876$. Since this
value is quite close to the optimal performance at 1 and far from the random
chance performance at 0.5, we find strong evidence for the quality of our
method for detecting motion within windowed subsets of video data.

Figure 7: Average of the ROC curves generated from the 20 videos in the
database.

###  4.4 Optimizing the Threshold

While our method contains a number of parameters to be set by the user, none
is as important as the threshold $\Delta^{*}$. In this subsection we present a
method of determining an optimal threshold to get the best performance from
the method using a database of test videos that should be curated by the user
before applying the method for video surveillance. We begin by defining an
appropriate error measure which can then be minimized by the optimal
threshold.

####  4.4.1 Measuring Error

Recall from (§ 4.3) that there are a total of four possible outcomes of the
algorithm: either it classifies correctly (encompassing TPs and TNs) or
incorrectly (FPs and FNs). In many applications, these two latter outcomes are
not equally as costly. This is because in the context of video surveillance, a
FN, such as not detecting an intruder, can be much more costly than a FP, such
as falsely indicating the presence of an intruder. Thus, our goal here is to
present a possible error metric that takes this into consideration.

We begin by fixing a parameter $d^{*}>0$. To obtain the error, we run the
method over all videos in the database and check if the detection system has
flagged motion in a window within plus or minus $d^{*}$ windows of where
motion is known to have taken place. Thus, $d^{*}$ functions as the tolerance
in lag for which the user allows the algorithm to detect motion. The result is
a tally of the total number of errors (FP + FN), for which we define the error
score as

$E=\mathrm{FP}+c\cdot\mathrm{FN}.$ (17)

Here $c>0$ is a weight parameter. Per the discussion in the previous
paragraph, one typically would like $c>1$, and often $c\gg 1$, to reflect the
fact that a FN is more costly than a FP in a real-world situation. Hence, for
a given threshold $\Delta^{*}$ the error $E$ is directly dependent upon both
$d^{*}$ and $c$.

####  4.4.2 A Variant of k-Fold Cross-Validation

We will use a variant of $k$-fold cross-validation (see, e.g., stat ) to
determine an optimal threshold value using our error metric (17) and database
of videos. In what follows we fix $d^{*}=30$, which corresponds to a tolerance
of detection within 1 second of an event taking place. The penalty ratio in
the error metric is taken to be $c=100$.

Recall that our goal is to optimize the threshold $\Delta^{*}$, rather than
estimate the error of the method applied to unseen data (which is the standard
objective of cross-validation). However, these two objectives are related, as
the error of our motion detection algorithm will inform the choice of
threshold. Thus, we modify the framework of $k$-fold cross-validation to
incorporate some minimization steps to function as an algorithm to solve for
an optimal threshold $\Delta^{*}$. Our implementation is as follows:

  1. 1.

Shuffle the dataset randomly, and split it into $k$ folds (i.e., groups) of
roughly equal size. Also, initialize a vector $P$ containing the threshold
values to test over.

  2. 2.

Then, for each iteration of $i=1,\dots,k$:

    1. (a)

Select one fold as the validation set, and group the $k-1$ others into the
training set.

    2. (b)

For each video in the training set, compute its error score for each threshold
value $\Delta\in P$.

    3. (c)

Take the mean of the error scores for each threshold value tested, and find
the threshold value $\Delta_{i}$ corresponding to the smallest average error.

    4. (d)

Apply this threshold value to the videos in the validation set, and calculate
the average error score over all these videos, denoted $E_{i}$.

  3. 3.

The result of this procedure is an array of threshold values
$\Delta_{i},\;i=1,\dots k$ and their corresponding errors $E_{i}$. The optimal
threshold $\Delta^{*}$ is selected as the $\Delta_{i}$ corresponding to the
smallest average error (from testing on the validation set).

Table 1: Results of our $4$-fold cross-validation for the threshold $\Delta_{i}$ at each iteration on the database. Iteration ($i$) | 1 | 2 | 3 | 4
---|---|---|---|---
Threshold $\Delta_{i}$ | 0.196 | 0.129 | 0.19 | 0.342
Error $E_{i}$ | 67.8 | 72.2 | 49 | 170.8

We implement the above with $k=4$ since our dataset is relatively small, and
we initialize $P$ with 1000 evenly-spaced values between 0 and 1. Table 1
presents our results for one application of the modified $k$-fold cross-
validation procedure. It can be seen that the optimal threshold corresponds to
an error score of 49, where we recall that FP and FN have a score of 1 and
100, respectively. However, due to the small size of the video databases,
there are large discrepancies between the error scores corresponding to the
optimal thresholds. Moreover, each possible arrangement of the database into
the training and validation sets results in different values. We expect that
this cross-validation method will produce a more representative set of optimal
thresholds and corresponding errors for a larger database.

Figure 8: The average error on the training set over all folds as a function
of the threshold value for the database. The optimal threshold value is
indicated by a red dot.

From these results, two observations can be made. First, while the eigenvalue
detection system can be effective when optimized for a single video, as shown
in Figure 6, when optimizing over a set of videos, the performance tends to
decrease. In particular, more FPs are made in order to minimize the occurrence
of FNs over all the videos in the training set. This is evidently a
consequence of the weight given to FN errors, and is thus dependent on the
application. The second observation is that the optimal thresholds and their
corresponding errors are always a trade-off between FPs and FNs, since they
vary heavily depending on how each type of error is weighed according to the
value of $c$. As demonstrated in Figure 8, plotting the average error over
each of the training sets on which the cross-validation procedure is applied
results in a curve with a distinct global minimum. Large error is observed for
very small and very large threshold values due to the abundance of FP and FN
errors, respectively.

##  5 Conclusion

In this paper, we have outlined a new method to automatically detect motion in
video data. Our method is firmly rooted in DMD, taking advantage of its
linearity to detect motion through changes in the eigenvalues of the DMD
matrix. While the method employs a number of parameters, the one that matters
the most is the detection threshold. Thus, after demonstrating performance on
individual videos, we turned to demonstrating the effect the threshold can
have on the method and presented a framework in order to identify a threshold
value that optimizes performance.

The method relies on spikes in the DMD spectrum coming from sudden motion in
the frame, typically from an individual entering or exiting it. Thus, one
possible way to cheat this method of motion detection is to move extremely
slow so that eigenvalue spikes remain below the threshold. Despite this
potential shortcoming, our work herein has shown that DMD can be applied to
motion detection to produce a real-time, flexible, and efficient method that
can also be used to isolate foreground motion once it has been detected.

###### Acknowledgements.

The authors gratefully acknowledge Bianca Boissonneault, Lisa Marino and
Miranda Mignacca for agreeing to be in our test videos.

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

  * (1) Askham, T., Kutz, J.N.: Variable projection methods for an optimized dynamic mode decomposition.  SIAM Journal on Applied Dynamical Systems 17(1), 380–416 (2018)
  * (2) Baddoo, P.J., Herrmann, B., McKeon, B.J., Nathan Kutz, J., Brunton, S.L.: Physics-informed dynamic mode decomposition.  Proceedings of the Royal Society A 479(2271), 20220576 (2023)
  * (3) Bi, C., Yuan, Y., Zhang, R., Xiang, Y., Wang, Y., Zhang, J.: A dynamic mode decomposition based edge detection method for art images.  IEEE Photonics Journal 9(6), 1–13 (2017)
  * (4) Boykov, Y., Veksler, O.: Graph cuts in vision and graphics: Theories and applications.  In: Handbook of mathematical models in computer vision, pp. 79–96. Springer (2006)
  * (5) Bramburger, J.J., Dylewsky, D., Kutz, J.N.: Sparse identification of slow timescale dynamics.  Physical Review E 102(2), 022204 (2020)
  * (6) Brunton, B.W., Johnson, L.A., Ojemann, J.G., Kutz, J.N.: Extracting spatial–temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition.  Journal of neuroscience methods 258, 1–15 (2016)
  * (7) Brunton, S.L., Budisic, M., Kaiser, E., Kutz, J.N.: Modern koopman theory for dynamical systems.  SIAM Review 64(2), 229–340 (2022)
  * (8) Cheung, S.C.S., Kamath, C.: Robust background subtraction with foreground validation for urban traffic video.  EURASIP Journal on Advances in Signal Processing 2005, 1–11 (2005)
  * (9) Colbrook, M.J., Ayton, L.J., Szőke, M.: Residual dynamic mode decomposition: robust and verified koopmanism.  Journal of Fluid Mechanics 955, A21 (2023)
  * (10) Dylewsky, D., Tao, M., Kutz, J.N.: Dynamic mode decomposition for multiscale nonlinear physics.  Physical Review E 99(6), 063311 (2019)
  * (11) Erichson, N.B., Brunton, S.L., Kutz, J.N.: Compressed dynamic mode decomposition for background modeling.  Journal of Real-Time Image Processing 16, 1479–1492 (2019)
  * (12) Garcia-Tenorio, C., Wouwer, A.V.: Extended predictive control of interconnected oscillators.  In: 2022 8th International Conference on Control, Decision and Information Technologies (CoDIT), vol. 1, pp. 15–20. IEEE (2022)
  * (13) Grosek, J., Kutz, J.N.: Dynamic mode decomposition for real-time background/foreground separation in video.  arXiv preprint arXiv:1404.7592 (2014)
  * (14) Han, J., Kou, K.I., Miao, J.: Quaternion-based dynamic mode decomposition for background modeling in color videos.  Computer Vision and Image Understanding 224, 103560 (2022)
  * (15) Haq, I.U., Fujii, K., Kawahara, Y.: Dynamic mode decomposition via dictionary learning for foreground modeling in videos.  Computer Vision and Image Understanding 199, 103022 (2020)
  * (16) Hemati, M.S., Rowley, C.W., Deem, E.A., Cattafesta, L.N.: De-biasing the dynamic mode decomposition for applied koopman spectral analysis of noisy datasets.  Theoretical and Computational Fluid Dynamics 31, 349–368 (2017)
  * (17) James, G., Witten, D., Hastie, T., Tibshirani, R.: An Introduction to Statistical Learning, 2 edn.  Springer (2021)
  * (18) Krake, T., Bruhn, A., Eberhardt, B., Weiskopf, D.: Efficient and robust background modeling with dynamic mode decomposition.  Journal of Mathematical Imaging and Vision 64(4), 364–378 (2022)
  * (19) Kutz, J.N., Brunton, S.L., Brunton, B.W., Proctor, J.L.: Dynamic Mode Decomposition.  Society for Industrial and Applied Mathematics (2016)
  * (20) Kutz, J.N., Fu, X., Brunton, S.L., Erichson, N.B.: Multi-resolution dynamic mode decomposition for foreground/background separation and object tracking.  In: 2015 IEEE International Conference on Computer Vision Workshop (ICCVW), pp. 921–929. IEEE (2015)
  * (21) Lee, M., Park, J.: An optimized dynamic mode decomposition model robust to multiplicative noise.  SIAM Journal on Applied Dynamical Systems 22(1), 235–268 (2023)
  * (22) Mann, J., Kutz, J.N.: Dynamic mode decomposition for financial trading strategies.  Quantitative Finance 16(11), 1643–1655 (2016)
  * (23) Menon, K., Mittal, R.: Dynamic mode decomposition based analysis of flow over a sinusoidally pitching airfoil.  Journal of Fluids and Structures 94, 102886 (2020)
  * (24) Morandin, R., Nicodemus, J., Unger, B.: Port-hamiltonian dynamic mode decomposition.  SIAM Journal on Scientific Computing 45(4), A1690–A1710 (2023)
  * (25) Oh, T.H., Lee, J.Y., Kweon, I.S.: Real-time motion detection based on discrete cosine transform.  In: 2012 19th IEEE International Conference on Image Processing, pp. 2381–2384. IEEE (2012)
  * (26) Partamian, H., Tabbal, J., Hassan, M., Karameh, F.: Analysis of task-related meg functional brain networks using dynamic mode decomposition.  Journal of Neural Engineering 20(1), 016011 (2023)
  * (27) Proctor, J.L., Brunton, S.L., Kutz, J.N.: Dynamic mode decomposition with control.  SIAM Journal on Applied Dynamical Systems 15(1), 142–161 (2016)
  * (28) Rahul-Vigneswaran, K., Sachin-Kumar, S., Mohan, N., Soman, K.: Dynamic mode decomposition based feature for image classification.  In: TENCON 2019-2019 IEEE Region 10 Conference (TENCON), pp. 745–750. IEEE (2019)
  * (29) Rowley, C.W., Mezić, I., Bagheri, S., Schlatter, P., Henningson, D.S.: Spectral analysis of nonlinear flows.  Journal of fluid mechanics 641, 115–127 (2009)
  * (30) Schmid, P.J.: Dynamic mode decomposition of numerical and experimental data.  Journal of Fluid Mechanics 656, 5–28 (2010)
  * (31) Schmid, P.J.: Dynamic mode decomposition and its variants.  Annual Review of Fluid Mechanics 54, 225–254 (2022)
  * (32) Schmid, P.J., Li, L., Juniper, M.P., Pust, O.: Applications of the dynamic mode decomposition.  Theoretical and computational fluid dynamics 25, 249–259 (2011)
  * (33) Shiraishi, Y., Kawahara, Y., Yamashita, O., Fukuma, R., Yamamoto, S., Saitoh, Y., Kishima, H., Yanagisawa, T.: Neural decoding of electrocorticographic signals using dynamic mode decomposition.  Journal of Neural Engineering 17(3), 036009 (2020)
  * (34) Sikha, O., Kumar, S.S., Soman, K.: Salient region detection and object segmentation in color images using dynamic mode decomposition.  Journal of Computational Science 25, 351–366 (2018)
  * (35) Sikha, O., Soman, K.: Multi-resolution dynamic mode decomposition-based salient region detection in noisy images.  Signal, Image and Video Processing 14, 167–175 (2020)
  * (36) Sikha, O., Soman, K.: Dynamic mode decomposition based salient edge/region features for content based image retrieval.  Multimedia Tools and Applications 80(10), 15937–15958 (2021)
  * (37) Singh, S., Prasad, A., Srivastava, K., Bhattacharya, S.: Object motion detection methods for real-time video surveillance: A survey with empirical evaluation.  In: Smart Systems and IoT: Innovations in Computing: Proceeding of SSIC 2019, pp. 663–679. Springer (2020)
  * (38) Tsai, D.M., Chiu, W.Y.: Motion detection using fourier image reconstruction.  Pattern Recognition Letters 29(16), 2145–2155 (2008)
  * (39) Tu, J.H., Rowley, C.W., Luchtenburg, D.M., Brunton, S.L., Kutz, J.N.: On dynamic mode decomposition: Theory and applications.  Journal of Computational Dynamics 1(2), 391–421 (2014).  DOI 10.3934/jcd.2014.1.391
  * (40) Vacavant, A., Chateau, T., Wilhelm, A., Lequievre, L.: A benchmark dataset for outdoor foreground/background extraction (2012).  URL backgroundmodelschallenge.eu
  * (41) Yu, Z., Chen, Y.: A real-time motion detection algorithm for traffic monitoring systems based on consecutive temporal difference.  In: 2009 7th Asian Control conference, pp. 1594–1599. IEEE (2009)