Finding "Unexplained" Activities in Video

1 Introduction

Video surveillance is omnipresent. For instance, airport baggage areas are continuously monitored for suspicious activities. In crime-ridden neighborhoods, police often monitor streets and parking lots using video surveillance. In Israel, highways are monitored by a central authority for suspicious activities. However, all these applications search for known activities - activities that have been identified in advance as being either "normal" or "abnormal". For instance, in the highway application, security officers may look both for normal behavior (e.g. driving along the highway in a certain speed range unless traffic is slow) as well as "suspicious" behavior (e.g. stopping the car near a bridge, taking a package out and leaving it on the side of the road before driving away).

Most past work on activity detection uses a priori definitions of normal/abnormal activities and explicitly searches for activity occurrences [Hongeng and Nevatia, 2001]. Hidden Markov Models have been applied to problems ranging from gesture recognition [Wilson and Bobick, 1999] to complex activity recognition [Vaswani et al., 2005]. [Oliver et al., 2002] describes an approach based on coupled HMMs (CHMMs) for learning and recognizing human interactions.

Dynamic Bayesian Networks (DBNs) have been used to capture causal relationships between observations and hidden states by [Hamid et al., 2003] who used them to detect complex, multi-agent activities. [Albanese et al., 2007] developed a stochastic automaton based language to detect activities in video, while [Cuntoor et al., 2008] presented an HMM-based algorithm. Alternatively, [Zhong et al., 2004] learn models of normal behavior and detect anomalies by finding deviations from normal behaviors. An approach for both single and multiple actor activity recognition has been proposed in [Hongeng et al., 2004], where Bayesian networks and probabilistic finite state automata are used to describe single actor activities, and the interaction of multiple actors is modeled by an event graph.

In contrast, in this paper, we assume we are given some set A of activity definitions expressed as stochastic automata with temporal constraints - we extend the stochastic automata of [Albanese et al., 2007] as this seems to be a common denominator underlying the HMM and DBN frameworks. A can consist of either "normal" activities or "suspicious" activities or both. In this paper, we try to find video sequences that are not "explained" by any of the activities in A. As an example of why detecting activities that are neither 'normal', nor 'abnormal' is a very important problem in many applications, consider a video surveillance application in an airport. While we do want to find instances of known suspicious activities, there may be many other dangerous activities for which no model exists yet. Such previously "unknown" activities can be flagged as unexplained activities in our framework.

In order to achieve this, we define a possible-worlds based model and define the probability that a sequence of video is totally (or partially) unexplained. Based on this, users can specify a probability threshold and look for all sequences that are totally (or partially) unexplained with a probability exceeding the threshold. We then define two algorithms - the FindTUA algorithm finds all subsequences of a video that are totally unexplained, while the FindPUA algorithm finds all subsequences of the video that are partially unexplained. We develop a prototype implementation and report on experiments showing that the algorithms are accurate and efficient.

The paper is organized as follows. Section 2 sets up the basic definitions of the activity model extending [Albanese et al., 2007] in a straightforward way. Section 3 defines the probability that a video sequence is totally (or partially) unexplained. Section 4 derives a set of theorems that enable fast search of totally and partially unexplained video sequences. Section 5 presents the FindTUA and FindPUA algorithms. Section 6 describes our experiments.

2 Basic ActivityModel

This section presents a slight variant of the stochastic activity model of [Albanese et al., 2007] as a starting point. The novel contributions of this paper start in the next section. We assume the existence of a finite set S of action symbols, corresponding to atomic actions that can be detected by image understanding methods.

Definition 2.1 (Stochastic activity) A stochastic activity is a labeled directed graph A = (V, E, δ, ρ) where

