CALI: An Online Scribble Recognizer for Calligraphic Interfaces
Manuel J. Fonseca, Cesar Pimentel, Joaquim A. Jorge, 2002
Summary:
In this paper, Fonseca, Pimentel and Jorge from Technical University of Lisbon describe their online scribble recognizer for calligraphic interfaces, CALI. Scribbles, as they say, are simply multi-stroke geometric shapes. There are two versions of CALI, a non-trainable gesture recognizer and a trainable one.
The recognition algorithm uses a combination of fuzzy logic, geometric features and a set of heuristics. Recognition rates of over 97% for the non-trainable version and 95% for the trainable version are reported.
The non-trainable recognizer uses three main ideas: extracting and using geometric features, using a set of filters to identify or remove unwanted shapes and using fuzzy logic to resolve uncertainities in shape sketches.
The geometric features are obtained first by computing the convex hull of the points. This convex hull is used to compute the largest area triangle and quadrilateral and the smallest area enclosing rectangle. The area and the perimeters of these polygons are used in computation of features. For example, Thinness ratio is defined as (Perimeter of complex hull)^2/(Area of complex hull) and is used to distinguish circles from other shapes, which is expected to give a value near 4PI. Likewise, lines are identified using the aspect ratio (Height of the enclosing rectangle)/(Width of the enclosing rectangle) which is expected to be near zero for lines and larger for other shapes. For each such feature and shape couple, a graph is obtained using training data. Fuzzy logic is then used to derive the fuzzy sets from this data and the degree of membership is calculated for each shape class. An example of the building of rules to classify shapes is given in the paper. Finally, possible ambiguities between shape classes are resolved using context information.
The trainable recognizer uses a Naive Bayes classifier. It is chosen among K-Nearest Neighbors and Inductive Decision Tree algorithms for its high classification efficiency and acceptable training and classification complexity. Naive Bayes algorithm computes the probability of each feature belonging to each class for any given shape instance. The probabilities are then combined by the algorithm to discover the class of the instance. The algorithm is reported to exhibit acceptable recognition rate with 50 examples per shape class and stabilize around 100 examples per class.
Discussion:
The system has two versions, non-trainable and trainable algorithms with the non-trainable algorithm having a slightly higher recognition rate. However, its flexibility for introducing new shape classes makes it a plausible choice.
The reported recognition rates of 95% and 97% are impressive. It should also be noted that the system also recognizes shapes drawn with dotted/dashed and overtraced strokes along with normally drawn strokes. The recognition system is also scale and rotation invariant.
Hiç yorum yok:
Yorum Gönder