Thursday, November 18, 2010

Reading #15 An Image-Based, Trainable Symbol Recognizer for Hand-drawn Sketches (Kara)

Comments

Whenze

Summary

This text describes a symbol recognizer that can be easily trained based on single examples of the symbols. The recognizer bases on template matching as other recognizers discussed before on this post. The novel approach of this recognizer relies on two basic aspects: the combination of multiple template matcher recognizers to provide a more accurate final recognition result. And a rotation invariance achieved by the transformation of the unknown symbol into polar coordinates which greatly reduces the rotation invariance processing time compared with other techniques. The accuracy reported is remarkably high, and the recognizer has very good time response.
The recognizer begins with a pre-recognition based on the transformation of the unknown shape into polar coordinates where the stored templates that are too dissimilar to the presented shape can be pruned away. Thereafter the remaining templates can be compared using 4 different methods (Hausdorff Distance, Modified Hausdorff Distance, Tanimoto Similarity Coefficient, and Yule Coefficient) these classifiers return their more likely shapes and a final module standardizes each output and combines the outputs together to form a final decision.

Discussion

This paper presents interesting results based on existing techniques. I think that the mayor contribution is the prerecognition based on polar transformation of coordinates, this smart idea converts the problem of rotation to a more natural domain making it easy to handle. Many advantages come from template matching as explained in the paper such as overtracing support and dashed lines. However shapes that are not always drawn with the same geometric proportions may be a problem (e.g. arrows), nevertheless for a standard symbol domain this is usually not the case so it is a very good option.

Wednesday, November 10, 2010

Reading #28 iCanDraw? – Using Sketch Recognition and Corrective Feedback to Assist a User in Drawing Human Faces (Dixon)

Comments on others

Chris

Summary

iCanDraw is the first application that uses Sketch Recognition to assist the user in learning how to draw. Although most of the algorithms and techniques of this paper are not new there is a major contribution in opening a new field of application for sketch recognition. They show sketch recognition can have great use in this kind of applications. The results going through 2 iterations of the application reveal that such application is feasible, and although much more studies have to be done to prove this is an efficient teaching tool, the end-to-end system is now available to begin such studies. Another important result of the paper is the set of design principles obtained from the user study in this kind of applications for assisted drawing using free sketch.
For the implementation of the application the user interface is remarkably well achieved. After a first iteration and a deep analysis of it, many mistakes or weaknesses were detected and corrected such that the final version of this interface is very user oriented and can give a more much effective teaching experience. Each face template goes through a face recognizer to extract its most prominent features, and then some hand corrections are done to finally get to a template of the ideal face sketch. The recognition then is mostly template matching oriented. Some gesture recognition is also used as part of the interface for actions such as erasing or undoing.

Discussion

The work presented opens a very interesting field of application to sketch recognition. In the sketch recognition class a project about how to draw an eye is one of the possible descendants of this project.  I think one of the mayor challenges in this field is to determine the appropriate amount and quality of the feedback given to the user. If the user is forced to draw too close to the template the experience can be frustrating, but if it is too loose the improvement in drawing might be poor, a solution might be having several difficulty level in different lessons.

Wednesday, November 3, 2010

Reading #14. Using Entropy to Distinguish Shape Versus Text in Hand-Drawn Diagrams (Bhat)

Comments

Jhonathan

Summary

This paper also addresses the problem of discerning shape from text. Unlike the paper in the previous post this recognizer does not attempt to use a lot of features, instead it uses only one single feature to split shape vs. text. Entropy proved to be a very distinctive feature between shape and text. Entropy is a measure of uncertainty associated with a random variable; it is in other words the randomness of an object or system.  Basically this gives the intuition that text is far more random than simple shapes. In order to measure this randomness in a sketch several steps were followed. First, the strokes were grouped on a time basis. Then, the sketch was resampled to leave every point in each stoke at the same fixed distance. With this angle each joint was classified in 7 possible labels and with this classification the overall entropy of the shape could be calculated according to the formula below.

Results show that this single feature is even better to differentiate shape vs. text than the combination of features shown by Plimmer. It achieved an accuracy of 95.56% with77.51% of the shapes classified (some were left as unclassified).

Discussion

This paper found a single feature that is very important to shape classification versus text. I think it is interesting that the paper analyzed the use of entropy by itself to be able to prove the power of this feature. However in a real classifier I would rely on more than this feature to be able to detect some of the cases not analyzed in this paper, for instance the musical notes, in which case entropy alone fails, but along with other features like density can discern accurately. Also other techniques may aid in the more general process, for instance wrong grouping that relies in time only can affect the whole classification. If other techniques such as growing boxes can detect and recover for a wrong groping this could turn this into a more robust classifier.

Tuesday, November 2, 2010

Reading #13. Ink Features for Diagram Recognition (Plimmer)

Comments

Danielle

Summary

This paper addresses the issue of selecting the right set of features for sketch recognition. Since Rubine the feature based sketch recognizers have become very popular, yet the set of features that is used is somewhat empiric in each case. This paper proposes a more formal method to select the most relevant features that will lead to accurate and fast recognition for certain domain. In this case the feature selection is applied to the problem of differentiating shape versus text. For each of the sample shapes 46 features are extracted and a statistical partitioning technique is employed to find the most relevant ones. The aim is to find the optimal position of a split for each feature such that there are a minimal number of misclassified strokes. After doing this for all features the most selective and important features can be used to build a binary classification or decision tree as shown below. The results were compared with other two classifiers achieving overall better classification than these two.

Discussion

Perhaps the mayor contribution of this paper is the fact that it formally analyzes a way of selecting features and it includes a complete feature set including some new features and some of the most representative found in the literature. The decision tree structure may likely guide to misleading strokes in certain cases which makes it difficult to think that it will ever achieve perfect accuracy without the aid of geometric interpretation or other means of recognition. However this method can be very fast and for most practical purposes it provides a reliable classification.