Covariance matrix computation: Jacobian matrix is rank deficient

1,284 views
Skip to first unread message

HA

unread,
Jul 6, 2017, 2:26:54 PM7/6/17
to Ceres Solver
Dear forum,
I am trying to get the covariance matrices of the camera poses in my BA, but I get the following error when the "covariance.Compute()" is called:
  • E0704 17:41:01.430168 1942073344 covariance_impl.cc:501] Jacobian matrix is rank deficient. Number of columns: 425979 rank: 421022
  • F0704 17:41:01.525382 1942073344 BA.cc:841] Check failed: covariance.Compute(cov_blocks, &problem) 
  • *** Check failure stack trace: ***
  •     @        0x1044c9522  google::LogMessage::Fail()
  •     @        0x1044c8c24  google::LogMessage::SendToLog()
  •     @        0x1044c917b  google::LogMessage::Flush()
  •     @        0x1044cc4c5  google::LogMessageFatal::~LogMessageFatal()
  •     @        0x1044c980f  google::LogMessageFatal::~LogMessageFatal()
  •     @        0x1041150dd  ceres::examples::SolveProblem()
  •     @        0x10411659e  main
  •     @     0x7fff85dd45ad  start
  •     @                0x3  (unknown)
My problem has the following specs: Number of observations: 668,004, number of 3D points: 141,563, number of cameras: 215. For each camera just the pose is optimized which is represented by 3 rotation parameters (Rodrigues vector) and 3 translation. As also indicated in the message above, my Jacobian has the size of 141,563*3+215*6=425,979.
My code snippet where I call the covariance computer (after solving) is as follows:

    ceres::Covariance::Options cov_options;
    ceres::Covariance covariance(cov_options);
    double* cameras = bal_problem.mutable_cameras();
    const int camera_block_size = 6 ;
    const int N=1 ; // bal_problem.num_cameras() ;
    std::vector<std::pair<const double*, const double*> > cov_blocks;
    for(size_t i = 0 ; i <N  ; i++) {
        const double* cam_block = cameras + camera_block_size * bal_problem.camera_index()[i] ;
        cov_blocks.push_back(std::make_pair(cam_block,cam_block) );
    }
    CHECK(covariance.Compute(cov_blocks, &problem) ) ;

And when I set "cov_options.algorithm_type=DENSE_SVD;" the program crashes (bad malloc error) even when I have about 40GB memory available.
I have read some related topics in this forum, and understand that it is related to the jacobian matrix deficiency, however I do not understand why my Jacobian would be deficient or how to overcome the problem and get the covariances for my camera poses. I should mention that the BA optimization works perfectly with no issue, thanks to the great implementation of the Ceres-solver.

Thank you.

Sameer Agarwal

unread,
Jul 7, 2017, 2:53:14 AM7/7/17
to Ceres Solver
Hadi,
Bundle adjustment problems have a gauge ambiguity -- you can rotate, translate and scale the whole reconstruction without changing the reprojection error. This is reflected in the fact that the Jacobian has a rank deficiency of 7. Further, the points themselves can be quite ill conditioned, so trying to estimate the covariance of the whole system does not work. This is reflected in the rank deficiency that you are seeing.

The solution to this is implementing an algorithm that can exploit the structure of the bundle adjustment problem to compute the pseudo inverse of J'J. 

There is a patch by Devin Lane
thats sitting in the queue for revision and review but its going to take some time to get it into ceres.
you could try it in the interim (I am not sure if it still builds with ceres at head).

Sameer


--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/e5389d2b-07d8-476b-85a8-9ed82e969e17%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Alan Buchanan

unread,
Oct 24, 2017, 2:17:54 AM10/24/17
to Ceres Solver
Sameer,

I would like to try this code as it looks promising:

How do you download it ?

doesn't seem to work

comes back with : fatal: Not a git repository (or any of the parent directories): .git

Regards,

Alan

Sameer Agarwal

unread,
Oct 24, 2017, 11:19:23 AM10/24/17
to ceres-...@googlegroups.com
Alan,
There is a "DOWNLOAD" link on that page that lets you download a zipped diff file.
I am not sure if the patch will cleanly apply to the master though. 
Sameer


--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/ddb72914-84f2-49aa-8ae8-1dff1643f17c%40googlegroups.com.

