Zoi Kaoudi

Ioana Manolescu

Triples in the clouds

The W3C's Resource Description Framework (or RDF, in short) is a promising candidate which may deliver many of the original semi-structured data promises: flexible structure, optional schema, and rich, flexible URIs as a basis for information sharing. Moreover, RDF is uniquely positioned to benefit from the efforts of scientific communities studying databases, knowledge representation, and Web technologies. Many RDF data collections are being published, going from scientific data to general-purpose ontologies to open government data, in particular in the Linked Data movement.

Managing such large volumes of RDF data is challenging, due to the sheer size, the heterogeneity, and the further complexity brought by RDF reasoning. To tackle the size challenge, distributed storage architectures are required. Cloud computing is an emerging paradigm massively adopted in many applications for the scalability, fault-tolerance and elasticity features it provides. This tutorial discusses the problems involved in efficiently handling massive amounts of RDF data in a cloud environment. We provide the necessary background, analyze and classify existing solutions, and discuss open problems and perspectives.

I. INTRODUCTION

During the past decade, many Semantic Web applications have been using the W3C's Resource Description Framework (or RDF, in short) [START_REF] Hayes | RDF Semantics[END_REF] as their data model. RDF data is organized in graphs consisting of triples of the form (s, p, o), stating that the subject node s has the property edge p whose value is the object node o. A key concept for RDF is that of URIs or Unique Resource Identifiers; these can be used in either of the s, p and o positions to uniquely refer to some entity or concept. Literals (constants) are also allowed in the o position. RDF allows some limited form of incomplete information through blank nodes, standing for unknown constants or URIs; an RDF database may, for instance, state that the author of X is Jane while the date of X is 4/1/2011, for a given, unknown resource X. This contrasts with standard relational databases where all attribute values are either constants or null.

RDF Schema (RDFS) [START_REF] Brickley | RDF Vocabulary Description Language 1.0: RDF Schema[END_REF] is the ontology language of RDF used for giving meaning to resources, grouping them into concepts and identifying the relationships between these concepts. If an RDF Schema is available, RDF semantics requires considering that the database consists not only of triples explicitly present in the store, but also of a set of implicit triples obtained through reasoning based on an RDF Schema and the RDFS rules. For instance, assume the RDF database contains the fact that the studentRegistrationNo of Bob is 12345, whereas an RDF Schema states that only a student can have a studentRegistrationNo. Then, the fact that Bob is a student is implicitly present in the database, and a query asking for all student instances in the database must return Bob.

The proliferation of RDF-based applications has created the need for systems capable of efficiently storing and querying RDF data. Some of the first systems that appeared in the Semantic Web community include Jena [START_REF] Wilkinson | Efficient RDF Storage and Retrieval in Jena2[END_REF] and Sesame [START_REF] Broekstra | Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema[END_REF]. More recently, RDF-based stores have gained interest in the database community as well, as illustrated by the works [START_REF] Neumann | The RDF-3X Engine for Scalable Management of RDF Data[END_REF], [START_REF] Abadi | SW-Store: a vertically partitioned DBMS for Semantic Web data management[END_REF], [START_REF] Weiss | Hexastore: sextuple indexing for semantic web data management[END_REF]. However, these works focus mostly on RDF viewed as a relational database on which to evaluate conjuctive queries, and do not consider RDF-specific features such as those related to implicit data. Recently, commercial database management systems also started providing some support for RDF, e.g., Oracle 11g RDF [START_REF] Chong | An efficient SQLbased RDF querying scheme[END_REF].

One could consider RDF as yet another graph model for semi-structured data [START_REF] Quass | Lore: a lightweight object repository for semistructured data[END_REF], useful in certain application contexts [START_REF] Trißl | Fast and practical indexing and querying of very large graphs[END_REF] but too expensive to handle in the general case. However, arguably, RDF has the potential for being the most successful semi-structured data model ever, since it draws on a fundamental tenet of the World Wide Web, namely, that every resource is assigned a single URI, which everyone can use to describe it. RDF also draws on other widely adopted W3C specifications, such as XML for serialization and exchange, namespaces for the interoperability of vocabularies etc. Thus, it has good potential for supporting data sharing on the Web.

A particularly interesting class of applications comes from the Open Data concept that "certain data should be freely available to everyone to use and republish as they wish, without restrictions from copyright, patents or other mechanisms of control"1 . Open Data federates players of many roles, from organizations such as business and government aiming to demonstrate transparency and good (corporate) governance, to end users interested in consuming and producing data to share with the others, to aggregators that may build business models around warehousing, curating, and sharing this data [START_REF] Raschia | Proceedings of the first international workshop on open data (WOD)[END_REF]. Sample governmental Open Data portals are the ones from the US (www.data.gov), UK (www.data.gov.uk) and France (www.etalab.fr). At the same time, if Open Data designates a general philosophy, Linked Data refers to the "recommended best practice for exposing, sharing, and connecting pieces of data, information, and knowledge on the Semantic Web using URIs and RDF" [START_REF] Berners-Lee | Linked data -design issues[END_REF]. In practice, Open and Linked data are frequently combined to facilitate data sharing, interpretation, and exploitation [START_REF]State of the LOD cloud[END_REF]. Sample applications of Linked Open Data are DBPedia (the Linked Data version of Wikipedia), BBC's platform for the World Cup 2010 and the 2012 Olympic games [START_REF] Kiryakov | The Features of BigOWLIM that Enabled the BBC's World Cup Website[END_REF] etc.

All these applications have led to plentiful RDF data collections that are available in the Web nowadays. To exploit such large volumes of RDF data, one could try to build a centralized warehouse. However, large and increasing data volumes raise the need for distributed storage architectures. Past works on distributed RDF query processing and reasoning have relied on peer-to-peer platforms [START_REF] Kaoudi | RDFS Reasoning and Query Answering on Top of DHTs[END_REF], [START_REF] Kaoudi | SPARQL Query Optimization on Top of DHTs[END_REF] or clustered architectures [START_REF] Harris | 4store: The Design and Implementation of a Clustered RDF Store[END_REF], [START_REF] Owens | Clustered TDB: A Clustered Triple Store for Jena[END_REF], [START_REF] Erling | RDF Support in the Virtuoso DBMS[END_REF].

Cloud computing is an emerging paradigm massively adopted in many applications for the scalability to very large data volumes and the fault-tolerance and elastic allocation that it provides. Recently, interest in massively parallel processing has been renewed by the MapReduce proposal [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] and many follow-up works, which aim at solving large-volume data management tasks based in a cloud environment. For these reasons, cloud-based stores are an interesting avenue to explore for handling very large volumes of RDF data.

This tutorial has two objectives.

• First, we will introduce the audience to the basics of RDF data management, including storage, query processing, reasoning and updating. We will achieve this based on the well-known concepts of semistructured data and existing works on RDF processing of the data management community.

• Second, we will present a classification of the existing architectures and tools for handling large volumes of RDF data in a cloud environment, compare their approaches and algorithms and discuss the respective trade-offs. Finally, we plan to draw a list of problems we currently find open and outline promising avenues to answer them.

II. TUTORIAL OUTLINE

Our tutorial will be structured as follows.

A. Semistructured data and RDF

We will start by briefly recalling the main principles of semistructured data [START_REF] Quass | Lore: a lightweight object repository for semistructured data[END_REF], [START_REF] Papakonstantinou | Object exchange across heterogeneous information sources[END_REF], a general concept pioneering many works on complex data management in the database community. The goal is to position RDF as one of the most popular models for semistructured data management currently around, while also acknowledging the contributions previously laid out for the more general model to which it can be traced.

We will provide the necessary background on RDF processing. This includes the basic concepts of RDF and RDFS, including their semantics [START_REF] Hayes | RDF Semantics[END_REF]. We will then focus on the Basic Graph Pattern (BGP) queries of SPARQL [START_REF] Prud | SPARQL Query Language for RDF[END_REF], and in particular on its conjunctive fragment allowing to express the core Select-Project-Join database queries. We will introduce the formal semantics of a BGP query, taking into account also the data entailed in an RDF database by the presence of an RDFS (or other flavor of) schema.

