Valérie Campanacci

Agathe Urvoas

Liza Ammar Khodja

Magali Aumont-Nicaise

Magali Noiray

Sylvie Lachkar

Patrick A Curmi

Philippe Minard

Benoît Gigant
email: benoit.gigant@i2bc.paris-saclay.fr

Structural convergence for tubulin binding of CPAP and vinca domain microtubule inhibitors

Keywords: Centrioles, Cytoskeleton, Microtubule dynamics, Peptide inhibitor, Structural biology

Microtubule dynamics is regulated by various cellular proteins and perturbed by small molecule compounds. To what extent the mechanism of the former resembles that of the latter is an open question. We report here structures of tubulin bound to the PN2-3 domain of CPAP, a protein controlling the length of the centrioles. We show that an a- helix of the PN2-3 N-terminal region binds and caps the longitudinal surface of the tubulin b subunit. Moreover, a PN2-3 N-terminal stretch lies in a b-tubulin site also targeted by fungal and bacterial peptide-like inhibitors of the vinca domain, sharing a very similar binding mode with these compounds. Therefore, our results identify several characteristic features of cellular partners that bind to this site and highlight a structural convergence of CPAP with small molecule inhibitors of microtubule assembly.

Microtubules are eukaryotic dynamic filaments made of ab-tubulin heterodimers and involved in major cellular functions including ciliogenesis, intracellular transport and cell division. The dynamics of microtubules is regulated by several families of proteins [START_REF] Desai | Microtubule polymerization dynamics[END_REF]. It is also perturbed by many small molecule compounds that target a growing number of tubulin binding sites [START_REF] Steinmetz | Microtubule-targeting agents: strategies to hijack the cytoskeleton[END_REF][START_REF] Mühlethaler | Comprehensive analysis of binding sites in tubulin[END_REF]. Some of these compounds have proven to be useful to fight human diseases, in particular in oncology [START_REF] Amos | What tubulin drugs tell us about microtubule structure and dynamics[END_REF][START_REF] Risinger | Microtubule dynamics as a target in oncology[END_REF]. Among these microtubule dynamics inhibitors, a diverse set of molecules including vinca alkaloids [START_REF] Duflos | Novel aspects of natural and modified vinca alkaloids[END_REF] and short peptides or depsipeptides [START_REF] Hamel | Antimitotic peptides and depsipeptides[END_REF] interact with the so-called tubulin vinca domain. This site is located at the interface between two tubulin molecules arranged in a curved protofilament-like manner [START_REF] Steinmetz | Microtubule-targeting agents: strategies to hijack the cytoskeleton[END_REF][START_REF] Cormier | Structural insight into the inhibition of tubulin by vinca domain peptide ligands[END_REF][START_REF] Gigant | Structural basis for the regulation of tubulin by vinblastine[END_REF]. These compounds therefore interact with the longitudinal surface of both aand b-tubulin. Doing so, they prevent protofilaments from adopting the straight conformation observed in the microtubule core, which accounts for their microtubule assembly inhibition. Whereas the a-tubulin subsite of vinblastine also binds to the N-terminal b-hairpin motif of stathmin proteins [START_REF] Gigant | Structural basis for the regulation of tubulin by vinblastine[END_REF], whether other cellular tubulin regulators similarly bind to the vinca domain pocket of the b subunit is not known. Centrosomal P4.1-associated protein (CPAP, also named CENPJ) is a 1338-residue long protein originally identified as a partner of the cytoskeletal protein 4.1R-135 [START_REF] Hung | Protein 4.1 R-135 interacts with a novel centrosomal protein (CPAP) which is associated with the gamma-tubulin complex[END_REF]. CPAP is however best characterized as a protein involved in centriole length regulation, allowing persistent slow growth of the centriolar microtubule plus end, CPAP overexpression leading to abnormally long microtubules [START_REF] Kohlmaier | Overly long centrioles and defective cell division upon excess of the SAS-4related protein CPAP[END_REF][START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Tang | CPAP is a cell-cycle regulated protein that controls centriole length[END_REF][START_REF] Zheng | Molecular basis for CPAP-tubulin interaction in controlling centriolar and ciliary length[END_REF][START_REF] Schmidt | Control of centriole length by CPAP and CP110[END_REF]. This activity can be recapitulated by a minimal construct comprising the tubulin-binding domain of CPAP, named PN2-3 and delineated as the CPAP 311-422 region [START_REF] Hung | Identification of a novel microtubuledestabilizing motif in CPAP that binds to tubulin heterodimers and inhibits microtubule assembly[END_REF], a microtubule-binding domain which is C-terminal to PN2-3 [START_REF] Hsu | Functional characterization of the microtubule-binding and -destabilizing domains of CPAP and d-SAS-4[END_REF] and a dimerization motif [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF]. When isolated, PN2-3 was shown to prevent microtubule assembly through a ~76 residue-long region [START_REF] Hung | Identification of a novel microtubuledestabilizing motif in CPAP that binds to tubulin heterodimers and inhibits microtubule assembly[END_REF][START_REF] Cormier | The PN2-3 domain of centrosomal P4.1-associated protein implements a novel mechanism for tubulin sequestration[END_REF]. Using a tubulin-binding DARPin protein [START_REF] Pecqueur | A designed ankyrin repeat protein selected to bind to tubulin caps the microtubule plus end[END_REF] as a crystallization helper, a partial structure of PN2-3 bound to tubulin was reported [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Zheng | Molecular basis for CPAP-tubulin interaction in controlling centriolar and ciliary length[END_REF]. Because the N-terminal part of PN2-3 competes with the DARPin for tubulin binding, it was not visible in the crystal structure, and only about 15 residues of the PN2-3 C-terminal region, defined as the SAC domain [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF], were traced bound to a b-tubulin site that corresponds to the outer surface of the microtubule.

Here, we report structures of tubulin bound to CPAP constructs as ternary complexes with a-tubulin specific aRep artificial proteins [START_REF] Campanacci | Selection and characterization of artificial proteins targeting the tubulin α subunit[END_REF][START_REF] Chevrel | Alpha repeat proteins (αRep) as expression and crystallization helpers[END_REF]. We show that part of the PN2-3 N-terminal region interacts with the b-tubulin longitudinal surface in a way very similar to that of vinca domain peptide ligands, therefore defining a type of cellular partners that binds to this site.

Results.

Structures of tubulin-bound PN2-3 define the interaction of this protein with tubulin.

We took advantage of the recently selected a-tubulin specific aRep proteins [START_REF] Campanacci | Selection and characterization of artificial proteins targeting the tubulin α subunit[END_REF] to obtain several crystal forms of aRep-tubulin-CPAP ternary complexes. The CPAP constructs used were based on the 321-397 fragment (Fig. 1A). First, we determined a 2.7 Å resolution structure (Table S1; crystal form 1, with one complex per asymmetric unit) in which the CPAP residues 339 to 387 could be traced (Fig. 1B). These crystals were obtained with the iiH5 aRep.

Surprisingly, in addition to the previously described iiH5-tubulin interaction (20), we identified a second tubulin-binding site for the aRep partner (Fig. 1B). In this structure, the CPAP 339-360 region folds as an a-helix which is connected by a linker, which does not interact with tubulin, to the C-terminal 371-387 SAC domain (Fig. 1B). Accordingly, the linker residues are among the least conserved ones of the CPAP PN2-3 domain from vertebrates (Fig. 1A). This linker is nevertheless reasonably defined in our structure, being stabilized by crystal contacts (see below).

To enhance the likelihood to obtain other crystal forms, we replaced the linker region by a shorter 5-glycine motif (Fig. 1A). We checked by ITC the effect of this modification on the binding affinity for tubulin and found that the resulting "∆loop" CPAP construct displayed an affinity for tubulin similar to that of the unmodified protein (KD about 7 nM and 15 nM, respectively; Fig. 1C, Fig. S1A,B, Table 1) and led to a high affinity complex. A new crystal form (Table S1; crystal form 2, two complexes per asymmetric unit), diffracting X-rays up to 2.35 Å resolution, was then obtained using the iE5 aRep crystallization chaperone.

Remarkably, in this case too, two aRep molecules were bound per tubulin, identifying a second iE5 binding site in addition to the one previously described (20) (Fig. 1D), although the electron density was weak for the part of the aRep that did not interact with tubulin. In this structure, the 5-glycine linker was disordered. The PN2-3 N-terminal a-helix was also less well defined than in crystal form 1, its two C-terminal turns being disordered. In contrast, the region Nterminal to this helix became visible from residues Asn321 to Ala330, whereas residues 331 to 338 remained poorly defined. In the next sections, the information from these two structures will be combined for analysis. Information from two additional structures (see Methods and Table S1) will also be used to characterize the dynamic binding of the N-terminal region of the CPAP 321-397 fragment to tubulin.

PN2-3 wraps around b-tubulin.

Using aRep proteins as crystallization helpers, we were able to trace the entire region of PN2-3 predicted to interact with tubulin [START_REF] Cormier | The PN2-3 domain of centrosomal P4.1-associated protein implements a novel mechanism for tubulin sequestration[END_REF]. This region comprises three modules, an N-terminal stretch, an a-helix and the SAC domain, that effectively interact with tubulin. They are separated by two non-interacting flexible modules, a "bulge" and the linker (Fig. 1,2A,B). The bulge is poorly ordered, but the other modules are clearly defined in one structure or the other. PN2-3 wraps around the tubulin b subunit, with the stretch and a-helix N-terminal moiety that cap a b-tubulin surface which is engaged in longitudinal interactions within protofilaments. The flexibility conferred by the bulge allows the N-terminal stretch to be oriented about 90° to the a-helix and to point toward the lumen of the microtubule when PN2-3 is modeled at the plus end of a protofilament (Fig. 2A). Overall, these results provide a complete structural view of the binding of PN2-3 to tubulin, which agrees with previous in vitro competition and crosslinking experiments [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Zheng | Molecular basis for CPAP-tubulin interaction in controlling centriolar and ciliary length[END_REF][START_REF] Cormier | The PN2-3 domain of centrosomal P4.1-associated protein implements a novel mechanism for tubulin sequestration[END_REF]. They also provide a structural explanation for the inhibition of microtubule assembly by PN2-3.

In its longest form, the PN2-3 N-terminal a-helix encompasses residues 339 to 360, in good agreement with the NMR-determined helical region of isolated PN2-3 [START_REF] Cormier | The PN2-3 domain of centrosomal P4.1-associated protein implements a novel mechanism for tubulin sequestration[END_REF]. It binds in a groove at the tip of b-tubulin boxed in by loop T5 and the H11-H11' region (Fig. 2B), giving a rationale for the competition for tubulin binding with the DARPin used as a crystallization helper in previous structural studies [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Zheng | Molecular basis for CPAP-tubulin interaction in controlling centriolar and ciliary length[END_REF] (Fig. 2C). It also explains the binding competition with maytansine [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Prota | A new tubulin-binding site and pharmacophore for microtubule-destabilizing anticancer drugs[END_REF] (Fig. 2C). Only the N-terminal moiety of this CPAP a-helix interacts with tubulin. This part is the only one that is ordered in crystal form 2 (Fig. 2B). In addition to being two turns shorter, the a-helix in this crystal form is also rotated ~21° compared to crystal form 1 (Fig. 2A, Fig. S2A). These observations underline a dynamic binding of this a-helix to tubulin. This feature was further supported by the analysis of two other crystal structures of aReptubulin-CPAP complexes (Table S1), showing additional orientations of the helix (Fig. S2A).

Moreover, inspection of the atomic temperature factors in the four structures indicated that those of the PN2-3 N-terminal region are higher than those of tubulin and of the CPAP SAC domain (Fig. S2B, Table S2). In addition, we studied the effect of two series of mutations in the N-terminal a-helix. We prepared the L342E-I346E (LI>EE) double mutant, targeting two hydrophobic residues pointing towards tubulin (Fig. 2B), and the 347 QLE 349 >GGG triple mutant aiming to destabilize the a-helix. Both mutated proteins have an affinity for tubulin only slightly lower than that of the parental CPAP construct, as estimated by ITC (Table 1, Fig. S1C,D). Finally, we recorded the interaction of CPAP 321-397 with soblidotin-induced tubulin rings [START_REF] Cormier | Structural insight into the inhibition of tubulin by vinca domain peptide ligands[END_REF]. Because PN2-3 inhibits the vinblastine-induced tubulin helical assembly [START_REF] Cormier | The PN2-3 domain of centrosomal P4.1-associated protein implements a novel mechanism for tubulin sequestration[END_REF], the CPAP construct was expected to inhibit also the formation of ring-type curved assemblies and it was indeed the case (Fig. S2C). Interestingly, when this construct was added to preformed rings, it did not induce their disassembly but interacted with them (Fig. S2C), although modeling indicated that the N-terminal a-helix of PN2-3 could not be accommodated at the tubulin longitudinal interface of curved assemblies (Fig. S2D). Taken together, these data argue for a moderate contribution of the PN2-3 N-terminal a-helix to the interaction with tubulin.

The N-terminal stretch of PN2-3 targets the binding site of vinca domain inhibitors.

The N-terminal stretch of the ∆loop construct in crystal form 2 (residues 321 to 330 of CPAP) interacts with tubulin in an extended conformation, mostly without forming regular secondary structure apart a short 310 helix from residues 322 to 324. It binds in a site mainly contributed by helix H1, loop T5, and the H6-H7 region of the b subunit. It also interacts with the M-loop residue Arg278 and with GDP (Fig. 3A). Therefore, PN2-3 contacts the same b-tubulin structural elements as small molecule compounds binding to the vinca domain. Consistently, it has been shown that the PN2-3 affinity for tubulin drops ~14-fold in the presence of the vinca domain-targeting compound eribulin [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Doodhi | Termination of protofilament elongation by eribulin induces lattice defects that promote microtubule catastrophes[END_REF]. Strikingly, the PN2-3 N-terminal stretch closely overlaps with peptide and depsipeptide microtubule inhibitors, including phomopsin A, auristatins and tubulysins, four structural features being shared by CPAP and most of these compounds [START_REF] Li | The X-ray structure of tubulysin analogue TGL in complex with tubulin and three possible routes for the development of next-generation tubulysin analogues[END_REF]. They are described hereunder.

First, the highly conserved Ile327 CPAP residue (Fig. 1A) points in a hydrophobic pocket of b-tubulin boxed in by Val177 (from T5), Tyr210 (H6), Pro222 (H6-H7 loop), Tyr224 and Leu227 (H7) (Fig. 3B). We tested the effect of an I327R substitution in the 321-397 construct and found a ~30-fold decrease of the binding affinity for tubulin (Fig. 3C, Fig. S1E, Table 1). This tubulin pocket is targeted by all the vinca domain ligands whose interaction with tubulin has been structurally characterized (Fig. 3D,E, Fig. S3). Remarkably, it accommodates a small aliphatic group in all cases, and it has been shown that replacing the corresponding isopropyl group in tubulysins by a bulkier aryl or cyclohexyl one leads to inactive compounds [START_REF] Shankar | Synthesis and structure-activity relationship studies of novel tubulysin U analogues -effect on cytotoxicity of structural variations in the tubuvaline fragment[END_REF].

However, in the case of CPAP, introducing the I327W mutation in the 321-397 construct did not decrease the affinity for tubulin (Table 1, Fig. S1F), indicating that, in the context of PN2-3 and in contrast to smaller peptide-like vinca domain inhibitors, a hydrophobic group bulkier than an Ile side chain is allowed at this position.

A second feature is the proline residue adjacent to Ile327 (Pro326, also conserved). A proline or proline-like residue is found at this position or at an adjacent one in most of the peptide-like inhibitors of tubulin (Fig. S3). Thirdly, whereas the Arg325 guanidino group interacts with the nucleotide base (Fig. 3A), its side chain aliphatic part together with Ile322 forms a hydrophobic patch interacting with b-tubulin, including with Tyr224. This tyrosine is in a stacking interaction with the guanine of the nucleotide and is involved in the regulation of microtubule assembly [START_REF] Ayukawa | GTP-dependent formation of straight tubulin oligomers leads to microtubule nucleation[END_REF]. Whereas the hydrophobic nature of the tubulin region interacting with these two CPAP residues is not strong, the observation that the vinca domain peptide inhibitors all have a hydrophobic group superposing with Ile322 and with the aliphatic part of Arg325 (Fig. 3E, Fig. S3) suggests such groups are important for tubulin binding. Accordingly, removing the corresponding phenyl group in tubulysin D leads to a compound ~40-fold less efficient in inhibiting cancer cell growth [START_REF] Patterson | Design, synthesis, and biological properties of highly potent tubulysin D analogues[END_REF].

Finally, two acidic CPAP residues (Glu323 and Glu324) are in positions to make salt bridges with Lys19 and Arg278 of b-tubulin, respectively (Fig. 3F), suggesting that these glutamic acid residues contribute substantially to the interaction with tubulin. This proposal is supported by the observation that several small peptide-like compounds also have acidic groups overlapping with Glu323 and Glu324 (Fig. 3E, Fig. S3), and the interaction with the M-loop residue Arg278 has been proposed to enhance the affinity of some inhibitors for tubulin [START_REF] Waight | Structural basis of microtubule destabilization by potent auristatin antimitotics[END_REF]. In addition, several compounds shown to also bind to the "partial" binding site of the tubulin-stathmin complex, contributed by b-tubulin only, have one or two acidic groups (e.g. phomopsin A ( 8)).

On the other hand, replacing the acidic group in tubulysins with, e.g., an hydrazine counterpart has only a mild effect on the activity [START_REF] Leamon | Folate targeting enables durable and specific antitumor responses from a therapeutically null tubulysin B analogue[END_REF][START_REF] Colombo | Total synthesis and biological evaluation of tubulysin analogues[END_REF]. In the case of CPAP, an E323R-E324R (EE>RR) mutant displayed an affinity for tubulin similar to that of the wild type construct (Fig. 3C, Fig. S1G, Table 1). Consistently, the affinity of a 3R mutant, having in addition the I327R substitution, was similar to that of the single I327R mutant (Fig. S1H, Table 1). It should also be noted that, whereas Glu323 is a conserved CPAP residue, Glu324 is not (Fig. 1A). We therefore conclude that Glu323 and Glu324 do not contribute much to the binding affinity of PN2-3 for tubulin.

Interestingly, whereas the N-terminal stretch of the 321-397 construct was not visible in crystal form 1, the vinca domain peptide site is not empty in that structure but occupied by the linker (which connects the N-terminal a-helix to the SAC domain) of a crystal-related symmetric molecule. Remarkably, the 362 EGPL 365 motif of the linker in that crystal form fills the space occupied by 324 ERPI 327 in crystal form 2 (Fig. 3G). This observation accounts for the destabilized N-terminal stretch in crystal form 1. More importantly, it confirms features important for targeting the vinca domain peptide of tubulin (Fig. S3).

Discussion.

In this study, we have shown that the PN2-3 domain of CPAP interacts with tubulin through three discrete, mostly linear binding motifs, a feature of intrinsically disordered proteins [START_REF] Wright | Linking folding and binding[END_REF][START_REF] Yang | Features of molecular recognition of intrinsically disordered proteins via coupled folding and binding[END_REF]. The overall affinity of PN2-3 for tubulin probably comes from the cumulative effect of these three interacting motifs, since constructs including either the N-terminal stretch and the N-terminal a-helix or the C-terminal SAC domain display KD in the µM to the tens of µM range, i.e. two to three orders of magnitude higher than that of PN2-3 [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Zheng | Molecular basis for CPAP-tubulin interaction in controlling centriolar and ciliary length[END_REF]. Such a binding mode, characterized by a cumulative contribution of weakly interacting points to the affinity, is likely to accommodate the mutation of (a priori) important residues. This proposal is supported by the moderate effect on the affinity of most mutations we studied, the most substantial being a 20-to 30-fold KD increase with the I327R substitution. In contrast, the effect of similar modifications in shorter peptide-like inhibitors is more pronounced.

Another characteristic of intrinsically disordered proteins is their remaining conformational flexibility even when bound to their partners. Our results, which identify several orientations of the N-terminal a-helix (Fig. 2A, Fig. S2A) and an N-terminal stretch that is well defined in only one crystal form (Fig. 1B,D, Fig. S2B), indeed suggest that PN2-3 retains some mobility when bound to tubulin. This observation has implications for the mechanism of centriolar microtubule regulation by CPAP. Indeed, slow growth of the microtubule plus end that is observed in the presence of CPAP [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF] implies that the N-terminal part of PN2-3 detaches from b-tubulin to unmask its longitudinal surface. The dynamic binding of this region to tubulin could lead to transient uncapping of protofilaments, therefore allowing microtubule elongation. Moreover, because CPAP constructs bind to tubulin rings (Fig. S2C,D), our results indicate that PN2-3 still interacts with tubulin even without the contribution of its N-terminal a-helix, consistent with the tracking by CPAP of the microtubule plus end during elongation [START_REF] Sharma | Centriolar CPAP/SAS-4 imparts slow processive microtubule growth[END_REF][START_REF] Zheng | Molecular basis for CPAP-tubulin interaction in controlling centriolar and ciliary length[END_REF]. Another finding of our work which is relevant to the mechanism of centriole length regulation by CPAP is the orientation of the N-terminal end of PN2-3. When the tubulin-CPAP 321-397 construct structure is modeled at the plus tip of a protofilament, this end points to the lumen of the microtubule (Fig. 2A). Remarkably, it has recently been shown that the CP110-CEP97 complex binds to the luminal side of microtubule plus ends and that CP110 interacts with a CPAP region (residues 89 to 196) which is N-terminal to PN2-3 [START_REF] Ogunmolu | Microtubule plus-end regulation by centriolar cap proteins[END_REF]. Because CP110 also controls the length of the centrioles [START_REF] Kohlmaier | Overly long centrioles and defective cell division upon excess of the SAS-4related protein CPAP[END_REF][START_REF] Schmidt | Control of centriole length by CPAP and CP110[END_REF][START_REF] Ogunmolu | Microtubule plus-end regulation by centriolar cap proteins[END_REF][START_REF] Spektor | Cep97 and CP110 suppress a cilia assembly program[END_REF], taken together, these data provide a basis for an interaction network at microtubule plus tips between centriolar microtubule regulators.

To conclude, we have determined the complete structure of the microtubule destabilizing motif of the CPAP protein bound to tubulin. We have shown that its N-terminal stretch interacts with the vinca domain of b-tubulin. Its binding mode is very similar to that of several vinca domain peptide-like compounds from bacteria or fungi, which inhibit microtubule assembly. This finding points to a structural convergence for tubulin binding and provides constraints on the type of cellular partners accommodated in this pocket.

Methods.

Proteins. The CPAP 321-397 construct was obtained by standard molecular biology methods from the PN2-3 DNA and inserted in the pET3d plasmid. ∆loop and point mutants were then generated from this construct by PCR. All constructs were verified by sequencing. The corresponding proteins were overexpressed in the BL21(DE3) E. coli strain and purified as described for PN2-3 [START_REF] Cormier | The PN2-3 domain of centrosomal P4.1-associated protein implements a novel mechanism for tubulin sequestration[END_REF]. Tubulin was purified from sheep brain [START_REF] Castoldi | Purification of brain tubulin through two cycles of polymerizationdepolymerization in a high-molarity buffer[END_REF]. The iE5 and iiH5 aReps were produced and purified as described previously [START_REF] Campanacci | Selection and characterization of artificial proteins targeting the tubulin α subunit[END_REF].

Isothermal titration calorimetry (ITC).

Calorimetry experiments were conducted at 20°C with a MicroCal PEAQ-ITC instrument (Malvern). All proteins were buffer-exchanged to 20 mM Mes-K pH 6.8, 1 mM MgCl2, 0.01 mM EGTA and 0.01 mM GDP. Aliquots (2 μl) of CPAP constructs at 112 to 250 µM concentrations were injected into a 15 µM tubulin solution (cell volume, 0.24 ml). In the case of the ∆loop construct, which has a higher affinity, titration experiments with 8 µM tubulin in the cell were also performed and led to a similar KD.

However, because the parameter c=stoichiometry (n) • [tubulin]/KD remained slightly above the optimal conditions for an accurate estimation of the affinity parameters by ITC [START_REF] Menéndez | Isothermal titration calorimetry: principles and applications[END_REF], the KD value for this construct should be taken with caution. We also checked that the titration of buffer into 15 µM tubulin and that of the CPAP 321-397 and ∆loop constructs into buffer yielded no heat signal (Fig. S1I-K).Analysis of the data was performed using the MicroCal PEAQ-ITC software provided by the manufacturer according to the one-binding-site model. The Origin software (Malvern) was used to superpose the data shown in Fig. 1C and3C.

Crystallization and structure determination. The aRep-tubulin-CPAP construct complexes were concentrated to about 20 mg ml -1 for crystallization experiments, leading to four crystal forms.

Crystal form 1. These crystals were obtained with the iiH5 aRep and with a CPAP 321-397 construct in which the lysine residues were methylated prior to the formation of the complex [START_REF] Nawrotek | Biochemical and structural insights into microtubule perturbation by CopN from Chlamydia pneumoniae[END_REF]. In addition, residue Leu342 had been mutated to a methionine to help tracing the CPAP chain in lower resolution data using SeMet version of this construct at earlier stages of this project. Crystals were obtained at 293 K by vapor diffusion in a crystallization buffer consisting of 0.1 M Mes-K pH 6.8, 8 % (W/V) polyethylene glycol 3350. They were harvested in the crystallization buffer containing also 20% glycerol and flash-cooled in liquid nitrogen.

Crystal form 2. iE5-tubulin-CPAP ∆loop construct crystals were obtained at 293 K in 0.18 M tri-ammonium citrate, 0.1 M Mes-K pH 6.8, 18.5 % (W/V) polyethylene glycol 3350 and cryoprotected in mother liquor supplemented with 20% glycerol.

Crystal form 3. The C-terminal tail of both tubulin subunits was cleaved by subtilisin [START_REF] Nawrotek | The determinants that govern microtubule assembly from the atomic structure of GTP-tubulin[END_REF] prior to the formation of a iiH5-tubulin-CPAP 321-397 construct complex. Crystals with one complex per asymmetric unit were obtained at 278 K in 0.2 M Na tartrate, 10% (W/V) polyethylene glycol 3350 and cryoprotected in mother liquor supplemented with 20% glycerol.

Crystal form 4. iE5-tubulin-CPAP 321-397 construct crystals (two complexes per asymmetric unit) were obtained at 293 K in 0.1 M Mes-K pH 6.0, 0.2 M Ca acetate, 20% (V/V) polyethylene glycol 400 and cryoprotected in the crystallization buffer containing 24% (V/V) polyethylene glycol 400.

Datasets were collected at 100 K at the SOLEIL Synchrotron (PROXIMA-1 and PROXIMA-2A beamlines). Data for crystal forms 1, 3 and 4 were processed with XDS (39) as implemented in the XDSME package [START_REF] Legrand | XDSME: XDS Made Easier[END_REF]. Crystal form 2 data were processed with autoPROC (41) which implements the STARANISO treatment for anisotropy (http://staraniso.globalphasing.org/).

Structures were solved by molecular replacement with Phaser (42) using tubulin-iiH5 (pdb id 6GWD) and tubulin-iE5 (pdb id 6GWC) as search models, and refined with BUSTER [START_REF] Bricogne | BUSTER version 2.10.3[END_REF] with iterative model building in Coot [START_REF] Emsley | Features and development of Coot[END_REF]. In crystal forms 3 and 4, there was one aRep per complex, in contrast to crystal forms 1 and 2 which comprised an extra aRep (Fig. 1B,D). Data collection and refinement statistics are reported in Table S1. Figures of structural models were generated with PyMOL (www.pymol.org).

Sequence conservation. The sequence conservation of the CPAP PN2-3 domain (Fig. 1A) was calculated using the ConSurf program [START_REF] Ashkenazy | ConSurf 2016: an improved methodology to estimate and visualize evolutionary conservation in macromolecules[END_REF]. The analysis was based on 150 sequences retrieved from the UniProt database and having a maximum of 95% sequence identity with human PN2-3 taken as a reference. About 40% of the sequences were from mammals, 55% from birds and 5% from reptiles, and there was one amphibian CPAP. or the ∆loop construct (see also Fig. S1A,B and Table 1). (D) Crystal form 2: structure of tubulin bound to the CPAP ∆loop fragment (magenta). The complex was crystallized with two molecules of the iE5 aRep. In panels B and D, the aReps in orange are those bound to tubulin in two structures of tubulin-aRep previously determined [START_REF] Campanacci | Selection and characterization of artificial proteins targeting the tubulin α subunit[END_REF], the ones in yellow define new binding sites.

Figures.Figure 1 .

 1 Figures.

Figure 2 .

 2 Figure 2. PN2-3 wraps around b-tubulin. (A) PN2-3 (cyan and magenta, from crystal forms 1 and 2, respectively) is modeled at the plus end of a microtubule (pdb id 6DPU), by superposing b-tubulin of tubulin-CPAP complexes to b-tubulin at the plus end of a protofilament. View from the plus end of the microtubule, three protofilaments are shown and CPAP is modeled on the middle one. The five structural motifs of PN2-3 are indicated (see also panel B and Fig. 1). (B) The PN2-3 N-terminal a-helix binding site. The b-tubulin elements interacting with this ahelix are highlighted in green. The side chains of residues Leu342 and Ile346, replaced in the LI>EE mutant, are shown in crystal form 2, whereas the main chain of residues 347 to 349, targeted in the QLE>GGG mutant, is in blue in crystal form 1. (C) Structural basis for PN2-3 competition with a DARPin (pdb id 5EIB) and with maytansine (4TV8) for tubulin binding.The side chain of Gln345, which would overlap with maytansine, is shown.

Figure 3 .

 3 Figure 3. The interaction of the N-terminal stretch of PN2-3 with tubulin. (A) Overview of the interaction. The PN2-3 ∆loop construct (from crystal form 2) is in magenta, and the tubulininteracting elements are in green. The side chain of CPAP Lys328 which is weakly defined in the electron density maps has been truncated after its Cb atom. (B) Zoom in on the interaction with tubulin of the CPAP residue Ile327. (C) ITC analysis of the tubulin:I327R and tubulin:E323R-E324R (EE>RR) interactions (see also Fig. S1E,G and Table 1). (D,E) The binding sites of vinblastine (pdb id 1Z2B, panel D) and of phomopsin A (3DU7, panel E) overlap with that of the N-terminal stretch of PN2-3. (F) Zoom in on the interaction with tubulin of the CPAP residues Glu323 and Glu324. (G) In crystal form 1, the linker region of a symmetry-related CPAP molecule (cyan) occupies the tubulin binding site of the N-terminal stretch of PN2-3.

Acknowledgements

We thank M. Knossow (I2BC, Gif-sur-Yvette) for many useful discussions and for a critical reading of the manuscript. Diffraction data were collected at SOLEIL synchrotron (PROXIMA-1 and PROXIMA-2A beamlines, Saint-Aubin, France). We are most grateful to the machine and beam line groups for making these experiments possible. This work has benefited from the crystallization and protein interaction platforms of I2BC supported by French Infrastructure for Integrated Structural Biology (FRISBI) ANR-10-INBS-05. Financial support by CNRS and by the Fondation ARC pour la Recherche sur le Cancer (Grants PJA20161204544 and ARCPJA2021050003651 to B.G.) is acknowledged.

Data availability. Coordinates and structure factors have been deposited with the Protein Data

Bank with accession numbers 7Q1E (crystal form 1), 7Q1F (crystal form 2), 7Z0F (crystal form 3), and 7Z0G (crystal form 4). Data supporting the findings of this study are available from the corresponding author upon reasonable request.

(a) mean ± s.d. (b) The number of measurements is indicated in parentheses.


Clément Riu
email: clement.riu@enpc.fr

Vincent Nozick
email: vincent.nozick@univ-eiffel.fr

Pascal Monasse
email: pascal.monasse@enpc.fr

Joachim Dehais
email: dehais.joachim@gmail.com

Classification Performance of RanSaC Algorithms with Automatic Threshold Estimation

Keywords: Multi-View Stereo, Structue-From-Motion, RanSaC, Semi-synthetic Dataset, Benchmark

The RANdom SAmpling Consensus method (RanSaC) is a staple of computer vision systems and offers a simple way of fitting parameterized models to data corrupted by outliers. It builds many models from small sets of randomly selected data points, and then scores them to keep the best. The original scoring function is the number of inliers, points that fit the model up to some tolerance. The threshold that separates inliers from outliers is data-and model-dependent, and estimating the quality of a RanSaC method is difficult as ground truth data is scarce or not quite reliable. To remedy that, we propose a data generation method to create at will ground truths both realistic and perfectly reliable. We then compare the RanSaC methods that simultaneously fit a model and estimate an appropriate threshold. We measure their classification performance on those semisynthetic feature correspondence pairs for homography, fundamental, and essential matrices. Whereas the reviewed methods perform on par with the RanSaC baseline for standard cases, they do better in difficult cases, maintaining over 80 % precision and recall. The performance increase comes at the cost of running time and analytical complexity, and unexpected failures for some algorithms.

INTRODUCTION

Over fourty years have passed since the publication of the RANdom SAmple Consensus algorithm [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. The algorithm approximates a solution to the NP-hard consensus maximization problem [START_REF] Chin | Robust fitting in computer vision: Easy or hard[END_REF]: fitting a parameterized model to data corrupted by noise and outliers. RanSaC generates tentative models using random, minimal subsets of data and validates them with the distance of data points to each model. Data points whose model distance are below a given threshold are inliers, and the retained model maximizes the inlier count, or consensus. Defining this threshold however requires knowing the noise level in the data. Some methods lift this constraint by estimating jointly a threshold and a model. For them, the inlier count is replaced by new measures involving both threshold and inlier count for optimization. We call these methods adaptive or automatic.

We review these methods and examine their performance on a benchmark of three computer vision problems central to Multi-View Stereo (MVS) and Structure-From-Motion (SfM) pipelines [START_REF] Schonberger | Structurefrom-motion revisited[END_REF][START_REF] Moulon | OpenMVG: Open multiple view geometry[END_REF]: ho-mography, fundamental and essential matrix fitting. Data for these problems consists of feature point pair correspondences, leading the algorithm to classify them as inlier or outlier.

Firstly, automatic threshold estimation does benefit MVS pipelines [START_REF] Moulon | Adaptive structure from motion with a contrario model estimation[END_REF], although its performance should be measured on ground-truth data independently. Secondly, incremental MVS pipelines also benefit from good inlier classification, as inliers are triangulated to from 3D points, thereafter used as anchors for following views to estimate their pose through Perspective from n Points (PnP). Thirdly, since RanSaC methods are the basis of SfM and MVS software, robust analysis will improve the state of the art. Fourthly and finally, deep-learning 3D pipelines use the output of MVS pipelines, most often [START_REF] Schonberger | Structurefrom-motion revisited[END_REF], for training database generation [START_REF] Li | MegaDepth: Learning singleview depth prediction from internet photos[END_REF].

We first contribute a method to create semisynthetic data with ground truth labels to assess classification power of RanSaC algorithms. Previous artificial datasets are unrealistic; e.g. [START_REF] Cohen | The likelihood-ratio test and efficient robust estimation[END_REF] performs the evaluation on plane estimation in random 3D point clouds, and [START_REF] Barath | MAGSAC: marginalizing sample consensus[END_REF] generates random homographies and cor-

I = I(θ, σ) ⊂ P set of model inliers Q : 2 P × Θ → R model quality function respondences.
Real datasets on the opposite end cannot offer a control over the noise and outliers: they often rely on an algorithm to calibrate an active sensor to the data which introduces error like the KITTI dataset [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF] and the 7 scenes dataset [START_REF] Shotton | Scene coordinate regression forests for camera relocalization in rgb-d images[END_REF] or do not correct inlier noise as in [START_REF] Cordts | The cityscapes dataset for semantic urban scene understanding[END_REF]. Our method offers the possibility to create, from any image dataset, a realistic semi-synthetic dataset. Note that there have already been comparative studies of RanSaC, such as (Choi et al., 2009). These studies however focus on threshold-controlled RanSaC derivatives on a small real-world dataset without ground truth. We contribute an analysis of the classification and retrieval power of adaptive RanSaC algorithms. We thus pit threshold-free methods against each other, rather than against baseline RanSaC as was done before.

Section 2 reviews the automatic RanSaC methods, Section 3 the benchmark data and methods. Sections 4 and 5 cover the results and their analysis, and Section 6 concludes.

AUTOMATIC RANSAC METHODS

Notation

We reuse and simplify the notation of [START_REF] Barath | MAGSAC: marginalizing sample consensus[END_REF], standardized in Table 1. Input points exist in S = R k , k > 0, with the input point set noted as P ⊂ S.

For image coordinates, the point dimension k = 2; for pair correspondences, k = 4.

A model of d degrees of freedom exists in Θ ⊂ R d , and can be obtained via the fitting function F, applied to a set of data points sampled by the sampling function Sa. d = 8 for homographies, 7 for fundamental matrices, and 5 for essential matrices.

The probability of Sa drawing an uncontaminated sample (including only correct data) is p(ε), with ε ∈ [0, 1] the true (hence generally unknown) inlier ratio. Sa typically samples s points uniformly in P , hence p(ε) = ε s , an increasing function of ε.

Given a model θ, we can calculate the residual error between that model and a data point P using D(P, θ). I selects the points that are inliers to a model based on the residuals. Finally, Q defines the quality of the fit θ on P .

While D is model-dependent, the standard selector I keeps points with residuals below a threshold σ:

I = I(θ, σ) = {P ∈ P : D(P, θ) < σ}. Q(I , θ) = |I |
is then the number of inliers. Since inlier count increases with σ, standard Q definitions are unreliable quality measures for RanSaC variants. Algorithm 1 is the pseudo-code for a generic RanSaC. A type II error corresponds to missing the true model due to insufficient search.

Input: P , Sa, F, p, Q, σ Input: confidence against type II error β, it max (or min. inlier rate ε) Output: Best model parameters and set of inliers

I max = / 0, q max = 0 it = 0 (and it max = ln(1-β) ln(1-p(ε)) if ε is input) while it ≤ it max do sample = Sa(P ), θ = F(sample) I = I(θ, σ), q = Q(I , θ) if q > q max then q max = q, θ max = θ, I max = I ε = |I |/|P |, it max = ln(1-β) ln(1-p(ε)) it = it + 1 return θ max , I max
Algorithm 1: RanSaC algorithm

Existing Algorithms

The methods gathered in Ref.

Consistency assumption Optimized function [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] Bounded residuals (inliers) Inlier set size [START_REF] Miller | MUSE: Robust surface fitting using unbiased scale estimates[END_REF] Gaussian residual distribution (inliers) Scale estimate [START_REF] Wang | Robust adaptive-scale parametric model estimation for computer vision[END_REF] Gaussian (inliers) Inlier/threshold Minimal residual density (transition) [START_REF] Fan | Robust scale estimation from ensemble inlier sets for random sample consensus methods[END_REF] Gaussian (inliers) Scale estimate Residuals correlate (cross-model) [START_REF] Choi | StaRSaC: Stable random sample consensus for parameter estimation[END_REF] Low parameter variance (cross-model) Variance [START_REF] Moisan | Automatic homographic registration of a pair of images, with a contrario elimination of outliers[END_REF] Problem specific (outlier) Number of false alarms [START_REF] Cohen | The likelihood-ratio test and efficient robust estimation[END_REF] Uniform (outliers) Likelihood [START_REF] Moisan | Fundamental matrix of a stereo pair, with a contrario elimination of outliers[END_REF] Problem specific (outliers) Number of false alarms [START_REF] Dehais | Two-view 3D reconstruction for food volume estimation[END_REF] Data-driven (outliers) False discovery rate [START_REF] Barath | MAGSAC: marginalizing sample consensus[END_REF] Uniform (inliers) -Uniform (outliers) Deviation [START_REF] Rabin | MAC-RANSAC: a robust algorithm for the recognition of multiple objects[END_REF] Problem specific (outliers) Greedy number of false alarms [START_REF] Isack | Energy-based geometric multi-model fitting[END_REF] Graph cuts energy [START_REF] Toldo | Image-consistent patches from unstructured points with J-linkage[END_REF] Residuals correlate (cross-model) Inlier cluster merging cost [START_REF] Magri | T-linkage: A continuous relaxation of J-linkage for multi-model fitting[END_REF] Residuals correlate (cross-model) Residual cluster merging cost [START_REF] Magri | Robust multiple model fitting with preference analysis and low-rank approximation[END_REF] Residuals correlate (cross-model) Factorization error of residual matrix peated patterns in residuals of different models using cross correlations or clustering. The original RanSaC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] algorithm uses inlier consistency: all inliers have residuals below a certain threshold. The first automatic threshold method was MUSE [START_REF] Miller | MUSE: Robust surface fitting using unbiased scale estimates[END_REF]. MUSE assumes that inlier residuals follow a Gaussian distribution, and estimates the noise level for all inlier sets of all tested models. The smallest noise for each model becomes its quality measure, and the model with the smallest noise level is selected overall. [START_REF] Wang | Robust adaptive-scale parametric model estimation for computer vision[END_REF] relies on inliers following a unimodal distribution (specifically Gaussian in experiments). For single models, this method puts a threshold on residual distribution density. The quality measure is the ratio of inliers to inlier threshold value.

The method in [START_REF] Fan | Robust scale estimation from ensemble inlier sets for random sample consensus methods[END_REF]) merges inlier and cross-model consistency. This method uses the weighted median absolute deviation of all residuals as both scale estimate and quality function. Each time a data point has a small residual for a sampled model, its weight and probability to be sampled increase. This way, the weight biases the quality function towards the median absolute deviation of inliers to stable models.

StarSaC [START_REF] Choi | StaRSaC: Stable random sample consensus for parameter estimation[END_REF]) uses crossmodel consistency as well, namely that variance of model parameters is minimal for the optimal threshold. The method calls RanSaC with multiple thresholds, multiple times per threshold. The quality measure is the variance of resulting model parameters for a given threshold.

A Contrario RanSaC [START_REF] Moisan | Automatic homographic registration of a pair of images, with a contrario elimination of outliers[END_REF][START_REF] Moisan | Fundamental matrix of a stereo pair, with a contrario elimination of outliers[END_REF] (AC-RanSaC, originally named ORSA [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF])) was the first outlier-consistent method. AC-RanSaC approximates for each problem the probability distribution of residuals for random input: the background distribution. It then minimizes a combinatorial prediction of false inliers by comparing the cumulative distributions of data and background residuals.

An extension of AC-RanSaC [START_REF] Dehais | Two-view 3D reconstruction for food volume estimation[END_REF]) adapts the method in two ways: by generating outlier data from inlier data, and simplifying the significance measure. This method scrambles input matches to generate background distributions, and seeks the model with the most inliers subject to a maximal rate of inliers in the background data.

The likelihood-ratio method [START_REF] Cohen | The likelihood-ratio test and efficient robust estimation[END_REF] relies on a uniform distribution of outlier residuals. The quality function approximates the likelihood of each model against this uniform distribution, using substantial statistical derivations.

MAGSAC [START_REF] Barath | MAGSAC: marginalizing sample consensus[END_REF] is the most recent publication on this work's subject. It combines inlier and outlier consistency assumptions, where both follow uniform distributions on different intervals. MAGSAC then estimates the model's deviation from the background noise, without explicitly classifying inputs into inliers and outliers.

Other methods exist to detect multiple models in data; though they are out of scope, we list some here. [START_REF] Rabin | MAC-RANSAC: a robust algorithm for the recognition of multiple objects[END_REF] uses the principle of A Contrario RanSac [START_REF] Moisan | Automatic homographic registration of a pair of images, with a contrario elimination of outliers[END_REF] in a greedy optimization to extract multiple models. [START_REF] Isack | Energy-based geometric multi-model fitting[END_REF] generates multiple models, before attaching data to those models to minimize total residuals and number of models. J-Linkage [START_REF] Toldo | Image-consistent patches from unstructured points with J-linkage[END_REF], its extension T-Linkage [START_REF] Magri | T-linkage: A continuous relaxation of J-linkage for multi-model fitting[END_REF], and Low-Rank Preference Analysis [START_REF] Magri | Robust multiple model fitting with preference analysis and low-rank approximation[END_REF] rely on cross-model consistency, while using different methods to cluster inlier sets and models jointly.

BENCHMARK

Data Generator

The distributions of inliers and ouliers in the image space have a major impact on the effectiveness of model fitting. Benchmarks on data extracted from photographs are invaluable, but lack the power to generalize observations because of their small size and the lack of control over noise and outliers. Synthetic data on the other hand are flexible and customizable but unrealistic as the chosen model generation and inlier sampling methods impact the results.

We propose a simple procedure to generate realistic, semi-synthetic data with ground truth classification. It gives access to real models and inliers, with outliers whose distance to the model is controlled.

The data generator takes an image pair with point matches and evaluates its underlying model using AC-RanSaC [START_REF] Moisan | Automatic homographic registration of a pair of images, with a contrario elimination of outliers[END_REF][START_REF] Moisan | Fundamental matrix of a stereo pair, with a contrario elimination of outliers[END_REF] at arbitrary precision and up to 10 000 iterations. The returned model is then used as "ground truth", and the estimated inliers as the basis for datadriven yet perfect inliers.

To generate perfect inliers, the matches are modified with respect to the ground truth model. For homographies, inlier points in the first image are mapped into the second using the ground truth homography (figure 1). For fundamental and essential matrices, the point on the second image of each inlier match is projected on the true epipolar line of the first point (figure 2).

The artificial inlier matches and outlier matches can then be derived from those "ground truth" inlier matches. Inlier matches are created by adding noise uniformly drawn in [-σ noise , σ noise ] 2 to the second image point of each match to generate a controled pixel error. Uniform noise gives here better control and testability for the inlier/outlier threshold than Gaussian noise, which is unbounded.

Once inlier matches are generated, outliers are inserted by generating random matches in the two images, uniformly sampled in error space ensuring a distance to the model greater than the maximum inlier error σ noise . Sampling in error space is explained for homography estimation in figure 3 and for fundamental and essential matrix estimation in figure 4. This choice of distribution in error space returns a realistic outlier distribution and truly challenges the algorithms. A simple uniform distribution of outliers in match space on the contrary has too little structure to disturb the RanSaC algorithm. For each dataset and inlier ratio, we generate enough outliers to obtain the desired ratio, and downsample uniformly to have 4000 data points or fewer.

Tested Algorithms

We benchmark seven algorithms with varied approaches to inlier classification: the baseline RanSaC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF], MUSE [START_REF] Miller | MUSE: Robust surface fitting using unbiased scale estimates[END_REF], StaRSaC [START_REF] Choi | StaRSaC: Stable random sample consensus for parameter estimation[END_REF], A-Contrario RanSaC (AC-RanSaC) [START_REF] Moisan | Fundamental matrix of a stereo pair, with a contrario elimination of outliers[END_REF], Likelihood Ratio Test (LRT) [START_REF] Cohen | The likelihood-ratio test and efficient robust estimation[END_REF], Marginalizing Sample Consensus (MAGSAC) [START_REF] Barath | MAGSAC: marginalizing sample consensus[END_REF] and Fast-AC-RanSaC-an adaptation of AC-RanSaC. [START_REF] Isack | Energy-based geometric multi-model fitting[END_REF][START_REF] Toldo | Image-consistent patches from unstructured points with J-linkage[END_REF][START_REF] Magri | T-linkage: A continuous relaxation of J-linkage for multi-model fitting[END_REF], though relatively recent, have been excluded as they tackle the multi-model settup which we do not consider in this study.

RanSaC acts as baseline, with fixed inlier/outlier thresholds σ(px) to show non-adaptive results. To avoid degenerate cases in the worst case we strengthen its stopping criterion to ensure it draws 5 outlier-free samples instead of just 1 with confidence β. This requires a modification in the formula for it max in Algorithm 1.

MUSE proposes an improvement over Least Median of Squares [START_REF] Leroy | Robust regression and outlier detection[END_REF] with a new objective function based on a scale estimate to increase robustness wrt outliers. The algorithm works similarly to RanSaC, with multiple iterations of a minimal sampler estimating a model and then ranking based on their scale estimate. We adapted the algorithm by adding the classic termination criterion of RanSaC to speed up the execution.

StaRSaC removes the need for a user set threshold of RanSaC by launching multiple RanSaCs for different thresholds. It then estimates at each threshold the variance over the parameters and the threshold yielding the lowest variance is selected. Our implementation uses the same thresholds as [START_REF] Cohen | The likelihood-ratio test and efficient robust estimation[END_REF] to speed up the process by only considering thresholds that make sense in pixel-scale problems.

AC-RanSaC seeks the model with the lowest risk of type I error. This is measured as the Number of False Alarms (NFA), which estimates the expected Figure 1: From an imperfect match (p 1 , p 2 ) considered inlier by AC-RanSaC, the "perfect match" (p 1 , p 2 ) is constructed such that p 2 = H p 1 using a realistic homography H given by AC-RanSaC.

Figure 2: From an imperfect match (p 1 , p 2 ) considered inlier by AC-RanSaC, the "perfect match" (p 1 , p 2 ) is constructed using p 2 the orthogonal projection of p 2 on the epipolar line L 1 = F p 1 where F is a realistic fundamental matrix given by AC-RanSac. This does not guarantee that p 2 represents the same physical point as p 1 , but that some 3D point at possibly different depth projects exactly at p 1 and p 2 .

Figure 3: A random point q 1 is drawn from the left image. Using the ground truth model H, its perfect match q 2 = Hq 1 is computed. Then a direction and a distance to q 2 are drawn uniformly in order to create q 2 so that it remains in the image and out of the inlier zone (marked in red) defined by the inlier noise level.

Figure 4: A random point q 1 is drawn from the left image.

Using the ground truth model F, the epipolar line L 1 = Fq 1 is computed. Then position on this line and a distance to L 1 are drawn uniformly in order to create q 2 so that it remains in the image and out of the inlier zone (marked in red) defined by the inlier noise level. number of false positive models generated by an inlier set:

NFA(θ, σ) ∼ |P | k(σ) k(σ) s p k(σ)-s σ , (1)
with k(σ) = |I(θ, σ)| the number of inliers at threshold σ and p σ the relative area of the image zone definining inliers at σ. This function is computed for all σ ≤ σ max such that k(σ) ∈ {s + 1, . . . , n}. The method is virtually parameter-free, with σ max = +∞ and the NFA upper bound NFA max = 1. The Likelihood Ratio Test (LRT) proposes a fast method to control type I and type II errors. Its quality function is the likelihood that the dataset is nonrandom for a given model:

L(ε, σ) = 2|P | ε log ε p σ + (1 -ε) log 1 -ε 1 -p σ , (2)
with inlier ratio ε = k(σ)/|P | and σ spanning a predefined list {σ min , . . . , σ max }. The adjustment of it max is the same as RanSaC, with an early bailout system to sift through models faster, controlled by a new parameter γ for the type II error (rejection of a good model). MAGSAC introduces a new quality function, based on the likelihood of a model given uniform inliers and outliers, a speedup method using computing blocks, and a post processing method, σ-consensus, that refits the final model on a weighted set of pseudoinliers. It uses four parameters: the threshold for pseudo-inliers σ max , a reference threshold σ re f , a lower bound on model likelihood, and the number of data blocks.

Fast-AC-RanSaC is a speed up of AC-RanSaC by exploiting ideas from LRT. The idea to create this method comes from our observations, see Section 5. It uses the same objective function as AC-RanSaC but instead of testing all thresholds it considers the same quantified thresholds as LRT. Using this selection of thresholds removes the need for a sorting of the residuals and thus speeds up the method.

Performance Measures

To compare the classification power of the various algorithms, we use precision-the ratio of correctly detected inliers among all detected inliers-and recallthe ratio of correctly detected inliers among true inliers. To represent results more easily, we use the harmonic mean of precision and recall, the F1-Score. We quantify the impact of noise and outliers on these metrics using the semi-synthetic data of Section 3.1. For efficiency evaluation, we measure execution time.

As MAGSAC does not separate data points into inliers and outliers but weighs them, we evaluate its performance through three metrics: highest recall at the precision of AC-RanSaC, which will be called Magsac-P, highest precision at the recall of AC-RanSaC, Magsac-R, and weighted equivalents of precision and recall, Magsac-W.

Parameters

We experimented the data generator on the SIFT [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF] point matches from the USAC dataset as well as SIFT points computed on Multi-H, kusvod2 and the homogr datasets. A SIFT ratio of 0.6 was used. USAC [START_REF] Raguram | USAC: a universal framework for random sample consensus[END_REF] proposes SIFT matches for 10 homography image pairs, 11 fundamental matrix image pairs, and 6 essential matrix image pairs with calibration matrices. Multi-H [START_REF] Barath | Multi-H: Efficient recovery of tangent planes in stereo images[END_REF] proposes 24 fundamental matrix image pairs, kusvod2 16 fundamental matrix image pairs, and homogr 16 homography image pairs. 1 The inlier noise σ noise varied between 0 and 3 pixels by steps of 0.1. The outlier ratio 1ε varied between 0 and 0.9 by steps of 0.1. For each image pair and setting, we generate N gen = 5 different datasets, and run each algorithm N run = 5 times on each for a total of 25 experiments. We average the precision and recall over each dataset and run, excluding cases where an algorithm failed to find a good model.

As minimal solvers F, we use the standard 4-point algorithm for homography and 7-point algorithm for fundamental matrix [START_REF] Hartley | Multiple view geometry in computer vision[END_REF], and the 5-point algorithm for essential matrix [START_REF] Nistér | An efficient solution to the fivepoint relative pose problem[END_REF].

We take the standard RanSaC algorithm as baseline and benchmark MUSE, StarSAC, LRT, AC-RanSaC, Fast-AC-RanSaC, and MAGSAC algo-1 http://cmp.felk.cvut.cz/data/geometry2view/ rithms. RanSaC and AC-RanSaC implementations came from [START_REF] Moulon | AC-RanSaC implementation[END_REF], MAGSAC from [START_REF] Barath | MAGSAC implementation[END_REF], MUSE from VXL 2 whereas LRT, Fast-AC-RanSaC and StarSAC were implemented from scratch.

The parameters defined in section 3.2 are set as follows (from the relevant publicaion when available). β, the standard success confidence, is set to 0.99. σ max , the inlier search cutoff threshold for AC-RanSaC, Fast-AC-RanSaC, StarSaC and LRT, is set to 16 pixels to improve speed. NFA max , the NFA threshold for AC-RanSaC and Fast-AC-RanSaC, is set to 1 false alarm. The other parameters of LRT, were set to α = 0.01, γ = 0.05.

The other parameters of MAGSAC were set to p = 10 data partitions, σ max = 10 pixels, and σ re f = 1.

RESULTS

Before presenting results for the different methods, StarSAC has been excluded from this benchmark. Indeed, after initial tests, it runs very slowly, even with modification to the initial algorithm to reduce runtime. A usual run will take 3 to 5 minutes with precision and recall only slightly above baseline.

Figure 5 gives an overview of each algorithm's execution time. LRT, MUSE, Fast-AC-RanSaC and RanSaC are usually the fastest, with LRT faster than the others on easy cases. Both LRT and RanSaC however are quite sensitive to the task complexity: when facing high inlier noise or outlier ratio, their runtime increases significantly, sometimes up to four or five seconds per run. MUSE and Fast-AC-RanSaC keep relatively low runtimes in all settings, always below 1s. AC-RanSaC's runtime is not impacted by inlier noise, only by the number of matches in the dataset. Its runtime remains almost always under one second per run, though it is often the slowest algorithm on easy settings. However, it can be faster than Fast-AC-RanSac on easy settings with not many points where the sorting time of residuals is fast compared to the computation of the residuals themselves. MAGSAC is the most efficient algorithm on complex tasks with runtimes up to ten times lower than AC-RanSaC. However, because of instabilities in MAGSAC's execution, a 1-second cap was used: for inlier noise level above 1 pixel or outlier ratio below 0.4, MAGSAC can find a good model but still fail to terminate.

Except for RanSaC, no algorithm presented a compromise between precision and recall (one increasing while the other decreases). This justifies the 2 https://github.com/vxl/vxl Runtime (s) for outlier ratio of 0.9 on artificial fundamental matrix -KUSVOD2 -dataset 11. Runtime (s) for outlier ratio of 0.9 on artificial essential matrix -USAC -dataset 1. use of F1-Score over either precision or recall.

Trends in behavior were impacted by the noise level and outlier ratio for all algorithms, but were neither by task, be it homography, fundamental matrix or essential matrix estimation, nor by dataset. While performance differed between image pairs or different tasks, performance always decreased consistently relative to the data generator parameters. Figures 6 and7 illustrate the typical behaviors with low and high outlier ratios on a variety of estimation problems and datasets. An intermediate setting, for example an outlier ratio around 0.5, is not included as the behavior was observed to be intermediate between the two extremes.

The two fixed-threshold RanSaC have opposite behaviors. The "tight" RanSaC with a threshold of 3 pixels has high precision on easy situations, but poor recall, and both drop as noise and outliers increase. The "loose" RanSaC with a threshold of 9 pixels has stable recall, but precision drops as noise and outlier ratio increase. Both eventually perform poorly in complex cases as too many outliers are wrongly classified.

MUSE's performance is not impacted much by the semi-artificial generation parameters but does not show consistently good behavior. On the one hand, it can have poor performance on easy settings, with below baseline precision and recall. On the other hand, it can show very good precision, above 95% on very complex settings. However, its recall is always low as the thresholds selected are usually smaller than other methods.

AC-RanSaC shows a very good performance on low outlier ratios. It maintains good precision as the outlier ratio increases, but its recall drops, impacting the F1-score.

LRT returns slightly lower precision and recall than AC-RanSaC, for low outlier ratios or cases where all algorithms perform well. The gap increases significantly for the highest inlier noise levels or outlier ratios data become more challenging, the performance dropping to baseline.

Fast-AC-RanSaC has medium performance. It has usually good recall but average precision as it selects a threshold twice as big as the real inlier noise level. It can however, in some cases perform relatively well or even to the same level as normal AC-RanSac but it is not a consistent behavior.

MAGSAC displays two interesting behaviors. For outlier ratios below 0.4, MAGSAC alternates between great fits and nearly random models, instead of consistently returning a satisfactory model. This explains the F1-scores around 0.75 on figure 6, the result of averaging models with precision and recall below 0.5 and models with precision and recall above 0.95. For outlier ratios above 0.4, MAGSAC shows equal or greater performances than AC-RanSaC and far less sensitivity to inlier noise. MAGSAC is also the only method to maintain precision and recall scores above 0.9 (resp. 0.8) in challenging cases. The 1-second cap F1-score for outlier ratio of 0.3 on artificial fundamental matrix -USAC -dataset 5.

Figure 6: Typical F1-score evolution over inlier noise for a low outlier ratio (0.3). Estimation problem, dataset name and image pair number can be found in each graph's title. Magsac-P, Magsac-R and Magsac-W correspond to the metrics presented in Section 3.3. on MAGSAC runtime does not impact performance in simple cases, where bad models are estimated irrespectively of runtime. On challenging cases, this cap is sometimes reached but performance remains overall better than other algorithms.

DISCUSSION

Differences in runtime can be explained by the number of iterations in each algorithm as much as their design. Indeed, each algorithm has to compute models-which is fast-and compute residuals for all points-slow. LRT's high and low speeds likely stem from its early bailout strategy, skipping residuals entirely. This is a benefit in easy settings, where correct models are plentiful, but hurts complexity in the opposite case, where some rare correct models are not fully evaluated. AC-RanSaC's high runtime for large datasets comes from its sorting step, which takes then as much time as computing residuals. However, this may be amended by bucket sorting and discretization of σ as with LRT to remove sorting entirely. This is what led to the development of Fast-AC-RanSaC which shows promising results but could be improved as its performance is usually worst than that of LRT that was developped directly in this settings.

StarSAC offers poor performance compared to other methods except RanSaC. Except in some rare cases, MUSE's performance is below that of newer methods. As explained below, in all settings one of the newest methods will offer better performance.

Though it is usually the slowest method, AC- F1-score for outlier ratio of 0.8 on artificial fundamental matrix -Multi H -dataset 21.

Figure 7: Typical F1-score evolution over inlier noise for a high outlier ratio (0.8). Estimation problem, dataset name and image pair number can be found in each graph's title. Magsac-P, Magsac-R and Magsac-W correspond to the metrics presented in Section 3.3.

RanSaC shows consistently good precision and recall. The algorithm does adapt well to change, and performs far above baseline in difficult cases. It is a robust but slower algorithm and except in our most complex settings, it produces a good result so it is a good pick when high classification performance is required.

LRT performed slightly worse than AC-RanSaC, with selected inlier threshold usually larger, yet much faster. LRT thus offers a valuable trade-off between quality and speed. It is however fairly sensitive to the complexity of the task: a decrease in performance to baseline level in complex settings and a steep increase in runtime.

Fast-AC-RanSaC was developped to improve over AC-RanSaC by reducing runtime but it fails to outperform LRT in most cases.

MAGSAC has the potential to perform similarly or better than AC-RanSaC, at comparable or better speeds with impressive performance on the most complex tasks. It has a very strong resilience to outlier and inlier noise and should be used when other algorithms fail to produce a satisfying result. The lack of robustness of its current implementation makes it more risky to use first hand.

Finally, our semi-artificial datasets help reveal behavior independent of the dataset chosen as initial input, and thus offers new insight in automatic RanSaC algorithm analysis.

CONCLUSION

RanSaC is a robust and efficient algorithm for a wide range of situations, whose major weaknesses appear in case of high outlier ratios and unknown inlier noise. Thanks to a new method to generate semi-synthetic ground truth data we have made a quantitative evaluation of three major algorithms for noise-and outlierrobust fitting based on RanSaC. For most standard usages, all algorithms perform well, with only execution speed varying. When outliers outnumber inliers and noise is large, adaptive methods justify their existence by outperforming standard RanSaC by a large margin, at the cost of speed. Overall, the algorithms offer a choice for those who seek to trade robustness, accuracy, and execution speed. For example, LRT is a good algorithm to use on simple cases, offering better performance than traditional RanSaC in comparable runtime. MAGSAC has a very strong resilience to outlier and inlier noise and should be used when other algorithms fail to produce a satisfying result. The lack of robustness of its current implementation makes it more risky to use first hand. AC-RanSaC would then be a more robust but slower algorithm. Except in our most complex settings, it produces a good result so it is a good pick when high accuracy is required. The variety of tests show the strength of the data generation procedure in exhibiting the sensitivity of the methods to each problem, to noise, and to outliers.

Thanks to such observations, we plan to improve these methods using the optimizations proposed above as we did with Fast-AC-RanSaC that proved a potential improvement if a more stable implementation can be developped. It is also possible now to perform an ablation study of each proposed ingredient like the σ-consensus post-processing of MAGSAC to determine precisly their impact on the robustness and retrieval power of each method. Finally, we plan to extend the study on the remaining model-fitting problem involved in MVS pipelines: Perspective from n points (PnP). This problem recovers the camera pose of a view inserted in the pipeline from 2D-3D correspondences, and model quality measures should be adapted to that specific case.

Figure 5 :

 5 Figure 5: Runtimes over different inlier noise levels and outlier ratios. The fitting problem, dataset name, and image pair number are in each graph title. Ransac-σ corresponds to RanSaC with threshold σ.

  for outlier ratio of 0.3 on artificial essential matrix -USAC -dataset 4.

Table 1 :

 1 Notations

		Definition	Description
	k ∈ N >0	dimension of data points
	S = R k	space of data points
	P ⊂ S	set of input data points
	d ∈ N >0	degrees of freedom of a model
	Θ ⊂ R d	space of model parameters
	θ ∈ Θ	parameter vector of a model
	s Sa : 2 S → S s ∈ N >0 F : S s → Θ	data sample size sampling function fitting function
	p : [0, 1] → [0, 1] proba. of sampling inliers only
	D : S × Θ → R	point-model residual function
	σ ∈ R	inlier threshold
	I	: Θ × R → 2 P	inlier selector function

Table 2

 2

	generate new in-

Table 2 :

 2 Overview of robust fitting methods with adaptive inlier criteria. Bracketed terms in the "Consistency assumption" column specify where the assumption is made.