back to ... Table of Contents Watch What I Do

NOTE: The images in this chapter could not be converted properly for use on the web


Example-Based Graphical Editing

David Kurlander


Human beings are great problem solvers, but find repetitive tasks tedious. In contrast, computers usually must be taught how to perform new tasks, but then they can quickly repeat the steps on new data. Given that a computer's strength lies in its ability to perform tasks repetitively, it is especially frustrating that many computer interfaces require the people using them to repeat interaction steps many times to achieve their desired goals. By building interfaces that can automate repeated interaction steps, we leverage off of the strengths of computers to make these goals easier to attain.

This paper explores several new techniques to automate repetition in user interfaces. Repetition in interfaces can be local to a particular session, or more global in scope and span multiple sessions and possibly multiple users as well. Tasks repeated in multiple sessions tend to be more general than tasks encountered in a single session. Accordingly, global repetition often results when the interface lacks a command to address a commonly useful function, while local repetition usually addresses a less general problem. The techniques to be discussed here address both types of repetition. By incorporating new techniques to automate repetition in an application, the application designer makes an application more extensible. Extensibility is important in that it enables users to customize applications for tasks that they often perform, making them more efficient. Experienced users, or those with a particular technical skill, can also encapsulate their knowledge in a form that others might invoke, thereby benefiting the entire user population.

The Domain: Graphical Editing

Since repetition in user interfaces is often application-specific, I have chosen to focus mainly on one particular domain: graphical editing. The techniques described here have been developed for a 2D object-based illustration system, similar to MacDraw and Adobe Illustrator, although some of these techniques apply to 3D editing and other domains as well. Graphical editors are an apt focus for this research, since they can be used for many different tasks, such as constructing technical illustrations, organizational charts, network diagrams, flow charts, and architectural drawings. Since these editors have a multitude of uses, there is a real need to allow individuals to customize the system for their particular tasks.

Graphical editing also involves different types of repetition, making it an interesting target for this work. Often it is helpful to make repetitive changes to the shape or graphical properties of a set of objects. Graphical editing tasks sometimes require that objects be laid out in a repetitive fashion. The same geometric relationships may have to be established several times in a single scene, or in multiple scenes. Certain geometric relationships may need to be re-established whenever an object is manipulated. Arbitrary object transformations or manipulations may need to be applied many times. The techniques described here facilitate these types of repetition.

An assortment of other reasons make graphical editing an ideal domain for this research. Since graphical editing is a common application, familiar to many people, the ideas presented here hopefully will be of wide interest, and potentially be quite useful. By choosing a domain with which other researchers have worked, I can compare and contrast my approaches with those of others. Graphical editing is just one of many tasks that involves placing artifacts on an electronic page. Other applications, such as page layout, interface editing, and VLSI design have this as a component as well, and the techniques described here are directly applicable to them. In fact, in Chimera these techniques can be used to construct interfaces as well as illustrations.

Example-Based Techniques

In all of the new techniques presented here, the user indicates a desired repetition, at least in part, by presenting an example. Hence, these methods are all example-based or demonstrational techniques, in which the user provides to the application an example of the desired task, and the application uses this specification to perform similar tasks on other examples.

Alternatively, the user could write a program to perform the desired repetition, but this has several disadvantages. First, it requires that the user know how to program, and many computer users lack this skill, particularly users of such basic, ubiquitous programs as graphical editors. Second, even if the user does have programming experience, they may be unfamiliar with the extension language or library interface of the editor. Third, the task of programming is very different from the tasks performed in applications such as graphical editors, and switching to a programming mindset requires a mental context switch.

In contrast, using demonstrational techniques is much closer to using the native application. Demonstrational techniques are accessible to anyone already possessing the skills to use the application's interface. Halbert, for example, describes one demonstrational technique, programming by example, as programming an application through its own interface (Chapter 5). Conventional programming skills are either not necessary or fewer are needed. Demonstrational interfaces also have the advantage that abstractions are specified using concrete examples, so those people that have difficulty working with abstractions will probably find these interfaces easier to use.

