# Resolve a thin plate spline function

I am trying to keep the outline of an object in a video. So I have the coordinate of the outline of the object in the image $t$ and after computing the optical flow I have the coordinate in the image $t+1$. However, as the optical flow contains error, I would like to interpolate the outline using the thin plate spline function.

I would like to resolve the thin plate spline function in (3) p.5 from the paper http://www.tc.umn.edu/~baixx015/Xue_Bai_mirage_2011.pdf which is $$f(x,y) = c_0 + c_xx + c_yy + \sum_{i=1}^M{c_i \phi(||(x,y)-(x_i',y_i')||)}$$ with M number of points and $$\phi(r)=r^2log(r)$$ which gives me in matrices this equation $$\left[ \begin{array}{ c c } K & T\\ T' & 0 \end{array} \right] \left[ \begin{array}{ c} c \\ d \end{array} \right] = \left[ \begin{array}{ c} z \\ 0 \end{array} \right]$$ where $K$ is $r^2log(r)$, $T$ is $(1,x_i,y_i)$, $c$ is $(c_i)$, $d$ is $(c_0, c_x, c_y)$ and $z$ is what I am looking for and correspond to $f(x,y)$.

I want to try the Uzawa's algorithm described in this document p.33 http://alexandria.tue.nl/extra1/afstversl/wsk-i/ghosh2010.pdf which can resolve equations of type: $$\left[ \begin{array}{ c c } A & B\\ B' & 0 \end{array} \right] \left[ \begin{array}{ c} x \\ y \end{array} \right] = \left[ \begin{array}{ c} b \\ c \end{array} \right]$$ As Daryl said $b=z$ and $c=0$ but I still don't know $z$.

I don't understand how he knows the vectors $b$ (or $z$) If we choose $x_0$ and $y_0$, we can compute a $b_0$ but he does not explicitly say to do that and recompute $b$ at every iteration. Also he said p. 25 that Azawa's method allows to resolve directly the thin plate spline equation.

So in the algorythm, I compute vectors c and d and after that i can compute b.

EDIT:

I tried with the conjugate gradient to resolve $Ax=b$ where $A= \left[ \begin{array}{ c c } K & T\\ T' & 0 \end{array} \right]$, $x = \left[ \begin{array}{ c } c\\ d \end{array} \right]$ and $b = \left[ \begin{array}{ c } z\\ 0 \end{array} \right]$ but it doesn't seem to converge. I think I don't understand what I have to put in $b$.

$b$ and $c$ do not need to be computed. They are the block sections of the RHS vector of the equation. (See (4.9) on p. 33)

In your equation given above, $b=z$ and $c=0$.

• But I don't know $z$. That's what I'm looking for. I edited the question to be more clear. – Seltymar Aug 3 '12 at 0:37
• Maybe I totally misunderstood the equation. Is $z$ correspond to the target control points ?? I thought that $(x',y')$ were coordinates of target control points. – Seltymar Aug 3 '12 at 1:28
• $z$ is the vector of values which are to be approximated by $f(x,y)$. I.e. $(x_i,y_i,z_i)$ is point $i$ of $n$ in 3D space. In higher dimensions, it is the coordinate which is being estimated. – Daryl Aug 3 '12 at 7:54
• If I understood, I know the $z$ vector (which is the optical flow in my case) and I try to approximate it with the function $f(x,y)$. So I have to find $c$ and $d$ for $z$ and therefore I can approximate a new $z'$ using $f(x,y)$ – Seltymar Aug 3 '12 at 8:22
• Yes, that is correct. – Daryl Aug 3 '12 at 8:36