0
$\begingroup$

In Computer Vision Algorithms and Applications book by Richard Szeliski, the author explains 2D alignment using least squares as follows:

Given a set of matched feature points ${(x_i, x_i')}$ and a planar parametric transformation of the form $$x' = f(x;p),$$ how can we produce the best estimate of the motion parameters $p$? The usual way to do this is to use least squares, i.e., to minimize the sum of squared residuals $$E_{LS} = \sum{\lVert{r_i}\rVert^2} = \sum{\lVert{f(x_i,p)-x'}\rVert^2},$$ where $r_i$ is the residual between the measured location $x_i'$ and its corresponding current predicted location $f(x_i; p)$.

Many of the motion models presented in Section 2.1.2 and Table 2.1, i.e., translation, similarity, and affine, have a linear relationship between the amount of motion $\Delta{x} = x'-x$ and the unknown parameters $p$, $$\Delta{x}=x'-x=J(x)p$$ where $J=\partial{f}/\partial{p}$ is the Jacobian of the transformation $f$ with respect to the motion parameters $p$ (see Table 6.1). In this case, a simple linear regression (linear least squares problem) can be formulated as $$E_{LSS} = \sum{\lVert{J(x_i)p - \Delta{x_i}}\rVert^2}$$

Question: In the last equation, what is the point of trying to minimize the difference between $J(x_i)p$ and $\Delta{x_i}$? What is a higher-level interpretation?

$\endgroup$
1
$\begingroup$

The set of feature points $\boldsymbol{x}_i$ and $\boldsymbol{x}^{\prime}_i$ is given, and you want to optimize the parameters $\boldsymbol{p}$ of a given planar transformation $\boldsymbol{f}(\boldsymbol{x};\boldsymbol{p})$ such that it predicts the actual transformation from $\boldsymbol{x}_i$ to $\boldsymbol{x}^{\prime}_i$ with minimum error. In this way, the parametric transformation optimally describes (and predicts) the actual transformation.

One way to do this is to minimize the error between the actual difference $\Delta\boldsymbol{x}_i=\boldsymbol{x}^{\prime}_i-\boldsymbol{x}_i$ and the difference predicted by the chosen transformation. The predicted difference is formulated in terms of the Jacobian of the transformation $\boldsymbol{f}(\boldsymbol{x};\boldsymbol{p})$ in order to get a linear least squares problem (which is easy to solve): ${\Delta\widehat{\boldsymbol{x}}_i}=\boldsymbol{J}(\boldsymbol{x}_i)\boldsymbol{p}$.

So the error to be minimized is given by

$$\sum_i\left[{\Delta\widehat{\boldsymbol{x}}_i}-\Delta\boldsymbol{x}_i \right]^2=\sum_i\left[\boldsymbol{J}(\boldsymbol{x}_i)\boldsymbol{p}-\Delta\boldsymbol{x}_i \right]^2\tag{1}$$

Chosing the parameters $\boldsymbol{p}$ that minimize $(1)$ minimizes the average squared error between the actual feature point difference $\Delta\boldsymbol{x}_i$ and the one predicted by the transformation $\boldsymbol{f}(\boldsymbol{x};\boldsymbol{p})$.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ You beat me to it; I come back just now about to answer my own question! One can also try to minimize $\Delta{\widehat{x_i}} - \Delta{x_i}$, which is just an indirect way to minimize $\widehat{x_i} - x_i$. $\endgroup$ – IgNite Aug 25 '19 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.