Shape-based registration for non-rigid objects with large holes

1. A computerized method for closed-form 3D model generation of non-rigid complex objects from scans with large holes, the method comprising:

receiving, by an image processing module of a computing device, (i) a partial scan of a non-rigid complex object captured by a sensor coupled to the computing device, (ii) a partial 3D model corresponding to the non-rigid complex object, and (iii) a whole 3D model corresponding to the non-rigid complex object, wherein the partial scan and the partial 3D model each includes one or more large holes;

performing, by the image processing module, a rough match between the partial 3D model and the partial scan;

changing, by the image processing module, the whole 3D model using the rough match to generate a deformed 3D model;

refining, by the image processing module, the deformed 3D model using a deformation graph;

reshaping, by the image processing module, the refined deformed 3D model to have greater detail; and

adjusting, by the image processing module, the refined deformed 3D model according to the reshaped 3D model to generate a closed-form 3D model that closes the one or more large holes in the partial scan.

2. The method of claim 1 , wherein the step of performing a rough match between the partial 3D model and the partial scan further comprises:

deforming, by the image processing module, the partial 3D model to at least partially match the partial scan by creating new holes in the partial 3D model that are similar to the one or more large holes in the partial scan; and

deforming, by the image processing module, the one or more large holes in the partial 3D model based upon the step of deforming the partial 3D model to at least partially match the partial scan.

3. The method of claim 2 , wherein the step of deforming the partial 3D model to at least partially match the partial scan is performed using a coherent point drift algorithm.

4. The method of claim 2 , wherein the step of deforming the one or more large holes in the partial 3D model is performed using a thin-plate spline algorithm.

5. The method of claim 2 , wherein the partial 3D model and the partial scan are down-sampled before deforming the partial 3D model to at least partially match the partial scan.

6. The method of claim 1 , wherein the step of refining the deformed 3D model using a deformation graph further comprises:

uniformly down-sampling, by the image processing module, the whole 3D model; and

building, by the image processing module, the deformation graph based upon the down-sampled whole 3D model.

7. The method of claim 6 , wherein the step of building a deformation graph further comprises:

generating, by the image processing module, one or more deformation nodes for each point in the down-sampled whole 3D model;

initializing, by the image processing module, a 3D position of the one or more deformation nodes using a 3D position of a corresponding point in the down-sampled whole 3D model;

searching, by the image processing module, neighboring deformation nodes for the one or more deformation nodes within a predetermined distance;

initializing, by the image processing module, a 3D affine matrix and a translation vector for the one or more deformation nodes based upon the searched neighboring deformation nodes; and

assigning, by the image processing module, to the deformation graph, a list of the generated deformation nodes, the 3D position of the one or more deformation nodes, the 3D affine matrix of the one or more deformation nodes, and the translation vector of the one or more deformation nodes.

8. The method of claim 7 , further comprising deforming, by the image processing module, the one or more deformation nodes of the deformation graph to match at least one point in the partial scan.

9. The method of claim 8 , wherein the 3D affine matrix of the one or more deformation nodes is kept as rigid as possible during the step of deforming the one or more deformation nodes of the deformation graph.

10. The method of claim 8 , wherein a first deformation influence of the one or more deformation nodes to at least one of the searched neighboring deformation nodes is kept as similar as possible to a second deformation influence of the at least one of the searched neighboring deformation nodes to the one or more deformation nodes.

11. The method of claim 8 , further comprising optimizing, by the image processing module,the deformation graph based upon at least one of rigidity, smoothness, and fit.

12. The method of claim 1 , wherein the step of reshaping the refined deformed 3D model to have greater detail further comprises:

identifying, by the image processing module, for each point in the refined deformed 3D model, one or more neighbor points in the refined deformed 3D model;

determining, by the image processing module, an average distance between each point in the refined deformed 3D model and the identified one or more neighbor points in the refined deformed 3D model;

identifying, by the image processing module, for each point in the refined deformed 3D model, one or more neighbor points in the partial scan;

selecting, by the image processing module, one or more of the identified neighbor points in the partial scan that are located inside a cylinder region of the partial scan;

determining, by the image processing module, an average of the selected neighbor points in the partial scan that are located inside the cylinder region of the partial scan; and

moving, by the image processing module, each point in the refined deformed 3D model to the average of the selected neighbor points in the partial scan that are located inside the cylinder region of the partial scan.

13. The method of claim 12 , wherein:

a center of the cylinder region of the partial scan is a point in the refined deformed 3D model,

an axis of the cylinder region of the partial scan is a normal of the point in the refined deformed 3D model, and

a radius of the cylinder region of the partial scan is the average distance between each point in the refined deformed 3D model and the one or more neighbor points in the refined deformed 3D model.

