Dip. Davide Chiarugi
email: chiarugi3@unisi.it

Moreno Falaschi
email: moreno.falaschi@unisi.it

Carlos Olarte
email: carlosolarte@puj.edu.co

Catuscia Palamidessi
email: catuscia@lix.polytechnique.fr

Compositional Modelling of Signalling Pathways in Timed Concurrent Constraint Programming *

The biological data regarding the signalling pathways often consider single pathways or a small number of them. We propose a methodology for composing this kind of data in a coherent framework, in order to be able to investigate a bigger number of signalling pathways. We specify a biological system by means of a set of stoichiometric-like equations resembling the essential features of molecular interactions. We represent these equations by a timed concurrent constraint (ntcc) language, which can deal with partial information and the time for a reaction to occur. We describe a freely available prototypical implementation of our framework.

INTRODUCTION

Cellular signalling pathways consist in groups of interacting proteins belonging to various functional classes, e.g. receptors, adaptor proteins and kinases [START_REF] Devlin | Textbook of Biochemistry with Clinical Correlations[END_REF]. Each pathway is specialized in sensing and transducing particular environmental signals such as growth factors, hormones, cytokines, light and nutrients. Misfunctioning or defects in signalling pathways are often associated with important diseases e.g. diabetes, immune disorders and cancer [START_REF] Devlin | Textbook of Biochemistry with Clinical Correlations[END_REF][START_REF] Finkel | Signal Transduction and Human disease[END_REF]. In living cells individual signalling pathways do not act in isolation. Rather, they cross talk due to the presence of components shared by different pathways or positive and negative feedback loops that form complex interaction networks. Thus, the overall behavior of a cell embedded in a given environment should be seen as the integrated response to a variety of sensed signals coming from the outside [START_REF] Devlin | Textbook of Biochemistry with Clinical Correlations[END_REF][START_REF] Blinov | Complexity and modularity of intracellular networks: a systematic approach for modelling and simulation[END_REF]. Understanding the dynamics underlying the functioning of whole cellular signalling networks is a task that is far from being accomplished. Unfortunately, nowadays wet-lab techniques are still not adequate to cope with this kind of "systemic" investigation. Moreover, the available information results to be heterogenous as it is obtained through different experimental techniques and comes from variable contexts. So, it results particularly difficult to organize the existing information in a coherent framework taking also into account the dynamics of the interactions, in order to gain knowledge at the network level. To address the problem of data integration and of heterogeneity, we present a new methodology for modelling molecular interaction networks, which allows to organize the existing knowledge in a compositional fashion. We aim at exploiting this method for describing and simulating the behavior of a big number of signalling pathways. Our modelling technique takes into account the fact that several features of the biological system may be undetermined or affected by measuring mistakes [START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF]. Our language allows us to represent partial information and to model explicitly the time which is necessary for a reaction to occur. In this paper we use our methodology by modeling and simulating some well known signalling pathways, namely the TNFα, EGF, and insulin signalling pathways.

CONCURRENT CONSTRAINT CALCULI

Concurrent system, i.e. systems whose components act simultaneously and potentially interact with each other, are ubiquitous in several domains and applications, as in biological and physical systems, mobile systems, Internet, etc. Due to their complex forms of interaction, concurrent systems are difficult to specify and reason out. In computer science, process calculi have been proposed to rise this challenge. They provide a mathematical language where concurrent systems can be modelled and their behaviour can be formally described and predicted. Timed Concurrent Constraint Programming (ntcc) [START_REF] Nielsen | Temporal concurrent constraint programming: Denotation, logic and applications[END_REF] is a simple but powerful model for concurrency aiming at modeling reactive systems, i.e., those whose components interact among each other and with the environment. Here, interactions are modeled by means of constraints accumulated in a common store. A constraint c, e.g., x ≥ 10, represents a piece of (partial) information upon which processes may act. Processes in ntcc can change the state of the system by telling information, and synchronize by asking information: A process tell(c) adds c to the store, thus making it available to the other processes. A process i∈I when ci do Pi non-deterministically chooses one of the Pi whose corresponding guard ci can be deduced from the store. The chosen alternative, if any, precludes the others. A process P Q denotes P and Q running concurrently possibly "communicating" via the common store. Processes in ntcc can be also executed along time-units or time-intervales: A process next P delays the execution of P to the next time-unit, and the replication ! P means unboundedly many copies of P but one at a time. We refer the reader to [START_REF] Nielsen | Temporal concurrent constraint programming: Denotation, logic and applications[END_REF] for a detailed account of the syntax and the operational semantics of the ntcc calculus.

A COMPOSITIONAL MODEL

A biochemical pathway can be represented as a set of interconnected biochemical reaction in which the product of a reaction is the reactant of another one. A signaling pathway is a biochemical pathway supporting the transduction of signals in a biological cell: molecules present in the external environment can affect the cellular behaviour linked to a specific receptor on the cell membrane and triggering the biochemical reactions of the receptor-dependent signaling pathways. For example, the equation

Insulin + Insulin_Receptor Insulin_Receptor_P
represents the reaction of one insuline molecule and its receptor (IR). This reaction causes the (auto)phosphorilation of the receptor molecule, and triggers the following events of the signal transduction pathway. Here we abstracted away various details regarding chemical features, such as reaction rate dependence from the temperature. These approximations are consistent with the in-vitro experiments, where the temperature is kept constant. The reaction rate will be considered at simulation time as stochastic parameters. In general, we shall represent the signaling pathway by a finite set of equations r1, ..., rm of the form

rj : i a j i Ai i b j i (1)
The constants a j 1 , ..., a j n and b j 1 , ..., b j n are the stoichiometric coefficients. Therefore, a j 1 A1, a j 2 A2, ..., a j 3 An are reactants that interact (and are consumed) yielding to the products b j 1 A1, b j 2 A2, ..., b j 3 An. We also assume that each equation rj has associated a duration dur(rj) defining the number of time-units required for that reaction to produce the components on the right-hand side. Our idea is to represent this set of equations as ntcc processes. This will provide a runnable specification of the system in which we can formally specify the time required for a reaction to occur. Furthermore, due to the constraint-based nature of ntcc, and the ability of dealing with partial information, we will be able to specify systems where we do not have a complete description of it (e.g., if we only have a partial information about the concentration of the reactants involved). Moreover, models specified in this language can be easily composed due to the parallel composition operator, thus yielding the description of more complex phenomena. Finally, another advantage of using ntcc, is that it is endowed with a logic semantics [START_REF] Nielsen | Temporal concurrent constraint programming: Denotation, logic and applications[END_REF], thus providing a valuable tool for the verification of properties of the modelled system.

The model in ntcc

The model we propose consists of three different components: A process to choose the rule (equation) to be applied in each time-unit; the processes modelling the equations and the processes changing the state of the concentrations of each reactant/product according to the equation applied.

We assume a set of equations as in Equation 1. In the sequel, the variables x1, ..., xn represent the current concentrations of the components A1, ..., An respectively. The process choose below, selects non-deterministically one of the equations (eq = j) s.t. the current concentration of each component is higher than the reactant necessaries for the equation to take place (e.g., x j i ≥ a j i ).

choose def = m j=1 when x j 1 ≥ a j 1 ∧ ... ∧ x j n ≥ a j n do tell(eq = j)
Improvements here can be done by adding the stochastic information about the reaction rate of each equation (if it is known). In this case, the non-deterministic operator is replaced by a probabilistic choice (see e.g., [START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF]).

A reaction (equation) rj is modelled by a process binding the variables x j i-and x j i+ to a j i and b j i respectively. This variables determine how the concentration of the component Ai must be affected due to the application of the equation: a j i units are consumed and b j i units are produced.

equation j def = when eq = j do next tell(x j 1-= a j 1 ∧ ... ∧ x j n-= a j n ) next dur(r j ) tell(x j 1+ = b j 1 ∧ ... ∧ x j n+ = b j n )
Notice that the concentration of the products b j i is incremented dur(rj) time-units later. Finally, the whole system looks like this:

system def = ! (state choose equation 1 ... equation n )
The process state computes the current concentration of the components according to their concentrations in the previous time-unit and the variables x j i+ and x j i-explained above. It also sets the initial concentration of the components that are parameters of the simulation. We omit the definition of this process for the sake of presentation.

A simulation tool: BioWayS

We have implemented a simulation tool based on our model, which we have called BioWayS and which is freely available on the web. This tool is based on a interpreter of the ntcc calculus written in the Oz Languages (http://www. mozart-oz.org/). BioWayS takes as input a text file containing the initial parameters of the simulation as well as the description of the equations. Then, it computes the final stores of each timeunit and outputs the number of equation applied and the concentration of each component. In the following sections we shall show some examples of simulations executed in this tool. More examples and the description of the input and output files can be found at http://lix.polytechnique. fr/~colarte/bioways/.

IN SILICO EXPERIMENTATION

We used our modelling technique to study some interconnected cellular signaling pathways related to three receptors: Tumor Necrosis Factor Receptor I (TNFR1), Insulin Receptor (IR), and the Epidermal Growth Factor Receptor (EGFR) [START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF]. This choice is motivated by the fact that the information regarding these pathways is relatively abundant and can be used to verify the viability of the model comparing them with the output of the simulations. Some aspects of the dynamics of this network have been characterized through wet-lab techniques that allow to measure the quantity (concentration or activity) of a pool of cellular proteins over a time period [START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF].

The model

The set of signalling pathways composing the network indicated above was considered. Using a system-level approach, our aim was to build a model based on the information available in the literature, adequate for describing the measured data and, eventually, to make predictions regarding the modeled system. Our model network is composed by 37 different kind of molecules (nodes) and 48 equations (interactions). Each interaction is rendered by a "reaction rule" resembling the corresponding chemical equation. The input for a simulation run is composed by the list of rules (i.e. the model of the network) and a set of parameters specifying the number of copies for each involved molecule (i.e. the amount of reacting molecules) and the length of the computation (i.e. the time length of the experiment).

For each rule it is possible to specify a parameter indicating the amount of time needed for the corresponding reaction to occur. This parameter corresponds to the first passage time and is evaluated according to [START_REF] Ninio | Alternative to the steady-state method: Derivation of reaction rates from first-passage times and pathway probabilities[END_REF]. Note that to estimate the first passage time for an enzymatically catalysed reaction, it is not necessary to know the details regarding the reaction's mechanism and, thus, the kinetic constants related to each elementary step. Instead, the needed data are the enzyme and substrate(s) concentrations, the enzymesubstrate(s) "affinity constant(s)" and the overall (macroscopic or apparent) rate constant. The first two parameters were taken from the literature or determined heuristically letting their initial amounts ranging on reasonably realistic intervals estimated by comparison with similar cases. The last parameter was estimated using Kinfer (http://www. cosbi.eu/index.php/research/prototypes/kinfer) and literature data. The choice of this approach reflects the need of building a "biochemically consistent" model using correctly the available data to avoid common misconceptions, e.g., to use the apparent rate constant instead of the microscopic rate constant. This mistake is often made in works relying on the Gillespie's Stochastic Simulation Algorithm (SSA) [START_REF] Gillespie | Stochastic simulation of chemical kinetics[END_REF] for the (stochastic) simulation of biochemical pathways. Gillespie's SSA, needs the knowledge of the elementary rate constants, which are often impossible to measure and evaluate. To circumvent this problem, apparent rate constants are typically used. This introduces a heavy approximation with unpredictable effects on the results of simulations.

In our framework, for each step of the computation, BioWayS chooses non deterministically one rule and simulates the occurrence of a chemical reaction. When a reaction occurs, reactant molecules are "consumed" and new copies of other molecules are eventually "produced" according to the corresponding rule. After a computation, initial and final states differ for the number of copies of each molecule.

Experiments and results

The in silico experiments were performed by simulating the model described above through BioWayS. In the first experimental session we tuned the model and tested its viability by comparing the simulations outputs with the corresponding wet-lab data reported in [START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF]. The in silico experiments were performed under different initial conditions mimicking the presence of different combinations of insulin, TNFα and EGF in the extracellular environment. For each combination of these three molecules, simulations differing in time length were performed to obtain time courses of the measured values, i.e., the amount of the various kind of molecules at the end of each computation. Some of these results are presented in Figure 1. We compared the "real" and "virtual" time series through the X 2 test (p > 0.05). In all the tested cases, the X 2 test showed that our results are consistent with wet-lab data.

For further validating our proposal, we studied particular cases of cross-talk amongst the considered signaling pathways. It is known [START_REF] Csehi | Tumor necrosis factor (tnf) interferes with insulin signaling through the p55 tnf receptor death domain[END_REF] that the pathways regulated by TNFR1 and IR interact, negatively influencing each other signaling dynamics. The effects of this cross-talk can be observed through proteomic techniques monitoring the amount of phosphorylated Insulin Receptor Substrate 1 (IRS1). IRS1 is specifically phosphorylated on tyrosine and serine residues. Tyrosine phosphorylation of IRS1 is performed by IR when it is bound to insulin and activates IR-dependent signaling pathways. Phosphorylation on serine residues decreases the activity of IRS1 and prevents tyrosine phosphorilation. This chemical modification occurs when certain signaling pathways, such as TNFR dependent pathways, are active and leads to the inactivation of IR-dependent signaling pathways. While the relationship between IR and IRS1 is structurally well characterized (IRS1 directly interacts with IR) the same cannot be said for TNFR and IRS1. Actually the model presented in Sec. 4.1 does not reproduce insulin/TNFα interference. This may depend on the fact that in [START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF] is used a cell culture line (namely human colon adenocarcinoma cells, ATCC) which, being cancerous cells, may not function as the non-cancerous ones such as adipocytes. Our hypothesis was that our model, being shaped on the findings reported in [START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF], does not mimic "correctly" the insulin-TNFα interactions. Some experimental evidences indicate a possible pathway responsible of this cross-talk [START_REF] Csehi | Tumor necrosis factor (tnf) interferes with insulin signaling through the p55 tnf receptor death domain[END_REF]. To test our hypothesis, we inserted compositionally this pathway in our model. We then performed a new session of in silico experiments by simulating the updated model through BioWayS mimicking the presence of insulin, TNFα or both in the extracellular environment. The results of these experiments (see Figure 2) show that the trend of in silico behavior resembles what happens for the real counterpart.

RELATED WORK AND CONCLUSIONS

Petri Nets (PN), both in their classical version [START_REF] Goss | Quantitative modeling of stochastic systems in molecular biology by using stochastic petri nets[END_REF] and in their stochastic ones [START_REF] Reddy | Qualitative analysis of biochemical reaction systems[END_REF] are one of the first approaches which has been used for modelling living systems. Our formalism should be easier to use as a programming language. Pathway Logic (PL) [START_REF] Talcott | Pathway logic[END_REF] is a symbolic approach to the modelling and analysis of biological systems which is based on rewriting logic [START_REF] Martí-Oliet | Rewriting Logic: Roadmap and Bibliography[END_REF]. Our methodology should have the advantage of modelling the time of reactions and treat in a natural way partial information. The language BIOCHAM was introduced in [START_REF] Fages | Modeling and querying interaction networks in the biochemical abstract machine biocham[END_REF], and was designed for being very close to the classical rules biologists use to describe biochemical reactions. We believe that we can model different sets of reaction rules by exploiting the fact that we do not require precise stoichiometric data. We use constraints for representing partial information. A programming language similar to ours has been used for representing Biological systems in [START_REF] Bockmayr | Using hybrid concurrent constraint programming to model dynamic biological systems[END_REF]. [START_REF] Bockmayr | Using hybrid concurrent constraint programming to model dynamic biological systems[END_REF] considers a language which is suitable for modelling hybrid systems, i.e., system where continuos and discrete time is considered. Some other major differences are as follows. We mainly focus on deriving a simple representation of equations, which can be easily used by non expert users. We model time duration of reactions as well as partial information, like [START_REF] Bockmayr | Using hybrid concurrent constraint programming to model dynamic biological systems[END_REF], but we present a new methodology which allows to compose several pathways and find results which normally requires the availability of more refined data.

As future work we plan to extend the language and add the possibility to specify the probability to choose a rule, thus introducing the possibility of making stochastic computations as in [START_REF] Gupta | Probabilistic concurrent constraint programming[END_REF]. We would also like to make use of the declarative nature of ntcc as formulae in temporal logic [START_REF] Nielsen | Temporal concurrent constraint programming: Denotation, logic and applications[END_REF] to verify properties of the modelled systems. Another ex-tension concerns the possibility to model continuous time. This would allow to describe hybrid systems as in [START_REF] Bockmayr | Using hybrid concurrent constraint programming to model dynamic biological systems[END_REF].

Figure 1 :

 1 Figure1: Amount of pAkt present in different experimental conditions: 500I=500µM of insulin (blue); 100T=100µM of TNFα (yellow); 100T 500I=100µM of TNFα and 500I=500µM of insulin (red). This figure should be compared with the homologous in[START_REF] Gaudet | A compendium of signals and responses triggered by prodeath and prosurvival cytokines[END_REF]

Figure 2 :

 2 Figure 2: The white columns represents the final amount of IRS1 (arbitrary units) when only insulin is present in the environment. The coloured columns represents the final amount of IRS1 (arbitrary units) when both insulin and TNFα are initially present.

* This work has been partially supported by the Italian MUR under grant RBIN04M8S8, FIRB project, Internationalization 2004.


Mário S Alvim

Konstantinos Chatzikokolakis

Pierpaolo Degano

Catuscia Palamidessi

Differential Privacy versus Quantitative Information Flow ⋆

Differential privacy is a notion of privacy that has become very popular in the database community. Roughly, the idea is that a randomized query mechanism provides sufficient privacy protection if the ratio between the probabilities of two different entries to originate a certain answer is bound by e ǫ . In the fields of anonymity and information flow there is a similar concern for controlling information leakage, i.e. limiting the possibility of inferring the secret information from the observables. In recent years, researchers have proposed to quantify the leakage in terms of the information-theoretic notion of mutual information. There are two main approaches that fall in this category: One based on Shannon entropy, and one based on Rényi's min entropy. The latter has connection with the so-called Bayes risk, which expresses the probability of guessing the secret. In this paper, we show how to model the query system in terms of an information-theoretic channel, and we compare the notion of differential privacy with that of mutual information. We show that the notion of differential privacy is strictly stronger, in the sense that it implies a bound on the mutual information, but not viceversa.

Introduction

The growth of information technology raises significant concerns about the vulnerability of sensitive information. The possibility of collecting and storing data in large amount and the availability of powerful data processing techniques open the way to the threat of inferring private and secret information, to such an extent that fully justifies the users' worries.

Differential privacy

The area of statistical databases has been, naturally, one of the first communities to consider the issues related to the protection of information. Already some decades ago, Dalenius [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF] proposed a famous "ad omnia" privacy desideratum: nothing about an individual should be learnable from the database that cannot be learned without access to the database.

Dalenius' property, however, is too strong to be useful in practice: it has been shown by Dwork [11] that no useful database can provide it. In replacement Dwork has proposed the notion of differential privacy, which has had an extraordinary impact in the community. Intuitively, such notion is based on the idea that the presence or the absence of an item in the database should not change in a significant way the probability of obtaining a certain answer for a given query [START_REF] Dwork | Differential privacy[END_REF][START_REF] Dwork | Differential privacy in new settings[END_REF][START_REF] Dwork | A firm foundation for private data analysis[END_REF][START_REF] Dwork | Differential privacy and robust statistics[END_REF].

In order to explain the concept more precisely, let us consider the typical scenario: we have databases whose entries are values (possibly tuples) taken from a given universe. A database can be queried by users which have honest purposes, but also by attackers trying to infer secret or private data. In order to control the leakage of secret information, the curator uses some randomized mechanism, which causes a certain lack of precision in the answers. Clearly, there is a trade off between the need of obtaining answers as precise as possible for legitimate use, and the need to introduce some fuzziness to the purpose of confusing the attacker.

Let K be the randomized function that provides the answers to the queries. We say that K provides ǫ-differential privacy if for all databases D and D ′ , such that one is a subset of the other and the larger contains a single additional entry, and for all S ⊆ range(K), the ratio between the probability that the result of K(D) is in S, and the probability that the result of K(D ′ ) is in S, is at most e ǫ .

Dwork has also studied sufficient conditions for a randomized function K to implement a mechanism satisfying ǫ-differential privacy. It suffices to consider a Laplacian distribution with variance depending on ǫ, and mean equal to the correct answer [START_REF] Dwork | A firm foundation for private data analysis[END_REF]. This is a technique quite diffused in practice.

Quantitative information flow and anonymity

The problem of preventing the leakage of secret information has been a pressing concern also in the area of software systems, and has motivated a very active line of research called secure information flow. Similarly to the case of privacy, also in this field, at the beginning, the goal was ambitious: to ensure non-interference, which means complete lack of leakage. But, as for Dalenius' notion of privacy, no-intereference is too strong for being obtainable in practice, and the community has started exploring weaker notions. Some of the most popular approaches are the quantitative ones, based on information theory. See for instance [START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF][START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF][START_REF] Michael | Belief in information flow[END_REF][START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF][START_REF] Malacaria | Assessing security threats of looping constructs[END_REF][START_REF] Malacaria | Lagrange multipliers and maximum information leakage in different observational models[END_REF][START_REF] Smith | On the foundations of quantitative information flow[END_REF].

Independently the field of anonymity, which is concerned with the protection of the identity of agents performing certain tasks, has evolved towards similar approaches. In the case of anonymity it is even more important to consider a quantitative formulation, because anonymity protocols typically use randomization to obfuscate the link between the culprit (i.e. the agent which performs the task) and the observable effects of the task. The first notion of anonymity, due to Chaum [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF], required that the observation would not change the probability of an individual to be the culprit. In other words, the protocol should guarrantee that the observation does not increase the chances of learning the identity of the culprit. This is very similar to Dalenius' notion of privacy, and equally unattainable in practice (at least, in the majority of real situations). Also in this case, researchers in the area have started considering weaker notions based on information theory, see for instance [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF][START_REF] Moskowitz | Covert channels and anonymizing networks[END_REF][START_REF] Zhu | Anonymity vs. information leakage in anonymity systems[END_REF].

If we abstract from the kind of secrets and observables, anonymity and of information flow are similar problems: there is some information that we want to keep secret, there is a system that produces some kind of observable information depending on the secret one, and we want to prevent as much as possible that an attacker may infer the secrets from the observables. It is therefore not surprising that the foundations of the two fields have converged towards the same information theoretical approaches. The majority of these approaches are based on the idea of representing the system (or protocol) as an informationtheoretic channel taking the secrets in input (X) and producing the observables in output (Y ). The entropy of X, H(X), represents the converse of the a priori vulnerability, i.e. the chance of the attacker to find out the secret. Similarly, the conditional entropy of X given Y , H(X | Y ), represents the converse of the a posteriori vulnerability, i.e. the chance of the attacker to find out the secret after having observed the output. The mutual information between X and Y , I(X; Y ) = H(X) -H(X | Y ), represents the gain for the adversary provided by the observation, and is taken as definition of the information leakage of the system. Sometimes we may want to abstract from the distribution of X, in which case we can use the capacity of the channel, defined as the maximum of I(X; Y ) over all possible distributions on X. This represents the worst case for leakage.

The various approaches in literature differ, mainly, for the notion of entropy. Such notion is related to the kind of attackers we want to model, and to how we measure their success (see [START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF] for an illuminating discussion of such relation). Shannon entropy [START_REF] Shannon | A mathematical theory of communication[END_REF], on which most of the approaches are based, represents an adversary which tries to find out the secret x by asking questions of the form "does x belong to set S?". Shannon entropy is precisely the average number of questions necessary to find out the exact value of x with an optimal strategy (i.e. an optimal choice of the S's). The other most popular notion of entropy (in this area) is Rényi's min entropy [START_REF] Rényi | On Measures of Entropy and Information[END_REF]. The corresponding notion of attack is a single try of the form "is x equal to v?". Rényi's min entropy is precisely the log of the probability of guessing the true value with the optimal strategy, which consists, of course, in selecting the v with the highest probability. Approaches based on this notion include [START_REF] Smith | On the foundations of quantitative information flow[END_REF] and [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF].

It is worth noting that, while the Rényi's min entropy of X, H ∞ (X), represents the a priori probability of success (of the single-try attack), the Rényi's min conditional entropy of X given Y , H ∞ (X | Y ), represents the a posteriori probability of success1 . This a posteriori probability is the converse of the Bayes risk [START_REF] Cover | Elements of Information Theory[END_REF] , which has also been used as a measure of leakage [START_REF] Braun | Compositional methods for information-hiding[END_REF][START_REF] Chatzikokolakis | On the Bayes risk in information-hiding protocols[END_REF].

Goal of the paper

From a mathematical point of view, privacy presents many similarities with information flow and anonymity. The private data of the entry constitute the secret, the answer to the query gives the observation, and the goal is to prevent as much as possible the inference of the secret from the observable. Differential privacy can be seen as a quantitative definition of the degree of leakage. The main goal of this paper is to explore the relation with the alternative definitions based on information theory, with the purpose of getting a better understanding of the notion of differential privacy, of the specific problems related to privacy, and of the models of attack used to formalize the notion of privacy, in relation to those used for anonymity and information flow.

Contribution

The contribution of this paper is as follows:

-We show how the problem of privacy can be formulated in an informationtheoretic setting. More precisely, we show how the answer function K can be associated to an information-theoretic channel. -We prove that ǫ-differential privacy implies a bound on the Shannon mutual information of the channel, and that this bound approach 0 as ǫ approaches 0. Same for Rényi min mutual information. -We show that the viceversa of the above point does not hold, i.e. that Shannon and Rényi min mutual information (and also the corresponding capacities) can approach 0 while the ǫ parameter of differential privacy approaches infinity.

Plan of the paper

Next section introduces some necessary background notions. Section 3 proposes an information-theoretic view of the database query systems. Section 4 show the main results of the paper, namely that differential privacy implies a bound on Shannon and Rényi min mutual information, but not viceversa. Section 5 concludes and presents some ideas for future work. The proofs of the results are in the appendix. Such appendix will not be included in the proceeding version (for reasons of space), but the proofs will be made available on line.

Preliminaries

Differential privacy

We assume a fixed finite universe U in which the entries of databases may range. The concept of differential privacy is tightly connected to the concept of adjacent (or neighbor ) databases.

Definition 1 ([13]

). A pair of databases (D ′ , D ′′ ) is considered adjacent (or neighbors) if one is a proper subset of the other and the larger database contains just one additional entry.

Dwork's definition of differential privacy is the following: Definition 2 ( [START_REF] Dwork | Differential privacy[END_REF]). A randomized function K satisfies ǫ-differential privacy if for all pairs of adjacent databases D ′ and D ′′ , and all S ⊆ Range(K),

P r[K(D ′ ) ∈ S] ≤ e ǫ × P r[K(D ′′ ) ∈ S] (1)

Information theory and interpretation in terms of attacks

In the following, X, Y denote two discrete random variables with carriers X = {x 1 , . . . , x n }, Y = {y 1 , . . . , y m }, and probability distributions p X (•), p Y (•), respectively. An information-theoretic channel is constituted by an input X, an output Y , and the matrix of conditional probabilities

p Y |X (• | •), where p Y |X (y | x)
represent the probability that Y is y given that X is x. We will use X ∧ Y to represent the random variable with carrier X × Y and joint probability distribution

p X∧Y (x, y) = p X (x) • p Y |X (y | x).
We shall omit the subscripts on the probabilities when they are clear from the context.

Shannon entropy

The Shannon entropy of X is defined as

H(X) = - x ∈ X p(x) log p(x)
The minimum value H(X) = 0 is obtained when p(•) is concentrated on a single value (i.e. when p(•) is a delta of Dirac). The maximum value H(X) = log |X | is obtained when p(•) is the uniform distribution. Usually the base of the logarithm is set to be 2 and, correspondingly, the entropy is measured in bits.

The conditional entropy of X given Y is

H(X | Y ) = y ∈ Y p(y) H(X | Y = y)
where

H(X | Y = y) = - x ∈ X p(x | y) log p(x | y)
We can prove that 0 ≤ H(X | Y ) ≤ H(X). The minimum value, 0, is obtained when X is completely determined by Y . The maximum value H(X) is obtained when Y reveals no information about X, i.e. when X and Y are independent.

The mutual information between X and Y is defined as

I(X; Y ) = H(X) -H(X | Y ) (2)
and it measures the amount of information about X that we gain by observing Y . It can be shown that I(X; Y ) = I(Y ; X) and 0 ≤ I(X; Y ) ≤ H(X).

Shannon capacity is defined as the maximum mutual information over all possible input distributions:

C = max pX (•) I(X; Y )

Rényi min-entropy

In [START_REF] Rényi | On Measures of Entropy and Information[END_REF], Rényi introduced an one-parameter family of entropy measures, intended as a generalization of Shannon entropy. The Rényi entropy of order α (α > 0, α = 1) of a random variable X is defined as

H α (X) = 1 1 -α log x ∈ X p(x) α
We are particularly interested in the limit of H α as α approaches ∞. This is called min-entropy. It can be proven that

H ∞ (X) def = lim α→∞ H α (X) = -log max x∈X p(x)
Rényi defined also the α-generalization of other information-theoretic notions, like the Kullback-Leibler divergence. However, he did not define the αgeneralization of the conditional entropy, and there is no agreement on what it should be. For the case α = ∞, we adopt here the definition of conditional entropy proposed by Smith in [START_REF] Smith | On the foundations of quantitative information flow[END_REF]:

H ∞ (X | Y ) = -log y∈Y p(y) max x∈X p(x | y) (3)
Analogously to (2), we can define the mutual information

I ∞ as H ∞ (X) - H ∞ (X | Y )
, and the capacity C ∞ as max pX (•) I ∞ (X; Y ). It has been proven in [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] that C ∞ is obtained at the uniform distribution, and that it is equal to the sum of the maxima of each column in the channel matrix:

C ∞ = y ∈ Y max x ∈ X p(y | x).
3

An information theoretic model of privacy

In this section we show how to represent a database query system (of the kind considered in differential privacy) in terms of an information-theoretic channel.

According to [START_REF] Dwork | Differential privacy[END_REF] and [START_REF] Dwork | A firm foundation for private data analysis[END_REF], differential privacy can be implemented by adding some appropriately chosen random noise to the answer x = f (D), where f is the query function and D is the database. The function can operate in the entire database at once, and even though the query may be composed by a chain of subqueries, we assume that subsequent sub-queries depend only on the true answer to previous sub-queries. Under this constraint, no matter how complex the query is, it is still a function f of the database D. The scenario where subsequent subqueries can depend on the reported answer to previous queries corresponds to adaptive adversaries [START_REF] Dwork | Differential privacy[END_REF], and is not considered in this paper.

After the true answer x to the query is obtained from D, some noise is introduced in order to produce a reported answer y. The reported answer can be seen as a random variable Y dependent on the random variable X corresponding to the real answer, and the two random variables are related by a conditional probability distribution p Y |X (•|•). The conditional probabilities p Y |X (y|x) constitute the matrix of an information theoretic channel from X to Y .

Figure 1 shows the scheme of implementation of a differential privacy scheme. In [START_REF] Dwork | Differential privacy[END_REF] it has been proved that a way to define the values of p Y |X (•|•) so to ensure ǫ-differential privacy, is by using the Laplace distribution:

P ((Y = y)|(X = x), ∆f /ǫ) = ∆f 2ǫ e -|y-x|ǫ/∆f ( 4
)
where ∆f is the L1-sensitivity of f , defined as

2 ∆f = max D ′ ,D ′′ adjacent |f (D ′ ) -f (D ′′ )|.
2 We give here the definition for the case in which the range of f is R. In the more general case in which the range is R n we should replace |f (D ′ )f (D ′′ )| by the 1-norm of the vector f (D ′ )f (D ′′ ).

Relation between differential privacy and mutual information

In this section we investigate the relation between differential privacy and informationtheoretic notions. We start by considering an equivalent definition of differential privacy, easier to handle for our purposes.

D ′ ) = k] ≤ e δ × P r[K(D ′′ ) = k] (5)
The following result shows that definition of differential privacy is equivalent to the classical one. Theorem 1. A function K gives ǫ-differential privacy iff it gives δ-differential privacy, with ǫ = δ.

