Nicolás Espitia

Iasson Karafyllis

Miroslav Krstic

Event-triggered boundary control of constant-parameter reaction-diffusion PDEs: a small-gain approach

Keywords: reaction-diffusion systems, backstepping control design, event-triggered control

This paper deals with an event-triggered boundary control of constant-parameters reaction-diffusion PDE systems. The approach relies on the emulation of backstepping control along with a suitable triggering condition which establishes the time instants at which the control value needs to be updated. In this paper, it is shown that under the proposed event-triggered boundary control, there exists a minimal dwell-time (independent of the initial condition) between two triggering times and furthermore the well-posedness and global exponential stability are guaranteed. The analysis follows small-gain arguments and builds on recent papers on sampled-data control for this kind of PDE. A simulation example is presented to validate the theoretical results.

Introduction

Control and estimation strategies must be implemented and validated into digital platforms. It is important to study carefully the issues concerning digital control such as sampling. This is because, if sampling is not addressed properly, the stability and estimation properties may be lost. For finite-dimensional systems, namely networked control systems modeled by ordinary differential equations (ODEs), digital control has been extensively developed and several schemes for discretization and for sampling in time continuous-time controllers have been investigated, e.g., by sampled-data control [START_REF] Hetel | Recent developments on the stability of systems with aperiodic sampling: An overview[END_REF] and event-triggered control strategies [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF][START_REF] Heemels | An introduction to event-triggered and self-triggered control[END_REF][START_REF] Marchand | A general formula for event-based stabilization of nonlinear systems[END_REF][START_REF] Lemmon | Event-triggered feedback in control, estimation, and optimization[END_REF][START_REF] Girard | Dynamic triggering mechanisms for event-triggered control[END_REF][START_REF] Postoyan | A framework for the event-triggered stabilization of nonlinear systems[END_REF][START_REF] Jiang | Event-triggered control of nonlinear systems: A small-gain paradigm[END_REF][START_REF] Liu | A small-gain-approach to robust eventtriggered control of nonlinear systems[END_REF]. The latter has become popular and promising due to not only its efficient way of using communication and computational resources by updating the control value aperiodically (only when needed) but also due to its rigorous way of implementing continuous-time controllers into digital platforms.

In general, event-triggered control includes two main components: a feedback control law which stabilizes the system ⋆ This work has been partially supported by CPER ELSAT 2020, Project, Contratech; when the first author was affiliated to the VALSE team, Inria Lille -Nord Europe.

Email addresses: nicolas.espitia-hoyos@univ-lille.fr (Nicolás Espitia), iasonkar@central.ntua.gr,iasonkaraf@gmail.com (Iasson Karafyllis), krstic@ucsd.edu (Miroslav Krstic). and an event-triggered mechanism which contains a triggering condition that determines the time instants at which the control needs to be updated. Two general approaches exist for the design: Emulation from which the controller is a priori predesigned and only the event-triggered algorithm has to be designed (as in e.g. [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF]) and Co-design, where the joint design of the control law and the event-triggering mechanism is performed simultaneously (see e.g. [START_REF] Seuret | LQ-based event-triggered controller co-design for saturated linear systems[END_REF]).

Nevertheless, for partial differential equations (PDEs) sampled-data and event-triggered control strategies without model reduction have not achieved a sufficient level of maturity as in the finite-dimensional case. It has not been sufficiently clear (from theoretical and practical point of view) how fast sampling the in-domain or the boundary continuous-time controllers should be for preserving both stability and convergence properties of PDE systems. Few approaches on sampled-data and event-triggered control of parabolic PDEs are considered in [START_REF] Fridman | Robust sampled-data control of a class of semilinear parabolic systems[END_REF][START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF] and [START_REF] Jiang | Event-driven observerbased control for distributed parameter systems using mobile sensor and actuator[END_REF][START_REF] Selivanov | Distributed event-triggered control of transport-reaction systems[END_REF][START_REF] Yao | Resource-aware model predictive control of spatially distributed processes using event-triggered communication[END_REF][START_REF] Katz | Network-based boundary observer-controller design for 1D heat equation[END_REF][START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF]. To the best of our knowledge, [START_REF] Katz | Network-based boundary observer-controller design for 1D heat equation[END_REF][START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF] are the first contributions to come up with sampled-data and observer-based event triggered boundary control for 1D reaction-diffusion systems in the presence of time-varying input delays. The approach relies on modal decomposition and proposes an observer-based event-triggered strategy that includes a novel switching-based dynamic triggering condition depending on the finite modes of the estimated state. The triggering policy, in turn, includes a suitable waitingtime parameter (for time regularization) allowing the avoid-Preprint submitted to Automatica February 3, 2021 ance of the so-called Zeno phenomena.

In the context of abstract formulation of distributed parameter systems, sampled-data control is investigated in [START_REF] Logemann | Generalized sampleddata stabilization of well-posed linear infinite-dimensional systems[END_REF] and [START_REF] Tan | Dynamic practical stabilization of sampled-data linear distributed parameter systems[END_REF]. For hyperbolic PDEs, sampled-data control is studied in [START_REF] Ma | Stability analysis of a 2 × 2 linear hyperbolic system with a sampled-data controller via backstepping method and looped-functionals[END_REF] and [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D Hyperbolic PDEs with non-local terms[END_REF]. Some recent works have introduced eventtriggered control strategies for linear hyperbolic PDEs under an emulation approach [START_REF] Espitia | Event-based control of linear hyperbolic systems of conservation laws[END_REF][START_REF] Espitia | Event-based stabilization of linear systems of conservation laws using a dynamic triggering condition[END_REF][START_REF] Espitia | Event-based boundary control of a linear 2x2 hyperbolic system via backstepping approach[END_REF], [START_REF] Espitia | Stabilization of boundary controlled hyperbolic PDEs via lyapunov-based event triggered[END_REF]. In [START_REF] Espitia | Event-based control of linear hyperbolic systems of conservation laws[END_REF], for instance, event-triggered boundary controllers for linear conservation laws using output feedback are studied by following Lyapunov techniques (inspired by [START_REF] Bastin | Stability and Boundary Stabilization of 1-D Hyperbolic Systems[END_REF]). The study has been extended in [START_REF] Espitia | Stabilization of boundary controlled hyperbolic PDEs via lyapunov-based event triggered[END_REF] while using static and dynamic output controllers (with measured output subject to event-triggered sampling and quantization) and establishing stability in different norms. In [START_REF] Espitia | Event-based boundary control of a linear 2x2 hyperbolic system via backstepping approach[END_REF], the approach relies on the backstepping method for coupled system of balance laws (inspired by [START_REF] Vazquez | Backstepping boundary stabilization and state estimation of a 2 × 2 linear hyperbolic system[END_REF][START_REF] Krstic | Backstepping boundary control for first-order hyperbolic PDEs and application to systems with actuator and sensor delays[END_REF]) which leads to a full-state feedback control which is sampled according to a dynamic triggering condition. Under such a triggering policy, it has been possible to prove the existence of a minimal dwell-time between triggering time instants and therefore avoiding the Zeno phenomena.

In sampled-data control as well as in event-triggered control scenarios for PDEs, the effect of sampling (and therefore, the underlying actuation error) has to be carefully handled. In particular, for reaction-diffusion parabolic PDEs the situation of having such errors at the boundaries has been challenging and has become a central issue; especially when having Dirichlet boundary conditions due to the lack of an ISS-Lyapunov function for the stability analysis. In [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF] this problem has been overcome by studying ISS properties directly from the nature of the PDE system (see also e.g. [START_REF] Karafyllis | Small-gain-based boundary feedback design for global exponential stabilization of 1-d semilinear parabolic pdes[END_REF][START_REF] Karafyllis | Input-to-State Stability for PDEs[END_REF]) while using modal decomposition and Fourier series analysis. Lyapunov-based approach has not been necessary to perform the stability analysis and to be able to come up with ISS properties and small-gain arguments. Thus, it has been possible to establish the robustness with respect to the actuation error. This approach has allowed the derivation of an estimate of the diameter of the sampling period on which the control is updated in a sampled-and-hold fashion. The drawback, however, is that such a period turns out to be truly small, rendering the approach very conservative. With periodic implementation, one may produce unnecessary updates of the sampled controllers, which cause over utilization of computational and communication resources, as well as actuator changes that are more frequent than necessary.

This issue strongly motivates the study of event-triggered control for diffusion-reaction PDE systems. Event-triggered control may show benefits with respect to periodic schemes as the actuation updating is done only when needed. In overall, event-triggered may represent a more realistic approach for the actuation on the PDE system. Therefore, in this paper we propose an event-triggered boundary control based on the emulation of the backstepping boundary control. An event-triggering condition is derived and the stability analysis is performed by using small-gain arguments.

The main contributions are summed up as follows:

• We prove that under the event-triggered control no Zeno solutions can appear. A uniform minimal dwell-time (independent of the initial condition) between two consecutive triggering time instants has been obtained.

• Consequently, we guarantee the existence and uniqueness of solutions to the closed-loop system. • We prove that under the event-triggered boundary control, the closed-loop system is globally exponentially stable in the L 2 -norm sense.

The paper is organized as follows. In Section 2, we introduce the class of reaction-diffusion parabolic systems, some preliminaries on stability and backstepping boundary control and the preliminary notion of existence and uniqueness of solutions. Section 3 provides the event-triggered boundary control and the main results. Section 4 provides a numerical example to illustrate the main results. Finally, conclusions and perspectives are given in Section 5.

Notation

f : [0, 1] → R such that f = 1 0 | f (x)| 2 dx 1/2 < ∞. Let u : R + × [0, 1] → R be given. u[t] denotes the profile of u at certain t ≥ 0, i.e. (u[t])(x) = u(t, x), for all x ∈ [0, 1]
. For an interval I ⊆ R + , the space C 0 (I; L 2 (0, 1)) is the space of continuous mappings

I ∋ t → u[t] ∈ L 2 (0, 1
). H 2 (0, 1) denotes the Sobolev space of functions f ∈ L 2 (0, 1) with square integrable (weak) first and second-order derivatives f ′ (•), f ′′ (•) ∈ L 2 (0, 1). I m (•), J m (•) with m ∈ Z, denote the modified Bessel and (nonmodified) Bessel functions of the first kind.

Preliminaries and problem description

Let us consider the following scalar reaction-diffusion system with constant coefficients:

u t (t, x) = εu xx (t, x) + λ u(t, x), (1) u(t, 0) = 0, (2) u(t, 1) = U(t), (3)
and initial condition:

u(0, x) = u 0 (x), (4)
where ε > 0 and λ ∈ R. u : [0, ∞) × [0, 1] → R is the system state and U(t) ∈ R is the control input. The control design relies on the Backstepping approach [START_REF] Smyshlyaev | Closed-form boundary state feedbacks for a class of 1-d partial integro-differential equations[END_REF][START_REF] Krstic | Boundary control of PDEs: A course on backstepping designs[END_REF] under which the following continuous-time controller (nominal boundary feedback) has been obtained:

U(t) = 1 0 K(1, y)u(t, y)dy. ( 5
)
It has then been proved that the under continuous-time controller (5) with control gain K satisfying:

K(x, y) = -y((λ + c)/ε) I 1 ((λ + c)/ε)(x 2 -y 2 ) ((λ + c)/ε)(x 2 -y 2 ) , (6)
evolving in a triangular domain given by T = {(x, y) : 0 ≤ y < x ≤ 1} where c ≥ 0 is a design parameter that can be chosen arbitrary, the closed-loop system (1)-( 4) is globally exponentially stable in L 2 -norm sense [START_REF] Smyshlyaev | Closed-form boundary state feedbacks for a class of 1-d partial integro-differential equations[END_REF].

2.1 Event-triggered control and emulation of the backstepping design

We aim at stabilizing the closed-loop system (1)-( 4) in an event-triggered fashion. We follow the emulation approach which means that the boundary controller is perfectly known (i.e. ( 5)-( 6)). This approach includes stabilizing on events while sampling the continuous-time controller (5) at a certain time instants that form an increasing sequence (t j ) j∈N with t 0 = 0 that will be characterized later on. The control value is held constant between two successive time instants and it is updated when some state-dependent condition is verified.

In this scenario, we need to suitably modify the boundary condition in ( 1)-( 3). The boundary value of the state is going to be given by:

u(t, 1) = U d (t), (7) with
U d (t) = 1 0 K(1, y)u(t j , y)dy, ( 8
)
for all t ∈ [t j ,t j+1 ), j ≥ 0. Note that U d (t) = U(t) + d(t) with U(t)
given by ( 5) and d given by:

d(t) = 1 0 K(1, y)u(t j , y)dy - 1 0 K(1, y)u(t, y)dy. ( 9
)
Here, d (which will be fully characterized along with (t j ) j∈N in the next section) can be viewed as an actuation deviation between the nominal boundary feedback and the eventtriggered boundary control1 .

Hence, the control problem we aim at handling can be reformulated by considering the following linear scalar reactiondiffusion PDE:

u t (t, x) = εu xx (t, x) + λ u(t, x), ( 10
) u(t, 0) = 0, (11) u(t, 1) = U d (t), (12)
for all t ∈ (t j ,t j+1 ), j ≥ 0, and initial condition:

u(0, x) = u 0 (x). ( 13
)
The emulation of the backstepping boundary control is performed by transforming ( 10)-( 13) into a target system which will reflect the influence of the deviation d(t). Indeed, the following invertible Volterra transformation

w(t, x) = u(t, x) - x 0 K(x, y)u(t, y)dy, (14)
with kernel K(x, y) satisfying (6) maps the system (10)-( 13) into the following target system:

w t (t, x) = εw xx (t, x) -cw(t, x) (15) w(t, 0) = 0 (16) w(t, 1) = d(t) ( 17
)
with initial condition:

w(0, x) = u 0 (x) - x 0 K(x, y)u 0 (y)dy, (18)
where c ≥ 0 (which is involved in ( 6)) can be chosen arbitrary. Notice that when d(t) = 0, one has that the target system is globally exponential stable. Moreover, the larger c, the faster the convergence rate.

It is worth recalling that the Volterra backstepping transformation ( 14) is invertible whose inverse is given as follows:

u(t, x) = w(t, x) + x 0 L(x, y)w(t, y)dy, ( 19
)
where L satisfies:

L(x, y) = -y((λ + c)/ε) J 1 ((λ + c)/ε)(x 2 -y 2 ) ((λ + c)/ε)(x 2 -y 2 ) . (20)

Well-posedness issues

The notion of solution for 1-D linear parabolic systems under boundary sampled-data control has been rigorously analyzed in [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF]Theorem 2.1]. In this paper, we follow the same framework and construct the solution by means of the following proposition:

