Search

Development of processing methods for color images has been slow, but over the past 10–15 years ideas have been developed employing geometric operations implemented with quaternion algebra in the color space of the image pixels as generalizations of the fundamental scaling and spatial shift operations of linear grey-scale image processing. The goal has been filters that are sensitive in some way to both color and spatial features. In Euclidean color space the set of linear operations is very limited. Recent developments, however, have shown that there is a simple connection between geometric operations expressed using quaternion equations and those expressed as 4×44×4 matrices using homogeneous coordinates. These operations include projective transformations as well as all the classical Euclidean operations. Remarkably, they are all linear in homogeneous coordinates. This realization greatly expands the possibilities of linear vector filtering methods and means that the insight gained by working in quaternion algebra can be applied to the design of algorithms implemented using matrix methods. This paper (1) illustrates the use of simple quaternion equations to express geometric operations and (2) shows how the use of homogeneous coordinates makes it possible to work with quite difficult geometric transformations relatively easily. The possibilities for using projective and other transformations for devising new types of color image filter are shown and the difficulties discussed.

Publisher Summary While the 3-D vector space model can nicely model directions, it is usually considered to be inadequate for use in 3-D computer graphics, primarily because of a desire to treat points and vectors as different elements that are transformed differently by translations. Instead, people commonly use an extension of linear algebra known as homogeneous coordinates. This is often described as augmenting a 3-D vector v with coordinates (v1,v2,v3)T to a 4-vector (v1,v2,v3,1)T. This extension makes nonlinear operations such as translations implementable as linear mappings. For the homogeneous model in geometric algebra, the modeling principle is the same: it embeds the n-dimensional base space Rn in an (n +1)-dimensional representational vector space Rn+1, of which it then uses the inherent algebra. That produces a complete algebraic framework, which is well suited to compute with oriented flats, subspaces offset from the origin in Rn represented as blades in Rn+1. The algebra of Rn+1 provides generally applicable formulas for translation, rotation, and even affine and projective transformations in the base space Rn. The operations of meet and join always return sensible results for incidences of flats. Some of the incidence constructions are cross ratios and can be interpreted as defining motion-invariant measures. Then motions and transformations are studied and show that all direct flats are moved by the same linear transformation and all dual flats by another. This simplifies the code even more.

Publisher Summary More complicated geometrical objects do not require new operations or techniques in geometric algebra, merely the standard computations in a higher-dimensional space, followed by an interpretation step. The geometric algebra approach considerably extends the classical techniques of homogeneous coordinates, so it pays to redevelop this fairly well-known material. The better model to treat the metric aspects of Euclidean geometry is a representation that can make full use of the power of geometric algebra. That is the conformal model which requires two extra dimensions. It provides an isometric model of Euclidean geometry. In this representation, all Euclidean transformations become representable as versors, and are therefore manifestly structure-preserving. This gives a satisfyingly transparent structure for dealing with objects and operators, far transcending the classical homogeneous coordinate techniques. Initially, it shows how this indeed extends the homogeneous model with metric capabilities, such as the smooth interpolation of rigid body motions. Then it is found that there are other elements of Euclidean geometry naturally represented as blades in this model: spheres, circles, point pairs, and tangents. These begin to suggest applications and algorithms that transcend the usual methods. In the last chapter on the conformal model, the reason behind its name is found: all conformal (angle-preserving) transformations are versors, and this now also gives the possibility to smoothly interpolate rigid body motions with scaling. In all of these chapters, the use of the interactive software is important to convey how natural and intuitive these new tools can become.

Publisher Summary The homogeneous model of Euclidean geometry is reasonably effective since it linearizes Euclidean transformations, and geometric algebra extends the classical homogeneous coordinate techniques nicely through its outermorphisms. In the next few chapters, the book presents the new conformal model for Euclidean geometry, which can represent Euclidean transformations as orthogonal transformations. Encoding those as versors gets the full power of geometric algebra, including the structure preservation of all constructions. This chapter starts the exposition by defining the new representational space (which has two extra dimensions and a degenerate metric) and showing what its vectors represent. The two extra dimensions are geometrically interpretable as the point at the origin (as in the homogeneous model) and the point at infinity (which nicely closes Euclidean geometry, making translations into rotations around infinity). It then focuses on how to represent the familiar flats and directions already present in the homogeneous model and how to move them around. As first applications, it uses the versor representation to provide straightforward closed-form interpolation of rigid body motions and universally valid constructions for the reflection of arbitrary elements. The natural coordinate-free specification of elements and operations in the conformal model is best appreciated using the interactive illustrations.

