Inferring Shape and Structure from Design Drawings
Patrick W. Yaner and Ashok K. Goel
Abstract: We describe a method for constructing a structural model of an unlabelled 2D line drawing by analogy to a known model of a drawing with similar structure. The source case is represented as a schema that contains its line drawing and its structural model represented at multiple levels of abstraction: the lines and intersections in the drawing, the shapes, the structural components and connections of the device depicted in the drawing. Given a target drawing and a relevant source case, our method of compositional analogy first constructs a representation of the lines and the intersections in the target drawing, then uses the mappings at the level of line intersections to transfer the shape representations from the source case to the target, next uses the mappings at the level of shapes to transfer the full structural model of the depicted system from the source to the target.
Visual media can be of great importance for designers, and so for example understanding a new design often means understanding a drawing. In artificial intelligence, this implies that knowledge acquisition in computer-aided design can productively occur using drawings as the knowledge source. However, for this to occur requires machines that are able to interpret drawings of designs.
In this work we view the task of interpreting drawings as one of constructing a model of what the drawing depicts: the model enables higher-level (i.e. non-visual) inferences regarding the depicted content of the drawing (see Glasgow, Narayanan, and Chandrasekaran, 1995, for different perspectives on diagram understanding). For example, in the context of CAD environments, the input to the task may be an un-annotated 2D line drawing depicting a kinematics device, and the output might then be a structural model of the device—i.e. a specification of the configuration and properties of the components and their structural relations. Current methods for extracting a model from a drawing (Alvarado & Davis, 2005; Ferguson & Forbus, 2000) rely on domain-specific rules. I propose to infer a model by analogy to a similar drawing whose model is known.
This theory is implemented in a program called Archytas. This program reads in a 2D un-labeled drawing and, given the source drawing and associated teleological model, attempts to infer by analogy (1) a representation of the shapes and spatial relations in the target drawing and (2) a representation of the structural components and interconnections of the device depicted in the drawing. This method of compositional analogy works iteratively to successively higher levels of abstraction, interleaving mapping and transfer at various levels to construct a new structural model.
Analogy-based comprehension is often presented as the problem of analogical mapping (e.g., Falkenhainer, Forbus, & Gentner, 1990; Holyoak & Thagard, 1989) and specifically that of structural alignment (where “structure” in this context means that of the representation itself—i.e. relational similarity as opposed to similarity of features). Certainly the transfer of some knowledge from source to target is always the goal of analogical inference, but when analogy is treated as structural alignment the tendency is to regard an analogy as an alignment or mapping In this work we will see that the use of multiple levels of abstraction and aggregation requires a change in this view, and in particular a whole mapping at one level can become a single match hypothesis (in SME’s terminology) at the next level. The role of mappings with respect to transfer thus changes when we consider working at several levels of abstraction all at once.
Let us consider the task of mapping the source drawing illustrated in figure 1(a) to the similar target drawing illustrated in figure 1(b). If we treat the problem as one of first recognizing the geometric elements and spatial relations among them, then we can treat this representation as a labeled graph: A contains B, C is adjacent to D, and so on. A graph-theoretic method for analogy-based recognition may then be used to find a consistent mapping between the graphs representing the source and target drawings. However, the method runs into difficulty for the target drawing shown in figure 1(c) or (d) with figure 1(a) as the source drawing. In this problem, the numberof components, and thus the number of shapes, is different, and either the graph-theoretic method would have to relax the constraint of one-to-one mapping, or else the analogy would have to be performed twice in order to transfer a model successfully from figure 1(a) to figure 1(c) or (d). Figure 2 illustrates a similar example from the domain of door latches.
[Figure 1 about here]
[Figure 2 about here]
To address the above difficulties, our method of compositional analogy performs analogy at multiple levels of abstraction. The analogical mapping and transfer at these levels is enabled by organizing knowledge of the source case at multiple levels. Figure 3 illustrates the knowledge organization in a source case. The structure, shape, and drawing in a source case form an abstraction hierarchy, where structure is a specification of components and structural relations along with properties (height, width, etc.) and variable parameters (e.g. position or angle of moving components). These models are based on the structural portion of so-called Structure-Behavior-Function (SBF) models (Goel & Chandrasekaran, 1989; Goel, 1991).
[Figure 3 about here]
Our method of compositional analogy first constructs a representation of individual lines and circles and intersection points in the target drawing, and then analogically infers shapes over this representation by grouping multiple symmetric mappings at the level of lines and intersections. Using these groups it infers shape patterns in the target and sets up a mapping at the level of whole shapes. This shape-level mapping then informs the transfer of structural elements from source to target, resulting in a full structural model for the depicted device in the target drawing as well as a component-level mapping of the source model onto this target model.