Lecture 18 Notes: Rotation and How to Represent It, Unit Quaternions, the Space of Rotations

6.801/6.866: Machine Vision, Lecture 18 1 Lecture 18: Rotation and How to Represent it, Unit Quaternions, the Space of Rotations Today, we will focus on rotations. Note that unlike translations, rotations are not commutative, which makes fitting estimates to data, amongst other machine vision tasks, more challenging. In this lecture, we will cover rotation in terms of: • Properties • Representations • Hamilton’s Quaternions • Rotation as Unit Quaternion • Space of rotations • Photogrammetry • Closed-form solution of absolute quaternions • Divison algebras, quaternion analysis, space-time We will start by looking at some motivations for why we might care about how we formulate and formalize rotations: What is rotation used for? • Machine vision • Recognition/orientation • Graphics/CAD • Virtual Reality • Protein Folding • Vehicle Attitude • Robotics • Spatial Reasoning • Path Planning - Collision Avoidance 1 1.1 Euclidean Motion and Rotation Rotation and translation form Euclidean motion. Some properties of Euclidean motion, including this property. Euclidean motion: • Contains translation and rotation • Preserves distances between points • Preserves angles between lines • Preserves handedness • Preserves dot-products • Preserves triple products • Does not contain: – Reflections – Skewing – Scaling 1.2 Basic Properties of Rotation Now that we have framed rotation to be a property of Euclidean motion, we can dive further into some properties of rotation: • Euler’s Theorem: There is a line of fixed points that remain the same in any rotation. This is known as the axis of rotation. • Parallel axis theorem: Any rotation is equivalent to rotation through the origin along with a translation. This allows for the decoupling between translation and rotation. • Rotation of sphere includes rotation of space: I.e, any rotation that is induced on a space can be induced on an equivalent-dimensional sphere. • Attitude, Orientation - Rotation Relative to Reference: This helps for determining the orientation of objects relative to another frame of reference. • Degrees of Freedom (in 3D) is 3. Some additional properties that are helpful for understanding rotation: • Rotational velocity can be described by a vector. This set of rotational vectors together form a lie algebra, specifically, so(3). The set of rotations form the counterpart to this lie algebra, namely the Special Orthogonal group SO(3), which is a Lie group. If you are not familiar with Lie groups/algebras, here are a few useful terms to get started with these concepts: – A group is a set equipped with a binary operation that combines any two elements to form a third element in such a way that four conditions called group axioms are satisfied, namely closure, associativity, identity and invertibility [1]. – A manifold is a d-dimensional topological space that locally resembles Euclidean space at each point i.e. any patch of the manifold can be “locally” approximated as a d-dimensional Euclidean space [2]. – A Lie group is a group that is also a differentiable manifold. One key Lie group that we will study in this course is the Special Orthogonal group, known as SO(3), which is the space of orthonormal rotation matrices. • We can define the derivative of the radius vector ṙ using Poisson’s Formula: ṙ = ω̂ × r • Rotational velocities add - this holds because these vectors belong to Lie algebras • Finite rotations do not commute - this holds because rotations are defined by Lie groups in a non-Euclidean space. • The Degrees of Freedom for rotation in dimension n is given by n(n−1) , 2 which coincidentally equals 3 in 3 dimensions. • Intuition: Oftentimes, it is easier to think about rotation “in planes”, rather than “about axes”. Rotations preserve points in certain planes. 2 1.2.1 Isomorphism Vectors and Skew-Symmetric Matrices A technical note that is relevant when discussing cross products: Although a cross product produces a vector in 3D, in higher dimensions the result of a cross product is a subspace, rather than a vector. Specifically, this subspace that forms the result of a higher-dimensional cross product is the space that is perpendicular/orthogonal to the two vectors the cross product operator is applied between. With this set up, we can think of cross products as producing the following isomorphism vectors and skew-symmetric matrices: One Representation: a × b = Ab ⎡ −az 0 0 A = ⎣ az −ay ax ⎤ ay −ax ⎦ 0 An Isomorphic Representation: a × b = B̄a ⎡ 0 bz 0 A = ⎣−bz by −bx ⎤ −by bx ⎦ 0 Note that while these skew-symmetric matrices have 9 elements as they are 3 × 3 matrices, they only have 3 DOF. 1.3 Representations for Rotation There are a myriad of representations for rotations, highlighting that different applications/domains/problem-solving techniques demand different representations for these transformations. Some of these representations include (we will proceed in greater detail about these later): 1. Axis and angle 2. Euler Angles 3. Orthonormal Matrices 4. Exponential cross product 5. Stereography plus bilinear complex map 6. Pauli Spin Matrices 7. Euler Parameters 8. Unit Quaternions Let us delve into each of these in a little more depth. 1.3.1 Axis and Angle This representation is composed of �a vector ω̂ and an angle θ, along with the Gibb’s vector that combines these given by �

