Shape grammar interpreter

• US 7,502,511 B2
• Filed: 08/29/2007
• Issued: 03/10/2009
• Est. Priority Date: 01/28/2000
• Status: Expired due to Fees

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: McCormack, Jay P., Cagan, Jonathan
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US11/897,180
• Publication Number:
  US 20070297680A1
• Time in Patent Office: 559 Days
• Field of Search: 382/203, 345419-427
• 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 uses 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 over just matching characteristic polygons in that it can match equivalent curves with differing characteristic polygons as well as emergent shapes.

Claims

1. A shape interpreter, comprising:

a shape decomposition module implemented as code stored on a computer readable medium for decomposing a shape into a group of subshapes, said subshapes having equivalent straight lines for curved lines; and

a shape recognition module implemented as code stored on a computer readable medium in communication with the shape decomposition module, wherein the shape decomposition module decomposes one side of a production system rule into at least one subshape belonging to one of a plurality of subshape groups.

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

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

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

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

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

7. The shape interpreter of claim 1, wherein the shape recognition module recognizes a parametric transformation of a shape on one side of a rule in a target shape by searching the target shape for a parametric transformation of the subshape.

8. The shape interpreter of claim 7, wherein the shape recognition module recognizes a parametric transformation of a shape on one side of a 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 shape interpreter of claim 8 wherein the parametric transformations are based on the original curved line.

10. A system, comprising:

a shape interpreter for recognizing a first shape in a target shape, said interpreter comprising a shape decomposition module implemented as code stored on a computer readable medium 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 implemented as code stored on a computer readable medium in communication with the shape decomposition module; and

a rule application module implemented as code stored on a computer readable medium in communication with said shape interpreter, wherein the first shape is one side of a production system rule, said shape decomposition module for decomposing said first shape into at least one subshape belonging to one of a plurality of subshape groups.

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

12. The system of claim 10, wherein the shape recognition module recognizes a parametric transformation of the shape on one side of said production system rule in said target shape by searching said target shape for a parametric transformation of the subshape.

13. The system of claim 12, wherein the shape recognition module recognizes a parametric transformation of the shape on one side of the production system 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 system of claim 12, wherein the rule application module applies the production system rule by subtracting the parametric transformation of the shape on one side of the rule from said target shape and substituting therefore a transformation of a shape on the other side of the rule.

15. The system of claim 12, further comprising a rule selection module implemented as code stored on a computer readable medium in communication with the shape interpreter.

16. A shape interpreter, comprising:

means implemented as code stored on a computer readable medium for decomposing one side of a production system 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 implemented as code stored on a computer readable medium for recognizing a parametric transformation of one side of a production system 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 means for recognizing including means implemented as code stored on a computer readable medium 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 one side of a production system rule in a target shape, comprising:

using a computer to perform the steps of;

decomposing one side the production system 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 one side a production system rule in a target shape, comprising:

using a computer to perform the steps of;

searching the target shape for a parametric transformation of a first subshape, from a group of subshapes derived from one side of a production system 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 subshapes; 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 subshape 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 the other side of the production system rule to the target shape.

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

using a computer to perform the steps of;

decomposing the first shape into at least one subshape belonging to one of a plurality of subshape groups using a production system rule, 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.