Thread Subject: How to solve TA = BT

Hi all,

I wonder if there is an existing program that solves the matrix equation: TA = BT, in which T is to be solved, all matrices (T, A, B) are 4-by-4 matrices. In addition, it is prior information that all matrices are rigid-body transformation matrices, so T only has 12 unknowns.

Please also note that I have many equations similar to the one given, so:

T*A1 = B1*T;
T*A2 = B2*T;
...
T*An = Bn*T;

In all of the equations, T should be the same. So my question is, how to solve T? thanks for any input.

"Pinpress" <nospam__@yahoo.com> wrote in message <gkkqeh$idk$1@fred.mathworks.com>...
> Hi all,
>
> I wonder if there is an existing program that solves the matrix equation: TA = BT, in which T is to be solved, all matrices (T, A, B) are 4-by-4 matrices. In addition, it is prior information that all matrices are rigid-body transformation matrices, so T only has 12 unknowns.
>
> Please also note that I have many equations similar to the one given, so:
>
> T*A1 = B1*T;
> T*A2 = B2*T;
> ...
> T*An = Bn*T;
>
> In all of the equations, T should be the same. So my question is, how to solve T? thanks for any input.

T=0 is an obvious solution. If you write a vector t=[t11 t12 t13 ...t44]', then you could show that your equation for T is:

C*t=0

where Cij=f(A,B) a linear combination of elements in A and B. Could there be another solution than t=[0 0 0 ...0]? Perhaps under special conditions on A and B?

/Per

"Pinpress" <nospam__@yahoo.com> wrote in message <gkkqeh$idk$1@fred.mathworks.com>...
> Hi all,
>
> I wonder if there is an existing program that solves the matrix equation: TA = BT, in which T is to be solved, all matrices (T, A, B) are 4-by-4 matrices. In addition, it is prior information that all matrices are rigid-body transformation matrices, so T only has 12 unknowns.
>
> Please also note that I have many equations similar to the one given, so:
>
> T*A1 = B1*T;
> T*A2 = B2*T;
> ...
> T*An = Bn*T;
>
> In all of the equations, T should be the same. So my question is, how to solve T? thanks for any input.

  Pinpress, you haven't told us if there is anything special about A and B. For example, if they, along with T, represent affine three-dimensional transformations in terms of augmented matrices, they would all have [0,0,0,1] in their bottom rows. The upper left 3x3 part would be a linear transformation and the rightmost top 3x1 part a subsequent translation. The transformation would be achieved by multiplying a column vector [x;y;z;1] on its left by the matrix as explained in:

 http://en.wikipedia.org/wiki/Affine_transformation

  You would then be taking the difference between 1) an affine transformation A followed by a rotation/translation T, and 2) the rotation/translation T followed by another affine transformation B, and hoping to find a T that would make that difference identically zero. Moreover this should be done for the same T and many different pairs of A and B.

  As you will see, it is a rather stringent condition that A and B are such that a solution T exists. Consider just the upper left 3x3 part in A, B, and T, and call them a, b, and t, respectively. By the nature of such matrices we must have t*a = b*t. Then take the singular value decomposition of a and b

 [ua,sa,va] = svd(a)
 [ub,sb,vb] = svd(b)

where a = ua*sa*va and b = ub*sb*vb. Such singular value decompositions into a unitary matrix times a nonnegative diagonal matrix times another unitary matrix are unique (assuming the three singular values are unequal.) Since we have t*a = b*t, we must have the equality

  (t*ua)*(sa)*(va) = (ub)*(sb)*(vb*t).

Here, t being a rotation matrix and therefore a valid unitary matrix, the products t*ua and vb*t are in themselves valid unitary matrices and it follows from the above uniqueness that

 t*ua = ub
 sa = sb
 va = vb*t

This shows that we can compute t as t = ub*ua' or t = vb'*va whichever we please. It also shows that the a and b svd decompositions must satisfy the equality

 va*ua = vb*ub

