ShortStraw: a simple and effective corner finder for polylines

In this paper, Wolin et al. discuss their ShortStraw corner finding algorithm.

Their algorithm is based on finding where "straws" connections between the endpoints in a window of points, bridge gaps.

Formally:

•  a straw at point i = distance(point i-w, point i+w) 
• where w = 3, an empirically determined constant for best results

After resampling (which normalizes the straw lengths), their algorithm uses a bottom-up approach to build a set of initial corners followed by a top-down approach to refine or add to the existing set of found corners.

Bottom-up stage: 

• Compute the straws for all points
• Find the median straw (distance)
• Set threshold t = median * 0.95
• Check for Additional Corners:
• For each (Straw straw : Straw)
• if( straw < threshold )
• corners.add( corresponding point for straw )

Top-down stage:

• Additive Co-linear check:
• for each( pair of points in corners)
• if( pair of points does not form a line [i.e. r <= 0.95])
• Check for Additional Corners between the pair of points 
• with relaxed threshold, t
• Reductive Co-linear check:
• for each( triplet of points in corners)
• if( triplet of points forms a line [i.e. r <= 0.95] )
• remove middle point from triplet of points

where r = distance(points,a,b) / path-distance(points,a,b)

Results
The shortstraw recognizer, when run on 244 different polyline shapes, identified 97.9% of actual corners as corners (Correct Corners Accuracy). More importantly, their recognizer achieved an "All-or-Nothing Accuracy" of 74.1% which means that the Shortstraw recognizer perfectly recognized all the corners as corners and did not mis-classify any of the non-corners as corners for 74.1% of the strokes.

This is impressive considering that the Sezgin and Kim recognizers had Correct Corner Accuracies of 82.4% and 79.0%, respectively and All-or-Nothing Accuracies of 27.8% and 29.7%.

Even better than that, the algorithm is simple and competitive in term of the computation time and resources required to run it.

It's encouraging to see simple ideas outperform the more advanced methods. Simplicity can be beautiful at times.

A. Wolin, B. Eoff, and T. Hammond. 2008. ShortStraw: a simple and effective corner finder for polylines. In Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling (SBM'08), Christine Alvarado and Marie-Paule Cani (Eds.). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 33-40. DOI=10.2312/SBM/SBM08/033-040 http://dx.doi.org/10.2312/SBM/SBM08/033-040