We will then consider the core data management issues raised by RDF processing, namely: storing (in row-and column-oriented stores), indexing, evaluating and ordering joins, query pattern selectivity estimation, updating, and the impact of reasoning. We will devote particular attention to a pedagogic introduction of the issues related to reasoning, since they are often ignored in mainstream database works. We will illustrate with detailed examples and introduce the various techniques proposed in the literature to handle implicit data [START_REF] Kaoudi | RDFS Reasoning and Query Answering on Top of DHTs[END_REF], [START_REF] Abiteboul | Web Data Management and Distribution[END_REF] and their performance trade-offs [START_REF] Goasdoué | BGP Query Answering against Dynamic RDF Databases[END_REF], [START_REF]Getting more RDF support from relational databases[END_REF].

At the end of this segment, the audience will have a good grasp of the RDF model and RDF data management issues.

We will end this part of the tutorial by noting that duplicate elimination is an important issue for RDF, since the usage of distinct URIs for the same conceptual resource hinders the basic RDF triple linking mechanism (through shared URIs). A full discussion of this issue is out of our scope, but we will mention it and provide pointers to the relevant literature [START_REF] Naumann | An Introduction to Duplicate Detection[END_REF], [START_REF] Bohm | LINDA: Distributed web-of-data-scale entity matching (short paper)[END_REF].

B. Cloud-based data management

Interest in massively parallel processing has been renewed recently since the emergence of the MapReduce proposal [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] and its open source implementation Hadoop [START_REF]Apache Hadoop[END_REF]. MapReduce has become popular in various computer science fields as it provides a simple programming paradigm which frees the developer from the burden of handling the issues of parallelization, scalability, load balancing and fault-tolerance. Although MapReduce was first mostly intended for data analysis tasks, it has also started to be used in query processing tasks. However, MapReduce provides simple primitives and more complex operations such as joins are not directly supported.

In this part of the tutorial, we will recall the basics of MapReduce and briefly outline the main existing strategies for processing joins in a MapReduce framework [START_REF] Blanas | A Comparison of Join Algorithms for Log Processing in MapReduce[END_REF], [START_REF] Afrati | Optimizing Multiway Joins in a Map-Reduce Environment[END_REF], [START_REF]Optimizing Joins in a Map-Reduce Environment[END_REF], since joins are at the heart of RDF BGP query processing.

RDFS reasoning can be assimilated to deductive databases and therefore recursive query processing techniques are pertinent. Therefore, we will highlight the connections between cloud-based RDFS reasoning and recursive query processing on top of MapReduce [START_REF] Afrati | Map-Reduce Extensions and Recursive Queries[END_REF], [START_REF] Bu | The HaLoop Approach to Large-Scale Iterative Data Analysis[END_REF].

This part of the tutorial will have introduced the audience to the basic primitives available in the cloud, the strong advantages of MapReduce and the difficulties that remain to be solved for high-level, declarative management of complex data such as RDF.

C. State-of-the-art cloud-based RDF systems

The core part of our tutorial will be a comprehensive classification of existing architectures and systems for handling RDF data within a cloud. We will present the main priciples used for: (i) organizing the data store, (ii) processing conjunctive queries and (iii) handling implicit data through reasoning.

A first classification of existing platforms can be made according to their underlying data storage facilities:

• The first category includes systems which use existing "NoSQL" key-value stores [START_REF] Cattell | Scalable SQL and NoSQL data stores[END_REF] as their back-end for storing and indexing RDF data; • Our second category consists of systems relying on a distributed file system, such as HDFS, for warehousing RDF data; • The third category comprises systems relying on other storage facilities, such as a set of independent single-site RDF stores, or data storage services supplied by the cloud providers. Representatives of the first category include systems such as Rya [START_REF] Punnoose | Rya: A Scalable RDF Triple Store for the Clouds[END_REF] which uses Apache Accumulo [START_REF]Apache Accumulo[END_REF], Cumulus-RDF [START_REF] Ladwig | CumulusRDF: Linked Data Management on Nested Key-Value Stores[END_REF] based on Apache Cassandra [START_REF]Apache Cassandra[END_REF], Stratustore [START_REF] Stein | RDF On Cloud Number Nine[END_REF] which relies on Amazon's SimpleDB [START_REF]Amazon Web Services[END_REF], and H 2 RDF [START_REF] Papailiou | H2RDF: adaptive query processing on RDF data in the cloud[END_REF] which is built on top of HBase [START_REF]Apache HBase[END_REF]. The second category comprises platforms such as those described in [START_REF] Husain | Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing[END_REF], [START_REF] Rohloff | High-Performance, Massively Scalable Distributed Systems using the MapReduce Software Framework: the SHARD Triple-Store[END_REF]. These systems are built to make the most out of the parallel processing capacities provided by the underlying MapReduce paradigm. However they may be seen disadvantaged from the perspective of the data store, given that they do not have efficient fine-grained data stores to rely on. Within the third category, centralized RDF stores distributed among multiple nodes are used in [START_REF] Huang | Scalable SPARQL Querying of Large RDF Graphs[END_REF], whereas [START_REF] Bugiotti | RDF Data Management in the Amazon Cloud[END_REF], [START_REF] Aranda-Andújar | Amada: Web Data Repositories in the Amazon Cloud (demo)[END_REF] use a mixed approach with data residing in Amazon's storage service (S3) and a full data index built in Amazon's key-value store.

Cloud-based RDF platforms can also be analyzed according to their strategy for processing conjunctive queries:

• systems relying on the parallel programming paradigm of MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF]; • systems attempting to reduce or avoid alltogether MapReduce steps. The reason is that while MapReduce achieves important parallel scalability, the start-up time of a MapReduce job is significant and it may be too high for interactive-style queries. Systems such as [START_REF] Husain | Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing[END_REF], [START_REF] Rohloff | High-Performance, Massively Scalable Distributed Systems using the MapReduce Software Framework: the SHARD Triple-Store[END_REF] belong to the first class above. In the second class we find systems relying on key-value stores, typically implementing their own join operators, often exploiting the key-based organization of the underlying store, which helps identical values from different triples meet in the same data partitions [START_REF] Punnoose | Rya: A Scalable RDF Triple Store for the Clouds[END_REF], [START_REF] Stein | RDF On Cloud Number Nine[END_REF]. Works such as [START_REF] Huang | Scalable SPARQL Querying of Large RDF Graphs[END_REF], [START_REF] Bugiotti | RDF Data Management in the Amazon Cloud[END_REF], [START_REF] Aranda-Andújar | Amada: Web Data Repositories in the Amazon Cloud (demo)[END_REF] which take advantage of existing RDF stores also belong to this group. Finally, [START_REF] Papailiou | H2RDF: adaptive query processing on RDF data in the cloud[END_REF] employs a hybrid approach depending on the nature of the query.

Having toured the issues of RDF storing and querying through the above techniques, we will show how reasoning is handled in these cloud-based systems. From this angle, the options are as follows:

• pre-compute and materialize all implicit triples; • compute the necessary implicit triples at query time;

• some hybrid approach among the two above, with some implicit data computed statically and some at query time. Most recent proposals on RDFS reasoning in cloud environments come from the Semantic Web community [START_REF] Urbani | Scalable Distributed Reasoning using MapReduce[END_REF], [START_REF] Urbani | QueryPIE: Backward Reasoning for OWL Horst over Very Large Knowledge Bases[END_REF] but do not integrate it with the querying phase. The only work from the above that injects RDF reasoning within query processing is [START_REF] Husain | Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing[END_REF].

This part of the tutorial will provide a principled categorization of existing works and point out the strength and limitations of various proposals.

D. Open issues

In the final part of the tutorial we will draw a list of problems we currently find open and outline some promising avenues to answer them. These range from RDF query optimization and RDF updates in a cloud environment, as well as RDF view materialization and sharing of intermediate results in the distributed environment of the cloud.

