Open-Domain Sketch Understanding: The nuSketch Approach.

Sketching is often used when working out ideas. This combination of drawing and conceptual labeling is a very natural and effective form of communication and problemsolving. Creating software that can participate in sketching provides many challenges. We outline the nuSketch approach to sketch understanding, which focuses on visual and conceptual understanding instead of recognition. We summarize three experiments in progress with the sketching Knowledge Entry Associate (sKEA), the first open-domain sketch understanding system. sKEA exploits a variety of visual and qualitative spatial reasoning capabilities and human-like analogical matching to tackle a variety of tasks. We present experimental results, and outline future plans. The nuSketch approach Sketching is a form of multimodal interaction where participants use a combination of interactive drawing and language to provide high-bandwidth communication. This communication relies on shared understanding, both visual and conceptual. Multimodal interface research has mainly focused on providing more natural interfaces to legacy software, using recognition technologies to provide the desired interaction (Alvarado and Davis 2001, Cohen et al. 1997). While such systems have been shown to be quite useful in practice, we take a radically different approach. The nuSketch approach is based on a key observation about human-to-human sketching: Recognition is not essential. People are not artists in real time; they rely on language for conceptual labeling much of the time. While some specialized domains have visual symbol languages that practitioners use fluently, sketching is used far more broadly than that. In other words, for people, recognition is an accelerant, not a necessity. This suggests a very different approach to sketch understanding that complements recognition-oriented research. In the nuSketch approach, we sidestep recognition issues by providing other interface mechanisms for people to conceptually label their ink. This provides two crucial advantages. First, it enables us to focus on deeper visual and conceptual understanding of sketches. Second, it enables us to build sketching systems that can operate outside the tight domain constraints that bind today’s recognition-based systems. In particular, the sketching Knowledge Entry Associate (sKEA) (Forbus and Usher 2002) is, we believe, the first open-domain sketch understanding system. sKEA’s only coverage limitation comes from the underlying knowledge base it uses – currently a subset of Cyc, consisting of over 35,000 concepts, constrained by 1.2M facts. This does not mean that we can effectively reason with all of these concepts in sketches yet – that is the nature of the challenge we have undertaken! The nuSketch Architecture and sKEA In the nuSketch architecture, the basic unit in a sketch is a glyph. Every glyph has ink and content. The ink consists of one or more poly-lines, representing what the user drew. The content is a conceptual entity, the kind of thing that the glyph is representing. There are two key problems that any sketching system must solve: 1. Segmentation. What pieces of ink should be considered together as glyphs? 2. Conceptual Labeling. What conceptual entity does a glyph denote? We solve the segmentation problem by having the user click a button when they begin drawing a glyph and click it again when they are finished. Other segmentation techniques, such as time-outs and connectivity, are in our experience very frustrating for users and error-prone. We solve the conceptual labeling problem by enabling the content of a glyph to be declared, via a simple dialog, as one or more types drawn from the underlying knowledge base. This requires users to be familiar with the subset of the knowledge base that they need in their task, which is a strong limitation with the current version of the system. (We return to this issue at the end.) The nuSketch architecture uses a variety of geometric computations to visually construct qualitative representations, including RCC8 relations (Cohen 1996), Voronoi diagrams (Edwards and Moulin 1998) for approximating proximity, and polygon operations to capture domain constraints. A central feature of nuSketch is our use of analogical processing, based on Gentner’s structure-mapping theory (Gentner 1983). Analogy provides a powerful means of entering and testing knowledge. Currently sKEA enables users to compare two layers of a sketch, which enables the detection of similarities and differences. We use the Structure-Mapping Engine (SME) (Falkenhainer, Forbus and Gentner 1989) to perform the comparisons. SME is a general-purpose analogical matcher. sKEA’s analogies are based on both the visual and the conceptual material in a sketch. Some of our experiments also take advantage of the MAC/FAC system (Forbus, Gentner and Law 1994) which does a coarse matching using content vectors and then uses SME to narrow the results. SME produces candidate inferences, conjectures about one description based on its alignment with another. Candidate inferences are useful in knowledge capture because they suggest ways to flesh out a description based on similarities with prior knowledge. Since there is independent psychological evidence that structural alignment occurs in visual processing, and that SME captures many aspects of this processing accurately, it means that when our sense of similarity and our software’s sense of similarity about a sketch diverge, it is a sign that our representations have failed to capture something crucial about the sketch. This provides a powerful constraint that drives the visual and conceptual representations we compute. Even if one does not care about modeling human performance, a sketching system will be a better partner if you and it agree on when things look alike. Spatial Processing in nuSketch and sKEA While we do not use recognition techniques on our sketches, we do compute some simple spatial properties of the ink (Forbus and Usher 2002). We focus on the spatial relationships between the glyphs rather than doing detailed analysis of the structure of the glyphs themselves; we call this approach blob semantics. When a glyph is added, moved, or resized, sKEA computes a set of spatial attributes and relationships. This process is described in detail in (Forbus, Tomai, and Usher 2003). The spatial attributes and relationships that make up the visual structure of the sketch are: groupings, positional relationships, size, and orientation. sKEA automatically computes two kinds of groupings: contained glyph groups and connected glyph groups. A contained group consists of a single container glyph and the set of glyphs that are fully contained within it, possibly tangentially so. The contained group does not include glyphs that are contained within other glyphs in the group. A connected glyph group consists of a set of glyphs that overlap ink strokes with one another. Articulation points can be computed over connected glyph groups and tangentially connected pairs of glyphs can be noted as such. Positional relationships are computed pair-wise and expressed in a viewer-oriented coordinate system of left/right and above/below. They are not computed between all pairs of glyphs, but rather in local neighborhoods based on adjacency, as determined via a Voronoi diagram. Positional relationships are computed only between glyphs on the same layer of a sketch. Glyph size in sKEA is assigned as either tiny, small, medium, large or huge. Sizes are based on the area of a glyph’s axis-aligned bounding box, a coarse but empirically useful approximation. Glyph areas are normalized with respect to either the area of the bounding box around all glyphs on all layers or the users view port, whichever is larger. The normalized areas are then clustered into qualitative size values based on a logarithmic scale of the square root of the area. Additional Spatial Reasoning As part of our ongoing research we are developing more spatial reasoning capabilities to accomplish different research goals. Currently we are working on adding the ability to articulate the “important” points and segments on different objects as well as to more specifically define the relationship between adjacent glyphs. Another area where we need to expand our available spatial reasoning abilities is curvature. We are working on different techniques to qualitative summarize degree of curvature.