Jean Ponce

Martial Hebert

Trinocular Geometry Revisited

When do the visual rays associated with triplets of point correspondences converge, that is, intersect in a common point? Classical models of trinocular geometry based on the fundamental matrices and trifocal tensor associated with the corresponding cameras only provide partial answers to this fundamental question, in large part because of underlying, but seldom explicit, general configuration assumptions. This paper uses elementary tools from projective line geometry to provide necessary and sufficient geometric and analytical conditions for convergence in terms of transversals to triplets of visual rays, without any such assumptions. In turn, this yields a novel and simple minimal parameterization of trinocular geometry for cameras with non-collinear or collinear pinholes.

Introduction

The images of points recorded by multiple cameras may only match when the corresponding visual rays convergethat is, intersect in a common point (Figure 1, left). For two views, this condition is captured by the bilinear epipolar constraint and the corresponding fundamental matrix [8,[START_REF] Luong | The fundamental matrix: theory, algorithms, and stability analysis[END_REF]. Three images can be characterized by both the pairwise epipolar constraints associated with any two of the pictures, and a set of trilinearities associated with all three views and parameterized by the associated trifocal tensor [START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Shashua | Algebraic functions for recognition[END_REF]16,[START_REF] Weng | Motion and structure from line correspondences: closed-form solution, uniqueness, and optimization[END_REF]. For cameras with non-collinear pinholes, at least, the rays associated with three image points that satisfy the corresponding epipolar constraints almost always converge: The only exception is when the points have been matched incorrectly, and all lie in the trifocal plane spanned by the three pinholes (Figure 1, right). Interestingly, Hartley and Zisserman state that the fundamental matrices associated with three cameras with non-collinear pinholes determine the corresponding trifocal tensor [6, Result 14.5], while Faugeras and Mourrain [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF] and Ponce et al. [START_REF] Ponce | The absolute quadratic complex and its application to camera self calibration[END_REF], for example, note that the rays associated with three points only satisfying certain (and different) subsets of the trilinearities alone must intersect. These claims contradict * Willow project team. DI/ENS, ENS/CNRS/INRIA UMR 8548. each other, since rays that satisfy epipolar constraints do not always converge, but they are true under some general configuration assumptions, rarely made explicit. It is thus worth clarifying these assumptions, and understanding exactly how much the trifocal constraints add to the epipolar ones for point correspondences. This is the problem addressed in this paper, using elementary projective line geometry. In particular, our analysis shows that exploiting both the epipolar constraints and one or two of the trinocular ones, depending on whether the camera pinholes are collinear or not, always guarantees the convergence of the corresponding visual rays. Our analysis also provides, in both cases, a novel and simple minimal parameterization of trinocular geometry.

Related Work

Geometric constraints involving multiple perspective views of the same point (Figure 1, left) have been studied in computer vision since the seminal work of Longuet-Higgins, who proposed in 1981 the essential matrix as a bilinear model of epipolar constraints between two calibrated cameras [8]. Its uncalibrated counterpart, the fundamental matrix, was introduced by Luong and Faugeras [START_REF] Luong | The fundamental matrix: theory, algorithms, and stability analysis[END_REF]. The trilinear constraints associated with three views of a straight line were discovered by Spetsakis and Aloimonos [16] and by Weng, Huang and Ahuja [START_REF] Weng | Motion and structure from line correspondences: closed-form solution, uniqueness, and optimization[END_REF]. The uncalibrated case was tackled by Shashua [START_REF] Shashua | Algebraic functions for recognition[END_REF] and by Hartley [START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF], who coined the term trifocal tensor. The quadrifocal tensor was introduced by Triggs [START_REF] Triggs | Matching constraints and the joint image[END_REF], and Faugeras and Mourrain gave a sim- ple characterization of all multilinear constraints associated with multiple perspective images of a point [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF]. The usual formulation of the trilinear constraints associated with three images of the same point are asymmetric, one of the images playing a priviledged role. A simple and symmetric formulation based on line geometry was introduced in [START_REF] Ponce | The absolute quadratic complex and its application to camera self calibration[END_REF]. A few minimal parameterizations of trinocular geometry are also available [START_REF] Canterakis | A minimal set of constraints for the trifocal tensor[END_REF][START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF][START_REF] Ressl | A minimal set of constraints and a minimal parameterization for the trifocal tensor[END_REF][START_REF] Torr | Robust parameterization and computation of the trifocal tensor[END_REF]. From a historical point of view, it is worth noting that epipolar constraints were already known by photogrammeters long before they were (re)discovered by Longuet-Higgins [8], as witnessed by the 1966 Manual of Photogrammetry [17], but that this book does not mention trilinear constraints, although it discusses higher-order trinocular (scale-restraint condition equations).

(2) (1) (3) (4)
The direct derivation of trifocal constraints for point correspondences typically amounts to writing that all 4 × 4 minors of some k × 4 matrix are zero, thus guaranteeing that the three lines intersect [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF][START_REF] Ponce | The absolute quadratic complex and its application to camera self calibration[END_REF]. These determinants are then rewritten as linear combinations of reduced minors that are bilinear or trilinear functions of the image point coordinates. The whole difficulty lies in selecting an appropriate subset of reduced minors that will always guarantee that the rays intersect. We have already observed that the bilinear epipolar constraints, alone, are not sufficient. We are not aware of any fixed set of four trilinearities that, alone, guarantee convergence in all cases. This suggests seeking instead appropriate combinations of bilinear and trilinear constraints, which is the approach taken in this presentation.

Problem Statement and Proposed Approach

As noted earlier, the goal of this paper is to understand exactly how much the trifocal constraints add to the epipolar ones for point correspondences. Since both types of constraints model incidence relationships among the light rays joining the cameras' pinholes to observed points, we address this problem using the tools of projective geometry [START_REF] Veblen | Projective Geometry[END_REF] in general, and line geometry [START_REF] Pottmann | Computational Line Geometry[END_REF] in particular. As noted earlier, the trifocal tensor was originally invented to characterize the fact that three image lines δ 1 , δ 2 , and δ 3 are the projections of the same scene line δ [START_REF] Shashua | Algebraic functions for recognition[END_REF]16,[START_REF] Weng | Motion and structure from line correspondences: closed-form solution, uniqueness, and optimization[END_REF] (Figure 1, left). The trilinearities associated with three image points y 1 , y 2 , and y 3 were then obtained by constructing lines δ 1 , δ 2 , and δ 3 passing through these points, and whose preimage is a line δ passing through the corresponding scene point x. By construction, this line is a transversal to the three rays ξ 1 , ξ 2 , and ξ 3 , that is, it intersects them. It is therefore not surprising that much of the presentation will be dedicated to the characterization of the set of transversals to a triplet of lines.

In particular, we have already seen that the fact that three lines intersect pairwise is necessary, but not sufficient for these lines to intersect. We will show in the rest of this presentation that a necessary and sufficient condition for three lines to converge is in fact that they be pairwise coplanar and admit a well defined family of transversals. We will also give a simple geometric and analytical characterization of these transversals under various assumptions. When applied to camera systems, it will provide in turn a new and simple minimal parameterization of trinocular geometry. Contributions • We give a new geometric characterization of triplets of converging lines in terms of transversals to these lines (Proposition 1).

• We provide a novel and simple analytical characterization of triplets of converging lines (Lemma 3 and Proposition 2), that does not rely on the assumptions of general configuration implicit in [START_REF] Ponce | The absolute quadratic complex and its application to camera self calibration[END_REF].

• We show by applying these results to camera geometry that the three epipolar constraints and one of the trifocal ones (two if the pinholes are collinear) are necessary and sufficient for the corresponding optical rays to converge (Propositions 3 and 4).

• We introduce a new analytical parameterization of epipolar and trifocal constraints, leading to a minimal parameterization of trinocular geometry (Propositions 5 and 6).

Converging Triplets of Lines

Geometric Point of View

All lines considered from now on are assumed to be different from each other. A transversal to some family of lines is a line intersecting every element of this family. We (4) [START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF] (6)

Figure 3. Top: The possible configurations of three distinct, nonpairwise-coplanar lines, classified according to the way they intersect. Bottom: Transversals to the three lines, forming (4) two pencils of lines having one of the input lines (in black) in common (5) two pencils of lines having one line (in red) in common; and (6) a non-degenerate regulus. See text for details.

prove in this section the following main result.

Proposition 1. A necessary and sufficient condition for three lines to converge is that they be pairwise coplanar, and that they admit a transversal not contained in the planes defined by any two of them.

To prove Proposition 1, we need two intermediate results. In projective geometry, two straight lines are either skew to each other or coplanar, in which case they intersect in exactly one point. Our first lemma enumerates the possible incidence relationships among three lines.

Lemma 1. Three distinct lines can be found in exactly six configurations (Figures 2 and 3, top): (1) the three lines are not all coplanar and intersect in exactly one point; (2) they are coplanar and intersect in exactly one point; (3) they are coplanar and intersect pairwise in three different points; (4) exactly two pairs of them are coplanar (or, equivalently, intersect); (5) exactly two of them are coplanar; or (6) they are pairwise skew.

The proof is by enumeration. Lemma 1 has an immediate, important corrolary-that is, when three lines are pairwise coplanar, either they are not coplanar and intersect in one point (case 1); they are coplanar and intersect in one point (case 2); or they are coplanar, and intersect pairwise in three different points (case 3). In particular, epipolar constraints are satisfied for triplets of (incorrect) correspondences associated with images of points in the trifocal plane containing the pinholes of three non-collinear cameras.

To go further, it is useful to introduce a notion of linear (in)dependence among lines. The geometric definition of independence of lines matches the usual algebraic definition of linear independence, in which, given a coordinate system, a necessary and sufficient for k lines to be linearly dependent is that some nontrivial linear combination of their Plücker coordinate vectors (Section 2.2.1) be the zero vector of R 6 . Geometrically, the lines linearly dependent on three skew lines form a regulus [START_REF] Veblen | Projective Geometry[END_REF]. A regulus is either a line field, formed by all lines in a plane; a line bundle, formed by all lines passing through some point; the union of all lines belonging to two flat pencils lying in different planes but sharing one line; or a non-degenerate regulus formed by one of the two sets of lines ruling a hyperboloid of one sheet or a hyperbolic paraboloid. Linear (in)dependence of four or more lines can be defined recursively. Armed with these definitions, we obtain an important corollary of Lemma 1.

Lemma 2. Three distinct lines always admit an infinity of transversals, that can be found in exactly six configurations (Figures 2 and 3, bottom): (1) the transversals form a bundle of lines; (2) they form a degenerate congruence consisting of a line field and of a bundle of lines; (3) they form a line field; (4) they form two pencils of lines having one of the input lines in common; (5) they form two pencils of lines having a line passing through the intersection of two of the input lines in common; or (6) they form a non-degenerate regulus, with the three input lines in the same ruling, and the transversals in the other one.

Lemma 2 should not come as a surprise since the transversals to three given lines satisfy three linear constraints and thus form in general a rank-3 family (the degenerate congruence is a rank-4 exception [START_REF] Veblen | Projective Geometry[END_REF]). Without additional assumptions, not much more can be said in general, since Lemma 2 tells us that any three distinct lines admit an infinity of transversals. When the lines are, in addition, pairwise coplanar, cases 4 to 6 in Lemmma 2 are eliminated, and we obtain Proposition 1 as an immediate corollary of this lemma.

The Analytical Point of View 2.2.1 Preliminaries

To translate the geometric results of the previous section into analytical ones, it is necessary to recall a few basic facts about projective geometry in general, and line geometry in particular. Readers familiar with Plücker coordinates, the join operator, etc., may safely proceed to Section 2.2.2. Given some choice of coordinate system for some twodimensional projective space P 2 , points and lines in P 2 can be identified with their homogeneous coordinate vectors in R 3 . In addition, if x and y are two distinct points on a line ξ in P 2 , we have ξ = x × y. A necessary and sufficient condition for a point x to lie on a line ξ is ξ • x = 0, and two lines intersect in exactly one point or coincide. A nec-essary and sufficient conditions for three lines to intersect is that they be linearly dependent, or Det(ξ 1 , ξ 2 , ξ 3 ) = 0.

In three dimensions, given any choice of coordinate system for a three-dimensional projective space P 3 , we can identify any line in P 3 with its Plücker coordinate vector ξ = (u; v) in R 6 , where u and v are vectors of R 3 , and we use a semicolon to indicate that the coordinates of u and v have been stacked onto each other to form a vector in R 6 . In addition, if x and y are two distinct points on some line ξ = (u; v) in P 3 , we have

u = x4y1 -x1y4 x4y2 -x2y4 x4y3 -x3y4 , and v = x2y3 -x3y2 x3y1 -x1y3 x1y2 -x2y1 . (1)
A Plücker coordinate vector is only defined up to scale, and its u and v components are by construction orthoganal to each other-this is sometimes known as the Klein con-

straint u • v = 0. Let us consider the symmetric bilinear form R 6 × R 6 → R associating with two elements λ = (a; b) and µ = (c; d) of R 6 the scalar (λ|µ) = a • d + b • c.
A necessary and sufficient for a nonzero vector ξ in R 6 to represent a line is that (ξ|ξ) = 0, and a necessary and sufficient condition for two lines λ and µ to be coplanar (or, equivalently, to intersect) is that (λ|µ) = 0.

Let us denote the basis points of some arbitrary projective coordinate system by x 0 to x 4 , with coordinates x 0 = (0, 0, 0, 1) T , x 1 = (1, 0, 0, 0) T , x 2 = (0, 1, 0, 0) T , x 3 = (0, 0, 1, 0) T , and x 4 = (1, 1, 1, 1) T . Points x 0 to x 3 are called the fundamental points. The point x 4 is the unit point. Let us also define four fundamental planes p j (j = 0, 1, 2, 3) whose coordinate vectors are the same as those of the fundamental points. The unique line joining two distinct points is called the join of these points and it is denoted by x ∨ y. Likewise, the unique plane defined by a line ξ = (u; v) and some point x not lying on this line is called the join of ξ and x, and it is denoted by ξ ∨ x. Algebraically, we have ξ ∨ x = [ξ ∨ ]x, where [ξ ∨ ] is the join matrix defined by

[ξ ∨ ] = [u×] v -v T 0 . (2)
A necessary and sufficient condition for a point x to lie on a line ξ is that ξ ∨ x = 0.

Back to Transversals

Let us translate some of the geometric incidence constraints derived in the previous section into algebraic ones. We assume that some projective coordinate system is given, and identify points, planes, and lines with their homogeneous coordinate vectors. Let us consider three distinct lines ξ j = (ξ 1j , . . . , ξ 6j ) T (j = 1, 2, 3) and define

D ijk = ξi1 ξi2 ξi3 ξj1 ξj2 ξj3 ξ k1 ξ k2 ξ k3 (3)
to be the 3 × 3 minor of the 6 × 3 matrix [ξ 1 , ξ 2 , ξ 3 ] corresponding to its rows i, j, and k. A necessary and sufficient condition for this matrix to have rank 2, and thus for the three lines to form a flat pencil (Section 2.1), is that all the minors T 0 = D 456 , T 1 = D 234 , T 2 = D 315 , and T 3 = D 126 be equal to zero.

Lemma 3. Given some integer j in {0, 1, 2, 3}, a necessary and sufficient condition for ξ 1 , ξ 2 , and ξ 3 to admit a transversal passing through x j is that T j = 0.

Proof. Let us prove the result in the case j = 0. The proofs for the other cases are similarA necessary and sufficient condition for a line δ = (u; v) to pass through x 0 is that v = 0 (this follows from the form of the join matrix). Thus a necessary and sufficient condition for the existence of a line δ passing through x 0 and intersecting the lines ξ j = (u j ; v j ) is that there exists a vector u = 0 such that

(ξ j |δ) = v j • u = 0 for j = 1, 2, 3, or, equivalently, that the determinant T 0 = D 456 = |v 1 , v 2 , v 3 | be zero.
Combining Proposition 2 and Lemma 3 now yields the following important result. Proposition 2. A necessary and sufficient condition for three lines ξ 1 , ξ 2 , and ξ 3 to converge is that (ξ i |ξ j ) = 0 for all i = j in {1, 2, 3}, and that T j = 0 for all j in {0, 1, 2, 3}.

Proof. The condition is clearly necessary. To show that is is sufficient, note that since the three lines are pairwise coplanar, they either intersect in exactly one point (cases 1 and 2 of Lemma 2), or are all coplanar, intersecting pairwise in three distinct points, with all their transversals in the same plane (case 3). But the latter case is ruled out by Lemma 3 and the condition T j = 0 for j = 0, 1, 2, 3 since the fundamental points x j are by construction not all coplanar, and at least one of them (and thus the corresponding transversal) does not lie in the plane containing the three lines.

Converging Triplets of Visual Rays

Bilinearities or Trilinearities?

Let us now turn our attention from general systems of lines to the visual rays associated with three cameras. As noted earlier, it follows from Lemma 1 that the epipolar constraints alone do not ensure that the corresponding viewing rays intersect (Figure 1, right). On the other hand, the only case where they do not is when the corresponding rays lie in the trifocal plane when the camera pinholes are not collinear, or in any plane containting the line joining the three pinholes when they are (Figure 4).

Contrary to the claim of [START_REF] Ponce | The absolute quadratic complex and its application to camera self calibration[END_REF]Appendix], the trilinear conditions T j = 0 (j = 0, 1, 2, 3) associated with three visual rays do not guarantee, on their own, that the rays intersect: In fact, one can in general construct a two-dimensional family of triplets of non-intersecting visual rays passing through three given non-collinear pinholes and satisfying these constraints. Likewise, although one can show that some set of trilinearities can always be chosen to ensure the convergence of the corresponding visual rays, we are not aware of any fixed set of trilinearities with the same guarantees, which in turns appears to contradict [3, Sec. 4.2.2] (also the discussion in [7]). This apparent contradiction stems from the fact that both Faugeras and Mourrain [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF] and Ponce et al. [START_REF] Ponce | The absolute quadratic complex and its application to camera self calibration[END_REF] characterize the convergence of visual rays by the vanishing of certain trilinear reduced minors of a k × 4 matrix, and have to (implicitly at times) resort to general configuration assumptions to select a representative set of minors. Characterizing the convergence of triplets of lines directly in terms of both binocular and trinocular constraints, as in Proposition 2, avoids this difficulty.

Bilinearities and Trilinearities

By definition, for any choice of projective coordinate system, the four fundamental points x j (j = 0, 1, 2, 3) are not coplanar. When the three pinholes are not collinear, it is thus always possible to choose a projective coordinate system such that one of the fundamental points, say x 0 , does not lie in the trifocal plane, and we obtain the following immediate corollary of Proposition 2. Proposition 3. Gven three cameras with non-collinear pinholes c 1 , c 2 , and c 3 , and any projective coordinate system such that x 0 does not belong to the trifocal plane, a necessary and sufficient for the three rays ξ j = c j ∨ y j (j = 1, 2, 3) to converge is that is that (ξ i |ξ j ) = 0 for all i = j in {1, 2, 3}, and T 0 = 0. tinct), the three cameras admit a single pencil of epipolar planes, and three rays in epipolar correspondence are in fact always coplanar (Figure 4). The trifocal constraints are necessary in this case to ensure that the three lines intersect in exactly one point. Note that, given three cameras with collinear pinholes, one can always choose a projective coordinate system such that the two fundamental points x 0 and x j (for any j in {1, 2, 3}) and the baseline joining the three pinholes are not coplanar. The following result characterizes the fact that visual rays intersect in this setting. Proposition 4. Given three cameras with collinear pinholes c 1 , c 2 , and c 3 , and any projective coordinate system such that the fundamental points x 0 and x 1 and the baseline β joining the pinholes are not coplanar, a necessary and sufficient condition for the three rays ξ j = c j ∨ y j (j = 1, 2, 3) to intersect is that is that (ξ i |ξ j ) = 0 for all i = j in {1, 2, 3}, and T 0 = T j = 0 for some j = 0.

