Finding Rigid Body Transformation Between Two Unrelated Point Sets - Graphics

On 20 mar, 13:14, adam.hartsho...@gmail.com wrote:
> Hi,
>
> Given a reference set of 3D points A and a test set of 3D points B, I
> would like to know how to calculate the rigid body transform which
> finds
> the best alignment of B with A.
>
> N.B. Set A and B are not representing the same thing, and are likely
> to
> contain different number of elements. Therefore I am not looking to
> find
> the direct correspondence between A or B.
>

To completly know a rigid body velocity field, you need to know the
velocity of two points V(A) and V(B):
Then: V(M)=V(A)+Omega X AM (1)
V(M)=V(B)+Omega X BM (2)
You thus you get Omega: V(A)-V(B)+Omega X AB=0 (3)
Of course, V(A) and V(B) must not be parallel to the axis of rotation.

Once you know Omega, you can use either (1) or (2) to get V(M).


> Any help much appreciated,
>
> Adam

On Mar 20, 8:14 am, adam.hartsho...@gmail.com wrote:
> Hi,
>
> Given a reference set of 3D points A and a test set of 3D points B, I
> would like to know how to calculate the rigid body transform which
> finds
> the best alignment of B with A.
>
> N.B. Set A and B are not representing the same thing, and are likely
> to
> contain different number of elements. Therefore I am not looking to
> find
> the direct correspondence between A or B.
>
> Any help much appreciated,
>
> Adam

Tough problem. A similar problem is found in spacecraft attitude
control. Given a set of stars (usualy 3 to 5) observed in the
spacecraft body frame using a star sensor, match them to stars in a
catalog that might contain as many as several thousand stars in an
inertial frame. The basic approach often used is to search for a set
of stars in the catalog with the same pattern as the observed stars.
After a pattern match is made, then the transformation from the body
frame to the inertial frame is found. Look up "star identification",
or "stellar referenced attitude determination".

In statistics, the problem of finding the best fit transformation that
carries one set of points to another is called the Procrustes
problem. It is usually solved using singluar value decomposition
methods. But for that problem you need to know the correspondance
between points in set A to point in set B.

- MO

Arhhh, A and B don't represent the same thing, thus there isn't as
such a correspondence. If I could do simple correspondence I would
employee ICP or something similar. A and B are point clouds of the
surface of difference parts of the human body as they move about. I am
looking to align set B with set A.

Put simply I am implementing a paper and the author simply states in
one of the formulae calculate the rigid body transform between these
two data sets, where A and B are point sets as describe above. It is
stated as if it is something trivial.

On 20 mar, 14:41, "oracle3001" <adam.hartsho...@gmail.com> wrote:
> Arhhh, A and B don't represent the same thing, thus there isn't as
> such a correspondence. If I could do simple correspondence I would
> employee ICP or something similar. A and B are point clouds of the
> surface of difference parts of the human body as they move about. I am
> looking to align set B with set A.
>
> Put simply I am implementing a paper and the author simply states in
> one of the formulae calculate the rigid body transform between these
> two data sets, where A and B are point sets as describe above. It is
> stated as if it is something trivial.

Rigib body transformation is just an orthogonal transformation which
leaves invariant the norm of any vector. In mechanics, the distance
between two points of a rigid body must be invariant.
So a set of points A is transformed into a set of points B if there is
an orthonormal matrix transforming the coordinates of the points of A
into those of B.

Guys,

First of all, if A and B do not represent the same object, they are
most likely two differently shaped rigid bodies.
( Question: do you know if they are rigid at all? I assume that is
given for this problem) Thus, in this case, the problem is ill-poised.
You might want to look at 'deformable registration' solutions.

Either ways, if you still want to estimate a rigid transform between
two 'different' yet 'similarly shaped' rigid bodies, read this paper:

P. J. Besl and N. D. McKay, A method for registration of 3-D shapes

(Do a search on google and you might find the text.)

I have used this method to register two similarly shaped rigid
objects, but from different sources.

HTH..

P.



On Mar 20, 9:33 am, "Shaktyai" <Fabrice.All...@gmail.com> wrote:
> On 20 mar, 14:41, "oracle3001" <adam.hartsho...@gmail.com> wrote:
>
> > Arhhh, A and B don't represent the same thing, thus there isn't as
> > such a correspondence. If I could do simple correspondence I would
> > employee ICP or something similar. A and B are point clouds of the
> > surface of difference parts of the human body as they move about. I am
> > looking to align set B with set A.
>
> > Put simply I am implementing a paper and the author simply states in
> > one of the formulae calculate the rigid body transform between these
> > two data sets, where A and B are point sets as describe above. It is
> > stated as if it is something trivial.
>
> Rigib body transformation is just an orthogonal transformation which
> leaves invariant the norm of any vector. In mechanics, the distance
> between two points of a rigid body must be invariant.
> So a set of points A is transformed into a set of points B if there is
> an orthonormal matrix transforming the coordinates of the points of A
> into those of B.

