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.

Sketch Based Interfaces : Early Processing for Sketch Understanding

Citation

T. M. Sezgin, T. Stahovich, and R. Davis, “Sketch Based Interfaces : Early Processing for Sketch Understanding.”

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8291

There are lot of inferences that can be adapted from real life to solve the technical problems. e.g. While driving, we normally get slow at the corners. The same inference can actually be observed while we tend to sketch things. Sezgin et al. (and Stahowich) used this inference and came up with this paper where he used the sketching Speed and Curvature to figure out the corners in a sketch.

For any sketch, he derived the Curvature Graph and the Speed Graph. The idea behind this was that while we are at corners, the curvature graph would have a spike (local Maxima) and on the other hand, the speed graph would have a local Minima. So, all the speed values below a certain threshold and all the curvature values beyond an empirically chosen threshold would correspond to the corners. For the first step, the authors proved that these two graphs, when used in isolation, don't give the correct corners as we may end up considering the non-corners as corners due to wrong threshold values and noise. So, they used the results from both the graphs and merged the corners.

To correctly determine the correct corners among the merged set, they introduced a new concept called ODSQ (Orthogonal Distance SQuared). This method involved starting with two initial end-points and computing ODSQ by adding a corner each from the set. If adding a corner gives a ODSQ value much below a threshold, the point is rejected from the list of potential corner. For curved regions, they used the concept of Bezier curves.

Thoughts:

The concept of using Speed and Curvature while drawing sketches is pretty novel and clever. This also underlines the fact that solutions to many problems can be adapted from real-life instances. These two features can be used by any Corner finder as they tend to give good results.

Future Ideas and Research:

We can think of deriving more such ideas from real life examples. As discussed in the class, sound can be one such feature. We can also look at the relative density of points collected. Since we tend to slow down at corner, the relative density of points at corners will be high as compared to the normal points. Although this idea is not fool-proof as user may intentionally/unintentionally slow down at non-corners. However, this feature can be tried in conjunction with the set of other features to overcome this problem.

ShortStraw: Now create your own Corner Detector!

Citiation:-
ShortStraw: A Simple and Effective Corner Finder for Polylines
A. Woliny, B. Eoffz, and T. Hammond
http://dl.acm.org/citation.cfm?id=2386308

"Simplicity is the ultimate sophistication". This paper unarguably justifies these lines by Leonardo Da Vinci. While many papers written before this one suggested complex approaches to develop a Corner Finder for Polylines, this paper puts forth a very simple yet effective Corner Finder Algorithm for Polylines.

To effectively detect the corners, this paper divides it approach into mainly 2 stages:-

Resampling:

The drawn sketch is resampled using a unique approach. The interspacing distance between any two  re-sampled points is decided by the length of the diagonal box of the bounding box divided by a constant factor (d = 40).

Corner-Finding:-

After the stroke is resampled, the next step is find the corners. The approach to Corner Detection is further divided into two sub-approaches:-

Bottom-Up Approach:-

In order to detect corners, the algorithm introduces the unique concept of straws for each point. To compute a straw for any particular point (p_i), it calculates the Euclidean distance between the points ( p_i-w, p_i+w) by choosing a Window (w=3). The value of straws decreases as we reach near the corners. So, the algorithm labels all those points as corners for which the straw value is a local minimum with value less than a particular threshold t where t = 0.95 * median(all straw points).

Top-Down Approach:-

The above approach is riddled with few problems as it can lead to Missing Corners and producing False Positives (classifying Non-Corners are Corners). To overcome these two problems, this paper further used two strategies:-

Finding Missing Corners:

To correctly find the missing corners, the authors performed Line Test. For this, they calculated the distance between two consecutive classified corners and compared it with the actual distance. Only if the ratio exceeds a developer-set value (t = 0.95), then there is a line between the consecutive corners. Else, there exists a Missing Corner between the two corners. Since this corner would have threshold value less than t, the threshold t is further relaxed and the point somewhere in between the two corners with the minimum straw value is added as New Corner.

Removing False Positives:

To remove False Positives, the algorithm runs a Collinear Test on three consecutive corners. If three corners are collinear, the middle corner is removed from the set of Corners.

Results:

ShortStraw performs exceptionally well in terms of Accuracy when compared with the other well known Corner Finding Algorithms. Not only this, it uses a All-or-Nothing Accuracy measure to compute the final results on which it, again, performed significantly better. In this, the number of segments in a stroke was compared with the actual number of strokes in the shape.

Critique:

This paper ridicules the notion that for something to be effective, it has to be complex. The algorithm is pretty straight-forward and easy to implement. The idea of Corner-Finding using general Mathematical Concepts is very good. Moreover, it introduces the idea of All-or-Nothing Accuracy measure which helps in discount the case where an algorithm would label everything as a Corner and can showcase 100% accuracy. So, it allows the system to compute and compare the accuracies in a fool-proof manner. In addition, the algorithm is pretty fast and most of the modules run in Linear Time.