When the three pinholes are collinear (but of course dis-

Proof. The condition is clearly necessary. Because of the epipolar constraints, the three rays must be coplanar, and either intersect in three distinct points with all their transversals in the same plane, intersect in a single point, or coincide with the baseline. Unless the point x 0 lies in the plane π 0 that contains the rays (Figure 5), the first case is ruled out by the condition T 0 = 0. If x 0 lies in π 0 , x j does not (by construction), and the first case is ruled out by T j = 0.

Minimal Parameterizations

Non-Collinear Pinholes

We assume in this section that the three pinholes are not aligned. In this case, we can always choose a projective coordinate system such that the three fundamental points distinct from x 0 are the three camera centers-that is, c j = x j for j = 1, 2, 3, and x 0 does not lie in the trifocal plane.

With our choice of coordinate system, and the notation y j = (y 1j , y 2j , y 3j , y 4j ) T , the three epipolar constraints can be written as Given these constraints, we know from Proposition 2 that a necessary and sufficient conditions for the three visual rays to intersect is that T 0 = 0 (the other three trilinearities are trivially satisfied with our choice of coordinate system), which is easily rewritten in our case as y 21 y 32 y 13 = y 31 y 12 y 23 .

(x 1 ∨ y 1 |x 2 ∨ y 2 ) = 0 (x 1 ∨ y 1 |x 3 ∨ y 3 ) = 0 (x 2 ∨ y 2 |x 3 ∨ y 3 ) = 0
(

) 5
Note that y 4j = 0 if and only if y j lies in p 0 , which is also the trifocal plane in our case. As expected, it follows immediately from Eqs. ( 4) and ( 5) that, unless y 41 = y 42 = y 43 = 0, that is, the observed point lies in the trifocal plane, the epipolar constraints imply the trifocal ones. We now need to translate Eqs. (4-5) to the corresponding equations in image coordinates. Let us denote by Π j (j = 1, 2, 3) the 4 × 3 matrix formed by the coordinate vectors of the basis points for the retinal plane of camera number j. The position of an image point with coordinate vector u j in that basis is thus y j = Π j u j . Let us denote by π T ij the ith row of the matrix Π j , and use superscripts to index coordinates, i.e., for k = 1, 2, 3, π k ij denotes the kth coordinate of π ij .

Proposition 5. Given three cameras with non-collinear pinholes and hypothetical point correspondences u 1 , u 2 , and u 3 , a necessary and sufficient condition for the three corresponding rays to converge is that

u T 1 F 12 u 2 = 0 u T 1 F 13 u 3 = 0 u T 2 F 23 u 3 = 0
where

F 12 = π 41 π T 32 -π 31 π T 42 F 13 = π 41 π T 23 -π 21 π T 43 F 23 = π 42 π T 13 -π 12 π T

43

, and

(6) (π 21 •u 1 )(π 32 •u 2 )(π 13 •u 3 ) = (π 31 •u 1 )(π 12 •u 2 )(π 23 •u 3 ), (7
) where the vectors π 1 = (π 21 ; π 31 ; π 41 ), π 2 = (π 12 ; π 32 ; π 42 ), and π 3 = (π 13 ; π 23 ; π 43 ), satisfy the 6 homogeneous constraints

π 1 21 = 0, π 2 31 = π 3 41 , π 2 32 = 0, π 3 12 = π 1 42 , π 3 13 = 0, π 1 23 = π 2 43 , (8)
and are thus defined by three groups of 7 coefficients, each one uniquely determined up to a separate scale. This is a minimal, 18dof parameterization of trinocular geometry.

Proof. Equations ( 6) and (7) are obtained immediately by substitution in Eqs. ( 4) and ( 5). Together, they provide a 24dof parameterization of the trifocal geometry by the three vectors π j = (π 1j ; π 2j ; π 3j ) (j = 1, 2, 3), each defined up to scale in R 9 by 8 independent parameters. Locating the camera pinholes at the fundamental points x j (j = 1, 2, 3) freezes 9 of the 15 degrees of freedom of the projective ambiguity of projective structure from motion. It is possible to exploit the remaining 6 degrees of freedom, and to impose the constraints of Eq. ( 8) on the vectors π j . Indeed, the general form of a projective transform Q mapping the three fundamental points x j onto themselves has 7 coefficients defined up to scale. Applying such a transform to the matrices Π j (j = 1, 2, 3) defined in some arbitrary projective coordinate system, and writing that the matrices QΠ j must satisfy the constraints of Eq. (8) yields a system of 6 homogeneous equations in the 7 nonzero entries of Q. Note that we can generate many different sets of homogeneous constraints by choosing different sets of entries of the vectors π 1 , π 2 , and π 3 . It can be shown that there is always some choice for which the system defining Q admits a unique solution defined up to scale, and that this solution is nonsingular, thus defining a valid change of coordinates. Together, Eqs. ( 6), ( 7) and (8) provide us with a minimal, 18dof parameterization of the trinocular geometry by the three vectors π 1 , π 2 and π 3 now each defined up to scale in R 9 by only 6 independent parameters.

To the best of our knowledge, the minimal parameterization of trinocular geometry proposed by Papadopoulo and Faugeras [START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF] is the only other one known so far to be oneto-one and parametric (other minimal ones, e.g., [START_REF] Canterakis | A minimal set of constraints for the trifocal tensor[END_REF][START_REF] Torr | Robust parameterization and computation of the trifocal tensor[END_REF], impose algebraic constraints). Contrary to [START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF], our parameterization does not require the use of a computer algebra system to impose rank constraints (see [START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF] for details). In addition, our parameterization is symmetric, none of the cameras playing a priviledged role.

Let us close this section by noting that Eq. ( 7) has an interesting geometric interpretation: Any point with coordinate vector u 1 in the first image that matches points with coordinate vectors u 2 and u 3 in the other two, must satisfy (7) and thus belong to the "trinocular line" (our terminology):

τ 1 = [(π 32 •u 2 )(π 13 •u 3 )]π 21 -[(π 12 •u 2 )(π 23 •u 3 )]π 31 .
(9) This should not come as a surprise since classical trifocal geometry is defined in terms of line correspondences, and Eq. ( 7) merely expresses the fact that the image point y 1 lies on the projection τ 1 of the line τ 0 passing through x 0 that intersects the rays passing through the other two image points, y 2 and y 3 . What is less well known is that the lines τ 1 belong to the pencil generated by the lines π 21 and π 31 , which intersect at the point z 1 = π 21 × π 31 of the first image. The same reasoning applies to the other two images.

Collinear Pinholes

Let us now assume that the three pinholes are collinear (as noted in [START_REF]Manual of Photogrammetry[END_REF], this case may be important in practice, in aerial photography for example). Let us position the two pinholes c 1 , c 2 in x 1 and x 2 , and the third pinhole, c 3 , in x 1 + x 2 . We are free to do this since this amounts to choosing c 1 and c 2 as the fundamental points of the baseline joining the three pinholes, and c 3 as its unit point. From Eq. ( 4

The other two minors T 1 and T 2 are zero with our choice of coordinate system. We can rewrite as before Eqs. ( 10) and [START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF] in terms of the rows of the matrices Π j (j = 1, 2, 3). Given the special role of y 23y 13 in Eq. ( 11), it is convenient to introduce the vector ω 3 = π 23π 13 , and we obtain the following characterization of the trinocular geometry. Proposition 6. Given three cameras with collinear pinholes and hypothetical point correspondences u 1 , u 2 , and u 3 , a necessary and sufficient condition for the three corresponding rays to converge is that

u T 1 F 12 u 2 = 0 u T 1 F 13 u 3 = 0 u T 2 F 23 u 3 = 0
where

F 12 = π 41 π T 32 -π 31 π T 42 F 13 = π 41 π T 33 -π 31 π T 43 F 23 = π 42 π T 33 -π 32 π T 43 , ( 12
) 0 = (π 31 • u 1 )(π 32 • u 2 )(ω 3 • u 3 )+ (π 33 • u 3 )[(π 31 • u 1 )(π 12 • u 2 ) -(π 21 • u 1 )(π 32 • u 2 )], 0 = (π 41 • u 1 )(π 42 • u 2 )(ω 3 • u 3 )+ (π 43 • u 3 )[(π 41 • u 1 )(π • u 2 ) -(π 21 • u 1 )(π 42 • u 2 )], (13
) where the vectors π 1 = (π 21 ; π 31 ; π 41 ), π 2 = (π 12 ; π 32 ; π 42 ) and π 3 = (ω 3 ; π 33 ; π 43 ) satisfy the 8 homogeneous constraints

π 1 21 = 0, π 2 31 = 0, π 1 12 = 0, π 2 42 = 0, π 3 31 = π 3 21 , π 3 32 = π 3 42 , ω 1 3 = ω 2 3 = ω 3 3 , (14)
and are thus defined by three groups of, respectively, 6, 6, and 7 independent coefficients, each uniquely determined up to a separate scale, for a total of 16 independent parameters. This is a minimal, 16dof trinocular parameterization.

Proof. Equations ( 12) and ( 13) are obtained immediately by substitution in Eqs. [START_REF]Manual of Photogrammetry[END_REF] and [START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF]. Together they provide a 24dof parameterization of the trifocal geometry by the three vectors π j (j = 1, 2, 3), each defined up to scale in R 9 by 8 independent parameters. Locating the camera pinholes in x 1 , x 2 , and x 1 + x 2 freezes 7 of the 15 degrees of freedom of the projective ambiguity of projective structure from motion. Similar to the proof of Proposition 5, the remaining 8 degrees of freedom can be used to impose the constraints of Eq. ( 14) on the vectors π j . Together, Eqs. ( 12), ( 13) and ( 14) provide us with a minimal, 16dof parameterization of the trinocular geometry by the three vectors π 1 , π 2 and π 3 now each defined up to scale in R 9 by only 5, 5, and 6 independent parameters.

Preliminary Implementation

Proposition 5 can be used to estimate the vectors π j associated with three cameras with non-collinear pinholes from at least six correspondences between three images: Initial values for these vectors are easily obtained from the corresponding projection matrices, estimated from six triplets of matching points using an affine or projective model [START_REF] Carlsson | Duality of reconstruction and positioning in multiple views[END_REF][START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF]. The vectors π j are then refined by minimizing the mean-squared distance between all data points and the corresponding epipolar and trinocular lines. We have constructed a preliminary implementation of this method, and Figure 6 shows an example with 38 correspondences between three images, and the corresponding epipolar and trinocular lines (data courtesy of B. Boufama and R. Mohr). Table 1 shows the average distances between the data points and these lines. The mean distance to epipolar lines is on the order of 1pixel, and comparable to that obtained by classical techniques for estimating the fundamental matrix from pairs of images on the same data [START_REF] Forsyth | Computer Vision: A Modern Approach[END_REF]Ch. 8]. Our method, on the other hand, is by construction robust to degeneracies with points lying near the trifocal plane. Further experiments and comparisons with other minimal parameterizations of the trinocular geometry [START_REF] Canterakis | A minimal set of constraints for the trifocal tensor[END_REF][START_REF] Papadopoulo | A new characterization of the trifocal tensor[END_REF][START_REF] Ressl | A minimal set of constraints and a minimal parameterization for the trifocal tensor[END_REF][START_REF] Torr | Robust parameterization and computation of the trifocal tensor[END_REF] are of course needed to truly assess the promise of our approach.

Discussion

We have characterized both geometrically and analytically the role of point trilinearities in multi-view geom-Init. E12 E13 E23 E21 E31 E32 T1 T2 T3 Aff. 1.0 1.0 0.9 1.0 0.9 0.9 6.3 0.9 0.8 Proj. 2.0 1.6 1.3 1.9 1.5 1.2 7.7 1.7 1.1 Table 1. Quantitative results for the dataset of Figure 6 and affine [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF] and projective [START_REF] Carlsson | Duality of reconstruction and positioning in multiple views[END_REF] initializations. Here, "Eij" refers to the distance between points in image i and the corresponding epipolar lines associated with image j, and "Tj" refers to the distance between points in image j and the corresponding trinocular line associated with the other two images.

etry. Although the nature of our presentation has been mainly theoretical (what are trifocal constraints really for?), our analysis has led to a new minimal parameterization of trinocular geometry for both non-collinear and collinear pinholes, and we have presented a preliminary implementation in the non-collinear case. A full-fledged experimental evaluation of this implementation and its extension to the collinear case is next on our agenda.

One may of course wonder whether the fact that four lines intersect in exactly one point can also be characterized geometrically or analytically. Indeed, there exists a quadrifocal tensor expressing the corresponding four-view constraints [START_REF] Triggs | Matching constraints and the joint image[END_REF], and it has been shown to be redundant with the epipolar and trifocal constraints. In retrospect, it is geometrically obvious that a necessary and sufficient condition for four lines to intersect in exactly one point is that any two triplets of lines among them also does: This follows immediately from the fact that these triplets have two lines in common, so the point where these two lines intersect is aso the point where all four lines intersect.

In other words, there is no need to write any equation to realize that considering four lines together instead of a set of triplets does not add anything to the geometric picture in this case. On the other hand, the natural algebraic constraints to write among four lines is that they be linearly dependent, which is equivalent to writing that all 4 × 4 minors of the 6 × 4 matrix formed by their Plücker coordinate vectors be zero. This yields a set of quadrilinear constraints similar to the quadrifocal ones. However, the elements of a rank-3 family of lines do not necessarily intersect in a single point: Instead they form a regulus, in one of the configurations shown in Figure 3, which of course includes bundles. Thus quadrilinearities, on their own, are neither necessary (which was already known), nor sufficient, to characterize the fact that the corresponding visual rays intersect. This is intriguing, and perhaps a step toward future work.

2 Figure 1 .

 21 Figure 1. Left: Visual rays associated with three (correct) correspondences. Right: Degenerate epipolar constraints associated with three coplanar, but non-intersecting rays lying in the trifocal plane τ (as in the rest of this presentation, the image planes are omitted for clarity in this part of the figure). See text for details.

Figure 2 .

 2 Figure 2. Top: The possible configurations of three pairwisecoplanar distinct lines, classified according to the way they intersect. The three given lines are shown in black; the planes where two of them intersect are shown in green; and the points where two of the lines intersect are shown in red. Bottom: Transversals to the three lines, shown in blue, and forming (1) a line bundle; (2) a degenerate congruence; and (3) a line field.

2 Figure 4 .

 24 Figure 4. Degenerate epipolar constraints associated with three images when the three pinholes are collinear and the rays are coplanar but don't intersect in a common point.

Figure 5 .

 5 Figure 5. For collinear pinholes, there exists a single scene plane π0 in the pencil passing through the baseline β that containts x0 and for which the condition T0 = 0 is ambiguous.

⇐⇒y

  41 y 32 = y 31 y 42 y 41 y 23 = y 21 y 43 y 42 y 13 = y 12 y 43 . (4)

  ): y 41 y 32 = y 31 y 42 , y 41 y 33 = y 31 y 43 , y 42 y 33 = y 32 y 43 , (10) and write T 0 = 0 and T 3 = 0 respectively as y 31 y 32 (y 23y 13 ) + y 33 (y 31 y 12y 21 y 32 ) = 0, y 41 y 42 (y 23y 13 ) + y 43 (y 41 y 12y 21 y 42 ) = 0.

