Pierre Gurdjos

Adrien Bartoli

Peter Sturm

Is Dual Linear Self-Calibration Artificially Ambiguous?

This purely theoretical work investigates the problem of artificial singularities in camera self-calibration. Selfcalibration allows one to upgrade a projective reconstruction to metric and has a concise and well-understood formulation based on the Dual Absolute Quadric (DAQ), a rank-3 quadric envelope satisfying (nonlinear) 'spectral constraints': it must be positive of rank 3. The practical scenario we consider is the one of square pixels, known principal point and varying unknown focal length, for which generic Critical Motion Sequences (CMS) have been thoroughly derived. The standard linear self-calibration algorithm uses the DAQ paradigm but ignores the spectral constraints. It thus has artificial CMSs, which have barely been studied so far.

We propose an algebraic model of singularities based on the confocal quadric theory. It allows to easily derive all types of CMSs. We first review the already known generic CMSs, for which any self-calibration algorithm fails. We then describe all CMSs for the standard linear selfcalibration algorithm; among those are artificial CMSs caused by the above spectral constraints being neglected. We then show how to detect CMSs. If this is the case it is actually possible to uniquely identify the correct selfcalibration solution, based on a notion of signature of quadrics. The main conclusion of this paper is that a posteriori enforcing the spectral constraints in linear self-calibration is discriminant enough to resolve all artificial CMSs.

Introduction

Structure-from-Motion (SfM) is the problem of recovering a metric model -the scene structure and the camera motion and intrinsic parameters-from multiple views. It has been extensively studied over the past few decades (see e.g. [START_REF] Faugeras | The geometry of multiple images[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF]). The self-calibration paradigm allows one to solve SfM with few assumptions about the intrinsics and barely none about the structure and the motion, thus making SfM versatile and flexible. In theory, the mere zero-skew assumption is sufficient for the SfM problem to be wellposed [START_REF] Heyden | Minimal conditions on intrinsic parameters for Euclidean reconstruction[END_REF]. We make the stronger standard assumption that the pixels are square and the principal point lies at the image centre, but that the focal length is time-varying.

