Combining Corners from Multiple Segmenters

Bibliography Information:

Wolin, Field, Hammond. "Combining Corners from Multiple Segmenters". SBIM '11 Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling. Pages 117-124 . ACM New York, NY, USA ©2011

URL:

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

This paper seeks to vastly improve the corner finding process by combining the corner finding algorithms from five different processes and determining which of the given points are discarded and which should be kept by using a variation of feature subset selection. This algorithm uses sequential floating backward selection (different from SFS - Sequential Forward Selection) and a mean-squared error (abbreviated MSE) to find the best subset of corners that are then used to identify the corners themselves. This combination reaches an all-or-nothing accuracy of 0.926.

Corner finding, also known as "segmentation", "fragmentation", or "cusp detection", is a vital aspect of sketch recognition. As the "segmentation" name may imply, it allows an algorithm to divide one polyline into a varying amounts of straight lines, which can easily be recognized and processed individually. From there, it is feasible to recognize lines, arcs, curves, ellipses, spirals, and helices. Existing corner finding algorithms focus on one technique, such as curvature detection or a combination of speed and curvature. There exist considerable drawbacks for each technique, however: over-segmentation (finding too many corners), under-segmentation (finding too few corners) and incorrect segmentation (finding the wrong corners). Another issue is the use of thresholds, which are typically calculated empirically but are far less flexible than data that can be trained onto the system. The paper recognizes the "No Free Lunch" theorem, where the increased focus of an algorithm into a particular area means that the algorithm will lose just as much focus (and performance) in a different area. The basic concept of this paper is that by combining the five major corner recognition algorithms, the shortcomings of one of these recognizers can be mitigated by the focus of the next.

The five segmenters that are used are ShortStraw, Douglas-Peucker, PaleoSketch, Sezgin's segmentation algorithm, and Kim et. al's. ShortStraw, Douglas-Peucker, and PaleoSketch rely on line tests to determine if a segment between two identified corners is a line, and Sezgin's and Kim's algorithms use multiple-primitive segmenters to split the strokes into lines, curves, and arcs. The results from all of these are combined with duplicates removed. This algorithm then uses a feature subset selection algorithm dubbed the "corner subset selection".

Feature subset selection is a technique to remove unneeded dimensions from the classification process that only contribute noise. In this case, each "feature" is the set of points. If removing a point reduces performance by 1%, we remove it since it is not likely to result in providing useful information. Conversely, if removing a point reduces performance by 20%, it is an important point and thus we preserve it.

This algorithm uses sequential floating backward selection algorithms to sift through the initial corner data, which differs from more traditional sequential forward selection algorithms by allowing the algorithm to  reconsider previously discarded points. Say, for instance, we remove feature Fs, and in the following step we analyze if adding Fs back into the subset will yield better performance. Bookkeeping techniques are employed to mitigate the possibility of adding the same Fs back and forth in subsequent steps, far after it has been proved that Fs is irrelevant to subset.

To determine the performance of the system, the Mean-Squared Error (MSE) is calculated between the stroke segments and an "ideal" shape created by linking the corners. The equation to calculate the MSE is as follows:

Where i is the index of the original stroke, opti is the optimal point that's vertically closest, pi is a point in the original stroke, and N is the number of original points.

To work against the fact that there's likely to be a change in MSE due to the changing of shape scaling, we normalize MSE between the existing i and the next. Overall, using this technique it was found that the overall accuracy was much higher than any of the individual implementations, and this combination was not significant enough in run time to affect performance.

I think that the paper was well presented and explained. I feel the evaluation segment could have been more elaborated upon, but it is possible that user testing was not needed when the accuracy was considered on an all-or-nothing basis.

Sketch Based Interfaces: Early Processing for Sketch Understanding

Bibliographical Information:
Sezgin, Stahovich, Davis. "Sketch Based Interfaces: Early Processing for Sketch Understanding". Proceedings of PUI-2001. NY. 2001. ACM Press.

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

This paper is one of the earlier efforts in attempting to generate corner-finding and curve recognition algorithms. The extended intention of this is to recognize shape primitives in such a way that makes geometric sense: drawn squares are converted into geometric squares that a second system would then be able to understand. This paper describes the multiple processes utilized to recognize freehand sketches.

There are three phases to the approach of "early processing" for sketch recognition: Approximation, Beautification, Basic Recognition.