Figure 6 .

 6 Figure 6. (Top) Example trinocular lines recovered from correspondences in three images; (Bottom) Estimated epipolar lines (two sets per image). Note that the two families of epipolar lines associated with an image typically contain (near) degenerate pairs that can be disambiguated using trilinearities.

Acknowledgments. This work was supported in part by the ERC grant VideoWorld, the Institut Universitaire de France, and ONR MURI N000141010934.


Jean Ponce

Martial Hebert

On Image Contours of Projective Shapes

This paper revisits classical properties of the outlines of solid shapes bounded by smooth surfaces, and shows that they can be established in a purely projective setting, without appealing to Euclidean measurements such as normals or curvatures. In particular, we give new synthetic proofs of Koenderink's famous theorem on convexities and concavities of the image contour, and of the fact that the rim turns in the same direction as the viewpoint in the tangent plane at a convex point, and in the opposite direction at a hyperbolic point. This suggests that projective geometry should not be viewed merely as an analytical device for linearizing calculations (its main role in structure from motion), but as the proper framework for studying the relation between solid shape and its perspective projections. Unlike previous work in this area, the proposed approach does not require an oriented setting, nor does it rely on any choice of coordinate system or analytical considerations.

Introduction

Under perspective projection, the image (occluding) contour of a solid shape is the intersection of the retina with the boundary of a cone tangent to the shape's surface, with apex at the pinhole. It is the projection of the rim curve where the cone and the surface meet tangentially.

