S. D. V. Stephens

notes / Basic Neuroscience and Geometry of Neuroscience / chapter 11: Image Segmentation

G14 Algebraic Geometry of Segmentation and Tracking

This lecture is about the geometry of lines in 3-space and how it is used in segmentation and tracking. It is based on three papers: Pellegrini’s survey of ray shooting and lines in space, Theobald’s enumerative geometry framework for algorithmic line problems in , and Sottile and Theobald’s survey of line problems in nonlinear computational geometry (full references at the end).

The computational problem

The general question is a computational geometry problem: efficiently find the intersections of a large number of rays (a flow of light) with the objects of a scene. The problem has several aspects:

  • vision: segmentation and tracking;
  • robotics: moving objects in 3-space without collisions;
  • computer graphics: rendering realistic images by simulating the flow of light.

Coordinates on lines in 3-space

A line in 3-space depends on four parameters, and there are several ways to choose them.

  1. By pairs of planes. Four parameters describe as the intersection of two planes:
  2. By pairs of points. Take the two reference planes and . A non-horizontal line meets them in points and , and these determine : four parameters .

Plücker coordinates

Definition G14.1 (Homogeneous coordinates). A point of 3-space is written in homogeneous coordinates , with where for every scalar . These are the projective coordinates on .

The third way of describing a line, by Plücker coordinates, uses two of its points in homogeneous coordinates.

Definition G14.2 (Plücker coordinates). Let and be two distinct points of , normalized so that . The line is recorded by the matrix The homogeneous Plücker coordinates of are the minors of this matrix, and the Plücker point of is the homogeneous coordinates of a point in .

Choosing two other points of multiplies every minor by the same nonzero determinant, so is well defined as a point of . (The sign normalization together with the order of the two rows lets the coordinates also record an orientation of , from to .)

Proposition G14.3 (Plücker relation). The coordinates of a line satisfy the Plücker relation and the only homogeneous coordinates in that satisfy this relation are those that come from lines in 3-space.

The Klein quadric

Definition G14.4 (Klein quadric and Plücker hyperplanes). The Klein quadric is the quadric hypersurface so the lines of 3-space are exactly the points of . To each line is attached the vector (its Plücker coordinates in reverse order) and the Plücker hyperplane

With this choice, , the bilinear form of the Klein quadric, and the points of are the lines that meet .

Plücker coordinates and incidence relations

Plücker coordinates are useful for describing certain incidence relations:

  • intersections of linear loci;
  • tangency of quadrics.

Grassmannians and the Plücker embedding

The same construction works for -dimensional planes in an -dimensional ambient space.

Definition G14.5 (Plücker coordinates of a -plane). A -plane in is spanned by the columns of an matrix. For each subset of row indices with , let be the minor of the matrix with rows . With the vector is the vector of Plücker coordinates of the -plane.

Definition G14.6 (Grassmannian and Plücker embedding). The set of all -planes in is the Grassmannian . The Plücker embedding identifies it with for all ordered sets and (with extended to ordered index sets as an alternating function).

For , this is the Klein quadric: , and the relations reduce to the single Plücker relation.

Dual Plücker coordinates and intersections

Definition G14.7 (Dual Plücker coordinates). An -plane in the ambient is the intersection of hyperplanes The dual Plücker coordinates of are the list of minors of the matrix with columns .

Proposition G14.8. A -plane intersects an -plane in if and only if the dot product of the Plücker coordinates of with the dual Plücker coordinates of vanishes:

In particular this gives the intersection condition for two lines in , which is the vanishing of the bilinear form above.

Tangency to quadrics

The next question is to characterize when a -plane in is tangent to a quadric in . Write the quadric as , with a symmetric matrix.

Definition G14.9 (Exterior power of a matrix). The -th exterior power of a matrix is the map where and is the minor of with rows indexed by and columns indexed by .

If is a -plane spanned by the columns of an matrix , then is an matrix, that is, a vector: it is the vector of Plücker coordinates of in .