Databases with the same number of entries and differing in at most one entry

Consider two databases D ′ and D ′′ that have the same number of entries and differ in at most one entry as in Figure 2. Let D be the common part shared by both databases, and let r ′ and r ′′ be the rows in which they differ, namely

D ′ = D ∪ {r ′ } and D ′′ = D ∪ {r ′′ }. D ′        D r ′ D ′′        D r ′′

Fig. 2. Two databases differing in exactly one entry

We prove that δ-differential privacy imposes also a bound on the comparison between databases with the same number of entries, and which differ in the values of only one entry. Lemma 1. Let K be a function that gives δ-differential privacy for all pairs of adjacent databases. Given two databases D ′ and D ′′ that have the same number of entries and differ in the value of at most one entry, then:

P r[K(D ′ ) = k] ≤ e 2δ × P r[K(D ′′ ) = k]

Shannon mutual information

We prove now that δ-differential privacy imposes a bound on Shannon mutual information, and that this bound approaches 0 as the parameter δ approaches 0.

Theorem 2. If a randomized function K gives δ-differential privacy according to Definition 3, then for every result x * of the function f the Shannon mutual information between the true answers X (i.e. the results of f ) and the reported answers Y (i.e. the results of K) is bounded by:

I(X; Y ) ≤ (e 2δ + e -2δ )δ log(e) + (e 2δ -e -2δ ) y p(y|x * ) log(p(y|x * ))
It is easy to see that the expression which bounds I from above, (e 2δ + e -2δ )δ log(e) + (e 2δ -e -2δ ) y p(y|x * ) log(p(y|x * )), converges to 0 when δ approaches 0.

