Laribi Med Amine
email: med.amine.laribi@univ-poitiers.fr

Giuseppe Carbone

Zeghloul Saïd

On the Optimal Design of Cable Driven Parallel Robot with a Prescribed Workspace for Upper Limb Rehabilitation Tasks

Keywords: LAWEX robot design, bionic robot, cable-driven robots, optimization, power of the point, rehabilitation tasks

This paper deals with an optimization approach to design a cable driven parallel robot intended for upper limb rehabilitation tasks. The cable driven parallel robots have characteristics that make them best candidate for rehabilitation exercise purposes such as large workspace, re-configurable architecture, portability and cost effectiveness. Here, both the cable tensions that are needed to move a wristband as well as the workspace need to be carefully optimized for fulfilling the prescribed operation tasks. A specific case of study is addressed in this work by referring to LARM wire driven exercising device (LAWEX), which is applied to upper limbs exercises. To that end, a motion capture system is used to collect quantitative data on the prescribed workspace of a human upper limb. A specific optimization problem is settled up for considering combining two optimization goals, namely, the smallest robot size reaching a prescribed workspace and the minimum cable tension distributions. A sequence of optimization steps is defined using Genetic Algorithms (GAs) applied to LAWEX robot. The proposed objective function is based on a mathematical formulation of the power of a point with respect to bounding surfaces in combination with a performance index to show the distributions of the minimum cable tensions.

Introduction

The rehabilitation of the upper or lower limb after neurological injury, illness or disease is often slow and difficult. In this scope, the therapists have to achieve as much function as possible and work towards an individual's own goals. This clinic action is expensive and time request. In that regard, the robotic researchers focus on the development of new and innovative technologies based on the use of powerful mechatronic systems for rehabilitation, such as the development of cable driven robot [START_REF] Kollet | Exercise system for physical rehabilitation and fitness[END_REF][START_REF] Bhugra | Exoskeleton for Gait Assistance and Rehabilitation, US Patent[END_REF][START_REF] Scholz | Wearable Cable-Driven Exo-Skeleton for Functional Arm Training[END_REF] . The systems enable patients reach their goals in a fast, more responsive and motivating way. This helps doctors and therapists guide their patients through the rehabilitation process in faster, goal focused and cost effective way.

Cable driven parallel robots present many advantages among classic robots, namely parallel and serial robots [START_REF] Ceccarelli | Fundamentals of Mechanics of Robotic Manipulation[END_REF] . The intrinsic flexibility of cables is one of the major characteristic of cable driven parallel robots, which leads them to provide excellent performances as the light weight, high velocity and acceleration [START_REF] Landsberger | A new design for parallel link manipulator[END_REF][START_REF] Miura | Variable geometry truss and its application to deployable truss and space crane arms[END_REF] . In addition, the ease of assembly and reconfiguration make them well suited for rehabilitation devices [START_REF] Merlet | Wire-driven parallel robot: Open issues[END_REF] . In literature, we can list some examples of cable driven robots for rehabilitation. For instance: MARIONET and STRING-MAN are dedicated to gait rehabilitation proposed by Merlet [START_REF] Merlet | A family of modular wire-driven parallel robots[END_REF] and Surdilovic et al. [START_REF] Surdilovic | STRING-MAN: Wire-robot technology for safe, flexible and human-friendly gait rehabilitation[END_REF] , respectively. NeReBot, CALOWI and MACARM are devices dedicated to upper limb rehabilitation proposed by Rosati et al. [START_REF] Rosati | On the use of cable-driven robots in early inpatient stroke rehabilitation[END_REF] , Ceccarelli [START_REF] Ceccarelli | Problems and experiences on cable-based service robots for physiotherapy applications[END_REF] and Mayhew et al. [START_REF] Mayhew | Development of the MACARM a novel cable robot for upper limb neurorehabilitation[END_REF] , respectively.

The design approaches are linked in most of the time to specification requirements defined for instance by a prescribed workspace [START_REF] Merlet | Designing a parallel manipulator for a specific workspace[END_REF][START_REF] Schonherr | Evaluation and optimum design of parallel manipulators having defined workspace[END_REF][START_REF] Bhattacharya | On the optimum design of stewart platform type parallel manipulators[END_REF] , stiffness properties [START_REF] Takeda | Kinematic synthesis of in-parallel actuated mechanisms based on the global isotropy index[END_REF] and/or kinematic behaviour including pose accuracy, maximum operation speed and maximum output force [START_REF] Gosselin | On the design of efficient parallel mecha-nisms[END_REF] . As well and due to the system complexity, these approaches are solved based on optimisation processes under mono or multi criteria design. Parallel robots have been addressed with optimal design approaches with multi-criteria formulation in many works [START_REF] Hao | Multi-criteria optimal design of parallel manipulators based on interval analysis[END_REF][START_REF] Ottaviano | A procedure for the multiobjective design of parallel manipulators[END_REF][START_REF] Gosselin | Cable-driven parallel mechanisms: State of the art and perspectives[END_REF] . On other side, cable driven parallel robots (considered close to parallel robots family) are less studied in a multi-criteria optimal approach [START_REF] Carbone | A study of feasibility for a limb exercising device[END_REF] .

The present work puts forward an approach dedicated to design a cable driven parallel robot. Multi-criteria optimal approach is proposed as based on the distance computation and the cable tension values. The first criterion allows locating a point, defined by its coordinates, compared to the cable driven parallel robot workspace using the power function definition of a point. The second criterion is based on the minimum cable tension at any position within the workspace.

The paper is structured as follows: Section 2 introduces the cable driven parallel robot as well as its kinematics description and wrench set. The specification requirements, to be satisfied by the cable driven robot, are defined by a prescribed workspace carried out through the record of rehabilitation exercises of the upper limb. Section 3 formulates the multi-criteria optimization problem leading to the optimal design variables for the LARM wire driven exercising device (LAWEX) robot sweeping a prescribed workspace and a minimal distribution of cable tensions. The implementation of the optimization algorithm and the numerical results of the cable driven parallel robot for upper limb rehabilitation are presented. Section 4 summarises some remarking outcomes and perspectives of the present study.

Characteristics and design requirements

System description: LAWEX robot

The main difference between analysis of a cable-driven parallel robot and other parallel architecture robots is related with the cables being only able of pulling. This characteristic leads to a mandatory condition, which should be verified by each cable, and only a positive tension can be accepted. Consequently, the workspace of cable driven robot is defined by all poses in Cartesian space of the end-effector where all cables tensions are positive. Many researches addressed the problems related with the identification problem of the feasible workspace kinds due to the cable behaviour.

In particular, constraints for LAWEX robot are itemized here:

(1) Each motor is connected to one cable; and therefore in the considered LAWEX robot, there are 3 motors and 3 cables.

(2) Each cable of the robot should present a positive tension at all times; this is due to the only-pull property.

(3) Only end-effector positions, which are leading to static equilibrium, are considered.

(4) The end-effector is defined by a point mass, only position is considered and not orientation. Thus, forces may be exerted but not moments.

(5) Dynamic effects are neglected as referring to the slow speeds of limb exercising.

