Reading Assignment: ShortStraw: A Simple and Effective Corner Finder for Polylines

Reference Information
Title: "ShortStraw: A Simple and Effective Corner Finder for Polylines"
Authors: A. Wolin, B. Eoff, and T. Hammond
Citation: "ShortStraw: A Simple and Effective Corner Finder for Polylines", A. Wolin, B. Eoff, T. Hammond,  Proceedings of the Fifth Eurographics Conference on Sketch-Based Interfaces and Modeling, pp. 33-40, 2008.

Summary
ShortStraw is a system created with the goal of being an easy-to-implement, accurate algorithm for corner finding with freehand sketches using the polyline corner finding method. Ideally, it is designed with the intention that it can be used for educational purposes such that beginning-level programming students can implement it without too much difficulty. Polyline corner finders find corners of gestures by finding the minimum set of points within the gesture that can be used as splitting points in order to retrieve a only a set of lines from the stroke.

ShortStraw is a bottom-up algorithm that first resamples the points to be equidistant, calculates the straw distance (the Euclidean distance between two resampled points within a constant window) between each resampled point, and then identifies corners as those points with the minimum values for their straw distance. Then, processing of the found corners occurs with a top-down approach in order to account missing corners or false positives. This processing includes using a line test on each pair of consecutive corners, calculating the distance divided by the path distance to see if it is within a particular threshold. If not within the threshold, a missing corner is detected within a midway window between the two points by using the minimum straw distance. False positives are removed by performing a collinear check.

Evaluation of ShortStraw occurred by testing the system on sketches done by students, then computing an all-or-nothing accuracy measure. This measure was compared to that of the Sezgin's and Kim and Kim's corner finding algorithms. Correct corners found accuracy (number of correct corners found / number of correct corners a human would percieve) and all-or-nothing accuracy (number of correctly segmented strokes / total number of strokes) were both used. It was postulated that all-or-nothing accuracy is a more important measure, since correct corners found can be manipulated by simply returning every point. It was determined that the all-or-nothing accuracy of ShortStraw was significantly better than that of the other corner finding algorithms that it was tested against. Ease of implementation was evaluated by having an undergraduate student implement the system, and it was determined that it was indeed simple to implement. In addition, it was determined that the algorithm runs quickly.

Thoughts
I thought that it was a great idea to aim to create a corner finding algorithm that is easy to understand and easy to implement for educational purposes. It makes the algorithm easy to understand for those reading the paper, and provides a means for introducing newer programmers to the field. I thought that it was even better, however, that the ShortStraw design was actually tested by having a student implement it. This provided a means to actually evaluate that particular goal of the design, instead of just jumping to conclusions and declaring that the algorithm is short, therefore it must be easy to understand.

In addition, I found the discussion of different accuracy measures to be very interesting. Instead of computing a single accuracy measure to report to the user, different methods of accuracy measure were provided, each with their own merits. Then, the all-or-nothing accuracy was determined to be the most important measurement. This is something to consider when reading other papers. Instead of just accepting a single measurement as the definitive accuracy measurement, this paper made it apparent that it should be taken into account what kind of accuracy measurement is being used and whether it is actually the best measurement for the given situation.

It was also useful to learn about polyline corner finding, since we have previously learned about Sezgin's temporal means of corner finding. This is useful as it adds to our knowledge another method for corner finding that may be more useful in some situations.