ω̂ tan θ2 , which has magnitude tan θ2 , providing the system with an additional degree of freedom that is not afforded by unit vectors. Therefore, we have our full 3 rotational DOF. 1.3.2 Euler Angles A few notes about these: • There are over 24 definitions of Euler angles! This is the case because these definitions are permutations - i.e. the order of the angles matters here. The order of angular composition matters. • These rotations are defined through each axis, roll, pitch, and yaw. 3 1.3.3 Orthonormal Matrices We have studied these previously, but these are the matrices that have the following properties: 1. RT R = RRT = I, RT = R−1 (skew-symmetric) 2. det |R| = +1 3. R ∈ SO(3) (see notes on groups above) - being a member of this Special Orthogonal group is contingent on satisfying the properties above. 1.3.4 Exponential Cross Product We can also write rotations in terms of a matrix exponential. To derive this matrix exponential, let us consider the matrix first-order, homogeneous differential equation defined by: dR = ΩR dθ Has the solution given by the matrix exponential: R = eθΩ Taking the Taylor expansion of this expression, we can write this matrix exponential as: R = eθΩ ∞ X 1 = (θΩ)i i! i=0 = ∞ X θi i=0 i! T T (VΩ ΛiΩ VΩ ) (Taking an eigendecomposition of Ω = VΩ ΛΩ VΩ ) (Optional) Let us look a little deeper into the mathematics behind this exponential cross product. We can write a rotation about ω̂ through angle θ as: r = R(θ)r0 dr d = (R(θ)r0 ) dθ dθ dr = ω̂ × r = Ωr = ΩR(θ)r0 dθ d R(θ)r0 = ΩR(θ)r0 dθ Then for all r0 : d R(θ) = ΩR(θ) =⇒ R(θ) = eθΩ dθ 1.3.5 Stereography Plus Bilinear Complex Map Intuitively, this notion of rotation corresponds to mapping a sphere to a complex plane, making transformations in the complex plane, and then mapping this transformed mapping from the complex plane back to the sphere. A few points here: • This is an instance of Stereography: a conformal (angle-preserving) spherical mapping. • The rotation of a sphere induces the rotation of a space. • This plane is treated as a complex plane that we can apply homogeneous transforms to. We can conceptually visualize this mapping from a sphere to the complex plane using the figure below: Figure 1: Mapping from a sphere to a complex plane, which we then apply a homogeneous transformation to and map back to the sphere in order to induce a rotation. 4 Specifically, the homogeneous transform we consider maps the complex variable z to z 0 : az + b , for some a, b, c, d ∈ C cz + d We can actually generalize this framework even further - any rotation in 3-space can be thought of as an operation in a complex plane. z0 = 1.3.6 Pauli Spin Matrices With a physical motivation, these are 2 × 2 complex-valued, unitary, Hermitian matrices (A = A¯T ). All these constraints create 3 DOF for these matrices:       ~ 0 1 ~ 0 −i ~ 1 0 Sx = , Sy = , Sz = 2 1 0 2 i 0 2 0 −1 1.3.7 Euler Parameters There are also known as Rodrigues parameters, leading to Rodrigues formula, which can be thought of as a rotation about the unit vector ω̂ through the angle θ: r0 = (cos θ)r + (1 − cos θ)(ω̂ · r)ω̂ + sin θ(ω̂ × r) The geometry of this problem can be understood through the following figure: Figure 2: Geometric interpretation of the Rodrigues formula: Rotation about the vector ω̂ through an angle θ. One disadvantage of this approach is that there is no way to have compositions of rotations. Next, let us take an in-depth analysis of the Rodrigues Formula and the Exponential Cross Product: dR = ΩR =⇒ R = eΩθ dθ ∞ eΩθ = I + θΩ + X θi 1 Ωi (θΩ)2 + ... = 2! i! i=0 5 Next, we have that: Ω2 = (ω̂ω̂ T − I) Ω3 = −Ω We can then write this matrix exponential as: θ3 θ5 θ2 θ4 θ6 + + · · · ) + Ω2 ( − + + ···) 3! 5! 2! 4! 6! ∞ ∞ X θ2i+1 X θ2i+2 = I + Ω( (−1)i ) + Ω2 ( (−1)i ) (2i + 1)! (2i + 2)! i=0 i=0 eθΩ = I + Ω(θ − = I + Ω sin θ + Ω2 (1 − cos θ) = I + (sin θ)Ω + (ω̂ ω ˆ T − I)(1 − cos θ) = (cos θ)I + (sin θ)Ω + (1 − cos θ)ω̂ ω ˆT From this, we have: r = eθΩ r r0 = (cos θ)r + (1 − cos θ)(ω̂ · r)ω̂ + sin θ(ω̂ × r) Where the last line is the result of the Rodrigues formula. 1.4 Desirable Properties of Rotations We would like rotations to exhibit the following properties: • The ability to rotate vectors - or coordinate systems • The ability to compose rotations • Intuitive, non-redundant representation - e.g. rotation matrices have 9 entries but only 3 degrees of freedom • Computational efficiency • Interpolate orientations • Averages over range of rotations • Derivative with respect to rotations - e.g. for optimization and least squares • Sampling of rotations - uniform and random (e.g. if we do not have access to closed-form solutions) • Notion of a space of rotations 1.5 Problems with Some Rotation Representations Let us discuss some problems with the representations we introduced and discussed above: 1. Orthonormal Matrices: Redundant, with complex constraints. 2. Euler Angles: Inability to compose rotations, “gimbal lock” (when two axes line up, you lose a DOF, which can be disastrous for control systems). 3. Gibb’s Vector: Singularity when θ = π, since tan( π2 ) is not defined. 4. Axis and Angle: Inability to compose rotations 5. There is no notion of the “space of rotations” (at least not in Euclidean space). How can we overcome these challenges? One way through which we can do is to look at another representation approach, this time through Hamilton. 1.6 Quaternions In this section, we will discuss another way to represent rotations: quaternions. 6 1.6.1 Hamilton and Division Algebras Goal: Develop an algebra where we can use algebraic operations such as addition, subtraction, mulitplication, and division. 1. Hamilton’s representation is motivated by Algebraic couples, for instance, complex numbers as pairs of reals a + bi, a − bi 2. Here, we want: Multiplicative inverses 3. Examples: Real numbers, complex numbers 4. Expected next: Three conponents (vectors) - note that this was before Gibb’s vector and 3-vectors Hamilton’s insight here is that these quaternions require a “4th dimension for the sole purpose of calculating triples”. 1.6.2 Hamilton’s Quaternions Hamilton noted the following insights in order to formalize his quaternion: • Quaternions cannot be constructed with three components • Quaternions need additional square roots of -1 Thereofore, the complex components i, j, k defined have the following properties: 1. i2 = j 2 = k 2 = ijk = −1 2. From which follows: (a) ij = k (b) jk = i (c) ki = j (d) ji = −k (e) kj = −i (f) ik = −j Note: As you can see from these properties, multiplication of the components of these quaternions is not commutatitve. 1.6.3 Representations of Quaternions There are several ways through which we can represent these quaternions: 1. Real and imaginary parts: q0 + iqx + jqy + kqz 2. Scalar and 3-vector: (q, q) o 3. 4-vector: q 4. Certain Orthogonal 4 x 4 Matrices q (this is an isomorphism of quaternions that allows us to do multiplications). 5. Complex Composite of Two Complex Numbers: Here, we have (a + bi) and (c + di), and we replace all the real constants a, b, c, d with complex numbers. We can build sophisticated algebras from these operations. 1.6.4 Representations for Quaternion Multiplication With several ways to represent these quaternions, we also have several ways through which we can represent quaternion multiplication: 1. Real and 3 Imaginary Parts: (p0 + px i + py j + pz k)((q0 + qx i + qy j + qz k) =(p0 q0 − px qx − py qy − pz qz )+ (p0 qx + px q0 + py qz − pz qy )i+ (p0 qy − px qz + py qz + pz qx )j+ (p0 qz + px qy − py qx + pz q0 )k 7 2. Scalar and 3-Vector: (p, p)(q, q) = (pq − p · q, pq + qp + p × q) Note: This multiplication operation is not commutative. 3. 4-Vector: ⎡ −px p0 pz −py p0 ⎢px ⎢ ⎣py pz −py −pz p0 px ⎤⎡ ⎤ −pz q0 ⎢qx ⎥ py ⎥ ⎥⎢ ⎥ −px ⎦ ⎣qy ⎦ p0 qz Note: Here we also have an isomorphism between the quaternion and the 4 x 4 orthogonal matrix (this matrix is orthonormal if we have unit quaternions). Here we can show the isomorphism and relate this back to the cross product we saw before by considering the equivalence of the two following righthand-side expressions: ⎡ ⎤ p0 −px −py −pz ⎢px p0 −pz py ⎥ oo o ⎥ (a) pq = P q, where P = ⎢ ⎣py pz p0 −px ⎦ pz −py px p0 ⎡ ⎤ q0 −qx −qy −qz ⎢qx q0 oo o qz −qy ⎥ ⎥ (b) pq = q̄p, where q̄ = ⎢ ⎣qy −qz q0 qx ⎦ qz qy −qx q0 A few notes about these matrices P and q̄: • These matrices are orthonormal if quaternions are unit quaternions o o • P is normal if p is a unit quaternion, and q̄ is normal if q is a unit quaternion. o o • P is skew-symmetric if p has zero scalar part, and q̄ is skew-symmetric if q has zero scalar part. • P and q̄ have the same signs for the first row and column, and flipped signs for off-diagonal entries in the bottom right 3 x 3 blocks of their respective matrices. 1.6.5 Properties of 4-Vector Quaternions These properties will be useful for representing vectors and operators such as rotation later: oo oo 1. Not commutative: pq 6= qp oo o o oo 2. Associative: (pq)r = p(qr) o∗ o oo 3. Conjugate: (p, p)∗ = (p, −p) =⇒ (pq) = q p 4. Dot Product: (p, p) · (q, q) = pq + p + q o o o 5. Norm: ||q||22 = q · q o o∗ 6. Conjugate Multiplication: qq : o o∗ qq = (q, q)(q, −q) = (q 2 + q · q, 0) o o o = (q · q)e o∗ o o Δ oo o Where e = (1, 0), i.e. it is a quaternion with no vector component. Conversely, then, we have: q q = (qq)e. o −1 7. Multiplicative Inverse: q o∗ = q o o (q·q o (Except for q = (0, 0), which is problematic with other representations anyway.) We can also look at properties with dot products: oo oo o o o o 1. (pq) · (pq) = (p · p)(q · q) 8 oo oo o o o o 2. (pq) · (pr) = (p · p)(q · r) oo o o o∗ o 3. (pq) · r = p · (rq ) We can also represent these quaternions as vectors. Note that these quaternions all have zero scalar component. o 1. r = (0, r) o∗ 2. r = (0, −r) o o 3. r · s = r · s oo 4. rs = (−r · s, r × s) oo o o oo 5. (rs) · t = r · (st) = [r s t] (Triple Products) oo o 6. rr = −(r · r)e Another note: For representing rotations, we will use unit quaternions. We can represent scalars and vectors with: • Representing scalars: (s, 0) • Representing vectors: (0, v) 1.7 Quaternion Rotation Operator To represent a rotation operator using quaternions, we need a quaternion operation that maps from vectors to vectors. More specifically, we need an operation that maps from 4D, the operation in which quaternions reside, to 3D in order to ensure that we are in the correct for rotation in 3-space. Therefore, our rotation operator is given: o0 o o o∗ o r = R(r) = qrq o o∗ = (Qr)q o = (Q̄T Q)r ¯ T Q is given by: Where the matrix Q ⎡ o o q·q ⎢ ⎢ 0 Q̄T Q = ⎢ ⎣ 0 0 0 q02 + qx2 − qy2 − qz2 2(qy qx + q0 qz ) 2(qz qx − q0 qy ) 0 2(qx qy − q0 qz ) q02 − qx2 + qy2 − qz2 2(qz qy + q0 qz ) ⎤ 0 ⎥ 2(qx qz + q0 qy ) ⎥ ⎥ 2(qy qz − q0 qx ) ⎦ q02 − qx2 − qy2 + qz2 A few notes about this matrix: o • Since the scalar component of q is zero, the first row and matrix of this column are sparse, as we can see above. o ¯ T Q will be orthonormal (it is an orthonormal rotation matrix). • If q is a unit quaternion, the lower right 3 × 3 matrix of Q o0 o o o∗ Let us look at more properties of this mapping r = qrq : o o 1. Scalar Component: r0 = r(q · q) 2. Vector Component: r0 = (q 2 − q · q)r + 2(q · r)q + 2q(q × r) o0 o0 o o 3. Operator Preserves Dot Products: r · s = r · s =⇒ r0 · s0 = r · s o0 o0 o0 o o o 4. Operator Preserves Triple Products: (r · s ) · t = (r · s) · t =⇒ (r0 · s0 )t0 = (r · s) · t =⇒ [r0 s0 t0 ] = [r s t] 5. Composition (of rotations!): Recall before that we could not easily compose rotations with our other rotation representations. Because of associativity, however, we can compose rotations simply through quaternion multiplication: o o o o∗ o∗ o o o o∗ o∗ oo o oo p(qrq )p = (pq)r(q p ) = (pq)r(pq)∗ o Δ oo I.e. if we denote the product of quaternions z = pq, then we can write this rotation operator as a single rotation: o o o o∗ o∗ o o o o∗ o∗ oo o oo o o o∗ p(qrq )p = (pq)r(q p ) = (pq)r(pq)∗ = zrz This ability to compose rotations is quite advantageous relative to many of the other representations of rotations we have seen before (orthonormal rotation matrices can achieve this as well). 9 1.7.1 Relation of Quaternion Rotation Operation to Rodrigues Formula Let us see how this operator relates to the Rodrigues formula and the axis-angle representation of rotations: r0 = (q 2 − q · q)r + 2(q · r)q + 2q(q × r) = (cos θ)r + (1 − cos θ)(ω̂ · r)ω̂ + (sin θ)(ω̂ × r) We have that q is parallel to ω̂. Note the following equalities: • (q 2 − q · q) = cos θ • 2||q||22 = (1 − cos θ) �
• 2q||q||22 = sin θ2 �
• q = cos θ2 �
• ||q||22 = sin θ2 From these statements of equality, we can conclude: o q = (cos �θ
�θ
, ω̂ sin ) 2 2 A few notes on this: o • We see that both the scalar and vector components of the quaternion q depend on the axis of rotation ω̂ and the angle of rotation θ. • The vector component of this quaternion is parallel to ω̂. • This representation is one way to represent a unit quaternion. • Knowing the axis and angle of a rotation allows us to compute the quaternion. o o • Note that −q represents the same mapping as q since: o o o∗ o o o∗ (−q)r(−q ) = qrq To build intuition with this quaternion rotation operator, one way we can conceptualize this is by considering that our space of rotations is a 3D sphere in 4D, and opposite points on this sphere represent the same rotation. 1.8 Applying Quaternion Rotation Operator to Photogrammetry Now that we have specified this operator and its properties, we are ready to apply this to photogrammetry, specifically for absolute orientation. Let us briefly review our four main problems of photogrammetry: 1. Absolute Orientation (3D to 3D): Range Data 2. Relative Orientation (2D to 2D): Binocular Stereo 3. Exterior Orientation (3D to 2D): Passive Navigation 4. Interior Orientation (2D to 3D): Camera Calibration We will start by applying this to our first problem, absolute orientation. Recall our goal with this photogrammetry problem is to find the 3D transformation between our coordinate systems. 10 1.8.1 Least Squares Approach to Find R Recall our first attempt to solve for this transformation was done through least squares to solve for an optimal rotation matrix and a translation vector. While we showed in lecture 17 that we can solve for an optimal translation vector that depends on the rotation matrix R, we could not find a closed-form solution for the rotation matrix R. We review why: min +R n X ||ei ||22 n X = i=1 (r0r,i − R(r0l,i )(r0r,i − R(r0l,i )) i=1 n X = ||r0r,i ||22 − i=1 n X 0 0 (rr,i − R(rl,i )) − n X i=1 0 ||rl,i ||22 i=1 Where the first of these terms is fixed, the second of these terms is to be maximized (since there is a negative sign in front of this term, this thereby minimizes the objective), and the third of these terms is fixed. Therefore, our rotation problem can be simplified to: R∗ = min R n X ||ei ||22 = −2 i=1 = min(−2 R n X 0 (r0r,i − R(rl,i )) n X 0 r0r,i · R(rl,i )) (2) i=1 n X 0 = max( rb0r,i · R(rl,i )) R (1) i=1 (3) i=1 But since we are optimizing over an orthonormal rotation matrix R, we cannot simply take the derivative and set it equal to zero as we usually do for these least squares optimization problems. Though we can solve this as a Lagrangian optimization problem, specifying these constraints is difficult and makes for a much more difficult optimization problem. It turns out this a common problem in spacecraft attitude control. Let us see how we can use quaternions here! 1.8.2 Quaternion-based Optimization Solving this with our quaternion operator above, and noting the following definitions: o0 0 • rl,i = (0, rl,i ) o0 • rr,i = (0, r0l,i ) Then we can solve for our optimal rotation by solving for quaternions instead: R∗ = max R n X 0 rb0r,i · R(rl,i ) i=1 = o max o n X o o0 o∗ o0 (qrl,i q ) · rr,i q,||q||2 =1 i=1 n X o o0 o0 o = o max o (qrl,i ) · (rr,i q) = o max o (R̄l,i q) · (Rr,i q) q,||q||2 =1 i=1 n X o o q,||q||2 =1 i=1 oT = o max q o n X q,||q||2 =1 o T ¯ l,i Rr,i q R o (Since q does not depend on i) i=1 Where the term in the sum is a 4 × 4 matrix derived from point cloud measurements. From here, we can solve for an optimal rotation quaternion through Lagrangian Optimization, with our objective given by: oT o o o Δ max q N q, subject to: q · q = 1, N = o q n X i=1 11 T R̄l,i Rr,i Then written with the Lagrangian constraints this optimization problem becomes: oT o o o max q N q + λ(1 − q · q) o q o Differentiating this expression w.r.t. q and setting the result equal to zero yields the following first-order condition: o o 2N q − 2λq = 0 It turns out that similarly to our inertia problem from the last lecture, the quaternion solution to this problem is the solution to an eigenvalue/eigenvector problem. Specifically, our solution is the eigenvector corresponding to the largest eigenvalue of a 4 × 4 real symmetric matrix N constructed from elements of the matrix given by a dyadic product of point cloud measurements from the left and righthand systems of coordinates: M= n X 0 T r0l,i rr,i i=1 This matrix M is an asymmetric 3 × 3 real matrix. A few other notes about this: • The eigenvalues of this problem are the Lagrange Multipliers of this objective, and the eigenvectors are derived from the eiegenvectors of N , our matrix of observations. • This analytic solution leads to/requires solving a quartic polynomial - fortunately, we have closed-form solutions of polynomials up to a quartic degree! Therefore, a closed-form solution exists. Specifically, the characteristic equation in this case takes the form: λ4 + c3 λ3 + c2 λ2 + c1 λ + c0 = 0 Because the matrix of point cloud measurements N is symmetric, this characteristic equation simplifies and we get the following coefficients: 1. c3 = tr(N ) = 0 2. c2 = −2tr(M T M ) 3. c1 = −8 det |M | 4. c0 = det |N | In addition to solving absolute orientation problems with quaternions, this approach has applications to other problems as well, such as: • Relative Orientation (Binocular Stereo) • Camera Calibration • Manipulator Kinematics • Manipulator Fingerprinting • Spacecraft Dynamics 1.9 Desirable Properties of Quaternions Next, let us look at what propreties we would like to obtain from using quaternions, and let us see how well these properties are satisfied: • The ability to rotate a vector or coordinate system Yes! • Ability to compose rotations Yes! • Intuitive, non-redundant representations There is some redundancy (but note that this is solved by using unit quaternions!), and this representation is not the most intuitive. 12 • Computational efficiency We will discuss this in more detail further below. • Ability to Interpolate Orientations Yes! • Ability to average over rotations Yes! • Ability to take derivative w.r.t. rotation - e.g. for optimization and least squares Yes! • Ability to sample rotations Yes! • Notion of a space of rotations Yes! 1.9.1 Computational Issues for Quaternions One helpful metric we can compare different representations for rotation on is their computational efficiency. Below, we compare quaternions for rotation with orthonormal matrices for rotation in several important operations: oo • Operation: Composition of Rotations: pq This is given by: oo pq = (p, p)(q, q) = (pp − pq, pq + qp + p × q) Carrying this out naively requires 16 multiplications and 12 additions. Compared with orthonormal matrices, composing quaternions is faster for this operation (orthonormal matrices require 27 multiplications and 18 additions. o o o∗ • Operation: Rotating Vectors: qrq This is given by: o o o∗ qrq →r0 = (q 2 − r · q)r + 2(q · r)q + 2q(q × r) r0 = r + 2q(q × r) + 2q × (q × r) (More efficient implementation) Carrying this out naively requires 15 multiplications and 12 additions. Compared with orthonormal matrices, composing quaternions is slower for this operation (orthonormal matrices require 9 multiplications and 6 additions. • Operation: Renormalization This operation is used when we compose many rotations, and the quaternion (if we are using a quaternion) or the orthonormal matrix is not quite an orthonormal matrix due to floating-point arithmetic. Since this operation requires matrix inversion (see below) for orthonormal matrices, it is much faster to carry out this operation with quaternions. o Nearest Unit Quaternion: √qo o q·q 1 Nearest Orthonormal Matrix: M (M T M )− 2 1.9.2 Space of Rotations We will conclude today’s lecture by discussing the space of rotations, now that we have a representation for it: • S 3 (the unit sphere ∈ R3 ) with antipodal points identified • Projective space P 3 • Sampling: Sampling in this space can be done in regular and random intervals 13 • Finite rotation groups: These include the platonic solids with 12, 24, 60 elements - we can have rotation groups for (i) tetrahedron, (ii) hexahedron/octahedron, and (iii) dodecahedron/icosahedron • Finer-grade Sampling can be achieved by sub-dividing the simplex in the rotation space o o0 o0 o o N • If {q i }N i=1 is a group, then so is {q i }i=1 , where q i = q 0 q i . 1.10 References 1. Group, ______________________________________________ https://en.wikipedia.org/wiki/Group (mathematics) 2. Manifold, https://en.wikipedia.org/wiki/Manifold 14