A particular attention is given in this work to workspace of cable driven parallel robot. LAWEX robot dedicated to rehabilitation tasks is considered as a case of study. The first prototype of LAWEX robot, Fig. 1, has been developed in Cassino [START_REF] Ceccarelli | Fundamentals of Mechanics of Robotic Manipulation[END_REF][START_REF] Merlet | Designing a parallel manipulator for a specific workspace[END_REF] . This cable robot design is inspired to facilitate the interaction with patient during the rehabilitation exercises [START_REF] Surdilovic | STRING-MAN: Wire-robot technology for safe, flexible and human-friendly gait rehabilitation[END_REF] , which explains its parallelepiped corner architecture. The patient arm is related to the end-effector of LAWEX robot via a wristband to be moved in translation through cables in pull and in equilibrium with gravity [START_REF] Rosati | On the use of cable-driven robots in early inpatient stroke rehabilitation[END_REF] . One notices that the considered LAWEX robot configuration includes three actuators (MX-64 dynamixel with torque equal to 6 Nm) and three cables.

Three cables are used to move the end-effector and each one controlled by an actuator. The gravity, as shown in Fig. 2, contributes to maintain the only-pully condition.

The architecture of the cable driven parallel robot is depicted in Fig. 2. The three cables as well as three actuators are located in the upper plane at a d distance from the ground. The location of each actuator M i,{i=1,2,3} is given by the cartisian coordinates of point C i,{i=1,2,3} in the frame (O, x, y, z). The position vector of each point can be written as: According to these vectors, the LAWEX robot can be described by four independent design variables r, a, b and d. These design variables will appear in the expression of cable lengths, l i , which is bounded between min i l and max i l . The Inverse Kinematic Model (IKM) addresses the problem of determining the lengths at rest of the cables for a given pose of the platform. IKM requires solving a square system of equations where each one can geometrically describe a sphere centred on point C i with radius l i . For a given point on the platform, point P on the wristband (Fig. 2) defined by its coordinates, the relation between design variables and the cable length is written as, for i = 1, 2, 3:

22 2 2 () () () . ii i p Cp C p C i Xx Yy Zz l -+ -+ -= (4)
The workspace that is accessible by the point P is a volume in Cartesian space. This volume is the intersection of three simple geometric forms, three spheres, expressed mathematically by the Eq. ( 1). If a bounding condition is considered, the following square system of equations can be written:

22 2 2 max () () () , ii i pC p C pC Xx Yy Zz l -+ -+ -= (5) 22 2 2 min () () () . ii i pC p C pC Xx Yy Zz l -+ -+ -= (6)
Eqs. ( 5) and ( 6) are useful to locate a given point in space defined by its coordinates. The point location is achieved and compared to the accessible workspace as based on the mathematical definition of the power of the point [START_REF] Vaida | On human robot interaction modalities in the upper limb rehabilitation after stroke[END_REF] . If one considers a point with coordinates X, Y, and Z and a given LAWEX robot, the point is inside the accessible workspace if and only if the following two equations are satisfied:

222 2 max max () ( ) ( ) ( ) 0 , iii i CCC PX x Y y Z z l μ = -+ -+ -- ≤ (7) 222 2 min min () ( ) ( ) ( ) 0 . iii i CCC PX x Y y Z z l μ = -+ -+ -- ≥ (8)
A boundary of the accessible workspace is depicted in Fig. 3. This geometric construction is obtained using Eqs. ( 4) and ( 5) and for i C z = d. It is important to mention that the obtained workspace represents all positions reachable for the platform but not necessary for satisfying the condition of only-pulling on cables. This issue will be considered in section 2.3.

Prescribed workspace: rehabilitation task

In this section, the rehabilitation exercise was studied in order to identify the prescribed workspace to be considered in the design procedure of the cable driven parallel robot. This step is carried out with the assistance of experts in physiotherapy and neurology. The rehabilitation task is focused on the upper limb motion and specifically on the motion of the shoulder joint with an unfolded arm. To that end, a patient has been asked to perform a motion that we recorded using the Vicon motion capture system (Fig. 4). A set of high-resolution cameras allowing detecting a number of reflective markers has been used. The cameras of Vicon system are connected to acquisition platform unit defined by a host PC with Nexus software for processing. The Nexus software allows to visualize in a 3D environment the detected markers and, specifically, to calculate positions of the used 19 markers. More details on additional experimentations and rehabilitation exercise can be found in Refs. [13] and [21]. After the post-processing step, a real trajectory of a rehabilitation task is obtained. Here, the reconstruction models under Nexus are composed of three segments (arm, forearm and torso) as shown in Fig. 5.

The point P is located on the center of rotation of the wrist and its coordinates are computed as a middle point between markers RAD and ULNA, as shown in Fig. 5. A trajectory can be obtained using successive positions of point P after experimental motion tracking, corresponding to the rehabilitation exercise. All matrix computations from segment reference frame to the fixed terrestrial reference frame are implemented under Matlab [START_REF] Laribi | Analysis and dimensional synthesis of the DELTA robot for a prescribed work-space[END_REF] . In addition to the trajectory performed to move the joint without any assistance to the muscles surrounding the joint, the range of motion characterising the patient exercise is reported in Table 1. In order to facilitate the comprehension, the range of motion is represented on a sphere and slices on this sphere along frontal, transverse and sagittal planes are given in Fig. 6.

The obtained range of motion is referring to a healthy subject. This choice is motivated by the fact that the prescribed workspace should reflect a larger range of motion as possible but based on a real case. This workspace/trajectory defined by a set of position in space will be considered as an input for the optimal design of the cable driven parallel robot.

Wrench set analysis

The positive tensions condition should be satisfied at all poses of the mobile platform of a cable driven parallel robot. The identification of the accessible workspace is not enough to perform the design issue. For the case of LAWEX robot, the maximum achievable workspace is a trigonal prism. The three motors constitute the three upper vertices of this trigonal prism, as shown in Fig. 7. The prescribed workspace must be inside this static equilibrium workspace. Additional conditions will be discussed in this paragraph through the wrench set analysis.

The cable driven robot accomplishes a motion during the desired tasks by exerting wrenches on the end-effector. For a given pose, it is possible to compute the set of all possible wrenches that the cables can apply to the end-effector.

Considering positive tension in all cables, the Jacobian relationship for parallel robots can be applied for cable driven robots. Thus, the cable wrench set can be computed by examining the positive range space of the transpose of the Jacobian matrix. The linear relationship between the cable tensions, T, and the resulting wrench, $, applied on the end-effector can be described using:

T , = $J T with { } { } max min 1, 2,3 1, 2,3 ii tt t ∈∈ ≥≥ ( 9
)
where T is cable tensions vector given by:

T 123 [, , ]. tt t = T ( 10
)
J T is the transpose of Jacobian matrix:

T 123

[, , ] , $$ $ = J (11) with $ i being the wrench along the ith cable defined by the unit vector u i along calble i and vector c i from P (center of the mass of the end-effector), as shown in Fig. 8.

. 0

i i i ii ⎧⎫ ⎧⎫ == ⎨ ⎬⎨ ⎬ × ⎩⎭ ⎩⎭ u PC $ cu ( 12
)
The constant external wrench is applied to the end-effector. Typically, the gravitational wrench, , 0

m ⎧ ⎫ = ⎨ ⎬ ⎩⎭ g g $
where m is the mass of the end-effector (about 1.5 kg in the case of the forearm with the wristband) and g is the gravitational vector, directed downward. Dexterity index is widely used for determining the workspace performance of a cable-driven robot and as a cost function in design optimization [START_REF] Laribi | Analysis and dimensional synthesis of the DELTA robot for a prescribed work-space[END_REF][START_REF] Carbone | Design issues for an inherently safe robotic rehabilitation device[END_REF] . This index is defined by Gosselin as the condition number of the Jacobian matrix [START_REF] Gosselin | On the design of efficient parallel mecha-nisms[END_REF] . The dexterity index indicates how close the end-effector pose is to singularity and informs about the system performance in terms of velocity and force transmission. In this paper, the dexterity index is considered and its distribution is computed in section 4.

