Bibliography:
Aaron Wolin, Brian Eoff, and Tracy Hammond. ShortStraw: a simple and effective corner finder for polylines. Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling. pp. 33-40. 2008.
Summary:
This paper explains a simple corner finding algorithm, that is is highly accurate for polyline corner finding. The authors claim its simplicity and high accuracy as motivating reasons to use it. They also provide a pseudocode for the algorithm in the appendix. ShorStraw involves resampling the points, finding the 'straw distance' and recognizing points with minimum straw distances as corner. The resampling process is done based on a 'interspacing distance' for points, found by length of diagonal divided by a constant. This constant was set to 40, determined empirically. After resampling the points, 'straw' distances are found for every point, with its neighbours. Corners tend to have a small value for the straw distance. After the initial processing to find the corners, some higher level processing is done to identify missing corners and remove false positives. To add missing corners, consecutive corners are checked to see if they form a line. If not, the system looks for an additional corner inbetween these points. The process is repeated till all consecutive corners form lines. For eliminating false positives, three consecutive points are checked for collinearity. If true, then the middle point is removed. The algorithm was tested based on 2 accuracy measures, namely correct corners found' and 'all or nothing' accuracy. ShortStraw was found to have high values for both, compared to Sezgin's and Kim's corner finders.
Discussion:
I find ShortStraw to be a great example of simplicity and minimalism. It does one task and does it very well. It would be interesting to see ShortStraw used as a component in an algorithm such as Sezgin's, so that it can handle polylines in a more complex algorithm, and also be used as a feature for identifying complex shapes.
Aaron Wolin, Brian Eoff, and Tracy Hammond. ShortStraw: a simple and effective corner finder for polylines. Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling. pp. 33-40. 2008.
Summary:
This paper explains a simple corner finding algorithm, that is is highly accurate for polyline corner finding. The authors claim its simplicity and high accuracy as motivating reasons to use it. They also provide a pseudocode for the algorithm in the appendix. ShorStraw involves resampling the points, finding the 'straw distance' and recognizing points with minimum straw distances as corner. The resampling process is done based on a 'interspacing distance' for points, found by length of diagonal divided by a constant. This constant was set to 40, determined empirically. After resampling the points, 'straw' distances are found for every point, with its neighbours. Corners tend to have a small value for the straw distance. After the initial processing to find the corners, some higher level processing is done to identify missing corners and remove false positives. To add missing corners, consecutive corners are checked to see if they form a line. If not, the system looks for an additional corner inbetween these points. The process is repeated till all consecutive corners form lines. For eliminating false positives, three consecutive points are checked for collinearity. If true, then the middle point is removed. The algorithm was tested based on 2 accuracy measures, namely correct corners found' and 'all or nothing' accuracy. ShortStraw was found to have high values for both, compared to Sezgin's and Kim's corner finders.
Discussion:
I find ShortStraw to be a great example of simplicity and minimalism. It does one task and does it very well. It would be interesting to see ShortStraw used as a component in an algorithm such as Sezgin's, so that it can handle polylines in a more complex algorithm, and also be used as a feature for identifying complex shapes.
No comments:
Post a Comment