"Short Straw: A Simple and Effective Corner Finder for Polylines"

by Aaron Wolin, Tracy Hammond

Summary

Corner finding is the technique that involves splitting up a stroke into primatives, such as lines and arcs. ShortStraw is a simple and effective algorithm for corner finding.

Sezgin et al. use a stroke's curvature and pen speed to determine stroke corners. Kim and Kim use local convexity and local monoticity and also use resampling in their algorithm. These algorithms are complex, while ShortStraw is simple and highly accurate.

Implementation of ShortStraw:
Step 1, resample points of a stroke to be evenly spaced apart, so that the path distances between adjacent points are equal. The interspacing distance is bounding box diagonal / 40 (where 40 is a constant number carefully chosen.)

Setp 2, bottom-up corner finding: Corners are points with local minimum straw below a threshold of median straw * 0.95. (window size of plus/minus 3 is chosen here)

Step 3, top-down corner checking to remove false positives and add false negatives. (1) do line tests between adjacent corners found by step 2, if Dist(a, b) / Path-Dist(a, b) < 0.95, then there are missing corners in the halfway, relax threshold and add the point with local minimum straw to corner set, repeat untill all the stroke segments between corners pass line test. (2) if a subset of triplet passes line test, then the middle corner is removed. Corners returned are from the resampled points. Or it can be the nearest original point to that corner.

Results show that ShortStraw has much higher all-or-nothing accurracy (calculated by taking the number of correctly segmented strokes divided by the total number of strokes) of 0.74 compared with less than 0.3 using Sezgin and Kims' algorithms. And the number of false negatives with ShortStraw is 1/10 the number with Sezgin and Kim. The missed corners at obtuse angles can possibly be fixed by utilizing a varied windowor straw length for each point, but this may sacrifice algorithm simplicity.


Discussion

This is a quite straightforward algorithm, and the accuracy is high. The top-down checking phase further increases accuracy. I think maybe context information can be included in the future, for example, human viewers will think some point as a corner even if it looks more like an arc than some line segments meet at corners.

Algorithm Video