The converse of Theorem 2 does not hold. One reason is that mutual information is sensitive to the values of the input distribution, while differential privacy is not. Next example illustrates this point.

Example 1.

Let n be the number of elements of the universe, and m the cardinality of the set of possible answers of f . Assume that p(x 1 ) = α and p(

x i ) = 1-α n-1 for 2 ≤ i ≤ n. Let p(y 1 | x 1 ) = β, p(y j | x 1 ) = 1-β m-1 for 2 ≤ j ≤ m, and p(y j | x i ) = 1 m .
otherwise. This channel is represented in Figure 0(a). It is easy to see that the Shannon mutual information approaches 0 as α approaches 0, independently of the value of β. Differential privacy, however, depends only on the value of β, more precisely, the parameter of differential privacy is max{log e m-1 }, and it is easy to see that such parameter is unbound and goes to infinity as β approaches 0.

The reasoning in the counterexample above is not valid anymore if we consider capacity instead than mutual information. However, there is another reason why the converse of Theorem 2 does not hold, and this remains the case also if we consider capacity. The situation is illustrated by the following example.

Example 2. Let n be the number of elements of the universe, and m the cardinality of the set of possible answers of f . Assume that p(y i | x i ) = β and p(y i | x j ) = 1-β m-1 for i = j. This channel is represented in Figure 0(b). It is easy to see that the Shannon capacity is C = log m-(1-β) log(m-1)+β log β+(1-β) log(1-β), and that C approaches 0 as β approaches 0 and m becomes large. Differential privacy, however, goes in the other direction when β approaches 0, and it is not very sensitive to the value of m. More precisely, the parameter of differential privacy is max{log e

1-β β(1-m) , β(1-m)
1-β }, and it is easy to see that such parameter is unbound and goes to infinity as β approaches 0, independently of the value of m. Table 1. The channels of Examples 1 and 2

