Samuel N Pagliarini
email: samuel.pagliarini@telecom-paristech.fr

Lirida A De

B Naviner

Jean-Franc ¸ois Naviner
email: lirida.naviner@telecom-paristech.fr

Selective Hardening Methodology for Combinational Logic

Keywords: Reliability, Single Event Effects, Selective Hardening, Logic Masking

Defects as well as soft errors are a growing concern in micro and nanoelectronics. Multiple faults induced by single event effects are expected to be seen more often. Thus, reliability has become an important design criterion. In this context we introduce a cost-aware methodology for selective hardening of combinational logic cells. The methodology is based on the SPRA algorithm for calculating logical masking, and it is capable to automatically perform a trade-off between reliability improvements and associated costs, providing a list of the most effective candidates for hardening. The methodology is applied to a set of benchmark circuits using costs extracted from an actual standard cell library. The results then show that the methodology is able to diminish the unreliability of circuits in a cost-effective manner.

I. INTRODUCTION

The amount of defects as well as the number of soft errors (i.e., transient errors) in electronic circuits are expected to increase, becoming a major concern in current and future technologies [START_REF] Nicolaidis | Design for soft error mitigation[END_REF]. Thus, there is a current trend in the design of these circuits in which reliability related criterion are more and more common in the design flows.

Transient errors have many different sources. The transient faults that originate the errors can be caused by different physical phenomena, such as high-energy particle hits originating from cosmic rays, capacitive coupling, electromagnetic interference, or power transients [START_REF] Saggese | An experimental study of soft errors in microprocessors[END_REF]. Transient errors induced by the strikes of energetic particles at the devices are of great concern, specially for dependable systems and circuits [START_REF] Nicolaidis | Design for soft error mitigation[END_REF][START_REF] Dodd | Basic mechanisms and modeling of single-event upset in digital microelectronics[END_REF]. In the past, transient errors used to be a concern only in the design of memories, thus resulting in the now widely used error correcting codes and other mitigation techniques such as nodal interleaving. On the other hand, at 90 nm and beyond, the reduced dimensions of the devices and also reduced operating voltage levels lead to more common radiation-induced faults in logic, with resulting error rates approaching those of memories [START_REF] Shivakumar | Modeling the effect of technology trends on the soft error rate of combinational logic[END_REF][START_REF] Narasimham | Characterization of digital single event transient pulse-widths in 130-nm and 90-nm cmos technologies[END_REF].

Therefore, transient errors in logic circuits are becoming an important reliability concern for current and future technology. Furthermore, the critical charge and the distance between sensitive junctions are decreasing with scaling. Thus, the energy of radiation particles that is required to cause multiple transient faults is also decreasing. The probability that a single high energetic particle affects the output of more than one circuit node, causing multiple faults, is no longer negligible [START_REF] Rossi | Multiple transient faults in logic: an issue for next generation ics?[END_REF].

On the ocasion of a transient fault, one or multiple electrical pulses may be created. These pulses, typically current spikes, are able to change the current output value of a node from one to zero or vice-versa. Yet, not all transients are able to reach the outputs of the combinational logic since there are natural masking properties against transient errors. These are:

• Electrical masking, which accounts for the attenuation of the current pulses as they propagate through the logic.

• Temporal masking, or latch-window masking, which defines a time interval in which the transients that reach the memory elements of the circuit will or will not be registered.

• Logical masking, which accounts for the lack of sensitized paths (from the erroneous node) to a primary output or memory element.

Among the masking phenomena that render immunity to combinational logic circuits from soft errors, logical masking is the hardest to model and characterize [START_REF] George | Characterization of logical masking and error propagation in combinational circuits and effects on system vulnerability[END_REF]. Also, logical masking is technology-independent. Thus, in this work we focus on calculating the reliability of a circuit considering only the logical masking. The other masking properties can be interpreted as derating factors, i.e., by calculating only the logical masking we are providing a underestimate of the actual circuit reliability. Electrical and latching-window masking computations may actually filter out some of the errors that logical masking does not filter.

Hardening techniques are applied in order to mitigate transient errors. Traditional hardening consumes too much area and/or energy to be cost-effective in commercial applications. Selective hardening, applied only to a design's most errorsensitive parts, offers an attractive alternative [START_REF] Polian | Selective hardening: Toward cost-effective error tolerance[END_REF][START_REF] De | Reliability analysis based on significance[END_REF]. Thus, considering logical masking, the main idea is to classify the composing blocks (i.e., standard cells) of a circuit according to their relative significance with respect to the reliability of the circuit. With the classified list of blocks it is possible to apply selective hardening either by using hardening by design techniques or by more generic fault tolerance techniques like Triple Modular Redundancy (TMR). By using an additional hardening affinity parameter, a trade-off between the hardening cost of a block and the reliability gain is then clearly stablished.

A. Related work

In [START_REF] De | Reliability analysis based on significance[END_REF] we have studied the same problem of selective hardening but considering only single faults and by applying a different simulation/emulation model for obtaining the reliability figures. Such reliability methodology is referred as Probabilistic Binomial Reliability (PBR) [START_REF] De Vasconcelos | Reliability analysis of combinational circuits based on a probabilistic binomial model[END_REF]. The main drawback of the PBR methodology is the need for fault simulation or fault emulation, tasks that are inherently time consuming.

In [START_REF] Polian | Scalable calculation of logical masking effects for selective hardening against soft errors[END_REF] the authors have described a very similar approach for selective hardening. They have chosen an algorithm with linear complexity and accept the fact that innacurate values will be used for estimating the relative reliability gains of hardening a given cell in a circuit. We have used the same premise in our work. Yet, they are only concerned with single faults. Also, they propose a cost target such that the number of hardened cells does not exceed a cost limit L. All nodes have the same weight if this hypothesis is used while in our approach each type of node has a different cost. For instance, it is quite less costy to triplicate an inverter than to triplicate an or gate with several inputs.

B. Contribution

Our contribution is to provide an efficient methodology for selective hardening of the most critical blocks of a digital circuit. This methodology takes into account the effects of multiple faults since these are more prone to happen nowadays. Our methodology is also scalable since it relies in an algorithm with linear complexity to calculate the logical masking effect. A parameter similar to a hardening cost is also introduced, which allows the designer to drive the methodology using accurate cost values for the hardening of each block.

C. Overview

This paper is organized as follows: Section II contains the basic definitions used by our reliability estimation method. Section III describes the steps used to build the methodology to classify the blocks. It also contains a comparison among an accurate reliability estimation method and the approach we have used. Finnaly, in Section IV we have applied the proposed methodology in a series of circuits of different types, while in Section V we present our final remarks.

II. PRELIMINARIES

The reliability of a given circuit is the degree of confidence observed in the outputs of this circuit, given a certain scenario in which faults are expected to occur with a given probability. In this work we obtain the reliability figures of a circuit by applying the Signal Probability Reliability Analysis (SPRA) algorithm [START_REF] Franco | Signal probability for reliability evaluation of logic circuits[END_REF]. Based on a straightforward signal reliability computation and propagation algorithm, SPRA allows the evaluation of the logical masking capability of combinational logic circuits. Let us then define signal reliability.

A. Signal reliability

We consider the signal reliability of a given signal as the probability that this signal carries a correct value [START_REF] Franco | Signal probability for reliability evaluation of logic circuits[END_REF]. So, it is assumed that a binary signal x can also carry incorrect information. This results in the fact that x can take four different values: correct zero (0 c ), correct one (1 c ), incorrect zero (0 i ) and incorrect one (1 i ). Then, the probabilities for occurrence of each one of these four values are represented in matrices, as shown bellow:

P (x = 0 c ) P (x = 1 i ) P (x = 0 i ) P (x = 1 c ) = x 0 x 1 x 2 x 3 (1)
The signal reliability for x, noted R x , comes directly from expression [START_REF] Saggese | An experimental study of soft errors in microprocessors[END_REF], where P (.) stands for the probability function:

R x = P (x = 0 c ) + P (x = 1 c ) = x 0 + x 3 (2)

B. Reliability of a block

Digital circuits are composed of many connected blocks, typically standard cells. Let us consider one of these blocks which performs a function on a signal x in order to produce a signal y, i.e., y is the output of the block. The probability that this block fails is given by p, such that (0 ≤ p ≤ 1). Thus, q = (1p) is the probability it works properly. We can obtain the reliability of the signal y as:

R y = (x 0 + x 3 ).q + (x 1 + x 2 ).p (3)
Equation [START_REF] Dodd | Basic mechanisms and modeling of single-event upset in digital microelectronics[END_REF] shows that, when the input signal is reliable, the output signal reliability is given by q. This implies that for fault-free inputs, the reliability of the output signal is given by the inherent reliability of the block that produces this signal. More complex scenarios are evaluated by also taking into account the truth table of the logic blocks.

SPRA uses both the reliability of the blocks as well as signal reliability to determine the cumulative effect of multiple simultaneous faults in the reliability of a circuit. To each signal in the circuit a signal reliability matrix is attributed. The propagation of these signals through the logic blocks is done by performing operations (tensoring and multiplying) in these matrices to calculate the actual reliability of the entire circuit. The basis for the SPRA algorithm comes from the Probabilistic Transfer Matrices algorithm (PTM) [START_REF] Patel | Evaluating circuit reliability under probabilistic gate-level fault models[END_REF][START_REF] Krishnaswamy | Accurate reliability evaluation and enhancement via probabilistic transfer matrices[END_REF]. The main difference is that the PTM approach does not scale well, while the SPRA approach has a linear complexity.