Proposition G14.10 (Tangency in Plücker coordinates). A -plane is tangent to a quadric if the quadric restricted to is singular. In Plücker coordinates this means

A side remark: twistor theory

The idea of turning problems about lines in 3-space into problems about points and hyperplanes in , through the Klein quadric , also arises in physics: it is Penrose’s twistor approach to general relativity (with one more dimension, time).

  • Start from a 4-dimensional vector space , the twistor space. Its projectivization is , and the Klein quadric is the embedding of the Grassmannian of 2-planes in the 4-space . (Here denotes the -dimensional linear subspaces of .)
  • The Penrose twistor transform is the diagram where is the flag variety (a line inside a 2-plane inside ) with its two projection maps.

The Klein quadric is ruled by two families of planes, the -planes and the -planes.

Two panels. On the left, inside a box labeled P^5, the Klein quadric K drawn as a hyperboloid-like surface carrying a red alpha-plane, a green point and a blue beta-plane. On the right, inside a box labeled P^3, a red point, a green line and a blue plane. Dashed double arrows match the alpha-plane with the point, the point of K with the line, and the beta-plane with the plane.

In the figure, a point of corresponds to a line of , an -plane to a point of , and a -plane to a plane of .

  • The -planes are the images under the second projection of the fibers of the first projection in the Penrose transform diagram the fiber over a point of consists of all lines through that point.
  • The -planes arise in the same way from the dual Penrose diagram where is the dual projective space, whose points are the planes of .
  • In these planes every line is a light ray. The base of the light cone is a product of two ’s, the same as , where is the 2-dimensional spinor space over the vertex of the light cone .
  • The Grassmannian is compactified and complexified Minkowski space, with big cell the complexified spacetime.

This was reviewed only as motivation; twistor theory is not used in what follows.

Why projective and complex geometry?

Why use the projective spaces and instead of the affine spaces and ? Projective algebraic geometry works better than affine geometry, because of compactness. Projective space decomposes as the big cell and the (projective) hyperplane at infinity.

Why use complex geometry for a real geometry problem? Complex algebraic geometry works better than real (polynomials always have the correct number of solutions: intersections, etc.). The set of real points sits inside the complex projective space ; similarly is a complex projective algebraic variety and is its set of real points.

Remark (General idea). Formulate the problem in projective algebraic geometry; solve it for complex algebraic varieties; restrict to the real points.

Use of Plücker coordinates

  • Problems about lines in 3-space are transformed into problems about hyperplanes and points in .
  • Why is this better? There are a lot of tools for the algebraic geometry of hyperplane arrangements.
  • The disadvantage: five parameters instead of four, which can increase the running time of algorithms.

However, it is known that even though the computational complexity of an arrangement of hyperplanes in is , its intersection with has computational complexity only .

A scene in 3-space becomes a hyperplane arrangement in

The geometric setup is as follows.

  • Suppose given a configuration of objects in 3-space. Assume they are polyhedra (smooth objects can always be approximated by polyhedra, through a mesh).
  • Triangulate the polyhedra and extend the edges of the triangulation to infinite lines .
  • Each such line determines a Plücker hyperplane in .
  • This gives a hyperplane arrangement in .

Ray shooting

The ray shooting problem is used for hidden surface removal and for detecting and computing intersections of polyhedra.

Definition G14.11 (Ray shooting problem). Given a collection of polyhedra in 3-space, a point and a direction , identify the first object of intersected by the ray starting at and pointing in the direction .

Consider a triangle of the triangulation of , with boundary lines . A line passes through if and only if its Plücker point in lies in the intersection of the (real) half-spaces determined by the hyperplanes , , . So to solve the ray shooting problem, locate in the hyperplane arrangement and check the list of triangles associated with the corresponding cell of the arrangement.

Visibility and common tangents

