7
$\begingroup$

I want to approximate the rotation in SO(3) (ie. 3D rotation) that minimizes some objective function.

I'm looking for a SO(3) rotation representation that lends itself to energy minimization. I'm writing a framework that performs minimization on shape parameters, where the goodness of the fit is given solely based on some arbitrary objective function which is a function of a rotation matrix.

One example solution would be to convert euler angles to matrix representation, minimize the objective function as a function of the angle parameters, and convert back to a matrix. This effectively to reparameterizing the objective function into some other rotation representation. However, one problem with euler angles is that the representation does not preserve uniformity and is prone gimbal locking problems. Thus I am afraid it may give biased results or create local minima.

I have heard it is possible to optimize based on quaternion or axis angle representations of 3D rotations, but I have been unable to find a good source or description.

(Added) More specifically. As suggested by Choward in the comments, a solution using quaternions would formaly be: Find some quaternion,$q^*$, that satisfies: $q^*=\arg \min f(R(q))$, where $R(q)$ is a rotation matrix as a function of the quaternion, and $f(\cdot)$ is some cost function being minimized as a function of the rotation matrix.

Edit: typo

Edit2: Added clarification based on comment.

$\endgroup$
  • $\begingroup$ Quaternions is definitely the way to go. Do you have any sample equations you could write out to help show the type of equations you're optimizing? It would make it more clear. I will note that I think this optimization will have local minima whether you use Euler angles or Quaternions. $\endgroup$ – spektr Jul 21 '16 at 16:47
  • $\begingroup$ One objective function I'm using for testing is the sum of squared distances of some set of points X to an ellipsoid. The code calculating the distance is not mine and from what I can gather, it is only possible to write up the distance function implicitly. $\endgroup$ – Dith Jul 21 '16 at 16:59
  • $\begingroup$ In this example, where does the rotation come into play? If you could write out your general problem in a mathematical form, it would be useful. I am thinking you want to, say, find some quaternion,$q^*$,that satisfies: $q^* = \text{arg} \min f(R(q))$, where $R(q)$ is a rotation matrix as a function of the quaternion, and $f(\cdot)$ is some cost function being minimized as a function of the rotation matrix. Is this the general problem you want to tackle? $\endgroup$ – spektr Jul 21 '16 at 17:07
  • $\begingroup$ Yes, that is EXACTLY the problem I want to tackle. I will edit my post to include that clarification. Thank you! $\endgroup$ – Dith Jul 21 '16 at 17:10
  • $\begingroup$ Are you trying to fit an ellipsoid to a set of points $X$ by preserving its shape? And your rotation matrix rotates the ellipsoid until it fits (plus translations too)? Basically you are optimizing over the Euclidean group? Do you need to keep the ellipsoid's shape unchanged or are you allowed to deform it? $\endgroup$ – Futurologist Jul 22 '16 at 13:57
3
$\begingroup$

So your problem statement is to find some quaternion, $q^*$, such that it satisfies the following:

$$ q^* = \text{arg} \min f(R(q))$$

where $f(\cdot)$ is some cost function, and $R(q)$ is a matrix created from some quaternion $q$. Now, this problem can be viewed as a more general problem, such as:

$$ \textbf{x}^* = \text{arg} \min J(\textbf{x})$$

where $\textbf{x} \in \mathbb{R}^4$, and $J(\cdot)$ is a more general cost function. In your case, you can tackle it in a variety of ways. If you can compute $\nabla J$ with respect to $\textbf{x}$, then you can use various gradient based methods. If not, then doing a gradient-free approach can work. Note that you will need to ensure you normalize the input $\textbf{x}$ within $J(\cdot)$ before you feed it into your original $f(R(\cdot))$ cost function.

$\endgroup$
  • $\begingroup$ I somehow thought it was more complicated than this. Looking at the transformation described here (euclideanspace.com/maths/geometry/rotations/conversions/…), it seems the quaternion coefficients does not need be constrained. They simply state the quaternion needs to be normalized before conversion to matrix representation. Do you know if I can simply perform unconstraint minimization on the $x \in \mathbb{R}^4$ and normalize when calculating $R(x)$ or normalize $x$ at each iteration in case the values grow out of control. $\endgroup$ – Dith Jul 22 '16 at 9:21
  • $\begingroup$ @Dith I think I would make the normalization a part of the cost function. Then, whatever your final answer is, you can just normalize it for use in whatever you need. This should then allow you to treat it as an unconstrained optimization problem. $\endgroup$ – spektr Jul 22 '16 at 13:30
  • $\begingroup$ Yes, use Lagrange multipliers, write the cost function as $L(q,\lambda)=J(q)+\lambda(q\bar{q}-1)$ where the quarternion is like four dimensional vector. You can also write the quarternions as a 2x2 matrix algebra $\mathbb{R}•SU(2)$, i.e. the span of the $i$ times the Pauli matrices and the identity. $\endgroup$ – Futurologist Jul 22 '16 at 13:52