What does the occluding contour tell us about solid shape? This is the question asked, and largely answered by Jan Koenderink in his landmark 1984 paper [START_REF] Koenderink | What does the occluding contour tell us about solid shape?[END_REF]. Specifically, contradicting an earlier claim by David Marr [START_REF] Marr | Analysis of occluding contour[END_REF] stating that inflections of image contours do not (in general) convey any information about three-dimensional shape, Koenderink proved a remarkable result: The inflections of the image contour of a solid bounded by a smooth surface are the projections of parabolic points, where the Gaussian curvature of the surface vanishes. The convex points of the contour are projections of convex points of the surface, and its concave points are the images of saddle-shaped, hyperbolic points. The concave parts of the surface themselves never show up on the contour, for they are hidden from view by the solid itself.

Koenderink's proof holds for both orthographic and perspective projection, and it is simple and elegant (see [START_REF] Arbogast | 3D structure inference from image sequences[END_REF][START_REF] Boyer | 3D surface reconstruction using occluding contours[END_REF][START_REF] Brady | Describing surfaces[END_REF][START_REF] Cipolla | Surface shape from the deformation of the apparent contour[END_REF][START_REF] Vaillant | Using extremal boundaries for 3D object modeling[END_REF] for variants). It is also firmly anchored in Euclidean (differential) geometry, since it largely relies on concepts such as curve and surface normals and curvatures. This paper revisits Koenderink's question in the more general setting of projective geometry, where Euclidean measurements such as distances, angles, and curvatures are forbidden, but more primitive incidence, tangency and more generally contact properties are still available.

Lazebnik and Ponce addressed the same problem in [START_REF] Lazebnik | The local projective shape of smooth surfaces and their outlines[END_REF], and showed that Koenderink's results are in fact valid in oriented projective geometry [START_REF] Stolfi | Oriented Projective Geometry: A Framework for Geometric Computations[END_REF]. In this setting, points, lines, and planes are all oriented, which allows for deciding, for example, on which side of a plane a point lies, but requires somewhat awkward constructions such as maintaining two oriented copies of each point. We go one step further in this presentation, and prove that Koenderink's results holds in classical projective geometry, without the need for such constructions (Theorems 1 and 2). Likewise, we show that the rim turns in the same direction as the pinhole at a convex point, and in the opposite direction at a hyperbolic one (Theorem 3), a well known property in Euclidean geometry, extended to oriented projective geometry in [START_REF] Lazebnik | The local projective shape of smooth surfaces and their outlines[END_REF].

While the paper does not introduce new theorems, it introduces new ways of manipulating concepts previously restricted to the Euclidean or oriented projective realms. Stated plainly, basic properties of the visual world that were known to be true in Euclidean or oriented projective settings are shown to be true in the much more general setting of plain projective geometry and, unlike most proofs in geometric computer vision, that require global or local coordinate systems and analytical parameterizations [START_REF] Arbogast | 3D structure inference from image sequences[END_REF][START_REF] Boyer | 3D surface reconstruction using occluding contours[END_REF][START_REF] Brady | Describing surfaces[END_REF][START_REF] Cipolla | Surface shape from the deformation of the apparent contour[END_REF][START_REF] Koenderink | What does the occluding contour tell us about solid shape?[END_REF][START_REF] Lazebnik | The local projective shape of smooth surfaces and their outlines[END_REF][START_REF] Vaillant | Using extremal boundaries for 3D object modeling[END_REF], ours are purely synthetic and do not require such an apparatus. Thus plain projective geometry is the appropriate framework for studying these properties.

We believe that the type of inquiry pursued in this paper is important because it identifies projective geometry as the natural setting for the qualitative study of the visual world: Koenderink's result (Theorems 1 and 2) tells us about the appearance of a solid shape in one image. Theorem 3 tells us about the rim moves with the viewpoint, and is therefore a first step toward understanding how the appearance of a solid changes in multiple pictures. We will come back to the latter point in Section 6.

