2.1. Topological and geometric entity graph

A feature is a geometric entity defined by its shape and technological characteristics, typically represented by a set of topologically associated faces. Given two finite, nonempty sets D^tpl = {D₁^tpl,D₂^tpl · · · D_m^tpl} and D^geo = {D₁^geo, D₂^geo · · · D_n^geo}, which are called the set of topological domains and the set of geometric domains, respectively; two sets of attributes A^tpl = {a₁^tpl, a₂^tpl · · · a_m^tpl} and A^geo = {a₁^geo, a₂^geo · · · a_n^geo}, which are called the set of topological attributes and the set of geometric attributes, respectively, where each attribute is associated with each domain; and X = {X₁, X₂ · · · X_i · · · X_m}, which is a set of features. Then, any shape feature X_i can be characterized by a set of faces F = {f₁, f₂ · · · f_i · · · f_m} that satisfy a set of topological and geometric relations. These relations are defined for domains corresponding to the set of topological and geometric attributes, respectively. Table 1 shows typical cases of those attributes and their respective domains. These relations may be represented by the topological and geometric entity graph, defined as follows:

Domains and associated attributes

Definition.

For two given sets

where F = {f₁, f₂ · · · f_i · · · f_m} is a set of faces and e_i* = (a₂^tpl, a₃^geo) is an entity associated with each face f_i, and

where e_ij = (a₁^tpl, a₁^geo, a₂^geo), we call G = (F*, E) the topological and geometric entity graph. █

In the graphical representation of the topological and geometric entity graph, the nodes associated with the label e_i* = (a₂^tpl, a₃^geo, a₄^geo) represent the topological and geometric relation of the faces, and the edges associated with the label e_ij = (a₁^tpl, a₁^geo, a₂^geo) represent the topological and geometric relation between a pair of faces (f_i, f_j). Figure 1 shows the representation of the “Slot” feature by the topological and geometric entity graph.

〈Slot〉 and its topologic and geometric entity graph.

2.2. Feature grammar

A feature language describes the generation of feature structures, joint elements, and attaching elements. A grammar provides the finite generic description of this language. Thus, we will focus on finding a feature grammar, which provides the generic and productive description of the feature language. In these conditions, a feature grammar can be defined as an 8-plet:

where V_structure^T = {a, b, c · · ·} is the terminal vocabulary of structures, a nonempty finite set; V_joint-tie^T = {0, 1, 2 · · · j · · · m}, m ∈ N, is the terminal vocabulary of joint-tie elements, a nonempty finite set; V_structure^N = {A, B · · · S · · ·} is the nonterminal vocabulary of structures, a nonempty finite set; V_joint-tie^N = {O, I, II, III · · · ∇, Λ} is the nonterminal vocabulary of joint-tie elements, a nonempty finite set; S, ∇, and Λ are the respective structure, joint, and connection axioms;

is a set of production rules; and

The production rules of the feature grammar have the following format:

where α is called the left-side component matrix, α = [α_ij], i = 1, j = 1; β is called the right-side component matrix, β = [β_ij], i = 1, j = 1, 2 · · · m; m is the number of components; Λ_α is called the left-side joint matrix, Γ_α = [Γ_αij], i = 1, 2 · · · n; j = 1; n is the number of attaching elements; Λ_β is called the right-side joint matrix; Γ_β = [Γ_βij], i = 1, 2 · · · n; j = 1, 2 · · · m; Δ_α is called the left-side tie-point matrix, Δ_α = [Δ_αij], i = 1, 2 · · · s; j = 1; s is the number of attaching elements; and Δ_β is called the right-side tie-point matrix, Δ_β = [Δ_βij], i = 1, 2 · · · s; j = 1, 2 · · · n.

There are three levels of production rules for the feature grammar. The first is the component level. These rules have the following formats:

or

where α ∈ V_structure^N; β = v₁, v₂ · · · v_j · · · v_m; this matrix defines an order relation for these components; v_j ∈ V_structure^T ∪ V_structure^N is a terminal or nonterminal structure called the component structure; and m is the number of structures.

The second level is the joint level. These rules have the following formats:

or

where y_i is a joint element and t_ij is an attaching element of component j, defined according to the order in the right-side component matrix, that participates in forming the y_i.

The third level is the connection level. These rules have the following formats:

or

where z_i is an attaching element and t_ij is an attaching element of component j, defined according to the order in the right-side component matrix, that participates in forming the z_i.

2.2.1. Conditional feature grammar

The feature grammar represents the purely syntactic side. It does not always allow the expression of the full complexity of structural relations between the primitive elements composing a feature. If a syntax rule must meet mandatory conditions before being applied, then a conditional feature grammar is defined as follows:

where G_feature is the feature grammar,

are the three levels of semantic conditions, A_geo-tpl is the set of geometric and topological attributes, and D_geo-tpl is the set of geometric and topological domains.

2.3. Application

Given a set of features (Fig. 2)

A sample of the features in the set X. [A color version of this figure can be viewed online at www.journals.cambridge.org]

A feature can be represented by the selected topological and geometric entity graph, defined as follows:

Definition.

For two given sets

where F = {f₁, f₂ · · · f_i · · · f_m} is a set of faces; e_i* = (a₂^tpl, a₃^geo) is an entity associated with each face f_i (see Table 1);

where e_ij = (adjacents, concave, a₂^geo) (see Table 1), we call G = (F*, E) the selected topological and geometric entity graph. █

For example, the representation of 〈Slot〉 and 〈Simple Blind Slot〉 features by the selected topological and geometric entity graph is illustrated below (Fig. 3).

Selected topological and geometric entity graph.

The strength of feature grammars for feature representation will depend on terminal vocabulary definition. For terminals definition, we are using the following hypothesis: a terminal represents a robust connection between faces of features. The problem of robust connection in the selected topological and geometric entity graph can be seen as the obtaining of the full maximal subgraphs of this graph. It is equivalent to decomposition of one similarity relation into maximal similarity subrelations. Considering the set of features X, we have two terminals (Fig. 4).

Selected topological and geometric entity graph.

The relationship between the set of features and the set of terminals can be represented by the bipartite graph (Fig. 5). The graph decomposition yields two classes of features: C₁^X = {Step, Slot, Partial Hole, Hole} and C₂^X = {Blind Step, Simple Blind Slot, Blind Slot, Pocket}, corresponding to two classes of terminals: C₁^V = {a} and C₂^V = {b}.

The bipartite graph and its decomposition.

Two fuzzy feature grammars G_Feature^C are inferred for the feature classes: C₁^X = {Step, Slot, Partial Hole, Hole} and C₂^X = {Blind Step, Simple Blind Slot, Blind Slot, Pocket}, respectively. For the first feature class, we have

The fuzzy feature grammar represents the syntactic and fuzzy aspect of features. Structures with the same syntax may represent features with different semantics. Thus, we can build the conditional and fuzzy feature grammar. In this case, the first level of production rules will be associated by conditions. For example, for the first level of production rules P₆, we have the following semantic condition:

Structures b and A (on the right side of rule B → bA) are attached if the direction of the main vector A (on the right side) is the same as the direction of the vector

of b, where 1 and 2 represent the attaching elements of b.

The previous condition is used in a similar fashion for rules P₁, P₃, and P₅. We will have the following condition for the first level of production rules:

The direction of the main vector of A (left side of the rule A → b) is initialized from

of b, where 1 and 2 represent the attaching elements of b.

There are no semantic conditions to be satisfied for the other rules.

For the second class, we have

The preceding production rules are associated by conditions similar to the previous class. In the case of this feature class, the mixed product

is considered. Thus, the structures (in the right part) are attached if the sign of the mixed product

does not change.

3.1. Regioning

A region defines a potential area of a part where either canonical features or features in interaction may be recognized. During the interaction, features may have lost their concavity. As a result, some faces of features in interaction are not identified during the recognition phase. In this case, the potential region for feature recognition is expanded with concave border faces (local expansion principle). Thus, we can define a region of the part as a set of connected faces characterized by their concavity or their convexity that may be transformed into concavity. Furthermore, the interaction between features may produce neighboring regions that may be either adjacent or recoverable. If {R₁ · · · R_i, R_i+1 · · · R_n} is a set of regions, then a macroregion R may be defined by grouping a set of neighboring regions (global expansion principle). For example, the part shown below (Fig. 7a) contains two regions. The first region comprises concave faces 1, 2, and 3 and convex face 7, which may be transformed to concave by the virtual extension toward face 1. The second region comprises concave faces 4, 5, and 6 and convex face 7. In this case, the convex face 7 can be transformed to concave by virtual extension toward face 6. These two regions share face 7. As a result, a macroregion is defined by 〈macroregion₁〉 → 〈region₁₁〉〈region₁₂〉, where 〈region₁₁〉 and 〈region₁₂〉 are the first and second regions, respectively, of the first macroregion 〈macroregion₁〉. The part in Marefat and Kashyap (1990; Fig. 7b) comprises a region that includes concave faces 1, 2, 3, 4, 5, and 6.

Examples of regions. [A color version of this figure can be viewed online at www.journals.cambridge.org]

Thus, the regioning procedure involves three subphases:

Example 1.

Given two parts (Fig. 7a,b). For the part in Figure 7a we can write the following:

█

3.2. Virtual extension

The faces in a region can be divided into three classes:

The first class concerns faces that resist to interaction. For example, faces 1, 2, and 3 and 4, 5, and 6 in the part in Figure 7a and faces 1, 2, 4, and 5 of the part in Figure 7b belong to this class. Despite the interaction, they kept their concavity characteristic. The second class concerns border faces. These convex faces probably lost all of their original concavity characteristics during the interaction. For example, face 7 (Fig. 7a) belongs to this class. The third class concerns primary faces, which probably lost their concavity characteristic during the interaction. For example, faces 3 and 6 (Fig. 7b) belong to this class. Thus, virtual extension consists of transforming the convex faces in the second and third classes into concave faces by generating virtual links. These links must meet the following conditions:

Illustrations of conditions. [A color version of this figure can be viewed online at www.journals.cambridge.org]

The recomposition of the virtual face is a special case for the generation of virtual links. The interaction between the canonical features may break a face down into a group of small faces. Then those small faces may be unified into a virtual face. The minimal conditions for a group of faces to be unified are as follows (Marefat & Kashyap, 1990):

The first and second conditions show that the faces have the same geometry, while the third shows that the unified face cannot be destroyed by the other faces of the part. We define an order relation between the generation of virtual faces and virtual links: we first try to generate the virtual faces by unifying the groups of faces that meet the minimal conditions. If a virtual face is generated from the unification of a group of faces, then any face in that group must be virtually extended to form virtual links.

Example 2.

Given the parts in Figure 7a and b. For the part in Figure 7a, face 7 may be transformed into a concave face by generating virtual links with faces 6 and 1 matrix (Fig. 9a), while for the part in Figure 7b, face 3 and face 6 may be transformed into concave faces by generating virtual links with faces 1 and 2, respectively (Fig. 9b). █

A matrix representing the real or virtual concavity between faces.

3.3. Structuring

Structuring consists of converting the representation of macroregions (created by regioning) with virtual faces and links (created by virtual extension) into a structure compatible with the feature grammar definition. Structuring involves the following subphases described in Section 3:

Example 3.

Given the part in Figure 7a and its matrix representing the relation between the faces (Fig. 9a). The terminals found and the canonical matrix are shown in Figure 10a and b.

The terminals and the canonical matrix of the recognized macroregion.

These terminals are type a. The terminal with faces 4 and 5 is colored first. Face 4 is colored with color 1 and face 5 with color 2. The terminal with faces 5 and 6 is colored second. As face 5 is colored with color 2 in a previous terminal, in this terminal it is colored with color 1. As a result, face 6 is colored with color 2. The membership function μ_V(a) associated with each terminal shows the extent to which that terminal is similar to terminal a. The terminal with a virtual concave edge is associated with μ_V(a) = 0.8. █

Example 4.

Given the part in Figure 7b and its matrix representing the relation between the faces (Fig. 9b). The terminals found and the canonical matrix are shown in Figure 11.

The terminals and the canonical matrix of the recognized macroregion.

The transformation of the maximum subrelations into colored terminals is shown in Figure 9b. These are type b terminals. For any terminal, the face considered as the base is colored with color 1. Thus, face 1 is colored with color 1. The other faces are colored using the same procedure. For example, the terminal with faces 1, 2, and 4 is colored first (face 1 is already colored). Face 2 is colored with color 2 and face 4 with color 3. The terminal with faces 1, 2, and 5 is colored second. As face 2 was colored with color 2 in a previous terminal, in this terminal it is colored with color 3. As a result, face 5 is colored with color 3. Thus, we continue coloring for all terminals. Terminals 5 and 6, with faces 6, 5, and 2 and 6, 2, and 4, respectively, are not colored because faces 5, 2, and 4 are already colored with colors 2 or 3. Furthermore, we consider that there is only one face with the characteristic base in a macroregion or a region. The membership function μ_V(a) associated with each terminal shows the extent to which the terminal is similar to terminal b. In the case of noncolored faces, this function takes the value of μ_V(b) = 0.3. The asterisk shows that terminals 5 and 6 participate in forming joints 2, 4, 5, and 6, but those terminals are not colored. █

3.4. Identification

The representation and the resolution of the recognition problem, for either canonical features or features in interaction, is shown in a state graph. Consider feature grammar G and a feature structure to be analyzed, represented by the canonical matrix (terminals matrix and joint matrix). A state is any possible rewriting of canonical matrices (terminal matrix and joint matrix) by one or more production rules of feature grammar G. States will constitute the nodes of the state graph. An arc will connect two states if we can pass from one state to another by a single application of a production rule of fuzzy feature grammar G or if the structure is updated after the recognition of a canonical feature in a region of features in interaction. The structure update consists of the following:

• virtually removing the faces and edges that are exclusively part of the recognized feature and considering the Virtual Extension conditions (union principle);

• reusing the faces shared by several features, knowing that if n virtual links are created to a real face, then that face will be shared by n + 1 features (sharing principle);

• creating new terminals knowing that if a face and/or edges are virtually erased in an order 3 terminal, then the terminal may be transformed into an order 2 terminal(s) (embedding principle).

Each arc is labeled with a letter representing either the production rule applied, or the notation for updating the structure. A state can be in one of the following conditions:

By applying the anchoring principle, virtual extension conditions, the sharing principle, the embedding principle, and the union principle, we have developed the following heuristic for identifying canonical features and/or features in interaction:

Step 1.

The initial structure represented by the canonical matrix defines the initial state (condition 0). The initial state is added to an ordered list of states according to the order relation of their structures.

Step 2.

If the list is empty, then failure; the procedure halts. Otherwise, we choose a state from the list using the following rule: last entered in the list, first out. It represents the current state w_i. We remove it from the list and add it to the group of processed states W.

Step 3.

If the current state w_i is a terminal state (condition 4), then success. The production rules can be found using the pointers created in step 5.

Step 4.

If production rules, set in an order relation, can be applied, then we develop the current state w_i by creating the set of successor states Y, otherwise if a feature is recognized, then the structure can be updated (according to the virtual extension conditions, the sharing principle, the embedding principle, the union principle) by creating only a successor state in Y (condition 2), otherwise go to 2 (condition 3).

Step 5.

For all states Yw_j, we put w_j in list if it does not already belong there and if it does not belong to the group of processed states. If we put w_j in the list, then we create a pointer w_j to w_i along with the production rule used.

Step 6.

Go to 2.

In the list, the last represents a maximal state. A state is maximal if it is hierarchically greater than the other states. Between two states at the same hierarchical level, the state from which a new state is formed and that is characterized by a value greater of the membership function μ is considered as a maximal state.

Example 6.

Given the part in Figure 7b, its canonical matrix (Fig. 10b) and the inferred conditional and fuzzy feature grammars G_Features^C for the feature classes: C₁^X = {Step, Slot, Partial Hole, Hole} and C₂^X = {Blind Step, Simple Blind Slot, Blind Slot, Pocket}. The canonical matrix (Fig. 10b) represents the initial state. By successively applying rules P₇, P₆, P₅, P₁, P₀ (developed on the right) in iterations 1, 2, 3, 4, and 5, we obtain the “Pocket” recognition feature with μ_Pocket = 0.8. This feature comprises faces 1, 2, 3, 4, and 5. The structure is updated in the sixth iteration. According to Condition 3 of the virtual extension conditions, the virtual extension of face 3 penalizes the virtual extension of face 6. Thus, virtual edge 6, 2 will no longer exist in the fifth and sixth terminals. According to the embedding principle, the fifth terminal of type b comprising faces 2, 5, 6 will be transformed into two type a terminals comprising faces 2, 5 and 5, 6, respectively. Similarly, the sixth terminal of type b comprising faces 2, 4, 6 will be transformed into two type a terminals comprising faces 2, 4 and 6, 4, respectively. As both terminals comprising faces 2, 5 and faces 2, 4, respectively, are already used in the two terminals comprising faces (1, 2, 5) and faces (1, 2, 4), respectively, of the Pocket feature, then they will not be considered for the recognition of a new feature. Thus, the two terminals comprising faces 5, 6 and 6, 4, respectively, remain to be considered. According to the sharing principle, face 1 will be shared with other features because a virtual link is built to it. Faces 2 and 3 will be erased because these faces do not exist in the remaining terminals. As a result, according to the embedding principle, we will have two terminals comprising faces 1, 5 and 4, 1, respectively. Finally, we have four type a terminals, comprising faces (1, 5), (5, 6), (6, 4), (4, 1), respectively. The matrix in Figure 12 shows the updated structure.

The updated structure.

By applying in succession rules P₇, P₆, P₅, P₁, and P₀ of the conditional and fuzzy feature grammar G_Feature^C, inferred for class C₁^X = {Step, Slot, Partial Hole, Hole}, we finally recognize the 〈Hole〉 feature with μ_Hole = 1. █

3.5. Modeling

The regioning phase transforms the representation B.Rep of the part into a representation by regions. The feature recognition in the identification phase transforms either the representation by macroregions into a representation by features (macroregions) or the representation by regions into a representation by features (regions). For example, for the part in Figure 7a we have

Equation (15) shows that the macroregion comprises three 〈Slots〉; Eq. (16) shows the faces that make up each 〈Slot〉.