Reading 16: Combining corners from multiple segmenters

Citation

Wolin, Aaron, Martin Field, and Tracy Hammond. "Combining corners from multiple segmenters." Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 2011.

PDF

Summary

This paper introduces a novel way to detect corners in sketches. Previous algorithms in corner detection work well for one case but might fail for another. This paper introduces a hybrid approach by combing the results of successful corner finding algorithms and trying to find the best subset of all the points detected by those algorithms. The paper uses subset selection to find the best subset. The algorithm is as follows:

1) Take corners detected by five famous corner finding algorithms viz PaleoSketch, Douglas Peucker, Sezgin, Kim and Kim, ShortStraw.

2) Take all these corners as initial set and apply subset selection by using Mean Square Error as the error metric.
3) Output the best subset.

Discussion

Subset selection algorithm used in this paper also allows to add any point that was removed earlier. Mean Square Error (MSE) itself was not used to set the threshold for finding the best subset because difference in MSE might be high for larger scale sketches and smaller for smaller scale sketches. So a ratio of the MSE's was taken. To find the threshold for finding the best subset in the delta MSE graph a dynamic approach was used. A system was trained on existing sketches and a delta MSE was calculated for n+1 to n named R(below) and n to n-1 named R(above) where n is the correct number of corners in that sketch. It was observed R(below) values lie close to 1 as removing irrelevant corners didn't increase MSE much. Whereas R(above) values had a higher range. R(below) and R(above) were represented as Gaussian curves and their intersection was taken as the threshold which came out to be 1.99. To fit R(below) and R(above) to Gaussian curves instead of using Mean and Standard Deviation of the collection, Median and MAD (Median Absolute Deviation) were used as Mean and Standard Deviation of the Gaussian Curve. The accuracy of this method was observed to be higher than any previous method. More specifically the all or nothing accuracy was considered the most important metric to measure the accuracy of this corner finding algorithm.