A Domain-Independent System for Sketch Recognition

In this paper, Yu and Cai, discuss their system which was designed with the following goals:

• Naturalness
• It must allow users to draw in a natural way just as how they do on paper.
• Consistency
• It should produce a consistent recognition result,
• i.e. if a user wants to sketch a line segment, no matter if it is drawn with a single stroke, or more than one stroke, or a compound stroke which contains other primitive elements, the system should interpret it as a line segment.
• Hierarchical Composition 
• It should understand the hierarchical relations among the recognized graphic objects. 
• For example, a stroke which is composed of several primitive shapes may serve as a constituent part of some more complex object.
• Beautification
• It should try to guess what the user intends to draw and turn the imprecise strokes into regular objects. 
• Although domain-specific knowledge may be very helpful here, some simple decisions can still be made according to low-level geometric features only.
• Editing Support
• Besides a fairly high recognition rate, it should provide an efficient and convenient user interface for drawing modification as well.
• Modularity
• It can be easily integrated as in input module into other more complex systems.

Their system was divided into two stages:

1. Imprecise Stroke Approximation

• Vertex Detection and Primitive Recognition
• Procedure: For every stroke,  check to stroke to see if primitive. Stop if it is, else cut the stroke at the point of highest curvature (corners) and perform primitive check on these two strokes. (recursive)

• Primitive Detection: Lines, Curves, Circles, Ellipses, Squares, Spiral (referred to as 'helixes' in the paper)
• Discussed Topics
• Line Segment Approximation
• Computes the least-squares best fit line for the direction curve or coordinates of points of the stroke and whether the number of deviation points is "small" with a threshold. If it is, then guess line segment and verify with feature area verification, else, delay classification.
• "Feature Area Verification" - checks the ratios between feature and standard area; Serves as a constraint to local criteria for line segment recognition on strokes that are based on direction and curvature information.
• Curve Approximation
• Do circle and ellipse approximation
• Circle: check if direction curve can be approximated with a line with a slope of 2pi / n. If so, guess circle with center as the bounding box center and mean distance from center as the radius. Verify with feature area verification.
• Overtracing is handled by breaking each 2pi revolution of the direction graph into separate circles and combining them by taking the mean features of the circles.
• Ellipse: "similar to circle" with extra constraint : area is symmetrical about major and minor ellipses.
• A dubious claim, according to Dr. Hammond
• Arc Stroke: Direction curve is approximated by line with slope *less than* 2pi / n.
• Self-Intersecting Stroke Handling
• If stroke can't be broken down into primitives and it has intersecting lines, make two copies of the stroke and divide them using two strategies:
1. At self intersection points
2. At points of maximum curvature
• Choose the one with the "better" recognition 

2. Post Processing

• Eliminates elements made by noise in data, beautifies remaining elements, do domain-independent recognition.
• Steps: 
• Simple Relation Retrieval
• Cleanup
• Basic Object Recognition

Their user interface also allowed for editing by going into a "modification state" and entering editing command symbols which included "delete","undo", and "redo".

The system was evaluated with only 10 students (totally :p) who thought that the system "was easy to use".

The students entered a set of primitive and hybrid shapes.

"Correct Rate":

• Primitive Shapes: 98%
• Arcs: 94%
• Hybrid Shapes: 70%
• Smooth connections in hybrid shapes were hard to detect.

The paper's evaluation was, qualitatively and quantitatively, extremely weak. Simply saying that system was easy to use is ambiguous. How was it easy to use? What parts did they like? Did they ask if they didn't like anything? Perhaps using a likert scale questionnaire would give a more solid grasp of user satisfaction. How long did they use it for? What the evaluation so short they couldn't find anything wrong about the system?

They only tested on 10 students and no mention was made of how many shapes the users each had to enter. Their correct rate metric is a little vague and not a standard measure for recognition performance.

The paper also erroneously calls spirals "helixes" and there were many spelling and grammatical errors that distracted from the paper.

Ex: "We has devised a function..." (Can they has chzburgers?)

Ex: "There were totally 10 students..." (Did a surfer write this paper?)

Ex: "the curvature curve..." (This happened a lot in the paper and it is really redundant.)

Don't get me wrong, they had some smart ideas. Their method of recognizing overtraced circles was very clear and concise  and their method of breaking strokes down at high curvature vertices makes perfect sense.

Bo Yu and Shijie Cai. 2003. A domain-independent system for sketch recognition. InProceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia (GRAPHITE '03). ACM, New York, NY, USA, 141-146. DOI=10.1145/604471.604499 http://doi.acm.org/10.1145/604471.604499