Approximation
Fits lines and curves into a given set of pixels. Intended to streamline data in such a way that it's easier to identify the geometric properties of a given freehand shape.

The first process in this phase is vertex detection. This essentially is what we refer to as "corner finding" in more modern sketch recognition systems. This paper uses three sources of information to help identify vertices: direction, curvature (change in direction with respect to arc length), and speed data. Interestingly enough, speed data was largely considered irrelevant in basic sketch recognition when it was introduced by Rubine, and Long, in fact, removed it entirely from his modified set of features. This vertex detection process uses the extrema in curvature and speed, and notices that the maxima in curvature and minima of speed are correlated. We cannot, for instance, simply take minima in speed to mean that the user was drawing a corner, even if a typical user typically slows down his or her pen when drawing a corner. There also has to be a change in curvature, or else we would consider any abrupt change in speed, even on straight lines, as a "corner". However, even using both of these attributes at once yields false positives, so the paper uses a technique called "average based filtering" that looks for extrema in portions of curvatures that lie beyond a specified threshold. This threshold is based on the mean of each data set. These thresholds help us separate the data into regions that we can then use local and global maxima/minima on to identify which of these are false positives. These thresholds are applied to the curvature data and speed change. From there, the paper generates hybrid fits that implement these together to identify true positives in vertex detection. To generate hybrid fits, the paper computes vertex certainties, generates a set of hybrid fits, and selects the best fit from the previous two.

Beautification
This is the process in which small alterations to the input sketch are generated. For instance, lines that were clearly meant to be drawn as parallel (e.g. a rectangle) are altered so that they are geometrically parallel. Circles drawn imperfectly are changed to have geometrically accurate diameters. Curves that are a hybrid of these two are approximated as a set of several small geometrically accurate ellipses pieced together to form one large curve. Slopes are determined as a weighted average of the slopes of each segmented section of the shape, to determine the intended slope when the user was drawing it.

Basic Recognition
Objects that can be drawn from the user's input sketch are classified into lines and curves, and then classified further into a set of basic geometric shapes such as ovals, circles, squares, and rectangles. These features are hand-tailored from the given information presented by the paper's algorithm. It uses the segmented sections of the shape divided out by the vertices recognized in the 'approximation' phase, and uses template matching to see if they align with the geometric rules given by the algorithm to classify them as each of the geometric shapes.

To evaluate this system, thirteen students used this system and a Unix tool called Xfig. Xfig is a tool that supports freehand sketching but requires users to indicate which sections of his or her sketch are meant to be straight lines, curves, etc. Users were given the chance to get comfortable with both of the systems, and their experiences were documented with qualitative analyses. The students expressed approval at the automated recognition of this new system, and all but one preferred to use this system than Xfig. Additionally, high-level recognizers were written to classify and beautify additional shapes. The paper also reports to be working toward supporting overtracing.

Overall, this paper I felt provides good information on early efforts given toward vertex recognition, and using them to construct a roughly hierarchical recognition system that would identify curves and lines to eventually generate geometrically-correct shapes. Some of the evaluation, particularly with the user study, was unclear and I felt could be expanded more. For instance, what happened when it generated incorrect sketch analyses to the user? Was the user expected to redraw the shape? Was this shortcoming communicated clearly? How did the user react? The only source of evaluation in the user study was whether they preferred this or Xfig, and whether they would use it again, but there is a significant amount of information that could be discerned from the user experience. Additionally, some of the information given with regards to the algorithm was unclear and required significant explanation to fully understand.

PaleoSketch: Accurate Primitive Sketch Recognition and Beautification

Bibliography Information:
Paulson, Hammond. "PaleoSketch: Accurate Primitive Sketch Recognition and Beautification." IUI '08 Proceedings of the 13th international conference on Intelligent user interfaces. Pages 1-10 . ACM New York, NY, USA 2008.

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

PaleoSketch, a novel low-level shape recognizer, is one of the flagship projects of the Sketch Recognition Lab. It is a recognition and beautification system that recognizes eight primitive shapes as well as combinations of these primitives themselves to achieve recognition rates upwards of 98.56%, as well as beautifying input input sketches to aid in classification at an early level. Much of this success has been brought about due to the inclusion of two new classification features, Normalized Distance between Direction Extremes (NDDE), and Direction Change Ratio (DCR).

