Interval-based Activity Recognition

Abstract

Activity recognition refers to the detection of temporal combinations of `low-level' or `short-term' activities on sensor data. Various types of uncertainty exist in activity recognition systems and this often leads to erroneous detection. Typically, the frameworks aiming to handle uncertainty compute the probability of the occurrence of activities at each time-point. We extend this approach by de ning the probability of a maximal interval and the credibility rate for such intervals.

Introduction

2.1

Background

holdsAt(F = V ; T ) initiatedAt(F = V ; Ts ); Ts < T ; not broken(F = V ; Ts ; T ): broken(F = V ; Ts ; T )

terminatedAt(F = V ; Tf ); Ts < Tf < T : broken(F = V ; Ts ; T )

initiatedAt(F = V 0; Tf ); V 6= V 0; Ts < Tf < T : According to axiom (1), F = V holds at some time-point T if it has been initiated by an event previously and has not been `broken' in the meantime. This expresses the law of inertia. F = V is `broken' in (Ts; T ) if it is terminated (see axiom (2)) or F = V 0 is initiated, for some V 0 6= V (see axiom (3)). The de nitions of initiatedAt and terminatedAt are domain-speci c. Consider, for example, the (partial) de nition of moving from the domain of activity recognition: F is a uent |a property that is allowed to have di erent values at di erent points in time|the term F = V denotes that uent F has value V . The domainindependent axioms are presented below: (1) (2) (3) (4) (5) initiatedAt(moving (P1 ; P2 ) = true; T ) happensAt(walking (P1 ); T ); happensAt(walking (P2 ); T ); holdsAt(close(P1 ; P2 ) = true; T ); holdsAt(similarOrientation(P1 ; P2 ) = true; T ): terminatedAt(moving (P1 ; P2 ) = true; T ) happensAt(walking (P1 ); T ); holdsAt(close(P1 ; P2 ) = false; T ): moving is a long-term activity (LTA) expressed as a Boolean uent, and dened in terms of a set of short-term activities (STA) expressed as instantaneous events, and contextual information detected on video content. walking , running , active and inactive are mutually exclusive STA detected on video frames. Each such STA is accompanied by the coordinates and orientation of the tracked entity in question. These are the input of the activity recognition system. close(P1 ; P2 ) is true when the distance between the tracked entities P1 and P2 is smaller than some pre-de ned threshold of pixel positions. Similarly, similarOrientation(P1 ; P2 ) is true when the di erence in orientation of P1 and P2 is less than 45 degrees. According to rule (4), moving (P1 ; P2 ) = true is said to be initiated when both P1 and P2 are walking, they are close to each other and have a similar orientation. Furthermore, moving (P1 ; P2 ) = true is said to be terminated when the two tracked persons walk away from each other (see rule (5)). The remaining terminating conditions are de ned in a similar manner [ 12 ].

Note that initiatedAt(F = V; T ) does not necessarily imply that F 6=V at T . Similarly, terminatedAt(F = V; T ) does not necessarily imply that F = V at T [ 3 ]. Suppose that F = V is initiated at time-points 10 and 20 and terminated at time-points 25 and 30 (and at no other time-points). In that case F = V holds at all T such that 10<T 25. 2.2