Cable robot design and optimization process 3.1 Formulation of the problem

The aim of this section is to formulate the optimi-zation problem of selecting the independent design variables for the LAWEX robot having the prescribed trajectory within its workspace with minimum positive tensions in the cables. For the design of the driven cable parallel robot, two constraints should be satisfied: a non-negative cable tension and a non-negative power function for each point on the prescribed workspace/trajectory. All feasible solutions that will be found by the proposed design approach should verify the two previous conditions. The solution that minimizes the maximum tensions over all the cables will be selected and considered as an optimal one. The prescribed trajectory, noted by Ω, is given by a set of points in 3D space. This trajectory is linked to the prescribed workspace arising from the real motion of rehabilitation defined at section 2.2.

The proposed approach is summarized in Fig. 9 and the corresponding general optimization problem can be formulated as follows:

Given: Prescribed trajectory, set of points in 3D space derived from rehabilitation movements.

Find: Optimal independent design variables of the LAWEX robot having the smallest workspace that:

(1) Includes prescribed trajectory.

( For every trajectory to be generated by LAWEX robot, cable-based parallel robot for rehabilitation, the vector of independent design variables is defined as: The last three elements of the design vector, Eq. ( 13), represent the Cartesian coordinates of the center of the shoulder. The optimal location of this joint will be investigated by the proposed algorithm, which will handle the optimal placement problem of the cable robot compared to the patient. Fig. 10 shows the way how the shoulder joint, point O s , is located in (x, y) plane, respectively by S x and S y .

Optimisation process

One of kinematic properties of serial and parallel robots is their workspaces. All accessible poses by the end-effector allow building the workspace, which can be described in most of the cases by an association of simple geometric forms [START_REF] Lamine | Design study of a cable-based gait training machine[END_REF][START_REF] Pusey | Design and workspace analysis of a 6-6 cable-suspended parallel robot[END_REF] . A mathematical formulation of the workspace can then be written and integrated in the expression of an objective function [START_REF] Fattah | On the design of cable-suspended planar parallel robots[END_REF][START_REF] Hamida | Geometric based approach for workspace analysis of translational parallel robots[END_REF] . An additional kinematic property, as singularities distribution, can be associated and handled by the objective function.

In the present formulation, we address the design problem of a cable-driven parallel robot for prescribed workspace with minimum tension over all the cables. Due to the fact that a cable can only exert a pulling force, workspace analysis of LAWEX robot is mainly limited by the constraint of keeping non-negative tensions in all the cables at all times. The constraint of having non-negative tensions for all reached poses, defines the so-called Wrench-Feasible Workspace (WFW). For the design of LAWEX robot, this condition has to be satisfied for each pose of a given prescribed workspace.

The objective function to minimize F(I), Eq. ( 11), handles the both constraints linked to the desired workspace and the cable tensions. The first part F 1 of the objective function given by Eq. ( 12), is defined by functions min (, ) A performance index is proposed, for the second part F 2 given by Eq. ( 13), to show the distribution of the minimum cable tensions in a specified region of the workspace. This index is a normalized quadratic sum of the force tensions and computed subject to a positive cable tension condition.

The optimal design vector of the LAWEX robot, I opt =[a b r d S x S y S z ] T , with a prescribed trajectory Ω inside its workspace, will be obtained through the optimisation process as a final result.

Numerous optimization techniques can be used to find the optimal solution to the problem specified in Eq. ( 9). The procedure consists of finding the combination of design variable values that yields to the best objective function value, while satisfying all the equality and inequality constraints. Some techniques such as flooding techniques, simulated annealing can have much better chance of finding the global or near global optimum than the other algorithms. They still cannot guarantee the convergence. Genetic algorithms (GAs) differ from traditional search and optimization methods [START_REF] Laribi | Identification of upper limb motion specifications via visual tracking for robot assisted exercising[END_REF] . GAs proceed in parallel from a population of points. This solver has the ability to avoid being trapped in local optimal solution. The fitness score, obtained from objective functions, is directly used without other derivative or auxiliary information. Due to all previous significant points and the successful use in design issue [START_REF] Essomba | Optimal synthesis of a spherical parallel mechanism for medical application[END_REF] , the GAs are applied here.

A penalty function method is used to handle the constraints and to ensure that the fitness of any feasible solution is better than the infeasible ones. The objective function is accordingly constructed as:

ii ii K k ii ii F μμ μμ == = == ∑+ ∑ =∑ ∑+ ∑ I ( 16
)
F 2 is the normalized quadratic sum of the force tensions and given by:

T 2 1 () ( ) , max( ) F = ⋅⋅ I TT T ( 17
)
and F 31 and F 32 are penalty functions defined respectively as:

33 31 1 1 min 1 max () ( (, ) (, ) ) , Ki i ki i FP P δ δ == = =∑ ∑ +∑ II I ( 18
)
where min min min 0( , ) 0 (, ) , (, ) 0 Here, χ is a large positive number. F 31 = 0 and F 32 = 0 that the constraints linked to a non-negative power function and non-negative cable tension, respectively, have been satisfied for all points on the prescribed trajectory Ω.

i i i P P P μ δ χμ ⎧ ≥ ⎪ = ⎨ < ⎪ ⎩ I I I (19)

Optimization results

This section presents the obtained results through the implementation of the GAs to solve the optimization problem of the cable driven parallel robot. The outcomes are the optimal design variables of the optimal solution of LAWEX robot allowing reaching all points on the prescribed trajectory. The different steps of GAs are depicted in Fig. 11 and accommodated with the fitness functions Eqs. ( 11) - (17). The parameters of the Genetic Algorithms are basically the population size equal to 600 and the upper and lower bounds for each design variable useful to initialize the population, given in Table 2.

The approach described in Fig. 11 with its different steps was implemented in MATLAB®, using the Global Optimization Toolbox™ and its genetic algorithm as implemented in the ga() function. As the number of generation in the GAs was limited and due to mutation, different results were generated that finally had to be judged by application. In the following table, the geometry parameters of the most promising optimization result are given. The minimum and maximum limits considered for the tensions are equal to 1 N and 200 N, respectively.

The power of points at a given height z = d is represented in Fig. 12 by a mapping of the objective function F as a function of x and y for a given design vector. The minimum values of F are located at the intersections of the surfaces. The results obtained in this section are the output of the algorithm presented in previous section and developed within Matlab. The optimal solution obtained by the GA is presented in Table 2.

The GAs converge to the optimal solution presented in Table 2 after computation time estimated in about 5 seconds and a number of evaluation function equal to 6000 (100 generations and a population of 600 individuals). The maximal tension distributions as well as the cable tension index over the static equilibrium workspace are shown in Figs. 13 and14. The distributions are given for z equal to 1000 and 50, respectively. The optimal solution will avoid singular configurations. The end-effector poses are far from singularity as observed through the dexterity distribution defined as the inverse of the condition number of the Jacobian matrix, Figs. 13 and14.

The optimal solution is given in Fig. 15 with the prescribed trajectory, Ω, obtained through motion tracking detailed in section 2. The positions of the motors will be adjusted according to the obtained solution, and the cable driven parallel robot can be reconfigurable.

Conclusion

In this paper, an optimisation approach has been presented for the design of a cable driven parallel robot with a prescribed workspace. Two optimization goals have been handled by the proposed approach, namely, the smallest robot size reaching a prescribed workspace and the minimum cable tension distributions. The optimisation is carried out using Genetic Algorithms (GAs) subject to the constraints being the non-negative power function and the non-negative cable tensions. The feasibility of the proposed approach is presented through a case of study. Namely, the cable driven LAWEX robot is addressed by referring to its specific application for exercising of human upper limbs. A real subject exercise is obtained through a motion capture session and used as prescribed workspace.

Fig. 1 A

 1 Fig. 1 A prototype of LAWEX robot at LARM.

Fig. 2

 2 Fig.2The cable-driven parallel robot and a wristband as its end-effector.

Fig. 3 A

 3 Fig. 3 A 3D representation of accessible workspace of a cable driven robot.

Fig. 4

 4 Fig. 4 Motion capture system set-up and subject with markers.

Fig. 5

 5 Fig. 5 Reconstruction of several detected markers into segments: arm, forearm and torso.

Fig. 6

 6 Fig. 6 (a) Shoulder range of motion for extended arm; (b) RoM projection on frontal, transverse and sagittal planes.

Fig. 7

 7 Fig. 7 (a) Slice of the accessible workspace in XY plane at Z = d; (b) Static equilibrium workspace for a three-cable.

  ) Minimizes the maximum tensions over all the cables.The general associated optimization problem, with n parameters for a suitably chosen objective function Ƒ(I) can be stated as: min Ƒ(I)