14. The method of claim 1 , wherein the step of adjusting the refined deformed 3D model according to the reshaped 3D model comprises deforming one or more points in the refined deformed 3D model to match one or more corresponding points in the reshaped 3D model.

15. A system for closed-form 3D model generation of non-rigid complex objects from scans with large holes, the system comprising a computing device having a memory that stores an image processing module and a processor that executes the image processing module to:

receive (i) a partial scan of a non-rigid complex object captured by a sensor coupled to the computing device, (ii) a partial 3D model corresponding to the non-rigid complex object, and (iii) a whole 3D model corresponding to the non-rigid complex object, wherein the partial scan and the partial 3D model each includes one or more large holes;

perform a rough match between the partial 3D model and the partial scan;

change the whole 3D model using the rough match to generate a deformed 3D model;

refine the deformed 3D model using a deformation graph;

reshape the refined deformed 3D model to have greater detail; and

adjust the refined deformed 3D model according to the reshaped 3D model to generate a closed-form 3D model that closes the one or more large holes in the partial scan.

16. The system of claim 15 , wherein the processor performs the rough match between the partial 3D model and the partial scan by:

deforming the partial 3D model to at least partially match the partial scan by creating new holes in the partial 3D model that are similar to the one or more large holes in the partial scan; and

deforming the one or more large holes in the partial 3D model based upon deforming the partial 3D model to at least partially match the partial scan.

17. The system of claim 16 , wherein the processor deforms the partial 3D model to at least partially match the partial scan using a coherent point drift algorithm.

18. The system of claim 16 , wherein the processor deforms the one or more large holes in the partial 3D model using a thin-plate spline algorithm.

19. The system of claim 16 , wherein the processor down-samples the partial 3D model and the partial scan before deforming the partial 3D model to at least partially match the partial scan.

20. The system of claim 15 , wherein the processor refines the deformed 3D model using the deformation graph by:

uniformly down-sampling the whole 3D model; and

building the deformation graph based upon the down-sampled whole 3D model.

21. The system of claim 20 , wherein the processor builds the deformation graph by:

generating one or more deformation nodes for each point in the down-sampled whole 3D model;

initializing a 3D position of the one or more deformation nodes using a 3D position of a corresponding point in the down-sampled whole 3D model;

searching neighboring deformation nodes for the one or more deformation nodes within a predetermined distance; and

initializing a 3D affine matrix and a translation vector for the one or more deformation nodes based upon the searched neighboring deformation nodes; and

assigning, to the deformation graph, a list of the generated deformation nodes, the 3D position of the one or more deformation nodes, the 3D affine matrix of the one or more deformation nodes, and the translation vector of the one or more deformation nodes.

22. The system of claim 21 , wherein the processor deforms the one or more deformation nodes of the deformation graph to match at least one point in the partial scan.

23. The system of claim 22 , wherein the 3D affine matrix of the one or more deformation nodes is kept as rigid as possible during deforming of the one or more deformation nodes of the deformation graph.

24. The system of claim 22 , wherein a first deformation influence of the one or more deformation nodes to one or more of the searched neighboring deformation nodes is kept as similar as possible to a second deformation influence of the one or more of the searched neighboring deformation nodes to the one or more deformation nodes.

25. The system of claim 22 , wherein the processor optimizes the deformation graph based upon at least one of rigidity, smoothness, and fit.

26. The system of claim 15 , wherein the processor reshapes the refined deformed 3D model to have greater detail by:

identifying for each point in the refined deformed 3D model, one or more neighbor points in the refined deformed 3D model;

determining an average distance between each point in the refined deformed 3D model and the one or more identified neighbor points in the refined deformed 3D model;

identifying, for each point in the refined deformed 3D model, one or more neighbor points in the partial scan;

selecting one or more of the identified neighbor points in the partial scan that are located inside a cylinder region of the partial scan;

determining an average of the selected neighbor points in the partial scan that are located inside the cylinder region of the partial scan; and

moving each point in the refined deformed 3D model to the average of the selected neighbor points in the partial scan that are located inside the cylinder region of the partial scan.

27. The system of claim 26 , wherein:

a center of the cylinder region of the partial scan is a point in the refined deformed 3D model,

an axis of the cylinder region of the partial scan is a normal of the point in the refined deformed 3D model, and

a radius of the cylinder region of the partial scan is the average distance between each point in the refined deformed 3D model and the identified one or more neighbor points in the refined deformed 3D model.

28. The system of claim 15 , wherein the processor adjusts the refined deformed 3D model according to the reshaped 3D model by deforming one or more points in the refined deformed 3D model to match one or more corresponding points in the reshaped 3D model.