3
$\begingroup$

I agree that quaternions are the way to go, as stated in other answers, but let me add a brief note on the axis-angle representation.

Given a vector \begin{equation} \mathbf{v} = \begin{bmatrix}v_1\\v_2\\v_3\end{bmatrix} \end{equation} let \begin{align} \theta & = \lvert \mathbf{v} \rvert & \mathbf{e} & = \frac{\mathbf{v}}{\lvert \mathbf{v} \rvert} & [\mathbf{v}]_\times & = \begin{bmatrix} 0 & -v_3 & v_2 \\ v_3 & 0 & -v_1 \\ -v_2 & v_1 & 0 \end{bmatrix} \end{align} and \begin{equation} \mathbf{R} = \exp([\mathbf{v}]_\times) \end{equation} where $\exp$ is the matrix exponential.

It can be shown that $\mathbf R$ is a rotation matrix corresponding to a rotation of magnitude $\theta$ about axis $\mathbf e$.

An alternative expression of $\mathbf{R}$ is the Rodrigues' rotation formula: \begin{equation} \mathbf{R} = \mathbf{I} + \sin\theta \, [\mathbf{e}]_\times + (1-\cos\theta) \,[\mathbf{e}]_\times^2 \end{equation}

The advantage of this representation is that you can optimise with respect to the three independent parameters $(v_1, v_2, v_3)$. The disadvantage of course is that you have to evaluate a matrix exponential (!) or $\sin(\lvert \mathbf v \rvert)$ and $\cos(\lvert \mathbf v \rvert)$. However a quick and dirty implementation using this representation is almost trivial, especially in a high level language that, like scipy, has a matrix exponential.

$\endgroup$
  • $\begingroup$ Funny. I coincidentally already have a Padé matrix exponential implementation already. Using quaternions seems to work well so far, but I'm really temped to try this as well. I have noticed this representation is also the one used in the geometric tools package (geometrictools.com). $\endgroup$ – Dith Jul 24 '16 at 10:16
  • $\begingroup$ This is a nice approach for minimization IMO, components are quite independent (compared to representations with angles) and also you have no restrictions on parameters. $\endgroup$ – Alleo Jul 25 '16 at 17:23
  • $\begingroup$ I agree with @Alleo: the only drawback of this representation, is that you have to introduce transcendental functions. On the contrary, if you start from the 4 components of a normalised quaternion, you have only plain algebra. $\endgroup$ – Stefano M Jul 26 '16 at 10:52
1
$\begingroup$

Basically the quaternions are the four dimensional Euclidean space together with a division algebra structure. The three dimensional space is the same as the imaginary part of the quaternions. A rotation of three space is given by a unit quarternion $q$ which acts on an imaginary quaternion $x$ by the formula $x \mapsto qx\bar{q}$. Now, one way you can implement rotations is the following: fix a vector in three space, say $\hat{a}=(a_1,a_2,a_3)^T$, write it as an imaginary quaternion $a=a_1 i + a_2 j + a_3 k$ and then a rotation around the vector $\hat{a}$ by angle $\theta$ is written as a unit quaternion in the form $$q = ( \cos{\theta}) + (\sin{\theta}) a.$$ Its inverse is its conjugat $$\bar{q}= ( \cos{\theta}) - (\sin{\theta}) a.$$ Thus, your cost function depends on four parameters $J(\theta,a_1,a_2,a_3) = J(q,\bar{q})$.

Edit: $ \hat{a}$ needs to be a unit vector so that $a$ is a unit imaginary quaternion.

Edit: In general, for any nonzero $q$, a transformation $x \mapsto q x q^{-1}$ of an imaginary quaternion $x$, is also a rotation so normalizing quaternions is not really necessary. This is true for example because $q^{-1} = \frac{1}{|q|^2} \bar{q}$, so $$q x q^{-1} = q x \left( \frac{\bar{q}}{|q|^2} \right) = \left(\frac{q}{|q|}\right) x \left(\frac{\bar{q}}{|q|}\right).$$ So it seem like you can end up with optimizing a function $J(q,\bar{q})$ without constraints.

$\endgroup$
  • 1
    $\begingroup$ Technically you would still have to constrain the components of the $a$ vector such that $a$ has a magnitude of $1$. That's the only way the overall quaternion remains normalized. $\endgroup$ – spektr Jul 23 '16 at 13:30
  • $\begingroup$ Yes that is true, I forgot about that detail. $\endgroup$ – Futurologist Jul 23 '16 at 19:00

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.