• V is a finite set of nodes labeled with action symbols from S;
• E ⊆ V ×V is a set of edges;
• δ : E → N+ is a function that associates, with each edge e = (vi, vj), an upper bound on the time that can elapse between vi and vj;
• ρ is a function that associates, with each node v ∈ V having out-degree 1 or more, a probability distribution on {〈v, v′ 〉 | 〈v, v′ 〉 ∈ E}, i.e., ∑ 〈v,v′ 〉∈E ρ(〈v, v′ 〉) = 1;
• {v ∈ V | ∄ v′ ∈ V s.t. 〈v′ , v〉 ∈ E} ̸= ∅, i.e., there exists at least one start node in the activity definition;
• {v ∈ V | ∄ v′ ∈ V s.t. 〈v, v′ 〉 ∈ E} ̸= ∅, i.e., there exists at least one end node in the activity definition.

Figure 1 shows an example of stochastic activity modeling deposits at an Automatic Teller Machine (ATM). Each edge e is labeled with (δ(e), ρ(e)). For instance, the two edges starting at node insertCard mean that there is a 50% probability of going to node insertChecks and a 50% probability of going to node insertCash from node insertCard. In addition, it is required that insertChecks and insertCash follow insertCard within 2 and 1 time units, respectively. In general, actions can be easily detected by either an image processing algorithm (e.g. detectPerson would check if a person is present in the image) or a sensor (e.g. to detect if insertCard holds).

The basic difference between this model and the one of [Albanese et al., 2007] is the addition of the function δ which allows us to express constraints on the maximum "temporal distance" between two actions for them to be considered part of the same activity.

Definition 2.2 (Stochastic activity instance) An instance of a stochastic activity (V, E, δ, ρ) is a sequence 〈s1, . . . , sm〉 of nodes in V such that

• 〈si, si+1〉 ∈ E for 1 ≤ i <m;
• {s | 〈s, s1〉 ∈ E} = ∅, i.e., s1 is a start node; and
• {s | 〈sm, s〉 ∈ E} = ∅, i.e., sm is an end node.

The probability of the instance is ∏m-1 i=1 ρ(〈si, si+1〉).

Thus, an instance of a stochastic activity A is a path in A from a start node to an end node. In Figure 1, 〈detectPerson, insertCard, insertCash, withdrawCard〉 is an instance with probability 0.35.

A video is a finite sequence of frames. Each frame f has an associated timestamp, denoted f.ts; without loss of generality, we assume timestamps to be positive integers. A labeling ℓ of a video v is a mapping ℓ : v → 2S that takes a video frame f ∈ v as input, and returns a set of action symbols ℓ(f) ⊆ S as output. Intuitively, a labeling can be computed via an appropriate suite of image processing algorithms and specifies what actions are detected in each frame of a video.

Example 2.1 Consider a video v = 〈f1, f2, f3, f4, f5〉, with fi.ts=i for 1≤i≤5. A possible labeling ℓ of v is: ℓ(f1)= {detectPerson}, ℓ(f2)={insertCard}, ℓ(f3)={insertCash}, ℓ(f4)={withdrawCash}, ℓ(f5)={withdrawCard}.

Throughout the paper, we use the following terminology and notation for sequences. Let S1 = 〈a1, . . . , an〉 and S2 = 〈b1, . . . , bm〉 be two sequences. We say that S2 is a subsequence of S1 iff there exist 1 ≤ j1 < j2 < . . . < jm ≤ n s.t. bi=aji for 1 ≤ i ≤ m. If ji=ji+1 - 1 for 1 ≤ i < m, then S2 is a contiguous subsequence of S1. We write S1 ∩ S2 ̸= ∅ iff S1 and S2 have a common element and write e ∈ S1 iff e is an element appearing in S1. The concatenation of S1 and S2, i.e., the sequence 〈a1, . . . , an, b1, . . . , bm〉, is denoted by S1 · S2. Finally, we use |S1| to denote the length of S1, that is, the number of elements in S1.

Definition 2.3 (Activity occurrence) Let v be a video, ℓ a labeling of v, and A= (V,E, δ, ρ) a stochastic activity. An occurrence o of A in v w.r.t. ℓ is a sequence 〈(f1, s1), . . . , (fm, sm)〉 such that

