Marcos Zuniga
email: marcos.zuniga@usm.cl

Francois Bremond
email: francois.bremond@sophia.inria.fr

Monique Thonnat
email: monique.thonnat@sophia.inria.fr

Marcos D Zúñiga

Hierarchical and Incremental Event Learning Approach based on Concept Formation Models

Keywords: incremental event learning, hierarchical event model, human behaviour, reliability measures, symbolic attribute

We propose an event learning approach for video, based on concept formation models. This approach incrementally learns on-line a hierarchy of states and event by aggregating the attribute values of tracked objects in the scene. The model can aggregate both numerical and symbolic values.

The utilisation of symbolic attributes gives high flexibility to the approach. The approach also proposes the integration of attributes as a doublet value-reliability, for considering the effect in the event learning process of the uncertainty inherited from previous phases of the video analysis process.

Simultaneously, the approach recognises the states and events of the tracked objects, giving a multi-level description the object situation.

The approach has been evaluated for an elderly care application and a rat behaviour analysis application. The results show that the approach is capable of learning and recognising meaningful events occurring in the scene, and to build a rich model of the objects behaviour. The results also show that the approach can give a description of the activities of a person (e.g. approaching to a table, crouching), and to detect abnormal events based on the frequency of occurrence.

Introduction

Video event learning presents relevant applications related to abnormal behaviour detection, as elderly health care [START_REF] Zouba | Multi-sensors analysis for everyday elderly activity monitoring[END_REF], [START_REF] Nater | Visual abnormal event detection for prologed independent living[END_REF], and traffic monitoring [START_REF] Jiang | Abnormal event detection from surveillance video by dynamic hierarchical clustering[END_REF]. In this sense, the utilisation of incremental models for event learning should be the natural step further real-time applications for handling unexpected events. Apart from being well-suited for real-time applications because of the inexpensive learning process, this incremental characteristic learning allows the systems to easily adapt their response to different situations. Also, the dependence on enormous datasets for each particular application is reduced.

The focus of this work is in applications for incremental event learning, where several objects of diverse type can interact in the scene (e.g. persons, vehicles). The events of interest are also diverse (e.g. events related to trajectories, human posture) as the focus of interest is learning events in general. The objects simultaneously evolving in the scene can be many, but the interest is centred in objects which can be individually tracked in order to be able of recognising the events each object is participating.

We propose a new event learning approach, which aggregates on-line the attributes and reliability information of tracked objects (e.g. people) to learn a hierarchy of concepts corresponding to states and events. Reliability measures are used to focus the learning process on the most valuable information. Simultaneously, the approach recognises new occurrences of states and events previously learnt. The only hypothesis of the approach is the availability of tracked object attributes, which are the needed input for the approach. This approach is able to learn states and events in general, so no limitation is imposed on the nature or number of attributes to be utilised in the learning process.

As previously described, the hierarchical model of the proposed approach can be incrementally updated. This feature is based on incremental concept formation models [START_REF] Gennari | Models of incremental concept formation[END_REF]. These concept formation models evaluate the goodness of the concepts represented by the formed clusters in a hierarchical model, with the added constraint that learning must be incremental. The main contributions of the proposed learning approach, with respect to incremental concept formation models, are:

• The capability of the hierarchical model to learn events, as an explicit transition between two states (described in Sections 3.1 and 4.4).

• The utilisation of reliability measures for weighting the contribution of data according to their quality, as a way to focus learning on meaningful information (for details, see Section 4.3).

• The extended utilisation of the concept of acuity to represent different normalisation scales and units associated to different attributes, and also represent the interest of users for different applications (see Section 3.2, for details).

• The incorporation of the acuity to the numerical category utility, in order to balance the contribution of numerical and symbolic attributes to the category utility. (see Section 4.2).

In a step further to bridge the gap between image-level data and high-level semantic information, this work extends previous work presented in [START_REF] Zúñiga | Incremental video event learning[END_REF] and [START_REF] Zúñiga | Uncertainty control for reliable video understanding on complex environments[END_REF] by integrating symbolic attribute information to the hierarchical model in a way that both numerical and symbolic attribute values can be in a common state model. The utilisation of symbolic attributes gives high flexibility to the approach, allowing the user to add significantly semantic attributes for assisting on scene interpretation.

Also, the approach can simultaneously learn different hierarchies representing different learning contexts (i.e. different states and events of interest). We propose a general representation for the context of each learning process and extend the analysis of each involved process for an easier implementation. The source code of the algorithm is publicly available 1 .

The approach has been extensively verified over both simulated and real data-sets. The real data-sets has been utilised for specific events for home-care (e.g. approaching to a table, crouching) and rat behaviour learning (position and velocity events).

This paper is organised as follows. In Section 2 the state-ofthe-art on incremental event learning approaches is presented. Section 3 describes the proposed event learning approach in general, and Section 4 focuses on describing the learning process in detail. Finally, Section 5 presents the experiments performed on simulated and real data-sets.

State-of-the-Art

