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
Tuesday, September 25, 2007
Online line simplification
Abam, de Berg, and Hachenberger. Streaming Algorithms for Line Simplification
The authors present a greedy algorithm that allows for the simplification of a polyline path to a simpler representative path on the fly, or as points along the path are being generated. The reasoning behind path simplification is a largely matter of storage space (not being able to store as many points as could be generated over long -- possibly infinite -- periods of time) rather then forming an idealized (or intentional) shape as usually seen in the sketch recognition setting. After discussing background information and previous approaches, they begin with the discussion of how their algorithm works. To begin, while the number of points does not exceed storage capacity, all points are stored. However, once the limit is exceeded their algorithm comes into play. Each point is stored in a priority queue with an associated error as the priority. The error assigned to a point is the error that would be generated by removing that point from the path (reducing a path p(i-1)p(i)p(i+1) to p(i-1)p(i+)). This error is measured in two way, Hausdorff error and Fréchet error, whose implementations are detailed towards the end of the paper. The errors are applicable to different types of paths, namely Hausdorff is only applicable to convex and xy-monotone paths. For arbitrary paths and the Fréchet error, they achieve a 4*sqrt(2)-competitive error with respect to an optimal offline algorithm (or at most 4*sqrt(2) time the optimal error).
This would be a novel concept to apply to the corner finding problem in sketch recognition, except for a problem, namely, in this method, the number of points (and therefore corners) is fixed a priori. One solution to this problem would be to use the set of points produced by this method as a set of candidate points similar to curvature points and speed points in Sezgin. This still runs into other problems, however. By limiting the number of points, we also limit the complexity of the figure, for example, choosing to remember only four points eliminates any figure with more than 3 segments. While extreme, this problem scales up, arbitrarily limiting user input. Though it seems unlikely that a user will require to be able to input drawings with 100 segments at a time, the possibility for such a sketch still exists. Additionally, if this set of points is used as candidate points in Sezgin, a quality metric must be assigned, possibly based on the Hausdorff and Fréchet errors, which could be feasible given the efficiency the authors assign to the error oracles.
The authors present a greedy algorithm that allows for the simplification of a polyline path to a simpler representative path on the fly, or as points along the path are being generated. The reasoning behind path simplification is a largely matter of storage space (not being able to store as many points as could be generated over long -- possibly infinite -- periods of time) rather then forming an idealized (or intentional) shape as usually seen in the sketch recognition setting. After discussing background information and previous approaches, they begin with the discussion of how their algorithm works. To begin, while the number of points does not exceed storage capacity, all points are stored. However, once the limit is exceeded their algorithm comes into play. Each point is stored in a priority queue with an associated error as the priority. The error assigned to a point is the error that would be generated by removing that point from the path (reducing a path p(i-1)p(i)p(i+1) to p(i-1)p(i+)). This error is measured in two way, Hausdorff error and Fréchet error, whose implementations are detailed towards the end of the paper. The errors are applicable to different types of paths, namely Hausdorff is only applicable to convex and xy-monotone paths. For arbitrary paths and the Fréchet error, they achieve a 4*sqrt(2)-competitive error with respect to an optimal offline algorithm (or at most 4*sqrt(2) time the optimal error).
This would be a novel concept to apply to the corner finding problem in sketch recognition, except for a problem, namely, in this method, the number of points (and therefore corners) is fixed a priori. One solution to this problem would be to use the set of points produced by this method as a set of candidate points similar to curvature points and speed points in Sezgin. This still runs into other problems, however. By limiting the number of points, we also limit the complexity of the figure, for example, choosing to remember only four points eliminates any figure with more than 3 segments. While extreme, this problem scales up, arbitrarily limiting user input. Though it seems unlikely that a user will require to be able to input drawings with 100 segments at a time, the possibility for such a sketch still exists. Additionally, if this set of points is used as candidate points in Sezgin, a quality metric must be assigned, possibly based on the Hausdorff and Fréchet errors, which could be feasible given the efficiency the authors assign to the error oracles.
Thursday, September 20, 2007
Curvature segmentation
Dae Hyun Kim and Myoung-Jun Kim, A curvature estimation for pen input segmentation in sketch-based modeling
Kim & Kim's paper takes somewhat of a middle ground between Sezgin and Yu. While Sezgin's paper relied equally on speed and curvature to detect the end of stroke subsegments, and Yu relied only on curvature, the Kims only uses speed at specific points to help aid the choice of curvature points. They also present two new methods for computing curvature. The first incorporates curvature of adjacent points to not only capture how curvy the line is a specific point, but also in the surrounding regions. To do this they simply sum up the curvature values over a window centered at the point in question if the values have the same sign as the curvature at that point. The second method imposes a monotonicity constraint on the window as well, considering only curvatures of the same sign with a smaller magnitude.
The speed-adaptive threshold is an interesting compromise between Sezgin and Yu, seemingly making it more likely that a curvature corner will be found at a lower speed. Broadening the window for which we examine curvature does seem improve the recognition of corners, but at the same time it may smooth out intentional, small changes in the stroke.
Kim & Kim's paper takes somewhat of a middle ground between Sezgin and Yu. While Sezgin's paper relied equally on speed and curvature to detect the end of stroke subsegments, and Yu relied only on curvature, the Kims only uses speed at specific points to help aid the choice of curvature points. They also present two new methods for computing curvature. The first incorporates curvature of adjacent points to not only capture how curvy the line is a specific point, but also in the surrounding regions. To do this they simply sum up the curvature values over a window centered at the point in question if the values have the same sign as the curvature at that point. The second method imposes a monotonicity constraint on the window as well, considering only curvatures of the same sign with a smaller magnitude.
The speed-adaptive threshold is an interesting compromise between Sezgin and Yu, seemingly making it more likely that a curvature corner will be found at a lower speed. Broadening the window for which we examine curvature does seem improve the recognition of corners, but at the same time it may smooth out intentional, small changes in the stroke.
Tuesday, September 18, 2007
Yu
Yu - A Domain-Independent System for Sketch Recognition
Yu's sketch system is very similar to Sezgin's. In both a sketch is segmented into lines and curves by finding perceived corners. Ideally, these corners match those that a human would perceive in an idealized version of the sketch, namely those corners that the human drawer intended are maintained and extraneous corners or jitter in the drawing are smoothed out. Like Sezgin, direction and curvature graphs are constructed; however, Yu does not use speed. Additionally, rather than choosing corners based on certainty metrics, Yu iteratively subdivides line segments a the highest point on the curvature graph to achieve a tighter fit. Yu begins by approximating the sketch as a single, horizontal line segment on either the direction graph (or actual sketch). If this approximation is close enough in a least-squares sense (under a threshold), the segment is accepted, while if not, the segment is subdivided at the maximal curvature point and each segment is fitted. Circles are fitted to a line on the direction graph whose slope is 2*PI/n (n=num of points on the segment). Overtraced circles are broken into multiple segments, and if they appear similarly shaped are replaced by a single "average" circle. Arc are represented by portions of circles. Yu also introduces a set of clean up rules that should help to fit the calculated shape to the intended one. This cleanup consists of deleting very small segments and merging segment that are similarly oriented and connect or overlap. As shown in Yu's examples, this can greatly reduce the number of corner and help achieve shapes that are much closer to the intended shape.
Yu's idea of adding corners that best improve the least squares accuracy of the sketch seems a much better idea than the metrics used by Sezgin. From the programming of Sezgin's algorithm on the class data, I'd frequently see that the best curvature point and the best speed point to add were often very close to each other. Due to this, initially one of the sets of points is largely ignored as the "best" point to add from it has been taken care of by a very close point in the other set, and other points that may improve the sketch neglected because they are good enough according to the metric. Usually this meant nearly all of the curvature and speed point needed to be added to the final fit to achieve a decent fit, severely overestimating the number of points. As clean-up method like Yu's could help alleviate this somewhat, but it seems that being able to skip those points and not add them at all would be more optimal
Yu's sketch system is very similar to Sezgin's. In both a sketch is segmented into lines and curves by finding perceived corners. Ideally, these corners match those that a human would perceive in an idealized version of the sketch, namely those corners that the human drawer intended are maintained and extraneous corners or jitter in the drawing are smoothed out. Like Sezgin, direction and curvature graphs are constructed; however, Yu does not use speed. Additionally, rather than choosing corners based on certainty metrics, Yu iteratively subdivides line segments a the highest point on the curvature graph to achieve a tighter fit. Yu begins by approximating the sketch as a single, horizontal line segment on either the direction graph (or actual sketch). If this approximation is close enough in a least-squares sense (under a threshold), the segment is accepted, while if not, the segment is subdivided at the maximal curvature point and each segment is fitted. Circles are fitted to a line on the direction graph whose slope is 2*PI/n (n=num of points on the segment). Overtraced circles are broken into multiple segments, and if they appear similarly shaped are replaced by a single "average" circle. Arc are represented by portions of circles. Yu also introduces a set of clean up rules that should help to fit the calculated shape to the intended one. This cleanup consists of deleting very small segments and merging segment that are similarly oriented and connect or overlap. As shown in Yu's examples, this can greatly reduce the number of corner and help achieve shapes that are much closer to the intended shape.
Yu's idea of adding corners that best improve the least squares accuracy of the sketch seems a much better idea than the metrics used by Sezgin. From the programming of Sezgin's algorithm on the class data, I'd frequently see that the best curvature point and the best speed point to add were often very close to each other. Due to this, initially one of the sets of points is largely ignored as the "best" point to add from it has been taken care of by a very close point in the other set, and other points that may improve the sketch neglected because they are good enough according to the metric. Usually this meant nearly all of the curvature and speed point needed to be added to the final fit to achieve a decent fit, severely overestimating the number of points. As clean-up method like Yu's could help alleviate this somewhat, but it seems that being able to skip those points and not add them at all would be more optimal
Sezgin
Metin Sezgin, Sketch Based Interfaces: Early Processing for Sketch Understanding
This'll get filled in as soon as I find the summary I wrote up.
This'll get filled in as soon as I find the summary I wrote up.
Subscribe to:
Posts (Atom)