• 〈f1, . . . , fm〉 is a subsequence of v,
• 〈s1, . . . , sm〉 is an instance of A,
• si ∈ ℓ(fi), for 1 ≤ i ≤m, and 1
• fi+1.ts - fi.ts ≤ δ(〈si, si+1〉), for 1 ≤ i < m.

The probability of o, denoted p(o), is the probability of the instance 〈s1, . . . , sm〉.

When concurrently monitoring multiple activities, shorter activity instances generally tend to have higher probability. To remedy this, we normalize occurrence probabilities by introducing the relative probability p∗ (o) of an occurrence o of activity A as p∗ (o) = p(o) pmax , where pmax is the highest probability of any instance of A.

1 With a slight abuse of notation, we use si to refer to both node si and the action symbol labeling it.

Example 2.2 Consider the video and the labeling of Example 2.1. An occurrence of the activity of Figure 1 is o = 〈(f1, detectPerson), (f2, insertCard), (f3, insertCash), (f5, withdrawCard)〉, and p∗ (o) = 0.875.

We use O(v, ℓ) to denote the set of all activity occurrences in v w.r.t. ℓ. Whenever v and ℓ are clear from the context, we write O instead of O(v, ℓ).

3 Unexplained Activity ProbabilityModel

In this section we define the probability that a video sequence is unexplained, given a set A of known activities. We start by noting that the definition of probability of an activity occurring in a video can implicitly involve conflicts. For instance, consider the activity occurrence o in Example 2.2 and consider a second activity occurrence o′ such that (f1, detectPerson) ∈ o′ . In this case, there is an implicit conflict because (f1, detectPerson) belongs to both occurrences, but in fact, detectPerson can only belong to one activity occurrence, i.e. though o and o′ may both have a non-zero probability of occurrence, the probability that these two activity occurrences coexist is 0. Formally, we say two activity occurrences o, o′ conflict, denoted o ≁ o′ , iff o ∩ o′ ̸= ∅. We now use this to define possible worlds.

Definition 3.1 (Possible world) A possible world for a video v and a labeling ℓ is a subset w of O s.t. ∄oi, oj ∈ w, oi ≁ oj .

Thus, a possible world is a set of activity occurrences which do not conflict with one another, i.e., an action symbol in a frame cannot belong to two distinct activity occurrences in the same world. We use W(v, ℓ) to denote the set of all possible worlds for a video v and a labeling ℓ; whenever v and ℓ are clear from the context, we simply write W.

Example 3.1 Consider a video with two conflicting occurrences o1, o2. There are 3 possible worlds: w0 = ∅, w1 = {o1}, and w2 = {o2}. Note that {o1, o2} is not a world as o1 ≁ o2. Each world represents a way of explaining what is observed. The first world corresponds to the case where nothing is explained, the second and third worlds correspond to the scenarios where we use one of the two possible occurrences to explain the observed action symbols.

Note that any subset of O not containing conflicting occurrences is a legitimate possible world - possible worlds are not required to be maximal w.r.t. ⊆. In the above example, the empty set is a possible world even though there are two other possible worlds w1 = {o1} and w2 = {o2} which are supersets of it. The reason is that o1 and o2 are uncertain, so the scenario where neither o1 nor o2 occurs is a legitimate one. We further illustrate this point below.

Example 3.2 Suppose we have a video where a single occurrence o has p∗ (o)=0.6. In this case, it is natural to say that there are two possible worlds w0 =∅ and w1 ={o} and expect the probabilities of w0 and w1 to be 0.4 and 0.6, respectively. By restricting ourselves to maximal possible worlds only, we would have only one possible world, w1, whose probability is 1, which is wrong. Nevertheless, if p∗ (o)=1, w1 is the only possible scenario. This can be achieved by assigning 0 and 1 to the probabilities of w0 and w1, respectively.

We use ∗≁ to denote the transitive closure of ≁. Clearly, ∗≁ is an equivalence relation and determines a partition of O into equivalence classes O1, . . . , Om.