Targeted Audience The intended audience consists of database students and researchers with an interest in RDF data management, cloud-based data processing, or both. We will provide brief self-sufficient introductions to both these areas to enable non-specialists to follow. In particular, while RDF querying has been well explored in database-oriented works, we will devote some time to the issues involved in RDF reasoning, which have not been considered in these works.

http://en.wikipedia.org/wiki/Open_data

Acknowledgments

We have studied the material on which the tutorial is based, while collaborating with many colleagues. We wish to thank in particular Franc ¸ois Goasdoué, Alexandra Roatis ¸and Jorge Quiané-Ruiz for many insightful discussions.

III. PRESENTERS

Zoi

Kaoudi received her PhD from National and Kapodistrian University of Athens in 2011, after graduating from the school of Electrical and Computer Engineering of the National Technical University of Athens. She is now a postdoctoral researcher at Inria Saclay and member of the OAK team. Her research interests include cloud-based management of Web data, distributed RDF query processing and reasoning. Personal webpage: http://pages.saclay.inria.fr/zoi.kaoudi/ Ioana Manolescu received her PhD from Inria and Université de Versailles Saint-Quentin in 2001, after graduating from Ecole Normale Supérieure in Paris. Ioana has been a post-doc at Politecnico di Milano, Italy, then she joined Inria where she is now senior researcher and the leader of the OAK team, specialized in database optimization techniques for complex, large data. Her research interests include algebraic optimizations, adaptive storage and efficient management of semantically rich data and cloud-based management of Web data. She has previously presented tutorials in VLDB (2003), ICDE (2005 and 2008), and the EDBT summer school (2002 and 2004). Personal webpage: http://pages.saclay.inria. fr/ioana.manolescu/


Julian Quiroga
email: julian.quiroga@inria.fr

Frédéric Devernay
email: frederic.devernay@inria.fr

James L Crowley
email: james.crowley@inria.fr

Local Scene Flow by Tracking in Intensity and Depth

Keywords: Scene flow, 3D motion estimation, Image tracking, Brightness consistency, Depth data, Locally-rigid motion, Optical flow, Image warping

Local scene flow by tracking in intensity and depth

Introduction

The scene flow corresponds to the 3D motion field of the scene [START_REF] Vedula | Three-dimensional scene flow[END_REF] and since it provides the motion of 3D points, an accurate estimation of the scene flow can be useful in a wide variety of applications including navigation, interaction, object segmentation, motion analysis, tracking, etc.

A current topic of great interest is human activity understanding, where video analyzing and interpretation is required to perform recognition or classification, and the 3D information given by the scene flow may be used to provide powerful features. However, there is no work that directly computes scene flow to perform tasks like human action recognition or gesture classification. Probably, this is due to the fact that most existing methods require stereo or multi-view camera systems, which are not always available. Besides, most of these methods compute a dense scene flow by optimizing a global energy function, spending a lot of processing time and becoming not suitable for real time applications. On the other hand, the optical flow that is related with the scene flow projection on the image plane has been successfully used in human action recognition. Histograms of optical flow are commonly used in stateof-the-art techniques in action recognition to construct descriptors over spatio-temporal interest points [START_REF] Laptev | Space-time interest points[END_REF][START_REF] Niebles | Modelling temporal structure of decomposable motion segments for activity classification[END_REF][START_REF] Raptis | Tracklet descriptors for action modelling and video analysis[END_REF] and to extract 2D trajectories by tracking key-points [START_REF] Raptis | Tracklet descriptors for action modelling and video analysis[END_REF][START_REF] Messing | Activity recognition using the velocity histories of tracked keypoints[END_REF][START_REF] Matikainen | Trajectons: Action recognition through the motion analysis of tracked features[END_REF]. Furthermore, since trajectory based methods outperform other state-of-theart approaches for action classification [START_REF] Wang | Action recognition by dense trajectories[END_REF], it is promising to use scene flow to capture motion information by extracting accurate 3D trajectories.

Recently with the arrival of depth cameras, based either on time-of-flight (ToF) or structured light sensing, it has been possible to compute scene flow using a pair of registered sequences of depth and intensity, as recently in [START_REF] Letouzey | Scene flow from depth and color images[END_REF][START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF]. Depth sensors have decreased system requirements needed to compute the 3D motion field, opening the door to incorporate scene flow based features in common recognition tasks. Some attempts have been made to include depth data in human action recognition tasks. For example, a bag of 3D points extracted from the depth data is used for recognition in [START_REF] Li | Action recognition based on a bag of 3D points[END_REF] while in [START_REF] Ni | RGBD-HuDaAct: A color-depth video database for human daily activity[END_REF] descriptors obtained by well known techniques [START_REF] Laptev | Space-time interest points[END_REF][START_REF] Bobick | The representation and recognition of action using temporal templates[END_REF] were extended with depth information, outperforming the original methods. Similarly, when a depth sensor is available the scene flow can be inferred from the optical flow by using the depth information. However, as we show in this paper, even small errors in the optical flow may generate significant errors in the scene flow computation. Computing scene flow in this way does not fully exploit the relation between the intensity and depth information. In this work we aim to explore how to simultaneously use intensity and depth data to compute local scene flow. As a result, we propose a method that can be used to get accurate 3D trajectories and define scene flow based descriptors.

One of the main contributions of this paper is the definition of a pixel motion model that allows the constraint of the scene flow in the image. Using this motion model and assuming a 3D local rigidity of the scene, we are able to solve for the scene flow that best explains the observed intensity and depth data. Therefore, our method combines information of both sensors and simultaneously solve for the scene flow and its projec-tion in the image, which we named image flow. This approach differs from previous scene flow methods using depth sensors, since they reconstruct the scene flow from the observed optical flow [START_REF] Letouzey | Scene flow from depth and color images[END_REF] or by using a large number of hypotheses to explain the motion of each point in 3D [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF], without exploiting the 2D parameterization. Moreover, unlike other scene flow methods that suffer from the smoothness constraint brought by 2D parameterization, we use a 3D local rigidity assumption, which is approximately real for most of the scenes of interest.

The other contribution of the paper is the formulation of a local scene flow computation method by extending the Lucas-Kanade framework [START_REF] Baker | Lucas-Kanade 20 years on: A unifying framework[END_REF] to exploit both intensity and depth data. In this formulation, it is possible to treat with large displacements in a coarse-to-fine procedure. Besides, instead of solving for a dense scene flow by optimizing a global energy, as most of previous methods, we solve for a local scene flow that can be focused over a selected set of key-points. This formulation is versatile enough to extract accurate 3D trajectories, initialize other methods by computing a dense scene flow, or refine a estimated 3D motion field over specific points. Unlike previous scene flow methods our local approach is suitable for real time applications and its extension to multiple cameras or depth sensors is straightforward.

Related work

Scene flow was first introduced by Vedula et al. [START_REF] Vedula | Three-dimensional scene flow[END_REF] as the full 3D motion field in the scene. Most scene flow methods assume a stereo, or multi-view camera system, in which the motion and the geometry of the scene are jointly estimated, in some cases, under a known scene structure. Since optical flow is (an approximation of) the projection of the 3D motion field on the camera image plane, an intuitive way to compute scene flow is to reconstruct it from the optical flow measured in a multi-view camera system, as proposed by Vedula et al. [START_REF] Vedula | Three-dimensional scene flow[END_REF], or including a simultaneously structure estimation as Zhang and Kambhamettu [START_REF] Zhang | On 3D scene flow and structure estimation[END_REF]. However, it is difficult to recover a scene flow compatible with several observed optical flows that may be contradictory.

The most common approach for estimating scene flow is to perform an optimization on a global energy function, including photometric constraints and some regularization. Some authors introduce constraints of a full calibrated stereo structure [START_REF] Li | Multi-scale 3D scene flow from binocular stereo[END_REF][START_REF] Wedel | Efficient dense scene flow from sparse of dense stereo data[END_REF][START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF][START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF][START_REF] Vogel | 3D scene flow estimation with a rigid motion prior[END_REF]. Wedel et al. [START_REF] Wedel | Efficient dense scene flow from sparse of dense stereo data[END_REF] enforce consistency on the stereo and motion solution but they decouple the disparity at the first time step without exploiting the spatio-temporal information. To overcome this limitation, simultaneous solution of the scene flow and structure was proposed. Huguet and Devernay [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF] simultaneously compute the optical flow field and two disparities maps, while Valgaerts et al. [START_REF] Valgaerts | Joint estimation of motion, structure and geometry from stereo sequences[END_REF] assume that only the camera intrinsics are known and they show that scene flow and the stereo structure can be simultaneously estimated.

