Julien Cervelle
email: julien.cervelle@univ-mlv.fr

Enrico Formenti
email: enrico.formenti@unice.fr

Pierre Guillon
email: pierre.guillon@univ-mlv.fr

Sofic trace subshift of a cellular automaton ⋆

Keywords: discrete-time dynamical systems, cellular automata, symbolic dynamics, sofic systems, formal languages

The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram. In this paper we study conditions for a sofic subshift to be the trace of a cellular automaton.

Introduction

Cellular automata are well-known formal models for complex systems. They are used in a huge variety of different scientific fields including mathematics, physics and computer science.

A cellular automaton (CA) consists in an infinite number of identical cells arranged on a regular lattice indexed by Z. Each cell is a finite automaton which state takes value in a finite set A. All cells evolve synchronously according to their own state and those of their neighbors.

The study and classification of the evolutions of cellular automata is one of the standing open problems in the field [START_REF] Gilman | Classes of linear automata[END_REF][START_REF] Hurley | Attractors in cellular automata[END_REF][START_REF] Dubacq | Kolmogorov complexity and cellular automata classification[END_REF][START_REF] Durand | On undecidability of equicontinuity classification for cellular automata[END_REF][START_REF] Culik | Undecidability of cellular automata classification schemes[END_REF][START_REF] Braga | Pattern growth in elementary cellular automata[END_REF]. Indeed, the simple definition of CA contrasts the wide variety of their evolutions. An interesting idea is to classify these behaviors according to some notion of complexity. Of course, the word "complexity" means different things to different researchers. For this reason, in literature one finds classifications according to topological entropy, measure theory, dimension theory, attractors, algorithmic complexity, etc.

In this paper we follow a formal languages approach. Each CA is associated with a language. The idea is that the more complex is the language, the more complex is the automaton.

The associated language is defined as follows (see Section 2 for more precise definitions). Each CA can be seen as a discrete dynamical system (A Z , F ), where F is the global function. Let β = β 1 , β 2 , . . . , β k a finite partition of A Z . Then an orbit of initial condition x, O F (x) = (x, F (x), . . . , F n (x), . . .) can be associated with the infinite word w such that ∀n ∈ N, w n = i if F n (x) ∈ β i . Then, w is the β-trace of F with initial condition x. The β-trace set Σ of F is the set of β-traces with all possible initial conditions. Remark that when A Z is endowed with the Cantor topology (see Section 2), Σ is a closed shift-stable set i.e. a subshift. The language L(Σ) of factors occurring in configurations of Σ is the language associated with (A Z , F ).

In [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF], Kůrka classified factor subshifts of CA according to their language complexity. He devised three classes: bounded periodic; regular but not bounded periodic; not regular. In this paper we address a somewhat complementary question, namely, given a subshift Σ of a certain language complexity we wonder if it can be the trace of a CA.

Motivations come both from classical symbolic dynamics but also from physics. Indeed, when observing natural phenomena due to physical constraints, one can keep trace only of a finite number of measurements. This set of measurements, usually, takes into account only a minor part of the parameters ruling the phenomenon under investigation. Hence, to some extent, what is observed is the "trace" of the phenomenon left on the "instruments" rather than the whole phenomenon in its globality.

It is a very important issue (Galilean principle) to find a formal model which can reproduce the observed trace. Restating those reasonings in our context: given a subshift Σ, one wonders which discrete dynamical system can produce it. In particular, one can ask if there exists a CA having Σ as a trace.

Giving a complete answer to this question seems very hard. In this paper we give some sufficient conditions for a regular language to be traceable. The proof is constructive. We believe that the construction of the CA is of some interest in its own. Because of the lack of space some of the proofs are omitted. They can be found in the Appendices.

Definitions

Let N * = N \ {0}. For i, j ∈ N with i ≤ j, [i, j] denotes the set of integers between i and j. For any function

F from A Z into itself, F n denotes the n-fold composition of F with itself. A set S ⊂ A Z is F -stable if F (S) ⊂ S.
Languages. Let A be a finite alphabet with at least two letters. A word is a finite sequence of letters w = w 0 . . . w |w|-1 ∈ A * . Its reverse w is w |w|-1 . . . w 0 and its rotation γ(w) is w 1 . . . w |w|-1 w 0 . A factor of a word w = w 0 . . . w |w|-1 ∈ A * is a word w [i,j] = w i . . . w j , for 0 ≤ i ≤ j < |w|. We note w [i,j] ⊏ w. The empty word is denoted by ε. Given two languages C, D ⊂ A * , CD denotes their concatenation, C + D their union, C * = n∈N C n , and

C ω = z ∈ A N ∀j ∈ N, ∃k ≥ j, z [0,k-1] ∈ C * .
When no confusion is possible, given a word w, we also denote w the language {w}.

Configurations. A configuration is a biinfinite sequence of letters x ∈ A Z . The set A Z of configurations is the phase space. The definition of factor can be naturally extended to configurations: for x ∈ A Z and i ≤ j, x [i,j] = x i . . . x j ⊏ x. If u ∈ A * , then u ω is the infinite word consisting in periodic repetitions of u, and ω u ω is the configuration consisting in periodic repetitions of u.

Topology. We endow the phase space with the Cantor topology. A base for open sets is given by cylinders. For j, k ∈ N and a finite set W of words of length j, we will note

[W ] k the cylinder w ∈ A Z w [k,k+j-1] ∈ W . [W ] C k is the complement of the cylinder [W ] k .
Cellular automata. A (one-dimensional) cellular automaton is a parallel synchronous computation model consisting in cells distributed over a regular lattice Z. Each cell has a state in the finite alphabet A, which evolves depending on the state of their neighbors according to a local rule f : A d → A, where m ∈ Z and d ∈ N * are the anchor and the diameter of the CA, respectively. The global function of the CA is F :

A Z → A Z such that F (x) i = f (x [i-m,i-m+d] ) for every x ∈ A Z and i ∈ Z. The space-time diagram of initial configuration x ∈ A Z
is the sequence of the configurations of the orbit (F j (x)) j∈N . Usually they are graphically represented by a two-dimensional diagram like in Figure 1.

The shift map σ : A Z → A Z is a particular CA global function defined by σ(x) i = x i+1 for every x ∈ A Z and i ∈ Z. According to the Hedlund theorem [START_REF] Hedlund | Endomorphism and automorphism of the shift dynamical system[END_REF], the global functions of CA are exactly the continuous self-maps of A Z commuting with the shift map.

Any local rule f of a CA can be extended naturally to an application on words

f (w) = (f (w [i,i+d-1] )) 0≤i≤|w|-d , for all w ∈ A * A d .
Dynamical systems. A dynamical system is a couple (X, F ) where X is a set called the phase space, and F :

X → X is a continuous self-map. (Y, F ) is a subsystem of (X, F ) if Y is a closed F -stable subset of X. A set Y is F -stable if F (Y ) ⊂ Y . Morphisms. A morphism of the dynamical system (X, F ) into the dynamical system (Y, G) is a continuous map φ : X → Y such that φ • F = G • φ.
A conjugacy (resp. a factorization) is a bijective (resp. surjective) morphism; in that case we say that (Y, G) is conjugate to (resp. a factor of) (X, F ) (we expect the reader not to confuse between the use of the word "factor" in the dynamical system context and the language theory one).

Subshifts. The onesided shift, also noted σ is the self-map of A N such that σ(z) i = z i+1 , for every z ∈ A N and i ∈ N. A onesided subshift (or simply a subshift ) Σ ⊂ A N is a σ-stable closed set of infinite words. The lan-

guage of Σ is L(Σ) = { w ∈ A * | ∃z ∈ Σ, w ⊏ z }, and characterizes Σ, since Σ = z ∈ A N ∀w ⊏ z, w ∈ L(Σ) . The alphabet of the subshift Σ is the set { a ∈ A| ∃z ∈ Σ, az ∈ Σ } i.e
. the set of letters that appear in infinite words belonging to Σ. A subshift Σ is transitive if for every words u, v ∈ L(Σ), there exists w ∈ A * such that uwv ∈ L(Σ). A subshift can also be characterized by a language F ⊂ A * of forbidden words, i.e. such that

Σ = z ∈ A N ∀u ∈ F, x ⊏ z .
A subshift is of finite type (SFT for short) if it has a finite language of forbidden words. It is a k-SFT (for k ∈ N) if it has a finite set of forbidden words of length k. A subshift Σ is sofic if L(Σ) is a regular language. The following characterization of sofic subshifts will be very useful in the sequel. For more about subshifts, see for instance [START_REF] Marcus | An introduction to symbolic dynamics and coding[END_REF].

Theorem 1 (Weiss [START_REF] Weiss | Subshifts of finite type and sofic systems[END_REF]). A subshift is sofic if and only if it is a factor of a SFT.

Hedlund's theorem can be extended as follows.

Theorem 2 (Hedlund [8]). A function φ is a morphism of a subshift (X, σ) on alphabet A into a subshift (Y, σ) on alphabet B if and only if there is a radius r ∈ N and a local rule f : A r+1 → B such that ∀j ∈ N, ∀x ∈ X, φ(x) j = f (x j . . . x j+r ) (we say φ is an r-block map).

Traces

