A Dynamics Optimization

Large dynamic systems like those described in Section 2.1 are difficult to engineer. There are many parameters that must be chosen, and furthermore there are few guidelines available, so, often a great deal of expertise with dynamic simulation is required to realize a working system. This sort of system is also computationally rather costly: the system described above consumes nearly 100% of a 500MHz Alpha 21164 processor.

The above system can be easily converted to an energy-based kinematics engine as describe by Witkin [21], by dropping the integration over acceleration. Here are the update equations for the dynamic case using the synchronous Euler method:

$$\ddot{\bf q}_t {\bf W} \cdot {\bf Q}$$ =

$$\dot{\bf q}_t \dot{\bf q}_{t-1}+\Delta t \cdot \ddot{\bf q}_{t-1}$$ =

$${\bf q}_t {\bf q}_{t-1} + \Delta t \cdot \dot{\bf q}_{t-1}$$ =

and here are the modified equations for the kinematic case:

$$\ddot{\bf q}_t {\bf W} \cdot {\bf Q}$$ =

$$\dot{\bf q}_t \Delta t \cdot \ddot{\bf q}_{t-1}$$ =

$${\bf q}_t {\bf q}_{t-1} + \Delta t \cdot \dot{\bf q}_{t-1}$$ =

notice the change in calcuation of $\dot{\bf q}_t$. In this form the system retains all it's power to find minimal solutions to multiple constraints and continues to be a fertile ground for sensor fusion. However, it loses its grip on Newtonian reality, and with that, much of its predictive power.

Fortunately there are other ways of making predictions about dynamic systems, including Kalman filters. Linear Kalman filters are computationally efficient, and, while Kalman filters also have a large number of parameters that must be chosen, there is a mature literature on the subject [1]. The update equation for the linear Kalman filter is the matrix form of the dynamic update equations above:

$$\left[ \begin{array}{c} {\bf q}_t \\ \dot{\bf q}_t \\ ... ...\ \ddot{\bf q}_{t-1} \end{array} \right] + {\bf w}_{t-1}$$ (7)

where ${\bf\Phi}_{t-1}$ is the system transition matrix. In our system $\bf { \Phi}$ is constant and represents a constant acceleration model Deviations from that model are captured in the random vector ${\bf w}$ that represents the system noise. Kalman filters don't require multiple calculations per observation to converge. At each observation time the optimal state estimate is calculated with the well known linear equation:

$$\left[ \begin{array}{c} \hat{{\bf q}}_{t\vert t} \\ \hat... ...hat{\ddot{\bf q}}_{t\vert t-1} \end{array} \right] \right)$$

Where ${\bf K}_t$ is the current Kalman Gain, and ${\bf y}_t$ is the observed 3-D position. ${\bf H}_t$ is the linear map between observation vector and the state vector. ${\bf H}_t$ can be linear since the perspective non-linearities are resolved by another part of the system as described in Section 2.2. ${\bf H}_t$ may be time-varying depending on the availability of observations at time t. The Kalman gain ${\bf K}_t$ is computed in the standard way, recursively calculating several internal covariance matrices including the error covariance estimate ${\bf P}_{t\vert t}$:

$${\bf P}_{t\vert t} = \left( {\bf I} - {\bf K}_t {\bf H}_t \right) {\bf P}_{t\vert t-1}$$

where ${\bf P}_{t\vert t-1}$ is the previous error covariance prediciton:

$${\bf P}_{t\vert t-1} = {\bf\Phi} {\bf P}_{t-1\vert t-1} {\bf\Phi}^T + {\bf R}$$

and ${\bf R}$ is the covariance of ${\bf w}$ in Equation 7. ${\bf P}_{t\vert t-1}$ is a measure of our confidence in our predictions. The norm $\Vert{\bf P}_{t\vert t-1}\Vert$ is used as a confidence metric by the observation model described in Section 2.2.1. ${\bf P}_{t\vert t-1}$ is also used to update ${\bf K}_t$:

$${\bf K}_t = {\bf P}_{t\vert t-1} {\bf H}^T_t \left[ {\bf H}_t {\bf P}_{t\vert t-1} {\bf H}^T_t - {\bf R} \right]^{-1}$$

For a detailed derivation of these equations see Gelb [1].

A system that uses one such individual Kalman filter per tracked body part demonstrates good local tracking characteristics (in fact, optimal characteristics for some narrow definition of the word), but are subject to the failing that they occasionally make predictions that, taken together, violate the global, known constraints of the system. By linking independent Kalman filters together with the kinematics-only constraint formulation, we achieve qualitatively identical performance to the full-dynamics implementation with significantly less engineering and only 15% utilization of the same 500MHz Alpha 21164 processor. The state estimates of the Kalman filter simply become the goals for the constraint system. The kinematics iterate to a globally consistent answer, and those results then become the new state estimates.

A more intimate connection could be achieved with considerably more work and computation by using the Jacobians calculated in the constraint system to guide extended Kalman filters, but we didn't find this to be necessary.

It's important to remember that these linear Kalman filters sit within the larger recurive estimation framework described in the rest of this paper. They share the ``Dynamics'' box in Figure 1 with the constraint system.