«

»

3D Line Fitting in 5 Easy Steps with SVD

Least squares fit is used for 2D line fitting. In 3D space, the line is called 3D Orthogonal Distance Regression (ODR) line. The line can be easily found in 3D using SVD (singular value decomposition).

Assuming that we have a bunch of 3D points (x0, y0, z0) to (xn, yn, zn), the algorithm (in MATLAB) is as follows:

 

12 comments

Skip to comment form

  1. Carl

    I would like to ask the equation obtained at the end is like this?
    x=mean_x+v(1,1)*t
    y=mean_y+v(1,2)*t
    z=mean_z+v(1,3)*t

    where t is a parametrical value for each point

    1. Mehran Maghoumi

      Yes 🙂

      1. Carl

        I tried it, with the data set as follow:
        points = [1 1 1;2 2 2;3 3 3;4 4 4;5 5 5];
        All of the parameters for “direction” should be the same , but it i choose
        direction = V(1, :);
        it is not the same, so should the final result be
        direction = V(:,1);
        Woudl you mind have a check?

        1. Mehran Maghoumi

          Thanks for spotting the error Carl 🙂
          I fixed the error. Also added the optional step of normalizing the direction vector. It should produce correct results now.

          1. Dave

            Or skip steps 2 and 3 and, per Rodger Stafford, change step 4 to [~,~,V] =svd(cov(points));

          2. Mehran Maghoumi

            Yes, it is true because we are essentially computing the covariance matrix.

  2. Ron

    Hi Mehran,
    I will like to know why the the direction vector given by V(:, 1)
    thank you

    1. Mehran Maghoumi

      Recall that the goal here is to minimize the distance between the points and their projection on the obtained line. This is equivalent to the first principal component of the covariance matrix. In layman’s terms, we want to find the dominant direction that the data is spread in the space, similar to PCA. This is equivalent to the singular vector corresponding to the largest singular value of the SVD decomposition. Take a look at here for more details:
      https://en.wikipedia.org/wiki/Principal_component_analysis#Singular_value_decomposition

  3. Ron

    Thank you Mehran
    I read on the link you posted.
    I agree with your equivalence you established with the PCA.
    I know the svd decomposition consists of the right singular vector, the diagonal matrix of the singular values and the left singular matrix.
    From your script you used the column of the left singular vector corresponding to the largest singular value
    What i wanted to find out was if the right singular vector could also give the same direction information?
    Thanks

    1. Mehran Maghoumi

      No problem.
      I’m not sure I follow: in the code I posted above, I’m using the right singular vector (not the left one). According to the link below, MATLAB’s svd function first outputs left singular vectors, then outputs singular values and finally outputs right singular vectors:
      https://www.mathworks.com/help/matlab/ref/svd.html#outputarg_V

      1. Ron

        Sorry about the typo.
        What i meant to ask was if the left singular matrix values give us any indication of the direction of best fit line as well?
        If not do you have any idea what the elements of the left singular matrix gives us?
        (To avoid ambiguity im referring to [U,~,~] = svd(3d points);

        I could make some correlation with the significance of the diagonal of the singular values and the right singular matrix
        however i am curious what the elements of the left singular matrix U gives us.

        Some insight on that will be much appreciated.
        Thanks.

        1. Mehran Maghoumi

          I’m unsure if the columns of the left matrix of singular vectors stand to have any meaning by themselves. However in [U,S,VT] = svd(3d points), columns of U*S would be principal components (the projections of data on the principal axes, or in other words, the transformed data along the direction of each principal axis).

          Also, one thing to note is that in the code above, when arranging the points in a matrix format, each row represents one point and each column represents one axis. If this matrix is transposed such that rows represent axes and columns are 3D points, then in SVD the role of U and V would be reversed. In other words, the columns of U would give you the principal components.

          Hope this helps.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

Time limit is exhausted. Please reload CAPTCHA.