00001 #ifndef OPENTISSUE_KINEMATICS_INVERSE_INVERSE_NONLINEAR_SOLVER_H
00002 #define OPENTISSUE_KINEMATICS_INVERSE_INVERSE_NONLINEAR_SOLVER_H
00003
00004
00005
00006
00007
00008
00009
00010 #include <OpenTissue/configuration.h>
00011
00012 #include <OpenTissue/kinematics/inverse/inverse_chain.h>
00013
00014
00015 #include <OpenTissue/kinematics/inverse/inverse_compute_jacobian.h>
00016 #include <OpenTissue/kinematics/inverse/inverse_set_joint_parameters.h>
00017 #include <OpenTissue/kinematics/inverse/inverse_get_joint_parameters.h>
00018 #include <OpenTissue/kinematics/inverse/inverse_compute_joint_limits_projection.h>
00019 #include <OpenTissue/kinematics/inverse/inverse_compute_weighted_difference.h>
00020
00021
00022 #include <OpenTissue/core/math/optimization/optimization_projected_bfgs.h>
00023 #include <OpenTissue/core/math/optimization/optimization_projected_steepest_descent.h>
00024
00025 #include <OpenTissue/core/math/big/big_prod_trans.h>
00026
00027 #include <OpenTissue/utility/utility_timer.h>
00028
00029 #include <OpenTissue/core/geometry/geometry_compute_closest_points_line_line.h>
00030
00031 #include <list>
00032 #include <cassert>
00033 #include <algorithm>
00034
00035 namespace OpenTissue
00036 {
00037 namespace kinematics
00038 {
00039 namespace inverse
00040 {
00041 namespace detail
00042 {
00043
00055 template< typename solver_type >
00056 class FunctionCalculator
00057 {
00058 public:
00059
00060 typedef typename solver_type::vector_type vector_type;
00061 typedef typename vector_type::value_type real_type;
00062 typedef typename solver_type::skeleton_type skeleton_type;
00063 typedef typename skeleton_type::bone_iterator bone_iterator;
00064 typedef typename skeleton_type::const_bone_iterator const_bone_iterator;
00065
00066 protected:
00067
00068 solver_type * m_S;
00069 vector_type m_delta;
00070
00071 public:
00072
00073 FunctionCalculator()
00074 : m_S(0)
00075 {}
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00165 void init(solver_type* S) { m_S = S; }
00166
00178 real_type operator ()(vector_type const & theta) const
00179 {
00180 using ublas::inner_prod;
00181 real_type retval;
00182
00183 OpenTissue::kinematics::inverse::set_joint_parameters( *(this->m_S->skeleton()), theta );
00184 vector_type & delta = const_cast<vector_type&>( this->m_delta );
00185 OpenTissue::kinematics::inverse::compute_weighted_difference( this->m_S->chain_begin(), this->m_S->chain_end(), delta );
00186 retval = inner_prod(delta,delta);
00187
00188
00189
00190
00191
00192
00193 return retval;
00194 }
00195 };
00196
00206 template<typename solver_type >
00207 class GradientCalculator
00208 {
00209 public:
00210
00211 typedef typename solver_type::math_types math_types;
00212 typedef typename solver_type::vector_type vector_type;
00213 typedef typename solver_type::matrix_type matrix_type;
00214 typedef typename math_types::value_traits value_traits;
00215
00216 protected:
00217
00218 solver_type * m_S;
00219 vector_type m_delta;
00220 matrix_type m_J;
00221 vector_type m_tmp;
00222
00223 public:
00224
00225 GradientCalculator()
00226 : m_S(0)
00227 {}
00228
00234 void init(solver_type* S ) { m_S = S; }
00235
00281 vector_type operator ()(vector_type const& theta) const
00282 {
00283 typedef typename solver_type::chain_iterator chain_iterator;
00284 typedef typename chain_iterator::value_type chain_type;
00285 typedef typename chain_type::bone_traits bone_traits;
00286
00287 using ublas::prod;
00288 using ublas::trans;
00289
00290 OpenTissue::kinematics::inverse::set_joint_parameters( *(this->m_S->skeleton()), theta );
00291
00292 vector_type & delta = const_cast<vector_type&>( this->m_delta );
00293 OpenTissue::kinematics::inverse::compute_weighted_difference( this->m_S->chain_begin(), this->m_S->chain_end(), delta);
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307 const chain_iterator chain_begin = this->m_S->chain_begin();
00308 const chain_iterator chain_end = this->m_S->chain_end();
00309
00310
00311 const size_t max_chains = std::distance( this->m_S->chain_begin(), this->m_S->chain_end() );
00312 const size_t max_bones = std::distance( this->m_S->skeleton()->begin(), this->m_S->skeleton()->end() );
00313
00314
00315 std::vector<size_t> row_index(max_chains);
00316 std::vector<size_t> column_index(max_bones);
00317
00318 size_t rows = 0;
00319 size_t columns = 0;
00320
00321 std::vector<size_t> dof_array(max_bones);
00322 {
00323 size_t index = 0;
00324 for(chain_iterator chain = chain_begin;chain!=chain_end;++chain)
00325 {
00326 row_index[index++] = rows;
00327 rows += chain->get_goal_dimension();
00328 }
00329
00330 typename solver_type::skeleton_type::bone_iterator bone = this->m_S->skeleton()->begin();
00331 typename solver_type::skeleton_type::bone_iterator bone_end = this->m_S->skeleton()->end();
00332 for(;bone!=bone_end;++bone)
00333 {
00334 dof_array[ bone->get_number()] = bone->active_dofs();
00335 }
00336
00337 for (size_t i=0;i<max_bones;++i)
00338 {
00339 column_index[i] = columns;
00340 columns += dof_array[i];
00341 }
00342 }
00343
00344 vector_type tmp2 (columns, 0.0);
00345 matrix_type J1 (3, 1);
00346 matrix_type J3 (3, 3);
00347 size_t chain_index = 0;
00348 for(chain_iterator chain = chain_begin;chain!=chain_end;++chain)
00349 {
00350 const typename chain_type::bone_iterator bend = chain->bone_end();
00351 typename chain_type::bone_iterator bone = chain->bone_begin();
00352
00353
00354 for(; bone != bend ; ++bone)
00355 {
00356 const size_t bone_index = bone->get_number();
00357 const size_t begin_row = row_index[chain_index];
00358 const size_t begin_column = column_index[bone_index];
00359
00360 const size_t dofs = dof_array[bone_index];
00361 if (dofs == 1)
00362 {
00363 bone_traits::compute_jacobian( (*bone) , (*chain), J1);
00364 tmp2 (begin_column) += delta (begin_row) * J1 (0, 0)
00365 + delta (begin_row+1) * J1 (1, 0)
00366 + delta (begin_row+2) * J1 (2, 0);
00367 }
00368 else if (dofs == 3)
00369 {
00370 bone_traits::compute_jacobian( (*bone) , (*chain), J3);
00371 for (size_t t = 0; t < dofs; t++)
00372 {
00373 tmp2 (begin_column+t) += delta (begin_row) * J3 (0, t)
00374 + delta (begin_row+1) * J3 (1, t)
00375 + delta (begin_row+2) * J3 (2, t);
00376 }
00377 }
00378 else
00379 {
00380 std::cerr << "For helvede da!" << std::endl;
00381 }
00382 }
00383 chain_index ++;
00384 }
00385 tmp2 *= -value_traits::two();
00386
00387
00388
00389
00390 return tmp2;
00391 }
00392 };
00393
00406 template<typename solver_type >
00407 class ProjectionCalculator
00408 {
00409 public:
00410
00411 typedef typename solver_type::math_types math_types;
00412 typedef typename solver_type::vector_type vector_type;
00413 typedef typename math_types::real_type real_type;
00414 typedef typename math_types::value_traits value_traits;
00415
00416 protected:
00417
00418 solver_type * m_S;
00419
00420 public:
00421
00422 ProjectionCalculator()
00423 : m_S(0)
00424 {}
00425
00431 void init(solver_type* S ){ this->m_S = S; }
00432
00433
00445 vector_type operator ()(vector_type const & theta) const
00446 {
00447
00448 vector_type ret = theta;
00449 OpenTissue::kinematics::inverse::compute_joint_limits_projection(*(this->m_S->skeleton()), ret );
00450 return ret;
00451 }
00452 };
00453
00454 }
00455
00520 template<typename skeleton_type_ >
00521 class NonlinearSolver
00522 {
00523 public:
00524
00525 typedef skeleton_type_ skeleton_type;
00526 typedef typename skeleton_type::math_types math_types;
00527 typedef typename skeleton_type::bone_traits bone_traits;
00528 typedef Chain<skeleton_type> chain_type;
00529
00530 protected:
00531
00532 typedef typename math_types::real_type real_type;
00533 typedef typename math_types::vector3_type vector3_type;
00534 typedef typename math_types::value_traits value_traits;
00535 typedef std::list<chain_type> chain_container;
00536
00537 public:
00538
00539 typedef typename chain_container::iterator chain_iterator;
00540 typedef typename chain_container::const_iterator const_chain_iterator;
00541 typedef typename ublas::vector<real_type> vector_type;
00542 typedef typename ublas::vector_range< vector_type > vector_range;
00543 typedef typename ublas::vector_range< const vector_type > const_vector_range;
00544 typedef typename ublas::compressed_matrix<real_type> matrix_type;
00545 typedef typename ublas::identity_matrix<real_type> identity_matrix_type;
00546
00547 protected:
00548
00549 typedef NonlinearSolver<skeleton_type> solver_type;
00550 typedef typename detail::GradientCalculator<solver_type> gradient_type;
00551 typedef typename detail::FunctionCalculator<solver_type > function_type;
00552 typedef typename detail::ProjectionCalculator<solver_type > projection_type;
00553
00554 protected:
00555
00556 gradient_type m_gradient;
00557 function_type m_function;
00558 projection_type m_projection;
00559 chain_container m_chains;
00560 skeleton_type* m_skeleton;
00561 vector_type m_theta;
00562 matrix_type m_H;
00563
00564 public:
00565
00571 skeleton_type * skeleton() { return this->m_skeleton; }
00572 skeleton_type const * skeleton() const { return this->m_skeleton; }
00573
00579 chain_iterator chain_begin() { return m_chains.begin(); }
00580 const_chain_iterator chain_begin() const { return m_chains.begin(); }
00581
00587 chain_iterator chain_end() { return m_chains.end(); }
00588 const_chain_iterator chain_end() const { return m_chains.end(); }
00589
00596 size_t size() const { return m_chains.size(); }
00597
00598
00599
00600
00601
00602
00603
00604
00605 chain_iterator add_chain(chain_type const & chain)
00606 {
00607 return m_chains.insert(m_chains.end(), chain);
00608 }
00609
00617 chain_iterator remove_chain(chain_iterator & chain)
00618 {
00619 chain_iterator iter = this->m_chains.erase(chain);
00620
00621 if( iter != this->m_chains.end() )
00622 return iter;
00623 return this->m_chains.begin();
00624 }
00625
00626 public:
00627
00628 NonlinearSolver()
00629 : m_gradient()
00630 , m_function()
00631 , m_projection()
00632 , m_skeleton(0)
00633 {
00634 this->m_gradient.init(this);
00635 this->m_function.init(this);
00636 this->m_projection.init(this);
00637 }
00638
00639 NonlinearSolver(solver_type const & solver)
00640 : m_gradient()
00641 , m_function()
00642 , m_projection()
00643 {
00644 *this = solver;
00645 }
00646
00647 NonlinearSolver(skeleton_type & S)
00648 {
00649 this->init(S);
00650 }
00651
00652 ~NonlinearSolver(){ }
00653
00654 solver_type& operator=(solver_type const &S)
00655 {
00656 if(this!= &S)
00657 {
00658 this->m_skeleton = S.m_skeleton;
00659 this->m_chains = S.m_chains;
00660 this->m_gradient = S.m_gradient;
00661 this->m_function = S.m_function;
00662 this->m_projection = S.m_projection;
00663 this->m_theta = S.m_theta;
00664 this->m_H = S.m_H;
00665
00666 this->m_gradient.init(this);
00667 this->m_function.init(this);
00668 this->m_projection.init(this);
00669 }
00670 return *this;
00671 }
00672
00673 public:
00674
00690 class Output
00691 {
00692 protected:
00693
00694 real_type m_value;
00695 real_type m_wall_time;
00696 size_t m_status;
00697 std::string m_error_message;
00698 size_t m_iterations;
00699 real_type m_gradient_norm;
00700 vector_type m_profiling;
00701
00702 public:
00703
00704 real_type const & value () const { return m_value;}
00705 real_type & value () { return m_value;}
00706
00707 real_type const & wall_time () const { return m_wall_time;}
00708 real_type & wall_time () { return m_wall_time;}
00709
00710 size_t const & status () const { return m_status;}
00711 size_t & status () { return m_status;}
00712
00713 std::string const & error_message () const { return m_error_message;}
00714 std::string & error_message () { return m_error_message;}
00715
00716 size_t const & iterations () const { return m_iterations;}
00717 size_t & iterations () { return m_iterations;}
00718
00719 real_type const & gradient_norm () const { return m_gradient_norm;}
00720 real_type & gradient_norm () { return m_gradient_norm;}
00721
00722 vector_type const * profiling () const { return &m_profiling;}
00723 vector_type * profiling () { return &m_profiling;}
00724
00725 public:
00726
00727 Output()
00728 : m_value(value_traits::zero())
00729 , m_wall_time(value_traits::zero())
00730 , m_status( OpenTissue::math::optimization::OK )
00731 , m_error_message( "" )
00732 , m_iterations(0u)
00733 , m_gradient_norm( value_traits::infinity() )
00734 {}
00735
00736 Output( Output const & o)
00737 {
00738 *this = o;
00739 }
00740
00741 Output & operator=( Output const & o)
00742 {
00743 if( this != &o)
00744 {
00745 m_value = o.m_value;
00746 m_wall_time = o.m_wall_time;
00747 m_status = o.m_status;
00748 m_error_message = o.m_error_message;
00749 m_iterations = o.m_iterations;
00750 m_gradient_norm = o.m_gradient_norm;
00751 m_profiling = o.m_profiling;
00752 }
00753 return *this;
00754 }
00755
00756 };
00757
00758 public:
00759
00785 class Settings
00786 {
00787 protected:
00788
00789 size_t m_choice;
00790 bool m_restart;
00791 size_t m_max_iterations;
00792 real_type m_absolute_tolerance;
00793 real_type m_relative_tolerance;
00794 real_type m_stagnation_tolerance;
00795 real_type m_alpha;
00796 real_type m_beta;
00797 real_type m_tau;
00798
00799 public:
00800
00801 size_t const & choice () const { return m_choice; }
00802 size_t & choice () { return m_choice; }
00803
00804 bool const & restart () const { return m_restart; }
00805 bool & restart () { return m_restart; }
00806
00807 size_t const & max_iterations () const { return m_max_iterations; }
00808 size_t & max_iterations () { return m_max_iterations; }
00809
00810 real_type const & absolute_tolerance () const { return m_absolute_tolerance; }
00811 real_type & absolute_tolerance () { return m_absolute_tolerance; }
00812
00813 real_type const & relative_tolerance () const { return m_relative_tolerance; }
00814 real_type & relative_tolerance () { return m_relative_tolerance; }
00815
00816 real_type const & stagnation_tolerance () const { return m_stagnation_tolerance; }
00817 real_type & stagnation_tolerance () { return m_stagnation_tolerance; }
00818
00819 real_type const & alpha () const { return m_alpha; }
00820 real_type & alpha () { return m_alpha; }
00821
00822 real_type const & beta () const { return m_beta; }
00823 real_type & beta () { return m_beta; }
00824
00825 real_type const & tau () const { return m_tau; }
00826 real_type & tau () { return m_tau; }
00827
00828 public:
00829
00830 Settings()
00831 : m_choice(0u)
00832 , m_restart(true)
00833 , m_max_iterations(0u)
00834 , m_absolute_tolerance( value_traits::zero() )
00835 , m_relative_tolerance( value_traits::zero() )
00836 , m_stagnation_tolerance( value_traits::zero() )
00837 , m_alpha( value_traits::zero() )
00838 , m_beta( value_traits::zero() )
00839 , m_tau( value_traits::zero() )
00840 {}
00841
00842 Settings(
00843 size_t const & choice
00844 , bool const & restart
00845 , size_t const & max_iterations
00846 , real_type const & absolute_tolerance
00847 , real_type const & relative_tolerance
00848 , real_type const & stagnation_tolerance
00849 , real_type const & alpha
00850 , real_type const & beta
00851 , real_type const & tau
00852 )
00853 : m_choice(choice)
00854 , m_restart(restart)
00855 , m_max_iterations(max_iterations)
00856 , m_absolute_tolerance( absolute_tolerance )
00857 , m_relative_tolerance( relative_tolerance )
00858 , m_stagnation_tolerance( stagnation_tolerance )
00859 , m_alpha( alpha )
00860 , m_beta( beta )
00861 , m_tau( tau )
00862 {}
00863
00864 Settings(Settings const & s){ *this = s; }
00865
00866 Settings & operator=(Settings const & s)
00867 {
00868 if(this != &s)
00869 {
00870 m_choice = s.choice();
00871 m_restart = s.restart();
00872 m_max_iterations = s.max_iterations();
00873 m_absolute_tolerance = s.absolute_tolerance();
00874 m_relative_tolerance = s.relative_tolerance();
00875 m_stagnation_tolerance = s.stagnation_tolerance();
00876 m_alpha = s.alpha();
00877 m_beta = s.beta();
00878 m_tau = s.tau();
00879 }
00880 return *this;
00881 }
00882
00883 };
00884
00885
00891 static Settings const & default_BFGS_settings()
00892 {
00893 static Settings settings(
00894 0u
00895 , true
00896 , 5u
00897 , boost::numeric_cast<real_type>(1e-3)
00898 , boost::numeric_cast<real_type>(0.00001)
00899 , boost::numeric_cast<real_type>(0.00001)
00900 , boost::numeric_cast<real_type>(0.0001)
00901 , boost::numeric_cast<real_type>(0.5)
00902 , value_traits::zero()
00903 );
00904 return settings;
00905 }
00906
00912 static Settings const & default_SD_settings()
00913 {
00914 static Settings settings(
00915 1u
00916 , false
00917 , 10u
00918 , boost::numeric_cast<real_type>(1e-3)
00919 , boost::numeric_cast<real_type>(0.00001)
00920 , boost::numeric_cast<real_type>(0.00001)
00921 , boost::numeric_cast<real_type>(0.0001)
00922 , boost::numeric_cast<real_type>(0.5)
00923 , value_traits::zero()
00924 );
00925 return settings;
00926 }
00927
00933 static Settings const & default_SDF_settings()
00934 {
00935 static Settings settings(
00936 2u
00937 , false
00938 , 100u
00939 , boost::numeric_cast<real_type>(1e-3)
00940 , boost::numeric_cast<real_type>(0.00001)
00941 , boost::numeric_cast<real_type>(0.00001)
00942 , value_traits::zero()
00943 , value_traits::zero()
00944 , boost::numeric_cast<real_type>(0.001)
00945 );
00946 return settings;
00947 }
00948
00949
00950
00951 public:
00952
00961 void init(skeleton_type const & S)
00962 {
00963 this->m_theta.resize(S.size()*6u);
00964 this->m_theta.clear();
00965
00966 this->m_H.clear();
00967 this->m_H.assign(identity_matrix_type(this->m_H.size1(),this->m_H.size2()));
00968 this->m_chains.clear();
00969 this->m_skeleton = const_cast<skeleton_type*>(&S);
00970
00971 this->m_gradient.init(this);
00972 this->m_function.init(this);
00973 this->m_projection.init(this);
00974 }
00975
00988 void solve(
00989 Settings const * settings_ = 0
00990 , Output * output = 0
00991 )
00992 {
00993 Settings const * settings = settings_ ? settings_ : &this->default_SD_settings();
00994
00995 size_t status = 0u;
00996 size_t iteration = 0u;
00997 real_type gradient_norm = value_traits::zero();
00998 vector_type * profiling = output ? output->profiling() : 0;
00999
01000 OpenTissue::utility::Timer<real_type> watch;
01001
01002 if(output)
01003 watch.start();
01004
01005 OpenTissue::kinematics::inverse::get_joint_parameters( *(this->m_skeleton), this->m_theta );
01006
01007 switch( settings->choice() )
01008 {
01009 case 0:
01010 {
01011
01012 size_t const N = this->m_theta.size();
01013 if( this->m_H.size1()!=N || this->m_H.size2()!=N )
01014 {
01015 this->m_H.resize( N, N, false);
01016 this->m_H.assign( identity_matrix_type(this->m_H.size1(),this->m_H.size2()) );
01017 }
01018
01019 if(settings->restart())
01020 {
01021 this->m_H.assign(identity_matrix_type(this->m_H.size1(),this->m_H.size2()));
01022 }
01023
01024 OpenTissue::math::optimization::projected_bfgs(
01025 this->m_function
01026 , this->m_gradient
01027 , this->m_H
01028 , this->m_theta
01029 , this->m_projection
01030 , settings->max_iterations()
01031 , settings->absolute_tolerance()
01032 , settings->relative_tolerance()
01033 , settings->stagnation_tolerance()
01034 , status
01035 , iteration
01036 , gradient_norm
01037 , settings->alpha()
01038 , settings->beta()
01039 , profiling
01040 );
01041 }
01042 break;
01043 case 1:
01044 {
01045 OpenTissue::math::optimization::projected_steepest_descent(
01046 this->m_function
01047 , this->m_gradient
01048 , this->m_theta
01049 , this->m_projection
01050 , settings->max_iterations()
01051 , settings->absolute_tolerance()
01052 , settings->relative_tolerance()
01053 , settings->stagnation_tolerance()
01054 , status
01055 , iteration
01056 , gradient_norm
01057 , settings->alpha()
01058 , settings->beta()
01059 , profiling
01060 );
01061 }
01062 break;
01063 case 2:
01064 {
01065 OpenTissue::math::optimization::projected_steepest_descent(
01066 this->m_function
01067 , this->m_gradient
01068 , this->m_theta
01069 , this->m_projection
01070 , settings->max_iterations()
01071 , settings->absolute_tolerance()
01072 , settings->relative_tolerance()
01073 , settings->stagnation_tolerance()
01074 , status
01075 , iteration
01076 , gradient_norm
01077 , settings->tau()
01078 , profiling
01079 );
01080 }
01081 break;
01082 default:
01083 assert(false || !"solve(): Could not determine the numerical method to be used");
01084 break;
01085 };
01086
01087 OpenTissue::kinematics::inverse::set_joint_parameters( *(this->m_skeleton) , this->m_theta );
01088
01089
01090 if(output)
01091 {
01092 watch.stop();
01093 output->status() = status;
01094 output->error_message() = OpenTissue::math::optimization::get_error_message(status);
01095 output->gradient_norm() = gradient_norm;
01096 output->iterations() = iteration;
01097 output->value() = this->m_function( this->m_theta );
01098 output->wall_time() = watch();
01099
01100 }
01101
01102 }
01103
01104 };
01105
01106 }
01107 }
01108 }
01109
01110
01111 #endif