To calculate NDDE, the point with the highest change in direction value (highest change of Y over change of X) and the point with the lowest change are recorded. The stroke length between these two points is the divided by the total stroke length, which essentially provides us with the percentage of the stroke that is between these two extremes. Shapes such as arcs have been observed to yield particularly high NDDE values. Polylines with particularly many "spikes" in their shapes, on the other hand, yield lower NDDE values.

DCR is used to telling polylines and curved strokes apart. DCR is similar to NDDE in that it's also used to see whether there are "spikes" in the drawn shape. DCR is the the max change in direction divided by average change in direction. Polylines will typically have very high DCR values, whereas they will have lower NDDE values.

From there, Paleosketch performs varying tests for classification, each with their own guidelines:

• Line Test: 
• Polyline Test
• Ellipse Test
• Circle Test
• Arc Test
• Spiral Test
• Helix Test
• Complex Test

After collecting two sets of data (the first collecting 900 shapes from 10 users for training, and same amount for testing), it was found that the correct-shape interpretation was 99.89%, but only 98.56% was reported as the top interpretation. Polylines accounted for 1.44% of the error. Overall, the results rival those of state-of-the-art, low-level recognizers that do not recognize as many of these primitives. These are promising results, as they can easily be fitted into fitting higher degree complex interpretations.

As previously mentioned, this paper proved to be one of the most important in the Sketch Recognition Lab, as it was the single most accurate and novel implementation of sketch recognition. The implementation of the different tests, and the fact that there's a difference between, for instance, a circle and an ellipse as two different primitives, makes it clear that the classification categories that were considered prior to this paper could stand to have significant improvement.

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

Bibliographical Information:
Paulson, Rajan, Davalos, Gutierrez-Osuna, Hammond. "What!?! No Rubine Features?: Using Geometric-based Features to Produce Normalized Confidence Values for Sketch Recognition." Visual Languages and Human Centric Computing Workshop on Sketch Tools for Diagramming, Herrsching am Ammersee, Germany, September 5, 2008

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

At the time of this paper's publication, there were two main types of recognizers: gesture-based recognizers or geometric-based recognizers. The former focused on a user's input gesture and analyzed it to recognize some low-level shape, but frequently did not analyze the resulting shape itself. The latter would take a single stroke and try to classify it as one set of several different primitives that can then be combined hierarchically to recognize more complex shapes. They both have their individual advantages and disadvantages, and typically their trade-offs would mean that one application would have to ignore the advantages of the other. This paper focuses on creating a combination of the two, resulting in a set of features that largely does not conform to the standards set forth in the Rubine paper.

The paper uses a quadratic classifier that includes the feature sets from geometric and gesture features. With a set that started off at 44 features, 31 of them were geometric based, with the rest being the 13 features proposed by Rubine. Tests were performed on 1800 sketch samples coming from 20 different users. The main goal was to see whether it was possible to create a statistical classifier that would classify single-stroke sketched primitives using both geometric and gestural features. The paper also sought to identify if such a system would produce results at least as good as PaleoSketch's.

Employing a greedy Sequential Forward Selection technique, the team selected a subset of the features. They used 10 folds of SFS, and the best-performing features (mostly anything above 50% accuracy) were chosen (a total of 14).  The paper found that, using only 6 of these features, an accuracy of up to 93% was observed, suggesting these features contained a wealth of information required to correctly classify the vast majority of input data. The most important observation is that only one of the gesture-based features ended up being statistically relevant to the classification (total rotation), which incidentally was also used in PaleoSketch. This suggests that we may be moving beyond the Rubine features that had been previously dominating the sketch recognition discussion.

I found this a valuable paper, mostly because it contextualizes and puts into practice both geometric and gesture-based sketch recognition. By making a practical comparison between the two types that analyzed the classification accuracy of both, the paper was able to provide some much-needed insight into whether Rubine remained closely relevant at this point in time.

Sketch System Principles and Mechanix Feedback

What a Sketch System Should Do:

1. Pressure-based line thickness. Though this is a recent development and is highly dependent on hardware, it greatly enhances the feeling of 
2. Use a stylus as its primary input method. Most touch systems of today use finger touch, but finger paint is an extremely limited subset of all kinds of paper sketching/painting. Stylus sketching is far more reflective of the type of sketching most people do on paper
3. Beautify strokes to appear as seamless as possible. Work to remove any jarring angular changes in sketches resulting from the touchscreen hardware. The more pixelated a sketch looks, the more it breaks the immersion of writing as one would on paper
4. Stroke deletion. Ensure that the system supports deleting entire strokes at a time. Although this does not reflects the realism of writing on actual paper, deleting entire strokes at a time is extremely convenient for anything other than drawing applications. It should at least be an option
5. Zoom in/out, translate. Since touch surfaces are typically smaller than regular pieces of paper (especially true of tablets), the user should be able to zoom in, out, and translate the page across a zoomed in version to better suit the user's preferred comfort of sketch size.
6. Have a non-intrusive interface. Interfaces in sketching is unlike any other kind of system. Features cannot be buried under menus, nor can every feature be listed at once. Features should be smartly presented and removed in such a way that it interferes as little as possible with the actual sketching
7. As big a sketch area as possible. Sketch areas should not stop strictly at the edge of the window. They should be easily and intuitively be resized. Avoid using the "Windows resize arrow" style of resizing, as it does not work well with a stylus or touchscreen.
8. Have a grid, unless it is a drawing application. Most every piece of paper, from regular writing to architecture sketching to mathematical formulas, all have notebook lines or grids to aid the user's writing task. Completely blank pages are only suitable for art drawing and should only be default if the application is intended for that domain
9. Provide ample amounts of stroke size and color options. Users are more creative when given stroke size and color choices, and frequently aid them when sketching for homework or productivity tasks. They are both fun in recreational use and useful in productivity tasks.
10. Simulate the on-paper experience as much as possible. The most successful sketch systems are the ones where a user acclimated to the system "forgets" he or she is writing on a digital surface when sketching or writing. All sketching system should strive for this kind of user experience.

What a Sketch System Should Not Do:

1. Aggressively auto-correct. While some beautification is expected, snapping lines to make them perfectly straight and at predetermined angles 100% of the time is jarring and removes a user's sense of agency.
2. Be laggy. A sketch system should have little to no lag between the user input and the sketch showing. Significant lag can break immersion at best and render the entire application useless at worst. A lag-less system is vital to capturing the illusion of writing on a regular piece of paper
3. Be "heavy". "Heavy" systems, whether in terms of computing power, or in terms of file size when saving sketches, is vastly inefficient and adds a layer of technology-borne burden that otherwise would not exist on regular paper.
4. Write or preserve a "mouse-based" interface. Do not assume that users have access to a mouse to complement their sketching needs, and thus do not use small interface items optimized for mice. Assume that the user will want to reach every last item of the UI through stylus or finger only.
5. Be strict in sketch order. Especially with sketches that are to be analyzed by a system, expecting users to know the order in which sketches should be drawn is highly unintuitive and should be completely avoided.
6. Fault the user for misinterpreted shapes. Nearly everyone is sure that the shapes they draw are "correct". If a stroke is misinterpreted, do not say "you have drawn this incorrectly", or something to that effect, as it is overly antagonistic and isn't in the spirit of free-hand sketching
7. Have the user spend more time on the UI than sketching. Digitized applications can always come with a plethora of options and features, but with sketching, less is more. Sketch systems should not see their users spend more time navigating and "figuring out" the UI than actually sketching.
8. Mix stylus with touch sketching at the same time. If the user is sketching with a stylus, disable all touch-based input and vice versa. Most people rest their hands on the paper when writing, so they do not expect the side of their hand to actually be involved with the writing process.
9. Use pre-determined shapes as a primary method of sketching. Paper sketching does not afford dragging and dropping items as a primary input method. These tasks are far more suited for more traditional, mouse-based systems.
10. Use non-paper backgrounds or patterns. Do not visually model the drawing surface aesthetic as anything other than what a person would reasonably expect to be a writing surface. Avoid the use of unusual colors or patterns that do not in any way resemble a drawing surface. This does not mean all interface should be skeuomorphic, it simply means they should not be so far removed from a writing experience that it is jarring to users.

Improvements for Mechanix:

1. Optimize idle CPU load. The CPU is always being "used" in Mechanix, even during idle time. This greatly drains batteries and runs hardware hot, which in a more tablet-based industry is quickly becoming unacceptable for users.
2. Save student progress on the database. Maintaining saved, partially completed homework assignments locally is not portable. Since the MCX system is online-only, there shouldn't be "I left my homework at home" scenarios of the offline world.
3. Re-think the items displayed on the drop-down menus. Some features are experimental, some antiquated, some buggy. For the user build, we should comb through what is shown on these and remove the ones that aren't intended for a student to use in his or her homework assignment.
4. Alter color palette. Some of the contrasting colors can be rethought to better suit the homework style for MCX. Green-on-white for the description of solved problems, for instance, strains the eyes too much.
5. UI scaling. Although this is a big task, most computers having a wide range of resolutions among them means Mechanix should implement UI scaling to preserve the user experience. Users with lower resolutions have considerably more trouble with much smaller sketching areas.