Fig. 8

 8 Fig. 8 Diagram of kinematic parameters.

Fig. 9

 9 Fig.9 Optimal design approach of cable driven parallel robot for prescribed workspace.

  between the point P and the bounding surfaces of the robot workspace. The expressions min i μ as well as max i μ applied to a point P allow to compute distances to the surfaces defined by min 0 i μ = as well as max 0 i μ = .

Fig. 10

 10 Fig. 10 Center of the shoulder joint, O s , in (x, y) plane.

Fig. 11

 11 Fig.11GAs flow chart to optimal design a cable driven parallel robot.

Fig. 12

 12 Fig. 12 Power function of the point at a given z function of x and y.

Fig. 13

 13 Fig. 13 (a) Distribution of maximal cable tensions in daN; (b) distribution of the cable tensions index; (c) distribution of dexterity index for a given high z = 1000 in (x, y) plane.

Fig. 14 (

 14 Fig. 14 (a) Distribution of maximal cable tensions in daN; (b) distribution of the cable tensions index; (c) distribution of dexterity index for a given high z = 50 in (x, y) plane.

Fig. 15

 15 Fig.15 Optimal solution of cable driven robot with prescribed trajectory Ω.

Table 1

 1 Angle limits in frontal, transverse and sagittal planes

			Min (˚)	Max (˚)
		Frontal	-124	53
	Extended forearm	Transversal	-30	98
		Sagittal	-87.5	140

Table 2

 2 The bounding interval for design variables

	I	a	b	r	d	S x	S y	S z
	max	10	10	10	10	-1500	-1500	-1500
	min	1000	1000	500	1500	1500	1500	1500

Table 3

 3 The optimal solution for the cable driven robot, LAWEX

	I opt	a 1086	b 1086	r 25	d 1420	S x 600	S y 600	S z 600

Acknowledgment

The paper presents results from the research activities of the project ID 37_215, MySMIS code 103415 "Innovative approaches regarding the rehabilitation and assistive robotics for healthy ageing" co-financed by the European Regional Development Fund through the Competitiveness Operational Program 2014-2020, Priority Axis 1, Action 1.1.4, through the financing contract 20/01.09.2016, between the Technical University of Cluj-Napoca and ANCSI as Intermediary Organism in the name and for the Ministry of European Funds.

The video tracking research is supported by ROBOTEX, the French national network of robotics platforms (N° ANR-10-EQPX-44-01) and by the French National Research Agency (ANR-14-CE27-0016).


Matthieu Vilain
email: matthieu.vilain@u-bordeaux.fr

Rémi Giraud
email: remi.giraud@u-bordeaux.fr

Hugo Germain

Guillaume Bourmaud
email: guillaume.bourmaud@u-bordeaux.fr

Are Semi-Dense Detector-Free Methods Good at Matching Local Features?

Keywords: Image matching, Transformer, Pose estimation

Semi-dense detector-free approaches (SDF), such as LoFTR, are currently among the most popular image matching methods. While SDF methods are trained to establish correspondences between two images, their performances are almost exclusively evaluated using relative pose estimation metrics. Thus, the link between their ability to establish correspondences and the quality of the resulting estimated pose has thus far received little attention. This paper is a first attempt to study this link. We start with proposing a novel structured attention-based image matching architecture (SAM). It allows us to show a counter-intuitive result on two datasets (MegaDepth and HPatches): on the one hand SAM either outperforms or is on par with SDF methods in terms of pose/homography estimation metrics, but on the other hand SDF approaches are significantly better than SAM in terms of matching accuracy. We then propose to limit the computation of the matching accuracy to textured regions, and show that in this case SAM often surpasses SDF methods. Our findings highlight a strong correlation between the ability to establish accurate correspondences in textured regions and the accuracy of the resulting estimated pose/homography. Our code will be made available.

Introduction

Image matching is the task of establishing correspondences between two partially overlapping images. It is considered to be a fundamental problem of 3D computer vision, as establishing correspondences is a precondition for several downstream tasks such as structure from motion [START_REF] Heinly | Reconstructing the World* in Six Days *(as Captured by the Yahoo 100 Million Image Dataset)[END_REF][START_REF] Schönberger | Structurefrom-motion revisited[END_REF], visual localisation [START_REF] Svärm | City-scale localization for cameras with known vertical direction[END_REF][START_REF] Sattler | Are large-scale 3D models really necessary for accurate visual localization?[END_REF][START_REF] Taira | In-Loc: Indoor visual localization with dense matching and view synthesis[END_REF] or simultaneous localization and mapping [START_REF] Strasdat | Double window optimisation for constant time visual slam[END_REF][START_REF] Sarlin | LaMAR: Benchmarking Localization and Mapping for Augmented Reality[END_REF]. Despite the abundant work dedicated to image matching over the last thirty years, this topic remains an unsolved problem for challenging scenarios, such as when images are captured from strongly differing viewpoints [START_REF] Arnold | Map-free visual relocalization: Metric pose relative to a single image[END_REF]) [START_REF] Jin | Image Matching across Wide Baselines: From Paper to Practice[END_REF], present occlusions [START_REF] Sarlin | LaMAR: Benchmarking Localization and Mapping for Augmented Reality[END_REF] or feature day-to-night changes [START_REF] Zhang | Reference pose generation for long-term visual localization via learned features and view synthesis[END_REF].