The rest of this presentation is organized as follows: We recall basic facts about the local shape of curves and surfaces in classical (differential) projective geometry in Section 2. We prove in Section 3 that inflections of the contour are the projections of parabolic points (Theorem 1), which can be seen as a weak version of Koenderink's theorem. The strong version (Theorem 2) is proven in Section 4, and the rim motion is characterized by Theorem 3 in Section 5. We conclude by a brief discussion of future work in Section 6.

The Local Projective Shape of Curves and Surfaces

Basic Setting

We assume that objects of interest live in the real projective space P m , m = 2 or 3, which can be defined as the quotient of R m \{0} by the equivalence relation identifying vectors that are nonzero multiples of each other [START_REF] Berger | Geometry[END_REF]. In our context, it is perhaps better viewed as a manifold, locally affine (in fact the complement of any hyperplane in P m has an affine structure) but globally exempt of affine exceptions such as non-intersecting (parallel) coplanar lines or planes. Put more plainly, a projective plane (for example), looks locally just like an affine plane. On the other hand, one has to be mindful of the fact that, for example, a line does not split a projective plane into two distinct components, nor does a plane split space into two components, and it is in general meaningless to talk about the "two sides" of such a line or plane. The whole arsenal of Euclidean measurements such as length or angle is also missing, along with the notions of normal, curvature, etc. Projective transformations (or collineations) are isomorphisms between projective spaces, and they preserve relations such as incidence or contact, as well as certain numerical invariants such as cross-ratios and homogeneous coordinates.

A perspective camera is defined in P 3 by its pinhole o and retinal plane Π. It maps any point in P 3 \ {o} onto the point y of the retina Π where the line joining o to x intersects that plane [START_REF] Ponce | What is a camera?[END_REF]. We are interested in this paper in qualitative relations between objects of P 3 and their perspective projections that are invariant under projective transformations.

The objects considered in this paper are solid, opaque, rigid bodies, bounded by smooth surfaces. These bodies will be called solids for short from now on. Certain visual features such as points, lines or curves drawn on these surfaces, are observed by cameras in the form of their projections onto some retinal plane. The images of the solids themselves, their shadows, so to speak, also form solid regions on the retinas, and they are in general bounded by piecewise-smooth curves.

Our setting excludes "hanging" threads for example, but so be it, and, as argued in [START_REF] Koenderink | Solid Shape[END_REF], it will simplify our arguments. In particular, this will allow us to easily generalize the familiar notions of (local) convexity and concavity to the projective setting. More importantly, the definitions below are intuitive and similar to those used in Euclidean geometry. Yet, they do not rely in any way on the Euclidean machinery of curve and surface normals and curvatures.

Flatland

Let us start in Flatland-that is, restrict the world to a (projective) plane, equipped with its natural topology. A curve of the projective plane is said to be smooth when it admits a unique tangent at every point. Its inflections and cusps of both kinds can be defined as usual. A piecewise-smooth curve is continuous and smooth everywhere except at isolated points where it may admit multiple tangents. ¿From a topological viewpoint, there are two kinds of simple (no crossing) connected curves in P 2 , one-sided curves (like straight lines), and two-sided ones, called ovals, that split the plane into two components, one, called the interior of the oval, homeomorphic to a disc, and the other, called its exterior, homeomorphic to a Möbius strip. We limit our attention in this section to solid regions ω of the plane, defined as the closure of the interior of an oval ∂ω.

We shall say that a piecewise-smooth oval ∂ω is (locally) convex at some point x when there exists a line passing through x and (locally) contained in the (closure of the) exterior of ω, and that it is (locally) concave in x when there exists a line passing through that point and (locally) contained in the (closure of the) interior of ω. Convex and concave subsets of ∂ω form connected arcs of this curve, and they are separated by inflections and cusps of the second kind.

A subset ω of the affine plane is said to be convex when the segment joining any two of its points is itself a subset of ω. This definition is problematic in the projective case because there are always two "antipodal" segments joining two points. This has led previous studies of local shape in computer vision [START_REF] Lazebnik | The local projective shape of smooth surfaces and their outlines[END_REF] to rely on notions from oriented projective geometry [START_REF] Stolfi | Oriented Projective Geometry: A Framework for Geometric Computations[END_REF]. Limiting our attention to curves bounding solid regions avoids this difficulty.

In the Round

Let us now move to the slightly more complicated world of surfaces bounding solid bodies defined "in the round"-that is, in the projective model we will adopt from now on for the three-dimensional world surrounding us.

The tangent plane π at a point x on a smooth surface σ (whether σ is orientable or not) is the plane that contains all the tangents to the curves drawn on σ and passing through x. The point x can be classified as elliptic, hyperbolic, or parabolic according to the way σ intersects its tangent plane π there (Figure 1): At an elliptic point, the intersection of σ and π consists of x itself, and σ locally lies on one side of π there (let us emphasize that this statement is only valid locally-that is, in some small neighborhood of x since, like a line in a projective plane, π does not split P 3 into two distinct components). At a hyperbolic point, on the other hand, σ and π meet along two asymptotic curves intersecting in x, and the surface traverses its tangent plane. Finally, at a parabolic point, σ and π intersect transversally along a curve that cusps there. Elliptic and hyperbolic subsets of smooth surfaces form connected regions, and they are separated by parabolic curves. Note that all the notions defined in this paragraph are purely projective, and depend in no way on Euclidean devices since they are entirely based on incidence and tangency relations. For simplicity, we define a solid as the closure of the interior of an oriented, connected and smooth surface, admitting a single tangent plane at each point. We shall say that the surface σ = ∂ω bounding some solid ω is (locally) convex at some elliptic point x when the tangent plane in x (locally) contained in the (closure of the) exterior of ω, and that it is (locally) concave in x when it is contained instead in the (closure of the) interior of ω.

As noted earlier, the image of ω is the intersection of the retinal plane Π with the solid cone tangent to σ with the pinhole o as its apex. The image contour formed by its boundary is an oval with piecewise-smooth boundary having at most two tangents at any point. 3 The intersection curve between the surface of the cone and σ is the rim curve γ. When x is a concave point, it cannot be visible because the line between o and x is tangent to σ, and thus locally contained in the interior of ω. We will use this fact in the proof of Theorem 2 in Section 4.

The Gauss Map

In Euclidean geometry, the Gauss map associates with every point on an oriented smooth curve γ drawn in a plane the point of the unit circle centered at the origin corresponding to the tip of its normal. Its folds correspond to inflections and cusps of the second kind. Likewise, the Gauss map associates with every point on the smooth oriented surface the point of the unit sphere centered at the origin corresponding to the tip of its normal. Interestingly, under orthographic projection, the Gaussian image of the rim is a great circle of the sphere, orthogonal to the projection direction. It is identical to the Gaussian image of the contour itself. This has been used in [START_REF] Forsyth | Computer Vision: A Modern Approach[END_REF] to prove the weak version of Koenderink's theorem, namely that inflections of the contour are the projections of parabolic points, in the Euclidean case.

In projective geometry, the Gauss map associates instead with each point on a curve its tangent line (Figure 2[a,b]). Its image is the dual of the curve. This time, the cusps of the dual correspond to inflections and cusps of the second kind. Double points of the Gaussian image correspond to bitangents of the curve. The Gauss map also associates with every point on a surface its tangent plane (Figure 2[c,d]). Note that the definition of the projective Gauss map does not require the curve or surface of interest to be orientable. When it is, however, the image of the Gauss map, that is, the dual, inherits an orientation from the corresponding curve or surface, and we can talk locally of the orientation of the corresponding tangent line or surface. This will prove extremely important in the rest of our presentation. Note also that some of the properties of the Gauss map and its cusps established in the Euclidean setting [START_REF] Banchoff | Cusps of Gauss mappings[END_REF] have been generalized to the projective one in [START_REF] Mccrory | Cusps of the projective Gauss map[END_REF]. In particular, cusps of the Gauss map correspond to the (tangential) intersections of the parabolic line with the flecnodal one (the locus of inflections of the asymptotic curves). Interestingly, the Gaussian image of the rim in this case is the intersection of the dual surface with the dual plane consisting of all the (primal) planes that contain the viewpoint. We will see in the next section that this can be be used to prove the weak version of Koenderink's theorem in the projective case.

Note:

The proofs of the classical results used in our presentation all assume that certain genericity conditions are satisfied [START_REF] Bruce | The duals of generic hypersurfaces[END_REF][START_REF] Mccrory | Cusps of the projective Gauss map[END_REF], that is (informally), that the surfaces considered are "sufficiently general", thus excluding quadrics, toruses, etc. We assume throughout the rest of this presentation that these genericity conditions are indeed satisfied.

Koenderink's Theorem: Weak Version

We first characterize the type of rim points corresponding to inflections of the image contour:

Theorem 1. Under perspective projection, the inflections of the image contour of a smooth surface are the images of parabolic points.

The Euclidean version of this theorem was proven by Koenderink in [START_REF] Koenderink | What does the occluding contour tell us about solid shape?[END_REF]. We now show that it also holds under a pure projective setting. We do so by first clarifying the relationship between the Gaussian image of the image contour and that of the surface. We then use this result to connect Theorem 1 to a known (projective) property of the Gaussian images of curves of smooth surfaces. Lemma 1. Under perspective projection, the rim of a surface and its image contour have the same Gaussian image, which is a planar section of the Gaussian image of the surface itself by the dual plane associated with the viewpoint.

Proof. By definition, the rim of a surface and the visual cone tangent to it with apex at the viewpoint share the same Gaussian image. In addition, the dual of a surface's rim is a planar section of its dual. More precisely, the Gaussian image of the rim is the intersection of the Gaussian image of the surface with the dual plane formed by all (primal) planes passing through the viewpoint.

The image contour is a planar section of the visual cone. Its Gaussian image is a curve in the projective plane (line field, or dual of plane π) l(π) formed by the lines of the retinal plane Π. Now for any π (and in particular for the retinal plane of course), the mapping ϕ x that associates with each element of l(π) the plane spanned by that line and some point x outside of π is a collineation between l(π) and the dual plane x ⋆ formed by all planes passing through x.

