Detecting Stochastically Scheduled Activities in Video

1 Introduction

There has been a tremendous amount of work in low-level computer vision video processing algorithms for detection of various types of elementary events or actions such as a person entering or leaving a room or unloading a package. However, there is much less work on how such low level detection algorithms can be utilized in high-level recognition of activities in video. High level activities can include transactions at a bank automatic teller machine (ATM), robberies at an ATM, unloading an aircraft, moving bags from a secure baggage zone at an airport to the truck that transports it to the plane, etc.

In this paper, we focus on such high level activities (and provide a simple ATM example to motivate our work). High level activities consist of a set of simple actions that are detectable using video image processing algorithms, together with some temporal requirements.

∗Authors listed in alphabetical order. This work was partly supported by AFOSR grants FA95500610405 and FA95500510298, ARO grant DAAD190310202 and by the Joint Institute for Knowledge Discovery.

In this paper, we provide fast algorithms to answer two kinds of queries. The first type of query tries to find minimal (i.e. the shortest possible) clips of video that contain a given event with a probability exceeding a specified threshold -we call these Threshold Activity Queries. The second type of query takes a portion of a video (the part seen thus far) and a set of activities, and tries to find the activity in the set that most likely has occurred in the video (we call these Activity Recognition Queries).

The key contributions of this paper are the following. We first introduce (in Section 2) a simple stochastic automata representation of complex activities based on atomic actions which are recognizable by an image understanding primitive such as those in [Elgammal et al., 2000; Bevilacqua, 2003; 2002; Cavallaro et al., 2005; 2000; Makarov, 1996]. Examples of actions we have implemented in our system using computer vision algorithms include person and object identification, identification of people entering and exiting rooms and motion tracking. Our first major contribution (in Section 3) is the MPS algorithm to answer threshold queries. Our second major contribution (Section 4) are the naiveMPA and MPA algorithms to solve activity recognition queries. We evaluate these algorithms theoretically as well as experimentally (in Section 5) on a third party dataset consisting of staged bank robbery videos [Vu et al., 2003] and provide evidence that the algorithms are both efficient and yield high-quality results.

2 Stochastic Activities

In this section, we provide a simple framework to represent high level activities on top of low level image processing primitives. This framework is a simple version of HMMs - we don't claim it is new. The novel part of this paper starts from the next section onwards.

We assume the existence of a finite set A of "action" symbols; we assume that each such atomic action can be detected by an image understanding method 1 . For the purposes of this paper, we will assume that action symbols are propositional, though there is no loss of generality in this assumption.

1 Although some of the image understanding methods cited in this paper return a numeric value between 0 and 1, this can be readily transformed into a method that returns either "yes" or "no" based on a fixed threshold.

Definition 1 (Stochastic activity) A stochastic activity is a labeled graph (V, E, ρ) where:

1. V is a finite set of action symbols;
2. E is a subset of (V ×V );
3. ρ is a function that associates, with each v of out-degree 1 or more, a probability distribution on {(v, v′ )|(v, v′ ) ∈ E}, i.e. for all v ∈ V , ∑ ρ((v, v′ )) = 1.

(v,v′ )∈E

1. {v ∈ V | ̸ ∃ v′ ∈ V s.t. (v, v′ ) ∈ E} ̸= ∅. This states that there exists at least one end symbol in the activity definition.
2. {v ∈ V | ̸ ∃ v′ ∈ V s.t. (v′ , v) ∈ E} ̸= ∅. This states that there exists at least one start symbol in the activity definition.

For v ∈ V , we denote by pb(v) the maximum product of probabilities on any paths between v and an end node.