An inherent part of the problem is the difficulty to evaluate image matching methods. In practice, it is often tackled with a proxy task such as relative or absolute camera pose estimation, or 3D reconstruction. In this context, image matching performances were recently significantly improved with the advent of attention layers [START_REF] Vaswani | Attention is all you need[END_REF]. Cross-attention layers are mainly responsible for this breakthrough [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF] as they enable the local features of detected keypoints in both images to communicate and adjust with respect to each other. Prior siamese architectures [START_REF] Yi | LIFT: Learned invariant feature transform[END_REF][START_REF] Ono | LF-Net: learning local features from images[END_REF][START_REF] Dusmanu | D2-net: A trainable CNN for joint description and detection of local features[END_REF], [START_REF] Revaud | R2D2: reliable and repeatable detector and descriptor[END_REF], [START_REF] Germain | [END_REF][START_REF] Germain | Neural reprojection error: Merging feature learning and camera pose estimation[END_REF] had so far prevented this type of communication. Shortly after this breakthrough, a second significant milestone was reached [START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF] by combining the usage of attention layers [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF] with the idea of having a detector-free method [START_REF] Rocco | Neighbourhood consensus networks[END_REF]Rocco et al., 2020a;[START_REF] Rocco | NCNet: neighbourhood consensus networks for estimating image correspondences[END_REF][START_REF] Li | Dualresolution correspondence networks[END_REF], [START_REF] Zhou | Patch2Pix: Epipolar-guided pixel-level correspondences[END_REF][START_REF] Truong | Learning accurate dense correspondences and when to trust them[END_REF]. In LoFTR [START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF], low-resolution dense crossattention layers are employed that allow semi-dense low-resolution features of the two images to communicate and adjust to each other. Such a method is said to be detector-free, as it matches semi-dense local features instead of sparse sets of local features coming from detected keypoint locations [START_REF] Lowe | Object recognition from local scaleinvariant features[END_REF].

Semi-dense Detector-Free (SDF) methods [START_REF] Chen | Aspanformer: Detector-free image matching with adaptive span transformer[END_REF][START_REF] Giang | TopicFM: Robust and interpretable feature matching with topic-assisted[END_REF][START_REF] Wang | Matchformer: Interleaving attention in transformers for feature matching[END_REF][START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF], [START_REF] Mao | 3DG-STFM: 3D geometric guided student-teacher feature matching[END_REF][START_REF] Tang | Quadtree attention for vision transformers[END_REF], such as LoFTR, are among the best performing image matching approaches in terms of pose estimation met-LoFTR+QuadTree SAM (ours) MA@2=60.6 MA text @2=84.0 errR=2.1' errT=5.4' MA@2=62.8 MA text @2=64.0 errR=5.5' errT=22.4' [START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF]+QuadTree [START_REF] Tang | Quadtree attention for vision transformers[END_REF]) -a semi-dense detector-free approach (line colors indicate the distance in pixels with respect to the ground truth correspondent). We report: (MA@2) -the matching accuracy at 2 pixels computed on all the semidense locations of the source image with available ground truth correspondent (which includes both textured and uniform regions), (MA text @2) -the matching accuracy at 2 pixels computed on all the textured semi-dense locations of the source image with available ground truth correspondent (i.e., uniform regions are ignored), (errR and errT) -the relative pose error. SAM has a better pose estimation but a lower matching accuracy (MA@2), which seems counterintuitive. However, if we consider only textured regions (MA text @2), then SAM outperforms LoFTR+QuadTree.

rics. However, to the best of our knowledge, the link between their ability to establish correspondences and the quality of the resulting estimated pose has thus far received little attention. This paper is a first attempt to study this link.

Contributions -We start with proposing a novel Structured Attention-based image Matching architecture (SAM). We evaluate SAM and 6 SDF methods on 3 datasets (MegaDepth -relative pose estimation and matching, HPatches -homography estimation and matching, ETH3D -matching).

We highlight a counter-intuitive result on two datasets (MegaDepth and HPatches): on the one hand SAM either outperforms or is on par with SDF methods in terms of pose/homography estimation metrics, but on the other hand SDF approaches are significantly better than SAM in terms of Matching Accuracy (MA). Here the MA is computed on all the semidense locations (of the source image) with available ground truth correspondent, which includes both textured and uniform regions.

We propose to limit the computation of the matching accuracy to textured regions, and show that in this case SAM often surpasses SDF methods. Our find-ings highlight a strong correlation between the ability to establish accurate correspondences in textured regions and the accuracy of the resulting estimated pose/homography (see Figure 1).

Organization of the paper -Sec. 2 discusses the related work. The proposed SAM architecture is introduced in Sec. 3 and the experiments in Sec. 4.

Related work

Since this paper focuses on the link between the ability of SDF methods to establish correspondences and the quality of the resulting estimated pose, we only present SDF methods in this literature review and refer the reader to [START_REF] Edstedt | Dkm: Dense kernelized feature matching for geometry estimation[END_REF][START_REF] Zhu | Pmatch: Paired masked image modeling for dense geometric matching[END_REF][START_REF] Ni | PATS: Patch area transportation with subdivision for local feature matching[END_REF] for a broader literature review.

To the best of our knowledge, LoFTR [START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF] was the first method to perform attention-based detector-free matching. A siamese CNN is first applied on the source/target image pair to extract fine dense features of resolution 1/2 and coarse dense features of resolution 1/8. The source and target coarse features are fed into a dense attention-based module, interleaving self-attention layers with cross-attention layers as proposed in [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF]. To reduce the computational complexity of these dense attention layers, Linear Attention [START_REF] Katharopoulos | Transformers are RNNs: Fast autoregressive transformers with linear attention[END_REF] is used instead of vanilla softmax attention [START_REF] Vaswani | Attention is all you need[END_REF]. The resulting features are matched to obtain coarse correspondences. Each coarse correspondence is then refined by cropping 5×5 windows into the fine features and applying another attentionbased module. Thus for each location of the semidense (factor of 1/8) source grid, a correspondent is predicted. In practice, a Mutual Nearest Neighbor (MNN) step is applied at the end of the coarse matching stage to remove outliers.

In [START_REF] Tang | Quadtree attention for vision transformers[END_REF], a QuadTree attention module is proposed to reduce the computational complexity of vanilla softmax attention from quadratic to linear while keeping its power, as opposed to Linear Attention [START_REF] Katharopoulos | Transformers are RNNs: Fast autoregressive transformers with linear attention[END_REF] which was shown to underperform on local feature matching [START_REF] Germain | Visual correspondence hallucination[END_REF]. The QuadTree attention module is used as a replacement for Linear Attention module in LoFTR. An architecture called ASpan-Former is introduced in [START_REF] Chen | Aspanformer: Detector-free image matching with adaptive span transformer[END_REF] that employs the same refinement stage as LoFTR but a different coarse stage architecture. Instead of classical cross-attention layers, the coarse stage uses globallocal cross-attention layers that have the ability to focus on regions around current potential correspondences. MatchFormer [START_REF] Wang | Matchformer: Interleaving attention in transformers for feature matching[END_REF] [START_REF] Wang | Pyramid vision transformer: A versatile backbone for dense prediction without convolutions[END_REF][START_REF] Xie | Segformer: Simple and efficient design for semantic segmentation with transformers[END_REF] and Linear Attention [START_REF] Katharopoulos | Transformers are RNNs: Fast autoregressive transformers with linear attention[END_REF] are employed. A feature pyramid network-like decoder [START_REF] Lin | Feature pyramid networks for object detection[END_REF]

is used to output a fine tensor of size 2× H 2 × W 2 ×C f and a coarse tensor of size 2× H 8 × W 8 ×C c
, and the matching is performed as in LoFTR.

TopicFM [START_REF] Giang | TopicFM: Robust and interpretable feature matching with topic-assisted[END_REF] follows the same global architecture as LoFTR with a different coarse stage.

Here, topic distributions (latent semantic instances) are inferred from coarse CNN features using crossattention layers with topic embeddings. These topic distributions are used to augment the coarse CNN features with self and cross-attention layers. In [START_REF] Mao | 3DG-STFM: 3D geometric guided student-teacher feature matching[END_REF], a method called 3DG-STFM proposes to train the LoFTR architecture with a student-teacher method. The teacher is first trained on RGB-D image pairs. The teacher model then guides the student model to learn RGB-induced depth information.

Structured attention-based image matching architecture

