REF MODTRANSFMS James Anderson June 1990 COPYRIGHT James Anderson 1991. All rights reserved. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<<<<< REF MODTRANSFMS >>>>>>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< CONTENTS - (Use g to access required sections) -- Introduction -- Modtransfms -- Configuration Space -- Active/Passive Transformations -- Coordinate/Axis Transformations -- Homogeneous Coordinates -- Perspective Transformation and Projection -- Creating a Modmatrix -- Copying a Modmatrix -- Recognising a Modmatrix -- Trapping a Modmatrix -- Getting the Bounds of a Modmatrix -- Printing a Modmatrix -- Transposing a Modmatrix -- Concatenating Modmatrices -- Homogeneous Division -- Inverting a Modmatrix -- Special Kinds of Transformation -- Magnitude -- Handedness -- Shear -- Rotation -- Translation -- Single-Point Perspective -- The Combined Transformation -- Generating the Combined Transformation from Parameters -- Generating Parameters from the Combined Transformation -- Recovering Parameters from an Image of an Object -- Model Variables Introduction ------------ model [] Model is a package to support model-based vision. At present it consists of only one sub-package - modtransfms. See REF * MODTRANSFMS/Modtransfms modtransfms [] Modtransfms is a package for describing and carrying out the affine (general linear) and single-point perspective transformations in any whole numbered dimension. These are the only transformations needed by simple model-based vision programs. See REF * MODTRANSFMS/Modtransfms Modtransfms ----------- This section gives a brief introduction to the modtransfms package. The following few sections describe the context, or meaning, of the transformations, and the last few sections describe the procedures in the package. You should read all of the sections now and then consult individual sections when needed. The modtransfms package provides all of the transformations needed by simple model-based vision programs. It also provides procedures for recovering transformations from images and for analysing transformations into parameters. Typically, you will want to create a transformation from some parameters and apply it to some coordinates. The matrix types 'modtransfm', 'modparams', and 'modcoords' are provided to describe these things. Collectively they are of type 'modmatrix'. A modmatrix is an array, but additional information about its type is hidden in the package - SHOWLIB *MODTRANSFMS. This type information is used to impose meaning on matrices and operations - so only arrays that are created by the modtransfms procedures can be used. Any other type of array will cause a *MISHAP. A *MISHAP will also occur if you try to create a meaningless object by operating on the wrong kind of matrix. This type of error is easy to catch. Alternatively, a warning will be given, by returning a status value, if an operation cannot be carried out reliably because of some numerical problem. This type of error is hard to catch - sometimes unreliable results will not be detected and sometimes valid results will be treated as unreliable. Thus correct execution indicates that the result is reliable, but does not guarantee it. The procedures that return a status value are intended for use in programs that can take another computational route to a useful solution, but there are also versions that will generate a mishap message instead of returning an error status - these are easier to combine into long chains of commands, as is often done by people developing new algorithms. There are also versions of procedures that do not copy data - they are intended for efficient programs, but are quite complicated to use. The affine transformations can be composed from five basic transformations applied in the order: magnitude, handedness, shear, rotation, and translation. These can be followed by a single-point perspective transformation. All of these transformations can be generated from their parameters and the compound transformation can be analysed back into the same parameters. You are guaranteed that the parameters used to generate the sequence by *one* application of the generating procedure will be the same as the parameters recovered by *one* application of the analysing procedure - up to some numerical resolution. Configuration Space ------------------- There are several ways of describing the space in which points are described by coordinates and in which transformations take place. Modtransfms uses one, particular, interpretation. It is assumed that there is an absolute, fixed space called the 'configuration space'. Configuration space has a right-handed coordinate frame embedded in it at a fixed origin. Configuration space and its coordinate frame are never transformed. They always remain fixed. Y 4 | 3 | 2 | 1 | . P(2,1) | __ __ __ __ 0 1 2 3 4 X FIGURE 1 Figure 1 shows a two dimensional, right handed coordinate frame. The position of the point P is described by the Euclidean coordinates (2,1). The point P in configuration space is fixed, it can never move or change its coordinates. A transformation 'maps' a point P in a space called the 'domain' into a new point P' in a space called the 'range'. A point can be transformed many times, always starting from the configuration space and passing through many successive domains and ranges. The points P, P', P'', and so on, are different instantiations of the configuration point P. You can chose to describe the relative positions of points within any of these spaces, but the description is always related to an interpretation in configuration space. This is what makes the idea of configuration space so useful - no matter how, or how often, you transform a point, some canonical description of it exists in configuration space. Active/Passive Transformations ------------------------------ A transformation is said to be 'active' if it maps all of the points and the coordinate frame in the range into the domain, by contrast, a 'passive' transformation maps only the coordinate frame into the range. The difference is that an active transformation can map a point in configuration space to a new instantiation of that point at a different location in configuration space, whereas a passive transformation leaves all instantiations of the point in the same place in configuration space, but moves a new instantiation of the coordinate frame. Modtransfms uses the 'active' interpretation of transformations so that the position of a point in configuration space has a single interpretation and does not refer to arbitrary coordinate frames. The practical consequence of the above is that the parameters you give to describe a transformation describe motions of points relative to a fixed coordinate frame, not motions of a coordinate frame relative to fixed points, which is the inverse. Modtransfms provides a procedure for obtaining the inverse of a transformation, but then a description of a passive transformation is made up of the parameters of the active transformation and an application of the inverse procedure. ACTIVE : parameters <-> transformation ^ ^ |________________| One Step PASSIVE: parameters <-> transformation <-> inverse transformation ^ ^ |_______________________________________| Two Steps FIGURE 2 You can obtain the effect of a passive transformation, but at the cost of breaking the one-step relationship between parameters and transformations. By contrast, constructing an inverse of an active transformation preserves the one-step relationship between parameters and transformations, by imposing the parameterisation regardless of the fact that a transformation might be an inverse. ACTIVE INVERSE: parameters <-> transformation <-> ^ ^ |________________| One Step inverse transformation <-> inverse parameters ^ ^ |_______________________| One Step FIGURE 3 In Figure 3 the active inverse transformation is known only by its inverse parameters whereas, in Figure 2, the passive transformation is known by its parameters plus an application of the inverse transformation procedure - it is not known by the parameters of the inverse transformation. The type system in modtransfms does not record the necessity of the extra application of the inverse transformation procedure and so does not preserve the semantics of passive transformations. This is a critical issue. Do not mix active and passive interpretations unless you are prepared to take responsibility for the resulting polymorphic semantics of transformations. Coordinate/Axis Transformations ------------------------------- A transformation can be applied to the coordinates of a point or to the coordinate frame axes - these are transposes of each other. As before, the transformation can be active or passive - these are inverses of each other. If active, the entire embedding space is carried with the point, if passive the point and the embedding space remain static and only the coordinate axes move. |a b| |x| |ax+by| |x'| |c d| |y| = |cx+dy| = |y'| FIGURE 4 In Figure 4 the coordinates of a point (x,y) are mapped onto the coordinates (x',y') by pre-multiplying them with a transformational matrix with elements (a,b,c,d). Notice that the elements (a,b) affect the x' coordinate and the elements (c,d) affect the y' coordinate. The rows of the transformational matrix are said to make up a 'row-basis'. When a pre-multiplying, transformational matrix is used the row-basis transforms the coordinates of a point. Conversely, the elements (a,c) affect the x-component of x' and the elements (b,d) affect the y-component of y'. The columns of a transformational matrix are said to make up a 'column-basis'. When a pre-multiplying, transformational matrix is used the column-basis transforms the components of a coordinate, that is, it transforms the coordinate frame axes. Notice that the same effect can be obtained using post-multiplying matrices by transposing the matrix and the coordinates. |a c| |x y| |b d| = |ax+by cx+dy| = |x' y'| FIGURE 5 Thus one cannot tell from a transformational matrix whether it is a coordinate or axis transformation until it is known whether the matrix is to be used to pre- or post-multiply coordinates. This syntactic ambiguity is resolved in modtransfms by interpreting all transformations as coordinate transformations. A pre-multiplying matrix is bound to the type and a post-multiplying matrix to the type , that is . Any attempt to multiply row-basis and column-basis matrices together will cause a MISHAP. Thus, any successful multiplication has the same effect regardless of whether it is performed pre- or post-multiplying. The transpose operator toggles the basis type as well as transposing the elements, so one can switch between pre- and post-multiplying form by transposing matrices. Homogeneous Coordinates ----------------------- Homogeneous coordinates are obtained by augmenting Euclidean coordinates with an extra coordinate. EUCLIDEAN : (x,y) HOMOGENEOUS: (x,y,w) FIGURE 6 This form has the advantage that translation is obtained by a matrix multiplication when the homogeneous coordinate, 'w' is set to unit. |1 0 Tx| |X| |X+Tx| |0 1 Ty| |Y| = |Y+Ty| |0 0 1 | |1| | 1 | Modtransfms will allow you to assign any values you like to the elements of a coordiante matrix, but modtranfms does not provide routines to support the convention that 'w' can be set to zero. This results in 'direction vector' that transforms differently from coordinates (position vectors). If you create such a thing, then it is your own responsibility to maintain it. FIGURE 7 An homogeneous vector is projected back onto a Euclidean vector by dividing every element by the w-coordinate, providing w is non-zero. This form of projection, or homogeneous division, is used to describe perspective projection (See next section). Perspective Transformation and Projection ----------------------------------------- In simple model-based vision the affine transformations are used to describe the shape, position, and orientation of objects in a scene. A perspective projection of the scene then mimics what a thin-lens camera would "see" in the scene. The perspective *projection* is carried out in three parts. Firstly, the scene undergoes a perspective *transformation*, this distorts the whole of the scene including the part outside the field of view. The last step, homogeneous division, loses some information about whether an object is in front of or behind the camera, so, before it is applied, all objects in the perspectively transformed space should be clipped to the field of view. Finally, the clipped objects should undergo a homogeneous division which *projects* them into Euclidean space. Thus perspective projection is composed of the three steps: perspective transformation, clipping, and homogeneous division. Model provides perspective transformation and homogeneous division operators, but does not describe objects or their clipping - that is left to the user. In modtransfms all coordinate frames are right handed and the last axis is the depth axis. Thus, in three dimensions, the x- and y-axes are in the image plane and the z-axis is in depth (increasing z-coordinates indicate increasing depth). There are several ways to place this coordinate frame in relation to a physical display device, one of which is shown in Figure 8. (Model does not provide any graphical tools - that is left to the user.) O______________ X |\ | \ | \ | \ | Z | Y FIGURE 8 Figure 9 shows the thin-lens projection used in Model. 'F' is considered to be a positive focal length which lies behind the origin 'O'. The real object lies at least a distance F in front of the origin. A distance of F or less will not give rise to a real image. However, to give a good approximation to a more realistic 'thick-lens' projection the object should typically lie more than 10F in front of the origin. The real, inverted, image lies between F and 2F behind the origin. Depth-Normal Axes | | | _________________________ /| ____/^ Real _/ | ____/ | Image _/ | ____/ | _/ | ____/ | 2F F / | ___/ | ___|__________|/________O_______________ ... _____|____ Depth | / ____/ | | Axis v/__/ F 10F ____/ _/ Object FIGURE 9 In Modtransfms the perspective transformation is parameterised not by the 'Focal' length, 'F', but by its reciprocal, 'View' parameter, 'V', where V = 1/F. In this parameterisation an affine transformation is given when V = 0 and a perspective transformation when V > 0. However, we define v = 0 in dimensions zero and one because: all transformations in dimension zero are identity so V = 0 in this case and in dimension one perspective projection is identical to orthographic projection so, again, V = 0. The perspective shown in Figure 9 is called a 'single-point' perspective, because only one principal vanishing point exists. Multi-point perspectives are possible, but they are just the combination of a rotation and a single-point perspective. There is no advantage in over-determining a projective transformation by specifying both a rotation and a multi-point perspective. (If multi-point perspectives are required they could be recovered from a transformational matrix by solving simultaneous equations and/or finding the rotations that will zero all but one of the vanishing point parameters, Vi. Creating a Modmatrix -------------------- modmatrix [] 'Modmatrix' is an abstract type composed of the abstract types: 'modcoords', 'modparams' and 'modtransfm'. Objects of these abstract types are created by the following procedures: 'modnewcoords', 'modnewparams', and 'modnewtransfm'. Other procedures operate on, or return, objects of these abstract types. See below. modcoords [] See ?? modmatrix in REF * MODTRANSFMS/Creating a Modmatrix modnewcoords(SIZE, DIMENSION) -> MODCOORDS; [procedure] 'Modnewcoords' creates a matrix of homogeneous coordinates 'modcoords' in a space of the given 'dimension' arranged in 'size' columns. Thus the bounds of a modcoords matrix are [1 %dimension+1% 1 ^size]. The matrix is initialised with every column of the matrix describing the Euclidean origin. Example ------- vars coords = modnewcoords(1, 3); coords => ** modmatrixpr(coords); 0.000000 0.000000 0.000000 1.000000 modnewtransfm(DIMENSION) -> MODTRANSFM; [procedure] 'Modnewtransfm' creates a matrix representing an homogeneous transformation 'modtransfm' of the given 'dimension'. Thus the bounds of a modtransfm are [1 %dimension+1% 1 %dimension+1%]. The matrix is initialised to identity. Example ------- vars transfm = modnewtransfm(3); transfm => ** modmatrixpr(transfm); 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 modnewparams(DIMENSION) -> MODPARAMS; [procedure] 'Modparams' creates a matrix of the parameters of a homogeneous transformation of the given 'dimension'. Thus the bounds of a modparams are [1 %dimension+1% 1 %dimension+1%]. The matrix is initialised to identity. See also modparams in REF * MODTRANSFMS/Creating a Modmatrix Example ------- vars params = modnewparams(3); params => ** modmatrixpr(params); 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 Copying a Modmatrix ------------------- modmatrixcopy(MATRIX1) -> MATRIX2; [procedure] Returns 'matrix2' which is a copy of 'matrix1'. 'Matrix1' can be any of the modmatrix types: modcoords, modparams, modtransfm. Example ------- vars matrix1 matrix2; modnewtransfm(3) -> matrix1; modmatrixcopy(matrix1) -> matrix2; ;;; Data copied ... matrix1 = matrix2 => ** ;;; ... but into a new area of memory. matrix1 == matrix2 => ** Recognising a Modmatrix ----------------------- modismatrix(OBJECT) -> ; [procedure] Returns if 'object' is a modmatrix, otherwise. modiscoords(OBJECT) -> ; [procedure] Returns if 'object' is a modcoords, otherwise. modistransfm(OBJECT) -> ; [procedure] Returns if 'object' is a modtransfm, otherwise. modisparams(OBJECT) -> ; [procedure] Returns if 'object' is a modparams, otherwise. modisrowbasis(OBJECT) -> ; [procedure] Returns if 'object' is a modmodmatrix organised by row-basis, otherwise. Example ------- modismatrix(modnewtransfm(3)) => ** modismatrix('Not Likely') => ** Trapping a Modmatrix -------------------- modmatrixneeded(OBJECT); [procedure] Mishaps if 'object' is not a modmatrix. modcoordsneeded(OBJECT); [procedure] Mishaps if 'object' is not a modcoords. modtransfmneeded(OBJECT); [procedure] Mishaps if 'object' is not a modtransfm. modparamsneeded(OBJECT); [procedure] Mishaps if 'object' is not a modparams. modrowbasisneeded(OBJECT); [procedure] Mishaps if 'object' is not a modmatrix organised by row-basis. Example ------- modmatrixneeded(modnewtransfm(3)); modmatrixneeded('Not Likely'); ;;; MISHAP - MODMATRIX NEEDED ;;; INVOLVING: 'Not Likely' ;;; DOING : modtypeneeded compile nextitem compile Getting the Bounds of a Modmatrix --------------------------------- moddimension(MODMATRIX) -> DIMENSION; [procedure] Returns the number of spatial dimensions described by a modmatrix. See REF * MODTRANSFMS/Homogeneous Coordinates modsize(MODMATRIX) -> SIZE; [procedure] Returns the size of a modmatrix. The size of a modcoords is the number of coordinate vectors. The size of a modparams or modtransfm is the upper array bound: dimension+1. See REF * MODTRANSFMS/Homogeneous Coordinates Printing a Modmatrix -------------------- modmatrixpr(MODMATRIX); [procedure] Prints a modatrix as a table of numbers in decimal format. A blank line is printed at the beginning and end of the table and a space between each element. Numbers are printed in a field of 'mod_pr_figs' to the left of the decimal point and 'mod_pr_places' to the right. The decimal point is not printed if 'mod_pr_places' is zero. 'mod_pr_places' is a synonym for 'pop_pr_places' so they share the same value. Example ------- modmatrixpr(modnewtransfm(3)); 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 vars mod_pr_figs = 1, mod_pr_places = 0; modmatrixpr(modnewtransfm(3)); 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 Transposing a Modmatrix ----------------------- modtranspose(MODMATRIX1) -> MODMATRIX2; [procedure] Returns the transpose of a modmatrix toggling its row/column basis type. modnctranspose(MODMATRIX, WORKSPACE) -> MODMATRIX; [procedure] 'Modnctranspose' is the 'No Copy' (NC) version of 'modtranspose'. The values in the input 'modmatrix' are overwritten by the transpose in the output 'modmatrix'. 'Workspace' is an (M+N)/2 array_of_integer. See SHOWLIB * MODTRANSFMS for an example. Example ------- vars t = modnewtransfm(3); 2 -> t(1,2); modmatrixpr(t); 1.000000 2.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 vars u = modtranspose(t); modmatrixpr(u); 1.000000 0.000000 0.000000 0.000000 2.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 modisrowbasis(t) = modisrowbasis(u) => ** Concatenating Modmatrices ------------------------- The operation of combining transformations with each other or with coordinates is called 'concatenation'. The only concatenation used in Modtransfms is matrix multiplication, so the matrix multiplication operators are called concatenation operators. MODMATRIX1 ##* MODMATRIX2 -> MODMATRIX3; [operator 1.5] Post multiplies 'modmatrix1' by 'modmatrix2' returning the result in 'modmatrix3'. This is a right acting operator with precedence higher than any arithmetic operator. The product of two modtransfms is a modtransfm and the product of a modtransfm and a modcoords is a modcoords. Both arguments must be of the same dimension and row/column basis - these are inherited by the result. In addition a modcoords must be of the correct row/column basis for a single coordinate vector to be conformable for multiplication. It is not enough that the matrix of coordinates might be the correct size. modcat(MODMATRIX1, MODMATRIX2) -> MODMATRIX3; [procedure] 'Modcat' is the procedural form of ##* . modnccat(MODMATRIX1, MODMATRIX2, MODMATRIX3) -> MODMATRIX3; [procedure] 'Modnccat' is the 'No Copy' (NC) form of 'modcat'. The values in the input 'modmatrix3' are overwritten by the product in the output 'modmatrix3'. The input modmatrix3 must be a modmatrix large enough to hold the product matrix, but need not be the correct shape and type - because these are coerced. Example ------- vars coords = modnewcoords(1, 3); 1 ->coords(1,1); 2 ->coords(2,1); 3 ->coords(3,1); modmatrixpr(coords); 1.000000 2.000000 3.000000 1.000000 vars transfm = modnewtransfm(3); 1/2 -> transfm(2,2); 1/3 -> transfm(3,3); modmatrixpr(transfm); 1.000000 0.000000 0.000000 0.000000 0.000000 0.500000 0.000000 0.000000 0.000000 0.000000 0.333333 0.000000 0.000000 0.000000 0.000000 1.000000 modmatrixpr(transfm ##* coords); 1.000000 1.000000 1.000000 1.000000 Homogeneous Division -------------------- modhdiv(MODCOORDS) -> MODCOORDS; [procedure] Homogeneous division divides every coordinate vector by its weight coordinate, 'w'. See REF * MODTRANSFMS/Homogeneous Coordinates REF * MODTRANSFMS/Perspective Transformation and Projection modnchdiv(MODCOORDS) -> MODCOORDS; [procedure] 'Modnchdiv' is the 'No Copy' (NC) version of 'modhdiv'. The input 'modcoords' are over-written by the homogeneous quotient in the output 'modcoords'. Example ------- vars coords = modnewcoords(3,2); 3 -> coords(1,1); 6 -> coords(2,1); 1 -> coords(3,1); 3 -> coords(1,2); 6 -> coords(2,2); 2 -> coords(3,2); 3 -> coords(1,3); 6 -> coords(2,3); 3 -> coords(3,3); modmatrixpr(coords); 3.000000 3.000000 3.000000 6.000000 6.000000 6.000000 1.000000 2.000000 3.000000 modmatrixpr(modhdiv(coords)); 3.000000 1.500000 1.000000 6.000000 3.000000 2.000000 1.000000 1.000000 1.000000 Inverting a Modmatrix --------------------- modinverse(MODTRANSFM) -> INVERSE; [procedure] Returns the matrix inverse of 'modtransfm'. Mishaps if 'modtransfm' is singular or ill-conditioned. modneinverse(MODTRANSFM) -> INVERSE -> STATUS; [procedure] 'Modneinverse' is the 'No Error' (NE) version of 'modinverse'. 'Inverse' is the matrix inverse of 'modtransfm'. 'Status' is 0 if the result is reliable, 1 if singular, 2 if ill-conditioned. modncneinverse(MATRIX, INVERSE, DECOMPOSITION, RESIDUAL, [procedure] IDENTITY, WORKSPACE) -> INVERSE -> DECOMPOSITION -> RESIDUAL -> STATUS; 'Modncneinverse' is the 'No Copy' (NC), 'No Error' (NE) version of 'modinverse'. All of the arguments should be modtransfm matrices, though 'workspace' can be an array_of_double([1 ^size]), where 'size' is the common modsize of the other matrices. 'Status' is 0 if the result is reliable, 1 if singular, 2 if ill-conditioned. 'matrix' is the matrix to be inverted, 'inverse' is the matrix inverse, 'decomposition' is the LU decomposition of 'matrix' with pivoting, 'residual' is the matrix of residual error vectors, 'identity' is the identity transformation. In general 'identity' is the right hand side of the linear equation: matrix ##* inverse = identity. See the NAG documentation of subroutine F04AEF for further details. Example ------- vars transfm inverse; modnewtransfm(3) -> transfm; 2 -> transfm(1,2); modmatrixpr(transfm); 1.000000 2.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 modinverse(transfm) ->inverse; modmatrixpr(inverse); 1.000000 -2.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 modmatrixpr(transfm ##* inverse); 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 Special Kinds of Transformation ------------------------------- The affine, or general linear, transformations can be described by the concatenation of five kinds of transformation: Magnitude (M), Handedness (H), Shear (S), Rotation (R), and Translation (T). This can be followed by a single-point perspective, or View transformation (V). In a zero dimensional Euclidean space none of the transformations has a degree of freedom. In a one dimension Magnitude, Handedness, and Translation, are free to vary, and in a two or more dimensional space all of the affine transformations are free to vary. In dimensions one and above View is free to vary, but the projection of View in dimension one is a given point, so we consider that it has no degree of freedom in dimension one. (In model-based vision we are interested only in the projection of View. Indeed, we have no interest in any transformation of Homogeneous space in itself - only in projections of these transformations into Euclidean space.) The form of the two dimensional transformations is given below. The superscript denotes the dimensionality of the Euclidean space. Magnitude --------- 2 |M1 0 0| M = |0 M2 0| , M1,M2 > 0. |0 0 1| Magnitude scales objects in the direction of the configuration space coordinate frame axes. Values of Md greater than unit increase the size of objects in the direction of the d'th axis, values less than unit decrease the size, and values of unit leave the size unaltered. Handedness ---------- 2 |1 0 0| H = |0 Hd 0| , Hd = +/- 1. |0 0 1| When Hd = -1 Handedness transforms left handed objects into right handed objects and vice versa. When Hd = +1 objects are unchanged. The handedness parameter, Hd, always transforms the last dimension of the space, so in a two dimensional space it transforms the second dimension and in a d-dimensional space it transforms the d'th dimension. Shear ----- 2 |1 S1 0| S = |0 1 0|. |0 0 1| Shear shears an object. The shear parameter in the i'th row and j'th column, Sij, translates the j'th coordinate by Sij times the i'th coordinate at that point. This is easier to draw than to describe. In Figure 11 the 2x1 rectangle on the left is sheared into the 2x1 parallelogram on the right. Y Y 4 | 4| 3 | S1 = 1 3| 2 | __ __.(2,1) -----> 2| -- -- .(3,1) 1 | | 1| / / | __ __|__ __ |/__ __/__ __ 0 1 2 3 4 X 0 1 2 3 4 X FIGURE 11 In spaces with dimension greater than two the shear parameters are laid out in raster order (left to right and top to bottom). For example: |1 S1 S2 0| 3 |0 1 S3 0| S = |0 0 1 0|. |0 0 0 1| The shear parameter, Sij, in the i'th row and j'th column shears the j'th coordinate in proportion to the i'th coordinate. That is, it is a shear in the ij-plane. Rotation -------- 2 |C -S 0| R = |S C 0| , C = cos(a), S = sin(a), a = angle of rotation. |0 0 1| Rotation performs a rotation in the plane by the angle 'a' in radians. Modtransfms does not allow you to describe angles in any other way, that would be against the notion of canonical description. When calculating parameters for Modtransfms remember to set *POPRADIANS to . The rotation parameters are laid out in inverse raster order (right to left and bottom to top). For example: |1 0 0 0| 3 |R3 1 0 0| R = |R2 R1 1 0| |0 0 0 1| In the case of Shear the parameters are identical to the components of the transformation, but with Rotation each parameter generates four components. The rotation transformation is obtained by concatenating each rotation in order. Remember that transformations are written right to left by default in Modtransfms. 3 R = R3.R2.R1 |C3 -S3 0 0| |C2 0 -S2 0| |1 0 0 0| |S3 C3 0 0| |0 1 0 0| |0 C1 -S1 0| = |0 0 1 0| |S2 0 C2 0| |0 S1 C1 0| |0 0 0 1| |0 0 0 1| |0 0 0 1| |C2C3 -S1S2C3-C1S3 -C1S2C3+S1S3 0| |C2S3 -S1S2S3+C1C3 -C1S2S3-S1C3 0| = |S2 S1C2 C1C2 0|. |0 0 0 1| Note that this parameterisation is in terms of rotations in the plane, not rotations about axes. The concept of rotations in the plane generalises easily to dimensions higher than three, the concept of rotations about axes does not. There are also constraints on the parameters of rotation. |1 0 0 0| 3 |R3+ 1 0 0| R = |R2 R1 1 0| |0 0 0 1| The last row (here R1,R2) can take on any value in a whole rotation: -pi < R <= pi + but the rows above (here R3 ) are constrained to a semi-rotation: + -pi/2 < R <= pi/2 Translation ----------- 2 |1 0 T1| T = |0 1 T2|. |0 0 1 | Translation moves an object in the Td'th axis by an amount Td. Single-Point Perspective ------------------------ The single-point perspective or 'View' transformation 'V' gives rise to a perspective transformation of homogeneous space. 'F' is the focal length of a thin-lens camera and Vd = 1/F is the parameter of the view transformation. Vd always lies in the last Euclidean dimension. That is, it lies in the depth axis. In dimensions zero and one V = 0. See REF * MODTRANSFMS/Perspective Transformation and Projection 2 |1 0 0| V = |0 1 0| , Vd >= 0. |0 -Vd 1| The Combined Transformation --------------------------- The general affine transformation (A) can be constructed by concatenating each of the five basic types of affine in the sequence Magnitude, followed by Handedness, followed by Shear, followed by Rotation, followed by Translation. That is A = TRSHM. (Recall that transformations are written from right to left by default in Modtransfms.) The general single point-perspective (P) is given by: P = VA = VTRSHM. When all of the parameter matrices are overlaid we obtain: 0 P = |1|. 1 |MH T| P = |0 1|. 2 |M S T| P = |R MH T|. |0 V 1| |M S S T| 3 |R+ M S T| P = |R R MH T|. |0 0 V 1| |M S S S T| 4 |R+ M S S T| P = |R+ R+ M S T|. |R R R MH T| |0 0 0 V 1| And so on. Generating the Combined Transformation from Parameters ------------------------------------------------------ modtransfm(MODPARAMS) -> MODTRANSFM; [procedure] Generates the transformation matrix 'modtransfm' from the parameter matrix 'modparams'. See also ?? modmatrix in REF * MODMATRIX/Creating a Modtransfm modnetransfm(MODPARAMS) -> MODTRANSFM -> STATUS; [procedure] `Modnetransfm' is the `No Error' (NE) version of 'modtransfm'. If 'status' is 0 then the result is reliable. If status = 1 then the magnitude or handedness constraints have been broken. If status = 2 then the rotation constraints have been broken. If status = 3 then the perspective constraints have been broken. modncnetransfm(MODPARAMS, MODTRANSFM) ->MODTRANSFM ->STATUS; [procedure] 'Modncnetransfm' is the 'No Copy' (NC), `No Error' (NE) version of 'modtransfm'. The input 'modtransfm' is over-written by the output 'modtransfm'. If 'status' is 0 then the result is reliable. If status = 1 then the magnitude or handedness constraints have been broken. If status = 2 then the rotation constraints have been broken. If status = 3 then the perspective constraints have been broken. Example (Compare with next section) ----------------------------------- vars params, transfm, status, h = -1, m1 = 2, m2 = 3, s1 = 5, r1 = pi/2, t1 = 7, t2 = 11, v = 1; modnewparams(2) -> params; m1 -> params(1,1); m2*h -> params(2,2); s1 -> params(1,2); r1 -> params(2,1); t1 -> params(1,3); t2 -> params(2,3); v -> params(3,2); modmatrixpr(params); 2.000000 5.000000 7.000000 1.570796 -3.000000 11.000000 0.000000 1.000000 1.000000 modtransfm(params) -> transfm; modmatrixpr(transfm); 0.000000 3.000000 7.000000 2.000000 -15.000000 11.000000 -2.000000 15.000000 -10.000000 Generating Parameters from the Combined Transformation ------------------------------------------------------ modparams(MODTRANSFM) -> MODPARAMS; [procedure] Generates the parameter matrix 'modparams' from the transformation matrix 'modtransfm'. See also ?? modmatrix in REF * MODTRANSFMS/Creating a Modmatrix modneparams(MODTRANSFM) -> MODPARAMS -> STATUS; [procedure] 'Modneparams' is the 'No Error' (NE) version of 'modparams'. If 'status' is 0 then the result is reliable. If status = 1 then the magnitude or handedness constraints have been broken. If status = 2 then the rotation constraints have been broken. If status = 3 then the perspective constraints have been broken. modncneparams(MODTRANSFM, MODPARAMS) -> MODPARAMS -> STATUS; [procedure] 'Modncneparams' is the 'No Copy' (NC), 'No Error' (NE) version of 'modparams'. The input 'modparams' is over-written by the output 'modparams' and the input 'modtransfm' is over-written by intermediate calculations. If 'status' is 0 then the result is reliable. If status = 1 then the magnitude or handedness constraints have been broken. If status = 2 then the rotation constraints have been broken. If status = 3 then the perspective constraints have been broken. Example (Compare with previous section) --------------------------------------- vars params transfm status h m1 m2 s1 r1 t1 t2 v; modnewtransfm(2) -> transfm; 0 -> transfm(1,1); 3 -> transfm(1,2); 7 -> transfm(1,3); 2 -> transfm(2,1); -15 -> transfm(2,2); 11 -> transfm(2,3); -2 -> transfm(3,1); 15 -> transfm(3,2); -10 -> transfm(3,3); modmatrixpr(transfm); 0.000000 3.000000 7.000000 2.000000 -15.000000 11.000000 -2.000000 15.000000 -10.000000 modparams(transfm) -> params; modmatrixpr(params); 2.000000 5.000000 7.000000 1.570796 -3.000000 11.000000 0.000000 1.000000 1.000000 abs(params(1,1)) ->> m1 => ** 2.0 abs(params(2,2)) ->> m2 => ** 3.0 sign(params(2,2)) ->> h => ** -1.0 params(1,2) ->> s1 => ** 5.0 params(2,1) ->> r1 => ** 1.570796 params(1,3) ->> t1 => ** 7.0 params(2,3) ->> t2 => ** 11.0 params(3,2) ->> v => ** 1.0 Recovering Parameters from an Image of an Object ------------------------------------------------ modrecoverparams(MODEL, IMAGE, F, TDEPTH) -> PARAMS; [procedure] Recovers the transformation that a model has undergone to give rise to a particular image. 'Model' is a matrix of model points, 'image' is a matrix of corresponding image points, 'f' is the focal-length, 'tdepth' is the value that the translation along the depth axis is clamped to, and 'params' is the parameter matrix describing the transformation. In dimension zero the recovered transformation is identity - this is the correct result. In dimension one the recovered transformation is also identity - this is a default value - all transformations in dimension one give rise to the same image. In dimensions greater than one the recovered transformation is unique up to some numerical resolution. modnerecoverparams(MODEL,IMAGE,F,TDEPTH) ->PARAMS ->STATUS; [procedure] 'Modnerecoverparams' is the 'No Error' (NE) version of 'modrecoverparams'. If 'status' is zero the result is reliable. If status = 1 then the correspondence is singular or near-singular. If status = 2 then the correspondence is ill-conditioned. modncnerecoverparams(MODEL, IMAGE, F, TDEPTH, [procedure] TRANSFM, PARAMS, A, QR, X, B, AA, E, Y, Z, R, IPIV) -> PARAMS -> STATUS; 'Modncnerecoverparams' is the 'No Copy' (NC), 'No Error' (NE) version of 'modparams'. The input arguments 'model', 'image', 'f', 'tdepth' and the output parameters 'params' and 'status' are the same as in 'modnerecoverparams'. The remaining parameters are workspaces that are over-written during computation. For an example of their use see modnerecoverparams in SHOWLIB * MODTRANSFMS. Example ------- vars model image f tdepth j temp transfm1 params1 transfm2 params2; ;;; Make a vertex-centered, unit-diagonal square with a point at the ;;; center coincident with the origin. modnewcoords(5,2) -> model; 0.5 ->> model(1,2) -> model(2,3); -0.5 ->> model(1,4) -> model(2,5); ;;; Print the model coordinates. modmatrixpr(model); 0.000000 0.500000 0.000000 -0.500000 0.000000 0.000000 0.000000 0.500000 0.000000 -0.500000 1.000000 1.000000 1.000000 1.000000 1.000000 ;;; Make a parameter matrix. modnewparams(2) -> params1; 1000 -> f; 10000 -> tdepth; 900 -> params1(1,1); ;;; X magnitude. 800 -> params1(2,2); ;;; Depth magnitude. 1 -> params1(1,2); ;;; Shear. pi/3 -> params1(2,1); ;;; Rotation. 700 -> params1(1,3); ;;; X translation. tdepth -> params1(2,3); ;;; Depth translation. 1/f -> params1(3,2); ;;; View. ;;; Make the corresponding transformational matrix. modtransfm(params1) -> transfm1; ;;; Make the corresponding perspective image of the model. modhdiv(transfm1 ##* model) -> temp; modnewcoords(5,1) -> image; for j to 5 do temp(1,j) -> image(1,j); endfor; ;;; Print the perspective image of the model. modmatrixpr(image); -77.777778 -98.512080 -57.989321 -55.166560 -100.124347 1.000000 1.000000 1.000000 1.000000 1.000000 ;;; Recover the parameter matrix. modrecoverparams(model, image, f, tdepth) -> params2; ;;; Recover the transformational matrix. modtransfm(params2) -> transfm2; ;;; Print the original parameter matrix. modmatrixpr(params1); 900.000000 1.000000 700.000000 1.047198 800.000000 10000.000000 0.000000 0.001000 1.000000 ;;; Print the recovered parameter matrix. modmatrixpr(params2); 900.000000 1.000000 700.000000 1.047198 800.000000 10000.000000 0.000000 0.001000 1.000000 ;;; Print the original transformational matrix. modmatrixpr(transfm1); 450.000000 -292.820323 700.000000 779.422863 1092.820323 10000.000000 -0.779423 -1.092820 -9.000000 ;;; Print the recovered transformational matrix. modmatrixpr(transfm2); 450.000000 -292.820323 700.000000 779.422863 1092.820323 10000.000000 -0.779423 -1.092820 -9.000000 Model Variables --------------- The Model package uses a number of variables and constants to control the behaviour of Model, or to inform the user of hardware or software configurations. mod_pr_figs [vars] Used to control the printing of numbers, especially by 'modprmatrix'. 'Mod_pr_figs' is the width of the digit field to the left of the decimal point. The default value of mod_pr_figs is six. See also mod_pr_places. mod_pr_places [vars] Used to control the printing of numbers, especially by 'modprmatrix'. 'Mod_pr_places' is the width of the digit field to the right of the decimal point. The decimal point is not printed if mod_pr_places is zero. 'Mod_pr_places' is a synonym for 'pop_pr_places' so they share the same value. The default value of mod_pr_places is six. See also mod_pr_figs. modprecision [constant] Lower bound on the precision of double decimal calculations. It has value 0.5 * B ** (1-P) if rounded arithmetic is used and B ** (1-P) if truncated arithmetic is used. B is the arithmetic base (2) and P is the number of base-B digits in the mantissa. modversion [constant] The version number of the current release of Model. Integer values are public releases and decimal values are development releases. --- COPYRIGHT James Anderson 1991. All rights reserved. ----------------