Multi-scale segmentation and partial matching 3d models

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.

1 . A method of searching a database of training models using partial matching a first set of values based on predetermined properties of a query model, said method comprising the steps of:
 partially matching said first set of values to a second set of values from a sub-graph isomorphism for said training models.   
     
     
         2 . (canceled) 
     
     
         3 . The method of  claim 1 , wherein said first set of values is obtained from a single scan of said query model. 
     
     
         4 . The method of  claim 1 , wherein said first set of values is obtained from a plurality of different scans of said query model. 
     
     
         5 . The method of  claim 1 , wherein said first set of values comprises values for the entire query model. 
     
     
         6 . The method of  claim 1 , wherein said sub-graph isomorphism is generated using a largest common subgraph algorithm. 
     
     
         7 . The method of  claim 1 , wherein said sub-graph isomorphism is used to assess the similarity of feature adjacency graphs. 
     
     
         8 . The method of  claim 1 , wherein determining the first set of values comprises decomposing the query model into a plurality of features. 
     
     
         9 . The method of  claim 8 , wherein the second set of values is determined by decomposing the training models into a plurality of features. 
     
     
         10 . The method of  claim 9 , wherein the decomposing of a feature is stopped when a root branch in a feature decomposition tree reaches a predetermined depth. 
     
     
         11 . The method of  claim 9 , wherein the decomposing of a feature is stopped when the distance of the angular shortest path between two triangular faces on the query model or training model is less than a predetermined value. 
     
     
         12 . The method of  claim 1 , wherein the first set of values is determined by a 3D scan and the second set of values is determined from CAD models. 
     
     
         13 . The method of  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. 
     
     
         14 - 20 . (canceled) 
     
     
         21 . The method of  claim 1 , wherein a hill-climbing algorithm with random restarts is used to implement the sub-graph isomorphism. 
     
     
         22 . The method of  claim 1 , wherein recall plots are constructed using a scale-space retrieval technique with max-angle distance function. 
     
     
         23 . The method of  claim 22 , wherein a plurality of recall plots are constructed each associated with a fidelity setting. 
     
     
         24 . The method of  claim 1 , wherein scale-space decomposition is used to extract features from the query model and said extracted features are used to provide said first set of values. 
     
     
         25 . The method of  claim 1 , wherein locality-based feature representation is used to represent features from the query model and said represented features are used to provide said first set of values.