To prove that ϕ x is a collineation, it is sufficient to show that if three points p 1 , p 2 , p 3 in l(π) are aligned, then ϕ x (p 1 ), ϕ x (p 2 ), ϕ x (p 3 ) are aligned in x * . Indeed, the lines l 1 , l 2 , l 3 in π corresponding to p 1 , p 2 , p 3 intersect at one point q since the points are aligned in l(π). Therefore, the planes corresponding to ϕ x (p 1 ), ϕ x (p 2 ), ϕ x (p 3 ) must meet at a common line, namely the line containing x and q. The points in the dual corresponding to any three planes intersecting at a common line are aligned. Therefore, ϕ x (p 1 ), ϕ x (p 2 ), ϕ x (p 3 ) are aligned and ϕ x is a collineation. When x is the viewpoint, ϕ x induces a bijection between tangent lines to the image contour and tangent planes to the rim. Since this bijection is a collineation, the two Gaussian images can thus be identified with the corresponding planar section of the surface's dual.

⊓ ⊔

Lemma 2 ( [START_REF] Bruce | The duals of generic hypersurfaces[END_REF][START_REF] Mccrory | Cusps of the projective Gauss map[END_REF]). The Gaussian image of the parabolic curve of a smooth surface consists of cuspidal edges with isolated swallowtail points.

Theorem 1 immediately follows from Lemmas 1 and 2 by noting that a planar section of a cuspidal edge is in general a cusp (Figure 2[d]).

Koenderink's Theorem: Strong Version

The weak version of Koenderink's theorem does not require the observed surface σ to be oriented. Its strong version, stated below, does. In fact, we assume from now on that σ bounds an opaque solid, with a well defined interior and exterior. It enables us to characterize the concave and convex points of the image contours in addition to the inflection points already addressed in Theorem 1. Notation. Let us define the perspective camera observing σ by its pinhole o and retina Π. Together, the surface and the camera define a conical surface κ with apex in o, tangent to σ along the rim γ. We denote by x ′ the perspective projection of a rim point x with tangent plane τ onto Π, and by γ ′ the image contour passing through x ′ with tangent τ ′ . The contour is obtained (equivalently) as the perspective projection of γ onto Π or the intersection of κ with that plane.

Theorem 2. Under perspective projection, the convexities of the image contour of an oriented smooth surface are the images of convex points, its concavities are the projections of hyperbolic points, and its inflections are the images of parabolic points.

The following lemma, given without proof, summarizes well known properties of a conical surface κ [START_REF] Hilbert | Geometry and the Imagination[END_REF]. These will prove to be a key to the proof of Theorem 2. These properties are true whether κ is a visual cone or not. Lemma 3. A conical surface κ is made up entirely of parabolic points. Contrary to the generic case depicted in Figure 1[right], its intersection with its tangent plane τ at Proof (of Theorem 2). The conical surface κ, the rim γ, the tangent plane τ to σ in x, the contour γ ′ and its tangent τ ′ all inherit their orientation from σ (in particular, γ ′ is also an orientable, and in fact oriented, curve). At a convex point x (Figure 3[a]), τ is (locally) outside σ and therefore κ, and thus τ ′ is also outside γ ′ , which in turn implies that the contour is convex in x ′ . When x is a concave point, on the other hand, τ is locally inside σ, and thus inside the opaque solid it bounds, which in turn implies that x is hidden from the pinhole o.

Consider now a hyperbolic point x (Figure 3[b]). The orientation of σ in x induces as before an orientation of the tangent plane τ , which locally splits the surface into an inner part "below" τ -that is, on the same side as the interior of the solid, and an outer part "above" this plane. Any ray passing through a point below the plane τ in a sufficiently small neighborhood of x intersects the solid's interior. Thus the rim γ must (locally) be drawn on the part of σ emerging above τ , i.e., there exists an open segment of γ containing x and entirely lying on the outer side of τ . According to Lemma 3, it follows that τ is (locally) inside κ. Likewise, τ ′ is locally inside κ and therefore inside γ ′ , which in turn implies that the contour is concave in x ′ . The parabolic case, already covered by Theorem 1, is illustrated by Figure 3(c).

⊓ ⊔ Consider a hyperbolic point and a viewpoint moving in its tangent plane. From Theorem 2, the contour is concave everywhere it is visible-that is, within the sector that lies outside the intersection curve γ of the observed solid and its tangent plane (Figure 4). This sector is bounded by the two asymptotic lines tangent to the two branches of γ. As illustrated by Figure 4, the contour cusps when the viewpoint belongs to one of the asymptotic lines.

Fig. 4. The rim at a hyperbolic point. Left: Two generic visual rays (in red and green) and the corresponding rim curves. For a surface bounding a solid, one of the two rays and the corresponding rim would be (locally) in the interior of the object. Right: An asymptotic ray and the corresponding rim curve (in blue). The ray is tangent to the rim, giving birth to a cusp in the image. For a surface bounding an opaque solid, one branch of the rim and the corresponding branch of the contour at the cusp would be invisible.

Relative Rim and Viewpoint Motions in the Tangent Plane

Having established the relationship between the configuration of the local surface at a point on the rim and that of the local contour at its projection, we now turn our attention to the relationship between a change of viewpoint and the motion of the rim on the surface which it induces. Informally, given a pair of viewpoints in the tangent plane of a point which is on the rims corresponding to the two viewpoints, can we say something about the direction in which the rims locally turn around the point? We show in this section that the following theorem holds in the general projective case: Theorem 3. The rim turns in the same direction as the viewpoint in the tangent plane of a smooth oriented surface at a convex point, and in opposite ones at a hyperbolic point (Figure 5).

In fact, this result can be shown in the Euclidean setting by showing explicitly that the Gauss map preserves orientation at elliptic points and reverses orientation at hyperbolic points [START_REF] Carmo | Differential Geometry of Curves and Surfaces[END_REF]. The same result was shown in the oriented projective geometry setting by tracing oriented rays from the pinhole to the point [START_REF] Lazebnik | The local projective shape of smooth surfaces and their outlines[END_REF]. Here, we go one step further by showing that the result holds without requiring the machinery of oriented projective geometry.

Of course, since we do not have any ready concept of signed angle or orientation at our disposal in the pure projective setting, what we mean by "turning in the same in the same direction or in the opposite direction" is not so obvious. Our first order of business is to introduce a clear definition. For that, we first need a notion of separability for pairs of lines in the same flat pencil (Figure 6). Definition 1. Given four distinct, coplanar and concurrent lines ξ 1 , δ 1 , ξ 2 and δ 2 , we say that (ξ 1 , ξ 2 ) and (δ 1 , δ 2 ) form separable pairs when both δ 1 and δ 2 lie in the interior of one of the sectors delimited by ξ 1 and ξ 2 in their common plane or, equivalently, when both ξ 1 and ξ 2 lie in the interior of one of the sectors delimited by δ 1 and δ 2 .

o 1 o 2 o 1 o 2 o 1 o 2 ξ 1 ξ 2 γ 1 γ 2 τ ν x y λ 2 λ 1 ρ o 1 o 2 o 1 o 2 o 1 o 2 ξ 1 ξ 2 γ 1 γ 2 τ ν x y λ 1 λ 2
When δ 1 and δ 2 (resp. ξ 1 and ξ 2 ) are fixed, a sufficient condition for separability is (for example) that ξ 2 (resp. δ 2 ) be close enough to ξ 1 (resp. δ 1 ) in the natural topology of the projective line formed by a pencil of lines. Whether the elements of two separable pairs of lines turn in the same direction or not can now be defined, again in terms of separability (Figure 6). Definition 2. Given two separable pairs of coplanar and concurrent lines (ξ 1 , ξ 2 ) and (δ 1 , δ 2 ), we say that δ 1 and δ 2 turn in the same direction as ξ 1 and ξ 2 when (ξ 1 , δ 2 ) and (ξ 2 , δ 1 ) are separable, and that they turn in opposite directions otherwise. This is indeed a projective notion, and a strictly analogous line of reasoning leads by duality to a notion of relative order for two pairs of separable points on a line.

Proof (of Theorem 3).

Let us consider a point x on the surface σ with tangent plane τ , two nearby pinholes o 1 and o 2 in τ , the corresponding visual rays ξ 1 and ξ 2 through x, and the corresponding rim curves γ 1 and γ 2 with tangents δ 1 and δ 2 in the neighborhood of x (Figure 5). We assume that o 1 is fixed, and that ξ 1 and δ 1 are distinct-that is, either x is convex, or it is hyperbolic but ξ 1 is not an asymptotic direction in x. We also assume

1 ξ 2 1 ξ 2 ξ δ1 ξ δ1 δ 1 ξ 1 ξ 2 δ 2 ξ 1 ξ 2 δ 2 δ 2 1 ξ 2 1 ξ 2 ξ δ2 ξ δ2 δ 2 ξ 1 ξ 2 δ 1 ξ 1 ξ 2 δ 1 δ 1
Fig. 6. Comparing the way separable pairs of lines in the same pencil turn in their plane. The lines ξ1 and ξ2 are separable from the lines δ1 and δ2 in each one of the four cases depicted. Top: The lines ξ1 and δ2 define two bidirectional sectors (here one is drawn in light blue, the other one is white). When ξ2 and δ1 lie in the same sector, (ξ1, δ2) and (ξ2, δ1) are separable, and δ1 and δ2 turn in the same direction as ξ1 and ξ2. Bottom: When (ξ1, δ2) and (ξ2, δ1) are not separable, (ξ1, δ1) and (ξ2, δ2) are separable instead, and the pairs (δ1, δ2) and (ξ1, ξ2) turn in opposite directions.

η 1 η 2 o 1 o 2 t 2 µ 1 µ 2 y u 1 t 1 u 2 λ 1 λ 2 ρ v 1 η 1 η 2 o 1 o 2 t 2 µ 1 µ 2 y u 1 t 1 u 2 λ 1 λ 2 ρ v 2
Fig. 7. Left: A convex point. Nearby rays λ1 and λ2 and the lines µ1 and µ2 joining y to the points where they graze the curve ρ. Right: A hyperbolic point. We have also highlighted the inner side of the lines λ1 and λ2 with hash marks.

that the second pinhole o 2 is fixed, but sufficiently close to o 1 for the two pairs of lines (ξ 1 , ξ 2 ) and (δ 1 , δ 2 ) to be separable.

