# “Normalizing” Points on a Sphere

I have a set of points on a unit sphere representing different orientations:

Now I need to apply rotation(s) such that the points will lay on the horizon as tightly as possible:

The ideal representation for rotation would be YPR (Yaw-Pitch-Roll), but any axis-angle representation would suffice.

Here is where I got up to now:

1. Find "centroid" orientation for the given orientations (How to find centroid of points laying on sphere?) The result would be some vector $u=(x,y,z)^{\mathbb{T}}$, $||u||=1$

2. Compute normalizing yaw and pitch angles (maybe using atan2 ?) so that the rotated vector $u'=(0,0,1)$

3. Compute roll angle (around $u'$) so that the points lay on the horizon line (the horizon is intersection of the sphere and a plane $y=0$). Maybe a least squares approach? Or compute average of normalizing angles for the points?

The problem arises in panoramic image stitching where I need to remove "wavy" effect from the projected mosaic (every image is represented by rotation around common center):

Note that the full 360° mosaic is a special case. I need to "straighten" partial mosaic as well, which are like the bunch of points depicted above.

-
What I would do is find the normal to the horizon first, as in your previous question. Once that is fixed, you're left with the much simpler one-dimensional problem of choosing the rotation about the normal, or equivalently, of choosing the horizontal center of the flattened image. –  Rahul Apr 14 '12 at 1:41
Thanks. The problem is that I also need to straighten partial mosaics as well. The mosaic can also contain several rows of images and user can choose an arbitrary central point, so that I am afraid the "up-vector" approach would not work always. Sometimes the mosaic can be vertically oriented (e.g. tower image) and then the roll rotation should be completely omitted. –  Libor Apr 14 '12 at 9:02
I'm afraid I don't understand the point of your comment. How does the arrangement of images in the mosaic relate to the question of rotating points on a sphere to lie on the equator? I assumed you had the images registered on the sphere already, with points on the horizon marked, and only needed to choose the view direction to project the mosaic onto a plane so that the horizon is drawn horizontal. Am I misunderstanding your problem? –  Rahul Apr 14 '12 at 23:38
Yes you understand it right. The problem is that I need to split the global rotation of the mosaic to three parts (yaw, pitch, roll), because there are other considerations because of which I cannot use the simple approach from the previous question. First, user can choose hiw own center point (it can also be chosen based on existing direction to choose the "most central" one). Second, the roll may not sometimes be used (e.g. when the mosaic is taken diagonally or vertically). This is why I need to split the process in three rotations and find the corresponding angles... –  Libor Apr 15 '12 at 11:03
IMHO, switching to yaw/pitch/roll too early in your calculations is a serious mistake here; they're a notoriously miserable representation of rotations for problems like this because they have almost none of the properties you'd like your orientation to have. I'd much rather work with a quaternion or matrix representation here (where rotations can be easily composed, for instance) and only convert to Euler angles at the very last step. –  Steven Stadnicki Jul 19 '12 at 17:20

Here's one idea, trying hard not to have any bias stemming from the initial orientation of the sphere:

1. Represent your points in euclidean 3-d coordinates with the unit sphere centered at $(0,0,0)$.
2. Take cross product of all pairs of points (or a random sample of pairs if you have many points and $O(n^2)$ is too much work).
3. Select the numerically largest cross product and adjust the sign of all others such that each makes an acute angle with it.
4. Add the sign-adjusted cross products. The direction of the resulting vector is the one you want to move to the north pole by your rotation.
-
+1: this is the first thing that came to mind for me, too. –  Steven Stadnicki Jul 19 '12 at 17:21

A different idea, supposing that in your application the points already almost line up with the equator, such that they can be normalized by a small rotation around some horizontal axis:

Assume we have the points given in "geographical" coordinates with latitude $\phi$ and longitude $\lambda$. For points close to the equator, a small rotation about a horizontal axis will act like $$(\phi,\lambda) \mapsto (\phi - \alpha\cos(\lambda+\psi), \lambda)$$ where $\alpha$ measures the amount of rotation and $\psi$ is a phase term determining the orientation of the rotation axis.

Now if $\alpha$ and $\psi$ are both unknown we can represent the north-south adjustment instead as $a\cos \lambda + b\sin\lambda$ for some (also unknown) coefficients $a$ and $b$. However in this form we can estimate the best $a$ and $b$ by a standard least-squares fit to the $\phi$ coordinates of our known points.

Once $a$ and $b$ are known, it's a matter of standard trigonometry to derive $\alpha$ and $\psi$ from them. We can then do the actual rotation of the sphere by rotating by angle $\psi$ around the $z$ axis and then by $\alpha$ around the $x$ axis.

-
Thanks for your valuable hints! I am currently thinking about least squares approach. I have a clue from your answer that averaging $\Phi$ and $\lambda$ will suffice to find the centroid. Computing yaw and pitch then will be straightforward (using atan2 to find normalizing angle). Finally, the roll angle would be found using least squares approach or maybe by computing normalizing roll angle for each point and averaging that, but I am not sure. –  Libor Apr 14 '12 at 9:11
How are you going to average $\lambda$, which is not a linear space? What would you take the "average" of {45°, 135°, 225°, 315°} to be? –  Henning Makholm Apr 14 '12 at 15:08
I assume $\lambda$ does not depend on $\Phi$ so I can simply average the values (e.g. one image pointing in 35° direction and other in -60° ... the average is $(35-60)/2$). –  Libor Apr 14 '12 at 17:49
And what is the average of {45°, 135°, 225°, 315°}? –  Henning Makholm Apr 14 '12 at 20:50
180°. If the angles correspond to yaw ($\lambda$), then the direction of 180° points backwards. –  Libor Apr 15 '12 at 11:06