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
- Resampling the points of the stroke
- Calculating the "straw" distance between the endpoints of a window around each resampled point
- 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.
