Reading #18: Spatial Recognition and Grouping of Text and Graphics (Shilman)

Comments

JianJie

Summary

Once again, this paper focuses in separating text and shape. In this case a general approach is taken based mainly on spatial features of the ink. A graph is built that relates each stroke in the sketch based on its neighboring with other strokes. Then strokes that are grouped closed together can be identified by different recognizers. The novel approach here is that both grouping and recognition are done in parallel such that the recognition can judge if a grouping was good or not and in this case another grouping can be tried. Once a sketch is represented as a graph many of the usual algorithms in graph theory can be used. In this case an A* search is used to optimize the grouping of the strokes. The results show grouping accuracies of 90% and recognition with grouping of 85%.

Discussion

A very nice feature of this recognizer is that it does not require hand coded heuristics. This is very useful for a general recognizer that can be applied to many domains. However as it is usually the case the generalization comes at the price of lower accuracy. Other recognizers that are fine-tuned for particular domains show better accuracy. However this is a very good start-point and the grouping idea can be exploited in similar recognizers.

Reading #17: Distinguishing Text from Graphics in On-line Handwritten Ink (Bishop)

Comments

JianJie

Summary

As in readings 13 & 14 this paper also addresses the problem of discerning between shape and text. The approach here is somewhat different than the previous posts, as this one uses not only features of the stroke but also characteristics of the sketch like gaps between strokes. Parting from an independent stroke model where features are extracted as in the other works to allow classification using cross-entropy. In a later step, machine learning techniques are used to take into account other important properties of the context of the stroke to improve classification. Particularly a Hidden Markov Model is used to represent the sketch and run algorithms to detect the optimal labeling for each stroke. The results shown are based on confusion matrices, they are not easily comparable to other recognizers but show internal differences amongst the use of context (independent, vs. uni-partite or bi-partite HMM).

Discussion

This paper presents another technique for classifying text vs shape. Altough the results are not very clear in terms of the accuracy of the recognizer in different domains, the concept of using context is very interesting. And even If their results cannot be trivially compared to others, they show improvements by using context. As a matter of fact the intuition of how humans recognize shape vs text in an apparently natural way relies heavily on concept. For instance the shape O in this paragraph would be classified by any normal person as the letter O. But in another context that letter O would be clearly classified as a wheel just depending on context. (See fig below).

Reading #16: An Efficient Graph-Based Symbol Recognizer (Lee)

Comments

Kim

Summary

In this paper a recognizer is presented that bases its recognition on the topology of the sketched symbol and the relationship between its primitives. The work presented resembles ladder in the sense that geometric primitives are extracted and recognition is made based on the relationship between this primitives. However one important difference is that ladder proposes a language for describing shapes and symbols. Instead, this recognizer attempts to represent the primitives and their relationships in an attributed relational graph. And then compare this graph with the stored template graphs. The resulting accuracies are not particularly high compared with similar work at the time of publication, but some advantages are presented.
The first problem this recognizer addreses is the modeling of the sketch as an attributed relational graph (ARG).This is a crucial step for the recognizer and it is not trivial because it inherits all the problems of primitive shape recognition (corner finding, noise reduction, arcs vs polylines…) Fortunately much work has been done in this area such that relatively accurate primitive finders can be used. Then some features like similarity and error are described to be used in a graph matcher. Several graph matching techniques can be used, 4 of them are presented and compared in this paper.

Discussion

Although the accuracy results are not the best presented in the recognizers of this post this approach presents several advantages over other recognizers that are worth looking. Compared to Kara and other template based recognizers for example, this one still works under non-uniform scaling, also compared to ladder for instance presents the advantage of example training, although at the expense of some accuracy drop. For some domains this recognizer might be an interesting choice as it presents easy training and is robust for several types of symbols.

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.

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.

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.

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.