The homogeneous model is well-suited to applications in which incidences of offset flat subspaces are central, but less so when metric properties are also important. In this, it plays a role similar to Grassmann-Cayley algebra. This chapter gives details on its direct use in applications. In the first part, it discusses the coordinate representations of the homogeneous elements. This naturally embeds the powerful Plucker coordinates for line computations, which are seen to be are a natural extension of homogeneous point coordinates (using the outer product). This chapter shows how to master them and derive new application formulas simply. Those coordinates for lines, as well as points and planes, permit compact formulation of the affine transformations as matrices. In the second part, it gives an advanced application of the homogeneous model. It is well-suited to encode the projective geometry involved in the imaging of the world by one or more pinhole cameras. The homogeneous model permits easy specification of how observations in the various cameras are connected, which permits using observations by one camera to guide the search for corresponding features in another camera. This chapter treats the fairly advanced subjects of stereo-vision based on point and line matches in 2 or 3 cameras. Both subjects of this chapter are incidental to the main flow of the book, though the section on Plucker coordinates prepares for the implementation of geometric algebra in Part III.

Publisher Summary Points and vectors are the fundamental building blocks upon which geometry is based. The dimension of a point is the number of coordinates it has. Maya doesn't provide an explicit 2D point or vector; however, a 3D point or vector can be used for the same purpose. Maya provides 3D points in Maya Embedded Language (MEL) and 4D points (homogenous points) in the C++ Application Programming Interface (API). Cartesian coordinates are based on distances from the origin (0, 0, and 0). Each coordinate is a distance measured along an axis, starting at the origin. Because each of the axes is perpendicular to the others, the combination of coordinates defines a precise position in space. For 3D points, the three coordinates define the distance along the standard X(1,0,0), Y(0,1,0), and Z(0,0,1) axes. A point can also be represented in homogeneous coordinates. Such a point has four dimensions and is represented as follows: p = (x, y, z, w). The additional coordinate, w, can be taken as a scaling of the point. MEL's use of the term “vector” is more closely related to the computer science definition of a vector—a one-dimensional array of scalars. There are very few restrictions on the kind of operations performed on the vector. Maya doesn't have a geometry shape for a single point. However, locators can be used for this purpose. Locators are visual guides that are drawn in viewports, but are not rendered.

Publisher Summary This chapter discusses general techniques, technical issues, and animation techniques presented in the remaining chapters. The chapter is divided into two sections. The first section serves as a quick review of the basics of computer graphics display pipeline and discusses the control of round-off error when data is repeatedly transformed. It is understood that readers know in advance about transformation matrices, homogeneous coordinates, and the display pipeline, including the perspective transformation. The second section deals with numerous orientation representations and quaternion arithmetic, which is important for the discussion of orientation interpolation. There are several orientation representations to choose from. The most robust representation of orientation is quaternion, but fixed angle, Euler angle, and axis angle are more intuitive, easier to implement, and often sufficient for a given situation. A detailed section on quaternion representation of orientation is presented in this chapter as well. If the reader is well versed in computer graphics, this chapter may be skimmed to pick up relevant terminology or skipped altogether.

Publisher Summary This chapter discusses how to decompose an arbitrary projective transformation of three-dimensional space into simple, geometrically meaningful factors. The standard way to factor any projective transformation of three-dimensional space is first to embed three-space into four-space, then to apply the 4 × 4 matrix M as a linear transformation in four-space, then to apply a perspective projection of four-space with the eye point at the origin and the perspective hyperplane at w = 1, and finally to project from four-space back to three-space by identifying the four-dimensional hyperplane w = 1 with standard three-dimensional space. In computer graphics and geometric modeling, the modeling transformations are generally applied to position an object in space, and then a perspective projection is applied to position the object on the screen for viewing. If a projective transformation has a perspective factor, then it must be a singular matrix. That is easy to see because every perspective transformation M has an eyepoint E that is mapped to a singularity, that is, to the point with homogeneous coordinates (0,0,0,0).