III. SELECTIVE HARDENING METHODOLOGY

The reliability of a circuit consisting of several blocks depends on the reliabilities of these individual blocks. This is shown in equation ( 4) for a circuit consisting of K blocks, where R is the circuit's reliability and q i , q j stand for the reliabilities of the blocks b i , b j respectively (1 ≤ i, j ≤ K). R = f (q 1 , q 2 , ...q i , ...q j , ...q K ) (

Assume that the blocks are independent in the sense that changing the reliability of a given block b i has no impact on the reliability of another block b j with i = j.

If we consider that a reliability change of a single block b i brings in its new reliability q * i , the circuit's reliability becomes R * i . Because different blocks b i and b j make different contributions to the reliability of a circuit, changes of different blocks may produce different values R * i and R * j [START_REF] De | Reliability analysis based on significance[END_REF]. In our methodology we assume that there is a hardening technique that is able to improve the reliability of a given block b i , such that q * i = 1. This is not a restriction, it is just a simplification, other values are also possible. Then, for all blocks of the circuit we perform an evaluation run of the SPRA algorithm. In each evaluation run we select a node b i , allow q * i to be 1, and obtain the new reliability value R * i . This effort is possible since the complexity of the SPRA algorithm is linear.

After all initial evaluation runs are performed, we obtain a list of all R * i values. At this point, one could sort the list and elect the block with the highest R * i to be hardened. This is the approach followed in [START_REF] De | Reliability analysis based on significance[END_REF]. Yet, we are interested in stablishing a trade-off between the cost of hardening this block against the cost of hardening any other block. In order to do so, we introduce a new parameter to express the hardening affinity of such block, given by Ha i .

The parameter Ha i of each type of cell is defined by the user. It must be constrained in the interval [0,1]. This parameter is generic and can be used to express any type of hardening trade-off: area, delay, power or combinations of the previous.

It can also be used to model other situation of particular interest: assume that a certain cell is available in two versions in the same standard cell library, let us say IN V t and IN V h . The former is a traditional design while the latter is a hardened by design version of an inverter. Assume that the hardening by design, once is already done, has no additional cost to be implemented. Thus, to model this situation one should say that this particular cell has the highest hardening affinity, i.e., the Ha i of IN V h is 1. Since the other types of cells have no hardened versions available, they will require a technique such as TMR to be applied. This technique is expected to have a larger cost and therefore any cell requiring TMR will have a Ha i < 1.

In Tab. I we show the values that were used in our experiments for some cells. These values are extracted from an actual 90nm standard cell library provided by Synopsys [START_REF]Saed 90nm generic library[END_REF]. In our analysis we considered that only the dynamic power of the blocks would be considered to calculate the hardening affinity. So, for each cell in the library, we have divided the dynamic power of the smallest inverter in the library by the given cell actual dynamic power. It is possible to notice that negated cells (like NOR and NAND) benefit from the CMOS natural inversion and have a higher hardening affinity. It is also possible to notice that inverters have the smallest dynamic power of all cells. All the other Ha i values are normalized.

After each cell's affinity is known it is necessary to apply this value to decide wich block should be selected for hardening. This step of the methodology introduces a new value, the reliability gain or reliability difference, given by Rg i . This is the difference from the circuit reliability before and after a single block was hardened. For each evaluation run this value is calculated as follows:

Rg i = R * i -R (5)
The value of ( 5) is then used to calculate the reliabilityaffinity product as follows:

P rh i = Rg w1 i × Ha w2 i (6)
where w1 and w2 are the weigths to be applied. I.e., the user may choose if reliability should be more important than power or vice-versa, and by which amount. In the experiments that are presented in Section IV, these values were set as w1 = 2 and w2 = 1.

Once the value of (6) has been calculated for all cells, these are sorted and the highest value is picked. This block is then assumed to be hardened and the new circuit reliability (R * i ) is obtained. This reliability is then compared against a user-given reliability target. If it is lower than the target the methodology algorithm starts again and all cells still not hardened are considered as candidates. Otherwise, if the target is met, the algorithm ends and outputs the ordered lists of cells to be hardened.

A. Comparison with an accurate reliability analysis algorithm

Our methodology uses the SPRA algorithm which is not accurate. The sources of inaccuracies come from incorrect evaluation of multiple fanout branches. An accurate analysis is possible using the multi-pass algorithm described in [START_REF] Franco | Signal probability for reliability evaluation of logic circuits[END_REF], here referred as SPRMP. It is well known that both algorithms produce different values for the reliability of a circuit. Yet, we are interested in comparing how well SPRA estimates the critical node in comparison with SPRMP.

Let us first consider a simple circuit, c17, which has only 6 nodes. By applying both algorithms just once, i.e., neglecting a reliability target given by the user, two lists of b i nodes are created. These lists are sorted according to the R * i of each node and are referred as L b . These lists are showed in Tab. II.

The meaning of each column of Tab. II is as follows:

• Position is the ranking of the nodes according to R * i . • SPRMP's L b is the list of nodes generated by the SPRMP algorithm, i.e., the accurate list.

• SPRA's L b is the list of nodes generated by the SPRA algorithm, i.e., the inaccurate list.

• Position difference is the difference in the ranking from column 3 with respect to column 2. E.g., block 4 is ranked first in the SPRA's L b list while it is ranked second in the SPRMP's L b list, thus the difference is 1 position.

• Normalized difference is the position difference divided by the maximum position error possible. In this example it is 5 since the circuit has 6 blocks. According to the analysis of the circuit c17 presented in Tab. II, the average error introduced by the SPRA algorithm is 13.3%. Yet, we have performed this same analysis for other circuits with different profiles, all containing multiple fanouts branches. The selected circuits are very limited in size since the execution time of the SPRMP algorithm is very high even for medium-sized circuits. The details of the chosen circuits are as follows:

• 74283, a 4 bit adder.

• AOI, which contains an and-or-inverter logic and 2 multiple fanouts.

• AOIX2, which contains a larger and-or-inverter logic followed by a buffer network with many multiple fanouts.

• decoder, which contains a large or-like logic to decode 8 inputs. Each input feeds many gates so multiple fanouts appear already in the inputs.

• chain, which contains a chain of inverters and or gates.

Table III summarizes the comparison of all the presented circuits plus the already presented c17 one.

The results in Tab. III clearly show that for some circuits both algorithms produce the same list of blocks to be hardened. Yet, for the circuits c17, 74283 and AOIX2 the maximum error is quite high. A deeper analysis is performed for such circuits, where the error distribution is analysed.

The error distribution for the 74283 circuit is shown in Fig. 1, where the nodes in the x axis are sorted according to R * i (the actual labels are the ids of the blocks in the circuit). It is possible to notice that some blocks have a higher error probability. Yet, that is not the case for the blocks that are closer to the y axis (which are exactly the best candidates for hardening). This same profile, where the error is not that high in the elected block, is also seen in the error distribution of the other circuits. The same profile is also observed after some cells have already been elected for hardening. Thus, our results are presented using the SPRA algorithm only.

In the particular case of the AOIX2 circuit, the higher error values are due to the large number of multiple fanouts in the buffer network. Regarding the circuit c17, it only has 6 cells. So any small difference is very meaningful, even in relative terms.

IV. EXPERIMENTAL RESULTS

The methodology described in Section III was applied to several ISCAS benchmark circuits [START_REF] Brglez | A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran[END_REF]. Each block from each circuit was set using q i = 0.9999. The reliability target was adjusted so a decrease of the unreliability would be reached for each circuit. The results are presented in tables IV and V. The former table contains the results for a reduction of at least 20% (w.r.t. the original unreliability) while the latter contains the results for a reduction of at least 40%. The original unreliability of each circuit is given in the second column of the aforementioned tables.

The column entitled "Original Power" contains the sum of the dynamic power of all cells of each circuit. The columns entitled "Hardened Cells" contain the amount of cells that are elected for hardening. By using the hardening affinity parameter this number tends to increase. Then, the columns entitled "Power" contain the sum of the dynamic power of all cells of the new version of the circuit. A fairly simple assumption was made: on hardening a given node we should add three times the value of the power of that node to the overall circuit power. Thus the additional power that would be consumed by a voter is not considered. Once again, this is a simplification. A voter should be considered for a group of cells and not for a single cell, otherwise the costs can become unfeasible. Assuming one voter for each hardened cell would create a large cost both in terms of area and power. Therefore the power figures given in the tables are a minimum value estimate. Voter placement (i.e., TMR granularity) is not the scope of this work.

In tables IV and V some power figures are highlighted in bold. It is clear that applying the methodology considering the hardening affinity is an effective trade-off between power and reliability in these cases. This does not mean that the methodology is not appropriate for the other circuits. In fact, it means that the current choice of parameters w1 and w2 is not a good one for the circuits that are not highlighted.

A. Comparison

A straightforward comparison with other methodologies is not simple since the goals are different. The results presented in [START_REF] De | Reliability analysis based on significance[END_REF] are in alignment with the results presented in this work, which is a strong suggestion that multiple faults do not have a large impact on the decision of which node to harden. Yet, they have a considerable effect on the actual reliability of the circuit. Thus, they are important when determining the tradeoffs between cost and reliability.

