Parametric shape grammar interpreter

• US 20030152273A1
• Filed: 01/24/2003
• Published: 08/14/2003
• Est. Priority Date: 01/28/2000
• Status: Active Grant

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Cagan, Jonathan, McCormack, Jay P.
• Granted Patent: US 7,415,156 B2
• Time in Patent Office: Days
• 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 method, comprising:

decomposing a first shape into at least one subshape;

identifying instances of said at least one subshape in a target shape; and

determining if said first shape is present in said target shape based on said identifying.

2. The method of claim 1 additionally comprising defining an equivalent straight line shape for each curved line in said first shape before decomposing said first shape.

3. The method of claim 2 additionally comprising, for any identified instances of a subshape corresponding to an equivalent straight line shape, confirming said identified instances with said curved line.

4. The method of claim 3 wherein said decomposing includes decomposing said first shape into a plurality of subshapes, said plurality of subshapes being arranged hierarchically according to constraints.

5. The method of claim 4 wherein said identifying is performed iteratively using said plurality of subshapes, beginning with a subshape having the most constraints, and ending when either instances of all of said plurality of subshapes have been identified in said target shape or no instances of one of said plurality of subshapes have been identified in said target.

6. The method of claim 5 additionally comprising applying a rule to said target shape based on said determining.

7. A method, comprising:

defining an equivalent straight line shape for each curved line in a first shape;

decomposing said first shape into at least one subshape;

identifying instances of parametric transformations of said at least one subshape in a target shape;

comparing any instances of a subshape corresponding to a straight line shape found in said target shape to said curved line; and

determining if said first shape is present in said target shape based on said identifying and said comparing.

8. The method of claim 7 wherein said decomposing includes decomposing said first shape into a plurality of subshapes, said plurality of subshapes being arranged hierarchically according to constraints.

9. The method of claim 8 wherein said identifying and comparing are performed iteratively using said plurality of subshapes, beginning with a subshape having the most constraints, and ending when either instances of all of said plurality of subshapes have been identified in said target shape or no instances of one of said plurality of subshapes have been identified in said target.

10. The method of claim 9 additionally comprising applying a rule to said target shape based on said determining.

11. A memory device carrying a set of instructions which, when performed, execute a method comprising:

decomposing a first shape into at least one subshape;

identifying instances of said at least one subshape in a target shape; and

determining if said first shape is present in said target shape based on said identifying.

12. A memory device carrying a set of instructions which, when performed, execute a method comprising:

defining an equivalent straight line shape for each curved line in a first shape;

decomposing said first shape into at least one subshape;

identifying instances of parametric transformations of said at least one subshape in a target shape;

comparing any instances of a subshape corresponding to a straight line shape found in said target shape to said curved line; and

determining if said first shape is present in said target shape based on said identifying and said comparing.

13. An apparatus, comprising:

means for decomposing a first shape into at least one subshape;

means for identifying instances of said at least one subshape in a target shape; and

means for determining if said first shape is present in said target shape in response to said means for identifying.

14. An apparatus, comprising:

means for defining an equivalent straight line shape for each curved line in a first shape;

means for decomposing said first shape into at least one subshape;

means for identifying instances of parametric transformations of said at least one subshape in a target shape;

means for comparing any instances of a subshape corresponding to a straight line shape found in said target shape to said curved line; and

means for determining if said first shape is present in said target shape in response to said means for identifying and said means for comparing.