Rényi min mutual information

We show now that a result analogous to that of Section 4.3 holds also in the case of Rényi min entropy.

Theorem 3. If a randomized function K gives δ-differential privacy according to Definition 3, then the Rényi min mutual information between the true answer of the function X and the reported answer Y is bounded by

I ∞ (X; Y ) ≤ 2δ log e.
The converse of Theorem 3 does not hold, not even if we consider capacity instead than mutual information. It is easy to prove, in fact, that Examples 1 and 2 lead to counterexamples also in the case of Rényi min mutual information and capacity.

Conclusion and future work

In this paper we have shown that the problem of privacy in statistical databases can be formulated in information-theoretic terms, in a way analogous to what has been done for information flow and anonymity: the database query system can be seen as a noisy channel, in the information-theoretic sense. Then we have considered Dwork's notion of differential privacy, and we have shown that it is strictly stronger than requiring the channel to have low capacity, both for the cases of Shannon and Rényi min entropy. It is natural to consider, then, whether a weaker notion would give enough privacy guarrantees. As future work, we intend to investigate this question.

We first need to understand, of course, what are the constraints that could be relaxed in the notion of differential privacy. To this aim, Example 2 is quite interesting: whenever we get an answer y, there are n-1 possible inputs (entries) which are equally likely to have generated that answer, and one input x that is much less likely than the others (p(x|y) = α, where α is a very small value). The existence of the latter seems quite harmless, yet it is exactly that entry that causes differential privacy to fail (in the sense that its parameter is unbound).

The notion of Rényi min capacity seems a plausible candidate for the notion of privacy: it's relation with the Bayes risk ensures that a bound C ∞ can be seen as a bound on the probability of guessing the right value of x (given the obsevable). In some scenario, this may be exactly what we want. Proof. Let us calculate the Rényi mutual information using the formula

I ∞ (X; Y ) = H ∞ (X) -X ∞ (X|Y ).
H ∞ (X) =log max

Fig. 1 .

 1 Fig.1. The channel corresponding to a differential privacy scheme.