In the following section, we present our novel Structured Attention-based image Matching architecture (SAM), whose architecture is illustrated in Figure 2.

Background and notations

Image matching -Given a set of 2D query locations {p s,i } i=1...L in a source image I s , we seek to find their

2D correspondent locations { pt,i } i=1...L in a target im- age I t : { pt,i } i=1...L = M I s , I t , {p s,i } i=1...L .
(

) 1
Here M is the image matching method. In the case of semi-dense detector-free methods, the query locations {p s,i } i=1...L are defined as the source grid locations using a stride of 8. As we will see, SAM is more flexible and can process any set of query locations. However, for a fair comparison, in the experiments all the methods (including SAM) will use source grid locations using a stride of 8 as query locations.

Vanilla softmax attention -A cross-attention operation, with H heads, between a D-dimensional query vector x and a set of D-dimensional vectors {y n } n=1...N can be written as follows:

H ∑ h=1 N ∑ n=1 1×1 s h,n D×D H W o,h D H ×D W v,h D×1 y n , (2)
where

s h,n = exp( 1×D x D×D H W q,h D H ×D W k,h D×1 y n ) ∑ N m=1 exp(x W q,h W k,h y m ) . (3)
In practice, all the matrices W •,• are learned. Usually D H = D H . The output is a linear combination (with coefficients s h,n ) of the linearly transformed set of vectors {y n } n=1...N . This operation allows to extract the relevant information in {y n } n=1...N from the point of view of the query x. The query x is not an element of that linear combination. As a consequence, a residual connection is often added, usually followed by a layer normalization and a 2-layer MLP (with residual connection) [START_REF] Vaswani | Attention is all you need[END_REF]. In practice, a cross-attention layer between a set of query vectors {x n } n=1...Q and {y n } n=1...N is performed in parallel, which is often computationally demanding since, for each head, the coefficients are stored in a Q×N matrix. A self-attention layer is a cross-attention layer where {y n } n=1...N = {x n } n=1...Q .

Feature extraction stage

Our method takes as input a source image

I s (H s × W s × 3), a target image I t (H t ×W t × 3)

Latent space attention-based stage

In order to allow for the descriptors {h s,i } i=1...L (at training-time we use L = 1024) to communicate and adjust with respect to H t , we draw inspiration from Perceiver [START_REF] Jaegle | Perceiver: General perception with iterative attention[END_REF][START_REF] Jaegle | Perceiver IO: A general architecture for structured inputs & outputs[END_REF], and consider a set of N = M+L latent vectors, composed of M learned latent vectors {m i } i=1...M and the L descriptors {h s,i } i=1...L . These latent vectors {m i } i=1...M , {h s,i } i=1...L are used as queries in an input cross-attention layer to extract the relevant information from H t , and finally obtain an updated set of latent vectors m . In these layers, all latent vectors can communicate and adjust with respect to each other. For instance, the set m