Most of video event learning approaches for abnormal behaviour recognition are supervised, requesting annotated videos representative of the events to be learnt in a training phase [START_REF] Howarth | Conceptual descriptions from monitoring and watching image sequences[END_REF], [START_REF] Hongeng | Video-based event recognition: activity representation and probabilistic recognition methods[END_REF], [START_REF] Chan | Joint recognition of complex events and track matching[END_REF]. As well described in [START_REF] Weinland | A survey of vision-based methods for action representation, segmentation and recognition[END_REF], these approaches normally use general techniques as Hidden Markov Models (HMM) [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. Some authors use hierarchical models, as they facilitate learning and generalisation. HMMs are robust, but require hierarchical (HHMM) and time-duration modelling for representing events with varying temporal and spatial scales, increasing the complexity of these approaches.

Generalisation is one of the keys to simplify the process of semantic interpretation. In [START_REF] Nater | Exploiting simple hierarchies for unsupervised human behavior analysis[END_REF], the authors propose an approach for abnormal behaviour detection, using unsupervised learning for two hierarchical representations, one for description of the observation and the other for temporal description. In [START_REF] Thome | A hhmm-based approach for robust fall detection[END_REF], the authors proposed a fall detection algorithm that uses HHMM, hand designed and operating on an observation sequence of rectified angles.

Few approaches can learn events in an unsupervised way using clustering techniques. For instance, [START_REF] Xiang | Video behavior profiling for anomaly detection[END_REF] use the clusters of attributes obtained with a Gaussian Mixture Model to represent the states of an HMM, [START_REF] Sridhar | Learning functional object-categories from a relational spatio-temporal representation[END_REF] learn events using spatial relationships between objects in an unsupervised way, but performed off-line, and [START_REF] Toshev | Unsupervised learning of scenario models in the context of video surveillance[END_REF] apply unsupervised learning of composite events using the APRIORI clustering algorithm. However, these unsupervised clustering techniques request to (re)process off-line (not real-time) the whole cluster distribution.

Some other techniques can learn on-line the event model by taking advantage of specific event distributions. For example, [START_REF] Piciarelli | Trajectory clustering and its applications for video surveillance[END_REF] propose a method for incremental trajectory clustering by mapping the trajectories into the ground plane decomposed in a zone partition. Their approach performs learning only on spatial information, it cannot take into account time information, and do not handle noisy data.

In conclusion, few work has been found on hierarchical and incremental approaches for abnormal behaviour detection. A critical aspect not considered in the current approaches is the uncertainty of mobile object attributes present in real applications and how this uncertainty can affect the model construction.

Following these directions, the current work is based on incremental concept formation models [START_REF] Gennari | Models of incremental concept formation[END_REF]. The knowledge is represented by a hierarchy of concepts partially ordered by generality. A category utility function is used to evaluate the quality of the obtained concept hierarchies [START_REF] Mckusick | Cobweb/3: A portable implementation[END_REF].

The proposed approach takes profit of this hierarchical structure, extending it to represent events, incorporate the effect of uncertainty in data, and to manage symbolic attributes which facilitate semantic interpretation.

Incremental state and event learning approach

As previously stated, the proposed approach is an extension of incremental concept formation models [START_REF] Gennari | Models of incremental concept formation[END_REF][START_REF] Carbonell | Paradigms and Methods[END_REF] for learning video events. The approach uses as input a set of attributes from the tracked objects in the scene. Hence, the only hypothesis of the approach is the availability of tracked object attributes (e.g. position, posture, class, speed).

The proposed approach has been called MILES, acronym standing for Method for Incremental Learning of Events and States. The approach has received its name since its first version, presented in [START_REF] Zúñiga | Incremental video event learning[END_REF]. MILES state hierarchy construction is mostly based on COBWEB [START_REF] Fisher | Knowledge acquisition via incremental conceptual clustering[END_REF] algorithm, but also considering ideas from other existing incremental concept formation approaches, as CLASSIT [START_REF] Gennari | Models of incremental concept formation[END_REF] algorithm.

The hierarchy of states and events

MILES builds a hierarchy of state and event concepts H, based on the state and event instances extracted on-line from the tracked object attributes. It is desirable (but not necessary) that the input data contains an estimate of the reliability on information. This hierarchy is formed by two building blocks:

State concept: It is the modelling of a state, as previously defined. A state concept S (c) , in a hierarchy H, is modelled as:

• its number of occurrences N(S (c) ) and its probability of occurrence P(S (c) ) = N(S (c) )/N(S (p) ). (S (p) is the root state concept of H),

• the number of event occurrences N E (S (c) ), corresponding to the number of times that the state S (c) passed to another state, generating an event.

• a set of numerical attribute models {n i }, with i ∈ {1, .., T }, where n i is modelled as a random variable N i which follows a Gaussian distribution

N i ∼ N(µ n i ; σ n i ),
• a set of symbolic attribute models {s j }, with j ∈ {1, .., S }, where s j is represented by every possible value for the attribute, and conditional probabilities P(V (k) s j |S (c) ) representing the frequency of occurrence of a the k-th value V (k) s j for s j , given S (c) .

Event concept: It is the modelling of the transition between two state concepts. An event concept E (c) is defined as the change from a starting state concept S (c) a to the arriving state concept S (c) b in a hierarchy H. An event concept E (c) , in a hierarchy H, is modelled as:

• its number of occurrences N(E (c) ) and its probability of occurrence P(E (c) ) = N(E (c) )/N E (S (c) a ) (with S (c) a its starting state concept).

The state concepts are hierarchically organised by generality, with the children of each state representing specifications of their parent. In the hierarchy, an event concept is represented as a unidirectional link between two state concepts. An example of a hierarchy of states and events is presented in Figure 1. In the example, the state S 1 is a more general state concept than states S 1.1 and S 1.2 , and so on. Each pair of state concepts (S 1.1 ; S 1.2 ) and (S 3.2 ; S 3.3 ), is linked by two events concepts, representing the occurrence of events in both directions.

The Learning Contexts

The learning process associated to a particular hierarchy H is guided by a learning context Z. A learning context corresponds to the description of a particular scope of the events of interest for the user. Multiple learning contexts can be defined and simultaneously processed, according to user interests. Each learning context requires the definition of:

• the moving object classes involved in the particular learning process, defining a list of the object classes of interest or stating that any class is of interest.

• the attributes of interest (numerical or symbolic). Normally, there is an intermediate step for obtaining these attributes from involved objects, as these attributes can be derived from other object attributes (e.g. symbolic attribute defining a zone in the scene, derived from object position).

• Particularly, for each numerical attribute of interest n i , a normalisation value A n i must be also defined. A n i represents the lower bound for the numerical attribute change to be considered as meaningful. In other words, the difference between the mean value for a numerical attribute n and the value of the attribute for a new instance will be considered as significant and noticeable when this difference is higher than A n i .

This normalisation value corresponds to the concept of acuity, utilised by [START_REF] Gennari | Models of incremental concept formation[END_REF] and described as a system parameter that specifies the minimum value for attributes σ in the CLASSIT algorithm for incremental concept formation. In psycho-physics, the acuity corresponds to the notion of a just noticeable difference, the lower limit on the human perception ability.

This concept is used for the same purpose in MILES, but the main difference with its utilisation in CLASSIT is that the acuity was used as a single parameter, while A n i acuity values are defined for each numerical attribute to be learnt for a given context. This improvement allows to represent the different normalisation scales and units associated to different attributes, and can also represent the interest of users for different applications. For instance, a trajectory position attribute x could have an acuity of 50 centimetres for an application with a camera in an office environment, while for the same attribute, the acuity could be two metres for a parking lot application with a camera far from the objects, where the user is not interested in little details on position change.

• In particular, for each symbolic attribute s j , it is necessary to list the associated values of interest.

As an example, for a Position-Posture learning context, as shown in Figure 2, the user can be interested in learning the events associated to a Person position (x, y), together with the human posture in an office environment. As an office is a small closed area, appropriate normalisation values for position attributes can be 50 centimetres. Then, this context mixes numerical position attribute information, with symbolic posture attribute information. It is worthy to notice that the purpose of learning contexts is to increase the possibilities of the users to customise the learning process according to the information of interest to an application. In other words, nothing limits a user to define a learning context with all the available attributes. All these possibilities of customisation by the user, give a high flexibility to the proposed approach for adapting to a wide variety of applications and typical issues present in the video understanding domain. Also, symbolic attributes allow the user to define attributes which help in the semantic interpretation, bridging the gap between image-level data and high-level information.

Contextualised Objects and State Instances

According to the learning context, pertinent attributes of a tracked object have to be extracted (or generated). In the context of MILES, each mobile object must also store information related to their position in the hierarchy tree, for each learning context in which it participates. Then, a contextualised object o will be an extended representation of a tracked object. This object o, for each learning context Z it participates, must then contain:

• a state instance, which is an instantiation of a state concept, associated to the object o. The state instance S (o) is represented as the set attribute-value-measure triplets

T o = {(v i ; V i ; R i )}, with i ∈ {1, . . . , T ′ + S ′ }
, where R i is the reliability measure associated to the obtained value V i for the attribute v i . T ′ and S ′ are the number of pertinent numerical and symbolic attributes, respectively, according to learning context Z. The measure R i ∈ [0, 1] is 1 if associated data is totally reliable, and 0 if totally unreliable, allowing to control the learning process according to quality of information. Attribute v i can be numerical or symbolic.

• For each level in the hierarchy H, associated to Z:

-Last detected event concept E (c) for object o.

-Previously detected state concept S (c) a . Corresponds to a matching between state concept S (c) a and a state instance S (o) previously extracted from object o.

-Currently detected state concept S (c) b . Corresponds to a matching between state concept S (c) b and the state instance S (o) currently extracted from object o.

Now, with all these elements and their interactions properly described, details on the event learning process can be presented in next Section 4.

MILES Learning Process

MILES needs that the objects are tracked in order to detect the occurrence of events. There is no constraint on the number and nature of attributes, as MILES has been conceived for learning state and event concepts in general, as discussed in section 3.2.

Initially, before the first execution of MILES, and for each defined learning context Z, a hierarchy H is initialised as an empty tree. If MILES has been previously executed, the incremental nature of MILES learning process allows that the hierarchy H resulting from this previous execution can be utilised as the initial hierarchy of a new one.

The input of MILES corresponds to a list of contextualised mobile objects O, according to the defined learning contexts. At each video frame, MILES utilises O for updating each hierarchy H. Considering a particular learning context Z and its corresponding hierarchy H, MILES first gets the set of triplets T o , equivalent to a state instance(see section 3.3), for each object o in O, pertinent to Z. These triplets will be the input for the state concept updating process of H. This updating process is described in Section 4.1. The updating process returns a list L o of the current state concepts recognised for the object o at each level of H.

Then, the event concepts E (c) of the hierarchy H are updated comparing the new state concept list L o with the list of state concepts recognised for the object o at the previous frame.

Finally, MILES gives as output for each video frame, the updated hierarchy H and the list of the currently recognised state and event concepts for each learning context for which an object o in O is pertinent.

States Updating Algorithm

State concept updating is a recursive process, as depicted in Figure 3.

The algorithm starts by accessing the analysed state C from hierarchy H (with rootOf returning the root state of H). Notice that, in the context of the algorithm, a hierarchy not necessarily corresponds to the complete tree, as the algorithm recursively utilises sub-branches of the hierarchy. The initialisation of H is performed by creating a state with the triplets T, for the first processed object. Remember that T represents the state instance for object o, given a learning context Z.

Then, for the case that C corresponds to a terminal state (state with no children), a cutoff test is performed. The cutoff is a criteria utilised for stopping the creation (i.e. specialisation) of children states. It is defined in

cutoff =          true if {µ (C) n i -V n i ≤ A n i |∀i ∈ {1, .., T ′ }} ∧ {P(V s j |s j (C) ) = 1|∀ j ∈ {1, .., S ′ }} false else , (1)
where V n i is the value of a numerical attribute n i , and V s j is the value of the symbolic attribute s j . µ (C) n i is the mean value of n i for C. P(V s j |s j (C) ) is the conditional probability of the value V s j , given s j of C. T ′ and S ′ are the number of pertinent numerical and symbolic attributes for Z, respectively.

This equation means that the learning process will stop at C if no meaningful difference exists between a numerical attribute value at T and the mean value of the attribute for C (using acuity A n i criteria), or if every symbolic attribute value in T is totally represented in C (probability equal to one for the attribute value). This means that the learning process will stop if no noticeable difference between the attribute values is found.

If the cutoff test is passed (noticeable difference found), the function insertTerminal generates two children for C, one initialised with T and the other as a copy of C. Then, T is incorporated to C (process described in Section 4.3). In this terminal state case, the updating process then stops.

If C has children, first T is immediately incorporated to C. In order to determine in which state concept the triplets list T is next incorporated (i.e. the state concept is recognised), a quality measure for state concepts called category utility (CU) is utilised, which is discussed in detail on Section 4.2. Then, the different alternatives for the incorporation of T are: At the end of function updateStates, each current state C for the different levels of the hierarchy is stored in the list L of current state concepts for object o, by the function insertCur-rentState.

The Category Utility

As previously discussed, the category utility measures how well the state instances are represented by a given state concept. This function has been derived by Gluck and Corter [START_REF] Gluck | Information, uncertainty, and the utility of categories[END_REF]. Category utility attempts to maximise intra-class similarity and inter-class differences, and it also provides a principled tradeoff between predictiveness and predictability [START_REF] Fisher | Knowledge acquisition via incremental conceptual clustering[END_REF]. A measure similar to the category utility function from COBWEB/3 [START_REF] Mckusick | Cobweb/3: A portable implementation[END_REF] algorithm has been considered. For the set of numerical attributes, the numerical category utility CU k (num), for a given state concept S k , is defined as:

CU k (num) = P(S k ) T ′ i=1        A n i σ (k) n i - A n i σ (p) n i        2• T ′ • √ π , (2)
where σ (k) n i is the standard deviation for the numerical attribute n i in S k , and σ (p) n i is the standard deviation for n i in the parent or root node S p . The value A n i corresponds to the acuity for n i .

The incorporation of the acuity term A n i to the equation 2 establishes a difference with the preceding versions of numerical category utility in the state-of-the-art. This is done to balance the contribution of numerical and symbolic attributes to the category utility. The obtained attribute contribution value always belongs to the interval [0, 1], as A n i is the lower bound for σ (k) n i .

Also, the acuity is useful to normalise the contributions of numerical attributes representing different metric units (e.g. position and velocity) and scales (e.g. a position in metres and a distance in centimetres).

For the set of symbolic attributes, the symbolic category utility CU k (sym), for S k , is defined as:

CU k (sym) = P(S k ) S ′ i=1 J i j=1 P(s i = V ( j) s i |S k ) 2 -P(s i = V ( j) s i |S p ) 2 S ′ , (3)
where P(s i = V ( j) s i |S k ) is the conditional probability that the symbolic attribute s i has a value V ( j) s i in S k , while P(s i = V ( j) s i |S p ) is the conditional probability that s i has a value V ( j) s i , in the parent or root node S p .

Then, for a set of mixed symbolic and numerical attributes, the overall category utility CU k , given a state concept S k , is the sum of the contributions of both sets of features:

CU k = CU k (sym) + CU k (num). (4)
Finally, the category utility CU for a class partition of K state concepts is defined as:

CU = K k=1 CU k K (5)

Incorporation of New Object Attribute Values

Upon the arrival of a new state instance, the attribute information of the instance must be used to update the state and event concept information. According to the type of attribute the information updating process differs.

For the case of a numerical attribute n, the information about the mean value µ n and the standard deviation σ n must be updated. The proposed updating functions are incremental in order to improve the processing time performance of the approach. For µ n , the function is presented in Equation [START_REF] Hongeng | Video-based event recognition: activity representation and probabilistic recognition methods[END_REF].

µ n (i) = V n • R n + µ n (i -1)• S um n (i -1) S um n (i) , (6)
with

S um n (i) = R n + S um n (i -1), (7)
where V n is the value in the new instance for n and R n corresponds to its reliability. Hence, the reliability R n weights the contribution of V n to µ n . S um n is the accumulation of reliability values R n for n.

The updating function for σ n is presented in Equation [START_REF] Jiang | Abnormal event detection from surveillance video by dynamic hierarchical clustering[END_REF].

σ n (i) = S um n (i -1) S um n (i) • σ n (i -1) 2 + R n • (V n -µ n (i -1)) 2 S um n (i) . (8)
In the case that a new state concept is generated from the attribute information of the instance, the initial values taken for Equations ( 6), [START_REF] Howarth | Conceptual descriptions from monitoring and watching image sequences[END_REF], and ( 8) with i = 0 correspond to µ n (0) = V n , S um n (0) = R n , and σ n (0) = A n , where A n is the acuity for the attribute n, as defined in Section 3.2.

In case that, after updating σ n (i), its value is lower than the acuity A n , σ n (i) becomes equal to A n . This way, the acuity value establishes a lower bound for the standard deviation, avoiding the possibility of zero division.

For a symbolic attribute s it is necessary to update the conditional probability P(s = V ( j) s |S ) of each possible value V ( j) s of s, given S . For this purpose, reliability measures R s are utilised in order to weight the quality of new incoming information, as presented in Equations ( 9), [START_REF] Nater | Exploiting simple hierarchies for unsupervised human behavior analysis[END_REF], and [START_REF] Nater | Visual abnormal event detection for prologed independent living[END_REF].

P(s = V ( j) s |S )[i] =                        S um ( j) V s (i) S um s (i) i f V s = V ( j) s S um ( j) V s (i -1) S um s (i) else (9)
with

S um ( j) V s (i) = R s + S um ( j) V s (i -1), (10)
and

S um s (i) = R s + S um s (i -1), (11)
where V s is the value in the new instance for s, and R s corresponds to its reliability. V ( j) s is the j-th possible value s. The functions S um ( j) V s (i) correspond to the accumulated reliability for each s value V s , while the function S um s (i) is the overall accumulated reliability for s.

Events Updating Algorithm

After the states updating phase (see Section 4.1). the changes of state concept occurred for an object o must update the events information according to the change of state. The occurrence of a state transition updates all the events representing the combinations between the analysed state concept from the stored list, where the possible combinations are:

• All the states of a lower level in the new list, if the state at its same level in the new list is different than the analysed state.

• The state at its same level in the new list if it is different than the analysed state.

• All the states at a higher level in the new list which do not have a kinship relation (defined below) with the analysed state.

A kinship relation between two states S m and S n in the hierarchy exists if S m is (directly or indirectly) the ascendant or one of the descendants of the state S n in the hierarchy. This means that the one state is related to the other as parent, or son, or grand-parent, or grand-son, and so on.

Examples of these state combinations can be found in Figure 5.

If an event E corresponds to a first detected event, a new event representation is created and associated to the generating state S a and the arriving state S b .

Then, the updated list of current states at different levels in the hierarchy is utilised to update the current states information of the object o.

Merge Operator

The merge operator consists in merging two state concepts S p and S q into one state S M , while S p and S q become the children of S M , and the parent of S p and S q becomes the parent S M , as depicted in Figure 6. Red dashed lines represent events, while the green dashed lines are the new events appearing from the merging process.

In order to generate the state S M several considerations must be made:

• N(S M ) = N(S p ) + N(S q ).

• P(S M ) = N(S M )/N(S r ), with S r the root node of the hierarchy.

• N E (S M ) corresponds to the number of events E having a starting state S a (E) = S p or S q , and as an ending state S b (E) a state not having a kinship relation with S M .

• Each numerical attribute n M for S M can be updated using the Equations [START_REF] Piciarelli | Trajectory clustering and its applications for video surveillance[END_REF], and (13) for mean and standard deviation of n M , respectively.

µ n M = S um n p • µ n p + S um n q • µ n q S um n p + S um n q , ( 12
)
σ 2 n M = S um n p • (∆ 2 M p + σ 2 n p ) + S um n q • (∆ 2 Mq + σ 2 n q ) S um n p + S um n q , (13)
where S um n p and S um n q correspond to the accumulated reliability values for numerical attributes n p and n q , respectively. ∆ M p = (µ n Mµ n p ) and ∆ Mq = (µ n Mµ n q ) were added to adjust the value of σ n M , considering the drift between the new mean µ n M , and the mean values µ n p and µ n q .

• Each symbolic attribute s M for S M can be updated using the Equation ( 14), for the conditional probability P(s M ) ( j) , for the j-th value of the symbolic attribute s M .

P(s M = V ( j) s M |S M )[i] = S um ( j) V sp + S um ( j) V sq S um s p + S um s q , ( 14
)
where S um ( j) V sp and S um ( j) V sq correspond to the accumulated reliability values of the j-th value for symbolic attribute s p and s q , respectively. In the same way, S um s p and S um s q are the overall reliability values accumulation for s p and s q , respectively.

The last task for the merging operator is to represent the events incoming and leaving states S p and S q (green dashed lines in Figure 6) by generating new events which generalise the transitions as the events incoming and leaving the state S M . For the incoming events to these states the event merge process is described as follows:

• If a state S n is the starting state for an event E n→x arriving to only one state S x of the merging states S p and S q (as event E S 2 →S 3 between states S 2 and S 3 in Figure 6), a new event E n→M must be generated with the same information as event E n→x , except for the arriving state that becomes the state S M .

• If a state S n is the starting state for the events E n→p and E n→q arriving to both states S p and S q (as events E S 4 →S 1 and E S 4 →S 3 in Figure 6), a new event E n→M must be generated with:

-N(E n→M ) = N(E n→p ) + N(E n→q ) -P(E n→M ) = N(E n→M )/N E (S n ).
Finally, events leaving the states S p and S q must be merged, with:

• N(E M→n ) = N(E p→n ) + N(E q→n ) • P(E M→n ) = N(E M→n )/N E (S M )

Experiments and Results

Illustration of MILES State and Event Representation

In order to better understand the learning process, an illustration example is presented in this section. The example consists in ten persons evolving in a metro scene, starting at different positions and time instants. A top view of the scene is depicted in Figure 7. The evolution of the persons in the scene is represented by ten hand-crafted trajectories (T0 -T9) of eight coordinate points (x,y) in the ground plane of the scene. The scene consists of three Access/Exit zones (referenced in the Figure 7 as A, C andD), and a ticket vending machine zone B, represented as a red box in Figure 7. The ten persons evolve in the scene over 13 time instants.

The idea is to utilise a simple learning context consisting in the (x,y) person positions, with an acuity of 200 [cm] . Then, the evolution of the hierarchy of states and events in time can be analysed to understand the event learning process. Also, the relations between the obtained states and events and the trajectories of the persons can be studied to understand how the hierarchy represents the situations occurring in this scene.

Learning up to Time instant 1:

At this instant two persons (represented by T0 and T1) arrive from the zone D and two other persons (represented by T2 and T3) arrive from the zone A. This situation is represented by two different states of the hierarchy, because the person positions entering at the two different zones were similar enough to be represented in the same state concept. The positions of T0 and T1 are then represented by the State 1, while the positions of T2 and T3 by the State 2.

Figure 8(a) shows a top view of the scene where these the two new states are represented. Figure 8(b) depicts the maximal marginal probability for each point in the scene, given the current two states of the hierarchy.

Learning up to Time instant 3:

The evolution of the hierarchy until this instant is depicted in Figure 9. T4 starts walking in the direction of the zone D, while T5 goes in the direction of the zone C. The position of T4 and T5 is not different enough yet to generate a new state. induces a new event between States 9 and 12 (in that order), as depicted in Figure 12(a). Figure 12(b) shows that even the probability map has arrived to a quite stable state, where only slight differences can be observed. From this time instant and until the end of the illustration example, the hierarchy is very stable, only showing some new events and updates in the states probability. The final result for the hierarchy of this illustration example is depicted in Figure 14. This figure shows that the hierarchy has arrived to a stable state since time instant 7. In Figure 13 only slight differences can be observed, with some few new events and slight modifications in the probability map.

Learning up to Final time instant 13:

This illustration has served to show the incremental nature of the proposed event learning approach. The hierarchy of states and events has shown a consistent behaviour on representing the frequency of states and events induced by the persons of the illustration example.

Exploiting the Hierarchy and the Effect of Acuity

The hierarchy learnt by MILES concentrates rich information, which can vary according to the attributes selected for the learning process. Figure 15 shows three different types of information extracted from the hierarchy, for an application to study the behaviour of a rat, consisting in 4850 frames. The utilised learning context considers three numerical attributes: 2D position attributes X and Y, and also 2D velocity magnitude attribute V2D. A video showing the evolution of the incremental learning process is available2 shows the maximal probability for each point, using likely states from the hierarchy (red to blue, for highest to lowest probability). Image (c) shows the same likely states from the hierarchy, only showing their peak probability, and also the events connecting these states. The events are represented with a triangle opening from the starting state to the arriving state (yellow to green, for highest to lowest probability). Recognised states are presented with a white ring. Finally, image (d) shows the behaviour of the V2D attribute according to the position (yellow to green, for highest to lowest velocity magnitude). Note that it can be easily inferred that the rat stops at corners and accelerates the most through the widest part of the experimental zone.

We have chosen position and velocity attributes because they can be more easily represented in the input video, but nothing limits the number or nature of the attributes to be learnt. The input information is obtained from a multi-hypothesis tracking approach which is able to compute reliability measures for object attributes, and is described in detail in [START_REF] Zuniga | Real-time reliability measure driven multi-hypothesis tracking using 2d and 3d features[END_REF]. It is important to notice that the presence of one or many objects in the video sequence is not relevant for MILES learning process to properly work, as the attributes are learnt each frame from any mobile object which matches with any of the classes defined in the learning context.

There must be certainly many ways of extracting information from the hierarchy. In this particular case, the states are selected searching for the deepest state with a probability higher than a threshold, to obtain relevant states according to the application. There are also many ways to consider the state probability to select the states. For example, we can just consider the probability of the state only, or the conditional probability considering attributes of interest, or even considering these attributes probability weighted by their reliability. In the presented case, we use a conditional probability considering the probabilities of X and Y attributes, so that likely states with low intra-class similarity are not considered.

The extracted information can then serve, for instance: to determine the more likely (or unlikely) zones according to their probability (figure 15, upper right), which is useful for abnormal behaviour detection and traffic frequency analysis, among many other applications; to determine the likely (or unlikely) behaviours through chains of events (figure 15, lower left), certainly useful for behaviour analysis; and understanding the relations between attributes as, for example, estimating which are the zones where the rat is static or moves quicker (figure 15, lower right).

Other element that has a notorious effect on the results is the acuity of each numerical attribute. As previously discussed, the acuity allows the users to define their interest on an attribute. Then, there is no ideal value for this parameter, as it depends on the application. Figure 16 depicts the effect of different val- ues of acuity on the probability map. A video showing the incremental evolution of the probability map, for different acuity values, is also available 3The figure shows how the state probabilities are affected with lower probability peaks and more plain probability distributions when acuity increases. This is the expected behaviour as, when an user defines a higher acuity, is implicitly saying that higher differences are not significant to the application so that the related instances can be clustered in the same state.

If acuity is increased, also the number of instances similar to a state. Then, the number of states and events is decreased, as shown in Figure 17.

Symbolic Attributes and Recognition Capabilities

The capability of MILES for automatically learning and recognising real world situations has been evaluated, using two videos for elderly care at home. The video scene corresponds to an apartment with a table, a sofa, and a kitchen, as shown in Figure 18. The videos correspond to an elderly man (Figure 18 The input information is obtained from the same tracking method, previously described, and presented in [START_REF] Zúñiga | Uncertainty control for reliable video understanding on complex environments[END_REF]. A learning context for the class Person, combining both numerical and symbolic attributes, was tested considering the following attributes: 3D position (x, y); symbolic Posture, with values for Standing or Crouching posture; and interaction symbolic attributes S ymD table , S ymD so f a , and S ymD kitchen between the person and three objects present in the scene (table, sofa, and kitchen table). The possible symbolic values are: FAR : distance ≥ 100[cm], NEAR : 50[cm] < distance < 100[cm], and V ERY NEAR : distance ≤ 50[cm]. The contextual objects in the video scene (sofa, table, and kitchen) have been modelled with 3D polygons. All the attributes are automatically computed by a tracking method, which is able to calculate the reliability measures of the attributes [START_REF] Zúñiga | Uncertainty control for reliable video understanding on complex environments[END_REF].

The learning process applied over the 68000 frames have resulted in a hierarchy of 670 state concepts and 28884 event concepts. From the 670 states, 338 state concepts correspond to terminal states (50.4%). From the 28884 events, 1554 event concepts correspond to events occurring between terminal states (5.4%). This evaluation consists in comparing the recognised events with the ground-truth of a sequence, utilising the proposed symbolic-numeric learning context. Different 750 frames from the elderly woman video are used for comparison, corresponding to a duration of 1.33 minutes. The recognition process has obtained as result the events summarised in Figure 19.

The evaluation has obtained 5 true positives (TP) and 2 false positives (FP) on event recognition. This results in a precision ( TP/(TP+FP) ) of 71%. MILES has been able to recognise all the events from the ground-truth, but also has recognised two nonexistent events, and has made a mean error on the starting state duration of 4 seconds. These errors are mostly due to bad segmentation near the kitchen zone, which had strong illumina- tion changes, and to the similarity between the colours of the elderly woman legs and the floor. The results are encouraging considering the fact that the description of the sequence generated by a human has found a very close representation in the hierarchy.

Recognised Situations and Symbolic Attributes

It is also very interesting to check how real situations find their representations in the obtained hierarchies. Here two examples with the previously defined learning context:

• Going from the kitchen to the table: This situation consists in the analysed person going from the zone near the kitchen, to the table zone, as depicted with the images shown in Figure 20.

In the obtained hierarchy the situation is described by the states and events depicted in Figure 21.

Notice that three states representing each of the displayed images in Figure 20. The probability of occurrence of the first state 25 is 9888/40000 = 0.25, as the elderly man spends a long time in the kitchen zone. Notice that this state is well describing the fact that the man is all the time very near of the kitchen, also showing that at this state the man is not standing all the time, but also crouching approximately a quarter of the total of time spent at this state.

For the same reason that the elderly man spends a long time in the kitchen zone, the events generated for this state are concentrated between states occurring in the kitchen and the conditional probability of the first event is very low (0.02). The second state represents an intermediate passage zone near the kitchen and the table, where the person passes most of the time standing. The third state represents the position very near the table. Here, the person has a crouching posture approximately a third of the total time spent in this state.

• Crouching and then standing at the table: This situation consists in the analysed person passing to a crouching posture and then returning to the standing posture, at the zone near the table, as depicted with the images shown in Figure 22.

In the hierarchy obtained from the previously defined learning context, the situation is described by the states and events depicted in Figure 23. Notice that three states representing each of the displayed images in Figure 22.

The probability of occurrence of the first state 131 is not very high 0.04, as the elderly man does not spend a long time in the table zone, compared with the time spent in the kitchen zone. This state is describing that the man is all the time very near of the table at a standing posture. The first event has a high conditional probability (0.4). The second state represents a person still very near of the table but now in a crouching posture.

Notice also that the utilisation of posture and proximityto-object symbolic attributes help the user to bridge the semantic gap of the representation, when needed. Nevertheless, the high number of event transitions between these states, compared with the observed video, highlights a problem inherent to the discretisation process to obtain symbolic attributes: the error is amplified. Here the situation can be that the person, because of errors in the estimation of the dimensions (due to a bad segmentation), gave as result the wrong posture, forcing wrong transitions between both states.

Discussion of the Results

As shown in this evaluation, rich information can be obtained with MILES. The results show that the system is able to learn and recognise meaningful events occurring in the scene and that the hierarchical representation can be very rich in information. Also, the utilisation of symbolic attributes allows an easier semantic interpretation of the states.

The computer time performance of MILES is 1300[ f rames/second] for a video with one tracked object and six attributes, and without considering prior stages in the process (e.g. segmentation and tracking), showing the real-time capability of the learning approach.

Conclusion

MILES has shown interesting capabilities for state and event recognition. Results have shown that its incremental nature is useful for real-time applications, as it considers the incorporation of new arriving information with a minimal processing time cost. Incremental learning of events can be useful for abnormal event recognition and for serving as input for higher level event analysis.

The approach allows to learn a model of the states and events occurring in the scene, when no a priori model is available, also giving to users a high flexibility and control through the utilisation of symbolic attributes, the definition of acuity values and the consideration of reliability measures for controlling the uncertainty of information. It has been conceived for learning state and event concepts in a general way, allowing the definition of simultaneously processed learning contexts. Depending on the availability of tracked object features, the possible combinations are large. MILES has shown its capability for recognising events, processing noisy image-level data, with a minimal configuration effort.

However, more evaluation is still needed for other type of scenes, for other attribute sets, and for different type of tracked objects. The anomaly detection capability of the approach on a large application must also be evaluated. Future work will be also focused in the incorporation of attributes related to interactions between tracked objects (e.g. meeting someone), automatic verification of stability on state instances before learning, and a general state permanence time model.

Figure 2 :

 2 Figure 2: Definition of a Position-Posture learning context for Person class in an office environment.

e 3 . 2 - 3 .1 e 3 . 2 - 3 . 3 e 3 . 3 - 3 . 2 Figure 1 :

 323323333321 Figure1: Example of a hierarchical event structure resulting from the proposed event learning approach. Rectangles represent states, while circles represent events.

Figure 3 :

 3 Figure 3: Scheme of the state concept updating algorithm.

Figure 5 :

 5 Figure 5: Examples of list comparisons for determining the events to update. Blue elements represent the previously stored states for a tracked object. Green elements represent the updated states obtained with the function updateStates. The red box represents the state concept which is common to both lists. The dashed red lines represent the events to update for two different cases (a) and (b).

2 MergeFigure 6 :

 26 Figure6: Merging states and events in MILES algorithm. Blue boxes represent the states to be merged, and the green box represents the resulting merged state. Red dashed lines represent events, while the green dashed lines are the new events appearing from the merging process.

Figure 7 :

 7 Figure 7: Top view of the metro scene illustration example. The ten handcrafted trajectories (T0-T9) are displayed.

Figure 8 :P 5 TFigure 9 :

 859 Figure 8: Hierarchy at instant 1. (a) Terminal states position in a top view of the scene. The oval surrounding the mean position of a state represents the standard deviation of this position. A state in the first level of the hierarchy is represented in blue. (b) Maximal marginal probability of a state. A darker colour represents a higher probability.

Figure 13 :Figure 10 :Figure 11 :Figure 12 :

 13101112 Figure 13: Final hierarchy associated to the position learning context, at instant 13. Figure (a) shows the position of the terminal states and the events. Figure (b) depicts the maximal marginal probability of a state of the hierarchy.

  State recognition and events. (d) V2D attribute profile.

Figure 15 :

 15 Figure 15: Different information extracted from MILES hierarchy. Image (a) image represents the input from tracking. Image (b)shows the maximal probability for each point, using likely states from the hierarchy (red to blue, for highest to lowest probability). Image (c) shows the same likely states from the hierarchy, only showing their peak probability, and also the events connecting these states. The events are represented with a triangle opening from the starting state to the arriving state (yellow to green, for highest to lowest probability). Recognised states are presented with a white ring. Finally, image (d) shows the behaviour of the V2D attribute according to the position (yellow to green, for highest to lowest velocity magnitude). Note that it can be easily inferred that the rat stops at corners and accelerates the most through the widest part of the experimental zone.

  (a) Acuity: 5.0 × 5.0. (b) Acuity: 10.0 × 10.0. (c) Acuity: 15.0 × 15.0. (d) Acuity: 20.0 × 20.0.

Figure 16 :

 16 Figure 16: Figures show the state probability map results, considering different acuity values (5.0, 10.0, 15.0, and 20.0) for image coordinate attributes X and Y.

  (a)) and an elderly woman (Figure 18(b)), both performing tasks of everyday life as cooking, resting, and having lunch. The lengths of the sequences are 40000 frames (approximately 67 minutes) and 28000 frames (approximately 46 minutes).

Figure 17 :Figure 18 :

 1718 Figure 17: Figures (a) and (b) respectively show the number of states and events at each frame, for each acuity value, obtained by processing the rat experiment video.

Figure 19 :

 19 Figure 19: Sequence of recognised events and ground-truth for the elderly woman video. The coloured arrows represent the events, while coloured zones represent the duration of a state before the occurrence of an event.

Figure 20 :

 20 Figure 20: Situation where the person goes from the kitchen to the table.Figures (a), (b), and (c), in this order, describe the way this situation occurs in the scene.

Figure 21 :

 21 Figure 21: Representation of the situation where the person goes from the kitchen to the table in the hierarchy obtained for the learning context Position -Posture -S ymbolicDistance.

Figure 22 :

 22 Figure 22: Situation where the person passes to the crouching posture and then returns to the standing posture, near the table.Figures (a), (b), and (c), in this order, describe the way this situation occurs in the scene.

  Figure 22: Situation where the person passes to the crouching posture and then returns to the standing posture, near the table.Figures (a), (b), and (c), in this order, describe the way this situation occurs in the scene.

Figure 23 :

 23 Figure 23: Representation of the situation where the person passes to the crouching posture and then returns to the standing posture in the hierarchy obtained for the learning context Position -Posture -S ymbolicDistance.

  1. Incorporating T to an existing state P gives the best CU score. In this case, updateStates is recursively called, considering P as root. 2. The generation of a new state concept Q from T gives the best CU score. In this case, Q is inserted as child of C, and the updating process stops.updateStates is recursively called, using the sub-tree from state M as the tree to be analysed. The merge operator is described in detail in Section 4.5. 4. Consider z as the CU score of replacing state P with its children. If z is the best score, H is modified by the split operator. This process implies to suppress the state concept P together with all the events in which the state is involved, as depicted in Figure4. Then, updateStates is called, using the sub-tree from the current state C again. Split operator in MILES algorithm. The blue box represents the state to be split. Red dashed lines represent events. Notice that the split operator suppresses the state S 3 and its arriving and leaving events, and ascends the children of S 3 in the hierarchy.

			S	0
								S	0
	S 1		S 2	S	3
						Split
							S 1	S 2	S 3.1	S 3.2	S 3.3
	S 1.1	S 1.2	S 3.1	S 3.2	S 3.3	S 1.1	S 1.2
	Figure 4:

3. Consider M as the resulting state from merging the best state P and the second best state R. Also, consider y as the CU score of replacing P and R with M. If y is the best score, H is modified by the merge operator. Then,

Standing up at table zone Start going to kitchen zone Changing position in the kitchen

	Ground-truth:
	0	50	100	150	200	250	300	350 Frame Number 400	450	500	550	600	650	700	750
	Recognized
	event concepts:
	0	50	100	150	200	250	300	350 Frame Number 400	450	500	550	600	650	700	750

The algorithm has been developed with C++, using QT libraries, and is available at http://profesores.elo.utfsm.cl/ ~mzuniga/MILES.zip

MILES information video available at: http://profesores.elo.utfsm.cl/ ~mzuniga/milesX4.mp4

MILES acuity video available at: http://profesores.elo.utfsm.cl/ ~mzuniga/acuityX4.mp4

Francois.Bremond (Franc ¸ois Brémond), http://www-sop.inria.fr/teams/pulsar/personnel/Monique.Thonnat (Monique Thonnat)