Transcript A Methodology for automatic retrieval of similarly shaped

A Methodology for automatic retrieval of
similarly shaped machinable components
Mark Ascher - Dept of ECE
1
Motivation
• Retrieval of similarly shaped components can:
– Add functionality to existing CAD databases
– allow for the reuse of process plans which can both speed up and
reduce the cost of development.
Challenges
• Retrieval of similarly shaped components has many
challenges:
–
–
–
–
Multiple interpretations
Interacting features
Topological differences do not guarantee component dissimilarity
Graph matching solution is computationally intensive
2
Examples of Challenges
Part1
Both Components Contain:
1 Slot
2 Blind Slots
Part2
1 Pocket
Example of components with similar features and different shapes
id
Slot BlindSlot Step Pocket Hole
Part1
1
2
0
1
0
Part2
1
2
0
1
0
3
Examples of Challenges
Example of multiple interpretations and representation complexity
id
Slot BlindSlot Step Pocket Hole
Part1
1
2
0
0
0
Part2
3
0
0
0
0
Part3
4
0
0
1
0
Part4
1
2
0
1
0
4
Contributions
• Retrieval of sub pieces to cover a component
– Use of Maximal Feature Sub-graphs to divide a
component
• Use of type abstraction hierarchies to guide
similarity search
– Feature and interaction Histogram based
– Ability to abstract Features and Interactions of
machinable components
– Ability to determine distances of features and
interactions based on objective criterion
5
Related Work
• Shape Based Similarity Retrieval (Eakins)
– Two dimensional parts
– retrieved complete components
• Volumetric Reasoning (Lee et al) and Planar
Reasoning (Cohn et al)
– Groundwork for symbolic volumetric reasoning
– Does not address part matching
• Content Retrieval From Images Based on
Knowledge of Shape (Hsu et al)
– Worked with medical images
– Presented the Type Abstraction Hierarchy Concept
6
Related Work
• 3D Model Shape Based Similarity Retrieval
(Osada et al, Regli et al)
– Uses D2 Distance measures
– Works well for simple models
• Feature Based Model Retrieval (Regli et al)
– Retrieves complete models
– Feature interaction representation too simplistic
– No method for indexing
7
Problem Formulation
• The problem simply stated is:
Given a component find components in a database
that have the same or the most similar shape to the
given component.
• Given a component represented as a set of features
F and a set of interactions between them I find the
component in the database that contain the closest
representation to the given component.
The
n
closest is defined as min( iE  df (FqS , Fi)  di( IqS , Ii))
S 1
Where E is the existing part
database, q
indicates the query part, S is the set of Sub-parts in
the query component. And df and di are the feature
and interaction distance functions respectively.
8
Problem Formulation
• Components represented as a qualitative model
– Features are nodes
– Interactions are directed labeled edges R1,2, where the
labels are nxm qualitative matrices
– Requires a unique way to interpret a component as
features
9
Features
• A Features is represented as a 4-tuple (T, f, D, I) where:
– T is the type (slot, hole, etc.)
• Slot
– f is the sweep face (set of points)
f
• {(1,1,0),(1,2,0),(2,2,0),(2,1,0)}
– D is the sweep direction (vector)
T=
D
Slot
• (0,0,-1)
– I is the sweep interval (distance)
I
• (2)
• Additional information that can be maintained for a feature
–
–
–
–
Finish
Accessibility
Tolerances
etc
10
Set of Canonical Features
Slot
Pocket
Blind
Slot
Hole
Step
Blind
Step
Note: Holes are modeled similar to pockets for
Interaction Characterization, But sweep face is modeled
as a center and radius
11
Interactions
• Interactions Represented as an nxm matrix where:
– n is the number of faces in feature 1(f1)
– m is the number of faces in feature 2 (f2)
– Entries are in the set { +, -, s, i}
•
•
•
•
+ indicates that f1 lies in the positive half space of f2
- indicates that f1 lies in the negative half space of f2
s indicates they lie on the same plane
I indicates that the features interact
R5,2
12
Interactions Continued
• If only orthonormal features are considered
– Results in 6x6 interaction Matrices
– The near diagonal data points contain the pertinent data
– The number of unique columns is reduced to 4 types
•
•
•
•
+s indicates a shared face with no internally points shared
-s indicates a shared face with internally shared points
-- indicates a face that is interior to both faces of the other feature
-+ indicates a face that is not interior to one face of the other feature
– The following Combinations are invalid:
• ++ can not be outside both faces parallel to the face of interest
• ss can not be the same as two faces which bound a feature
-s
--
+-
+s
13
Interactions Continued
• For feature interactions Pairs of parallel Faces need to be
compared Resulting in 7 Feasible Combinations:
Type Face 1 Face 2 Relation of faces to other Feature
1
-s
-s
Both Faces Shared
2
-s
-One Face Shared Other Inside
-+
3
One face shared, Other Outside Opp
-s
-s
+s
Not Possible
4
--Both Faces Inside
5
--+
One Face Inside, Other Outside
-+s
Not Possible
6
-+
-+
Both Outside
7
-+
+s
One Face Shared, Other Outside
+s
+s
Not Possible
14
Interactions Continued
• Each Interaction Type has an inverse.
Type Face 1 Face 2
1
-s
-s
2
-s
--+
3
-s
4
--5
--+
6
-+
-+
7
-+
+s
Inverse Interaction
1
3
2
6
5
4
7
15
Interactions Continued
• Several types indicate a family of interactions.
Type Face 1 Face 2
3
-s
-+
5
--+
6
-+
-+
7
-+
+s
Interaction Family
Intrusion
Improper Interaction
Pass Through
Face
16
Show All Interactions Here
17
Example of Interaction Directedness
Delta Volume
Slot to Pocket
Pocket to Blindslot
18
Definition of Closeness (Distance Measures)
Distance measures characterize the distance between two
features or two interactions. Objectives for the distance
measures were:
•Determinable based on the data available
•Objectively based
Additional desirable properties include:
•Ease of calculation
•Scalable to other features/interactions
19
Feature Distance Measure
• Measures Considered For Comparison
– Number of Faces created on the component
• Parallel to D
• Perpendicular to D
–
–
–
–
Number of internal Edges created on the component
Number of total Edges created on the component
Number of non-convex Corners created by feature
Number of Accessibility faces
20
Interaction Distance Measure
• Measures Considered For Comparison
–
–
–
–
–
–
–
–
Number of Faces created on the component
Number of Edges created on the component
Number of convex Corners created on the component
Number of Corners created on the component
Histogram of Interaction Symbols {-, +, S, I}
Histogram of Parallel face types { (--,--), (-s,--),…}
Histogram of Single – Parallel Face interactions { --. +-, +s, -s}
Number of relative face changes to equate near diagonal values of one
interaction to the other
21
Maximal Feature Sub-Graph
• Maximal Features
– Features that can not be subsumed by other features
• The Maximal Feature Sub-Graph is the graph containing
only Maximal Features
– Unique interpretation of a component
– Contains fewer features
22
Blocks of MFSG
• The Maximal Feature Sub-Graphs can be further subdivided into blocks
– Blocks are defined as Maximal sets of features that all interact
– Blocks represent sub-pieces of a component that can be utilized for
searching.
– Isomorphism can be used to determine redundant blocks from a
component
• Further reduces the search space
23
Example Component
24
Interaction Types
• Consideration of Maximal Orthonormal Features reduces
the number of interaction types.
– Maximal Features necessitate that the example component shown
be reduced to two features A  C, and B  C  D.
• Volume D and C can not be combined as a Maximal Feature
• Volumes A, B, C, D alone are not Maximal Features
• Volume C can not be subdivided
Example:
A
B
D
C
25
Solution Approach
• The solution approach
–
–
–
–
–
Methods to reduce the search space
TAHs encode knowledge of existing components
TAHs encode knowledge for query relaxation
Separate hierarchies for features and interactions
Final comparison performed using graph isomorphism
26
Solution Approach Continued
• Feature Type Hierarchy
– Each level contains histograms of feature types
– Feature types are combined into fewer buckets based on feature
similarity
– Similarity can be based on:
• Family (slot, pocket, hole)
27
Example Component and Feature TAH
4
2,2,1,0
Holes
Pockets
Steps
Slots
2,0,0,1,1,0,0,0
Through Hole
Hole
Through Pocket
Pocket
BlindStep
Step
BlindSlot
Slot
4 Features present in the part 2 slots, 1
step, and 1 pocket. The level of
abstraction (level of query relaxation)
indicates which of the histograms are
compared to the query. This example
groups features based on type.
28
Solution Approach Continued
• Feature Interaction Hierarchy
– Each level contains histograms of feature interactions
– Feature interactions are combined into fewer buckets based on
feature interaction sorts
29
Example Component and Interaction TAH
9
1,7,1,2,0
Improper Only
Face
Pass Through
Intrusion
Boundary
1,7,0,1,0,0,2,0,0,0
I
FP
IF
FI
FB
IB-1
IP
I-1
PI-2b
PI-2a
…
PI-3
…
PI-1
PI-0
PI-2a(BST-3, BST-2), FI-2(BST-3, SL-2), FI-2(BST-3, SL-1),
IP
PP
II
PI
IB
The features present have 9 Interactions:
2,0,0,1,1,0,0,0
PI-3(BST-1, SL-1), PI-3(BST-1, SL-2), PP-2b(SL-1, SL-2),
IB-1(BST-1,BST-2), PI-2a(BST-1, SL1), PI-2a(BST-1, SL2)
30
TAH Comments
• The TAHs can be relaxed individually to
allow for only feature relaxation or
interaction relaxation
• The Hierarchies can be constructed such
that only certain interaction or feature types
are considered for relaxation
31
Searching
• Searching is performed by comparing the feature and
interaction histograms for the target component with those
saved in the database
– A TAH can direct the search to a similar feature set when exact
matches can not be found.
– A TAH can direct the search to a similar feature interaction set
when exact matches can not be found
– Histograms encode the knowledge about features and interactions
in the database components
32
Overview of Solution Approach - Query
Processing
Qualitative Model
Pick a block
MFSG
Is the block
isomorphic to a
previous block
Extract Blocks
and make a list
Yes
No
No
Yes
Blocks Remaining
Relax Query
Return Match
List
No
Search for
Matching
Histograms
Match Found
Yes
Post Selection
Processing
Return Match
Mark Block as
Matched
33
Example
Select: Match List
From: TAHs
Where: Same as Reference to b-rep
Component
This component contains:
27 Extractable features
over 200 interactions
Many potential interpretations!
Submitted
Features Extracted (only
Feature Interactions
maximal features shown)
34
Example Continued
Maximal Feature Sub Graph
Blocks determined to be
isomorphic
•Further reduces the search
space
MFSG Blocks Extracted
Example Component Database
•For purposes of illustration a sub-set of a
database is presented
•TAHs constructed containing all of the
blocks of existing components
35
Example Continued
Component
Submitted
Example components
The block contains 3 steps
The block contains 2 PI-3 interactions and 1 PI-2A
interaction
Component d’s block is determined to contain the same
feature and interaction histograms and is returned as a
match
36
Summary
• Methodology for intelligently searching for similarly
shaped components presented
–
–
–
–
Spatial interactions modeled by a qualitative model
Generates a unique component model with the MFSG
Reduces search space through the use of MFSG blocks
Reduces computational intensiveness through encoding knowledge
of features and interactions into TAHs
Future Work
• Increase the size and complexity of the example database
37