One of the most remarkable results in SfM says that, given enough point correspondences, a projective reconstruction of 3D points and cameras can be computed [START_REF] Finsterwalder | Die geometrischen Grundlagen der Photogrammetrie[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Hartley | Stereo from uncalibrated cameras[END_REF]. The metric upgrade of this model is a further reconstruction step, that draws on the equivalence of the projective to the metric model via an unknown 3D homography. This is mathematically formulated using the elegant geometrical paradigm of the Dual Absolute Quadric (DAQ) proposed by Triggs in 1997 [START_REF] Triggs | Autocalibration and the absolute quadric[END_REF], which has also been extended to that of the Absolute Quadratic Complex [START_REF] Ponce | On the absolute quadratic complex and its application to autocalibration[END_REF][START_REF] Valdés | Camera autocalibration and the calibration pencil[END_REF]. The DAQ has nonlinear 'spectral constraints': it is semipositive and rank-3. This models the fact that the DAQ is the plane-envelope of the Absolute Conic, a virtual conic (i.e. consisting only of complex points). Once the DAQ is recovered, the upgrading homography is easily extracted from it. This class of algorithms has been popularised by the linear least-squares formulation of Pollefeys et al. [START_REF] Pollefeys | Self-calibration and metric reconstruction inspite of varying and unknown intrinsic camera parameters[END_REF][START_REF] Seo | Auto-calibration by linear iteration using the DAC equation[END_REF], which is hereafter dubbed dual linear selfcalibration. Recently, self-calibration approaches enforcing the spectral constraints while globally optimizing some algebraic error measure have been proposed [START_REF] Bocquillon | On constant focal length self-calibration from multiple views[END_REF][START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF]. However, the above dual linear self-calibration approach is probably still the most used one.

As mentioned in [8, p498], 'self-calibration can work well in the right circumstances, but used recklessly it will fail', especially if one does not 'take care to avoid ambiguous motion sequences', so-called critical motion sequences (CMSs). For these, there exist more than one virtual conic satisfying the self-calibration constraints. Sturm [START_REF] Sturm | Critical motion sequences for the self-calibration of cameras and stereo systems with variable focal length[END_REF] and Kahl et al. [START_REF] Kahl | Critical motions for autocalibration when some intrinsic parameters can vary[END_REF] studied this problem and established that there exist generic critical motion sequences for the camera, and that they defeat any self-calibration algorithm.

The SfM framework has all its basic building blocks in place. There is however an important missing piece regarding artificial CMSs. It has been known that there exist CMSs which are not generic for the self-calibration problem, but for which the dual linear self-calibration algorithm fails in finding the 'true' DAQ [START_REF] Sturm | A case against Kruppa's equations for camera selfcalibration[END_REF]. This is essentially due to this algorithm ignoring the spectral constraints. In other words, in generic criticality, only quadric envelopes representing a virtual conic can satisfy the self-calibration equations while, in artificial criticality, any quadric envelope (virtual or not, degenerate or not) can satisfy them. In the case where a linear self-calibration algorithm returns a 1D family of ambiguous solutions, previous works [START_REF] Pollefeys | Self-calibration and metric reconstruction inspite of varying and unknown intrinsic camera parameters[END_REF][START_REF] Seo | Auto-calibration by linear iteration using the DAC equation[END_REF] showed that the rank-deficiency constraint can be enforced a posteriori to select candidate solutions. Bartoli et al. [START_REF] Bartoli | The 3D line motion matrix and alignment of line reconstructions[END_REF] select the most realistic solution by examining the camera focal length.

In this paper, we propose a theoretical framework for exhaustively studying CMSs in dual linear self-calibration, based on the confocal quadric theory. Interestingly enough, this theory has been established long ago by famous mathematicians. The resulting framework can be viewed as an add-on to the DAQ model of self-calibration. The main conclusion of this paper is thus that for the studied selfcalibration problem, even linear algorithms only suffer from the generic CMSs, if spectral constraints are enforced a posteriori.

Paper organization. In section 2, the self-calibration problem and its ingredients are formulated and the notion of CMS is defined. Generic CMSs are reviewed in section 3. In section 4, we provide an exhaustive list of CMSs for dual linear self-calibration and highlight which of these are artificial, i.e. only exist due to neglecting the spectral constraints. Some details on the underlying theoretical analysis are provided in section 5. In section 6, we show how a projectively invariant signature for quadrics allows one to identify the type of CMS that caused linear selfcalibration to give ambiguous results. Finally, we explain that in the case of an artificial CMS, this signature allows us to uniquely recover the true self-calibration solution.

Problem Formulation

We consider the self-calibration problem for the case of a varying focal length but where the other intrinsic parameters are known. Let us review the classical formulation based on the Dual Absolute Quadric (DAQ) [START_REF] Triggs | Autocalibration and the absolute quadric[END_REF]. This is the planeenvelope of the Absolute Conic Ω ∞ (AC). Given a 3 × 4 perspective projection matrix P, the image of the DAQ is given by the projection equation

ω * ∼ PQ * ∞ P . ( 1
)
where ω * is the Dual Image of the Absolute Conic (DIAC). We assume to be given a set of n cameras obtained by means of projective reconstruction, that we write

P j =   a j b j c j   , j = 1, . . . , n (2)
where a j , b j and c j are 4-vectors representing planes.

Camera j projects the DAQ to ω * j . Under the above assumptions on the camera's intrinsic parameters, we may assume ω * j ∼ diag (f j ) 2 , (f j ) 2 , 1 , where f j denotes the focal length of camera j. It can be readily seen that Q * ∞ then satisfies a set of four linear equations for each camera:

a j Q * ∞ a j -b j Q * ∞ b j = 0, a j Q * ∞ b j = 0, (3) a j Q * ∞ c j = 0, b j Q * ∞ c j = 0. (4)
Solving those constraints for multiple cameras e.g., by optimizing in a linear least squares manner forms the basis of the dual linear self-calibration algorithms [START_REF] Pollefeys | Self-calibration and metric 3D reconstruction from uncalibrated image sequences[END_REF].

Additional constraints are that the DAQ Q * ∞ has rank 3 and is positive semi-definite. These constraints are nonlinear and are thus not taken into account in dual linear selfcalibration.

In this paper, we investigate critical motion sequences (CMS) for self-calibration, i.e., camera motions for which the problem does not have a unique solution. It is well known that there are CMSs that are generic for a given selfcalibration problem, in the sense that any algorithm will suffer from them, and that some algorithms may suffer from additional, artificial CMSs, due to not exploiting all available constraints [START_REF] Sturm | A case against Kruppa's equations for camera selfcalibration[END_REF]. In this paper, we study this issue for dual linear self-calibration. In section 3, we first review the generic CMSs and in section 4 we then derive all CMSs for dual linear self-calibration and explain which among these are artificial. After that, we show how articial CMSs can be detected from an ambiguous self-calibration result and that the ambiguity can indeed be resolved.

The definition of a CMS is as follows. Let the true cameras be P j E ∼ diag(f j , f j , 1)R j I | -t j . If there exists a Q * different from the true DAQ that satisfies all selfcalibration constraints (equations [START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF] as well as the (spectral) rank-3 and positiveness constraints on Q * ∞ ), then the set of camera poses is termed a generic CMS. Artificial CMS for dual linear self-calibration are additional sets of camera poses for which there exists a Q * different from the true DAQ that only satisfies the linear equations [START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF]. In these cases, Q * is called a 'false DAQ'.

Generic Critical Motion Sequences

The generic CMSs for self-calibration with varying focal length have been derived by Sturm [START_REF] Sturm | Critical motion sequences for the self-calibration of cameras and stereo systems with variable focal length[END_REF] and Kahl et al. [START_REF] Kahl | Critical motions for autocalibration when some intrinsic parameters can vary[END_REF]. They proceeded as follows. They sought after virtual proper conics in 'regular' 3-space (in contrast to a search in 'dual' 3-space) other than the AC; if such a conic exists that satisfies all constraints, it is called a 'false' AC. With regard to their approach, the self-calibration equations [START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF] have a simple meaning: they impose that the image of the AC is a circle, centered in the principal point. The image of a conic is such a circle, exactly if the cone, with centre the camera's optical centre and containing the conic, is a right (circular) cone. This geometric interpretation of the self-calibration constraints can now be used to reason on critical motions. Consider the existence of a false AC. Then, any camera position in a CMS, must satisfy the constraint that the cone, with centre the optical center and tangent to the false AC, is circular. Further, for any such camera position, the camera orientation must be such that the optical axis coincides with a revolution axis of that cone. Based on this interpretation, Sturm and Kahl et al. derived all types of critical motions. This was done by considering all possible cases of false ACs and working out the camera positions and orientations according to the above definition. Basically Sturm and Kahl et al. (re)discovered (and proved) a specialised case of the following result: the locus of the vertices of a circular cone through a conic consists of its conjugate conics, which is illustrated in Fig. 1. By definition, two conjugate conics are conics lying on perpendicular planes and having an axis in common and the foci-pair (either both real or complex conjugate) of one conic must be coinciding with the intersection point-pair of the other with this axis [18, p245]. We wrote 'rediscovered' as this more general result has been known for a long time and is attributed to Dupin and Steiner in [19, p82].

Artificial Critical Motion Sequences

We now consider dual linear self-calibration i.e., the problem of estimating the DAQ without imposing that it is rank 3 and positive semi-definite i.e., without imposing that the AC is actually a conic and that it is a virtual conic. In other words, any quadric in dual form can now be a candidate false DAQ, under the condition that it satisfies the constraints expressed in [START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF]. As explained above, these convey exactly that the image of the DAQ is a circle centered in the image's principal point (to be precise, the dual of such a circle). A set of camera poses is thus critical if there exists another dual quadric that is projected to centered circles in all images. More exactly, the existence of such a CMS is equivalent to that of a p-parameter linear family of false DAQs with p > 0. Terminology-wise, a CMS is said to be degenerate if the solution family is entirely degenerate i.e., if it consists of ∞ p degenerate dual quadrics D * . It is not proved here but a condition for this is that D * is 'squashed' at infinity i.e., its points are located on the plane at infinity π ∞ i.e., D * π ∞ = 0 4 .

Consider now a dual quadric and a cone enveloping it whose vertex is the optical center. Its image is a centered circle (radii can be zero or imaginary) exactly if that cone is circular and if the camera's optical axis is aligned with a revolution axis of the cone. Based on this observation, CMS can be derived as in the works cited in the previous section, by considering all (Euclidean) types of dual quadrics, and determining the camera poses that satisfy the above constraints. This latter task is greatly simplified due to results in the projective geometry literature of the 19th-and the early 20th-century [START_REF] Salmon | A treatise on the analytic geometry of three dimensions[END_REF][START_REF] Sommerville | Analytical geometry of three dimensions[END_REF][START_REF] Staude | Géométrie algébrique dans l'espace[END_REF]. In the following, we briefly summarize these and their implications for our study.

Before going further let us introduce the notions of (real and imaginary) foci and focal axes of a quadric (e.g., as in [16, p339] or [18, p225]). Any point such that the tangentcone to a quadric with that point as vertex, is circular, is a focus of the quadric. Any line through a focus relative to which that cone is rotationally symmetric is a focal axis of the quadric. This is illustrated in Fig. 2. Note that for each focus, there is either a single focal axis, or all lines through it are focal axes (this is the case if the mentioned cone is isotropic i.e., contains the AC).

Regarding the issue of which dual quadrics other than the DAQ, get projected to a dual circle that is centred in the principal point, the answer is surprisingly enough quite simple: these are the quadrics for which the camera centre is a real focus and the optical axis a real focal axis. The result that we infer from this is fundamental; a sketch of the proof is given in the appendix.

Prop. 1 (Fundamental condition)

A motion sequence is critical iff there exists an irreducible1 quadric other than the DAQ such that:

any camera centre is a focus of the quadric, 2. any optical axis is a focal axis of the quadric.

In other words, it is equivalent to say that a camera motion is critical or that the camera moves on the 'focal curve' of some irreducible quadric while its optical axis, for each position, is a focal axis of the quadric through the camera centre. Note that, as a result, only the orientation of the camera's optical axis matters, whereas rotation about the optical axis is irrelevant. quadric is a point of its focal conics (a set of focal curves also called focals, cf. [19, p81]) which are conics lying on its principal planes (mutually orthogonal and such that any two of them share a principal axis). There are other properties, see e.g. [START_REF] Sommerville | Analytical geometry of three dimensions[END_REF]. Furthermore, it is known that there are only two types of focal conic-sets of a general quadric 2 : (i) the parabola/parabola pair, (ii) the ellipse/hyperbola/virtual conic triplet (see Fig. 1). Other quadrics need special treatments that will be discussed in the sequel.

What are the foci of a quadric

The second main result is due to Chasles (see [19, p81] and also [START_REF] Primrose | Foci of a quadric[END_REF] What are the focal axes of a quadric? A focal axis of a quadric is a line through which the two (complex) planes touching the AC are also tangent to the quadric [18, p224] (see Fig. 2). Thanks in particular to Plücker (see [19, p82]), it has been established that the assemblage of focal axes of a quadric consists of the generators i.e., the axes of pencils of planes, of the quadrics of its confocal range. The general notion of focal axis is less intuitive than that of focus and, as we are only interested in focal axes through foci, we will not look deeper into the theory of confocal quadrics.

The Geometry of Criticality

The above results, in particular Chasles' result, can be used to efficiently derive types of CMSs as shown in the following section. To determine all possible geometries of CMSs, it now suffices to compute the focal conics of quadrics of different Euclidean types and to describe the results 2 Here, a general quadric is a proper quadric that is not of revolution. in a generic geometric manner (this is done quite easily using a symbolic software like MAPLE). It is rather mechanical to carry out this procedure (see e.g., example 2 below), besides a few exceptions explained below (e.g., example 3). The results are summarized in table 1, which contains all critical motions for the dual linear self-calibration problem.

To obtain these results, we needed to consider, besides the above classical geometric results, several other issues. First, these results only directly provide the camera positions in a CMS, the camera orientations are less directly given and are obtained algebraically. Second, as said previously, these results only hold for general proper quadrics; the cases of quadrics of revolution, spheres, and degenerate quadrics, need special treatment.

If we deal with a quadric of revolution, there is a major specificity: one conic in its focal-set is repeated and degenerates into either a rank-1 or a 'rank-0' conic (see Fig. 3). Note that no rank-2 focal conic does exist. The rank-1 focal conic is a ('repeated') line that coincides with the axis of revolution of the quadric. We will also call this a focal line. It contains two specialised foci called principal foci, which are the two foci of the conic obtained by meridiansection3 of the quadric. In the special case of a sphere, this linear locus of foci further degenerates into a 'rank-0 conic', meaning that every point in 3-space is a focus of the sphere. The sphere has a single principal focus, its centre. Note that all lines passing through a principal focus, are focal axes of the quadric.

Let us consider, for these special cases, the nature of focal axes that pass through a focus (keep in mind that they determine the orientation of optical axes in CMSs). Consider first the general case of a quadric having general focal conics. For any point on such a focal conic, the focal axis passing through it coincides with the tangent line to that focal conic at that point which is coplanar with the focal conic. Next, we consider the case of a focal line, which happens for quadrics of revolution, see above. For any point on a focal line, the focal axis passing through that point is the focal line itself (which is always a real line). An exception are the two principal foci, where any line passing through them is a focal axis. Finally, in the case of a sphere, every point in 3-space is a focus, as explained above, and through it there is just one focal axis which is the line joining that point and the centre of the sphere. Again, an exception is the centre of the sphere itself, for which all lines passing through it, are focal axes (see Fig. 3).

There are two classes of confocal ranges for which the locus of foci is the entire 3-space i.e., a focal space. The first includes (i) all confocal (i.e., concentric) ranges of spheres (type (R4) in table 1) and the second (ii) all degenerate confocal ranges, for which arbitrary values of α 1 , α 2 satisfy det(α

1 Q * + α 2 Q * ∞ ) = 0 (type (D)).
Here, degenerate con-focal quadric ranges correspond to ranges of conics at infinity with the dual absolute conic Ω * ∞ as member (cf. § 4). What distinguishes (i) and (ii) is that, in the former case, the focal axes through foci concur at a finite (unique) principal focus; in the latter case, they concur at a principal foci at infinity and hence all focal axes are parallel.

We now give two examples carrying some technical details on how to determine the real points of the focal conics. Other cases are solved in very similar ways.

Example 2

We here determine the foci and focal axes of a central quadric Q (class G1). Write the envelope of Q in Euclidean canonical form as

Q * = diag(a 1 , a 2 , a 3 , -1)
The parameters of the degenerate envelopes of the confocal range determined by Q * are the generalized eigenvalues of the matrix-pair (Q * , Q * ∞ ) which can be easily computed since Q * ∞ = diag(1, 1, 1, 0). These parameters are a 1 , a 2 , a 3 and ∞ (the latter is the parameter of Q * ∞ ). Hence it is straightforward to compute, in this order, the matrices of the degenerate envelopes -other than Q * ∞ -and their (ordinary) eigenvalues:

F * 1 =        0 0 0 0 0 a 2 -a 1 0 0 0 0 a 3 -a 1 0 0 0 0 -1        ; eig(F * 1 )=        0 -1 a 3 -a 1 a2-a1        F * 2 =        a 1 -a 2 0 0 0 0 0 0 0 0 0 a3-a2 0 0 0 0 -1        ; eig(F * 2 )=        0 -1 a 3 -a 2 a1-a2        F * 3 =        a1-a3 0 0 0 0 a 2 -a 3 0 0 0 0 0 0 0 0 0 -1        ; eig(F * 3 )=        0 -1 a2-a3 a1-a3       
The F * k 's are matrices of three rank-3 dual quadrics encoding three focal conics on the principal planes of the quadric (point-equations of these focals can be easily derived). Assume Q to be general e.g., a 1 < a 2 < a 3 and a 1 a 2 a 3 = 0. The first two point-equations represent conjugate focal conics i.e., a (real) ellipse on the Y Z-plane and a (real) hyperbola on the XZ-plane respectively, while the third one represents a virtual ellipse on the XY -plane. Each tangent line to the conic on the supporting plane of the conic is the axis of a pencil of planes of F * k and thus is a focal axis of Q.

Example 3 We now determine the foci and focal axes of an elliptic paraboloid of revolution Q (R3). Write the envelope of Q in Euclidean canonical form as

Q * =     1 0 0 0 0 1 0 0 0 0 0 2/b 0 0 2/b 0     b = 0. ( 5
)
The parameters of the degenerate envelopes of the confocal range of Q * are the generalized eigenvalues of (Q * , Q * ∞ ). One gets generalized eigenvalues equal to 1 and ∞, both with multiplicity two (∞ is the parameter of Q * ∞ ). The matrix of the single 'focal' degenerate envelope (with parameter 1) is given below with its (ordinary) eigenvalues:

F * =        0 0 0 0 0 0 0 0 0 0 -1 2/b 0 0 2/b 0        ; eig(F * )= 1 2b        0 0 -b+(b 2 +16) 1/2 -b-(b 2 +16) 1/2       
As the product of the 3rd and 4th eigenvalues yields -4/b 2 , one deduces that F * is a real point-pair, say F * = fg +gf where f , g ∈ R 4 , formed by the two principal foci of the quadric. By inspecting the element F * 44 = 0 = 2f 4 g 4 , one can see that f or g -but not both-is at infinity. The line spanned by f and g is a focal line i.e., a rank-1 focal conic. Through each of f and g, there passes ∞ 2 planes (a star of planes) and hence ∞ 2 lines which are the focal axes of Q , including the line through f and g.

Along these lines, we can derive all CMSs ; they are summarized in table 1. Naturally, they subsume the generic critical motions summarized in section 3. Concretely, the classes of motions (G1), (R1) and (D) are generic critical motions, all others are artificial ones for the dual linear selfcalibration approach (see Fig. 4).

How to Detect Artificial Critical Motions

In this section, we show how one may detect and handle artificial CMSs, starting from a projective reconstruction. (G1) General virtual ellipsoids, el- lipsoids and hyperboloids of one or two sheets This is based on the notion of signature of a degenerate dual quadric D * .

(G2) (R2) (R4)
{ Q * ∞ , Q * virt , E * , H * } { (3,
Let ρ and ν be respectively the numbers of positive and negative eigenvalues of D * . The signature of D * is the pair (ξ 1 , ξ 2 ) with ξ 1 ≡ max(ρ, ν) and ξ 2 ≡ min(ρ, ν) while ξ 1 + ξ 2 = rank D * . A crucial property of signature and rank is that they are invariant to homographies [8, p74].

A projective description of a confocal range, spanned by

Q * 1 and Q * 2
, is now given by its signature sequence

{(• • • (ξ 1 1 , ξ 1 2 ) • • • ), . . . , (• • • (ξ r 1 , ξ r 2 ) • • • )} (6)
where r ∈ {1..4} and

• (ξ r 1 , ξ r 2 ) is the signature of any degenerate Q * 1 -λ r Q * 2 , where λ r is a generalized eigenvalue of (Q * 1 , Q * 2 );
• the number of brackets around a signature (cf. 2nd column of table 1) indicates the number of times that Q * 1 -λ r Q * 2 is repeated in the set of degenerate envel-opes i.e., the algebraic eigenvalue multiplicity of λ r .

The signature sequence describes the four (possibly repeated) degenerate dual quadrics of the range. It yields a projective description as it relies on signatures and multiplicities of these dual quadrics which are the same in any projective representation 4 . The signature sequences including the signatures of the false DAQs for all cases of CMSs, are given in table 1. They are at the basis of identifying and handling artificial CMSs, as described in the following.

Let us consider the solution of the linear self-calibration equations [START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF]. Of course, if there are ambiguous solutions, we are in the presence of a critical motion. Since we deal with linear equations, ambiguous solutions correspond to a linear family of dual quadrics. We assume that there is only a 1D linear family. This is the most practical common case as soon as there are n ≥ 3 critical cameras taken anywhere in the critical sequence 5 , except for (R2) in which at least one must be on the circle, cf. Fig. 4. This can be easily proved e.g., using MAPLE. We first compute the four degenerate members of that linear family, e.g. by computing the generalized eigenvalues of a pair of dual quadrics that span the family. Then, for each of these degenerate dual quadrics, we compute its signature. A first observation is that the signature sequence allows one to uniquely identify the class of CMSs (cf. 2nd column of table 1). A second observation is that all false DAQs of all artificial critical motions (classes (G2), (R2), (R3) and (R4)) have a signature that is different from that of the true DAQ, (3, 0). Hence, in the presence of an artificial CMSs, the true DAQ can be identified without ambiguity, as the single one having signature (3, 0). In conclusion, artificial CMSs can, when taking into account all self-calibration constraints after solving the linear equation system, always be disambiguated. Figure 5 shows a typical example where our algorithm resolves an artificial CMS.

Conclusions

Our theoretical results have two major consequences in practical applications. First, existing SfM implementations using dual linear self-calibration [START_REF] Pollefeys | Self-calibration and metric 3D reconstruction from uncalibrated image sequences[END_REF][START_REF] Pollefeys | Self-calibration and metric reconstruction inspite of varying and unknown intrinsic camera parameters[END_REF][START_REF] Seo | Auto-calibration by linear iteration using the DAC equation[END_REF] are known to be unstable due to degeneracies and noise. But degeneracies are intrinsically due to critical motions. Knowing the artificial CMSs will allow one to avoid them. Second, encapsulating the spectral constraints in the signature sequence, we proved that those are discriminant enough to find the true DAQ within a 1D family of potential DAQs. In other words, we stated that the spectral constraints can be safely enforced a posteriori, making it possible to avoid ambiguous self-calibration in the presence of artificial CMSs (refer Figure 5. (3D interactive graphic) We ran the dual self-calibration linear algorithm from the publicly available "Model House" image sequence (www.robots.ox.ac.uk/vgg/data). To get the projective cameras, we used Sturm-Triggs' projective factorization (see [8, p444]), followed by projective bundle adjustment. Only the first six (out of seven) frames were considered, forming a subsequence in which 94 2D points were matched all over. Regarding the selfcalibration solution given by a SVD-based algorithm (similar to A5.3 in [8, p592]), after computing the ratios of the first singular value to the last three ones, respectively equal to 5.70e + 004, 9.43e+002 and 32.83, we concluded that we were facing a critical motion, which was confirmed by visualising the 'meaningless' 3D metric reconstruction associated with the lowest singular value. Hence, the solution for the DAQ is included in a tangential pencil of quadrics α 1 Q * 1 + α 2 Q * 2 . We normalise the Q * i 's by dividing them by their largest singular values, and next assume that, regarding the signatures of the degenerate quadrics Q * 1 -λrQ * 2 where the λ r 's are the generalized eigenvalues of (Q * 1 , Q * 2 ), any value lower than 10e -3 is zero. The obtained signature sequence (with no other 'numerical trick') was {(3,0),(((1,0)))}. This indicates that all the cameras fixates a point, whose matrix is associated with the signature corresponding to (1, 0). We picked up as solution the degenerate envelope associated with (3, 0) and obtained the reconstruction of points and cameras which is displayed here, completed by reconstructions of additional pair-wise matched points.

to the interactive graphic in Fig. 5).

Figure 1 .

 1 Figure 1. The two types of focal conic-sets: (left) ellipse / hyperbola / virtual-conic triplet; (right) parabola / parabola pair. Focal conics have the remarkable general property of being conjugate (see text) and each conic completely determines the others.

Figure 2 .

 2 Figure 2. A focus and a focal axis of a quadric respectively coincide with the vertex and the revolution axis of a circular cone (i.e., having double contact with Ω∞) enveloping the quadric (see text).

  ). It describes how to obtain the focal conics of a general quadric Q. Consider the confocal range of its dual Q * , i.e. the 1D linear family of dual quadrics spanned by Q * and the DAQ Q * ∞ . This family has in general four degenerate members; these, except Q * ∞ , are exactly the envelopes of the focal conics of Q.

Figure 3 .

 3 Figure 3. Four degenerate types of focus loci (black dots), including principal foci (white dots), and assemblage of focal axes through them (arrows). The dashed style indicates virtual objects. The general case is shown in Fig. 1.

Figure 4 .

 4 Figure 4. The three classes (G2), (R2) and (R4) of artificial CMS completing the known generic CMS. The ambiguity for the DAQ is 1D if the CMS is rank-2 i.e., it includes at least three cameras with at least one on the circle for (R2).

  0), (3, 0), (2, 1), (2, 1) } L is a conjugate conic-pair formed by a general ellipse and a general hyperbola; A consists of axes tangent to these conics in their supporting planes.(G2) General elliptic and hyper- bolic paraboloids{ Q * ∞ × 2, P * 1 , P * 2 } { ((3, 0)), (2, 1), (2, 1) }L is a conjugate conic-pair formed by two general parabolas; A consists of axes tangent to these conics in their supporting planes.(R1) Prolate ellipsoids and hyper- boloids of two sheets, oblate virtual ellipsoidsQ * ∞ , C * virt , (FF + F F ) × 2 { (3, 0), (3, 0), ((1, 1)) }L is a single line; A consists of L and two stars of axes through two fixed finite points on L .(R2) oblate ellipsoids and hyper- boloids of one sheet; prolate virtual ellipsoidsQ * ∞ , C * , (F + F -+ F -F + ) × 2 { (3, 0), (2, 1), ((2, 0)) }L consists of a circle and a line which cuts orthogonally its centre; A consists of this line and the axes tangent to the circle in its supporting plane.(R3) Elliptic paraboloids of re- volutionQ * ∞ × 2, (FF ∞ + F ∞ F ) × 2 { ((3, 0)), ((1, 1)) }L is a single line; A consists of two stars of axes through two fixed points on L , one finite and the other infinite.(R4) Spheres Q * ∞ , CC × 3 { (3, 0), (((1, 0))) }L is the 3-space; A consists of a star of nonparallel axes, through a fixed finite point.(D) Degenerate confocal ranges ∞ 1 degenerate envelopes L is the 3-space; A consists of all parallel axes.

Table 1 . All types of critical motions, induced by a seven-class partition of confocal ranges w

 1 .r.t. signature sequences. Glossary: virtual degenerate envelopes are marked by 'virt' -objects at infinity are marked by '∞'. E * virt : virtual ellipse, E * : ellipse, H * : hyperbola, P * j : parabola j, C * : circle, (F, F ): (real) principal foci-pair, (F+, F-): (complex conjugate) principal foci-pair, C: single principal focus.

A (full) rank-4 or (deficient) rank-3 quadric in locus or envelope form.

Any planar section of the quadric through its axis of revolution.

A signature is projectively invariant by Sylvester's law of inertia. The multiplicity of a generalized eigenvalue also has this property.

We do not consider the class (D) here.

What is the tangent line to a dual quadric? A tangent line to a quadric locus is a line which meets the quadric at two coinciding points. Through a line there are just two planes which belong to a dual quadric; this line is a tangent line to the dual quadric if the two planes coincide.

p should be a plane of X * while q should not.

Appendix

Due to lack of space, only a sketch of the proof of proposition 1 can be given here. Before, we remind some known projective facts [START_REF] Salmon | A treatise on the analytic geometry of three dimensions[END_REF][START_REF] Semple | Algebraic projective geometry[END_REF][START_REF] Sommerville | Analytical geometry of three dimensions[END_REF] . Except for the plane at infinity π ∞ , which is real, all the planes of the DAQ Q * ∞ are complex conjugate ; hence all the tangent-lines 6 of Q * ∞ are also complex conjugate. We refer to such pairs as isotropic plane-pairs and isotropic line-pairs respectively. An important property of an isotropic plane-pair is to be invariant under rotations around its axis i.e., the intersection line of its two planes.

We also require an alternate definition of the focus of quadric, which can be found in [15, p127] and actually applies in dual 3-space for an algebraic surface of any order. 'A focus is a point through which can be drawn two lines, each touching the surface and meeting the absolute conic, and such that the tangent plane to the surface through either also touches the absolute conic. ' Now, let us reveal the complex geometry of equations [START_REF] Chandraker | Globally optimal affine and metric upgrades in stratified autocalibration[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF] by considering the algebraically equivalent pair:

with i 2 = -1. Thus, we treat a j (resp. b j ) in (2) as the real (resp. imaginary) part of a complex conjugate plane-pair. Since any camera P j , cf. (2), satisfies equations [START_REF] Hartley | Stereo from uncalibrated cameras[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF], then (i) π j ± = a j ± ib j is an isotropic plane-pair whose axis is the optical axis, (ii) the intersection of π j ± and c j , denoted π j ± c j , is an isotropic line-pair through the optical centre O j . Indeed, using ( 7), (i) holds by definition of an isotropic plane-pair. Using [START_REF] Hartley | Stereo from uncalibrated cameras[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF], (ii) also holds by definition as the intersection of two planes p and q is a tangent line of a quadric envelope X * iff both equations 7 p X * p = 0 and p X * q = 0 are satisfied [15, pp147-148].

That said the proof can be sketched: (i) A camera P j of the form (2) is critical w.r.t. X * Q * ∞ iff (ii) P j and X * satisfy [START_REF] Hartley | Stereo from uncalibrated cameras[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Using a similar reasoning as above, an equivalent condition is that (iii) the isotropic plane-pair π ± is also a plane-pair of X * and (iv) the isotropic line-pair π j ± c j is also a tangent line-pair 6 of X * . When this holds, the optical centre is a point through which there pass two isotropic lines tangent to X and such that the isotropic planes through the lines belong to X * . By the alternate definition, the optical axis is a real focal axis of X and the optical centre is a real focus on the focal axis.


Simon Gabay
email: simon.gabay@unige.ch

Ariane Pinche

Kelly Christensen

Jean-Baptiste Camps

SegmOnto -A Controlled Vocabulary to Describe and Process Digital Facsimiles

Our initiative aims at designing a controlled vocabulary for the description of the layout of textual sources: SegmOnto. Following a codicological approach rather than a semantic one, it is designed as a generic typology, coping with a maximal number of cases rather than answering specific needs. The harmonisation of the layout description has a double objective: on the one hand it facilitates the mutualisation of annotated data and therefore the training of better models for image segmentation (a crucial preliminary step for text recognition), on the other hand it allows the development of a shared post-processing workflow and pipeline for the transformation of ALTO or PAGE files into DH standard formats, which preserves as much as possible the link between the extracted information and the digital facsimile.

I INTRODUCTION

Extracting text from a digital facsimile with Optical Character or Handwritten Text Recognition (OCR/HTR) requires not one, but (at least) two tasks: first we recognise the layout, and then the text it contains. Because a textual source is usually a composition of multiple elements, containing different kinds of data (engravings, library stamps, headings, verses. . . cf. fig. 1), acquiring only the raw text is not satisfactory. The forefront of research today is to produce semi-structured data as automatically as possible, rather than unstructured data. If possible, all of a document's inscribed components as well as each one's semantic status need to be captured and evaluated during the extraction process. This evaluation serves to identify textual and visual data, to distinguish the text from the paratext, and to reorder the lines of multi-columns documents (cf. fig. 2). Semi-structured data is particularly useful for text-mining and publication purposes because it avoids introducing noise, which is detrimental to philological work on a document [START_REF] Thibault | Don't worry, it's just noise": quantifying the impact of files treated as single textual units when they are really collections[END_REF]. In order to study the title character's presence in the play (such as [START_REF] Douguet | La Composition dramatique : La liaison des scènes dans le théâtre français du XVIIe siècle[END_REF]), editorial artefacts that are not part of the text but rather of the paratext should be differenciated from the body of the text. For instance, if we look at the 1668 edition of Andromaque by Racine, because "Andromaque" is both the name of the main character and the title, many occurrences of this name come from the running title (cf. fig. 3), which produce noise and distort the results of the analysis by artificially over-representing the presence of Andromaque in the play, at least once every second page. Beside this computational problem, from an ecdotic point of view, a good edition would not need to display running titles, page numbers, which are sometimes wrong in the original, or present differently the name of the speakers (centered) than the verses (left-aligned). Similar conclusions can be drawn from documents with highly complex layouts, which are extremely frequent in the Middle Ages. Medieval manuscripts can include musical notations (cf. fig. 4) as well as commentaries and glosses (cf. fig. 5) that we need to differentiate from the main textual content. New methods are now available to classify different regions and zones, as well as different types of text lines on a page. First rule-based [START_REF] Reul | LAREX: A semi-automatic open-source tool for layout analysis and region extraction on early printed books[END_REF]] and now neural-based [START_REF] Kiessling | A modular region and text line layout analysis system[END_REF][START_REF] Thibault | You Actually Look Twice At it (YALTAi): using an object detection approach instead of region segmentation within the Kraken engine[END_REF], the efficiency of such algorithms has been increasing dramatically. Nevertheless, their application to HTR projects remains limited without a clear taxonomy for document description, particularly because every digitisation project can decide to create its own. Thus, the standardisation of practices has many interests. The following two are of special importance:

• Upstream: research teams need to share annotated documents to improve the results of HTR by increasing the amount of training data; • Downstream: Research teams also need to share post-processing means for corpus exploration and automated document production/transformation (TEI, RDF, IIIF. . . ).

Several vocabularies already exist, such as the Vocabulaire codicologique by Denis Muzerelle, now available online with other resources on the Codicologia site [START_REF] Muzerelle | Vocabulaire codicologique : répertoire méthodique des termes français relatifs aux manuscrits[END_REF]. Richly illustrated and offering translations of technical terms in several languages, including in a SKOS version [START_REF] Geoffroy | Vocabulaire Internationale de la Codicologie SKOS -GAMS: Vokabularien und Ontologien. GAMS Vokabularien und Ontologien[END_REF], the Vocabulaire codicologique is one of the main resources available. With more than 1500 different categories, this work is however not suitable for computational analysis, which notably requires a smaller number of classes to be efficient.

On the other end of the spectrum, we find the framework of PageXML [Pletschacher and [START_REF] Pletschacher | The page (page analysis and ground-truth elements) format framework[END_REF] which proposes an extremely simple typology of about ten zones that is simple to implement in a classification algorithm but does not meet the needs of philologists.1

The SegmOnto controlled vocabulary tries to balance the pros and cons of these two solutions: a simple taxonomy which is easy to implement computationally, but adapted to philological needs. stance, does it really matter if we distinguish between a title in a modern print and a rubric in a manuscript (cf. green zones in fig. 6), both of which function as a section heading? Should we differentiate a headpiece (cf. fig. 7) from a tailpiece (cf. fig. 9)? Or group them as ornamentation that does not bear any semantic connection with the text, as opposed to illustrations such as engravings (cf. fig. 8)? Or should we group all three as decorations, which are different from drop capitals (cf. fig. 10), because the latter bear text? Obviously, the answer to these questions depends on each philological project, but the existence of singular needs does not inhibit the creation of common guidelines, especially if they are conceived with enough flexibility to accommodate as many situations as possible. In the broad continuum of possibilities, we have therefore tried to design a generic rather than specific controlled vocabulary, which focuses more on the material aspects (position, shape, color. . . ) than on the precise semantic content of regions and text lines. Because it is impossible to encompass all the cases found in all written historical sources, the SegmOnto guidelines have been primarily designed for western medieval and modern documents. However, several mechanisms have however been designed to cope with problematic cases and potentially go beyond this original objective.

II THE SEGMONTO VOCABULARY

The SegmOnto syntax

The first mechanism to introduce flexibility in the annotation is the existence of a simple three-tier syntax, made of mandatory and optional parts that can be combined.

type(:subtype)?(#\d)?

The three parts are the following:

1. Types are mandatory text strings with only controlled values -the SegmOnto controlled vocabulary; 2. Subtypes are optional text strings, with only a suggested open list of possible values; 3. Numbers are optional integers.

Only types are defined precisely (cf. infra), and subtypes offer the opportunity to specify the value of the type. To annotate a GraphicZone, which is a type of region designed to annotate all the illustrations or ornamentation found in a digital facsimile, it is possible to use the following subtypes:

GraphicZone:headpiece GraphicZone:tailpiece Numbers do not specify the value of the type, but rather the succession (#1, #2, #3, #4) or alternation (#1, #2, #1, #2) of zones. Indeed, it is common that a manuscript or a print is organised with different columns, going from left to right in western documents (cf. fig. 2). We can document this organisation of the page in the following way:

MainZone#1 MainZone#2
It is possible to combine the label's three components in order to annotate different footnotes on a page with:

MarginTextZone:footnote#1 MarginTextZone:footnote#2
It is important to state that, at least for now, if MarginTextZone, MarginTextZone:footnote MarginTextZone:footnote#1, are closely related for a philologist, they are different for most current layout recognition systems, which would not recognise the last two categories as subversions of the first one. The more the annotation is precise, the more complexity it adds to the description, and therefore the more training data is required to reach a decent accuracy for the classifier.

The SegmOnto types

Types are divided into two different categories because a facsimile can be divided, as mentioned before, into regions (running title, page number, marginal notes. . . ) and lines (heading, normal line, interlinear addition or correction. . . ).

The SegmOnto regions

Fifteen different regions have been identified:

• MainZone is the main area containing the text, excluding any paratext, and it is either a single block or multiple columns. Thus, the MainZone is characterised by the importance of the text it bears, yet it does not exclude the presence of non-textual information (music notation, illumination. . . ). When a page is divided into columns or blocks, each one is a different zone. Possible values for a subtype are:

-MainZone:column -MainZone:block

• GraphicZone is a zone containing any type of graphic element, from purely ornamental information to information con-substantial to the text (e.g., full-page paintings, line-fillers, marginal drawings, figures, etc.). Drop capitals are excluded from this category. Captions, • NumberingZone is a zone containing the page, the folio, or the document number, with no regard for the mark's origin (scribe, curator, etc). The zone usually is at the top of the page. Letters/numbers denoting a folio's order within a quire are annotated differently with a special zone: QuireMarksZone. Possible values for the subtypes of the NumberingZone are:

-NumberingZone:page -NumberingZone:folio -NumberingZone:item • MarginTextZone characterises any text zone contained in the margins no matter its position on the page (upper, lower, inner or outer), including the space between two columns. We do not differentiate the zone's particular semantic status (gloss, addition, correction, intertextual or bibliographic reference, . . . ). Possible values for subtypes are:

-MarginTextZone:note -MarginTextZone:commentary -MarginTextZone:correction -MarginTextZone:variants -MarginTextZone:criticalApparatus -QuireMarksZone:signature -QuireMarksZone:catchword • RunningTitleZone is a zone containing a running title, traditionally at the top of the page or of the double page. It can be the title (or the abbreviated title) of a document or of the current section. • TitlePageZone characterises the entire page, rather than a section within a page, that contains for instance headings (chapter title, act or scene number, etc.). It is distinct from other pages and is traditionally the first page of a document, especially in the case of prints. It provides bibliographic or identifying information, such as the title of the work, the production date, the names of the printer(s), publisher(s) and author(s), etc. • TableZone is a zone containing a table of any kind. The table can be clearly drawn (with rows and columns) or not. The tables of contents are in the vast majority of cases not tables.

The SegmOnto text lines

Six different text lines have been identified:

• DefaultLine characterises any kind of standard text line, verse or prose, regardless if it is included in the MarginZone or the MainZone, though not if it is in a DropCapitalZone.

It can be used in the MusicZone for textual parts, such as the lyrics, and not the music notation; • HeadingLine is a line containing any type of heading, which is defined as a string with a distinctive typesetting (font, size, colour, capitalisation. . . ) different than that seen in the body of the text. It is not limited to the header. Rather the HeadingLine indicates the beginning of a new unit, no matter the unit's size, such as a medieval rubric, a speaker's name in a play, or the title of a poem in a collection. It is also used in the TitlePageZone.

Possible values for subtypes are:

-HeadingLine:rubric -HeadingLine:title -HeadingLine:incipit DropCapitalZone; • InterlinearLine is a line that is not a standard text line. Instead, it is a line that has been added between two of text lines, often in order to include a forgotten word or a gloss.

Possible values for subtypes are:

-InterlinearLine:addition -InterlinearLine:correction -InterlinearLine:gloss • MusicLine characterises the central line of a musical stave.

III TOWARDS TEI

ALTO and PAGE, which are standard XML formats for OCR tasks' exports, are insufficient when it comes to text mining and digital editing (cf. ex. 1). It is therefore crucial to convert files produced by any OCR/HTR engine to a standard format such as TEI [START_REF] Burnard | What is the Text Encoding Initiative? : How to add intelligent markup to digital resources[END_REF], which offers additional elements relevant to scholars working with textual sources because of the XML elements it provides for linguistic, ecdotic and literary annotation. Two TEI elements in particular are especially suited to accomplish two tasks that we should expect from an effective TEI publication. The first task is to store virtually all of the information that the OCR/HTR engine produced. It is undesirable to lose any information when converting data from an ALTO-XML into a TEI-XML file. The second task is to prepare the TEI publication as efficiently as possible for any future editing and annotation tasks. The <sourceDoc> accomplishes the first task because it can store all of the data procured by the HTR process and maintain a link between the predicted text and its place within the digitised image. The <body> accomplishes the second desired task because it presents the text in a structured hierarchy suitable for tools and procedures that are standard in digital publishing and literary analysis.

<sourceDoc>

Such a richly annotated and rigidly structured <sourceDoc> serves two important purposes. First, because it contains all the data that HTR models export into ALTO-XML files, the <sourceDoc> can be used to reconstruct an ALTO-XML file. Such reverse-engineered ALTO-XML files can become (re)training data. This means that researchers can take advantage of a document published according to the TEI and use its <sourceDoc> to fine tune new HTR models. Second, structured data in the <sourceDoc> can be converted into alternative formats such as json and RDF, or any additional export format. The use of a <sourceDoc> rather than a <facsimile> is recommended in order to "translate" ALTO files' topographic and textual information into a TEI schema (cf. tab. 1).

Basic mapping

As evidenced in tab. 1, mapping data from ALTO to TEI is not straightforward and requires some basic manipulation. For instance, both an element and its attributes are not necessarily kept together in the transformation from ALTO to TEI. In example, the ALTO element <TextLine> is mapped to the TEI element <zone>. However, the attribute @BASELINE of <TextLine> is not likewise mapped to <zone>; instead, the coordinates of a baseline are mapped to the TEI element <path>, which descends from the same <zone> to which the ALTO file's <TextLine> was mapped (cf. ex. 2). Another complication is that multiple ALTO files need to become one TEI file. OCR/HTR engines produce one XML file per page of a digital facsimile, exporting into either ALTO or PAGE format. In order to not lose the relationship between these encoded pages, it is important to group all the output files' information into a single TEI document. Thus in the <sourceDoc> all the data of one ALTO-XML file is organised within one <surface> element, repeated as many times as there are ALTO-XML files.

<TEI>

Coordinates, topographic attributes and IIIF

Certain coordinates recorded in the ALTO-XML file are not always mapped directly to a similarly topographic attribute in the TEI file. For example, in the ALTO-XML file, the elements <Page>, <TextBlock>, and <TextLine> have two sets of X,Y coordinates (@HPOS/@VPOS and @WIDTH/@HEIGHT) that outline the region that the HTR model had detected . These four attributes, however, are not mapped to four similar attributes in a TEI schema. Instead, they are used to specify a region of the source image in the URI for a IIIF Image API. This URI is the value of the attribute @source for the equivalent TEI element.

The IIIF documentation provides the following syntax to create a URI: • {scheme} is the transfer protocol, traditionally http or https;

• {server} is the host server, in other words the URL/web address, where the service is hosted, such as gallica.bnf.fr; • {prefix} is the path on the host server, usually iiif for the iiif service;

• {identifier} is the name of the image file requested, traditionally an ARK;

• {region} is created with four attributes found on the <TextBlock> and <TextLine> ALTO elements (@alto:HPOS, @alto:VPOS, @alto:WIDTH, @alto:HEIGHT) separated by commas; • {size}, {rotation}, {quality} and {format} are IIIF parameters to request the image.

In the example of a 1525 edition of the incunabulum Menus propos Mère Sotte by Pierre Gringore, which the BnF has digitised and given the ARK bpt6k15260973, the IIIF URI for a block of text on the tenth folio would therefore be the following:

Example 4: IIIF URI generated from an ALTO-XML file

The IIIF URI's region parameter is provided with data from the relevant ALTO element's attributes @HPOS, @VPOS, @WIDTH, @HEIGHT. In the example above (cf. ex. 4), having first been recognised by a HTR model, that block of text would be encoded in the following ALTO format (cf. ex. 5):

<TextBlock HPOS="194" VPOS="76" WIDTH="1368" HEIGHT="2051" ID="eSc_textblock_ca612caa" TAGREFS="BT1824"> <Shape> <Polygon POINTS="209 76 194 2127 1505 2127 1562 100"/> </Shape> Example 5: ALTO <TextBlock> of zone 1 on folio 10 of doc. bpt6k15260973

To put the IIIF URI in context, that block of text and the URI would be encoded in the following TEI format (cf. ex. 6):

Example 6: TEI <zone> of zone 1 on folio 10 of doc. bpt6k15260973

In the above example of Menus propos Mère Sotte by Pierre Gringore, the HTR model output a document whose coordinates were encoded in pixels, which is typically the case yet nevertheless always explicitly declared in an ALTO schema. Thus, the values of the ALTO attributes @HPOS, @VPOS, @WIDTH, @HEIGHT already and perfectly conform to the IIIF standards without any manipulation.

It is also possible to provide the IIIF URI of the entire page in a <graphic> element associated with a <surface>:

Example 7: TEI <zone> of zone 1 on folio 10 of doc. bpt6k15260973

Zone and Line Types

All of an ALTO-XML file's topographic and linguistic data can be mapped to a TEI schema. Consequently, by training HTR/OCR models with a SegmOnto vocabulary, that codicological system will be fully available in a TEI publication, accessible to philological, linguistic, and literary analyses as well as editorial tasks. As was suggested in Ex. 6, every <zone> in a TEI publication, whether it represents a <TextBlock> or a <TextLine>, has a @type as well as a @subtype and a @n. These attributes are parsed from the decoded name with which the HTR model tagged that region of the image. In the case of Ex. 5, the model tagged the block of text as a "MainZone," to which it assigned the alphanumeric reference code "BT1824." The TEI attributes @type, @subtype and @n take parsed portions of the tag's name. In this case, there was no subtype in the tag name "MainZone." However, when a HTR model trained on a SegmOnto vocabulary identifies a region of text as a "MainZone:column#1", for example, that <zone> in the TEI publication would have the value "MainZone" for its attribute @type the value "column" for its attribute @subtype and the value "1" for its attribute @n. The transcription is stored both in the <sourceDoc> element and the <body>. The schema used for the latter is less strict than the one used for the <sourceDoc> and allows philologists to have a pre-edited text via another mapping between ALTO and TEI (cf. tab. 2).

<body>

Whereas in the <sourceDoc> every page was completely contained within an element <sur-face>, the pre-edited text in the <body> merely interrupts a continuous stream of text with the element <pb>, meaning page beginning. This empty element carries the attribute @corresp and points to the xml:id of the corresponding page in the <sourceDoc> (cf. ex. 8).

<body> <div> <pb corresp="#page5"/> <note corresp="#page5_zone2" type="MarginTextZone"> <lb corresp="#page5_zone2_line1"/>79/4120 </note> <pb corresp="#page6"/> <ab corresp="#page6_zone1"> <hi rend="HeadingLine"> <lb corresp="#page6_zone1_line1"/>BRADAMANTE, <lb corresp="#page6_zone1_line2"/>TRAGECOMDEDIE. </hi> </ab> <pb corresp="#page9"/> <fw corresp="#page9_zone1" type="RunningTitleZone"> <lb corresp="#page9_zone1_line1"/>AV ROY. </fw> <ab corresp="#page9_zone2"> <lb corresp="#page9_zone2_line1"/>uiuront nostre siecle, les admira¬ <lb corresp="#page9_zone2_line2"/>bles effets de vos heroiques ver¬ <gap reason ="sampling"/> </ab> </div> </body> Example 8: Example of a pre-editorialised <body>: Robert Garnier, Tragédies, Paris: Robert Estienne, 1582.

IV CONCLUSIONS AND FURTHER WORK

For several years, the expression "automated editions", defined as "presentational editions generated from both digital images of text, and their corresponding transcriptions created by artificial intelligence" [START_REF] Terras | On automating editions: The affordances of handwritten text recognition platforms for scholarly editing[END_REF] has become more and more frequent. Some scholars also remark (deplore?) that "editions generated via HTR [are] not considered in the scholarly editing literature" [START_REF] Mühlberger | Could handwritten text recognition revolutionise the future of digital editions of primary sources? transkribus as a platform to facilitate the editorial workflow[END_REF], insisting on the role of the editor training and documenting the HTR model. This is not the place to engage in an umpteenth debate on the definition of the term "(scholarly) edition", but it seems to us that these debates maintain the confusion between the transcription, obviously useful, and the edition itself. Producing a good transcription is a complex, laborious act, which should not be devalued, but the "critical" part remains absent [START_REF] Duval | Pour des éditions numériques critiques. lexemple des textes français[END_REF]. In other words, paleography is not ecdotics.

If HTR cannot automatically produce "editions" but only transcriptions, segmentation cannot produce "editions" either, but contribute to speeding up the editorial work. As the pipeline for a critical edition is necessarily "semi-automatic" [START_REF] Stoekl | From htr to critical edition: A semi-automatic pipeline[END_REF], without human intervention one cannot expect more than a "pre-edition" (or a corpus). The creation of a vocabulary like SegmOnto is therefore a necessary condition, but not a sufficient one for the creation of proper scholarly editions.

Preliminary tests have already show the efficiency of a TEI encoding from ALTO via SegmOnto [START_REF] Janès | Towards automatic TEI encoding via layout analysis[END_REF]. We are now facing large scale tests, which will help refine the use of especially subtypes, whose impact of the efficiency of the region and classification is not fully understood. Mixing data from various documents from different period or genre, to increase the efficiency, also has to be evaluated, in order to create to most efficient models.

Figure 1 :

 1 Figure 1: Title page with manuscript annotation, printer's mark, bibliographic information, library stamp. . .

Figure 2 :

 2 Figure 2: Ms. BnF, fr. 25550, 14 th c. Lines are reordered (yellow circle) according to the layout in three columns.

Figure 3 :

 3 Figure 3: Racine, Andromaque, 1668. The first ANDROMAQUE is the running title, while the second is part of the play.

Figure 4 :

 4 Figure 4: Chansonnier du Roi, Ms. BnF, fr. 844, fol. 4r

Figure 5 :

 5 Figure 5: Decretum Gratiani, Sion, Archives du Chapitre, Ms. 89, fol. 3v

Figure 6 :

 6 Figure6: Similarities between the layout of a modern print (left) and a medieval manuscript (right). The running title is in orange, the pagination/foliation in red, headings/rubrics in green, drop capitals in pink, main textual zones in blue and marginal notes in grey.

Figure

  Figure 7: Headpiece Figure 8: Engraving

Figure

  Figure 9: Tailpiece Figure 10: Drop capital

  if there are any, is part of this zone, and its text line is labelled HeadingLine. If an image contains text, it is possible to label the lines as DefaultLine. Possible values for subtypes are: -GraphicZone:illustration, cf. fig. 8. -GraphicZone:ornamentation, cf. fig. 11, 12, fig. 7, fig. 9. -GraphicZone:figure, cf. fig. 11 et 12.

Figure 11 :

 11 Figure 11: GraphicZone:figure Figure 12: GraphicZone:figure

Figure 13 :

 13 Figure 13: DropCapitalZone:flourished Figure 14: DropCapitalZone

Figure 15 :

 15 Figure 15: Double numbering: item (left) and folio (right).

Figure 16 :

 16 Figure 16: MainZone:addition Figure 17: MainZone:commentary

Figure 18 :

 18 Figure 18: QuireMarksZone:catchword Figure 19: Signature and catchword.

Figure 20 :

 20 Figure 20: RunningTitle

Figure 21 :

 21 Figure 21: StampZone:post Figure 22: StampZone:library

Figure 23 :

 23 Figure 23: DamageZone:hole Figure 24: DamageZone:soaked

Figure 27 :

 27 Figure 27: Sections in prose and in verse Figure 28: Several poems

Figure

  Figure 29: TableZone

Figure 30 :

 30 Figure 30: TableZone

Figure 31 :

 31 Figure 31: MusicZone:neume Figure 32: MusicZone:stave

Figure 33 :

 33 Figure 33: HeadingLine:rubric Figure 34: HeadingLine

Figure 35 :

 35 Figure 35: InterlinearLine:correction

  Basic structure of the sourceDoc.

  {scheme}://{server}/{prefix}/{identifier}/ {region},{size},{rotation},{quality},{format} Example 3: Creating a IIIF URI for a IIIF Image API where: Journal of Data Mining and Digital Humanities

Table 1 :

 1 Basic mapping between ALTO and TEI encodings (expressed in xPath).

	ALTO	TEI
	//Page	sourceDoc/surface
	//TextBlock	sourceDoc/surface/zone
	//TextBlock[@TAGREFS]	sourceDoc/surface/zone[@type]
	//TextBlock/Polygon[@POINTS]	sourceDoc/surface/zone/[@points]
	//TextLine	sourceDoc/surface/zone/zone
	//TextLine[@BASELINE]	sourceDoc/zone/zone/path[@points]
	//TextLine/Shape/Polygon[@POINTS]	sourceDoc/zone/zone[@points]
	//TextLine/String[text()]	sourceDoc/zone/zone/line[text()]

Table 2 :

 2 SegmOnto regions and their corresponding TEI element.

	Segmonto zone	Corresponding TEI element
	CustomZone	<div>
	DamageZone	<damage>
	DigitizationArtefactZone <figure type="DigitizationArtefactZone">
	DropCapitalZone	<hi type="DropCapitalZone">
	GraphicZone	<figure type="GraphicZone">
	MainZone	<ab>
	MarginTextZone	<note type="MarginTextZone">
	MusicZone	<musicNotation>
	NumberingZone	<fw type="pageNumber">
	QuireMarksZone	<fw type="QuireMarksZone">
	RunningTitleZone	<fw type="RunningTitleZone">
	SealZone	<figure type="SealZone">
	StampZone	<figure type="StampZone">
	TableZone	<table>
	TitlePageZone	<div>

Journal of Data Mining and Digital Humanities

http://jdmdh.episciences.org

ACKNOWLEDGEMENTS

We would like to thank previous interns for their precious work (Juliette Janès and Claire Jahan), the BNF Datalab for the funding, and our colleagues of the Gallic(orpor)a project at the INRIA Paris (Benoît Sagot, Rachel Bawden, Pedro Ortiz Suarez) and the université Gustave Eiffel (Philippe Gambette). Daniel Stökl Ben Ezra and Peter Stokes participated in the first working discussions.

DATA

Full documentation, with more examples for each of the types, is available and maintained online: https://segmonto.github.io. It is preferable to refer to the site rather than to this article in the event of modification of the guidelines.