User:Vossman/3D Line Regression

Fit a 3-Dimensional Line to Data Points

Setup variables

This problem seems similar to what simple linear regression does: fit a straight line to a set of data points. However, ordinary linear regression minimizes the sum of the squared deviations between the points and the line, and it defines the deviation as the distance in the vertical (Y) direction. The problem we are going to solve in this example minimizes the direct distance between the points and the line. The direct distance is along a line that runs from the point and is perpendicular to the target line. In the following figure, the distance d is the direct distance from the point at $(x_{0},y_{0},z_{0})$ to the line.

The parametric equation for a 3D line is:

$x=\;x_{0}+v_{x}*t$

$y=\;y_{0}+v_{y}*t$

$z=\;z_{0}+v_{z}*t$

Where $(x_{0},y_{0},z_{0})$ is some point on the line and $(v_{x},v_{y},v_{z})$ is a vector defining the direction of the line. t is the parameter whose value is varied to define points on the line.

With this definition, there are six parameters: $x_{0},y_{0},z_{0},v_{x},v_{y},v_{z}$. But this overspecifies the line because a 3D line can be defined by 4 parameters as long as it is not parallel to one of the X, Y or Z planes.

When fitting a function to data, it is important that there are no mutually dependent (redundant) parameters in the function. If there are mutually dependent parameters, then there is no unique solution, and the fitting process will not converge.

So we need to eliminate two parameters.

Removing a parameter from the point on the line

Rather than allowing an arbitrary point $(x_{0},y_{0},z_{0})$ to specify a point on the line, we will force $z_{0}$ to be 0 and make $x_{0}$ and $y_{0}$ be the coordinates on the X-Y plane where the line penetrates the plane (i.e., where Z is zero). This eliminates $z_{0}$ as a parameter that needs to be computed. We can do this as long as we know that the line is not parallel to the X-Y plane, so it intersects it at some point.

$(x_{0},\;y_{0},\;z_{0})=(x_{0},\;y_{0},\;0)$

Removing a parameter from the direction vector

Next, we will work on the direction vector $(v_{x},v_{y},v_{z})$ that defines the direction of the line. Scaling the direction vector by a non-zero factor changes its length but not its direction (e.g., the direction defined by the vector <1,2,3> is the same as <2,4,6>, but the second vector is twice as long). If we scale the direction vector by $1/v_{z}$ to force $v_{z}$ to be 1, then we can define a revised direction vector,

