Bibliography:
Sezgin, Tevfik Metin, Thomas Stahovich, and Randall Davis. "Sketch based interfaces: early processing for sketch understanding." ACM SIGGRAPH 2006 Courses. ACM, 2006.
Link:
http://dl.acm.org/citation.cfm?id=1185783
Summary:
In this paper the authors present a system designed to be a natural sketch interface for the design of mechanical-engineering drawings. It was designed to recognize what is drawn instead of how something is drawn.
The system follows three steps to create its drawings: approximation, beautification, and basic recognition of the stroke.
To approximate strokes it tries to detect the vertices of the shape. This is done by doing some preprocessing of the stroke. The direction, curvature, and speed graphs of the stroke are computed and used to determine the which points are vertices. Vertices are usually found at the peaks of high curvature. It has also been observed that users slow down at corners, which is signified by valleys in the speed graph. To factor out the noise from the stroke, peaks and valleys are only considered if above/below a certain threshold. These where empirically found to be the mean of curvature graph and %90 of the mean of the speed graph. The mean is used so that the threshold is dependent on the graph data instead of it being a global value. The threshold splits the graph into regions and the extrema are chosen from the satisfying regions.
Usually taking only curvature into consideration is insufficient, and both speed and curvature are taken into account. The certainty that points are vertices are calculated by find the scaled magnitude of curvature in a neighborhood for those found in the curvature graph and the ratio of speed from the speed graph. The initial hybrid fit is the intersection of points that are both peaks and valleys in the curvature and speed graphs respectively. Subsequent hybrid fits are made by adding the next best speed and curvature fits. The error of the fit by finding the orthogonal squared distance error of the stroke to the fit. Points are added until an error threshold is reached and the best fit with the least number of vertices is chosen.
Curves are found by calculating the ratio of arc length between vertices to the euclidean distance between vertices with those with a high enough ration being deemed curves. Arcs are approximated with Bezier curves that are approximated by linear segments. It is subdivided until the squared distance error is below some threshold.
Beautification is done by rotating line segments around their midpoints when they are 'supposed to be linear,' to match nearby segments. This is done by comparing segments to others within a window.
Finally basic recognition is done by testing distance to its bounding box for squares and squared distance error measures for fitted ellipses.
A high level recognizer was implemented to recognize domain specific shapes. Also over-tracing was addressed.
It seems as though how something is drawn, slowing down before taking corners, can still aid in recognition. Also comparing the arc length and euclidian distance for finding corners is very similar to that of Short Straw's.
I wonder what other behavioral features can used to recognize sketches.
Usually taking only curvature into consideration is insufficient, and both speed and curvature are taken into account. The certainty that points are vertices are calculated by find the scaled magnitude of curvature in a neighborhood for those found in the curvature graph and the ratio of speed from the speed graph. The initial hybrid fit is the intersection of points that are both peaks and valleys in the curvature and speed graphs respectively. Subsequent hybrid fits are made by adding the next best speed and curvature fits. The error of the fit by finding the orthogonal squared distance error of the stroke to the fit. Points are added until an error threshold is reached and the best fit with the least number of vertices is chosen.
Curves are found by calculating the ratio of arc length between vertices to the euclidean distance between vertices with those with a high enough ration being deemed curves. Arcs are approximated with Bezier curves that are approximated by linear segments. It is subdivided until the squared distance error is below some threshold.
Beautification is done by rotating line segments around their midpoints when they are 'supposed to be linear,' to match nearby segments. This is done by comparing segments to others within a window.
Finally basic recognition is done by testing distance to its bounding box for squares and squared distance error measures for fitted ellipses.
A high level recognizer was implemented to recognize domain specific shapes. Also over-tracing was addressed.
Comments:
It seems as though how something is drawn, slowing down before taking corners, can still aid in recognition. Also comparing the arc length and euclidian distance for finding corners is very similar to that of Short Straw's.
Research Ideas:
I wonder what other behavioral features can used to recognize sketches.
In my opinion, combining these with other features could bring out the best performance.
ReplyDelete