Example 3.3 Suppose we have a video v = 〈f1, . . . , f16〉 and a labeling ℓ such that five occurrences o1, o2, o3, o4, o5 are detected as depicted in Figure 2, that is, o1 ≁ o2, o2 ≁ o3, and o4 ≁ o5. There are two equivalence classes determined by ∗≁, namely O1 = {o1, o2, o3} and O2 = {o4, o5}.

The equivalence classes determined by ∗≁ lead to a conflictbased partitioning of a video.

Definition 3.2 (Conflict-Based Partitioning) Let v be a video, ℓ a labeling, and O1, . . . ,Om the equivalence classes determined by ∗≁. A Conflict-Based Partitioning (CBP) of v (w.r.t. ℓ) is a sequence 〈(v1, ℓ1), . . . , (vm, ℓm)〉 such that:

• v1 · . . . · vm = v;
• ℓi is the restriction of ℓ to vi, i.e., it is a labeling of vi s.t. ∀f ∈ vi, ℓi(f) = ℓ(f), for 1 ≤ i ≤ m; and
• O(vi, ℓi) = Oi, for 1 ≤ i ≤ m.

The vi's are called segments.

Example 3.4 A CBP of the video in Example 3.3 is 〈(v1, ℓ1), (v2, ℓ2)〉, where v1 = 〈f1, . . . , f9〉, v2 = 〈f10, . . . , f16〉, ℓ1 and ℓ2 are the restrictions of ℓ to v1 and v2, respectively. Another partitioning of the same video is v1 = 〈f1, . . . , f10〉 and v2 = 〈f11, . . . , f16〉.

Thus, activity occurrences determine a set of possible worlds (intuitively, different ways of explaining what is in the video). We wish to find a probability distribution over all possible worlds that (i) is consistent with the relative probabilities of the occurrences, and (ii) takes conflicts into account. We assume the user specifies a function Weight : A → R+ which assigns a weight to each activity and prioritizes the importance of the activity for his needs. The weight of an occurrence o of activity A is the weight of A. We use C(o) to denote the set of occurrences conflicting with o, i.e., C(o) = {o′ | o′ ∈ O ∧ o′ ≁ o}. Note that C(o) includes o itself and C(o) = {o} when o does not conflict with any other occurrence. Finally, we assume that activity occurrences belonging to different segments are independent events. Suppose pi denotes the (unknown) probability of world wi. As we know the probability of occurrences, and as each occurrence occurs in certain worlds, we can induce a set of nonlinear constraints that are used to learn the values of the pi's.

Definition 3.3 Let v be a video, ℓ a labeling, and O1, . . . ,Om the equivalence classes determined by ∗≁. We define the non-linear constraints NLC(v, ℓ) as follows:

The first two types of constraints enforce a probability distribution over the set of possible worlds. The third type of constraint ensures that the probability of occurrence o - which is the sum of the probabilities of the worlds containing o - is equal to its relative probability p∗ (o) weighted by Weight(o) ∑oj∈C(o) Weight(oj) , the latter being the weight of o divided by the sum of the weights of the occurrences conflicting with o. Note that: (i) the value on the right-hand side of the third type of constraint decreases as the amount of conflict increases, (ii) if an occurrence o is not conflicting with any other occurrence, then its probability ∑wi∈W s.t. o∈wi pi is equal to p∗ (o), namely the probability returned by the stochastic automaton. The last kind of constraint reflects the independence between segments.

In general NLC(v, ℓ) might admit multiple solutions.

Example 3.5 Consider a single-segment video consisting of frames f1, . . . , f9 shown in Figure 2. Suppose three occurrences o1, o2, o3 have been detected with relative probability 0.3, 0.6, and 0.5 respectively. Suppose the weights of o1, o2, o3 are 1, 2, 3, respectively. Five worlds are possible in this case: w0 = ∅, w1 = {o1}, w2 = {o2}, w3 = {o3}, and w4 = {o1, o3}. Then, NLC(v, ℓ) is as follows (we omit the constraints expressing independence among segments because, in this case, they are trivial):