A radiation hardening technique for combinational logic is proposed in [START_REF] Zhou | Cost-effective radiation hardening technique for combinational logic[END_REF]. The hardening is achieved by increasing the gate size of some critical nodes in the circuit but no hardening against defects is mentioned. Thus the technique presented here is more of a general solution since it is technologyindependent. The overheads mentioned in [START_REF] Zhou | Cost-effective radiation hardening technique for combinational logic[END_REF] are not directly comparable.

Nevertheless, in qualitative terms it is easily observed that certain cells have a larger impact in the reliability of the circuit than others. This observation is highlighted in [START_REF] De | Reliability analysis based on significance[END_REF][START_REF] Polian | Scalable calculation of logical masking effects for selective hardening against soft errors[END_REF][START_REF] Zhou | Cost-effective radiation hardening technique for combinational logic[END_REF]. In our exeperiments this was also observed. There are some particular cases, like the one illustrated in Fig. 2, where choosing the correct node to harden has a large impact in the overall circuit reliability. The analysis depicted in Fig. 2 is from the circuit c1355.

Regarding Fig. 2, it contains the R * i values related to the hardening of all possible cells. The nodes in the x axis are ordered by the reliability gain that hardening that node would produce. The circuit was evaluated given the parameter q i = 0.9999 for each cell. In absolute terms the difference from the Fig. 2: Reliability gain versus chosen node to be hardened. best to the worst candidate is not large. Yet, usually several cells are selected for hardening (as in Tab. V), so these values accumulate. Thus choosing the best candidate for hardening is critical.

V. CONCLUSION

In a context where defects and soft errors are a growing concern, we have proposed a selective hardening methodology for combinational logic nodes. Furthermore, we have also concerned multiple faults to determine the actual reliability of the circuits.

Our results present the use of the methodology in conjunction with a standard cell library from an actual vendor, where the trade-off between power and reliability gain is highlighted. Thus, the methodology can be integrated in commercial design flows in a very straightforward manner. Other cost-effective schemes are also possible since the methodology contains a generic parameter to define the hardening affinity of a node.

In our future works we plan to investigate the effects of multiple faults in the reliability of a circuit by limiting the effect of multiple faults locally in the circuit. The study of the relationship between parameters w1 and w2 is also a matter for a future work.

Fig. 1 :

 1 Fig. 1: Error distribution for the circuit 74283.

TABLE I :

 I Hardware affinity (Ha i ) parameters for several blocks.

	Block	Power (nW/MHz) Hardening affinity
	INVX0	10	1
	NAND2X0	3583	0.002790957
	NOR2X0	4211	0.002374733
	AND2X1	6545	0.001527884
	OR2X1	6859	0.001457938
	OR4X1	7698	0.001299039
	MUX21X1	8639	0.001157541
	XOR2X1	8702	0.001149161
	AOI21X1	13912	0.000718804

TABLE II :

 II Comparison of the SPRA and SPRMP algorithms.

TABLE III :

 III Comparison of the methodology using the SPRA and SPRMP algorithms.

TABLE IV :

 IV Results for decreasing the unreliability by at least 20%.

	Circuit	Original Unreliability	Original Power (nW/MHz)	No hardening affinity Hardened cells Power (nW/MHz) Hardened With hardening affinity cells Power (nW/MHz)
	c17	0.000562	21498	1	21498	1	21498
	74283	0.003848	189244	4	222932	8	189404
	c432	0.013466	624686	9	624866	9	624866
	c499	0.013611	1321460	20	1669540	41	1322280
	c1355	0.021905	1907300	38	2179608	38	2179608
	c1908	0.031668	2146539	58	2147699	58	2147699
	c3540	0.062635	5.90419e+06	54	5.90527e+06	54	5.90527e+06
	c2670	0.064015	4.07731e+06	41	4.12503e+06	42	4.08044e+06
	c5315	0.085614	8.89708e+06	59	8.96576e+06	60	8.90057e+06

TABLE V :

 V Results for decreasing the unreliability by at least 40%.

	Circuit	Original Unreliability	Original Power (nW/MHz)	No hardening affinity Hardened cells Power (nW/MHz) Hardened With hardening affinity cells Power (nW/MHz)
	c17	0.000562	21498	2	35830	2	35830
	74283	0.003848	189244	10	273464	16	189564
	c432	0.013466	624686	26	625206	26	625206
	c499	0.013611	1.32146e+06	48	2.15685e+06	80	1.42736e+06
	c1355	0.021905	1.90730e+06	83	2.50208e+06	83	2.50208e+06
	c1908	0.031668	2.14653e+06	132	2.14918e+06	132	2.14918e+06
	c3540	0.062635	5.90419e+06	175	5.90769e+06	175	5.90769e+06
	c2670	0.064015	4.07731e+06	128	4.22630e+06	128	4.08444e+06
	c5315	0.085614	8.89708e+06	205	9.13570e+06	207	8.90465e+06

ACKNOWLEDGMENT

This work was partially funded by the CATRENE project RELY.


Manar Qamhieh
email: manar.qamhieh@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Laurent George
email: lgeorge@ece.fr

A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model

In this paper, we consider parallel real-time tasks following a Directed Acyclic Graph (DAG) model. This task model is classical in embedded and industrial system applications. Each real-time task is defined by a set of subtasks under precedence constraints. With each subtask being associated a worst case execution time and a maximal degree of parallelism. We propose a parallelizing algorithm based on the critical path concept, in which we find the best parallelizing structure of the task according to the response time and the required number of processors, considering the worst case execution time of the subtasks.

Introduction

Multi-core processors are widely produced nowadays in order to cope with the physical constraints of the manufacturing process, which makes the development of parallel softwares more and more important. The same concept can be applied to real-time systems. Those systems have been thoroughly studied over the last forty years but were mostly focused on sequential processing. In order to get advantage of the new hardware developments in real-time systems, a new challenge towards integrating parallelism in real-time systems has appeared.

Many models of parallelism have been used in programming languages and APIs, but few of them have been studied in real-time systems. In our work, we propose a more general model of parallel tasks following a Directed Acyclic Graph (DAG) with 2 levels of parallelism. This type of model can be used to represent real industrial applications like video surveillance network and complex 3D games, in which many images are processed at the same time. Then, we propose a parallelism algorithm in order to execute the DAG task with the best parallel structure of the task while taking the response time in consideration.

In this paper, we start by presenting other related parallel task models already studied in the literature in section 2. Then we present our task model in section 3. Section 4 describes the parallelizing algorithm applied to a DAG. Finally, we finish the paper with conclusion and perspectives in section 5.

Related Work

Parallelism in real-time systems is a new domain with many open issues to be studied. There exist many programming APIs which support parallelism like OpenMP [START_REF]Openmp[END_REF], Cilkplus, Go, etc. The fork-join parallelism model is used in OpenMP. It is defined as a sequence of sequential and parallel segments, since the main thread of the task forks into many parallel threads during the execution, and when they finish their execution, they join the main thread again. This model is studied in [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF] and a stretching algorithm has been proposed to transform parallel tasks into sequential tasks when possible.

However, a more general model of parallel tasks has been recently proposed in [START_REF] Saifullah | Multi-core realtime scheduling for generalized parallel task models[END_REF] which overcomes the restrictions of the fork-join model. It replaces the sequential-parallel segment ordering with parallel segments. Those segments have an arbitrary number of threads, but the execution time of all the threads in the same segment is the same. In their work, they propose a decomposition algorithm to assign local deadlines for the different parallel segments and to transform them into sporadic sequential tasks. They also provide a resource augmentation bound for this decomposition algorithm of 4 when the tasks are scheduled using global EDF and of 5 for partitioned deadline monotonic scheduling, respectively.

The latter model has been generalized in [START_REF] Nelissen | Optimizing the number of processors to schedule multi-threaded tasks[END_REF], they propose sporadic parallel real-time tasks with constrained deadlines. It differs from the model in [START_REF] Saifullah | Multi-core realtime scheduling for generalized parallel task models[END_REF] by allowing threads in the same segment to have different worst case execution time. As a result of the paper, they optimize the number of processors needed to schedule this model of tasks while applying the same resource augmentation bounds performed before.

Task Model

In this paper, we deal with parallel implicit-deadline real time tasks, where the deadline of a task equals to their period, and each task of this model is represented by a directed acyclic graph (DAG), which is a collection of subtasks and directed edges, which represents the execution flow of the task and the precedence constraints between the subtasks. Precedence constraint means that each node can start its execution when all of its predecessors have finished theirs. If there is an edge from subtask τ i,u to τ i,v , then we can say that τ i,u is a parent of τ i,v , and τ i,v has to wait for τ i,u to finish its execution before it can start its own. Each vertex in the graph may have multiple parents, and multiple child vertices as well, but each graph should have single source and sink vertices.

Each parallel real-time task τ i consists of a set of q i subtasks, τ i = {τ i,1 , τ i,2 , ..., τ i,qi }, and each subtask τ i,k is represented as the following:

τ i,k = {e i,k , m i,k }
, where e i,k is the worst execution time of the subtask, and m i,k is the maximal degree of parallelism of τ i,k , which means that the subtask τ i,k can be scheduled on m i,k parallel processors at most. Figure 1 shows an example of a parallel real-time task τ i of 6 subtasks. τ 1 = {τ 1,1 , τ 1,2 , ..., τ 1,6 }. τ 1 has a single source subtask τ 1,1 and a single sink subtask τ 1,6 . Each subtask is characterized by an ordered pair, the first is the total execution time of the subtask and the second is the maximal degree of parallelism. As shown in Figure 1, τ 1,4 for example, has a total execution time of 3, and it can be parallelized at most on 3 processors with 1 execution time unit on each processor. This parallel real-time tasks of graph model have 2 levels of parallelism; a inter-subtask parallelism and intra-subtask parallelism. The inter-subtask parallelism is caused by the precedence constraints between the different subtasks in the task. Subtasks sharing the same parent means that they are activated at the same time (when the parents finish their execution), allowing them to execute in parallel on multiple processors. τ 1,2 and τ 1,3 in Figure 1 are an example of this subtask parallelism. The intra-subtask parallelism is denoted by the possibility of parallelizing each subtask τ i,k on x number of processors, where 1 ≤ x ≤ m i,k . A parallel subtask τ i,k with maximal degree of parallelism m i,k equals to 1 can be considered as a sequential subtask.

In this paper, we chose to work with a generalized model of parallel tasks, a model that describes the industrial and embedded systems applications. We are different from the parallel models of [START_REF] Saifullah | Multi-core realtime scheduling for generalized parallel task models[END_REF] and [START_REF] Nelissen | Optimizing the number of processors to schedule multi-threaded tasks[END_REF] by proposing the intra-subtask parallelism within the real-time task model of graphs. While in the other models, a parallel real-time task starts as a collection of segments and then they propose the possibility of transforming it into a DAG, while the same decomposition algorithm and feasibility analysis remain ap-plied. 1,1 6,2 This general parallel task model of graphs has many possibilities regarding the execution flow of the subtasks in the same task due to the intra-subtask parallelism described before in 3. Task τ 1 from Figure 1 has 3 parallelizable subtasks (τ 1,2 , τ 1,3 , τ 1,4 ), they can either be parallelized or executed sequentially. The simplest solution will be to parallelize them all up to their maximum degree of parallelism. However, this solution will achieve the minimum response time of τ 1 when compared with other parallelizing structures, but with no consideration for the precedence constraints within the subtasks or the number of processors needed.

In this section, we propose a parallelizing algorithm that uses the critical path of a graph technique which is based on the depth-first search algorithm, and finds the best parallel structure of the task with minimum response time and number of processors. We assume a univocal task to processor assignment (the processors assigned to a task will only run this task). This leads to consider that the number of processor is high compared to the number of tasks. We plan to remove this restriction as a further work.

The algorithm we propose considers first a system with unlimited number of processors. We finally obtain with the algorithm the exact number of processors required for a given task.

Definition. Critical path P i of a parallel real-time task is the path through task τ i with the longest sequential execution time when τ i is executed without intra-subtask parallelism on a system with infinite number of processors.

For a real-time graph task, P i can be considered as the maximum execution time of τ i , that τ i will need at least P i units of time to finish its execution when all its subtasks execute sequentially without parallelism. Subtasks in the critical path are called the critical subtasks.

According to task τ 1 shown before in Figure 1, Figure 2(a) shows its critical path, P 1 = {τ 1,1 , τ 1,2 , τ 1,6 }. We can notice that this path has the longest consecutive execution time of the task which is 8, while the other possible paths {τ 1,1 , τ 1,3 , τ 1,4 , τ 1,6 } and {τ 1,1 , τ 1,3 , τ 1,5 , τ 1,6 } have execution time of 7 and 6 respectively.

According to Algorithm 1, we can calculate the critical path and the slack time of the non-critical subtasks by performing forward and backward calculations, the forward calculation of a subtask x is denoted as F (x), for each subtasks in the graph starting from the source of the graph, F (x) is the maximum sum of the execution time of its preceding subtasks. F (τ i,sink ) is the response time of τ i .

Backward calculation R(x) is performed on each subtask starting from the sink of the graph, we calculate the minimum available time for the path of subtasks to execute from the x until the source of the graph. For each subtask τ i,j , the difference between the backward and forward calculations is its slack time, if it equals to 0, then τ i,j is a critical subtask.

In order to perform the calculations proposed in Algorithm 1, we need to find the subtask flow in the graph, by determining depth levels of each subtask. The source subtask will be in the first level, and its children are in 2, and so on... For any subtask τ i,k in the graph, its depth is denoted as h(k) and is calculated as the following:

h(k) = max u parent of k h(u) + 1
If a subtask τ i,k has multiple parents, it will follow the parent subtask with the maximum depth. The maximum depth of the graph is denoted by H = h(τ i,sink ).

In our algorithm and while calculating the critical path of a graph, we give a higher priority for the parallel nodes, that if we have 2 different critical paths, we choose the one with the highest probability of parallelism. In this case, we increase the number of parallelized subtasks while keeping the same response time or reduce it.

The critical path method is not new, it is used in operation analysis of graph tasks and based on depth-first search algorithm, in order to choose the sequence of actions that will define the execution of the task as whole, and any delay in these actions will delay the total execution time of the operation.

Parallelizing algorithm:

By using the critical path algorithm and as shown in Figure 2, we can find the critical subtasks in τ i that determine the response time of the task, where the rest of the "noncritical subtasks" has certain amount of slack time calcu-Algorithm 1 Calculating the critical path of a graph

for depth h = 1 → H do for each subtask k in h do F (k) = max u parent of k F (u) + e i,k end for end for R(H) = F (H) for h = (H -1) → 1 do for each subtask k in h do R(k) = min u child of k F (u) -e i,u end for end for for i = 1 → s i do if F (i) = R(i) then subtask i is a critical subtask. else Slack(i) = R(i) -F(i).
end if end for lated by Algorithm 1. Since we are concerned with parallelizing the parallel subtasks of the graph while keeping the best possible response time of the task, we will start by parallelizing the critical subtasks.

Figure 2 shows the parallelizing process of the task τ 1 shown before. The first step is to find the critical path of the task, which is P 1 = {τ 1,1 , τ 1,2 , τ 1,6 }, which has a single parallel critical subtask τ 1,2 , and it can be executed on 2 processors (m 1,2 = 2). So, we will divide it into 2 sequential subtasks of execution time = 6/2 = 3. This parallelizing process will modify the structure of the graph and its response time, so we can calculate a new critical path P 1 = {τ 1,1 , τ 1,3 , τ 1,4 , τ 1,6 } which can be also parallelized as shown in Figure 2(b). This process will be repeated until we get a graph with critical path that can't be parallelized any more, like in Figure 2(c).

This parallelizing process will change the structure of the graph and reduce the response time of the task as well. As shown in Figure 2, τ 1 had a response time of 8 when executed on 3 processors in the first iteration, but in the final iteration, it has 5 units of response time when executed on 6 processors. We believe that reducing the response time of the task on the behalf of the number of processors is acceptable since multi-processor systems are widely manufactured. However, in the next section we will optimize the number of processors resulted from the parallelizing algorithm.

Optimization:

As mentioned before, the previous parallelizing algorithm tends to parallelize the real-time subtasks to their maximal degree of parallelism in order to reduce the response time of the task, without considering the placement of these parallel subtasks or the number of processors needed for scheduling. As a final step of the algorithm we tend to find a better placement of the generated parallelized subtasks so as to reduce the number of processors without affecting the calculated response time. Optimizing the placement of the non-critical subtasks depends on 2 factors; the execution time of the subtask and the slack time.

1,1 6,2 1,1 2,2 3,3 2,1 2(3,1) 1,1 2,2 1,1 3,3 2,1 1,1 1,1 2(3,1) 2(1,1) 2,1 3(1,1) Processors Time
According to algorithm 1, critical subtasks have no slack time, and they have to execute without delay in order to get the best response time of the task. But this is not the case for the non-critical subtasks, their paths through the graph will have strictly an execution time equal to the critical path at most, and algorithm 1 can calculate the slack time of all the non-critical subtasks in the graph.

Figure 3(a) shows the final placement of the subtasks of τ 1 after applying the parallelizing algorithm, and we can notice that task τ 1 can be fully executed on 6 processors with 5 units of time. However, this placement of subtasks is not the optimal, since there exists a non-critical subtask in the graph with slack time S 1,4 = 1. So, the 3 rd thread of the subtask can be placed in the slack time of the subtask without increasing the response time of the τ 1 .

The advantage of this optimizing process is to occupy the idle time of processors with non-critical subtasks with sufficient slack time. This optimizing step will reduce the overall number of processors needed by the task in order to execute within the same response time.

Perspective and Conclusion

In this paper, we have introduced a parallel real-time tasks graph model, and we have proposed a parallelizing algorithm for this model which gives the best parallelizing structure of the task according to the response time when executed on a specific number of processors. Until now, we only considered a univocal task to processor association, but we aim to extend our work to take into account several parallel graph tasks on a processor, and study their schedulability and interference. The parallelized task can be seen as a set of parallel segments with arbitrary number of threads execute on multiple processors, feasibility analysis studies used before in [START_REF] Saifullah | Multi-core realtime scheduling for generalized parallel task models[END_REF] and [START_REF] Nelissen | Optimizing the number of processors to schedule multi-threaded tasks[END_REF] can be adapted on our task model, and in the future we will work on proposing feasibility analysis for the schedulability of tasks parallelized using the proposed DAG model.