However, there are many possible abstractions or interpretations for a single concrete example, so there must be a way of resolving this ambiguity. Demonstrational systems often deal with this problem by using heuristics to choose the most likely mapping, or requiring that the user explicitly choose a particular mapping. Also since few demonstrational techniques are Turing equivalent, sometimes there are useful abstractions that cannot be specified using this approach. Programming is still the easiest way to specify many complex extensions, and will be so for the foreseeable future. However, there are many extensions that can be expressed without programming, and the goal here is to identify classes of these and develop new demonstrational techniques for expressing them.


To test the ideas contained in this chapter, I have built the Chimera editor system. Chimera is actually an editor framework or substrate, in which other editor modes are embedded. Three different editor modes are currently present in Chimera: modes for editing graphics, interfaces, and text. The methods presented in the next section have been implemented so that they work in both the graphics and interface modes. Both the graphics and interface modes of Chimera are very complete, and have extensive coverage of the primitives and commands one might want in such editors. The graphics mode of Chimera can create and manipulate boxes, circles, ellipses, lines, text, arcs, Bezier curves, freehand curves, beta splines, and cardinal splines (cyclic and non-cyclic). The interface mode can edit windows, command buttons, radio buttons (exclusive and non-exclusive), menus, checkboxes, horizontal and vertical sliders, application canvases, scroll bars, labels, scrolling lists, text controls, text editors, graphical editors, and mini-buffers. All of Chimera's interfaces were generated in Chimera. The graphics and interface editing modes each have around 180 commands (most of them shared).

The following sections introduce five new example-based techniques to automate repetition in graphical editor interactions. These techniques: graphical search and replace, constraint-based search and replace, constraints from multiple snapshots, editable graphical histories, and graphical macros by example, are briefly described, along with examples of their use. All figures were generated by the PostScript output of Chimera, and each figure depicting a demonstration of a technique was generated by the system running on a real example. A more detailed discussion of this material is presented elsewhere [Kurlander 93]. A videotape is also available, showing an interactive demonstration of these techniques in Chimera [Kurlander 92a].

Graphical Search and Replace

Often shapes are repeated many times in a single illustration. Similarly, many illustrations contain the same graphical properties, such as particular fill colors or line styles, repeated multiple times. When it becomes necessary to change one of these coherent properties, the task can be very tedious since these modifications will need to be made throughout the illustration. Graphical search and replace is a technique for automating tasks such as these. Users of text editors have long been familiar with the utility of textual search and replace, and graphical search and replace is intended to be its analogue in graphical editors.
Figure 1. A network diagram drawn in Chimera.

Figure 1 shows a simple diagram of a computer network consisting of 18 terminals, a magnetic tape device, a file server and a compute server. The network manager decides to replace all of the conventional terminals with workstations, and wants to update the diagram with as little effort as possible. One approach would be to delete each drawing of a terminal and replace it with a drawing of a workstation, but this would be repetitious. Since the artist did not group together all of the graphical primitives composing a terminal, and there is no pre-defined terminal object, this approach would be especially tedious. An alternative approach would be to use graphical search and replace.

Figure 2. MatchTool 2 window containing a search and replace specification that changes drawings of terminals to workstations.

Chimera's graphical search and replace utility is called MatchTool 2, and it appears in Figure 2. At the top of the window are two fully editable graphical canvases, in which objects can be drawn or copied. The left pane contains the search objects and the right pane contains the replacement objects. Unlike pure textual search and replace, there are many attributes of graphical objects that can participate in queries and be modified by replacements. For example, we might want to search only for objects of a particular object class or having a certain line width, and replace these attributes or others. Below the search and replace panes and to the left are rows of graphical attributes followed by checkboxes. The first column of checkboxes specifies which attributes of the objects in the search pane must be present in each match. During a replacement, the second column specifies which attributes of the objects in the replace pane will be applied to the match. Here we check nearly all the graphical attributes in the two columns since we want to match and replace all of these properties, and then press the ChangeAll button. Figure 3 shows the resulting scene.

Figure 3. The network diagram of Figure 1 after applying the graphical search and replace specification of Figure 2. All terminals are replaced by workstations.