which has multiple solutions. One solution is p0 = 0.4, p1 = 0.1, p2 = 0.2, p3 = 0.3, p4 = 0. Another solution is p0 = 0.5, p1 = 0, p2 = 0.2, p3 = 0.2, p4 = 0.1.

In the rest of the paper, we assume that NLC(v, ℓ) is solvable. We say that a sequence S = 〈(f1, s1), . . . , (fn, sn)〉 occurs in a video v w.r.t. a labeling ℓ iff 〈f1, . . . , fn〉 is a contiguous subsequence of v and si ∈ ℓ(fi) for 1 ≤ i ≤ n. We give two semantics for S to be unexplained in a world w:

1. S is totally unexplained in w, denoted w⊭TS, iff ∀(fi, si) ∈ S, ∄o ∈ w, (fi, si) ∈ o;
2. S is partially unexplained in w, denoted w⊭PS, iff ∃(fi, si) ∈ S, ∄o ∈ w, (fi, si) ∈ o.

Intuitively, S is totally (resp. partially) unexplained in w iff w does not explain every (resp. at least one) symbol of S. We now define the probability that a sequence occurring in a video is totally or partially unexplained.

Definition 3.4 Let v be a video, ℓ a labeling, and S a sequence occurring in v w.r.t. ℓ. The probability interval that S

is totally unexplained in v w.r.t. ℓ is IT (S) = [l, u], where:

Likewise, the probability interval that S is partially unexplained in v w.r.t. ℓ is IP (S) = [l′ , u′ ], where:

Thus, given a solution of NLC(v, ℓ), the probability that a sequence S occurring in v is totally (resp. partially) unexplained is the sum of the probabilities of the worlds in which S is totally (resp. partially) unexplained. As NLC(v, ℓ) may have multiple solutions, we find the tightest interval [l, u] (resp. [l′ , u′ ]) s.t. this probability is in [l, u] (resp. [l′ , u′ ]) for any solution. Different criteria can be used to infer a value from an interval [l, u], e.g. the MIN l, the MAX u, the average (i.e., (l +u)/2), etc. Clearly, the only requirement is that this value has to be in [l, u]. In the rest of the paper we assume that one of the above criteria has been chosen - PT (S) (resp. PP (S)) denotes the probability that S is totally (resp. partially) unexplained.

Given two sequences S1 and S2 occurring in a video, it can be easily verified that if S1 is a subsequence of S2, then PT (S1) ≥ PT (S2) and PP (S1) ≤ PP (S2).

Definition 3.5 (Unexplained activity occurrence) Let v be a video, ℓ a labeling, τ ∈ [0, 1] a probability threshold, and L ∈ N+ a length threshold. Then,

• a totally unexplained activity occurrence is a sequence S occurring in v s.t. (i) PT (S) ≥ τ, (ii) |S| ≥ L, and (iii) S is maximal, i.e., there does not exist a sequence S′ ̸= S occurring in v s.t. S is a subsequence of S′ , PT (S′ ) ≥ τ , and |S′ | ≥ L.
• a partially unexplained activity occurrence is a sequence S occurring in v s.t. (i) PP (S) ≥ τ, (ii) |S| ≥ L, and (iii) S is minimal, i.e., there does not exist a sequence S′ ̸= S occurring in v s.t. S′ is a subsequence of S, PP (S′ ) ≥ τ , and |S′ | ≥ L.

In the definition above, L is the minimum length a sequence must be for it to be considered a possible unexplained activity occurrence. Totally unexplained occurrences S have to be maximal because once we find S, then any sub-sequence of it has a probability of being (totally) unexplained greater than or equal to the probability of S. On the other hand, partially unexplained occurrences S′ have to be minimal because once we find S′ , then any super-sequence of it has a probability of being (partially) unexplained greater than or equal to the one of S.

Intuitively, an unexplained activity occurrence is a sequence of action symbols that are observed in the video and poorly explained by the known activity models. Such sequences might correspond to unknown variants of known activities or to entirely new - and unknown - activities.

