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.

Paleo-Sketch: For Primitive Shape Recognition and Beautification

Citation

B. Paulson and T. Hammond, “PaleoSketch : Accurate Primitive Sketch Recognition and Beautification,” pp. 1–10, 2008.

http://dl.acm.org/citation.cfm?id=1378775

Summary

Paleosketch is a Recognizer for Primitive-Shape like Lines, Arc, Circles etc. Besides recognition, it is also used for beautifying them. Since it uses Geometric recognition at its helm, so it is free from the vagaries from the system using Gesture Recognition techniques like Rotation, direction, starting point etc. That's the reason it performs much better for domains where the system should have rotation invariance etc. It doesn't distinguish between a Circle drawn clockwise or anti-clockwise.

Approach

1. Each stroke consists of sequence of points represented by (x, y, time)
2. It, then, removes duplicates points. Points with either the same (x, y) co-ordinates or the same timestamp,
3. It computes two new exciting and innovative features for finding Corners:
1. NDDE: Normalized Distance between Direction Extremes
2. DCR: Direction Change Ratio
4. It then performs two tests to determine:
1. If the line is over-traced (no of revolutions are greater than a threshold),
2. If the shape is a closed-shape (Compares the distance between two end-points and the total length of the stroke)

NDDE:

1. It calculates the distance between the points of highest direction value and points of lowest direction value where direction value is arctan of change of y over change of x,
2. NDDE = above value/ total length of the stroke
3. Since for Arcs, two points of direction extremes are the starting point and the ending points, this value is pretty high
4. While for Polylines, these two points can be pretty near and hence this value is pretty low

DCR:

1. DCR = Max change in direction value/avg change in direction value,
2. Since in case of Polylines, average change in direction value is very less (mostly at corners), DCR value is pretty high,
3. Since in the case of Arcs, there is a change in the direction at every point, the average value is pretty high and hence the low value of DCR,
4. We normally ignore the first and the last 5% of the stroke to mitigate noise

It then performs a series of tests to distinguish between different kind of shapes.

1. Line Test,
2. Arc Test,
3. Polyline Test
4. Ellipse and Circle Test
5. Curve Test
6. Spiral and Helix Test
7. Complex Test

To determine Complex Shapes, it uses a Ranking Algorithm where it ranks the each interpretation and chooses the one with with Lowest Rank.

Thoughts:

It performed really better than the existing recognizers. This was evident from the high accuracy it achieved during the testing.

Future Ideas

This can be used as Primitive Recognizer in domains with Complex Shapes. This has already shown good results with a system named LADDER. This idea can be expanded into other domains as well.