All these methods suffer from the smoothness constraints brought by 2D parametrization. Basha et al. [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF] improve the estimation by formulating the problem as a point cloud in 3D space and the scene flow is regularized using total variation (TV). Recently, Vogel et al. [START_REF] Vogel | 3D scene flow estimation with a rigid motion prior[END_REF] regularize the problem by encouraging a locally rigid 3D motion field, outperforming TV regularization. Furthermore, other methods simultaneously solve the 3D surface and motion [START_REF] Neumann | Spatio-temporal stereo using multi-resolution division surfaces[END_REF][START_REF] Fukurawa | Dense 3d motion capture from synchronized video streams[END_REF]. Another possibility is to work in the scene domain, and to track 3D points or surface elements [START_REF] Carceroni | Multi-view scene captured by surfer sampling: From video streams to non-rigid 3D motion[END_REF][START_REF] Devernay | Multi-camera scene flow by tracking 3D points and surfels[END_REF]. Carceroni and Kutulakos [START_REF] Carceroni | Multi-view scene captured by surfer sampling: From video streams to non-rigid 3D motion[END_REF] model the scene as a set of surfels but it requires a well-controlled lighting and acquisition setup, and because its complexity the scene flow solution is only suitable in a limited volume. Rather than computing a dense scene flow, Devernay et al. [START_REF] Carceroni | Multi-view scene captured by surfer sampling: From video streams to non-rigid 3D motion[END_REF] directly get a set of 3D trajectories from which the scene flow is derived. However, this method suffers from drifts problems and its proposed point visibility handling is a difficult task.

When a depth camera is available, the sensor provides structure information and surface estimation is not needed. Spies et al. [START_REF] Spies | Dense range flow from depth and intensity data[END_REF] estimate the scene flow by solving for the optical flow and range flow. Lukins and Fisher [START_REF] Lukins | Colour constrained 4d flow[END_REF] extend this approach to multiple color channels and one aligned depth image. In these approaches the 3D motion field is computed by constraining the flow in intensity and depth images of an orthographically captured surface, so that, the range flow is not used to support the optical flow computation. Letouzey et al. [START_REF] Letouzey | Scene flow from depth and color images[END_REF] directly estimate the 3D motion field using photometric constraints and a global regularization term without fully exploiting the information given by the depth sensor. Recently, Hadfield and Bowden [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF] estimate the scene flow by modeling moving points in 3D using a particle filter, reducing the over-smoothing caused by global regularization. However, this method requires a lot of computational time since a large number of motion hypotheses must be generated and tested for each 3D point.

Our approach

Similar to [START_REF] Letouzey | Scene flow from depth and color images[END_REF][START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF], we estimate the scene flow using a pair of aligned intensity and depth sequences. Although, rather than computing a dense scene flow we get a set of 3D motions by tracking in the image domain using a coarse-to-fine procedure. The work in this paper is inspired by that of Devernay et al. [START_REF] Devernay | Multi-camera scene flow by tracking 3D points and surfels[END_REF], in which a sparse scene flow is derived from 3D trajectories using several cameras. In our approach, instead of tracking 3D points we use a Lucas-Kanade framework [START_REF] Baker | Lucas-Kanade 20 years on: A unifying framework[END_REF] to solve for a local scene flow using constraints in intensity and depth data.

Previous works [START_REF] Spies | Dense range flow from depth and intensity data[END_REF][START_REF] Lukins | Colour constrained 4d flow[END_REF] solve at the same time for the optical flow and range flow assuming an orthographic camera, however, under this approach the estimated depth velocity can not be included to constraint the optical flow computation. Instead, we directly compute a local scene flow by tracking small surface patches in intensity and depth data. As in [START_REF] Vogel | 3D scene flow estimation with a rigid motion prior[END_REF], we assume that the scene is composed of independently, but rigidly, moving 3D parts avoiding the use of smoothness constraints in 2D. Thus, considering a 3D local rigidity of the scene, we model the image flow induced by the surface motion by using a rigid translation flow model. This model allows the constraint of the 3D motion field in the image domain. In this way we are able to solve for the scene flow that best explains the observed intensity and depth data for each interest region on the image.

Previous Lucas-Kanade methods use a 2D warping [START_REF] Baker | Lucas-Kanade 20 years on: A unifying framework[END_REF]. Unlike them, we model the image flow as a function of the 3D motion vector with help from a depth sensor, improving the accuracy of the optical flow and solving directly for the scene flow. Besides, without expecting a planar surface patch as in surfels based techniques [START_REF] Carceroni | Multi-view scene captured by surfer sampling: From video streams to non-rigid 3D motion[END_REF][START_REF] Devernay | Multi-camera scene flow by tracking 3D points and surfels[END_REF], this motion model allows the constraint of scene flow in intensity and depth images. In order to treat with large displacement the scene flow can be propagated in a coarse-to-fine strategy.

Incorporating depth data our approach improves tracking precision in the image domain that allows at the same time the computation of the scene flow. Because we solve directly for the scene flow by performing tracking in the image domain, this method can be directly used to extract accurate 2D or 3D trajectories, initialize/refine other scene flow methods or define scene flow based descriptors for motion analysis.

Paper structure

The remainder of this paper is organized as follows. We begin in Section 2 with the definition of a motion model that allows the constraint of the 3D motion vector in the image domain. In Section 3 we describe how this motion model can be used, in a Lucas-Kanade framework, to solve for the local scene flow using constraints from the intensity data. In Section 4, we extend this formulation to include constraints from depth data. In Section 5 we present the experimental results and we discuss the major conclusions that can be derived from them.

Pixel motion model

In order to constrain the scene flow in the image domain, it is required a model to explain the image flow induced by 3D motions in the scene. We consider a fixed camera observing a scene composed by locally-rigid 3D parts.

The instantaneous motion, relative to the camera, of a rigid surface in the scene can be decomposed into two components: a translation velocity V = (V X , V Y , V Z ) and an angular velocity W = (Ω X , Ω Y , Ω Z ). The camera frame is defined with its origin at the optical center and its (X, Y, Z) axes respectively in the direction of the image axes and the optical axis, with positive Z pointing in the direction of sight. Let X = (X, Y, Z) be coordinates at time t -1 of a surface point in the camera reference frame and let X ′ = (X ′ , Y ′ , Z ′ ) be the corresponding coordinates at time t. If between t -1 and t the surface performs a rotation W followed by a translation induced by velocity V then

X ′ = RX + V, (1)
where the rotation matrix R can be approximated (assuming small values of W [START_REF] Fang | Solving three-dimensional small-rotation motion equations[END_REF]) by

R =           1 -Ω Z Ω Y Ω Z 1 -Ω X -Ω Y Ω X 1           . (2)

Rigid translation flow model

Let x = (x, y) be the projection of a surface point X on the image plane, if the camera matrix M is given by

M =           f x 0 c x 0 f y c y 0 0 1           , (3)
then x = (X f x /Z) + c x and y = (Y f y /Z) + c y (we suppose in the rest of this paper that nonlinear distortion was removed from the images). In a similar way the image coordinates

x ′ = (x ′ , y ′ ) = M(X ′
) is the projection of the point X ′ , where M is the projective function derived from (3). The 3D movement of the surface generates a motion of its projection. Let (u, v) be the image flow (an element of the 2D motion field) induced on pixel x by rotation and translation of the surface, then

u = x ′ -x = f x X -YΩ Z + ZΩ Y + V X Z -XΩ Y + YΩ X + V Z - X Z (4)
and