Let us now consider a plane ν in the pencil of planes passing through o 1 and o 2 , close enough to τ to intersect the rim. When x is a convex point, ν is "below" (on the inner side of) τ and locally intersects σ along a non-empty, closed and (everywhere locally) convex curve ρ (Figure 5, top). The curve ρ inherits its orientation from that of σ. Given some point y in its interior, this point approaches x as ν approaches τ , and the ray η 1 passing through o 1 and y approaches ξ 1 . Let us further assume from now on, without loss of generality, that ν is close enough to τ that all "inside" and "outside" relations below are meaningful (they indeed are, locally, in general). In particular, among the two rays passing through the first viewpoint o 1 and tangent to ρ, let us choose λ 1 to be the one with η 1 on its inner side.

Let us also denote by µ 1 the line joining y to t 1 , and define similarly η 2 , t 2 , λ 2 and µ 2 for the second viewpoint o 2 . For ν close enough to τ , the pairs (η 1 , η 2 ) and (µ 1 , µ 2 ) are separable since the lines η 1 and η 2 approach the rays ξ 1 and ξ 2 , and µ 1 and µ 2 approach the rim tangents δ 1 and δ 2 . Finally, let u 1 (resp. u 2 ) denote the intersection of λ 1 and µ 2 (resp. λ 2 and µ 1 ), and let v 1 denote the intersection of λ 1 and η 2 . We can (again) always pick ν close enough to τ that the points t 1 , u 1 , t 2 , u 2 , and v 1 are all in a small open neighborhood of y where it is meaningful to say that one of these points is on the inner or outer side of λ 1 or λ 2 . In particular, t 1 (resp. t 2 ) is by construction on the inner side of λ 2 (resp. λ 1 ), thus u 1 (resp. u 2 ) is on the outer side of λ 2 (resp. λ 1 ).

Let us show that the two pairs of points (o 1 , u 1 ) and (v 1 , t 1 ) on λ 1 are separable. By duality, this will show in turn that the pairs (η 1 , µ 2 ) and (η 2 , µ 1 ) are separable. Let us define [v 1 t 1 ] as the intersection of the line λ 1 with the sector formed by η 2 and µ 1 which does not contain o 1 . Since t 1 and v 1 are on the inner side of λ 2 (and for ν close enough to τ ), the entire segment [v 1 t 1 ] is also on the inner side of λ 2 . Since u 1 is by construction outside λ 2 , it is thus also outside [v 1 t 1 ]. It follows that the two pairs of points (o 1 , u 1 ) and (v 1 , t 1 ) are separable, and thus the lines (η 1 , µ 2 ) and (η 2 , µ 1 ) are separable too. Since the lines η 1 and η 2 approach the rays ξ 1 and ξ 2 , and the lines µ 1 and µ 2 approach the rim tangents δ 1 and δ 2 as ν approaches τ , if finally follows that the rim turns in the same direction as the viewpoint in x.

The same reasoning can be applied at a hyperbolic point, except that the plane ν intersecting the rim must lie "above" (on the outer side of) τ (Theorem 2), and locally intersects the surface along two curves (Figure 5, bottom). These curves inherit the orientation of σ, and we can choose some point y lying outside both these curves and approaching x as ν approaches τ . When ν is close enough to τ , we can always choose a ray λ 1 tangent to one of these curves such that y lies on the outer side of λ 1 (Figure 7[right]). A similar line of reasoning one shows that (v 1 , u 2 ) can be separated from (o 2 , t 2 ), and thus (ξ 1 , µ 1 ) can be separated from (ξ 2 , µ 2 ). Since µ 1 and µ 2 converge to δ 1 and δ 2 as ν approaches τ , the rim and the viewpoint turn in opposite directions in x.

⊓ ⊔

Discussion

We have shown that two fundamental questions on the relationship between a threedimensional shape and its image contour could be answered in a purely projective setting without resorting to analytical tools or oriented projective geometry. Specifically, we have shown how the inflections, convex, and concave parts of an image contour can be related to local properties of the surface at the corresponding points with a new proof of Koenderink's theorem, and we have shown how the motion of the rim relates to that of the viewpoint. These results are first steps toward a complete reformulation of several classical models of shape and appearance in purely projective terms. In particular, the oriented projective version of Theorem 3 is used in [START_REF] Lazebnik | The local projective shape of smooth surfaces and their outlines[END_REF] as a building block for an algorithm for computing the rim mesh [START_REF] Lazebnik | On computing exact visual hulls of solids bounded by smooth surfaces[END_REF] defined on the surface of a solid by the rim curves associated with multiple cameras. It would interesting to see whether the purely projective version of the theorem can be used in a similar fashion. This would have practical implications in the context of visual hulls as well [START_REF] Baumgart | Geometric modeling for computer vision[END_REF][START_REF] Lazebnik | Projective visual hulls[END_REF]. The geometry of the Euclidean Gauss map has also been shown to dictate (in part) the evolution of the image contour and its topology under changes in viewpoint (see [START_REF] Forsyth | Computer Vision: A Modern Approach[END_REF]Ch. 20] for an overview). Using the projective Gauss map in a similar way would be very interesting. Results in this direction [START_REF] Mccrory | Cusps of the projective Gauss map[END_REF] showing that the cusps of the Gauss map correspond to the (tangential) intersections of the parabolic line with the flecnodal one, in the projective case as well as in the Euclidean one, are encouraging, and may lead to a purely projective formulation of aspect graphs [START_REF] Koenderink | The internal representation of solid shape with respect to vision[END_REF] for example.

More generally, we have introduced new concepts and tools such as separability in order to generalize concepts such as ordering or "in betweenness" normally defined in a Euclidean or oriented projective setting to a general projective setting. We believe that they are crucial in formulating many geometric properties of solid shapes and their projections in the projective realm.

Fig. 1 .

 1 Fig. 1. The local shape of a surface. From left to right: an elliptic point, a hyperbolic point, and a parabolic point. (Reproduced with permission from the authors of [17].)

Fig. 2 .

 2 Fig. 2. Dual curves and surfaces: (a) a planar curve, with its inflections and bitangent; (b) its dual, with the cusps and double point associated with the inflections and bitangent; (c) a surface, with its parabolic line (in green) and a rim curve (in red); and (d) (part of) its dual, with the cuspidal edge associated with the parabolic line and the planar section corresponding to the rim. Best seen in color.

Fig. 3 .

 3 Fig. 3. Koenderink's theorem: (a) convex points project onto convex points of the image contour; (b) hyperbolic points project onto concave ones; (c) parabolic points project onto inflections.

Fig. 5 .

 5 Fig. 5. Visual rays and rim curves turn in the same direction at an elliptic point (top) and in opposite directions at a hyperbolic one (bottom).

Points with multiple tangents may occur for exceptional viewpoints.

Acknowledgments. This work was supported in part by the ERC grant VideoWorld, the Institut Universitaire de France, and ONR MURI N000141010934.


Chuan Shan

Eldar Zianbetov

Mohammad Javidan

Franc ¸ois Anceau

Mehdi Terosiet

Sylvain Féruglio

Dimitri Galayko

Olivier Romain

Éric Colinet

Jérôme Juillard

FPGA Implementation of Reconfigurable ADPLL Network for Distributed Clock Generation

This paper presents a FPGA platform for the design and study of network of coupled all-digital phase locked loops (ADPLLs), destinated for clock generation in a large synchronous system on chip (SOC). An implementation of a programmable and reconfigurable 4×4 ADPLL network is described. The paper emphasises the difference between the FPGA and ASIC-based implementation of such a system, in particular, implementation of digitally contolled oscillators and phase-frequency detector. The FPGA-implemented network allows to study complex phenomena related with coupled ADPLL operation, and to exploit stability issues and nonlinear behaviour. A dynamic setup mechanism has been proposed for the network, allowing to select the desirable synchronised state. Experimental results demonstrate the global synchronization of network and performance of the network for different configuraitons.

I. INTRODUCTION

Clocking is one of the main issues in design of large circuits on chip (SOC) like manycore processors. synchronous communication is still largely used in SOCs, espetially for application requiring high reliability. However, practical implementation of a global clock distribution is very difficult in advanced deeply submicronic CMOS technologies. Our study explores an alternative technique of clocking, consisting in distributed clock generation through a network of all-digital PLLs. Such a network is composed of several oscillators distributed over the chip, which are coupled in the phase domain. Each oscillator generates a local clock. A network properly designed guarantiees that all oscillators generates a signal at the same frequency and with the same phase. The originality of our study is the fact that the network of PLL is fully digital, contrary to previous implementations [START_REF] Pratt | Distributed Synchronous clocking[END_REF].

A network of coupled digital PLLs is a very complex nonlinear high-degree dynamic system, having different operating modes, among which only some of them are desirable. The selection of the mode is done through the appropriate choice of the network parameters (the ADPLL filter coefficients, the choice of initial conditions, etc.), and requires a solid underlying theory and a prototyping platform. This work presents an implementation of such a prototype on a single FPGA chip. The goal of the prototype is to model as close as possible the behaviour of an ASIC-based ADPLL network, which is being designed in the LIP6 analog/mixed circuit group. The FPGA emulator must have exactly the same architecture with the same parameters values, however, scaled down proportionally in frequency because of the maximum frequency limit of the FPGA board. However, the FPGA emulator must reproduces with high fidelity the functional behaviour of the designed ASIC chip.

However, the FPGA-implementation is different from the implementation of their ASIC counterpart, in particular, in blocks whose operation is based on controllable pure delays, like time-to-digital converter (TDC) and the digitally controlled oscillator (DCO). The paper describes the way to prototype these elements on FPGA, so to model as close as possible the ASIC-based blocks.

The validation of the prototype is done through testing the network synchronisation with different filter coefficient, and by observing nonlinear phenomena predicted theoretically for a PLL network. The method of selection of the synchronised mode presented in [START_REF] Zianbetov | All-digital PLL array provides reliable distributed clock for SOCs[END_REF] has been implemented and tested.

In section II the architecture of network and functional blocks are described. Section III presents the procedure allowing to respect the homothety in dimensionning of the FPGA prototype with repsect to the ASIC prototype. Section IV presents experimental results.

II. NETWORK ARCHITECTURE