Figure 1 .

 1 Figure 1. Example of the task model.

Figure 2 .

 2 Figure 2. Example of the parallelizing algorithm.

Figure 3 .

 3 Figure 3. Optimizing the parallelized graph using slack time.


Alessandro Prest
email: prest@vision.ee.ethz.ch

Vittorio Ferrari
email: ferrari@vision.ee.ethz.ch

Cordelia Schmid
email: cordelia.schmid@inria.fr

Explicit modeling of human-object interactions in realistic videos

Keywords: Action Recognition, Human-Object Interaction, Video Analysis. !

 show that (i) our explicit human-object model is an informative cue for action recognition; (ii) it is complementary to traditional low-level descriptors such as 3D-HOG extracted over human tracks. When combining our human-object interaction features with 3D-HOG features [23], we show to improve over their separate performance as well as over the state of the art.

INTRODUCTION

Human action recognition is an open problem in computer vision. It is important for a wide range of applications, such as video indexing and surveillance. It is challenging due to the high variety of human appearances and poses within an action class. In this paper we focus on actions defined by the interaction between a person and an object, such as drinking and smoking.

Many previous approaches represent actions by distributions of low-level descriptors such as bags of spacetime interest points [START_REF] Dollar | Behavior 916 recognition via sparse spatio-temporal features[END_REF], [START_REF] Laptev | Learning 961 realistic human actions from movies[END_REF], [START_REF] Schuldt | Recognizing human actions: 988 A local SVM approach[END_REF] or describe the action as a distribution over point motion features localized in space and time on the human [START_REF] Fathi | Action recognition by learning mid-level 927 motion features[END_REF], [START_REF] Kläser | Human 958 focused action localization in video[END_REF], [START_REF] Laptev | Retrieving actions in movies[END_REF], [START_REF] Mikolajczyk | Action recognition with motion-974 appearance vocabulary forest[END_REF], [START_REF] Willems | Exemplar-996 based action recognition in video[END_REF].

In this paper, we propose a novel approach that has an explicit notion of the action object and represents an action by spatio-temporal descriptors dedicated to human-object interactions. These include the relative motion of the object with respect to the human, which is typically highly distinctive for the action. Measuring these features involves automatically localizing the human and the action object and tracking them over time as shown in fig. 1. Our method is especially designed to do this in realistic videos, such as feature films. It does not involve any component that depends on background subtraction, which makes it suitable for any camera and background motion. Moreover, the method builds on state-of-the-art object detection techniques [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF] Fig. 1. Human-object interactions. Top row: one drinking and two smoking instances from the Coffee & Cigarettes dataset [START_REF] Laptev | Retrieving actions in movies[END_REF]. Second row: examples from the dataset of [START_REF] Gupta | Observing human-949 object interactions: Using spatial and functional compatibility for 950 recognition[END_REF]. Human and object locations automatically obtained by our method are indicated in green and cyan respectively. operating in single frames, and robustly links detections 28 over time even across many frames where the object 29 was missed, again using a state-of-the-art approach [START_REF] Sundaram | Dense point trajectories by 994 GPU-accelerated large displacement optical flow[END_REF]. recent human-centric approaches [START_REF] Laptev | Retrieving actions in movies[END_REF], [START_REF] Mikolajczyk | Action recognition with motion-974 appearance vocabulary forest[END_REF], [START_REF] Kläser | Human 958 focused action localization in video[END_REF], [START_REF] Rodriguez | Action mach: a spatio-983 temporal maximum average correlation height filter for action 984 recognition[END_REF] deal 111 with action localization in realistic video. Laptev and 112 Perez [START_REF] Laptev | Retrieving actions in movies[END_REF] aggregate local spatio-temporal features over 113 time into a spatio-temporal grid. They use keyframe 114 priming to refine the output of their method. In [START_REF] Mikolajczyk | Action recognition with motion-974 appearance vocabulary forest[END_REF] 115 authors also adopt a human-centric approach where 116 vocabularies of local motion and shape features are 117 combined with a voting approach. Liu et al. [START_REF] Liu | Recognizing realistic actions from 965 videos in the wild[END_REF] propose The weakly-supervised approaches by Ikizler et 129 al. [START_REF] Ikizler | Searching for complex human 952 activities with no visual examples[END_REF], [START_REF] Ikizler-Cinbis | Learning actions from 954 the web[END_REF] attempt to decrease the amount of super- human-object interactions in video [START_REF] Filipovych | Recognizing primitive interactions 936 by exploring actor-object states[END_REF], [START_REF] Filipovych | Robust sequence alignment for 938 Actor-Object interaction recognition: Discovering Actor-Object 939 states[END_REF], [START_REF] Gupta | Observing human-949 object interactions: Using spatial and functional compatibility for 950 recognition[END_REF], [START_REF] Matikainen | Representing 969 pairwise spatial and temporal relations for action recognition[END_REF], 137 [START_REF] Messing | Activity recognition using the 972 velocity histories of tracked keypoints[END_REF]. Messing et al. [START_REF] Messing | Activity recognition using the 972 velocity histories of tracked keypoints[END_REF] introduce a dataset of human- Ribeiro [START_REF] Filipovych | Recognizing primitive interactions 936 by exploring actor-object states[END_REF], [START_REF] Filipovych | Robust sequence alignment for 938 Actor-Object interaction recognition: Discovering Actor-Object 939 states[END_REF] model human-object interactions based on the trajectory and appearance of spatio-temporal interest points. Their approach is demonstrated in controlled videos taken by a static camera against a static, uniform background. Importantly, the scene is seen from the actor's viewpoint. This is substantially different from the type of video we consider.

Our work is also related to methods for modeling human-object interactions in static images [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF], [START_REF] Yao | Grouplet: A structured image representation 1005 for recognizing human and object interactions[END_REF], [START_REF] Yao | Modeling mutual context of object and 1007 human pose in human-object interaction activities[END_REF]. However, these approaches do not take advantage of motion characteristics of actions. Furthermore, [START_REF] Yao | Grouplet: A structured image representation 1005 for recognizing human and object interactions[END_REF] operates in a constrained setup where human location is given even at test time, and [START_REF] Yao | Modeling mutual context of object and 1007 human pose in human-object interaction activities[END_REF] expects the full human body pose to be always visible.

OVERVIEW OF OUR METHOD

In this section we present an overview of our approach to action recognition, based on explicitly modeling the human-object interaction (fig. 2). We summarize the stages of the pipelines for training the model for an action class (sec. 3.1) and for localizing it in space and time in a novel test video (sec. 3.2). TR1. We localize and track the humans in the training video. We first apply the human detector of [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF] independently on each frame and then link the resulting detections over time into tracks (sec. 4). For each annotation cuboid, we select the track which best overlaps with it and cut it to the precise temporal extent. This results in our set of positive human tracks. There is exactly one such track for each cuboid.

Training

Input

As the overall goal of our work is to learn the relative motion between humans and objects that is characteristic for the action class, we also need to track action-objects.

For each annotation cuboid, we track the object starting from the single annotated frame forward and backward in time until either end of the temporal extent of the cuboid (sec. 4). These form the positive object tracks (fig. 3, left). Again, there is exactly one such track for each cuboid. For each cuboid we now associate its human and object track into a positive human-object pair.

TRACKING HUMANS AND OBJECTS 259

Our approach for modeling human-object interactions We take a more general approach by employing the 283 generic part-based human detector presented in [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF]. In addition to being small, these objects present a high 293 degree of pose and appearance variability. For this task 294 we rely on the detection approach of Felzenswalb et 295 al. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], which demonstrated state-of-the-art results on 296 the PASCAL VOC object detection challenge [START_REF] Everingham | The PASCAL Visual Object Classes 923 Challenge 2007[END_REF]. We use

Tracking 301

Tracking is needed at various stages of our approach.

302

During training we need to track each action object 303 Fig. 4. The DPT-MS tracker at test time. In the first frame (left) the cup is automatically detected by an object detector. In the subsequent frames no detections are found on the cup. DPT-MS produces an object track (dashed window) by propagating the detection from the first frame according to point tracks (white segments). In the last frame (right) the cup is again detected. DPT-MS adds this detection to the track and uses it to update the confidence score, but not the location of the track.

starting from the initialization in a single annotated frame (TR1). This is a traditional tracking task [START_REF] Yang | Efficient mean-shift 1003 tracking via a new similarity measure[END_REF], [START_REF] Wu | Tracking with dynamic 1001 hidden-state shape models[END_REF], [START_REF] Grabner | Semi-supervised on-line 947 boosting for robust tracking[END_REF]. Furthermore, during TR1 we need to link over time human detections obtained automatically in individual frames. This is instead a tracking-by-detection task [START_REF] Breitenstein | Robust tracking-909 by-detection using a detector confidence particle filter[END_REF], [START_REF] Ferrari | Progressive 934 search space reduction for human pose estimation[END_REF], [START_REF] Kläser | Human 958 focused action localization in video[END_REF]. During testing (TE1) tracking-by-detection is needed again for both humans and objects (as at this point we have an object detector from TR2).

