## [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way?

 [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way? From: Lianqing Yu - 2006-08-28 15:09:57 Attachments: Message as HTML Hi, I've got an issue when I use vnl_levenberg_marquardt to refine the estimation of the 2-D homography between calibration rig plane and image plane. My algorithm follows the gold standard algorithm proposed in [Hartley & Zisserman, 2000] (algorithm 3.3, p98) and I choose to use Sampson error for the sake of speed. For implementation, I write a class similar to FMatrixComputeNonLinear. To gain faster convergence, I provide a customized routine gradf(), in which the Jocabian is a 2N x 9 matrix (equation 3.31, p114), where N is the number of point correspondences between the two planes. Here comes the problem. For geometric minimization of Sampson error, the number of residuals is N, since there is one residual (the norm $||\delta_x||^2$, equation 3.12, p83) for each correspondence: HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) : vnl_least_square_function(9, N, use_gradient) {} However, if my class is initialized like this, I find in the vnl_levenberg_marquardt code that dimension of Jocabian matrix in gradf() is fixed as N x 9 and my program will crash. One workaround is to set the number of residuals to 2*N. HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) : vnl_least_square_function(9, 2*N, use_gradient) {} But this will introduce some minor problems (more RAM consumption, slower speed, unintuitive). In all, I'd like to know your opinions on this issue. I'd appreciate your patience to read this mail and thanks in advance. Lianqing Yu 8/28/2006 PhD Candidate Robot Vision Group National Laboratory of Pattern Recognition (NLPR) Institute of Automation, Chinese Academy of Sciences (CASIA) No. 95, Zhongguancun East Road, 100080,Beijing, China Email: lqyu@... 

 [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way? From: Lianqing Yu - 2006-08-28 15:09:57 Attachments: Message as HTML Hi, I've got an issue when I use vnl_levenberg_marquardt to refine the estimation of the 2-D homography between calibration rig plane and image plane. My algorithm follows the gold standard algorithm proposed in [Hartley & Zisserman, 2000] (algorithm 3.3, p98) and I choose to use Sampson error for the sake of speed. For implementation, I write a class similar to FMatrixComputeNonLinear. To gain faster convergence, I provide a customized routine gradf(), in which the Jocabian is a 2N x 9 matrix (equation 3.31, p114), where N is the number of point correspondences between the two planes. Here comes the problem. For geometric minimization of Sampson error, the number of residuals is N, since there is one residual (the norm $||\delta_x||^2$, equation 3.12, p83) for each correspondence: HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) : vnl_least_square_function(9, N, use_gradient) {} However, if my class is initialized like this, I find in the vnl_levenberg_marquardt code that dimension of Jocabian matrix in gradf() is fixed as N x 9 and my program will crash. One workaround is to set the number of residuals to 2*N. HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) : vnl_least_square_function(9, 2*N, use_gradient) {} But this will introduce some minor problems (more RAM consumption, slower speed, unintuitive). In all, I'd like to know your opinions on this issue. I'd appreciate your patience to read this mail and thanks in advance. Lianqing Yu 8/28/2006 PhD Candidate Robot Vision Group National Laboratory of Pattern Recognition (NLPR) Institute of Automation, Chinese Academy of Sciences (CASIA) No. 95, Zhongguancun East Road, 100080,Beijing, China Email: lqyu@... 
 Re: [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way? From: Gehua Yang - 2006-08-28 19:28:09 Hi, First of all, you'll need to understand the difference between Homography and Fundamental matrix and the difference between their associated error measures, which I am afraid we (VXL community) can provide little help. I'll give this problem a shot based on my understanding of your description. You are confused by "the number of residuals". In the context of the Levenberg-Marquardt, the objective function has a least-squares form: sum_i( f_i^2 ) (i=1...N). Thus, the input to vnl_levenberg_marquardt is a vector of [f_1, f_2, ..., f_N] and the corresponding Jacobian is a N-times-k matrix (k is the degree of freedom). When estimating the fundamental matrix, N equals to the number of correspondences as each correspondence provides only one constraint. But as you are estimating the homography, N equals to ***2 times the number of correspondences*** as each provides two constraints. Also, when providing vnl_levenberg_marquardt with the analytic Jacobian matrix, it is a good practice to turn on vnl_levenberg_marquardt::set_check_derivatives( int ), which will compare the provided Jacobian with the one computed from numerical differences. After verifying the two are equal within a small error range, it is to be turned off for the consideration of speed. Gehua Lianqing Yu wrote: > Hi, > I've got an issue when I use vnl_levenberg_marquardt to refine the > estimation of the 2-D homography between calibration rig plane and > image plane. > My algorithm follows the gold standard algorithm proposed in [Hartley > & Zisserman, 2000] (algorithm 3.3, p98) and I choose to use Sampson > error for the sake of speed. For implementation, I write a class > similar to FMatrixComputeNonLinear. To gain faster convergence, I > provide a customized routine gradf(), in which the Jocabian is a 2N x > 9 matrix (equation 3.31, p114), where N is the number of point > correspondences between the two planes. > Here comes the problem. For geometric minimization of Sampson error, > the number of residuals is N, since there is one residual (the norm > $||\delta_x||^2$, equation 3.12, p83) for each correspondence: > HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) > : vnl_least_square_function(9, N, use_gradient) {} > However, if my class is initialized like this, I find in the > vnl_levenberg_marquardt code that dimension of Jocabian matrix in > gradf() is fixed as N x 9 and my program will crash. One workaround is > to set the number of residuals to 2*N. > HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) > : vnl_least_square_function(9, 2*N, use_gradient) {} > But this will introduce some minor problems (more RAM consumption, > slower speed, unintuitive). > In all, I'd like to know your opinions on this issue. > I'd appreciate your patience to read this mail and thanks in advance. > Lianqing Yu > 8/28/2006 > > PhD Candidate > Robot Vision Group > National Laboratory of Pattern Recognition (NLPR) > Institute of Automation, Chinese Academy of Sciences (CASIA) > > No. 95, Zhongguancun East Road, > 100080,Beijing, China > Email: lqyu@... > >------------------------------------------------------------------------ > >------------------------------------------------------------------------- >Using Tomcat but need to do more? Need to support web services, security? >Get stuff done quickly with pre-integrated technology to make your job easier >Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo >http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 > >------------------------------------------------------------------------ > >_______________________________________________ >Vxl-users mailing list >Vxl-users@... >https://lists.sourceforge.net/lists/listinfo/vxl-users > > 
 Re: [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way? From: Lianqing Yu - 2006-08-29 01:03:22 > When estimating the fundamental matrix, N equals to the number of > correspondences as each correspondence provides only one constraint. But > as you are estimating the homography, N equals to ***2 times the number > of correspondences*** as each provides two constraints. I can't agree with you on this point. Take estimating the fundamental matrix by minimizing geometric distance $\sum_i d(x_i, \hat{x}_i)^2 + d(x'_i, \hat{x'}_i)^2$ for instance, if one regards $d(x_i, \hat{x}_i)^2 + d(x'_i, \hat{x'}_i)^2$ as one item, the number of residual is 1 for each point correspondence. This is what FMatrixComputeNonLinear has done. If one takes $d(x_i, \hat{x}_i)^2 + d(x'_i, \hat{x'}_i)^2$ as summation of two terms, the number of residual is 2 for each point correspondence. Furthermore, if ones take d(x_i, \hat{x}_i)^2 as a summation of coordinate differences in both x and y direction, the number of residual will be 4. For nonlinear estimation with Sampson error, I believe there is one residual for each correspondence because the error is a scaler $\epsilon^T (J J^T)^{-1} \epsilon$. > Also, when providing vnl_levenberg_marquardt with the analytic Jacobian > matrix, it is a good practice to turn on > vnl_levenberg_marquardt::set_check_derivatives( int ), which will > compare the provided Jacobian with the one computed from numerical > differences. After verifying the two are equal within a small error > range, it is to be turned off for the consideration of speed. Thanks for this tip. Lianqing Yu ----- Original Message ----- From: "Gehua Yang" To: "Lianqing Yu" Cc: Sent: Tuesday, August 29, 2006 3:27 AM Subject: Re: [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way? > Hi, > > First of all, you'll need to understand the difference between > Homography and Fundamental matrix and the difference between their > associated error measures, which I am afraid we (VXL community) can > provide little help. > > I'll give this problem a shot based on my understanding of your > description. > > You are confused by "the number of residuals". In the context of the > Levenberg-Marquardt, the objective function has a least-squares form: > sum_i( f_i^2 ) (i=1...N). Thus, the input to vnl_levenberg_marquardt is > a vector of [f_1, f_2, ..., f_N] and the corresponding Jacobian is a > N-times-k matrix (k is the degree of freedom). > > When estimating the fundamental matrix, N equals to the number of > correspondences as each correspondence provides only one constraint. But > as you are estimating the homography, N equals to ***2 times the number > of correspondences*** as each provides two constraints. > > Also, when providing vnl_levenberg_marquardt with the analytic Jacobian > matrix, it is a good practice to turn on > vnl_levenberg_marquardt::set_check_derivatives( int ), which will > compare the provided Jacobian with the one computed from numerical > differences. After verifying the two are equal within a small error > range, it is to be turned off for the consideration of speed. > > Gehua > > > Lianqing Yu wrote: > >> Hi, >> I've got an issue when I use vnl_levenberg_marquardt to refine the >> estimation of the 2-D homography between calibration rig plane and >> image plane. >> My algorithm follows the gold standard algorithm proposed in [Hartley >> & Zisserman, 2000] (algorithm 3.3, p98) and I choose to use Sampson >> error for the sake of speed. For implementation, I write a class >> similar to FMatrixComputeNonLinear. To gain faster convergence, I >> provide a customized routine gradf(), in which the Jocabian is a 2N x >> 9 matrix (equation 3.31, p114), where N is the number of point >> correspondences between the two planes. >> Here comes the problem. For geometric minimization of Sampson error, >> the number of residuals is N, since there is one residual (the norm >> $||\delta_x||^2$, equation 3.12, p83) for each correspondence: >> HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) >> : vnl_least_square_function(9, N, use_gradient) {} >> However, if my class is initialized like this, I find in the >> vnl_levenberg_marquardt code that dimension of Jocabian matrix in >> gradf() is fixed as N x 9 and my program will crash. One workaround is >> to set the number of residuals to 2*N. >> HMatrix2DComputeSampson::HMatrix2DComputeSampson(int N) >> : vnl_least_square_function(9, 2*N, use_gradient) {} >> But this will introduce some minor problems (more RAM consumption, >> slower speed, unintuitive). >> In all, I'd like to know your opinions on this issue. >> I'd appreciate your patience to read this mail and thanks in advance. >> Lianqing Yu >> 8/28/2006 >> >> PhD Candidate >> Robot Vision Group >> National Laboratory of Pattern Recognition (NLPR) >> Institute of Automation, Chinese Academy of Sciences (CASIA) >> >> No. 95, Zhongguancun East Road, >> 100080,Beijing, China >> Email: lqyu@... >> >>------------------------------------------------------------------------ >> >>------------------------------------------------------------------------- >>Using Tomcat but need to do more? Need to support web services, security? >>Get stuff done quickly with pre-integrated technology to make your job easier >>Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo >>http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 >> >>------------------------------------------------------------------------ >> >>_______________________________________________ >>Vxl-users mailing list >>Vxl-users@... >>https://lists.sourceforge.net/lists/listinfo/vxl-users >> >> > 
 Re: [Vxl-users] Why is the dimension of Jacobian in vnl_levenberg_marquardt is fixed in this way? From: Gehua Yang - 2006-08-29 20:23:33 >I can't agree with you on this point. Take estimating the fundamental matrix by minimizing geometric distance $\sum_i d(x_i, \hat{x}_i)^2 + d(x'_i, \hat{x'}_i)^2$ for instance, if one regards $d(x_i, \hat{x}_i)^2 + d(x'_i, \hat{x'}_i)^2$ as one item, the number of residual is 1 for each point correspondence. This is what FMatrixComputeNonLinear has done. If one takes $d(x_i, \hat{x}_i)^2 + d(x'_i, \hat{x'}_i)^2$ as summation of two terms, the number of residual is 2 for each point correspondence. Furthermore, if ones take d(x_i, \hat{x}_i)^2 as a summation of coordinate differences in both x and y direction, the number of residual will be 4. > >For nonlinear estimation with Sampson error, I believe there is one residual for each correspondence because the error is a scaler $\epsilon^T (J J^T)^{-1} \epsilon$. > > > > > By skimming the code of FMatrixComputeNonLinear, I guess its objective function to be optimized is (please correct me if I am wrong): sum_i ( d^2(x_i, epipolar_line(y_i)) + d^2(y_i, epipolar_line(x_i)) )^2 You have a point in the number of residuals. It all depends on how you define your objective function. Gehua