Visual Similarity of Pen Gestures

Bibliographical Information:
Long, Landay, Rowe, Michiels. "Visual Similarity of Pen Gestures." CHI '00 Proceedings of the SIGCHI conference on Human Factors in Computing Systems. Pages 360-367. ACM New York, NY, USA

URL:
http://dl.acm.org.lib-ezproxy.tamu.edu:2048/citation.cfm?id=332458

This paper provides somewhat of an early look into computational interpretation of sketches. Specifically, the authors gear this research toward one-stroke gestures intended to be used as commands, as was common the year this paper was published. PDA devices with smaller screens relied on one-stroke gestures to perform commands, and while it proved convenient, many felt frustration and confusion when the system failed to interpret their gestures as intended. The paper presents two experiments intended to provide better insight into how humans perceive "similarity" between two gestures. Indeed, one of the more common complaints when a user is presented with a gesture recognition failure is "but my gesture really does look like a triangle!" Providing insight into why and how a human can perceive similarity is what leads to the paper's main motivation, that being the identification of what the paper calls "perceptual similarity", and whether this similarity can be computed empirically. Both experiments involve users being presented with similar shapes, with the user selecting the shape in the set that is the least similar. Computationally, the authors generated a set of gesture features that played the most vital role in determining how something can be perceived as "similar" or "different" based on these responses. The first experiment involved the user picking between a set of three gestures, called triads. All triads were seen exactly once. The second experiment involved three new gesture sets of nine gestures each, with those gestures being the point of comparison. The paper presented a computable model to determine this perceptual similarity, which they found to coordinate with reported similarity with a factor of 0.56. The authors found these results to be encouraging and significant, as a computational model was now possible to help determine what could previously only be a subjective analysis.

The paper provides a good foundation for the concept of perception and what would eventually become geometric recognition. I did find some issues with the fact that none of these gestures compared were drawn by users, but rather picked as shapes from a menu of choices. While the significant reduction in experiment time was important, the task being observed here is one of simple image comparison, which is very different from the actual practice of a user's gesture and how a computer would perceive it. Additionally, even though subjectivity is important to capture, relying on pure subjective analysis between individual users to then generate a computational formula to replicate it would only reflect the differences in perceptions of that particular group at best. However, this paper still did provide a significant first step toward computationally determining similarity as it would be reported by a human being.

Specifying Gestures by Example

Bibliographical Information:
Rubine. "Specifying Gestures by Example." SIGGRAPH '91 Proceedings of the 18th annual conference on Computer graphics and interactive techniques. Pages 329-337. ACM New York, NY, USA.

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

This paper focuses on the discussion of GRANDMA (Gesture Recognizers Automated in a Novel Direct Manipulation Architecture), which is a toolkit for rapidly adding gesture to an interface designed to recognize sketches. At the time of the paper's publication, most sketch templates of gestures to be recognized required careful hand coding and maintenance as more gestures were added. This tool, however, provides a system for the owner of the gesture curator to continue adding new gestures via example. By implementing gesture recognition on a "curator" level, gestures themselves are saved as templates that can then be used identify input from users. This algorithm is considered lightweight enough for implementation as part of the back-end of some larger sketching system. GRANDMA uses a set of 13 features, which analyzes the input of the new template sketches to create classifiers on its own when creating these templates. Some of these include cosine and sine are included to determine the stroke's angle, bounding box, length, duration of the gesture, "sharpness" of the gesture (to help differentiate between, for example, the letters "U" and "V"), among others. These help generate attributes of these sketches that will then be associated as features of said templates.

This paper presents valuable insight into the on-the-fly generation of templates and the associated features. I find the inclusion and simple explanation of each of the mathematical formulas used to identify the features was useful in explaining the simplicity of the system. Indeed, one of the bigger features of the system is the fact that it is lightweight. However, the system was not implemented in a case study, nor was it shown to work in an end application as it was designed to be. It also spoke about some design decisions such as whether to recognize or not recognize ambiguous user input that is likely to be mislabeled, but since the application was not shown to have a "field test" it is unclear if these decisions were useful or based on user data.