Proposition 1 (Special case of [18, Theorem 2.1]). For every initial data u[t j ] ∈ L 2 (0, 1) there exists a unique function u ∈ C 0 ([t j ,t j+1 ]; L 2 (0, 1)) satisfying u ∈ C 1 ((t j ,t j+1 ) × [0, 1]), u[t] ∈ C 2 ([0, 1]
) for all t ∈ (t j ,t j+1 ] and satisfying (10)-( 12) for t ∈ (t j ,t j+1 ).

Proposition 1 allows us to construct a solution in the sense described in [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF] i.e. a solution u ∈

C 0 [0, lim j→∞ (t j ); L 2 (0, 1) with u[t] ∈ C 2 ([0, 1]) for t ∈ (0, lim j→∞ (t j )) and u ∈ C 1 ( Ĩ × [0, 1]) where Ĩ = [0, lim j→∞ (t j )) \{t j : j = 0, 1, 2, ...} which also satisfies (10)- (12) for t ∈ Ĩ.
In what follows we assume that in open loop, the system (10)-( 13) is unstable or neutrally stable, i.e., λ ≥ επ 2 ( see e.g. [25, Section 3.1] for details). We focus on this case as it constitutes a more challenging problem than considering open-loop asymptotically stable systems (i.e. λ < επ 2 ).

Event-triggered boundary control and main results

In this section we introduce the event-triggered boundary control and the main results: the existence of a minimal dwell-time which is independent of the initial condition, the well-posedness and the exponential stability of the closedloop system under the event-triggered boundary control. By building on the emulation approach, let us first define the event-triggered boundary control considered in this paper. It encloses both a triggering condition (which determines the time instant at which the controller needs to be updated) and the backstepping boundary feedback [START_REF] Espitia | Event-based boundary control of a linear 2x2 hyperbolic system via backstepping approach[END_REF]. The proposed event-triggering condition is based on the evolution of the magnitude of the actuation deviation ( 9) and the evolution of the L 2 -norm of the state.

Definition 1 (Definition of the event-triggered boundary control). Let β > 0 be a design parameter and define

k(y) := K(1, y), ( 21
)
with K being the kernel given in [START_REF] Espitia | Event-based control of linear hyperbolic systems of conservation laws[END_REF]. We define the following set:

E(t j ) := {t ∈ R + |t > t j ∧|d(t)| > β k u[t] +β k u[t j ] }, ( 22
)
where u[t] denotes the solution of (1), ( 2), ( 7) and (8) for all t ≥ t j and d(t) is defined by [START_REF] Espitia | Boundary time-varying feedbacks for fixed-time stabilization of constantparameter reaction-diffusion systems[END_REF].

The event-triggered boundary control is defined by considering the following components:

I) (The event-trigger) The times of the events t j ≥ 0 with t 0 = 0 form a finite or countable set of times which is determined by the following rules for some j ≥ 0:

a) if E(t j ) = /
0 then the set of the times of the events is {t 0 , ...,t j }. b) if E(t j ) = / 0, then the next event time is given by:

t j+1 := inf E(t j ). (23)

II) (the control action)

The boundary feedback law,

U d (t) = 1 0 k(y)u(t j , y)dy, ∀t ∈ [t j ,t j+1 ). ( 24
)
Remark 1. Since λ ≥ επ 2 and the open loop system is not asymptotically stable, it follows that k > 0. As already pointed out, β is a design parameter that will be suitably selected in the sequel.

Avoidance of the Zeno phenomena

It is worth mentioning that guaranteeing the existence of a minimal dwell-time between two triggering times avoids the so-called Zeno phenomena that means infinite triggering times in a finite-time interval. It represents infeasible practical implementations into digital platforms because it would be required to sample infinitely fast. Before we tackle the result on existence of minimal dwell-time, let us first introduce the following intermediate result.

Lemma 1. For the closed-loop system (10)-( 12), the following estimate holds, for all t ∈ [t j ,t j+1 ], j ≥ 0: sup

t j ≤s≤t j+1 ( u[s] ) ≤ Q j u[t j ] , (25)
where Q j = exp p(t j+1t j )/2 (1 +

√ 3 3 k + k √ p ) + √ 3
3 k and p > 0 is given by p = -2επ 2 + 2λ + 4 3 λ 2 .

Proof. We consider U d given by ( 24) and define

v(t, x) = u(t, x) -xU d . (26)
It is straightforward to verify that v satisfies the following PDE for all t ∈ (t j ,t j+1 ), j ≥ 0,

v t (t, x) = εv xx (t, x) + λ v(t, x) + λ xU d , ( 27
) v(t, 0) = 0, ( 28
) v(t, 1) = 0. ( 29
)
Well-posedness issues for ( 27)-( 29) readily follows while being a particular case of the PDE considered in [21, Lemma 5.2]. Now, by considering the function 2 and taking its time derivative along the solutions of ( 27)-( 29) and using the Wirtinger's inequality, we obtain, for t ∈ (t j ,t j+1 ):

V (t) = 1 2 v[t]
V ≤ -επ 2 v[t] 2 + λ v[t] 2 + U d 1 0 (λ x)v(t, x)dx.
In addition, using the Young's inequality on the last term along with the Cauchy-Schwarz inequality, we get

V (t) ≤ -επ 2 v[t] 2 + λ v[t] 2 + 1 2 U 2 d + 2 3 λ 2 v[t] 2 .
Then, for t ∈ (t j ,t j+1 ):

V (t) ≤ pV (t) + 1 2 U 2 d ,
where p = -2επ 2 + 2λ + 4 3 λ 2 . Note that p > 0 since we have assumed that λ ≥ επ 2 . Using the Comparison principle on an interval [a, b] where a > t j and b < t j+1 , one gets, for all t ∈ [a, b]:

V (t) ≤ exp (p(t -a)) V (a) + 1 2p U 2 d .
Due to the continuity of V (t) on [t j ,t j+1 ] and the fact that a, b are arbitrary, we can conclude that

V (t) ≤ exp p(t j+1 -t j ) V (t j ) + 1 2p U 2 d , (30)
v[t] 2 ≤ exp p(t j+1 -t j ) v[t j ] 2 + 1 p k 2 u[t j ] 2 .
Using the above estimate in conjunction with [START_REF] Lemmon | Event-triggered feedback in control, estimation, and optimization[END_REF] and the triangle inequalities, we obtain the following inequalities:

u[t] ≤ v[t] + √ 3 3 |U d | v[t j ] ≤ u[t j ] + √ 3 3 |U d |, together with |U d | ≤ k u[t j ] ,
we finally obtain, for all t ∈ [t j ,t j+1 ],

sup

t j ≤s≤t j+1 ( u[s] ) ≤ Q j u[t j ] ,
with

Q j = exp p(t j+1 -t j )/2 (1 + √ 3 3 k + k √ p ) + √ 3
3 k . This concludes the proof.

Theorem 1. Let β > 0 be given. Under the event-triggered boundary control (23)-( 24), there exists a minimal dwelltime between two triggering times, i.e. there exists a constant τ > 0 (independent of the initial condition u 0 ) such that t j+1 -t j ≥ τ, for all j ≥ 0.

Proof. Define g ∈ C 2 ([0, 1]) by the following equation:

g(x) := N ∑ n=1 k n φ n (x), (31)
where N ≥ 1 is an integer, k n := 1 0 k(y)φ n (y)dy, k(y) = K(1, y) with K satisfying (6) and φ n (x) = √ 2 sin(nπx), n = 1, 2... are the eigenfunctions of the Sturm-Liouville operator A : D → L 2 (0, 1) defined by