However, I was left confused with the following two things:-

1. In the Top-Down Approach, Why the Missing Corners were looked for before actually removing the False Positives. In my opinion, it is slowing down the algorithm as we might  unnecessarily be looking for a corner between two corners one of which may not actually be a Corner (or a False Positive).
2. It also says that the time complexity in finding a Median is O(n log n) which, according to me, is linear O(n) (Although it won't have any impact on the final Time Complexity of the algorithm).

Future Work:-

Since the algorithm doesn't work well with the corners having obtuse angles, we can explore the idea of Variable Window (w) size or the threshold (t) to increase its Accuracy. Moreover, this idea can be extended to other shapes like Curves etc.

Write your own Gesture Recognizer: Quick and Easy

$1 Recognizer

Citation

J. O. Wobbrock, M. G. Hall, and A. D. Wilson, “Gestures without Libraries , Toolkits or Training : A $ 1 Recognizer for User Interface Prototypes,” pp. 159–168.

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

The motivation behind this paper was that the existing Gesture recognizers were too complex for them to be implemented by UI developers or Software developers unfamiliar with the field of Pattern Recognition. So, the authors put forth a very simple and implementable algorithm that is capable of recognizing a single stroke gestures. They also argue that the lack of such an algorithm actually inhibited the widespread adoption of Gesture-based Recognition in designing the applications.

The algorithm is famously known as $1 recognizer. This approach is mainly divided into four steps:

1. Re-Sampling the points: The points of the stroke are resampled so that all the points are equidistant from each other
2. Rotate and Translate: In this step, the strokes are rotated along the indicative angle so that they get aligned with the template strokes with which they will be compared. Indicative angle is the angle made by the first point of the stroke and the centroid of the stroke,
3. Scale: The image is then scaled to a reference square of the size to which the template strokes have been scaled
4. Recognition: This step compares the stroke with the template strokes by finding out the distance between the two strokes. During this step, the matching is done for various angles as the rotation in the second step might not have aligned the stroke at the required angle

Thoughts:

The motivation behind this algorithm is that any UI developer or a person known to programming should be able to implement this quite easily. They performed a user study to verify this claim and they found that most of them were able to implement the algorithm in few hours. This algorithm also performed well on Gesture recognition for Single strokes. Moreover, this algorithm doesn't really have much training time as it just requires a simple template for any gesture comparison.

Future Ideas and Research Work:

The author tried to keep the algorithm as simple as possible, at the same time, ensuring that it works well. Since, in Step 2, the algorithm rotates the stroke, so this makes this algorithm rotation invariance, There are many applications where the rotation/direction of the gestures actually matters a lot. e.g. Swipes (left, right, up and down). So, this algorithm can be made more context aware. Also, the idea of indicative angle is good but not that effective. Certain improvements can be carried out in that field as well.

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.

Which features are better? - Geometric or Gesture

What?! No Rubine Features?: Using Geometric-based Features to Produce Normalized Confidence Values for Sketch Recognition

Paulson, B., Rajan, P., Davalos, P., Gutierrez-Osuna, R., and Hammond, T.

Citiation:

http://srl.tamu.edu/srlng/research/paper/23?from=/srlng/research/

With the advent of Tablets PCs and touch screens, Sketch-based applications are assuming more significance day-by-day. They are one of the best ways to help convey ideas and designs. However, at the same time it is challenging as it becomes really important to understand the intention of the sketcher.

Previous Work:

The previous work done to identify the sketches mainly focused on two approaches : Gesture-based and Geometric-based. These two approaches were tried in isolation by different researchers.

Gesture-based:

This approach was tried by Rubine and Long to identify gestures. The approach has the advantage of using statistical classifiers that are really fast and sound. It also produces Normalized Confidence Values that can be used for alternative interpretations (e.g. differentiate between circle and ellipse). 

This approach mainly focuses on how the sketch was drawn and not how the final sketch looks like. Since every user has his way of drawing a given sketch, this approach is highly user-and-style dependent. As a result, this requires training on example sets of each gesture class respective to every user. Moreover, this approach is tightly coupled with the scale and rotation of the gestures and imposes user to start drawing from specific points and in certain directions only. So, this approach suffers heavily when it comes to draw "free" or "natural" sketch recognition.

 

Geometric-based:

This approach was tried as a part of low level recognizer (PaleoSketch) for identifying primitive shapes. It relies upon finding errors between the sketched shape and the ideal version of the sketch. It makes use of a series of mathematical tests and formulas to perform the recognition. This mainly focuses on how the final sketch looks like rather than how it was drawn. So this approach is independent of the user and his style and hence, performs well for different users.

However, this approach is riddled with couple of disadvantages. It uses numerical thresholds and heuristic hierarchies that are difficult to analyze and optimize. Inferences can't be generalized easily as the classification is not statistical. Alternative interpretations for a given sketch are also difficult if multiple error measures per shape are used.

So, the author, in this paper, went a step ahead and tried the hybrid approach in such a way as to take advantage of using both the approaches. To allow fast and alternative interpretations, a statistical (Quadratic) classifier was used. The geometric features ensured that the model remained user independent.

The data for performing the tests was taken from the PaleoSketch. Following on the lines of Paleosketch, a total of 1800 sketch examples (belonging to 9 different shape classes) by 20 users were taken and split into two equal halves. Each half contained 900 examples sketched by 10 distinct users. The idea behind this was to find out if the system is really agnostic to user's style. This also helped them compare results with PaleoSketch.

The full feature set didn't provide the accuracy as reported by PaleoSketch. So, the paper also used Multi-dimensional Scaling method (Sequential Forward Selection) for Optimal Feature Subset Selection and was able to obtain comparable results.

Using this, the system determined that 14 out of 31 Geometric were significant to obtain good results. Out of the 14 features, the main features were related to Complex shapes and Polylines as they were hard to recognize. 

The most significant observation was that only 1 gesture-based feature (Total Rotation) was found to be optimal. This mainly resulted from the Data split approach based on user. Since most of the gesture-based features are user-dependent, the Data split approach rendered all of them insignificant.

The results, thus, prove that the geometric based feature set is more significant than geometric-based-recognition which was the core of many sketch recognition applications.

Critique:

This approach culled out the best parts of both the gesture-based as well geometric-based techniques. Using the features from the both the techniques augured well in achieving good accuracy for recognizing sketches.The idea of Feature Subset Selection to use the subset of Optimal Features is also good as this helped in leaving out the unnecessary features. Moreover, using such approach made the system user-independent which is always at the core of any Sketch Recognition.

However, the paper only discusses about One Example (Pendulum) when it comes to recognizing Complex shapes. This doesn't throw light on what all sorts of Complex sketches it would be able to handle.

Design Principles of a Sketch Recognition System

A Sketch Recognition should :

1. be Pretty Intuitive and incorporate Simple design
2. be a Well-organized system (Optimum space for everything and fitting to different resolutions) 
3. Gives user the natural feeling of drawing sketches on paper or boards
4. incorporate a Demo or a Help Section with well laid-out instructions on How to use the system
5. be Fast and responsive
6. automatically Improve with time with more Training data and adapt itself to user
7. have a Context-Aware Feedback/Assistive Mechanism to guide users (Error and Help Messages or on a completion of a phase)
8. have a Good Disambiguation method to recognize closely matched sketches (shapes, gestures etc)
9. collect Statistics related to user's drawn sketch and improve itself
10. Multi-stroke recognition system should be able to make out the end of a stroke  

Although obvious, but a Sketch Rec system should also:

1. recognize Primitive, trivial shapes like Lines, Polylines, triangles
2. incorporate basic functions like Cut, Copy, Paste, Redo, Undo etc
3. display the name of the Function upon Hovering (if images without text are being used)
4. have a Color pallet with extensive range of colors as it lends user the ability to add creativity to their sketches

What a Sketch Recognition System shouldn't :

1. be Slow and Unresponsive
2. display unclear and ambiguous Error messages
3. aggressively pop-up Help or Error messages interfering with user's sketching
4. over-fit or under-fit the templates
5. be Complex to work with
6. generally depend upon the Order of the strokes
7. be overloaded with Functionality
8. make the process of switching between a drawn stroke and related controls very complex and time-consuming. Controls/Commands pertaining to a stroke should be in close proximity and can be laid-out right next to the stroke (upon right-click of mouse)
9. be agnostic of factors like Pen Tilt vs Finger Tilt even for the same user. It should clearly lay instructions if such a case exists (may be a very specific point). In such cases, it can't be Input-Mode Agnostic.

Improvements in Mechanix (Not listing the bugs)

1. Progress should be saved on the server as well:
1. It can be accessed by user from any machine
2. User would no longer have to find out the latest copy amongst the different versions of the saved copies
3. Also, he need not worry even if he looses the local copy of the homework 
2. Should collect Statistics (Point 1 assumes significance in light of this):
1.  It will help Instructor find out in real time if many students are stuck on same problem and can modify the feedback to help students
2. It will also help students figure out how much time they spent on a certain problem and the areas they need to improve into
3. It can also lead to Adaptive (User-specific) Feedback Mechanism.
3. A Mechanism for Students to post his doubt regarding a problem directly to the Instructor 
4. A Demo or a Help section can be included
5. Navigation through problems can be simplified as well
6. A Customizable Sound mechanism (that cannot only be turned on or off, but can be updated) can be added as soon as a student accomplishes a stage. This adds to the better user experience.
7. For different platforms like tablets
8. Last, but not the least, a Credits Page Section :)