Early Processing for Sketch Understanding

-Sezgin, Stahovich

COMMENTS

SUMMARY

The algorithm described in this paper uses both speed and curvature data to detect corners in a stroke. The underlying idea of using speed is that at corners stroke speed reaches a local minima. Thus corners are typically located where curvature reaches a maximum and speed reaches a minimum. The author uses a technique called average based filtering to eliminate any false positives. Only those extrema are considered where speed and curvature data lie beyond a threshold. False positives are also tackled with hybrid generation scheme. Hybrid generation occurs in three steps - computing vertex certainties, generating a set of hybrid fits and selecting the best fit. The initial fit is the intersection of the corners generated by speed and curvature data. The error is computed as an average of sum of squares of the distances to the fit from each point in the stroke. Additional fits are generated by adding highest scoring (least error) curvature and speed candiates not already in the fit. The algorithm can also be used to produce a fit for curved portion of the stroke. If the ratio of total path distance and euclidean distance between two points is significantly higher than one, that indicates a curved stroke segemnt between these points. Curves are approximated using Bezier curves using two end points and two control points. The approximation and identification of the shapes was correct 96% of the time when tested with ten figures.

DISCUSSION

The algorithm serves as benchmark beacuse it first introduced the idea of using speed data to find corners. The use of Bezier curve approximation makes it very powerful, since it can handle both linear and curved segments of the stroke. However, the accuracy (which ignores false positives) might be a point of contention.