Can Least Squares Solve for Rigid Transform?

[PabloBot]

Background: I have a set of known 3D feature points {x_i} on the surface of an object in some reference position/orientation at time t = 0. At t > 0 the object will have moved by a rigid transform. I am using computer vision to estimate the position of the 3D feature points {y_i}. I want to solve for the rigid transform (rotation and translation).

The obvious solution is if I have 4 points, I can use homogeneous coordinates and just solve Y = AX for A, where Y has columns y_i and X has columns x_i.

Am I guaranteed that A will only contain rotation and translation?

Also, I read online that for this system:
"Since there are errors but the problem is linear, the best approach to solve this is through least squares"

Why is this so? As long as the points aren't collinear won't X be invertible to satisfy the equation?

Another approach I was thinking was to use that distance are preserved and solve for the translation separately. Suppose Q is the pivot point in the reference position. After translation Q' = Q + t.
I know distances are preserved so:

|P'_0 - Q'| = c1
|P'_1 - Q'| = c2
|P'_2 - Q'| = c3

Can I use some numerical method to solve this system of nonlinear equations? I think there will be two solutions in 3D space, but I could use constraint that the overall rotation angle will be < 90 degrees to pick the right one.

 

[FactChecker]

Background: I have a set of known 3D feature points {x_i} on the surface of an object in some reference position/orientation at time t = 0. At t > 0 the object will have moved by a rigid transform. I am using computer vision to estimate the position of the 3D feature points {y_i}. I want to solve for the rigid transform (rotation and translation).

The obvious solution is if I have 4 points, I can use homogeneous coordinates and just solve Y = AX for A, where Y has columns y_i and X has columns x_i.

Am I guaranteed that A will only contain rotation and translation?

It is guaranteed that a rigid transformation is a combination of translation and rotation. It seems like that would be Y = AX + B.

Also, I read online that for this system:
"Since there are errors but the problem is linear, the best approach to solve this is through least squares"

Why is this so? As long as the points aren't collinear won't X be invertible to satisfy the equation?

You don't just want any solution. You want one that is a combination of translation and rotation. If there are errors in the position measurements, a solution of the linear equations will probably not be a combination of translation and rotation. You can use lease squares to find the closest approximation that is.

Another approach I was thinking was to use that distance are preserved and solve for the translation separately. Suppose Q is the pivot point in the reference position. After translation Q' = Q + t.

It's not clear to me that you should separate the problem that way when there are position measurement errors. It will give you a solution, but to get the best lease squared solution It may have to be solved as one least squares problem.

 

[PabloBot]

that would be Y = AX + B.

Yes, but there is a trick using augmented/homogeneous coordinates where if you write points (x, y, z, 1) and use 4x4 matrix, you can represent the translation and linear transformation (I want to restrict to rotation, however), as a single matrix. See "Augmented Matrix" from https://en.wikipedia.org/wiki/Affine_transformation.

You don't just want any solution. You want one that is a combination of translation and rotation. If there are errors in the position measurements, a solution of the linear equations will probably not be a combination of translation and rotation. You can use lease squares to find the closest approximation that is.

I think I see what you are saying. If I just use 4 data points with errors, I'll probably get some scaling/shear in there. Even with least squares how do I restrict it to rotation and translation only?

 

[FactChecker]

Yes, but there is a trick using augmented/homogeneous coordinates where if you write points (x, y, z, 1) and use 4x4 matrix, you can represent the translation and linear transformation (I want to restrict to rotation, however), as a single matrix. See "Augmented Matrix" from https://en.wikipedia.org/wiki/Affine_transformation.

Good point.

I think I see what you are saying. If I just use 4 data points with errors, I'll probably get some scaling/shear in there. Even with least squares how do I restrict it to rotation and translation only?

Put the matrices in the general form of a rotation and a translation with parameters. Then use least squares minimization to determine the best parameter values.