"Recognizing Free-form Hand-sketched Constraint Network Diagrams by Combining Geometry and Context"

by Tracy Hammond, Barry O’Sullivan

Summary

Constraint programming can be divided very crudely into modeling and solving. Modeling defines the problem: which variables are involved, and what constraints on them. Solving finds values for all the variables that simultaneously satisfy all the constraints. While solving can seek to embedded algorithms, libraries, and programming languages, bottleneck exists in modelling phase. This paper tries to solve this bottleneck by providing a free-hand sketching system.

The system uses geometric-based to allow free-form drawing. It is built using LADDER, and the user interface is generated by GUILD. In a modelling graph of a constraint problem graph, nodes are CSP variables and edges between variables represent constraints. The set of possible values (domain) each variable can take is specified by writing a set adjacent to a node. The constraint between two variables is specified by giving a direction on an edge and a relation adjacent to the edge. Text can be enterred by handwriting, typing, or variable names (t, v, w , x, y, z) handwritten directly onto the diagram. Then the corresponding constraint satisfaction model is automatically generated.

Nodes are recognized as ellipses that contain a variable name within them. An undirected link is recognized geometrically as a line. Directed links are recognized as an arrow that extends between two nodes. Other shapes are variable name, variables: T, V, W, X, Y, Z, and constraints: less than, equal, not equal.

Shapes appear to be similar (less than, V, W, arrow head) are distinguished in context. Two lines in each direction (partners) are added in the system to allow flexible drawing order, for example, arrow head coincide with either end of the shaft will be recognized as an arrow. And to keep recognition response times short, as soon as shapes are recognized, their properties are computed and placed into a hash-table. Thresholds are determined by combining absolute (within 10 pixels), relative (5% of stroke length), and perceptual ("coincididence": closer to the endpoint than to the midpoint) rules to give a more accurate representation of the
error.

Accuracy was 100% but (1) UI for drawing gives feedback if shapes are drawn wrong, (2) testing graphs are drawn by designer of the system.


Discussion

This is an application of LADDER in a specific domain. The benefit of sketch recognition system over paper-based drawing is evident in that the sketch can be automatically converted to the model.