Skip to content

Small note on Quaternion distance metrics

January 7, 2013

There’s multiple ways to measure distances between unit quaternions (a popular rotation representation in 3D). What’s interesting is that the popular choices are essentially all equivalent.

Polar form

A standard way to build quaternions is using the polar (axis-angle) form
q = \exp(\frac{1}{2} \theta \mathbf{n}) = \cos(\theta/2) + \sin(\theta/2) (i n_x + j n_y + k n_z), where n is the (unit length) axis of rotation, θ is the angle, and i, j and k are the imaginary basis vectors.

For a rotation in this form, we know how “far” it goes: it’s just the angle θ. Since the real component of q is just cos(θ/2), we can read off the angle as
\theta(q) = \theta(q, 1) := 2 \arccos(\textrm{real}(q)) = 2 \arccos(q \cdot 1)
where the dot denotes the quaternion dot product.

This measures, in a sense, how far away the quaternion is from the identity element 1. To get a distance between two unit quaternions q and r, we rotate both of them such that one of them becomes the identity element. To do this for our pair q, r, we simply multiply both by r’s inverse from the left, and since r is a unit quaternion its inverse and conjugate are the same:
\theta(q,r) := \theta(r^*q, r^*r) = \theta(r^*q, 1) = 2 \arccos((r^*q) \cdot 1)

Note that cosine is a monotonic function over the interval we care about, so in any numerical work, there’s basically never the need to actually calculate that arc cosine: instead of checking, say, whether the angle is less than some maximum error threshold T, we can simple check that the dot product is larger than cos(T/2). If you’re actually taking the arc cosine for anything other than display purposes, you’re likely doing something wrong.

Dot product

Another way is to use the dot product directly as a distance measure between two quaternions. How does this relate to the angle from the polar form? It’s the same, as we quickly find out when we use the fact that the dot product is invariant under rotations:

(q \cdot r) = (r^*q \cdot r^*r) = (r^*q \cdot 1)

and hence also

\theta(q,r) = 2 \arccos(q \cdot r)

So again, whether we minimize the angle between q and r (as measured in the polar form) or maximize the dot product between q and r boils down to the same thing. But there’s one final choice left.

L2 distance

The third convenient metric is just using the norm of the difference between the two quaternions: ||q-r||. The question is, can we relate this somehow to the other two? We can, and as is often the case, it’s easier to work with the square of the norm:

||q-r||^2 = ||q||^2 - 2 (q \cdot r) + ||r||^2 = 1 - 2 (q \cdot r) + 1 = 2 (1 - q \cdot r).

In other words, the distance between two unit quaternions again just boils down to the dot product between them – albeit with a scale and bias this time.

Conclusion

The popular choices of distance metrics between quaternions all boil down to the same thing. The relationships between them are simple enough that it’s easy to convert, say, an exact error bound on the norm between two quaternions into an exact error bound on the angle of the corresponding rotation. Each of these three representations is the most convenient to use in some context; feel free to convert back and forth between them for different solvers; they’re all compatible in the sense that their minima will always agree.

UPDATE: As Sam points out in the comments, you need to be careful about the distinction between quaternions and rotations here (I cleared up the language in the article slightly). Each rotation in 3-dimensional real Euclidean space has two representations as a quaternion: the quaternion group double-covers the rotation group. If you want to measure the distances between rotations not quaternions, you need to use slightly modified metrics (see his comment for details).

About these ads

From → Maths

4 Comments
  1. I’m afraid there’s a serious problem here. Cosine is not monotonic over the interval we care about, because that interval has size 2π, not π.

    The « distance » between two rotations cannot be reduced to θ(q,r) = 2acos((q/r)·1) because there would be a discontinuity at 2π: when θ goes beyond π the rotations are actually becoming closer to each other. Luckily this can be fixed using a simple absolute value: θ(q,r) = 2acos(|(q/r)·1|)

    Similarly, the L2 metric is not a proper measure of how far apart two rotations are. You can just use 2(1-|q·r|) instead. (By the way, if you only care about monotonicity, you can just drop the 2!)

    One last note: some people believe (and some write in books and articles) that enforcing rules such as q.w ≥ 0 when storing or creating quaternions will magically fix the problem. It will not.

    • Note that, in the polar form, we are taking the cosine of θ/2, not θ directly, and similarly all other forms measure half-angles not angles. I’m a bit careless in using the term “rotation” here though; technically, the metrics defined here are over the quaternions (i.e. spinors), not the rotations they represent (the problem here is that the quaternion group provides a double-cover of SO(3), so each rotation has two representations as quaternions; if q represents a given rotation, so does -q).

      Cosine is monotonic over [0,π], which is enough to cover quaternions up to 2π apart (as measured by the angle in the polar form). There is no discontinuity here! The distance is nonzero because two rotations 2π apart actually have distinct quaternions; due to the double-cover, the period is indeed 4π. Because of this period, two quaternions can’t be apart by further than 2π – you can, figuratively speaking, just go the other way round (and indeed our distance metric will slowly decrease, until at 4π we again report a distance of 0). This is not a bug and does not need “fixing”, because sloppy terminology on my part aside, this post is really (as the title states) about distance metrics on quaternions, not rotations. While you can enforce 2π-periodicity like you mention, this is usually not the right thing to do; slathering quaternion-handling code in neighborhooding operations (whether it be enforcing a nonnegative real part or something else) usually causes more problems than it solves; when properly used, quaternions double-covering the rotation group is a feature, not a bug.

      • Sure, if you consider the class of rotations spanning 4π you’re perfectly right in all respects here. I think I just wish it was made clearer to the reader that they must be careful to use the shortcuts if their set of quaternions conver the more naive 3D rotations rather than the doubly covered ones, then.

  2. Marc B. Reynolds permalink

    aside: I’ve always had a pet peeve about the double-coverage thing. p’=qp(1/q), which can be simplified to p’=qpq* with assumption that ||q||=1. The first version all lines thorough the origin (excluded) represent the same orientation. The second version becomes a scaled (by ||q||^2) orientation if you ignore the restriction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 183 other followers

%d bloggers like this: