ShortStraw-A Simple and Effective Corner Finder for Polylines

ShortStraw-A Simple and Effective Corner Finder for Polylines

Summarized by urjnasw xkfjjkn

This paper introduces a polylines corner finding algorithm called ShortStraw. It is simple to implement and outperforms the state-of-the-art corner finding algorithm for polylines.

The implementation is comprised of the following two basic steps:

(1)    Resampling:

Unlike traditional resampling using fixed time period to determine a resampling point, ShortStraw uses fixed distance to determine when to insert a point to original graph. The fixed distance is  (size of bounding box / 40 ) empirically. Specifically speaking, resampling point set is generated according to the following algorithm:

The termination condition for this algorithm is when i > |number of points in original graph|.

(2)    Corner Finding:

There are two approaches for corner finding:

[1] Bottom-up:

First of all, the concept of straw should be clarified. Straw means the Euclidean distance between point P_i+w and P_i-w, where w is window size. Empirically it should be 3 for higher corner recognition rate. After summing up the straw of each point in the original stroke and take the average, we will get a straw median. 0.95 * straw median is used as a threshold. When the straw length of a point is less than the threshold, we take the local minimum as a corner.

[2] Top-down:

Top-down is run after bottom-up. It is used to find missing corners and rejecting false positives.

After running Bottom-up, we have already got a bunch of corners. For each consecutive corners, we run IS-Line test:

Basically, this is the simplest line test ever. If it is a line, r equals to 1. Otherwise, r should be less than 1. Here, we set r equals 0.95 as threshold. When r between two consecutive corners is less than the threshold, we need to relax the threshold to find missing corner around the middle half of the segment. This process is repeated until r is larger than the threshold.

On the other hand, we need to do collinear check on three consecutive corners c_l, c_m, c_n. If c_l and c_n pass the IS-Line test mentioned above, just remove c_m. What should be emphasized is all returned corners should be from resampling points obtained in the first step.

Pros and Cons for ShortStraw:

Pros: Compared with other common corner recognition techniques, such as Sezgin, Kim, ShortStraw is quicker, easier to implement and more accurate. It does not need any temporal information.

Cons: Only applicable to stroke consisting only polylines, cannot handle arcs, not sensitive to obtuse angles. 

Bibliography:

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.
https://diglib.eg.org/EG/DL/WS/SBM/SBM08/033-040.pdf.abstract.pdf%3binternal&action=action.digitallibrary.ShowPaperAbstract