Previous works [START_REF] Breitenstein | Robust tracking-909 by-detection using a detector confidence particle filter[END_REF], [START_REF] Ferrari | Progressive 934 search space reduction for human pose estimation[END_REF], [START_REF] Kläser | Human 958 focused action localization in video[END_REF], [START_REF] Ramanan | Tracking people 981 by learning their appearance[END_REF] have been successful in tracking people in realistic videos by linking the output of a person detector run independently on each frame (tracking-by-detection). However, tracking small objects such as cups or cigarettes in this manner is much harder because detectors tend to miss the object in many frames. As a consequence, the object motion is typically broken into many short tracks. Furthermore, tracking-by-detection does not work when we do not have a detector yet, i.e. when the object to be tracked is given only as a bounding-box in a single frame. This corresponds to the traditional tracking scenario where the target is annotated in one frame [START_REF] Yang | Efficient mean-shift 1003 tracking via a new similarity measure[END_REF], [START_REF] Wu | Tracking with dynamic 1001 hidden-state shape models[END_REF], [START_REF] Grabner | Semi-supervised on-line 947 boosting for robust tracking[END_REF].

We propose here a general-purpose tracking method to robustly track multiple targets in an integrated manner that encompasses both the traditional tracking of a target annotated in one frame and the tracking-bydetection scenario. Inspired by [START_REF] Sivic | Person spotting: video 990 shot retrieval for face sets[END_REF], our algorithm takes as input any number of detection windows of the target, and propagates them forward and backward in time based on point-tracks. During this process, multiple windows that spatially meet in a frame are automatically merged in a single output track.

Our tracker, referred to by dense point tracks [START_REF] Sundaram | Dense point trajectories by 994 GPU-accelerated large displacement optical flow[END_REF] median shift (DPT-MS), works as follows:

1) Input. A sequence of frames {s, . . . , e} and a set of detections D i for each frame i ∈ {s, . . . , e}. At least one detection in one frame is required for the algorithm to run. If more are provided, the algorithm will try to link them over time (tracking-bydetection). Any in-between situation is supported, e.g. where some targets have a single initialization window and others have a sparse set of windows output by a detector. For producing point tracks we compute long-term point tracks using the code of [START_REF] Sundaram | Dense point trajectories by 994 GPU-accelerated large displacement optical flow[END_REF] over the entire sequence. object interactions [START_REF] Gupta | Observing human-949 object interactions: Using spatial and functional compatibility for 950 recognition[END_REF], [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF], [START_REF] Yao | Modeling mutual context of object and 1007 human pose in human-object interaction activities[END_REF], [START_REF] Yao | Grouplet: A structured image representation 1005 for recognizing human and object interactions[END_REF] have shown the