(A f )(x) = -ε d 2 f dx 2 (x) -λ f (x),
for all f ∈ D and x ∈ (0, 1) and

D ⊂ H 2 ([0, 1]) is the set of functions f : [0, 1] → R for which f (0) = f (1) = 0.
Let us also define

d(t) = 1 0 g(y) (u(t j , y) -u(t, y))dy, ( 32
)
for t ∈ [t j ,t j+1 ), for j ≥ 0 and g given by [START_REF] Orlov | Output feedback stabilization of coupled reaction-diffusion processes with constant parameters[END_REF]. Taking the time derivative of d(t) along the solutions of ( 10)-( 12) yields, for all t ∈ [t j ,t j+1 ):

ḋ(t) =ε dg dx (1)u(t, 1) -g(1) ∂ u ∂ x (t, 1) + ε g(0) ∂ u ∂ x (t, 0) - dg dx (0)u(t, 0) + 1 0
(Ag)(y)u(t, y)dy.

Note that g(1) ∂ u ∂ x (t, 1) = 0 by virtue of the function g evaluated at x = 1 as φ n (1) = 0. In addition, by the eigenvalue problem Aφ n = λ n φ n where λ n = n 2 π 2 ελ are real eigenvalues and using the boundary conditions [START_REF] Girard | Dynamic triggering mechanisms for event-triggered control[END_REF], we get

ḋ(t) =ε 1 0 k(y)u(t j , y)dy N ∑ n=1 k n dφ n dx (1) + N ∑ n=1 k n λ n 1 0
φ n (y)u(t, y)dy.

Using the Cauchy-Schwarz inequality and φ n = 1 for n = 1, 2, ... the following estimate holds for t ∈ (t j ,t j+1 ), j ≥ 0:

| ḋ(t)| ≤ ε k u[t j ] F N + u[t] G N , (33)
where

F N := ∑ N n=1 k n dφ n
dx [START_REF] Bastin | Stability and Boundary Stabilization of 1-D Hyperbolic Systems[END_REF] and

G N := ∑ N n=1 |k n λ n |.
There- fore, we obtain from [START_REF] Selivanov | Distributed event-triggered control of transport-reaction systems[END_REF] and the fact that d(t j ) = 0, the following estimate:

| d(t)| ≤ (t -t j )ε k u[t j ] F N + (t -t j ) sup t j ≤s≤t ( u[s] )G N .
(34) Note that from ( 9),( 24) and ( 32), the deviation d(t) can be expressed as follows:

d(t) = d(t) + 1 0 (k(y) -g(y))(u(t j , y) -u(t, y))dy. (35)
Hence, combining [START_REF] Seuret | LQ-based event-triggered controller co-design for saturated linear systems[END_REF] and [START_REF] Smyshlyaev | Closed-form boundary state feedbacks for a class of 1-d partial integro-differential equations[END_REF] we can obtain an estimate of d as follows:

|d(t)| ≤ (t -t j )ε k u[t j ] F N + (t -t j ) sup t j ≤s≤t ( u[s] )G N + k -g u[t j ] + k -g u[t] . (36)
Notice that if u[t j ] = 0, then Lemma 1 guarantees that u[t] remains zero. In this case, by Definition 1, one would not need to trigger anymore and thus Zeno phenomenon is immediately excluded. Let us consider now the case u[t j ] = 0. Using [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF] and assuming that an event is triggered at t = t j+1 , we have

|d(t j+1 )| ≤ (t j+1 -t j )ε k u[t j ] F N + (t j+1 -t j ) sup t j ≤s≤t j+1 ( u[s] )G N + k -g u[t j ] + k -g u[t j+1 ] , (37)
and by Definition 1, we have that, at t = t j+1

|d(t j+1 )| ≥ β k u[t j ] + β k u[t j+1 ] . (38)
Combining [START_REF] Tan | Dynamic practical stabilization of sampled-data linear distributed parameter systems[END_REF] and [START_REF] Vazquez | Backstepping boundary stabilization and state estimation of a 2 × 2 linear hyperbolic system[END_REF], we get

β k u[t j ] + β k u[t j+1 ] ≤ (t j+1 -t j )ε k F N u[t j ] + (t j+1 -t j )G N sup t j ≤s≤t j+1 ( u[s] ) + k -g u[t j ] + k -g u[t j+1 ] ,
therefore,

(β k -k -g ) u[t j+1 ] + (β k -k -g ) u[t j ] ≤ (t j+1 -t j )ε k F N u[t j ] + (t j+1 -t j )G N sup t j ≤s≤t j+1 ( u[s] ).
We select N ≥ 1 in (31) sufficiently large so that kg < β k . Notice that we can always find N sufficiently large so that the condition kg < β k , since g is simply the N-mode truncation of k (which implies that kg tends to zero as N tends to infinity). In addition, using the fact that u[t j+1 ] ≥ 0 and by [START_REF] Krstic | Boundary control of PDEs: A course on backstepping designs[END_REF] in Lemma 1, we obtain the following estimate:

(β k -k -g ) u[t j ] ≤ (t j+1 -t j )ε k F N u[t j ] + (t j+1 -t j )G N Q j u[t j ] ,
where

Q j = exp p(t j+1 -t j )/2 (1 + √ 3 3 k + k √ p ) + √ 3
3 k and p = -2επ2 + 2λ + 4 3 λ 2 strictly positive (as we have assumed that λ ≥ επ 2 ). Denoting

• a 0 := β k -k -g • a 1 := ε k F N + G N √ 3 3 k • a 2 := G N (1 + √ 3 3 k + k √ p )
we obtain an inequality of the form:

a 0 ≤ a 1 (t j+1 -t j ) + a 2 (t j+1 -t j ) exp p(t j+1 -t j )/2 , (39)
from which we aim at finding a lower bound for (t j+1t j ).

Note that the right hand side of ( 39) is a K ∞ function of (t j+1 -t j ). Let us denote it as α(s) := a 1 s + a 2 s exp (ps/2) with s = (t j+1t j ). The solution of inequality (39) is then s ≥ α -1 (a 0 ) where α -1 is the inverse of α. Since a 0 is strictly positive, then there exists τ > 0 such that s = (t j+1t j ) ≥ τ > 0. This concludes the proof.

Remark 2. For the proof of Theorem 1, we have used the approximation [START_REF] Orlov | Output feedback stabilization of coupled reaction-diffusion processes with constant parameters[END_REF] which is instrumental to find an estimate of the actuation deviation d(t) through d(t) (and ḋ(t)). Notice that we have not used directly the time-derivative of d(t) in our analysis. It can be proved that it is given as follows:

ḋ(t) = ε dk dx (1)u(t, 1) -k(1) ∂ u ∂ x (t, 1) + ε k(0) ∂ u ∂ x (t, 0) -dk dx (0)u(t, 0) + 1 0 (Ak)(s)u(t, s)ds,
for all t ∈ (t j ,t j+1 ). The main problem is that the above differential equation does not allow a derivation of an upper bound of the magnitude of ḋ(t) since it contains terms (such as k(1)

∂ u ∂ x (t, 1

)) which cannot be estimated. Actually, this specific issue constitutes one of the major challenges in the framework of ISS for reaction diffusion PDEs with linear boundary control (designed by backstepping). Having such a deviation d(t) at one of the boundaries and the incapability of finding upper bounds of terms like k(1) ∂ u

∂ x (t, 1) does not allow to perform directly a Lyapunov-based analysis. This is one of the reasons why, modal decomposition and smallgain analysis are the main tools in our approach.

Explicit dwell-time

A solution τ from (39) can be found numerically. Nevertheless, we can upper bound the right-hand side of [START_REF] Yao | Resource-aware model predictive control of spatially distributed processes using event-triggered communication[END_REF] such that

a 0 ≤ (a 1 + a 2 )(t j+1 -t j ) exp p(t j+1 -t j )/2 , ( 40
)
which turns out to be more conservative (thus, one can expect solutions of [START_REF] Yi | Time-Delay Systems: Analysis and Control Using the Lambert W Function[END_REF] to take smaller values). Furthermore, by rewriting (40) yields,

pa 0 2(a 1 + a 2 ) ≤ p 2 (t j+1 -t j ) exp p 2 (t j+1 -t j ) , (41)
so that the right-hand side corresponds to a transcendental function whose solution can be found using the so-called Lambert W function 2 (see e.g. [START_REF] Corless | On the Lambert W function[END_REF] for more details). Hence, we have

(t j+1 -t j ) ≥ 2 p W pa 0 2(a 1 + a 2 ) . ( 42
)
Note that the argument pa 0 2(a 1 +a 2 ) of the Lambert W function is strictly positive yielding W (•) to take a strictly positive value. We denote then τ := 2 p W pa 0 2(a 1 +a 2 ) > 0 being τ the minimal dwell-time between two triggering times, i.e. t j+1 -t j ≥ τ for all j ≥ 0. Remark 3. It is worth remarking that if a periodic sampling scheme -where the control value is updated periodically on a sampled-and-hold manner -is intended to be applied to stabilize the system (10)-( 13), then a period can be chosen according to [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF]. However, an alternative way of choosing a suitable period while meeting the theoretical guarantees, is precisely by using the minimal dwell-time τ that was obtained from [START_REF] Yao | Resource-aware model predictive control of spatially distributed processes using event-triggered communication[END_REF] and its explicit form by the Lambert W function as in (42). Unfortunately, as one may expect, such a dwell-time may be very small and conservative (similar to the sampling period obtained in [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF] since the derivation was done using conservative estimates).This issue, however, supports the main motivation highlighted throughout the paper: stabilize on events only when is required and in an more efficient way. Event-triggered control offers advantages with respect periodic schemes as it reduces execution times while meeting theoretical guarantees.

Since there is a minimal dwell-time (which is uniform and does not depend on either the initial condition or on the state of the system), no Zeno solution can appear. Consequently, the following result on the existence of solutions of the closed-loop system (10)-( 13) with ( 23)-( 24) holds.

Corollary 1. For every u 0 ∈ L 2 (0, 1), there exist a unique solution u ∈ C 0 (R + ; L 2 (0, 1)) to the system (10)-( 13), ( 23),( 24)

satisfying u ∈ C 1 (I × [0, 1]), u[t] ∈ C 2 ([0, 1]) for all t ∈ I where I = R + \{t j ≥ 0, j = 0, 1, 2, ...} Proof.
It is an immediate consequence of Proposition 1 and Theorem 1. Indeed, the solution is constructed (by the step method) iteratively between successive triggering times.

Stability result

In this subsection, we are going to follow small-gain arguments and seek for an Input-to-State stability property with respect to the deviation d(t).

Lemma 2 (ISS of the target system). The target system (15)-( 18) is ISS with respect to d(t); more precisely, the following estimate holds:

w[t] ≤ G exp(-σt) w[0] +γ sup 0≤s≤t (|d(s)| exp (-σ (t -s))) , (43) for any σ ∈ (0, µ 1 ) with µ 1 = π 2 ε + c, G := (1 + b -1
), for arbitrary b > 0 and the gain γ is given as follows:

γ := (1 + b)        π 2 ε+c π 2 ε+c-σ sinh 2 √ c √ ε -2 √ c √ ε 2 sinh √ c √ ε ( c ε ) 1/4 , if c = 0 1 √ 3 π 2 ε π 2 ε-σ , if c = 0. ( 44
)
Proof. See [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF]Appendix].

Theorem 2. Let L := 1 + 1 0 x 0 |L(x, y)| 2 dy dx 1/2 < ∞
with L satisfying [START_REF] Karafyllis | Small-gain-based boundary feedback design for global exponential stabilization of 1-d semilinear parabolic pdes[END_REF] and k(y) be defined by [START_REF] Karafyllis | Adaptive boundary control of constant-parameter reaction-diffusion pdes using regulation-triggered finite-time identification[END_REF]. Let σ ∈ (0, µ 1 ) with µ 1 = π 2 ε + c and b > 0 be given constants.

Let β > 0 be a design parameter (involved in the triggering condition [START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF]) that is selected in such a way that the following condition is fulfilled:

Φ e := 2β γ k L < 1 ( 45
)
where γ is defined by (44). Then, the closed-loop system (10)-( 13) with event-triggered boundary control (23)-( 24) is globally exponentially stable. More specifically, there exists a constant M > 0 such that:

u[t] ≤ M exp (-σt) u[0] , for all t ≥ 0. ( 46
)
Proof. It follows from ( 23) that events are triggered to guarantee that the following inequality holds for all t ∈ [t j ,t j+1 ) :

|d(t)| ≤ β k u[t j ] + β k u[t] . (47)
For every t ≥ 0 define, q(t) = max{t j : j ≥ 0,t ≥ t j }. Then, inequality (47) implies for all t ≥ 0

|d(t)| ≤ β k u[q(t)] + β k u[t] . (48)
Notice that q(t) ≤ t. Consequently, the inequality (48) gives for t ≥ 0

|d(t)| exp (σt) ≤ 2β k sup 0≤s≤t ( u[s] exp(σ s)) . (49)
Pick any t * ≥ 0. Inequality (49) implies the following estimate for all t ∈ [0,t * ]

|d(t)| exp (σt) ≤ 2β k sup 0≤s≤t * ( u[s] exp(σ s)) . (50)
Since (50) holds for all t ∈ [0,t * ], we obtain:

sup 0≤s≤t * (|d(s)| exp (σ s)) ≤ 2β k sup 0≤s≤t * ( u[s] exp(σ s)) .
(51) Since t * is arbitrary, we obtain from (51):

sup 0≤s≤t (|d(s)| exp (σ s)) ≤ 2β k sup 0≤s≤t ( u[s] exp(σ s)) .
(52) On the other hand, by Lemma 2, we have

w[t] exp(σt) ≤ G w[0] + γ sup 0≤s≤t (|d(s)| exp (σ s)) . (53)
Let us pick any t * ≥ 0. Then the following estimate for t ∈ [0,t * ] is a direct consequence of (53).

w[t] exp(σt) ≤ G w[0] + γ sup 0≤s≤t * (|d(s)| exp (σ s)) .
(54) Since the above estimate holds for all t ∈ [0,t * ], we obtain the following estimate:

sup 0≤t≤t * ( w[t] exp(σt)) ≤ G w[0] +γ sup 0≤t≤t * (|d(t)| exp (σt)) .
(55) Since t * is arbitrary, it follows that the following estimate holds for all t ≥ 0: < ∞ 3 and K satisfying (6), we 3 Both K and L are finite due to the properties of the modified and non modified Bessel functions. A suitable characterization of upper bounds for K and L can also be established by using e.g. the results in [START_REF] Smyshlyaev | Closed-form boundary state feedbacks for a class of 1-d partial integro-differential equations[END_REF]Theorem 2 and 3] or [START_REF] Coron | Null controllability and finite time stabilization for the heat equations with variable coefficients in space in one dimension via backstepping approach[END_REF]. obtain from (57) and (58) the following estimate for the solution to the closed-loop system (10)-( 13) with event-triggered control ( 23)- [START_REF] Krstic | Backstepping boundary control for first-order hyperbolic PDEs and application to systems with actuator and sensor delays[END_REF]:

sup 0≤s≤t ( u[s] exp(σ s)) ≤ G(1 -Φ e ) -1 K L u[0] ,
which leads to (46):

u[t] ≤ M exp (-σt) u[0] ,
with M := G(1 -Φ e ) -1 K L. This concludes the proof.

Remark 4. It is worth remarking a trade-off between the convergence rate and the sampling speed. As it can be noticed, σ affects the decay rate. The closer to µ 1 (fast decay rate), the higher γ. This requires, in light of (45), that β has to be selected small and therefore we have to trigger more frequently. In addition, notice that b affects the overshoot. If b is large, one has less overshoot. However, (44) shows that γ increases and consequently, β has to be small (recall (45); fast triggering sampling).

In the context of a co-design approach where the boundary control parameters as well as β have to be designed simultaneously, one could even formulate an optimization problem aiming at e.g. maximizing the decay rate σ while minimizing the gain γ. As event-triggered control with co-design is out of the scope of the paper, we leave these aspects for a future work.

Numerical simulations

We consider the reaction-diffusion system with ε = c = 1, λ = π 2 and initial condition u 0 (x) = ∑ 3 n=1 √ 2 n sin(nπx) + 3(x 2x 3 ), x ∈ [0, 1]. For numerical simulations, the state of the system has been discretized by divided differences on a uniform grid with the step h = 0.01 for the space variable. The discretization with respect to time was done using the implicit Euler scheme with step size ∆t = h 2 . We stabilize the system on events under the event-triggered boundary control ( 23)- [START_REF] Krstic | Backstepping boundary control for first-order hyperbolic PDEs and application to systems with actuator and sensor delays[END_REF] where the parameter β is selected such that condition (45) in Theorem 2 is verified. In addition, L = 1.8407, k = 5.61 and γ = 0.574 which is computed according to the information provided in Lemma 2. Therefore, two cases are pointing out: we choose e.g. β = 0.07 and β = 0.02 yielding Φ e = 0.83 < 1 and Φ e = 0.23 < 1, respectively. In the former case, 12 events (updating times of the control) are obtained whereas in the later case, 47 events are obtained; on a frame of 1s 4 . Figure 1 shows the numerical solution of the closed-loop system (10)-( 13) with event-triggered control ( 23)-( 24) (on the left β = 0.07 and on the right when β = 0.02, which results in slow and fast sampling, respectively). The time-evolution of control functions under the event-triggered case is shown in Figure 2 (orange line with black circle marker for slow sampling and blue line with red circle marker for fast sampling). In addition, Figure 3 shows the time evolution of the func-tions appearing in the triggering condition [START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF] (on the left with β = 0.07 and on the right with β = 0.02). Once the trajectory |d| reaches the trajectory β k u[t] + β k u[t j ] , an event is generated, the control value is updated and d is reset to zero. It can be observed that the lower β is, the faster the sampling and control updating which in turn implies smaller inter-executions times. This case turns out to be more conservative and the control function gets closer to the one in continuous case or even when considering a periodic scheme with a very small period.

As a matter of fact, it is worth remarking that a sampling period can be computed from [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF]Section 3.3]. Indeed, for the reaction-diffusion system with a boundary control whose actuation is done in a sampled-and-hold fashion, such a period would be T = 9.96 × 10 -7 . For the sake of comparison according to Remark 3 and using (42), we compute τ = 4.43 × 10 -7 (with β = 0.02) and τ = 1.55 × 10 -6 (with β = 0.07). Notice that both T and τ's are very small (even smaller than the time step discretization for the current simulations); consequently the periodic scheme turns out not be practically implementable. This is one of the reasons why event-triggered boundary control offers advantages with respect to periodic schemes. In our framework, the control value is updated aperiodically and only when needed.

Finally, we run simulations for 100 different initial conditions given by u

0 (x) = ∑ l n=1 n 2 √ 2 sin(nπx) + l(x 2 -x 3 ) for l = 1, .., 10 and u 0 (x) = ∑ l n=1 n √ 2 sin(n 2 πx) + l(x 2 -x 3
), for l = 11, ..., 100 on a frame of 1s. We have computed the interexecution times between two triggering times. We compared the cases for slow and fast sampling, i.e. when β = 0.07 and β = 0.02, respectively. Figure 4 shows the density of the inter-execution times plotted in logarithmic scale where it can be observed that, the larger β the less often is the sampling and control updating which in turn implies larger inter-executions times.

It is interesting to notice that when choosing β small (resulting in fast sampling, as aforementioned), there are several inter-execution times of the order of 10 -1.7 as depicted in blue bars in Figure 4 where the density predominates. It might suggest that a possible period (whenever one intends to sample periodically in a sampled-and-hold fashion) might be chosen with a length of the order 10 -1.7 . This issue is left for further tests and investigation with possible theoretical connections with periodic schemes as in [START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF]. This issue may give some hints on how to suitably choose sampling periods in order to reduce conservatism on periodic schemes.

Conclusion

In this paper, we have proposed an event-triggered boundary control to stabilize (on events) a reaction-diffusion PDE system with Dirichlet boundary condition. A suitable statedependent event-triggering condition is considered. It determines when the control has to be updated. It has been proved the existence of a minimal dwell-time which is independent of the initial condition. Thus, it has been proved that there is n sin(nπx) + 3(x 2 -x 3 ), x ∈ [0, 1] and under the event-triggered control ( 23)- (24). With β = 0.07 in ( 23) the control updating is slower (closed-loop solution depicted on the left). With β = 0.02 in [START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF], the control updating is faster (closed-loop solution depicted on the right). no Zeno behavior and thus the well-posedness and the stability of the closed-loop system are guaranteed.

In future work, we may consider extending the approach to output-feedback of coupled parabolic PDEs with spatiallyvarying coefficients (following e.g. [START_REF] Orlov | Output feedback stabilization of coupled reaction-diffusion processes with constant parameters[END_REF][START_REF] Deutscher | Backstepping control of coupled linear parabolic PIDEs with spatially-varying coefficients[END_REF]). In addition, robust event-triggered control with respect to external disturbances or dynamic uncertainties is of great interest as well and can be studied by extending some existing results from finite-dimensional systems [START_REF] Liu | Event-triggered input-to-state stabilization of nonlinear systems subject to disturbances and dynamic uncertainties[END_REF]. Finally, another interesting direction is to combine event-triggered control strategies with finite/fixed-time boundary control for parabolic PDEs (see e.g. [START_REF] Espitia | Boundary time-varying feedbacks for fixed-time stabilization of constantparameter reaction-diffusion systems[END_REF]) which makes use of time-varying kernels. It would imply event-triggered sampling the time-varying kernel. Of course, one will not achieve perfect finite-time stabilization to the origin but to a residual set that may be char-acterized in terms of the size of initial condition and the parameters of the event-triggered scheme.