Figure 1(a) shows a small example of a stochastic activity associated with transactions at an Automatic Teller Machine (ATM). In this figure, we have assumed that edges without a label have probability 1. For example, consider the node withdraw-cash. There are two edges starting at this node - one to withdraw-card labeled with a probability of 0.9 and one to insert-checks with probability 0.1. This means that there is a 90% probability of transitioning to the withdraw-card state after executing withdraw-cash and a 10% probability of transitioning to insert-checks after executing withdraw-cash. For the purposes of this paper, this example is somewhat simplified (e.g., we avoided talking about receipts generated by ATMs, etc.). Each of the actions in this stochastic activity can be easily detected by either an image processing algorithm (e.g. detect-person would check if a person is present in the image) or a sensor (e.g. to detect if insert-card holds). It is also important to note that in this framework, it is possible to execute withdraw-cash, then execute insert-checks, and then again execute withdraw-cash - informally speaking, the probability of this sequence occurring would be 0.1 × 0.2 = 0.02. Similarly, Figure 1(b) describes an attempted robbery at an ATM.

A labeling ℓ of a video v is a mapping that takes a video frame f as input, and returns a set of action symbols as output.

Example 1 The following is a labeling of a 500-frame video w.r.t. to the stochastic activity presented in Figure 1(a): (5, {detect - person}), (26, {present - card}), (45, {insert - card}), (213, {withdraw - cash}), (320, {insert - checks}), (431, {withdraw - card}), (496, {¬detect - person}).

We say that an action a′ follows an action a in segment [s, e] ⊆ v w.r.t. labeling ℓ and activity definition (V, E, ρ) iff: (i) a ∈ ℓ(s), a′ ∈ ℓ(e) and (a, a′ ) ∈ E; (ii) ∀a′′ ∈ {b ∈ V |(a, b) ∈ E} - {a′} and ∀f s.t. s ≤ f ≤ e, a′′ ̸∈ ℓ(f).

Example 2 Consider the labeling in Example 1. In the subvideo [45, 320], action withdraw - cash follows action insert - card. However, action insert - checks does not follow action insert - card.

Intuitively, a labeling of video v specifies which actions are detected in a given video. We now define the probability with which a given video segment [s, e] satisfies an activity specification.

Definition 2 (Probabilistic satisfaction) Let v = [s, e] be a video segment and let (V,E, ρ) be a stochastic activity. Let ℓ : v → 2V be a labeling of the video segment v. We say that v satisfies (V,E, ρ) with probability p iff there exists a sequence of framesf1 ≤ . . . ≤ fn ∈ [s, e] and a sequence of activity symbols u1, . . . , un such that:

• (i) ∀i ∈ [1, n]ui ∈ ℓ(fi).
• (ii) For all i ∈ [1, n-1], ui+1 follows ui in [fi, fi+1] w.r.t. ℓ and (V, E, ρ).
• (iii) {w ∈ V |(w, u1) ∈ E} = ∅ and {w ∈ V )|(un,w) ∈ E} = ∅.
• (iv) Πn-1 i=1 ρ((ui, ui+1)) ≥ p.

One problem with the above definition is that an activity consisting of very few action symbols will in most cases yield a higher probability than an activity with a hundred times as many actions. In caseswhenwewant to decidewhich activity from a given set most likely occurs in a video, we need to normalize the probability w.r.t. to the activity definition. We say that a video [s, e] satisfies an activity (V,E, ρ) w.r.t. labeling ℓ with relative probability p∗ iff [s, e] satisfies (V,E, ρ) with probability p and p∗ = p-pmin pmax-pmin , where pmin, pmax are the lowest and respectively highest probabilities labeling a path from a start node 2 to an end node 3 in (V, E, ρ).

Example 3 Consider the labeling in Example 1 and the stochastic activity in Figure 1. Then the video satisfies the action with probability 0.056. For this example, pmin = 0 (since we can have an arbitrarily large sequence of activities repeating the action symbols withdraw - cash, insert - checks) and pmax = 0.63. Then the video whose labeling is given in Example 1 satisfies the activity in Figure 1 with a relative probability of approximately 0.089.

Proposition 1 Let v = [s, e] be a video segment, and let ℓ be its labeling. Let (V,E, ρ) be a stochastic activity such that v satisfies (V,E, ρ) with probability p. Then for all videos v′ with labeling ℓ′ such that v ⊆ v′ and ∀f ∈ [s, e] ℓ(f) = ℓ′ (f), v′ satisfies (V, E, ρ) with probability p.