The topology of network is presented in Fig. 1 [START_REF] Zianbetov | All-digital PLL array provides reliable distributed clock for SOCs[END_REF]. It is composed of Phase Frequency Detectors (PFD) and 16 filter/oscillator (FO) blocks. PFDs are placed on each border between two FO blocks, measuring the phase error between each couple of neighboring oscillators. The PFD placed in upper left corner compares the phase of the input reference and the first oscillator in the network. Such a network, if properly designed, will be synchronized with the reference clock both in frequency and in phase.

The structure of a typical network node is presented in Fig. 2 [START_REF] Zianbetov | Design and VHDL modeling of all-digital PLLs[END_REF]. Each node contains 2-4 PFDs: each PFD detects the phase/frequency difference between the locally-generated clock and a neighboring clock. The number of PFDs depends on the number of the neighbors of a node. A PFD generates Fig. 1. Topology of network a 5 bits signed binary code. For each node, the errors with neighbours are added and are processed by the loop filter, so to generate a control word for the digital controlled oscillator (DCO). The loop filter is a proportional-integral (PI) filter similar to one used in classical single ADPLLs. The frequency divider is used to generate a clock with a frequency higher than that at which the error phase information is processed. A. PFD Fig. 3 presents the structure of a PFD. The Bang-Bang phase-frequency detector (BBPFD) detects the sign of phase error (SIGN ) and the interval of it (M ODE) [START_REF] Thierno | A Wide Power Supply Range, Wide Tuning Range, All Static CMOS All Digital PLL in 65 nm SOI[END_REF]. The duration of the signal M ODE represents the absolute value of the phase error; it is applied to the input of Time-to-Digital Converter (TDC). The TDC converts the duration of input signal to an unsigned binary code, which is then combined with the SIGN signal by the arithmetic block to form a signed binary code. The BBPFD can be seen as a finite state automaton driven by events (rising edges) at its inpus. For this implementation, the architecture presented in [START_REF] Thierno | A Wide Power Supply Range, Wide Tuning Range, All Static CMOS All Digital PLL in 65 nm SOI[END_REF], is described at behavioural level for the FPGA synthesis. In an ASIC-based TDC, the M ODE is delayed by a tapped delay line [START_REF] Levine | A high-resolutino flash time-to-digital converter and calibration[END_REF]. At the falling edge of M ODE, the thermometer code produced by the delay line is stored in a register and then converted to an unsigned binary code. The sensitivity of PFD (∆T ASIC ) is defined as one stage delay in the delay line. Since a logic gate with defined delay cannot be realized in FPGA, in the FPGA-based network, the TDC is implemented as a digital chronometer with an external clock, counting the number of the clock event included in the measured time interval. The period of the external clock corresponds to the sensitivity of PFD (∆T F P GA ). However, the external clock is desynchronized with the start of the time interval to measure. Hence, even if the time interval is below the TDC time step and if the clock event happens to be inside the interval, the FPGA-based TDC may output 1, whereas the ASIC-based TDC outputs 0, which causes a signal-correlated noise with amplitude of ±1 unit over the output code; the sign of the noise is the same as the sign of the error. The transfer function is presented in Fig. 4. A proportional-integral (PI) filter is implemented as the loop filter. Its transfer function is described as follows:

H(z) = K p + K i 1 -z -1 (1)
where K p and K i are gain coefficients of the proportional and integral paths respectively. Their values are programmable. The filter has up to 4 inputs (Fig. 5), which are weighted with programmable coefficients K wi . The number of inputs can be regulated by programming the coefficients K wi to one or zero.

The programming of the filter coefficients is designed so that all the programmable values of the network can be changed in parallel, at the same time moment. This is achievied with a simple serial-to-parallel register used for the programming value loading. This allows to test scenarii of dynamic reconfiguration of the network.

C. DCO

Because of the limits of FPGA, a ring oscillator with programmable delay is difficult to be implemented on FPGA. Instead, the DCO is implemented as a pre-loaded N c -bit counter which defines the DCO clock period, where N c is decided by the number of bit of command signal. The DCO based on counter uses an external clock with a high frequency (f DCO clk ). When the counter saturates, an output event is generated, and at the same time the counter will be reloaded with the DCO input code. Hence, the period of the clock (T DCO F P GA ) generated by DCO for a some input code C in is defined as

T DCO F P GA (C in ) = (2 Nc -C in ) × T DCO clk (2)
where T DCO clk is the period of the external clock. The frequency step of DCO in the FPGA prototype (∆f DCO F P GA ) is defined as

∆f DCO F P GA = 1 T oF P GA - 1 T oF P GA + T DCO clk (3)
where T oF P GA is the period value corresponding to the nominal frequency of FPGA-based DCO (f oP F GA ).

D. Scaling of FPGA prototype parameters

Due to the limit of maximum frequency in FPGA device, all the temporal parameters in the prototype have to be scaled down propotionally respecting the following relation

∆f DCO ASIC : f oASIC : 1 ∆T ASIC =∆f DCO F P GA : f oF P GA : 1 ∆T F P GA =M 1 : M 2 : M 3 (4)
where f oASIC and ∆f DCO ASIC are respectively the nominal frequency and the frequency step of the ASIC-based DCO. M 1 , M 2 , and M 3 are three constants used to simplify the derivation.

From Eq.(3) and Eq.( 4), the ratio between the external clock frequency of FPGA-based TDC (f T DC clk ) and that of FPGAbased DCO (f DCO clk ) can be derived (Eq.( 5)). f T DC clk and f DCO clk are respectively the inverse of the sensitivity of PFD (∆T F P GA ) and the inverse of T DCO clk . The two clocks are generated respectively by two PLLs located in two corners of the device, thus are uncorrelated with each other.

f T DC clk f DCO clk = M 3 M 2 × 1 M 2 /M 1 -1 (5)
Using the ASIC parameters given in TABLE I, the ratio can be calculated (f T DC clk /f DCO clk ≃ 0.1068). If f DCO clk uses the largest frequency value of device, the other temporal parameters could be calculated by using the ratio equation (Eq.4). The result is shown in TABLE I. Since the DCO in prototype has the same number of frequency steps as the one in ASIC has, and the center code of the binary control code range corresponds to the nominal frequency of DCO, the value of N c could be calculated from Eq.( 2).

In this way, the FPGA emulator is designed as a propotionally scaled down prototype of the ASIC system, and it could operate with the same filter coeffients as those designed for ASIC.

III. EXPERIMENTAL RESULTS

A. System stability and performance

A FPGA emulator for a network with 16 clock generators is implemented on ALTERA CYCLONE II EP2C70 platform. Tests are done to compare the stability and performance of system with different filter coefficients. The phase error between the first and second clock generators in the network is observed. Fig. 6 presents the results of three tests with different groups of coefficients. The upper plot demonstrates a system with good performance. The maximum error is only ±2 units when it converges, where one unit corresponds to the resolution of PFD (∆T = 149.88ns). The middle plot shows a system which converges rapidly, while with worse performance when it is stable. The maximum error is about ±4 units. With some other coefficient values, the frequencies oscillate wildly and the system is no longer stable, like shown in the lower plot. With the help of this FPGA prototype, designers could choose the coefficients according to the specification of system and observe the results easily.

B. Prevention of undesired stable states

Due to cyclic (modular) nature of phase and a large number of degrees of freedom in the complex system, the system could have more than one stable states. In some of the states, all oscillators have equal frequency, but may have fixed nonzero phase difference compared with their neighbors. The stable state that the system will enter despends on the initial condition, thus is not controllable. Therefore, a configuration mechanism is necessary to garantee the actual setteled state of the system is that at which all the oscillators are synchronized both in frequency and in phase. by its 4 neighbors (node7, 10, 12, 15). In this case, when the network is stable, the rising edge of clock11 is about 1.8 us ahead of those of clock7 and clock10 but about 1.8 us late compared to edges of clock12 and clock15. 1.8 us is 12 times the resolution of PFD, which is a big value, while due to a nealy zero average value (one-fourth of T otal Err presented by the lowest plot in Fig. 7), the frequency of clock11 keeps unchanged, and similar phenomenon happens in other nodes. The network falls into an undesired stable state. It is known that these undisired modes can be eliminated if the network is unidirectional [START_REF] Pratt | Distributed Synchronous clocking[END_REF], which means each node receives the phase error information only from upper and left neighbors. Thus, the information is transmitted in one direction from the upper-left corner of the network to the lower-right corner. However, it has a drawback: Just like a traditional clock tree, any perturbation appearing in early nodes will propagate through the entire network. The clock in the area far from the reference clock will have a relatively poor quality compared with clocks near the reference. This drawback could be critical and could degrade the system performance if the network has a high order.

A solution has been presented in [START_REF] Zianbetov | All-digital PLL array provides reliable distributed clock for SOCs[END_REF]. The network is configured dynamically and works in two phases. In the first phase, the network is unidirectional configured in order to avoid undesirable stable states. When the phase errors are corrected and all the nodes are synchronized in phase, the network is reconfigured quickly as bidirectional mode. All the links are activated: This is the second phase. In this phase, each clock is coupled with its four neighboring clocks so that perturbations will be suppressed. The switching of the connectivity is implemented by programming dynamically the coefficients K wi in the loop filters presented in Fig. 5. A link can be activated or deactivated simply by assigning 1 or 0 to the corresponding coefficient K wi .

Fig. 8 shows the four phase errors after weight coefficients (K wi ) multiplication between node 11 and its neighboring nodes. During the period 0ms ∼ 30ms, the network is unidirectional configured, only the phase differences between the node and its left (node10) and upper node (node7) are considered. After 30ms, the network switches to bidirectional mode, all the four errors are taken into consideration.

Fig. 2 .

 2 Fig. 2. Architecture of ADPLL

Fig. 3 .

 3 Fig. 3. Architecture of PFD

Fig. 4 .

 4 Fig. 4. Transfer function of PFD

Fig. 5 .

 5 Fig. 5. Architecture of the loop filter

Fig. 7

 7 is a figure captured by the oscillator showing the clock generated by one node (node11) and those generated

Fig. 6 .

 6 Fig. 6. Phase error between node 1 and node 2

Fig. 7 .

 7 Fig. 7. clock of node11 and its 4 neighbors (configuration: bidirectional)

Fig. 8 .

 8 Fig. 8. phase errors between node11 and its neighboring nodes after weight coefficients multiplication

V. ACKNOWLEDGMENT This work has been funded by the French National Agency of Research (ANR) under grant ANR-07-ARFU-05.