Paper #10 - Recognizing and Beautifying Low-level Sketch Shapes with Two New Features and Ranking Algorithm

Paper:
Recognizing and Beautifying Low-level Sketch Shapes with Two New Features and Ranking Algorithm
(Brandon Paulson and Tracy Hammond)

Summary:
Problems with current recognition systems include having users learn the system instead of vice versa. Paulson’s recognition system does not pose such constraints on the user and only require users to draw single-stroke primitive shapes. Additional features include returning multiple features, higher recognition rates compared to popular low-level recognizers, and high level of recognition rates. Currently recognized shapes are: lines, polylines, circles, ellipses, arcs, curves, spirals, and helixes.

The recognizer’s overall system architecture first consists of performing pre-recognition calculations on single-stroke inputs. In this stage, various graphs and values are computed, and corners are calculated using a multi-pass corner finding algorithm. Two additional features are added in the recognition process: normalized distance between direction extremes (NDDE) and direction change ratio (DCR). NDDE is calculated by taking the computing the stroke length between the point with the highest and lowest directional values. DCR is calculated as the maximum change in direction divided by the average change in direction. In general, polylines have lower NDDE values and higher DCR values than curved strokes. Furthermore, two tests are applied before recognition: existence of overtracing and existence of a closed figure.

For each of the recognized shapes in the system, shape tests are conducted on them. One special note about the shape tests is the complex test, which is set as the default interpretation for shapes which do not pass the other shape tests. After the shape tests, a hierarchy is created to sort the interpretations. Using inherent properties of the multi-pass corner finding, a ranking algorithm was used to determine the best fit of a stroke as a complex, curve, or polyline fit. The study on the recognizer involved collecting two sets of data of 900 shapes from 10 users. The first set was used for training, and the second set was used for testing. Correct shape interpretation returned 99.89%, with 98.56% of those being the top interpretation. Complex interpretations made up half of the error.

Discussion:
I wish I had read this paper earlier. The low-level techniques used here would have sure helped me on the earlier homework assignments. Anyway, I really like the architecture used in this paper, especially the pre-recognition step. Those two new features seem like really novel ways for arc-polyline differentiation. In addition, the shape tests seem quite developed. Unfortunately, I wouldn't be able to comment much more without actually seeing it in action. For now, I shall use faith.

My main observation concern the shapes that were misrecognized in the study. The recognizer does a fine job on normal strokes, but the strokes that the recognizer didn’t identify correctly were quite sloppy. Figure 7 was especially the case. Just by looking at those example strokes, I wouldn’t be able to figure out if they were truly just polylines myself (seriously). If this is difficult for people to differentiate, I believe that it would be unrealistic to expect the recognizer to accurately make such a distinction on such sloppy input data. If I found the user who made those stroke inputs, I’d vote him or her off the island in the next tribal council vote.