
## 4.8 An Efficient Inference Procedure For Event Logic

Given the above procedures for computing hii, i1 \ i2, :i, SPAN(i1; i2), D(r; i), and I(i; r; j), one can now define a procedure for computing E(M ; ). This procedure takes a model M along with an event-logic expression  and computes a set of normalized spanning intervals that represents the set I of intervals i for which i is true. The model M is a set of atomic event-occurrence formulae of the form p( 1; : : : ; 
n)i, where p( 1; : : : ; 
n) is a ground primitive event-logic expression and i is a normalized spanning interval. A model entry p( 1; : : : ; 
n)i indicates that the primitive event p( 1; : : : ; 
n) occurred during all intervals in the extension of i.

E(M ; p( 1 ; : : : ;  E(M ; :) 4 = E(M ;  ^R 	) 4=[ E(M ; 3R) 4=[ E(M ;  _ 	) 4
n)) 4= fijp(
$\{\mathbf{i}|p(c_{1},\ldots,c_{n})\,\mathbf{0}\mathbf{i}\in M\}$  $\mathcal{E}\left(M,\,\Phi\right)\cup\mathcal{E}\left(M,\,\Psi\right)$  $\bigcup\ldots\bigcup\mathbf{i}_{1}^{\prime}\cap\ldots\cap\mathbf{i}_{n}^{\prime}$  $\mathbf{i}_{1}\in\mathbf{-i}_{1}$$\mathbf{i}_{n}\in\mathbf{-i}_{n}$  where $\mathcal{E}\left(M,\,\Phi\right)=\{\mathbf{i}_{1},\ldots,\mathbf{i}_{n}\}$  $\bigcup\bigcup\bigcup\mathcal{E}\left(\mathbf{i},r,\mathbf{j}\right)$  $\mathbf{i}\in\mathcal{E}\left(M,\Phi\right)\mathbf{j}\in\mathcal{E}\left(M,\Psi\right)r\in R$  $\bigcup\bigcup\mathcal{D}\left(r,\mathbf{i}\right)$

The procedure performs structural induction on . It computes a set of normalized spanning intervals to the represent the occurrence of each atomic event-logic expression in  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 ; ),
the set I of intervals i for which i is true, can be represented by a finite set of normalized spanning intervals. Nominally, the number of normalized spanning intervals in E(M ; ) can be exponential in the subexpression depth of  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 ; ) for all of the event types given in Figure 10 for all of the movies that have been tried so far have yielded sets of fewer than a dozen normalized spanning intervals.

## 5. Experimental Results

The techniques described in this paper have been implemented as a system called LEONARD and tested on a number of video sequences.7 LEONARD successfully recognizes the events pick up, put down, stack, unstack, move, *assemble*, and *disassemble* using the definitions given in Figure 10.

Figures 1 and 11 through 15 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-240 resolution at 30fps. Figures 4 and 16 through 20 show the results of segmentation, tracking, and model reconstruction for those key frames superimposed on the original images. Figures 5 and 21 through 25 show the results of event classification for these movies. These figures show LEONARD correctly recognizing the intended event classes for each movie.

7. 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 ftp://ftp.nj.nec.com/pub/qobi/leonard.tar.Z.