Definition 3 A stochastic activity query (SAQ) is a four-tuple (v, ℓ, (V,E, ρ), p) where v is a video, ℓ is a labeling of the video, (V,E, ρ) is a stochastic activity, and p is a threshold probability.

A sequence [s, e] is an answer to the above SAQ iff [s, e] satisfies (V, E, ρ) with probability p and there is no strict subset [s′ , e′ ] ⊂ [s, e] which satisfies (V, E, ρ) with probability p.

Intuitively, we are looking for the smallest subvideos that satisfy an activity definition with probability above a given threshold p. We will now define the most probable subvideo and most probable activity problems more formally.

The Most Probable Subvideo (MPS) Problem. The most probable subvideo problem can now be defined as follows: given a stochastic activity query (v, ℓ, (V,E, ρ), p), find the set of all answers to the query.

2 A node of indegree 0.

3 A node of outdegree 0.

The Most Probable Activity (MPA) Problem. In many practical cases - airport security, ATM monitoring, etc., the system users are interested in monitoring a list of specific activities. The goal is to identify the activity (or activities) that most likely occur in a given portion of the surveillance video. The most likely activity problem can be defined as follows: given a video v, its labeling ℓ, a set of activity definitions A = {(V1,E1, ρ1), . . . , (Vn,En, ρn)}, find the set A′ ⊆ A such that the following hold: (i) Let pm = max({p ∈ [0, 1]|∃Ai = (Vi, Ei, ρi) ∈ A s.t. v satisfies Ai with relative probability p}). Then ∀(Vi, Ei, ρi) ∈ A′ , (Vi, Ei, ρi) satisfy v with relative probability pm; (ii) ̸ ∃(Vj , Ej , ρj) ∈ A - A′ , s.t. v satisfies (Vj , Ej , ρj) with relative probability pm.

3 Threshold Queries

The most probable subvideo (MPS) algorithm tries to find all answers to a stochastic activity query (v, ℓ, (V,E, ρ), p) and is shown in Figure 2.

Algorithm MPS Input: Query (v, ℓ, (V, E, ρ), pt), where v = [s, e]. Output: The set of subvideos representing the answer to the input query and the probabilities with which the activity is satisfied. Notation: C is a set of triples (f, p, a), where f is a frame in v, p ∈ [0, 1] and a ∈ V is an activity symbol. 1. R ← ∅; 2. C ← ∅; 3. Vs ← {a ∈ V | ̸ ∃a′ ∈ V s.t. (a′ , a) ∈ E}; 4. Ve ← {a ∈ V | ̸ ∃a′ ∈ V s.t. (a, a′ ) ∈ E}; 5. for fi = s to e do 6. for every (f, p, a) ∈ C do 7. D← ℓ(fi) ∩ {b ∈ V |(a, b) ∈ E}; 8. if D ̸= ∅ then 9. C ←C - {(f, p, a)}; 10. for a′ ∈ D do 11. if p · ρ(a, a′ ) ≥ pt then 12. T ← {(f ′ , p′ , b) ∈ C|f ′ = f ∧ a′ = b}; 13. C ←C -T ∪ {(f, max(max(f ′ ,p′ ,a′)∈T (p′ ), p · ρ(a, a′ )), a′ )}; 14. endif 15. endfor 16. endfor 17. for every a ∈ Vs ∩ ℓ(fi) do 18. C ←C ∪ {(fi, 1, a)}; 19. for every (f, p, a) ∈ C s.t. a ∈ Ve do 20. R←R∪ {([f, fi], p)}; 21. C ←C - {(f, p, a)}; 22. endfor 23.endfor 24.for ([f1, f2], p) ∈ R do 25. for ([f ′1 , f ′2 ], p′ ) ∈ R- {([f1, f2], p)} do 26. if [f ′1 , f ′2 ] ⊂ [f1, f2] then 27. R←R- {([f1, f2], p)}; 28. else if ([f ′1 , f ′2 ] = [f1, f2]) ∧ (p′ > p) then 29. R←R- {([f1, f2], p)}; 30. endfor 31.endfor 32.return R;