(

  w[s] exp (σ s)) ≤ G w[0] +γ sup 0≤s≤t (|d(s)| exp (σ s)) .

  (52) with (56), we obtain sup 0≤s≤t ( w[s] exp (σ s)) ≤G w[0]+ 2β γ k sup 0≤s≤t ( u[s] exp(σ s)) ,and using the factu[t] ≤ L w[t] , we get sup 0≤s≤t ( w[s] exp (σ s)) ≤ G w[0] +Φ e sup 0≤s≤t ( w[s] exp (σ s)) ,(57)where Φ e := 2β γ k L.(58) Notice that, by virtue of (45), it holds that Φ e < 1. Thereby, using the estimate of the backstepping transformation, i.e. w[t] ≤ K u[t] with K := 1 +

Figure 1 .

 1 Figure 1. Numerical solutions of the closed-loop system (10)-(13) with ε = c = 1, λ = π 2 , initial condition u 0 (x) = ∑ 3 n=1

Figure 2 .

 2 Figure 2. Time-evolution of the event-triggered boundary control (23)-(24) (orange line with black circle marker for slow control updating, i.e. β = 0.07 in[START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF] and blue line with red circle marker for fast control updating, i.e. β = 0.02 in[START_REF] Katz | Boundary delayed observercontroller design for reaction-diffusion systems[END_REF]).

Figure 3 .

 3 Figure 3. Trajectories involved in the triggering condition (23) (on the left with β = 0.07 and on the right with β = 0.02, resulting in slow and fast sampling, respectively). Once the trajectory |d| reaches the trajectory β k u[t] + β k u[t j ] , an event is generated, the control value is updated and d is reset to zero.

Figure 4 .

 4 Figure 4. Density of the inter-execution times (logarithmic scale) computed for 100 different initial conditions given by u 0 (x) = ∑ l n=1 n 2 √ 2 sin(nπx) + l(x 2x 3 ) for l = 1, .., 10 and u 0 (x) = ∑ l n=1 n √ 2 sin(n 2 πx) + l(x 2x 3 ), for l = 11, ..., 100 on a frame of 1s. With β = 0.07 implying slow sampling and therefore larger inter-execution times (red bars) and with β = 0.02 implying fast sampling and therefore smaller inter-execution times (blue bars).

  sampling and quantization. In 56th IEEE Conference on Decision and Control (CDC), pages 1266-1271, 2017.

  R + will denote the set of nonnegative real numbers. Let S ⊆ R n be an open set and let A ⊆ R n be a set that satisfies S ⊆ A ⊆ S. By C 0 (A; Ω), we denote the class of continuous functions on A, which take values in Ω ⊆ R.

	By
	C k (A; Ω), where k ≥ 1 is an integer, we denote the class of functions on A, which takes values in Ω and has continuous
	derivatives of order k. In other words, the functions of class C k (A; Ω) are the functions which have continuous deriva-
	tives of order k in S = int(A) that can be continued continu-
	ously to all points in ∂ S ∩A. L 2 (0, 1) denotes the equivalence class of Lebesgue measurable functions

  for all t ∈ [t j ,t j+1 ]. Using the Cauchy-Schwarz inequality, we have that |U d | ≤ k u[t j ] . Using this fact in (30), we get, in addition:

In sampled-data control as in[START_REF] Karafyllis | Sampled-data boundary feedback control of 1-D parabolic PDEs[END_REF], such a deviation is called input holding error.

To the best of our knowledge, in control theory, Lambert W functions have been used within the framework of time-delay systems (see e.g.[START_REF] Yi | Time-Delay Systems: Analysis and Control Using the Lambert W Function[END_REF]).

For an infinite time horizon, one would expect infinite number of triggering times.


Danda Pani Paudel

Adlane Habed
email: adlane.habed@icube.unistra.fr

Cédric Demonceaux
email: cedric.demonceaux@u-bourgogne.fr

D Paudel
email: paudel@vision.ee.ethz.ch

P Vasseur
email: pascal.vasseur@univ-rouen.fr

Robust and Optimal Registration of Image Sets and Structured Scenes via Sum-of-Squares Polynomials

Keywords: 2D-3D registration, Structure-from-Motion, Polynomial Sum-of-Squares optimization

This paper addresses the problem of registering a known structured 3D scene, typically a 3D scan, and its metric Structure-from-Motion (SfM) counterpart. The proposed registration method relies on a prior plane segmentation of the 3D scan. Alignment is carried out by solving either the point-to-plane assignment problem, should the SfM reconstruction be sparse, or the plane-to-plane one in case of dense SfM. A polynomial Sum-of-Squares optimization theory framework is employed for identifying point-to-plane and plane-toplane mismatches, i.e. outliers, with certainty. An inlier set maximization approach within a Branch-and-Bound search scheme is adopted to iteratively build potential inlier sets and converge to the solution satisfied by the largest number of assignments. Plane visibility conditions and vague camera locations may be incorporated for better efficiency without sacrificing optimality. The registration problem is solved in two cases: (i) putative correspondences (with possibly overwhelmingly many outliers) are provided as input and (ii) no initial correspondences are available. Our approach yields outstanding results in terms of robustness and optimality.

Introduction

The emergence of affordable 3D sensors and high quality 2D cameras has triggered a growing interest in combining both imaging modalities. 3D sensors provide faithful 3D scene models in the form of dense 3D point clouds while images are used to extract texture information. High quality 3D models with mapped texture can be obtained so long as the 2D and 3D sensors are registered in a common reference frame. The two modalities are generally registered off-line and the 2D and 3D sensors kept rigidly attached during acquisition. Doing so, however, may prove impractical considering that suitable acquisition conditions for one sensor may not be adequate for the other (e.g. lighting conditions for cameras, surface orientation for 3D sensor, etc.). Some applicationspecific requirements (e.g. camera on a drone and a 3D scanner on a vehicle) may altogether prohibit the sensors to be rigidly attached. When the 2D and 3D sensors are free, reliable methods for registering the two modalities, i.e. establishing inter-modality correspondences and estimating the rigid transformation aligning their reference frames, are highly desirable.

Structure-from-Motion (SfM) techniques compute 3D point coordinates from pixel correspondences across images. It is thus tempting to regard the problem of registering 3D and 2D sensors as that of aligning two 3D point sets: one set induced by the images and the other obtained from scanner measurements. Registering 3D point clouds is a well-studied problem. Most methods use the Iterative-Closest-Point (ICP) algorithm (or its variants) [START_REF] Bartoli | 3d shape registration[END_REF][START_REF] Fitzgibbon | Robust registration of 2D and 3D point sets[END_REF][START_REF] Rusinkiewicz | Efficient variants of the ICP algorithm[END_REF]. While ICP is a local method, recent work by Yang et. al [START_REF] Yang | Go-icp: Solving 3d registration efficiently and globally optimally[END_REF] (Go-ICP) provides the very first globally optimal solution to same-scale point set registration. However, because SfM reconstructions suffer from a scale ambiguity, methods devised for registering same-scale data cannot be employed.

Most methods handling the scale ambiguity rely on establishing correspondences either between the 3D measurements obtained by both modalities or directly between scanned data and images [START_REF] Liu | Automatic 3d to 2d registration for the photorealistic rendering of urban scenes[END_REF][START_REF] Christy | Iterative pose computation from line correspondences[END_REF][START_REF] Ferraz | Very fast solution to the pnp problem with algebraic outlier rejection[END_REF]. The sought transformation parameters are then obtained by either minimizing the registration loss function or maximizing the consensus set of inliers. Note that Random Sample Consensus (RANSAC) [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] is the most widely used method for finding the set of maximum inliers. Methods based on loss function minimization are more prone to outliers than their inlier-set-maximization counterparts [START_REF] Bazin | A branch-and-bound approach to correspondence and grouping problems[END_REF]. Some approaches exploit scene knowledge or the Manhattan World assumption. For instance, methods have been devised based on line segment matching [START_REF] Liu | Automatic 3d to 2d registration for the photorealistic rendering of urban scenes[END_REF], target segmentation [START_REF] Taneja | Cityscale change detection in cadastral 3d models using images[END_REF], repeated patterns detection [START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF], mutual information maximization [START_REF] Mastin | Automatic registration of lidar and optical images of urban scenes[END_REF], and extended Chamfer matching [START_REF] Zhang | Alignment of 3d building models with satellite images using extended chamfer matching[END_REF]. Registration methods relying on establishing correspondences may be undermined by unreliable visual feature descriptors. Alternative methods, not establishing initial correspondences, have also been proposed [START_REF] Danda | Localization of 2d cameras in a known environment using direct 2d-3d registration[END_REF][START_REF] Du | An extension of the icp algorithm considering scale factor[END_REF][START_REF] Corsini | Fully automatic registration of image sets on approximate geometry[END_REF][START_REF] Plotz | Registering images to untextured geometry using average shading gradients[END_REF]. The methods in [START_REF] Danda | Localization of 2d cameras in a known environment using direct 2d-3d registration[END_REF][START_REF] Du | An extension of the icp algorithm considering scale factor[END_REF] use variants of the ICP algorithm and hence remain susceptible to partial scene overlap, scene occlusion, and high levels of outliers. The one in [START_REF] Corsini | Fully automatic registration of image sets on approximate geometry[END_REF] employs a RANSAC-based inlier set maximization in which the scale problem is handled by an extension of the 4-point congruent sets algorithm. A recent approach presented in [START_REF] Plotz | Registering images to untextured geometry using average shading gradients[END_REF] computes the average gradient magnitude over all lighting directions under Lambertian shading. These gradients are then matched with the image gradient to obtain a coarse 2D-3D registration.

