From: somi <se...@gm...> - 2010-09-02 13:50:48
|
Hi Peter, Thanks for the reply. I checked the solution in atleast two programs (octave ->roots and Numerical Recipies->zroots) and they give the correct solution for these coefficients. You are right, this has something to do with numerical instabilities during scaling. Unfortunately I can't change the co-efficients. Let me explain the context in which I am using these coefficients. I have to compute the rigid transformation between two 3D point set v1 and v2 v2 = s R v1 + T , based on Horn's derivation of the closed form least squares formulation (for horns method see : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.971&rep=rep1&type=pdf ) For this I have to solve a polynomial as an intermediate step. However the function " vnl_rnpoly_solve" included in the ITK (vnl library) doesn't seem to be returning the correct roots for a particular case. a) BUGGY CASE: I used the following points: +9 -253 -1187 -45 -222 -740 -98 -223 -750 For this the polynomial coefficients would be (while registering above points to self) : 1.0000e+00 0.0000e+00 -4.0615e+09 4.0000e-06 4.1220e+18 The roots of the polynomial should be 4.5546e+04 4.4576e+04 -4.5546e+04 -4.4576e+04 But vnl_rnpoly_solve , doesn't return any root. b) TEST CASE: I then scaled the points by 0.1 to get the modified points +0.9 -25.3 -118.7 -4.5 -22.2 -74.0 -9.8 -22.3 -75.0 For this the polynomial coefficients would be (while registering above points to self) : 1.0000e+00 0.0000e+00 -4.0615e+07 0.0000e+00 4.1220e+14 For this the roots should be: -4554.6 -4457.6 4554.6 4457.6 Which is what I get using VNL. This is how I get the coefficients: a) center the point sets at their respective centroids b) compute the cross covariance terms of the two centered datasets c) Form the matrix "N" as in horns method d) form the quartic coefficients of the characteristic equation of matrix N for solving for the rotation in terms of quaternions e) Solve the polynomial with co-efficients from step (d) Is there any way around it ? I could scale down points by 10, and again scale back the results. But I want to get a generic solution as I use this program in a library and I would have no way of telling automatically when to scale and when not to scale. Thanks, Somi On Thu, Sep 2, 2010 at 9:41 AM, Peter Vanroose <pet...@ya...>wrote: > Somi, > > I have the impression that this has to do with the precision and size of > your coefficients, > and more precisely of the magnitude difference between them. > Your constant coefficient is around 4e18. > If I scale the solutions by a factor 10, by dividing coefficient 3 by 100 > and coefficient 5 by 10000, I obtain the correct result (to be interpreted > 10x larger): > ======================== > VNL roots are > 4554.6 +i 4.62223e-32 > -4457.61 +i -1.44445e-34 > -4554.6 +i -4.62223e-32 > 4457.61 +i 1.44445e-34 > ======================== > > So try reducing too extreme values first (e.g. by dividing coefficient n by > 10^n) before calling the solver. > > I presume that the original algorithm (by Kriegman and Ponce) has this same > instability. > > Not sure whether this scaling solution should be introduced into the VNL > interface layer, or whether this should better be left to the user who calls > the method. Suggestions welcome, of course. > > -- Peter. > > > -- > > --- Den *ons 2010-09-01 skrev somi <se...@gm...>*: > > > Från: somi <se...@gm...> > Ämne: [Vxl-users] Bug in VNL vnl_rnpoly_solve ? > Till: vxl...@li... > Datum: onsdag 1 september 2010 22:29 > > > Hi, > I am getting incorrect solution when I try to solve a polynomial using the > method "vnl_rnpoly_solve", > that is provided in ITK. > > a) Polynomial coefficients (buggy case ) > > 1.0000e+00 0.0000e+00 -4.0615e+09 4.0000e-06 4.1220e+18 > > The roots of the polynomial should be > 4.5546e+04 > 4.4576e+04 > -4.5546e+04 > -4.4576e+04 > > But vnl_rnpoly_solve , doesn't return any root. > > > b) Polynomial coefficients (test case) > > > 1.0000e+00 0.0000e+00 -4.0615e+07 0.0000e+00 4.1220e+14 > > For this the roots should be: > -4554.6 > -4457.6 > 4554.6 > 4457.6 > > Which is what I get using VNL. > > > > I have included a test program. > > Thanks, > Somi > > -----Infogad bilaga följer----- > > > ------------------------------------------------------------------------------ > This SF.net Dev2Dev email is sponsored by: > > Show off your parallel programming skills. > Enter the Intel(R) Threading Challenge 2010. > http://p.sf.net/sfu/intel-thread-sfd > > -----Infogad bilaga följer----- > > _______________________________________________ > Vxl-users mailing list > Vxl...@li...<http://mc/compose?to=Vxl...@li...> > https://lists.sourceforge.net/lists/listinfo/vxl-users > > > |