Alan Buchanan

unread,
Oct 24, 2017, 5:55:09 PM10/24/17
to 'Sameer Agarwal' via Ceres Solver

Thanks Sameer,

I am not sure how I apply patches !

I ended up downloaded the files in the directory and copied them into my project.
- This didn't work and ended up with a bunch of errors !

Is there any chance of just downloading a project with these amendments

You received this message because you are subscribed to a topic in the Google Groups "Ceres Solver" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ceres-solver/1SrLa1Pr8D4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CABqdRUDkFRphxqYvUWqb8XPRXD1k2Ou%3DmqyLRzP6efszpSiy0g%40mail.gmail.com.

Sameer Agarwal

unread,
Oct 24, 2017, 7:40:31 PM10/24/17
to ceres-...@googlegroups.com
Alan,
The original developer of the patch has moved on. I have a plan to update the patch and land it, but I need to refactor it and need to find some time to do it :/
Sameer


To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/b9c843f9-ca4f-14ac-2293-6c8ecc08dfbe%40gmail.com.

Alan Buchanan

unread,
Oct 24, 2017, 7:44:44 PM10/24/17
to 'Sameer Agarwal' via Ceres Solver

Thanks Sameer,

Do you have a rough time frame for this ?

I am very interested in generating the covariance matrices and the gauge ambiguity problem has me stumped.

Regards,

Alan

Sameer Agarwal

unread,
Oct 24, 2017, 7:46:39 PM10/24/17
to ceres-...@googlegroups.com
Sorry Alan, but I do not have an ETA. Just a matter of when the spare time gods smile upon me :)
Sameer


To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/12f16e49-3833-b918-36b9-3d7dd0d49167%40gmail.com.

Keir Mierle

unread,
Oct 24, 2017, 8:15:09 PM10/24/17
to ceres-...@googlegroups.com
Hi Alan,

We can't support general git and gerrit issues here; please do some research and see what you can find before asking on the list. For example,


was the first hit I found on Google.

Thanks and happy optimizing,
Keir

On Tue, Oct 24, 2017 at 2:54 PM, Alan Buchanan <abuc...@gmail.com> wrote:

Thanks Sameer,

I am not sure how I apply patches !

I ended up downloaded the files in the directory and copied them into my project.
- This didn't work and ended up with a bunch of errors !

Is there any chance of just downloading a project with these amendments





On 10/24/2017 11:19 PM, 'Sameer Agarwal' via Ceres Solver wrote:
Alan,
There is a "DOWNLOAD" link on that page that lets you download a zipped diff file.
I am not sure if the patch will cleanly apply to the master though. 
Sameer


On Mon, Oct 23, 2017 at 11:17 PM Alan Buchanan <abuc...@gmail.com> wrote:
Sameer,

I would like to try this code as it looks promising:

How do you download it ?

doesn't seem to work

comes back with : fatal: Not a git repository (or any of the parent directories): .git

Regards,

Alan

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver+unsubscribe@googlegroups.com.
--
You received this message because you are subscribed to a topic in the Google Groups "Ceres Solver" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ceres-solver/1SrLa1Pr8D4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ceres-solver+unsubscribe@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver+unsubscribe@googlegroups.com.
 To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/b9c843f9-ca4f-14ac-2293-6c8ecc08dfbe%40gmail.com.

Keir Mierle

unread,
Oct 24, 2017, 8:27:52 PM10/24/17
to ceres-...@googlegroups.com
Hi Alan,

I see in your case, the issue is that you need to first clone the repo, then you can pull down the particular patch. Here's how you apply it as a patch to master (though you can see it fails to apply cleanly):

(venv) ==== 17:22 ==== keir@keir ==== ~ ====   
Cloning into 'ceres-solver'...
remote: Sending approximately 12.92 MiB ...
remote: Counting objects: 26, done
remote: Total 10605 (delta 5970), reused 10605 (delta 5970)
Receiving objects: 100% (10605/10605), 12.90 MiB | 21.83 MiB/s, done.
Resolving deltas: 100% (5970/5970), done.
(venv) ==== 17:22 ==== keir@keir ==== ~ ====   
% cd ceres-solver 
(venv) ==== 17:22 ==== keir@keir ==== ~/ceres-solver ==== master  
% git pull https://ceres-solver.googlesource.com/ceres-solver refs/changes/81/9581/2
remote: Counting objects: 529, done
remote: Finding sources: 100% (17/17)
remote: Total 17 (delta 1), reused 12 (delta 1)
Unpacking objects: 100% (17/17), done.
 * branch            refs/changes/81/9581/2 -> FETCH_HEAD