Another problem: which bodies of a given scene cannot be seen from any location outside the scene?

  • Geometric formulation: determining the common tangents to four given bodies in .
  • For polyhedra, common tangents means common transversals to edge lines; for smooth objects, tangents.

Theorem G14.12 (Model result). Four spheres in (with centers not all aligned) have at most 12 common tangent lines, and there are configurations that realize 12.

The slides show such a configuration, a figure from Sottile–Theobald: four spheres with coplanar centers and 12 common tangent lines. Three equal spheres sit around a smaller fourth sphere in the middle, and twelve lines cross the picture, each touching all four spheres. (In Sottile–Theobald’s example, three spheres of radius are centered at the vertices of an equilateral triangle of side and a sphere of radius at its center.)

Partial visibility

Here is how to arrive at the geometric formulation.

Definition G14.13 (Partial visibility). A convex body is a bounded, closed, convex set with inner points. A scene is a set of convex bodies in . A body is partially visible if there exist and a direction such that the ray from in the direction does not intersect any other : there is an unobstructed view of at least some points of from some viewpoint outside the scene. Such a ray is a visibility ray.

Reduce the collection by removing all bodies that are not partially visible.

If there is a visibility ray for , it can be moved continuously (translated, rotated) until the line is tangent to at least two bodies in (one of which can be ). At that point it has reached the boundary of the visibility region for .

The set of common transversals

Definition G14.14. Let be the set of lines in that intersect all the bodies .

  • Lines in have four parameters, and meeting a body with inner points is an open condition, so is a 4-dimensional set.
  • is a semialgebraic set (defined by algebraic equalities and inequalities), whose boundary consists of lines that are tangent to at least one .
  • The combinatorial structure of : its faces are determined by the sets of lines tangent to a fixed subset of bodies in .
  • Because is 4-dimensional, it has faces of dimensions , given by lines tangent to bodies.

Lines and spheres

  • When the bodies are polyhedra, this is linear computational geometry.
  • When the bodies are smooth (for example spheres), it is nonlinear computational geometry.

Core problem: find the configurations of lines tangent to spheres and transversal to lines in . All these cases are referred to as “common tangents”.

The slides show a figure from Theobald: one sphere and three lines with four common tangents, drawn in gray, each of which touches the sphere and meets all three lines.

Bounds on the number of common tangents

Theorem G14.15 (Theobald). Consider spheres and lines in . If they have only finitely many common tangents, then the maximal number of common tangents is In each case there are configurations realizing the bound.

The upper bounds for small come from Bézout’s theorem.

Theorem G14.16 (Bézout). Let be homogeneous polynomials in of degrees with a finite number of common zeros in . Then the number of common zeros, counted with multiplicity, is at most .

Bézout gives , , .

The bound

Proof that . The common tangents to three lines and one sphere are described by the following equations on (write ).

  1. Three linear equations, one for each of the three given lines with : which express the fact that and the fixed line intersect in .
  2. One quadratic equation which expresses the fact that is tangent to the quadric (the sphere).
  3. The Plücker relation, which restricts to the Klein quadric :

These are five homogeneous equations in of degrees , so if they have finitely many common solutions, Bézout gives at most of them. Hence . ∎

Here is the case of the exterior power defined earlier: the linear operator where with , with , and is the minor of with rows and columns .

Remark (Where the tangency equation comes from). The equation for tangency of a line and a quadric comes from the fact that is tangent to the quadric if and only if the matrix is singular, where is the matrix representing in Plücker form, The condition that is singular is since is multiplicative (the Cauchy–Binet formula) and of a matrix is its determinant. Here , identifying the matrix with a vector in .

Example G14.17 (Tangency to a sphere). For a sphere in of radius and center the quadric is in homogeneous coordinates, and the tangency equation is explicitly

The bounds are attained for

  • The case is as above.
  • The case is a very similar argument.
  • The case is also similar. Common transversals to four lines in 3-space are a classical problem of enumerative geometry, and it is known that 2 can be achieved (with real solutions), so .
  • : a construction achieving the maximum is the configuration of one sphere and three lines shown earlier.
  • : there is an explicit construction of a configuration of two lines and two balls with eight common tangent lines.