adam.hartshorne@gmail.com wrote:

>Hi,
>
>Given a reference set of 3D points A and a test set of 3D points B, I
>would like to know how to calculate the rigid body transform which
>finds
>the best alignment of B with A.
>
>N.B. Set A and B are not representing the same thing, and are likely
>to
>contain different number of elements. Therefore I am not looking to
>find
>the direct correspondence between A or B.
>
>Any help much appreciated,
>
>Adam
>
>
>
Compute for both point sets the inertia coordinate system (i.e. the
center of a point set and the three axis by PCA). Then the rigid body
translation is given by the the translation to put the center of the
second point set to the center of the first point set. After that, the
rigid body rotation can be found by aligning the axis of both point
sets. Take care of the lengths of the PCA components. If these are
different align the directions with about the same length. By the way,
this is similar to the ellips solution.

Kind Regards,

--
Jan Bruijns
Senior Scientist, Philips Research Europe - Eindhoven

Office: WO-p-94, Postbox WO02
High Tech Campus 36, 5656 AE EINDHOVEN
The Netherlands

Phone: +31 40 2744724
Fax: +31 40 2744675
E-mail: jan.bruijns@philips.com

In article <1174392863.485482.41180@n59g2000hsh.googlegroups.com>,
<adam.hartshorne@gmail.com> wrote:
>Hi,

>Given a reference set of 3D points A and a test set of 3D points B, I
>would like to know how to calculate the rigid body transform which
>finds
>the best alignment of B with A.

Define "best alignment"; different definitions give
different results.

Given any definition using only algebraic functions, there
is a "computable" solution. Whether it can be computed in
a humanly attainable amount of time is another matter.

>N.B. Set A and B are not representing the same thing, and are likely
>to
>contain different number of elements. Therefore I am not looking to
>find
>the direct correspondence between A or B.

>Any help much appreciated,

>Adam



--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558

On 20 mar, 21:39, "pixel.to.life" <pixel.to.l...@gmail.com> wrote:
> Guys,
>
> First of all, if A and B do not represent the same object, they are
> most likely two differently shaped rigid bodies.
> ( Question: do you know if they are rigid at all? I assume that is
> given for this problem) Thus, in this case, the problem is ill-poised.
> You might want to look at 'deformable registration' solutions.
>
> Either ways, if you still want to estimate a rigid transform between
> two 'different' yet 'similarly shaped' rigid bodies, read this paper:
>
> P. J. Besl and N. D. McKay, A method for registration of 3-D shapes
>
> (Do a search on google and you might find the text.)
>
> I have used this method to register two similarly shaped rigid
> objects, but from different sources.
>
> HTH..
>
> P.
>
> On Mar 20, 9:33 am, "Shaktyai" <Fabrice.All...@gmail.com> wrote:
>
> > On 20 mar, 14:41, "oracle3001" <adam.hartsho...@gmail.com> wrote:
>
> > > Arhhh, A and B don't represent the same thing, thus there isn't as
> > > such a correspondence. If I could do simple correspondence I would
> > > employee ICP or something similar. A and B are point clouds of the
> > > surface of difference parts of the human body as they move about. I am
> > > looking to align set B with set A.
>
> > > Put simply I am implementing a paper and the author simply states in
> > > one of the formulae calculate the rigid body transform between these
> > > two data sets, where A and B are point sets as describe above. It is
> > > stated as if it is something trivial.
>
> > Rigib body transformation is just an orthogonal transformation which
> > leaves invariant the norm of any vector. In mechanics, the distance
> > between two points of a rigid body must be invariant.
> > So a set of points A is transformed into a set of points B if there is
> > an orthonormal matrix transforming the coordinates of the points of A
> > into those of B.

Call A the initial body. A1 and A2 are two points of A.
Call B the final body. A1' and A2' are (your best bet) image of A1
and A2.

Now use the rigid body transformation:
OA1=OA1'+omega X A1'A1 (all quatities are vectors)
OA2=OA2'+omega X A2'A2

>From there you compute omega. And you do the same for all the couple
of points you can find. At last you average omega, compute the rms and
pray for the result to be what you want. Since you want a rigid body
transformation, pick up only the points such that OA almost equal OA'