ShortStraw: A Simple and Effective Corner Finder for Polylines

Comments

Daniel's blog

Summary

In this paper the author discusses a simple corner finding algorithm which he compares to more complex corner finding algorithms given by Sezgin and Kim Kim. The basic theme defined for this algorithm is that it can be implemented easily and still be very accurate when compared to it's counterparts. When implementing this algorithm the developer only has to have a very basic knowledge of higher mathematical function defined in calculus.

The algorithm works in three stages

1. Resampling of input points of a stroke.
   
2. Calculate 'straws' which is the distance between the endpoints of window.
3. Points with minimum 'straw' distances as the corners of the stroke.

In resampling the point from the original stroke a resampled in such a way that the resulting stroke has equidistant points. Its based on the Wobbrock resampling algorithm.

In corner finding the author takes two approaches. First is the bottom-up approach in which the corner are indentified by a defined algoritym. Secondly the author takes a top-down approach in which the corner which are not identified by the first algorithm are identified and the corners which are misrecognized earlier are removed.
The bottom-up approach of corner finding algorithm works by first calculating straw values at each point. A straw value is the euclidean distance between the two points pi-w and pi+w where w is the window size. The algorithm works on the fact that these straw values will become samller when points will get closer to a corner. The corners are identified by first taking the median of all the straw values. Then multiplying the median with a constant value to calculate the threshold t. The local minima below the threshold t is taken as corner.
The top-down approach of the corner finding algorithm works to find the missed corners and remove false positives. This is done by calculating the ratio between the euclidean distance to the path distance between the two points taken as corners. If the ratio is below a defined threshold value then the two points are considered as lines and there are no corners between the two points. If the value is larger than the threshold then there could be more corners between the tow points. The threshold value is relaxed and the minimum straw value which is in the middle half of the stroke is taken as a corner. A collinear check is then run on the subsets of triplet, consecutive corners and the middle point is removed if the three points are collinear.

It is interesting to note that the ShortStraw with it's simplicity is able to produce better results than Sezgin and Kim Kim with this logic. It also doesnot uses any temporal information which as Sezgin and Kim Kim so it can also be used for sketches taken from offline sources.


Discussion
I like the idea of the ShortStraw which uses a very intuitive algorithm for corner finding. The good thing about ShortStraw is that uses no temporal information which more close to how the human perceives corners from sketches.

The algorithm uses a lot of threshold values and constants which tells that ShortStraw can only be fine tuned for a perticular set of strokes and not a blanket solution for corner finding. I think this is where the contextual information about the stroke can make a differenece in the accuracy and usability of this algorithm for a wide range of problems.