Finding rotation and translation using (residual) vectors

214 Views Asked by At

enter image description here

As illustrated in Fig.1 I have $n$ (blue) straight lines represented by $F = \{f_1(x),f_2(x) \dots f_n(x)\}$. These lines passes through the (yellow) straight line $g(x)$. Similarly $X = \{\mathbf{x}_1, \mathbf{x}_2, \dots \mathbf{x}_n \}$ are sample points that lie on $g(x)$ and lie close to the intersecting points between $f_1(x),f_2(x) \dots f_n(x)$ and $g(x)$. The red (residual) vectors $\mathbf{v}_1,\mathbf{v}_2 \dots \mathbf{v}_n$ are obtained by connecting the sample points with its corresponding intersecting points. $$\textbf{v}_n = \bar{X}_n - X_n$$ $\qquad$ where $\bar{X}$ is the set of intersecting points between $F$ and $g(x)$. All the values of the points, lines and vectors are assumed to be known.

My goal is to find $\hat{g}(x)$ (as shown in Fig.2) or in other words to rotate and translate $g(x)$ and the sample points in such a way that the size of the (residual) vectors becomes smaller after the transformation. Note that the distances between sample points remain unchanged after the transformation; that is

$$||\mathbf{x}_{n} - \mathbf{x}_{n - 1}|| = || \mathbf{x}_{n}' - \mathbf{x}_{n - 1}'|| \qquad \mathrm{where} \,\, n = 1,2, \cdots N$$

If $X' = \{\mathbf{x}_1', \mathbf{x}_2', \cdots \mathbf{x}_n'\}$ that lies on $\hat{g}(x)$ as shown in Fig.2 is the set containing the transformed (Rotation and Translation) sample points than there exists a Rotation $\mathbf{R}$ and Translation $\mathbf{T}$ such that $$X' = \mathbf{R} X + \mathbf{T}$$

Finding the best transformation here is to minimize the sum of the square of the residual vectors. Thus

$$ \sum_i || \bar{X}_i' - (\mathbf{R} X_i + \mathbf{T})||^2 \rightarrow \mathrm{min}$$

$\qquad$ where $\bar{X}'_i$ is the set of intersecting points between $F$ and $\hat{g}(x)$ and itself depends on $\mathbf{R}$ and $\mathbf{T}$. How would one proceed further from here? The constraints: the sample points of $X$ and $X'$ are collinear and that the spacing between the sample points remain unchanged.

Is it possible to solve this problem by exploiting the information (magnitude and direction) contained in the vectors? Or in other words, is the information contained in the vectors sufficient to tell me which direction $g(x)$ must be moved so that it ends up at $\hat{g}(x)$?

1

There are 1 best solutions below

11
On

Hint:

Assume that you fix the rotation angle $\theta$ of $g(x)$ around some fixed point. Let the coordinates of the intersection points with the lines $f_k$ be $(u_k,v_k)$ and let the slopes of these lines be $s_k$. Let the distances between the points $x_k$ and $x_{k+1}$ be $d_{k,k+1}$.

We can find an "optimal" translation of horizontal component $t$ by solving the least-squares problem

$$\min_t\sum_{k=1}^{n-1}((u_{k+1}-u_k)^2+(v_{k+1}-v_k+t(s_{k+1}-s_k))^2-d_{k,k+1}^2)^2.$$

This leads to a cubic equation, which can be solved analytically. From the value of $t$, we can draw the residual error $E(\theta)$. Then the problem is reduced to 1D minimization.


Expressing $u,v$ in terms of $\theta$, you will get linear functions of the form $a+b\cos\theta+c\sin\theta$ and the above cost function is a bivariate mixed trigonometric polynomial of degree four. This amounts to a polynomial equation of a higher degree (like eight, but I am unsure). Chances for an analytical solution are zero or less.


Other criteria than the above least-squares can be used. This will only make the resolution harder.