An Unexplained Activity Problem (UAP) instance is a 4tuple 〈v, ℓ, τ,L〉, where v is a video, ℓ is a labeling of v, τ ∈ [0, 1] is a probability threshold, and L ∈ N+ is a length threshold. The desired result is all totally/partially unexplained activity occurrences.

4 Properties of UAPs

In this section, we derive properties of the above model that can be leveraged (in the next section) to devise efficient algorithms to find unexplained activities. Specifically, we first show an interesting property concerning the resolution of NLC(v, ℓ) (some subsequent results rely on it); then, in the following two subsections, we consider specific properties for totally and partially unexplained activities.

For a given video v and labeling ℓ, we now show that if 〈(v1, ℓ1), . . . , (vm, ℓm)〉 is a CBP, then we can find the solutions of the non-linear constraints NLC(v, ℓ) by solving m smaller sets of linear constraints. 2 We define LC(v, ℓ) as the set of linear constraints of NLC(v, ℓ) (thus, we include all the constraints of Definition 3.3 except for the last kind). Henceforth, we use W to denote W(v, l) and Wi to denote W(vi, ℓi), 1 ≤ i ≤ m. A solution of NLC(v, ℓ) is a mapping P : W → [0, 1] which satisfies NLC(v, ℓ). Likewise, a solution of LC(vi, ℓi) is a mapping Pi : Wi → [0, 1] which satisfies LC(vi, ℓi). It is important to note that W = {w1 ∪ . . . ∪ wm | wi ∈ Wi, 1 ≤ i ≤ m}.

Theorem 1 Let v be a video, ℓ a labeling, and 〈(v1, ℓ1), . . . , (vm, ℓm)〉 a CBP. P is a solution of NLC(v, ℓ) iff ∀i ∈ [1,m] there exists a solution Pi of LC(vi, ℓi) s.t. P(⋃mi=1 wi) = ∏mi=1 Pi(wi) for every w1 ∈ W1, . . . , wm ∈ Wm.

Consider a video v and a labeling ℓ, and let 〈(v1, ℓ1), . . . , (vm, ℓm)〉 be a CBP. Given a sequence S = 〈(f1, s1), . . . , (fq, sq)〉 occurring in v, we say that vi, vi+1, . . . , vi+n (1 ≤ i ≤ i + n ≤ m) are the sub-videos containing S iff f1 ∈ vi and fq ∈ vi+n. In other words, S spans the sub-videos vi, vi+1, . . . , vi+n: it starts at some point in sub-video vi (as vi contains the first frame of S) and ends at some point in sub-video vi+n (as vi+n contains the last frame of S). In addition, we use Sk to denote the projection of S on the k-th sub-video vk (i ≤ k ≤ i+n), that is, the subsequence of S containing all the pairs (f, s) ∈ S with f ∈ vk.

4.1 Totally unexplained activities

The following theorem says that we can compute IT (S) by solving LC (which are linear constraints) for each sub-video containing S (instead of solving a non-linear set of constraints for the whole video).

Theorem 2 Consider a video v and a labeling ℓ. Let 〈(v1, ℓ1), . . . , (vm, ℓm)〉 be a CBP and 〈vi, . . . , vi+n〉 be the sub-videos containing a sequence S occurring in v. For

2 This therefore yields two benefits: first it allows us to solve a smaller set of constraints, and second, it allows us to solve linear constraints which are usually easier to solve than nonlinear ones.

The following theorem provides a sufficient condition for a pair (f, s) not to be included in any sequence S occurring in v and having PT (S) ≥ τ .

If the condition stated in the theorem above holds for a pair (f, s), then we say that (f, s) is sufficiently explained. It is important to note that to check whether a pair (f, s) is sufficiently explained, we do not need to solve any set of linear or non-linear constraints, since ε is computed by simply summing the (weighted) probabilities of the occurrences containing (f, s). Thus, this result yields a further efficiency. A frame f is sufficiently explained iff (f, s) is sufficiently explained for every s ∈ ℓ(f). If (f, s) is sufficiently explained, then it can be disregarded for the purpose of identifying unexplained activity occurrences, and, in addition, this may allow us to disregard entire parts of videos as shown in the example below.