Since the search and replace panes contain example objects as part of the specification, this technique is example-based. These objects represent large sets of potential matches and replacements, and the columns of checkboxes, which are explicitly set by the user, indicate how these objects are to be generalized for the search and replace specification. Note that these illustrations contain more repetition than the recurrence of terminals and workstations. The same fill color is used in many of the objects, and we could make the illustration darker or lighter with a few search and replace iterations. The drawers of the filing cabinet, the files in the middle drawer, the triangular holes in the reels of tape, and the button shapes on the tape recorder are all repeated shapes that can be altered easily using graphical search and replace. In fact, graphical search and replace proved useful here in increasing the diameter of all the polygons comprising the segments of the numeric LCD display, since they were too narrow in a preliminary drawing. As discussed in [Kurlander 88a], graphical search and replace is useful for a number of other applications, such as producing repetitive shapes generated by graphical grammars, filling out graphical templates, and searching for shapes in multiple files using a graphical grep utility.

Constraint-Based Search and Replace

Graphical search and replace, as presented in the last section, lacks an important capability: it can be used to find and alter the complete shape of an object, but not individual geometric relationships. If a search takes into account shape, every slope, angle, and distance is significant. Similarly, when a shape-based replacement is performed, the replacement receives its complete shape from the objects in the replace pane. However, sometimes it is useful to search for objects that match a few specific geometric relationships, and change some of these relationships. For example, we might want to look for lines that are nearly connected, and connect them. The angle between the lines is not significant for the search, nor are the lengths. We also might want to leave some geometric relationships unaltered, such as the positions of the remote endpoints of the lines. To perform tasks such as this, an extension of graphical search and replace, called constraint-based search and replace, is useful.

Constraint-based search and replace specifications can have constraints in the search and replace patterns. Constraints in the search pattern indicate which relationships must be present in each match, and those in the replacement pattern indicate which relationships are to be established in the match and which are to remain unaltered. For example, consider the aforementioned task of connecting nearly connected lines. The search and replace panes for this task are shown in Figure 4, and contain graphical objects and constraints as they are visually represented in Chimera. The search pane in Figure 4a contains two lines with endpoints connected by a 0 inch distance constraint. Note however that these endpoints do not obey this constraint. The tolerance of the search is provided by example--all pairs of lines that have endpoints at least this close will match the pattern. The search pattern graphically shows how far off objects can be from the specified relationships and still match.

The replacement pattern in Figure 4b contains two different kinds of constraints. The first constraint, the distance constraint that also appears in the search pane, indicates that the lines are to be connected together by the replacement. However there are two other constraints in the replace pane, marked by c*, that fix the remote vertices of the match at their original locations when performing this change. (a)


Figure 4. Constraint-based search and replace pattern to connect nearly connected lines. (a) the search pane; (b) the replace pane.

Figure 5 shows the result of applying this rule to a rough drawing of a W. All of the segments in Figure 5a are nearly connected, so they become precisely connected after the replacement, as shown in Figure 5b. Both graphical and constraint-based search and replace rules can be collected in rule sets and archived. Rules can be applied to a static scene, or can be expanded dynamically as the scene is drawn and edited. Constraint-based search and replace provides a means to establish particular geometric relationships repeatedly in a graphical scene. As is discussed in [Kurlander 92b], this technique can be used for a variety of scene transformations, including illustration beautification, but unlike other graphical editors capable of illustration beautification, Chimera allows beautification rules to be defined by the end user, without programming, using a demonstrational technique.


Figure 5. Application of the new rule. (a) a scene before the replacements; (b) the scene after the replacements.

Constraints from Multiple Snapshots


(b) As in the last example, constraint-based search and replace can be used to infer the intended presence of certain constraints in a static scene. Often static scenes do not contain enough information to infer all the desired geometric constraints. Since these constraints govern the way objects move in relation to one another, it is often easier to infer the presence of constraints by determining which relationships remain invariant as the scene objects move. Another new technique, constraints from multiple snapshots, does just that. Given several valid configurations or snapshots of a scene, this technique determines which constraints are satisfied in all of them, and instantiates these. The initial snapshot completely constrains the scene. Subsequent snapshots remove additional constraints from the constraint set. Geometric constraints make graphical editing easier by automatically maintaining desired geometric relationships between scene objects. However, it is often very difficult for people using graphical editors to figure out all of the useful constraints that need to be instantiated. This technique uses examples of valid scene configurations to automatically determine these constraints.

Figure 6. Two snapshots of a balance. (a) initial snapshot; (b) subsequent snapshot.