$(v_{x}',\;v_{y}',\;v_{z}')=(v_{x}/v_{z},\;v_{y}/v_{z},\;1)$

So we will force $v_{z}$ to be 1 and define $v_{x}$ and $v_{y}$ as multiples of $v_{z}$.

This eliminates $v_{z}$ as a parameter that needs to be computed. Note that this is only valid if $v_{z}$ is not zero which means the line is not parallel to the X-Y plane. You can divide by $v_{x}$ or $v_{y}$ if you want to allow the line to be parallel to the X-Y plane but not some other plane.

Use cross-products

$\left|{\begin{matrix}\mathbf {i} &\mathbf {j} &\mathbf {k} \\a_{x}&a_{y}&a_{z}\\v_{x}&v_{y}&v_{z}\end{matrix}}\right|=\left[a_{y}v_{z}-a_{z}v_{y}\right]\mathbf {i} +\left[a_{z}v_{x}-a_{x}v_{z}\right]\mathbf {j} +\left[a_{x}v_{y}-a_{y}v_{x}\right]\mathbf {k}$

$\left|{\begin{array}{ccc}\mathbf {i} &\mathbf {j} &\mathbf {k} \\x-x_{i}&y-y_{i}&z-z_{i}\\v_{x}'&v_{y}'&v_{z}'\end{array}}\right|=\left[(y-y_{i})*v_{z}'-(z-z_{i})*v_{y}'\right]\mathbf {i} +\left[(z-z_{i})*v_{x}'-(x-x_{i})*v_{z}'\right]\mathbf {j} +\left[(x-x_{i})*v_{y}'-(y-y_{i})*v_{x}'\right]\mathbf {k}$

In addition,

$\left|v'\right|=1$

so

$v_{x}'^{2}+v_{y}'^{2}+v_{z}'^{2}=1$

For our least squares minimization, we want to minimize the square of the cross product in each dimension

$A^{2}:\left[(y-y_{i})*v_{z}'-(z-z_{i})*v_{y}'\right]^{2}=min$

$B^{2}:\left[(z-z_{i})*v_{x}'-(x-x_{i})*v_{z}'\right]^{2}=min$

$C^{2}:\left[(x-x_{i})*v_{y}'-(y-y_{i})*v_{x}'\right]^{2}=min$

Then for each variable: $x,y,z,v_{x}',v_{y}',$ and $v_{z}'$, we take the derivative:

${\frac {dA^{2}}{dv_{z}'}}=(y-y_{i})*A=0$

${\frac {dA^{2}}{dv_{y}'}}=(z-z_{i})*A=0$

Bad Optimization

So, now we have 4 variables: $x_{0},y_{0},v_{x}',v_{y}'$ to optimize from our list of points.

$\sum _{i}\left[(v_{x}'*t+x_{0}-x_{i})^{2}+(v_{y}'*t+y_{0}-y_{i})^{2}+(v_{z}'*t+z_{0}-z_{i})^{2}\right]$

$=\sum _{i}\left[(v_{x}'*t+x_{0}-x_{i})^{2}+(v_{y}'*t+y_{0}-y_{i})^{2}+(t-z_{i})^{2}\right]$

from this it is obvious that $t\approx z_{i}$ for each point, therefore:

$\Longrightarrow \sum _{i}\left[(v_{x}'*z_{i}+x_{0}-x_{i})^{2}+(v_{y}'*z_{i}+y_{0}-y_{i})^{2}\right]$

we want to minimize this equation with respect to our four variables $x_{0},y_{0},v_{x}',v_{y}'\;$, so we can take the derivative with respect to each which in turn generates four equations for our four unknowns:

$\sum _{i}z_{i}*(v_{x}'*z_{i}+x_{0}-x_{i})\;=0$

$\sum _{i}-1*(v_{x}'*z_{i}+x_{0}-x_{i})\;=0$

$\sum _{i}z_{i}*(v_{y}'*z_{i}+y_{0}-y_{i})\;=0$

$\sum _{i}-1*(v_{y}'*z_{i}+y_{0}-y_{i})\;=0$

simplifying:

$\sum _{i}v_{x}'*z_{i}^{2}+x_{0}*z_{i}\;=x_{i}*z_{i}$

$\sum _{i}v_{x}'*z_{i}+x_{0}\;=x_{i}$

$\sum _{i}v_{y}'*z_{i}^{2}+y_{0}*z_{i}\;=y_{i}*z_{i}$

$\sum _{i}v_{y}'*z_{i}+y_{0}\;=y_{i}$

rearranging two of the equations:

$\sum _{i}x_{0}\;=x_{i}-v_{x}'*z_{i}$

$\sum _{i}y_{0}\;=y_{i}-v_{y}'*z_{i}$

therefore,

$x_{0}\;={\frac {\sum _{i}x_{i}-v_{x}'*z_{i}}{N}}$

$y_{0}\;={\frac {\sum _{i}y_{i}-v_{y}'*z_{i}}{N}}$

where N is the number of points

Try again

Distance from line to point, $(x_{i},y_{i},z_{i})\;$:

$l={\sqrt {v_{x}'^{2}+v_{y}'^{2}+v_{z}'^{2}}}\;$

$t*l=v_{x}'*(x_{i}-x_{0})+v_{y}'*(y_{i}-y_{0})+v_{z}'*(z_{i}-z_{0})\;$

External links

• Fit a 3-Dimensional Line to Data Points