A hyperboloid of one sheet drawn with a light mesh of its two families of ruling lines. Three blue lines l1, l2, l3 belong to one ruling; a red line m_p of the other ruling passes through a marked point p and crosses each of the three blue lines at a red dot.

The figure (after Sottile–Theobald) shows why . Three pairwise skew lines lie in one ruling of a hyperboloid, and the lines transversal to all three are the lines of the second ruling: through each point of the hyperboloid passes exactly one of them, . A fourth line meets the hyperboloid in either two or zero real points, and the common transversals of are the lines through those points. Sottile–Theobald also draw the case where the three lines lie on a hyperbolic paraboloid (a saddle surface), which is ruled in the same way.

The slides then show Theobald’s configuration of two lines and two balls with eight common tangent lines: two overlapping balls, two thick black lines crossing near them, and eight lines in shades of gray, each touching both balls and meeting both black lines.

The bound

Now take one line and three spheres, given by quadrics .

  • The hyperplane in characterizing the lines transversal to is and the points of correspond to such lines.
  • For the quadrics and the corresponding , the equations characterize tangency to for .
  • Bézout alone would give the count (the Klein quadric, one linear equation and three quadratic equations). But these equations are not independent at infinity: there are spurious solutions at infinity, intersections of multiplicity two, and removing them leads to the count of 12.

Proof (Getting the multiplicity count).

  • The quadric of a sphere is in homogeneous coordinates in . It intersects the plane at infinity () in the conic , the same conic for every sphere.
  • For a point on this conic, the tangent line to the conic at in the plane has Plücker coordinates .
  • The Plücker vector of a tangent to the conic in the at infinity therefore also lies on the quadrics defined by , , (the lower right block of each is the identity, so the equation becomes ), and on . Two of these tangent lines, the two tangents to the conic through the point at infinity of , also lie in , so they are solutions at infinity of the system.
  • Use this to conclude that at these points the tangent hyperplanes to the quadrics , , and all contain a common 2-dimensional subspace.
  • Conclude that the multiplicity of intersection there is at least 2. The two solutions at infinity account for at least of the , which gives the correct count of the maximal number of tangents, .

∎

The slides show Theobald’s configuration of one line and three balls with twelve common tangent lines: a vertical line passes between three balls, and twelve lines in black and shades of gray each meet and touch all three balls.

Four spheres, and infinitely many tangents

  • A similar argument gives the bound (see Theobald and Sottile–Theobald).
  • A further step is to characterize the configurations with infinitely many common tangents, such as four spheres with collinear centers and equal radii (or collinear centers and inscribed in the same hyperboloid); see Theobald and Sottile–Theobald.

The slides show Sottile–Theobald’s pictures of configurations of four spheres with infinitely many common tangents. In each, the centers lie on one line , and rotating one common tangent about gives infinitely many more. The four panels show spheres that all touch one another at a single point (every line through that point in the common tangent plane is tangent to all of them), spheres inscribed in a circular cone, spheres meeting in a common circle, and spheres inscribed in a hyperboloid of revolution.

Conclusions

The geometric argument on the maximal number of common tangents gives an estimate of the algorithmic complexity of the visibility problem: it comes down to solving polynomial equations of the given degree (for example a degree 12 equation in the case of four spheres).

References

  • Marco Pellegrini, Ray shooting and lines in space, in Handbook of Discrete and Computational Geometry, pp. 599–614, CRC Press Ser. Discrete Math. Appl., CRC, 1997.
  • Thorsten Theobald, An enumerative geometry framework for algorithmic line problems in , SIAM J. Comput. 31 (2002), no. 4, 1212–1228.
  • Frank Sottile and Thorsten Theobald, Line problems in nonlinear computational geometry, Contemp. Math. 453 (2008), 411–432.