For example, Figure 6a shows a drawing of a balance. After completing this initial drawing, the user presses a button labeled "Snapshot", to indicate this illustration is a valid configuration of the scene. Next, the user rotates the arm of the balance on its axis, and translates each of the trays so that they are still connected to the arms, to produce the illustration shown in Figure 6b. The user presses the "Snapshot" button once more. The system calculates and instantiates constraints that are present in each snapshot. For example, the base remains fixed, the arm rotates about its axis, and the trays remain upright, and connected to the arm. Up until now, all of the constraints inferred by the system have been ignored during graphical editing, since constraint maintenance was turned off. The user turns on constraints, and moves one end of the balance's arm. The various components of the balance automatically reconfigure as shown in Figure 7, maintaining the inferred geometric relationships.

Figure 7. A third configuration of the balance, generated by the system, when one end of the arm is moved.

After providing a few snapshots and manipulating scene objects, the user may find that the system inferred unintended constraints that were present in all of the snapshots. If these unwanted constraints prevent scene objects from being moved into a desired configuration, the user can always turn off constraints, move the objects into this new configuration and take another snapshot. The new arrangement automatically becomes a valid configuration.

By inferring constraints from multiple snapshots, Chimera provides an alternative form of constraint specification to the traditional declarative method of explicitly instantiating all the constraints in an illustration. Further examples of this form of constraint inferencing, as well as the algorithm that Chimera uses to infer constraints from multiple snapshots, appear in [Kurlander 91]. Having constraints in an illustration makes it easier to repeatedly alter scene elements, when geometric relationships between the objects need to be maintained, so this technique, like the others discussed so far, addresses the problem of reducing repetition in graphical editing tasks.

Editable Graphical Histories

Another approach to reducing repetition in many applications is to save all of the operations as they are being performed and allow the user to select a set of these operations to reexecute or redo. There are several approaches to selecting the operations to be redone. Some applications limit redos to the last operation performed; others require that these operations be performed in a special recording mode. Other systems detect repetitions and automatically extract out the repeated elements themselves [Cypher 91]. Another approach is to provide an understandable history representation from which the user selects operation sequences to redo.

Textual command histories are easy to represent--the lines of text can be laid out one after another sequentially. However, histories of applications in a graphical user interface present a special challenge, since graphical properties such as colors and line styles must be represented in a user-understandable fashion, and geometric characteristics such as position become important to the interpretation of commands. Another of the techniques discussed here, editable graphical histories, is a representation for commands in a graphical user interface.

Figure 8. A simple graphical scene

Editable graphical histories use a comic strip metaphor to depict commands in a graphical user interface. Commands are distributed over a set of panels that show the graphical state of the interface changing over time. These histories use the same visual language as the interface, so users of the application should understand them with little difficulty. For example, consider the illustration of Figure 8 containing two boxes and an arrow. The history generated during its construction is shown in Figure 9. Though Figure 9 appears to include two history windows, the figure really shows two successive scrolls of a single window.

The first panel depicts grids being turned on from the editor control panel. The name of the command (Toggle-Grids) appears above the first panel, and the panel itself shows the checkbox that was toggled to invoke the command. The second panel shows a box created in the editor scene using the Add-Box command.

Figure 9. Editable graphical history that generated Figure 8.

In the third panel the box is selected, a color (yellow) is typed into the Text Input widget, and the Set-Fill-Color command is invoked. This panel is split to show parts of both the control panel and editor scene. The next panels show changes to the rectangle's stroke width and line color, a line being added beside the rectangle, and two lines being added above the first to create a hand drawn arrowhead. The scrolled window below shows in its four panels a box being added to the scene, the arrow being dragged to the box, the arrow being rotated so that its base aligns with the first box, and finally the arrow's base being stretched to reach the first box.

Several strategies are employed to make the histories shorter and easier to understand. Multiple related operations are coalesced in the same panel. For example, the third panel of Figure 9 contains two operations: one to select a scene object, and the other to change the fill color of selected objects. Each panel's label indicates the number of commands that it represents. We can expand high-level panels into lower-level ones and vice versa. This panel expands into the third and fourth panels of Figure 10. So that the history panels will be less cluttered, each panel shows only those objects that participate in its operations, plus nearby scene context. Objects in the panels are rendered in a style according to their role in the explanation. By default, Chimera subdues contextual objects by lightening their colors, and objects that participate in the operations appear normally. In the first panel, the grid checkbox and its label are important, and they stand out since all other control panel widgets are subdued.