and that a and b must have the same singular values in sa and sb. As I say, A and B must satisfy a very strong condition for any T to possibly exist.

  I leave it to you to work out the details of the problem for the remaining translational aspects of these matrices - that is, the upper right 3x1 portion of the matrices.

Roger Stafford

"Pinpress" <nospam__@yahoo.com> wrote in message <gkkqeh$idk$1@fred.mathworks.com>...
> Hi all,
>
> I wonder if there is an existing program that solves the matrix equation: TA = BT, in which T is to be solved, all matrices (T, A, B) are 4-by-4 matrices. In addition, it is prior information that all matrices are rigid-body transformation matrices, so T only has 12 unknowns.
---------------------------------------

Actually, it has 6, if you parametrize T in terms of 3 Euler angles and 3 translations...


---------------------------------
> Please also note that I have many equations similar to the one given, so:
>
> T*A1 = B1*T;
> T*A2 = B2*T;
> ...
> T*An = Bn*T;
>
> In all of the equations, T should be the same. So my question is, how to solve T? thanks for any input.
--------------------------------

In addition to what Roger said, T has 6 degrees of freedom, so if n>6, it is likely that the above system of equations will be overdetermined. So, I'm assuming that what you want is some sort of least squares solution

(1) min. sum_i || T*Ai-Bi*T ||^2

If you parameterized T in terms of angles and translations, you could solve this using fmincon(), althrough you would want a good initial guess of T as insurance against local minima.

"Matt " <mjacobson.removethis@xorantech.com> wrote in message <gl29kl$qn5$1@fred.mathworks.com>...
> .......
> In addition to what Roger said, T has 6 degrees of freedom, so if n>6, it is likely that the above system of equations will be overdetermined. So, I'm assuming that what you want is some sort of least squares solution
>
> (1) min. sum_i || T*Ai-Bi*T ||^2
>
> If you parameterized T in terms of angles and translations, you could solve this using fmincon(), althrough you would want a good initial guess of T as insurance against local minima.
> .......

  Even with n = 1, it is overdetermined in that sense, Matt. The equality

 T*A = B*T

for a single A and B amounts to 12 linear equations to satisfy by itself (ignoring the bottom rows which are always identically equal to [0 0 0 1].) That is why I said that A and B have to abide by rather stringent conditions for solutions to exist. In fact, requiring sa = sb (in my earlier notation) represents three constraints and va*ua = vb*ub makes three more, thus leaving six degrees of freedom out of the original twelve for T. This becomes all the more true for n > 1.

  Pinpress's wordage seemed to me to suggest that the Ai and Bi affine transformations arose from some kind of actual measurements that pertained to a real translation plus rotation that was known to exist, and it was only necessary to determine from these measurements just what it was.

  With reference to the least squares approach, I think you meant 'fminunc'. There would be no constraints in that case with the six parameters - any Euler angles and any displacements are valid cases to be considered in the minimization process.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gl2f6r$91v$1@fred.mathworks.com>...
> "Matt " <mjacobson.removethis@xorantech.com> wrote in message <gl29kl$qn5$1@fred.mathworks.com>...
> > .......
> > In addition to what Roger said, T has 6 degrees of freedom, so if n>6, it is likely that the above system of equations will be overdetermined. So, I'm assuming that what you want is some sort of least squares solution
> >
> > (1) min. sum_i || T*Ai-Bi*T ||^2
> >
> > If you parameterized T in terms of angles and translations, you could solve this using fmincon(), althrough you would want a good initial guess of T as insurance against local minima.
> > .......
>
> Even with n = 1, it is overdetermined in that sense, Matt. The equality
----------------------------------------------------------------------------------------

Well, not always. Suppose n=1 and A=B=I. Then the equations reduce simply to
T=T and you have as undetermined a problem as you can get.



> With reference to the least squares approach, I think you meant 'fminunc'. There would be no constraints in that case with the six parameters - any Euler angles and any displacements are valid cases to be considered in the minimization process.

I suppose. But there's also the possibility that you might wish to constrain the angles to [0,2*pi] to avoid redundant solutions...