(0) i i=1...M , h (
(s) i i=1...M
can be used to disambiguate certain correspondences.

Then, H t is used as a query in an output cross-attention layer to extract the relevant information from the latent vectors. The resulting tensor is written H out t . For each updated descriptor h

(S) s,i , a correspondence map C t,i (of size H t 4 × W t 4
) is obtained by computing the dot product between h (S) s,i and H out t . Finally, for each 2D query location p s,i , the predicted 2D correspondent location pt,i is defined as the argmax of C t,i .

In Figure 3, we propose a visualization of the learned latent vectors of SAM. For visualization purposes, we used L = 64. Thus the average query map is obtained by averaging the 64 correspondence maps of the 64 query locations, while the average latent map is obtained by averaging the 128 correspondence maps of the 128 learned latent vectors. We observe that the average query map is mainly activated around the correspondents, whereas these regions are less activated in the average latent map.

Structured attention

At the end of the feature extraction stage, the upper half of each vector is visual features, while the lower half is positional encodings. In each attention layer (input cross-attention, self-attention and output crossattention), we found it important to structure the linear transformation matrices W o,h and W v,h to constrain the lower half of each output vector to only contain a linear transformation of the positional encodings:

D×D H W o,h = D 2 ×D H W o,h,up 0 D 2 × D H 2 | W o,h,low D 2 × D H 2 . ( 4
)
The matrices W v,h and the fully connected layers within the MLP (at the end of each attention module) are structured the exact same way. Consequently, throughout the network, the lower half of each latent vector only contains transformations of positional encodings, but no visual feature.

In Figure 4 we propose a visualization of two different correspondence maps before the output crossattention.

The first map is produced using the first 128 dimensions of the feature representation and contains high-level visio-positional features. The second map is produced using the 128 last dimensions of the feature representation and contains only positional encodings. By building these distinct correspondence maps we can observe that while the visio-positional representation is sensitive to repetitive structures, the purely positional representation tends to be only activated in the areas neighbouring the match.

Loss

At training time, we use a cross-entropy (CE) loss function [START_REF] Germain | [END_REF] on each correspondence map C t,i in order to maximise its score at the ground truth location p t,i :

CE (C t,i , p t,i ) = -ln exp C t,i (p t,i ) ∑ q exp C t,i (q)
.

(5)

Refinement

The previously described architecture produces coarse correspondence maps of resolution 1/4. Thus the predicted correspondents { pt,i } i=1...L need to be refined. To do so, we simply use a second siamese CNN that outputs dense source and target features at full resolution. For each 2D query location p s,i , a correspondence map is computed on a window of size 11 centered around the coarse prediction. The predicted 2D correspondent location pt,i is defined as the argmax of this correspondence map. This refinement network is trained separately using the same crossentropy loss eq. 5. Technical details are provided in the appendix.

Experiments

In these experiments, we focus on evaluating six SDF networks (LoFTR [START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF], QuadTree [START_REF] Tang | Quadtree attention for vision transformers[END_REF], ASpanFormer [START_REF] Chen | Aspanformer: Detector-free image matching with adaptive span transformer[END_REF], 3DG-STFM [START_REF] Mao | 3DG-STFM: 3D geometric guided student-teacher feature matching[END_REF], MatchFormer [START_REF] Wang | Matchformer: Interleaving attention in transformers for feature matching[END_REF], TopicFM [START_REF] Giang | TopicFM: Robust and interpretable feature matching with topic-assisted[END_REF]) and our proposed architecture SAM. In all the following Tables, best and second best results are respectively bold and underlined.

Table 1: Evaluation on MegaDepth1500 [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF]. We report Matching Accuracy (6) for several thresholds η, computed on the set of all the semi-dense query locations (source grid with stride 8) with available ground truth correspondents (MA), and on a subset containing only query locations that are within a textured region of the source image (MA text ).

Concerning the pose estimation metrics, we report the classical AUC at 5, 10 and 20 degrees. The proposed SAM method outperforms SDF methods in terms of pose estimation, while SDF methods are significantly better in terms of MA. However, when uniform regions are ignored (MA text ), SAM often surpasses SDF methods. These results highlight a strong correlation between the ability to establish precise correspondences in textured regions and the accuracy of the resulting estimated pose. Table 2: Evaluation on HPatches [START_REF] Balntas | Hpatches: A benchmark and evaluation of handcrafted and learned local descriptors[END_REF]. We report Matching Accuracy (6) for several thresholds η, computed on the set of all the semi-dense query locations (source grid with stride 8) with available ground truth correspondents (MA), and on a subset containing only query locations that are within a textured region of the source image (MA text ). Concerning the homography estimation metrics, we report the classical AUC at 3, 5 and 10 pixels. The proposed SAM method is on par with SDF methods in terms of homography estimation, while SDF methods are significantly better in terms of MA. However, when uniform regions are ignored (MA text ), SAM matches SDF performances. These results highlight a strong correlation between the ability to establish precise correspondences in textured regions and the accuracy of the resulting estimated homography. Table 3: Evaluation on ETH3D [START_REF] Schöps | BAD SLAM: Bundle adjusted direct RGB-D SLAM[END_REF] for different frame interval sampling rates r. We report Matching Accuracy (6) for several thresholds η, computed on the set of all the semi-dense query locations (source grid with stride 8) with available ground truth correspondents (MA). For ETH3D, ground truth correspondents are based on structure from motion tracks. Consequently, the MA already ignores untextured regions of the source images which explains why SAM is able to outperform SDF methods.

Method

Matching Accuracy (MA) (6) ↑

r = 3 r = 7 r = 15 η=1 η=2 η=3 η=5 η=10 η=1 η=2 η=3 η=5 η=10 η=1 η=2 η=3 η=5 η=10
Implementations -For each network, we employ the code and weights (trained on MegaDepth) made available by the authors. Concerning SAM, we train it similarly to the SDF networks on MegaDepth [START_REF] Li | Megadepth: Learning singleview depth prediction from internet photos[END_REF], during 100 hours, on four GeForce GTX 1080 Ti (11GB) GPUs (see the appendix for details). Our code will be made available.

Query locations -Concerning SDF methods, the query locations are defined as the source grid locations using a stride of 8. Thus, in order to be able to compare the performances of SAM against such methods, we use the exact same query locations. To do so (recall that SAM was trained with L = 1024 query locations), we simply shuffle the source grid locations (with stride 8) and feed them to SAM by batch of size 1024 (the CNN features are cached making the processing of each minibatch very efficient).

Evaluation criteria -Regarding the pose and homography estimation metrics, we use the classical AUC metrics for each dataset. Thus in each Table, the pose/homography results we obtained for SDF methods (we re-evaluated each method) are the same as the results published in the respective papers. Concerning SAM, the correspondences are classically filtered (similarly to what SDF methods do) before pose/homography estimator using a simple Mutual Nearest Neighbor with a threshold of 5 pixels.

In order to evaluate the ability of each method to establish correspondences, we consider the Matching Accuracy (MA) as in [START_REF] Truong | Glunet: Global-local universal network for dense flow and correspondences[END_REF], i.e., the average on all images of the ratio of correct matches, for different pixel error thresholds (η):

MA (η) = 1 K K ∑ k=1 ∑ L k i=1 pt k ,i -p GT t k ,i 2 < η L k , (6)
where K is the number of pairs of images, L k is the number of ground truth correspondences available for the image pair #k and [•] is the Iverson bracket. We refer to this metric as MA and not "Percentage of Correct Keypoints" because we found this term misleading in cases where the underlying ground truth correspondences are not based on keypoints, as it is the case in MegaDepth and HPatches.

We also propose to introduce the Matching Accuracy in textured regions (MA text ) that consists in ignoring, in eq. ( 6), ground truth correspondences whose query location is within a low-contrast region of the source image, i.e., an almost uniform region of the source image.

Note that SAM's MNN (and the MNN of SDF methods) is only used for the pose/homography estimation, i.e., it is not used to compute matching accuracies, otherwise the set of correspondences would not be the same for each method.

Evaluation on MegaDepth

We consider the MegaDepth1500 [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF] benchmark. We use the exact same settings as those used by SDF methods, such as an image resolution of 1200. The results are provided in Table 1. We report Matching Accuracy (6), for several thresholds η, computed on the set of all the semi-dense query locations (source grid with stride 8) with available ground truth correspondents (MA). The ground truth correspondents are obtained using the available depth maps and camera poses. Consequently, many query locations located in untextured regions have a ground truth correspondent. Thus, we also report the matching accuracy computed only on query locations that are within a textured region of the source image (MA text ). Concerning the pose estimation metrics, we report the classical AUC at 5, 10 and 20 degrees. The proposed SAM method outperforms SDF methods in terms of pose estimation, while SDF methods are significantly better in terms of MA. However, when uniform regions are ignored (MA text ), SAM often surpasses SDF methods. These results highlight a strong correlation between the ability to establish precise correspondences in textured regions and the accuracy of the resulting estimated pose.

In Figure 5, we report qualitative results that visually illustrate the previous findings.

Evaluation on HPatches

We evaluate the different architectures on HPatches [START_REF] Balntas | Hpatches: A benchmark and evaluation of handcrafted and learned local descriptors[END_REF] (see Table 2). We use the exact same settings as those used by SDF methods. We report Matching Accuracy (6) for several thresholds η, computed on the set of all the semi-dense query locations (source grid with stride 8) with available ground truth correspondents (MA). The ground truth correspondents are obtained using the available homography matrices. Consequently, many query locations located in untextured regions have a ground truth correspondent. Thus, we also report the matching accuracy computed only on query locations that are within a textured region of the source image (MA text ). Concerning the homography estimation metrics, we report the classical AUC at 3, 5 and 10 pixels. The proposed SAM method is on par with SDF methods in terms of homography estimation, while SDF methods are significantly better in terms of MA. However, when uniform regions are ignored (MA text ), SAM matches SDF performances. These results highlight a strong correlation between the ability to establish precise correspondences in textured regions and the accuracy of the resulting estimated homography.

In Figure 6, we report qualitative results that visually illustrate the previous findings.

Evaluation on ETH3D

We evaluate the different networks on several sequences of the ETH3D dataset [START_REF] Schöps | BAD SLAM: Bundle adjusted direct RGB-D SLAM[END_REF] as proposed in [START_REF] Truong | Glunet: Global-local universal network for dense flow and correspondences[END_REF]. Different frame interval sampling rates r are considered. As the rate r increases, the overlap between the image pairs reduces, hence making the matching problem more difficult. The results are provided in Table 3. We report Matching Accuracy (6) for several thresholds η, computed on the set of all the semi-dense query locations (source grid with stride 8) with available ground truth correspondents (MA). For ETH3D, ground truth correspondents are based on structure from motion tracks. Consequently, the MA ignores untextured regions of the source images which explains why SAM is able to outperform SDF methods in terms of MA.

In Figure 7, we report qualitative results that illustrate the accuracy of the proposed SAM method.

Ablation study

In Table 4, we propose an ablation study of SAM to evaluate the impact of each part of our architecture. This study is performed on MegaDepth validation scenes. Starting from a standard siamese CNN, we show that a significant gain in performance can simply be obtained with the input cross-attention layer (here the PE is added and not concatenated) and selfattention layers. We then add learned latent vectors (LV) in the latent space and use an output crossattention which again significantly improves the performance. Concatenating the positional encoding information instead of adding it to the visual features reduces the matching accuracy at η = 2 and η = 5. However, combining it with structured attention leads to a significant improvement in terms of MA. Finally, as expected, the refinement step improves the matching accuracy for small pixel error thresholds.

Conclusion

We proposed a novel Structured Attention-based image Matching architecture (SAM). The flexibility of this novel architecture allowed us to fairly compare it against SDF methods, i.e., in all the experiments we used the same query locations (source grid with stride 8). The experiments highlighted a counter-intuitive result on two datasets (MegaDepth and HPatches): on the one hand SAM either outperforms or is on par with SDF methods in terms of pose/homography estimation metrics, but on the other hand SDF approaches are significantly better than SAM in terms of Matching Accuracy (MA). Here the MA is computed on all the semi-dense locations of the source image with available ground truth correspondent, which includes both textured and uniform regions. We proposed to limit the computation of the matching accuracy to textured regions, and showed that in this case SAM often surpasses SDF methods. These findings highlighted a strong correlation between the ability to establish precise correspondences in textured regions and the accuracy of the resulting estimated pose/homography. We also evaluated the aforementioned methods on ETH3D which confirmed, on a third dataset, that SAM has a strong ability to establish correspondences in textures regions. We finally performed an ablation study of SAM to demonstrate that each part of the architecture is important to obtain such a strong matching capacity.

Refinement description. The previous CNN backbone is used for refinement. We simply added a FPN (Feature Pyramid Network) module to extract the feature maps after the first convolutional layer and each ResNet layer. It leaves us with a feature map of size 128 × H × W on which the refinement stage is performed. of 10 -3 and a batch size of 1 (Figure 8). We minimize the cross-entropy of the full resolution correspondence maps produced using the FPN.

The CNN backbone of SAM is initialized with the weights of the previously trained network. We train SAM for 100 hours. The same setup with 4 Nvidia GTX1080 Ti GPUs, Adam optimizer and a batch size of 1 is used. Concerning the learning rate schedule, we use a linear warm-up of 5000 steps (from 0 to 10 -4 ) and then an exponential decay (towards 10 -5 ) (Figure 9). We minimize the cross-entropy of the 1

Figure 1 :

 1 Figure 1: Given query locations within textured regions of the source image (left), we show their predicted correspondents in the target image (right) for: (Top row) SAM (Proposed) -Structured Attention-based image Matching, (Bottom row) LoFTR[START_REF] Sun | LoFTR: detector-free local feature matching with transformers[END_REF]+QuadTree[START_REF] Tang | Quadtree attention for vision transformers[END_REF]) -a semi-dense detector-free approach (line colors indicate the distance in pixels with respect to the ground truth correspondent). We report: (MA@2) -the matching accuracy at 2 pixels computed on all the semidense locations of the source image with available ground truth correspondent (which includes both textured and uniform regions), (MA text @2) -the matching accuracy at 2 pixels computed on all the textured semi-dense locations of the source image with available ground truth correspondent (i.e., uniform regions are ignored), (errR and errT) -the relative pose error. SAM has a better pose estimation but a lower matching accuracy (MA@2), which seems counterintuitive. However, if we consider only textured regions (MA text @2), then SAM outperforms LoFTR+QuadTree.

