Interactive Learning of Structural Shape Descriptions from Automatically Generated Near-miss Examples - Hammond and Davis
Summary
The authors present an extension of the previous version of LADDER, focusing on the refinement of constraints to ensure the shapes described are not overly specific or too general. Two types of constraint errors are considered, inclusion of an extraneous constraint and omission of a required constraint. More complex errors, such as substitution, are treated as a combination of both basic error types. Shape descriptions can be generated in two ways. The first is user description, in which the user inputs directly the constraints for a given shape. LADDER provides online debugging tools through auto-completion and marking syntax errors in red. Next, a sketch corresponding to the shape must be drawn, and if the sketch does not meet the constraints, it is assigned to the shape for which it fails the least constraints. Alternately, the constraints may be automatically generated by drawing the shape and allowing LADDER to generate all constraints seen in the sketch and heuristically pruning the constraints. Next, the shape description is examined for over-constraint. For each constraint a near miss is generated in which that constraint is false while all others hold. If the user believes the near miss represents the same shape concept, the constraint is overly specific and is deleted. Next, under-constraint is examined. Additional potential constraints are generated similarly to the generation of all possible constraints for automatic description generation, and are filtered to omit those that are directly derivable from the current set of constraints. To test if a constraint should be added, its negation is added to the constraint list and a sketch is generated. If the sketch is representative of the shape concept, the new constraint is not added as it would over constrain the description, while if the sketch is rejected the constraint is added as descriptive of the concept. For both methods, example sketches are generated by converting the set of constraints to a set of equations (along with some general rules about shapes) and the set of equations is minimized. In this equation, required constraints and optimal constraints are distinguished by weighting. Required constraints are those that must be true to be considered representative of a shape concept, while optimal are not necessarily true. If the minimization process fails or reports a high error, the shape is considered impossible and eliminated.
Tuesday, October 9, 2007
Monday, October 1, 2007
Ladder
LADDER, a sketching language for user interface developers - Hammond and Davis
Summary
LADDER is a system that allows the specification of domain specific sketch recognition systems. Users begin by defining basic shapes. Each shape consists of a set of components, geometrics constraints on those components, component aliases, editing methods, and how the components are drawn. Shapes are defined hierarchically, beginning at the lowest level with predefined shapes such as line, circle, etc. Much like object oriented languages, abstract shapes can be defined forcing shapes that inherit from them to contain certain components or methods. Shape groups can also be defined, allowing for changes to one shape in the group to be reflected in all shapes in the group. The system provides not only a set of primitive shapes but also defines two sets of constraints. The first, consisting of constraints such as parallel, meet, etc., is rotation invariant, while the second (vertical, horizontal, etc.) is not. Several predefined editing methods and display methods, such as delete, rotate, or translate and original or cleaned strokes, are also defined. Users may also define a shape to contain a vector of subshapes, should a large or unknown number of these type of shapes be needed. Lowest level, predefined shapes are recognized in a domain independent manner and are added as facts to a Jess-based rule system whose rule are translated from the shape definition. As low level shapes are added as facts, the Jess system attempts to combine the shape with all others to generate a higher level shape. Once a high level shape has been fixed, its components are removed from the list of facts. If idealized representation is desired, the set of constraints associated with the shapes is solved via Mathematica.
Summary
LADDER is a system that allows the specification of domain specific sketch recognition systems. Users begin by defining basic shapes. Each shape consists of a set of components, geometrics constraints on those components, component aliases, editing methods, and how the components are drawn. Shapes are defined hierarchically, beginning at the lowest level with predefined shapes such as line, circle, etc. Much like object oriented languages, abstract shapes can be defined forcing shapes that inherit from them to contain certain components or methods. Shape groups can also be defined, allowing for changes to one shape in the group to be reflected in all shapes in the group. The system provides not only a set of primitive shapes but also defines two sets of constraints. The first, consisting of constraints such as parallel, meet, etc., is rotation invariant, while the second (vertical, horizontal, etc.) is not. Several predefined editing methods and display methods, such as delete, rotate, or translate and original or cleaned strokes, are also defined. Users may also define a shape to contain a vector of subshapes, should a large or unknown number of these type of shapes be needed. Lowest level, predefined shapes are recognized in a domain independent manner and are added as facts to a Jess-based rule system whose rule are translated from the shape definition. As low level shapes are added as facts, the Jess system attempts to combine the shape with all others to generate a higher level shape. Once a high level shape has been fixed, its components are removed from the list of facts. If idealized representation is desired, the set of constraints associated with the shapes is solved via Mathematica.
Paulson
Recognizing and Beautifying Low-level Sketch Shapes with Two New Features and Ranking Algorithm - Paulson and Hammond
Summary
Paulson has developed a new low level shape recognizer supplemented by two novel features. The first is normalized distance between direction extremes (NDDE), the distance between the point with the highest direction and the lowest direction divided by total stroke length. Next is direction change ratio (DCR), which is the maximum change in direction divided by the average change in direction. Both are used to determine the spikiness of the direction graph. Both, along with direction, curvature, and speed graphs and corners, are computed during the "pre-recognition" phase of the recognizer. Next, a series of tests determine if the sketch can be classified as one of several primitives. These are Line, Poly-line, Circle, Arc, Curve, Ellipse, Spiral, and Helix. Additionally, a stroke may be classified as a Complex figure. If classified as Complex, the stroke is subdivided into subsegments until each subsegment can be classified as under one of the low level shapes. Complex, Poly-line, and Curve classes are further distinguished by a ranking system. Each subsegment is assigned a weight associated with the complexity of the assigned shape. The weights are summed over the stroke and the interpretation with the lowest score wins. Next low level shapes are hierarchically added to an interpretation.
Discussion
Summary
Paulson has developed a new low level shape recognizer supplemented by two novel features. The first is normalized distance between direction extremes (NDDE), the distance between the point with the highest direction and the lowest direction divided by total stroke length. Next is direction change ratio (DCR), which is the maximum change in direction divided by the average change in direction. Both are used to determine the spikiness of the direction graph. Both, along with direction, curvature, and speed graphs and corners, are computed during the "pre-recognition" phase of the recognizer. Next, a series of tests determine if the sketch can be classified as one of several primitives. These are Line, Poly-line, Circle, Arc, Curve, Ellipse, Spiral, and Helix. Additionally, a stroke may be classified as a Complex figure. If classified as Complex, the stroke is subdivided into subsegments until each subsegment can be classified as under one of the low level shapes. Complex, Poly-line, and Curve classes are further distinguished by a ranking system. Each subsegment is assigned a weight associated with the complexity of the assigned shape. The weights are summed over the stroke and the interpretation with the lowest score wins. Next low level shapes are hierarchically added to an interpretation.
Discussion
Subscribe to:
Posts (Atom)