In this section we define the main notion introduced in the paper, namely, the trace of a CA and the traceability of a subshift. Moreover, we give a simple necessary condition for a subshift being traceable. Definition 1 (Trace). Given a CA F , the trace applications are defined for k ∈ Z by T k F (x) = (F j (x)) j∈N . In other words, T k F (x) is the k th column of the space-time diagram of initial configuration x (see Figure 1). We note T F = T 0 F . We say that T F (x) is the trace of F with initial condition x.

The study of trace applications can be reduced to the study of T F , because of shift-invariance of CA.

It can be noticed that this notion of trace corresponds to the β-trace as defined in the introduction, with β = { [a]| a ∈ A } being the partition of A Z into cylinders of width 1.

Definition 2 (Traceability). The trace subshift of a CA F is τ (F ) = T F (A Z ).
It is a factor subshift of (A Z , F ), since T F is continuous and commutes with σ. A subshift Σ is traceable if there exists a CA F for which Σ = τ (F ).

We begin with a condition for the traceability of a subshift. Proposition 2 proves that it is necessary.

Definition 3 (T0 subshift). A subshift is T0 if it includes a 2-SFT with the same alphabet. Proposition 1. A subshift is T0 if and only if there exists a map φ : A → A such that for every letter a ∈ A, (φ j (a)) j∈N ∈ Σ.

Proof. If ∀a ∈ A, (φ j (a)) j∈N ∈ Γ , then (φ j (a)) j∈N a ∈ A is a 2-SFT of alphabet A and set of forbidden words a∈A a(A \ {φ(a)}). Conversely, consider a 2-SFT Γ of alphabet A. Define φ(a) = b such that ab ∈ L(Γ ). Since Γ is a 2-SFT, we have that ∀a ∈ A, (φ j (a)) j∈N ∈ Γ .

⊓ ⊔ Example 1. Consider the following subshifts :

-Σ = (1 + ε)(01) ω ; it is finite T0 (with φ(0) = 1 and φ(1) = 0); -Σ = 0 ω + 0 * 1 ω ; it is infinite T0 (with φ(0) = φ(1) = 1); -Σ = (01 + 1 + ε)(001) ω ; it is finite but not T0.
Proposition 2. The trace subshift of a CA is T0.

Proof. Consider a CA F . For any a ∈ A, define φ(a) as F ( ω a ω ) 0 . Then (φ j (a)) j∈N = T F ( ω a ω ) ∈ τ (F ). By Proposition 1, τ (F ) is T0. ⊓ ⊔ Theorem 3. Any 2-SFT is traceable.

Proof. Consider a 2-SFT Σ and let A be its alphabet. For each a ∈ A, define φ(a) = b such that ab ∈ L(Σ). Consider the CA of anchor 0, diameter 2 and local rule f defined by f (x 0 , x 1 ) = x 1 if x 0 x 1 ∈ L(Σ), and φ(x 0 ) otherwise. If x ∈ A Z , then the definition of the rule gives that every factor of length 2 of its trace is in L(Σ). Conversely, if z ∈ Σ, then we can see by induction that Σ is the trace of F with initial condition x as soon as x [0,+∞) = z. ⊓ ⊔

k-traceability

In order to establish finer results we first need a weaker condition for traceability, namely k-traceability. A subshift of alphabet A is k-traceable if it is the set of columns of a CA on the alphabet A k . The difference between a CA tracing a subshift of alphabet A and one tracing a subshift of alphabet A k is that the rule of the latter can use the knowledge of the position of a letter of A in a word over A k . This results in a much simpler construction.

Notation. If Σ is a subshift on an alphabet B ⊂ A k , and q ∈ [0, k -1], then the q th projection is defined as

π q : B N → A N (z j ) j∈N → ((z j ) q ) j∈N .
We also note π(Σ) = 0≤q<k π q (Σ), which is a subshift on A. In this section we will limit our study to onesided CA, i.e. with anchor 0.

Definition 4 (k-traceability). Given a CA F on the alphabet B ⊂ A k , the ktrace subshift is defined by

• τ (F ) = 0≤q<k ((F j (x) 0 ) q ) j∈N x ∈ B Z = π(τ (F )).
A subshift is k-traceable if it is the k-trace of a onesided CA on the alphabet

B ⊂ A k .
Similarly to what done in the previous section we give a necessary condition for being k-traceable.

Definition 5 (T1 subshift). A subshift Σ on the alphabet

A is T1 if there exists k ∈ N * and a 2-SFT Γ ⊂ (A k ) N , such that π 0 (Γ ) = π(Γ ) = Σ (in particular, Σ is a factor of Γ ). Theorem 4. A T1 subshift is k-traceable for some k ∈ N * . Proof. By Theorem 3, the corresponding Γ ⊂ (A k ) N is the trace of a CA F on some alphabet B ⊂ A k . Hence, • τ (F ) = π(τ (F )) = π(Γ ) = Σ. ⊓ ⊔ Example 2.
Consider the subshift Σ = (01 + 1 + ε)(001) ω . It is T1 (define the 2-SFT Γ = (uvw) ω on the alphabet B = {u, v, w} ⊂ A 3 , where u = 001, v = 010 and w = 100). It is thus 3-traceable, but not traceable since it is not T0.

Theorem 5. Any SFT is T1.

Proof. Let Σ be a k-SFT for some k

∈ N * . Γ = (z [j,j+k-1] ) j∈N z ∈ Σ is a 2-SFT, and π(Γ ) = 0≤q<k { (z j+q ) j∈N | z ∈ Σ } = 0≤q<k σ q (Σ) = Σ = π 0 (Γ ). ⊓ ⊔
This result allows us to prove the next proposition, which is a less restrictive condition for being T1. Proposition 3. A subshift Σ is T1 if and only if it is a factor of a SFT Γ on alphabet A k for some k ∈ N * such that π(Γ ) ⊂ Σ. Now we extend the results on k-traceability to sofic subshifts (with some additional properties).

Definition 6 (T2 subshift).

A subshift is T2 if it is sofic and includes an infinite transitive subshift. Theorem 6. Any T2 subshift is T1.

The proof of Theorem 6 is given using the following lemmata. Lemma 1. A sofic transitive subshift on alphabet A is infinite if and only if for all n ≥ 2, it includes a subshift B ω with B ⊂ A k , |B| ≥ n and some k ∈ N * . Lemma 2. If Σ is a factor subshift of a SFT Γ on alphabet B such that B ω ⊂ Σ, then Σ is T1.

Proof (of Theorem 6). Let Σ a T2 subshift. From Theorem 1, it is a factor of a SFT Γ . Thanks to Lemma 1, there is an arbitrarily large set of words B on A such that B ω ⊂ Σ, so we can assume without loss of generality that Γ is a subshift on such an alphabet B ⊂ A k for some k ∈ N * . From Lemma 2, we conclude that Σ is T1.

⊓ ⊔

5 From k-trace to trace

In the previous section, we gave a sufficient condition for a particular subshift Σ to be k-traced by a CA G on an alphabet B ⊂ A k . In this section, we show how to simulate G with another CA, on alphabet A, in such way that its trace is Σ. This can be done if we add a further condition to our subshift.

Definition 7 (T3 subshift).

A subshift Σ is T3 if there is a map φ : A → A such that for every letter a ∈ A, (φ j (a)) j∈N ∈ Σ (it is T0) and there is a word

w ∈ A * \ φ(A) * such that w ω ∈ Σ.
Example 3. Consider the following subshifts.

-Σ = (1 + ε)(01) ω is not T3.

-Σ ′ = 0 ω + 0 * 1 ω is T3 (with φ(0) = φ(1) = 1 and w = 0).

Theorem 7. Any T3 k-traceable subshift (for some k ∈ N * ) is traceable.

This section presents a sketch of the proof of Theorem 7. Remark that it is well known that a CA on any alphabet can be simulated by a CA on any other alphabet (with at least two letters), provided that its diameter is wide enough.

In particular, any CA on B ⊂ A k can be simulated by a CA on A. Each cell can see its neighborhood as words of A k and evolve accordingly. The problem is that all cells must have the same local rule, so they have to find from the neighborhood which column of the A k simulation they are representing. This is usually done using a special border word to delimit the words of A k . In this section, Σ denotes a T3 subshift on alphabet which is k-traceable by a onesided CA G. Let φ and w be as in Definition 7. Assume G has diameter 2 (the construction can easily be generalized) and local rule g : B 2 → B.

In order to achieve the simulation, we first define border words to delimit A k cells. We have two execution modes: a simulation mode will simulate properly the execution of the CA on alphabet B, and a default mode will be applied if the neighborhood contains invalid information. This adds some issues: default evolution must be in Σ; border evolution must also evolve according to Σ; and we have to ensure that when a mode is applied to a cell, the same mode keeps being applied there in the following generations, since a change of mode would produce an invalid trace. These problems will be solved in the three following subsections.

Borders

In order to make our simulations, we need to delimit computation zones. This is obtained by using some special words called borders and defined as follows:

Υ = a |w| vva k+3|w| a ∈ φ(A), v ∈ O γ (w) ⊂ A l ,
where O γ (w) = { γ q (w)| 0 ≤ q < |w| }, and l = k + 6 |w|.

Borders have the property that they cannot have a too wide overlap.

Border evolution. The border words of Υ must have an evolution in Σ. The following rule (of diameter 1) respects that condition:

∆ Υ : Υ → Υ a |w| vva k+3|w| → φ(a) |w| γ(v)γ(v)φ(a) k+3|w| .
Macrocells. We will decompose our configurations into macrocells. A macrocell is the concatenation of a border word and a valid word of B. We can simulate the local rule g by a macroevolution rule (local rule on macrocells of BΥ ⊂ A h , where h = k + l = 2k + 6 |w|, and of diameter 2):

∆ : (BΥ ) 2 → BΥ (u, v) → g(u [0,k-1] , v [0,k-1] )∆ Υ (u [k,h-1]
) .

Default mode

Our CA will work as follows. Valid zones (with macrocells), which evolve according to the macroevolution rule ∆ so that they remain valid zones. Invalid zones run a microdefault mode so that they remain invalid zones. Nevertheless, frontiers between the zones must not move. In the frontiers, a macrodefault mode is applied in order for a macrocell to have the opportunity to evolve without taking into account its neighbors; that way, each cell will keep the same execution mode.

Macrodefault mode. To do so, we extend the macroevolution to a function on ΘA h , where Θ = BΥ A h \ 0<i<h A i BΥ A h-i because it does not take into account overlapping macrocells. This is crucial in order to define a local rule. If the central macrocell has a neighbor macrocell in Θ, we apply a simulation step of the CA. Otherwise, we evolve as a macrodefault mode (simulation from a monochromatic configuration):

∆ : ΘA h → BΥ u → g(u [0,k-1] , u [h,h+k-1] )∆ Υ (u [k,h-1] ) if u ∈ BΥ Θ g(u [0,k-1] , u [0,k-1] )∆ Υ (u [k,h-1] ) otherwise .
Microdefault mode. The function φ (corresponding to the fact Σ is T0) allows to define a microdefault mode for a neighborhood that does not contain any macrocell. We are now able to transform the function ∆ into a local rule on A. Indeed, we can define, for anchor m = h -1 and diameter d = 3h -1: A configuration which is a valid encoding of some y ∈ B Z (simulation mode), then its trace is some projection of the trace of y. Otherwise, microdefault and microdefault mode also produce a trace which is in Σ. This concludes the proof of Theorem 7.

f : A d → A w → ∆(u) i if w ∈ A m-i uA i , where u ∈ ΘA h , i ∈ [0, h -1] φ(

Examples

Example 4 (Finite untraceable T1 subshift). No CA traces subshift Σ = {0 ω , (01) ω , (10) ω }, even though it is T1.

Example 5 (T1, T3, non-SFT, non-T2 subshift). The subshift Σ = (0 * 1 + 1 * )0 ω is neither a SFT nor T2, but it is T1 and T3. Hence, by Theorems 4 and 7 it is traceable.

Example 6 (Traceable non-T3 subshift). Let f be the local rule of anchor 3 and diameter 7 such that f (u -3 000111) = 1, f (000111u 3 ) = 0, f (u -3 001011) = 0, f (001011u 3 ) = 1, and f (u) = u 0 otherwise. The trace subshift of the corresponding CA is τ (F ) = {0 ω , (10) ω , (01) ω , 1 ω }. In this case, τ (F ) is finite but not T3.

Example 7 (Traceable non-sofic subshift). Let F be the CA on alphabet A = {b, r, l, w} (the white, the right, the left and the wall particles, respectively) defined by the following local rule f of anchor 1 and diameter 3:

x -1 x 0 x 1 rl? ?rl r?l ?w? ?rw wl? r?? ??l ??? f (x -1 x 0 x 1 ) w w w w l r r l b where ? stands for any letter in A and the first applicable rule is used (left to right). Then, τ (F ) is not sofic.

In this paper, we have given sufficient conditions for a subshift to be the trace of a CA.

T1 ⇒ k-traceable (Theorem 4) SFT ⇒ T1 (Theorem 5) T2 ⇒ T1 (Theorem 6) T3 and k-traceable ⇒ traceable (Theorem 7)

The following summarizes all these results: Theorem 8. Any T3+T1, T3 SFT, or T3+T2 subshift is traceable.

The present result follows other works on the structure that the trace of a CA can have. Here, we take the problem the other way around: we construct a CA that traces a particular kind of subshifts. Though we do not have a necessary and sufficient condition, Conditions T0, T1, T2 and T3 are a first step toward a better understanding of what makes a sofic subshift traceable or not.

Moreover, we expect our construction to be generalizable to weaker conditions. Nevertheless, the non-sofic case is still obscure. The general feeling is that it needs a completely different approach.

In [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF], it is proved that every factor subshift of a CA F is a factor of some βtrace, where β is a partition of A Z , and every β-trace is a factor of some column factor (i.e. a subshift (F j (x) [0,q-1] ) j∈N x ∈ A Z , for some q ∈ N). Hence we can wonder now whether this kind of result can be generalized, in particular to the canonical factor (F j (x) [0,d-1] ) j∈N x ∈ A Z of the CA.

2 Fig. 1 .

 21 Fig. 1. The trace seen on the space-time diagram.

  w 0 ) otherwise since such an integer i, and such a word u would be unique (from the construction of Θ). This local rule is such that f (A m uA m ) = ∆(u) for every u ∈ ΘA h , which is what we wanted: it can simulate in one step the behavior of our CA on B. Let F be the corresponding global rule.The following lemma guarantees that no column changes its evolution mode.

Lemma 3. The preimage of cylinder [BΥ ] is cylinder [Θ]. Moreover, cylinder [Θ] and its complementary [Θ] C are F -stable (in particular, we cannot create a border).

⋆ This work has been supported by the Interlink/MIUR project "Cellular Automata:

Topological Properties, Chaos and Associated Formal Languages", by the ANR Blanc "Projet Sycomore".

A Proofs of Section 4

Proof (of Proposition 3). Assume that Σ is a T1 subshift; then there is a 2-SFT Γ such that π 0 (Γ ) = Σ. As π 0 is a factorization, Σ is a factor of the SFT Γ .

For the converse implication, assume that Σ is a subshift on alphabet A, Γ a SFT on alphabet B ⊂ A k , and φ : Γ → Σ a factorization, where k ∈ N and π(Γ ) ⊂ Σ. We can suppose without loss of generality that π(Γ ) = π 0 (Γ ) = Σ, should we replace it by its conjugate (a j w j ) j∈N ∈ (AB) N (w j ) j∈N ∈ Γ and (a j ) j∈N = φ((w j ) j∈N ) , which is still a SFT. From Theorem 5, Γ is T1, i.e. there exists a 2-SFT Γ ′ on alphabet C ⊂ B l for some l ∈ N such that π 0 (Γ ′ ) = π(Γ ′ ) = Γ . We have just used the projections with respect to alphabet B (recall that C ⊂ B l ⊂ (A k ) l ), which projections with respect to A itself are π 0 (Γ ) = π(Γ ) = Σ. Hence, with respect to A, we get π 0 (Γ ′ ) = π(Γ ′ ) = Σ, and Σ is T1.

⊓ ⊔ Proof (of Lemma 1). If |B| ≥ 2, then B ω is infinite (since all words of B have the same length). Conversely, if Σ is an infinite transitive sofic subshift, and (A, Q, δ) a deterministic finite automaton which recognizes the regular language L(Σ), then there is a state q ∈ Q and two letters a, b ∈ A such that δ(a, q) and δ(b, q) are defined (otherwise there would only be one possibility to extend the word from each state, and there would be at most as much infinite words in Σ as initial states in Q). By transitivity, there is a word ũ and a word ṽ such that δ(ũ, δ(a, q)) = δ(ṽ, δ(b, q)) = q.

The function H defined in the following lemma allows us to define a clock of period 2n: the word H(i) represents the i-th clock tick. Then there is an injection H : [0, 2n -1] → A 3n such that the subshift

Proof. Let u, v ∈ B, suppose u 0 = v 0 (other cases are obtained by rotation), and define:

Then, by the definition of H, γ h1 (u)γ h1 (uv) = γ h2 (u)γ h2 (uv). Hence, γ h1 (u) = γ h2 (u) and γ h1 (uv) = γ h2 (uv), giving u = γ h (u) and uv = γ h (uv). Finally,

This is a contradiction, hence H is injective.