The MPS algorithm maintains a set C of triples (f, p, a) that correspond to partially detected activities. f represents the frame when a start symbol in (V,E, ρ) is detected; this is later used to determine the subvideos that should go in the answer. p represents the product of probabilities on the path from the start symbol up to the action symbol a - the last symbol detected up to the current frame. The algorithm works by changing the state represented by C - intuitively, consisting of all paths through the activity definition for which we may reach an end node with probability above the threshold. Triples are removed fromC when it is evident that the current path will result in a probability lower than pt (lines 12-13). When all frames of the video have been analyzed, the minimality condition in Definition 3 is enforced on lines 24-31 by removing redundant subvideos.

Consider the labeling in Example 1 and the activity definition in Figure 1(a) and assume that pt = 0.01. At frame 5, the MPS algorithm will add the triple (5, 1, detect - person) to C (line 18). At frame 26, this triple will be replaced by (5, 1, present - card). Immediately after frame 213, we have C = {(5, 0.7, withdraw - cash)}. The process continues until frame 496, after which the condition on line 19 becomes true and (5, 0.056, ¬detect - person) causes the subvideo [5, 496] to be added to the answer R on line 20.

Theorem 1 (MPS correctness) Algorithm MPS terminates and for an input query (v, ℓ, (V, E, ρ), pt) it returns the set of answers R to the query - i.e.:

• ∀[s, e] ∈ R, [s, e] is an answer to (v, ℓ, (V, E, ρ), pt) as per Definition 3.
• ̸ ∃[s, e] s.t. [s, e] is an answer to (v, ℓ, (V, E, ρ), pt) and [s, e] ̸∈ R.

Theorem 2 (MPS complexity) Algorithm MPS for input query (v, ℓ, (V, E, ρ), pt) runs in time O(|v|2 · |V |).

Note that MPS makes only one pass through the video, which allows it to process a video as it comes in frame by frame. MPS is therefore well suited for scenarios (such as surveillance) in which a video is analyzed while playing.

4 Activity recognition queries

In this section, we present two methods to answer activity recognition queries where:

• v is a video with labeling ℓ.
• A = {(V1,E1, ρ1), . . . , (Vn,En, ρn)} is a finite set of activities.

One way to find the set of activities (Vi, Ei, ρi) satisfied by v with the maximum relative probability among all activities in A is to use the MPS algorithm presented earlier as follows:

1. Start with pt = 1.
2. If pt has not changed since the previous iteration, return the last set of activities obtained at step 3.
3. RunMPS and record all activities satisfiedwith relative probability at least pt.
4. If there is more than one activity in the previous set, then set pt to the average between its current and previous value and go to step 2. Otherwise if only one activity is obtained at step 3, return it.
5. If there is no activity in the previously computed set, set pt to half its previous value and go to step 2.

For reasons of space, we omit a detailed algorithmic description of naiveMPA. The algorithm's main issue is the binary search, which can run for many iterations, each taking O(n · |v|2 · |V |) steps. Our experiments show that the algorithm is particularly slow when there is more than one activity to be returned.

Example 4 Consider the set of activities depicted in Figure 1 and the following labeling: (5, {detect - person}), (26, {present - card}), (45, {insert - card}), (213, {withdraw - cash}), (320, {insert - checks}), (344, {detect - assailant}), (431, {withdraw - card}), (446, {withdraw - cash}), (496, {¬detect - person}), (500, {¬detect - person}).

naiveMPA will determine that T = ∅ until pt = 0.0625. At this point, subvideo [5, 496] satisfies the activity depicted in Figure 1(a) with relative probability 0.089 > pt, whereas the subvideo [30, 500] satisfies the activity in Figure 1(b) with relative probability of 0.044 < pt, hence the former will be returned.

The activity recognition problem problem can be more efficiently solved by maintaining state in a similar fashion to MPS for each of the activities in the set A. The algorithm is shown in Figure 3.

MPA maintains an array C[1] . . .C[n] of sets, in which C[i] holds the current state for activity (Vi,Ei, ρi) in a similar way to the C set used by MPS. m[i] holds the maximum relative probability with which A[i] has been satisfied thus far. Pruning occurs when a triple (f, p, a) in C[i] denotes a path that cannot be completed with relative probability greater than m[i] (line 13). As MPS, MPA makes only one pass through the video, thus permitting incremental computation.

