\documentclass[twoside,11pt]{article}
\newcommand{\LastEditDate}{August 1, 2001}
\newcommand{\LastEditTime}{Wednesday, 1--August--2001 18:52:24 EDT}
\usepackage{times}
\usepackage{jair}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{english}
\usepackage{theapa}

\jairheading{15}{2001}{31-90}{8/00}{8/01}
\ShortHeadings{Grounding the Lexical Semantics of Verbs}{Siskind}
\firstpageno{31}

\newcommand{\Leonard}{{\mbox{\sc Leonard}}}
\newcommand{\Issac}{{\mbox{\sc Issac}}}
\newcommand{\Mecho}{{\mbox{\sc Mecho}}}
\newcommand{\figpercent}[2]{\mbox{\scalebox{\ifnum #1=100 1 \else .#1\fi}
{\includegraphics{siskind2001a/#2}}}}
\newenvironment{lisp}{\begin{tt}\begin{tabular}{l}}{\end{tabular}\end{tt}}
\newcommand{\theset}[1]{{\{#1\}}}
\newcommand{\define}{\stackrel{\triangle}{=}}
\newcommand{\NI}[4]{_{#3}[#1,#2]_{#4}}
\newcommand{\NORM}[1]{\langle#1\rangle}
\newcommand{\E}[2]{{\cal E}(#1,#2)}
\newcommand{\II}[3]{{\cal I}(#1,#2,#3)}
\newcommand{\D}[2]{{\cal D}(#1,#2)}
\newcommand{\Span}[2]{\mbox{\sc Span}(#1,#2)}
\newcommand{\I}{\mbox{\bf i}}
\newcommand{\J}{\mbox{\bf j}}
\newcommand{\K}{\mbox{\bf k}}
\newcommand{\sI}{\mbox{\scriptsize\bf i}}
\newcommand{\sJ}{\mbox{\scriptsize\bf j}}
\newcommand{\sK}{\mbox{\scriptsize\bf k}}
\newcommand{\TRUE}{\mbox{\tiny\bf T}}
\newcommand{\FALSE}{\mbox{\tiny\bf F}}
\newcommand{\STABLEF}{\mbox{\sc Stable}}
\newcommand{\STABLE}[2]{\STABLEF(#1,#2)}
\newcommand{\TOUCHES}[2]{\mbox{\sc Touches}(#1,#2)}
\newcommand{\GROUNDEDF}{\mbox{\sc Grounded}}
\newcommand{\RIGIDF}{\mbox{\sc Rigid}}
\newcommand{\REVOLUTEF}{\mbox{\sc Revolute}}
\newcommand{\SAMELAYERF}{\mbox{\sc SameLayer}}
\newcommand{\GROUNDED}[1]{\GROUNDEDF(#1)}
\newcommand{\RIGID}[3]{\RIGIDF(#1,#2,#3)}
\newcommand{\REVOLUTE}[3]{\REVOLUTEF(#1,#2,#3)}
\newcommand{\SAMELAYER}[2]{\SAMELAYERF(#1,#2)}
\newcommand{\SUPPORTED}[1]{\mbox{\sc Supported}(#1)}
\newcommand{\SUPPORTS}[2]{\mbox{\sc Supports}(#1,#2)}
\newcommand{\CONTACTS}[2]{\mbox{\sc Contacts}(#1,#2)}
\newcommand{\ATTACHED}[2]{\mbox{\sc Attached}(#1,#2)}
\newcommand{\RIGIDLYATTACHEDF}{\mbox{\sc RigAtt}}
\newcommand{\RIGIDLYATTACHED}[2]{\RIGIDLYATTACHEDF(#1,#2)}
\newcommand{\RIGIDLYATTACHEDSTAR}[2]{\RIGIDLYATTACHEDF^{*}(#1,#2)}
\newcommand{\PICKUP}[3]{\mbox{\sc PickUp}(#1,#2,#3)}
\newcommand{\PUTDOWN}[3]{\mbox{\sc PutDown}(#1,#2,#3)}
\newcommand{\STACK}[4]{\mbox{\sc Stack}(#1,#2,#3,#4)}
\newcommand{\UNSTACK}[4]{\mbox{\sc Unstack}(#1,#2,#3,#4)}
\newcommand{\MOVE}[4]{\mbox{\sc Move}(#1,#2,#3,#4)}
\newcommand{\ASSEMBLE}[4]{\mbox{\sc Assemble}(#1,#2,#3,#4)}
\newcommand{\DISASSEMBLE}[4]{\mbox{\sc Disassemble}(#1,#2,#3,#4)}
\newcommand{\REDBLOCK}{\mbox{\bf red-block}}
\newcommand{\GREENBLOCK}{\mbox{\bf green-block}}
\newcommand{\BLUEBLOCK}{\mbox{\bf blue-block}}
\newcommand{\YELLOWBLOCK}{\mbox{\bf yellow-block}}
\newcommand{\HAND}{\mbox{\bf hand}}
\newcommand{\AlleniF}{\mbox{\small\sf i}}
\newcommand{\AllenmF}{\mbox{\small\sf m}}
\newcommand{\AllenmiF}{\mbox{\small\sf mi}}
\newcommand{\AllenoF}{\mbox{\small\sf o}}
\newcommand{\AllenoiF}{\mbox{\small\sf oi}}
\newcommand{\AllensF}{\mbox{\small\sf s}}
\newcommand{\AllensiF}{\mbox{\small\sf si}}
\newcommand{\AllenfF}{\mbox{\small\sf f}}
\newcommand{\AllenfiF}{\mbox{\small\sf fi}}
\newcommand{\AllendF}{\mbox{\small\sf d}}
\newcommand{\AllendiF}{\mbox{\small\sf di}}
\newcommand{\Allenm}[2]{#1\;\AllenmF\;#2}
\newcommand{\Allenmi}[2]{#1\;\AllenmiF\;#2}
\newcommand{\Alleno}[2]{#1\;\AllenoF\;#2}
\newcommand{\Allenoi}[2]{#1\;\AllenoiF\;#2}
\newcommand{\Allens}[2]{#1\;\AllensF\;#2}
\newcommand{\Allensi}[2]{#1\;\AllensiF\;#2}
\newcommand{\Allenf}[2]{#1\;\AllenfF\;#2}
\newcommand{\Allenfi}[2]{#1\;\AllenfiF\;#2}
\newcommand{\Allend}[2]{#1\;\AllendF\;#2}
\newcommand{\Allendi}[2]{#1\;\AllendiF\;#2}
\newcommand{\Allennotm}[2]{#1\;\mbox{\AllenmF\hspace{-0.6em}$/$}\;#2}
\newcommand{\Allennotmi}[2]{#1\;\mbox{\AllenmiF\hspace{-0.5em}$/$}\;#2}
\newcommand{\Allennoto}[2]{#1\;\mbox{\AllenoF\hspace{-0.5em}$/$}\;#2}
\newcommand{\Allennotoi}[2]{#1\;\mbox{\AllenoiF\hspace{-0.5em}$/$}\;#2}
\newcommand{\Allennots}[2]{#1\;\mbox{\AllensF\hspace{-0.4em}$/$}\;#2}
\newcommand{\Allennotsi}[2]{#1\;\mbox{\AllensiF\hspace{-0.5em}$/$}\;#2}
\newcommand{\Allennotf}[2]{#1\;\mbox{\AllenfF\hspace{-0.4em}$/$}\;#2}
\newcommand{\Allennotfi}[2]{#1\;\mbox{\AllenfiF\hspace{-0.5em}$/$}\;#2}
\newcommand{\Allennotd}[2]{#1\;\mbox{\AllendF\hspace{-0.5em}$/$}\;#2}
\newcommand{\Allennotdi}[2]{#1\;\mbox{\AllendiF\hspace{-0.5em}$/$}\;#2}
\newcommand{\sAllenmF}{\mbox{\scriptsize\sf m}}
\newcommand{\sAllenmiF}{\mbox{\scriptsize\sf mi}}
\newcommand{\sAllenoF}{\mbox{\scriptsize\sf o}}
\newcommand{\sAllenoiF}{\mbox{\scriptsize\sf oi}}
\newcommand{\sAllensF}{\mbox{\scriptsize\sf s}}
\newcommand{\sAllensiF}{\mbox{\scriptsize\sf si}}
\newcommand{\sAllenfF}{\mbox{\scriptsize\sf f}}
\newcommand{\sAllenfiF}{\mbox{\scriptsize\sf fi}}
\newcommand{\sAllendF}{\mbox{\scriptsize\sf d}}
\newcommand{\sAllendiF}{\mbox{\scriptsize\sf di}}

\begin{document}

\title{Grounding the Lexical Semantics of Verbs in Visual Perception using
Force Dynamics and Event Logic}

\author{\name Jeffrey Mark Siskind \email qobi@research.nj.nec.com\\
\addr NEC Research Institute, Inc.\\
4 Independence Way\\
Princeton, NJ 08540 USA}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle

\begin{abstract}
This paper presents an implemented system for recognizing the
occurrence of events described by simple spatial-motion verbs in short image
sequences.
The semantics of these verbs is specified with event-logic expressions
that describe changes in the state of force-dynamic relations between the
participants of the event.
An efficient finite representation is introduced for the infinite sets of
intervals that occur when describing liquid and semi-liquid events.
Additionally, an efficient procedure using this representation is presented for
inferring occurrences of compound events, described with event-logic
expressions, from occurrences of primitive events.
Using force dynamics and event logic to specify the lexical semantics of
events allows the system to be more robust than prior systems based on
motion profile.
\end{abstract}

\section{Introduction}

If one were to look at the image sequence in Figure~\ref{videoOne}(a),
one could describe the event depicted in that sequence by saying
{\em Someone picked the red block up off the green block}.
Similarly, if one were to look at the image sequence in
Figure~\ref{videoOne}(b), one could describe the event depicted in that
sequence by saying {\em Someone put the red block down on the green block}.
One way that one recognizes that the former is a
{\em pick up}\footnote{Throughout this paper, I treat verb-particle
constructions, like {\em pick up}, as atomic verbs, despite the fact that the
verb and its associated particle may be discontinuous.
Methods for deriving the semantics of a verb-particle construction
compositionally from its (discontinuous) constituents are beyond the scope of
this paper.}
event is that one notices a state change in the force-dynamic relations
between the participant objects.
Prior to Frame~13, the red block is supported by the green block by a
substantiality constraint, the fact that solid objects cannot interpenetrate
\cite{Spelke83,BaillargeonSW85,Baillargeon86,Baillargeon87,Spelke87,Spelke88}.
From Frame~13 onward, it is supported by being attached to the hand.
Similarly, one way that one recognizes that the latter is a {\em put down\/}
event is that one notices the reverse state change in Frame~14.
This paper describes an implemented computer system, called \Leonard, that can
produce similar event descriptions from such image sequences.
A novel aspect of this system is that it produces event descriptions by
recognizing state changes in force-dynamic relations between participant
objects.
{\sl Force dynamics} is a term introduced by \citeA{Talmy88} to describe a
variety of causal relations between participants in an event, such as
allowing, preventing, and forcing.
In this paper, I use force dynamics in a slightly different sense, namely, to
describe the {\sl support}, {\sl contact}, and {\sl attachment} relations
between participant objects.

\begin{figure}
\begin{center}
\begin{tabular}{rccc}
\raisebox{32pt}{(a)}&
\figpercent{30}{pick-up00-0-image}&
\figpercent{30}{pick-up00-1-image}&
\figpercent{30}{pick-up00-2-image}\\
&
Frame 0&
Frame 1&
Frame 2\\
&
\figpercent{30}{pick-up00-13-image}&
\figpercent{30}{pick-up00-14-image}&
\figpercent{30}{pick-up00-20-image}\\
&
Frame 13&
Frame 14&
Frame 20\\\hline\\[-5pt]
\raisebox{32pt}{(b)}&
\figpercent{30}{put-down00-1-image}&
\figpercent{30}{put-down00-13-image}&
\figpercent{30}{put-down00-14-image}\\
&
Frame 1&
Frame 13&
Frame 14\\
&
\figpercent{30}{put-down00-22-image}&
\figpercent{30}{put-down00-23-image}&
\figpercent{30}{put-down00-27-image}\\
&
Frame 22&
Frame 23&
Frame 27
\end{tabular}
\end{center}
\caption{Image sequences depicting (a)~a {\em pick up\/} event and (b)~a
{\em put down\/} event.}
\label{videoOne}
\end{figure}

A number of systems have been reported that can produce event descriptions
from video input.
Examples of such systems include the work reported in \citeA{YamotoOI92},
\citeA{Starner95}, \citeA{SiskindM96}, \citeA{Brand96}, and \citeA{BobickI98}.
\Leonard\ differs from these prior systems in two crucial ways.
First, the prior systems classify events based on the motion profile of the
participant objects.
For example, \citeA{SiskindM96} characterize a {\em pick up\/} event as a
sequence of two subevents: the agent moving towards the patient while the
patient is at rest above the source, followed by the agent moving with the
patient away from the source while the source remains at rest.
Similarly, a {\em put down\/} event is characterized as the agent moving with
the patient towards the destination while the destination is at rest, followed
by the agent moving away from the patient while the patient is at rest above
the destination.
In contrast, \Leonard\ characterizes events as changes in the force-dynamic
relations between the participant objects.
For example, a {\em pick up\/} event is characterized as a change from
a state where the patient is supported by a substantiality constraint with the
source to a state where the patient is supported by being attached to the
agent.
Similarly, a {\em put down\/} event is characterized as the reverse state
change.
Irrespective of whether motion profile or force dynamics is used to recognize
events, event recognition is a process of classifying time-series data.
In the case of motion profile, this time-series data takes the form of
relative-and-absolute positions, velocities, and accelerations of the
participant objects as a function of time.
In the case of force dynamics, this time-series data takes the form of the
truth values of force-dynamic relations between the participant objects as a
function of time.
This leads to the second difference between \Leonard\ and prior systems.
The prior systems use stochastic reasoning, in the form of hidden
Markov models, to classify the time-series data into event types.
In contrast, \Leonard\ uses logical reasoning, in the form of
{\sl event logic}, to do this classification.

Using force dynamics and event logic (henceforth the `new approach') to
recognize events offers several advantages over using motion profile and
hidden Markov models (henceforth the `prior approach').
First, the new approach will correctly recognize an event despite a wider
variance in motion profile than the prior approach.
For example, when recognizing, say, a {\em pick up\/} event, the prior approach
is sensitive to aspects of event execution, like the approach angle and
velocity of the hand, that are irrelevant to whether or not the event is
actually a {\em pick up}.
The new approach is not sensitive to such aspects of event execution.
Second, the new approach will correctly recognize an event despite the
presence of unrelated objects in the field of view.
The prior approach computes the relative-and-absolute positions and motions of
all objects and pairs of objects in the field of view.
It then selects the subset of objects whose positions and motions best
matched some model.
This could produce incorrect descriptions when some unintended subset matched
some unintended model better than the intended subset matched the intended
model.
The new approach does not exhibit such deficiencies.
Extraneous objects typically do not exhibit the precise sequence of state
changes in force-dynamic relations needed to trigger the event-classification
process and thus will not generate spurious claims of event occurrences.
Third, the new approach performs temporal and spatial segmentation of events.
The prior approach matches an entire image sequence against an event model.
It fails if that image sequence depicts multiple event executions, either in
sequence or in parallel.
In contrast, the new approach can segment a complex image sequence into a
collection of sequential and/or overlapping events.
In particular, it can handle {\sl hierarchal} events, such as {\em move}, that
consist of a {\em pick up\/} event followed by a {\em put down\/} event.
It can recognize that all three events, and precisely those three events,
occur in an appropriate image sequence whereas the prior approach would try to
find the single best match.
Finally, the new approach robustly detects the non-occurrence of events as well
as the occurrence of events.
The prior approach always selects the best match and reports some event
occurrence for every image sequence.
Thresholding the match cost does not work because an approach based on motion
profile can be fooled into triggering recognition of an event occurrence by an
event whose motion profile is similar to one or more target event classes even
though that event is not actually in any of those target event classes.
Consider, for example, the two image sequences in Figure~\ref{videoTwo}.
Suppose that an event-recognition system contained two target event
classes, namely {\em pick up\/} and {\em put down}.
Neither of the image sequences depict {\em pick up\/} or
{\em put down\/} events.
Nonetheless, the prior approach might mistakingly classify
Figure~\ref{videoTwo}(a) as a {\em pick up\/} event because the second half of
this image sequence matches the second half of the motion profile of a
{\em pick up\/} event.
Alternatively, it might mistakingly classify this image sequence as a
{\em put down\/} event because the first half of this image sequence matches
the first half of the motion profile of a {\em put down\/} event.
Similarly, the prior approach might mistakingly classify
Figure~\ref{videoTwo}(b) as a {\em pick up\/} event because the first half of
this image sequence matches the first half of the motion profile of a
{\em pick up\/} event.
Alternatively, it might mistakingly classify this image sequence as a
{\em put down\/} event because the second half of this image sequence matches
the second half of the motion profile of a {\em put down\/} event.
In contrast, the new approach correctly recognizes that neither of these image
sequences exhibit the necessary state changes in force-dynamic relations to
qualify as either {\em pick up\/} or {\em put down\/} events.
All four of these advantages will be discussed in greater detail in
Section~\ref{experimentalResults}.

\begin{figure}
\begin{center}
\begin{tabular}{rccc}
\raisebox{32pt}{(a)}&
\figpercent{30}{none01-4-image}&
\figpercent{30}{none01-11-image}&
\figpercent{30}{none01-12-image}\\
&
Frame 4&
Frame 11&
Frame 12\\
&
\figpercent{30}{none01-18-image}&
\figpercent{30}{none01-19-image}&
\figpercent{30}{none01-21-image}\\
&
Frame 18&
Frame 19&
Frame 21\\\hline\\[-5pt]
\raisebox{32pt}{(b)}&
\figpercent{30}{none00-0-image}&
\figpercent{30}{none00-6-image}&
\figpercent{30}{none00-7-image}\\
&
Frame 0&
Frame 6&
Frame 7\\
&
\figpercent{30}{none00-12-image}&
\figpercent{30}{none00-13-image}&
\figpercent{30}{none00-18-image}\\
&
Frame 12&
Frame 13&
Frame 18
\end{tabular}
\end{center}
\caption{Image sequences depicting non-events.}
\label{videoTwo}
\end{figure}

The techniques described in this paper have been implemented in a system
called \Leonard.
\Leonard\ is a comprehensive system that takes image sequences as input and
produces event descriptions as output.
The overall architecture of \Leonard\ is shown in Figure~\ref{blockDiagramOne}.
The input to \Leonard\ consists of a sequence of images taken by a Canon VC-C3
camera and Matrox Meteor frame grabber at 320$\times$240 resolution at 30fps.
This image sequence is first processed by a {\sl segmentation-and-tracking}
component.
A real-time colour- and motion-based segmentation algorithm places a convex
polygon around each coloured and moving object in each frame.
A tracking algorithm then forms a correspondence between the polygons in each
frame and those in temporally adjacent frames.
The output of the segmentation-and-tracking component consists of a sequence
of {\sl scenes}, each scene being a set of polygons.
Each polygon is represented as a sequence of image coordinates corresponding
to a clockwise traversal of the polygon's vertices.
The tracker guarantees that each scene contains the same number of polygons
and that they are ordered so that the $i^{\rm th}$ polygon in each scene
corresponds to the same object.
Figure~\ref{segmentationAndTrackingOne} shows the output of the
segmentation-and-tracking component on the image sequences from
Figure~\ref{videoOne}.
The polygons have been overlayed on the input images for ease of comprehension.

\begin{figure}
\begin{center}
\begin{tabular}{rccc}
\raisebox{32pt}{(a)}&
\figpercent{30}{pick-up00-0-image-and-polygons}&
\figpercent{30}{pick-up00-1-image-and-polygons}&
\figpercent{30}{pick-up00-2-image-and-polygons}\\
&
Frame 0&
Frame 1&
Frame 2\\
&
\figpercent{30}{pick-up00-13-image-and-polygons}&
\figpercent{30}{pick-up00-14-image-and-polygons}&
\figpercent{30}{pick-up00-20-image-and-polygons}\\
&
Frame 13&
Frame 14&
Frame 20\\\hline\\[-5pt]
\raisebox{32pt}{(b)}&
\figpercent{30}{put-down00-1-image-and-polygons}&
\figpercent{30}{put-down00-13-image-and-polygons}&
\figpercent{30}{put-down00-14-image-and-polygons}\\
&
Frame 1&
Frame 13&
Frame 14\\
&
\figpercent{30}{put-down00-22-image-and-polygons}&
\figpercent{30}{put-down00-23-image-and-polygons}&
\figpercent{30}{put-down00-27-image-and-polygons}\\
&
Frame 22&
Frame 23&
Frame 27
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking component applied to the
image sequences from Figure~\protect\ref{videoOne}.
(a)~depicts a {\em pick up\/} event.
(b)~depicts a {\em put down\/} event.
The polygons have been overlayed on the input images for ease of
comprehension.}
\label{segmentationAndTrackingOne}
\end{figure}

This scene sequence is passed to a {\sl model-reconstruction} component.
This component produces a force-dynamic model of each scene.
This model specifies three types of information: which objects are
{\sl grounded}, i.e.~are supported by an unseen mechanism that is not
associated with any visible object, which objects are {\sl attached} to other
objects by rigid or revolute joints, and the qualitative depth of each object,
i.e.~a qualitative representation of the relative distance of different
objects in the field of view from the observer, in the form of a
{\sl same layer} relation specifying which objects are at the same qualitative
depth.
Figure~\ref{modelReconstructionOne} shows the output of the
model-reconstruction component on the scene sequences from
Figure~\ref{segmentationAndTrackingOne}.
The models are depicted graphically, overlayed on the input images, for ease
of comprehension.
The details of this depiction scheme will be described momentarily.
For now, it suffices to point out that Figure~\ref{modelReconstructionOne}(a)
shows the red block on the same layer as the green block up through Frame~1
and attached to the hand from Frame~14 onward.
Figure~\ref{modelReconstructionOne}(b) shows the reverse sequence of
relations, with the red block attached to the hand up through Frame~13
and on the same layer as the green block from Frame~23 onward.

\begin{figure}
\begin{center}
\begin{tabular}{rccc}
\raisebox{32pt}{(a)}&
\figpercent{30}{pick-up00-0-image-and-most-preferred-model}&
\figpercent{30}{pick-up00-1-image-and-most-preferred-model}&
\figpercent{30}{pick-up00-2-image-and-most-preferred-model}\\
&
Frame 0&
Frame 1&
Frame 2\\
&
\figpercent{30}{pick-up00-13-image-and-most-preferred-model}&
\figpercent{30}{pick-up00-14-image-and-most-preferred-model}&
\figpercent{30}{pick-up00-20-image-and-most-preferred-model}\\
&
Frame 13&
Frame 14&
Frame 20\\\hline\\[-5pt]
\raisebox{32pt}{(b)}&
\figpercent{30}{put-down00-1-image-and-most-preferred-model}&
\figpercent{30}{put-down00-13-image-and-most-preferred-model}&
\figpercent{30}{put-down00-14-image-and-most-preferred-model}\\
&
Frame 1&
Frame 13&
Frame 14\\
&
\figpercent{30}{put-down00-22-image-and-most-preferred-model}&
\figpercent{30}{put-down00-23-image-and-most-preferred-model}&
\figpercent{30}{put-down00-27-image-and-most-preferred-model}\\
&
Frame 22&
Frame 23&
Frame 27
\end{tabular}
\end{center}
\caption{The output of the model-reconstruction component applied to the
scene sequences from Figure~\protect\ref{segmentationAndTrackingOne}.
(a)~depicts a {\em pick up\/} event.
(b)~depicts a {\em put down\/} event.
The models have been overlayed on the input images for ease of comprehension.
In~(a), the red block is on the same layer as the green block up through
Frame~1 and is attached to the hand from Frame~14 onward.
In~(b), the reverse sequence of relations holds, with the red block attached
to the hand up through Frame~13 and on the same layer as the green block from
Frame~23 onward.}
\label{modelReconstructionOne}
\end{figure}

This model sequence is passed to an {\sl event-classification} component.
This component first determines the intervals over which certain primitive
event types are true.
These primitive event types include $\SUPPORTED{x}$, $\SUPPORTS{x}{y}$,
$\CONTACTS{x}{y}$, and $\ATTACHED{x}{y}$.
This component then uses an inference procedure to determine the intervals
over which certain compound event types are true.
These compound event types include $\PICKUP{x}{y}{z}$, $\PUTDOWN{x}{y}{z}$,
$\STACK{w}{x}{y}{z}$, $\UNSTACK{w}{x}{y}{z}$, $\MOVE{w}{x}{y}{z}$,
$\ASSEMBLE{w}{x}{y}{z}$, and\\%
$\DISASSEMBLE{w}{x}{y}{z}$ and are specified as
expressions in event logic over the primitive event types.
The output of the event-classification component consists of an indication of
which compound event types occurred in the input movie as well as the
subsequence(s) of frames during which those event types occurred.
Figure~\ref{eventClassificationOne} shows the output of the
event-classification component on the model sequences from
Figure~\ref{modelReconstructionOne}.
The subsequences of frames during which the events occurred are depicted as
{\sl spanning intervals}.
Spanning intervals will be described in Section~\ref{spanningIntervals}.

\begin{figure}
\begin{center}
\begin{tabular}{c}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[0,1],[14,22])\symbol{125}\\
\ \\
(SUPPORTED?\ RED)@\symbol{123}[[0:22])\symbol{125}\\
(SUPPORTED?\ MOVING)@\symbol{123}[[1:13]), [[24:26])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[1:13]), [[24:26])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[13:22])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:14])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[1:13])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:2]), [[6:14])\symbol{125}\\
(ATTACHED?\ RED MOVING)@\symbol{123}[[1:26])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[1:6])\symbol{125}\\
\end{lisp}}\\
(a)\\*[2ex]
\fbox{\begin{lisp}
(PUT-DOWN MOVING RED GREEN)@\symbol{123}[[0,14],[23,32])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[14:23])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:32])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[0:14])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[14:23])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[14:23])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[14:32])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[22:32])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[0:23])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[14:22])\symbol{125}\\
\end{lisp}}\\
(b)
\end{tabular}
\end{center}
\caption{The output of the event-classification component applied to the
model sequences from Figure~\protect\ref{modelReconstructionOne}.
Note that the {\em pick up\/} event is correctly recognized in~(a) and the
{\em put down\/} event is correctly recognized in~(b).}
\label{eventClassificationOne}
\end{figure}

\Leonard\ is too complex to describe completely in one paper.
This paper provides a detailed description of the event-classification
component and, in particular, the event-logic inference procedure.
The segmentation and tracking algorithms are extensions of the algorithms
presented in \citeA{SiskindM96} and \citeA{Siskind1999}, modified to place
convex polygons around the participant objects instead of ellipses.
The model-reconstruction techniques are extensions of those presented in
\citeA{Siskind97,Siskind2000}.
The model-reconstruction techniques will be described briefly below to allow
the reader to understand the event-classification techniques without reference
to those papers.

\begin{figure}
\begin{center}
\figpercent{50}{f107}
\end{center}
\caption{The overall architecture of \Leonard.}
\label{blockDiagramOne}
\end{figure}

\section{Model Reconstruction}
\label{modelReconstruction}

Certain properties of objects are visible.
For example, position, orientation, shape, size, colour, texture, and so forth.
Furthermore, relational variants of these properties are also visible,
as well as changes in such properties and relations over time.
In contrast, force-dynamic properties and relations are not visible.
One cannot {\em see\/} the fact that the door knob is attached to, and
supported by, the door.
One must {\em infer\/} that fact using physical knowledge of the world.
Such knowledge includes the fact that unsupported objects fall and attachment
is one way of offering support.
Using physical knowledge to infer force-dynamic properties and relations was
first discussed by \citeA{Siskind91b,Siskind92,Siskind93b}.
This later became known as the {\sl perceiver framework} advanced by
\citeA{JepsonR93}.
The perceiver framework states that perception involves four levels.
First, one must specify the {\sl observables}, what properties and relations
can be discerned by direct observation.
Second, one must specify an {\sl ontology}, what properties and relations must
be inferred from the observables.
Descriptions of the observables in terms of such properties and relations are
called {\sl interpretations}.
There may be multiple interpretations of a given observation.
Third, one must specify a {\sl theory}, a way of differentiating
{\sl consistent} interpretations from {\sl inconsistent} ones.
The consistent interpretations are the {\sl models} of the observation.
There may be multiple models of a given observation.
Finally, one must specify a {\sl preference relation}, a way of ordering the
models.
The most-preferred models of the observations are the {\sl percepts}.
One can instantiate the perceiver framework for different observables,
ontologies, theories, and preference relations.
\citeA{Siskind91b,Siskind92,Siskind93b,Siskind94b,Siskind95,Siskind97}
instantiated this framework for a kinematic theory applied to simulated video.
\citeA{MannJS96,MannJS97} and \citeA{MannJ98} instantiated this framework for
a dynamics theory applied to real video.
\citeA{Siskind2000} instantiated this framework for a kinematic theory applied
to real video.
This paper uses this later approach.

The input to the model-reconstruction process consists of a sequence of
{\sl scenes}, each scene being a set of convex polygons.
Each polygon is represented as a sequence of points corresponding to a
clockwise traversal of the polygon's vertices.
The tracker guarantees that each scene contains the same number of polygons
and that they are ordered so that the $i^{\rm th}$ polygon in each scene
corresponds to the same object.
The output of the model-reconstruction process consists of a sequence of
{\sl interpretations}, one interpretation per scene.
The interpretations are formulated out of the following primitive properties
of, and relations between, the objects in each scene.
\begin{description}
\item[$\GROUNDED{p}$]Polygon~$p$ is {\sl grounded}.
It is constrained to occupy a fixed position and orientation by an unseen
mechanism that is not associated with any visible object and thus cannot move
either translationally or rotationally.
\item[$\RIGID{p}{q}{r}$]Polygons~$p$ and~$q$ are {\sl attached} by a
{\sl rigid joint} at point~$r$.
Both the relative position and orientation of~$p$ and~$q$ are constrained.
\item[$\REVOLUTE{p}{q}{r}$]Polygons~$p$ and~$q$ are {\sl attached} by a
{\sl revolute joint} at point~$r$.
The relative position of~$p$ and~$q$ is constrained but the relative
orientation is not.
\item[$\SAMELAYER{p}{q}$]Polygons~$p$ and~$q$ are on the {\sl same layer}.
Layers are a qualitative representation of depth, or distance from the
observer.
This representation is impoverished.
There is no notion of `in-front-of' or `behind' and there is no notion of
adjacency in depth.
The only representable notion is whether two objects are on the same or
different layers.
The same-layer relation is constrained to be an equivalence relation, i.e.~it
must be reflexive, symmetric, and transitive.
Furthermore, two objects on the same layer must obey the
{\sl substantiality constraint}, the constraint that they not interpenetrate
\cite{Spelke83,BaillargeonSW85,Baillargeon86,Baillargeon87,Spelke87,Spelke88}.
\end{description}

An interpretation~$I$ is a $4$-tuple:
$\langle\GROUNDEDF,\RIGIDF,\REVOLUTEF,\SAMELAYERF\rangle$.
Throughout this paper, interpretations will be depicted graphically, overlayed
on scene images, for ease of comprehension.
Figure~\ref{visualInterpretations} gives a sample interpretation depicted
graphically.
The symbol `\figpercent{15}{f110}' attached to a polygon indicates that it is
grounded.
A solid circle indicates that two polygons are rigidly attached at the center
of the circle.
A hollow circle indicates that two polygons are attached by a revolute joint
at the center of the circle.
The same-layer relation is indicated by giving a {\sl layer index}, a
small nonnegative integer, to each polygon.
Polygons with the same layer index are on the same layer, while those with
different layer indices are on different layers.

\begin{figure}
\begin{center}
\figpercent{50}{f111}
\end{center}
\caption{The graphical method for depicting interpretations that is used in
this paper.
The symbol `\protect\figpercent{15}{f110}' indicates that a polygon is
grounded.
A solid circle indicates a rigid joint.
A hollow circle indicates a revolute joint.
Two polygons with the same layer index are on the same layer.}
\label{visualInterpretations}
\end{figure}

Model reconstruction can be viewed as a generate-and-test process.
Initially, all possible interpretations are generated for each scene.
Then, {\sl inadmissible} and {\sl unstable} interpretations are filtered out.
Admissibility and stability can be collectively viewed as a consistency
requirement.
The stable admissible interpretations are thus {\sl models} of a scene.
The nature of the theory guarantees that there will always be at least one
model for each scene, namely the model where all objects are grounded.
There may, however, be multiple models for a given scene.
Therefore, a {\sl preference relation} is then applied through a sequence of
circumscription processes \cite{McCarthy80} to select the minimal, or
preferred, models for each scene.
While there will always be at least one minimal model for each scene, there
may be several, since the preference relation may not induce a total order.
If there are multiple minimal models for a given scene, one is chosen
arbitrarily as the most-preferred model for that scene.
The precise details of the admissibility criteria, the stability checking
algorithm, the preference relations, and the circumscription process are
beyond the scope of this paper.
They are discussed in \citeA{Siskind2000}.
What is important, for the purpose of this paper, is that, given a scene
sequence, model reconstruction produces a sequence of interpretations, one for
each scene, and that these interpretations are $4$-tuples containing the
predicates $\GROUNDEDF$, $\RIGIDF$, $\REVOLUTEF$, and~$\SAMELAYERF$.
Figure~\ref{modelReconstructionOne} shows sample interpretation sequences
produced by the model-reconstruction component on the scene sequences from
Figure~\ref{segmentationAndTrackingOne}.

\section{Event Logic}
\label{eventLogic}

Model reconstruction determines the truth values of the force-dynamic relations
on a frame-by-frame basis in the input movie.
Intervals of constant truth value for a given force-dynamic relation are taken
to be primitive event occurrences.
\Leonard\ uses {\sl event logic} to infer compound event occurrences from
primitive event occurrences.
For example, for the image sequence in Figure~\ref{videoOne}(a), model
reconstruction determines that the green block supports the red block from
Frame~0 to Frame~13 and that the hand is attached to the red block from
Frame~13 to Frame~20.
This will be denoted as $\SUPPORTS{\GREENBLOCK}{\REDBLOCK}@[0,13)$ and\\%
$\ATTACHED{\HAND}{\REDBLOCK}@[13,20)$, i.e.~that the primitive event types\\%
$\SUPPORTS{\GREENBLOCK}{\REDBLOCK}$ and $\ATTACHED{\HAND}{\REDBLOCK}$ occurred
during the intervals $[0,13)$ and $[13,20)$ respectively.
The compound event type\\%
$\PICKUP{\HAND}{\REDBLOCK}{\GREENBLOCK}$ might be defined as
\begin{displaymath}
\SUPPORTS{\GREENBLOCK}{\REDBLOCK};\ATTACHED{\HAND}{\REDBLOCK}
\end{displaymath}
i.e.~$\SUPPORTS{\GREENBLOCK}{\REDBLOCK}$ followed by
$\ATTACHED{\HAND}{\REDBLOCK}$.
(In the above, I use `;' informally as a sequence operator.
The precise definition of `;' will be given momentarily.)
The task of the event-logic inference procedure is to infer\\%
$\PICKUP{\HAND}{\REDBLOCK}{\GREENBLOCK}@[0,20)$, i.e.~that the compound event
type\\%
$\PICKUP{\HAND}{\REDBLOCK}{\GREENBLOCK}$ occurred during the interval
$[0,20)$.

Event logic provides a calculus for forming compound event types as
expressions over primitive event types.
The syntax and semantics of event logic will be described momentarily.
Event-logic expressions denote event types, not event occurrences.
As such, they do not have truth values.
Rather, they are predicates that describe the truth conditions that must hold
of an interval for an event to occur.
In contrast, an event-occurrence formula does have a truth value.
If~$\Phi$ is an event-logic expression that denotes a primitive or compound
event type, and~$\I$ is an interval, then $\Phi@\I$ is an atomic
event-occurrence formula that is true if and only if the truth conditions for
the event type~$\Phi$ hold of the interval~$\I$.

$\Phi@\I$ denotes {\sl coincidental} occurrence, the fact that an occurrence
of~$\Phi$ started at the beginning of~$\I$ and finished at the end of~$\I$.
$\Phi@\I$ would not hold if an occurrence of~$\Phi$ did not precisely coincide
with~$\I$, but instead overlapped,\footnote{I am using the term `overlap' here
in a different sense than the $\sAllenoF$ relation from \citeA{Allen83}.
Here, I am using the term overlap in the sense that two intervals overlap if
they have a nonempty intersection.
This corresponds to the union of the $\sAllenoF$, $\sAllenoiF$, $\sAllensF$,
$\sAllensiF$, $\sAllenfF$, $\sAllenfiF$, $\sAllendF$, and $\sAllendiF$
relations from \citeA{Allen83}.}
partially or totally, with~$\I$.
Event types have internal temporal structure that render this distinction
important.
In the case of primitive event types, that structure is simple.
Each primitive event type is derived from a predicate.
If~$\phi$ is a predicate, then~$\overline{\phi}$ denotes the primitive event
type derived from~$\phi$.
A primitive event type~$\overline{\phi}$ holds of an interval if the
corresponding predicate~$\phi$ holds of every instant in that
interval.\footnote{To deal with noise, in the actual implementation, the
primitive event type~$\overline{\phi}$ is derived from the predicate~$\phi$ by
first passing~$\phi$ through a low-pass filter that takes~$\phi(t)$ to be the
majority vote of a five-frame window centered on~$t$.}
This means that $\neg(\overline{\phi}@\I)$ and $\overline{\neg\phi}@\I$ might
have different truth values.
For example, if~$\phi$ is true of every instant in $[0,2)$ and false of every
other instant, then $\neg(\overline{\phi}@[1,3))$ is true while
$\overline{\neg\phi}@[1,3)$ is false.
Event logic takes coincidental occurrence to be a primitive notion.
As will be demonstrated below, overlapping occurrence is a derived notion that
can be expressed in terms of coincidental occurrence using compound
event-logic expressions.

Two auxiliary notions are needed to define the syntax and semantics of event
logic.
First, there are thirteen possible relations between two intervals.
Following \citeA{Allen83}, I denote these relations as~$=$, $<$, $>$,
$\AllenmF$, $\AllenmiF$, $\AllenoF$, $\AllenoiF$, $\AllensF$, $\AllensiF$,
$\AllenfF$, $\AllenfiF$, $\AllendF$, and $\AllendiF$ and refer to them
collectively as {\sl Allen relations} throughout the paper.
The names $\AllenmF$, $\AllenoF$, $\AllensF$, $\AllenfF$, and $\AllendF$ are
mnemonics for {\em meet}, {\em overlap}, {\em start}, {\em finish}, and
{\em during\/} respectively.
The inverse relations, such as $\AllenmiF$, whose names end in $\AlleniF$
are the same as the corresponding relations, such as $\AllenmF$, whose names do
not end in $\AlleniF$ except that the arguments are reversed.
Figure~\ref{Allen} depicts all thirteen Allen relations graphically.
Second, I define the {\sl span} of two intervals~$\I$ and~$\J$, denoted
$\Span{\I}{\J}$, as the smallest super-interval of both~$\I$ and~$\J$.

\begin{figure}
\begin{center}
\figpercent{80}{f30}
\end{center}
\caption{The Allen relations, the thirteen possible relations between two
intervals.}
\label{Allen}
\end{figure}

The syntax of event logic is defined as follows.
We are given finite disjoint sets of constant symbols
along with a finite set of primitive event-type symbols, each of a specified
arity.
Constant symbols, such as $\REDBLOCK$ and $\HAND$, denote objects in the input
movie while primitive event-type symbols, such as $\mbox{\sc Supports}$,
denote parameterized primitive event types.
An atomic event-logic expression is a primitive event-type symbol of arity~$n$
applied to a sequence of~$n$ constants.
For example, $\SUPPORTS{\HAND}{\REDBLOCK}$.
An event-logic expression is either an atomic event-logic expression or
one of the compound event-logic expressions $\neg\Phi$, $\Phi\vee\Psi$,
$\Phi\wedge_R\Psi$, or $\Diamond_R\Phi$,
where~$\Phi$ and~$\Psi$ are event-logic expressions
and $R\subseteq\theset{=,<,>,\AllenmF,\AllenmiF,\AllenoF,\AllenoiF,\AllensF,%
\AllensiF,\AllenfF,\AllenfiF,\AllendF,\AllendiF}$.

Informally, the semantics of compound event-logic expressions is defined as
follows:
\begin{itemize}
\item $\neg\Phi$ denotes the non-occurrence of~$\Phi$.
An occurrence of $\neg\Phi$ coincides with~$\I$ if no occurrence of~$\Phi$
coincides with~$\I$.
Note that $(\neg\Phi)@\I$ could be true, even if an occurrence of~$\Phi$
{\em overlapped\/} with~$\I$, so long as no occurrence of~$\Phi$
{\em coincided\/} with~$\I$.
\item $\Phi\vee\Psi$ denotes the occurrence of either~$\Phi$ or~$\Psi$.
\item $\Phi\wedge_R\Psi$ denotes the occurrence of both~$\Phi$ and~$\Psi$.
The occurrences of~$\Phi$ and~$\Psi$ need not be simultaneous.
The subscript~$R$ specifies a set of allowed Allen relations between the
occurrences of~$\Phi$ and~$\Psi$.
If occurrences of~$\Phi$ and~$\Psi$ coincide with~$\I$ and~$\J$ respectively,
and $\I r\J$ for some $r\in R$, then an occurrence of $\Phi\wedge_R\Psi$
coincides with the span of~$\I$ and~$\J$.
I abbreviate the special case $\Phi\wedge_{\theset{=}}\Psi$ simply
as $\Phi\wedge\Psi$ without any subscript.
$\Phi\wedge\Psi$ describes an aggregate event where both~$\Phi$ and~$\Psi$
occur simultaneously.
I also abbreviate the special
case $\Phi\wedge_{\theset{\sAllenmF}}\Psi$ as $\Phi;\Psi$.
$\Phi;\Psi$ describes an aggregate event where an occurrence of~$\Phi$ is
immediately followed by an occurrence of~$\Psi$.
\item An occurrence of $\Diamond_R\Phi$ coinciding with~$\I$ denotes an
occurrence of~$\Phi$ at some other interval~$\J$ such that $\J r\I$ for
some $r\in R$\@.
$\Diamond_R$ can act as a tense operator.
Expressions such as $\Diamond_{\theset{<}}\Phi$,
$\Diamond_{\theset{>}}\Phi$,
$\Diamond_{\theset{\sAllenmF}}\Phi$,
and $\Diamond_{\theset{\sAllenmiF}}\Phi$ specify that~$\Phi$
happened in the noncontiguous past, noncontiguous future, contiguous past,
or contiguous future respectively.
The~$\Diamond_R$ operator can also be used to derive overlapped occurrence
from coincidental occurrence.
An occurrence of $\Diamond_{\theset{=,\sAllenoF,\sAllenoiF,\sAllensF,%
\sAllensiF,\sAllenfF,\sAllenfiF,\sAllendF,\sAllendiF}}\Phi$ coincides
with~$\I$ if an occurrence of~$\Phi$ overlaps with~$\I$.
I abbreviate $\Diamond_{\theset{=,\sAllenoF,\sAllenoiF,\sAllensF,\sAllensiF,%
\sAllenfF,\sAllenfiF,\sAllendF,\sAllendiF}}\Phi$ simply as $\Diamond\Phi$
without any subscript.
Note that while $(\neg\Phi)@\I$ indicates that no occurrence of~$\Phi$
{\em coincided\/} with~$\I$, $(\neg\Diamond\Phi)@\I$ indicates that no
occurrence of~$\Phi$ {\em overlapped\/} with~$\I$.
\end{itemize}

Formally, the truth of an atomic event-occurrence formula $\Phi@\I$ is
defined relative to a model.
Let~$I$ be the set of all intervals and~$O$ be the set of all objects in
the movie.
A model~$M$ is a map from primitive event-type symbols of arity~$n$ to subsets
of $I\times\underbrace{O\times\cdots\times O}_n$.
($M$ can be viewed as either a \underline{m}odel or as a \underline{m}ovie.)
$M$ thus maps primitive event-type symbols to relations that take an interval
as their first argument, in addition to the remaining object parameters.
The semantics of event logic is formally defined by specifying an entailment
relation $M\models\Phi@\I$ as follows:
\begin{itemize}
\item $M\models p(t_1,\ldots,t_n)@\I$ if and only
if $\langle\I,t_1,\ldots,t_n\rangle\in M(p)$.
\item $M\models(\neg\Phi)@\I$ if and only if $M\not\models\Phi@\I$.
\item $M\models(\Phi\vee\Psi)@\I$ if and only if $M\models\Phi@\I$
or $M\models\Psi@\I$.
\item $M\models(\Phi\wedge_R\Psi)@\I$ if and only if there exist two
intervals~$\J$ and~$\K$ such that $\I=\Span{\J}{\K}$, $\J r\K$ for
some $r\in R$, $M\models\Phi@\J$, and $M\models\Psi@\K$.
\item $M\models(\Diamond_R\Phi)@\I$ if and only if there exists some
interval~$\J$ such that $\J r\I$ for some $r\in R$ and $M\models\Phi@\J$.
\end{itemize}

Figure~\ref{primitiveEventTypes} shows the primitive event types currently
used by \Leonard.
The definitions in Figure~\ref{primitiveEventTypes} are formulated in terms of
the predicates $\GROUNDEDF$, $\RIGIDF$, $\REVOLUTEF$, and $\SAMELAYERF$ that
are produced by model reconstruction as described in
Section~\ref{modelReconstruction}.
An object is supported if it is not grounded.
Two objects contact if their polygons touch and they are on the same layer.
Two polygons~$p$ and~$q$ touch, denoted~$\TOUCHES{p}{q}$, if they intersect
and their intersection has zero area.
Two objects are attached if there is a rigid or revolute joint that joins
them.
Determining whether an object~$x$ supports an object~$y$ is a little more
complex and requires counterfactual reasoning.
Let~$\cal P$ be the set of polygons in a scene,
$I=\langle\GROUNDEDF,\RIGIDF,\REVOLUTEF,\SAMELAYERF\rangle$ be the
most-preferred model of the scene as produced by model reconstruction,
and $\STABLE{{\cal P}}{I}$ be true if the scene~${\cal P}$ is stable under
an interpretation~$I$\@.
Stability analysis, i.e. the $\STABLEF$ predicate, is a subroutine used by the
model-reconstruction component.
An object~$x$ supports an object~$y$ if~$y$ is not grounded in the
most-preferred model~$I$ and a variant of~${\cal P}$ with~$x$ removed is
not stable under a variant of~$I$ where all objects except for~$y$ and those
rigidly attached, directly or indirectly, to~$y$ are grounded.
In Figure~\ref{primitiveEventTypes}, ${\cal P}\setminus\theset{x}$ denotes
the variant of~${\cal P}$ with~$x$ removed, $\RIGIDLYATTACHED{x}{y}$ denotes
the fact that~$x$ is rigidly attached to~$y$, $\RIGIDLYATTACHEDF^{*}$ denotes
the reflexive transitive closure of the $\RIGIDLYATTACHEDF$ relation,
$\theset{z|\neg\RIGIDLYATTACHEDSTAR{z}{y}}$ denotes the set of objects that
are rigidly attached, directly or indirectly, to~$y$, and
$\langle\GROUNDEDF\cup\theset{z|\neg\RIGIDLYATTACHEDSTAR{z}{y}},%
\RIGIDF,\REVOLUTEF,\SAMELAYERF\rangle$
denotes a variant of~$I$ where all objects except for~$y$ and those
rigidly attached, directly or indirectly, to~$y$ are grounded.

\begin{figure}
\begin{eqnarray*}
x=y&\define&\overline{x=y}\\
\SUPPORTED{x}&\define&\overline{\neg\GROUNDED{x}}\\
\RIGIDLYATTACHED{x}{y}&\define&(\exists r)\RIGID{x}{y}{r}\\
\SUPPORTS{x}{y}&\define&
\overline{\left[\begin{array}{l}
\neg\GROUNDED{y}\wedge\\
\neg\STABLEF
\left(\begin{array}{l}
{\cal P}\setminus\theset{x},
\left\langle\begin{array}{l}
\GROUNDEDF\cup\theset{z|\neg\RIGIDLYATTACHEDSTAR{z}{y}},\\
\RIGIDF,\\
\REVOLUTEF,\\
\SAMELAYERF
\end{array}\right\rangle
\end{array}\right)
\end{array}\right]}\\
\CONTACTS{x}{y}&\define&
\overline{\TOUCHES{x}{y}\wedge\SAMELAYER{x}{y}}\\
\ATTACHED{x}{y}&\define&
\overline{(\exists r)\RIGID{x}{y}{r}\vee\REVOLUTE{x}{y}{r}}
\end{eqnarray*}
\caption{Definition of the primitive event types used by \Leonard.}
\label{primitiveEventTypes}
\end{figure}

Figure~\ref{compoundEventTypes} shows the compound event-type definitions
currently used by \Leonard.\\%
$\PICKUP{x}{y}{z}$ denotes an event type where~$x$ picks~$y$ up off of~$z$.
It is specified as a sequence of three intervals, where~$x$ is not attached
to and does not support~$y$ in the first interval but is attached to and does
support~$y$ in the third interval.
Additionally, $z$ supports~$y$ in the first interval but does not support~$y$
in the third interval.
Furthermore, several conditions must hold in both the first and third
intervals: $x$~must be unsupported, $y$~must not support either~$x$ or~$z$,
$x$~and~$z$ must not support each other, and~$y$ must not be attached to~$z$.
During the second interval, intermediate between the first and third
intervals, either~$x$ is attached to~$y$ or~$y$ is attached
to~$z$.\footnote{Originally, a two-interval definition was used, consisting of
only the first and third intervals.
Such a definition better reflects human intuition.
This requires that~$x$ be unsupported, $y$~not support either~$x$ or~$z$,
$x$~and~$z$ not support each other, and~$y$ not be attached to~$z$ throughout
the event.
Unfortunately, however, the model-reconstruction process has some quirks.
When the hand grasps the patient while the patient is still resting on the
source it produces a most-preferred model where all three objects are attached
and collectively supported by one of them being grounded.
While such a model is consistent with the theory and is minimal, it does not
match human intuition.
Pending improvements in the model-reconstruction process to better reflect
human intuition, the compound event-type definition for {\em pick up\/} was
modified to reflect the force-dynamic interpretations produced by the current
model-reconstruction process.
Fortunately, the current model-reconstruction process is robust in reproducing
this counterintuitive interpretation.}
Additionally, several conditions must hold throughout the entire event: $x$,
$y$, and~$z$ must be distinct and~$y$ must be supported.
$\PUTDOWN{x}{y}{z}$ denotes an event type where~$x$ puts~$y$ down on~$z$.
It is specified in a fashion that is similar to $\PICKUP{x}{y}{z}$ but where
the three subevents occur in reverse order.
$\STACK{w}{x}{y}{z}$ denotes an event type where~$w$ puts~$x$ down on~$y$
which is resting on~$z$.
It is specified as $\PUTDOWN{w}{x}{y}$, where~$z$ supports but is not
attached to~$y$ and~$z$ is distinct from~$w$, $x$, and~$y$.
$\UNSTACK{w}{x}{y}{z}$ denotes an event type where~$w$ picks~$x$ up off
of~$y$ which is resting on~$z$.
It is specified as $\PICKUP{w}{x}{y}$, where~$z$ supports but is not
attached to~$y$ and~$z$ is distinct from~$w$, $x$, and~$y$.
$\MOVE{w}{x}{y}{z}$ denotes an event type where~$w$ picks~$x$ up off of~$y$ and
puts it down on~$z$ which is distinct from~$y$.
$\ASSEMBLE{w}{x}{y}{z}$ denotes an event type where~$w$ first puts~$y$ down
on~$z$ then sometime later stacks~$x$ on top of~$y$.
Finally, $\DISASSEMBLE{w}{x}{y}{z}$ denotes an event type where~$w$ first
unstacks~$x$ from on top of~$y$ (which is resting on~$z$) and then sometime
later picks~$y$ up off of~$z$.
Figure~\ref{videoOne} shows sample movies depicting occurrences of the event
types $\PICKUP{x}{y}{z}$ and $\PUTDOWN{x}{y}{z}$.
Figures~\ref{videoThreeA} through~\ref{videoThreeE} show sample movies
depicting occurrences of the event types $\STACK{w}{x}{y}{z}$,
$\UNSTACK{w}{x}{y}{z}$, $\MOVE{w}{x}{y}{z}$, $\ASSEMBLE{w}{x}{y}{z}$, and
$\DISASSEMBLE{w}{x}{y}{z}$ respectively.

\begin{figure}
\begin{eqnarray*}
\PICKUP{x}{y}{z}&\define&
\left(\begin{array}{l}
\neg\Diamond x=y\wedge
\neg\Diamond z=x\wedge
\neg\Diamond z=y\wedge\\
\SUPPORTED{y}\wedge
\neg\Diamond\ATTACHED{x}{z}\wedge\\
\left\{\begin{array}{l}
\left[\begin{array}{l}
\neg\Diamond\ATTACHED{x}{y}\wedge
\neg\Diamond\SUPPORTS{x}{y}\wedge\\
\SUPPORTS{z}{y}\wedge\\
\neg\Diamond\SUPPORTED{x}\wedge
\neg\Diamond\ATTACHED{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{y}{x}\wedge
\neg\Diamond\SUPPORTS{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{x}{z}\wedge
\neg\Diamond\SUPPORTS{z}{x}
\end{array}\right];\\
\left[\ATTACHED{x}{y}\vee\ATTACHED{y}{z}\right];\\
\left[\begin{array}{l}
\ATTACHED{x}{y}\wedge
\SUPPORTS{x}{y}\wedge\\
\neg\Diamond\SUPPORTS{z}{y}\wedge\\
\neg\Diamond\SUPPORTED{x}\wedge
\neg\Diamond\ATTACHED{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{y}{x}\wedge
\neg\Diamond\SUPPORTS{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{x}{z}\wedge
\neg\Diamond\SUPPORTS{z}{x}
\end{array}\right]
\end{array}\right\}
\end{array}\right)\\
\PUTDOWN{x}{y}{z}&\define&
\left(\begin{array}{l}
\neg\Diamond x=y\wedge
\neg\Diamond z=x\wedge
\neg\Diamond z=y\wedge\\
\SUPPORTED{y}\wedge
\neg\Diamond\ATTACHED{x}{z}\wedge\\
\left\{\begin{array}{l}
\left[\begin{array}{l}
\ATTACHED{x}{y}\wedge
\SUPPORTS{x}{y}\wedge\\
\neg\Diamond\SUPPORTS{z}{y}\wedge\\
\neg\Diamond\SUPPORTED{x}\wedge
\neg\Diamond\ATTACHED{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{y}{x}\wedge
\neg\Diamond\SUPPORTS{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{x}{z}\wedge
\neg\Diamond\SUPPORTS{z}{x}
\end{array}\right];\\
\left[\ATTACHED{x}{y}\vee\ATTACHED{y}{z}\right];\\
\left[\begin{array}{l}
\neg\Diamond\ATTACHED{x}{y}\wedge
\neg\Diamond\SUPPORTS{x}{y}\wedge\\
\SUPPORTS{z}{y}\wedge\\
\neg\Diamond\SUPPORTED{x}\wedge
\neg\Diamond\ATTACHED{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{y}{x}\wedge
\neg\Diamond\SUPPORTS{y}{z}\wedge\\
\neg\Diamond\SUPPORTS{x}{z}\wedge
\neg\Diamond\SUPPORTS{z}{x}
\end{array}\right]
\end{array}\right\}
\end{array}\right)\\
\STACK{w}{x}{y}{z}&\define&
\left[\begin{array}{l}
\neg\Diamond z=w\wedge
\neg\Diamond z=x\wedge
\neg\Diamond z=y\wedge\\
\PUTDOWN{w}{x}{y}\wedge
\SUPPORTS{z}{y}\wedge\\
\neg\ATTACHED{z}{y}
\end{array}\right]\\
\UNSTACK{w}{x}{y}{z}&\define&
\left[\begin{array}{l}
\neg\Diamond z=w\wedge
\neg\Diamond z=x\wedge
\neg\Diamond z=y\wedge\\
\PICKUP{w}{x}{y}\wedge
\SUPPORTS{z}{y}\wedge
\neg\ATTACHED{z}{y}
\end{array}\right]\\
\MOVE{w}{x}{y}{z}&\define&
\neg\Diamond y=z\wedge\left[\PICKUP{w}{x}{y};\PUTDOWN{w}{x}{z}\right]\\
\ASSEMBLE{w}{x}{y}{z}&\define&
\PUTDOWN{w}{y}{z}\wedge_{\theset{<}}\STACK{w}{x}{y}{z}\\
\DISASSEMBLE{w}{x}{y}{z}&\define&
\UNSTACK{w}{x}{y}{z}\wedge_{\theset{<}}\PICKUP{x}{y}{z}\\
\end{eqnarray*}
\caption{The lexicon of compound event types used by \Leonard.}
\label{compoundEventTypes}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{stack00-3-image}&
\figpercent{30}{stack00-11-image}&
\figpercent{30}{stack00-12-image}&
\figpercent{30}{stack00-23-image}\\
Frame 3&
Frame 11&
Frame 12&
Frame 23\\
\figpercent{30}{stack00-24-image}&
\figpercent{30}{stack00-26-image}\\
Frame 24&
Frame 26
\end{tabular}
\end{center}
\caption{An image sequence depicting a {\em stack\/} event.}
\label{videoThreeA}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{unstack00-1-image}&
\figpercent{30}{unstack00-10-image}&
\figpercent{30}{unstack00-11-image}&
\figpercent{30}{unstack00-24-image}\\
Frame 1&
Frame 10&
Frame 11&
Frame 24\\
\figpercent{30}{unstack00-25-image}&
\figpercent{30}{unstack00-29-image}\\
Frame 25&
Frame 29
\end{tabular}
\end{center}
\caption{An image sequence depicting an {\em unstack\/} event.}
\label{videoThreeB}
\end{figure}

% note: frames were incorrect in jair2000-submission and fixed here

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{move00-0-image}&
\figpercent{30}{move00-8-image}&
\figpercent{30}{move00-9-image}&
\figpercent{30}{move00-16-image}\\
Frame 0&
Frame 8&
Frame 9&
Frame 16\\
\figpercent{30}{move00-17-image}&
\figpercent{30}{move00-33-image}&
\figpercent{30}{move00-34-image}&
\figpercent{30}{move00-45-image}\\
Frame 17&
Frame 33&
Frame 34&
Frame 45\\
\figpercent{30}{move00-46-image}&
\figpercent{30}{move00-47-image}\\
Frame 46&
Frame 47
\end{tabular}
\end{center}
\caption{An image sequence depicting a {\em move\/} event.}
\label{videoThreeC}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{assemble00-0-image}&
\figpercent{30}{assemble00-9-image}&
\figpercent{30}{assemble00-10-image}&
\figpercent{30}{assemble00-17-image}\\
Frame 0&
Frame 9&
Frame 10&
Frame 17\\
\figpercent{30}{assemble00-18-image}&
\figpercent{30}{assemble00-32-image}&
\figpercent{30}{assemble00-33-image}&
\figpercent{30}{assemble00-40-image}\\
Frame 18&
Frame 32&
Frame 33&
Frame 40\\
\figpercent{30}{assemble00-41-image}&
\figpercent{30}{assemble00-46-image}&
\figpercent{30}{assemble00-47-image}&
\figpercent{30}{assemble00-56-image}\\
Frame 41&
Frame 46&
Frame 47&
Frame 56\\
\figpercent{30}{assemble00-57-image}&
\figpercent{30}{assemble00-67-image}&
\figpercent{30}{assemble00-68-image}&
\figpercent{30}{assemble00-80-image}\\
Frame 57&
Frame 67&
Frame 68&
Frame 80
\end{tabular}
\end{center}
\caption{An image sequence depicting an {\em assemble\/} event.}
\label{videoThreeD}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{disassemble00-18-image}&
\figpercent{30}{disassemble00-19-image}&
\figpercent{30}{disassemble00-22-image}&
\figpercent{30}{disassemble00-23-image}\\
Frame 18&
Frame 19&
Frame 22&
Frame 23\\
\figpercent{30}{disassemble00-49-image}&
\figpercent{30}{disassemble00-50-image}&
\figpercent{30}{disassemble00-56-image}&
\figpercent{30}{disassemble00-57-image}\\
Frame 49&
Frame 50&
Frame 56&
Frame 57\\
\figpercent{30}{disassemble00-62-image}&
\figpercent{30}{disassemble00-63-image}&
\figpercent{30}{disassemble00-87-image}&
\figpercent{30}{disassemble00-88-image}\\
Frame 62&
Frame 63&
Frame 87&
Frame 88
\end{tabular}
\end{center}
\caption{An image sequence depicting a {\em disassemble\/} event.}
\label{videoThreeE}
\end{figure}

Nominally, all atomic event-logic expressions are primitive event types.
However, we allow giving a name to a compound event-logic expression and using
this name in another event-logic expression as short hand for the named
expression with appropriate parameter substitution.
This is simply a macro-expansion process and, as such, no recursion is allowed.
This feature is used in Figure~\ref{compoundEventTypes} to define
$\mbox{\sc Unstack}$, $\mbox{\sc Move}$, and $\mbox{\sc Disassemble}$
in terms of $\mbox{\sc PickUp}$; $\mbox{\sc Stack}$, $\mbox{\sc Move}$, and
$\mbox{\sc Assemble}$ in terms of $\mbox{\sc PutDown}$; $\mbox{\sc Assemble}$
in terms of $\mbox{\sc Stack}$, which is itself defined in terms of
$\mbox{\sc PutDown}$; and $\mbox{\sc Disassemble}$ in terms of
$\mbox{\sc Unstack}$, which is itself defined in terms of
$\mbox{\sc PickUp}$.

The overall goal of the event-classification component is to infer all
occurrences of a given set of compound event types from a given set of
primitive event occurrences.
The model-reconstruction component combined with the primitive event-type
definitions given in Figure~\ref{primitiveEventTypes} produces a set of
primitive event occurrences for a given scene sequence.
Figure~\ref{compoundEventTypes} lists parameterized compound event types.
These are instantiated for all tuples of objects in the scene sequence to yield
ground compound event-logic expressions.
The event-classification component infers all occurrences of these compound
event types that follow from the set of primitive event occurrences.
Let us define $\E{M}{\Phi}$ to be $\theset{\I|M\models\Phi@\I}$.
The model-reconstruction component combined with the primitive event-type
definitions given in Figure~\ref{primitiveEventTypes} produces~$M$\@.
Instantiating the parameterized compound event types from
Figure~\ref{compoundEventTypes} for all object tuples yields a set of
event-logic expressions.
The event-classification component computes $\E{M}{\Phi}$ for every~$\Phi$ in
this set.

In principle, $\E{M}{\Phi}$ could by implemented as a straightforward
application of the formal semantics for event logic as specified above.
There is a difficulty in doing so, however.
The primitive event types have the property that they are {\sl liquid}.
Liquid events have the following two properties.
First, if they are true during an interval~$\I$, then they are also true during
any subinterval of~$\I$.
Second, if they are true during two overlapping intervals~$\I$ and~$\J$, then
they are also true during $\Span{\I}{\J}$ and any subinterval of
$\Span{\I}{\J}$.
For example, if an object is supported during $[1,10]$, then it also is
supported during $[2,5]$, $[3,8]$, and all other subintervals of $[1,10]$.
Similarly, if an object is supported during $[1,5]$ and $[4,10]$, then it also
is supported during $[1,10]$ and all of its subintervals.
\citeA{Shoham87} introduced the notion of liquidity and \citeA{Vendler67},
\citeA{Dowty79}, \citeA{Verkuyl89}, and \citeA{Krifka92} have observed that
many event types have this property.
Because the primitive event types are liquid, they will hold over an infinite
number of subintervals.
This renders the formal semantics inappropriate for a computational
implementation.
Even if one limits oneself to intervals with integral endpoints, the primitive
event types will hold over quadratically many subintervals of the scene
sequence.
Furthermore, a straightforward computational implementation of the formal
semantics would be inefficient, because it requires quantifying over
subintervals to implement~$\Diamond_R$ and quantifying over pairs of
subintervals to implement~$\wedge_R$.
The central result of this paper is a novel representation, called
{\sl spanning intervals}, that allows an efficient representation of the
infinite sets of subintervals over which liquid event types hold along with an
efficient inference procedure that operates on that representation.
This representation, and the inference procedure that implements $\E{M}{\Phi}$,
are presented in the next section.

\section{An Efficient Representation and Inference Procedure for Event Logic}

One might try to implement event logic using only closed intervals of the
form $[q,r]$, where $q\leq r$.
Such a closed interval would represent the set $\theset{p|q\leq p\leq r}$ of
real numbers.
With such closed intervals, one would define Allen's relations as follows:
\begin{eqnarray*}
[q_1,r_1]=[q_2,r_2]&\define&(q_1=q_2)\wedge(r_1=r_2)\\{}
[q_1,r_1]<[q_2,r_2]&\define&r_1<q_2\\{}
[q_1,r_1]>[q_2,r_2]&\define&q_1>r_2\\
\Allenm{[q_1,r_1]}{[q_2,r_2]}&\define&r_1=q_2\\
\Allenmi{[q_1,r_1]}{[q_2,r_2]}&\define&q_1=r_2\\
\Alleno{[q_1,r_1]}{[q_2,r_2]}&\define&q_1<q_2<r_1<r_2\\
\Allenoi{[q_1,r_1]}{[q_2,r_2]}&\define&r_1>r_2>q_1>q_2\\
\Allens{[q_1,r_1]}{[q_2,r_2]}&\define&(q_1=q_2)\wedge(r_1<r_2)\\
\Allensi{[q_1,r_1]}{[q_2,r_2]}&\define&(q_1=q_2)\wedge(r_1>r_2)\\
\Allenf{[q_1,r_1]}{[q_2,r_2]}&\define&(q_1>q_2)\wedge(r_1=r_2)\\
\Allenfi{[q_1,r_1]}{[q_2,r_2]}&\define&(q_1<q_2)\wedge(r_1=r_2)\\
\Allend{[q_1,r_1]}{[q_2,r_2]}&\define&(q_1>q_2)\wedge(r_1<r_2)\\
\Allendi{[q_1,r_1]}{[q_2,r_2]}&\define&(q_1<q_2)\wedge(r_1>r_2)
\end{eqnarray*}
One difficulty with doing so is that it would be possible for more than one
Allen relation to hold between two intervals when one or both of them are
instantaneous intervals, such as $[q,q]$.
Both~$\AllenmF$ and~$\AllensF$ would hold between $[q,q]$ and $[q,r]$,
both~$\AllenmiF$ and~$\AllensiF$ would hold between $[q,r]$
and $[q,q]$, both~$\AllenmF$ and~$\AllenfiF$ would hold
between $[q,r]$ and $[r,r]$, both~$\AllenmiF$ and~$\AllenfF$ would
hold between $[r,r]$ and $[q,r]$, and~$=$, $\AllenmF$, and~$\AllenmiF$
would all hold between $[q,q]$ and itself.
To create a domain where exactly one Allen relation holds between any pair of
intervals, let us consider both open and closed intervals.
Closed intervals contain their endpoints while open intervals do not.
The intervals $(q,r]$, $[q,r)$, and $(q,r)$, where $q<r$, represent the
sets $\theset{p|q<p\leq r}$, $\theset{p|q\leq p<r}$, and $\theset{p|q<p<r}$
of real numbers respectively.
The various kinds of open and closed intervals can be unified into a single
representation $\NI{q}{r}{\alpha}{\beta}$, where~$\alpha$ and~$\beta$ are true
or false to indicate the interval being closed or open on the left or right
respectively.\footnote{Throughout this paper, I use lowercase
Greek letters, such as~$\alpha$, $\beta$, $\gamma$, $\delta$, $\epsilon$,
and~$\zeta$, to denote Boolean values, lowercase Latin letters, such as~$p$,
$q$, $r$, $i$, $j$, $k$, and~$l$, to denote real numbers, lowercase bold Latin
letters, such as $\I$, $\J$, and~$\K$, to denote intervals or spanning
intervals, and uppercase Latin letters, such as~$I$, $J$, and~$K$, to denote
sets of intervals or sets of spanning intervals.}
More specifically, $\NI{q}{r}{\TRUE}{\TRUE}$ denotes $[q,r]$,
$\NI{q}{r}{\FALSE}{\TRUE}$ denotes $(q,r]$,
$\NI{q}{r}{\TRUE}{\FALSE}$ denotes $[q,r)$, and
$\NI{q}{r}{\FALSE}{\FALSE}$ denotes $(q,r)$.
To do this, let us use $q\leq_{\alpha}r$ to mean $q\leq r$ when~$\alpha$ is
true and $q<r$ when~$\alpha$ is false.
Similarly, let us use $q\geq_{\alpha}r$ to mean $q\geq r$ when~$\alpha$ is
true and $q>r$ when~$\alpha$ is false.
More precisely, $q\leq_{\alpha}r\define(q<r)\vee[\alpha\wedge(q=r)]$
and $q\geq_{\alpha}r\define(q>r)\vee[\alpha\wedge(q=r)]$.
With these, $\NI{q}{r}{\alpha}{\beta}$ represents the set
$\theset{p|q\leq_{\alpha}p\leq_{\beta}r}$ of real numbers.

One can extend the definition of Allen's relations to both open and closed
intervals as follows.
The relation $\I_1=\I_2$ holds if the corresponding endpoints of~$\I_1$
and~$\I_2$ are equal and have the same openness.
The relation $\I_1<\I_2$ holds if the right endpoint of~$\I_1$ precedes the
left endpoint of~$\I_2$ or if they are equal and both open.
For example, $[1,3]<[4,5]$ and $[1,3)<(3,5]$, but
$[1,3]\not<(3,5]$, $[1,3)\not<[3,5]$, and $[1,3]\not<[3,5]$.
The relation $\Allenm{\I_1}{\I_2}$ holds if the right endpoint of~$\I_1$
equals the left endpoint of~$\I_2$ and one of those endpoints is open while
the other is closed.
For example, $\Allenm{[1,3]}{(3,5]}$ and $\Allenm{[1,3)}{[3,5]}$
but $\Allennotm{[1,3]}{[3,5]}$ and $\Allennotm{[1,3)}{(3,5]}$.
The relation $\Alleno{\I_1}{\I_2}$ holds if
\begin{itemize}
\item either the left endpoint of~$\I_1$ precedes the left endpoint of~$\I_2$
or they are equal while the former is closed and the latter is open,
\item either the left endpoint of~$\I_2$ precedes the right endpoint of~$\I_1$
or they are equal while both endpoints are closed, and
\item either the right endpoint of~$\I_1$ precedes the right endpoint
of~$\I_2$ or they are equal while the former is open and the latter is closed.
\end{itemize}
For example, $\Alleno{[1,3]}{[2,4]}$, $\Alleno{[1,3]}{(1,4]}$,
$\Alleno{[1,2]}{[2,4]}$, and $\Alleno{[1,4)}{[2,4]}$, but
$\Allennoto{[1,3]}{[1,4]}$, $\Allennoto{[1,2)}{[2,4]}$, and
$\Allennoto{[1,4]}{[2,4]}$.
The relation $\Allens{\I_1}{\I_2}$ holds if
\begin{itemize}
\item the left endpoints of~$\I_1$ and~$\I_2$ are equal and have the same
openness and
\item either the right endpoint of~$\I_1$ precedes the right endpoint
of~$\I_2$ or they are equal while the former is open and the latter is closed.
\end{itemize}
For example, $\Allens{[1,3]}{[1,4]}$, $\Allens{(1,3]}{(1,4]}$, and
$\Allens{[1,3)}{[1,3]}$, but $\Allennots{[1,3]}{(1,4]}$,
$\Allennots{[1,3]}{[1,3]}$, $\Allennots{[1,3)}{[1,3)}$, and
$\Allennots{[1,3]}{[1,3)}$.
The relation $\Allenf{\I_1}{\I_2}$ holds if
\begin{itemize}
\item the right endpoints of~$\I_1$ and~$\I_2$ are equal and have the same
openness and
\item either the left endpoint of~$\I_1$ follows the left endpoint of~$\I_2$
or they are equal while the former is open and the latter is closed.
\end{itemize}
For example, $\Allenf{[2,4]}{[1,4]}$, $\Allenf{[2,4)}{[1,4)}$, and
$\Allenf{(2,4]}{[2,4]}$, but $\Allennotf{[2,4)}{[1,4]}$,
$\Allennotf{(2,4]}{(2,4]}$, $\Allennotf{[2,4]}{[2,4]}$, and
$\Allennotf{[2,4]}{(2,4]}$.
The relation $\Allend{\I_1}{\I_2}$ holds if
\begin{itemize}
\item either the left endpoint of~$\I_1$ follows the left endpoint of~$\I_2$
or they are equal while the former is open and the latter is closed and
\item either the right endpoint of~$\I_1$ precedes the right endpoint
of~$\I_2$ or they are equal while the former is open and the latter is closed.
\end{itemize}
For example, $\Allend{[2,3]}{[1,4]}$ and $\Allend{(1,4)}{[1,4]}$, but
$\Allennotd{[1,4)}{[1,4]}$, $\Allennotd{(1,4]}{[1,4]}$,
$\Allennotd{(1,4)}{(1,4]}$, and $\Allennotd{(1,4)}{[1,4)}$.
The inverse Allen relations~$>$, $\AllenmiF$, $\AllenoiF$, $\AllensiF$,
$\AllenfiF$, and $\AllendiF$ are defined analogously to the~$<$,
$\AllenmF$, $\AllenoF$, $\AllensF$, $\AllenfF$, and $\AllendF$ relations
respectively with the arguments reversed.

The above definitions can be stated more precisely as follows:
\begin{eqnarray}
\NI{q_1}{r_1}{\alpha_1}{\beta_1}=\NI{q_2}{r_2}{\alpha_2}{\beta_2}&\define&
(q_1=q_2)\wedge(\alpha_1=\alpha_2)\wedge(r_1=r_2)\wedge(\beta_1=\beta_2)\\
\label{ltdef}
\NI{q_1}{r_1}{\alpha_1}{\beta_1}<\NI{q_2}{r_2}{\alpha_2}{\beta_2}&\define&
r_1\leq_{(\neg\beta_1\wedge\neg\alpha_2)}q_2\\
\label{gtdef}
\NI{q_1}{r_1}{\alpha_1}{\beta_1}>\NI{q_2}{r_2}{\alpha_2}{\beta_2}&\define&
q_1\geq_{(\neg\alpha_1\wedge\neg\beta_2)}r_2\\
\label{mdef}
\Allenm{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&(r_1=q_2)\wedge(\beta_1\not=\alpha_2)\\
\label{midef}
\Allenmi{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&(q_1=r_2)\wedge(\alpha_1\not=\beta_2)\\
\label{odef}
\Alleno{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&
q_1\leq_{(\alpha_1\wedge\neg\alpha_2)}q_2\leq_{(\beta_1\wedge\alpha_2)}r_1
\leq_{(\neg\beta_1\wedge\beta_2)}r_2\\
\label{oidef}
\Allenoi{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}&}
\define&
r_1\geq_{(\beta_1\wedge\neg\beta_2)}r_2\geq_{(\alpha_1\wedge\beta_2)}q_1
\geq_{(\neg\alpha_1\wedge\alpha_2)}q_2\\
\label{sdef}
\Allens{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&(q_1=q_2)\wedge(\alpha_1=\alpha_2)\wedge
[r_1\leq_{(\neg\beta_1\wedge\beta_2)}r_2]\\
\label{sidef}
\Allensi{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&(q_1=q_2)\wedge(\alpha_1=\alpha_2)\wedge
[r_1\geq_{(\beta_1\wedge\neg\beta_2)}r_2]\\
\label{fdef}
\Allenf{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&[q_1\geq_{(\neg\alpha_1\wedge\alpha_2)}q_2]\wedge
(r_1=r_2)\wedge(\beta_1=\beta_2)\\
\label{fidef}
\Allenfi{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&[q_1\leq_{(\alpha_1\wedge\neg\alpha_2)}q_2]\wedge
(r_1=r_2)\wedge(\beta_1=\beta_2)\\
\label{ddef}
\Allend{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&[q_1\geq_{(\neg\alpha_1\wedge\alpha_2)}q_2]\wedge
[r_1\leq_{(\neg\beta_1\wedge\beta_2)}r_2]\\
\label{didef}
\Allendi{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}
{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}&
\define&[q_1\leq_{(\alpha_1\wedge\neg\alpha_2)}q_2]\wedge
[r_1\geq_{(\beta_1\wedge\neg\beta_2)}r_2]
\end{eqnarray}
With the above definitions, exactly one Allen relation holds between any pair
of intervals.

I refer to the set of real numbers represented by an interval as its
{\sl extension}.
Given the above definition of interval, any interval, such as $[5,4]$,
$(5,4]$, $[5,4)$, or $(5,4)$, where the upper endpoint is less than the lower
endpoint represents the empty set.
Furthermore, any open interval, such as $[5,5)$, $(5,5]$, or $(5,5)$, where the
upper endpoint equals the lower endpoint also represents the empty set.
To create a situation where the extension of each interval has a unique
representation, let us represent all such empty sets of real numbers
as~$\theset{}$.
Thus whenever we represent an interval $\NI{q}{r}{\alpha}{\beta}$ explicitly,
it will have a nonempty extension and will satisfy the following normalization
criterion: $q\leq_{(\alpha\wedge\beta)}r$.

\subsection{Spanning Intervals}
\label{spanningIntervals}

When using event logic, we wish to compute and represent the set~$I$ of all
intervals over which some event-logic expression~$\Phi$ holds.
Many event types, including all of the primitive event types used in \Leonard,
are {\sl liquid} \cite{Shoham87} in the sense that if some event holds of an
interval then that event holds of every subinterval of that interval.
With real-valued interval endpoints, this creates the need to compute and
represent an infinite set of intervals for a liquid event.
Even limiting ourselves to integer-valued interval endpoints, a liquid event
will require the computation and representation of quadratically many
intervals.

To address this problem, let us introduce the notion of {\sl spanning
interval}.
A spanning interval $[i\!:\!j]$ represents the set of all subintervals of
$[i,j]$, in other words
$\theset{[q,r]|(i\leq q\leq j)\wedge(i\leq r\leq j)}$.
Similarly $(i\!:\!j]$, $[i\!:\!j)$, and $(i\!:\!j)$ represent
$\theset{(q,r]|(i\leq q\leq j)\wedge(i\leq r\leq j)}$,\\%
$\theset{[q,r)|(i\leq q\leq j)\wedge(i\leq r\leq j)}$, and
$\theset{(q,r)|(i\leq q\leq j)\wedge(i\leq r\leq j)}$ respectively.
We wish to use spanning intervals to represent the set of all
intervals over which the primitive event types hold and to compute and
represent the set of all intervals over which compound event types hold via
structural induction over the compound event-logic expressions.
A problem arises however.
Given two liquid event types~$\Phi$ and~$\Psi$, the compound event
type $\Phi;\Psi$ is not liquid.
If~$\Phi$ holds over $[i\!:\!j)$ and~$\Psi$ holds over $[j\!:\!k)$, then
$\Phi;\Psi$ might not hold over every subinterval of $[i,k)$.
It holds over only those subintervals that include~$j$.
For example, if $\Phi$ holds over $[1\!:\!10)$ and $\Psi$ holds over
$[8\!:\!20)$ then $\Phi;\Psi$ holds for every interval that starts between $1$
and $10$ and ends between $8$ and $20$.
But it doesn't hold for every subinterval of $[1,20)$.
For example, it doesn't hold of $[12,20)$.
I refer to such event types as {\sl semi liquid}.
Since spanning intervals are not sufficient to efficiently represent
semi-liquid events, let us extend the notion of spanning interval.
A spanning interval $[[i,j],[k,l]]$ represents the set of intervals
$\theset{[q,r]|(i\leq q\leq j)\wedge(k\leq r\leq l)}$.
Similarly the spanning intervals $([i,j],[k,l]]$, $[[i,j],[k,l])$,
and $([i,j],[k,l])$ represent the sets
$\theset{(q,r]|(i\leq q\leq j)\wedge(k\leq r\leq l)}$,
$\theset{[q,r)|(i\leq q\leq j)\wedge(k\leq r\leq l)}$, and
$\theset{(q,r)|(i\leq q\leq j)\wedge(k\leq r\leq l)}$ respectively.
This extended notion of spanning interval subsumes the original notion.
The spanning intervals $[i\!:\!j]$, $(i\!:\!j]$, $[i\!:\!j)$, and $(i\!:\!j)$
can be represented as the spanning intervals $[[i,j],[i,j]]$,
$([i,j],[i,j]]$, $[[i,j],[i,j])$, and $([i,j],[i,j])$ respectively.
For reasons that will become apparent in Section~\ref{complement}, it is
necessary to also allow for spanning intervals where the ranges of endpoint
values are open.
In other words, we will need to consider spanning intervals
like $[(i,j],[k,l]]$ to represent sets like
$\theset{[q,r]|(i<q\leq j)\wedge(i\leq r\leq j)}$.
All told, there are six endpoints that can independently be either open or
closed, namely $q$, $r$, $i$, $j$, $k$, and~$l$, yielding sixty four kinds of
spanning intervals.
These can all be unified into a single representation
$\NI{\NI{i}{j}{\gamma}{\delta}}{\NI{k}{l}{\epsilon}{\zeta}}{\alpha}{\beta}$,
where~$\alpha$, $\beta$, $\gamma$, $\delta$, $\epsilon$, and~$\zeta$ are true
or false if the endpoints~$q$, $r$, $i$, $j$, $k$, and~$l$ are closed or open
respectively.
More precisely, the spanning interval
$\NI{\NI{i}{j}{\gamma}{\delta}}{\NI{k}{l}{\epsilon}{\zeta}}{\alpha}{\beta}$
represents the set
\begin{equation}
\label{spandef}
\theset{\NI{q}{r}{\alpha}{\beta}|
(i\leq_{\gamma}q\leq_{\delta}j)\wedge
(k\leq_{\epsilon}r\leq_{\zeta}l)}
\end{equation}
of intervals.
I refer to the set of intervals represented by a spanning interval as its
{\sl extension}.
Moreover, a set of spanning intervals will represent the union of the
extensions of its members.
Additionally, the empty set of spanning intervals will represent the empty set
of intervals.
I further refer to the set of intervals represented by a set of spanning
intervals as its {\sl extension}.
A key result of this paper is that if the set of all intervals over which some
set of primitive event types hold can be represented as finite sets of spanning
intervals then the set of all intervals over which all event types that are
expressible as compound event-logic expressions over those primitives hold
can also be represented as finite sets of spanning intervals.

While we require that all intervals have finite endpoints, for reasons that
will also become apparent in Section~\ref{complement}, it is necessary to allow
spanning intervals to have infinite endpoints, for example
$[[-\infty,j],[k,l]]$.
Such spanning intervals with infinite endpoints represent sets of
intervals with finite endpoints but where the range of possible endpoints is
unconstrained from above or below.

\subsection{Normalizing Spanning Intervals}

Just as we desire that the extension of every interval have a unique
representation, we also desire that the extension of every spanning interval
have a unique representation.
There are a number of situations where two different spanning intervals will
have the same extension.
First, all spanning intervals
$\NI{\NI{i}{j}{\gamma}{\delta}}{\NI{k}{l}{\epsilon}{\zeta}}{\alpha}{\beta}$
where $i=\infty$, $j=-\infty$, $k=\infty$, or $l=-\infty$ represent the empty
set of intervals, because there are no intervals with an endpoint that is less
than or equal to minus infinity or greater than or equal to infinity.
Second, if $i=-\infty$, $j=\infty$, $k=-\infty$, or $l=\infty$, the value
of~$\gamma$, $\delta$, $\epsilon$, or~$\zeta$ does not affect the denotation
respectively, because there are no intervals with infinite endpoints.
Third, if $j>l$, $j$~can be decreased as far as~$l$ without changing the
denotation, because all intervals where the upper endpoint is less than the
lower endpoint equivalently denote the empty interval.
Similarly, if $k<i$, $k$~can be increased as far as~$i$ without changing the
denotation.
Fourth, all spanning intervals where $i>j$ or $k>l$ represent the empty set of
intervals, because the range of possible endpoints would be empty.
Fifth, all spanning intervals where $i=j$ and either~$\gamma$ or~$\delta$ is
false (indicating an open range for the lower endpoint) represent the empty
set of intervals, because the range of possible endpoints would be empty.
Similarly, all spanning intervals where $k=l$ and either~$\epsilon$ or~$\zeta$
is false (indicating an open range for the upper endpoint) also represent the
empty set of intervals.
Sixth, all spanning intervals where $i=l$ and either~$\alpha$ or~$\beta$ is
false (indicating an open interval) also represent the empty set of intervals,
because the endpoints of an open interval must be different.
Seventh, if $j=l$ and~$\zeta$ is false, the
value of~$\delta$ does not affect the denotation, because if $j=l$ and~$\zeta$
is false, the upper endpoint must be less than~$l$ and the lower endpoint must
be less than or equal to~$j$ which equals~$l$, so the lower endpoint must be
less than~$j$.
Similarly, if $k=i$ and~$\gamma$ is false, the value of~$\epsilon$ does not
affect the denotation.
Eighth, if $j=l$ and either~$\alpha$ or~$\beta$ is false, the
value of~$\delta$ does not affect the denotation, because the lower endpoint
of an open interval must be less than its upper endpoint.
Similarly, if $k=i$ and either~$\alpha$ or~$\beta$ is false, the
value of~$\epsilon$ does not affect the denotation.

To create a situation where the extension of every spanning interval has a
unique representation, let us represent all empty sets of intervals
as~$\theset{}$.
When the values of~$i$, $j$, $k$, $l$, $\alpha$, $\beta$, $\gamma$,
$\delta$, $\epsilon$, or~$\zeta$ can be changed without changing the
denotation, we will select the tightest such values.
In other words, false values for the Boolean parameters, maximal values for
the lower bounds, and minimal values for the upper bounds.
Thus whenever we represent a spanning interval
$\NI{\NI{i}{j}{\gamma}{\delta}}{\NI{k}{l}{\epsilon}{\zeta}}{\alpha}{\beta}$
explicitly, it will have a nonempty extension and will satisfy the following
normalization criterion:
\begin{displaymath}
\begin{array}{ll}
(1)&(i\not=\infty)\wedge
(j\not=-\infty)\wedge
(k\not=\infty)\wedge
(l\not=-\infty)\wedge\\
(2)&[(i=-\infty)\rightarrow\neg\gamma]\wedge
[(j=\infty)\rightarrow\neg\delta]\wedge
[(k=-\infty)\rightarrow\neg\epsilon]\wedge
[(l=\infty)\rightarrow\neg\zeta]\wedge\\
(3)&(j\leq l)\wedge
(k\geq i)\wedge\\
(4)&(i\leq j)\wedge
(k\leq l)\wedge\\
(5)&[(i\not=j)\vee(\gamma\wedge\delta)]\wedge
[(k\not=l)\vee(\epsilon\wedge\zeta)]\wedge\\
(6)&[(i\not=l)\vee(\alpha\wedge\beta)]\wedge\\
(7)&\{[(j=l)\wedge\neg\zeta]\rightarrow\neg\delta\}
\wedge
\{[(k=i)\wedge\neg\gamma]\rightarrow\neg\epsilon\}
\wedge\\
(8)&\{[(j=l)\wedge(\neg\alpha\vee\neg\beta)]\rightarrow\neg\delta\}
\wedge
\{[(k=i)\wedge(\neg\alpha\vee\neg\beta)]\rightarrow\neg\epsilon\}
\end{array}
\end{displaymath}
Criteria~(1) through~(8) correspond to points one through eight above.

A spanning interval
$\NI{\NI{i}{j}{\gamma}{\delta}}{\NI{k}{l}{\epsilon}{\zeta}}{\alpha}{\beta}$ is
{\sl normalized} if~$i$, $j$, $k$, $l$, $\alpha$, $\beta$, $\gamma$, $\delta$,
$\epsilon$, and~$\zeta$ cannot be changed without changing its denotation.
Given a (potentially non-normalized) spanning interval~$\I$, its
{\sl normalization} $\NORM{\I}$ is the smallest set of normalized spanning
intervals that represents the extension of~$\I$.
One can compute $\NORM{\I}$ as follows:
\begin{displaymath}
\NORM{\NI{\NI{i}{j}{\gamma}{\delta}}{\NI{k}{l}{\epsilon}{\zeta}}
{\alpha}{\beta}}\define
\left\{\begin{array}{l}
\theset{\NI{\NI{i}{j'}{\gamma'}{\delta'}}{\NI{k'}{l}{\epsilon'}{\zeta'}}
{\alpha}{\beta}}\\
\;\;\;\mbox{\rm where}\;
\begin{array}[t]{rcl}
j'&=&\min(j,l)\\
k'&=&\max(k,i)\\
\gamma'&=&\gamma\wedge(i\not=-\infty)\\
\delta'&=&\delta\wedge[\min(j,l)\not=\infty]\wedge
[(j<l)\vee(\zeta\wedge\alpha\wedge\beta)]\\
\epsilon'&=&\epsilon\wedge[\max(k,i)\not=-\infty]\wedge
[(k>i)\vee(\gamma\wedge\beta\wedge\alpha)]\\
\zeta'&=&\zeta\wedge(l\not=\infty)
\end{array}\\
\;\;\;\mbox{\rm when}\;
\begin{array}[t]{l}
(i\leq j')\wedge
(k'\leq l)\wedge\\{}
[(i=j')\rightarrow(\gamma'\wedge\delta')]\wedge
[(k'=l)\rightarrow(\epsilon'\wedge\zeta')]\wedge\\{}
[(i=l)\rightarrow(\alpha\wedge\beta)]\wedge\\
(i\not=\infty)\wedge
(j'\not=-\infty)\wedge
(k'\not=\infty)\wedge
(l\not=-\infty)
\end{array}\\
\theset{}\;\;\;\mbox{\rm otherwise}
\end{array}\right.
\end{displaymath}
An important property of spanning intervals is that for any spanning
interval~$\I$, $\NORM{\I}$ contains at most {\em one\/} normalized spanning
interval.\footnote{The reason that $\NORM{\I}$ contains {\em at most\/} one
normalized spanning interval and not {\em exactly\/} one normalized spanning
interval is that~$\I$ may denote the empty set of intervals.
For example, normalizing the (non-normalized) spanning interval
$[[10,10],[1,1]]$ yields the empty set.
Many of the definitions in the coming sections compute sets of normalized
spanning intervals as unions of one or more applications of the normalization
operator $\langle\cdot\rangle$.
Each such application might yield either the empty set or a set containing a
single normalized spanning interval.
This leads to upper, but not lower, bounds on the size of the computed unions.}

\subsection{Computing the Intersection of Two Normalized Spanning Intervals}

Given two normalized spanning intervals~$\I_1$ and~$\I_2$, their
{\sl intersection} $\I_1\cap\I_2$ is a set of normalized spanning intervals
whose extension is the intersection of the extensions of~$\I_1$ and~$\I_2$.
One can compute $\I_1\cap\I_2$ as follows:
\begin{displaymath}
\begin{array}{l}
\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}{\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
{\alpha_1}{\beta_1}\cap
\NI{\NI{i_2}{j_2}{\gamma_2}{\delta_2}}{\NI{k_2}{l_2}{\epsilon_2}{\zeta_2}}
{\alpha_2}{\beta_2}\define\\
\;\;\;\left\{\begin{array}{l}
\NORM{\NI{\NI{\max(i_1,i_2)}{\min(j_1,j_2)}{\gamma}{\delta}}
         {\NI{\max(k_1,k_2)}{\min(l_1,l_2)}{\epsilon}{\zeta}}
         {\alpha_1}{\beta_1}}\\
\;\;\;\mbox{\rm where}\;
\begin{array}[t]{rcl}
\gamma&=&\left\{\begin{array}{ll}
\gamma_1&i_1>i_2\\
\gamma_1\wedge\gamma_2&i_1=i_2\\
\gamma_2&i_1<i_2
\end{array}\right.\\
\delta&=&\left\{\begin{array}{ll}
\delta_1&j_1<j_2\\
\delta_1\wedge\delta_2&j_1=j_2\\
\delta_2&j_1>j_2
\end{array}\right.\\
\epsilon&=&\left\{\begin{array}{ll}
\epsilon_1&k_1>k_2\\
\epsilon_1\wedge\epsilon_2&k_1=k_2\\
\epsilon_2&k_1<k_2
\end{array}\right.\\
\zeta&=&\left\{\begin{array}{ll}
\zeta_1&l_1<l_2\\
\zeta_1\wedge\zeta_2&l_1=l_2\\
\zeta_2&l_1>l_2
\end{array}\right.
\end{array}\\
\;\;\;\mbox{\rm when}\;(\alpha_1=\alpha_2)\wedge(\beta_1=\beta_2)\\
\theset{}\;\;\;\mbox{\rm otherwise}
\end{array}\right.
\end{array}
\end{displaymath}
An important property of normalized spanning intervals is that for any two
normalized spanning intervals~$\I_1$ and~$\I_2$, $\I_1\cap\I_2$ contains at
most {\em one\/} normalized spanning interval.

The intuition behind the above definition is as follows.
All of the intervals in the extension of a spanning interval are of the same
type, namely $[q,r]$, $(q,r]$, $[q,r)$, or $(q,r)$.
The intersection of two spanning intervals has a nonempty extension only if
the two spanning intervals contain the same type of intervals in their
extension.
If they do, and the sets contain intervals whose lower endpoint is bound from
below by~$i_1$ and~$i_2$ respectively, then the intersection will
contain intervals whose lower endpoint is bound from below by both~$i_1$
and~$i_2$.
The resulting bound is open or closed depending on which of the input bounds
is tighter.
Similarly for the upper bound on the lower endpoint and the lower and upper
bounds on the upper endpoint.

\subsection{Computing the Complement of a Normalized Spanning Interval}
\label{complement}

Given a normalized spanning intervals~$\I$, its {\sl complement}~$\neg\I$
is a set of normalized spanning intervals whose extension is
the complement of the extension of~$\I$.
One can compute $\neg\I$ as follows:
\begin{displaymath}
\neg\NI{\NI{i}{j}{\gamma}{\delta}}
       {\NI{k}{l}{\epsilon}{\zeta}}
       {\alpha}{\beta}\define
\left(\begin{array}{l}
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{-\infty}{k}{\TRUE}{\neg\epsilon}}
         {\alpha}{\beta}}\cup\\
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{l}{\infty}{\neg\zeta}{\TRUE}}
         {\alpha}{\beta}}\cup\\
\NORM{\NI{\NI{-\infty}{i}{\TRUE}{\neg\gamma}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\alpha}{\beta}}\cup\\
\NORM{\NI{\NI{j}{\infty}{\neg\delta}{\TRUE}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\alpha}{\beta}}\cup\\
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\neg\alpha}{\beta}}\cup\\
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\alpha}{\neg\beta}}\cup\\
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\neg\alpha}{\neg\beta}}
\end{array}\right)
\end{displaymath}
An important property of normalized spanning intervals is that for any
normalized spanning interval~$\I$, $\neg\I$ contains at most {\em seven\/}
normalized spanning intervals.

The intuition behind the above definition is as follows.
First note that the negation of $q\leq_{\alpha}r$ is
$q\geq_{\neg\alpha}r$.
Next note that the extension of~$\I$ contains intervals whose endpoints~$q$
and~$r$ satisfy
$(q\geq_{\gamma}i)\wedge(q\leq_{\delta}j)\wedge(r\geq_{\epsilon}k)\wedge%
(r\leq_{\zeta}l)$.
Thus the extension of $\neg\I$ contains intervals whose endpoints satisfy the
negation of this, namely
$(q\leq_{\neg\gamma}i)\vee(q\geq_{\neg\delta}j)\vee%
(r\leq_{\neg\epsilon}k)\vee(r\geq_{\neg\zeta}l)$.
Such a disjunction requires four spanning intervals, the first four in the
above definition.
Additionally, if the extension of~$\I$ contains intervals of the form $[q,r]$,
the extension of $\neg\I$ will contain all intervals not of the form $[q,r]$,
namely $(q,r]$, $[q,r)$, and $(q,r)$.
Similarly for the cases where the extension of~$\I$ contains intervals of the
form $(q,r]$, $[q,r)$, or $(q,r)$.
This accounts for the last three spanning intervals in the above definition.

We now see why it is necessary to allow spanning intervals to have open ranges
of endpoint values as well as infinite endpoints.
The complement of a spanning interval, such as $[[i,j],[k,l]]$, with closed
endpoint ranges and finite endpoints includes spanning intervals, such as\\%
$[[-\infty,i),[-\infty,\infty]]$, with open endpoint ranges and infinite
endpoints.

\subsection{Computing the Span of two Normalized Spanning Intervals}

The {\sl span} of two intervals~$\I_1$ and~$\I_2$, denoted
$\Span{\I_1}{\I_2}$, is the smallest interval whose extension contains the
extensions of both~$\I_1$ and~$\I_2$.
For example, the span of $(1,4)$ and $[2,6]$ is $(1,6]$.
Similarly, the span of $[3,7)$ and $(3,7]$ is $[3,7]$.
More generally, the lower endpoint of $\Span{\I_1}{\I_2}$ is the minimum of the
lower endpoints of~$\I_1$ and~$\I_2$.
The lower endpoint of $\Span{\I_1}{\I_2}$ is open or closed depending on
whether the smaller of the lower endpoints of~$\I_1$ and~$\I_2$ is open or
closed.
Analogously, the upper endpoint of $\Span{\I_1}{\I_2}$ is the maximum of the
upper endpoints of~$\I_1$ and~$\I_2$.
The upper endpoint of $\Span{\I_1}{\I_2}$ is open or closed depending on
whether the larger of the upper endpoints of~$\I_1$ and~$\I_2$ is open or
closed.
More precisely, $\Span{\I_1}{\I_2}$ can be computed as follows:
\begin{displaymath}
\begin{array}{l}
\Span{\NI{q_1}{r_1}{\alpha_1}{\beta_1}}{\NI{q_2}{r_2}{\alpha_2}{\beta_2}}
\define\\
\;\;\;\;\;\NI{\min(q_1,q_2)}{\max(r_1,r_2)}
{\{[\alpha_1\wedge(q_1\leq q_2)]\vee[\alpha_2\wedge(q_1\geq q_2)]\}}
{\{[\beta_1\wedge(r_1\geq r_2)]\vee[\beta_2\wedge(r_1\leq r_2)]\}}
\end{array}
\end{displaymath}
The notion of span will be used in Section~\ref{spanAllen}.

Let us extend the notion of span to two sets of intervals by the following
definition:
\begin{displaymath}
\Span{I_1}{I_2}\define
\bigcup_{\sI_1\in I_1}\bigcup_{\sI_2\in I_2}\Span{\I_1}{\I_2}
\end{displaymath}
We will want to compute the span of two sets of intervals~$I_1$ and~$I_2$, when
both~$I_1$ and~$I_2$ are represented as spanning intervals.
Additionally, we will want the resulting span to be represented as a small set
of spanning intervals.

Given two normalized spanning intervals~$\I_1$ and~$\I_2$, their {\sl span}
$\Span{\I_1}{\I_2}$ is a set of normalized spanning intervals whose extension
is the span of the extensions of~$\I_1$ and~$\I_2$.
One can compute $\Span{\I_1}{\I_2}$ as follows:
\begin{displaymath}
\begin{array}{l}
\Span{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
         {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
         {\alpha_1}{\beta_1}}
     {\NI{\NI{i_2}{j_2}{\gamma_2}{\delta_2}}
         {\NI{k_2}{l_2}{\epsilon_2}{\zeta_2}}
         {\alpha_2}{\beta_2}}\define\\
\;\;\;\left(\begin{array}{l}
\NORM{\NI{\NI{i_1}{j}{\gamma_1}{\delta}}
         {\NI{k}{l_1}{\epsilon}{\zeta_1}}
         {\alpha_1}{\beta_1}}\cup\\
\NORM{\NI{\NI{i_1}{j}{\gamma_1}{\delta}}
         {\NI{k}{l_2}{\epsilon}{\zeta_2}}
         {\alpha_1}{\beta_2}}\cup\\
\NORM{\NI{\NI{i_2}{j}{\gamma_2}{\delta}}
         {\NI{k}{l_1}{\epsilon}{\zeta_1}}
         {\alpha_2}{\beta_1}}\cup\\
\NORM{\NI{\NI{i_2}{j}{\gamma_2}{\delta}}
         {\NI{k}{l_2}{\epsilon}{\zeta_2}}
         {\alpha_2}{\beta_2}}
\end{array}\right)\\
\;\;\;\mbox{\rm where}
\begin{array}[t]{rcl}
j&=&\min(j_1,j_2)\\
k&=&\max(k_1,k_2)\\
\delta&=&[\delta_1\wedge(j_1\leq j_2)]\vee[\delta_2\wedge(j_1\geq j_2)]\\
\epsilon&=&[\epsilon_1\wedge(k_1\geq k_2)]\vee[\epsilon_2\wedge(k_1\leq k_2)]
\end{array}
\end{array}
\end{displaymath}
An important property of normalized spanning intervals is that for any two
normalized spanning intervals~$\I_1$ and~$\I_2$, $\Span{\I_1}{\I_2}$ contains
at most {\em four\/} normalized spanning intervals.
In practice, however, fewer normalized spanning intervals are needed, often
only one.

The intuition behind the above definition is as follows.
Consider, first, the lower endpoint.
Suppose that the lower endpoints~$q_1$ and~$q_2$ of~$\I_1$ and~$\I_2$ are in
$\NI{i_1}{j_1}{\gamma_1}{\delta_1}$ and $\NI{i_2}{j_2}{\gamma_2}{\delta_2}$
respectively.
That means that $i_1\leq_{\gamma_1}q_1\leq_{\delta_1}j_1$ and
$i_2\leq_{\gamma_2}q_2\leq_{\delta_2}j_2$.
The lower endpoint of $\Span{\I_1}{\I_2}$ will be~$q_1$, when $q_1\leq q_2$,
and~$q_2$, when $q_1\geq q_2$.
Thus it will be~$q_1$, for all
$i_1\leq_{\gamma_1}q_1\leq_{\delta}\min(j_1,j_2)$, and will be~$q_2$,
for all $i_2\leq_{\gamma_2}q_2\leq_{\delta}\min(j_1,j_2)$, where
$\delta=\delta_1$, when $j_1\leq j_2$, and $\delta=\delta_2$,
when $j_1\geq j_2$.
Thus there will be two potential ranges for the lower endpoint of
$\Span{\I_1}{\I_2}$: $\NI{i_1}{\min(j_1,j_2)}{\gamma_1}{\delta}$ and
$\NI{i_2}{\min(j_1,j_2)}{\gamma_2}{\delta}$.
When the lower endpoint of $\Span{\I_1}{\I_2}$ is taken from the former, it
will be open or closed depending on whether the lower endpoint of~$\I_1$ is
open or closed.
When it is taken from the later, it will be open or closed depending on
whether the lower endpoint of $\I_2$ is open or closed.
Thus the lower endpoint of $\Span{\I_1}{\I_2}$ can be either
$_{\alpha_1}[\NI{i_1}{\min(j_1,j_2)}{\gamma_1}{\delta}$ or
$_{\alpha_1}[\NI{i_2}{\min(j_1,j_2)}{\gamma_2}{\delta}$.
Analogous reasoning can be applied to the upper endpoints.
If the upper endpoints of~$\I_1$ and~$\I_2$ are
$\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}]_{\beta_1}$ and
$\NI{k_2}{l_2}{\epsilon_2}{\zeta_2}]_{\beta_2}$ respectively, then there are
two possibilities for the upper endpoint of $\Span{\I_1}{\I_2}$, namely
$\NI{\max(k_1,k_2)}{l_1}{\epsilon}{\zeta_1}]_{\beta_1}$ and
$\NI{\max(k_1,k_2)}{l_2}{\epsilon}{\zeta_2}]_{\beta_2}$, where
$\epsilon=\epsilon_1$, when $k_1\geq k_2$, and $\epsilon=\epsilon_2$, when
$k_1\leq k_2$.

\subsection{Computing the $\cal D$ of a Normalized Spanning Interval}

Given an Allen relation~$r$ and a set~$I$ of intervals, let $\D{r}{I}$ denote
the set~$J$ of all intervals~$\J$ such that $\I r\J$ for some $\I\in I$\@.
Given an Allen relation~$r$ and a normalized spanning interval~$\I$, let
$\D{r}{\I}$ denote a set of normalized spanning intervals whose extension is
$\D{r}{I}$, where~$I$ is the extension of~$\I$.
One can compute $\D{r}{\I}$ as follows:
\begin{eqnarray*}
\D{=}{\I}&\define&
\theset{\I}\\
\D{<}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\alpha_2,\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{k_1}{\infty}
             {(\neg\beta_1\wedge\neg\alpha_2\wedge\epsilon_1)}{\TRUE}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\alpha_2}{\beta_2}}\\
\D{>}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\alpha_2,\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{-\infty}{j_1}
             {\TRUE}{(\neg\alpha_1\wedge\neg\beta_2\wedge\delta_1)}}
         {\alpha_2}{\beta_2}}\\
\D{\AllenmF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
         {\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\neg\beta_1}{\beta_2}}\\
\D{\AllenmiF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\alpha_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{-\infty}{\infty}{\TRUE}{\TRUE}}
         {\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
         {\alpha_2}{\neg\alpha_1}}\\
\D{\AllenoF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&\\
\lefteqn{\hspace{-1.5in}\bigcup_{\alpha_2,\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{i_1}{l_1}
             {(\alpha_1\wedge\neg\alpha_2\wedge\gamma_1)}
             {(\beta_1\wedge\alpha_2\wedge\zeta_1)}}
         {\NI{k_1}{\infty}
             {(\neg\beta_1\wedge\beta_2\wedge\epsilon_1)}{\TRUE}}
         {\alpha_2}{\beta_2}}}\\
\D{\AllenoiF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&\\
\lefteqn{\hspace{-1.5in}\bigcup_{\alpha_2,\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{-\infty}{j_1}
             {\TRUE}{(\neg\alpha_1\wedge\alpha_2\wedge\delta_1)}}
         {\NI{i_1}{l_1}
             {(\alpha_1\wedge\beta_2\wedge\gamma_1)}
             {(\beta_1\wedge\neg\beta_2\wedge\zeta_1)}}
         {\alpha_2}{\beta_2}}}\\
\D{\AllensF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
         {\NI{k_1}{\infty}
             {(\neg\beta_1\wedge\beta_2\wedge\epsilon_1)}{\TRUE}}
         {\alpha_1}{\beta_2}}\\
\D{\AllensiF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
         {\NI{-\infty}{l_1}
             {\TRUE}{(\beta_1\wedge\neg\beta_2\wedge\zeta_1)}}
         {\alpha_1}{\beta_2}}\\
\D{\AllenfF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\alpha_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{-\infty}{j_1}
             {\TRUE}{(\neg\alpha_1\wedge\alpha_2\wedge\delta_1)}}
         {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
         {\alpha_2}{\beta_1}}\\
\D{\AllenfiF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&
\bigcup_{\alpha_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{i_1}{\infty}
             {(\alpha_1\wedge\neg\alpha_2\wedge\gamma_1)}{\TRUE}}
         {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
         {\alpha_2}{\beta_1}}\\
\D{\AllendF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&\\
\lefteqn{\hspace{-1.5in}\bigcup_{\alpha_2,\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{-\infty}{j_1}
             {\TRUE}{(\neg\alpha_1\wedge\alpha_2\wedge\delta_1)}}
         {\NI{k_1}{\infty}
             {(\neg\beta_1\wedge\beta_2\wedge\epsilon_1)}{\TRUE}}
         {\alpha_2}{\beta_2}}}\\
\D{\AllendiF}
{\NI{\NI{i_1}{j_1}{\gamma_1}{\delta_1}}
    {\NI{k_1}{l_1}{\epsilon_1}{\zeta_1}}
    {\alpha_1}{\beta_1}}&\define&\\
\lefteqn{\hspace{-1.5in}\bigcup_{\alpha_2,\beta_2\in\theset{\TRUE,\FALSE}}
\NORM{\NI{\NI{i_1}{\infty}
             {(\alpha_1\wedge\neg\alpha_2\wedge\gamma_1)}{\TRUE}}
         {\NI{-\infty}{l_1}
             {\TRUE}{(\beta_1\wedge\neg\beta_2\wedge\zeta_1)}}
         {\alpha_2}{\beta_2}}}
\end{eqnarray*}
An important property of normalized spanning intervals is that for any
normalized spanning interval~$\I$, $\D{r}{\I}$ contains at most~$1$, $4$, $4$,
$2$, $2$, $4$, $4$, $2$, $2$, $2$, $2$, $4$, or~$4$ normalized spanning
intervals when~$r$ is~$=$, $<$, $>$, $\AllenmF$, $\AllenmiF$, $\AllenoF$,
$\AllenoiF$, $\AllensF$, $\AllensiF$, $\AllenfF$, $\AllenfiF$, $\AllendF$,
or~$\AllendiF$ respectively.
In practice, however, fewer normalized spanning intervals are needed, often
only one.

The intuition behind the above definition is as follows.
Let us handle each of the cases separately.
\begin{description}
\item[$r=<$] For any intervals~$\I'_1$ and~$\I'_2$ in the extensions of~$\I_1$
and~$\I_2$ respectively we want $\I'_1<\I'_2$.
From~(\ref{ltdef}) we get $r_1\leq_{(\neg\beta_1\wedge\neg\alpha_2)}q_2$.
Furthermore, from~(\ref{spandef}) we get $k_1\leq_{\epsilon_1}r_1$.
Combining these we get
$k_1\leq_{(\neg\beta_1\wedge\neg\alpha_2\wedge\epsilon_1)}q_2$.
In this case, both~$\alpha_2$ and~$\beta_2$ are free indicating that either
endpoint of~$\I'_2$ can be open or closed.
\item[$r=>$] For any intervals~$\I'_1$ and~$\I'_2$ in the extensions of~$\I_1$
and~$\I_2$ respectively we want $\I'_1>\I'_2$.
From~(\ref{gtdef}) we get $q_1\geq_{(\neg\alpha_1\wedge\neg\beta_2)}r_2$.
Furthermore, from~(\ref{spandef}) we get $q_1\leq_{\delta_1}j_1$.
Combining these we get
$r_2\leq_{(\neg\alpha_1\wedge\neg\beta_2\wedge\delta_1)}j_1$.
In this case, both~$\alpha_2$ and~$\beta_2$ are free indicating that either
endpoint of~$\I'_2$ can be open or closed.
\item[$r=\AllenmF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allenm{\I'_1}{\I'_2}$.
From~(\ref{mdef}) we get $r_1=q_2$ and $\beta_1\not=\alpha_2$.
Furthermore, from~(\ref{spandef}) we get
$k_1\leq_{\epsilon_1}r_1\leq_{\zeta_1}l_1$.
Combining these we get
$k_1\leq_{\epsilon_1}q_2\leq_{\zeta_1}l_1$ and $\beta_1\not=\alpha_2$.
In this case, only~$\beta_2$ is free indicating that the upper endpoint
of~$\I'_2$ can be open or closed.
\item[$r=\AllenmiF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allenmi{\I'_1}{\I'_2}$.
From~(\ref{midef}) we get $q_1=r_2$ and $\alpha_1\not=\beta_2$.
Furthermore, from~(\ref{spandef}) we get
$i_1\leq_{\gamma_1}q_1\leq_{\delta_1}j_1$.
Combining these we get
$i_1\leq_{\gamma_1}r_2\leq_{\delta_1}j_1$ and $\alpha_1\not=\beta_2$.
In this case, only~$\alpha_2$ is free indicating that the lower endpoint
of~$\I'_2$ can be open or closed.
\item[$r=\AllenoF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Alleno{\I'_1}{\I'_2}$.
From~(\ref{odef}) we get
$q_1\leq_{(\alpha_1\wedge\neg\alpha_2)}q_2\leq_{(\beta_1\wedge\alpha_2)}r_1%
\leq_{(\neg\beta_1\wedge\beta_2)}r_2$.
Furthermore, from~(\ref{spandef}) we get $i_1\leq_{\gamma_1}q_1$ and
$k_1\leq_{\epsilon_1}r_1\leq_{\zeta_1}l_1$.
Combining these we get
$i_1\leq_{(\alpha_1\wedge\neg\alpha_2\wedge\gamma_1)}q_2%
\leq_{(\beta_1\wedge\alpha_2\wedge\zeta_1)}l_1$
and
$k_1\leq_{(\neg\beta_1\wedge\beta_2\wedge\epsilon_1)}r_2$.
In this case, both~$\alpha_2$ and~$\beta_2$ are free indicating that either
endpoint of~$\I'_2$ can be open or closed.
\item[$r=\AllenoiF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allenoi{\I'_1}{\I'_2}$.
From~(\ref{oidef}) we get
$q_2\leq_{(\neg\alpha_1\wedge\alpha_2)}q_1\leq_{(\alpha_1\wedge\beta_2)}r_2%
\leq_{(\beta_1\wedge\neg\beta_2)}r_1$.
Furthermore, from~(\ref{spandef}) we get $r_1\leq_{\zeta_1}l_1$ and
$i_1\leq_{\gamma_1}q_1\leq_{\delta_1}j_1$.
Combining these we get
$i_1\leq_{(\alpha_1\wedge\beta_2\wedge\gamma_1)}r_2%
\leq_{(\beta_1\wedge\neg\beta_2\wedge\zeta_1)}l_1$
and
$q_2\leq_{(\neg\alpha_1\wedge\alpha_2\wedge\delta_1)}j_1$.
In this case, both~$\alpha_2$ and~$\beta_2$ are free indicating that either
endpoint of~$\I'_2$ can be open or closed.
\item[$r=\AllensF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allens{\I'_1}{\I'_2}$.
From~(\ref{sdef}) we get $q_1=q_2$, $\alpha_1=\alpha_2$, and
$r_1\leq_{(\neg\beta_1\wedge\beta_2)}r_2$.
Furthermore, from~(\ref{spandef}) we get
$i_1\leq_{\gamma_1}q_1\leq_{\delta_1}j_1$ and $k_1\leq_{\epsilon_1}r_1$.
Combining these we get $\alpha_1=\alpha_2$,
$i_1\leq_{\gamma_1}q_2\leq_{\delta_1}j_1$, and
$k_1\leq_{(\neg\beta_1\wedge\beta_2\wedge\epsilon_1)}r_2$.
In this case, only~$\beta_2$ is free indicating that the upper endpoint
of~$\I'_2$ can be open or closed.
\item[$r=\AllensiF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allensi{\I'_1}{\I'_2}$.
From~(\ref{sidef}) we get $q_1=q_2$, $\alpha_1=\alpha_2$, and
$r_1\geq_{(\beta_1\wedge\neg\beta_2)}r_2$.
Furthermore, from~(\ref{spandef}) we get
$i_1\leq_{\gamma_1}q_1\leq_{\delta_1}j_1$ and $r_1\leq_{\zeta_1}l_1$.
Combining these we get $\alpha_1=\alpha_2$,
$i_1\leq_{\gamma_1}q_2\leq_{\delta_1}j_1$, and
$r_2\leq_{(\beta_1\wedge\neg\beta_2\wedge\zeta_1)}l_1$.
In this case, only~$\beta_2$ is free indicating that the upper endpoint
of~$\I'_2$ can be open or closed.
\item[$r=\AllenfF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allenf{\I'_1}{\I'_2}$.
From~(\ref{fdef}) we get $q_1\geq_{(\neg\alpha_1\wedge\alpha_2)}q_2$,
$r_1=r_2$, and $\beta_1=\beta_2$.
Furthermore, from~(\ref{spandef}) we get
$k_1\leq_{\epsilon_1}r_1\leq_{\zeta_1}l_1$ and $q_1\leq_{\delta_1}j_1$.
Combining these we get $\beta_1=\beta_2$,
$k_1\leq_{\epsilon_1}r_2\leq_{\zeta_1}l_1$, and
$q_2\leq_{(\neg\alpha_1\wedge\alpha_2\wedge\delta_1)}j_1$.
In this case, only~$\alpha_2$ is free indicating that the lower endpoint
of~$\I'_2$ can be open or closed.
\item[$r=\AllenfiF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allenfi{\I'_1}{\I'_2}$.
From~(\ref{fidef}) we get $q_1\geq_{(\alpha_1\wedge\neg\alpha_2)}q_2$,
$r_1=r_2$, and $\beta_1=\beta_2$.
Furthermore, from~(\ref{spandef}) we get
$k_1\leq_{\epsilon_1}r_1\leq_{\zeta_1}l_1$ and $i_1\leq_{\gamma_1}q_1$.
Combining these we get $\beta_1=\beta_2$,
$k_1\leq_{\epsilon_1}r_2\leq_{\zeta_1}l_1$, and
$i_1\leq_{(\alpha_1\wedge\neg\alpha_2\wedge\gamma_1)}q_2$.
In this case, only~$\alpha_2$ is free indicating that the lower endpoint
of~$\I'_2$ can be open or closed.
\item[$r=\AllendF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allend{\I'_1}{\I'_2}$.
From~(\ref{ddef}) we get $q_1\geq_{(\neg\alpha_1\wedge\alpha_2)}q_2$ and
$r_1\leq_{(\neg\beta_1\wedge\beta_2)}r_2$.
Furthermore, from~(\ref{spandef}) we get $q_1\leq_{\delta_1}j_1$ and
$k_1\leq_{\epsilon_1}r_1$.
Combining these we get
$q_2\leq_{(\neg\alpha_1\wedge\alpha_2\wedge\delta_1)}j_1$ and
$k_1\leq_{(\neg\beta_1\wedge\beta_2\wedge\epsilon_1)}r_2$.
In this case, both~$\alpha_2$ and~$\beta_2$ are free indicating that either
endpoint of~$\I'_2$ can be open or closed.
\item[$r=\AllendiF$] For any intervals~$\I'_1$ and~$\I'_2$ in the
extensions of~$\I_1$ and~$\I_2$ respectively we want
$\Allendi{\I'_1}{\I'_2}$.
From~(\ref{didef}) we get $q_1\leq_{(\alpha_1\wedge\neg\alpha_2)}q_2$ and
$r_1\geq_{(\beta_1\wedge\neg\beta_2)}r_2$.
Furthermore, from~(\ref{spandef}) we get $i_1\leq_{\gamma_1}q_1$ and
$r_1\leq_{\zeta_1}l_1$.
Combining these we get
$i_1\leq_{(\alpha_1\wedge\neg\alpha_2\wedge\gamma_1)}q_2$ and
$r_2\leq_{(\beta_1\wedge\neg\beta_2\wedge\zeta_1)}l_1$.
In this case, both~$\alpha_2$ and~$\beta_2$ are free indicating that either
endpoint of~$\I'_2$ can be open or closed.
\end{description}

\subsection{Computing the $\cal I$ of two Normalized Spanning Intervals}
\label{spanAllen}

Given an Allen relation~$r$ and two sets~$I$ and~$J$ of intervals, let
$\II{I}{r}{J}$ denote the set~$K$ of all intervals~$\K$ such that
$\K=\Span{\I}{\J}$ for some $\I\in I$ and $\J\in J$, where $\I r\J$.
Given an Allen relation~$r$ and two normalized spanning intervals~$\I$
and~$\J$, let $\II{\I}{r}{\J}$ denote a set of normalized spanning intervals
whose extension is $\II{I}{r}{J}$, where~$I$ and~$J$ are the extensions
of~$\I$ and~$\J$ respectively.
One can compute $\II{\I}{r}{\J}$ as follows:
\begin{displaymath}
\II{\I}{r}{\J}\define
\bigcup_{\sI'\in\D{r^{-1}}{\sJ}}
\bigcup_{\sI''\in\sI'\cap\sI}
\bigcup_{\sJ'\in\D{r}{\sI}}
\bigcup_{\sJ''\in\sJ'\cap\sJ}
\Span{\I''}{\J''}
\end{displaymath}
Here, $r^{-1}$ denotes the inverse relation corresponding to~$r$, i.e.~the
same relation as~$r$ but with the arguments reversed.
It is easy to see that $|\II{\cdot}{r}{\cdot}|\leq4|\D{r}{\cdot}|^2$.
Thus an important property of normalized spanning intervals is that for any
two normalized spanning intervals~$\I$ and~$\J$, $\II{\I}{r}{\J}$ contains at
most~$4$, $64$, $64$, $16$, $16$, $64$, $64$, $16$, $16$, $16$, $16$, $64$,
or~$64$ normalized spanning intervals, when~$r$ is~$=$, $<$, $>$, $\AllenmF$,
$\AllenmiF$, $\AllenoF$, $\AllenoiF$, $\AllensF$, $\AllensiF$, $\AllenfF$,
$\AllenfiF$, $\AllendF$, or~$\AllendiF$ respectively.
While simple combinatorial enumeration yields the above weak bounds on the
number of normalized spanning intervals needed to represent $\II{\I}{r}{\J}$,
in practice, far fewer normalized spanning intervals are needed, in most cases
only one.

The intuition behind the above definition is as follows.
Let~$I$ and~$J$ be the extensions of~$\I$ and~$\J$ respectively.
The extension of the set of all~$\I'$ is the set of all intervals~$\I$ such
that $\I r\J$ for some~$\J$ in~$J$\@.
Furthermore, the extension of the set of all~$\I''$ is the set of all
intervals~$\I$ in~$I$ such that $\I r\J$ for some~$\J$ in~$J$\@.
Similarly, the extension of the set of all~$\J'$ is the set of all
intervals~$\J$ such that $\I r\J$ for some~$\I$ in~$I$\@.
Analogously, the extension of the set of all~$\J''$ is the set of all
intervals~$\J$ in~$J$ such that $\I r\J$ for some~$\I$ in~$I$\@.
Thus the extension of the set of all $\Span{\I''}{\J''}$ is the set of all
intervals~$\K$ such that $\K=\Span{\I}{\J}$ where~$\I$ is in~$I$, $\J$ is
in~$J$, and $\I r\J$.

\subsection{An Efficient Inference Procedure for Event Logic}

Given the above procedures for computing~$\NORM{\I}$, $\I_1\cap\I_2$,
$\neg\I$, $\Span{\I_1}{\I_2}$, $\D{r}{\I}$, and $\II{\I}{r}{\J}$, one can
now define a procedure for computing $\E{M}{\Phi}$.
This procedure takes a model~$M$ along with an event-logic expression~$\Phi$
and computes a set of normalized spanning intervals that represents the
set~$I$ of intervals~$\I$ for which $\Phi@\I$ is true.
The model~$M$ is a set of atomic event-occurrence formulae of the form
$p(c_1,\ldots,c_n)@\I$, where $p(c_1,\ldots,c_n)$ is a ground primitive
event-logic expression and~$\I$ is a normalized spanning interval.
A model entry $p(c_1,\ldots,c_n)@\I$ indicates that the primitive event
$p(c_1,\ldots,c_n)$ occurred during all intervals in the extension of~$\I$.
\begin{eqnarray*}
\E{M}{p(c_1,\ldots,c_n)}&\define&\theset{\I|p(c_1,\ldots,c_n)@\I\in M}\\
\E{M}{\Phi\vee\Psi}&\define&\E{M}{\Phi}\cup\E{M}{\Psi}\\
\E{M}{\neg\Phi}&\define&
\begin{array}[t]{l}
\displaystyle
\bigcup_{\sI'_1\in\neg\sI_1}\cdots
\bigcup_{\sI'_n\in\neg\sI_n}\I'_1\cap\cdots\cap\I'_n\\
\mbox{\rm where}\;\E{M}{\Phi}=\theset{\I_1,\ldots,\I_n}
\end{array}\\
\E{M}{\Phi\wedge_R\Psi}&\define&
\bigcup_{\sI\in\E{M}{\Phi}}\bigcup_{\sJ\in\E{M}{\Psi}}
\bigcup_{r\in R}\II{\I}{r}{\J}\\
\E{M}{\Diamond_R\Phi}&\define&
\bigcup_{\sI\in\E{M}{\Phi}}\bigcup_{r\in R}\D{r}{\I}
\end{eqnarray*}
The procedure performs structural induction on~$\Phi$.
It computes a set of normalized spanning intervals to the represent the
occurrence of each atomic event-logic expression in~$\Phi$ and recursively
combines the sets so computed for each child subexpression to yield the sets
for each parent subexpression.
An important property of this inference procedure is that for any finite
model~$M$, $\E{M}{\Phi}$, the set~$I$ of intervals~$\I$ for which $\Phi@\I$ is
true, can be represented by a finite set of normalized spanning intervals.
Nominally, the number of normalized spanning intervals in $\E{M}{\Phi}$ can be
exponential in the subexpression depth of~$\Phi$ because each step in the
structural induction can introduce a constant factor growth in the size of the
set.
However, in practice, such exponential growth does not occur.
Computing $\E{M}{\Phi}$ for all of the event types given in
Figure~\ref{compoundEventTypes} for all of the movies that have been tried so
far have yielded sets of fewer than a dozen normalized spanning intervals.

\section{Experimental Results}
\label{experimentalResults}

The techniques described in this paper have been implemented as a system
called \Leonard\ and tested on a number of video
sequences.\footnote{The code for \Leonard, the video input
sequences discussed in this paper, and the full frame-by-frame output of
\Leonard\ on those sequences is available as Online Appendix~1, as well as
from\\%
{\tt ftp://ftp.nj.nec.com/pub/qobi/leonard.tar.Z}\@.}
\Leonard\ successfully recognizes the events {\em pick up}, {\em put down},
{\em stack}, {\em unstack}, {\em move}, {\em assemble}, and {\em disassemble\/}
using the definitions given in Figure~\ref{compoundEventTypes}.
Figures~\ref{videoOne} and~\ref{videoThreeA} through~\ref{videoThreeE} show
the key frames from movies that depict these seven event types.
These movies were filmed using a Canon VC-C3 camera and a Matrox Meteor frame
grabber at 320$\times$240 resolution at 30fps.
Figures~\ref{modelReconstructionOne} and~\ref{modelReconstructionThreeA}
through~\ref{modelReconstructionThreeE} show the results of segmentation,
tracking, and model reconstruction for those key frames superimposed on the
original images.
Figures~\ref{eventClassificationOne} and~\ref{eventClassificationThreeA}
through~\ref{eventClassificationThreeE} show the results of event
classification for these movies.
These figures show \Leonard\ correctly recognizing the intended event classes
for each movie.

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{stack00-3-image-and-most-preferred-model}&
\figpercent{30}{stack00-11-image-and-most-preferred-model}&
\figpercent{30}{stack00-12-image-and-most-preferred-model}&
\figpercent{30}{stack00-23-image-and-most-preferred-model}\\
Frame 3&
Frame 11&
Frame 12&
Frame 23\\
\figpercent{30}{stack00-24-image-and-most-preferred-model}&
\figpercent{30}{stack00-26-image-and-most-preferred-model}\\
Frame 24&
Frame 26
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components applied to the image sequence from
Figure~\protect\ref{videoThreeA}, an image sequence that depicts a
{\em stack\/} event.}
\label{modelReconstructionThreeA}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{unstack00-1-image-and-most-preferred-model}&
\figpercent{30}{unstack00-10-image-and-most-preferred-model}&
\figpercent{30}{unstack00-11-image-and-most-preferred-model}&
\figpercent{30}{unstack00-24-image-and-most-preferred-model}\\
Frame 1&
Frame 10&
Frame 11&
Frame 24\\
\figpercent{30}{unstack00-25-image-and-most-preferred-model}&
\figpercent{30}{unstack00-29-image-and-most-preferred-model}\\
Frame 25&
Frame 29
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components applied to the image sequence from
Figure~\protect\ref{videoThreeB}, an image sequence that depicts an
{\em unstack\/} event.}
\label{modelReconstructionThreeB}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{move00-0-image-and-most-preferred-model}&
\figpercent{30}{move00-8-image-and-most-preferred-model}&
\figpercent{30}{move00-9-image-and-most-preferred-model}&
\figpercent{30}{move00-16-image-and-most-preferred-model}\\
Frame 0&
Frame 8&
Frame 9&
Frame 16\\
\figpercent{30}{move00-17-image-and-most-preferred-model}&
\figpercent{30}{move00-33-image-and-most-preferred-model}&
\figpercent{30}{move00-34-image-and-most-preferred-model}&
\figpercent{30}{move00-45-image-and-most-preferred-model}\\
Frame 17&
Frame 33&
Frame 34&
Frame 45\\
\figpercent{30}{move00-46-image-and-most-preferred-model}&
\figpercent{30}{move00-47-image-and-most-preferred-model}\\
Frame 46&
Frame 47
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components applied to the image sequence from
Figure~\protect\ref{videoThreeC}, an image sequence that depicts a
{\em move\/} event.}
\label{modelReconstructionThreeC}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{assemble00-0-image-and-most-preferred-model}&
\figpercent{30}{assemble00-9-image-and-most-preferred-model}&
\figpercent{30}{assemble00-10-image-and-most-preferred-model}&
\figpercent{30}{assemble00-17-image-and-most-preferred-model}\\
Frame 0&
Frame 9&
Frame 10&
Frame 17\\
\figpercent{30}{assemble00-18-image-and-most-preferred-model}&
\figpercent{30}{assemble00-32-image-and-most-preferred-model}&
\figpercent{30}{assemble00-33-image-and-most-preferred-model}&
\figpercent{30}{assemble00-40-image-and-most-preferred-model}\\
Frame 18&
Frame 32&
Frame 33&
Frame 40\\
\figpercent{30}{assemble00-41-image-and-most-preferred-model}&
\figpercent{30}{assemble00-46-image-and-most-preferred-model}&
\figpercent{30}{assemble00-47-image-and-most-preferred-model}&
\figpercent{30}{assemble00-56-image-and-most-preferred-model}\\
Frame 41&
Frame 46&
Frame 47&
Frame 56\\
\figpercent{30}{assemble00-57-image-and-most-preferred-model}&
\figpercent{30}{assemble00-67-image-and-most-preferred-model}&
\figpercent{30}{assemble00-68-image-and-most-preferred-model}&
\figpercent{30}{assemble00-80-image-and-most-preferred-model}\\
Frame 57&
Frame 67&
Frame 68&
Frame 80
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components applied to the image sequence from
Figure~\protect\ref{videoThreeD}, an image sequence that depicts an
{\em assemble\/} event.}
\label{modelReconstructionThreeD}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{disassemble00-18-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-19-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-22-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-23-image-and-most-preferred-model}\\
Frame 18&
Frame 19&
Frame 22&
Frame 23\\
\figpercent{30}{disassemble00-49-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-50-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-56-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-57-image-and-most-preferred-model}\\
Frame 49&
Frame 50&
Frame 56&
Frame 57\\
\figpercent{30}{disassemble00-62-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-63-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-87-image-and-most-preferred-model}&
\figpercent{30}{disassemble00-88-image-and-most-preferred-model}\\
Frame 62&
Frame 63&
Frame 87&
Frame 88
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components applied to the image sequence from
Figure~\protect\ref{videoThreeE}, an image sequence that depicts a
{\em disassemble\/} event.}
\label{modelReconstructionThreeE}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PUT-DOWN MOVING RED BLUE)@\symbol{123}[[0,12],[24,30])\symbol{125}\\
(STACK MOVING RED BLUE GREEN)@\symbol{123}[[0,12],[24,30])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[13:24])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:30])\symbol{125}\\
(SUPPORTED?\ BLUE)@\symbol{123}[[0:30])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[0:12])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[13:24])\symbol{125}\\
(SUPPORTS?\ RED BLUE)@\symbol{123}[[19:20]), [[21:22])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[19:20]), [[21:22])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[19:20]), [[21:22])\symbol{125}\\
(SUPPORTS?\ GREEN BLUE)@\symbol{123}[[0:30])\symbol{125}\\
(SUPPORTS?\ BLUE MOVING)@\symbol{123}[[13:24])\symbol{125}\\
(SUPPORTS?\ BLUE RED)@\symbol{123}[[12:30])\symbol{125}\\
(CONTACTS?\ RED BLUE)@\symbol{123}[[12:19]), [[20:21]), [[22:30])\symbol{125}\\
(CONTACTS?\ GREEN BLUE)@\symbol{123}[[0:30])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[0:24])\symbol{125}\\
(ATTACHED?\ RED BLUE)@\symbol{123}[[19:20]), [[21:22])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionThreeA}.
Note that the {\em stack\/} event is correctly recognized, as well as the
constituent {\em put down\/} event.}
\label{eventClassificationThreeA}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED BLUE)@\symbol{123}[[0,11],[25,33])\symbol{125}\\
(UNSTACK MOVING RED BLUE GREEN)@\symbol{123}[[0,11],[25,33])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[11:23])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:36])\symbol{125}\\
(SUPPORTED?\ BLUE)@\symbol{123}[[0:36])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[23:36])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[11:23])\symbol{125}\\
(SUPPORTS?\ RED BLUE)@\symbol{123}[[13:14])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[13:14])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[13:14])\symbol{125}\\
(SUPPORTS?\ GREEN BLUE)@\symbol{123}[[0:36])\symbol{125}\\
(SUPPORTS?\ BLUE MOVING)@\symbol{123}[[11:23])\symbol{125}\\
(SUPPORTS?\ BLUE RED)@\symbol{123}[[0:25])\symbol{125}\\
(CONTACTS?\ MOVING RED)@\symbol{123}[[34:36])\symbol{125}\\
(CONTACTS?\ RED BLUE)@\symbol{123}[[0:13]), [[14:24])\symbol{125}\\
(CONTACTS?\ GREEN BLUE)@\symbol{123}[[0:13]), [[14:36])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[11:33])\symbol{125}\\
(ATTACHED?\ RED BLUE)@\symbol{123}[[13:14])\symbol{125}\\
(ATTACHED?\ GREEN BLUE)@\symbol{123}[[13:14])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionThreeB}.
Note that the {\em unstack\/} event is correctly recognized, as well as the
constituent {\em pick up\/} event.}
\label{eventClassificationThreeB}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[0,9],[17,46])\symbol{125}\\
(PUT-DOWN MOVING RED BLUE)@\symbol{123}[[17,35],[46,52])\symbol{125}\\
(MOVE MOVING RED GREEN BLUE)@\symbol{123}[[0,9],[46,52])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[9:15])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:52])\symbol{125}\\
(SUPPORTED?\ BLUE)@\symbol{123}[[35:46])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[17:46])\symbol{125}\\
(SUPPORTS?\ MOVING BLUE)@\symbol{123}[[35:46])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[9:15])\symbol{125}\\
(SUPPORTS?\ RED BLUE)@\symbol{123}[[35:46])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[9:15])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:17])\symbol{125}\\
(SUPPORTS?\ BLUE RED)@\symbol{123}[[46:52])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:17])\symbol{125}\\
(CONTACTS?\ RED BLUE)@\symbol{123}[[46:52])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[9:46])\symbol{125}\\
(ATTACHED?\ RED BLUE)@\symbol{123}[[35:46])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionThreeC}.
Note that the {\em move\/} event is correctly recognized, as well as the
constituent {\em pick up\/} and {\em put down\/} subevents.}
\label{eventClassificationThreeC}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PUT-DOWN MOVING RED GREEN)@\symbol{123}[[57,68],[68,87])\symbol{125}\\
(PUT-DOWN MOVING GREEN BLUE)@\symbol{123}[[18,35],[41,47])\symbol{125}\\
(STACK MOVING RED GREEN BLUE)@\symbol{123}[[57,68],[68,87])\symbol{125}\\
(ASSEMBLE MOVING RED GREEN BLUE)@\symbol{123}[[18,35],[68,87])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[10:18]), [[47:57])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[57:87])\symbol{125}\\
(SUPPORTED?\ GREEN)@\symbol{123}[[11:87])\symbol{125}\\
(SUPPORTED?\ BLUE)@\symbol{123}[[35:41])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[57:68])\symbol{125}\\
(SUPPORTS?\ MOVING GREEN)@\symbol{123}[[11:41])\symbol{125}\\
(SUPPORTS?\ MOVING BLUE)@\symbol{123}[[35:41])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[10:18]), [[47:57])\symbol{125}\\
(SUPPORTS?\ RED GREEN)@\symbol{123}[[11:16])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[68:87])\symbol{125}\\
(SUPPORTS?\ GREEN BLUE)@\symbol{123}[[35:41])\symbol{125}\\
(SUPPORTS?\ BLUE GREEN)@\symbol{123}[[41:87])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[68:87])\symbol{125}\\
(CONTACTS?\ GREEN BLUE)@\symbol{123}[[41:87])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[11:16]), [[49:68])\symbol{125}\\
(ATTACHED?\ MOVING GREEN)@\symbol{123}[[11:41])\symbol{125}\\
(ATTACHED?\ GREEN BLUE)@\symbol{123}[[35:41])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionThreeD}.
Note that the {\em assemble\/} event is correctly recognized, as well as the
constituent {\em put down\/} and {\em stack\/} subevents.}
\label{eventClassificationThreeD}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[0,19],[23,50])\symbol{125}\\
(PICK-UP MOVING GREEN BLUE)@\symbol{123}[[22,58],[62,87])\symbol{125}\\
(UNSTACK MOVING RED GREEN BLUE)@\symbol{123}[[0,19],[23,50])\symbol{125}\\
(DISASSEMBLE MOVING RED GREEN BLUE)@\symbol{123}[[0,19],[62,87])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[19:22])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:50])\symbol{125}\\
(SUPPORTED?\ GREEN)@\symbol{123}[[0:87])\symbol{125}\\
(SUPPORTED?\ BLUE)@\symbol{123}[[58:62])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[23:50])\symbol{125}\\
(SUPPORTS?\ MOVING GREEN)@\symbol{123}[[58:87])\symbol{125}\\
(SUPPORTS?\ MOVING BLUE)@\symbol{123}[[58:62])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[19:22])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[19:22])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:23])\symbol{125}\\
(SUPPORTS?\ GREEN BLUE)@\symbol{123}[[58:62])\symbol{125}\\
(SUPPORTS?\ BLUE GREEN)@\symbol{123}[[0:58])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:23])\symbol{125}\\
(CONTACTS?\ GREEN BLUE)@\symbol{123}[[0:58])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[19:50])\symbol{125}\\
(ATTACHED?\ MOVING GREEN)@\symbol{123}[[58:87])\symbol{125}\\
(ATTACHED?\ GREEN BLUE)@\symbol{123}[[58:62])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionThreeE}.
Note that the {\em disassemble\/} event is correctly recognized, as well as
the constituent {\em pick up\/} and {\em unstack\/} subevents.}
\label{eventClassificationThreeE}
\end{figure}

In Figure~\ref{modelReconstructionOne}(a), Frames~0 through~1 correspond to
the first subevent of a {\em pick up\/} event, Frames~2 through~13 correspond
to the second subevent, and Frames~14 through~22 correspond to the third
subevent.
In Figure~\ref{modelReconstructionOne}(b), Frames~0 through~13 correspond to
the first subevent of a {\em put down\/} event, Frames~14 through~22 correspond
to the second subevent, and Frames~23 through~32 correspond to the third
subevent.
\Leonard\ correctly recognizes these as instances of {\em pick up\/} and
{\em put down\/} respectively.
In Figure~\ref{modelReconstructionThreeA}, Frames~0 through~11, 12
through~23, and~24 through~30 correspond to the three subevents of a
{\em put down\/} event.
\Leonard\ correctly recognizes this as a {\em put down\/} event and also as a
{\em stack\/} event.
In Figure~\ref{modelReconstructionThreeB}, Frames~0 through~10, 11
through~24, and~25 through~33 correspond to the three subevents of a
{\em pick up\/} event.
\Leonard\ correctly recognizes this as a {\em pick up\/} event and also as an
{\em unstack\/} event.
In Figure~\ref{modelReconstructionThreeC}, Frames~0 through~8, 9
through~16, and~17 through~45 correspond to the three subevents of a
{\em pick up\/} event and Frames~17 through~33, 34 through~45, and~46
through~52 correspond to the three subevents of a {\em put down\/} event.
\Leonard\ correctly recognizes the combination of these two events as a
{\em move\/} event.
In Figure~\ref{modelReconstructionThreeD}, Frames~18 through~32, 33
through~40, and~41 through~46 correspond to the three subevents of a
{\em put down\/} event and Frames~57 through~67 and~68 through~87
correspond to the first and third subevents of a second {\em put down\/} event,
with the second subevent being empty.
The second {\em put down\/} event is also correctly recognized as a
{\em stack\/} event and the combination of these two events is correctly
recognized as an {\em assemble\/} event.
In Figure~\ref{modelReconstructionThreeE}, Frames~0 through~18, 19
through~22, and~23 through~50 correspond to the three subevents of a
{\em pick up\/} event and Frames~23 through~56, 57 through~62, and~63
through~87 correspond to the three subevents of a second {\em pick up\/} event.
The first {\em pick up\/} event is also correctly recognized as an
{\em unstack\/} event and the combination of these two events is correctly
recognized as a {\em disassemble\/} event.
These examples show that \Leonard\ correctly recognizes each of the seven
event types with no false positives.

As discussed in the introduction, using force dynamics and event logic to
recognize events offers several advantages over the prior approach of using
motion profile and hidden Markov models.
\begin{itemize}
\item robustness against variance in motion profile
\item robustness against presence of extraneous objects in the field of view
\item ability to perform temporal and spatial segmentation of events
\item ability to detect non-occurrence of events
\end{itemize}
Figures~\ref{modelReconstructionFourA} through~\ref{eventClassificationTwo}
illustrate these advantages.
Figure~\ref{modelReconstructionFourA} shows a {\em pick up\/} event from
the left in contrast to Figure~\ref{modelReconstructionOne}(a) which is from
the right.
Even though these have different motion profiles,
Figure~\ref{eventClassificationFourA} shows that \Leonard\ correctly
recognizes that these exhibit the same sequence of changes in force-dynamic
relations and constitute the same event type, namely {\em pick up}.
Figure~\ref{modelReconstructionFourB} shows a {\em pick up\/} event with
two extraneous blocks in the field of view.
Figure~\ref{eventClassificationFourB} shows that \Leonard\ correctly
recognizes that these extraneous blocks do not participate in any events and,
despite their presence, the truth conditions for a {\em pick up\/} event still
hold between the other objects.
Figure~\ref{modelReconstructionFourC} shows a {\em pick up\/} event,
followed by a {\em put down\/} event, followed by another
{\em pick up\/} event, followed by another {\em put down\/} event.
Figure~\ref{eventClassificationFourC} shows that \Leonard\ correctly
recognizes this sequence of four event occurrences.
Figure~\ref{modelReconstructionFourD} shows two simultaneous {\em pick up\/}
events.
Figure~\ref{eventClassificationFourD} shows that \Leonard\ correctly
recognizes these two simultaneous event occurrences.
Finally, Figure~\ref{modelReconstructionTwo} shows two non-events.
Figure~\ref{eventClassificationTwo} shows that \Leonard\ is not fooled
into thinking that these constitute {\em pick up\/} or {\em put down\/} events,
even though portions of these events have similar motion profile to
{\em pick up\/} and {\em put down\/} events.
\Leonard\ correctly recognizes that these movies do not match any known
event types.

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{pick-up01-5-image-and-most-preferred-model}&
\figpercent{30}{pick-up01-10-image-and-most-preferred-model}&
\figpercent{30}{pick-up01-11-image-and-most-preferred-model}&
\figpercent{30}{pick-up01-17-image-and-most-preferred-model}\\
Frame 5&
Frame 10&
Frame 11&
Frame 17\\
\figpercent{30}{pick-up01-18-image-and-most-preferred-model}&
\figpercent{30}{pick-up01-22-image-and-most-preferred-model}\\
Frame 18&
Frame 22
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components on an image sequence depicting a {\em pick up\/} event from the
left instead of from the right.}
\label{modelReconstructionFourA}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{pick-up02-6-image-and-most-preferred-model}&
\figpercent{30}{pick-up02-7-image-and-most-preferred-model}&
\figpercent{30}{pick-up02-8-image-and-most-preferred-model}&
\figpercent{30}{pick-up02-18-image-and-most-preferred-model}\\
Frame 6&
Frame 7&
Frame 8&
Frame 18\\
\figpercent{30}{pick-up02-19-image-and-most-preferred-model}&
\figpercent{30}{pick-up02-24-image-and-most-preferred-model}\\
Frame 19&
Frame 24
\end{tabular}
\end{center}
\caption{The output of the  segmentation-and-tracking and model-reconstruction
components on an image sequence depicting a {\em pick up\/} event with
extraneous objects in the field of view.}
\label{modelReconstructionFourB}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{sequential00-4-image-and-most-preferred-model}&
\figpercent{30}{sequential00-8-image-and-most-preferred-model}&
\figpercent{30}{sequential00-9-image-and-most-preferred-model}&
\figpercent{30}{sequential00-18-image-and-most-preferred-model}\\
Frame 4&
Frame 8&
Frame 9&
Frame 18\\
\figpercent{30}{sequential00-19-image-and-most-preferred-model}&
\figpercent{30}{sequential00-44-image-and-most-preferred-model}&
\figpercent{30}{sequential00-45-image-and-most-preferred-model}&
\figpercent{30}{sequential00-51-image-and-most-preferred-model}\\
Frame 19&
Frame 44&
Frame 45&
Frame 51\\
\figpercent{30}{sequential00-52-image-and-most-preferred-model}&
\figpercent{30}{sequential00-69-image-and-most-preferred-model}&
\figpercent{30}{sequential00-70-image-and-most-preferred-model}&
\figpercent{30}{sequential00-77-image-and-most-preferred-model}\\
Frame 52&
Frame 69&
Frame 70&
Frame 77\\
\figpercent{30}{sequential00-78-image-and-most-preferred-model}&
\figpercent{30}{sequential00-102-image-and-most-preferred-model}&
\figpercent{30}{sequential00-103-image-and-most-preferred-model}&
\figpercent{30}{sequential00-109-image-and-most-preferred-model}\\
Frame 78&
Frame 102&
Frame 103&
Frame 109\\
\figpercent{30}{sequential00-110-image-and-most-preferred-model}&
\figpercent{30}{sequential00-111-image-and-most-preferred-model}\\
Frame 110&
Frame 111
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components on an image sequence depicting a sequence of a {\em pick up\/}
event, followed by a {\em put down\/} event, followed by another
{\em pick up\/} event, followed by another {\em put down\/} event.}
\label{modelReconstructionFourC}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\figpercent{30}{simultaneous00-0-image-and-most-preferred-model}&
\figpercent{30}{simultaneous00-5-image-and-most-preferred-model}&
\figpercent{30}{simultaneous00-6-image-and-most-preferred-model}&
\figpercent{30}{simultaneous00-10-image-and-most-preferred-model}\\
Frame 0&
Frame 5&
Frame 6&
Frame 10\\
\figpercent{30}{simultaneous00-11-image-and-most-preferred-model}&
\figpercent{30}{simultaneous00-15-image-and-most-preferred-model}&
\figpercent{30}{simultaneous00-16-image-and-most-preferred-model}&
\figpercent{30}{simultaneous00-21-image-and-most-preferred-model}\\
Frame 11&
Frame 15&
Frame 16&
Frame 21
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components on an image sequence depicting two simultaneous {\em pick up\/}
events.}
\label{modelReconstructionFourD}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{rccc}
\raisebox{32pt}{(a)}&
\figpercent{30}{none01-4-image-and-most-preferred-model}&
\figpercent{30}{none01-11-image-and-most-preferred-model}&
\figpercent{30}{none01-12-image-and-most-preferred-model}\\
&
Frame 4&
Frame 11&
Frame 12\\
&
\figpercent{30}{none01-18-image-and-most-preferred-model}&
\figpercent{30}{none01-19-image-and-most-preferred-model}&
\figpercent{30}{none01-21-image-and-most-preferred-model}\\
&
Frame 18&
Frame 19&
Frame 21\\\hline\\[-5pt]
\raisebox{32pt}{(b)}&
\figpercent{30}{none00-0-image-and-most-preferred-model}&
\figpercent{30}{none00-6-image-and-most-preferred-model}&
\figpercent{30}{none00-7-image-and-most-preferred-model}\\
&
Frame 0&
Frame 6&
Frame 7\\
&
\figpercent{30}{none00-12-image-and-most-preferred-model}&
\figpercent{30}{none00-13-image-and-most-preferred-model}&
\figpercent{30}{none00-18-image-and-most-preferred-model}\\
&
Frame 12&
Frame 13&
Frame 18
\end{tabular}
\end{center}
\caption{The output of the segmentation-and-tracking and model-reconstruction
components applied to the image sequences from
Figure~\protect\ref{videoTwo}, image sequences that depict non-events.}
\label{modelReconstructionTwo}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[0,11],[18,30])\symbol{125}\\
\ \\
(SUPPORTED?\ RED)@\symbol{123}[[0:30])\symbol{125}\\
(SUPPORTED?\ GREEN)@\symbol{123}[[11:18])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[11:30])\symbol{125}\\
(SUPPORTS?\ MOVING GREEN)@\symbol{123}[[11:18])\symbol{125}\\
(SUPPORTS?\ RED GREEN)@\symbol{123}[[11:18])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:11])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:11])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[11:30])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[11:18])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionFourA}.
Note that the {\em pick up\/} event is correctly recognized despite the fact
that it was performed from the left instead of from the right.}
\label{eventClassificationFourA}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[0,8],[19,30])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[8:19])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:30])\symbol{125}\\
(SUPPORTED?\ BLUE)@\symbol{123}[[0:30])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[19:30])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[8:19])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[8:19])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:19])\symbol{125}\\
(SUPPORTS?\ YELLOW BLUE)@\symbol{123}[[0:30])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:10]), [[16:19])\symbol{125}\\
(CONTACTS?\ BLUE YELLOW)@\symbol{123}[[0:30])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[8:30])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[10:16])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionFourB}.
Note that the {\em pick up\/} event is correctly recognized despite the
presence of extraneous objects in the field of view.}
\label{eventClassificationFourB}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[52,70],[78,102]),\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [[0,9],[19,44])\symbol{125}\\
(PUT-DOWN MOVING RED GREEN)@\symbol{123}[[19,44],[52,70]),\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [[78,102],[110,117])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[9:18]), [[44:52]),\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [[70:77]), [[102:110])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:117])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[18:44]), [[78:102])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[9:18]), [[44:52]),\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [[70:77]), [[102:110])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[9:18]), [[44:52]),\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [[70:77]), [[102:110])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:19]), [[44:78]), [[102:117])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:9]), [[13:18]), [[46:70]),\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [[106:117])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[9:52]), [[70:110])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[9:13]), [[70:76]), [[104:106])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionFourC}.
Note that \Leonard\ correctly recognizes a {\em pick up\/} event, followed
by a {\em put down\/} event, followed by another {\em pick up\/} event,
followed by another {\em put down\/} event.}
\label{eventClassificationFourC}
\end{figure}

\begin{figure}
\begin{center}
\fbox{\begin{lisp}
(PICK-UP MOVING RED GREEN)@\symbol{123}[[0,6],[16,22])\symbol{125}\\
(PICK-UP MOVING YELLOW BLUE)@\symbol{123}[[0,12],[17,22])\symbol{125}\\
\ \\
(SUPPORTED?\ MOVING)@\symbol{123}[[6:16])\symbol{125}\\
(SUPPORTED?\ MOVING)@\symbol{123}[[12:15])\symbol{125}\\
(SUPPORTED?\ RED)@\symbol{123}[[0:22])\symbol{125}\\
(SUPPORTED?\ YELLOW)@\symbol{123}[[0:22])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[16:22])\symbol{125}\\
(SUPPORTS?\ MOVING YELLOW)@\symbol{123}[[17:22])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[6:16])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[6:16])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:16])\symbol{125}\\
(SUPPORTS?\ BLUE MOVING)@\symbol{123}[[12:15])\symbol{125}\\
(SUPPORTS?\ BLUE YELLOW)@\symbol{123}[[0:17])\symbol{125}\\
(SUPPORTS?\ YELLOW MOVING)@\symbol{123}[[12:15])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:15])\symbol{125}\\
(CONTACTS?\ BLUE YELLOW)@\symbol{123}[[0:17])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[6:22])\symbol{125}\\
(ATTACHED?\ MOVING YELLOW)@\symbol{123}[[12:22])\symbol{125}\\
\end{lisp}}
\end{center}
\caption{The output of the event-classification component applied to the
model sequence from Figure~\protect\ref{modelReconstructionFourD}.
Note that the two simultaneous {\em pick up\/} events are correctly
recognized.}
\label{eventClassificationFourD}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{c}
\fbox{\begin{lisp}
(SUPPORTED?\ RED)@\symbol{123}[[0:19])\symbol{125}\\
(SUPPORTED?\ MOVING)@\symbol{123}[[13:31])\symbol{125}\\
(SUPPORTS?\ RED MOVING)@\symbol{123}[[13:31])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[0:13])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[12:19])\symbol{125}\\
(SUPPORTS?\ GREEN MOVING)@\symbol{123}[[13:19])\symbol{125}\\
(ATTACHED?\ RED MOVING)@\symbol{123}[[0:31])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[13:19])\symbol{125}\\
\end{lisp}}\\
(a)\\*[2ex]
\fbox{\begin{lisp}
(SUPPORTED?\ RED)@\symbol{123}[[0:25])\symbol{125}\\
(SUPPORTED?\ GREEN)@\symbol{123}[[7:13])\symbol{125}\\
(SUPPORTS?\ MOVING RED)@\symbol{123}[[7:13])\symbol{125}\\
(SUPPORTS?\ MOVING GREEN)@\symbol{123}[[7:13])\symbol{125}\\
(SUPPORTS?\ RED GREEN)@\symbol{123}[[7:13])\symbol{125}\\
(SUPPORTS?\ GREEN RED)@\symbol{123}[[0:7]), [[13:25])\symbol{125}\\
(CONTACTS?\ RED GREEN)@\symbol{123}[[0:7]), [[13:25])\symbol{125}\\
(ATTACHED?\ MOVING RED)@\symbol{123}[[7:13])\symbol{125}\\
(ATTACHED?\ RED GREEN)@\symbol{123}[[7:13])\symbol{125}\\
\end{lisp}}\\
(b)
\end{tabular}
\end{center}
\caption{The output of the event-classification component applied to the
model sequences from Figure~\protect\ref{modelReconstructionTwo}.
Note that \Leonard\ correctly recognizes that no events occurred in these
sequences.}
\label{eventClassificationTwo}
\end{figure}

An approach to even classification is valid and useful only if it is robust.
A preliminary evaluation of the robustness of \Leonard\ was conducted.
Thirty five movies were filmed, five instances of each of the seven event types
{\em pick up}, {\em put down}, {\em stack}, {\em unstack}, {\em move},
{\em assemble}, and {\em disassemble}.
These movies resemble those in Figures~\ref{videoOne} and~\ref{videoThreeA}
through~\ref{videoThreeE}.
The same subject performed all thirty five events.
These movies were processed by \Leonard.\footnote{The movies, as well as the
results produced by \Leonard\ when processing the movies, are available as
Online Appendix~1, as well as from
{\tt ftp://ftp.nj.nec.com/pub/qobi/leonard.tar.Z}\@.}
The results of this preliminary evaluation are summarized in
Table~\ref{evaluation}.
A more extensive evaluation of \Leonard\ will be conducted in the future.

\begin{table}
\begin{center}
\begin{tabular}{l|ccccccc}
&
{\em pick up\/} &
{\em put down\/} &
{\em stack\/} &
{\em unstack\/} &
{\em move\/} &
{\em assemble\/} &
{\em disassemble\/}\\\hline
{\em pick up\/} & 5/5 & & & & & & \\
{\em put down\/} & & 5/5 & & & & & \\
{\em stack\/} & & 5/5 & 5/5 & & & & \\
{\em unstack\/} & 5/5 & & & 4/5 & & & \\
{\em move\/} & 4/5 & 5/5 & & & 4/5 & & \\
{\em assemble\/} & & 5/10 & 1/5 & & & 1/5 & \\
{\em disassemble\/} & 10/10 & & & 5/5 & & & 5/5
\end{tabular}
\end{center}
\caption{An evaluation of the robustness of \Leonard\ on a test set of five
movies of each of seven event types.
The rows represent movies of the indicated event types.
The columns represent classifications of the indicated event type.
The entries $x/y$ indicate $x$, the number of times that a movie of the
indicated event type was classified as the indicated event type, and $y$, the
number of times that the movie should have been classified as the indicated
event type.
Note that {\em stack\/} entails {\em put down}, {\em unstack\/} entails
{\em pick up}, {\em move\/} entails both a {\em pick up\/} and a
{\em put down}, {\em assemble\/} entails both a {\em put down\/} and a
separate {\em stack}, and {\em disassemble\/} entails both a {\em pick up\/}
and a separate {\em unstack}.
Thus off-diagonal entries are expected in these cases.
There were six false negatives and no false positives.
Four of the false negatives were for the event type {\em assemble}.
In three of those cases, \Leonard\ successfully recognized the constituent
{\em put down\/} subevent but failed to recognize the constituent
{\em stack\/} subevent as well as the associated {\em put down\/} subevent.
In one case, \Leonard\ failed to recognize both the constituent
{\em put down\/} and {\em stack\/} subevents along with the associated
{\em put down\/} constituent of the {\em stack\/} subevent.
One of the false negatives was for the event type {\em move}.
In this case, \Leonard\ successfully recognized the constituent
{\em put down\/} subevent but failed to recognize the constituent
{\em pick up\/} subevent.
The remaining false negative was for the event type {\em unstack}.
In this case, \Leonard\ successfully recognized the constituent {\em pick up\/}
subevent but failed to recognize the aggregate {\em unstack\/} event.}
\label{evaluation}
\end{table}

\section{Discussion}

This paper presents a new approach to event recognition that differs from
the prior approach in two ways.
First, it uses force dynamics instead of motion profile as the feature set to
differentiate between event types.
Second, it uses event logic instead of hidden Markov models as the
computational framework for classifying time-series data containing these
features.
Nominally, these two differences are independent.
One can imagine using hidden Markov models to classify time series of
force-dynamic features or using event logic to classify time series of
motion-profile features.
While such combinations are feasible in principle, they are unwieldy in
practice.

Consider using event logic to classify time series of motion-profile features.
Motion-profile features, such as position, velocity, and acceleration, are
typically continuous.
A given event usually corresponds to a vague range of possible feature
values.
This vagueness is well modeled by continuous-output hidden Markov
models.
Event logic, which is discrete in nature, requires quantizing precise
feature-value ranges.
Such quantization can lead to a high misclassification rate.
Furthermore, continuous distributions allow partitioning a multidimensional
feature space into different classes where the boundaries between classes are
more complex than lines along the feature axes.
Emulating this in event logic would require complex disjunctive expressions.

Similarly, consider using hidden Markov models to classify time series of
force-dynamic features.
Suppose that a feature vector contains~$n$ features.
Since both force-dynamic and motion-profile features typically relate pairs
of objects, $n$~is often quadratic in the number of event participants.
Let us contrast the number of parameters needed to represent these features
in both the motion-profile and force-dynamic approaches.
Since, as discussed above, motion-profile features are typically continuous,
hidden Markov models with continuous outputs can be used in the motion-profile
approach.
When the features are independent, such a model requires $O(n)$ parameters per
state to specify the output distributions.
Even if one uses, say, a multivariate Gaussian to model dependent features,
this requires only $O(n^2)$ parameters per state to specify the output
distributions in the motion-profile approach.
However, force-dynamic features are Boolean.
This requires using discrete-output hidden Markov models.
Such models output a stream of symbols, not feature vectors.
Constructing an appropriate alphabet of output symbols requires considering
all possible subsets of features.
This requires $O(2^n)$ parameters per state to specify the output
distributions in the force-dynamic approach.
Thus continuous-output hidden Markov models appear to be better
suited to an approach that uses motion-profile features while event logic
appears to be better suited to an approach that uses force-dynamic features.

Humans use language for three fundamental purposes: we describe what we see,
we ask others to perform actions, and we engage in conversation.
The first two require grounding language in perception and action.
Only the third involves disembodied use of language.
Almost all research in computational linguistics has focused on such
disembodied language use.
Data-base query processing, information extraction and retrieval, and
spoken-language dialog all use language solely to manipulate internal
representations.
In contrast, the work described in this paper grounds language in perception
of the external world.
It describes an implemented system, called \Leonard, that uses language to
describe events observed in short image sequences.

Why is perceptual grounding of language important and relevant to
computational linguistics?
Current approaches to lexical semantics suffer from the `bold-face syndrome.'
All too often, the meanings of words, like {\em throw}, are taken to be
uninterpreted symbols, like {\bf throw}, or expressions over uninterpreted
symbols, like {\bf cause to go}
\cite{Leech69,Miller72,Schank73,Jackendoff83,Jackendoff90,Pinker89}.
Since the interpretation of such symbols is left to informal intuition, the
correctness of any meaning representation constructed from such uninterpreted
symbols cannot be verified.
In other words, how is one to know whether {\bf cause to go} is the correct
meaning of {\em throw}?
Perceptual grounding offers a way to verify semantic representations.
Having an implemented system use a collection of semantic representations to
generate appropriate descriptions of observations gives evidence that those
semantic representations are correct.
This paper takes a small step in this direction.
In contrast to prior work, which presents informal semantic representations
whose interpretation is left to intuition, it presents perceptually-grounded
semantic representations.
While the system described in this paper addresses only perceptual grounding
of language, the long-term goal of this research is to provide a
unified semantic representation that is sufficiently powerful to support all
three forms of language use: perception, action, and conversation.

Different parts of speech in language typically describe different aspects of
visual percepts.
Nouns typically describe objects.
Verbs typically describe events.
Adjectives typically describe properties.
Prepositions typically describe spatial and temporal relations.
Grounding language in visual perception will require construction of semantic
representations for all of these different parts of speech.
It is likely that different parts of speech will require different machinery
to represent their lexical semantics.
In other words, whatever the ultimate representation of {\em apple\/} and
{\em chair\/} are, they are likely to be based on very different principles
than the ultimate representation of {\em pick up\/} and {\em put down}.
These, in turn, are likely to be further different from those needed to
represent {\em in}, {\em on}, {\em red}, and {\em big}.
Indeed, machine vision research, at least that aspect of machine vision
research that focuses on object recognition, can be viewed as an attempt to
perceptually ground the lexical semantics of nouns.
In contrast, this paper focuses solely on verbs.
Accordingly, it develops machinery that is very different from what is
typically used in the machine-vision community, machinery that is more
reminiscent of that which is used in the knowledge-representation community.
On the other hand, unlike typical knowledge-representation work, it grounds
that machinery in image processing.

When one proposes a representation, such as {\bf cause to go}, as the meaning
of a word, such as {\em throw}, one must specify three things to effectively
specify the meaning of that word.
First, one must specify the lexical semantics of the individual primitives,
how one determines the truth conditions of items like {\bf cause} and
{\bf to go}.
Second, one must specify the compositional semantics of the representation,
how one combines the truth conditions of primitives like {\bf cause} and
{\bf to go} to get the aggregate truth conditions of compound expressions like
{\bf cause to go}.
Third, one must specify a lexical entry, a map from a word, like {\em throw},
to a compound expression, like {\bf cause to go}.
All three are necessary in order to precisely specify the word meaning.

Prior work in lexical semantics, such as the work of \citeA{Leech69},
\citeA{Miller72}, \citeA{Schank73}, \citeA{Jackendoff83,Jackendoff90}, and
\citeA{Pinker89}, is deficient in this regard.
It specifies the third component without the first two.
In other words, it formulates lexical entries in terms of compound expressions
like {\bf cause to go}, without specifying the meanings of the primitives, like
{\bf cause} and {\bf to go}, and without specifying how these meanings are
combined to form the aggregate meaning of the compound expression.
This paper attempts to address that deficiency by specifying all three
components.
First, the lexical semantics of the event-logic primitives is precisely
specified in Figure~\ref{primitiveEventTypes}.
Second, the compositional semantics of event logic is precisely specified in
Section~\ref{eventLogic}.
Third, lexical entries for several verbs are precisely specified in
Figure~\ref{compoundEventTypes}.
These three components together formally specify the meanings of those verbs
with a level of precision that is absent in prior work.

While these lexical entries are {\em precise}, there is no claim that they are
{\em accurate}.
Lexical entries are {\sl precise} when their meaning is reduced to an
impartial mechanical procedure.
Lexical entries are {\sl accurate} when they properly reflect the truth
conditions for the words that they define.
Even ignoring homonymy and metaphor, words such as {\em move\/} and
{\em assemble\/} clearly have meanings that are much more complex than what is,
and even can be, represented with the machinery presented in this paper.
But that holds true of prior work as well.
The lexical entries given in, for example, \citeA{Leech69}, \citeA{Miller72},
\citeA{Schank73}, \citeA{Jackendoff83,Jackendoff90}, and \citeA{Pinker89}
also do not accurately reflect the truth conditions for the words that they
define.
The purpose of this paper is not to improve the accuracy of definitions.
In fact, the definitions given in prior work might be more accurate, in some
ways, than those given here.
Rather, its purpose is to improve the precision of definitions.
The definitions given in prior work are imprecise and that imprecision makes
assessing their accuracy a subjective process: do humans think an informally
specified representation matches their intuition.
In contrast, precision allows objective assessment of accuracy: does the
output of a mechanical procedure applied to sample event occurrences match
human judgments of which words characterize those occurrences.

Precision is the key methodological advance of this work.
Precise specification of the meaning of lexical semantic representations,
by way of perceptual grounding, makes accuracy assessment possible by way of
experimental evaluation.
Taking this first step of advancing precision and perceptual grounding will
hopefully allow us to take future steps towards improving accuracy.

\section{Related Work}

Most prior work uses motion profile, some combination of relative-and
absolute linear-and-angular positions, velocities, and accelerations, as the
features that drive event classification.
That work follows the tradition of linguists and cognitive scientists,
such as \citeA{Leech69}, \citeA{Miller72}, \citeA{Schank73},
\citeA{Jackendoff83,Jackendoff90}, and \citeA{Pinker89}, that represent the
lexical semantics of verbs via the causal, aspectual, and directional
qualities of motion.
Some linguists and cognitive scientists, such as \citeA{Herskovits86} and
\citeA{JackendoffL91}, have argued that force-dynamic relations
\cite{Talmy88}, such as support, contact, and attachment, are crucial for
representing the lexical semantics of spatial prepositions.
For example, in some situations, part of what it means for one object to
be {\em on\/} another object is for the former to be in contact with, and
supported by, the latter.
In other situations, something can be on something else by way of attachment,
as in {\em the knob on the door}.
\citeA{Siskind92} has argued that change in the state of force-dynamic
relations plays a more central role in specifying the lexical semantics of
simple spatial motion verbs than motion profile.
The particular relative-and-absolute linear-and-angular positions, velocities,
and accelerations don't matter when picking something up or putting something
down.
What matters is a state change in the source of support of the patient.
Similarly, what distinguishes putting something down from dropping it is
that, in the former, the patient is always supported, while in the latter, the
patient undergoes unsupported motion.

The work described in this paper differs from prior work in visual-event
perception in a number of respects.
\citeA{WaltzB79}, \citeA{Waltz81}, \citeA{MarrV82}, and \citeA{RubinR85}
describe unimplemented frameworks that are not based on force dynamics.
\citeA{Thibadeau86} describes a system that recognizes when an event occurs
but not what event occurs.
His system processes simulated video and is not based on force dynamics.
\citeA{Badler75}, \citeA{Adler77}, \citeA{TsujiMK77}, \citeA{Okada79},
\citeA{TsujiOY79,TsujiOY80}, \citeA{AbeST81}, \citeA{AbeT82},
\citeA{NovakB90}, and \citeA{Regier92} describe systems that process
simulated video and that are not based on force dynamics.
\citeA{Borchardt84,Borchardt85} presents event definitions that are based on
force-dynamic relations but does not present techniques for recovering those
relations automatically from either simulated or real video.
\citeA{YamotoOI92}, \citeA{Starner95}, \citeA{SiskindM96}, \citeA{Siskind96a},
\citeA{Brand96,Brand97a}, \citeA{BrandOP97}, and \citeA{BobickI98} present
systems that recognize event occurrences from real video using motion profile
but not force dynamics.
These systems use hidden Markov models rather than event logic as the
event-classification engine.
\citeA{Funt80} presents a heuristic approach to stability analysis that
operates on simulated video but does not perform model reconstruction or event
classification.
\citeA{BrandBC93} and \citeA{Brand97} present a heuristic approach to
stability analysis that operates on real video but do not use stability
analysis to perform model reconstruction and event classification.
\citeA{BlumGN70} and \citeA{Fahlman74} present stability-analysis algorithms
that are based on linear programming but do not use stability analysis to
perform model reconstruction or event classification.
These stability-analysis algorithms use dynamics rather than kinematics.
\citeA{Siskind91b,Siskind92,Siskind93b,Siskind94b,Siskind95,Siskind97} presents
systems that operate on simulated video and use force dynamics to recognize
event occurrences.
All of that work, except \citeA{Siskind97}, uses heuristic approaches to
stability analysis, model reconstruction, and event classification.
\citeA{Siskind97} presents an early version of the stability-analysis and
event-logic--based event-recognition techniques used in the current system.
\citeA{MannJS96,MannJS97} and \citeA{MannJ98} present a system that does model
reconstruction from real video but does not use the recovered force-dynamic
relations to perform event classification.
That work uses an approach to stability analysis based on dynamics instead of
the kinematic approach used in this paper.

There is also a body of prior work that grounds fragments of natural-language
semantics in physical relations between objects in graphically represented
blocks worlds or for solving physics word problems.
Examples of such work include \citeA{Bobrow64}, \citeA{Winograd72}, and
\citeA{Palmer90} as well the \Issac\ system \cite{Novak76} and the
\Mecho\ project \cite{BundyLPW76,BundyBLMMP79,Luger81}.
While that work does not focus on recognizing events, {\em per se}, it does
relate lexical semantics to physical relations between represented objects.

\Leonard\ currently does not contain a learning component.
It is given a fixed physical theory of the world, implicitly represented in the
model-reconstruction procedure, and a fixed collection of event-type
descriptions, explicitly formulated as event-logic expressions.
One potential area for future work would be to automatically learn a physical
theory of the world and/or event-type descriptions.
Adding a learning component could potentially produce more robust
model-reconstruction and event-classification components than those currently
constructed by hand.
Techniques such as those presented in \citeA{MartinG2000} and
\citeA{CumbyR2000} might be useful for this task.

\section{Conclusion}

This paper has presented \Leonard, a comprehensive implemented system for
recovering event occurrences from video input.
It differs from the prior approach to the same problem in two fundamental ways.
First, it uses state changes in the force-dynamic relations between objects,
instead of motion profile, as the key descriptive element in defining event
types.
Second, it uses event logic, instead of hidden Markov models, to perform event
classification.
One key result of this paper is the formulation of spanning intervals, a novel
efficient representation of the infinite sets of intervals that arise when
processing liquid and semi-liquid events.
A second key result of this paper is the formulation of an efficient
procedure, based on spanning intervals, for inferring all occurrences of
compound event types from occurrences of primitive event types.
The techniques of force-dynamic model reconstruction, spanning intervals, and
event-logic inference have been used to successfully recognize seven event
types from real video: {\em pick up}, {\em put down}, {\em stack},
{\em unstack}, {\em move}, {\em assemble}, and {\em disassemble}.
Using force dynamics and event logic to perform event recognition offers four
key advantages over the prior approach of using motion profile and hidden
Markov models.
First, it is insensitive to variance in the motion profile of an event
occurrence.
Second, it is insensitive to the presence of extraneous objects in the field
of view.
Third, it allows temporal segmentation of sequential and parallel event
occurrences.
Fourth, it robustly detects the non-occurrence of events as well as their
occurrence.

At a more fundamental level, this paper advances a novel methodology:
grounding lexical-semantic representations in visual-event perception as a
means for assessing the accuracy of such representations.
Prior work in lexical-semantic representations has used calculi whose
semantics were not precisely specified.
Lexical entries formulated in such calculi derived their meaning from
intuition and thus could not be empirically tested.
By providing a lexical-semantic representation whose semantics is precisely
specified via perceptual grounding, this paper opens up the field of lexical
semantics to empirical evaluation.
The particular representations advanced in this paper are clearly only
approximations to the ultimate truth.
This follows from the primitive state of our understanding of language and
perception.
Nonetheless, I hope that this paper offers an advance towards the ultimate
truth, both through its novel methodology and the particular details of its
mechanisms.

\vskip 0.2in
\bibliography{QobiTeX}
\bibliographystyle{theapa}

\end{document}