v = y ′ -y = f y Y -XΩ Z + ZΩ X + V Y Z -XΩ Y + YΩ X + V Z - Y Z . (5)
The image flow induced by the 3D motion does not necessarily correspond with the optical flow, which is defined as the apparent motion of brightness patterns in the image. We define the Rigid Translation Flow Model assuming that i) the contribution of the inter-frame rotation is negligible and ii) the Z component of the translational velocity is very small w.r.t. Z. Starting from ( 4) and ( 5), we first neglect the rotation term W so that the image flow can be written as:

u = f x X + V X Z + V Z - X Z = 1 Z f x V X -(x -c x )V Z 1 + V Z /Z (6)
and

v = f y Y + V Y Z + V Z - Y Z = 1 Z f y V Y -(y -c y )V Z 1 + V Z /Z . (7)
Now, assuming that |V Z /Z| ≪ 1, the image flow induced on a pixel (x, y) by the surface translation is modeled by

u v = 1 Z 1 0 -x 0 1 -y           V X V Y V Z           , (8)
where, for brevity and without loss of generality, we have considered the focal lengths as the unit and the optical center at the image origin. In general, the motion of each pixel can be expressed as a function of its depth Z, its current image position x, the surface motion V and the intrinsic camera matrix M.

The resulting image flow in expression [START_REF] Letouzey | Scene flow from depth and color images[END_REF] agrees with that of Longuet [START_REF] Longuet-Higgins | The interpretation of a moving retinal image[END_REF] for the translational component of the instantaneous velocity of a retinal image point. The rigid translation model ( 8) can be used to describe the flow induced on the image for all visible points of a rigid surface performing a 3D translation V.

Other motion models

The inter-frame image flow induced by the 3D motion of a rigid surface has been modeled in the literature using different assumptions. The instantaneous velocity of a retinal point (x, y) is modeled in [START_REF] Longuet-Higgins | The interpretation of a moving retinal image[END_REF] as [START_REF] Li | Action recognition based on a bag of 3D points[END_REF] with (u, v) = (dx/dt, dy/dt), and (V X , V Y , V Z ) and (Ω X , Ω Y , Ω Z ) the instantaneous translation vector and angular velocities, respectively. Horn et al. [START_REF] Horn | Direct methods for recovering motion[END_REF] use this instantaneous velocity model to describe the inter-frame pixel motion, where velocities become displacements between t -1 and t, and the optical flow is defined as (u, v) = (x ′x, y ′y). Adiv [START_REF] Adiv | Determining three-dimensional motion and structure from optical flow generated by several moving objects[END_REF] shows that equations ( 9) and ( 10) can be used to approximate the image flow defined by ( 4) and ( 5) under the assumptions that the view of field of the camera is not very large, and V Z /Z ratio and rotation velocities are very small. This model is named Rigid Body Model in the hierarchy classification of motions proposed by Bergen et al. [START_REF] Bergen | Hierarchical modelbased motion estimation[END_REF], and it is characterized by 6 degrees of freedom which are functions of the 3D motion and the depth Z.

u = 1 Z (V X -xV Z ) -xyΩ X + 1 + x 2 Ω Y -yΩ Z (9) v = 1 Z (V Y -yV Z ) -1 + y 2 Ω X + xyΩ Y + yΩ Z
If the optical flow corresponds to the projection of a planar surface k

X X + k Y Y + k Z Z = 1, the plane parameters (k X , k Y , k Z )
constrain the flow induced by the 3D motion of the surface. This optical flow model is called Planar Surface Flow [START_REF] Bergen | Hierarchical modelbased motion estimation[END_REF] and it is expressed as a function of 8 parameters in [START_REF] Adiv | Determining three-dimensional motion and structure from optical flow generated by several moving objects[END_REF] as

u = a 1 + a 2 x + a 3 y + a 7 x 2 + a 8 xy v = a 4 + a 5 x + a 6 y + a 7 xy + a 8 y 2 , (11)
where coefficients {a 1 , ..., a 8 } are functions of the motion parameters

{(V X , V Y , V Z ), (Ω X , Ω Y , Ω Z )} and the surface parame- ters (k X , k Y , k Z )
. This 8 DOF model is also known as the Homography Model in [START_REF] Baker | Lucas-Kanade 20 years on: A unifying framework[END_REF].

In [START_REF] Bergen | Hierarchical modelbased motion estimation[END_REF] the surface is considered to be far from the camera and rotation components Ω x and Ω y are assumed to be zero, which leads to the Affine Flow Model, defined as

u = a 1 + a 2 x + a 3 y v = a 4 + a 5 x + a 6 y, ( 12
)
In this case the induced flow is modeled by the coefficients {a 1 , ..., a 6 } which are functions of the depth Z, the motion parameters (V X , V Y , V Z ) and the rotational component Ω Z . Finally, the simplest model is defined assuming negligible angular velocities and an orthographic camera model, in which Z displacements do not affect the projection of the 3D point on the image. In this model the image flow is given by u = a 1 and v = a 2 where a 1 and a 2 are functions of V X and V Y , respectively.

Locally-rigid tracking approach

The rigid translation model allows the constraint of the scene flow in the image domain. Hence, the scene flow problem can be formulated as finding the 3D motion field that best explains the observed intensity data, exploiting the 2D parameterization. Assuming a scene composed of independently but locally-rigid 3D parts, we state below the scene flow computation inspired by the Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] formulation for local optical flow.

Lucas-Kanade framework

The goal of Lucas-Kanade algorithm is to align a template image T (x) to an input image I(x), so that, it allows to compute optical flow or to track an image patch between two frames. Following [START_REF] Baker | Lucas-Kanade 20 years on: A unifying framework[END_REF], this problem can be stated as finding the parameter vector P = (p 1 , ..., p n ) T which minimizes a squared sum of intensities between the template T an the current image I:

P = arg min P x [I (W(x; P)) -T (x)] 2 , (13)
where the warp function W(x; P) maps each template pixel x to a pixel on the image. The warp function can be defined using any motion model, e.g., one of those presented in Section 2.

Brightness consistency and locally-rigid warp

Under brightness constancy assumption, points X at time t -1 and X ′ = X + V at time t are projected with the same intensity on the image according to

I t-1 ( M(X)) = I t ( M(X ′ )), ( 14
)
where M is the projective function that maps points in the space to the image plane. Hence, if I t (x) is the intensity of the image pixel x at time t , the brightness consistency can be written in the image domain as

I t-1 (x) = I t (x ′ ), (15)
with x and x ′ corresponding to the projections of 3D points X and X ′ , respectively. Let T stand for the previous frame I t-1 (intensity template) and I stand for the current frame I t , then for a set of visible points S of the rigid surface, under translation V and satisfying the brightness constancy assumptions, we have:

X∈S I M (X + V) -T M(X) 2 = 0. ( 16
)
If the set s is the projection of S on the image and W(x; V) is a warp function mapping each pixel x off the image T to the corresponding pixel x ′ on the image I, [START_REF] Li | Multi-scale 3D scene flow from binocular stereo[END_REF] becomes

x∈s [I (W(x; V)) -T (x)] 2 = 0. ( 17
)
The warp function that satisfies (17) can be defined as

W(x; V) = x + ∆(x; V) = x ′ (18)
with the delta function modeling the image flow induced by translation V. Following (8) the image flow induced over each surface pixel is given by:

∆(x; V) = 1 Z(x) f x 0 c x -x 0 f y c y -y           V X V Y V Z           , (19)
where Z(x) is the depth of pixel x (Z component of X).

Tracking in the intensity image

We assume a locally-rigid scene where 2D motions on a image region are generated by the translational motion of a rigid surface. In this case, the warp function given by equation [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF] allows to estimate the 3D motion in a Lucas-Kanade formulation, where the parameter vector P corresponds to the 3D motion vector V that describes the surface translation.

To get a reliable estimation of the 3D motion vector the image region must be sufficiently large to constrain the solution, yet the larger the region of summation the more likely it is to contain multiple motions. Besides, the brightness constancy assumption could be violated due to factors as noise sensor, illumination changes, specular surfaces, etc. To reduce the influence of outliers we use the function ψ(x 2 ) = √ x 2 + ǫ 2 [START_REF] Brox | High accuracy optical flow estimation based on a theory for warping[END_REF], a differentiable variant of the L 1 -norm. Therefore, we formulate the tracking problem as finding the velocity vector V that minimizes

