# A Hilbert Scheme in Computer Vision C. Aholt, B. Sturmfels and R

## Comments

## Transcription

A Hilbert Scheme in Computer Vision C. Aholt, B. Sturmfels and R

A Hilbert Scheme in Computer Vision C. Aholt, B. Sturmfels and R. Thomas REPORT No. 40, 2010/2011, spring ISSN 1103-467X ISRN IML-R- -40-10/11- -SE+spring A HILBERT SCHEME IN COMPUTER VISION arXiv:1107.2875v1 [math.AG] 14 Jul 2011 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS Abstract. Multiview geometry is the study of two-dimensional images of three-dimensional scenes, a foundational subject in computer vision. We determine a universal Gröbner basis for the multiview ideal of n generic cameras. As the cameras move, the multiview varieties vary in a family of dimension 11n−15. This family is the distinguished component of a multigraded Hilbert scheme with a unique Borel-fixed point. We present a combinatorial study of ideals lying on that Hilbert scheme. 1. Introduction Computer vision is based on mathematical foundations known as multiview geometry [7, 9] or epipolar geometry [11, §9]. In that subject one studies the space of pictures of three-dimensional objects seen from n ≥ 2 cameras. Each camera is represented by a 3 × 4-matrix Ai of rank 3. The matrix specifies a linear projection from P3 to P2 , which is well-defined on P3 \{fi }, where the focal point fi is represented by a generator of the kernel of Ai . The space of pictures from the n cameras is the image of the rational map (1) φA : P3 99K (P2 )n , x 7→ (A1 x, A2 x, . . . , An x). The closure of this image is an algebraic variety, denoted VA and called the multiview variety of the given n-tuple of 3×4-matrices A = (A1 , A2 , . . . , An ). In geometric language, the multiview variety VA is the blow-up of P3 at the cameras f1 , . . . , fn , and we here study this threefold as a subvariety of (P2 )n . The multiview ideal JA is the prime ideal of all polynomials that vanish on the multiview variety VA . It lives in a polynomial ring K[x, y, z] in 3n unknowns (xi , yi , zi ), i = 1, 2, . . . , n, that serve as coordinates on (P2 )n . In Section 2 we give a determinantal representation of JA for generic A, and identify a universal Gröbner basis consisting of multilinear polynomials of degree 2, 3 and 4. This extends previous results of Heyden and Åström [12]. The multiview ideal JA has a distinguished initial monomial ideal Mn that is independent of A, provided the configuration A is generic. Section 3 gives an explicit description of Mn and shows that it is the unique Borel-fixed ideal with its Zn -graded Hilbert function. Following [3], we introduce the multigraded Hilbert scheme Hn which parametrizes Zn -homogeneous ideals in K[x, y, z] with the same Hilbert function as Mn . We show in Section 6 that, for n ≥ 3, Hn has a distinguished component of dimension 11n − 15 which compactifies the space of camera positions studied in computer vision. For two cameras, that space is an irreducible cubic hypersurface in H2 ' P8 . 1 2 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS Figure 1. A multiview variety VA for n = 3 cameras degenerates into six copies of P1 ×P2 and one copy of P1 ×P1 ×P1 . Section 4 concerns the case when n ≤ 4 and the focal points fi are among the coordinate points (1:0:0:0), . . . , (0:0:0:1). Here the multiview variety VA is a toric threefold, and its degenerations are parametrized by a certain toric Hilbert scheme inside Hn . Each initial monomial ideal of the toric ideal JA corresponds to a three-dimensional mixed subdivision as seen in Figure 1. A classification of such mixed subdivisions for n = 4 is given in Theorem 4.3. In Section 5 we place our n cameras on a line in P3 . Moving them very close to each other on that line induces a two-step degeneration of the form (2) trinomial ideal −→ binomial ideal −→ monomial ideal. We present an in-depth combinatorial study of this curve of multiview ideals. In Section 6 we finally define the Hilbert scheme Hn , and we construct the space of camera positions as a GIT quotient of a Grassmannian. Our main result (Theorem 6.3) states that the latter is an irreducible component of Hn . As a key step in the proof, the tangent space of Hn at the monomial ideal in (2) is computed and shown to have the correct dimension 11n−15. Thus, the curve (2) consists of smooth points on the distinguished component of Hn . For n ≥ 3, our Hilbert scheme has multiple components. This is seen from our classification of monomial ideals on H3 , which relates closely to [3, §5]. Acknowledgments. Aholt and Thomas thank Fredrik Kahl for hosting them at Lund in February 2011 and pointing them to the work of Heyden and Åström. They also thank Sameer Agarwal for introducing them to problems in computer vision and continuing to advise them in this field. Sturmfels thanks the Mittag-Leffler Institute, where this project started, and MATHEON Berlin for their hospitality. All three authors were partially supported by the US National Science Foundation. We are indebted to the makers of the software packages CaTS, Gfan, Macaulay2 and Sage which allowed explicit computations that were crucial in discovering our results. A HILBERT SCHEME IN COMPUTER VISION 3 2. A universal Gröbner basis Let K be any algebraically closed field, n ≥ 2, and consider the map φA defined as in (1) by a tuple A = (A1 , A2 , . . . , An ) of 3 × 4-matrices of rank 3 with entries in K. The subvariety VA = image(φA ) of (P2 )n is the multiview variety, and its ideal JA ⊂ K[x, y, z] is the multiview ideal. Note that JA is prime because its variety VA is the image under φA of an irreducible variety. We say that the camera T configuration A is generic if all 4 × 4-minors of T T the (4 × 3n)-matrix A1 A2 · · · An are non-zero. In particular, if A is generic then the focal points of the n cameras are pairwise distinct in P3 . For any subset σ = {σ1 , . . . , σs } ⊆ [n] we consider the 3s × (s + 4)-matrix Aσ1 pσ1 0 · · · 0 .. . 0 0 pσ2 A , Aσ := .σ2 .. .. .. .. .. . . . . Aσs 0 · · · 0 pσs T where pi := xi yi zi for i ∈ [n]. Assuming s ≥ 2, each maximal minor of Aσ is a homogeneous polynomial of degree s = |σ| that is linear in pi for i ∈ σ. Thus for s = 2, 3, . . . these polynomials are bilinear, trilinear, etc. The matrix Aσ and its maximal minors are considered frequently in multiview geometry [11, 12]. Recall that a universal Gröbner basis of an ideal is a subset that is a Gröbner basis of the ideal under all term orders. The following is the main result in this section. Theorem 2.1. If A is generic then the maximal minors of the matrices Aσ for 2 ≤ |σ| ≤ 4 form a universal Gröbner basis of the multiview ideal JA . The proof rests on a sequence of lemmas. Here is the most basic one. Lemma 2.2. The maximal minors of Aσ for |σ|≥2 lie in the prime ideal JA . Proof: If (p1 , . . . , pn ) ∈ (K 3 )n represents a point in image(φA ) then there exists a non-zero vector q ∈ K 4 and non-zero scalars c1 , . . . , cn ∈ K such that Ai q = ci pi for i = 1, 2, . . . , n. This means that the columns of Aσ are linearly dependent. Since Aσ has at least as many rows as columns, the maximal minors of Aσ must vanish at every point p ∈ VA . Later we shall see that when A is generic, JA has only one initial monomial ideal up to symmetry. We now identify that ideal. Let M n denote the ideal n n in K[x, y, z] generated by the quadrics x x , the 3 i j 2 3 cubics xi yj yk , and n the 4 quartics yi yj yk yl , where i, j, k, l runs over distinct indices in [n]. We fix the lexicographic term order ≺ on K[x, y, z] which is specified by x1 · · · xn y1 · · · yn z1 · · · zn . Our goal is to prove that the initial monomial ideal in≺ (JA ) is equal to Mn . We begin with the easier inclusion. 4 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS Lemma 2.3. If A is generic then Mn ⊆ in≺ (JA ). Proof: The generators of Mn are the quadrics xi xj , the cubics xi yj yk , and the quartics yi yj yk yl . By Lemma 2.2, it suffices to show that these are the initial monomials of maximal minors of A{ij} , A{ijk} and A{ijkl} respectively. For the quadrics this is easy. The matrix A{ij} is square and we have 1 Ai xi 0 2 A2i yi 0 Ai 3 Ai zi 0 A3i (3) det(A{ij} ) = det A1j 0 xj = detA2j xi xj + lex. lower terms. 2 Aj 0 yj A3j A3j 0 zj where Art is the rth row of At . The coefficient of xi xj is non-zero because A was assumed to be generic. For the cubics, we consider the 9 × 7-matrix Ai p i 0 0 (4) A{ijk} = Aj 0 pj 0 . Ak 0 0 p k Now, xi yj yk is the lexicographic initial monomial of the 7 × 7-determinant formed by removing the fourth and seventh rows of A{ijk} . Here we are using that, by genericity, the vectors A2i , A3i , A3j , A3k are linearly independent. Finally, for the quartic monomial yi yj yk yl we consider the 12 × 8 matrix Ai pi 0 0 0 Aj 0 p j 0 0 (5) A{ijkl} = Ak 0 0 pk 0 . Al 0 0 0 pl Removing the first row from each of the four blocks, we obtain an 8 × 8matrix whose determinant has yi yj yk yl as its lex. initial monomial. The next step towards our proof of Theorem 2.1 is to express the multiview variety VA as a projection of a diagonal embedding of P3 . This will put us in a position to utilize the results of Cartwright and Sturmfels in [3]. bi We extend each camera matrix Ai to an invertible 4×4-matrix Bi = Ai by adding a row bi at the top. Our diagonal embedding of P3 is the map (6) ψB : P3 → (P3 )n , x 7→ (B1 x, B2 x, . . . , Bn x). Let V B := image(ψB ) ⊂ (P3 )n and J B ⊂ K[w, x, y, z] its prime ideal. Here (wi : xi : yi : zi ) are coordinates on the ith copy of P3 and (w, x, y, z) are coordinates on (P3 )n . The ideal J B is generated by the 2 × 2-minors of w1 w2 wn −1 x1 −1 x2 B B · · · Bn−1 xn . (7) 1 y1 2 y2 yn z1 z2 zn A HILBERT SCHEME IN COMPUTER VISION 5 This is a 4 × n-matrix. Now consider the coordinate projection π : (P3 )n 99K (P2 )n , (wi : xi : yi : zi ) 7→ (xi : yi : zi ) for i = 1, . . . , n. The composition π ◦ ψB is a rational map, and it coincides with φA on its domain of definition P3 \{f1 , . . . , fn }. Therefore, VA = π(V B ) and (8) JA = J B ∩ K[x, y, z]. The polynomial ring K[w, x, y, z] admits the natural Zn -grading deg(wi ) = deg(xi ) = deg(yi ) = deg(zi ) = ei where ei is the standard unit vector in Rn . Under this grading, K[w, x, y, z]/J B has the multigraded Hilbert function u1 + · · · + un + 3 n N → N, (u1 , . . . , un ) 7→ . 3 The multigraded Hilbert scheme H4,n which parametrizes Zn -homogeneous ideals in K[w, x, y, z] with that Hilbert function was studied in [3]. More generally, the multigraded Hilbert scheme Hd,n represents degenerations of the diagonal Pd−1 in (Pd−1 )n for any d and n. For the general definition of multigraded Hilbert schemes see [10]. It was shown in [3] that Hd,n has a unique Borel-fixed ideal Zd,n . Here Borel-fixed means that Zd,n is stable under the action of B n where B is the group of lower triangular matrices in PGL(d, K). Here is what we shall need about the monomial ideal Z4,n . Lemma 2.4. (Cartwright-Sturmfels [3, §2] and Conca [4, §5]) (1) The unique Borel-fixed monomial ideal Z4,n on H4,n is generated by the following monomials where i, j, k, l are distinct indices in [n]: wi wj , wi xj , wi yj , xi xj , xi yj yk , yi yj yk yl . (2) This ideal Z4,n is the lexicographic initial ideal of J B when B is sufficiently generic. The lexicographic order here is w x y z with each block ordered lexicographically in increasing order of index. Using these results, it was deduced in [3] that all ideals on H4,n are radical and Cohen-Macaulay, and that H4,n is connected. We now use this distinguished Borel-fixed ideal Z4,n to prove the equality in Lemma 2.3. Lemma 2.5. If A is generic then Mn = in≺ (JA ). Proof: We fix the lexicographic term order ≺ on K[w, x, y, z] and its restriction to K[x, y, z]. Lemma 2.4 (1) shows that Mn = Z4,n ∩ K[x, y, z]. Lemma 2.4 (2) states that Z4,n = in≺ (J B ) when B is generic. The lexicographic order has the important property that it allows the operations of taking initial ideals and intersections to commute [5, Chapter 3]. Therefore, in≺ (JA ) = in≺ (J B ∩ K[x, y, z]) = in≺ (J B ) ∩ K[x, y, z] = Z4,n ∩ K[x, y, z] = Mn . 6 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS This identity is valid whenever the conclusion of Lemma 2.4 (2) is true. We claim that, for this to hold, the appropriate genericitynotion for B is that all 4 × 4-minors of the (4 × 4n)-matrix B1T B2T · · · BnT are non-zero. Indeed, under this hypothesis, the maximal minors of the 4s × (s + 4)-matrix Bσ1 p̃σ1 0 · · · 0 .. T . 0 0 p̃σ2 B w x y z for i ∈ [n], , where p̃ := Bσ := .σ2 i i i i i .. .. .. .. .. . . . . Bσs 0 · · · 0 p̃σs have non-vanishing leading coefficients. We see that Z4,n ⊆ in≺ (J B ) by reasoning akin to that in the proof of Lemma 2.3. The equality Z4,n = in≺ (J B ) is then immediate since Z4,n is the generic initial ideal of J B . Hence, for any generic camera positions A, we can add a row to Ai and get Bi that are “sufficiently generic” for Lemma 2.4 (2). This completes the proof. Proof of Theorem 2.1: Lemma 2.5 and the proof of Lemma 2.3 show that the maximal minors of the matrices Aσ for 2 ≤ |σ| ≤ 4 are a Gröbner basis of JA for the lexicographic term order. Each polynomial in that Gröbner basis is multilinear, thus the initial monomials remain the same for any term order satisfying xi yi zi for i = 1, 2, . . . , n. So, the minors form a Gröbner basis for that term order. The set of minors is invariant under permuting {xi , yi , zi } for each i. Moreover, the genericity of A implies that every monomial which can possibly appear in the support of a minor does so. Hence, these minors form a universal Gröbner basis of JA . Remark 2.6. Computer vision experts have known for a long time that multiview varieties VA are defined set-theoretically by the above multilinear constraints of degree at most 4. We refer to work of Heyden and Åström [12, 13]. What is new here is that these constraints define VA in the strongest possible sense: they form a universal Gröbner basis for the prime ideal JA . The n cameras are in linearly general position if no four focal points are coplanar and no three are collinear. While the number of multilinear polynomials in our lex Gröbner basis of JA is n2 + 3 n3 + n4 , far fewer suffice to generate the ideal JA when A is in linearly general position. Corollary 2.7. If A is in linearly general position then the ideal JA is minimally generated by n2 bilinear and n3 trilinear polynomials. Proof: This can be shown for n ≤ 4 by a direct calculation. Alternatively, these small cases are covered by transforming to the toric ideals in Section 4. First map the focal points of the cameras to the torus fixed focal points of the toric case, followed by multiplying each Ai by a suitable gi ∈ PGL(3, K). Now let n ≥ 5. For any three cameras i, j, k, the maximal minors of (4) are generated by only one such maximal minor modulo the three bilinear polynomials (3). Likewise, for any four cameras i, j, k and l, the maximal minors of (5) are generated by the trilinear and bilinear polynomials. A HILBERT SCHEME IN COMPUTER VISION 7 This implies that the resulting n2 + n3 polynomials generate JA , and, by restricting to two or three cameras, we see that they minimally generate. 3. The Generic Initial Ideal We now focus on combinatorial properties of our special monomial ideal Mn = xi xj , xi yj yk , yi yj yk yl : ∀ i, j, k, l ∈ [n] distinct . We refer to Mn as the generic initial ideal in multiview geometry because it is the lex initial ideal of any multiview ideal JA after a generic coordinate change via the group Gn where G = PGL(3, K). Indeed, consider any rank 3 matrices A1 , A2 , . . . , An ∈ K 3×4 with pairwise distinct kernels K{fi }. If g = (g1 , g2 , . . . , gn ) is generic in Gn then g ◦ A is generic in the sense that all 4 × 4-minors of the matrix (g1 A1 )T (g2 A2 )T · · · (gn An )T are non-zero. Thus, by the results of Section 2, Mn is the initial ideal of Jg◦A , or, using standard commutative algebra lingo, Mn is the generic initial ideal of JA . Since Mn is a squarefree monomial ideal, it is radical. Hence Mn is the intersection of its minimal primes, which are generated by subsets of the variables xi and yj . We begin by computing this prime decomposition. Proposition 3.1. The generic initial ideal Mn is the irredundant intersection of n3 + 2 n2 monomial primes. These are the monomial primes Pijk and Qij ⊆ K[x, y, z] defined below for any distinct indices i, j, k ∈ [n]: • Pijk is generated by x1 , . . . , xn and all yl with l 6∈ {i, j, k}, • Qij is generated by all xl for l 6= i and yl for l 6∈ {i, j}. Proof: Let L denote the intersection of all Pijk and Qij . Each monomial generator of Mn lies in Pijk and in Qij , so Mn ⊆ L. For the reverse inclusion, we will show that V (Mn ) is contained in V (L) = (∪V (Pijk )) ∪ (∪V (Qij )). Let (x̃, ỹ, z̃) be any point in the variety V (Mn ). First suppose x̃i = 0 for all i ∈ [n]. Since ỹi ỹj ỹk ỹl = 0 for distinct indices, there are at most three indices i, j, k such that ỹi , ỹj and ỹk are nonzero. Hence (x̃, ỹ, z̃) ∈ V (Pijk ). Next suppose x̃i 6= 0. The index i is unique because xi xj ∈ Mn for all j 6= i. Since x̃i ỹj ỹk = 0 for all j, k 6= i, we have ỹj 6= 0 for at most one index j 6= i. These properties imply (x̃, ỹ, z̃) ∈ V (Qij ). We regard the monomial variety V (Mn ) as a threefold inside the product of projective planes (P2 )n . If the focal points are distinct, VA has a Gröbner degeneration to the reducible threefold V (Mn ). The irreducible components of V (Mn ) are (9) V (Pijk ) ' P1 × P1 × P1 and V (Qij ) ' P2 × P1 . We find it convenient to regard (P2 )n as a toric variety, so as to identify it with its polytope (∆2 )n , a direct product of triangles. The components in (9) are 3-dimensional boundary strata of (P2 )n , and we identify them with faces of (∆2 )n . The corresponding 3-dimensional polytopes are the 3-cube and the triangular prism. The following three examples illustrate this view. 8 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS Figure 2. The variety of the generic initial ideal M2 seen as two adjacent facets of the 4-dimensional polytope ∆2 ×∆2 . Figure 3. The monomial variety V (M3 ) as a subcomplex of (∆2 )3 . Example 3.2. [Two cameras (n = 2)] The variety of M2 = hx1 i ∩ hx2 i is a hypersurface in P2 × P2 . The two components are triangular prisms P2 × P1 , which are glued along a common square P1 × P1 , as shown in Figure 2. Example 3.3. [Three cameras (n = 3)] The variety of M3 is a threefold in P2 × P2 × P2 . Its seven components are given by the prime decomposition M3 = hx1 , x2 , y1 i ∩ hx1 , x2 , y2 i ∩ hx1 , x3 , y1 i ∩ hx1 , x3 , y3 i ∩ hx2 , x3 , y2 i ∩ hx2 , x3 , y3 i ∩ hx1 , x2 , x3 i. The last component is a cube P1 × P1 × P1 , and the other six components are triangular prisms P2 × P1 . These are glued in pairs along three of the six faces of the cube. For instance, the two triangular prisms V (x1 , x2 , y1 ) and V (x1 , x3 , y1 ) intersect the cube V (x1 , x2 , x3 ) in the common square face V (x1 , x2 , x3 , y1 ) ' P1 × P1 . This polyhedral complex lives in the boundary of (∆2 )3 , and it shown in Figure 3. Compare this picture with Figure 1. A HILBERT SCHEME IN COMPUTER VISION 9 Example 3.4. [Four cameras (n = 4)] The variety V (M4 ) is a threefold in (P2 )4 , regarded as a 3-dimensional subcomplex in the boundary of the 8dimensional polytope (∆2 )4 . It consists of four cubes and twelve triangular prisms. The cubes share a common vertex, any two cubes intersect in a square, and each of the six squares is adjacent to two triangular prisms. From the prime decomposition in Proposition 3.1 we can read off the multidegree [17, §8.5] of the ideal Mn . Here and in what follows, we use the natural Zn -grading on K[x, y, z] given by deg(xi ) = deg(yi ) = deg(zi ) = ei . Each multiview ideal JA is homogeneous with respect to this Zn -grading. Corollary 3.5. The multidegree of the generic initial ideal Mn is equal to X X 1 1 + (10) C K[x, y, z]/Mn ; t) = t21 t22 · · · t2n · 2t ti tj tk t 1≤i,j≤n i j 1≤i<j<k≤n A more refined analysis also yields the Hilbert function in the Zn -grading. Theorem 3.6. The multigraded Hilbert function of K[x, y, z]/Mn equals X n u1 + · · · + un + 3 ui + 2 (11) Nn → N, (u1 , . . . , un ) 7→ − . 3 3 i=1 Proof: Fix u ∈ Nn . A K-basis Bu for (K[x, y, z]/Mn )u is given by all monomials xa y b z c 6∈ Mn such that a + b + c = u. Therefore, either (i) a = 0 and at most three components of b are non-zero; or (ii) a 6= 0, in which case only one ai can be non-zero and bj 6= 0 for at most one j ∈ [n]\{i}. We shall count the monomials in Bu . Monomials of type (i) look like y b z c , with at most three nonzero entries in b. Also, b determines c since ci = ui − bi for all i ∈ [n], and so we count the number of possibilities for y b . There are ui choices for bi 6= 0, and thus U := u1 + · · · + un many monomials in the set Y := {yibi : 1 ≤ bi ≤ ui , i = 1, . . . , n}. The factor y b in y b z c is the product of 0, 1, 2 or 3 monomials from Y with distinct subscripts. To resolve over-counting, consider a fixed index i. There are u2i ways of choosing two monomials from Y with subscript i and u3i ways of choosing three monomials from Y with subscript i. Also, there are u2i (U − ui ) ways of choosing two monomials from Y with subscript i and a third monomial with a different subscript. Hence, the number of choices for y b in y b z c is # " " X # n n n n X X X U U U ui U ui ui ui + + − + − −U + ui . 0 1 2 2 3 3 2 2 i=1 i=1 i=1 i=1 For case (ii) we count all monomials xa y b z c ∈ Bu with ai 6= 0 and all other aj = 0. It suffices to count the choices for the factor xa y b . For fixed i, there are ui2+1 monomials of the form xai i yibi with ai + bi ≤ ui and ai ≥ 1. Such b a monomial may be multiplied with yj j such that j 6= i and 0 ≤ bj ≤ uj . 10 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS This amounts to choosing zero or one monomial from Y\{yi , yi2 , . . . , yiui } for which there are 1 + U − ui choices. Hence, there are n n X X ui + 1 ui + 1 [1 + U ] − ui 2 2 i=1 i=1 monomials in Bu of type (ii). Adding the two expressions, we get X n n n X X U U ui ui ui + + (1 + U ) − ui − 2 3 1 1 3 i=1 i=1 i=1 n X ui + 2 U U =1+U + + + (1 + U )U − 2 3 3 i=1 X n U +3 ui + 2 = − . 3 3 i=1 |Bu | = 1 + U + Our analysis of Mn has the following implication for the multiview ideals JA . Note that these are Zn -homogeneous for any camera configuration A. Theorem 3.7. For an n-tuple of camera matrices A = (A1 , . . . , An ) with rank(Ai ) = 3 for each i, the multiview ideal JA has the Hilbert function (11) if and only if the focal points of the n cameras are pairwise distinct. Proof: The if-direction follows from the argument in the first paragraph of this section. If the n camera positions fi = ker(Ai ) are distinct in P3 then Mn is the generic initial ideal of JA , and hence both ideals have the same Zn -graded Hilbert function. For the only-if-direction we shall use: (12) If Q ∈ PGL(4, K) and AQ := (A1 Q, . . . , An Q), then JA = JAQ . This holds because Q defines an isomorphism on P3 and hence φA as in (1) has the same image in (P2 )n as φAQ . Suppose first that n = 2 and A1 and A2 have the same focal point and hence the same (three-dimensional) rowspace W . We can map W to the hyperplane {x1 = 0} by some Q ∈ PGL(4, K), and (12) ensures that JA = 0 C 0 C JAQ . Thus we may assume that A1 = and A2 = where 1 2 C1 and C2 are invertible matrices and 0 is a column of zeros. Choosing f1 = f2 = (1, 0, 0, 0) as the top row of B1 and B2 (as in Section 2), we have 1 0 1 0 −1 −1 B1 = , B2 = . 0 C1−1 0 C2−1 The ideal J B is generated by the 2 × 2 minors of the matrix (7) which is w1 w2 p1 (x1 , y1 , z1 ) q1 (x2 , y2 , z2 ) D= p2 (x1 , y1 , z1 ) q2 (x2 , y2 , z2 ) p3 (x1 , y1 , z1 ) q3 (x2 , y2 , z2 ) A HILBERT SCHEME IN COMPUTER VISION 11 where the pi ’s and qi ’s are linear polynomials. The ideal I generated by the 2 × 2 minors of the submatrix of D obtained by deleting the top row lies on the Hilbert scheme H3,2 from [3] and hence K[x, y, z]/I has Hilbert function u1 + u2 + 2 2 N → N, (u1 , u2 ) 7→ . 2 For (u1 , u2 ) = (1, 1), this has value 6. Since I ⊆ JA = J B ∩ K[x, y, z], the Hilbert function of K[x, y, z]/JA has value ≤ 6, while (11) evaluates to 8. If n > 2, we may assume without loss of generality that A1 and A2 have the same rowspace. The argument for n = 2 shows that JA = J B ∩ K[x, y, z] ⊇ I. The Hilbert function value of K[x, y, z]/JA in degree e1 + e2 is again 8, while the Hilbert function value of K[x, y, z]/I in degree e1 + e2 coincides with the value 6 for K[x1 , y1 , z1 , x2 , y2 , z2 ]/I. So we again conclude that K[x, y, z]/JA does not have Hilbert function (11). For G = PGL(3, K), the product Gn acts on K[x, y, z] by left-multiplication xi xi (g1 , . . . , gn ) · yi = gi yi . zi zi An ideal I in K[x, y, z] is said to be Borel-fixed if it is fixed under the induced action of B n where B is the subgroup of lower triangular matrices in G. Proposition 3.8. The generic initial ideal Mn is the unique ideal in K[x, y, z] that is Borel-fixed and has the Hilbert function (11) in the Zn -grading. Proof: The proof is analagous to that of [3, Theorem 2.1], where Zd,n plays the role of Mn . The ideal Mn is Borel-fixed because it is a generic initial ideal. The same approach as in [6, §15.9.2] can be used to prove this fact. The multidegree of any Zn -graded ideal is determined by its Hilbert series [17, Claim 8.54]. Thus any ideal I with Hilbert function (11) has multidegree (10). Let I be such a Borel-fixed ideal. This is a monomial ideal. Each maximum-dimensional associated prime P of I has multidegree either t21 t22 · · · t2n /(ti tj tk ) or t21 t22 · · · t2n /(t2i tj ), by [17, Theorem 8.53]. In the first case P is generated by 2n − 3 indeterminates, one associated with each of the three cameras i, j, k and two each from the other n − 3 cameras. Borelfixedness of I tells us that the generators indexed by each camera must be the most expensive variables with respect to the order ≺. Hence P = Pijk . Similarly, P = Qij in the case when P has multidegree t21 t22 · · · t2n /(t2i tj ). Every prime component of Mn is among the minimal associated primes √ of I. This yields the containments I ⊆ I ⊆ Mn . Since I and Mn have the same Zn -graded Hilbert function, the equality I = Mn holds. The Stanley-Reisner complex of a squarefree monomial ideal M in a polynomial ring K[t1 , . . . , ts ] is the simplicial complex on {1, . . . , s} whose facets are the sets [s]\σ where Pσ := {ti : i ∈ σ} is a minimal prime of M . A shelling of a simplicial complex is an ordering F1 , F2 , . . . , Fq of its facets 12 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS such that, for each 1 < j ≤ q, there exists a unique minimal face of Fj (with respect to inclusion) among the faces of Fj that are not faces of some earlier facet Fi , i < j; see [18, Definition 2.1]. If the Stanley-Reisner complex of M is shellable, then K[t1 , . . . , ts ]/M is Cohen-Macaulay [18, Theorem 2.5]. Proposition 3.9. The Stanley-Reisner complex of the generic initial ideal Mn is shellable. Hence the quotient ring K[x, y, z]/Mn is Cohen-Macaulay. Proof: This proof is similar to that for Zd,n given in [3, Corollary 2.6]. Let ∆n denote the Stanley-Reisner complex of the ideal Mn . By Proposition 3.1, there are two types of minimal primes for Mn , namely Pijk and Qij , which we describe uniformly as follows. Let P = (pij ) be the 3 × n matrix whose ith column is [xi yi zi ]T . For u ∈ {0, 1, 2}n define Pu := hpij : i ≤ uj , 1 ≤ j ≤ ni. Then the minimal primes Pijk of Mn are precisely the primes Pu as u varies over all vectors with three coordinates equal to one and the rest equal to two, and the minimal primes Qij are those Pu where u has one coordinate equal to zero, one coordinate equal to one and the rest equal to two. The facet of ∆n corresponding to the minimal prime Pu is then Fu := {pij : uj < i ≤ 3, 1 ≤ j ≤ n}. We claim that the ordering of the facets Fu induced by ordering the u’s lexicographically starting with (0, 1, 2, 2, . . . , 2) and ending with (2, 2, . . . , 2, 1, 0) is a shelling of ∆n . Consider the face ηu := {pij : j > 1, i = uj + 1 ≤ 2} of the facet Fu . We will prove that ηu is the unique minimal one among the faces of Fu that have not appeared in a facet Fu0 for u0 < u. Suppose G is a face of Fu that does not contain ηu . Pick an element puj +1,j ∈ ηu \G. Then j > 1, uj ≤ 1 and so if Fu is not the first facet in the ordering, then there exists i < j such that ui > 0 because u > (0, 1, 2, 2, . . . , 2) and of the form described above. Pick i such that i < j and ui > 0 and consider Fu+ej −ei = Fu \{puj +1,j } ∪ {pui ,i }. Then u + ej − ei < u and G is a face of Fu+ej −ei . Conversely, P 0 suppose P G is a face of Fu that is also a face of Fu0 where u0 < u. Since uj = uj , there exists some j > 1 such that u0j > uj . Therefore, G does not contain puj +1,j which belongs to ηu . Therefore, ηu is not contained in G. 4. A Toric Perspective In this section we examine multiview ideals JA that are toric. For an introduction to toric ideals we refer the reader to [20]. We now assume that, for each camera i, each of the four torus fixed points in P3 either is the camera position or is mapped to a torus fixed point in P2 . This implies n ≤ 4. We fix n = 4 and fi = ei for i = 1, 2, 3, 4. Up to permuting and rescaling columns, our assumption implies that the configuration A equals " # " # " # " # 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 A1 = , A2 = , A3 = , A4 = 0 1 0 0 . 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 For this camera configuration, the multiview ideal JA is indeed a toric ideal: A HILBERT SCHEME IN COMPUTER VISION 13 Proposition 4.1. The ideal JA is obtained by eliminating the diagonal unknowns w1 , w2 , w3 and w4 from the ideal of 2 × 2-minors of the 4 × 4-matrix w1 x 2 x 3 x 4 x1 w2 y3 y4 (13) y 1 y 2 w3 z 4 . z 1 z 2 z 3 w4 This toric ideal is minimally generated by six quadrics and four cubics: JA = hy1 y4 −x1 z4 , y3 x4 −x3 y4 , y2 x4 −x2 z4 , z1 y3 −x1 z3 , z2 x3 −x2 z3 , z1 y2 −y1 z2 , y2 z3 y4 − z2 y3 z4 , y1 z3 x4 − z1 x3 z4 , x1 z2 x4 − z1 x2 y4 , x1 y2 x3 − y1 x2 y3 i Proof: We extend Ai to a 4 × 4-matrix Bi as in Section 2 by adding the row bi = eTi . The Bi ’s are then all permutation matrices, and the matrix in (7) equals the matrix in (13). The ideal J B is generated by the 2 × 2 minors of that matrix of unknowns. The multiview ideal is JA = J B ∩ K[x, y, z]. We find the listed binomial generators by performing the elimination with a computer algebra package such as Macaulay2. Toric ideals are precisely those prime ideals generated by binomials and hence JA is a toric ideal. Remark 4.2. The normalized coordinate system in multiview geometry proposed by Heyden and Åström [12] is different from ours and does not lead to toric varieties. Indeed, if one uses the camera matrices in [12, §2.3], then JA is also generated by six quadrics and four cubics, but seven of the ten generators are not binomials. One of the cubic generators has six terms. In commutative algebra, it is customary to represent toric ideals by integer matrices. Given A ∈ Np×q with columns a1 , . . . , aq , the toric ideal of A is IA := htu − tv : Au = Av, u, v ∈ Nq i ⊂ K[t] := K[t1 , . . . , tq ], u where tu represents the monomial tu1 1 tu2 2 · · · tq q . If A0 is the submatrix of A obtained by deleting the columns indexed by j1 , . . . , js for some s < q, then the toric ideal IA0 equals the elimination ideal IA ∩ K[tj : j 6∈ {j1 , . . . , js }]; see [20, Prop. 4.13 (a)]. The integer matrix A for our toric multiview ideal JA in Proposition 4.1 is the following Cayley matrix of format 8 × 12: T A1 AT2 AT3 AT4 1 0 0 0 A = 0 1 0 0 0 0 1 0 0 0 0 1 where 1 = [1 1 1] and 0 = [0 0 0]. This matrix A is obtained from the following 8 × 16 matrix by deleting columns 1, 6, 11 and 16: I4 I4 I4 I4 1 0 0 0 0 1 0 0 (14) 0 0 1 0 0 0 0 1 14 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS Figure 4. Initial monomial ideals of the toric multiview variety correspond to mixed subdivisions of the truncated tetrahedron P . These have 4 cubes and 12 triangular prisms. The vectors 1 and 0 now have length four, I4 is the 4 × 4 identity matrix and we assume that the columns of (14) are indexed by w1 , x1 , y1 , z1 , x2 , w2 , y2 , z2 , x3 , y3 , w3 , z3 , x4 , y4 , z4 , w4 . The matrix (14) represents the direct product of two tetrahedra, and its toric ideal is known (by [20, Prop. 5.4]) to be generated by the 2 × 2 minors of (13). Its elimination ideal in the ring K[x, y, z] is IA , and hence JA = IA . The matrix A has rank 7 and its columns determine a 6-dimensional polytope conv(A) with 12 vertices. The normalized volume of conv(A) equals 16, and this is the degree of the 6-dimensional projective toric variety in P11 defined by JA . In our context, we don’t care for the 6-dimensional variety in P11 but we are interested in the threefold in P2 ×P2 ×P2 ×P2 cut out by JA . To study this combinatorially, we apply the Cayley trick. This means we replace the 6-dimensional polytope conv(A) by the 3-dimensional polytope P = conv(AT1 ) + conv(AT2 ) + conv(AT3 ) + conv(AT4 ). This is the Minkowski sum of the four triangles that form the facets of the standard tetrahedron. Equivalently, P is the scaled tetrahedron 4∆3 with its vertices sliced off. Triangulations of A correspond to mixed subdivisions of P . Each 6-simplex in A becomes a cube or a triangular prism in P . Each mixed subdivision has four cubes P1 × P1 × P1 and twelve triangular prisms P2 × P1 . Such a mixed subdivision of P is shown in Figure 4. Note the similarities and differences relative to the complex V (M4 ) in Example 3.4. We worked out a complete classification of all mixed subdivisions of P : Theorem 4.3. The truncated tetrahedron P has 1068 mixed subdivisions, one for each triangulation of the Cayley polytope conv(A). Precisely 1002 of the 1068 triangulations are regular. The regular triangulations form 48 symmetry classes, and the non-regular triangulations form 7 symmetry classes. A HILBERT SCHEME IN COMPUTER VISION 15 Figure 5. The dual graph of the mixed subdivision given by Y1 . We offer a brief discussion of this result and how it was obtained. Using the software Gfan [15], we found that IA has 1002 distinct monomial initial ideals. These ideals fall into 48 symmetry classes under the natural action of (S3 )4 o S4 on K[x, y, z] where the i-th copy of S3 permutes the variables xi , yi , zi , and S4 permutes the labels of the cameras. The matrix A being unimodular, each initial ideal of IA is squarefree and each triangulation of A is unimodular. To calculate all non-regular triangulations, we used the bijection between triangulations and A-graded monomial ideals in [20, Lemma 10.14]. Namely, we ran a second computation using the software package CaTS [14] that lists all A-graded monomials ideals, and we found their number to be 1068, and hence A has 66 non-regular triangulations. The 48 distinct initial monomial ideals of the toric multiview ideal JA can be distinguished by various invariants. First, their numbers of generators range from 12 to 15. There is precisely one initial ideal with 12 generators: Y1 = h y1 z2 , z1 y3 , x1 z4 , z2 x3 , y2 x4 , x3 y4 , x1 y2 x3 , z1 y2 x3 , x1 z2 x4 , z1 x3 z4 , z2 y3 x4 , z2 y3 z4 i. At the other extreme, there are two classes of initial ideals with 15 generators. These are the only classes having quartic generators, as all ideals with ≤ 14 generators require only quadrics and cubics. A representative is Y2 = h z1 y2 , x1 z3 , x1 z4 , x2 z3 , y2 x4 , y3 x4 , y1 z2 x3 y4 , x1 y2 x3 , x1 z2 x3 , x1 z2 x4 , x4 z2 y1 , y1 z3 x4 , y1 z3 y4 , y2 x3 y4 , y2 z3 y4 i. All non-regular A-graded monomial ideal have 14 generators. One of them is Y3 = h z1 y2 , z1 y3 , x1 z4 , x2 z3 , x2 z4 , y3 x4 , x1 y2 z3 , y1 x2 y3 , x1 y2 x4 , x1 z2 x4 , x1 z3 x4 , y1 z3 x4 , y2 z3 x4 , y2 z3 y4 i. 16 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS A more refined combinatorial invariant of the 55 types is the dual graph of the mixed subdivision of P . The 16 vertices of this graph are labeled with squares and triangles to denote cubes and triangular prisms respectively, and edges represent common facets. The graph for Y1 is shown in Figure 5. For complete information on the classification in Theorem 4.3 see the website www.math.washington.edu/∼aholtc/HilbertScheme. That website also contains the same information for the toric multiview variey in the easier case of n = 3 cameras. Taking A1 , A2 and A3 as camera matrices, the corresponding Cayley matrix has format 7 × 9 and rank 6: 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 T A1 AT2 AT3 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 A = = 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 This is the transpose of the matrix A{123} in (4) when evaluated at x1 = y1 = · · · = z3 = 1. The corresponding 6-dimensional Cayley polytope conv(A) has 9 vertices and normalized volume 7, and the toric multiview ideal equals (15) JA = hz1 y3 − x1 z3 , z2 x3 − x2 z3 , z1 y2 − y1 z2 , x1 y2 x3 − y1 x2 y3 i. We note that the quadrics cut out VA plus an extra component P1 × P1 × P1 : (16) hz1 y3 − x1 z3 , z2 x3 − x2 z3 , z1 y2 − y1 z2 i = JA ∩ hz1 , z2 , z3 i This equation is precisely [12, Theorem 5.6] but written in toric coordinates. The toric ideal JA has precisely 20 initial monomial ideals, in three symmetry classes, one for each mixed subdivision of the 3-dimensional polytope P = conv(AT1 ) + conv(AT2 ) + conv(AT3 ). Thus P is the Minkowski sum of three of the four triangular facets of the regular tetrahedron. Each mixed subdivision of P uses one cube P1 ×P1 ×P1 and six triangular prisms P2 ×P1 . A picture of one of them is seen in Figure 1. Remark 4.4. Our toric study in this section is universal in the sense that every multiview variety VA for n ≤ 4 cameras in linearly general position in P3 is isomorphic to the toric multiview variety under a change of coordinates in (P2 )n . This fact can be proved using the coordinate systems for the Grassmannian Gr(4, 3n) furnished by the construction in [21, §4]. Here is how it works for n = 4. The coordinate change via PGL(3, K)4 gives 0 0 0 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ∗ ∗ ∗ ∗ T T T T (17) A1 A2 A3 A4 = ∗ ∗ ∗ ∗ ∗ ∗ 0 0 0 ∗ ∗ ∗ , ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 0 0 0 A HILBERT SCHEME IN COMPUTER VISION 17 where the 3 × 3-matrices indicated by the stars in the four blocks are invertible. Now, the 4 × 12-matrix (17) gives a support set Σ that satisfies the conditions in [21, Proposition 3.1]. The corresponding Zariski open set UΣ of the Grassmannian Gr(4, 12) is non-empty. In fact, by [21, Remark 4.9(a)], the set UΣ represents configurations whose cameras f1 , f2 , f3 , f4 are not coplanar. Now, Theorem 4.6 in [21] completes our proof because (the universal Gröbner basis of) the ideal JA depends only on the point in UΣ ⊂ Gr(4, 12) represented by (17) and not on the specific camera matrices A1 , . . . , A4 . 5. Degeneration of Collinear Cameras In this section we consider a family of collinear camera positions. The degeneration of the associated multiview variety will play a key role in proving our main results in Section 6, but they may be of independent interest. Collinear cameras have been studied in computer vision, for example in [11]. Let ε be a parameter and fix the configuration A(ε) := (A1 , . . . , An ) where 1 1 0 0 0 1 0 Ai := 1 εn−i 0 0 1 The focal point of camera i is fi = (−1 : 1 : 1 : εn−i ) and hence the n cameras given by A(ε) are collinear in P3 . Note that these camera matrices stand in sharp contrast to those for which A is generic which was the focus of Sections 2 and 3. They also differ from the toric situation in Section 4. We consider the multiview ideal JA(ε) in the polynomial ring K(ε)[x, y, z], where K(ε) is the field of rational functions in ε with coefficients in K. Then JA(ε) has the Hilbert function (11), by Theorem 3.7. Let Gn be the set of polynomials in K(ε)[x, y, z] consisting of the n2 quadratic polynomials (18) and the 3 (19) n 3 xi yj − xj yi for 1 ≤ i < j ≤ n cubic polynomials below for all choices of 1 ≤ i < j < k ≤ n: (εn−k − εn−i )xi zj xk + (εn−j − εn−k )zi xj xk + (εn−i − εn−j )xi xj zk (εn−k − εn−i )yi zj yk + (εn−j − εn−k )zi yj yk + (εn−i − εn−j )yi yj zk (εn−k − εn−i )yi zj xk + (εn−j − εn−k )zi yj xk + (εn−i − εn−j )yi xj zk Let Ln be the ideal generated by (18) and the following binomials from the first two terms in (19): * + x i z j x k − zi x j x k , Ln := xi yj − xj yi : 1≤i<j≤n + yi zj yk − zi yj yk , : 1≤i<j<k≤n . yi zj xk − zi yj xk Let Nn be the ideal generated by the leading monomials in (18) and (19): Nn := xi yj : 1≤i<j≤n + xi zj xk , yi zj yk , yi zj xk : 1≤i<j<k≤n . 18 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS The main result in this section is the following construction of a two-step flat degeneration JA(ε) → Ln → Nn . This gives an explicit realization of (2). We note that VA(ε) can be seen as a variant of the Mustafin varieties in [2]. Theorem 5.1. The three ideals JA(ε) , Ln and Nn satisfy the following: (a) The multiview ideal JA(ε) is generated by the set Gn . (b) The binomial ideal Ln equals the special fiber of JA(ε) for ε = 0. (c) The monomial ideal Nn is the initial ideal of Ln , in the Gröbner basis sense, with respect to the lexicographic term order with x y z. The rest of this section is devoted to explaining and proving these results. Let us begin by showing that Gn is a subset of JA(ε) . The determinant of Ai p i 0 A(ε){ij} = Aj 0 pj equals (εn−j −εn−i )(xi yj −xj yi ). Hence JA(ε) contains (18), by the argument in Lemma 2.2. Similarly, for any 1≤i<j<k≤n, consider the 9 × 7 matrix 1 1 0 0 xi 0 0 1 n−i 0 1 0 yi 0 0 ε 0 0 1 zi 0 0 1 1 0 0 0 xj 0 1 0 1 0 0 yj 0 A(n){ijk} = n−j . ε 0 0 1 0 z 0 j 1 1 0 0 0 0 x k 1 0 1 0 0 0 yk εn−k 0 0 1 0 0 zk The three cubics (19), in this order and up to sign, are the determinants of the 7 × 7 submatrices of A(ε){ijk} obtained by deleting the rows corresponding to yj and yk , the rows corresponding to xj and xk , and the rows corresponding to xi and yk respectively. We conclude that Gn lies in JA(ε) . We next discuss part (b) of Theorem 5.1. Every rational function c(ε) ∈ K(ε) has a unique expansion as a Laurent series c1 εa1 + c2 εa2 + · · · where ci ∈ K and a1 < a2 < · · · are integers. The function val : K(ε) → Z given by c(ε) 7→ a1 is then a valuation on K(ε), and K[[ε]] = {c ∈ K(ε) : val(c) ≥ 0} is its valuation ring. The unique maximal ideal in K[[ε]] is m = hc ∈ K(ε) : val(c) > 0i. The residue field K[[ε]]/m is isomorphic to K, so there is a natural map K[[ε]] → K that represents the evaluation at ε = 0. The special fiber of an ideal I ⊂ K(ε)[x, y, z] is the image of I ∩ K[[ε]][x, y, z] under the induced map K[[ε]][[x, y, z] → K[x, y, z]. The special fiber is denoted in(I). It can be computed from I by a variant of Gröbner bases (cf. [16, §2.4]). What we are claiming in Theorem 5.1 (b) is the following identify in(JA(ε) ) = Ln in K[x, y, z]. A HILBERT SCHEME IN COMPUTER VISION 19 It is easy to see that the left hand side contains the right hand side: indeed, by multiplying the trinomials in (19) by εk−n and then evaluating at ε = 0, we obtain the binomial cubics among the generators of Ln . Finally, what is claimed in Theorem 5.1 (c) is the following identity in≺ (Ln ) = Nn in K[x, y, z]. Here, in≺ (Ln ) is the lexicographic initial ideal of Ln , in the usual Gröbner basis sense. Again, the left hand side contains the right hand side because the initial monomials of the binomial generators of Ln generate Nn . Note that Nn is distinct from the generic initial ideal Mn . Even though Mn played a prominent role in Sections 2 and 3, the ideal Nn will be more useful in Section 6. The reason is that Mn is the most singular point on the Hilbert scheme Hn while, as we shall see, Nn is a smooth point on Hn . In summary, what we have shown thus far is the following inclusion: (20) Nn ⊆ in≺ in(JA(ε) ) We seek to show that equality holds. Our proof rests on the following lemma. Lemma 5.2. The monomial ideal Nn has the Zn -graded Hilbert function (11). Proof: Let u = (u1 , . . . , un ) ∈ Nn , and let Bu be the set of all monomials of multidegree u in K[x, y, z] which are not in Nn . We need to show that X n u1 + · · · + un + 3 ui + 2 |Bu | = − . 3 3 i=1 It can be seen from the generators of Nn that the monomials in Bu are of the form z a y b xc z d for a, b, c, d ∈ Nn such that u = a + b + c + d and a = (a1 , . . . , ai , 0, . . . , 0) b = (0, . . . , 0, bi , . . . , bj , 0, . . . , 0) c = (0, . . . , 0, cj , . . . , ck , 0, . . . , 0) d = (0, . . . , 0, dk , . . . , dn ) for some triple i, j, k with 1 ≤ i ≤ j ≤ k ≤ n. We count the monomials in Bu using a combinatorial “stars and bars” argument. Each monomial can be formed in the following way. Suppose there are u1 + · · · + un + 3 blank spaces laid left to right. Fill exactly three spaces with bars. This leaves u1 + · · · + un open blanks to fill in, which is the total degree of a monomial in Bu . The three bars separate the blanks into four compartments, some possibly empty. From these compartments we greedily form a, b, c, and d to make z a y b xc z d as described below. In what follows, ? is used as a placeholder symbol. Fill the first u1 blanks with the symbol ?1 , the next u2 blanks with ?2 , and continue to fill up until the last un blanks are filled with ?n . Now we pass once more through these symbols and replace each ?i with either xi , yi , or zi such that all variables in the first compartment are z’s, those in the second are y’s, then x’s and in the fourth compartment z’s. Removing the bars gives z a y b xc z d in Bu . 20 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS u1 + · · · + un + 3 ways of choosing the three bars. The 3 monomials in Bu are overcounted only when i = j = k if zi appears in both the first and fourth compartments. Indeed, in such cases if we require a i = 0, the monomial is uniquely represented, so we are overcounting by the ui + 2 choices when ai 6= 0. 3 There are We are now prepared to derive the main result of this section. Proof of Theorem 5.1: Lemma 5.2 and Theorem 3.7 tell us that Nn and JA(ε) have the same Zn -graded Hilbert function (11). We also know from [16, §2.4] that in(JA(ε) ) has the same Hilbert function, just as passing to an initial monomial ideal for a term order preserves Hilbert function. Hence the equality Nn ⊆ in≺ in(JA(ε) ) holds in (20). This proves parts (b) and (c). We have shown that Gn is a Gröbner basis for the homogeneous ideal JA(ε) in the valuative sense of [16, §2.4]. This implies that Gn generates JA(ε) . Remark 5.3. The polyhedral subcomplexes of (∆2 )n defined by the binomial ideal Ln and the monomial ideal Nn are combinatorially interesting. For instance, Ln has prime decomposition I3 ∩ I4 ∩ · · · ∩ In ∩ In+1 , where It := h xi , yi : i = t, t + 1, . . . , n i + h xi yj − xj yi : 1 ≤ i < j < t i + h xi zj − xj zi , yi zj − yj zi : 1 ≤ i < j < t − 1 i. The monomial ideal Nn is the intersection of in≺ (It ) for t = 3, . . . , n + 1. 6. The Hilbert Scheme We define Hn to be the multigraded Hilbert scheme which parametrizes all Zn -homogeneous ideals in K[x, y, z] with the Hilbert function in (11). According to the general construction given in [10], Hn is a projective scheme. The ideals JA and in≺ (JA ) for n distinct camera positions, as well as the combinatorial ideals Mn , Ln and Nn all correspond to closed points on Hn . Our Hilbert scheme Hn is closely related to the Hilbert scheme H4,n which was studied in [3]. We already utilized results from that paper in our proof of Theorem 2.1. Note that H4,n parametrizes degenerations of the diagonal P3 in (P3 )n while Hn parametrizes blown-up images of that P3 in (P2 )n . Let G = PGL(3, K) and B ⊂ G the Borel subgroup of lower-triangular 3 × 3 matrices modulo scaling. The group Gn acts on K[x, y, z] and this induces an action on the Hilbert scheme Hn . Our results concerning the ideal Mn in Section 3 imply the following corollary, which summarizes the statements analogous to Theorem 2.1 and Corollaries 2.4 and 2.6 in [3]. Corollary 6.1. The multigraded Hilbert scheme Hn is connected. The point representing the generic initial ideal Mn lies on each irreducible component of Hn . All ideals that lie on Hn are radical and Cohen-Macaulay. A HILBERT SCHEME IN COMPUTER VISION 21 In particular, every monomial ideal in Hn is squarefree and can hence be identified with its variety in (P2 )n , or, equivalently, with a subcomplex in the product of triangles (∆2 )n . One of the first questions one asks about any multigraded Hilbert scheme, including Hn , is to list its monomial ideals. This task is easy for the first case, n = 2. The Hilbert scheme H2 parametrizes Z2 -homogeneous ideals in K[x, y, z] having Hilbert function u1 + u2 + 3 u1 + 2 u2 + 2 2 h2 : N → N, (u1 , u2 ) 7→ − − . 3 3 3 There are exactly nine monomial ideals on H2 , namely hx1 x2 i, hx1 y2 i, hx1 z2 i, hy1 x2 i, hy1 y2 i, hy1 z2 i, hz1 x2 i, hz1 y2 i, hz1 z2 i. In fact, the ideals on H2 are precisely the principal ideals generated by bilinear forms, and H2 is isomorphic to an 8-dimensional projective space H2 = {hc0 x1 x2 + c1 x1 y2 + · · · + c8 z1 z2 i : (c0 : c1 : · · · : c8 ) ∈ P8 }. The principal ideals JA which actually arise from two cameras form a cubic hypersurface in this H2 ' P8 . To see this, we write Aji for the j-th row of the i-th camera matrix and [Aji11 Aji22 Aji33 Aji44 ] for the 4 × 4-determinant formed by four such row vectors. The bilinear form can be written as c0 c3 c6 x1 xT2 F x1 = x2 y2 z2 c1 c4 c7 y1 , c2 c5 c8 z1 where F is the fundamental matrix [11]. In terms of the camera matrices, [A21 A31 A22 A32 ] −[A11 A31 A22 A32 ] [A11 A21 A22 A32 ] [A11 A31 A12 A32 ] −[A11 A21 A12 A32 ] . (21) F = −[A21 A31 A12 A32 ] 2 3 1 2 [A1 A1 A2 A2 ] −[A11 A31 A12 A22 ] [A11 A21 A12 A22 ] This matrix has rank ≤ 2, and every 3 × 3-matrix of rank ≤ 2 can be written in this form for suitable camera matrices A1 and A2 of size 3 × 4. The formula in (21) defines a map (A1 , A2 ) 7→ F from pairs of camera matrices with distinct focal points into the Hilbert scheme H2 . The closure of its image is a compactification of the space of camera positions. We now precisely define the corresponding map for arbitrary n ≥ 2. The construction is inspired by the construction due to Thaddeus discussed in [3, Example 7]. Let Gr(4, 3n) denote the Grassmannian of 4-dimensional linear subspaces of K 3n . The n-dimensional algebraic torus (K ∗ )n acts on this Grassmannian by scaling the coordinates on K 3n , where the ith factor K ∗ scales the coordinates indexed by 3i − 2, 3i − 1 and 3i. Thus, if we represent each point in Gr(4, 3n) as the row space of a (4 × 3n)-matrix AT1 AT2 · · · ATn , then λ = (λ1 , . . . , λn ) ∈ (K ∗ )n sends this matrix to λ1 AT1 λ2 AT2 · · · λn ATn . The multiview ideal JA is invariant under this action by (K ∗ )n . In symbols, Jλ◦A = JA . In the next lemma, GIT stands for geometric invariant theory. 22 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS Lemma 6.2. The assignment A 7→ JA defines an injective rational map γ from a GIT quotient Gr(4, 3n)//(K ∗ )n to the multigraded Hilbert scheme Hn . Proof: For the proof it suffices to check that JA = 6 JA0 whenever A and A0 are generic camera configurations that are not in the same (K ∗ )n -orbit. We call γ the camera map. Since we need γ only as a rational map, the choice of linearization does not matter when we form the GIT quotient. The closure of its image in Hn is well-defined and independent of that choice of linearization. We define the compactified camera space, for n cameras, to be Γn := γ(Gr(4, 3n)//(K ∗ )n ) ⊆ Hn . The projective variety Γn is a natural compactification of the parameter space studied by Heyden in [13]. Since the torus (K ∗ )n acts on Gr(4, 3n) with a one-dimensional stabilizer, Lemma 6.2 implies that the compactified space of n cameras has the dimension we expect from [13], namely, dim(Γn ) = dim(Gr(4, 3n)) − (n − 1) = 4(3n − 4) − (n − 1) = 11n − 15. We regard the following theorem as the main result in this paper. Theorem 6.3. For n ≥ 3, the compactified camera space Γn appears as a distinguished irreducible component in the multigraded Hilbert scheme Hn . Note that the same statement if false for n = 2: Γ2 is not a component of H3 ' P8 . It is the hypersurface consisting of the fundamental matrices (21). Proof: By definition, the compactified camera space Γn is a closed subscheme of Hn . The discussion above shows that the dimension of any irreducible component of Hn that contains Γn is no smaller than 11n − 15. We shall now prove the same 11n − 15 as an upper bound for the dimension. This is done by exhibiting a point in Γn whose tangent space in the Hilbert scheme Hn has dimension 11n − 15. This will imply the assertion. For any ideal I ∈ Hn , the tangent space to the Hilbert scheme Hn at I is the space of K[x, y, z]-module homomorphisms I → K[x, y, z]/I of degree 0. In symbols, this space is Hom(I, K[x, y, z]/I)0 . The K-dimension of the tangent space provides an upper bound for the dimension of any component on which I lies. It remains to specifically identify a point on Γn that is smooth on Hn , an ideal which has tangent space dimension exactly 11n−15. It turns out that the monomial ideal Nn described in the previous section has this desired property. Lemmas 6.4 and 6.5 below give the details. Lemma 6.4. The ideals Ln and Nn from the previous section lie in Γn . Proof: The image of γ in Hn consists of all multiview ideals JA , where A runs over configurations of n distinct cameras, by Theorem 3.7. Let A(ε) denote the collinear configuration in Section 5, and consider any specialization of ε to a non-zero scalar in K. The resulting ideal JA(ε) is a K-valued point of Γn , for any ε ∈ K\{0}. The special fiber JA(0) = Ln is in the Zariski closure of these points, because, locally, any regular function vanishing on A HILBERT SCHEME IN COMPUTER VISION 23 the coordinates of JA(ε) for all ε 6= 0 will vanish for ε = 0. We conclude that Ln is a K-valued point in the projective variety Γn . Likewise, since Nn = in≺ (Ln ) is an initial monomial ideal of Ln , it also lies on Γn . Lemma 6.5. The tangent space of the multigraded Hilbert scheme Hn at the point represented by the monomial ideal Nn has dimension 11n − 15. Proof: The tangent space at Nn equals Hom(Nn , K[x, y, z]/Nn )0 . We shall present a basis for this space that is broken into three distinct classes: those homomorphisms that act nontrivially only on the quadratic generators, those that act nontrivially only on the cubics, and those with a mix of both. Each K[x, y, z]-module homomorphism ϕ : Nn → K[x, y, z]/Nn below is described by its action on the minimal generators of Nn . Any generator not explicitly mentioned is mapped to 0 under ϕ. One checks that each is in fact a well-defined K[x, y, z]-module homomorphism from Nn to K[x, y, z]/Nn . Class I: For each 1 ≤ i < n, we define the following maps • αi : xi yk 7→ yi yk for all i < k ≤ n, • βi : xi yi+1 7→ xi+1 yi . For each 1 < k ≤ n, we define the following map • γk : xi yk 7→ xi xk for all 1 ≤ i < k. We define two specific homomorphisms • δ1 : x1 y2 7→ y1 z2 , • δ2 : xn−1 yn 7→ zn−1 xn . Class II: For each 1 < j < n, we define the following maps. Each homomorphism is defined on every pair (i, k) such that 1 ≤ i < j < k ≤ n. • ρj : xi zj xk 7→ xi xj xk and yi zj xk 7→ yi xj xk , • σj : xi zj xk 7→ xi xj zk and yi zj xk 7→ yi xj zk , • τj : xi zj xk 7→ xi zj zk and yi zj xk 7→ yi zj zk , • νj : yi zj xk 7→ yi yj xk and yi zj yk 7→ yi yj yk , • µj : yi zj xk 7→ zi yj xk and yi zj yk 7→ zi yj yk , • πj : yi zj xk 7→ zi zj xk and yi zj yk 7→ zi zj yk . Class III: For each 1 ≤ i < n, we define the map • i : xi yk 7→ zi yk and xi zj xk 7→ zi zj xk for i < k ≤ n and i < j < k. For each 1 < k ≤ n, we define the map • ζk : xi yk 7→ xi zk and yi zj yk 7→ yi zj zk for 1 ≤ i < k and i < j < k. All these maps are linearly independent over the field K. There are n − 1 maps each of type αi , βi , γk , i , and ζk , for a total of 5(n − 1) different homomorphisms. Each subclass of maps in class II has n − 2 members, adding 6(n − 2) more homomorphisms. Finally adding δ1 and δ2 , we arrive at the total count of 5(n − 1) + 6(n − 2) + 2 = 11n − 15 homomorphisms. We claim that any K[x, y, z]-module homomorphism Nn → K[x, y, z]/Nn can be recognized as a K-linear combination of those from the three classes described above. To prove this, suppose that ϕ : Nn → K[x, y, z]/Nn is a 24 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS module homomorphism. For 1 ≤ i < k ≤ n, we can write ϕ(xi yk ) as a linear combination of monomials of multidegree ei + ek which are not in Nn . By subtracting appropriate multiples of αi , i , γk , and ζk , we can assume that ϕ(xi yk ) = a yi xk + b yi zk + c zi xk + d zi zk for some scalars a, b, c, d ∈ K. We show that this can be written as a linear combination of the maps described above by considering a few cases. In the first case we assume i + 1 < k. We use K[x, y, z]-linearity to infer ϕ(xi yi+1 yk ) = a yi yi+1 xk +b yi yi+1 zk +c zi yi+1 xk +d zi yi+1 zk = yk ϕ(xi yi+1 ). Specifically, yk divides the middle polynomial. But none of the four monomials are zero in the quotient K[x, y, z]/Nn . Hence, 0 = a = b = c = d. For the subsequent cases we assume k = i + 1. This allows us to further assume that a = 0, since we can subtract off a βi (xi yi+1 ). Now suppose that we have strict inequality k < n. As before, the K[x, y, z]-linearity of ϕ gives ϕ(xi yk yn ) = d zi zk yn = yk ϕ(xi yn ). Specifically, yk divides the middle term. Hence, d = 0. Similarly, c = 0: ϕ(xi yk zk xn ) = c zi xk zk xn = yk ϕ(xi zk xn ). Suppose we further have the strict inequality 1 < i. Then necessarily b = 0: ϕ(y1 zi xi yk ) = b y1 zi yi zk = xi ϕ(y1 zi yk ). However, if i = 1 and k = 2, we have that ϕ(x1 y2 ) = b δ1 (x1 y2 ). The only case that remains is k = n and i = n − 1. Here, we can also assume that c = 0 by subtracting c δ2 (xn−1 yn ). We will show that d = 0 = b by once more appealing to the fact that ϕ is a module homomorphism: ϕ(x1 xn−1 yn ) = d x1 zn−1 zn = xn−1 ϕ(x1 yn ), which gives d = 0. This subsequently implies the desired b = 0, because ϕ(y1 xi zi yn ) = b y1 yi zi zn = xi ϕ(y1 zi yn ). This has finally put us in a position where we can assume that ϕ(xi yk ) = 0 for all 1 ≤ i < k ≤ n. To finish the proof that ϕ is a linear combination of the 11n − 15 classes described above, we need to examine what happens with the cubics. Suppose 1 ≤ i < j < k ≤ n, and consider ϕ(yi zj xk ). This can be written as a linear sum of the 17 standard monomials of multidegree ei + ej + ek which are not in Nn . Explicitly, these standard monomials are: xi xj xk , yi yj xk , zi xj xk , zi yj zk , x i x j zk , yi yj yk , zi xj zk , zi zj xk , x i zj z k , yi yj zk , zi yj xk , zi zj yk , yi xj xk , yi xj zk y i zj zk , zi yj yk , zi zj zk . By subtracting off multiples of the maps ρj , σj , τj , νj , µj , and πj , we can assume that this is a sum of the 11 monomials remaining after removing yi xj xk , yi xj zk , yi zj zk , yi yj xk , zi yj xk , and zi zj xk . However, now note that ϕ(xi yi zj xk ) = xi ϕ(yi zj xk ) = yi ϕ(xi zj xk ). A HILBERT SCHEME IN COMPUTER VISION 25 This means that for every one of the 11 monomials m appearing in the sum, either xi m = 0 or yi divides m. Similarly, ϕ(yi zj xk yk ) = yk ϕ(yi zj xk ) = xk ϕ(yi zj yk ), and so either yk m = 0 or xk divides m. Taking these both into consideration actually kills every one of the 11 possible standard monomials (we spare the reader the explicit check), and hence we can assume that ϕ(yi zj xk ) = 0. Now consider what happens with ϕ(xi zj xk ). Indeed, 0 = xi ϕ(yi zj xk ) = ϕ(xi yi zj xk ) = yi ϕ(xi zj xk ). So for every one of the 17 standard monomials m which possibly appears in the support of ϕ(xi zj xk ) we must have that yi m = 0 in K[x, y, z]/Nn . This actually leaves us with only two possible such standard monomials – namely zi zj xk and zi zj yk . We write ϕ(xi zj xk ) = a zi zj xk + b zi zj yk . The fact that we assume ϕ(xi yk ) = 0 implies a = 0 = b. This is because 0 = zj xk ϕ(xi yk ) = ϕ(xi zj xk yk ) = yk ϕ(xi zj xk ). To sum up, we have shown that, under our assumptions, if ϕ(yi zj xk ) = 0 holds then it also must be the case that ϕ(xi zj xk ) = 0. We can prove in a similar manner that ϕ(yi zj yk ) = 0, and this finishes the proof that ϕ can be written as a K-linear sum of the 11n − 15 classes of maps described. We reiterate that Theorem 6.3 fails for n = 2, since H2 ' P8 , and Γ2 is a cubic hypersurface cutting through H2 . We offer a short report for n = 3. Remark 6.6. The Hilbert scheme H3 contains 13, 824 monomial ideals. These come in 16 symmetry classes under the action of (S3 )3 oS3 . A detailed analysis of these symmetry classes and how we found the 13, 824 ideals appears on the website www.math.washington.edu/∼aholtc/HilbertScheme. For seven of the symmetry classes, the tangent space dimension is less than dim(Γ3 ) = 18. From this we infer that H3 has components other than Γ3 . We note that the number 13, 824 is exactly the number of monomial ideals on H3,3 as described in [3]. Moreover, the monomial ideals on H3,3 also fall into 16 distinct symmetry classes. We do not yet fully understand the relationship between Hn and H3,n suggested by this observation. Moreover, it would be desirable to coordinatize the inclusion Γ3 ⊂ H3 and to relate it to the equations defining trifocal tensors, as seen in [1, 13]. It is our intention to investigate this topic in a subsequent publication. Our study was restricted to cameras that take 2-dimensional pictures of 3-dimensional scenes. Yet, residents of flatland might be more interested in taking 1-dimensional pictures of 2-dimensional scenes. From a mathematical perspective, generalizing to arbitrary dimensions makes sense: given n matrices of format r × s we get a map from Ps−1 into (Pr−1 )n , and one could study the Hilbert scheme parametrizing the resulting varieties. Our focus on r = 3 and s = 4 was motivated by the context of computer vision. 26 CHRIS AHOLT, BERND STURMFELS AND REKHA THOMAS References [1] A. Alzati and A. Tortora: A geometric approach to the trifocal tensor, Journal of Mathematical Imaging and Vision 38 (2010) 159–170. [2] D. Cartwright, M. Häbich, B. Sturmfels and A. Werner: Mustafin varieties, Selecta Mathematica, to appear. [3] D. Cartwright and B. Sturmfels: The Hilbert scheme of the diagonal in a product of projective spaces, International Mathematics Research Notices 9 (2010) 1741–1771. [4] A. Conca: Linear spaces, transversal polymatroids and ASL domains, Journal of Algebraic Combinatorics 25 (2007) 25–41. [5] D. Cox, J. Little and D. O’Shea: Ideals, Varieties and Algorithms, Fifth edition, Undergraduate Texts in Mathematics, Springer, New York, 2007. [6] D. Eisenbud: Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, Springer, New York, 1995. [7] O. Faugeras and Q-T. Luong: The Geometry of Multiple Images, MIT Press, Cambridge, MA, 2001. [8] D. R. Grayson and M. E. Stillman: Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/ [9] F. Grosshans: On the equations relating a three-dimensional object and its twodimensional images, Advances in Applied Mathematics 34 (2005) 366–392. [10] M. Haiman and B. Sturmfels: Multigraded Hilbert schemes, Journal of Algebraic Geometry 13 (2004) 725–769. [11] R. Hartley and A Zisserman: Multiple View Geometry in Computer Vision, Second edition, Cambridge University Press, 2003. [12] A. Heyden and K. Åström: Algebraic properties of multilinear constraints, Mathematical Methods in the Applied Sciences 20 (1997) 1135–1162. [13] A. Heyden: Tensorial properties of multiple view constraints, Mathematical Methods in the Applied Sciences 23 (2000) 169–202. [14] A. Jensen: CaTS, a software system for toric state polytopes, Available at http://www.soopadoopa.dk/anders/cats/cats.html [15] A. Jensen: Gfan, a software system for Gröbner fans and tropical varieties, Available at http://www.math.tu-berlin.de/∼jensen/software/gfan/gfan.html. [16] D. Maclagan and B. Sturmfels: Introduction to Tropical Geometry, draft of book available at http://www.warwick.ac.uk/staff/D.Maclagan/papers/papers.html. [17] E. Miller and B. Sturmfels: Combinatorial Commutative Algebra, Springer, New York, 2005. [18] R. Stanley: Combinatorics and Commutative Algebra, Progress in Mathematics, Birkhäuser, Boston, 1996. [19] W. Stein et al: Sage Mathematics Software (Version 4.7), The Sage Development Team, 2011, http://www.sagemath.org. [20] B. Sturmfels: Gröbner Bases and Convex Polytopes, University Lecture Series, American Mathematical Society, Providence, 1996. [21] B. Sturmfels and A. Zelevinsky: Maximal minors and their leading terms, Advances in Mathematics 98 (1993) 65–112. Chris Aholt, Mathematics, University of Washington, Seattle, WA 98195 E-mail address: [email protected] Bernd Sturmfels, Mathematics, Univ. of California, Berkeley, CA 94720 E-mail address: [email protected] Rekha Thomas, Mathematics, University of Washington, Seattle, WA 98195 E-mail address: [email protected]