Paper Review #8: ShortStraw

1. Paper Bibliography

• Title: ShortStraw: A Simple and Effective Corner Finder for Polylines
• Authors: Aaron Wolin, Brian Eoff, and Tracy Hammond
• Publication: Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling. Eurographics Association, 2008.

2. Summary

• Main step

1. Resampling the points of the stroke
2. Calculating the "straw" distance between the endpoints of a window around each resampled point
3. Taking the points with the minimum straw distance to be corners

• Providing free-sketch recognition
• A stroke is broken down into primitives.
• The primitives can be recognized with high accuracy.
• It is recombined using geometrical rules to allow for recognition of naturally sketched shapes

• Corner finding = splitting a stroke into primitives
• Find the minimum set of points such that, if the polyline is split at those points, the resulting primitives would consist of only lines.

3. Details

• Resampling
• same as $1 recognizer (but interspacing distance of the points is different).
• based on diagonal length of the stroke's bounding box. (reason: various sizes)

Interspacing distance = the diagonal length of the bounding box / constant value

• Increasing the constant val: too noisy 
• Decreasing the constant val: over-smoothed 

• Corner Finding
• Bottom-Up: build corner from primitives
• Set up initial corners
• A corner is based on the length of "straw" (w is a constant window size) 
• Euclidean distance

Straw_i = | P_i - w, P_i + w |

• Straw: short, local minimum
• If Straw_i < threshold(median Straw * 0.95) and is local minimum, it is a corner. 

• Top-Down: insert or delete corners from higher-level pattern
• Find missing corners or false corners
• Adding
• Line test (equality ratio) 

r = chord distance(a,b) / path distance(a,b)

• If r > developer-set threshold(0.95), it is line.
• Removing
• If three corners are collinear, remove the middle one.

4. Experiment & Discussion

• Training data (6 people * 11 shapes * 4 times - 20 errors = 244)
• Compared targets: Sezgin's corner finder, Kim and Kim's
• Measurement: 
• correct corner accuracy(penalty for false negatives) 
• all-or-nothing accuracy(penalty for both false positives and false negatives)

• Complexity
• Resampling points: O(n)
• Calculating the straw for each points(bottom-up): O(n)
• Calculating the median straw length: O(nlogn)
• POST-PROCESS-CORNER(top-down): O(cn)
• To reduce complexity: replace euclidean distance with a squared distance
• Lack of recognizing curvature 

5. My opinion

I was wondered the result of testing circle shape. Probably it might not be suitable for circle shapes because I think that this would cause high complexity. However, it would be much nicer if corner recognition and circle recognition are combined.