Point-based Probabilistic Event Calculus Prob-EC [ 12 ] is a probabilistic version of the Event Calculus implemented in ProbLog [ 7 ]. The aim of Prob-EC is to compute the probabilities of holdsAt(F = V ; T ), i.e. the truth value of F = V at time-point T . A Prob-EC programme consists of probabilistic facts, the domain-indepedent rules of the Event Calculus (see rules (1){(3)), as well as domain-speci c rules (such as rules (4) and (5)). Probabilistic facts are de ned as p :: f , meaning that f holds as true with probability p in each of its groundings. All these facts represent independent random variables. The marginal probability of the head holding is therefore the product of the probabilities of the facts holding. This way, Prob-EC deals with uncertainty in the input data. The probability of holdsAt(LTA = true; T ) is equal to the probability of the disjunction of the initiation conditions of LTA = true before T , assuming that LTA = true has not been `broken' in the meantime. Hence, multiple initiations of LTA = true increase its probability. Moreover, if LTA = true is `broken' with probability p1 , then the probability of LTA = true becomes equal to the product of the probability of the disjunction of initiations and 1 p1 (see axiom (1)). Therefore, the higher the probability p1 the more signi cant the decrease of the probability of LTA = true. Furthermore, consecutive terminations decrease further the probability of LTA = true [ 12 ]. 3

Probabilistic Maximal Interval Estimation

An instantaneous indication of an activity, by means of holdsAt, for example, may lead to erroneous detection, which may be due to the unreliability of the sensors or due to the inaccuracy of the recognition patterns. Towards this, we propose a Probabilistic Interval based Event Calculus (PIEC ). Figure 1 shows a high-level description of the inference procedure. First, we use Prob-EC, as described in the previous section, to compute the probabilities of LTA at each time-point given the probabilistic `short-term' activities (STA). The recognition is based on domain-speci c rules of initiation and termination, such as rules (4){(5). The next phase consists of the interval-based activity recognition. With respect to a probability threshold, PIEC computes all `probabilistic maximal intervals', i.e. the maximal intervals within which an activity is likely to hold. De nition 1. The probability of interval ILTA =[i ; j ] length(ILTA) = j i +1 time-points is de ned as of

LTA with P (ILTA) =

Pjk = i P (holdsAt(LTA; k )) length(ILTA) :

In other words, the probability of an interval is equal to the average of the probabilities at the time-points that it contains.

A key concept of PIEC is that of probabilistic maximal interval: De nition 2. A probabilistic maximal interval ILTA =[i ; j ] of LTA is an interval such that, given some threshold T 2 [0; 1], P (ILTA) T , and there is no other interval IL0TA such that P (IL0TA) T and ILTA is a sub-interval of IL0TA. Instantaneous

Activity Recognition

Short Term Activities (STA) 0.5::happensAt(walking(id1) = true, 1) 0.7::happensAt(walking(id2) = true, 1) 0.92::happensAt(walking(id3) = true, 2) ... 0.6::happensAt(active(id2) = true, 4) 0.7::happensAt(inactive(id3) = true, 4) 0.05::happensAt(walking(id1) = true, 9)

Probability of

Meeting Interval-based

Activity Recognition

P([ 1, 5 ]) = (0.3+0.3+0.7+0.7+0.5)/5

= 0.5 Cred([ 1, 5 ]) = P([ 1, 5 ]) lenght([ 1, 5 ])

= 0.5 * 5 =2.5 P([ 3, 6 ]) = (0.7+0.7+0.5+0.1)/4 =

0.5 Cred([ 3, 6 ]) = P([ 3, 6 ]) lenght([ 3, 6 ]) = 0.5 * 4 =2

LTA initiation rules

Prob-EC LTA termination rules Probability of

Moving P([ 0, 4 ]) = (0+0.5+0.7+0.9+0.4)/5 =

0.5 Cred([ 0, 4 ]) = P([ 0, 4 ]) lenght([ 0, 4 ])

= 0.5 * 5 = 2.5 P([ 1, 5 ]) = (0.5+0.7+0.9+0.4+0.1)/5

= 0.52 Cred([ 1, 5 ]) = P([ 1, 5 ]) lenght([ 1, 5 ])

= 0.52 * 5 = 2.6

P([ 7, 9 ]) = (0+0.5+1)/3 = 0.5 Cred([ 7, 9 ]) = P([ 7, 9 ]) lenght([ 7, 9 ])

= 0.5 * 3 =1.5 Time [ 1, 5 ] [ 3, 6 ]

A consequence of the de nition of a probabilistic maximal interval is that such intervals may be overlapping. Two examples are shown in Figure 1|see the overlapping red lines under the instantaneous probability evolution diagrams of meeting and moving. From a set of overlapping probabilistic maximal intervals, we keep only one, using interval `credibility', de ned as the product of interval length and probability:

Cred (ILTA) = length(ILTA) P (ILTA) = X P (holdsAt(LTA; k )); k (6) where k are the time-points of the interval ILTA. Hence, for each set of overlapping probabilistic maximal intervals S =fI1 ; I2 ; : : : ; Ik g, we select the one with the highest credibility, i.e. we select ILTA with Cred (ILTA) = max (Cred (Ii )) for i i = 1 ; : : : ; k . In Figure 1 the credible intervals are depicted by the solid red lines. Equation (6) ensures that we keep an interval which is as likely and long as possible. Nevertheless, this is just one of the many ways of picking between overlapping probabilistic maximal intervals.

1 0.8 A T L fo 0.6 y t i l i ab0.4 b o r P 0.2 0

Time Fig. 2: Probabilistic activity recognition. The black line represents the LTA probability evolution computed by Prob-EC. The green horizontal lines denote the maximal intervals that may be derived by Prob-EC using a 0:7 threshold, i.e. the set of all consecutive time-points with LTA probability above 0:7. The red line denotes the credible maximal interval computed by PIEC using the same threshold value, and the blue line expresses the ground truth.

Figure 2 illustrates, with the use of a benchmark activity recognition dataset1, the conditions in which the proposed approach is bene cial. This gure shows a 1 http://homepages.inf.ed.ac.uk/rbf/CAVIARDATA1/ case of probability uctuation|a steady increase in probability is followed by a noisy observation that reduces dramatically the LTA probability. Subsequently, the probability increases again. PIEC is able to compute a single maximal interval, mitigating the e ects of the noisy observation reducing temporarily the LTA probability. In contrast, Prob-EC is directly a ected by the noisy observation, creating a series of false negatives between its two maximal intervals. To approximate the interval of PIEC, we would have to lower signi cantly the threshold value for Prob-EC, creating numerous false positives in other cases. 4

Related Work

The input data of an activity recognition system exhibit various types of uncertainty [ 2 ]. One such type is that of incomplete or missing evidence [ 5 ]. Additionally, the input events typically have a noise component added to them. Consequently, events are often accompanied by a probability value. Several factors contribute to the corruption of the input events, such as the limited accuracy of sensors and distortion along a communication channel.

A recent survey [ 2 ] identi ed the following classes of methods for handling uncertainty in activity recognition: automata-based methods, probabilistic graphical models, probabilistic/stochastic Petri Nets and approaches based on stochastic (context-free) grammars. The closest line of work to our approach concerns the use of probabilistic graphical models, such as Markov Networks. When used for activity recognition, Markov Networks are combined with rst-order logic, in which case they are called Markov Logic Networks (MLN) [ 9 ]. The work of Skarlatidis et al. [ 13 ] is one of the rst attempts to provide a general probabilistic framework for activity recognition via MLN. In order to establish such a framework, Skarlatidis and colleagues employed the Event Calculus [ 8 ]. They aimed to tackle LTA de nition uncertainty, i.e. model imperfect rules expressing LTA. Instead, we built upon a probabilistic Event Calculus handling data uncertainty. Although probabilistic STA can be incorporated into graphical models, correctly encoding their dependencies can be far from obvious, especially with MLN [ 2 ].

There are also logic-based approaches to activity recognition that do not (directly) employ graphical models, such as [ 4, 10, 1, 11 ]. A key di erence between our work and these methods lies in the use of the Event Calculus, which allows us to develop an expressive activity recognition framework, specifying succinctly complex LTA by taking advantage of the built-in representation of inertia. A recently proposed probabilistic Event Calculus is presented in [ 6 ]. Our work is complementary to the Event Calculus of [ 6 ], as well as that of Skarlatidis et al. [ 13 ]. The computation of probabilistic maximal intervals may operate on top of any dialect for point-based probability calculation.

References

1. Massimiliano Albanese , Rama Chellappa, Naresh Cuntoor, Vincenzo Moscato, Antonio Picariello, V. S. Subrahmanian , and Octavian Udrea . PADS: A Probabilistic Activity Detection Framework for Video Data . IEEE Transactions on Pattern Analysis and Machine Intelligence , 32 ( 12 ): 2246 { 2261 , 2010 .

2. Elias Alevizos , Anastasios Skarlatidis, Alexander Artikis, and Georgios Paliouras . Probabilistic complex event recognition: A survey . ACM Comput. Surv. , 50 ( 5 ): 71 :1{ 71 : 31 , 2017 .

3. Alexander Artikis , Marek J. Sergot , and Georgios Paliouras . An event calculus for event recognition . IEEE Trans. Knowl . Data Eng., 27 ( 4 ): 895 { 908 , 2015 .

4. William Brendel , Alan Fern, and Sinisa Todorovic . Probabilistic event logic for interval-based event recognition . In The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011 , Colorado Springs , CO, USA, 20 - 25 June 2011, pages 3329 { 3336 , 2011 .

5. Nimrod Busany , Avigdor Gal, Arik Senderovich, and Matthias Weidlich . Intervalbased queries over multiple streams with missing timestamps . 2017 .

6. Fabio Aurelio D'Asaro , Antonis Bikakis, Luke Dickens, and Rob Miller . Foundations for a probabilistic event calculus . In Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6 , 2017 , Proceedings, pages 57 { 63 , 2017 .

7. A. Dries , A. Kimmig , W. Meert , J. Renkens , G. Van den Broeck, J. Vlasselaer, and L. De Raedt. Problog2: Probabilistic logic programming . In ECML , 2015 .

8. Robert A. Kowalski and Marek J. Sergot . A logic-based calculus of events. New Generation Comput ., 4 ( 1 ): 67 { 95 , 1986 .

9. M. Richardson and P. Domingos . Markov logic networks . Machine Learning , 62 ( 1 { 2): 107 { 136 , 2006 .

10. Joseph Selman , Mohamed R. Amer , Alan Fern , and Sinisa Todorovic . PEL-CNF: Probabilistic event logic conjunctive normal form for video interpretation . In ICCVW , pages 680 { 687 . IEEE, 2011 .

11. Vinay D. Shet , Jan Neumann, Visvanathan Ramesh, and Larry S. Davis . Bilatticebased Logical Reasoning for Human Detection . In (CVPR) , pages 1 {8 . IEEE Computer Society, 2007 .

12. Anastasios Skarlatidis , Alexander Artikis, Jason Filipou, and Georgios Paliouras . A probabilistic logic programming event calculus . TPLP , 15 ( 2 ): 213 { 245 , 2015 .

13. Anastasios Skarlatidis , Georgios Paliouras, Alexander Artikis, and George A. Vouros . Probabilistic event calculus for event recognition . ACM Trans. Comput. Logic , 16 ( 2 ), 2015 .