Figure 3 :

 3 Figure3: Visualization of the learned latent vectors of SAM. The average query map is obtained by averaging 64 correspondence maps of 64 query locations (Red crosses) while the average latent map is obtained by averaging the 128 correspondence maps of the 128 learned latent vectors. We observe that the average query map is mainly activated around the correspondents, whereas these regions are less activated in the average latent map.

  0) s,i i=1...L . On the one hand, the outputs h (0) s,i i=1...L contain the information relevant to find their respective correspondents within H t . On the other hand, the outputs m representation of H t since they are not aware of the query 2D locations. In practice, we set M to 128. Afterward, a series of S self-attention layers are applied to the latent vectors to get m

Figure 4 :

 4 Figure 4: Visualization -Structured attention. The visio-positional and positional maps are computed before the output cross-attention. Red crosses represent the ground-truth correspondences. Blue and Green crosses are the maxima of the visio-positional and positional maps, respectively. One can see that the visio-positional maps are highly multimodal (i.e., sensitive to repetitive structures) while the positional maps are almost unimodal.

  Structured attention. In our implementation, D = 256, we use 8 heads, thus D H = 32.Training details. The first part of the model to be trained is the refinement model (CNN+FPN). It is trained during 50 hours on 4 Nvidia GTX1080 Ti GPUs using Adam optimizer, a constant learning rate

Figure 8 :

 8 Figure 8: Training (left) and Validation (right) loss for refinement ResNet-18+FPN. x-axis represent the number of mini-batches seen by the model and y-axis the crossentropy value.

Figure 9 :

 9 Figure 9: Training (left) and Validation (right) loss for SAM. x-axis represent the number of mini-batches seen by the model and y-axis the cross-entropy value.

proposes an

  Overview of the proposed Structured Attention-based image Matching (SAM) method. (a) The matching architecture first extracts features from both source and target images at resolution 1/4. Then it uses a set of learned latent vectors alongside the descriptors of the query locations, and performs an input structured cross-attention with the dense features of the target. The latent space is then processed through a succession of structured self-attention layers. An output structured cross-attention is applied to update the target features with the information from the latent space. Finally, the correspondence maps are obtained using a dot product. (b) Proposed structured attention layer. See text for details.

	Source PE
				: Dot product
	CNN
	Source Image	Query 2D locations	xS	Corresp. Maps
		Structured	Structured
		Cross-	Self-
		Attention	Attention
				Softmax
	Learned latent vectors	Latent space		Attention Maps
	Target PE
			Structured
	CNN		Cross-
			Attention
	Target
	Image			Structured Attention
		(a) SAM architecture	(b) Structured Attention
	Figure 2:

attention-based backbone, interleaving self and crossattention layers, to progressively transform a tensor of size 2×H ×W ×3 into a tensor of size 2× H 16 × W 16 ×C. Efficient attention layers such as Spatial Efficient Attention

  and a set of 2D query locations {p s,i } i=1...L . The first stage of SAM is a classical feature extraction stage. From the source image I s (H s ×W s × 3) and the target image I t (H t ×W t × 3), dense visual source features F s ( For each 2D query point p s,i , a descriptor h s,i of size 256 is extracted from H s . In practice, we use integer query locations thus there is no need for interpolation here. Technical details concerning this stage are provided in the appendix.

	H s 4 × W s 4 × 128) and target features F t ( H t 4 × W t 4 × 128) are extracted using a siamese CNN backbone. The
	Positional Encodings (PE) of the source and target are
	computed, using an MLP (Sarlin et al., 2020), and
	concatenated with the visual features of the source
	and target to obtain two tensors H s ( H s 4 × W s 4 × 256) and H t ( H t 4 × W t 4 × 256).

Table 4 :

 4 Ablation study of proposed SAM method (MegaDepth validation set).

	Method	MA text ↑ η=1 η=2 η=5 η=10 η=20 η=50
	Siamese CNN	0.029 0.112 0.436 0.581 0.622 0.687
	+ Input CA and SA (x16)	0.137 0.321 0.671 0.734 0.767 0.822
	+ Learned LV and output CA 0.132 0.462 0.823 0.871 0.898 0.935
	+ PE concatenated	0.121 0.419 0.796 0.868 0.902 0.939
	+ Structured AM	0.140 0.487 0.857 0.902 0.922 0.947
	+ Refinement (Full model)	0.673 0.791 0.870 0.902 0.921 0.946

resolution correspondence maps produced by SAM.

APPENDIX

SAM architecture. Each attention layer in SAM is a classical series of softmax attention, normalization, MLP and normalization layers with residual connections, except for the "output" cross-attention where we removed the MLP, the last normalization and the residual connection.

We empirically choose a combination of 16 selfattention layers and 128 vectors in the learned latent space. We found this combination to be a good tradeoff between performance and computational cost.

Backbone description. We use a modified ResNet-18 as our feature extraction backbone. We extract the feature map after the last ResBlock in which we removed the last ReLU. The features are reduced to 1 4 th of the image resolution (3 × H × W ) by applying a stride of 2 in the first and third layer. The feature representation built by the backbone is of size 128 × 1 4 H × 1 4 W .