Boisbunon Aurélie

✶❀✷❀✄

Flamary Rémi

Alain Rakotomamonjy ✸❀②

Alain ✹❀③

Giros

Josiane Zerubia

✷ ✶ Cnes

LARGE SCALE SPARSE OPTIMIZATION FOR OBJECT DETECTION IN HIGH RESOLUTION IMAGES

Keywords: Object detection, sparsity, active set, unsupervised learning, image processing

In this work, we address the problem of detecting objects in images by expressing the image as convolutions between activation matrices and dictionary atoms. The activation matrices are estimated through sparse optimization and correspond to the position of the objects. In particular, we propose an efficient algorithm based on an active set strategy that is easily scalable and can be computed in parallel. We apply it to a toy image and a satellite image where the aim is to detect all the boats in a harbor. These results show the benefit of using nonconvex penalties, such as the log-sum penalty, over the convex ❵ ✶ penalty.

INTRODUCTION

We address the problem of object detection in high resolution images with the hypotheses that, in such images, our object of interest can be approximated by a simple shape. In addition, the number of objects in the image is unknown, but typically reaches several hundreds or thousands. This problem is also known as monitoring in the remote sensing community and, in particular, we are interested in the special case of boat detection in harbors on satellite images. Images provided by Pleiades satellites are typically of size ✹✷✵✵✵ ✂ ✹✷✵✵✵ px for several gigabytes in memory.

In this setting, marked point processes (MPP) are a useful model of unsupervised learning for getting a refined configuration of the objects. MPPs are point processes where the position of objects is augmented by their shape, called the mark. The associated method consists in modeling the distribution of the configuration in order to estimate both the position and the shape parameters of the objects [see e.g. 1]. In [START_REF] Ben Hadj | Parameter estimation for a marked point process within a framework of multidimensional shape extraction from remote sensing images[END_REF] and references therein, the probability of the configuration ❈, given ✄ The first author would like to thank the French Spatial Agency (CNES) for the financial support of her post-doc at INRIA.

② RF acknowledges support of CNRS MASTODONS project DIS-PLAY. ③ AR acknowlegdes support form grant ANR GRETA 12-BS02-004.

