Parametric shape grammar interpreter

• US 7,415,156 B2
• Filed: 01/24/2003
• Issued: 08/19/2008
• Est. Priority Date: 01/28/2000
• Status: Expired due to Fees

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Cagan, Jonathan, McCormack, Jay P.
• Primary Examiner(s): CARTER, AARON W
• Application Number:
  US10/350,428
• Publication Number:
  US 20030152273A1
• Time in Patent Office: 2,034 Days
• Field of Search: 382/203, 345419-428
• US Class Current: 382/203
• CPC Class Codes: G06V 10/424 Syntactic representation, e.g. by using alphabets or grammars
• CPC Class Codes: G06V 10/752 Contour matching
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

Parametric shape recognition is achieved through a decomposition of shapes into a hierarchy of subshapes ordered by their decreasing restrictions. Instances of each of the subshapes are individually located in the design shape and then reconstructed to form an instance of the entire shape. The basis for the hierarchy of subshapes can be specified by the designer or based on the default parameter relations that come from architectural and engineering knowledge. The levels of the hierarchy are defined so that the most constrained lines of a shape are those lines that the designer intended exactly. These most constrained lines have specified parametric relations to other line segments and those relations, if altered, will compromise the designer'"'"'s intentions. Conversely, the lowest level of the hierarchy, which contains the least constrained line segments, only implies a specific connectivity between line segments, necessitating a vaster search. The parametric recognition of curved line shapes used a two-step approach that first performs shape matching with an equivalent straight-line shape then checks those transformations for matching with the actual curved lines. This approach has advantages characteristic polygons as well as emergent shapes.

Claims

1. A parametric shape interpreter, comprising:

a shape decomposition module for decomposing a shape into a group of subshapes, said subshapes having equivalent straight lines for curved lines; and

a shape recognition module in communication with the shape decomposition module, wherein the shape decomposition module decomposes a left-hand shape of a shape grammar rule into at least one subshape belonging to one of a plurality of subshape groups.

2. The parametric shape interpreter of claim 1, wherein the subshape groups have a hierarchical order of decreasing constraints.

3. The parametric shape interpreter of claim 1 wherein the shape decomposition module decomposes a two-dimensional, left-hand shape of a shape grammar rule into one or more subshapes.

4. The parametric shape interpreter of claim 1, wherein the shape decomposition module decomposes a three-dimensional, left-hand shape of a shape grammar rule into one or more subshapes.

5. The parametric shape interpreter of claim 1, wherein the shape decomposition module decomposes a one-dimensional, left-hand shape of a shape grammar rule into one or more subshapes.

7. The parametric shape interpreter of claim 1, wherein the shape recognition module recognizes a parametric transformation of the left-hand shape of the shape grammar rule in a target shape by searching the target shape for a parametric transformation of the subshape.

8. The parametric shape interpreter of claim 7, wherein the shape recognition module recognizes a parametric transformation of the left-hand shape of the shape grammar rule in a target shape by progressively searching for a parametric transformation of a subshape belonging to each of the subshape groups that is not null and subtracting the parametric transformation from the target shape.

9. The parametric shape interpreter of claim 8 wherein the parametric transformations are based on the original curved line.

6. The parametric shape interpreter of 1, wherein the shape recognition module searches a target shape for a parametric transformation of the subshape.

10. A shape grammar system, comprising:

a parametric shape grammar interpreter for recognizing parametric transformations of a first shape in a target shape, said interpreter comprising a shape decomposition module for decomposing said first shape into a group of subshapes, said subshapes having equivalent straight lines for curved lines, said interpreter further comprising a shape recognition module in communication with the shape decomposition module; and

a rule application module in communication with the parametric shape grammar interpreter, wherein the first shape is a left-hand shape of a shape grammar rule, said shape decomposition module for decomposing said left-hand shape into at least one subshape belonging to one of a plurality of subshape groups.

11. The shape grammar system of claim 10, wherein the subshape groups have a hierarchical order of decreasing constraints.