Let q ∈ [0, 2n -1] and p ∈ [0, n -1]. Then, π p ((H((q + j) mod 2n)) j∈N ) = (γ (q+j) mod 2n (u)

Similarly, taking the projection p in [n, 3n -1] we find π p ((H(q + j mod 2n)) j∈N ) = (γ q+j mod 2n (uv)) j∈N = ((uv) q+j mod 2n

, where B ⊂ A n and n ∈ N * , is a factor of a SFT Ψ on alphabet A 4n such that π(Ψ ) ⊂ O σ (B ω ), seen as a subshift on A.

Proof. For 0 ≤ q < n, we define the set of time-q encodings as P si q = ((w 0 ) j , . . . , (w n-1

and the decoding function as:

φ q is surjective. If we apply σ, we pass from a time-q encoding to a time-(q + 1) encoding: σ(Ψ q ) = Ψ q+1 mod n . In order to know which step we are in (which of the first n columns to look at), we use a "clock" represented by the last 3n columns as described in Lemma 4. We use the set:

which is a disjoint union from Lemma 4, and has the advantage of being a subshift, since σ(Ψ q mod n ) = Ψ q+1 mod n and σ((H(q + j mod 2n)) j∈N ) = (H(q + 1 + j mod 2n)) j∈N . The decoding

is a factorization deriving from the n-block map ((w 0 ) j . . . (w n-1 ) j , H(q

. By definition of Ψ q and Lemma 4, the projections are in B ω . Last point, we can see that Ψ is an n-SFT, since:

where

Proof (of Lemma 2). Let Σ be a factor subshift of a SFT Γ on alphabet B such that B ω ⊂ Σ. By Lemma 5, the full shift B N , where

B Proofs of Section 5

Remark 1. From the definition of w, we immediately notice that border words have at least one letter that is not in φ(A):

Here is a formalization of the property that border words cannot overlap each other too much:

k] (we will not have overlapping border words sharing more than k letters). Lemma 6. The set Υ of borders is (k + 3 |w|)-freezing.

Proof.

-

Here we use the symmetry of words uu and vv. Let p = min j ∈ [0, l -1] x j+|v| / ∈ φ(A) . On the one hand:

On the other hand:

Combining Equalities (1) and (2), we get i = 0.

⊓ ⊔

The following lemma grants the columns that it produces are in Σ.

Lemma 7. For every border b ∈ Υ , and every column i ∈ [0, l -1], the infinite word

Proof. Consider a border word b = a |w| γ j (w)γ j (w)a k+3|w| .

-

, then by a direct induction one finds that:

The following lemma grants that in particular we will be able to apply function ∆ if there are two macrocells in the neighborhood.

Proof (of Lemma 3). From the definition of f in execution mode and of ∆, we notice that:

The apparition of a letter which is not in φ(A) would mean we are in the left part of an execution mode around that cell: if

Now if a configuration x has an image in cylinder [BΥ ], then, from Remark 1, there is a cell g

Hence, combining with Equation ( 4), with i = gj:

Υ being (k + 3 |w|)-freezing (Lemma 6), we can conclude that i = 0.

Combining with Equation (3), we get:

Another consequence of Equation ( 6) is the stability: 6)), and from Equation (3),

⊓ ⊔ Lemma 9. Let y ∈ B Z , and

We can prove by induction on the generation j ∈ N, that for any i ∈ N, F j (x) ∈ [G j (y)Υ ] ih . This property holds for j = 0. Now suppose it is true at generation j ∈ N, and let us prove it for time j + 1. Let i ∈ N. F j (x) ∈ [BΥ BΥ ] ih ⊂ Θ from the induction hypothesis and Lemma 8. Therefore we are in execution mode between cells ih and (i + 1)h:

In particular, T F (x) = (F j (y) 0 ) j∈N = π 0 (τ F (y)). ⊓ ⊔ Lemma 10. The trace of every configuration x ∈ A Z is in Σ.

Proof.

-First, if x / ∈ [Θ] -i for any i ∈ [0, h -1], then we will always (see Lemma 3) apply the default mode in cell 0: ∀i ∈ [0, h -1] , ∀j ∈ N, F j (x) / ∈ [Θ] -i , and by a trivial recurrence,

, and by recurrence,

and every q ∈ N, then from Lemma 9,

-Otherwise, there is some i ∈ [0, k -1] and some q ∈ N * such that x ∈ [Θ q Θ C ] -i , and thanks to Lemma 3, ∀j ∈ N,

a configuration such that for 0 ≤ p < q, x [ph-i,ph+k-i-1] = y p and for p ≥ q, y p y q-1 . Then we can show by induction on j ∈ Z that for 0 ≤ p < q, F j (x) [ph-i,ph+k-i-1] = G k (y) i , from the definition of f . Hence, T F (x) = π i (T G (y)).

⊓ ⊔

C Proofs of examples

Proof (of Example 4). By contradiction, assume that such a CA F exists. Let f be the corresponding local rule, m its anchor and d its diameter. Being surjective (we can immediately check that for any configuration

Proof (of Example 5). 10 * and 0 * 1 are included in the language of (0 * 1 + 1 * )0 ω , but not 10 * 1; hence Σ is not a SFT. Σ contains two distinct transitive subshifts, namely 0 ω and 1 ω , both of which are finite; hence it is not T2. If φ is defined by ∀a ∈ {0, 1}, φ(a) = 0, then 0 ω , 1 ω ∈ Σ and w = 1 ∈ {0, 1} * \ 0 ω . Hence Σ is T3. Finally, build a 2-SFT Γ = ((0, 1) * (1, 1) + (1, 1) * )(0, 0) ω ⊂ ({0, 1} 2 ) ω , and remark that π 0 (Γ ) = Σ; therefore Σ is T1.

⊓ ⊔

In order to prove Example 7, we first need to prove the following lemma. [wb p lb q w] -p-1 .

Intuitively, if there were no wall on the left, no particle would come from the left, since right particles cannot cross left particles. Similarly, there must be a wall on the right. Fix p, q ∈ N. For any j ∈ N, let i = jp -1 mod 2(p + q + 1) and S j = F j ([wb p lb q w] -p-1 ). By induction on j one can easily prove that S j ⊆ [wb i lb p+q-i w] -p-1 if i ≤ p+q and S j ⊆ [wb 2(p+q)+1-i lb i-p-q-1 w] -p-1 otherwise. Hence, the trace of a configuration x ∈ [wb p lb q w] -p-1 is T F (x) = lb 2p rb 2q ω . ⊓ ⊔ Proof (of Example 7). By Lemma 11 we have that L = L(τ (F )) ∩ lb * rb * lb * r = p,q∈N lb 2p rb 2q lb 2p r .

Since lb * rb * lb * r is regular and L is not, we conclude that L(τ (F )) is irregular. ⊓ ⊔


Damien Graux

Pierre Genevès

Nabil Layaïda

Smart Trip Alternatives for the Curious

When searching for flights, current systems often suggest routes involving waiting times at stopovers. There might exist alternative routes which are more attractive from a touristic perspective because their duration is not necessarily much longer while offering enough time in an appropriate place. Choosing among such alternatives requires additional planning efforts to make sure that e.g. points of interest can conveniently be reached in the allowed time frame. We present a system that automatically computes smart trip alternatives between any two cities. To do so, it searches points of interest in large semantic datasets considering the set of accessible areas around each possible layover. It then elects feasible alternatives and displays their differences with respect to the default trip.

Introduction

In trip planning, it is very common to query for flight combinations according to criteria such as shortest total duration, or cheapest combination for instance. Resulting routes often include inescapable waiting times at airports between connecting flights. Instead, other trip alternatives might reveal much more interesting, such as those setting an appropriate time between connections to allow for a specific activity that leverages the local environment. For instance, when travelling from Lyon to Singapore, the shortest duration criterion yields a stopover in Dubai with a waiting time of 3 hours. Instead, it might be more interesting to slightly defer the connection and obtain enough time to enjoy Dubai's city on the way to Singapore, for instance. Choosing among such alternatives requires additional planning efforts to make sure that e.g. points of interest can effectively and conveniently be reached in the allowed time frame, attractions of interest are open, etc. This additional effort is particularly significant when the user is not aware of local possibilities at all viable stopovers. We introduce a system that computes and suggests smart trip alternatives automatically, given any two origin and destination cities in the world and tolerated connection times. Our system explores large universes of semantically-checked possibilities in the set of all viable layovers, from which it automatically selects a few relevant options. Our system finally suggests two feasible smart trip alternatives while displaying their differences with respect to the default trip with e.g. shortest duration. Thus our system does not require any additional user input when compared to systems such as Google Maps or Rome2Rio1 . Our system leverages the increasing availability of open city transportation data (in e.g. the General Transit Feed Specification (gtfs) [3]), and combines them with flight information as well with external data sources for the selection of e.g. particularly remarkable points of interests. In Section 2, we present how we designed our system around a scalable infrastructure for supporting the mass of worldwide gtfs information (i.e. several csv files providing routes, schedules, stations stop times. . . ), how we leverage various data sources in heterogeneous formats (e.g. rdf, json, xml, gtfs, etc.) for semantic enrichment of information, and how we encode constraints and heuristics for the efficient selection of smart trip options. In Section 3 we illustrate the use of our novel system in a real-world setting before reviewing related works and concluding in Section 4.

Overall System Architecture

The global architecture of our system is shown in Figure 1. It consists of a lightweight client-side part in which users indicate a city of origin and a city of destination and which also displays results, and a backend part with an entry point called master. As shown in Figure 1, the master executes three different processes A,B and C. Process A corresponds to a usual flight finder: it returns trips sorted by simple criteria such as the number of connections and the transit time (by default). Process C queries the Open Street Map (osm) [START_REF] Haklay | Openstreetmap: User-generated street maps[END_REF] tiles servers to fetch cartographic data for drawing resulting routes on a map. Processes A and C basically correspond to what can be found in common flight finding applications. The novelty of our idea and our system resides in process B, which is in charge of computing recommendations by reasoning on enriched data.

Design for scalability. In the backend we distinguish datasets according to their sizes. For performance reasons, when datasets fit in main-memory of a single machine, we use in-memory engines (for e.g. the flight database) whereas city transit datasets (expressed using gtfs [3]) and large rdf datasets are distributed across a cluster of nodes. Specifically, we use a gtfs store implemented on top of the Apache Spark framework2 for the purpose of supporting a large number of gtfs datasets of moderate size3 . When rdf datasets used in the data enrichment process (B3) are large, we rely on our sparqlgx implementation introduced in [START_REF] Graux | SPARQLGX: A distributed RDF store mapping SPARQL to Spark[END_REF] for efficiently evaluating sparql queries on distributed rdf datasets.

To obtain smart trip alternatives for a transit between two airports A 1 and A 2 , process B performs reasoning on aggregated data coming from various sources thanks to the four sub-processes B1, B2, B3, and B4 (Figure 1). The analyzer first queries the flight finder (B1) to gather possible paths (without cycles) taking off from A 1 and landing at A 2 . Then, it applies filters to this set of paths according to two customizable usecases: (1) it keeps paths having at most a X-hour connection; (2) it only considers paths having at least a connection longer than Y hours; where X and Y are user-defined. Moreover, it always tries to avoid connections requiring to spend one night in a hotel somewhere on Earth and rather promotes night in aircrafts, by default. Knowing the possible connections, the analyzer asks the gtfs store (B2) to find among the city transit datasets all the accessible areas from each intermediate airport. This concept of accessibility depends on the usecase i.e. the gtfs store only considers areas from which one can go and return in less than M minutes, where M is equal to the minimum between one quarter of the connection time and 2 hours. A set of accessible stations (using public transport) is hence available for each possible connection. To enrich user experience, the analyzer first seeks points of interest (pois) in these areas using sparql queries evaluated on DBpedia4 , and then further queries other rdf databases for semantic enrichment (B3), e.g. with local restaurants. Then, in (B4) the analyzer fetches ranks and reviews of other users concerning all accessible pois. All these considerations are used to obtain an overall score for each area; the analyzer can thereby choose among the best retained ones using a (customizable) score function.

The typical scenario consists in using our processing pipeline in order to obtain smart trip alternatives using various data sources: gtfs schedules, osm tiles and DBpedia rdf data. One interest of such a tool relies on the fact that users can find alternatives using real data e.g. the scheduling grids are the ones used each day by official transit agencies and semantic data comes from DBpedia. For instance it is possible to review suggestions of trip alternatives to come to the conference. Users can search for trip alternatives passing as argument two airports and two allowed time lapses for connections. For instance, from Paris in France (CDG) to Honolulu in Hawaii USA (HNL) allowing 3 to 5 hours and more than 8 hours, the pipeline (Figure 1) might propose at first to pass through San Francisco CA (as a conventional "fastest trip finder") since it is the fastest trip available. Then, it considers e.g. the Naritasan Shinsho-ji Temple (20 min. far from Tokyo) and also Venice Beach (40 min. far from Los Angeles).

Related Work and Conclusion

There exists many trip planning systems such as Google Maps and Rome2Rio. These systems allow to obtain routes that satisfy simple criteria such as shortest path, shortest duration, cheapest price, and combinations of them. Compared to these systems, we bring an additional semantic layer that allows our system to suggest smart alternatives, e.g. alternatives that do not necessarily satisfy the initial criteria entered by the user, but that will be preferred in the end. Closest to our approach are the works on automatic construction of travel itineraries [START_REF] Chen | Automatic itinerary planning for traveling services[END_REF][START_REF] De Choudhury | Automatic construction of travel itineraries using social breadcrumbs[END_REF] and interactive itinerary planning [START_REF] Roy | Interactive itinerary planning[END_REF]. Compared to these approaches, we notably leverage the use of gtfs big data [3] for checking feasibility of the itinerary by public transportation. Furthermore, an advantage of our system compared with [START_REF] De Choudhury | Automatic construction of travel itineraries using social breadcrumbs[END_REF][START_REF] Roy | Interactive itinerary planning[END_REF] is to provide alternatives at booking time. The user becomes active in the layover decision process deciding how and where to spend its time budget.

Fig. 1 .

 1 Fig. 1. Overall Architecture.

Fig. 2 .

 2 Fig. 2. Application Screenshot: Paris to Honolulu (CDG→HNL).

http://www.google.com/maps & http://rome2rio.com

http://spark.apache.org

For example, gtfs data for the Los Angeles city area represent 20GB (due to seventy million direct paths between all regional stations).

http://dbpedia.org


Damien Graux
email: damien.graux@inria.fr

Louis Jachiet
email: louis.jachiet@inria.fr

Pierre Genevès
email: pierre.geneves@cnrs.fr

Nabil Layaïda
email: nabil.layaida@inria.fr

SPARQLGX in Action: Efficient Distributed Evaluation of SPARQL with Apache Spark

We demonstrate sparqlgx: our implementation of a distributed sparql evaluator. We show that sparqlgx makes it possible to evaluate sparql queries on billions of triples distributed across multiple nodes, while providing attractive performance figures.

Introduction

We demonstrate the sparqlgx system introduced in [START_REF] Graux | SPARQLGX: A distributed RDF store mapping SPARQL to Spark[END_REF] which is designed to evaluate sparql queries efficiently in a distributed manner on top of the Apache Spark framework 1 . sparql [START_REF]SPARQL 1.1 overview[END_REF] is the standard query language for retrieving and manipulating data represented in rdf [START_REF] Hayes | RDF semantics[END_REF]. The core of the sparql query language is the Basic Graph Pattern fragment (bgp) composed of conjunctions of triple patterns (tps) which express conditions on rdf triples. sparqlgx supports the bgp fragment of sparql extended with union and optional operators at top level and with solution modifiers. sparqlgx implements specific optimizations aimed at optimizing the evaluation of bgps. For example, the following query taken from the WatDiv benchmark [START_REF] Aluç | Diversified stress testing of RDF data management systems[END_REF] (c3) involving one bgp composed of six triple patterns returns all the matching subjects from the dataset. Direct Evaluation. In certain situations, queried data might be subject to updates; in others users might only need to evaluate a single query once (for data cleaning purposes for instance). In such cases, it is interesting to limit as much as possible both the preprocessing time and the query evaluation time. For this purpose, sparqlgx provides a specific tool, called sde, capable of directly evaluating sparql queries without preprocessing.

Demonstration Details

We report on our experimental comparisons of sparqlgx against other open source hdfs-based distributed rdf systems such as PigSPARQL [START_REF] Schätzle | PigSPARQL: Mapping SPARQL to pig latin[END_REF], RYA [START_REF] Punnoose | Rya: a scalable RDF triple store for the clouds[END_REF], CliqueSquare [START_REF] Goasdoué | Cliquesquare: Flat plans for massively parallel RDF queries[END_REF], S2RDF [START_REF] Schätzle | S2RDF: RDF querying with SPARQL on spark[END_REF] and RDFHive [START_REF] Graux | SPARQLGX: A distributed RDF store mapping SPARQL to Spark[END_REF]. We deploy them on the same 10-node cluster having the hdfs installed with default settings which imply a resiliency to the loss of two nodes. Furthermore, we consider several datasets (presented in Table 1) coming from two popular bgp benchmarks: LUBM [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF] and WatDiv [START_REF] Aluç | Diversified stress testing of RDF data management systems[END_REF]. These benchmarks are respectively composed of 14 and 20 sparql queries. We present in Figure 1 the response times obtained with WatDiv1k. This illustrates that, for this dataset: (1) SDE always outperforms other tested "direct evaluators" (e.g. PigSPARQL and RDFHive); (2) sparqlgx is able to answer all the queries unlike RYA and CliqueSquare; (3) it shares with CliqueSquare the same order of magnitude for queries L [START_REF]SPARQL 1.1 overview[END_REF][START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF][START_REF] Aluç | Diversified stress testing of RDF data management systems[END_REF][START_REF] Goasdoué | Cliquesquare: Flat plans for massively parallel RDF queries[END_REF][START_REF] Graux | SPARQLGX: A distributed RDF store mapping SPARQL to Spark[END_REF]; (4) it outperforms its competitors on queries C1, C2 and C3 (shown in the introduction).

To further illustrate the performance of sparqlgx, we provide an interactive GUI. Attendees can interact directly with our engines (i.e. sparqlgx and sde) by evaluating several sparql queries on various rdf datasets: such as those presented in Table 1 and other smaller ones. Additionnally, we also deploy the other hdfs-based distributed systems (to have a common basis of comparison); thereby, participants can compare several systems running exactly on the same cluster. We demonstrate sparqlgx and sde with various interaction scenarios:

SPARQLGX RYA S2RDF CliqueSquare PigSPARQL RDFHive SDE C1 C2 C3 F1 F2 F3 F4 F5 L1 L2 L3 L4 L5 S1 S2 S3 S4 S5 S6 S7
1. Loading datasets: participants can select a dataset among several predefined ones and a system to run its preprocessing phase. They can experience the preprocessing time of sparqlgx, RYA, CliqueSquare and S2RDF. Since the loading and indexing cost can be high, we limit this feature to the smaller rdf datasets. 2. Query Evaluation (e.g. Figure 2b): attendees can evaluate predefined sparql queries which are extracted from LUBM and Watdiv. After choosing a dataset and a query, participants can select the evaluation system among sparqlgx, sde, RYA, CliqueSquare, S2RDF, RDFHive and PigSPARQL.

3. Query Rewriting (e.g. Figure 2a): participants can also experience the optimizer module which orders by selectivity the triple patterns of a sparql query according to a chosen rdf dataset. Attendees can see the generated Spark code. 4. System Comparison: finally, participants can observe how the different systems compare head-to-head.

Fig. 1 :

 1 Fig. 1: Query Response Times with WatDiv1k.

  (a) Statistic Module Screenshot. (b) Query Evaluator Screenshot.

Fig. 2 :

 2 Fig. 2: Screenshots.

Table 1 :

 1 General Information about Used Datasets. Compilation of sparql bgps. Conjunctions of triple patterns are translated in terms of primitives of the Apache Spark framework expressed in Scala code. Each bgp is first translated in terms of a list of filters, which are then joined based on common variables.

	SELECT ?v0 WHERE {
	?v0 wsdbm:likes ?v1 .	?v0 wsdbm:friendOf ?v2 .
	?v0 terms:Location ?v3 .	?v0 foaf:age ?v4 .
	?v0 wsdbm:gender ?v5 .	?v0 foaf:givenName ?v6 . }
	2 SPARQLGX Architecture and Principles
	Data Storage Model. In order to process rdf datasets, we adopt the vertical
	partitioning approach introduced by Abadi et al. in [2] which stores a triple
	(s p o) in a file named p whose contents keeps only s and o entries. Converting
	rdf data into a vertically partitioned dataset is straightforward while (1) tending
	to minimize the memory footprint and the datasets size on disks and (2) reducing
	response time when queries have bounded predicates since searches are limited
	to the relevant files.

Optimized Joins With Statistics. To speed up the evaluation of queries, particular attention is paid to the ordering of joins in the translation process. We compute statistics on data (i.e. we count all the distinct subjects, predicates and objects to obtain a notion of triple pattern selectivity based on occurrence numbers). Then we rewrite queries in order to minimize the sizes of intermediate results. Triple patterns are joined in decreasing order of their selectivities (i.e. triple patterns that return the smallest number of results are joined first).

4

  Conclusion sparqlgx outperforms several related implementations in many cases, while implementing a simple architecture exclusively built on top of open source and publicly available technologies. The sparqlgx implementation is available from: http://github.com/tyrex-team/sparqlgx

http://spark.apache.org/


Fernando I Ireta Muñoz

Andrew I Comport

A Proof that Fusing Measurements Using Point-to-Hyperplane Registration is Invariant to Relative Scale

The objective of this paper is to demonstrate that the metric error between different types of measurements can be jointly minimized without a scaling factor for the estimation processes if a Point-to-hyperplane approach is employed. This article is an extension of previous work based on the Point-tohyperplane approach in 4 dimensions applied to pose estimation, where the proposed method minimized a fused error (3D Euclidean points + Image intensities) and it was experimentally demonstrated that the method is invariant to the choice of scale factor. In this paper, the invariance to the scale factor will be mathematically demonstrated. By doing this, it will be shown how the proposed method can further improve the convergence domain in 4D (or higher dimensions) and speed up the alignment between augmented frames (color + depth) whilst maintaining the robust and accurate properties of hybrid approaches when different types of measurements are available.

I. INTRODUCTION

View registration has been widely studied in the field of computer vision and it is especially applied in mobile robotics to perform autonomous navigation by computing visual odometry and reconstructing 3D maps of the environment. One of the most fundamental problems is estimating the pose that relates measurements obtained from a moving sensor at different times.

RGB-D sensors provide rich geometric and photometric information from the scene that can be registered. The alignment between frames is ideally computed by jointly optimizing over color and depth measurements in a so-called hybrid-based manner. Basically, hybrid approaches combine geometric techniques, such as the well know ICP algorithm and its variants, with photometric techniques (direct or feature-based methods) together in order to obtain the benefits of each.

Different approaches have been proposed in the literature to estimate the pose between two different RGB-D views. The main surveys were recently cited in [START_REF] Zhang | Experimental evaluation of RGB-D visual odometry methods[END_REF]. For the purpose of this paper, we will focus on proving that the Point-tohyperplane approach proposed in [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF] is invariant to a scale factor λ . The Point-to-hyperplane minimization avoids the estimation of λ , which weights the contribution of each measurement type and is usually required for methods that minimize the geometric and photometric error simultaneously. The estimation of λ has been widely studied by the vision community and various strategies had been proposed. Depending on how it is estimated, the scale factor λ can be categorized as an "adaptive" or a "non-adaptive" coefficient. *This work is supported by the European H2020 project: COMANOID, Université Côte dAzur, CNRS, I3S, France and CONACYT, México.

The non-adaptive category mostly involves strategies for dense 3D reconstruction from RGB-D images. The coefficient λ is computed only once and it is used to align all the following frames which contain similar information, such as [START_REF] Henry | The 12th International Symposium on Experimental Robotics, chapter RGB-D Mapping: Using Depth Cameras for Dense 3D Modeling of Indoor Environments[END_REF], [START_REF] Men | Color point cloud registration with 4D ICP algorithm[END_REF], [START_REF] Michael Korn | Color supported generalized-ICP[END_REF], [START_REF] Douadi | Pair-wise registration of 3D/Color data sets with ICP[END_REF], [START_REF] Johnson | Registration and integration of textured 3-D data[END_REF], [START_REF] Zhou | Color map optimization for 3D reconstruction with consumer depth cameras[END_REF], [START_REF] Georgel | A unified approach combining photometric and geometric information for pose estimation[END_REF]. A real-time RGB-D SLAM using a non-adaptive scale factor is found in [START_REF] Whelan | Robust real-time visual odometry for dense RGB-D mapping[END_REF], [START_REF] Whelan | Elasticfusion: Dense slam without a pose graph[END_REF], [START_REF] Whelan | Real-time large-scale dense RGB-D SLAM with volumetric fusion[END_REF] where λ was also set empirically to reflect the relative difference in metrics used for color and depth costs.

On the other hand, adaptive methods increase the importance of the geometric error or the photometric error to ensure that each measurement is in the same order of magnitude. They are however more complex methods that compute the adequate scalar factor for each RGB-D image. These methods are usually employed to perform real-time tasks as 3D visual tracking [START_REF] Morency | Stereo tracking using ICP and normal flow constraint[END_REF], [START_REF] Batu Akan | 3D Head tracking using normal flow constraints in a vehicle environment[END_REF], visual odometry [START_REF] Tykkälä | Direct Iterative Closest Point for Real-time Visual Odometry[END_REF], [START_REF] Steinbruecker | Large-scale multi-resolution surface reconstruction from RGB-D sequences[END_REF], [START_REF] Han | Bi-objective optimization for robust RGB-D visual odometry[END_REF] and SLAM [START_REF] Kerl | Dense visual SLAM for RGB-D cameras[END_REF], [START_REF] Meilland | On unifying key-frame and voxelbased dense visual SLAM at large scales[END_REF]. They improve the convergence rate, however, it can be computationally expensive to estimate a λ for each new RGB-D frame.

The aim of this paper is to give the mathematical proof of the invariance to λ if a Point-to-hyperplane technique is used for minimizing different types of metrics as a single combined error. In particular, in [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF] we proposed a method to minimize a 4D joint error which is invariant to the scale factor λ where, as a side note, the alignment is accelerated by performing the searching of the nearest neighbours via 4D-vector. The method performs visual odometry on real and simulated environments by estimating the camera poses from RGB-D sequences. During the experiments, the invariance of the tuning parameter λ was empirically observed. The method is based on a Point-to-plane method for 3D Euclidean points [START_REF] Chen | Object modeling by registration of multiple range images[END_REF], but the normals are estimated in 4D space using a Principal Component Analysis (PCA) algorithm, as is done in [START_REF] Segal | Generalized-ICP[END_REF], where the eigenvector with the lowest eigenvalue is chosen as the normal. The normal is therefore closely related to the relative uncertainty in the measurements.

In order to provide the proof that the Point-to-hyperplane method is invariant to λ , this paper is structured as follows. Section II establishes a general pipeline that is common to different hybrid methods for RGB-D pose estimation. Regularly, these methods minimize the errors simultaneously and scale them to the same magnitude by λ , which weighs the contribution of each during the minimization process. In Section III, demonstrates that the Point-to-hyperplane method can minimize the error as a single vector without any influence by the choice of λ , and the approach is generalized for higher dimensions such as 6D color and depth. Finally, extended results with respect to [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF] for both, real and simulated environments, will be shown.

II. HYBRID-BASED RGB-D POSE ESTIMATION

The hybrid-based methods are useful when only geometric or color information alone are not significant enough to obtain a correct alignment. The main feature of these strategies, is that they can improve the robustness and accuracy of motion estimation than using only geometric or photometric minimization separately [START_REF] Zhang | Experimental evaluation of RGB-D visual odometry methods[END_REF]. This section will give an overview of a general model that is common to all pose estimation approaches. In particular, the hybrid-based model presented in this paper will attempt to unify both, color and depth measurements, in a common framework.

The geometric and photometric techniques, share much similarity when estimating the pose. The strategy common to many classic techniques involves the following pipeline:

1) Acquire the set of measurements (color, depth, extracted features, etc) at different viewpoints. 2) Find the closest points between the datasets based on the current best pose estimation. 3) Minimize the weighted error function and estimate an incremental update for the pose. 4) Iteratively perform all the steps from 2 until convergence. Therefore, if we develop the aforementioned stages and we consider that a RGB-D sensor is available, a 4D-vector measurement, defined here as M i = [P i I i ] ∈ R 4 , is obtained for the i-th point and its corresponding match is found in the other image. Each intensity value I i is associated with an unique 3D Euclidean point 3 which is computed by the back projection function such as: P i = K -1 p i Z i , where K ∈ R 3×3 is the intrinsic calibration matrix, p i = [p x i p y i 1] ∈ R 3 are the homogeneous pixel coordinates and Z i is the metric distance. Based on the corresponding point pairs between two datasets with an unknown pose x, an ith error metric can be defined as:

P i = [X i Y i Z i ] ∈ R
e H i = λ λ λ (M * i -f (M i , x)) ∈ R 4 (1)
where the superscript * denotes reference measurements that correspond to a keyframe. This superscript will be used throughout this paper to denote the reference measurements.

As is shown in (1), the intensity is fused with the Euclidean distance with a weight matrix λ λ λ that scales the importance of the 3D geometric points with respect to the intensities such as:

λ λ λ = λ G λ G λ G 0 0 λ I (2)
where

λ G λ G λ G = diag(λ G 1 , λ G 2 , λ G 3
). The given non-linear error in (1) is minimized iteratively using a Gauss-Newton approach to compute the unknown parameter x with increments given by:

x = -(J WJ) -1 J W λ G λ G λ G e G λ I e I (3)
where J = [ J G J I ] represents the stacked Jacobian matrices obtained by derivating the stacked geometric and photometric error functions (e G and e I , respectively), and Point-to-hyperplane method [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF], the closest points are estimated via 4D-vector and the error is minimized as a single vector, the coefficient λ is not longer any needed (see Section III).

the weight matrix W contains the stacked weights associated with each set of coordinates obtained by M-estimation [START_REF] Huber | Robust statistics[END_REF].

For the purposes of this paper, the Jacobian J I is computed by using the Second Order Minimization (ESM) method [START_REF] Benhimane | Real-time image-based tracking of planes using efficient second-order minimization[END_REF]. Often, M-estimation is performed separately on each measurement vector since their scale is different. Finally, the pose estimation T(x) is computed at each iteration and is updated incrementally as T ← TT(x) until convergence.

