Superposition
- 3-D Rotation Problem: Given S = s_{0}, s_{1}, ..., s_{n-1}, and T = t_{0}, t_{1}, ... t_{n-1}, where each s_{i} and each t_{i} is a 3-D vector, ⟨?_{x}, ?_{y}, ?_{z}⟩, find a rotation, R, by some angle θ, about some axis, u, through the origin, ⟨0, 0, 0⟩, so as to minimise the sum of squared errors between S' = map R S and T, that is ∑_{i} (norm(s'_{i} - t_{i}))^{2}.
- Note, it is given that s_{i} ~ t_{i}, 0 ≤ i < n.
- To find the general rigid-body transformation of S that gives the least-squares superposition of S on T (a version of the Total Least-Squares (TLS) problem), first make the centre of gravity (CoG) of T the origin, then translate S's CoG (carrying S with it) to that origin, and finally solve the rotation problem above.
- This problem appears in the superposition of two protein structures in Bioinformatics.
- Kearsley's Method: This uses the quaternion representation of 3-D rotations, and an Eigen-value finding algorithm, such as the Jacobi algorithm, say. A pure rotation is represented by a constrained quaternion -- a general quaternion having four degrees of freedom and a 3-D rotation only three -- so a Lagrange multiplier also gets a look in. All this leads to an Eigen-value problem on a 4×4 matrix. The smallest Eigen-value, λ, is the least-square error, and the corresponding Eigen-vector yields the required rotation (quaternion).
— L.A. ©
xm2 = ∑_{i} xm*xm; xp2 = ∑_{i} xp*xp; ym2 = ∑_{i} ym*ym; yp2 = ∑_{i} yp*yp; zm2 = ∑_{i} zm*zm; zp2 = ∑_{i} zp*zp; xmym = ∑_{i} xm*ym; xmyp = ∑_{i} xm*yp; xmzm = ∑_{i} xm*zm; xmzp = ∑_{i} xm*zp; xpym = ∑_{i} xp*ym; xpyp = ∑_{i} xp*yp; xpzm = ∑_{i} xp*zm; xpzp = ∑_{i} xp*zp; ymzm = ∑_{i} ym*zm; ymzp = ∑_{i} ym*zp; ypzm = ∑_{i} yp*zm; ypzp = ∑_{i} yp*zp; where xm = si[0]-ti[0], xp = si[0]+ti[0], ym = si[1]-ti[1], yp = si[1]+ti[1], zm = si[2]-ti[2], zp = si[2]+ti[2]; M = [ [xm2+ym2+zm2, ypzm-ymzp, xmzp-xpzm, xpym-xmyp], [ ypzm-ymzp, xm2+yp2+zp2, xmym-xpyp, xmzm-xpzp], [ xmzp-xpzm, xmym-xpyp, xp2+ym2+zp2, ymzm-ypzp], [ xpym-xmyp, xmzm-xpzp, ymzm-ypzp, xp2+yp2+zm2] ]; val_vec = Jacobi(M); // Eigen-values and -vectors val = val_vec[0], vec = val_vec[1]; small = 0; for(i = 1; i < val.length; i ++) if(val[i] < val[small]) small=i; return rotationQ( vec[small] );
- Thanks to Arun K for bringing this method to my attention.
- Search for [Kearsley superposition] in the [Bib].