Next: An Efficient Representation and Up: Grounding the Lexical Semantics Previous: Model Reconstruction

Event Logic

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 event logic to infer compound event occurrences from primitive event occurrences. For example, for the image sequence in Figure 1(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 and , i.e. that the primitive event types and occurred during the intervals [0,13) and [13,20) respectively. The compound event type might be defined as

i.e.  followed by . (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 , i.e. that the compound event type 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  is an event-logic expression that denotes a primitive or compound event type, and  is an interval, then is an atomic event-occurrence formula that is true if and only if the truth conditions for the event type  hold of the interval  .

denotes coincidental occurrence, the fact that an occurrence of  started at the beginning of  and finished at the end of  . would not hold if an occurrence of  did not precisely coincide with  , but instead overlapped, partially or totally, with  . 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  is a predicate, then  denotes the primitive event type derived from  . A primitive event type  holds of an interval if the corresponding predicate  holds of every instant in that interval. This means that and might have different truth values. For example, if  is true of every instant in [0,2) and false of every other instant, then is true while 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 [4], I denote these relations as =, <, >, , , , , , , , , , and and refer to them collectively as Allen relations throughout the paper. The names , , , , and are mnemonics for meet, overlap, start, finish, and during respectively. The inverse relations, such as , whose names end in are the same as the corresponding relations, such as , whose names do not end in except that the arguments are reversed. Figure 8 depicts all thirteen Allen relations graphically. Second, I define the span of two intervals  and  , denoted , as the smallest super-interval of both  and  .

Figure 8: The Allen relations, the thirteen possible relations between two intervals.

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 and , denote objects in the input movie while primitive event-type symbols, such as , 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, . An event-logic expression is either an atomic event-logic expression or one of the compound event-logic expressions , , , or , where  and  are event-logic expressions and .

Informally, the semantics of compound event-logic expressions is defined as follows:

• denotes the non-occurrence of  . An occurrence of coincides with  if no occurrence of  coincides with  . Note that could be true, even if an occurrence of  overlapped with  , so long as no occurrence of  coincided with  .
• denotes the occurrence of either  or  .
• denotes the occurrence of both  and  . The occurrences of  and  need not be simultaneous. The subscript R specifies a set of allowed Allen relations between the occurrences of  and  . If occurrences of  and  coincide with  and  respectively, and for some , then an occurrence of coincides with the span of  and  . I abbreviate the special case simply as without any subscript. describes an aggregate event where both  and  occur simultaneously. I also abbreviate the special case as . describes an aggregate event where an occurrence of  is immediately followed by an occurrence of  .
• An occurrence of coinciding with  denotes an occurrence of  at some other interval  such that for some . can act as a tense operator. Expressions such as , , , and specify that  happened in the noncontiguous past, noncontiguous future, contiguous past, or contiguous future respectively. The  operator can also be used to derive overlapped occurrence from coincidental occurrence. An occurrence of coincides with  if an occurrence of  overlaps with  . I abbreviate simply as without any subscript. Note that while indicates that no occurrence of  coincided with  , indicates that no occurrence of  overlapped with  .

Formally, the truth of an atomic event-occurrence formula 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 . (M can be viewed as either a model or as a movie.) 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 as follows:

• if and only if .
• if and only if .
• if and only if or .
• if and only if there exist two intervals  and  such that , for some , , and .
• if and only if there exists some interval  such that for some and .

Figure 9 shows the primitive event types currently used by LEONARD. The definitions in Figure 9 are formulated in terms of the predicates , , , and that are produced by model reconstruction as described in Section 2. 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  , 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  be the set of polygons in a scene, be the most-preferred model of the scene as produced by model reconstruction, and be true if the scene  is stable under an interpretation I. Stability analysis, i.e. the 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  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 9, denotes the variant of  with x removed, denotes the fact that x is rigidly attached to y, denotes the reflexive transitive closure of the relation, denotes the set of objects that are rigidly attached, directly or indirectly, to y, and denotes a variant of I where all objects except for y and those rigidly attached, directly or indirectly, to y are grounded.

Figure 9: Definition of the primitive event types used by LEONARD.

Figure 10 shows the compound event-type definitions currently used by LEONARD. 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. Additionally, several conditions must hold throughout the entire event: x, y, and z must be distinct and y must be supported. denotes an event type where x puts y down on z. It is specified in a fashion that is similar to but where the three subevents occur in reverse order. denotes an event type where w puts x down on y which is resting on z. It is specified as , where z supports but is not attached to y and z is distinct from w, x, and y. denotes an event type where w picks x up off of y which is resting on z. It is specified as , where z supports but is not attached to y and z is distinct from w, x, and y. denotes an event type where w picks x up off of y and puts it down on z which is distinct from y. denotes an event type where w first puts y down on z then sometime later stacks x on top of y. Finally, 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 1 shows sample movies depicting occurrences of the event types and . Figures 11 through 15 show sample movies depicting occurrences of the event types , , , , and respectively.

Figure 10: The lexicon of compound event types used by LEONARD.

Figure 11: An image sequence depicting a stack event.

Figure 12: An image sequence depicting an unstack event.

Figure 13: An image sequence depicting a move event.

Figure 14: An image sequence depicting an assemble event.

Figure 15: An image sequence depicting a disassemble event.

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 10 to define , , and in terms of ; , , and in terms of ; in terms of , which is itself defined in terms of ; and in terms of , which is itself defined in terms of .

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 9 produces a set of primitive event occurrences for a given scene sequence. Figure 10 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 to be . The model-reconstruction component combined with the primitive event-type definitions given in Figure 9 produces M. Instantiating the parameterized compound event types from Figure 10 for all object tuples yields a set of event-logic expressions. The event-classification component computes for every  in this set.

In principle, 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 liquid. Liquid events have the following two properties. First, if they are true during an interval  , then they are also true during any subinterval of  . Second, if they are true during two overlapping intervals  and  , then they are also true during and any subinterval of . 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. [48] introduced the notion of liquidity and [68], [22], [69], and [30] 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  and quantifying over pairs of subintervals to implement  . The central result of this paper is a novel representation, called 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 , are presented in the next section.

Next: An Efficient Representation and Up: Grounding the Lexical Semantics Previous: Model Reconstruction

Jeffrey Mark Siskind
Wed Aug 1 19:08:09 EDT 2001