3D Rotations

Parameter Computation and Lie Algebra based Optimization

Kenichi Kanatani

• Publisher: Chapman and Hall/CRC
• Year: 2020
• ISBN:
  9781000071658
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Graphics
• Index: Computer Science

3D rotation analysis is widely encountered in everyday problems thanks to the development of computers. Sensing 3D using cameras and sensors, analyzing and modeling 3D for computer vision and computer graphics, and controlling and simulating robot motion all require 3D rotation computation. This book focuses on the computational analysis of 3D rotation, rather than classical motion analysis. It regards noise as random variables and models their probability distributions. It also pursues statistically optimal computation for maximizing the expected accuracy, as is typical of nonlinear optimization. All concepts are illustrated using computer vision applications as examples.

Mathematically, the set of all 3D rotations forms a group denoted by SO(3). Exploiting this group property, we obtain an optimal solution analytical or numerically, depending on the problem. Our numerical scheme, which we call the "Lie algebra method, " is based on the Lie group structure of SO(3).

This book also proposes computing projects for readers who want to code the theories presented in this book, describing necessary 3D simulation setting as well as providing real GPS 3D measurement data. To help readers not very familiar with abstract mathematics, a brief overview of quaternion algebra, matrix analysis, Lie groups, and Lie algebras is provided as Appendix at the end of the volume.

Chpater 1

Introduction

Here, we describe the background of the problems we discuss in this book. Then, we summarize the contents of the subsequent chapters.

1.1 3D Rotations

As mentioned in Preface, 3D rotation has been historically an important theme of physics in relation to rigid body motion and quantum mechanics. In today’s computer age, however, “computational” aspects of 3D rotation are important issues of 3D measurement using cameras and 3D sensors for computer vision and computer graphics applications as well as control and simulation of robots. As will be pointed out in the next chapter, 3D rotation is specified by a “rotation matrix” R (a 3 × 3 orthogonal matrix of determinant 1). A typical problem that needs to be solved is find rotations R₁, R₂, …, R_M that optimize, i.e., minimize or maximize, a function

J=J(⋯,R1,R2,⋯,RM),	(1.1)

that includes these rotations in its arguments.

Consider, for example, computing from camera images the postures of the cameras that capture them and the objects seen in the images, which is a typical computer vision task called “3D reconstruction.” By “posture.” we mean the position and the orientation. The position is specified by the 3D coordinates of a prescribed reference point such as the centroid of the object or the lens center of the camera. The orientation is specified by the relative rotation between a coordinate system fixed to the object or the camera and a coordinate system fixed to the scene, called the “world coordinate system.” The 3D reconstruction problem reduces to optimization of a function that includes rotations in its arguments in the form of Eq. (1.1).

Similar problems also occur in various other situations. For graphics applications, for example, we need to compute optimal postures of generated objects and the optimal illumination source arrangement. For robotics applications, we need to compute optimal postures of actuators such as robot hands, drones, and cameras. Such problems related to 3D orientations usually reduce to function optimization involving 3D rotations in the form of Eq. (1.1).

Considering such applications, we describe in Chapter 2 geometric meanings of 3D rotation and show how to represent 3D rotation using vectors and matrices. It is concluded that 3D rotation is specified by a rotation matrix, i.e., an orthogonal matrix of determinant 1. From this fact, we see that the nine elements of the rotation matrix are not independent of each other, having only three degrees of freedom. Then, we prove “Euler’s theorem,” which states that 3D rotation is a rotation around some axis by some angle. As a special case, we derive the matrix form for rotation around each coordinate axis.

In Chapter 3, we show how to describe a general rotation matrix R in terms of three parameters. The most straightforward way is the use of three rotation angles α, β, and γ around each coordinate axis, called the “roll,” the “pitch,” and the “yaw.” We point out, however, that the resulting rotation depends on the order of composition. We also point out that this composition has different meanings, depending on whether each axial rotation takes place with respect to a coordinate system fixed to the object or with respect to a coordinate system fixed to the surrounding space. Taking this into consideration, we define the “Euler angles” θ, ϕ, and ψ of rotation, which are determined uniquely. We also discuss their potential singularities. Next, we derive the “Rodrigues formula,” which specifies 3D rotation by an axis l and the angle Ω of rotation around it. Finally, we introduce the “quaternion representation” that specifies 3D rotation by four parameters q₀, q₁, q₂, and q₃ such that their sum of squares is 1 (hence the degree of freedom is 3). This is an extension of expressing 2D rotation on a plane by a complex number to 3D rotation in 3D.

1.2 Estimation of rotation

If we apply rotation R to N vectors a₁, …, a_N, we obtain a₁′, …, a_N′ such that a_α′ = R a_α, α = 1, .., N. In Chapter 4, we consider its “inverse problem,” namely, given two sets of vectors a₁, …, a_N, and a₁′, …, a_N′, we compute the rotation R between them. The solution is immediately obtained if there is no noise in the data so that a_α′ = R a_α, α = 1, .., N, exactly holds for some R. However, the important issue in practical applications is the case in which the data a_α and a_α′ obtained via 3D sensing or camera images are not necessarily exact, namely the case in which

aα′≈Raα,α=1,..,N.	(1.2)

In practical situations, this problem arises in the process of estimating the motion between two 3D objects. A “motion” (or “Euclidean motion” to be strict) is a composition of translation and rotation. Given a 3D object in motion, we compute its translation and rotation from the locations before and after the motion. To do this, we first translate the object so that a specified reference point, such as its centroid, coincide before and after the motion. Then, the problem reduces to rotation estimation in the form of Eq. (1.2). In order to solve this problem, we need to give an interpretation of “≈” in Eq. (1.2) and mathematically model the data noise. The simplest and the most practical model is to assume that the noise is subject to an isotropic Gaussian distribution of constant variance. Then, the problem reduces to computing an R that minimizes the sum of the squares of the differences between the left and right sides of Eq. (1.2). The resulting R is called the “least-squares solution.” Its computation is sometimes called the “Procrustes problem.”

In Chapter 4, it is pointed out that this least-squares computation is “maximum likelihood estimation” from the viewpoint of statistics and that the solution is obtained by singular value decomposition of a matrix defined by the data. It is also pointed out that the same solution is obtained using the quaternion representation introduced in Chapter 3. We show an important application of this procedure: if we estimate the rotation R from data by some means, the computed R may not be an exact orthogonal matrix. In that case, we need to correct it to an exact orthogonal matrix. This problem arises in may engineering problems involving 3D configuration computation. The solution is obtained using the singular value decomposition.

The least-squares solution minimizes the sum of squares of the discrepancies of Eq. (1.2). In real applications, however, the measurement using 3D sensors often involves errors whose orientation is biased. For example, if we emit laser or ultrasonic waves for 3D measurement, the accuracy is generally different between the emission direction and directions orthogonal to it. The accuracy in the emission direction depends on the wavelength of the emission while the accuracy in directions orthogonal to it depends on the emission direction controller, e.g., servomotor. Such orientation dependence of the measurement accuracy is described by a matrix called the “covariance matrix.” In Chapter 5, we study maximum likelihood estimation from biased data whose covariance matrix is provided. If the noise has no orientation dependence, the covariance matrix is a multiple of the identity...