an image ( is defined by a Gibbs distribution taking into account both the image and prior information:

P ✒ ❬❈•(( ❂ ❝ ✶ ✌ ❡①♣❢ ✌❯ ❞ ✭❈❀ (✮✰❯ ♦ ✭❈✮ ✰ ❯ ❛ ✭❈✮❣❀ (1)
where ✌ is the parameter weighting the data and prior terms, ❝ ✌ is the normalizing constant, the data term ❯ ❞ ✭❈❀ (✮ is based on the contrast between the objects and their neighborhoods, and the prior terms ❯ ♦ ✭❈✮ and ❯ ❛ ✭❈✮ respectively model the overlapping and alignment between objects, (see Figure 1). The aim is to estimate both the configuration ❈ and the parameter ✌ based on the image (. The procedure for building MPPs consists in first initializing and estimating ✌, which is currently performed from the null configuration and the Stochastic Expectation-Maximization (SEM) algorithm [START_REF] Celeux | The SEM algorithm: a probabilistic teacher algorithm derived from the EM algorithm for the mixture problem[END_REF], and then extracting the objects by simulated annealing [see 4, Chapter 7 and references therein]. However, the price to pay to get a fine extraction is a large computational time. Indeed, in practice, it already takes several minutes for an image of size ✷✼✺ ✂ ✸✽✺ px [START_REF] Boisbunon | Estimation of the weight parameter with SAEM for marked point processes applied to object detection[END_REF]. It would thus take a very long time to run it on full Pleiades images. The computational cost of MPPs could be greatly reduced if it started with a coarse initial configuration instead of the empty one. This is the reason why, in this work, we consider a different approach for the initialization of the configuration. This approach consists in representing the image as a sum of convolutions between a small image with one single object and a highly sparse matrix with non-zero entries corresponding to Dirac delta functions defining the positions of objects. Our approach thus relies on two main components: first, the construction of a dictionary containing representative instances of a proxy of the object with different rotations and scales; then, the determination of the non-zero entries of the matrix associated with each dictionary element. This latter component is based on sparse optimization problems, with e.g. an ❵ ✶ [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF] or a log-sum penalty [START_REF] Candes | Enhancing sparsity by reweighted ❵ ✶ minimization[END_REF]. The complexity of the problem is linear with the number of pixels in the image multiplied by the number of atoms in the dictionary, which can be very large even for medium-size images. Hence, we propose to use an active set algorithm in order to solve efficiently this Fig. 1. Representations of the data (left), overlapping (middle) and alignment (right) terms used in the MPP model [START_REF] Van Lieshout | Markov Point Processes And Their Applications[END_REF]. problem, in a similar fashion as in [START_REF] Boisbunon | Active set strategy for high-dimensional non-convex sparse optimization problems[END_REF]. The problem we address bears resemblance to the convolutive non-negative matrix factorization as described in [START_REF] Smaragdis | Convolutive speech bases and their application to supervised speech separation[END_REF][START_REF] Grady | Convolutive nonnegative matrix factorisation with sparseness constraint[END_REF]. The main difference is that, in this work, we essentially focus on the sparse approximation stage and on devising an algorithm able to recover very efficiently in a very high-dimensional setting the few active variables.

The remainder of the paper is organized as follows. Section 2 exposes the methods currently used for initialization and estimation of the parameter of the MPP model. Section 3 presents our approach based on the resolution of sparse optimization problems and the efficient active set algorithm proposed for solving it. In Section 4, we compare the performances of two penalties, namely the ❵ ✶ and the log-sum penalties, on a toy image, and we show how the algorithm can be used as an initial configuration for a finer method, such as MPPs, on a real satellite image. Finally, we present some perspectives of future work in Section 5.

CONTEXT AND BACKGROUND

The difficulty of estimating the parameter ✌ in (1) comes from two facts: first, the setting is unsupervised, so that the unknowns are both the configuration ❈ and the parameter ✌; second, the normalizing constant ❝ ✌ itself depends on the parameter ✌, resulting in a difficult optimization problem. In this section, we briefly introduce the methods currently used for the initialization and the estimation of ✌. We refer the reader to [START_REF] Ben Hadj | Parameter estimation for a marked point process within a framework of multidimensional shape extraction from remote sensing images[END_REF][START_REF] Boisbunon | Estimation of the weight parameter with SAEM for marked point processes applied to object detection[END_REF] and references therein for more details.

Initialization of MPP

In [START_REF] Descombes | Stochastic geometry for image analysis[END_REF]Chapter 7], the initialization is performed as follows.

First, a manual over-estimate ☞ ✵ of the number of objects in the image is required. This over-estimate can be taken for instance as the maximum number of average-size objects that could fit in a rectangle of the size of the image. Then, the tradeoff parameter ✌ is obtained by taking the root of the function

☞ ✵ ✰ ) ❑ ☞ ❡①♣❢ ✌❯ ❞ ✭✉✮❣✄✭❞✉✮❀
where ✄✭✁✮ is the intensity distribution of a Poisson process, ❑ is the compact space corresponding to the image, and the integral corresponds to the average number of objects with re-spect to a Papangelou conditional intensity for an empty configuration ❈ ❂ ❀.

Estimation of the tradeoff parameter

One way to overcome the complexity of the inference problem in unsupervised setting is to use the Stochastic Expectation-Maximization (SEM) algorithm [START_REF] Celeux | The SEM algorithm: a probabilistic teacher algorithm derived from the EM algorithm for the mixture problem[END_REF], and to replace the likelihood (1) by the pseudo-likelihood [START_REF] Besag | Statistical analysis of non-lattice data[END_REF] considering independance between the objects. Starting from an initial value ) ✌ ✭✵✮ , the algorithm alternates between approximating the expected likelihood based on a simulated configuration ❈ ✭❦✮ for fixed ❜ ✌ ✭❦✮ , and updating the parameter ❜ ✌ ✭❦✰✶✮ from Maximum of Pseudo-Likelihood [START_REF] Ben Hadj | Parameter estimation for a marked point process within a framework of multidimensional shape extraction from remote sensing images[END_REF]. The main issue of the SEM algorithm is that it is quite long to converge. A slightly faster estimation can be obtained by Stochastic Approximation EM (SAEM) algorithm [START_REF] Delyon | Convergence of a stochastic approximation version of the EM algorithm[END_REF], which takes into account all the simulated configurations in the approximation of the expected pseudo-likelihood. Even so, the estimation step is still long to compute in practice [START_REF] Boisbunon | Estimation of the weight parameter with SAEM for marked point processes applied to object detection[END_REF].

SPARSE OPTIMIZATION FOR OBJECT DETECTION

In this work, we consider a completely different approach for initializing the configuration. We believe it will considerably speed up the estimation step, since it can be started from a good coarse configuration instead of the empty one.

The general idea of our approach is to consider the image as the sum of convolutions of dictionary elements, representing each instance of the object, with Dirac delta functions on the position of the objects in the image. This actually corresponds to a sparse linear optimization problem, since we are looking for the highly sparse matrix of positions. In the following paragraphs, we first explain the main idea into more details, then we expose our algorithm and, finally, we discuss some techniques to use it in very high dimensions.

Optimization problem

We first assume that we have a dictionary with atoms ❉ ❦ , ❦ ❂ ✶❀ ✿ ✿ ✿ ❀ ❑, of size ❞ ✂ ❞ corresponding to a proxy of the object with different shapes. For an input image ( of size ♥ ✂ ♠, the problem can be stated as

♠✐♥ ❳✷| ♥✂♠✂❑ ✰ ❦( ❑ ❳ ❦❂✶ ❳ ❦ ✄ ❉ ❦ ❦ ✷ ❋ ✰ ✕✡✭❳✮❀ (2)
where ❳ ❦ is the activation matrix of size ♥✂♠ corresponding to element ❉ ❦ of the dictionary, ✄ is the convolution operation with zero-padding and conservation of the size of ❳ ❦ , ❦✁❦ ❋ is the Frobenius norm, ✡✭✁✮ is a penalty function, and ✕ is the tradeoff between goodness of fit and penalization. This representation is illustrated in Figure 2. Note that the regularization term ✡✭✁✮ should promote sparsity in the activation coefficients in ❳, since these coefficients correspond to the position of the objects on the image. The construction of the dictionary will be discussed in Section 4.

Problem in (2) can be rewritten in the following way:

♠✐♥ ①✕✵ ❦② ❋①❦ ✷ ✷ ✰ ✕✡✭①✮❀ (3)
where ② is the vectorized image of length ♥♠, ① contains all the vectorized activation matrices ❳ ❦ , ❦ ❂ ✶❀ ✿ ✿ ✿ ❀ ❑, concatenated in one single vector of size ♥♠❑ and ❋ is a block Toeplitz matrix that corresponds to the convolution, as displayed in Figure 3. In this work, we choose to regularize ① with a component-wise sparsity promoting term such as an ❵ ✶ -norm [6], corresponding to ✡✭①✮ ❂ ❦①❦ ✶ , or a more aggressive non-convex regularization term such as the log-sum

penalty ✡✭①✮ ❂ P ♥♠❑ ✐❂✶ •♦❣✭✶ ✰ •① ✐ •❂✒✮ [7].

2D active set algorithm

One particularity of problem in (2) is that it is both high dimensional and extremely sparse. For instance, for an image of size ✶✵✷✹ ✂ ✶✵✷✹ with ✶✺ dictionary elements, and containing several hundreds of objects, say ◆ , we need to recover only ◆ non-zero entries in ❳ ❦ out of ✶✺ million components.

Therefore, it is crucial to use a very efficient algorithm that takes this extreme sparsity into account in order to obtain the solution in reasonable time.

In [START_REF] Boisbunon | Active set strategy for high-dimensional non-convex sparse optimization problems[END_REF], the authors considered an active set algorithm for solving extremely sparse nonconvex optimization problems. Their approach is of particular interest in our case as it allows the use of nonconvex regularization terms that improve sparsity. The main idea behind an active set is to iteratively solve the problem on a small subset of active variables. The subset of variables is updated at each iteration by adding the variable that most violates the optimality conditions. We propose to adapt this algorithm to the context of image processing as shown in Algorithm 1. First we want to emphasize that we can take advantage of the convolution in order to have efficient computations of correlations (Line 3 in the algorithm). The inner problem (Line 6) is solved on a restricted number of active positions and with a sparse matrix ❋ containing in each column (im dic✭✐❀ •❀ ❉ ❝ ✮), a vectorized sparse image with a unique dictionary element at position ✭✐❀ •✮ in the image. As in [START_REF] Boisbunon | Active set strategy for high-dimensional non-convex sparse optimization problems[END_REF], the inner problem is solved by using a proximal gradient descent method, such as FISTA [START_REF] Beck | A fast iterative shrinkagethresholding algorithm for linear inverse problems[END_REF] for the ❵ ✶ -penalty and GIST [START_REF] Gong | A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems[END_REF] for non-convex ones. Next, we discuss several strategies that have been performed in order to scale the proposed algorithm to extremely large scale optimization.

Strategies for large scale optimization

First, step 3 in Algorithm 1 consists in computing a 2D intercorrelation between the residue | and each of the dictionary elements ❉ ❦ . This step requires ♠♥❞ ✷ operations for dictionary elements of size ❞ ✂ ❞ if performed directly or

✷♠ •♦❣ ✷ ✭♠✮♥ •♦❣ ✷ ✭♥✮ if performed
in the Fourier domain. In our applications, objects are typically small with respect to the image and a direct computation leads to a computational complexity linear in the number of pixels in the image. Moreover, this step is a typical case of embarrassingly parallel computation as the correlations can be computed in parallel for each dictionary element.

Second, we use in the algorithm what is known as a warmstarting trick: the solution at a given iteration is given as initialization of the inner problem (line 6) for the following iteration. The inner solver being implemented by a gradient descent, the algorithm converges in a few iterations to the new solution. Another trick that allows faster convergence is to add multiple variables to the active set at each iteration. When the number of objects in the image is important, an active set algorithm requires a lot of iterations. When the variables are added by batch, lines 4-5 are executed several times before solving the problem line 6. Hence, the final number of active set iterations can be greatly decreased as discussed in [START_REF] Boisbunon | Active set strategy for high-dimensional non-convex sparse optimization problems[END_REF].

Finally we propose to use the structure of the image model and the fact that the objects are of limited size to further improve speed through a parallel version of the optimization (line 6). First, one can see from the left part of Figure 4 that, when new active variables are added (in red) to the optimization problem, the corresponding objects have a limited impact on the objects located far outside a certain range. This suggests that the re-optimization at line 6 of the algorithm can be exactly solved only on a subset of the current active variables, leading to a significant decrease in computational cost. The subset of parameters to be re-optimized can be obtained simply by using an efficient algorithm on the connected component graph of the objects as described in [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF]. An additional benefit of this approach is that all the connected components in the graph (black clusters illustrated in the right part of Figure 4), can be solved independently, allowing a parallel implementation of the re-optimization line 6 in the algorithm.

NUMERICAL EXPERIMENTS

Generated images

In this paragraph, we compare the performances of the ❵ ✶ and the log-sum penalties for a detection task in a toy image where we know exactly the position and shape of the objects. The aim is to investigate the benefit of non-convex penalties over convex ones.

The study was driven as follows. First, we built the dictionary from 15 rotations of a truncated 2D-Gaussian distribution, as displayed in the top-right part of Figure 2. Then, we created a ✶✵✷✹ ✂ ✶✵✷✹ image by placing randomly over the image 10 objects per atom of the dictionary, and we added a Gaussian noise with variance ✛ ✷ ❂ ✿✵✺. One example of generated image is displayed in Figure 5 and contains 150 objects.

We run the algorithm 2D-SO (see Algorithm 1) with the ❵ ✶ and the log-sum penalties and computed four measures of performance along the regularization path (for a varying ✕).

The first three measures are based on the F-score, defined by F-score ❂ ✷❚P ✷❚P ✰ ❋P ✰ ❋◆ ❀ where ❚P (true positive) is the number of pixels correctly estimated as part of an object, ❋P (false positive) is the number of pixels that have been incorrectly estimated as part of an object, and ❋◆ (false negative) is the number of pixels that have been incorrectly estimated as part of the background. The Fscore thus gives an estimation of the detection rate: the closer to 1, the better the detection is. We computed the F-score on three different matrices: first, for the full image, measuring the overlap between the binary result image and the ground truth; then on the true and reconstructed ❳ which measures how well are estimated both position and shape of the objects; and finally, for the position only, thus measuring how well the position of the objects can be recovered, regardless of which dictionary atom is activated. We also computed a fourth measure of quality, namely the mean-squared error between the true matrix of activation and the estimated one.

Figure 6 shows the evolution of these four measures as a function of the number of activated objects when varying the regularization parameter ✕. The results are averaged over 20 draws. First, note that, between 90 and 170 objects activated, the performances of the log-sum penalty are better than that of the ❵ ✶ penalty, whatever the measure. Outside that range, it has equivalent or lower performances. Also, the best F-scores (closest to 1) and MSE (closest to 0) of the log-sum penalty are obtained for 150 activated objects in average, which is exactly the number of objects in the toy image. On the other hand, for the ❵ ✶ penalty, the best results are obtained between 200 and 270 objects. These results highlight, in the detection problem, the well known issue of the ❵ ✶ penalty's bias, resulting in poor performances for a small number of objects detected and in good performances when the bias is decreased, that is, when more objects are activated. Finally, the performances in F-score for the full image and for the positions are very good, close to one at the optimum, which means that both penalties are able to recover the right position of the objects and a shape at least close to the true one. However, the results in terms of F-score for both the position and the shape are less satisfactory and seem to show a difficulty of the algorithm to detect the correct rotation for a given position.

In order to illustrate the temporal complexity of our approach, we ran the algorithm on a ✹✵✾✻ ✂ ✹✵✾✻ image containing ✹✽✵ objects. The optimization with LSP regularization took ✻✿✵ min on a computer with 30GB RAM for estimating a sparse vector of size 2.51✂✶✵ ✽ .

Boat detection on real images

In this paragraph, we apply our algorithm to the problem of boat detection in satellite images of harbors. The original image is part of a satellite image, of size ✷✼✺ ✂ ✸✽✺. As the objects all have the same orientation, we fixed it to ✵✿✻✙, both in the MPP model and in 2D-SO. Also, in the MPP model, boats are approximated by ellipses. Hence, we generated a dictionary of binary ellipses with different scaling so as to better fit the discrepancy in boat size.

In order to compare the performances between the ❵ ✶ and the log-sum penalties, we tuned the penalty tradeoff parameter ✕ in (2) so as to activate a similar number of objects, as shown in Table 1. The table also shows the number of non-overlapping objects obtained after a post-processing step keeping the boats with highest activation coefficient, the Fscore for the full image compared to a ground truth, the number of steps for the algorithm to reach convergence, and the computation time. For a similar number of objects, it is clear that LSP is more accurate as it has less overlapping objects and a better F-score than the ❵ ✶ penalty. It still misses some objects, the correct number being 615, but the computation time is very good and promising. Figure 7 displays the configurations obtained from the estimation step with SAEM (top right), and from the 2D-SO algorithm with the ❵ ✶ and the log-sum penalties (top row).

For 2D-SO, the images displayed result from after a postprocessing step removing overlapping objects where we keep the objects having the biggest activation coefficient. From this figure, it appears that the detection with the ❵ ✶ penalty is not as good as the one with LSP, since it has many spaces where no objects were detected or many objects still overlap. This suggests that running SAEM from an initial configuration obtained with 2D-SO instead of the null configuration might speed up the estimation step and improve the quality of the estimation, which is confirmed by the results in Table 2. Indeed, the estimation step is performed almost twice faster, while the gain in detection rate is of more than ✸✪. The big difference of computation time between MPP and 2D-SO is mainly due to the fact that MPP tests for many small random perturbations of the objects' shape to find the one that best fits the image. Hence, it results in a fine estimation of the parameters of each ellipse. Note that the detection rate is lower at the end of MPP than at the end of our algorithm. This is a side effect of the parametrization of MPPs fixing the maximum size of the boats, which can still be optimized. Indeed, the MPP program removes the larger boats, while it greatly improves the shape of the smaller boats (see bottom images of Figure 7).

CONCLUSION AND FUTURE WORKS

In this work, we presented an original way of treating the problem of detecting objects in an image as a sparse optimization problem. We proposed an efficient algorithm based on an active set strategy that is able to solve the problem in millions of dimensions. The numerical study confirmed that nonconvex penalties result in a more aggressive sparsity and a more accurate detection, and should be preferred over the ❵ ✶ penalty. The next step of our work is to test the scalability of our method on larger images, and its performances on other types of images, such as astronomical or medical images.In the longer-term, we intend to work on the refinement of the dictionary. Several options seem interesting: an interpolation or a vote to select between different atoms for overlapping objects, which can also be done automatically with the Elitist Lasso [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signal models with dependent coefficients[END_REF]; and finally, dictionary learning, where both the dictionary and the activations are estimated simultaneously.

Fig. 2 .

 2 Fig. 2. Representation of an image as a sum of convolutions of activation matrices with elements of the dictionary.

Fig. 3 .

 3 Fig. 3. The matrix ❋ is formed by concatenation of ❑ Toeplitz matrices where each column corresponds to the vectorized atoms ❉ ❦ at one possible location in the vectorized image. Here, we only show a simple example for an image of size ✺ ✂ ✶ with one atom.

Algorithm 1 4 :

 14 2D-sparse optimization (2D-SO) -Input: (, ✭❉ ❦ ✮ ❑ ❦❂✶ -Init.: ⑦ ( ❂ ✵ (reconstructed image) ❋ ❂ ❬ ( (active elements) corr2✭|❀ ❉ ❦ ✮ % Correlation ✽❦ ✐❀ •❀ ❝ ✥ ❛r❣ ♠❛① ✐❀•❀❝ ❈ ✐❀•❀❝ 5: ❋ ✥ ❬❋ im dic✭✐❀ •❀ ❉ ❝ ✮( % add new active element 6: ① ✥ Solve Problem (3) with current active elements ❋ 7: ⑦ ( ✥ reshape✭❋①✮ % Update reconstructed image 8: until stopping criterion is met

Fig. 4 .

 4 Fig. 4. Illustration of the impact of new added objects in a current active set of objects (left). Only a subset of the active variables has to be updated (in green) and this update can be performed in parallel for several connected component clusters (right).

Fig. 5 .

 5 Fig. 5. ✶✵✷✹ ✂ ✶✵✷✹ noisy toy image (left), and zoom (right).

Fig. 6 .

 6 Fig. 6. Comparisons of performance of the ❵ ✶ (dashed line) and the log-sum (solid line) penalties, in F-score for the full image (top left), for the positions and shapes (top right), for the positions only (bottom left), and in MSE (bottom right), averaged over 20 draws.

2DFig. 7 .

 7 Fig. 7. Detail of the configurations obtained from 2D-SO with ❵ ✶ penalty after post-processing (2D-SO-❵ ✶ ), and from 2D-SO with log-sum penalty after post-processing (2D-SO-LSP), from MPP with null configuration (NC-SAEM) and from MPP initialized with the results of 2D-SO-LSP (2D-SO-SAEM). Best seen in color.

Table 1 .

 1 Comparison between ❵ ✶ and log-sum penalties for a

			❵ ✶ LSP
	Activated objects	712 713
	Non-overlap. objects 424 489
	F-score (image)	0.71 0.77
	Steps		77	78
	Time (sec)	8.8 11.7
	dictionary with 6 scales.
	Method	Final F-score Estimation time (min.)
	NC-SEM NC-SAEM 2D-SO-SAEM ✼✸✿✻✼ ✭✵✿✾✾✮ ✼✵✿✹✷ ✭✶✿✷✵✮ ✼✵✿✶✹ ✭✵✿✾✾✮		✽✿✶✾ ✭✷✿✵✶✮ ✼✿✸✶ ✭✷✿✺✷✮ ✹✿✷✹ ✭✶✿✸✺✮

Table 2 .

 2 Comparison of performances in F-score for the image and in computational time of the estimation step when MPPs are initialized with the null configuration (NC) and with our algorithm (2D-SO). The results are given in average over 50 examples with standard deviations given in parenthesis.


David F Fouhey
email: dfouhey@cs.cmu.edu

Vincent Delaitre

Abhinav Gupta

Alexei A Efros

Ivan Laptev

Josef Sivic

Human Actions as a Cue for Single View Geometry

Keywords: Scene understanding, action recognition, 3D reconstruction

We present an approach which exploits the coupling between human actions and scene geometry to use human pose as a cue for single-view 3D scene understanding. Our method builds upon recent advances in still-image pose estimation to extract functional and geometric constraints on the scene. These constraints are then used to improve single-view 3D scene understanding approaches. The proposed method is validated on monocular time-lapse sequences from YouTube and still images of indoor scenes gathered from the Internet. We demonstrate that observing people performing different actions can significantly improve estimates of 3D scene geometry.

Introduction

The human body is a powerful and versatile visual communication device. For example, pantomime artists can convey elaborate storylines completely non-verbally and without props, simply with body language. Indeed, body pose, gestures, facial expressions, and eye movements are all known to communicate a wealth of information about a person, including physical and mental state, intentions, reactions, etc. But more than that, observing a person can inform us about the surrounding environment with which the person interacts.

Consider the two people detections depicted in Figure 1. Can you tell which one of the three scenes these detections came from? Most people can easily see that it is room A. Even though this is only a static image, the actions and poses of the disembodied figures reveal a lot about the geometric structure of the scene. The pose of the left figure reveals a horizontal surface right under its pelvis ending abruptly at its knees. The right figure's pose reveals a ground plane under its feet as well as a likely horizontal surface near the hand location. In both cases we observe a strong physical and functional coupling between people and the 3D geometry of the scene. In this work, we aim to exploit this coupling.

This paper proposes to use human pose as a cue for 3D scene understanding. Given a set of one or more images from a static camera, the idea is to treat each person as an "active sensor," or probe that interacts with the environment and in so doing carves out the 3D free-space in the scene. We reason about human poses following J.J. Gibson's notion of affordances [START_REF] Gibson | The ecological approach to visual perception[END_REF] -each pose is associated with the local geometry that permits or affords it. This way, multiple poses in space and time can jointly discover the underlying 3D structure of the scene.

In practice, of course, implementing this simple and elegant scenario would be problematic. First of all, the underlying assumption that the humans densely explore the entire observed 3D scene is not realistic: in many scenes, humans may not interact with certain regions for months. But more problematic is the need to recover high-quality 3D pose information for all people in an image. While several very promising 2D pose estimation approaches exist [START_REF] Andriluka | Pictorial structures revisited: People detection and articulated pose estimation[END_REF][START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF][START_REF] Yang | Articulated pose estimation using flexible mixtures of parts[END_REF], and while it is possible to use anthropometric constraints to lift the poses into 3D [START_REF] Taylor | Reconstruction of articulated objects from point correspondences in a single image[END_REF], the accuracy of these methods is still too low to be used reliably.

As a result, we take a soft, hybrid approach that integrates appearance cues as well. We first employ the single-view indoor reconstruction method of Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF] which produces a number of possible 3D scene hypotheses. We then use existing human detection machinery to generate pose candidates. The crux of our algorithm is in simultaneously considering the appearance of the scene and perceived human actions in a robust way to produce the best 3D scene interpretation given all the available evidence. We evaluate our approach on both time-lapses and still images taken from the Internet, and demonstrate significant performance gains over state-of-the-art appearance-only methods. We additionally demonstrate the viability of using humans as a cue without appearance and provide substantial analysis of how and when observing humans helps us better understand scenes.

Background

Our goal is to understand images in terms of 3D geometry and space. Traditional approaches in computer vision for 3D understanding have focused on using correspondences and multiple view geometry [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. While these methods have been successful, they are not applicable when only a single view of the scene is available; accordingly, they are incapable of understanding the great wealth of consumer and historic photographs not captured with multiple views or depth sensors. Reasoning about this sort of data is an enormous challenge for computers and an open research question since it is a wildly underconstrained problem. Nonetheless, it is trivial for any human being. Since humans can infer scene structure from a single image, single-view re-construction is thus a necessary step towards vision systems with human-like capabilities. Furthermore, 3D scene estimates from a single image not only provide a richer interpretation of the image but also improve performance of traditional single-image tasks such as object detection [START_REF] Hedau | Thinking inside the box: Using appearance models and context based on room geometry[END_REF][START_REF] Hoiem | Putting objects in perspective[END_REF].

Past work on single-image 3D understanding has overcome the underconstrained nature of the problem in a variety of ways. For instance, Kanade demonstrated the recovery of 3D shapes from a single image in [START_REF] Kanade | Recovery of the three-dimensional shape of an object from a single view[END_REF] with the overarching constraint that "regularities observable in the picture are not by accident, but are some projection of real regularities," along with a variety of regularities such as parallelism and skewed symmetry. Advances in computing power as well as increased availability of data have led to work that learns to produce 3D understandings from data. This has led to methods that take a single image and recover the dominant 3D directions and horizon line of scenes [START_REF] Barinova | Geometric image parsing in man-made environments[END_REF], surface orientations [START_REF] Fouhey | Data-driven 3D primitives for single image understanding[END_REF][START_REF] Hoiem | Geometric context from a single image[END_REF][START_REF] Payet | Scene shape from texture of objects[END_REF], volumetric objects [START_REF] Gupta | Blocks world revisited: Image understanding using qualitative geometry and mechanics[END_REF][START_REF] Schwing | Box in the box: Joint 3D layout and object reasoning from single images[END_REF][START_REF] Xiao | Localizing 3D cuboids in single-view images[END_REF], or depth [START_REF] Karsch | Depth extraction from video using non-parametric sampling[END_REF][START_REF] Saxena | Make3D: Learning 3D scene structure from a single still image[END_REF]. In many of these, constraints used in the past (e.g., parallelism) are integrated into the models' objective functions.

There has been particular success in the field of indoor single-view 3D understanding. This has been made possible by the fusion of effective learning techniques for single image 3D prediction such as [START_REF] Hoiem | Geometric context from a single image[END_REF] and lowdimensional (i.e., highly constrained) models for 3D layout specifically tailored for indoor images [START_REF] Choi | Understanding indoor scenes using 3D geometric phrases[END_REF][START_REF] Del Pero | Bayesian geometric modeling of indoor scenes[END_REF][START_REF] Del Pero | Sampling bedrooms[END_REF][START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF][START_REF] Lee | Estimating spatial layout of rooms using volumetric reasoning about objects and surfaces[END_REF][START_REF] Schwing | Efficient Exact Inference for 3D Indoor Scene Understanding[END_REF][START_REF] Wang | Discriminative learning with latent variables for cluttered indoor scene understanding[END_REF][START_REF] Yu | Inferring spatial layout from a single image via depth-ordered grouping[END_REF]. The constraints involved usually concern the human-made nature of the scene: almost all approaches make the Manhattan-world assumption in which there are three orthogonal scene directions, and in most cases, it is assumed that the room can be roughly modeled as a cuboid. However, although they assume a humancentric scene structure, each of these approaches treats humans as clutter rather than as a cue: for all previous work, the best and arguably correct reaction to a human in the scene is to classify her as clutter and to ignore her pixels in room layout estimation. In fact, despite being fundamentally dependent on the human-centric nature of the scenes, all recent work on room layout predic- Fig. 2 Overview of the proposed approach. We propose the use of both appearance and human action cues for estimating single-view geometry. Given an input image or set of input images taken by a fixed camera, we estimate human poses in each image (a), yielding a set of human-scene interactions (b), which we aggregate over time (for time-lapses). We use these to to infer functional surfaces (c) in the scene, such as sittable (red) and walkable (blue). We simultaneously generate room hypotheses (d) from appearance cues alone. We then select a final room hypothesis and infer the occupied space in the 3D scene using both appearance and human action cues.

tion has been evaluated on datasets containing exactly zero people. Given that humans and their activities are often the primary motivation for documenting scenes and that human scenes are constructed for humans, this seems unnatural. This work aims to demonstrate that humans are not a nuisance, but rather another valuable source of constraints.

Other work on the interface between humans and image understanding has mostly focused on modeling these constraints at a semantic level [START_REF] Delaitre | Learning person-object interactions for action recognition in still images[END_REF][START_REF] Gupta | Objects in action: An approach for combining action understanding and object perception[END_REF][START_REF] Turek | Unsupervised learning of functional categories in video scenes[END_REF]. For example, drinking and cups are functionally related and therefore joint recognition of the two should improve performance. Semantic-level constraints have been also shown to improve object discovery and recognition [START_REF] Gall | Functional categorization of objects using real-time markerless motion capture[END_REF][START_REF] Prest | Weakly supervised learning of interactions between humans and objects[END_REF][START_REF] Turek | Unsupervised learning of functional categories in video scenes[END_REF], action recognition [START_REF] Delaitre | Learning person-object interactions for action recognition in still images[END_REF][START_REF] Desai | Discriminative models for static human-object interactions[END_REF][START_REF] Gupta | Objects in action: An approach for combining action understanding and object perception[END_REF][START_REF] Kjellstrom | Simultaneous visual recognition of manipulation actions and manipulated objects[END_REF], and pose estimation [START_REF] Gupta | Context and observation driven latent variable model for human pose estimation[END_REF][START_REF] Yao | Classifying actions and measuring action similarity by modeling the mutual context of objects and human poses[END_REF]. Recently Delaitre et al. [START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF] proposed the use of poses for semantic segmentation of scenes; like ours, their work also uses poses as a cue, but it solves the complementary problem of giving each pixel in an image a semantic label (e.g., chair), not improving estimates of 3D scene geometry.

In this paper we specifically focus on modeling relationships at a physical level between humans and 3D scene geometry. In this domain, most earlier work has focused on using geometry to infer human-centric information [START_REF] Grabner | What makes a chair a chair?[END_REF][START_REF] Gupta | From 3D scene geometry to human workspace[END_REF], or the question "what can a human do with a given 3D model". For instance, Gupta et al. [START_REF] Gupta | From 3D scene geometry to human workspace[END_REF] argued that functional questions such as "Where can I sit?" are more important than categorizing objects by name, and used estimated 3D geometry in images to infer Gibsonian affordances [START_REF] Gibson | The ecological approach to visual perception[END_REF], or "opportunities for interaction" with the environment. Jiang et al. [START_REF] Jiang | Hallucinated humans as the hidden context for labeling 3D scenes[END_REF] used the sizes and poses of humans to infer human-object affordances from 3D scenes containing no humans.

Our work focuses on the inverse of the problem addressed in [START_REF] Grabner | What makes a chair a chair?[END_REF][START_REF] Gupta | From 3D scene geometry to human workspace[END_REF]: we want to observe human actors, infer their poses and then use the functional constraints from these poses to improve 3D scene understanding. Our goal is to harness the recent advances in person detection and pose estimation [START_REF] Andriluka | Pictorial structures revisited: People detection and articulated pose estimation[END_REF][START_REF] Bourdev | Poselets: Body part detectors trained using 3D human pose annotations[END_REF][START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF][START_REF] Yang | Articulated pose estimation using flexible mixtures of parts[END_REF], and design a method to improve single-view indoor geometry estimation. Even though the building blocks of this work, human pose estimation and 3D image understanding, are by no means perfect, we show that they can be robustly combined. We also emphasize our choice of the monocular case, which sets our work apart from earlier work on geometric reasoning using human silhouettes [START_REF] Guan | 3D occlusion inference from silhouette cues[END_REF] in multi-view setups. In single-view scenarios, the focus has been on coarse constraints from person tracks [START_REF] Krahnstoever | Bayesian autocalibration for surveillance[END_REF][START_REF] Rother | What can casual walkers tell us about the 3D scene[END_REF][START_REF] Schodl | Depth layers from occlusions[END_REF], whereas we focus on fine-grained physical and functional constraints using human actions and poses.

A preliminary version of this work appeared as [START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF]. We clarify many technical details omitted in the previous version, present results on substantially extended datasets, and offer an in-depth analysis of how, why, and when observing humans can improve understanding of the 3D geometry of scenes.

Overview

Our work is an attempt to marry human action recognition with 3D scene understanding. We have made a number of simplifying assumptions. We limit our focus to indoor scenes: they allow for interesting humanscene interactions and several successful approaches exist specifically for estimating their geometry from a single view [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF][START_REF] Lee | Estimating spatial layout of rooms using volumetric reasoning about objects and surfaces[END_REF]. We use a set of commonly observed physical actions, reaching, sitting, and walking, to provide constraints on the free and occupied 3D space in the scene. To achieve this, we manually define surface constraints provided by each action, e.g., there should be a sittable horizontal surface at the knee height for the sitting action. We adopt a geometric representation that is consistent with recent methods for indoor scene layout estimation. Specifically, each scene is modeled in terms of the layout of the room (walls, floor, and ceiling) and the 3D layout of the objects. It is assumed that there are three principal directions in the 3D scene (the Manhattan world assumption [START_REF] Coughlan | The Manhattan world assumption: Regularities in scene statistics which enable bayesian inference[END_REF]) and therefore estimating a room involves fitting a parametric 3D box that is aligned with the vanishing points.

While temporal information can be useful for detecting human actions and imposing functional and geometrical constraints, in this work, we only deal with still images and time-lapse videos with no temporal continuity. Time-lapses are image sequences recorded at a low framerate, e.g., one frame a second. Such sequences are often shot with a static camera and show a variety of interactions with the scene while keeping the static scene elements fixed. People use time lapses to record and share summaries of events such as home parties or family gatherings. Videos can nonetheless be used in the proposed framework without any modifications by ignoring the temporal information and treating them as a time-lapse, or by substituting our single-frame pose estimators with approaches that integrate temporal information [START_REF] Andriluka | Monocular 3D pose estimation and tracking by detection[END_REF][START_REF] Park | N-best maximal decoders for part models[END_REF][START_REF] Ramakrishna | Tracking human pose by tracking symmetric parts[END_REF]. Time-lapse data is ideal for our experiments for many reasons. In our case, the time discontinuity works in our favor as it naturally compresses highly diverse personscene interactions into a small number of frames: a time-lapse video lasting a few minutes may show many hours of events. Moreover, the static nature of the underlying scene enables joint reasoning about multiple images without solving for camera pose to find a common reference frame. This lets us focus on the core of our problem, rather than a structure-from-motion preprocessing step. Finally, the time-lapses also enable us to test our method on realistic data with non-staged activities in a variety of natural environments: timelapses are captured by consumers in their daily living environments, frequently with viewing angles similar to consumer still photographs. Our datasets, for instance, contain time-lapses gathered from a consumer video sharing site, YouTube.com.

An overview of our approach is shown in Figure 2. First, we detect humans performing different actions in the image and use the inferred body poses to extract functional regions in the image such as sittable and reachable surfaces (Section 3). For time-lapses, we accumulate these detections over time for increased robustness. We then use these functional surface estimates to derive geometrical constraints on the scene. These constraints are combined with an existing indoor scene understanding method [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF] to predict the global 3D geometry of the room by selecting the best hypothesis from a set of hypotheses (Section 4.1). Once we have the global 3D geometry, we can use these human poses to reason about the free-space of the scene (Section 4.2).

Local Scene Constraints from People's Actions

Our goal is to predict functional image regions corresponding to walkable, sittable and reachable surfaces by analyzing human actions in the scene. We achieve this by detecting and localizing people performing the three different actions (standing, sitting, reaching) and then using their pose to predict contact points with the surfaces in the scene. For time-lapses, contact points are aggregated over multiple frames to provide improved evidence for the functional image regions. We illustrate these contact points on detected humans in Fig. 3.

Given a person detected performing an action, we predict contacts with surfaces as follows: (i) for walkable surfaces we define a contact point as the mean location of the feet position, and use all three types of actions; (ii) for sittable surfaces, we define a contact point at the mean location of the hip joints, and consider only sitting actions; and (iii) for reachable surfaces, we define a contact point as the location of the hand further from the torso, and use only reaching actions. These surfaces are not mutually exclusive (e.g., the tops of beds are sittable and reachable) and are estimated independently. To increase robustness to mistakes in localization, we place a Gaussian at the contact points of each detection and weight the contribution of the pose by the classifier confidence; one can also equivalently view this as each contact point voting for the properties of the scene with higher weight placed on nearby locations and on detections with high confidence. The standard deviation of each Gaussian is set to a fraction of the detection bounding box, 1/4 in X-and 1/40 in Y-direction, respectively; we use the bounding box dimensions to automatically scale our region of uncertainty with human proportions. This yields probability maps h for the different types of functional image regions, as illustrated in Figures 2c and5c,d.

Since a sitting detector may also respond to standing people, we discriminate between different actions by converting the detection score of each model into a probability by fitting a decreasing exponential law on their firing rate. Action classification is performed with non-maximum suppression: if bounding boxes of several detections overlap irrespective of action class, the detection with the highest calibrated response is kept.

Our approach is agnostic to the particular method of pose detection and only requires a detector that produces a class (e.g., sitting) as well as estimates for the relevant joints of the human (e.g., pelvic joint, feet). In this work, we use two complementary approaches. We build primarily on the articulated pose model of Yang and Ramanan [START_REF] Yang | Articulated pose estimation using flexible mixtures of parts[END_REF]. Here, we employ the model for detecting human action by training a separate model for each of the three actions. To supplement the articulated model, we use the deformable parts model (DPM) of Felzenszwalb et al. [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF] for sitting and standing: the low variance of the relevant joints of these actions (e.g., feet for standing) enable us to accurately approximate 1 Fig. 4 Example detections with the deformable part models (top row: sitting; bottom row: standing) and approximated joint locations from bounding boxes (red: pelvic joint/sittable; blue: feet/walkable) poses by simply transferring a fixed pose with respect to the bounding box. We find that these two methods have complementary strengths and error modes. Examples of detected actions together with estimated body pose configurations and predicted contact points for the articulated model are shown in Figure 3 and for the deformable parts model in Figure 4.

The articulated pose estimator and deformable parts model are trained and used separately and produce independent estimates of functional regions. These functional regions are integrated separately in our room layout ranking function in Equation 2.

Space Carving Via Humans

In the previous section we discussed how we estimate human poses and functional regions such as sittable and walkable surfaces. Using the inferred human poses, we now ask: "What 3D scene geometry is consistent with these human poses and functional regions?" We build upon [START_REF] Gupta | From 3D scene geometry to human workspace[END_REF], and propose three constraints that human poses impose on 3D scene geometry: Containment. The volume occupied by a human should be inside the room. Free space. The volume occupied by a human cannot intersect any objects in the room. For example, for a standing pose, this constraint would mean that no voxels below 5ft can be occupied at standing locations. Support. There must be object surfaces in the scene which provide sufficient support so that the pose is physically stable. For example, for a sitting pose, there must exist a horizontal surface beneath the pelvis (such as a chair). This constraint can also be written in terms of the functional regions; for example, the backpro- jected sittable regions must be supported by occupied voxels in the scene.

Our goal is to use these constraints from observed human poses to estimate room geometry and the occupied voxels in the scene. Estimating voxels occupied by the objects in the scene depends on the global 3D room layout as well as the free-space and support constraints. On the other hand, estimating 3D room layout is only dependent on the containment constraint and is independent of the free-space and support constraints. Therefore, we use a two-step process: in the first step, we estimate the global 3D room layout, represented by a 3D box, using appearance cues and the containment constraints from human actors. This is done by ranking a large collection of room hypotheses and selecting the top-ranked hypothesis. In the second step, we use the estimated box-layout to estimate the occupied voxels in the scene. Here, we combine cues from scene appearance and human actors to carve out the 3D space of the scene.

Estimating Room Layout

Given an image and the set of observed human poses, we want to infer the global 3D geometry of the room. We build on the approach of Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF], which ranks a collection of vanishing-point aligned room hypotheses according to their agreement with appearance features. However, estimating the room layout from a single view is a difficult problem and it is often almost impossible to select the right layout using appearance cues alone: frequently, there are a handful of top hypotheses with inadequate evidence to decide which is correct. We propose to further constrain the inference problem by using the containment constraint from human poses. This is achieved with a scoring function that uses appearance terms as in [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF] as well as terms to evaluate to what degree the hypothesized room layout is coherent with observed human actors.

Given input image features x and the observed human actors H (represented by functional surface probability maps h ∈ H), our goal is to find the best room layout hypothesis y * ∈ Y. We use the following scoring function to evaluate the coherence of image features and human poses with the hypothesized room layout y:

f (x, H, y) = α ψ ψ(x, y) + α φ φ(H, y) + α ρ ρ(y), (1)
where ψ(x, y) measures the compatibility of the room layout configuration y with the estimated surface geometry computed using image appearance, φ(H, y) measures compatibility of human poses and room layout, and ρ(y) is a regularizing penalty term on the relative floor area that encourages smaller rooms; the αs tradeoff between the compatability terms.

As we build upon the code of Hedau et al., the first term, ψ(x, y) is the scoring function learned via Eqns. 3-4 of [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF]. The function uses global appearance cues, such as detected straight lines and the per-pixel classifier predictions for different surface labels (walls, floor, ceiling). The second term enforces the containment constraints and expands as

φ(H, y) = h∈H α φ,h ϕ(ζ(h), y), (2)
where ζ(h) is the mapping of functional surfaces onto the ground plane and ϕ measures the normalized overlap between the projection and floor in the hypothesized room layout. Intuitively, φ(H, y) enforces that the projection of both the human body and the objects it is interacting with should lie inside the room. The α φ,h terms trade off the weightings of the functional surfaces. In the current system, we do not enforce that the body does not intersect the ceiling, although this is not an issue in practice. We approximate ζ(h) by using the feet locations of detected actors, which produces accurate results for our action vocabulary. Finally, the term ρ(y) = -max(0, (A -M )/M ) imposes a penalty for excessive floor area A, measured with respect to the

Clutter Backprojected Functional Regions Free Space

Walkable Sittable Reachable Fig. 6 We estimate the free space of the scene by taking the backprojected clutter map and refining it with backprojected functional regions. Voxels above all backprojected functional regions recieve votes against being occupied due to the free space constraint; voxels below reachable and sittable regions (i.e., within the volumes) receive votes in favor of being occupied due to the support constraint. The result of combining all cues is shown on the right.

minimum floor area M out of the top three hypotheses. We include this regularization term since φ(H, y) can only expand the room to satisfy the containment constraint.

The relative weights α on the terms are learned in a leave-one-out fashion. One term, α ψ , is held constant, and grid search is performed on a fairly coarse grid (2 i for i = {-4, . . . , 2} for the other αs. For the regularization term, we include the additional option of setting α ρ to 0. We chose the weighting that results in the highest mean performance when choosing the top-ranked room on the training set. However, we note that the system is fairly insensitive to the particular αs: on no parameter setting does the system produce worse results than the appearance-only system on any dataset.

We select our room interpretation from the same hypothesis pool Y as [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF]. First, a modified version of the vanishing point detector of Rother [START_REF] Rother | A new approach to vanishing point detection in architectural environments[END_REF] estimates three orthogonal vanishing points in the scene. The discrete pool of hypotheses is generated by discretizing the space of all vanishing-point aligned boxes. We rank each hypothesis with Equation 1 and return the top-scoring hypothesis as our predicted layout.

Estimating Free Space in the Scene

Once we have estimated the room layout we now estimate the voxels occupied by objects. However, this is a difficult and ill-posed problem. Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF] use an appearance based classifier to estimate pixels corresponding to objects in the scene. These pixels are then back-projected under the constraint that every occupied voxel must be supported. Lee et al. [START_REF] Lee | Estimating spatial layout of rooms using volumetric reasoning about objects and surfaces[END_REF] and Gupta et al. [START_REF] Gupta | From 3D scene geometry to human workspace[END_REF] further constrain the problem with domain-specific cuboid object models and constraints such as "attachment to walls." We impose functional constraints: a human actor carves out the free space and support surfaces by interacting with the scene.

The room layout and camera calibration gives a cuboidal 3D voxel map in which we estimate the free space. We first back project the clutter mask of Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF], and then incorporate constraints from different human poses to further refine this occupied voxel map. Specifically, we backproject each functional region h at its 3D height, yielding a horizontal slice inside the voxel map. Because our classes are fine-grained, we can use human dimensions (waist height) for the heights of the sitting and reaching surfaces. This slice is then used to cast votes above and below in voxel-space: votes in favor of occupancy are cast in the voxels below; votes against occupancy are cast in the voxels above. This is illustrated in Fig. 6. The final score for occupancy of a particular voxel is a linear sum of these votes; as the result is probabilistic, to produce a binary interpretation as shown in the figures, we must threshold the results.

Experiments

In this section, we describe experiments done to validate our contributions. We introduce the experimental setup, the datasets, and raw quantitative results as well as some qualitative results. A detailed analysis of how observing people changes room layout estimation is presented in Section 6.

As preface, we note that the primary contribution of this work is the demonstration that humans can serve as a valuable cue for single-view geometry problems in practice. Although we present a way of integrating functional surfaces into single-view reasoning with a particular appearance-based system operating in a particular paradigm, there are many other ways of recovering the layout, surfaces, or 3D structure of a room from a single view. The purpose of this work is not to demonstrate that our particular system out-performs all other approaches; instead, it is to demonstrate that affordance-based cues offer complementary evidence to appearance-based ones. Accordingly, we design our experiments and analysis to investigate how our system performs relative to a system using the same appearance features and set of hypotheses.

Input Image

Functional Regions Scene Geometry 1 Fig. 7 Example time-lapse sequence results: given an input image, we use functional regions (walkable: blue; sittable: red; reachable: green) to constrain the room layout; having selected a layout, we can also infer a more fine-grained geometry of the room via functional reasoning.

(a) Appearances Only (Hedau et al ).

(b) Appearances + People (Our approach).

Fig. 8 Timelapse experiment: A comparison of (a) the appearance only baseline [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF] with (b) our improved room layout estimates. In many cases, the baseline system selects small rooms due to large amounts of clutter. On the right, even though the room is not precisely a cuboid, our approach is able to produce a better interpretation of the scene.

Baselines and evaluation criteria. For both timelapses and single images, we compare our estimates of room geometry to a number of baselines. Our primary baseline is the appearance-only system of Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF], which we use to provide appearance cues. To provide context, we also include another baseline, in which we impose the box model on the output of Lee et al. [START_REF] Lee | Geometric reasoning for single image structure recovery[END_REF] that maximizes the agreement. Finally, to show that all methods are operating better than chance, we use location alone to predict the pixel labels, akin to a per-pixel prior: after resizing all scenes to common dimensions, we use the majority label in the training images for each pixel.

To quantitatively evaluate how well we estimate the layout of an image, we use the standard metric of perpixel accuracy (i.e., treating the problem as a semantic segmentation one). Note that since the camera is fixed in time-lapses, the scene can be summarized with a single image (the one provided to the appearanceonly approaches) and thus only a single annotation is needed. In some time-lapses, the camera is adjusted or zoomed slightly; this only impacts our approach, and not the apperance-only approaches. When aggregating a statistic over a dataset, we quantify our uncertainty regarding the statistic via boostrapped confidence intervals, which we compute with the Bias-Corrected Accelerated method [START_REF] Efron | Better bootstrap confidence intervals[END_REF], using 10,000 replicates. Implementation details. We train detectors using the Yang and Ramanan model for all three actions [START_REF] Yang | Articulated pose estimation using flexible mixtures of parts[END_REF] and the Felzenszwalb et al. model for sitting and standing. For the standing action, we use a subset of 196 images from [START_REF] Yang | Articulated pose estimation using flexible mixtures of parts[END_REF] containing standing people. For sitting and reaching, we collect and annotate 113 and 77 new images, respectively. All images are also flipped, doubling the training data size. As negative training data we use the INRIA outdoor scenes [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], indoor scenes from [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF], and a subset of Pascal 2008 classification training data. None of the three negative image sets contains people. On testing sequences, adaptive background subtraction is used to find foreground regions in each frame, which are used as the appearance for the time-lapse and to remove false-positive detections on the background. We also use geometric filtering similar to [START_REF] Hoiem | Putting objects in perspective[END_REF] to remove detections that significantly violate the assumption of a single ground plane.

Datasets

We test the proposed approach on consumer time-lapse videos and a collection of indoor still images. The data for both originates from the Internet and depicts challenging, cluttered, and non-staged scenes capturing one or more people engaged in everyday activities interacting with the scene. Comparison on existing datasets is impossible since previous work on room layout estimation has ignored people as a cue and has been evaluated on datasets composed entirely of unoccupied rooms.

Time-lapse data. For time-lapse videos, we present results on the dataset introduced in [START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF], as well as on the larger semantic segmentation dataset presented in [START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF], which contains the dataset of [START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF] as a subset. We refer to the dataset of [START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF] as the People Watching timelapses, and that of [START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF] as the Scene Semantics timelapses. We have re-labeled the Scene Semantics dataset for room layout prediction.

Both datasets were collected from Youtube using keywords such as "time-lapse," "living room," "party," or "cleaning." The People Watching dataset contains 40 videos with about 140,000 frames. The Scene Semantics dataset contains 146 videos, totaling about 400,000 frames.

Unlike the People Watching dataset, which contains largely unambiguous and cuboidal bedrooms and living rooms, the Scene Semantics dataset contains a wider variety of scene classes as well as many scenes that violate the assumptions of our method. These include straight-forward violations of explicit assumptions, such as that no more than three walls are visible. These also include violations of more subtle implicit assumptions, such as that the full body of a person will be within the frame and that the floor will occupy some reasonable fraction of the scene: 10% of scenes in the Scene Semantics dataset have floor coverage of 15% or less, as compared to none in the People Watching dataset. This leads to truncated detections on the bottom of the image that do not actually rest on the floor. In the handful of cases where the cuboidal model is explicitly violated, only the unambiguous parts are annotated: for instance if four walls are visible due to a fish-eye lens, only the floor and ceiling are annotated.

Still image data. Our previous work [START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF] introduced a dataset of 100 still images of indoor scenes with people. We expand this dataset to 500 images. These images were retrieved from the Internet with queries such as "living room" and "waiting room" with the criterion that they are roughly cuboidal and that they contain at least one person. These non-staged images depict celebrities, political figurs, and ordinary people engaged in everyday tasks, ranging from simply sitting and talking to having meetings or parties.

Experiment 1: Time-lapse data

Figure 7 shows the performance of our approach on a set of time-lapses. The second column shows the probabilistic estimates of "walkable", "sittable" and "reachable" surfaces in blue, red and green respectively. We use these functional region estimates to select the best room hypothesis and estimate the free space of the scene, which is shown in the third column. These results show that human actors provide lot of information about the scene as they interact with it. For example, in the second row, even though the scene is cluttered, human reaching actions help us to infer a horizontal surface on the left. We also qualitatively compare the 3D room layout estimated by our approach to that of Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF]. Figure 8 shows some examples of the relative performance.

We present a summary of the quantitative results on both time-lapse datasets in Table 1. In both cases, our method is able to consistently improve on the baseline. On the People Watching dataset, our method averages a gain of 7.6% (bootstrapped 95% confidence interval: 4.5% to 11.3%) over the Appearance-alone baseline. Further, our performance is as good (within 5%) or better than the baseline in 92.5% of images. On the Scene Semantics dataset, our method averages a gain of 3.1% (bootstrapped 95% confidence interval: 1.1% to 5.1%) over the Appearance-only baseline. Further, on an individual image basis, our performance is generally about the same or better: in the overwhelming majority of cases, 88.6%, our system produces as good or better results.

To demonstrate the power of cues from people, we show results using human action cues alone to select room hypotheses. Specifically, we use only our human action compatibility and room size terms, φ and ρ, to rank the hypotheses. Since we have no appearance term to counter-balance the expansion preferred by our containment constraint, we modify ρ to use the minimum floor area from a larger number of top hypotheses. Specifically, this fraction is the top n% for n = {1, 5, 10, 25, 50} selected via leave-one-out cross-validation. This can be thought of as aiming to select a small room among the top n% hypotheses that explain the people observed in the scene. Even with only people as cues, our system performs only about 4% worse on average than Hedau et al. and equivalently to Lee et al. on both time-lapse datasets.

Finally, we evaluate the use of functional regions as a cue for free space estimation on the Scene Semantics dataset. Since high-quality labels already exist for semantic segmentation from [START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF], we evaluate in the image plane, predicting whether a region is free or not on the floor. We linearly combine the functional regions with the clutter map as in Section 4.2 with the weighting learned by logistic regression. We characterize performance via average precision (AP) obtained by sweeping a threshold over classifier output. In comparison to the clutter map produced by [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF], our approach obtains a boost of 6.7% AP (boostrapped 95% confidence interval: 4.6% to 8.9%) when combined with the clutter map. Further, using people alone as an indicator of free-space produces about the same accuracy as the predicted clutter map, a -0.5% comparative loss in AP (boostrapped 95% confidence interval -4.7% to 2.9%).

Experiment 2: Understanding single images

In the second experiment, we run the system on still images to see whether functional reasoning can improve room layout estimation with a single image. We report results on our new extended dataset of 500 images. We additionally report results on the dataset introduced in [START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF] for completeness. Our results show that functional constraints from human actions provide strong evidence of 3D geometry even in single images. Figure 9 shows a few examples of our estimated room geometry compared to Hedau et al. [START_REF] Hedau | Recovering the spatial layout of cluttered rooms[END_REF]. We are able to obtain substantial improvements over the appearance-only approach; in most cases in Figure 9, this gain comes when people disambiguate a cluttered scene where estimating the true extent of the room is difficult. Figure 10 shows examples of estimated 3D room geometry and the 3D occupied voxels.

We report quantitative results in Table 2. On the extended dataset, we we obtain a 1.26% improvement (bootstrapped 95% confidence interval: 0.61% -1.97%) and our performance is as good or better in 86.3% of Appearance Alone Appearance + People 1 Fig. 9 Single Image Experiment: The correct person in the correct place can easily disambiguate complex scene interpretation problems. In the last example, although the vanishing points are inaccurate, we produce a more accurate intepretation.

cases. On average, our gain over the appearance-only baseline on single images is lower than in the time-lapse case although we obtain many scenes with substantial gains. This seeming drop in performance happens because a single frame gives us fewer chances to use functional reasoning to adjust our scene interpretation, resulting in equivalent interpretations with and without people (and even, as Table 2 shows, with the groundtruth poses). In subsequent analysis we more thorougly explore the nature of our gains in performance.

Input: Image

Output: Room

Discussion

We now present an analysis of how observing humans improves room layout prediction. We first show how observing humans changes layout estimation beyond summary statistics. We then analyze when our system succeeds and show how our performance varies with respect to the number of humans present and detected. Finally, we illustrate when our system does not succeed, and analyze a number of failure modes.

6.1 How do humans change layout estimation? On average our system provides consistent performance gains over the appearance-only baseline; however, considering just mean performance hides important aspects of how performance varies. In particular, one could wonder if the performance gains are consistent or the result of a process with higher mean but high variance as well. The former is more reassuring than the latter since in the latter case whether performance improves is largely a product of chance; further, adding people as a cue should not hurt performance. The peformance of the system is bi-modal: in one mode, the Appearance + People system produces similar results to the Appearance only system; in the other, functional reasoning produces different and systematically better results. We present an analysis of these two populations on the expanded still image dataset and both time-lapse datasets in Table 3. We define similar predictions as scenes in which the pixel-map output of the two systems differs by 10% or less, and different predictions as the rest. We present the proportion of the cases (i.e., how often they differ), the accuracy of the appearance-only system on each set of scenes, and the gain of the proposed system over the appearance-only baseline. Table 3 shows that our system consistently obtains most of its gains from the scenes in which appearance by itself is inadequate for reasoning. Compare the appearance-alone accuracies between the similar and different columns, as well as the relative performance: across all datasets, the scenes in which people help improve rooms are the ones in which appearance produces worse results. This has important implications for the nature of our performance gains. It shows that the mean statistics presented in Tables 1 and2 are not a large number of gains outweighing a large number of substantial losses leading to an improvement, but instead are systematic gains diluted down by largely unchanged (but correctly so) scenes. This no-difference mode stems from the nature of humans as a cue: unlike a new feature or learning algorithm, direct observation of humans can only act as a cue where humans are present in the scene. If the room is largely correct or the people in the scene are entirely contained within an incorrect interpretation, then functional reasoning cannot help. These cases are illustrated qualitatively in Figure 11.

How many people do we need to see to succeed?

We now provide an analysis of how the number of people in a scene affects the performance of our system in terms of room layout estimation: does our system need to see a large number of people densely scattered through the scene in order to function or can our system achieve substantial gains with relatively few people in the scene? The latter is preferable to the former since our system would have little chance of working on most real world images if it required dozens of people spread throughout the scene. We answer the latter: our system does not rely on a dense crowd of people to find a room, but can use as little as a one peson to dramati-

Identical Results

Estimated with and without People Functional Regions 11 Illustrations of the cases where observing people produces identical results to using appearance cues alone. Top-tobottom: frequently, the room is correct and our constraints do not change the ranking of hypotheses; sometimes the room's size is estimated as incorrectly large, and the containment constraint is satisfied; sometimes the room's size is too small, but all people are contained within the incorrect estimate. For clarity, the variance of the Gaussians for functional surface computation have been increased and the map has been rendered more strongly.

cally change a scene's interpretation. In the process, we analyze the connection between the number of people in the scene and the performance of our system relative to the appearance only baseline.

We show scatterplots of the relative performance of our system on the extended still image dataset against both the number of people present in the scene and 12 Scatterplots of relative performance vs. number of people present and the number of people detected on the extended still image dataset. To better illustrate the density, the x values of points are slightly jittered. Substantial gains (> 5%) are shown in green, approximately equivalent (±5%) in blue, and substantial losses (< -5%) in red (where substantial losses account for only 13.7% of the data). Our system is able to achieve substantial gains in performance with even a single person acting as a cue.

the number of people detected in Figure 12 (changes in performance with 0 detections are due to our regu-larization term). Quantitatively, we can analyze the relationship between our relative performance and these two measures of the number of people via Spearman's rank correlation coefficient ρ, which characterizes the degree to which two variables can be related with a monotonic function (i.e., whether increases in the number of people lead to greater gains in performance), with -1 indicating perfect negative rank correlation and 1 perfect rank correlation. Ideally, we would like a weak correlation and a positive one, if any (i.e., ρ near 0 but preferably positive): if there was a strong correlation, then all of our large gains would be the result of the lesslikely densely populated scenes. Relative performance is more or less unaffected by the number of people present in the scene (ρ = 0.0081, bootstrapped 95% confidence interval -0.0827 to 0.0979). If we consider the number of detections, performance is also more or less unaffected for scenes in which we detect at least one person (ρ = 0.0564, bootstrapped 95% confidence interval -0.0416 to 0.1496); there is, of course, a much stronger correlation if we also include scenes with no detections in the analysis since our algorithm requires at least one person to produce large gains. Accordingly, our system is not limited to scenes in which large numbers of people appear, and crucially can produce substantial gains in sparsely populated scenes which are more likely in consumer photograph collections. To explain this result, we show qualitative examples in Figure 13 of all pairings of small and large performance gains and densely and sparsely filled scenes. When small gains occur, appearance cues give a largely correct interpretation of the scene but cannot disambinguate two interpretations of a small detail (e.g., where the floor ends); in these cases, a person reveals the correct interpretation, producing a better result. Large gains are generally the result of appearance cues being completely incorrect; in these cases, while a large number of people may help provide additional evidence, even a single observation can compensate for the incorrect appearance evidence.

6.3 When does trying to observe people hurt us and why?

Our system is built from noisy detectors, vanishing point estimators, and appearance classifiers and is therefore by no means perfect. We now present an analysis of our failure modes, which show where future work could perhaps provide improved performance. Here, we focus on modes in which our system produces worse results. In turn, we discuss the dominant causes for our system to have lower performance than the appearance-only system: (a) incorrect vanishing point estimation; (b) inaccurate detections; (c) clipped and occluded detections; (d) regularization (with a caveat); and (e) fundamental limits of our model. The first three failure modes, illustrated in Figure 14, are due to limitations of components that provide inputs to our system, and can be fixed by improved approaches for their solution or better models learned from better data: our approach is agnostic to the source of vanishing points and, as demonstrated by the use of two detectors, is also agnostic to the source of human poses.

Vanishing point estimation is largely successful on the datasets used, but incorrect estimates that give an incorrect search space can occur, leading to substantial performance losses. For instance, in Figure 14(a) right, a floor has been expanded to agree with functional surfaces; since the hypothesis space is incorrect due to incorrect vanishing points, the floor cannot be expanded correctly and covers the ground-truth wall, making a bad result worse. On the left, the estimation has catastrophically failed, and an already incorrect result is made worse. This is not particular to our approach, but a weakness common to all approaches that search over a single family of vanishing-point aligned cuboidal models.

Incorrect output of the pose estimators can also mislead our system. This can take the straight-forward form of outright false-positives and mistakes in localization that force the room to be expanded incorrectly as in Figure 14(b). This can also happen when the full extent of a person's body is not visible, and the functional contact points are inaccurately predicted, as shown in Figure 14(c): e.g., an occluded standing person predicted as a too-short sitting person or a person with feet below the image predicted with the feet within the image. As future work improves the performance of our subcomponent systems, we anticipate these issues becoming less frequent.

The last failure modes, illustrated in Figure 15 are tied to the proposed model, and cannot be improved by outside algorithmic improvements. A large fraction of our performance losses on a per-image basis can be explained by our regularization term's preference for smaller rooms, illustrated in Figure 15(a); nonetheless, these are generally modest losses, and on average this regularization term improves results and is always made non-zero by parameter learning. Finally, occasionally there are images that violate our model, as shown in Figure 15(b), and thus lead to worse performance. This can happen with scenes with large and populated hallways outside the room, in which case the room is improperly expanded and walls are labeled as floor. Similarly, our system is confused by mirrors or pictures. While edge cases such as mirors and life-sized icons are presently too rare and difficult to handle, the noncuboidal scene case can be remedied by integrating functional reasoning into other layout estimation models that are not limited to cuboids, such as that of Flint et al. [START_REF] Flint | Manhattan scene understanding using monocular, stereo, and 3D features[END_REF]: our functional surfaces are not tied to the box-prediction paradigm.

The above discussion describes how the system can have worse performance, but not how it can fail to capitalize on people in the scene. At this point, a large fraction of these cases are explained by the limits of our pose detectors. Another contributing factor is the local nature of our constraints: given an observed contact point between a human and a surface, our system only infers functional properties at that contact point and does not propagate the functional property to similarappearing regions. In future work, a more complex and learned relationship between human poses and scene properties, such as the one developed in [START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF], may permit individual joints to provide constraints on room layout that have larger spatial support and higher likelihood of helping correct an inaccurate room estimate.

Conclusions

While recognizing actions and estimating poses for a given person is still a very challenging problem, we have shown that noisy pose detections can significantly improve estimates of scene geometry and 3D layout even in a single image. We have shown how even a single person in the right place can greatly improve scene interpretation. In the future, we expect further gains in the accuracy of the proposed method when better pose estimators become available; we further anticipate that our approach to afforance reasoning via functional surfaces can be extended to other models and problems in sceneunderstanding, for instance non-cuboidal Manhattanworld layout recovery or anomaly detection.

Fig. 1

 1 Fig. 1 What can human actions tell us about the 3D structure of a scene? Quite a lot, actually. Consider the people depicted on the left. They were detected in a time-lapse sequence in one of rooms A, B, or C. Which room did they come from? See the text for the answer.

1 Fig. 3

 13 Fig. 3 Example action detection and pose estimation results with the articulated model. The predicted surface contact points are shown by ellipses: blue (walkable), red (sittable), green (reachable). Shown actions are: standing (1-2), sitting (3-5), and reaching (6-8).

1 Fig. 5

 15 Fig. 5 Predicting functional image regions. (a) An image from a time-lapse sequence. (b) Overlaid example person detections from different frames: standing (blue), reaching (green). (c,d) Probability maps of predicted locations for (c) walkable and (d) reachable surfaces. Note that the two functional surfaces overlap on the floor.

Fig. 10

 10 Fig. 10 Single Image Experiment: Functional reasoning to detect sittable surfaces in still images.

  (a) People consistent with correct room (b) People contained in too-large room (c) People consistent with incorrect room

Fig.

  Fig.11Illustrations of the cases where observing people produces identical results to using appearance cues alone. Top-tobottom: frequently, the room is correct and our constraints do not change the ranking of hypotheses; sometimes the room's size is estimated as incorrectly large, and the containment constraint is satisfied; sometimes the room's size is too small, but all people are contained within the incorrect estimate. For clarity, the variance of the Gaussians for functional surface computation have been increased and the map has been rendered more strongly.

1 Fig. 13

 113 Fig.13Examples of small refinements (left) and large improvements (right) in scenes with small or large numbers of people detected. For clarity, the variances of the Gaussians for functional surface computation have been increased and the map has been rendered more strongly.

Fig.

  Fig.12Scatterplots of relative performance vs. number of people present and the number of people detected on the extended still image dataset. To better illustrate the density, the x values of points are slightly jittered. Substantial gains (> 5%) are shown in green, approximately equivalent (±5%) in blue, and substantial losses (< -5%) in red (where substantial losses account for only 13.7% of the data). Our system is able to achieve substantial gains in performance with even a single person acting as a cue.

  Pose confusion and clipped detections

Fig. 14

 14 Fig.14Failure modes of the system due to external components. In the single image cases, the variances of the Gaussians for functional surface computation have been increased for clarity and the map has been rendered more strongly.

Fig. 15

 15 Fig.15Failure modes of the system for both single images and time-lapses intrinsic to our system. In the single image cases, the variances of the Gaussians for functional surface computation have been increased for clarity and the map has been rendered more strongly.

Table 1

 1 Time-lapse Experiment: Average pixel accuracy for geometry estimation on the People Watching[START_REF] Fouhey | People watching: Human actions as a cue for single-view geometry[END_REF] and Scene Semantics[START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF] Time-lapse datasets. Our method achieves significant gains and using humans alone produces competitive performance.

		Location	Appearance Only People Only Appearance + People
			Lee et al. Hedau et al.
	People Watching [16]	64.1%	70.4 %	74.9%	70.8%	82.5%
	Scene Semantics [10]	61.4%	68.3 %	74.3%	70.7%	77.4%

Table 2

 2 Single Image Experiment: Average pixel accuracy for geometry estimation on single images. With even a single pose, our method achieves significant gains. Lee et al. Hedau et al.

		Location	Appearance Only	Appearance + People
					Ours	with Ground Truth Poses
	People Watching Single Images [16]	66.4%	71.3%	77.0%	79.6%	80.8%
	Extended Single Images	62.5%	70.7%	76.0%	77.8%	78.8%

Table 3

 3 Analysis of the scenes in which we produce similar (< 10% difference) and different predictions to the appearance only baseline. Across all datasets, we produce most of our gains from scenes in which appearance is inadequate.

		Still Images	People Watching Time-lapses [16] Scene Semantics Time-lapses [10]
		Different Similar	Different	Similar	Different	Similar
	Proportion	40.2%	59.8%	62.5%	37.5%	55.3%	44.7%
	Appearance Acc.	71.6%	79.1%	71.9%	79.7%	71.4%	77.6%
	Relative Acc.	3.0%	0.8%	11.5%	0.6%	5.3%	0.4%

Acknowledgments: This work was supported by NSF Graduate Research and NDSEG Fellowships to DF, and by ONR-MURI N000141010934, NSF IIS-1320083, the MSR-INRIA laboratory, the EIT-ICT labs, Google, ERC Activia, and the Quaero Programme, funded by OSEO.