Doc Ok's Move tracking

[Alexander Nitsch]

Hello list.

Some of you may remember the PS Move tracking test video at
https://www.youtube.com/watch?v=0J5LaWykiIU. Oliver says he stopped
working on the tracker after publishing the video, but he generously
provided the source code (GPL'ed, attached) and the following
description of the underlying algorithm:


> The core algorithm is surprisingly simple. Find the left and right
> edges of horizontal pixel spans that match the configured bulb color
> up to some threshold, and create one linear equation for every edge
> pixel. Throw those into a least-squares system to solve for the axis
> vector of a cone of variable opening angle (parametrized as a
> non-unit length 3d vector) that envelops all edge pixels. Then
> iterate the algorithm to remove edge pixels that don't lie on the
> convex hull, due to partial occlusion.
>
> The equation system is simple as well. A cone with some axis a = (ax,
> ay, az) and opening angle alpha is defined by cos(alpha) = (a*p) /
> (|a|*|p|),
>
> where p = (px, py, pz) is the ray in 3D camera space associated with
> some image pixel.
>
> The trick to solving this non-linear system is to re-parametrize.
> Given that a always points from the camera's optical center out into
> camera space, and az is therefore <0, we can introduce a new unknown
> a' = a/-az = (ax', ay', -1) = (ax/-az, ay/-az, -1). Then
>
> cos(alpha) = (a'*az*p) / (|a'*az|*|p|) = (a'*p)*az / (|a'|*az*|p|)
> = (a'*p) / (|a'|*|p|)
>
> Now we multiply both sides by (|a'|*|p|), yielding
>
> cos(alpha)*|a'|*|p| = a'*p,
>
> and introduce another new variable, az' = cos(alpha)*|a'|, yielding
>
> az'*|p| = a'*p = (ax', ay', -1)*(px, py, pz)
>
> This is a linear system in ax', ay', and az', which can be solved
> using a standard least-squares method.
>
> After solving, the cone's normalized central axis is axis0 =
> a'/|a'|, and the opening angle is alpha = acos(az'/|a'|).
>
> Once you have the opening angle, you can calculate the ball's
> position along the axis ray via simple trigonometry, assuming that
> the calculated cone is a tangential envelope to a sphere of the the
> ball's radius:
>
> ballPos = axis0*(ballRadius/sin(alpha))
>
> I'm attaching the source code for the tracking visualization utility
> I showed in the video. It's under the GNU General Public License.
> The actual tracking happens in PSMoveTracker::trackingThreadMethod.
> Besides the core algorithm, important fine points are lens
> distortion correction, and calculating (distortion-corrected) pixel
> rays that are half a pixel to the left when starting a span, and half
> a pixel to the right when ending a span, otherwise one introduces
> systematic bias.
>
> Properly done, the algorithm requires no magic parameters or
> non-linear correction after solving the least-squares system.
>
> Hope this helps,
>
> Oliver
>
> --
> Email: kre...@cs.ucdavis.edu
> WWW: http://idav.ucdavis.edu/~okreylos/ResDev
> Blog: http://doc-ok.org