Theorem 3 (MPA correctness) Algorithm MPA terminates and returns the correct answer - i.e. the set of activities {Ai} that is satisfied by v with the highest relative probability among all activities in A.

Theorem 4 (MPA complexity) AlgorithmMPA runs it time O(|v|2 · maxi∈[1,n](|Vi|) · n).

5 Experiments and Implementation

Our prototype implementation of the MP S, naiveMPA and MPA consists of approximately 1000 lines of Java code. In addition, we implemented an image processing library of approximately 25,000 lines of Java code. The library operates on video frames, identifying blobs (corresponding to objects in the video), information about such objects (e.g., whether

Algorithm MPA

Input: Video v with labeling ℓ, set of activities A. Output: (Vi,Ei, ρi) ∈ A that is satisfied by v with the highest probability p and ∀j ∈ [1, n], j ̸= i, (Vj,Ej, ρj) is either not satisfies by v or is satisfied with probability p′ < p. Notes: C is a vector of sets, each C[i] has the same structure as C for the MPS algorithm. By notation, fi(p) = p-pimin pimax-pimin , where pimax , pimin are the maximum and respectively minimum probabilities for a path in (Vi, Ei, ρi).

1. for i = 1 to n do 2. m[i] ← 0; 3. C[i] ← ∅; 4. endfor 5. for every frame fj in v do 6. for every i = 1 to n do 7. for every (f, p, a) ∈ C[i] do 8. D← ℓ(fj) ∩ {b ∈ Vi|(a, b) ∈ Ei}; 9. if D ̸= ∅ then 10. C[i] ← C[i] - {(f, p, a)}; 11. for a′ ∈ D do 12. p′ ← p · ρi(a, a′ ); 13. if fi(p′ · pb(a′ )) > max(m[1], . . . ,m[n]) then 14. T ← {(f ′ , p′ , b) ∈ C|f ′ = f ∧ a′ = b}; 15. C[i] ← C[i] - T ∪ {(f, max(max(f,p,b)∈T (p), p′ ), a′ )}; 16. endif 17. endfor 18. endfor 19. for every a ∈ {x ∈ Vi| ̸ ∃ y ∈ Vi s.t. (y, x) ∈ Ei} ∩ ℓ(fj ) do 20. C[i] ←C[i] ∪ {(fj, 1, a)}; 21. for every (f, p, a) ∈ C[i] s.t. a ∈ {x ∈ Vi| ̸ ∃y ∈ Vi s.t. (x, y) ∈ Ei} do 22. C[i] ←C[i] - {(f, p, a)}; 23. m[i] ←max(m[i], fi(p)); 24. endfor 25. endfor 26.endfor 27.return {(Ai, m[i])|m[i] = max(m[1], . . . , m[n])};

an portion of an image is a person) and implementing motion tracking primitives - this in turn leads to the ability to detect atomic actions (e.g., a person entering a room). The library implements algorithms described in [Elgammal et al., 2000; Bevilacqua, 2003; 2002; Cavallaro et al., 2005; 2000; Makarov, 1996]. Labeling data obtained from video processing was stored in a MySQL DBMS. All experiments were run on a Pentium Centrino at 1.5 Mhz, with 1.5GB of RAM, running Windows XP Professional.

Our experiments were performed over a dataset of 7 video sequences of approximately 15-30 seconds, depicting both regular bank operations and (staged) attempted robberies; the dataset is a superset of that described in [Vu et al., 2003]. We developed five activity definitions with the following notation: (a1) depicts regular customer-employee interaction; (a2) describes a non-employee that enters the vault room (the "safe"); (a3) describes a bank robbery attempt; (a4) describes a successful bank robbery - in which the assailant(s) enter the bank, then enter the safe by holding an employee hostage and then escape; (a5) describes an employee accessing the safe on behalf of a customer.

In the first set of experiments we measured the running time of MPS for activity definitions (a1)-(a4). We implemented two version of the algorithm: CA refers to the original algorithm in Figure 2; we found that in many scenarios (such as activities at an ATM), we can improve efficiency by assuming activities cannot be interleaved - which lead to the version denoted by CNA. The running times for labeling

(b) MPS frame precision and recall

Figure 4: MPS experimental results

size between 2 and 60 actions are shown in Figure 4(a) 4 . The activity definitions (a1)-(a4) are satisfied when the labeling size reaches 30, leading to a visible increase in running time; as expected, CNA is more efficient than the original CA version. We have also observed that running times are dependent on the complexity of an activity definition.

In the second set of experiments, we measure the precision and recall of MPS w.r.t. a set of 4 human annotators. The average among the annotations from the four subjects was considered the ground truth when measuring both precision and recall. The results are shown in Figure 4(b). We notice that precision is always very high and generally constant, while recall has a rather surprising variation pattern - namely, recall is monotonic with the threshold. The explanation for the apparently anomalous behavior comes from the fact that for low thresholds, the number of candidate subvideos is relatively high, hence the minimality condition causes fewer frames to appear in the answer. The monotonic behavior pattern stops when the threshold becomes high enough (.4 in this case).

4 This does not include the running time of library methods that generate the labeling.

In the third set of experiments, we analyzed the performance and answer quality for naiveMPA and MPA. The following sets of activities were used: S1 = {a5}, S2 = {a3, a5}, S3 = {a3, a4, a5} and S4 = {a2, a3, a4, a5}. The running times are shown in Figure 5. naiveMPA is especially inefficient until the labeling satisfies one of the activities - this is due to the large number of iterations taken until the threshold is close enough to 0. Running times for the two algorithms are comparable for labeling sizes greater than 30, although naiveMPA is always less efficient than MPA. The graph shows running time is generally proportional to the number of actions in the labeling.

6 Related work and Conclusions

Model-based anomaly recognition techniques provide an a priori definition of an anomalous activity and then detect new anomalous activities [Hongeng and Nevatia, 2001]. [Zhong et al., 2004; Stauffer and Grimson, 2000] define models of regular activities and bags of event n-grams to detect abnormalities. Context-free grammars have also been studied [Ivanov and Bobick, 2000; Vu et al., 2003; Nevatia et al., 2003; Narayanan, 1997]. Oliver et al. [Oliver et al., 2002] described an approach based on coupled HMMs for learning and recognizing human interactions. Dynamic Bayesian networks - which can be viewed as a generalization of HMMs -, can be used for tracking and recognizing multi-agent activities [Hamid et al., 2003]. Data-based methods detect activities based on extracted features; Cuntoor and Chellappa [Cuntoor and Chellappa, 2006] proposed a characterization of events based on anti-eigenvalues, which are sensitive to changes. Parameswaran and Chellappa [Parameswaran and Chellappa, 2003] computed view invariant representations for human actions in both 2D and 3D.

Ontologies have been recently used in different contexts for video surveillance. Chen et al [Chen et al., 2004] use ontologies for analyzing social interaction in nursing homes; Hakeem et al use ontologies for classification of meeting videos [Hakeem and Shah, 2004]. Georis et al [Georis et al., 2004] use ontologies to recognize activities in a bank monitoring setting. As a result of the Video Event Challenge Workshops held in 2003, ontologies have been defined for six domains of video surveillance, among which Visual Bank Monitoring and Airport-Tarmac Security; the workshop also led to the development of two languages. The Video Event Representation Language (VERL) [Hobbs et al., 2004], provides an ontological representation of complex events in terms of simpler sub-events. The Video Event Markup Language (VEML) is used to annotate VERL events in videos.

Our work differs from the above approaches in the following respects:

1. Our stochastic activity model is not based on features extracted from data or on state-space representations, but on atomic actions that are recognizable by image understanding primitives.
2. To our knowledge, MPA is one of the very few algorithms that addresses the issue of detecting the most likely activity from a given set to have occurred in a certain video. In contrast, model-based representations usually train a specific model to recognize specific situations.
3. To our knowledge, we are the first to find the minimal video segments that contain an event with probability exceeding a threshold - this is important as a security guard wants to zero in immediately on the part of the video that contains the desired activity.