1
$\begingroup$

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$.

1 Answers 1

2

$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$.

  • 0
    But I don't know $z$. That's what I'm looking for. I edited the question to be more clear.2012-08-03
  • 0
    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.2012-08-03
  • 0
    $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.2012-08-03
  • 0
    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)$2012-08-03
  • 0
    Yes, that is correct.2012-08-03
  • 0
    Ok, thank's. One more thing, in other websites, for example http://elonen.iki.fi/code/tpsdemo/#page-comments, he said that $K_{ij}=r^2*log(r)$ with $r=||(x_i,y_i)-(y_i,y_j)||$ and in the publication $r=||(x,y)−(x′,y′)||$ where $(x′,y′)$ correspond to the new location of my points (after warping using optical flow). Obviously the result is not the same. So I don't understand why in the publication he used warped coordinates ? Or is it used only to find the new $z'$ ?2012-08-03
  • 0
    I think one of them is a typo. $r$ is the distance between the two points. So $r_{ij}=\|p_i-p_j\|$ (used in $K_{ij}$) is the distance between points $p_i$ and $p_j$.2012-08-03
  • 0
    It's weird, when I try the algorithm with the example http://www.engineering.uiowa.edu/~aip/papers/bookstein-89.pdf p.571, I have exactly the same ouput vector. But it does not converge at all with my data. If 2 control points cross each other after warping, can it break the algorithm ?2012-08-06
  • 0
    Maybe I should make a new question ?2012-08-06
  • 0
    Actually, it's not that because even if I erase cross points, it still doesn't converge.2012-08-06
  • 0
    In that case, I's not sure. I have not spent a substantial amount of time with this particular thin plate formulation, nor with the solution technique you want to use. I do recall that it was a difficult problem to solve at the time. All the best.2012-08-06
  • 0
    I found that with a few data, the algorithm converges correctly but if I have more than 18 points, it diverges. Maybe because I'm not using a preconditionned conjugate gradient. I will create another thread to explain my problem.2012-08-07
  • 0
    Conjugate gradient won't work as the matrix $\begin{pmatrix}A&B\\B^T&0\end{pmatrix}$ is indefinite, even if $A$ is spd.2012-08-07
  • 0
    Actually, I don't understand why I have so much problem to resolve this equation as I have the same number of unknown and equations.2012-08-07
  • 0
    As I said in my previous comment, the coefficient matrix is indefinite. Also, I recall that for my problem, it was also poorly conditioned. Both of those things make for slow convergence of any iterative method.2012-08-07
  • 0
    There is something I omitted to say because I thought it would complicate the problem. There is a regularization term in the equation, when $r=0$ I add a term to avoid the $0$ in the diagonale of $K$. In this case, the matrix is invertible and I just invert it to resolve it. It is computationally very expensive so I think I will swap for a LU decomposition as other people do for resolve a thin plate spline. Thank's for your help.2012-08-09