high-degree polynomial regression

April 2003

This is where principal component analysis [3] comes handy. If we represent motion data as a matrix, we can do SVD (*singular value
decomposition*)
and obtain a set of singular values, whose magnitude indicates how important
is the particular component in the whole matrix. By cutting off less important
components, we can represent slightly altered version of original matrix
with less data.

Let us suppose our motion data is represented as a rectangular matrix **A**. Singular value decomposition allows us to
factorize **A** into three special matrices: **A**=**USV**. **U** and **V** are our new principal component
matrices, and **S** is a diagonal matrix, with *singular values* on the diagonal. For a data matrix **A** representing human
motion clip, the graph of its singular values looks like this:

As a demonstration of correlation removing ability of PCA we will include
two illustrations below. One shows the original 128 curves of the motion
clip, while the other is a graph of 10 principal components of that clip's
motion data matrix.

**fftgraphd.exe**

is a binary executable for Windows, it launches a local copy of Matlab when
started. Then it establishes COM link with Matlab and uploads motion data
into the Matlab's workspace as a rectangular matrix. The Matlab script **mfit.m**

provides GUI for the data manipulation tasks. The GUI
window together with brief description of its controls is depicted below:
**Enter**

on the keyboard.
After that the control menu appears in the upper left corner of the player window.
**Quit**

item in the menu and press spacebar on the keyboard.
To switch between original and Matlab processed motion, the user has to select the

menu item with up and down arrows, and use left/right arrows to switch motion
type. Left and middle mouse buttons allow the user to control the camera
- orbiting, panning and zooming.**Motion**

**fftgraphd filename**

in the
operating system's command prompt, where filename points to the motion data file. After that two windows appear on the screen.
One is the player's window and the other is the Matlab COM server window. Now the user has to change to the directory with
**mfit.m**

and issue command **mfit**

in
the Matlab window. The GUI window comes up and the system is ready to process
motion data. To load another motion clip, quit the player, reload it with
a new motion data file and also restart GUI by closing it and typing **mfit**

in Matlab again. After each data processing session you can observe the
resulted motion by switching to the motion player and choosing original motion and then Matlab processed one. This will refresh
motion data in the player by reloading it from Matlab.The set of motion data files included with the system is described below.

- run followed by sharp turn and fall**255_3_or.o**

- slightly crouched run followed by collision, roll and fall**255_3_st.o**

- plain run**256_1_or.o**

- run, collision, squat and run in the opposite direction**256_1_st.o**

- run, collision and fall**257_3_or.o**

- run followed by violent collision, short flight in the air and fall**257_3_st.o**

- run with mild collision in the middle**258_3_or.o**

- run, sharp turn with crouching and almost losing balance followed by run in the opposite direction**258_3_st.o**

- run and fall forward**259_2_or.o**

- run, collision, losing balance, fall and roll over**259_2_st.o**

**Motion type**

group of checkboxes controls display of the original motion curves, smoothed curves and
post-PCA curves. Read on to understand what they are. **PC display**

checkboxes control the appearance of the principal
component curves, both original and fit ones.
- Stage 1: smoothing. Done by the averaging low-pass filter. Gets rid of high-frequency motion components, thus making it possible to keep less principal components of the motion data matrix.
- Stage 2: dimensionality reduction through PCA. Done by singular value decomposition followed by pruning unimportant components of the motion data matrix.
- Stage 3: high-degree polynomial regression. Done by linear least squares polynomial fitting. Note that we try to fit the principal component curves obtained in stage 2, not the original motion ones.

**Filter strength**

slider at the bottom left
of the GUI window. The wider is the window - the smoother are the resulting curves.
**Principal components**

slider to the
right of the **Filter strength**

slider. The more principal components are being kept - the less is the compression
ratio and the better is the resulting motion quality.
Fit precision calculation code in the system is a bit tricky. It tries to adjust the fit error tolerance according to the
importance of the particular curve, or its *weight* in restoring matrix **A**.
Obviously, human skeleton joints have various importance in locomotion. For
example hip or waist joints are much more important during run or jump than
finger or neck joints. On the other hand, the same effect is observed after
PCA - certain singular values have much larger magnitude than the others.
Hence we have to do our best to avoid *flat error tolerance* where it is set to the same value for all curves being fit.

Second pass is done over the results of the first pass. Now we adjust error tolerance for each curve once more, except for the most important one. This time we employ singular values directly (instead of the curve span) as a guide in the process. We multiply each error tolerance by the fixed fraction of the reciprocal of singular value for that curve. Currently fraction coefficient is set to 0.2, this value seemed to be optimum during experiments with mocap data compression. The smaller is the singular value - the larger is its reciprocal and hence the looser will be the polynomial approximation.

All these highly technical details mean one important thing - value of a slider**Fit precision**

is just a guide.
The user suggests the system how precise he wants the fit to be, and the system distributes error tolerance values among curves
according to that guide and curve importance.
**Original.**Number of samples in the original motion data matrix**A**.**Post-PCA.**Number of samples in the pruned principal component matrix**Uc**.**PCA ratio.**Ratio between two values above. The larger it is - the better is PCA compression.**CPC ratio.***Current Principal Component*ratio. Ratio between a number of polynomial coefficients necessary to restore a currently selected principal component curve and a number of samples in that curve. The larger value indicates better compression.**TPC ratio.***Total Principal Component*ratio. This is the same as above but summarized over all the principal component curves.**Total ratio.**Ratio between the total number of polynomial coefficients for all the principal component curves plus the number of samples in the transformation matrix**D**and the number of samples in the original motion data matrix**A**. In fact, this is reasonable approximation to the real compression ratio produced by the production-quality system similar to our prototype. The larger is this value - the better is overall compression.

First, it has a lot of uncorrelated data in it, because run plus sharp turn
plus fall constitutes "chaotic" limb motion. Chaotic in the sense "uncorrelated".
This forces us to keep more principal components in matrix **Uc**.

A serious disadvantage of our framework is total lack of scientific measure of motion quality. All measurements were done just by observing compressed motion in the player. The author admits that all that has been said about "reasonable" motion quality is highly subjective matter. However, finding and proving good metric for compressed motion quality would constitute a topic of research by itself.

Another major disadvantage is the choice of model equations. Polynomials are not only the poor approximation equations for many types of curves common in animation (such as much discussed above straight lines), they also could be extremely expensive as a tool of compression for video games. Evaluating numerous polynomials of degrees between 8 and 18 for a small motion clip is not the way to go.The last important thing worth mentioning is recurring again and again importance of storing certain constraints together with animation data. Foot-floor contact points are the best example. By storing and using them in compression, we could possibly avoid main artifact occurring during compression - sliding feet. It is likely that we could compensate for additional storage requirements for these constraints by applying more powerful and more lossy compression methods.

`S. Sudarsky and D. House.`

*Motion capture data manipulation and reuse via B-splines.*`D. Cuthbert and F. S. Wood.`

*Fitting equations to data.*John Wiley & Sons, 1980.`Z. Ghahramani and G. E. Hinton.`

*Parameter estimation for linear dynamical systems.*