As far as maximizing the set of inliers is concerned, RANSAC is non-deterministic and provides no guarantee with respect to the optimality of its solution. Globally optimal inlier set maximization methods [START_REF] Li | Consensus set maximization with guaranteed global optimality for robust geometry estimation[END_REF][START_REF] Bazin | A branch-and-bound approach to correspondence and grouping problems[END_REF] have recently been proposed for problems formulated through linear equations. Extensions to problems with nonlinear equations [START_REF] Yang | Optimal essential matrix estimation via inlier-set maximization[END_REF] is problem-specific, difficult and may result in much more complicated (possibly numerically intractable) mathematical formulations. Note that a variety of methods for solving systems of nonlinear polynomial equations exist. Some are based on Gröbner bases or homotopy continuation [START_REF] Verschelde | Algorithm 795: Phcpack: A generalpurpose solver for polynomial systems by homotopy continuation[END_REF][START_REF] Habed | new set of quartic trivariate polynomial equations for stratified camera self-calibration under zero-skew and constant parameters assumptions[END_REF]. Others use polynomial Sum-of-Squares (SoS) optimization [START_REF] Schweighofer | Globally optimal o(n) solution to the pnp problem for general camera models[END_REF][START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Parrilo | Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization[END_REF][START_REF] Olsson | The registration problem revisited: Optimal solutions from points, lines and planes[END_REF][START_REF] Chandraker | Autocalibration via rank-constrained estimation of the absolute quadric[END_REF][START_REF] Chesi | Estimating the fundamental matrix via constrained least-squares: a convex approach[END_REF]. However, such methods are dedicated to solving outlier-free systems and dealing with outliers is carried out through RANSAC.

In this paper, we address the problem of registering the 3D scan and a set of images of a structured scene captured by calibrated cameras. Our assumption is that the scene is structured in the sense that it can be segmented into and represented by planes (or planar patches). Such representation is compact [START_REF] Borrmann | The 3d hough transform for plane detection in point clouds: A review and a new accumulator design[END_REF] and can also be useful for scene knowledge-based refinement methods [START_REF] Tamaazousti | Nonlinear refinement of structure from motion reconstruction by taking advantage of a partial knowledge of the environment[END_REF]. The plane-based assumption is particularly valid when dealing with man-made environments, including (but not limited to) Manhattan World, urban and indoor scenes that are abundant with planes. In our approach, we seek the metric transformation relating the scene's planes and the SfM-induced 3D structure. The SfM structure may either be represented by a sparse set of 3D points, obtained from sparse matching across images, or by planes should a sufficiently dense matching between images be obtained and the resulting point cloud segmented. When the SfM 3D structure is a sparse set of points, registration is carried out by establishing point-to-plane correspondences. Point-to-plane registration methods are known to perform better than their point-to-point counterparts [START_REF] Aleksandr | Generalized-icp[END_REF]. When the SfMinduced 3D structure consists of planes, registration is carried out by seeking plane-to-plane correspondences.

We rely on the fact that, under metric ambiguity, both point-to-plane and plane-to-plane assignments can be expressed as a second degree polynomial in scaledquaternion and translation parameters. Our approach aims at maximizing the set of inlier assignments with guaranteed optimality of the consensus set. The consensus set maximization methods [START_REF] Li | Consensus set maximization with guaranteed global optimality for robust geometry estimation[END_REF][START_REF] Bazin | A branch-and-bound approach to correspondence and grouping problems[END_REF] discussed above are not applicable because of the nonlinearity of the problem at hand. In our approach, we use the Branchand-Bound (BnB) algorithmic paradigm to explore the scaled-quaternion and translation parameter space. As in [START_REF] Li | Consensus set maximization with guaranteed global optimality for robust geometry estimation[END_REF][START_REF] Bazin | A branch-and-bound approach to correspondence and grouping problems[END_REF], we rely on establishing optimistic and pessimistic sets of inlier assignments for pruning branches whose most optimistic sets are worse than the best pessimistic one. Our contribution is threefold:

(i) We propose a novel modeling of the point-to-plane (possibly point-to-patch) and plane-to-plane correspondence problems. Our modeling is based on a rigorous Sum-of-Squares polynomial optimization theory and is used to derive new conditions to identify, with certainty, mismatched correspondences within parameters' bounds. Our registration approach relies upon such conditions to build optimistic inlier assignment sets for given parameters' bounds. (ii) We introduce SfM-specific constraints in our modeling, namely, a plane visibility criterion and optional vague constraints on the positions of the camera. (iii) Based on our modeling and constraints, we propose a globally optimal registration algorithm that maximizes the inlier set of either point-to-plane or planeto-plane assignments in presence of putative correspondences along with its non-combinatorial counterpart in the absence of such correspondences.

Our paper is organized as follows: Section 2 provides the main results from polynomial SoS optimization theory that we exploit in our registration approach. In Section 3, we present our working hypotheses along with the assignment polynomials arising in the point-toplane and plane-to-plane alignment problems. In Section 4, we derive polynomial SoS conditions for identifying mismatches within given registration parameters' bounds. In section 5, we present our modeling of additional geometric constraints to handle the scale ambiguity, to exploit vague knowledge on camera locations, and to perform point-to-patch rather than pointto-plane registration. Plane visibility, vague camera locations, and (to a lesser extent) scaling are rather SfMspecific constraints. These, and the point-to-patch constraints, may be used to boost the search for mismatches. This leads us to the statement of our main result that we give in Section 6 along with the description of our BnB registration algorithm for point-to-plane (or pointto-patch) and plane-to-plane registration. The results of our experiments are summarized and discussed in Section ??. Section 7 concludes our work.

Polynomial Sum-of-Squares theory

In this section, we present an overview of some important results in Polynomial Sum-of-Squares optimization theory. These results account for the main ingredients of our registration approach.

Definition 1 (SoS and PSD) Let R[x] be the ring of polynomials in n variables, x = (x 1 , x 2 , . . . , x n ), with real-valued coefficients. A polynomial f

(x) ∈ R[x] is -Positive Semi-Definite (PSD) (or nonnegative) if f (x) ≥ 0 for all x ∈ R n ; -Sum-of-Squares (SoS) if there exist polynomials f i (x) ∈ R[x] such that f (x) = i f i (x) 2 .
A SoS is obviously always PSD and the converse is generally untrue. However, Hilbert [START_REF] Hilbert | Uber die darstellung definiter formen als summe von formen quadraten[END_REF] proved that, for some classes of polynomials including quadratic ones, a polynomial is PSD if and only if it is SoS. Checking whether a polynomial is PSD is NP-hard (though decidable) while checking whether a polynomial is SoS is computationally tractable using Semi-definite Programming (SDP) and employing the so-called Gram matrix of the polynomial.

Definition 2 (Gram matrix [START_REF] Powers | An algorithm for sums of squares of real polynomials[END_REF])

Consider a poly- nomial f (x) ∈ R[x] of degree 2d. Let Z d (x) be the vector of monomials of f (x) up to monomials of degree d. The matrix G such that f (x) = Z d (x) GZ d (x) is a Gram matrix of f (x). Theorem 1 ([6, 25]) A polynomial f (x) ∈ R[x]
of degree 2d is SoS if and only if there exists a real symmetric positive semi-definite Gram matrix of f (x).

Note that since odd-degree polynomials cannot be SoS, only even-degree polynomials are concerned by such test. Checking for the existence of a positive semi-definite Gram matrix G boils down to solving a Linear Matrix Inequality (LMI) feasibility problem. LMI feasibility can be efficiently solved using the interior-point algorithm [START_REF] Boyd | Convex Optimization[END_REF]. Theorem 1 allows us to check whether a polynomial f (x) is nonnegative for every x ∈ R n . One is often interested in checking whether f (x) is nonnegative in a semi-algebraic set K defined by polynomials

g i (x) ∈ R[x] such that K = {x ∈ R n : g i (x) ≥ 0, i = 1 . . . m}. (1)
This can be answered via the so-called Positivstellensatz (Psatz) [START_REF] Parrilo | Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization[END_REF]. The Psatz states that f (x) is nonnegative on K if there exist SoS polynomials σ v (x) such that

f (x) = v∈{0,1} m σ v (x)g 1 (x) v1 g 2 (x) v2 . . . g m (x) vm . (2)
Exploiting Psatz is difficult and may turn numerically intractable in practice because (2) requires 2 m SoS σ v polynomials. Putinar [START_REF] Putinar | Positive polynomials on compact semialgebraic sets[END_REF] provides a much simpler Psatz under Archimedean conditions on the so-called quadratic module.

Definition 3 (Quadratic module [START_REF] Wagner | Archimedean quadratic modules: A decision problem for real multivariate polynomials[END_REF]) The quadratic module M (g) = M (g 1 , . . . , g m ) ⊂ R[x] of polynomials g 1 (x), g 2 (x), . . . , g m (x) is the set

M (g) = {σ 0 (x) + m i=1 σ i (x)g i (x) : each σ i is SoS}. (3)
Definition 4 (Archimedean [START_REF] Wagner | Archimedean quadratic modules: A decision problem for real multivariate polynomials[END_REF]) The quadratic module M (g) of polynomials

g 1 (x), g 2 (x), . . . , g m (x) is Ar- chimedean if N - n k=1 x 2 k ∈ M (g) for some N ∈ N. Theorem 2 (Putinar's Positivstellensatz [26]) As- sume the quadratic module M (g) is Archimedean. If f (x) > 0 on K (defined by (1)), then f (x) ∈ M (g).

Assignment polynomials

In this paper, we consider a set of two or more calibrated cameras observing a scene consisting of a set P of at least four distinct planes in general positions. The scene has been scanned by a 3D sensor and segmented into these planes. A plane Π ∈ P is given by its normal 3-vector π and signed distance to the origin d. We also consider the set Y of seven or more points (lying on at least four distinct scene planes) whose projections are matched across two or more cameras. We distinguish two working hypotheses depending on whether image correspondences are sparse or dense:

when the set Y is sparse, the SfM-induced [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF] 3D points are likewise sparse. Each reconstructed point is then represented by a y ∈ R 3 of cartesian coordinates; should Y be sufficiently dense, the SfM-induced point cloud may further be segmented into a set of planes P r . Each such plane is represented by its normal 3-vector π r and distance to the origin d r .

The coordinates of the SfM-reconstructed points and/or planes and those of the scanned scene planes are represented in two distinct reference frames. The two representations of the scene also differ by a generally unknown scale factor. Consequently, the transformation aligning the SfM-reconstructed scene (whether represented by points or by planes) and the scanned scene is represented by a 3 × 3 scaled-rotation matrix Q and a translation 3-vector t. A quaternion representation with no enforcement of unit quaternion q = ( z u v w ) is used to represent the scaled-rotation matrix Q:

Q=   z 2 + u 2 -v 2 -w 2 2uv -2wz 2uw + 2vz 2uv + 2wz z 2 -u 2 + v 2 -w 2 2vw -2uz 2uw -2vz 2vw + 2uz z 2 -u 2 -v 2 + w 2   .
Aligning the SfM and scanned representations consists in finding Q and t that together map the 3D SfMreconstructed points, or alternatively the SfM-induced planes, to their corresponding planes in the scanned scene. The problem of finding the correct matches between the 3D SfM-reconstructed points and scanned planes is referred to as the "point-to-plane" assignment problem. That of finding the correct match between the SfM and scanned planes is referred to as the plane-toplane assignment problem. In both cases, the assignments are described by polynomials in the unknown entries of Q and t and which we denote by a vector x ∈ R 7 such that x = (q , t ) .

Point-to-plane assignment polynomials: When relying on point-to-plane assignments for registering the image and scanner modalities, we consider A ⊂ Y×P as a set of putative point-to-plane assignments (× refers to the cartesian product) and a = (Y, Π) ∈ A is one such assignment. The polynomial f a (x) in R[x] induced by a is given by:

f a (x) := π (Qy + t) -d. ( 4
)
If x is the true registration parameter vector, then for every correct assignment a ∈ A, f a (x) = 0.

Plane-to-plane assignment polynomials: When carrying out plane-to-plane registration, the set of putative assignments A represents a subset of P r × P. The assignment a = (Π r , Π) ∈ A is described by a 4-vector of polynomials

f a (x) := q q π r -d r + δ Q 0 t 1 π -d . (5)
Should x be the true registration parameter vector, all four polynomials in f a (x) simultaneously vanish for some value of δ = ±1.

Polynomial SoS assignment conditions

Our goal is to simultaneously estimate the registration parameters x and associated set of correct assignments.

The problem can be solved by considering either pointto-plane or plane-to-plane assignments. Note, however, that we voluntarily do not distinguish between the cases in which the initial set A is a point-to-plane putative assignments set from that in which it is a plane-to-plane one. Unless stated otherwise, f a (x) is always considered as a vector of polynomials of appropriate dimension: a 1-vector representing the single polynomial (4) induced by a point-to-plane putative assignment or a 4-vector of polynomials ( 5) induced by a plane-to-plane assignment. f a (x) = 0 means that all polynomials in this vector simultaneously vanish. We may assume, for the sake of clarity of the exposition, that, in the case of plane-toplane assignments, the value of δ = ±1 in (4) is known.

It will be made clear, further in this section (see Result 3), how the two cases are handled in our method.

Our registration approach is based on the BnB algorithmic paradigm and branching is carried out on the space of registration parameters x. At each iteration, we are given parameter intervals, in the form of two vectors x and x in R 7 whose respective entries x k and x k satisfy x k ≤ x k for k = 1 . . . 7. Although the full approach is detailed further in the paper, the idea is that such intervals are to be probed for potentially correct assignments by attempting to solve the following problem:

Problem 1 For a given a ∈ A, is there a vector x ∈ R 7 satisfying x k ≤ x k ≤ x k , k = 1 . . . 7 such that f a (x) = 0?
In other words, one would like to know whether all polynomials in f a (x) cross zero for some x within the considered bounds. The assignment would then qualify as a potential inlier, i.e. possible correct assignment, within these bounds. This is however difficult to answer. Considering only one polynomial or attempting to establish whether the polynomials in f a (x) cross zero for possibly different values of x within the bounds may seem less demanding. While doing so wouldn't make the problem any easier, considering the following alternative does: Problem 2 For a given a ∈ A, is there a vector λ a of scalars of appropriate dimension such that λ a f a (x) > 0 for every x satisfying

x k ≤ x k ≤ x k f or k = 1 . . . 7?
If λ a f a (x) > 0, then at least one of the polynomials in f a (x) is guaranteed not to cross zero. As a result, the assignment a is definitely an outlier, i.e. incorrect assignment, within the bounds. Otherwise, it is a potential inlier. Indeed, if the question of Problem 2 is answered in the affirmative, the one of Problem 1 is answered in the negative: i.e. there exist no x in the interval with which f a (x) = 0. Furthermore, one can rely on Putinar's Theorem 2 to solve Problem 2. To do so, assume we are given a set of polynomials g i (x) whose quadratic module M (g) is Archimedean: if, for λ a a vector of scalars of appropriate dimension, λ a f a (x) > 0 for all x ∈ K = {x ∈ R 7 : g i (x) ≥ 0, i = 1 . . . m}, then λ a f a (x) ∈ M (g). Hence, there must exist SoS polynomials σ i such that:

λ a f a (x) - m i=1 σ i (x)g i (x) is SoS. (6)
Note that, in general, if (6) is satisfied, then λ a f a (x) may not be necessarily positive in K since K could possibly be empty. However, so long as K is not empty and σ i SoS polynomials can be found, one is guaranteed that λ a f a (x) > 0 everywhere in K since

m i=1 σ i (x)g i (x) > 0 in K.
There are two main pending issues before one is able to use [START_REF] Choi | Sums of squares of real polynomials[END_REF]. First, one needs to find a set of polynomials g i (x), representative of the parameter intervals, whose quadratic module M (g) is Archimedean. Second, it is so far unclear how the σ i SoS polynomials can be found. Let us explore now the first of these issues. Note that the Archimedean property is a matter of representation and the quadratic module of the set constructed from the linear interval constraints x k -x k ≥ 0 and x k -x k ≥ 0 is not Archimedean. In the following, we show that quadratic polynomial inequalities derived from such bound constraints yield an Archimedean quadratic module. k to be in M (g) with the g k (x) polynomials of this proposition, there must exist SoS polynomials σ 0 (x) and σ k (x), k = 1 . . . 7, such that

Proposition 1 Consider the polynomials g k (x) = (x k - x k )(x k -x k ), k = 1 . . .
N - n k=1 x 2 k = σ 0 (x) + 7 k=1 σ k (x)(x k -x k )(x k -x k ). ( 7
)
In particular, because σ 0 (x) must be SoS, the proof boils down to establishing the existence of SoS σ k (x), k = 1 . . . 7 that can turn σ 0 (x), of the form

σ 0 (x) = N - 7 k=1 x 2 k - 7 k=1 σ k (x)(x k -x k )(x k -x k ), (8)
into a SoS polynomial. The polynomial σ 0 (x) can be rewritten as

σ 0 (x) = N - 7 k=1 x 2 k + σ k (x)(x k -x k )(x k -x k ) . (9)
Let us first show that a PSD, not necessarily SoS, σ 0 (x) exists. To do so, we thus seek σ k (x), k = 1 . . . 7, for which there exists N satisfying

N ≥max x 7 k=1 x 2 k + σ k (x)(x k -x k )(x k -x k ) . (10)
Such N exists if the polynomial argument of max(.) is concave. Observe that using zero-degree SoS polynomials σ k that are independent from x, i.e. nonnegative real scalars, this polynomial is quadratic. Its expansion into

7 k=1 (1 -σ k )x 2 k + σ k (x k + x k )x k -σ k x k x k (11)
shows that its Hessian matrix, H = diag((1 -σ 1 ), (1σ 2 ), . . . , (1 -σ 7 )), is diagonal. This polynomial is then concave if H is negative-definite which happens for σ k > 1 for k = 1 . . . 7. This shows that N and nonnegative scalars (SoS) σ k , k = 1 . . . 7, do exist for σ 0 (x) to be PSD. Furthermore, σ k being scalars, σ 0 (x) is a quadratic polynomial. As discussed in Section 2, Hilbert [START_REF] Hilbert | Uber die darstellung definiter formen als summe von formen quadraten[END_REF] showed that, for quadratic polynomials, every PSD polynomial is SoS.

Let us now consider the problem of checking whether or not [START_REF] Choi | Sums of squares of real polynomials[END_REF] is SoS when considering the polynomials g k (x), k = 1 . . . 7 of Proposition 1. If so the assignment a is definitely an outlier within the bounds. If one knows beforehand that λ a f a (x) must be positive, a sequence of σ k (x) of increasing degree can be used until a positivity certificate is obtained. However, for the problem at hand, when a set of σ k (x) of some degree fails to deliver such certificate, it is either because λ a f a (x) indeed crosses zero (inlier) or the required degree for a positivity certificate has not been reached. The good news here is that, within a BnB search, the considered bound intervals [x, x] get smaller and we show in the following that using nonnegative scalars σ k rather than SoS polynomials of higher degree suffices. To see this, consider the following proposition: Proposition 2 Let x ∈ R 7 with known entries. The following statements are equivalent

(i) λ a f a (x) > 0. (ii) ∃ nonnegative scalars σ k ∈ R, k = 1 . . . 7: λ a f a (x) + 7 k=1 (x k -xk ) 2 σ k > 0. ( 12
)
Proof (ii) =⇒ (i) is straightforward. For (i) =⇒ (ii), consider λ a f a (x)'s Gram matrix G f and G x that of 7 k=1 (x k -xk ) 2
. These matrices are defined by: f a (x) = x G f x and

7 k=1 (x k -xk ) 2 = x G x x.
Note that G x is PSD and can be written as G x = U U with Ux = 0. The Gram matrix of the polynomial in ( 12) is then written as G f + U diag(σ 1 , σ 2 , . . . , σ 7 )U. A direct application of Finsler's lemma [START_REF] Finsler | Uber das vorkommen definiter und semidefiniter formen in scharen quadratischer formen[END_REF] is that the latter matrix is positive-definite if and only if x G f x > 0. This, not only shows (i) =⇒ (ii), but also proves the equivalence of the two statements.

We now state the following preliminary result:

Result 3 (Preliminary) Consider two vectors x and x in R 7 whose respective entries x k and x k satisfy x k ≤ x k for k = 1 . . . 7. Let K b be the set [START_REF] Fitzgibbon | Robust registration of 2D and 3D point sets[END_REF] a ∈ A be either a point-to-plane or plane-to-plane putative assignment, and f a (x) the vector of polynomials induced by this assignment (4) for point-to-plane and (5) for plane-to-plane).

K b = {x ∈ R 7 : g k (x) := (x k -x k )(x k -x k ) ≥ 0},
If ∃ a vector λ a of appropriate dimension and nonnegative scalars σ k such that

λ a f a (x) - 7 k=1 g k (x)σ k ( 14
)
is SoS, then λ a f a (x) > 0 for every x k ≤ x k ≤ x k . In this case, one of the polynomials in f a (x) never crosses zero within the considered bounds of x. The assignment a is then guaranteed to be an outlier (a point-to-plane or plane-to-plane mismatch) within these bounds. Otherwise, a is a potential inlier. Note that, in the case of a plane-to-plane assignment a, the latter is deemed an outlier only if ( 14) is found to be SoS for both values ±1 of δ in [START_REF] Chesi | Estimating the fundamental matrix via constrained least-squares: a convex approach[END_REF].

Furthermore, a consequence of Proposition 2 is that when x k -x k tends towards zero, we are guaranteed that any outlier within the bound is detected. Indeed, this can be seen by noticing that when x k = x k = xk , polynomial [START_REF] Habed | new set of quartic trivariate polynomial equations for stratified camera self-calibration under zero-skew and constant parameters assumptions[END_REF] turns into [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF].

Whether ( 14) is SoS can be tested by converting it into its corresponding Gram matrix LMI feasibility problem for the λ a and σ k indeterminates. Although the guarantee of identifying outliers using scalar σ k multipliers is demonstrated with a zero-gap bound, in practice, outliers are detected very early in the process. As demonstrated in our experiments, the ability to detect outliers is improved with every size reduction of the investigated bounds. It may be tempting to use higher degree σ k (x) SoS polynomials to boost the process. However, this is unnecessary and yields slower performances compared to branching.

Semi-algebraic sets for geometric constraints

Recall that our goal is to register a SfM-induced reconstruction of points or planes and a plane-segmented scanned scene. Unlike when dealing with 3D-3D registration, additional geometric constraints emanating from the cameras can be exploited. Some may be implicit, such as plane visibility, others, such as vague camera locations, may be obtained from extra knowledge. In addition, when dealing with segmented scanned scenes, one is given planar patches rather than infinite planes. These patches can be used for point-to-patch in lieu of point-to-plane registration to restrict the location of the SfM-induced points patches. In all cases, these constraints are described by quadratic polynomial inequalities that may augment the semi-algebraic set K b derived from the bound constraints. Indeed, adding new polynomial inequalities to those in K b has no effect on the Archimedean property of its quadratic module and Proposition 2 still holds. Note though that some of the constraints presented herein, which we refer to as "generic constraints", may be exploited in both pointto-plane and plane-to-plane registration. Others are applicable only to point-to-plane registration.

Generic constraints

Whether engaging in point-to-plane or plane-to-plane, extra-knowledge about vague camera locations or scale information can be used as additional registration constraints.

Camera bounds: A camera center C may lie within a box delimited by six planes in the set Ψ = {Ψ k } 6 k=1 defined by their normal vectors ψ k and signed distances d k . Such information can be obtained from applicationspecific knowledge (GPS, moving vehicle, etc.). This knowledge can be used for further enforcing the search for point-to-plane or plane-to-plane outliers and turns very useful when no putative correspondences are initially known. Consider the cartesian coordinate vector c of the camera center and let

K c ={x ∈ R 7 : h k (x) := (ψ k (Qc + t) -d k )δ k ≥ 0, k = 1 . . . 6} (15)
where δ k is the known sign, with respect to Φ k , of any point within the considered box. If h k (x) are positive, the camera center is within the box. One can now test if λ a f a (x) > 0 whenever the camera center is in the box defined by K c .

Quaternions and scale: In the absence of scale, quaternion parameters demand that q q = 1. When dealing with a scaled scene, the rotation is represented by a scaled quaternion matrix and one can only enforce that q q > 0. It is understood that, in order to keep the problem numerically tractable via the Archimedean property, all registration parameters need to be bounded. The scale of the scene is no exception. When a better lower bound s > 0 on the scale s is available, it is advised to enforce that q q ≥ s. This condition not appear in the set K b and hence must be accounted for.

Assuming the entries x k , k = 1 . . . 4 of x correspond the quaternion parameters, we consider the set

K q = {x ∈ R 7 : q(x) := -s + 4 k=1 x 2 k ≥ 0} (16)
Furthermore, since both q and -q yield the same rotation matrix, the initial lower bound of one of the quaternion parameters may arbitrarily be chosen nonnegative. The rest of the quaternion parameters may be initially bounded between -√ s and √ s where s is the scale's upper bound.

Additional point-to-plane geometric constraints

In addition to camera bounds and scale constraints, other constraints can be used when dealing specifically with point-to-plane registration.

Patches: Consider a plane Π, from the scanned scene, and three or more planes Φ k , not necessarily from the scene, orthogonal to it. The Φ k planes must be chosen such that their intersection with Π defines a convex region on Π. The set of points on Π within this convex region is a patch. In practice, four such planes are adequate to represent meaningful patches in manmade environments. Each Φ k is described by its normal vector φ k and signed distance d k . Let us denote by Φ the set {Φ k } 4 k=1 and let δ k = ±1 be the known sign, with respect to Φ k , of a scanned point lying within the considered region. In the point-to-patch case, we can then identify outliers by checking whether point-toplane f a (x) (4) is positive everywhere within x s bounds and in the set

K Φ a ={x ∈ R 7 : p k (x) := (φ k (Qy + t) -d k )δ k ≥ 0, k = 1 . . . 4} (17)
The polynomials in this set indicate the sign of the point Y , with coordinates y, with respect to each Φ k .

Plane visibility: Consider a point Y on a scene plane Π. If this point is imaged by two cameras, then these can only observe the same side of the plane: the one on which the point lies. In order for the cameras to observe the same side of the plane, their camera centers must lie on one side with respect to Π. Camera centers can easily be obtained from the SfM-calculated camera matrices: they are their right null space. Let C k be the camera centers of n ≥ 2 cameras with cartesian coordinates c k . We define the set K δ Π such that

K δ Π ={x ∈ R 7 : v k (x) := (π (Qc k + t) -d)δ ≥ 0, k = 1 . . . n} (18)
where δ = ±1. We denote K + Π the set K δ Π obtained using δ = +1 and K - Π otherwise. A given assignment a is a definite outlier if f a (x) > 0 in K + Π and in K - Π (in addition to patch and bounds conditions). Furthermore, planes for which v 1 (x) and v 2 (x) (for two cameras 1 and 2) always have opposite signs within x s bounds cannot be assigned any points visible in those cameras. This would indicate that the plane always cuts the base-line of the two camera and cannot contain points visible in both cameras. Testing this can be carried out by checking, for δ = ±1, whether

∃σ k : v 1 (x) - 7 k=1 g k (x)σ k is SoS, ∃σ k : -v 2 (x) - 7 k=1 g k (x)σ k is SoS. (19)
If for both values of δ, each polynomial in [START_REF] Liu | Automatic 3d to 2d registration for the photorealistic rendering of urban scenes[END_REF] is SoS, plane Π shall not be considered for assigning SfM points emanating from those cameras.

Registration

The preliminary results in Result 3 apply to both pointto-patch and plane-to-plane registration problems. Based on these results and the semi-algebraic sets presented in Section 5, we are now ready to state additional results for point-to-plane, or rather plane-to-patch, and planeto-plane registration. These results along with those in Result 3 are used in our BnB registration algorithm which is also presented in this Section.

Result 4 (Point-to-patch) Assume we are given a putative point-to-plane assignment a = (Y, Π) ∈ A, a patch on Π delimited by the planes in the set Φ = {Φ k } 4 k=1 , lower x and upper x bounds on the registration parameter vector x, bounds s and s on the scale of the scene, and (optionally) bounds defined by planes

Ψ = {Ψ k } 6
k=1 on the location of the camera of one (possibly more) camera. One would like to know whether or not the SfM-reconstructed point Y may lie on Π, while Π is visible by the cameras observing Y , within the patch Φ with registration parameters in the bounds x and x. In order to establish whether such assignment is possible, we consider the set

K = {x ∈ R 7 : x ∈ K b ∩ K Φ a ∩ K δ Π ∩ K c ∩ K q ) ( 20
)
resulting from the intersection of all the sets defined by ( 13),( 17),( 18), ( 15) and ( 16). If there exist a scalar λ a and nonnegative scalars σ k , σ k , σ k , σ k and σ such that

λ a f a (x) - 7 k=1 g k (x)σ k - 4 k=1 p k (x)σ k - n k=1 v k (x)σ k - 6 k=1 h k (x)σ k -q(x)σ (21)
is SOS, then λ a f a (x) > 0 in K and the assignment a is a definite outlier. It is a potential inlier otherwise.

Note that a point-to-plane version of this results can simply be obtained by not using K Φ a to construct K.

Result 5 (Plane-to-plane) Assume we are given a putative plane-to-plane assignment a = (Π r , Π) ∈ A, lower x and upper x bounds on the registration parameter vector x, bounds s and s on the scale of the scene, and (optionally) bounds defined by planes Ψ = {Ψ k } 6 k=1 on the location of the camera centers of one (possibly more) camera. One would like to know whether or not the SfM-reconstructed plane Π r may be aligned with Π for registration parameters in the bounds x and x. In order to establish whether such assignment is possible, we consider the set

K = {x ∈ R 7 : x ∈ K b ∩ K c ∩ K q ) ( 22
)
resulting from the intersection of all the sets defined by ( 13), ( 15) and ( 16). If there exist a 4-vector λ a of scalars and nonnegative scalars σ k , σ k and σ such that

λ a f a (x) - 7 k=1 g k (x)σ k - 6 k=1 h k (x)σ k -q(x)σ (23)
is SOS, then λ a f a (x) > 0 in K and the assignment a is a definite outlier. It is a potential inlier otherwise.

Recall that SoS problems ( 21) and ( 23) in these results can be solved as a LMI feasibility problem.

Our registration approach is based on Results 4 and 5. In the following, we use the term point-to-plane to refer to both point-to-plane and point-to-patch assignments. The goal of the BnB algorithm is to estimate the registration parameters yielding the largest number of inliers. Our algorithm is provided either a set of putative point-to-plane or plane-to-plane correspondences. In the absence of such correspondences, we consider every SfM-induced point or plane to be putatively assigned to all the planes (or patches) in the scanned scene. A dynamically-built search tree, whose nodes are registration parameters' bounds, allows to explore the space of parameters. Given an assignments and bounds on the registration parameters, the algorithm (see Algorithm 1) estimates the optimistic number of potential inliers using appropriate semi-algebraic sets from Results 4 and 5. A local refinement method, explained below, is used to obtain a pessimistic number of inliers for each given node. We keep track of the highest number of potential inliers (bestPessimistic in Algorithm 1) over all bound intervals. Any node whose optimistic number of inliers is worse than bestPessimistic is rejected. Otherwise, the node is qualified and branched along its longest edge resulting in two new nodes to be processed. The node corresponding to the bestPessimistic number of inliers is processed first. The algorithm terminates when no node has an optimistic number of inliers that is better than bestPessimistic. To qualify a point as an inlier, we distinguish two cases:

1. Putative point-to-plane (resp. plane-to-plane) correspondences are provided: a point-to-plane (resp. plane-to-plane) assignment qualifies as a potential inlier if (21) (resp. 23) is not proven SoS. 2. No putative correspondences are provided: the pointto-plane (resp. plane-to-plane) assignment is considered a potential inlier as soon as (21) (resp. 23) is not proven SoS.

Local refinement: To maximize the bestPessimistic number of inliers, the local method iteratively refines the registration parameters. The refinement process starts from the mid-values of the registration parameters' bounds. In order to be representative of the node, it searches the optimal solution within the investigated bounds. Given the assignments, the algorithm iteratively updates the registration parameters to:

argmin x∈K b a∈A ||f a (x)|| 2 . ( 24
)
At each iteration, only those assignments with |f a (x)| < ξ are selected some threshold ξ. In case of insufficient number of assignments, the refinement process is terminated with the best obtained output so far.

Discussion: In general, our method converges while the explored bounds are still quite large. The solution maximizing the inlier consensus set is the one returned by the local method. When the bounds are large enough, polynomials constructed from noisy data would still cross zero within the bounds allowing inliers, although affected by noise, to be accounted for. Therefore, the robustness to noise is more influenced by the local method than it is by the SoS tests. In our implementation, no special care was taken to further deal with noise when using SoS tests. However, in the case of highly noisy data, the proposed SoS framework may allow to deal more efficiently with noise by incorporating an extra bounded variable (bounded by the allowed threshold), accounting for noise. For example, if the point-to-plane assignment polynomial a (x) does not cross zero at the sought solution, f a (x) + (for some value of ) would. Furthermore, we have assumed throughout that the camera information fed to our algorithm is, to some extent, reliable. Should incorrect/noisy information about a camera be used, it may cause, especially with small camera bounding boxes, the registration to fail. In such cases, the camera-to-box constraints may be include in the set of putative assignments when maximizing the consensus set.

Conclusion

We proposed a method for registering a 3D scan and a set of images of a structured scene. The proposed approach is based on the theory of polynomial SoS optimization. Our method uses SoS registration conditions for point-to-plane as well as plane-to-plane registration. The method presented in this paper can incorporate various constraints emanating from scene and camera knowledge (patch segmentation, camera locations, plane visibility, scaling, etc.). Using Branch-and-Bound and SoS theory, we devised a robust and optimal method for inlier set maximization of either point-toplane or plane-to-plane correspondences. Although the problem is nonlinear and combinatorial, our method has provided outstanding results in terms of robustness and optimality. In particular, the employed optimization framework has the potential to be efficiently applied to other nonlinear Computer Vision problems.

7 .

 7 The quadratic module M (g) of these polynomials is Archimedean.Proof As per Definition 4, for M (g) to qualify as Archimedean, one ought to demonstrate that N -n k=1 x 2 k ∈ M (g) for some N ∈ N. Definition 3 indicates that, for N -n k=1 x 2

Acknowledgements This research has been funded by the International Project NRF-ANR DrAACaR: ANR-11-ISO3-0003, the Regional Council of Bourgogne and European Regional Development Fund.