Publisher Summary This chapter provides an overview of the canonical embedding, Plucker coefficients, and the Grassmann manifolds. Plucker (or Grassmann) coordinates are a generalization of homogeneous coordinates to flats of arbitrary rank. The Plucker representation is mathematically more elegant than the simplex representation, but is substantially more expensive, exponentially so, in time and space. Therefore, Plucker coordinates are valuable mostly in theoretical work, and in computations restricted to spaces of dimension four or less. The analysis that led one to the Plucker coordinates of a line is equally valid for a flat a of arbitrary rank k in any space Tv. The flat a is uniquely determined by the values of a ◊ h where h ranges over all flats of Tv with rank m = n – k. The Plucker coordinates of a flat cannot be all zero. Two flats of Tv are the same flat only if their Plucker coordinates differ only by a positive factor.

Publisher Summary This chapter describes three-dimensional (3D) homogeneous clipping of triangle strips. Triangle strips are among the complex primitives handled by most 3D graphics software packages. One of the most expensive operations in graphics is to perform clipping. This chapter presents a solution that takes into account the specific organization of the list of points provided with a triangle strip to achieve up to 50,000+ triangle clippings per second in software. Some of the principles discussed in the chapter can be applied to other, simpler graphic structures, such as multi-bounded polygons, to improve the efficiency of standard clipping methods. The same principles also have been applied to quadrilateral mesh clipping. One easy way of optimizing a graphics pipeline operation is to keep the primitive (and its logic) all along the graphics pipeline. Unfortunately, some operations of the pipeline can modify, or break, the logical structure of the initial primitive. The chapter also proposes a method to clip triangle strips in 3D homogeneous coordinates, in the general case of a non-normalized clipping volume, accepting a triangle strip structure at the input of the clipping process, and giving a triangle strip structure at the output.

Publisher Summary This chapter provides an overview of the standard (unsigned) homogeneous coordinates for the plane, and the classical (unoriented) projective geometry which they implicitly define. It also discusses the advantages and disadvantages of homogeneous coordinates as a computational model, compared to ordinary Cartesian coordinates. The projective plane can be defined either by a means of a concrete model, borrowing concepts from linear algebra or Euclidean geometry, or as an abstract structure satisfying certain axioms. The axiomatic approaches have the advantage of being concise and elegant, but unfortunately they cannot be generalized easily to spaces of arbitrary dimension. To avoid the axiomatic approach and to base all definitions, four concrete models of projective space have been chosen: the straight, spherical, analytic, and vector space models. The use of homogeneous coordinates generally leads to simpler formulas that involve only the basic operations of linear algebra: determinants, dot and cross products, matrix multiplications, and the like. Another advantage of projective geometry is its ability to unify seemingly disparate concepts.

This chapter discusses the representation of flats by simplices in computational geometry. These encodings are sufficient for doing computational geometry on the plane, where points and hyperplanes (lines) are the only nontrivial flats. The simplex representation is an established tool in unoriented projective geometry. A flat of T v generated by the k -dimensional simplex a can be represented by the k × n real matrix, whose rows are the homogeneous coordinates of the vertices of a . The two k -dimensional simplices are equivalent only if their matrices a and b satisfies the equation, a = Kb , where K is some k × k matrix with positive determinant. Therefore, the flats of T v with rank k can be identified with the equivalence classes of the full-rank k × n matrices under this relation. In particular, the universe γ of T v is represented by the class of square n × n matrices with positive determinant, and its opposite – γ by those with negative determinant.

The transformation of the three-dimensional coordinates of a point to the two-dimensional coordinates of its image can be expressed compactly as a 4 × 4 homogeneous coordinate transformation matrix in accordance with a particular imaging geometry. The matrix can either be derived analytically from knowledge about the camera and the geometry of image formation, or it can be computed empirically from the coordinates of a small number of three-dimensional points and their corresponding image points. Despite the utility of the matrix in image understanding, motion tracking, and autonomous navigation, very little is understood about the inverse problem of recovering the projection parameters from its coefficients. Previous attempts have produced solutions that require iteration or the solution of a set of simultaneous nonlinear equations. This paper shows how the location and orientation of the camera, as well as the other parameters of the image-formation process can easily be computed from the homogeneous coordinate transformation matrix. The problem is formulated as a simple exercise in constructive geometry and the solution is both noniterative and intuitively understandable.