4. 1

 1 Testing single elements Definition 2 considers tests which check whether the result of K(D) belongs to a certain set or not. We prefer to simplify this definition by considering only tests over single elements: Definition 3. A randomized function K gives δ-differential privacy if for all pairs adjacent datasets D ′ and D ′′ , and all k ∈ Range(K), P r[K(

1 mβ,

 1 log e mβ, log e m-1 m(1-β) , log e m(1-β)

Proof.eeTheorem 6 (

 6 Let us calculate the Shannon mutual information using the formula I(X; Y ) = H(Y ) -X(Y |X). H(Y ) =y p(y) log p(y) )e -2δ p(y|x * ) log x p(x)e -2δ p(y|x * ) (by Definition 3 and Lemma 1) =y e -2δ p(y|x * ) x p(x) log e -2δ p(y|x * ) x p(x) =y e -2δ p(y|x * ) log(e -2δ p(y|x * )) (by probability laws) =y e -2δ p(y|x * ) log e -2δy e -2δ p(y|x * ) log p(y|x * ) (by distributivity) = -e -2δ log e -2δ y p(y|x * )y e -2δ p(y|x * ) log p(y|x * ) = δe -2δ log e -e -2δ y p(y|x * ) log p(y|x * ) (by probability laws) 2δ p(y|x * ) log(e 2δ p(y|x * )) (by Definition 3 and Lemma 1) =y e 2δ p(y|x * ) log(e 2δ p(y|x * )) 2δ p(y|x * ) log(e 2δ p(y|x * )) (by probability laws) =y e 2δ p(y|x * ) log(e 2δ )y e 2δ p(y|x * ) log p(y|x * ) = -e δ log e 2δ y p(y|x * ) -e 2δ y p(y|x * ) log p(y|x * ) = -δe 2δ log e -e 2δ y p(y|x * ) log p(y|x * ) (by probability laws) (7) I(X; Y ) = H(Y ) -X(Y |X) (by definition) ≤ δe -2δ log e -e -2δ x p(y|x * ) log p(y|x * )+ 2δe 2δ log e + e 2δ y p(y|x * ) log p(y|x * ) (by Equations 6 and 7) = (e 2δ + e -2δ )δ log(e) + (e 2δ -e -2δ ) y p(y|x * ) log(p(y|x * )) (by distributivity) Theorem 3 in the paper). If a randomized function K gives δ-differential privacy according to Definition 3, then the Rényi min mutual information between the true answer of the function X and the reported answer Y is bounded by: I ∞ (X; Y ) ≤ 2δ log e.

I

  ∞ (X; Y ) = H ∞ (X) -H ∞ (X|Y ) (by definition) ≤log maxx p(x) + 2δ log e + log max x p(x) (by Equations 8 and 9) = 2δ log e

We should mention that Rényi did not define the conditional version of the min entropy, and that there have been various different proposals in literature for this notion. We use here the one proposed by Smith in[START_REF] Smith | On the foundations of quantitative information flow[END_REF].

Acknowledgement

We wish to thank Daniel Le Métayer for having pointed out to us the notion of differential privacy, and brought to our attention the possible relation with quantitative information flow.

⋆ This work has been partially supported by the project ANR-09-BLAN-0169-01 PANDA and by the INRIA DRI Equipe Associée PRINTEMPS.

Appendix

Theorem 4 (Theorem 1 in the paper). A function K gives ǫ-differential privacy iff it gives δ-differential privacy, with ǫ = δ.

Proof.

⇒ Let k ∈ Range(K). Then for all pair of adjacent databases D ′ , D ′′ we have

(taking S to be a singleton set)

(by union of elements)

(by union of elements)

Lemma 2 (Lemma 1 in the paper). Let K be a function that gives δdifferential privacy for all pairs of adjacent databases. Given two databases D ′ and D ′′ that have the same number of entries and differ in the value of at most one entry, then:


Fredrick Rothganger

Svetlana Lazebnik

Cordelia Schmid

Jean Ponce

3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints

This paper presents a novel representation for three-dimensional objects in terms of affine-invariant image patches and their spatial relationships. Multi-view constraints associated with groups of patches are combined with a normalized representation of their appearance to guide matching and reconstruction, allowing the acquisition of true three-dimensional affine and Euclidean models from multiple images and their recognition in a single photograph taken from an arbitrary viewpoint. The proposed approach does not require a separate segmentation stage and is applicable to cluttered scenes. Preliminary modeling and recognition results are presented.

Introduction

This paper addresses the problem of recognizing threedimensional (3D) objects in photographs. Traditional feature-based geometric approaches to this problem, for example alignment and interpretation trees [START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF], enumerate all triples of image features before pose consistency constraints can be used to confirm or discard competing match hypotheses. Appearance-based techniques, on the other hand, use rich local descriptions of the image brightness pattern to select a relatively small set of promising potential matches before using geometric consistency constraints to retain the correct ones. However, they normally either require storing a large number of views for each object (e.g., [START_REF] Murase | Visual learning and recognition of 3D objects from appearance[END_REF][START_REF] Pope | Probabilistic models of appearance for 3-D object recognition[END_REF][START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF]), or limiting the range of admissible viewpoints (e.g., [START_REF] Schneiderman | A statistical method for 3D object detection applied to faces and cars[END_REF][START_REF] Weber | Unsupervised learning of models for recognition[END_REF]).

Viewpoint invariants (or invariants for short) provide a natural indexing mechanism for object recognition tasks. Unfortunately, although planar objects and certain simple shapes (e.g., bilaterally symmetric ones) admit invariants, general 3D shapes do not [START_REF] Burns | View variation of point-set and line-segment features[END_REF], which is the main reason why invariants have fallen out of favor after an intense flurry of activity in the early 1990s [START_REF] Mundy | Geometric Invariance in Computer Vision[END_REF][START_REF] Mundy | Applications of Invariance in Computer Vision[END_REF]. We propose in this paper to revisit invariants as a local object description: Indeed, although smooth surfaces are almost never planar in the large, they are always planar in the small-that is, sufficiently small surface patches can always be thought of as being comprised of coplanar points. The surface of a solid can thus be represented by a collection of small patches, their invariants, and a description of their 3D spatial relationship.

We propose such a surface representation in terms of the affine-invariant patches introduced by Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] and geometric consistency constraints related to the multi-view geometry studied in the structure-frommotion literature [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF]. The detection and representation of affine-invariant patches is discussed in Section 2. We show in Section 3 that it is possible to exploit the multiview geometry of affine projection to impose effective poseconsistency constraints on matching patches (see [START_REF] Lowe | Local Feature View Clustering for 3D Object Recognition[END_REF][START_REF] Schaffalitzky | Zisserman Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?[END_REF][START_REF] Tell | Wide baseline point matching using affine invariants computed from intensity profiles[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighborhoods[END_REF] for related work). Thus, different views of the same scene can be matched by checking whether groups of potential correspondences found by correlation are geometrically consistent. This matching strategy is used in modeling tasks, where matches found in pairs of successive (unregistered) images of the same object are used to create a global 3D (affine or Euclidean) model of this object. We show in Section 4 that multi-view consistency constraints imposed on potential correspondences between these 3D models and image patches can also be used to identify 3D objects in photographs taken from arbitrary viewpoints. In practice, modeling is done in controlled situations with little or no clutter; the stronger consistency constraints associated with 3D models make up for the presence of significant clutter in object recognition tasks, avoiding the need for a separate segmentation stage. The proposed approach to 3D object modeling and recognition has been implemented, and preliminary experiments are presented in Section 5. We conclude in Section 6 with a brief discussion of its promise and limitations.

Affine-Invariant Patches

Operators capable of finding rotation- [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], scale- [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF][START_REF] Mikolajczyk | Indexing based on scale invariant interest points[END_REF] and affine-invariant [START_REF] Baumberg | Reliable feature matching across widely separated views[END_REF][START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF][START_REF] Pritchett | Wide baseline stereo matching[END_REF][START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighborhoods[END_REF] image descriptors in the neighborhood of salient image features ("interest points" [START_REF] Harris | A combined edge and corner detector[END_REF]) have recently been proposed in the context of wide-baseline stereo matching and image retrieval. In this paper, we use an implementation of the affine-invariant region detector developed by Mikolajczyk and Schmid [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] for low-level im-age description. In this approach, the dependency of an image patch's appearance on affine transformations of the image plane is eliminated by an iterative rectification process based on using (a) the second-moment matrix computed in the neighborhood of a point to normalize the shape of the corresponding image patch in an affine-invariant manner; (b) the local extrema of the normalized Laplacian over scale to determine the characteristic scale of the local brightness pattern; (c) an affine-adapted Harris detector to determine the patch location; and (d) image gradient information to eliminate any remaining rotational ambiguity.

The output of the interest point detection/rectification process is a set of image patches in the shape of parallelograms, together with the corresponding affine rectifying transformations. The transformation associated with each patch maps the corresponding parallelogram onto a square with unit edge half-length centered at the origin (Figure 1). The rectified patch is a normalized representation of the local surface appearance that is invariant under planar affine transformations. We will assume from now on an affine-that is, orthographic, weak-perspective, or paraperspective-projection model (the full perspective case will be briefly discussed in Section 6). Under this model, our normalized appearance representation is invariant under arbitrary changes in viewpoint. For Lambertian patches and distant light sources, it can also be made invariant to changes in illumination (ignoring shadows) by subtracting the mean patch intensity from each pixel value and normalizing the sum of squared intensity values to one (or equivalently using normalized correlation to compare patches). The rectifying transformation associated with a planar patch and its inverse can be represented by two £ ¥¤ §¦ ma- trices and ¨that map homogeneous (affine) plane coordinates onto non-homogeneous ones. These transformations will play a fundamental role in the rest of this paper. For the time being, let us note that the columns vectors of the matrix ¨admit a simple geometric interpretation: Since they are respectively the images of the vectors © , © ! " # $ $ , and © % " # & ' under that mapping, the third column ( of ¨is the (non-homogeneous) coordinate vector of the patch center ) , and its first two columns 0 and 1 are respectively the (non-homogeneous) coordinate vectors of the "horizontal" and "vertical" vectors joining ) to the sides of the patch (Figure 1). These two vectors can also be interpreted as the po-sitions of the points, dubbed normalized side points in the sequel, where the "horizontal" and "vertical" axes of a copy of the image patch placed at the origin pierce its right and top side.

In particular (and not surprisingly), a match between 2 43 £ images of the same affine invariant patches contains ex- actly the same information as a match between 2 triples of points. It is thus clear that all the machinery of structure from motion [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF] and pose estimation [START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF] from point matches can be exploited in our modeling and object recognition tasks. Reasoning in terms of multi-view constraints associated with the matrix ¨will provide in this paper a unified and convenient representation for all stages of both tasks, but one should always keep in mind the simple geometric interpretation of the matrix ¨and the deeply rooted relationship between these constraints and those used in motion analysis and pose estimation. We will come back to this issue in Section 6.

3D Object Modeling

In this section, we exploit the multi-view geometry of affine projection to impose effective pose-consistency constraints on matching patches. This allows us to match different views of the same scene by checking whether groups of potential correspondences found by correlation are geometrically consistent. Matches found in pairs of successive (unregistered) images of the same object are finally stitched into a global 3D (affine or Euclidean) model of this object.

Matching Constraints

Let us assume for the time being that we are given 5 patches observed in 2 images, together with the correspond- ing £ 6¤ §¦ matrices 87 @9 and ¨7 @9 defined as in Section 2 for

A CB #D ED #D F 2 and G B ED #D #D # 5 ( A and G serving respectively as image and patch indices). We use these transformations to derive in this section a set of geometric and algebraic constraints that must be satisfied by matching image patches.

A rectified patch can be thought of as a fictitious view of the original surface patch (Figure 2), and the inverse mapping

¨7 H9

can thus be decomposed into an inverse projection I 9

[3] that maps the rectified patch onto the corresponding surface patch, followed by a projection P 7 that maps that patch onto its projection into image number A , i.e., ¨7 H9 B P 7 I 9 be written as I 9 B §¦ ©¨9 © % " # & where ¨9 is a ¦ ¤ ¦ matrix, and it satisfies the constraint I 9 9 B , where 9 is the coordinate vector of the plane 9 that contains the patch. In addition, the columns of the matrix ¨9 admit in our case a geometric interpretation related to that of the matrix ¨7 @9 : Namely, the first two are the (non-homogeneous) coordinate vectors of the "horizontal" and "vertical" axes of the surface patch, and the third one is the (non-homogeneous) coordinate vector of its center 9

(see appendix).

To account for the form of I 9

, we construct a reduced factorization of R ¨by picking, as in Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF], the center of mass of the observed patches' centers as the origin of the world coordinate system, and the center of mass of these points' projections as the origin of every image coordinate system: In this case, the projection matrices reduce to P 7 B r 7 w , where 7 is a £ ¤ ¦ matrix, and ¨7 @9 B 7 ¨9 .

It follows that the reduced £ y2 4¤ ¥¦ y5

matrix R ¨B R R ¨ where R S EU WV B X Y `. . . d p q R ¨S EU WV B r ¨`D #D #D ¨c Cw
has at most rank 3, a fact that can be used as a matching constraint when at least two matches are visible in at least two views. Alternatively, singular value decomposition can be used as in Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF]