The bi-objective minimization has been introduced as an error function that minimizes the photometric and geometric error simultaneously for hybrid-based approaches. However, it depends on the computation of the tuning parameter λ , which has a huge influence on the minimization process. If it is well estimated, it can speed up the alignment between two different frames while maintaining robustness and accuracy. An example of the influence of the coefficient is shown in the Fig. 2, where each error is fitted into a normal Gaussian distribution.

The cited hybrid-based strategies that uses the adaptive coefficient λ [START_REF] Morency | Stereo tracking using ICP and normal flow constraint[END_REF], [START_REF] Batu Akan | 3D Head tracking using normal flow constraints in a vehicle environment[END_REF], [START_REF] Tykkälä | Direct Iterative Closest Point for Real-time Visual Odometry[END_REF], [START_REF] Steinbruecker | Large-scale multi-resolution surface reconstruction from RGB-D sequences[END_REF], [START_REF] Han | Bi-objective optimization for robust RGB-D visual odometry[END_REF], [START_REF] Kerl | Dense visual SLAM for RGB-D cameras[END_REF], [START_REF] Meilland | On unifying key-frame and voxelbased dense visual SLAM at large scales[END_REF] perform the ICP Point-to-Plane algorithm [START_REF] Chen | Object modeling by registration of multiple range images[END_REF] and a direct image-based method [START_REF] Irani | About direct methods[END_REF] whilst minimizing the error simultaneously. Generally, these strategies minimize the following error function:

e H i = λ G λ G λ G N * i (P m i -P w i ) λ I (I m i -I w i ) ∈ R 4 (4)
with λ G λ G λ G = I 3 , where P w i ∈ R 3 is the warped 3D point and I w i is the warped intensity. The 3D correspondences (matches) with their associated intensities are respectively defined by P m i and I m i . In fact, the searching of the closest points is often the most computationally expensive performed stage in the pose estimation process. Several strategies can be used, such as kd-trees, linear interpolation or performing feature-based methods using various correlation strategies.

From the cited methods above, only [START_REF] Morency | Stereo tracking using ICP and normal flow constraint[END_REF] matches the closest points using the 4D-vector in order to better constrain the search for the closest 3D points, but in that paper the minimization remains similar to the others (As is shown in Fig. 1(a)).

III. POINT-TO-HYPERPLANE

Based on the error function defined in (1) and its expanded form in ( 4), a Point-to-hypeplane minimization can be defined such that:

e H i = N * i λ λ λ (M * i -f (M i , x)) ∈ R 4 (5)
where N * i ∈ R 4 are the normals of the reference measurements and the scale parameter λ λ λ = diag (λ 1 , λ 2 , λ 3 , λ 4 ) depends of the length of the measurement vector. If hybrid measurements are used, then the concept of Point-tohyperplane is introduced and the integrated error is defined as follows:

e

H i = N * i M m i -M w i ∈ R 4 (6)
where M m i denotes the match found between the reference and the transformed current measurements:

M * i = [X * i Y * i Z * i I * i ] and M w i = [X w i Y w i Z w i I w i ]
, respectively. M w i is the measurement vector transformed by the geometric warping function w(•), which projects a 3D reference point P * i ∈ R 3 onto the current image plane. It should be noted that the tuning parameters λ λ λ are not included in [START_REF] Georgel | A unified approach combining photometric and geometric information for pose estimation[END_REF]. This is due to the fact that the normals N * are estimated by performing the cross product between the neighbouring reference points that forms an hyperplane, so that the distance of another point M w i to the formed hyperplane will be scaled by the geometric and photometric elements of λ λ λ , which have not influence since all scale elements appears for each element of the error function. The coefficient λ λ λ is not longer needed since it has not effect in the error function (This demonstration will be shown below).

In order to extend (6) to higher dimensions and to demonstrate that the method is invariant to λ λ λ , consider that the measurements vectors λ λ λ M * and λ λ λ M contain j different types of measurements that are scaled by the same magnitude λ λ λ . The general form of the equation of a plane for 3D geometric points is ax + by + cz + d = 0, where x, y, z are the coordinates of the 3D point and a, b, c defines the normal vector. Therefore, an hyperplane of dimension j can be defined as follows:

N * 1 λ 1 M * 1 + N * 2 λ 2 M * 2 + • • • + N * j λ j M * k + d = 0 (7)
where

d = -N * 1 λ 1 M * 1 -N * 2 λ 2 M * 2 -• • • -N * j λ j M * l .
The normals are calculated by performing the cross product in j dimensions such that:

N * i = V * 1 × V * 2 × • • • × V * j-1 ∈ R j (8)
where each m = 1, 2, • • • , j -1 vector V * m = λ λ λ M * k -M * l is similarly computed with the Point-to-point distance equation. The integer index k = l selects the N closest points lying in the hyperplane. N is the number of vectors employed to compute the normal (For this paper N = 8). The minimum number of vectors that are required to perform the multidimensional cross product, depends on the number of dimensions used in the measurements vector (See Fig. 3).

The elements of the normal in (8) can be expressed as:

N * i = c(λ 1 )[M * k-l ] 1 c(λ 2 )[M * k-l ] 2 • • • c(λ j )[M * k-l ] j (9)
where the operator [•] i extracts the i-th row of M * k -M * l ∈ R j , and the operator c(λ i ) corresponds to the product of the elements of the diagonal of λ λ λ except for λ i such as:

c(λ i ) = i = j j ∏ i diag(λ λ λ ), i = 1, 2, • • • , j (10)
The equation to compute the distance e H of a point λ λ λ M i to the hyperplane, which is formed by the reference points λ λ λ M * i , can be represented in general form such as:

e H i = [N * i ] 1 λ 1 M 1 + • • • + [N * i ] j λ j M j + d ([N * i ] 1 λ 1 ) 2 + • • • + ([N * i ] j λ j ) 2 (11)
where

d = -[N * i ] * 1 λ 1 M * 1 -• • • -[N * i ] * j λ j M * j and the operator [N * i ] j = c(λ j )[M * k-l
] j extracts the jth element of (9). Equation ( 11) can be easily represented in Hessian normal form as:

e H i = -N * i (M * i -M i ) (12)
where N * i is the normalization of the normal j-vector such as:

N * i =        [M * k-l ] 1 ([M * k-l ] 1 ) 2 +•••+([M * k-l ] j ) 2 . . . [M * k-l ] j ([M * k-l ] 1 ) 2 +•••+([M * k-l ] j ) 2        ∈ R j (13)
that demonstrates the invariance to λ λ λ in [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF], due to the fact that all its diagonal factors appears for both, numerator and denominator, and for each j -th element of (13) as: c(λ j )λ j . Applied to the error function in [START_REF] Georgel | A unified approach combining photometric and geometric information for pose estimation[END_REF], the following lemma is established. Lemma 3.1: The integrated error e H in jth dimension is invariant to the relative scale λ if it is minimized by a Point-to-hyperplane method.

e

H i = N * i (M * i -f (M i , x)) = N * i λ λ λ (M * i -f (M i , x
)) Proof: Consider for simplicity the 3D case instead of 4D. Three hybrid 3D points that belong to the same cloud of points M ∈ R 3×n (2D points + intensity) such as: = Π 3 T(x)M 2 . Note that the j-D case is an extension of this basic case.

M 0 = X 0 Y 0 I 0 , M 1 = X 1 Y 1 I 1 and M 2 = X 2 Y 2 I 2 ,
In order to balance the magnitude of the metric measurements, a scalar factor is applied to all the points as: λ λ λ M and λ λ λ M w , where λ λ λ is defined as λ λ λ = diag(λ X , λ Y , λ I ). The coefficients of λ λ λ are introduced in a 3D point-to-hyperplane error function such that:

e H i = N * i λ λ λ (M * i -f (M i , x)) ∈ R 3 ( 14
)
where the normals N * are computed by performing the cross product of the vectors formed from λ λ λ M. Considering the 3 hybrid points M 0 , M 1 and M 2 as reference points, the normal N * i = N X N Y N I is defined here as the cross product between the vectors V 01 and V 02 , which are defined as V 01 = λ (M 1 -M 0 ) and V 02 = λ (M 2 -M 0 ). that provides all the elements of the normal N * at M 0 such that:

N * i =   λ Y λ I V 01 Y V 02 I -V 01 I V 02 Y λ X λ I V 01 I V 02 X -V 01 X V 02 I λ X λ Y V 01 X V 02 Y -V 01 Y V 02 X   =   λ Y λ I N X λ X λ I N Y λ X λ Y N I   (15)
Equation ( 14) can be rewritten as follows:

e H i = λ X λ Y λ I N X (X i -X w ) + N Y (Y i -Y w ) + N I (I i -I w )
The normalization of the normal is calculated such as:

N i = a √ a 2 +b 2 +c 2 b √ a 2 +b 2 +c 2 c √ a 2 +b 2 +c 2 (16)
where

a = λ X λ Y λ I N X , b = λ X λ Y λ I N y and c = λ X λ Y λ I N I .
The error function of ( 14) can be minimized just as:

e H i = N i (M i -M w ) (17)
The unknown parameter x is estimated by following the same pipeline of the hybrid-based methods, where (3) is rewritten as follows:

x = -(J WJ) -1 J We H (18)
IV. RESULTS

All the experiments presented in this paper were performed on both, real and synthetic, RGB-D grayscale images. In order to improve computational efficiency, a multiresolution pyramid was used. The iterative closest points minimization can be stopped by two criteria: when the maximum number of iterations (200) is reached or if the norm of the transformation matrix is less than 1 × 10 -6 in rotation and 1 × 10 -5 in translation. The Huber influence function was employed in the M-estimator to reject outliers and obtain more robust estimations. Only one M-estimator was used for the unified measurement vector as opposed to two in [START_REF] Meilland | On unifying key-frame and voxelbased dense visual SLAM at large scales[END_REF].

The Point-to-hyperplane method is compared here with the following hybrid error function, which weights the minimization between the geometric and photometric error [START_REF] Meilland | On unifying key-frame and voxelbased dense visual SLAM at large scales[END_REF].

e H i =   λ λ λ RR(x)N * i P m i -Π 3 TT (x) P * i I i w( TT(x), P * i ) -I * i (p * i )   ∈ R 4 ( 19
)
where

P m i ∈ R 3 is the closest point in the current cloud, R ← RR(x) is the incremental update of the rotations, N * i = [N x i N y i N z i ]
are the normals of the reference points and Π 3 = [1, 0] ∈ R 3×4 is the projection matrix. For this strategy, the normals are only estimated for the geometric points (e.g. a classic Point-to-plane [START_REF] Chen | Object modeling by registration of multiple range images[END_REF] approach). The selection is done by choosing the neighbouring pixels in the color image as is shown in Fig. 3(a).

In the case of the 4-dimensional space, a 3 × 3 window is selected to compute the normals as is shown in Fig. 3(b). Based on the Generalized-ICP algorithm [START_REF] Segal | Generalized-ICP[END_REF], the Principal Component Analysis (PCA) is employed on the covariance Fig. 4: Examples of the Absolute Trajectory Error evaluation obtained by the Point-to-Hyperplane method. The benchmarck datasets [START_REF] Handa | A benchmark for RGB-D visual odometry, 3D reconstruction and SLAM[END_REF] and [START_REF] Sturm | A benchmark for the evaluation of RGB-D SLAM systems[END_REF] were used.

matrix of the 8 closest points for each point, where the eigenvector with the lowest eigenvalue corresponds to the normal vector N * i4D . An alternative algorithm that can be used to compute the normals is given in [START_REF] Badino | Fast and accurate computation of surface normals from range images[END_REF].

For the comparisons, the Point-to-hyperplane method is compared with different strategies that compute a nonadaptive λ , which are computed based on the strategies [START_REF] Men | Color point cloud registration with 4D ICP algorithm[END_REF] (The intensities are normalized λ I = I i /255) and an adaptive λ [START_REF] Tykkälä | Direct Iterative Closest Point for Real-time Visual Odometry[END_REF] (where the scale parameter is the ratio between the Median Absolute Deviation (MAD) of the errors λ G = MAD(e I )/MAD(e G )). The minimization of the error presented in [START_REF] Segal | Generalized-ICP[END_REF] will also be compared with a λ = 1 (λ is not estimated).

1) Simulated environment: In order to verify the performance of the method, 1000 synthesized images were generated with random poses. The alignment process between the generated images and its reference image ensures exact correspondences at the solution. The mean of number of iterations and computational time until reaching convergence is shown in Table I. The normals were computed only once for the reference image, obtaining 9.29 seconds.

2) Real environments: For the test with real RGB-D images the Freiburg 1 sequences from [START_REF] Sturm | A benchmark for the evaluation of RGB-D SLAM systems[END_REF] were employed to perform Visual Odometry with frame-to-frame tracking in the same way as the simulated environment [START_REF] Handa | A benchmark for RGB-D visual odometry, 3D reconstruction and SLAM[END_REF]. The performance of the hybrid-based techniques that estimate an adaptive λ is compared to the Point-to-hyperplane technique. The Absolute Trajectory Error (ATE) and Relative Pose Error (RPE) between the estimated trajectories and their respective groundtruth trajectories (Table II) are compared. It should be noted that the averages in time and number of iterations is less than the averages obtained by the Point-to-hyperplane method for sequences desk and floor, but obtaining also less error. With respect to the previous results in [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF], the experiments were carried with different strategies that estimate the scale parameter λ for hybrid-based approaches. Here, the proposed method is compared with an adaptive λ strategy that normalizes the intesities, in order to demonstrate the invariance to the scale factor. A comparison of the ATE for some of the sequences are shown in Fig. 4.

V. CONCLUSION

In this paper, it is proven mathematically that the Pointto-hyperplane approach [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF] is invariant to λ λ λ . The normals have been obtained by performing the multidimensional cross product of vectors in j dimension and the λ λ λ coefficients are shown to not influence the minimization process. Evaluations in the experiments, show that more accurate results are obtained for the Point-to-hyperplane method when the normals are estimated with the PCA algorithm instead of the cross product. However, the former algorithm requires extra computational time which is linear with the number of nearest neighbours selected in the image [START_REF] Badino | Fast and accurate computation of surface normals from range images[END_REF].

We aim to generalize this approach to any measurement fusion approach for which enough data is available to compute normals, such as color or IR measurements. the simulated and real dataset [START_REF] Handa | A benchmark for RGB-D visual odometry, 3D reconstruction and SLAM[END_REF], [START_REF] Sturm | A benchmark for the evaluation of RGB-D SLAM systems[END_REF]. It can be seen that the Point-to-hyperplane method [START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF] improves hybrid methods that combine the direct approach and the geometric Point-to-plane approach.

Fig. 1 :

 1 Fig. 1: Hybrid-based approaches. (a) A Point-to-plane ICP algorithm is minimized simultaneously with a direct imagebased method while searching the 3D closest points. The coefficient λ automatically scales both errors in the same magnitude for each new frame. (b)Point-to-hyperplane method[START_REF] Fernando | Point-to-hyperplane RGB-D pose estimation: Fusing photometric and geometric measurements[END_REF], the closest points are estimated via 4D-vector and the error is minimized as a single vector, the coefficient λ is not longer any needed (see Section III).

Fig. 2 :

 2 Fig. 2: Influence on the error function residual (Equation (19)) of the scale coefficient when (a) it is not estimated (λ = 1) and greyscale units are compared to m, (b) when the intensities and 3D points are normalized (non-adaptive λ [16]) and (c) when an adaptive λ is estimated [22]. Finally in (d) their cost function at each iteration of minimization until reach convergence is shown. It is clearly seen that non-adaptive or adaptive coefficients attempt to preserve about the same contribution of each measurement type (The photometric error and geometric error distributions are shown in red and blue, respectively).

Fig. 3 :

 3 Fig. 3: At least two vectors are needed to compute (a) the plane for 3 dimensions and (b) three vectors for 4 dimensions (In this paper 8 vectors are computed). In general, for N dimensions a N -1 vectors are needed. The points that forms the plane (or hyperplane) are selected depending on its associated pixel coordinates. Any pixel on the image can be selected as a central pixel (except for the corners) to compute the distance with its surrounding neighbours.

  and consider one warped point M w = X w Y w I w which represent any element of the warped point cloud M w f(x)

TABLE I :

 I Averages in Time and in Number of Iterations until Convergence for 1000 Synthesized Images at Random Poses.

	Method	# Iterations Time (sec)
	1) Hybrid-based + non-adaptive λ [16]	124.2280	1.5403
	2) Hybrid-based + adaptive λ [22]	152.3790	1.9019
	3) Hybrid-based (λ is not estimated)	155.0030	1.9406
	4) Point-to-hyperplane	44.6280	0.4679

TABLE II :

 II Averages in Time (miliseconds), number of iterations, Relative Pose Error (RPE) and Absolute Trajectory Error (ATE) for

ireta@i3s.unice.fr

Andrew.Comport@cnrs.fr