m(H t , O t ) = l(H t , O t ) -l(H t-1 , O t-1 ) (3

EXPERIMENTAL RESULTS

547

We present an evaluation of our method on two ex- The training annotations [START_REF] Laptev | Retrieving actions in movies[END_REF] come in the form of cuboids A which define the location in time and space of humans performing the action. For each training cuboid we complement these original annotations with a bounding-box delimiting the action-object in one frame.

Evaluating the DPT-MS tracker

In this section we evaluate our tracker presented in sec. 4. While tracking humans in the C&C dataset is quite easy [START_REF] Kläser | Human 958 focused action localization in video[END_REF], this dataset poses a serious challenge for tracking small objects such as cups and cigarettes which are central to recognizing actions. These objects are often very small, occluded by the person and in difficult lighting conditions.

We evaluate DPT-MS for tracking cup and cigarette objects in the training sequences for the drinking and smoking actions. We operate our tracker in a traditional scenario, where we use the object location annotated in one frame of every positive training clip as initialization (see sec. 3.1). We, then, have the tracker run through the temporal extent of the action (typically < 100 frames).

For evaluation only, we manually marked the ob- Results are presented in tab. 1 where we compare to three state-of-the-art techniques [START_REF] Grabner | On-line boosting and vision[END_REF], [START_REF] Grabner | Semi-supervised on-line 947 boosting for robust tracking[END_REF], [START_REF] Kalal | P-n learning: Bootstrapping 956 binary classifiers by structural constraints[END_REF]. Interestingly, DPT-MS outperforms the more complex approaches [START_REF] Grabner | On-line boosting and vision[END_REF], [START_REF] Grabner | Semi-supervised on-line 947 boosting for robust tracking[END_REF] on this dataset, although the approach of Kalal et al. [START_REF] Kalal | P-n learning: Bootstrapping 956 binary classifiers by structural constraints[END_REF] does even better. However, it is 627 important to note that, unlike [START_REF] Grabner | On-line boosting and vision[END_REF], [START_REF] Grabner | Semi-supervised on-line 947 boosting for robust tracking[END_REF], [START_REF] Kalal | P-n learning: Bootstrapping 956 binary classifiers by structural constraints[END_REF], DPT-MS is trained on the PASCAL 2007 VOC training set [START_REF] Everingham | The PASCAL Visual Object Classes 923 Challenge 2007[END_REF]; and

(ii) our detector [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF], which complements [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] with additional detectors specialized for the face and upper-body regions (sec. 4.1). We can observe that the combination of different human part detectors [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF] is beneficial on this difficult Coffee & Cigarettes dataset, improving over [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] by 7% AP.

The Tracks methods link the detections output by the corresponding detector using the tracker presented in sec. 4.2. For this evaluation, detections are first computed on each frame in a short temporal interval around a test image, and then linked using the tracker. However, evaluation is only done on the 137 test frames, as for the Single frames methods. The associated score is the one of the track, i.e., the average detection score over the track.

The Tracks methods outperform substantially both their corresponding single-frame methods, confirming the contribution of our DPT-MS tracker. The "Ours

Tracks" method gets +12% AP over the single-frame detector of [START_REF] Prest | Weakly supervised learning 979 of interactions between humans and objects[END_REF]. Moreover, it also achieves 9% higher AP than the human tracker of [START_REF] Kläser | Human 958 focused action localization in video[END_REF] (AP 52%). This is remarkable, as [START_REF] Kläser | Human 958 focused action localization in video[END_REF] was trained specifically on C&C, while our detector is trained using only external material ([32, sec. 2]).

Objects. We evaluate object detection performance on frames selected from the test part of C&C. We sample either one or two frames from every positive sample depending on its temporal length. This results in 54 frames for drinking and 47 for smoking. We also evaluate on negative images (i.e. not containing the object): for each class we select a number of negative images that reflects the proportion between positive and negative frames in the test set. This results in 500 negative images for drinking and 349 for smoking. As discussed in sec. 1. This explains the difference in recall for human tracks wrt figure 6, where the evaluation is performed on a different subset of C&C. 2. Our reimplementation of the 3DHOG-Track classifier achieves a slightly lower performance than the one reported by [START_REF] Kläser | Human 958 focused action localization in video[END_REF] (52/22 vs 54/25). This might be because [START_REF] Kläser | Human 958 focused action localization in video[END_REF] uses a finer temporal sliding window for the test tracks (7 scales vs our 3). Fig. 9. Drinking results. Human-object pairs localized in test videos. The ordering corresponds to the ranking of the combined action classifier. We also show the rank of the individual classifiers separately (I: interaction classifier, H: 3DHOGtrack classifier). These results show that the interaction and 3DHOG-track classifiers complement each other. Samples 13 and 14 have a relatively low 3DHOG-track score, whereas the interaction classifier successfully captures the discriminative motion of the object track. In contrast, for samples 2 and 4 the object track is incorrect, resulting in a lower interaction score rank, whereas the 3DHOG-track classifier correctly scores these samples highly. It is interesting, how our method finds object tracks also on unconventional objects such as the jug in samples 25 and 32, which receive top scores by the interaction classifier. For these examples 3DHOG-track fails due to the unusual object appearance. This confirms the ability of the interaction classifier to generalize the appearance of objects and describe their relative motion wrt to the human. Failure cases of the interaction classifier are often due to other objects moving in a similar way as action objects. For example in sample 30 the actor is pouring water from a teapot, resulting in a trajectory similar to the drinking action. For the 3DHOG-track classifier, a typical failure case is when low-level features perform poorly, as is the case in scenes with difficult lighting conditions, as in sample 14, or when the object has an unusual appearance, as in 25 and 32. Other failures by 3DHOG-track (classifying a negative as positive) are due to the actor being in a pose similar to the action, but not performing it, as in sample 12. Note that the interaction classifier receives a relatively low score as there is no motion. The performance obtained with our combined action classifier is on par with the result from [START_REF] Gupta | Observing human-949 object interactions: Using spatial and functional compatibility for 950 recognition[END_REF]. Note that [START_REF] Gupta | Observing human-949 object interactions: Using spatial and functional compatibility for 950 recognition[END_REF] explicitly takes advantage of the static camera and background used in these videos, rendering it unsuitable for more complex videos such as C&C.

Moreover, our method needs substantially less manual annotation for training than [START_REF] Gupta | Observing human-949 object interactions: Using spatial and functional compatibility for 950 recognition[END_REF], which requires the location of the person's hand and a pixelwise segmentation object, a feature which is not used here. Misclassifications between 'answering' and 'calling' are due to their similar motion. In the case of the combined classifier, there are only two misclassified samples, i.e, "light" is misclassified as "answer" and "pour" as "spray", see figure 11. These could probably be removed if colour information was used.

Multi-class classification on Rochester Daily Activities dataset

The Rochester Daily Activities [START_REF] Messing | Activity recognition using the 972 velocity histories of tracked keypoints[END_REF] dataset contains 10 activities of daily living recorded in a controlled environment with a static camera and background (fig. 13).

Each activity was performed three times by five persons, We report in tab. 5 also the performance of our full method using our combined action classifier (sec. 6). It is 3% higher compared to the full method of [START_REF] Messing | Activity recognition using the 972 velocity histories of tracked keypoints[END_REF], who also combines motion information with complementary contextual information.

CONCLUSION

This paper introduces an approach for learning human-

30 Finally,

 30 our technique takes advantage of the temporal 31 continuity in video to reduce the amount of supervision 32 needed to learn an appearance model of the action object 33 as well as the interaction model. As a result, it can be 34 trained with a modest amount of annotation: for each 35 video clip of the action class we only need a spatio-36 temporal cuboid on the person and a bounding-box on 37 the action object in one frame. aggregate differences between subsequent frames of an 97 action sequence resulting in a binary motion energy im-98 age. Temporal information is included through a motion 99 history image. The method proposed in [7] operates on 100 sports footage. They compensate camera movement by 101 tracking the person and calculate optical flow in person-102 centered tracks. In [41] a method based on particle 103 filtering is used for modeling crowd flow and detect 104 anomalies. 105 All of the above mentioned human-centric approaches 106 operate either with static cameras, i.e., human can be 107 located based on background subtraction, or with sim-108 ple backgrounds from which human can be extracted 109 easily, as for example football or ice hockey fields. More 110

  118 a combination of static and motion low-level features 119 and efficient techniques for mining the most discrim-120 inative ones in realistic youtube videos. The method 121 proposed in [23] localizes actions in space and time by 122 first extracting human tracks and then detecting specific 123 actions within the tracks using a sliding window clas-124 sifier. Actions are described by track-aligned 3D-HOG 125 features. These features are shown to be complementary 126 to our human-object interaction descriptors and are in-127 corporated in our final classifier.128

  130 vision necessary for training action classifiers. Training 131 videos for learning actions are obtained inexpensively 132 from YouTube [21]. Their approach is robust to the low-133 quality video as well as complex scenes necessary for 134 such video material. 135 Several works tackle the problem of recognizing 136

  138 object interactions recorded in controlled conditions and 139 propose a descriptor based on the velocity history of 140 tracked point features. Matikainen et al. [28] extends this 141 descriptor to include relations between pairs of tracked 142 points and quantize them into vocabularies. In contrast 143 with our work, both these approaches are based on low-144 level features to describe actions. The work most closely 145 related to ours is by Gupta et al. [19]. They model the 146 action object and the human-object motion for classifying 147 interactions between humans and objects. However, the 148 motion features used in their approach are more fragile: 149 they rely on hand trajectories to model how objects are 150 reached and grasped. In particular, the velocity profile 151 of the reaching hand and the time interval between a 152 reach and a grasp motion proved to be powerful features 153 in their experiments. Nevertheless, these fine-grained 154 features rely on motion extracted based on background 155 subtraction, which limits its applicability to static cam-156 eras and backgrounds (as opposed to uncontrolled video 157 such as feature films). Moreover, [19] requires substantial annotation effort for training, including the location of the person, of its hands, and a pixelwise segmentation of the action object in all video frames. Filipovych and

.

  In order to train the model for an action class, our method takes as input: (i) a long video including instances of the action class; (ii) spatio-temporal cuboids, constant in the spatial dimension. Each annotation cuboid defines the location in time and space of a human performing an instance of the action class; (iii) for each annotation cuboid, the location of the action-object is annotated in one frame within the temporal extent of the cuboid. In the following we describe each step of the training (TR) procedure, marked as TR1 -5.

Fig. 2 .

 2 Fig. 2. Overview of our method. We show the training pipeline (TR1 -5) and the test pipeline (TE1 -3). See text for details.

Fig. 3 .

 3 Fig. 3. Tracking at training and test time. (Left) The training stage TR1 tracks the annotated bounding-boxes (dashed yellow) throughout the temporal extent of the annotation cuboid (persons in green and objects in cyan). (Right) The test stage TE1 detects both humans and objects automatically and tracks them throughout the video. For illustration we show here only two object tracks, out of many more (a positive one covering the cup, and a negative one on the actor's face).

  260 depends on the availability of human and object tracks 261 in the same time period. For robustness, it is important 262 to ensure the highest possible recall for both human and 263 object tracks, as missing either of the two prevents the 264 system from recognizing the action. 265 It is an elusive goal to design robust detectors and 266 trackers to deal with difficult, small objects such as 267 cigarettes or cups. Instead, we propose a tracking-by-268 detection approach that can be run on top of weak 269 single-frame detectors, and produces a large number of 270 candidate tracks in order to miss as few positive tracks 271 as possible, see sec. 7.1.2 for an experimental evaluation. 272 Then, in sec. 5 we introduce a highly discriminative 273 descriptor that allows to mine for relevant human-object 274 track pairs out of this pool of candidates.

  Detecting humans in the C&C dataset is par-277 ticularly hard due to their variety of appearance, pose, 278 viewpoints and lighting conditions. The previous work 279 of Klaser et al. [23] used a human detector based on 280 HOG features [4] trained on C&C to learn the specific 281 features of this dataset.

  282

284

  This detector combines four part detectors dedicated to 285 different regions of the human body (including full-body, 286 upper-body, and face). It was trained from external still 287 images without using any C&C images [32, sec. 2]. Two 288 of the four components of this combined detector are 289 taken from the popular person detector of [10]. 290 Objects. Detecting small objects such as cups and 291 cigarettes is an even harder task than detecting humans.

  292

  297 the windows from the positive object tracks obtained in 298 TR2 as positive training data. As negative training data 299 we randomly sample windows from Caltech-101 [11].

  300

347 2 ) 3 ) 4 )

 234 Initialization. Let f be the first frame for which a 348 detection is available. For each detection D f j ∈ D f 349 create a new track T j , and add it to the overall track 350 set T . 351 Forward pass. Loop over frames i from f to e 352 a) Loop over tracks T j ∈ T 353 i) Update location. The position of T i+1 j of 354 track T j in frame i + 1 is the position 355 of T i j shifted by the median displacement 356 between frame i and i+1 of the point tracks 357 inside window T i j . 358 ii) Include a detection. If a detection D i+1 k Add new tracks. For each detection D i+1 k that 367 was not included into an existing track in step 368 3.(a).ii, we start a new track and add it to T . 369 Backward pass. Store away the current tracks. 370 Restart the process from step 2, this time over the 371 reversed sequence from f to s.

372 5 ) 6 )0 and 1 .

 561 Concatenate forward-backward tracks. Assemble the fi-373 nal tracks by concatenating the tracks from forward 374 pass to the (reverse) tracks from backward pass. 375 Confidence scores. The confidence of a track is the 376 average over the scores of the windows it contains, 377 where the windows scores are normalized between 378 Windows which are not supported by 379 any detection (see the two central images in fig. 4) 380 are given a score of 0, thus penalizing the overall 381 average.

  467 importance of limiting the spatial range of an action-468 object wrt a human. We learn the interaction range for 469 the relative location and relative area features. After the 470 training step TR1, we have a set of positive human-471 object track pairs. For each frame in every human-object 472 pair, we compute the two interaction features, see fig. 5 473 for their distribution. For each feature, we then select 474 the range of the feature such that 90% of the mass of the 475 distribution is contained in it. Note how this threshold 476 operates at a frame level thus discarding 10% of the 477 outlying mass of the distribution and preserving relevant 478 geometric information from the remaining frames. 479 Forming pairs. The ranges learned for the spatial in-480 teraction features are used to select spatially consistent 481 pairs from the set of temporally overlapping ones. Fig. 5 482 illustrates the feature distributions and learned ranges 483 for the drinking action from Coffee & Cigarettes.

484 5 . 3 Fig. 5 .

 535 Fig. 5. Learning the interaction ranges. Histograms of relative location and relative area accumulated over all positive training human-object pairs. In red are shown the learned ranges. The left plot shows that the location of the cup is typically in the middle of the human window along the horizontal axis and slightly above it along the vertical axis.

  ject bounding-box in each frame of the training clips (throughout the paper these annotations are never used for training). We count a bounding-box output by the tracker as a correct detection if it overlaps with the ground-truth object by more than 50%. We measure recall R as number of correct detections divided by the number of frames where the object is visible. All other tracker outputs are counted as false-positives. Precision P is the number of correct detection. The F-measure combines these two measures as F = 2P R/(P + R).

Fig. 6 .

 6 Fig. 6. Human detection performance. See text for details.

  628 specifically designed to handle both traditional tracking 629 (i.e. from a manual annotation in one frame) as well 630 as tracking-by-detection, which simultaneously tracks a 631 very large number of candidate windows. In sec. 7.1.2 632 we show that this is a crucial requirement for obtaining 633 a sufficient recall in detecting and tracking the object of 634 interest in the C&C dataset. 635 Finally, DPT-MS is computationally very efficient. 636 Computing the point tracks of [39] takes 2 seconds per 637 frame and represents nearly all the runtime of DPT-MS. 638 The rest of the procedure (sec. 4.2) tracks simultaneously 639 1000 candidate windows over two frames in only 10 640 milliseconds and it is linear in the number of windows. 641 In comparison, although [22] tracks one window over 642 two frames in 20 milliseconds, it would take 20 seconds 643 to track 1000 windows, making it impractical on a full-644 length movie such as the C&C dataset.

