Robust Real-Time Periodic Motion Detection, Analysis, and Applications.
AbstractWe describe new techniques to detect and analyze periodic motion as seen from both a static and a moving camera. By tracking objects of interest, we compute an object's self-similarity as it evolves in time. For periodic motion, the self-similarity measure is also periodic and we apply Time-Frequency analysis to detect and characterize the periodic motion. The periodicity is also analyzed robustly using the 2D lattice structures inherent in similarity matrices. A real-time system has been implemented to track and classify objects using periodicity. Examples of object classification (people, running dogs, vehicles), person counting, and nonstationary periodicity are provided.
Introduction
Object motions that repeat are common in both nature and the man-made environment in which we
live. Perhaps the most prevalent periodic motions are the ambulatory motions made by humans and
animals in their gaits (commonly referred to as "biological motion" [16]). Other examples include
a person walking, a waving hand, a rotating wheel, ocean waves, and a flying bird. Knowing that
an object's motion is periodic is a strong cue for object and action recognition [16, 11]. In addition,
periodic motion can also aid in tracking objects. Furthermore, the periodic motion of people can be
used to recognize individuals [20].
1.1 Motivation
Our work is motivated by the ability of animals and insects to utilize oscillatory motion for action
and object recognition and navigation. There is behavioral evidence that pigeons are well adapted to
recognize the types of oscillatory movements that represent components of the motor behavior shown
by many living organisms [9]. There is also evidence that certain insects use oscillatory motion for
navigational purposes (hovering above flowers during feeding) [17]. Humans can recognize biological
motion from viewing lights placed on the joints of moving people [16]. Humans can also recognize
periodic movement of image sequences at very low resolutions, even when point correspondences are
not possible. For example, Figure 1 shows such a sequence. The effective resolution of this sequence
is 9x15 pixels (it was created by resampling a 140x218 (8-bit, 30fps) image sequence to 9x15 and back
to 140x218 using bicubic interpolation). In this sequence, note the similarity between frames 0 and 15.
We will use image similarity to detect and analyze periodic motion.

Figure

1. Low resolution image sequences of a periodic motion (a person walking on a treadmill). The
e#ective resolution is 9x15 pixels.
1.2 Periodicity and motion symmetries
We define the motion of a point #
X(t), at time t, periodic if it repeats itself with a constant period p,
i.e.:
T (t) is a translation of the point. The period p is the smallest p > 0 that satisfies (1); the
frequency of the motion is 1/p. If p is not constant, then the motion is cyclic. In this work, we analyze
locally (in time) periodic motion, which approximates many natural forms of cyclic motion.
Periodic motion can also be defined in terms of symmetry. Informally, spatial symmetry is self-similarity
under a class of transformations, usually the group of Euclidean transformations in the plane
(translations, rotations, and reflections)[36]. Periodic motion has a temporal (and sometimes spatial)
symmetry. For example, Figures 3(a), 4(a), 5(a), and 6(a) show four simple dynamic systems (pendu-
lums). For each system, the motion is such that #
X(t) for a point #
X(t) on the pendulum.
However, each system exhibits qualitatively different types of periodic motion. Figure 5(a) is a simple
planar pendulum with a fixed rod under a gravitational field. The motion of this system gives it a temporal
mirror symmetry along the shown vertical axis. The system in Figure 4(a) is a similar pendulum, but
with a sufficient initial velocity such that it always travels in one angular direction. The motion of this
system gives it a temporal mirror symmetry along the shown vertical axis. The system in Figure 3(a)
is a similar pendulum, but in zero gravity; note it has an infinite number of axes of symmetry that pass
through the pivot of the pendulum. The system in Figure 6(a) consists of a pair of uncoupled and 180 #
out of phase pendulums, a system which is often used to model the upper leg motion of humans [24].
This system has a temporal mirror symmetry along the shown vertical axis, as well as an approximate
spatial mirror symmetry along the same vertical axis (it is approximate because the pendulums are not
identical).
The above examples illustrate that while eq. 1 can be used to detect periodicity, it is not sufficient
to classify different types of periodic motion. For classification purposes, it is necessary to exploit the
dynamics of the system of interest, which we do in Section 3.4.
1.3 Assumptions
In this work, we make the following assumptions: (1) the orientation and apparent size of the segmented
objects do not change significantly during several periods (or do so periodically); (2) the frame
rate is sufficiently fast for capturing the periodic motion (at least double the highest frequency in the
periodic motion).
Contributions
The main contribution of this work is the introduction of novel techniques to robustly detect and
analyze periodic motion. We have demonstrated these techniques with video of the quality typically
found in both ground and airborne surveillance systems. Of particular interest is the utilization of the
symmetries of motion exhibited in nature, which we use for object classification. We also provide
several other novel applications of periodic motion, all related to automating a surveillance system.
Organization of the Paper
In Section 2, we review and critique the related work. The methodology is described in Section 3.
Examples and applications of periodic motion, particularly for the automated surveillance domain, are
given in Section 4. A real-time implementation of the methods is discussed in Section 5, followed by a
summary of the paper in Section 6.
Related Work
There has been recent interest in segmenting and analyzing periodic or cyclic motion. Existing methods
can be categorized as those requiring point correspondences [33, 35]; those analyzing periodicities
of pixels [21, 30]; those analyzing features of periodic motion [27, 10, 14]; and those analyzing the
periodicities of object similarities [6, 7, 33]. Related work has been done in analyzing the rigidity of
moving objects [34, 25]. Below we review and critique each of these methods. Due to some similarities
with the presented method, [33, 21, 30] are described in more detail than the other related work.
Seitz and Dyer [33] compute a temporal correlation plot for repeating motions using different image
comparison functions, dA and d I . The affine comparison function dA allows for view-invariant analysis
of image motion, but requires point correspondences (which are achieved by tracking reflectors on
the analyzed objects). The image comparison function d I computes the sum of absolute differences
between images. However, the objects are not tracked, and thus must have non-translational periodic
motion in order for periodic motion to be detected. Cyclic motion is analyzed by computing the period-
trace, which are curves that are fit to the surface d. Snakes are used to fit these curves, which assumes
that d is well-behaved near zeros so that near-matching configurations show up as local minima of d.
The K-S test is utilized to classify periodic and non-periodic motion. The samples used in the K-S
test are the correlation matrix M and the hypothesized period-trace PT . The null hypothesis is that
the motion is not periodic, i.e., the cumulative distribution function M and PT not are significantly
different. The K-S test rejects the null hypothesis when periodic motion is present. However, it also
rejects the null hypothesis if M is non-stationary. For example, when M has a trend, the cumulative
distribution function of M and PT can be significantly different, resulting in classifying the motion as
periodic (even if no periodic motion present). This can occur if the viewpoint of the object or lighting
changes significantly during evaluation of M (see Figure 19(a)). The basic weakness of this method
is it uses a one-sided hypothesis test which assumes stationarity. A stronger test is needed to detect
periodicity in non-stationary data, which we provide in Section 3.4.
Polana and Nelson [30] recognize periodic motions in an image sequence by first aligning the frames
with respect to the centroid of an object so that the object remains stationary in time. Reference curves,
which are lines parallel to the trajectory of the motion flow centroid, are extracted and the spectral
power is estimated for the image signals along these curves. The periodicity measure of each reference
curve is defined as the normalized difference between the sum of the spectral energy at the highest
amplitude frequency and its multiples, and the sum of the energy at the frequencies half way between.
et. al [35] analyze the periodic motion of a person walking parallel to the image plane. Both
synthetic and real walking sequences are analyzed. For the real images, point correspondences were
achieved by manually tracking the joints of the body. Periodicity was detected using Fourier analysis
of the smoothed spatio-temporal curvature function of the trajectories created by specific points on the
body as it performs periodic motion. A motion based recognition application is described, in which one
complete cycle is stored as a model, and a matching process is performed using one cycle of an input
trajectory.
Allmen [1] used spatio-temporal flow curves of edge image sequences (with no background edges
present) to analyze cyclic motion. Repeating patterns in the ST flow curves are detected using curvature
scale-space. A potential problem with this technique is that the curvature of the ST flow curves is
sensitive to noise. Such a technique would likely fail on very noisy sequences, such as that shown in

