Multi-scale segmentation and partial matching 3D models

• US 8,015,125 B2
• Filed: 08/30/2007
• Issued: 09/06/2011
• Est. Priority Date: 08/31/2006
• Status: Active Grant

• Current Assignee: Drexel University
• Original Assignee: Drexel University
• Inventors: Shokoufandeh, Ali, Bespalov, Dmitriy, Regli, William C.
• Primary Examiner(s): Rivas; Omar F Fernandez
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US11/847,942
• Publication Number:
  US 20080215510A1
• Time in Patent Office: 1,468 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics

Abstract

A scale-Space feature extraction technique is based on recursive decomposition of polyhedral surfaces into surface patches. The experimental results show that this technique can be used to perform matching based on local model structure. Scale-space techniques can be parameterized to generate decompositions that correspond to manufacturing, assembly or surface features relevant to mechanical design. One application of these techniques is to support matching and content-based retrieval of solid models. Scale-space technique can extract features that are invariant with respect to the global structure of the model as well as small perturbations that 3D laser scanning may introduce. A new distance function defined on triangles instead of points is introduced. This technique offers a new way to control the feature decomposition process, which results in extraction of features that are more meaningful from an engineering viewpoint. The technique is computationally practical for use in indexing large models.

Claims

1. A method of searching a database for a solid model comprising the steps of:

providing a query model;

determining a first set of values based on predetermined properties of said query model;

wherein said first set of values includes at least a first set of distances between points on triangular faces of said query model, said distances being determined by determining an angular shortest path between two triangular faces on said query model, wherein the angular shortest path on the query model is the shortest path on the surface of the training model which is computed in terms of an angular difference between the two triangular faces on the query model;

comparing said first set of values to a second set of values that is determined by predetermined properties for a group of models for training, said predetermined properties of said models for training including at least a second set of distances between points on triangular faces of the models for training, said second set of distances being determined by determining an angular shortest path between two triangular faces on said models for training, wherein the angular shortest path on the model for training is the shortest path on the surface of the model for training which is computed in terms of an angular difference between the two triangular faces on the model for training; and

indexing, classifying and partially matching said query model with one or more models for training based on said comparing step.

2. A method as claimed in claim 1, wherein a maximum angle D(t_i, t_j) on the angular shortest path on the query model or the model for training is computed using a distance function:

3. A method as claimed in claim 1, wherein said comparing step compares values from a sub-graph isomorphism.

4. A method as claimed in claim 1, wherein said comparing step compares values obtained from a single scan of said query model.

5. A method as claimed in claim 1, wherein said comparing step compares values obtained from a plurality of different scans of said query model.

6. A method as claimed in claim 1, wherein said comparing step compares values for the entire query model.

7. A method as claimed in claim 1, wherein said query model is at least partially matched with a plurality of models for training to identify five to twenty models for training similar to said query model.

8. A method as claimed in claim 1, wherein said query model is indexed.

9. A method as claimed in claim 1, wherein said query model is classified.

18. A method as claimed in claim 1, wherein said comparing step comprises the step of many-to-many comparison of groups of features of the query model to groups of features of the models for training.

10. A method as claimed in 1, wherein said determining step comprises the step of decomposing the query model into a plurality of significant features.

11. A method as claimed in claim 10, wherein said decomposing step finds a subspace S having k dimensions corresponding to k significant features by minimizing a quantity:

12. A method as claimed in claim 11, wherein said decomposing step comprises the following steps:

13. A method as claimed in claim 11, wherein the decomposing of a feature is stopped when a root branch in a feature decomposition tree reaches a predetermined depth.

14. A method as claimed in claim 11, wherein the decomposing of a feature is stopped when the distance of the angular shortest path between two triangular faces on said query model is less than a predetermined value.

15. A method as claimed in claim 12, wherein the decomposing of a feature is stopped when the distance of the angular shortest path between two triangular faces on said query model is less than a predetermined value.

16. A method as claimed in claim 11, wherein the decomposing of a feature is stopped when the angular shortest path between two triangular faces on said query model with t_iε

M₂ and t_jε

M₃ containing two faces t_m and t_l meets the following condition;

∀

t_iε

M₂, t_jε

M₃∃

t_m→

t_lε

t_it_j s.t.

t_mε

M₂^t_lε

M₃^∠

(t_m,t_l)=D(t_i, t_j).

17. A method as claimed in claim 12, wherein the decomposing of a feature is stopped when the angular shortest path between two triangular faces on said query model with t_iε

M₂ and t_jε

M₃ containing two faces t_m and t_l meets the following condition;

∀

t_iε

M₂, t_jε

M₃∃

t_m→

t_lε

t_it_j s.t.

t_mε

M₂^t_iε

M₃^∠

(t_m,t_l)=D(t_i, t_j).

19. A method as claimed in claim 17, wherein said comparing step comprises the step of many-to-many comparison of groups of features of the query model to groups of features of the models for training.

20. A method of searching a database for a solid model comprising the steps of:

providing a query model;

determining a first set of values based on predetermined properties of said query model;

wherein said first set of values includes at least a first set of distances between points on triangular faces of said query model, said distances being determined by determining an angular shortest path between two triangular faces on said query model; and

comparing said first set of values to a second set of values that is determined by predetermined properties for a group of models for training, said predetermined properties of said models for training including at least a second set of distances between points on triangular faces of the models for training, said second set of distances being determined by determining an angular shortest path between two triangular faces on said models for training, wherein a maximum angle D(t_i, t_j) on the angular shortest path is computed using a distance function;