Combining Corners from Multiple Segmenters

Citation

A. Wolin, M. Field, and T. Hammond, “Combining Corners from Multiple Segmenters,” vol. 1, pp. 117–124, 2011.

http://dl.acm.org/citation.cfm?id=2021164.2021185&coll=DL&dl=GUIDE

Throughout the class, we read a lot of Corner Recognizers. Each one of them were good at recognizing different corners but almost all of them could perform well only on limited domains. e.g ShortStraw could recognize corners in Polylines but would miss corners with Obtuse Angles. Also, most of them were riddled with the problem of reporting either False Positives or False Negatives. So, the author of this paper came up with the idea of combining all the Corner Recognizers with a thought towards General Corner recognizer and then applying a novel approach called SBFS (Sequential Backward Floating Selection) to remove False Positives and False Negatives.

This paper used 5 Corner Recognizers namely by Douglas Peucker, ShortStraw, Paleo-Sketch, Kim and Kim's and Sezgin et all.. The first 3 recognizers are the Polyline Corner recognizers while the last two are Primitive-Shape Segmenters (they divide the shapes into primitives or lower-level shapes like Arcs, Lines and Curves).

Approach:

1. Any given stroke is made to pass through all the 5 above mentioned algorithms and their respective corners are then combined,
2. Duplicate corners are removed,
3. To remove False Positives and False Negatives, the paper applies an algorithm called SBFS,
4. It also uses another novel approach termed as  delta-MSE to decide when to stop removing the corners from the set of corners

SBFS:

1. It is based on a Greedy approach,
2. It starts by removing Corners one-by-one and then tries to compute Mean Squared Error (MSE) distance of the original stroke with optimal Stroke formed by those corners,
3. Whichever set/combination gives the minimum error, it takes that set and greedily moves forward repeating Step 2,
4. Also, at every step, it tries to figure out if adding any one of the earlier removed corners would help decreasing that value,
5. Since it is a Greedy Approach, it doesn't give the optimal solution. However, it runs much faster than a Dynamic Programming solution which is known to give the optimal solution but would have run forever.

Delta-MSE Approach:

1. This approach was used to determine when to stop removing the corners,
2. This basically takes the ratio of MSE of Set with (i) corners and a set with (i+1) corners,
3. The idea behind this ratio is that whenever we start removing the actual corners, this ratio will see a sudden increase in value (termed as elbow)

Thoughts:

The idea of combining all Multiple Corner recognizers and segmenters and then applying SBFS on those set of reported corners is an excellent idea. This was evident from the All-or-Nothing Accuracy metric that came out to be ~92%. 

Further Ideas and Research Work:

The author reported the running times of all the algoirthms. Paleo-sketch takes a lot of time and the CSS (Corner subset selection - which is actually SBFS) also ends up consuming a lot of time which renders the task of real time corner finding on any shapes a bit time-consuming. We can parallelize all the Corner Finders and their individual steps as well. Further, we can think of using a Machine Learning or a trained Classifier based approach which can run in much faster time as compared to SBFS to remove the non-corners.