x ψ E I (x; V) 2 , ( 20
)
where E I (x; V) = I (W (x; V)) -T (x) stands for the intensity difference image. In our approach, we assume that all template pixels belong to the same rigid surface in the scene, which performs a translational motion between consecutive frames. Minimization of expression ( 20) is a nonlinear optimization problem, which can be solved by IRLS [START_REF] Green | Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives[END_REF]. Considering that an initial estimate of V is known and using the first order Taylor expansion on the intensity function I, equation ( 20) becomes the problem of finding the incremental ∆V that minimizes

x ψ        E I (x; V) + ∇ I ∂W ∂V ∆V 2        , (21)
where ∇ I = (∂I/∂x, ∂I/∂y) is the row vector gradient evaluated at W (x; V) and the term ∂W/∂V is the Jacobian J of the warp. If W (x; V) = (W x , W y ) T the Jacobian is given by:

J =           ∂W x ∂V X ∂W x ∂V Y ∂W x ∂V Z ∂W y ∂V X ∂W y ∂V Y ∂W y ∂V Z           = 1 Z(x)           f x 0 c x -x 0 f y c y -y           . (22)
Finding the minimum of expression [START_REF] Valgaerts | Joint estimation of motion, structure and geometry from stereo sequences[END_REF] requires an iterative solution. Taking the partial derivative with respect to ∆V gives:

2 x Ψ (x; V; ∆V) (∇ I J) T (E I (x; V) + (∇ I J)∆V), (23)
where for brevity Ψ (x; V; ∆V) = ψ ′ (E I (x; V) + (∇ I J)∆V) with ψ ′ (x) the derivative of the robust norm. At the minimum of (21), equation ( 23) is zero, so that, the incremental scene flow ∆V can be computed by the following iterative procedure:

1. Initialize: ∆V = 0. 2. Compute Ψ (x; V; ∆V) and then the velocity update

∆V = -H -1 x Ψ (x; V; ∆V) (∇ I J) T E I (x; V), (24)
where H, the Gauss-Newton approximation of the Hessian, is given by:

H = x Ψ (x; V; ∆V) (∇ I J) T (∇ I J), (25)
3. Update step: V ← V + ∆V.

4. If ∆V < ǫ stop, otherwise goto 1.

Over each iteration the Hessian matrix can be expressed as

H = x ψ ′ I (x; V; ∆V) Z(x) 2           I 2 x I x I y I x I Σ I x I y I 2 y I y I Σ I x I Σ I y I Σ I 2 Σ           , (26)
with I Σ = -(xI x + yI y ). A reliable solution of [START_REF] Vogel | 3D scene flow estimation with a rigid motion prior[END_REF] requires that matrix H given by ( 26) must be above of the noise of the intensity images and well conditioned. To construct H each 3 × 3 gradient based matrix is weighted by the square inverse depth of the pixel. Since the depth of each template pixel is required to computed the solution only template pixels with valid depth measures should be considered.

Tracking in intensity and depth

In the previous Section we have solved for local scene flow by using a tracking approach in a Lucas-Kanade framework. Thus, assuming a local rigidity of the scene, the parameter vector of the warp function corresponds to the 3D motion vector. The depth value of each image pixel is only used to compute the image flow induced by the estimated scene flow. However, in this approach the motion vector is constrained using only brightness data and the information from the depth sensor is not fully exploited.

Taking advantage of the structure information captured by the depth sensor we propose to incorporate a constraint based on the observed depth velocity. The new constraint is computed from the squared difference between the estimated depth of each template pixel, given by V Z , and the current depth measure provided by the sensor.

Depth velocity constraint

Since the scene is assumed to be composed by locally-rigid 3D parts performing translation, the motion of a set of 3D points belonging to a rigid surface can be expressed as X ′ = X + V. Therefore, the depth of each surface point between consecutive frames, is related by the Z component of the local scene flow as

Z ′ = Z + V Z . If Z t (x)
is the depth of the image pixel x at time t, the depth data must satisfy:

Z t-1 ( M(X)) + V Z = Z t ( M(X ′ )), ( 27
)
where M is the projective function and, x and x ′ correspond to the projections of 3D points X and X ′ , respectively. Let T Z stand for the previous depth frame Z t-1 (depth template) and Z stand for the current frame Z t . Then for a set of visible points S of a rigid surface we have:

X∈S Z M (X + V) -T Z M(X) + V Z 2 = 0. ( 28
)
Using the warp function ( 18) equation ( 28) can be expressed in the image domain as follows:

x∈s [Z (W(x; V)) -(T Z (x) + V Z )] 2 = 0, ( 29
)
where s is the projection of set S on the image.

Tracking algorithm in intensity and depth

Using brightness and depth velocity constraints the scene flow computation can be formulated as finding de 3D motion vector that best explains the observed intensity and depth data over an image region. Therefore, we formulate the local scene flow as the optimization problem given by:

V = arg min V x E I (x; V) 2 + λE Z (x; V) 2 , (30)
where

E I (x; V) = I(W(x; V)) -T (x), (31)
E Z (x; V) = Z (W (x; V)) -T Z (x) + D T V , (32)
and λ = σ 2 I /σ 2 Z , with σ 2 I and σ 2 Z the noise variance in intensity and depth sensors, respectively. The row vector D T = (0, 0, 1) isolates the Z component of the scene flow.

The first term E I (x; V) 2 is the intensity term which measures how consistent is the image flow (induced by V) of each template pixel with the input intensity images. The second term E Z (x; V) 2 is the depth term which measures the consistency of the estimated scene flow V with the input depth data. A reliable solution of the optimization problem (30) ensures a scene flow consistent with both intensity and depth data.

Assuming an initial estimation of V, each optimization step searches for ∆V which minimizes

x E I (x; V + ∆V) 2 + λE Z (x; V + ∆V) 2 . ( 33
)
In order to solve for the incremental ∆V, (33) is linearized using the first order Taylor expansions on I and Z

x

[E I (x; V) + (∇ I J)∆V] 2 +λ E Z (x; V) + ∇ Z J -D T ∆V 2 ( 34
)
where ∇ I = (∂I/∂x, ∂I/∂y) and ∇ Z = (∂Z/∂x, ∂Z/∂y), both evaluated at W (x; V), and with J the Jacobian of the warp function given by [START_REF] Neumann | Spatio-temporal stereo using multi-resolution division surfaces[END_REF]. Now, taking the partial derivative of (34) with respect ∆V, setting this expression to zero and solving for ∆V, the update rule can be stated as

∆V = -H -1 x (∇ I J) T E I (x; V)+λ ∇ Z J -D T T E Z (x; V) (35)
where matrix H is given by

H = x (∇ I J) T (∇ I J) + λ ∇ Z J -D T T ∇ Z J -D T . ( 36
)
The Hessian matrix can be expressed as

H = x 1 Z(x) 2           I 2
x + λZ 2

x I x I y + λZ x Z y I x I Σ + λZ x (Z Σ -1)

I x I y + λZ x Z y I x I Σ + λZ x (Z Σ -1) I 2 y + λZ 2 y I y I Σ + λZ y (Z Σ -1) I y I Σ + λZ y (Z Σ -1) I 2 Σ + λ(Z Σ -1) 2           , ( 37
)
with I Σ = -(xI x + yI y ) and Z Σ = -(xZ x + yZ y ). A reliable solution of [START_REF] Horn | Direct methods for recovering motion[END_REF] requires that matrix H given by ( 37) must be both above of the noise of the images (intensity and depth) and well conditioned. Unlike Lucas-Kanade approach with a pure translation motion model, where the aperture problem can be analyzed using the 2×2 gradient covariance matrix of the image [START_REF] Shi | Good features to track[END_REF], equation [START_REF] Scharstein | High-accuracy stereo depth maps using structured light[END_REF] state a new formulation. Now intensity and depth data are combined to determine the local scene flow and the image motion.