This chapter presents an introduction to coordinate geometry. It discusses cartesian coordinates and polar coordinates. The chapter also describes the transformation from polar coordinates to cartesian coordinates or vice versa. It presents the calculation of the distance between two given points in terms of their cartesian coordinates. The chapter also discusses the coordinates of the points that divide the line joining two given points internally and externally in a given ratio. It explains how to find out the area of a triangle in terms of the co-ordinates of its vertices. If a curve can be defined by a geometrical property common to all points on it, then there will be an algebraic relation that is satisfied by the co-ordinates of all points on the curve. Such an algebraic relation is called the equation of the curve. Conversely, all points of which co-ordinates satisfy a given algebraic relation are on a curve known as the locus of the given equation. To find the points of intersection of two loci, it is noted that, where they intersect, there is a point common to both curves. The co-ordinates of this point will satisfy the equations of both curves simultaneously. Thus, if the equations are solved simultaneously, the solutions will be the co-ordinates of the common points.

Publisher Summary This chapter provides an overview of the coordinates in space. It discusses the coordinates of a point. The chapter presents the equation of a plane. It has been shown that a plane corresponds to a three-dimensional subspace; a line, as the intersection of two planes, corresponds to a two-dimensional subspace. The chapter discusses the homogenous coordinates. It has been shown that a projective plane can be isomorphically embedded in a projective space.

Publisher Summary This chapter discusses the coordinates in a plane. It provides an overview of ternary field and axiom system. The chapter discusses ternary fields attached to a given projective plane. With respect to the relation of left-proportionality, equivalence class that does not consist of the null sequence is called left n-ratio. The definitions of right-proportionality and of right ratio are analogous. In every projective plane, left-homogeneous coordinates can be assigned to the points and right-homogeneous coordinates to the lines.

Publisher Summary This chapter describes homogeneous coordinates. For many purposes, it is useful to introduce four quantities X, Y, Z, W not all zero defined by X:Y:Z:W = x:y:z:l. The quantities (X, Y, Z, W) are called homogeneous Cartesian coordinates of the point (x, y, z). As ρX: ρY:pZ: ρW = X: Y: Z: W one can also select (ρX, ρY, ρZ, ρW) as the homogeneous coordinates of the point (x, y, z). It will be convenient to use x, y, z, w instead of X, Y, Z, W as homogeneous coordinates. If one requires at any stage to revert to nonhomogeneous coordinates, it is only necessary to put w = 1.

Publisher Summary This chapter discusses Axiom IV theorem by Hilbert. Hilbert called ends the points at infinity of the plane defined by any pencil of parallel lines. The consequence of the theorem is that a line possesses always two ends. After the proof of the theorem, according to which two lines neither intersecting each other nor being parallel, must have a common perpendicular, Hilbert also proved the existence of the line which possesses two prescribed ends. Thus, a determined perpendicular can be dropped on a line from an end not belonging to it. The way designed for the construction of hyperbolic geometry in the plane, leads through projective geometry. The chapter describes a complete elementary construction of hyperbolic plane geometry by means of direct introduction of certain homogeneous coordinates and an independent foundation of hyperbolic analytic geometry. These coordinates are called the Weierstrass homogeneous coordinates.

This chapter focuses on some problems of integral geometry in the complex domain. The equation p = ‘α, z’ implies that the line is uniquely determined by its Plucker coordinates. Conversely, the Plucker coordinates are determined uniquely by the line to within a constant factor. The set of all lines in a three-dimensional complex space can be considered a manifold. The set of numbers (α 1 , α 2 , α 3 , p 1 , p 2 , p 3 ) are assumed to be homogeneous coordinates of points in a five-dimensional complex projective space. These will be the Plucker coordinates of a line if and only if (α, p ) = 0.

This chapter discusses the theory of elimination. The aim of the theory of elimination is to solve systems of algebraic equations of an arbitrary degree and in an arbitrary number of unknowns. The theory of elimination gives methods of evaluating the coordinates of the points of intersection of two plane curves. The further development of the theory of algebraic curves consists in introducing homogeneous coordinates, which makes possible the investigation of improper points lying on the curves. The chapter also discusses Bezout's theorem. In the chapter, the theory of elimination has been given only in the case of a system of two equations in two unknowns. The generalization of this theory to the case of polynomials in more variables is not obvious and leads to new important problems.