Preconditioner for solving linear equations for reconstructing three-dimensional structure of a scene

A computer-implemented system for constructing a three-dimensional model of a scene from a set of images of the scene captured using a set of cameras, the system comprising:

• a computer processor;
• and
• a computer-readable storage medium storing computer program modules configured to execute on the computer processor, the computer program modules comprising:
• a model correction module configured to:
• iteratively modify a set of parameters representing the three-dimensional model of the scene, the set of parameters comprising observations of the scene from the set of cameras, each camera associated with a set of points of the scene observed from the camera, the modifying comprising:
• determining corrections to the set of parameters, comprising, for an iteration:
• formulating a linear system of equations representing an error in the three dimensional model;
• determining clusters of cameras, each cluster associated with a portion of the scene and comprising cameras from the set of cameras that observe the portion of the scene;
• determining a preconditioner matrix by:
• for each pair of clusters, determining a number of terms of the linear system of equations representing interactions between clusters of the pair;
• selecting pairs of clusters based on the number of terms representing interactions between clusters of each pair;
• and
• forming the preconditioner matrix by eliminating one or more terms of the linear system of equations representing interactions between clusters of the selected pairs;
• preconditioning the linear system of equations using the preconditioner matrix and solving the preconditioned linear system of equations to determine corrections to the set of parameters;
• and
• refining the set of parameters based on the corrections to the set of parameters to produce a refined three-dimensional model of the scene;
• and
• a three-dimensional model construction module configured to store the refined three-dimensional model of the scene.

A computer program product having a non-transitory computer-readable storage medium storing computer-executable code for constructing a three-dimensional model of a scene from a set of images of the scene captured using a set of cameras, the code comprising:

• a model correction module configured to:
• iteratively modify a set of parameters representing the three-dimensional model of the scene, the set of parameters comprising observations of the scene from the set of cameras, each camera associated with a set of points of the scene observed from the camera, the modifying comprising:
• determining corrections to the set of parameters, comprising, for an iteration:
• formulating a linear system of equations representing an error in the three dimensional model;
• determining clusters of cameras, each cluster associated with a portion of the scene and comprising cameras from the set of cameras that observe the portion of the scene;
• determining a preconditioner matrix by:
• for each pair of clusters, determining a number of terms of the linear system of equations representing interactions between clusters of the pair;
• selecting pairs of clusters based on the number of terms representing interactions between clusters of each pair;
• and
• forming the preconditioner matrix by eliminating one or more terms of the linear system of equations representing interactions between clusters of the selected pairs;
• preconditioning the linear system of equations using the preconditioner matrix and solving the preconditioned linear system of equations to determine corrections to the set of parameters;
• and
• refining the set of parameters based on the corrections to the set of parameters to produce a refined three-dimensional model of the scene;
• and
• a three-dimensional model construction module configured to store the refined three-dimensional model of the scene.