Figure 10. The beginning of the history shown in Figure 9, with Figure 9's third panel expanded, and three panels selected for redo.

Editable graphical histories can be used to review the operations in a session, and to undo or redo a sequence of these operations. For example, we would like to apply to the upper rectangle the commands that set the fill color, stroke width, and line color of the lower one. We find the relevant panels in the history, and select them. In Figure 10, we have selected the fourth through sixth panels. The panel selections are indicated by white labels on a black background. We did not include the third panel depicting the selection of the original rectangle, since we want to apply these commands to a different object. After selecting the upper rectangle, we replay these commands verbatim by executing the Redo-Selected-Panels command, and the top rectangle changes appropriately.

Editable graphical histories reduce repetition in Chimera by forming an interface to a redo facility. Chimera also has a mechanism for inserting new commands at any point in the history, which reduces repetition in a subtler manner. The histories can be made editable, which replaces each static panel with a graphical editor canvas. The panels can be edited and a command invoked to propagate these changes into the history. To insert new commands in the middle of the history, the system undoes subsequent commands, executes the new commands, and redoes the old ones. Since redo is being performed, repetition is automated.

Figure 11. Operations added in place, in a history panel, to make a fancier arrow.

Figure 12. The scene of Figure 8, after the modifications described in this section.

As an example, we make the panels editable, and modify the last panel of the first row of Figure 9 to draw a fancier arrowhead and change the width of the arrow's base. The new panel is shown in Figure 11. We modify this history panel rather than the editor scene directly, since at this point in time the arrow is still aligned with the grid axes and later the change would be more difficult. Propagating these changes into the history results in the new scene shown in Figure 12. [Kurlander 90] contains a more detailed treatment of this history representation.

Graphical Macros by Example

The basic redo operation discussed in the last section is limited in that it can only play back commands verbatim. Command sequences executed in one application context often lack the generality to perform the same high-level function in others. The process of generating a procedure by demonstrating a task in an application is called programming by demonstration, and one of the major challenges involves generalizing the demonstrated commands to work in different contexts. Another challenge is in providing a visual representation of these programs. Chimera includes a programming by demonstration or macro by example component that uses editable graphical histories as its visual representation for reviewing, editing, and generalizing the program, as well as reporting errors.

Figure 13. Graphical history showing the creation of two rectangles, and the left-alignment of the top rectangle with the bottom one.

For example, consider an editing task in which we left-align two rectangles. The steps are captured in the graphical history of Figure 13. Initially we create the two rectangles (panels 1 and 2). Next we turn on 0 and 90 degree slope alignment lines (panels 3 and 4), and select the upper left corner of the bottom rectangle (panel 5) and lower right corner of the top rectangle (panel 6) to generate these lines. Finally we select the top rectangle, and drag it until it snaps to the appropriate intersection of two alignment lines (panel 7).

At some later time we realize that these operations are generally useful, and decide to encapsulate them in a macro. There is no need to repeat the operations in a special learning mode. We scroll through the history, find the relevant panels, and execute a command to turn them into a macro. Here we select all the panels, except those showing the Add-Box commands, since we want the boxes to be arguments to the macro. A macro builder window appears, containing the panels that were selected in the history window.

In the next step we choose the arguments of the macro. To do this we make the panels editable which allows objects in the panels to be selected. We select an instance of each argument, give it a name, and invoke the Make-Argument command. This appends argument declaration panels at the beginning of the history. Here we select the lower left rectangle from a panel, name it "fixed" since it doesn't move, and execute Make-Argument. We do the same for the other rectangle, but call it "moved" since this is the rectangle that was translated. Figure 14 shows the resulting macro builder window, with the argument declaration panels just created.

Figure 14. Macro builder window, containing a macro to left-align two rectangles.

Next we execute a command that chooses default generalizations of all the commands, according to built-in heuristics. Users can view and alter these generalizations. Finally we choose to invoke this macro on another set of rectangles. A macro invocation window appears that allows us to set and view the arguments. We test this macro on a sample scene, and it works as expected. Chapter 15 discusses the many ways that editable graphical histories support the macro definition process.