Example 4.1 Consider a UAP instance 〈v, ℓ, τ,L〉 where v = 〈f1, . . . , f9〉 and ℓ is s.t. ℓ(fi) = {si} for 1 ≤ i ≤ 9, as depicted in the figure below.

Suppose that L = 3 and that (f1, s1), (f4, s4), (f6, s6) are sufficiently explained, that is, because of Theorem 3, we can conclude that there is no sequence S occurring in v with PT (S) ≥ τ and containing any of them. Even though we have been able to apply the theorem to a few (fi, si) pairs, we can conclude that no unexplained activity occurrence can be found before f7, because L = 3.

Given a UAP instance I = 〈v, ℓ, τ,L〉 and a contiguous subsequence v′ of v, v′ is relevant iff (i) |v′ | ≥ L, (ii) ∀f ∈ v′ , f is not sufficiently explained, and (iii) v′ is maximal (i.e., there does not exist v′′ ̸= v′ s.t. v′ is a subsequence of v′′ and v′′ satisfies (i) and (ii)). We use relevant(I) to denote the set of relevant sub-videos.

PDFill PDF Editor with Free Writer and Tools Theorem 3 entails that relevant sub-videos can be individually considered when looking for totally unexplained activities because there is no totally unexplained activity spanning two different relevant sub-videos.

4.2 Partially unexplained activities

The following theorem states that we can compute IP (S) by solving NLC for the sub-video consisting of the segments containing S (instead of solving NLC for the whole video).

Theorem 4 Consider a video v and a labeling ℓ. Let 〈(v1, ℓ1), . . . , (vm, ℓm)〉 be a CBP and 〈vi, . . . , vi+n〉 be the sub-videos containing a sequence S occurring in v. Let v∗ = vi · . . . · vi+n and ℓ∗ be a labeling for v∗ s.t., for every f ∈ v∗ , ℓ∗ (f) = ℓ(f). IP (S) computed w.r.t. v and ℓ is equal to IP (S) computed w.r.t. v∗ and ℓ∗ .

5 Algorithms

We now present algorithms to find totally and partially unexplained activities. Due to lack of space, we assume |ℓ(f)| = 1 for every frame f in a video (this makes the algorithms much more concise - generalization to the case of multiple action symbols per frame is straightforward 3 ). Given a video v = {f1, . . . , fn}, we use v(i, j) (1 ≤ i ≤ j ≤ n) to denote the sequence S = 〈(fi, si), . . . , (fj, sj)〉, where sk is the only element in ℓ(fk), i ≤ k ≤ j.

The FindTUA algorithm computes all totally unexplained activities in a video. Leveraging Theorem 3, FindTUA only considers relevant subsequences of v. When the algorithm finds a sequence v′ (start, end) of length at least L having a probability of being unexplained greater than or equal to τ (line 5), then the algorithm makes it maximal by adding frames on the right. Instead of adding one frame at a time, v′ (start, end) is extended of L frames at a time until its probability drops below τ (lines 7-10); then, the exact maximum length of the unexplained activity is found (line 12, this is accomplished by performing a binary search between s and e). Note that PT is computed by applying Theorem 2.

Algorithm 1 FindTUA

Input: UAP instance I = 〈v, ℓ, τ, L〉 Output: Set of totally unexplained activities 1: Sol = ∅ 2: for all v′ ∈ relevant(I) do 3: start = 1; end = L 4: repeat 5: if PT (v′ (start, end)) ≥ τ then 6: end′ = end 7: while end < |v′ | do 8: end = min{end + L, |v′ |} 9: if PT (v′ (start, end)) < τ then 10: break 11: s = max{end -L, end′ }; e = end 12: end = max{mid | s ≤ mid ≤ e ∧PT (v′ (start, mid)) ≥ τ} 13: S = v′ (start, end); Add S to Sol; 14: start = start + 1; end = start + |S| - 1 15: else 16: start = start + 1; end = max{end, start +L- 1} 17: until end > |v′ | 18: return Sol