Figure

15.
Niyogi and Adelson [27] analyze human gait by first segmenting a person walking parallel to the
image plane using background subtraction. A spatio-temporal surface is fit to the XYT pattern created
by the walking person. This surface is approximately periodic, and reflects the periodicity of the gait.
Related work [26] used this surface (extracted differently) for gait recognition.
Liu and Picard [21] assume a static camera and use background subtraction to segment motion.
Foreground objects are tracked, and their path is fit to a line using a Hough transform (all examples
have motion parallel to the image plane). The power spectrum of the temporal histories of each pixel is
then analyzed using Fourier analysis, and the harmonic energy cause by periodic motion is estimated.
An implicit assumption in [21] is that the background is homogeneous (a sufficiently non-homogeneous
background will swamp the harmonic energy). Our work differs from [21] and [30] in that we analyze
the periodicities of the image similarities of large areas of an object, not just individual pixels aligned
with an object. Because of this difference (and the fact that we use a smooth image similarity metric)
our Fourier analysis is much simpler, since the signals we analyze do not have significant harmonics of
the fundamental frequency. The harmonics in [21] and [30] are due to the large discontinuities in the
signal of a single pixel; our self-similarity metric does not have such discontinuities.
Fujiyoshi and Lipton [10] segment moving objects from a static camera and extract the object bound-
aries. From the object boundary, a "star" skeleton is produced, which is then Fourier analyzed for
periodic motion. This method requires accurate motion segmentation, which is not always possible
(e.g., see

Figure

16). Also, objects must be segmented individually; no partial occlusions are allowed
(as shown in Figure 21(a)). In addition, since only the boundary of the object is analyzed for periodic
change (and not the interior of the object), some periodic motions may not be detected (e.g., a textured
rolling ball, or a person walking directly toward the camera).
Selinger and Wixson [34] track objects and compute self-similarities of that object. A simple heuristic
using the peaks of the 1-D similarity measure is used to classify rigid and non-rigid moving objects,
which in our tests fails to classify correctly for noisy images (e.g., the sequence in Figure 15).
Heisele and Wohler [14] recognize pedestrians using color images from a moving camera. The
images are segmented using a color/position feature space, and the resulting clusters are tracked. A
quadratic polynomial classifier extracts those clusters which represent the legs of pedestrians. The
clusters are then classified by a time delay neural network, with spatio-temporal receptive fields. This
method requires accurate object segmentation. A 3-CCD color camera was used to facilitate the color
clustering, and pedestrians are approximately 100 pixels in height. These image qualities and resolutions
are typically not found in surveillance applications.
There has also been some work done in classifying periodic motion. Polana and Nelson [30] use
the dominant frequency of the detected periodicity to determine the temporal scale of the motion. A
temporally scaled XYT template, where XY is a feature based on optical flow, is used to match the
given motion. The periodic motions include walking, running, swinging, jumping, skiing, jumping
jacks, and a toy frog. This technique is view dependent, and has not been demonstrated to generalize
across different subjects and viewing conditions. Also, since optical flow is used, it will be highly
susceptible to image noise.
Cohen et. al [5] classifies oscillatory gestures of a moving light by modeling the gestures as simple
one-dimensional ordinary differential equations. Six classes of gestures are considered (all circular
and linear paths). This technique requires point correspondences, and has not been shown to work on
arbitrary oscillatory motions.
Area-based techniques, such as the present method, have several advantages over pixel-based tech-
niques, such as [30, 21]. Specifically, area-based techniques allow the analysis of the dynamics of the
entire object, which is not achievable by pixel based techniques. This allows for classification of different
types of periodic motion, such as those given in Section 4.1 and Section 4.4. In addition, area-based
techniques allow detection and analysis of periodic motion that is not parallel to the image plane. All
examples given in [30, 21] have motion parallel to the image plane, which ensures there is sufficient
periodic pixel variation for the techniques to work. However, since area-based methods compute object
similarities which span many pixels, the individual pixel variations do not have to be large. For exam-
ple, our method can detect periodic motion from video sequences of people walking directly toward
the camera. A related benefit is that area-based techniques allow the analysis of low S/N images, such
as that shown in Figure 16, since the S/N of the object similarity measure (such as (5)) is higher than
that of a single pixel.
The algorithm for periodicity detection and analysis consists of two parts. First, we segment the
motion and track objects in the foreground. We then align each object along the temporal axis (using
the object's tracking results) and compute the object's self-similarity as it evolves in time. For periodic
motions, the self-similarity metric is periodic, and we apply Time-Frequency analysis to detect and
characterize the periodicity. The periodicity is also analyzed robustly using the 2-D lattice structures
inherent in similarity matrices.
3.1 Motion Segmentation and Tracking
Given an image sequence I t from a moving camera, we segment regions of independent motion. The
images I t are first Gaussian filtered to reduce noise, resulting in I #
. The image I #
is then stabilized [12]
with respect to image I #
t-#
, resulting in V t,t-# . The images V t,t-# and I #
are differenced and thresholded
to detect regions of motion, resulting in a binary motion image:
(2)
where TM is a threshold. In order to eliminate false motion at occlusion boundaries (and help filter
spurious noise), the motion images M t,# and M t,-# are logically and'ed together:
An example of M t is shown in Figure 21(b). Note that for large values of # , motion parallax will cause
false motion in M t . In our examples (for a moving camera), #=300 ms was used.
Note that in many surveillance applications, images are acquired using a camera with automatic gain,
shutter, and exposure. In these cases, normalizing the image mean before comparing images I t 1
and I t 2
will help minimize false motion due to a change in the gain, shutter, or exposure.
A morphological open operation is performed on M t (yielding M # t ), which reduces motion due to
image noise. The connected components for M # t are computed, and small components are eliminated
(further reducing image noise). The connected components which are spatially similar (in distance)
are then merged, and the merged connected components are added to a list of objects O t to be tracked.
An object has the following attributes: area, centroid, bounding box, velocity, ID number, and age (in
frames). Objects in O t and O t+k , k > 0, are corresponded using spatial and temporal coherency.
It should be noted that the tracker is not required to be very accurate, as the self-similarity metric we
use is robust and can handle tracking errors of several pixels (as measured in our examples).
Also note that when the background of a tracked object is sufficiently homogeneous, and the tracked
object does not change size significantly during several periods, then accurate object segmentation is not
necessary. In these cases, we can allow O t to include both the foreground and background. Examples
of such backgrounds include grassy fields, dirt roads, or parking lots. An example of such a sequence
is given in Figure 15.
3.2 Periodicity Detection and Analysis
The output of the motion segmentation and tracking algorithm is a set of foreground objects, each
of which has a centroid and size. To detect periodicity for each object, we first align the segmented
object (for each frame) using the object's centroid, and resize the objects (using a Mitchell filter [32])
so that they all have the same dimensions. The scaling is required to account for apparent size change
due to change in distance from the object to the camera. Because the object segmentation can be noisy,
the object dimensions are estimated using the median of N frames (where N is the number of frames
we analyze the object over). The object O t 's self-similarity is then computed at times t 1 and t 2 . While
many image similarity metrics can be defined (e.g., normalized cross-correlation, Hausdorff distance
[15], color indexing [2]), perhaps the simplest is absolute correlation:
is the bounding box of object O t 1
. In order to account for tracking errors, the minimal S is
found by translating over a small search radius r:
|dx,dy|<r
For periodic motions, S # will also be periodic. For example, Figure 8(a) shows a plot of S # for all
combinations of t 1 and t 2 for a walking sequence (the similarity values have been linearly scaled to
the grayscale intensity range [0,255]; dark regions show more similarity). Note that a similarity plot
should be symmetric along the main diagonal; however, if substantial image scaling is required, this
will not be the case. In addition, there will always be a dark line on the main diagonal (since an object
is similar to itself at any given time), and periodic motions will have dark lines (or curves if the period
is not constant) parallel to the diagonal.
To determine if an object exhibits periodicity, we estimate the 1-D power spectrum of S #
a fixed t 1 and all values of t 2 (i.e., the columns of S # ). In estimating the spectral power, the columns
of S # are linearly detrended and a Hanning filter is applied. A more accurate spectrum is estimated by
averaging the spectra of multiple t 1 's [31] to get a final power estimate P (f i ), where f i is the frequency.
Periodic motion will show up as peaks in this spectrum at the motion's fundamental frequencies. A peak
at frequency f i is significant if
where K is a threshold value (typically 3),  P is the mean of P , and # P is the standard deviation of P .
Note that multiple peaks can be significant, as we will see in the examples.
In the above test, we assume that the period is locally constant. The locality is made precise using
Time-Frequency analysis given in Section 3.3. We also assume that there are only linear amplitude
modulations to the columns of S # (so that linear detrending is sufficient to make the data stationary),
and that any additive noise to S # is Gaussian. Both of these assumption are relaxed in the method given
in Section 3.4.
3.2.1 Fisher's Test
If we assume that columns of S # are stationary and contaminated with white noise, and that any periodicity
present consists of a single fundumental frequency, then we can apply the well known Fisher's test
[29, 3]. Fisher's test will reject the null hypothesis (that S # is only white noise) if P (f i ) is substantially
larger than the average value. Assuming N is even, let
. (7)
To apply the test, we compute the realized value x of E q from S # , and then compute the probability:
0). If this probability is less than #, then we reject the null hypothesis at level
(in practice we use This test is optimal if there exists a single periodic component at a
Fourier frequency f i in white noise stationary data [29]. To test for periodicities containing multiple
frequencies, Seigel's test [29] can be applied.
In practice, Fisher's test, like the K-S test used by [33], works well if the periodic data is stationary
with white noise. However, in most of our non-periodic test data (e.g., Figure 19(a)), which is not
stationary, both Fisher's and the K-S test yield false periodicities with high confidence.
3.2.2 Recurrence Matrices
It is interesting to note that S # is a recurrence matrix [8, 4], without using time-delayed embedded
dimensions. Recurrence matrices are a qualitative tool used to perform time series analysis of non-linear
dynamical systems (both periodic and non-periodic). Recurrence matrices make no assumptions
on the stationarity of the data, and do not require many data points to be used (a few cycles of periodic
data is sufficient). The input for a recurrence matrix is a multi-dimensional temporally sampled signal.
In our use, the input signal is the tracked object image sequence O t , and the distance measure is image
similarity. Given a recurrence matrix, the initial trajectory #
X(t) of a point on an object can be recovered
up to an isometry [23]. Therefore, the recurrence plot encodes the spatiotemporal dynamics of the
moving object. The similarity plot encodes a projection of the spatiotemporal dynamics of the moving
object.
3.3 Time-Frequency Analysis
For stationary periodicity (i.e., periodicity with statistics that don't change with time), the above analysis
is sufficient. However, for non-stationary periodicity, Fourier analysis is not appropriate. Instead,
we use Time-Frequency analysis and the Short-Time Fourier Transform (STFT) [28]:
-#
is a short-time analysis window, and x(u) is the signal to analyze (S # in our case). The
short-time analysis window effectively suppresses the signal x(u) outside a neighborhood around the
analysis time point t. Therefore, the STFT is a "local" spectrum of the signal x(u) around t.
We use a Hanning windowing function as the short-time analysis window. The window length should
be chosen to be long enough to achieve a good power spectrum estimate, but short enough to capture
a local change in the periodicity. In practice, a window length equal to several periods works well for
typical human motions. An example of non-stationary periodicity is given in Section 4.7.
3.4 Robust Periodicity Analysis
In Sections 3.2 and 3.3, we used a hypothesis test on the 1-D power spectrum of S # to determine if
contained any periodic motion. The null hypothesis is that there is only white noise in the spectrum,
which is rejected by eq. 6 if significant periodic motion is present. However, the null hypothesis can
also be rejected if S # contains significant non-Gaussian noise, or if the period is locally non-constant,
or if S # is amplitude modulated non-linearly. We seek a technique that minimizes the number of false
periodicities, while maximizing the number of true periodicities. Toward this end, we devise a test
that performs well when the assumptions stated in Section 3.2 are satisfied, but does not yield false
periodicities when these assumptions are violated.
An alternative technique to Fourier analysis of the 1-D columns of S is to analyze the 2-D power
spectrum of S # . However, as noted in [19], the autocorrelation of S # for regular textures has more
prominent peaks than those in the 2-D Fourier spectrum. Let A be the normalized autocorrelation of
the
A(d x , d y
where
S # R is the mean of S # over the region R,
# RL is the mean of S # over the region R shifted by the
lag (dx, dy), and the regions R and R L cover S # and the lagged S # . If S # is periodic, then A will have
peaks regularly spaced in a planar lattice M d , where d is the distance between the lattice points. In our
examples, we will consider two lattices, a square lattice M S,d (Figure 2(a)), and a 45 # rotated square
lattice M R,d (Figure 2(b)). The peaks P in A are matched to M d using the match error measure e:
is the closest peak to the lattice point M d,i , TD (T D < d/2) is the maximum distance P i can
deviate from M d,i , and is the minimum autocorrelation value that the matched peak may have. M d
matches P if all the following are satisfied:
min
where T e is a match thresholds; [d 1 , d 2 ] is the range of d; TM is the minimum number of points in M d
to match. In practice, we let 0.25. The range
determines the possible range of the expected period, with the requirement 0 < d 1 < d 2 < L,
where L is the maximum lag used in computing A. The number of points in MR and M S can be based
on the period of the expected periodicity, and frame-rate of the camera. The period
is the sampling interval (e.g., ms for NTSC video).
Peaks in A are determined by first smoothing A with Gaussian filter G, yielding A # . A # (i, j) is a
peak if A # (i, j) is a strict maximum in a local neighborhood with radius N . In our examples, G is a
5. Lin et. al [19] provides an automatic method for determining the
optimal size of G.
Square Lattice
d
(a)
2d
(b)

Figure

2. Lattices used to match the peaks of the autocorrelation of S # . (a) Square lattice (b)
rotated square lattice.
4 Examples and Applications
4.1 Synthetic Data
In this section, we demonstrate the methods on synthetic data examples. We generated images of a
periodic planar pendulum, with different initial conditions, parameters, and configurations. Note that
the equation of motion for a simple planar pendulum is
sin
where g is the gravitational acceleration, L is the length of the rigid rod, and # is the angle between the
pendulum rod and vertical axis [22]. In the first example (see Figure 3(a)), we set so that the
pendulum has a circular motion with a constant angular velocity. The diagonal lines in the similarity
plot (

Figure

are formed due to the self-similarity of the pendulum at every complete cycle. The
autocorrelation (Figure 3(c)) has no peaks.
(a)
TSimilarity of Image T 1 and T 2
50 100 150 200 250 300 350 400100200300400
(b)
Autocorrelation of Similarity
TLag
-252575125(c)

Figure

3. (a) Pendulum in zero gravity with a constant angular velocity. The arrows denote the direction
of motion. (b) Similarity plot for pendulum. Darker pixels are more similar. (c) Autocorrelation of
similarity plot.
In the next example, we use the same configuration, but set g > 0 and the initial angular velocity
to be sufficient so that the pendulum still has a single angular direction. However, in this configuration
the angular velocity is not constant, which is reflected in the qualitatively different similarity plot

Figure

4(b)) and autocorrelation (Figure 4(c)). Note that the peaks in A match the lattice structure in

Figure

2(a).
By decreasing the initial angular velocity, the pendulum will oscillate with a changing angular di-
rection, as shown in Figure 5(a). The similarity plot for this system is shown in Figure 5(b), and the
autocorrelation in Figure 5(c). Note that the peaks in A match the lattice structure in Figure 2(b).
(a)
TSimilarity of Image T 1
and T 2
100 200 300 400 500 600200400600
(b)
Autocorrelation of Similarity
TLag
(c)

Figure

4. (a) Pendulum in gravity with single angular direction. The arrows denote the direction and
magnitude of motion; the pendulum travels faster at the bottom of its trajectory than at the top.
(b) Similarity plot for pendulum. (c) Autocorrelation of similarity plot. The peaks are denoted by '+'
symbols.
(a)
TSimilarity of Image T 1 and T 2
100 200 300 400 500 600200400600
(b)
Autocorrelation of Similarity
TLag
(c)

Figure

5. (a) Pendulum in gravity with an oscillating angular direction. The arrows denote the direction
of motion. (b) Similarity plot for pendulum. (c) Autocorrelation of similarity plot. The peaks are
denoted by '+' symbols.
Finally, for the system of two pendulums 180 # out of phase shown in Figure 6(a), the similarity plot
is shown in Figure 6(b), and the autocorrelation is shown in Figure 6(c). Note that the peaks in A match
the lattice structure in Figure 2(b). Also note the lower measures of similarity for the diagonal lines
and the cross-diagonal lines S(t, and the corresponding effect on
A.
(a)
TSimilarity of Image T 1 and T 2
100 200 300 400 500 600200400600
(b)
Autocorrelation of Similarity
TLag
(c)

Figure

6. (a) Two pendulum out of phase 180 # in gravity. The arrows denote the direction of motion.
(b) Similarity plot for pendulums. (c) Autocorrelation of similarity plot. The peaks are denoted by '+'
symbols.
4.2 The Symmetry of a Walking Person
In this example we first analyze periodic motion with no (little) translational motion, a person walking
on a treadmill (Figure 7). This sequence was captured using a static JVC KY-F55B color camera
at 640x480 @ 30fps, deinterlaced, and scaled to 160x120. Since the camera is static and there is no
translational motion, background subtraction was used to segment the motion [6].
The similarity plot S # for this sequence is shown in Figure 8(a). The dark lines correspond to two
images in the sequence that are similar. The darkest line is the main diagonal, since S # (t,
dark lines parallel to the main diagonal are formed since S # (t, kp/2+ t) # 0, where p is the period, and
k is an integer. The dark lines perpendicular to the main diagonal are formed since S # (t, kp/2- t) # 0,
and is due to the symmetry of human walking (see Figure 10).
It is interesting to note that at the intersections of these lines, these images are similar to either (a),
(b), or (c) in Figure 7 (see Figure 8(b)). That is, S # encodes the phase of the person walking, not just
the period. This fact is exploited in the example in Section 4.5.
The autocorrelation A of S # is shown in Figure 9(b). The peaks in A form a rotated square lattice

Figure

2(b)), which is used for object classification (Section 4.4). Note that the magnitude of the peaks
in A (

Figure

9(b)) have a pattern similar to the A in Figure 6(c).
(a) (b) (c)

Figure

7. Person walking on a treadmill.
TSimilarity of Image T 1 and T 2
(a)
TSimilarity of Image T 1 and T 2
AC
AA
(b)

Figure

8. (a) Similarity plot for the person walking in Figure 7. (b) Lattice structure for the upper left
quadrant of (a). At the intersections of the diagonal and cross diagonal lines are images similar to (a),
(b), (c) in

Figure

7. This can be used to determine the phase of the walking person.
Frequency (Hz)
Power
Spectral Power
Power
Mean
(a)
Autocorrelation of Similarity
TLag
(b)

Figure

9. (a) Power spectrum of similarity of a walking person. (b) Autocorrelation of the similarity of
the walking person in Figure 7 (smoothed with a 5  5 filter). The peaks (shown with
white '+' symbols) are used to fit the rotated square lattice in Figure 2(b).

Figure

10. Cycle of a person walking (p = 32). Note the similarity of frame t and p/2 - t, and the
similarity of frame t and p/2 t.
We next analyze the motion of a person who is walking at an approximately 25 # offset to the camera's
image plane from a static camera. (Figure 11(a)). The segmented person is approximately 20 pixels in
height, and is shown in Figure 12(a). The similarity plot (Figure 11(b)) shows dark diagonal lines at a
period of approximately 1 second (32 frames), which correspond to the period of the person's walking.
The lighter diagonal lines shown with a period of approximately 0.5 seconds (16 frames) are explained
by first noting that the person's right arm swing is not fully visible (due to the 25 # offset to the image
plane). Therefore, it takes two steps for the body to be maximally self-similar, while the legs become
very self-similar at every step. The effect of this is that the similarity measure S # is the composition of
two periodic signals, with periods differing by a factor of two. This is shown in Figure 12(b), where
the aligned object image is partitioned in the three segments (the upper 25%, next 25%, and lower
50% of the body), and S # is computed for each segment. The upper 25%, which includes the head and
shoulders, shows no periodic motion; the next 25%, which includes the one visible arm, has a period
double that of the lower 50% (which includes the legs). Figure 12(c) shows the average power spectrum
for all the columns in S # .
(a)
TSimilarity of Image T 1 and T 2
(b)

Figure

11. (a) First image of a 100-image walking sequence (the subject is walking approx. 25 # o#set
from the camera's image plane). (b) Walking sequence similarity plot, which shows the similarity of
the object (person) at times t 1 and t 2 . Dark regions show greater degrees of similarity.
Similarity
Similarity of Image 1 with Image T
(a)
Similarity
Separated Similarity of Image 1 to Image T
upper 25%
next 25%
lower 50%
(b)
Power
Spectral Power of Similarity
Power
Mean
(c)

Figure

12. (a) Column 1 of Figure 11(b), with the corresponding segmented object for the local minima.
(b) Image similarity for upper 25%, next 25%, and lower 50% of body. (c) Average power spectrum
of all columns of Figure 11(b).
4.3 The Symmetry of a Running Dog
In this example, we look at the periodicity of a running dog from a static camera. Figure 13 shows
a complete cycle of a dog (a Black Labrador). Unlike the symmetry of a walking/running person, a
running dog has a lack of similarity for S # (t, kp - t). This results in the similarity plot (Figure 14(a))
having dark lines parallel to the main diagonal, formed by S # (t, kp + t), but no lines perpendicular to
the main diagonal (as with a walking/running person). The similarity plot has peaks (Figure 14(a))
that correspond to poses of the dog at frame 0 in Figure 13. The autocorrelation A of S # is shown in

Figure

14(b); the peaks of the A form a square lattice (Figure 2(a)), which is used in Section 4.4 for
object classification.

Figure

13. Cycle of a running dog (p = 12). Note the lack of similarity for any two frames t 1 and t 2 ,
4.4 Object Classification Using Periodicity
A common task in an automated surveillance system is to classify moving objects. In this example,
we classify three types of moving objects: people, dogs, and other. We use the lattice fitting method
described in Section 3.4 for the classification, which is motivated by texture classification methods.
Specifically, the square lattice M S (Figure 2(a)) is used to classify running dogs, and the 45 # square
lattice MR (Figure 2(b)) is used to classify walking or running people. Note that M R,d is a subset of
M S,d , so if both M S,d and M R,d match, MR is declared the winner. If neither lattice provides a good
match to A, then the moving object is classified as other.
The video database used to test the classification consists of video from both airborne surveillance
(people and vehicles), and ground surveillance (people, vehicles, and dogs). The database consists of
vehicle sequences (25 from airborne video); 55 person sequences (50 from airborne video); and 4
Similarity of Image T 1 and T 2
(a)
Autocorrelation of Similarity
TLag
(b)

Figure

14. (a) Similarity plot of the running dog in Figure 13. Note there there are no dark lines
perpendicular to the main diagonal, as shown in Figure 8(a). (b) Autocorrelation of the similarity plot
(smoothed with a 5  5 filter). The peaks (shown with white '+' symbols) are used
to fit the square lattice in Figure 2(a).
dog sequences (all from ground video).
For the airborne video and dog sequences, the background was not segmented from the foreground
object. For these sequences, the background was sufficiently homogeneous (e.g., dirt roads, parking
lots, grassy fields) for this method to work. For the other sequences (taken with a static camera), the
background was segmented as described in [6].
The airborne video in was recorded from a Sony XC-999 camera (640x240 @ 30fps) at an altitude
of about 1500 feet. There is significant motion blur due to a slow shutter speed and fast camera motion.
Additional noise is induced by the analog capture of the video from duplicated SVHS tape. Figure 15
shows a person running across a parking lot. The person is approximately 12x7 pixels in size (Fig-
ure 16). The similarity plot in Figure 17(a) shows a clearly periodic motion, which corresponds to the
person running. Figure 18 shows that the person is running with a frequency of 1.3Hz; the second peak
at 2.6Hz is due to the symmetry of the human motion described in Section 4.2. The autocorrelation
of S # is shown in Figure 17(b). Figure 19(b) shows the similarity plot for the vehicle in Figure 19(a),
which has no periodicity. The spectral power for the vehicle (Figure 20(b)) is flat. The autocorrelation
of S # has only 2 peaks (Figure 20(a)).
The results of the classifications are shown in Table 1. The thresholds used for the lattice matching
are those given in Section 3.4. Each sequence is 100 images (30 fps); a lag time of images (1 second)
is used to compute A.
Other Person Dog
Other
Person

Table

1. Confusion matrix for person, dog, and other classification.
4.5 Counting People
Another common task in an automated surveillance system is to count the number of people entering
and leaving an area. This task is difficult, since when people are close to each other, it is not always

Figure

15. Person running across a parking lot, viewed from a moving camera at an altitude of 1500'.
(a) (b) (c)

Figure

16. Zoomed images of the person in Figure 15, which correspond to the poses in Figure 7. The
person is 12x7 pixels in size.
Similarity of Image T 1 and T 2
Autocorrelation of Similarity
TLag
(b)

Figure

17. (a) Similarity plot of the running person in Figure 15. (b) Autocorrelation of upper quadrant
of S # . The peaks are used to fit the rotated square lattice in Figure 2(b).
Power
Spectral Power of Similarity
Power
Mean

Figure

18. Spectral power of the running person in Figure 15.
(a)
Similarity of Image T 1 and T 2
(b)

Figure

19. (a) Vehicle driving across a parking lot. (b) Similarity plot of the vehicle.
Autocorrelation of Similarity
TLag
(a)
Power
Spectral Power
power
mean
(b)

Figure

20. (a) Spectral power of the vehicle in Figure 19(a). (b) Autocorrelation of S # of the vehicle in

Figure

19(a) (smoothed with a 5  5 filter). The peaks are denoted by '+' symbols.
simple to distinguish the individuals. For example, Figure 21(a) is a frame from an airborne video
sequence that shows three people running along a road, and the result of the motion segmentation

Figure

21(b)). Simple motion blob counting will give an inaccurate estimate of the number of people.
However, if we know the approximate location of the airplane (via GPS) and have an approximate site
model (a ground plane), we can estimate what the expected image size an "average" person should
be. This size is used to window a region with motion for periodic detection. In this example, three
non-overlapping windows were found to have periodic motion, each corresponding to a person. The
similarity plots and spectral powers are shown in Figure 22.
The similarity plots in Figure 22 can also be used to extract the phase angle of the running person.
The phase angle is encoded in the position of the cross diagonals of S # . In this example, the phase angles
are all significantly different from one another, giving further evidence that we have not over-counted
the number of people.
(a) (b)

Figure

21. (a) Three people running, viewed from a moving camera at an altitude of 1500'. (b)
Segmented motion.
Person 1
Person 2
Person 3
Frequency (Hz)
Power
Frequency (Hz)
Frequency (Hz)

Figure

22. Similarity plots and spectral power for 3 people in Figure 21(a). Note that the frequency
resolution is not as high as in Figure 18, since fewer frames are used to estimate the power.
4.6 Simple Event Detection
In this example, we show how periodicity can be used as input for event detection. Figure 23(a)
shows a person walking through a low contrast area (in a shadow) toward the camera; half way through
the 200 image sequence the person stops swinging his arms and puts them into his pockets. This
action is shown on the similarity plots for the upper and lower portions of the body. Specifically, in

Figure

23(c), a periodic pattern for the upper part of the body is visible for the images [1,100], but
not for [101,200]. This is further shown by the significant peak in the power spectrum for the images

Figure

24(a)) and the lack of significant peaks in the power spectrum for the images [101,200]

Figure

24(b)). Thus, while the image of the person is only 37 pixels high in this sequence and we are
not tracking his body parts, we can deduce that he stopped swinging his arms at about frame 100. An
automated surveillance system can use this technique to help decide if someone is carrying an object.
In [13], we combine periodicity and shape analysis to detect if someone is carrying an object.
4.7 Non-Stationary Periodicity
In this example, a person is walking, and roughly half way through the sequence, starts to run (see

Figure

25(a)). The similarity plot (Figure 25(b)) clearly shows this transition. Using a short-time
analysis windowing Hanning function of length 3300 ms (100 frames), the power is estimated in the
(a)
TSimilarity of Image T 1 and T 2 (Lower 40% of Body)
(b)
TSimilarity of Image T 1 and T 2 (Upper 60% of Body)
(c)

Figure

23. (a) Frame 100 from a low contrast 200 frame sequence; the subject (marked with a white
arrow) puts his hands in his pockets halfway through the sequence. (b) Similarity plot of the lower
40% of the body. (c) Similarity plot of the upper 60% of the body. The periodicity ceases after the
middle of the sequence.
0.20.40.60.8Frequency (Hz)
Power
Spectral Power of Similarity - Upper - Q2
Power Mean
(a)
Power
Spectral Power of Similarity - Upper - Q4
Power
Mean
(b)

Figure

24. (a) Power spectra of the upper left quadrant of Figure 23(c). (b) Power spectra of the lower
right quadrant of Figure 23(c).
walking and running stages (Figure 26).
4.8 Estimating Human Stride Using Periodicity
In [26] and [20], human gait was used for person recognition. In this example, we do not analyze
the gait (which is how people walk or run), but rather estimate the stride length of a walking or running
person. The stride itself can be useful for person recognition, particularly during tracking. For example,
stride length can help object (person) correspondence after occlusions. Stride length can also be used
for input to a surveillance system to detect auto-theft in a parking area (e.g., a person of different size
and stride length drove off with a car than the person who drove in with the car).
Assume the area of surveillance has a site model, and the camera is calibrated. The estimated stride
length is is the ground velocity of the person, and p is the period. For best results, v g
and p should be filtered to reduce the inherent noise in the tracking and period estimation. For example,
in

Figure

25(a), the estimated stride of the person is 22" when walking, and 42" when running, which
is within 2" of the person's actual stride.
(a)
TSimilarity of Image T 1 and T 2
50 100 150 200 250 300100200300
(b)

Figure

25. (a) Person walking, then running. (b) Similarity plot of walking/running sequence.
Frequency (Hz)
Power
Walking
power
mean
Frequency (Hz)
Power
Running
power
mean

Figure

26. Spectral power for walking/running sequence in Figure 25(a).
5 Real-Time System
A real-time system has been implemented to track and classify objects using periodicity. The system
uses a dual Processor 550MHz Pentium III Xeon-based PC, and runs at 15Hz with 640x240 grayscale
images captured from an airborne video camera. The system uses the real-time stabilization results
from [12].
We will briefly discuss how the method can be efficiently implemented to run on a real-time system.
In computing S # , for each new frame, only a single column that corresponds to the new frame needs to
be recomputed; the remaining entries can be reused (shifted) for the updated S # . Therefore, for each
new frame, only O(N) S # (i, computations need to be done, where N is the number of rows and
columns in S # .
For computing A, the 2D FFT can be utilized to greatly decrease the computational cost [18].
Finally, SIMD instructions, such as those available on the Pentium III, can be utilized for computing
as well as A (either directly or using the FFT).
6 Conclusions
We have described new techniques to detect and analyze periodic motion as seen from both a static
and moving camera. By tracking objects of interest, we compute an object's self-similarity as it evolves
in time. For periodic motion, the self-similarity measure is also periodic, and we apply Time-Frequency
analysis to detect and characterize the periodic motion. The periodicity is also analyzed robustly using
the 2-D lattice structures inherent in similarity matrices.
Future work includes using alternative independent motion algorithms for moving camera video,
which could make the analysis more robust for non-homogeneous backgrounds for the case of a moving
camera. Further use of the symmetries of motion for use in classification of additional types of periodic
motion is also being investigated.

Acknowledgments

The airborne video was provided by the DARPA Airborne Video Surveillance project. This paper
was written under the support of contract DAAL-01-97-K-0102 (ARPA Order E653), DAAB07-98-C-
J019, and AASERT Grant DAAH-04-96-1-0221.



--R

Image sequence description using spatiotemporal flow curves: Toward Motion-Based Recog- nition
Color indexing.
Time Series: Theory and Methods.
Recurrence plots revisited.
Dynamic system representation


Recurrence plots of dynamical systems.
The pigeon's discrimination of movement patterns (lissajous figures) and contour-dependent rotational invariance

The interpretation of visual motion: recognizing moving light displays.

Backpack: Detection of people carrying objects using silhouettes.

Comparing images using the hausdorff distance.
Visual motion perception.
Visual position stabilization in the hummingbird hawk moth
Fast normalized cross-correlation
Extracting periodicity of a regular texture based on autocorrelation functions.
Recognizing people by their gate: the shape of motion.
Finding periodicity in space and time.
Classical dynamics of particles and systems.
Recurrence matrices and the preservation of dynamical properties.

Rigidity checking of 3D point correspondences under perspective projection.
Analyzing and recognizing walking figures in xyt.
Analyzing gait with spatiotemporal surfaces.

Spectral Analysis for Physical Applications: Multitaper and Conventional Univariate Techniques
Detection and recognition of periodic
Numerical Recipes in C.
General filtered image rescaling.

Classifying moving objects as rigid or non-rigid without correspondences
Cyclic motion detection for motion based recognition.
Princeton University Press
--TR

--CTR
J. Janta , P. Kumsawat , K. Attakitmongkol , A. Srikaew, A pedestrian detection system using applied log-Gabor, Proceedings of the 7th WSEAS International Conference on Signal, Speech and Image Processing, p.55-60, September 15-17, 2007, Beijing, China
Paul Viola , Michael J. Jones , Daniel Snow, Detecting Pedestrians Using Patterns of Motion and Appearance, International Journal of Computer Vision, v.63 n.2, p.153-161, July      2005
Computational Model for Periodic Pattern Perception Based on Frieze and Wallpaper Groups, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.354-371, March 2004
G. Aliaga, Efficient multi-viewpoint acquisition of 3D objects undergoing repetitive motions, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington
Enrica Dente , Anil Anthony Bharath , Jeffrey Ng , Aldert Vrij , Samantha Mann , Anthony Bull, Tracking hand and finger movements for behaviour analysis, Pattern Recognition Letters, v.27 n.15, p.1797-1808, November, 2006
Enrica Dente , Anil Anthony Bharath , Jeffrey Ng , Aldert Vrij , Samantha Mann , Anthony Bull, Tracking hand and finger movements for behaviour analysis, Pattern Recognition Letters, v.27 n.15, p.1797-1808, November 2006
Tao Zhao , Ram Nevatia, Tracking Multiple Humans in Complex Situations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1208-1221, September 2004
S. Ioffe , D. A. Forsyth, Probabilistic Methods for Finding People, International Journal of Computer Vision, v.43 n.1, p.45-68, June 2001
Yang Ran , Isaac Weiss , Qinfen Zheng , Larry S. Davis, Pedestrian Detection via Periodic Motion Analysis, International Journal of Computer Vision, v.71 n.2, p.143-160, February  2007
D. M. Gavrila , S. Munder, Multi-cue Pedestrian Detection and Tracking from a Moving Vehicle, International Journal of Computer Vision, v.73 n.1, p.41-59, June      2007
Robert Pless, Spatio-temporal background models for outdoor surveillance, EURASIP Journal on Applied Signal Processing, v.2005 n.1, p.2281-2291, 1 January 2005
Guangyu Zhu , Changsheng Xu , Qingming Huang , Wen Gao , Liyuan Xing, Player action recognition in broadcast tennis video with applications to semantic analysis of sports game, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
Josh Wills , Sameer Agarwal , Serge Belongie, A Feature-based Approach for Dense Segmentation and Estimation of Large Disparity Motion, International Journal of Computer Vision, v.68 n.2, p.125-143, June 2006
Zhongfei (Mark) Zhang , Stoyan Kurtev, Independent motion detection directly from compressed surveillance video, First ACM SIGMM international workshop on Video surveillance, November 02-08, 2003, Berkeley, California
Gary R. Bradski , James W. Davis, Motion segmentation and pose recognition with motion history gradients, Machine Vision and Applications, v.13 n.3, p.174-184, July 2002
Chiraz BenAbdelkader , Ross G. Cutler , Larry S. Davis, Gait recognition using image self-similarity, EURASIP Journal on Applied Signal Processing, v.2004 n.1, p.572-585, 1 January 2004
Congxia Dai , Yunfei Zheng , Xin Li, Pedestrian detection and tracking in infrared imagery using shape and appearance, Computer Vision and Image Understanding, v.106 n.2-3, p.288-299, May, 2007
Yingen Xiong , Francis Quek , David McNeill, Hand motion gestural oscillations and multimodal discourse, Proceedings of the 5th international conference on Multimodal interfaces, November 05-07, 2003, Vancouver, British Columbia, Canada
ChunMei Lu , Nicola J. Ferrier, Repetitive Motion Analysis: Segmentation and Event Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.258-263, January 2004
Chung-Lin Huang , Chia-Ying Chung, A real-time model-based human motion tracking and analysis for human computer interface systems, EURASIP Journal on Applied Signal Processing, v.2004 n.1, p.1648-1662, 1 January 2004
Yingen Xiong , Francis Quek, Hand Motion Gesture Frequency Properties and Multimodal Discourse Analysis, International Journal of Computer Vision, v.69 n.3, p.353-371, September 2006
M. Bertozzi , A. Broggi , C. Caraffi , M. Del Rose , M. Felisa , G. Vezzoni, Pedestrian detection by means of far-infrared stereo vision, Computer Vision and Image Understanding, v.106 n.2-3, p.194-204, May, 2007
Berna Erol , Faouzi Kossentini, Retrieval by local motion, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.41-47, January
David A. Forsyth , Okan Arikan , Leslie Ikemoto , James O'Brien , Deva Ramanan, Computational studies of human motion: part 1, tracking and motion synthesis, Foundations and Trends in Computer Graphics and Vision, v.1 n.2, p.77-254, July 2006
motion-based recognition;periodic motion;motion segmention;object classification;person detection;motion symmetries