12. The shape grammar system of claim 10, wherein the shape recognition module recognizes a parametric transformation of the left-hand shape of the shape grammar rule in said target shape by searching said target shape for a parametric transformation of the subshape.

13. The shape grammar system of claim 12, wherein the shape recognition module recognizes a parametric transformation of the left-hand shape of the shape grammar rule in said target shape by progressively searching for a parametric transformation of a subshape belonging to each of the subshape groups that is not null and subtracting the parametric transformation of the subshape from the target shape.

14. The shape grammar system of claim 12, wherein the rule application module applies the shape grammar rule by subtracting the parametric transformation of the left-hand shape of the shape grammar rule from said target shape and substituting therefore a transformation of a right-hand shape of the shape grammar rule.

15. The shape grammar system of claim 12, further comprising an intelligent rule selection module in communication with the parametric shape grammar interpreter.

16. A parametric shape grammar interpreter, comprising:

means for decomposing a left-hand shape of a shape grammar rule into at least one subshape belonging to one of a plurality of subshape groups, said subshapes having equivalent straight lines for curved lines; and

means for recognizing a parametric transformation of the left-hand shape of the shape grammar rule in a target shape by progressively searching for a parametric transformation of a subshape belonging to each of the subshape groups that is not null and subtracting the parametric transformation of the subshape from the target shape, said mean for recognizing including means for adding a parametric transformation of a first subshape found in the target shape belonging to a first of the subshape groups and a parametric transformation of a second subshape found in a second target shape belonging to a second of the subshape groups, wherein the second target shape corresponds to the transformed first subshape subtracted from the target shape.

17. A method of recognizing parametric transformations of a left-hand shape of a shape grammar rule in a target shape, comprising:

decomposing the left-hand shape of the shape grammar rule into at least one subshape belonging to one of a plurality of subshape groups, said subshapes having equivalent straight lines for curved lines;

progressively searching for a parametric transformation of a subshape belonging to each of the subshape groups that is not null and subtracting the parametric transformation from a target shape; and

adding a parametric transformation of a first subshape found in the target shape belonging to a first of the subshape groups and a parametric transformation of a second subshape found in a second target shape belonging to a second of the subshape groups, wherein the second target shape corresponds to the transformed first subshape subtracted from the target shape.

18. A method of recognizing parametric transformations of a left-hand shape of a shape grammar rule in a target shape, comprising:

searching the target shape for a parametric transformation of a first subshape, from a group of subshapes derived from the left-hand shape of the shape grammar rule, said subshapes having equivalent straight lines for curved lines;

generating a second target shape corresponding to the parametric transformation of the first subshape, found in the target shape, subtracted from the target shape;

searching the second target shape for a parametric transformation of a second subshape from said group of subshapes; and

adding the parametric transformation of the first subshape found in the target shape to a parametric transformation of the second subshape found in the second target shape.

19. The method of claim 18, further comprising:

generating a third target shape corresponding to the parametric transformation of the second subshape subtracted from the second target shape;

searching the third target shape for a parametric transformation of a third subshape from said group of sub shapes; and

adding the parametric transformation of the third subshape found in the third target shape to a sum of the parametric transformation of the first sub shape found in the target shape and the parametric transformation of the second subshape found in the second target shape.

20. The method of claim 18, further comprising:

subtracting a sum of the parametric transformation of the first subshape found in the target shape and the parametric transformation of the second subshape found in the second target shape from the target shape; and

adding a corresponding transformation of a right-hand shape of the shape grammar rule to the target shape.

21. A method of recognizing a first shape in a target shape, comprising:

decomposing the first shape into at least one subshape belonging to one of a plurality of subshape groups, said subshapes having equivalent straight lines for curved lines; and

searching the target shape for a parametric transformation of the subshape, wherein searching the target shape includes progressively searching the target shape for a parametric transformation of a subshape belonging to each of the subshape groups that are not null and subtracting the parametric transformation of the subshape from the target shape.