The FindPUA algorithm below computes all partially unexplained activities. To find an unexplained activity, it starts with a sequence of a certain length (at least L) and adds frames on the right of the sequence until its probability of being unexplained is greater than or equal to τ . As in the case of FindTUA, this is done not by adding one frame at a time, but adding L frames at a time (lines 5-8) and then determining the exact minimal length (line 11, this is accomplished by performing a binary search between s and e). The sequence is then shortened on the left making it minimal (line 15, this is again done by performing a binary search instead of proceeding one frame at a time). Note that PP is computed by applying Theorem 4.

3 Indeed, it suffices to consider the different sequences given by the different action symbols.

Algorithm 2 FindPUA

Input: UAP instance I = 〈v, ℓ, τ, L〉 Output: Set of partially unexplained activities 1: Sol = ∅; start = 1; end = L 2: while end ≤ |v| do 3: if PP (v(start, end)) < τ then 4: end′ = end 5: while end < |v| do 6: end = min{end + L, |v|} 7: if PP (v(start, end)) ≥ τ then 8: break 9: if PP (v(start, end)) ≥ τ then 10: s = max{end′ + 1, end -L+ 1}; e = end 11: end = min{mid | s ≤ mid ≤ e ∧ PP (v(start, mid)) ≥ τ} 12: else 13: return Sol 14: s′ = start; e′ = end - L + 1 15: start = max{mid | s′ ≤mid ≤ e′ ∧PP (v(mid, end)) ≥ τ} 16: S = v(start, end); Add S to Sol 17: start = start + 1; end = start + |S| - 1 18: return Sol

6 Experimental Results

Our prototype implementation of the proposed framework consists of:

• an image processing library, which performs low-level processing of video frames, including object tracking and classification;
• a video labeler, which maps frames to action symbols, based on the output of the image processing stage;
• an activity recognition algorithm, based on [Albanese et al., 2007], which identifies all possible occurrences of known activities;
• a UAP engine, which implements algorithms FindTUA and FindPUA in 7500 lines of Java code.

We generated a video by concatenating multiple videos from the ITEA CANDELA dataset, a publicly available dataset depicting a number of staged package exchanges and object drop-offs and pick-ups (http://www.multitel. be/˜va/candela/abandon.html). We evaluated precision and recall against a ground truth provided by human annotators. Annotators were informed about known activities by providing them with a graphical representation of the activity models (for an example, see Figure 1). They were asked to watch the video and identify video segments where totally (resp. partially) unexplained activities occurred.

Running time. Figure 3 shows the processing time of FindTUA and FindPUA as a function of the length of the video. Note that both axes are on a logarithmic scale. It is clear that both algorithms run in time linear in the length of the video, and significantly outperform na¨ıve algorithms that do not use the optimizations of Theorems 2, 3, and 4.

Precision/recall. Given a set A of activity definitions, let {Sa i }i∈[1,m] denote the set of unexplained sequences returned by our algorithms, and let {Sh j }j∈[1,n] denote the set of sequences flagged as unexplained by human annotators. We evaluate precision and recall as

where Sa i ≈p Sh j means that Sa i and Sh j overlap by a percentage no smaller than p.

The precision/recall graph for algorithms FindTUA and FindPUA, when p = 75%, is reported in Figure 4. The value of the probability threshold τ that maximizes the Fmeasure for FindTUA and FindPUA is 0.6. For τ = 0.6, FindTUA achieves P = 70% and R = 69%, whereas FindPUA achieves P = 67% and R = 72%.

7 Conclusions

Suppose A is a given set of known activity models and v is a video. This paper presents a possible worlds framework to find all subsequences of v that cannot be explained by an activity in A with a probability exceeding a user-specified threshold. We develop the FindTUA and FindPUA algorithms to find totally and partially unexplained sequences respectively.

Finally, we present a prototype implementation of the proposed framework, and show, through experiments, that algorithms FindTUA and FindPUA work well in practice on a real world video data set.