The techniques discussed in the last sections automate several different types of editor repetition, and though they may at first seem unrelated, they actually fit together in a coherent whole with synergistic relationships. Figure 15 is a graph with the five techniques represented as nodes, and edges that indicate which components are related to one another. The edges on the left show components that are currently related in Chimera, and those on the right show other relationships that might be established in the future.

Listed below are the existing relationships between the components:

Listed next are relationships that could potentially link the components:
Figure 15. Relationships between the five techniques. Edges on the left represent existing relationships, and those on the right potential relationships.

The relationships between the components are numerous, and interestingly Figure 15 would be a complete graph if it were not for the missing edge between graphical search and replace and constraints from multiple snapshots.


Steven Feiner advised me during this research and made many helpful suggestions. Eric Bier collaborated with me in developing graphical search and replace, and introduced me to the wonderful world of graphical editing. This research was partially funded by a grant from the IBM Watson Research Center.

Chimera -- MatchTool 2

Uses and Users

Application domain: Graphical editing and interface editing

Intended users: End users

User Interaction

How does the user create, execute and modify programs? MatchTool 2 automates repetitive search and replace tasks. The user draws (or copies) in the search pane an example of a valid match, and then draws (or copies) in the replace pane an example exhibiting the desired changes. By setting checkboxes, the user specifies which properties of the search and replace pane objects are significant. Additional parameters, such as scale and rotation invariance, can be set to further control the search and replace process.

The user can specify relevant geometric features and tolerances in the search and replace patterns by editing constraints (in the Chimera editor, objects can be described in terms of constraints).
The user can create multiple rules and make any subset of them active at a given time. An active rule fires automatically whenever an instance of its search pattern occurs.

Feedback about capabilities and inferences:
Search and replace patterns are defined and displayed graphically in MatchTool 2. The search and replace panes are instances of the Chimera editor, and can use its built-in constraint facility to present an iconic view of the constraints.


Inferencing: None. The user edits data descriptions, pictures and constraints.

Program constructs: Repeated search and replace rules.


Types and sources of information:
The types of constraints include distance, slope, angle, and others.


Machine, language, size, date:
Chimera runs on Sun Sparcstations, under the PostScript-based OpenWindows system. The code is a mix of Common Lisp, C, and PostScript. MatchTool 2 is 3K lines of commented Common Lisp (excluding the constraint solver). The initial graphical search tool was built in 1987. Constraints were added in 1991.

Notable Features

MatchTool 2 can be used to make repetitive changes to graphical properties, shapes, and geometric relationships. It can be used to create shapes defined by graphical grammars, and perform end-user-defined scene beautifications.

Chimera --
Constraints from multiple snapshots

Uses and Users

Application domain: Graphical editing and interface editing

Intended users: End users

User Interaction

How does the user create, execute and modify programs?
The user creates two or more pictures of a scene in different configurations, and takes "snapshots" of them. The system determines which geometric features of the objects remain the same throughout; these are inferred as constraints. When the user moves parts of the scene in the future, these constraints are invoked automatically. To eliminate a constraint, the user simply moves the part that was constrained and takes another snapshot. There is no need to add constraints, since the system remembers the relations that held true in all snapshots.

Feedback about capabilities and inferences: Inferred constraints can be displayed as icons attached to the affected parts, and their effects tested by manipulating objects with constraints turned on.


The system generalizes by dropping constraints that do not apply to all examples.

Types of examples: Uses multiple examples.


Types and sources of information:
The snapshot mechanism can infer all of the geometric constraints incorporated in Chimera, a set based on constraints that have proven useful in other editors. The inferences are based purely on the geometry of the scene, and do not depend on domain knowledge describing an illustration's semantics.


Machine, language, size, date:
Chimera runs on Sun Sparcstations, under the PostScript-based OpenWindows window system. The code is a mix of Common Lisp (25K lines), C (3K lines), and PostScript (2K lines). Of this, the code for inferring constraints from multiple snapshots is about 2K lines of Lisp code, and Chimera's other general constraint support is 2K lines of Lisp and 1.5K lines of C (these numbers include comments). 1990.

back to ... Table of Contents Watch What I Do