Matching Strategy

Image matching requires two key ingredients: (a) a measure of appearance similarity between two images of the same patch, and (b) a measure of geometric consistency between 5 matches ' `, D #D ED , ' c established across 2 images (a match is an 2 -tuple of image patches). For the former we use normalized correlation between rectified patches. For the latter, we use the method described in the previous section to estimate ( In our current implementation, we only match patches across pairs of images (2 B £ ), and follow a strategy similar to that used in the range data domain by Johnson and Hebert [START_REF] Johnson | Surface matching for object recognition in complex three-dimensional scenes[END_REF] with spin images. Given a patch in one image, we first select its 2 most promising matches in the second image based on normalized correlation of the rectified patches. We then find groups of consistent matches as follows: For each one of the 3 matches, we initialize the group 4 to that match ' . We then find the match ' 65 minimizing ( © )4 0' 65 (naturally defined as ( © 7' ` #D ED #D F 8' @9 8' 5 when 4 B © )' ` ED #D #D E 0' @9 ). If ( © )4 0' A5 CB ED , where D is a preset threshold, we add ' F5 to 4 and continue. This results in the construction of 3 groups. Finally, we discard all groups smaller than some threshold G .

The remaining matches are judged to be correct. We then use estimated projection matrices to predict additional matches. The implementation of this matching strategy is determined by the choice of the three thresholds 2 , D , and G . In the experiments presented in Section 5 we have used 2 B IH , and only group matches with correlation above 0.9. We determine the other two thresholds from statistics on the data itself.

Constructing an Integrated Model

The matching strategy outlined in the previous section can be used in modeling tasks to match successive pairs of views of the same object. The matching process provides as a side benefit the affine structure of the scene: The planes 9 are the zero eigenvectors of the matrices I 9 , and the points P 9 are the third columns of these matrices.

When some of the patches are only observed in some of the frames (the usual case), the data can be split into overlapping blocks of two or more frames, using all the patches visible in all images of the same block to run the factorization technique, then using the points common to overlapping blocks to register the successive reconstructions in a common frame. In principle, it is sufficient to have blocks that overlap by four points. Once all blocks are registered, the initial estimates of the variables P 7

and I 9

are refined by minimizing Q c 9 SR `Q 7 UT &V 7W " ¨7 @9 TP 7 I 9 " X , where Y 9 denotes the set of images where patch number G is visible. Given the reasonable guesses available from the initial registration, this non-linear least-squares process only takes (in general) a few iterations to converge. It is not possible to go from affine to Euclidean structure and motion from two views only. When three or more views are available, on the other hand, it is a simple matter to compute the corresponding Euclidean weak-perspective projection matrices (assuming the aspect-ratios are known) and recover the Euclidean structure [START_REF] Ponce | Metric upgrade of a projective reconstruction under the rectangular pixel assumption[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF].

3D Object Recognition

We now assume that the technique described in Section 3 has been used to create a library of 3D object models, and address the problem of identifying instances of these models in a test image. As before, we start by deriving matching constraints between model and image patches before using these constraints to retain or discard groups of potential correspondences.

Matching Constraints

We assume in the rest of this section that 5 3 v£ affine- invariant patches found in a test image have been putatively matched to 5 patches from a single object model, and de- rive consistency constraints that must be satisfied by these matches. Let us assume that we have the rectification matrices ¨`, D #D #D , ¨c associated with the corresponding patches in the test image. As in Section 3, we can always pick the center of mass of the 5 patch centers in the test image as the origin of its coordinate system, and change the origin of the world coordinate system so that it coincides with the center of mass of their matches in the model.

With this convention, the projection matrix can be written as P B r S w and we can write as before ¨9 B ¨9 .

We have therefore B ¨9 ¡ 9 for G B #D ED #D F 5 . Note that the value of ¨9 is available from the modeling stage in the coordinate system attached to the model. If P denotes the (known) position of the center of mass of the patch centers in the original coordinate system, it is easy to see that the value of ¨9 in the new coordinate frame is obtained by subtracting P © % " # & from its old value. We can now write

¢ ¨ B ¢ Q where ¢ ¨S #U WV B X Y ¨ D#D ED ¨ c p q ¢ ¨S #U WV B X Y ẍ `D #D ED ẍ c p q
and the least-squares solution of this equation is

B ¢ ¨£ ¢ ¨,
where ¢ ¨£ denotes the pseudoinverse of ¢ ¨. An appropriate measure of consistency in this case is (similar to the image matching case) " ¢ @ ¢ ¨ C" $ % ¦ 5 that can once again be interpreted in terms of image distances measured in pixels.

Matching Strategy

Our current implementation uses the affine matching constraints derived in Section 4.1. Normalized correlation between rectified patches is once again used as a measure of appearance similarity between image patches. Note that a representative image patch must be chosen for each patch in the model. We pick the patch with the largest characteristic scale. For geometric consistency, we use the method described in the previous section to estimate (when 5 T3 £ ) the matrices and use ( 5 © )' ` #D ED #D # 8' c S EU WV B " ¢ ¨ ¢ ¨ " $ % ¦ 5

as a measure of inconsistency between the matches. Except for these minor differences, the matching strategy remains the same as in the modeling case.

Implementation

We have implemented the approach proposed in Sections 3 and 4 and present preliminary modeling and recognition experiments. Since both the modeling and matching constraints are based on the inverse rectification matrices ¨7 H9

, it is important to estimate these matrices as accurately as possible. Initial estimates provided by the affine-invariant region detector are improved as follows at every stage of the matching/reconstruction process. Assuming that patch number G is seen in 2 9

views, we can adjust the inverse rectification matrices ¨7 @9 by maximizing the average normalized correlation between the 2 9 © 2 9 T 0$ y£ pairs of (inversely rectified) images of this patch (see Figure 3). We have applied the modeling approach described in Section 3 to several different objects, four of which are shown in Figure 4. For each object, the figure shows one sample input picture from the set of input pictures. Each set contains an average of 16 input pictures. Below each input picture, the figure shows a rendering of the Euclidean model. The models are rather sparse, but one should keep in mind that they are intended for object recognition, not for image-based rendering applications.

Figure 5 shows the results of some recognition experiments. On top are the test pictures, with recognized patches marked. Some of the pictures contain instances of two different models. Below are the models rendered in their recovered poses. The average re-projection error is small in all cases, ranging from 2.8 pixels for the bear to 0.7 pixels for the salt, for 2200x1700 images.

Discussion

We have proposed in this paper to revisit invariants as a local object description that exploits the fact that smooth surfaces are always planar in the small. Combining this idea with the affine-invariant patches of Mikolajczyk and Schmid [12] has allowed us to construct a normalized representation of local surface appearance that can be used to select promising matches in 3D object modeling and recognition tasks. We have used multi-view geometric constraints to represent the 3D surface structure in the large, retain groups of consistent matches, and reject incorrect ones. We believe that our preliminary experiments demonstrate the promise of the proposed approach.

The current implementation is limited to affine viewing conditions. As noted in Section 2, a match between 2 3 £ images of the same affine invariant patches is equivalent to a match between 2 triples of points, thus the machinery de-veloped in the structure from motion [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF] and pose estimation [START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF] literature can in principle be used to extend our approach to the perspective case. Perhaps more interestingly, it might be possible to mix local affine constraints with global perspective/projective ones: Indeed, for patches whose relief is small compared to the distance separating them from the camera, the local projective distortions associated with the perspective projection process are normally negligible, and the rectifying transformations can thus be modeled as planar homographies that just happen to have an affine form. As shown in [START_REF] Faugeras | The Geometry of Multiple Images[END_REF] for example, planar homographies can also be written as the composition of a (perspective) projection and an inverse projection, although this factorization is only defined up to an unknown scale factor, preventing the straightforward use of singular value decomposition techniques. Thus it would be interesting to combine affine and perspective/projective matching constraints in modeling and recognition tasks (as was done by Tuytelaars and Van Gool [START_REF] Tuytelaars | Matching widely separated views based on affinely invariant neighborhoods[END_REF] in the image matching domain). Another problem that we feel has not been dealt with in a satisfactory manner is the combinatorics of the matching process: What is the best way (or at least a good way) to combine multiple views of multiple objects with some patches visible in some images but not in others? This remains an open question that we plan to address in the future.

Appendix: Inverse Projection Matrices

Consider a plane with coordinate vector in the world coordinate system. For any point in this plane we can write the affine projection in some image plane as B P ¢¡ and ¤£ ¡ B . These two equations determine the homogeneous coordinate vector ¡ up to scale. To completely determine it, we can impose that its fourth coordinate be 1, and the corresponding equations become P ¡ B X Y p q

where P B X Y P © ! " " E p q D

Not surprisingly, P is an affine transformation matrix.

So is its inverse, and if P B §¦ ( `( X ( ¦¥ ( ¨ § is the matrix associated with the projection into the (fictitious) rectified image plane. Note that P 9 maps the center 9

of patch number G onto the origin of the rectified image plane. It follows that the (non-homogeneous) coordinate vector of this point is P 9 B I 9 X Y p q or, equivalently, that P 9 is the third column of the matrix I 9

. A similar reasoning shows that the "horizontal" and "vertical" axes of the patch are respectively the first and second columns of I 9

.

2 Figure 1 :

 21 Figure 1: Geometric interpretation of the rectification matrix ¡ and its inverse ¢ .

Figure 2 :

 2 Figure 2: Geometric interpretation of the decomposition of the mapping ¢ ¡ ¢ into the product of a projection matrix £ ¤ and an inverse projection matrix ¥ ¢ .

  &% ¦ 2 5 of this matrix can be interpreted geometrically as the average distance (in pixels) between the center and normalized side points of the patches observed in the image, and the center and normalized side points predicted from the recovered matrices

when 2 5

 5 % ¦ y2 65 as a measure of inconsistency between the matches.

Figure 3 :

 3 Figure 3: Adjusting the rectifying transformations: Rectified patches associated with a match in three views before (top) and after applying the refinement process (bottom).

Figure 5 :

 5 Figure 5: Recognition experiments. (Top) Test pictures, with recognized patches marked. (Bottom) Models rendered in their recovered poses. (Left to right) Teddy bear, vase, salt and rubble together.

Figure 4 :

 4 Figure 4: Object gallery. (Top) One of several input pictures for each object. (Bottom) Rendering of each model, not necessarily in same pose as input picture. (Left to right) Teddy bear, vase, plastic model of a pile of rubble, Morton Salt container.

!

  The © ¤ ¦ matrix P £ is the inverse projection matrix[START_REF] Faugeras | The Geometry of Multiple Images[END_REF] associated with the plane . Note that, for any point in the image plane, the point¡ B P £¦ lies in the plane , thus ¡ B . Since this must be true for all points , we must have

Acknowledgments: This research was partially supported by the UIUC Campus Research Board, by the National Science Foundation under grant IRI-990709, by the CNRS-