645 7 . 1 . 2 Fig. 7 .

 7127 Fig. 7. Object detection performance. See text for details.

Fig. 6

 6 Fig. 6 compares four methods. The two Single frames methods run a human detector on each test image independently: (i) the popular human detector of [10],

4 . 1 ,

 41 Fig.7compares the performance of the object detectors

  Fig.8shows precision-recall curves for drinking and 769

7 . 2

 72 Fig.11shows frames extracted from the Gupta video test 800

  827

Fig. 12 .Fig. 10 .

 1210 Fig. 12. Confusion matrices on the Gupta video dataset. (Left) performance of the interaction classifier; (Right) combined action classifier.

Fig. 11 .Fig. 13 .

 1113 Fig. 11. Human-object pairs localized on the Gupta video test set with the combined classifier. Every row shows one frame from each of the five test sequences of a class. Actions in this dataset follow precise motion patterns: each row displays samples selected to follow the temporal pattern. We also show one of the two misclassified samples, indicated with the incorrect class label overlaid.

Fig. 14 .

 14 Fig. 14. Confusion matrix on the Rochester Daily Activities dataset. Performance of the interaction classifier.

1 Interaction descriptor 421

	389	an illustration. Moreover, it can be used to track any
	390	object by providing a single initialization window in one
	391	frame, as the tracker updates the position of a window
	392	over time according to the median motion of its point
	393	tracks. Once a track is initialized, it does not require
	394	additional detections to survive, as opposed to [12],
	395	[23], [38]. Finally, note how DPT-MS tracks any number
	396	of detections in parallel without substantial increase in
	397	computation time.
	398	Robust point tracks. For obtaining point tracks in step
	399	1, we rely on the recent work on obtaining dense point
	400	trajectories [39] from large-displacement optical flow [3]
	401	(LDOF). LDOF is a variational technique that integrates
	402	discrete point matches, namely the midpoints of regions,
	403	into a continuous energy formulation. The energy is
	404	optimized by a coarse-to-fine scheme to estimate large
	405	displacements also for small scale structures. As opposed
		to traditional optical flow, the algorithm [39] tracks
	432
		l(H t , O t ) = ((O t x -H t x )/H t W , (O t y -H t y )/H t H ) (1)
	433	where subscripts indicate a window's center x, y,
		width W and height H.
		388

382

An important problem this tracker addresses is that 383 detectors of small objects such as cigarettes and cups 384 tend to produce sparse detections in time. As we ob-385 served in Coffee & Cigarettes, it is common to have 386 tens of frames without detecting the object. DPT-MS 387 links detections even in this situation, see figure 4 for 406 points over multiple frames, not only over two. 407 5 MODELING HUMAN-OBJECT INTERACTIONS 408 In this section we model the interaction between a 409 human track H and an object track O in terms of relative 410 position and motion features (stages TR4 and TE3).

411 These features are computed for a human-object track 412 pair, which have been formed before. Positive human-413 object pairs are formed easily at training time, as there is 414 only one possible pair for each annotation cuboid (TR1). 415 Instead, forming negative training pairs, and all pairs 416 at test time, requires a dedicated procedure which we 417 describe in sec. 5.2. In sec. 5.1 we start by presenting 418 our interaction descriptor, which we compute for any 419 human-object pair.

420

5.

In the following we describe the relative location, area 422 and motion of the object track wrt the human track in 423 the time interval [t min , t max ] in which they both exist (i.e. 424 the intersection of their temporal extents). Note that both 425 H and O have a window H t and O t in every frame t ∈ 426 [t min , t max ], as our tracker never skips a frame (sec. 4.2). 427 At every frame t in the interval [t min , t max ] we com-428 pute three features: 429 1) Relative location. The relative location l(H t , O t ) of 430 the object window O t wrt to the human window 431 H t in frame t 434 2) Relative area. The area of O t relative to H t 435 a(H t , O t ) = area(H t )/area(O t )

(2)

3) Relative motion. The relative motion of the object wrt 436 to the human is an important cue for distinguishing 437 actions. We define this as the 2D vector 438

  We represent this vector by its magnitude

	441
	442	and direction.
	443	We compute an interaction feature at every frame of
	444	a human-object pair and then aggregate them into a
	445	single descriptor of fixed dimensionality as follows. For
	446	each feature we accumulate its values over the time
	447	interval in a histogram. We independently L1-normalize
	448	each histogram and then concatenate them to obtain the
	449	final interaction descriptor. The 2D relative location and
	450	relative motion cues are quantized into 16-dimensional
	451	histograms each and relative area is quantized into 4
	452	dimensions. This results in a total of 36 dimensions.
	453	Interestingly, we did not observe any improvement by
		using a higher dimensionality.

) the difference between the relative location 439 l(H t , O t ) in frame t and l(H t-1 , O t-1 ) in frame 440 t -1. 454 5.2 Forming human-object pairs 455 We describe here how to associate human and object 456 tracks when collecting negative human-object pairs dur-457 ing training (stage TR3) and when forming pairs during 458 testing (stage TE2). A simple approach would be to take 459 all temporally overlapping pairs of human and object 460 tracks. However, this would lead to a huge number of 461 pairs, which would make action detection very slow. 462 Instead, we perform here a preselection stage, where we 463 associate pairs based on two interaction features from 464 sec. 5.1. 465 Learning interaction ranges. Previous works on human-466

TABLE 1 Evaluation of our DPT-MS tracker. We

 1

	compare to other

Ours Tracks (61) Ours Single Frames (49) Felzenszwalb et al. Tracks (50) Felzenszwalb et al. Single Frames (42)

TABLE 2

 2 Number of tracks and recall (in parentheses) for humans H, objects O and human-object pairs (H, O) on the Coffee & Cigarettes test set.

	705	on the test part of the dataset in the Single Frames and
	706	the Tracks modes. The Tracks mode, although introducing
	707	some additional false-positives, doubles the maximum
	708	recall compared to the Single Frames mode, and detects
	709	more than 90% of all object instances. This fits the goal
	710	stated at the beginning of sec. 4: to produce a pool of can-
	711	didate tracks which misses as few true object instances
	712	as possible. The lower performance of the Tracks method
	713	in terms of Average Precision is inherent to the context
	714	we operate in: we deal with detections which are sparse
	715	in time (typically less than 30% of a positive track's
	716	frames are supported by a detection) and every frame
		where a detection is missing penalizes the overall score
	723
	724	We stress that object detection and tracking in this
	725	dataset is very difficult due to the highly cluttered
	726	scenes, varying lighting conditions, and especially the
	727	small size of the objects. In fact 76% of the objects cover
		less than 1.5% of the image surface.
	729
	730	with our human-object interaction model, the human
	731	as well as the object track need to be present. To miss
	732	as few as possible human-object pairs performing the
	733	action, we keep all human and object tracks, i.e., we
	734	operate at the maximum recall level, see the right-most
	735	datapoints in fig. 6 and 7. The corresponding numbers
	736	are reported in tab. 2. Note that the number of tracks
	737	and the recall are reported for the final test datasets, i.e.,
	738	the two and three short stories used to evaluate drinking
	739	and smoking localization. 1
	740	Given this set of human and object tracks, we form
	741	human-object pairs based on the approach described in
	742	sec. 5.2, i.e., use preselection based on relative location
	743	and area. This results in 418980 track pairs and a recall
	744	of 90% for drinking and 1619284 track pairs and a recall
	745	of 89% for smoking, see last row of table 2. This shows
	746	that the recall is sufficiently high, to make localization
	747	of most action instances possible.
	748	This is not the case, if we keep only the 50% highest
	749	scoring human and object tracks, i.e., the overall number

717

of the track. As a result, the average track score loses 718 significance. The track score could certainly be made 719 more robust to outliers, but this was not necessary in 720 our context, which requires maximum recall. Note also 721 that this is not a problem when a reliable detector is 722 available, as is the case for human detection (fig.

6

).

728

Human-object pairs. In order to localize an action

TABLE 4 Average classification accuracy on the Gupta video dataset.

 4

TABLE 5 Average classification accuracy on the Rochester Daily Activities dataset.

 5

 [START_REF] Laptev | Retrieving actions in movies[END_REF]43 -Willems et al. [START_REF] Willems | Exemplar-996 based action recognition in video[END_REF] 45 -Klaeser et al. [START_REF] Kläser | Human 958 focused action localization in video[END_REF] 54 25 TABLE 3 Average precision for spatio-temporal localization on C&C. First three rows: our individual classifiers. Fourth row: our full method combing the three classifiers. Last three rows: competing methods ( [START_REF] Laptev | Retrieving actions in movies[END_REF], [START_REF] Willems | Exemplar-996 based action recognition in video[END_REF] do not report AP for smoking).

of human-object pairs is reduced by approximatively a 750 factor four and recall drops to 43% respectively 39% for 751 drinking and smoking.

752

In the next section we will show that our interaction For each method we present its average precision (AP) in parenthesis.

Evaluating action detection (localization in space