Implementation details

In order to compute the local scene flow at a given pixel x 0 , the proposed approach assumes an aligned pair of intensity and depth sequences, I(x, t) and Z(x, t), respectively. Taking the former frames, the intensity template T (x) and the depth template T Z (x) are defined by selecting a (2ω x + 1) × (2ω y + 1) neighborhood Ω(x 0 ), centering at x 0 . The initial estimate of V is set to zero and thereby in the first iteration the warp function obeys W(x; V) = x for all x ∈ Ω(x 0 ). In formulation [START_REF] Horn | Direct methods for recovering motion[END_REF], we have not used a robust norm in order to get a closed solution for ∆V. However in our implementation we apply the same variant of the L 1 -norm that in [START_REF] Vogel | 3D scene flow estimation with a rigid motion prior[END_REF] to each one of the terms:

V = arg min V x∈Ω(x 0 ) ψ [I(W(x; V)) -T (x)] 2 + λ ψ Z (W (x; V)) -T Z (x) + D T V 2 (38)
with ǫ = 0.001. Setting parameter λ to be zero, the intensity and depth based objective function [START_REF] Bouguet | Pyramidal implementation of the Lucas-Kanade feature tracker[END_REF] becomes the only intensity tracking formulation of Section 3.3. Since it is possible that the depth sensor does not provide a measure for each pixel on Ω(x 0 ), only pixels with a valid depth measure are taken into account for both Z (W (x; V)) and T Z (x).

Coarse-to-fine estimation. The proposed algorithm solves for the scene flow estimation problem as local nonlinear optimization by assuming an initial estimate of V at pixel x. In order to deal with long-range motion, a coarse-to-fine strategy is required. We perform a multi-resolution technique to estimate scene flow under large displacement, where the local 3D motion estimated at a coarser level is used to locally warp the input intensity and depth images toward the intensity and depth templates at the next finer level.

We construct an image pyramid with a downsampling factor of 2. For the intensity images we build a Gaussian pyramid where the standard deviation of the Gaussian anti-aliasing filter is set to be 1/2. In order to not propagate invalid depth measures, the depth pyramid is constructed by averaging pixels in non-overlapped neighborhoods of 2 × 2 where only pixels with valid depth are used. For both intensity and depth pyramids, each level is recursively downsampled from its nearest lower level. Using a pyramid with levels L = 0, 1, ..., M, where L = 0 is the original resolution, the local scene flow estimation starts from the highest level M with the initial condition V = 0. In each pyramid level L the computation is performed over the image neighborhood given by Ω(x/2 L ) and the warp function [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF] is modified by scaling the focal length and the camera center by the factor 2 L . The computed scene flow is directly propagated to the next lower level.

Experiments

Middlebury datasets

In order to evaluate the performance of our method we have conducted experiments using an existing scene flow benchmark. The proposed algorithm that allows the constraint of the scene flow in intensity and depth is named SF ID and its version using only intensity constraints (λ = 0) is SF I . We compare our method with three versions of the Lukas-Kanade tracker (KLT) as well as with other scene flow algorithms.

As in [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF][START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF][START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF] Middlebury stereo datasets [START_REF] Scharstein | High-accuracy stereo depth maps using structured light[END_REF], Cones and Teddy, were used for the experiments. Using images of one of these datasets is equivalent to a fixed camera observing a moving object along X axis. We took image 2 of each dataset as the first frame and image 6 as the second frame, both in quartersize. Parameters of the camera setup were estimated and the depth data was generated from the disparity map of each image.

The ground truth for the scene flow is constant and given by the baseline of the stereo setup. On the other hand, the ground truth for the optical flow is given by the disparity map (used as depth image) from frame 1, as show in Figure 1. In this dataset all movements, both in the 3D scene and on the image, are purely horizontal.

Error measures

In order to measure errors in 2D we compute the root mean squared error of the optical flow (RMS OF ) and the average angle error (AAE OF ). Besides, as in [START_REF] Scharstein | High-accuracy stereo depth maps using structured light[END_REF], we use the statistic RX of RMS OF to observe the percentage of pixels that have an error measure above X pixels, for the values X = 1.0 and X = 5.0. Since errors on the image do not necessarily correspond with errors in the scene [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF], we evaluate both 2D and 3D errors in the experiments. In order to asses errors in the scene flow we compute the normalized root mean squared error of the 3D flow vector (NRMS V ). The NRMS V definition is close to that of [START_REF] Vogel | 3D scene flow estimation with a rigid motion prior[END_REF], but we normalize the rms error by the (constant) magnitude of the scene flow ground truth which is the same for both datasets. This normalization allows calculating the error as percentage of the ground truth. As in the 2D case, we compute the statistic RX of NRMS V , now for the percentages X = 5% and X = 20%.

Unlike optical flow, there is no standard metric to assess scene flow algorithms. Each author uses an error metric with or without normalization. In order to compare our method with other scene flows approaches we choose the normalized root mean squared error of the optical flow (NRMS OF ) because it is available or can be derivate from the selected previous works. We normalize our results by the optical flow range of each dataset, given by 42.5 for Teddy and 48.5 for Cones.

Comparison with sparse optical flow methods

Lucas-Kanade algorithm is the most frequently used method to compute sparse optical flow and to get 2D trajectories. Even different motions models can be used in this framework (e.g., affine, homography) the pure translation model [START_REF] Shi | Good features to track[END_REF] is the most successfully used. Therefore, we select for comparison the C pyramidal implementation of KLT by Bouguet [START_REF] Bouguet | Pyramidal implementation of the Lucas-Kanade feature tracker[END_REF] and our own pyramidal implementation with a robust norm (KLT R ). We also implemented a pyramidal version of the orthographic intensity and depth tracker [START_REF] Spies | Dense range flow from depth and intensity data[END_REF] provided of a robust norm, which we call (KLT O ). All algorithms were configured to use a fixed window size of 11 × 11, in a Gaussian pyramidal decomposition of 5 levels. In the experiments we performed the computation over a regular grid covering the 85% of the image area.

Results over non-occluded regions are presented in Table 1 for the optical flow. The proposed algorithm SF ID and its variant SF I outperform other trackers in the estimation of the optical flow magnitude. Errors in orientation are very close. It is important to note that using the depth information as proposed by [START_REF] Spies | Dense range flow from depth and intensity data[END_REF] does not improve the optical flow estimation, indeed the KLT R without including depth information performs better. Statistic R5.0 shows that the number of outliers (above 5 pixels) is reduced when the proposed pixel motion model is used even under the large displacements of the dataset.

The most direct way to compute scene flow when a depth camera and an optical flow algorithm are available is by inferring the 3D motion using the resulting image motion and the provided depth data. We follow this procedure to estimate the scene flow for each optical flow method. Results for the scene flow are presented in Table 2. The SF ID algorithm achieves the most accurate results. Statistics R5% and R20% allows to do a more detailed comparison between the methods since NRMS V is highly sensitive to outliers. As can be seen from Tables 1 and2, even small pixel deviations in the image domain can have a strong influence in the 3D error computed in the scene. Comparing the results of SF ID and KLT O , it is clear that the pro- posed warp function allows to estimate a more accurate scene flow than the pure translation model. In order to observe the performance in specific regions, the scene flow is computed on textured and untextured regions, as well as on depth discontinuities. Points for texture analysis are chosen by observing the minimum eigenvalue (λ min ) of the Hessian matrix of I on a region. Higher values of λ min are used to select textured (Tex) regions while lower values of λ min define untextured (Utex) regions. Regions with depth discontinuities (DD) are selected by finding higher values in the depth image gradient. For each of these regions the averaged error on Teddy and Cones images is presented in Table 3. For all regions our method outperforms the robust norm KLT version and results show that better regions to track correspond to textured regions avoiding strong depth discontinuities. The accuracy is reduced on DD regions since the number of outliers increases due to occluded regions and unmeasured depth points. Although scene flow error R5% is strongly affected on DD, the use of depth data reduce the number of outliers in the image domain w.r.t. OF R . In average, errors on untextured regions are lower but the percentage of points with inaccurate optical flow or scene flow is the highest, as can be seen in Table 3 for R1.0 and R5%. Finally, on textured regions the NRMS V error is increased due to the presence of depth discontinuities, however, observing R1.0 and R5% it is evident that precision on this regions is higher, both in optical flow and scene flow.

