Reading #10. Graphical Input Through Machine Recognition of Sketches (Herot)

Summary

In this paper, the introduces a series of smaller programs which when intertwined form the basis of a graphical input recognition system named HUNCH. Some basic issues in sketch recognition are discussed including how to find lines and corners from raw data and how to methods for dealing with latching and over-tracing. Underlying problems of the bottom-up approach for recognition are also discussed and brief exploration is given into how a top-to-bottom approach might function. 

Discussion

In a modern sketch recognition system, many of the smaller programs implemented here may simply be seen as function of a complete recognition program. However, since at the time, computer resources were limited, the process of breaking up the recognition process into smaller tasks provides great insight into the basic steps to be taken for recognition. It is also interesting that in order to locate corners, the author utilizes speed and "bentness". "Bentness" later proved to be a very effective method of locating corners as seen in the Short-Straw method discussed in class. Although it may not have been as effective at the time of this writing since they most likely lacked the computer resources to re-sample a sketch.

Reading #9. PaleoSketch: Accurate Primitive Sketch Recognition and Beautification (Paulson)

Summary

In this paper, the author presents PaleoSketch, a low-level recognizer which performs with almost 99% accuracy when recognizing 8 primitive shapes. PaleoSketch uses many previously employed pre-processing techniques for recognition but also introduces two new important pre-processing features. The normalized distance between direction extremes (NDDE) and the direction change ratio (DCR) are both very helpful in distinguishing curves from corners. An overview of how each primitive shape is recognized with the inclusion of these features is also presented.

Discussion

This paper two important pre-processing features that prove very useful in primitive shape recognition, the NDDE and the DCR. Using these features, the accuracy of PaleoSketch returning the correct interpretation as the top interpretation increased by over 30%. These features will most likely be included in any future low-level recognizers developed.  

Reading #8. A Lightweight Multistroke Recognizer for User Interface Prototypes (Anthony)

Summary

In this paper, the author presents the $N Recognizer. This system is built on top of the $1 Recognizer but contains various improvements. $N is capable of recognizing gestures comprised of multiple strokes, recognizing 1D gestures such as lines, and providing bounded rotation invariance to allow for recognition of more symbols. $N also employs two optimization techniques based on the starting angle of a gesture and the number of strokes in a gesture, the second technique being optional. Even though $N is slightly more complex than $1, these optimization techniques help to run faster than $1 since both system are based on template matching.

Discussion

The use of optimization techniques in $N to reduce the number of templates compared greatly helps to reduce the run time of the recognition algorithm. Such techniques could be implemented in other template based recognition systems to reduce the amount of processing required. In order to recognize multi-stroke gestures, $N simply creates multiple templates by connecting the strokes in every possible order. For gestures with three or more strokes this can often greatly increase the number of templates being compared. An alternative method might be to have a single template consisting of only the strokes drawn on the interface and use all possible starting angles when attempting to match to a gesture. 

Reading #7. Sketch Based Interfaces: Early Processing for Sketch Understanding (Sezgin)

Summary
In this paper, the author describes an early processing system to be used as the basis for higher level sketch understanding. The system consists of three processing steps: approximation, beautification, and basic recognition. The system described allowed users to enter free-hand strokes in a sketch based input system without the need to switch between drawing modes. Previous works required that a user somehow notify the system whether a line, curve, or arc was being drawn. 

Discussion

This paper introduces an interesting method of detecting corners in sketched inputs. Instead of relying only on curvature data as some previous works, this system employed a combination of curvature and speed data to determine the most likely locations of corners. This new method helped the authors successfully distinguish between different stroke components and implement the rest of their system. Recognizing the basic geometric components of a sketch is a valuable addition for almost all areas of study in which one might use a sketch based interface.

Reading #6: Protractor: A Fast and Accurate Gesture Recognizer (Li)

Summary

In this paper, Li introduces his gesture recognizer named Protractor. It works similar to the $1 Recognizer presented by Wobbrock but is faster and can be made to be orientation-sensitive. Protractor first resamples to N points and then rotates based on the indicative angle or to one of eight orientations if it is specified to be orientation-sensitive. It then calculates the optimal angular distance against each template and returns the top choice of the N-best list of results. 

Discussion

Protractor uses the same concepts presented in the $1 Recognizer but also makes some key improvements. Protractor is able to recognize gesture which are orientation-sensitive by only rotating to certain angles and not scaling to avoid distorting the input. It also uses a closed-form solution to find the rotation that leads to the minimum angular distance instead of using the iterative approach utilized in $1. This helps Protractor to produce a higher accuracy in shorter amounts of time.

Reading #5: Gestures without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes (Wobbrock)

Summary

In this paper, Wobbrock introduces his "$1 recognizer". This recognizer is easy to implement compared to other methods of gesture recognizing, such as Rubine's method. The simple algorithm consists of resampling the point path, rotating the gesture based on "indicitave angle", scaling and translating to a reference square, and then finding the optimal angle for the best score. The score is computed as a function of the distance between the template points and the points of the gesture. 

Discussion

This paper introduces a simple gesture recognizer that requires less processing to implement than many recognizer before it. The $1 recognizer provided accuracy rates of over 99% for a selection of gestures. However, since it changes the orientation and scale of each gesture that is input, it would not perform well with gestures such as arrows or shapes that may be similar such as squares and rectangles. 

Reading #4: Sketchpad: A Man-Made Graphical Communication System (Sutherland)

Summary

In this paper, the author describes the Sketchpad system. Since the hardware of the time was limited, the author uses a light pen and a combination of push buttons, on and off switches, and turning knobs to input and manipulate data in the system. The system is only able to use lines, circles, and points but the data structure for each was well defined along with the types of constraints that may be used. Several examples of Sketchpad projects were given including bridge drawings, artistic drawings, and electrical circuit diagrams.

Discussion

This paper introduces many ideas that are still used in sketch input systems today such the data structures and constraint systems presented. The idea of copying instances and being able to have sub-pictures within sub-pictures allows for more efficient sketches to be created. The constraint system introduced is very useful for defining components composed of subcomponents.