Paper Review #10: Combining Corners from Multiple Segmenters

1. Paper Bibliography

• Title: Combining Corners from Multiple Segmenters
• Authors: Aaron Wolin, Martin Field, and Tracy Hammond.
• Publication: Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 2011.

2. Summary

• There are several stroke segmentation algorithms. The algorithm attempts to slice strokes into primitives.  Combine  

Terms

• Feature subset selection
• Sequential floating backward selection(SFBS)
• Mean-squared error(MSE) objective function
• Bookkeepting technique
• Optimal polyline

3. Details

• Previous work
• Corner Subset Selection

• Step 1: Segmenters Used
• Douglas-Peucker
• ShortStraw
• PaleoSketch
• Sezgin
• Kim
• Step 2: Subset Selection
• For dimensionality reduction in pattern classification problems
• Feature = Dimension
• Sequential floating backward selection(SFBS)
• Start with the entire set of feature
• Remove greedy - the least performance
• Add previously removed one - bookkeeping techniques
• Mean-Squared error(MSE)
• Choose which corner to remove 
• Step 3: Training and Testing 
• 
  

4. Evaluation

• Recall
• Traditional accuracy

5. My opinion

Paper Review #9: Sketch Based Interfaces

1. Paper Bibliography

• Title: Sketch Based Interfaces: Early Processing for Sketch Understanding
• Authors: Tevfik Metin Sezgin, Thomas Stahovich, and Randall Davis
• Publication: ACM SIGGRAPH 2006 Courses. ACM, 2006.

2. Summary

• Target: free sketching
• Target Domain: mechanical engineering design
• Purpose: flexibility & easy to use
• Goal: 
• Converting the original digitized pen strokes in a sketch into the intended geometric objects
• Combining multiple sources of knowledge 

3. Definitions

• A single stroke: from mouse-down to mouse up

4. Details

• Free sketching

• The timing of pen motion can be very informative in regard to free sketching.
• There is no fixed shape to be recognized.

early processing of the basic geometry finding corner + new processing finding line & curve

1. Stroke approximation
: approximate a stroke with more compact and abstract description while minimizing error and avoid overfitting

• Vertex detection
  - Corner of a stroke = high local curvature
  - Combining stroke direction, curvature and speed data
  ex) corner: minimal of speed or maxima of the absolute value of curvature
  1) Average based filtering: Rule out noises(false positives) + variety in angle changes
  - Maxima of curvatures and minima of speed
  - Use thresholds to separate the data into two regions for global extrema
  - Use hybrid fit generation scheme to eliminate false positives
  - The reason why using only curvature data cannot be enough
  
  - The reason why using only speed data cannot be enough
  
  2) Generating hybrid fits
  - Computing vertex certainties
  - Generating a set of hybrid fits
  - Selecting the best fit

• Handling curves: (this is hart part to understand.)

2. Beautification
: make the output visually more appealing without changing its meaning

3. Basic recognition
: interpret the strokes

4. Evaluation

• 13 subjects

5. My opinion

I think this is similar to ShortStraw, but it is much mathematical approach.

Paper Review #8: ShortStraw

1. Paper Bibliography

• Title: ShortStraw: A Simple and Effective Corner Finder for Polylines
• Authors: Aaron Wolin, Brian Eoff, and Tracy Hammond
• Publication: Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling. Eurographics Association, 2008.

2. Summary

• Main step

1. Resampling the points of the stroke
2. Calculating the "straw" distance between the endpoints of a window around each resampled point
3. Taking the points with the minimum straw distance to be corners

• Providing free-sketch recognition
• A stroke is broken down into primitives.
• The primitives can be recognized with high accuracy.
• It is recombined using geometrical rules to allow for recognition of naturally sketched shapes

• Corner finding = splitting a stroke into primitives
• Find the minimum set of points such that, if the polyline is split at those points, the resulting primitives would consist of only lines.

3. Details

• Resampling
• same as $1 recognizer (but interspacing distance of the points is different).
• based on diagonal length of the stroke's bounding box. (reason: various sizes)

Interspacing distance = the diagonal length of the bounding box / constant value

• Increasing the constant val: too noisy 
• Decreasing the constant val: over-smoothed 

• Corner Finding
• Bottom-Up: build corner from primitives
• Set up initial corners
• A corner is based on the length of "straw" (w is a constant window size) 
• Euclidean distance

Straw_i = | P_i - w, P_i + w |

• Straw: short, local minimum
• If Straw_i < threshold(median Straw * 0.95) and is local minimum, it is a corner. 

• Top-Down: insert or delete corners from higher-level pattern
• Find missing corners or false corners
• Adding
• Line test (equality ratio) 

r = chord distance(a,b) / path distance(a,b)

• If r > developer-set threshold(0.95), it is line.
• Removing
• If three corners are collinear, remove the middle one.

4. Experiment & Discussion

• Training data (6 people * 11 shapes * 4 times - 20 errors = 244)
• Compared targets: Sezgin's corner finder, Kim and Kim's
• Measurement: 
• correct corner accuracy(penalty for false negatives) 
• all-or-nothing accuracy(penalty for both false positives and false negatives)

• Complexity
• Resampling points: O(n)
• Calculating the straw for each points(bottom-up): O(n)
• Calculating the median straw length: O(nlogn)
• POST-PROCESS-CORNER(top-down): O(cn)
• To reduce complexity: replace euclidean distance with a squared distance
• Lack of recognizing curvature 

5. My opinion

I was wondered the result of testing circle shape. Probably it might not be suitable for circle shapes because I think that this would cause high complexity. However, it would be much nicer if corner recognition and circle recognition are combined.

Paper Review #7: Gestures without libraries, toolkits or training

1. Paper Bibliography

• Title: Gestures without Libraries, Toolkits or Training- A $1 Recognizer for User Interface Prototypes 
• Authors: Wobbrock, Jacob O., Andrew D. Wilson, and Yang Li
• Publication: Proceedings of the 20th annual ACM symposium on User interface software and technology. ACM, 2007.

2. Summary

• This paper suggest a recognizer called $1 recognizer which is easy simple and powerful. When developing user interface prototype, most people except experts usually need to use user libraries or tools as a gesture recognizer, but sometimes the libraries or tools provided by industries might not enough because the usage of sketch techniques with pen, finger and wand gestures are increased. Although the $1 recognizer is simple, it supports high recognition rate comparing to Dynamic Time Warping and Rubine classifier. 

3. My opinion

    1) Method

• The simple four-step algorithm suggested by the paper is very easy to understand, so it was impressive that $1 recognizer is powerful and the recognition rate of $1 recognizer is same as of more complex recognizers. 

    2) Idea

• This is not sophisticated but simple and powerful. I think it is a great idea that providing easy-to-use gesture recognizer to people who are not experts. 

    3) New research idea

• I do not have a new research idea but I think this idea could be improved if $1 recognizer combined with techniques based on features to classify.