Comparison with other scene flow methods

There is not a standard procedure or error measure to compare scene flow methods. Therefore, in order to compare the proposed SF ID algorithm we compute the NRMS OF and AAE OF in T eddy and Cones datasets, as in [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF], [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF] and [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF] the comparison with dense methods we compute the scene flow for all pixels. Results are presented in Table 4.

The proposed method SF ID outperforms [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF] which is based on particle filtering using intensity and depth. The particle filter is benefited from the constant scene flow of the datasets, since most likely hypothesis are diffused over the whole image. On the other hand, comparison with stereo-based techniques is not straightforward since they use closer images of the Middlebury datasets and the depth information (disparity) must be estimated. In [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF] and [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF], images 2 and 6 are taken as the stereo pair at time t -1 and images 4 and 8 correspond to the stereo pair at time t. Accordingly, the optical flow ground truth is half of the disparity and there are fewer occluded regions. Moreover, since [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF] uses a total variation regularization in 3D this algorithm is also favored by the constant scene flow of the dataset. Results of the SF I algorithm are good enough even it does not use a global regularization as in [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF] and [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF], or a large set of hypotheses as in [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF]. In order to get more accurate estimation the scene flow computation must be concentrated in good regions to track.

A non-optimized version of the proposed local scene flow algorithm processed the Middlebury dataset, on a single core desktop machine in under 5 s, as opposed to 5 h for [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF] or 10 min for [START_REF] Hadfield | Kinecting the dots: Particle based scene flow form depth sensors[END_REF] (run time was not reported in [START_REF] Basha | Multi-view scene flow estimation: A view centered variational approach[END_REF]).

Kinect images

Some experiments were performed with image sequences from a Microsoft Kinect sensor where intensity and depth images were accessed using the libfreenect library in C++. We used the Kinect calibration toolbox [START_REF] Herrera | Accurate and practical calibration of a depth and color camera pair[END_REF] to get intrinsic and extrinsic parameters of the depth and RGB camera pair and to perform the image alignment. Aligned pairs of intensity and depth images are shown in Figure 2. Depth data is encoded using gray levels, where lighter pixels correspond to closer points from the sensor. Unmeasured regions are encoded in black and they correspond to occluded or out of range regions to the depth camera, or to points belonging to reflective surfaces.

In the first experiment we computed a local scene flow for each pixel having a valid depth measure and being within 2 meters from the camera. For the computation we used a window size of 11×11 in a pyramidal decomposition of 2 levels. Figure 2 shows the results of the motion field estimation between a pair of images where a person is performing a motion with both hands. In the sequence, the left (on the image) hand is moving Points on the hand surface present approximately the same scene flow while the optical flow magnitude is function of the depth. Using only the optical flow is not possible to distinguish the different types of movement that each hand performs. This ambiguity can be resolved by means of the scene flow, e.g. using its Z component as illustrated in Figure 2(e). Since the scene flow is computed locally a reliable solution can not be found over untextured regions, e.g., the t-shirt, or in depth discontinuities where most of depth data is missing. However, the solution on slightly textured regions, as the hands, is good enough. Figure 3 shows an sparse projection of the scene flow on an image region containing a hand, where missing values correspond to regions without enough depth information.

In the second experiment we track a set of 4 image points selected manually, over a sequence of 200 frames. Figure 4(a) shows the chosen points which are located in both arms on slightly textured regions. Considering a neighborhood around each point, a local scene flow is computed between consecutive frames to determine the new location of the interest point. Although the skin color is not textured enough, the tracking can be performed with help from the depth data. Some images of the tracking experiment are presented in Figure 4(a)-(f).

Conclusions

We have proposed a novel approach to compute local scene flow by tracking surface patches in intensity and depth. Using a rigid translation flow model we state the scene flow computation as a 2D tracking problem, achieving the computation of the 3D motion vector that best explains the provided intensity and depth data. Our solution is formulated in a Lucas-Kanade framework provided of a L 1 -norm approximation for each data term, allowing to deal with outliers and to perform a coarse-tofine solution. Although we have chosen a specific flow model on the image, using some assumptions, the presented formulation for the scene flow problem is valid with other motion models wherever motion field V = (V X , V Y , V Z ) can be computed from the vector parameter P. Throughout some experiments we demonstrated the validity of our method and we showed that it outperforms other Lucas-Kanade tracker for optical flow and scene flow computation. We also perform comparison with other scene flow techniques with very encouraging results. As we simultaneously solve for the 2D tracking and for the scene flow this method could be used directly in motion analysis tasks to generate accurate 3D trajectories or define scene flow based descriptors. Unlike previous scene flow methods, the proposed approach is "near" real time with 5s processing time per frame.

We are currently exploring a variational formulation of the scene flow computation using intensity and depth in order to improve estimation on untextured regions and those close to strong depth discontinuities. Besides we are investigating how to define scene flow based descriptors to perform action or gestures recognition. Since our method require the inversion of a 3×3 matrix which is function of the gradients of intensity and depth images, we expect to obtain a criterion for selecting good regions to compute its local scene flow.

Figure 1 :

 1 Figure 1: Teddy stereo dataset [37]. (a) Color image, (b) depth image (disparity image in the dataset), (c) optical flow ground truth and (d) flow color coding.

Figure 2 :

 2 Figure 2: Results from a pair of Kinect images. (a-b) frames at times t -1 and t,(c-d) depth images at times t -1 and t, (e) Z component of the scene flow and (f) scene flow projection on the image (optical flow). The scene flow is computed for each pixel within 2 meters from the sensor, results for farther pixels are presented in black as well as the motion estimation in regions where most pixels have no valid depth. Depth changes (Z component of the scene flow) are encoded in a cold-to-warm color map for the range [-2.5,2.5] cm, where the zero velocity is green, blue and magenta colors represent negative velocities (approaching pixels) and red and yellow colors are positives velocities. Optical flow is presented using the color coding shown in Figure1(d)[START_REF] Baker | A database and evaluation methodology for optical flow[END_REF].

Figure 3 :

 3 Figure 3: Scene flow projection on the image.

Figure 4 :

 4 Figure 4: Tracking a set of points by computing local scene flow.

Table 1 :

 1 SF ID SF I KLT KLT R KLT O Results in the image domain: optical flow errors. SF ID SF I KLT KLT R KLT O

		RMS OF 2.71 2.92 7.21	4.18	4.62
	Teddy	R1.0 R5.0	9.54 12.9 40.2 2.50 3.70 21.9 13.25 23.7	28.9 19.1
		AAE OF 1.17 1.38 1.67	1.18	1.48
		RMS OF 2.32 2.31 4.70	5.20	4.02
	Cones	R1.0 R5.0	16.3 16.7 39.9 2.15 4.29 17.6	33.1 17.2	40.3 14.6
		AAE OF 1.14 1.28 1.24	1.84	1.42
		NRMS V 11.4 60.6 74.1	41.2	41.2
	Teddy	R5%	18.6 29.1 40.2	37.2	38.3
		R20%	7.06 12.6 22.2	20.4	23.2
		NRMS V 10.8 51.2 89.9	95.6	93.7
	Cones	R5%	15.6 28.5 35.9	38.6	39.8
		R20%	2.89 6.77 16.0	14.5	14.9

Table 2 :

 2 Results in 3D: scene flow errors.

Table 3 :

 3 Errors by regions.

Table 4 :

 4 Comparison of scene flow algorithms in 2D.

	. To allow

Acknowledgement

Part of this work was previously presented [41] in the 2nd International Workshop on Human Activity Understanding from 3D Data (HAU3D12), which was held on in conjunction with the IEEE Conference on Computer Vision and Pattern Recognition, Providence, 2012.