Least Squares

Basic least square formula

Ax = b
where you solve for x: x = (A^T * A)^-1 * A^T * b

Least Square For Bsplines

When fitting bsplines these are the values for A, x, and b.

            / Nd0(t0) ... Ndn(t0) \
            | .             .     |
        A = | .             .     |
            | .             .     |
            \ Nd0(tk) ... Ndn(tk) /
        

                                   
            / C0 c         / Q0 \
            | .  |        |  .  |         
        x = | .  |    b = |  .  |      
            | .  |        |  .  |         
            \ Cn /         \ Qn /
        

where

• N is the bsplien basis function
• d is the dimention (3 in my case)
• n is the number of control points in the spline
• k is the number of sample points
• C is a control point
• Q is a sample point

Least Square For Bsplines - Fixed Points

Usualy we want the end points of the samples to be the end points of the curve. To fix a control point to a sample point, set C_i = Q_j. Now our matrix A has extra rows and columns. Remove row i. Remove column j but save it in another matrix (lets call it R). This is because we need to modify the samples so least squares still takes the fixed points into account.

so the new modified formula is: x' = (A'^T * A')^-1 * A'^T * (b' - R * q)
with

                                   
            /    |    |   \            
        R = | Ai1| ...| Aim|     
            \    |    |   /       
            
            /  bj1 \
            |  .   |
        q = |  .   |
            |  .   |
            \  bjp  /
        

• A' is A with removed rows and columns
• x' is x with the fixed control points removed
• b' is b with the fixed sample points removed
• A_i are the removed columns of A
• b_j is a fixed sample point

Implementation

generic m x n matrix template class, yay!

References

"Distrotion Minimization and Continutit Preservation in Surface Pasting", Ricky Ying-Kei Leung

• had least squares fitting with fixed endopoints