Auto-merging internal/ceres/schur_eliminator_impl.h
Auto-merging internal/ceres/schur_complement_solver.h
Auto-merging internal/ceres/schur_complement_solver.cc
CONFLICT (content): Merge conflict in internal/ceres/schur_complement_solver.cc
Auto-merging internal/ceres/random.h
Auto-merging internal/ceres/program_evaluator.h
Auto-merging internal/ceres/covariance_test.cc
Auto-merging internal/ceres/covariance_impl.cc
CONFLICT (content): Merge conflict in internal/ceres/covariance_impl.cc
Auto-merging include/ceres/types.h
CONFLICT (content): Merge conflict in include/ceres/types.h
Auto-merging include/ceres/covariance.h
CONFLICT (content): Merge conflict in include/ceres/covariance.h
Automatic merge failed; fix conflicts and then commit the result.

As you can see, the patch no longer applies on master. You may want to check out the exact commit that the patch is based off of:

cd ceres-solver
git fetch https://ceres-solver.googlesource.com/ceres-solver refs/changes/81/9581/2 && git checkout FETCH_HEAD

That should check out the exact version that was uploaded.

Cheers,
Keir

HA

unread,
Oct 24, 2017, 10:49:21 PM10/24/17
to Ceres Solver
Hi Sameer,
Sorry for my late reply. Just wanted to thank you for your prompt reply and information :)
Regards,
Hadi.

Alan Buchanan

unread,
Oct 25, 2017, 11:42:27 PM10/25/17
to Ceres Solver
I have managed to incorporate this patch into Ceres and compile the libraries.

I have been looking at covariance_test.cc and in particular 'FastSchurCovarianceTest' class.to see how I can implement

Is it correct in assuming that to implement this I need to add  the following in addition to the standard method in the webpage

A. Parameter Block Ordering prior to solving

lines 1551
    // Create explicit parameter blocks
    // points, cameras, then intrinsics
    ParameterBlockOrdering* ordering = new ParameterBlockOrdering;
    for (std::set<size_t>::iterator it = point_indices.begin();
         it != point_indices.end(); ++it) {
      ordering->AddElementToGroup(&s.points[*it].P.x(), 0);
    }
    for (std::set<size_t>::iterator it = camera_indices.begin();
         it != camera_indices.end(); ++it) {
      ordering->AddElementToGroup(&s.cameras[*it].C.x(), 1);
    }
    ordering->AddElementToGroup(s.intrinsics.params, 2);

B. Add this prior to calling Compute

   Covariance::Options coptions_schur;
    coptions_schur.linear_solver_ordering.reset(new ParameterBlockOrdering(*ordering));
    if (IsSchurType(options.linear_solver_type)) {
      coptions_schur.algorithm_type = SUITE_SPARSE_SCHUR_CHOLESKY;
    }
    Covariance cov_schur(coptions_schur);
    ASSERT_TRUE(cov_schur.Compute(covariance_blocks, problem.get()));

C. Class Members Missing

I have noticed that linear_solver_ordering and linear_solver_type are not members of Covariance:Options.

Any suggestions 

Alan Buchanan

unread,
Oct 26, 2017, 4:44:27 PM10/26/17
to Ceres Solver
Ignore 
"
C. Class Members Missing

I have noticed that linear_solver_ordering and linear_solver_type are not members of Covariance:Options.
"

I hadn't copied the correct covariance.h file across.

I am still trying to work out the method to call this new method

Adit

unread,
Feb 13, 2018, 11:05:52 AM2/13/18
to Ceres Solver
Hey Sameer,

I am looking at this patch (9581), is this added to the master? If not do you know when will this feature be available on the master? Thanks.

Adit

Sameer Agarwal

unread,
Feb 13, 2018, 11:07:14 AM2/13/18
to ceres-...@googlegroups.com
Adit,
Someone needs to take it on and rewrite that that patch. I do not have an eta.
Sameer

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages