Paper Review #14: Using Entropy to Distinguish Shape Versus Text in Hand-Drawn Diagrams

1. Paper Bibliography

• Title: Using Entropy to Distinguish Shape Versus Text in Hand-Drawn Diagrams

• Authors: Bhat, Akshay, and Tracy Hammond. 

• Publication: IJCAI. Vol. 9. 2009.

2. Summary

• Distinguish between shapes and texts 
• Text has higher entropy rate than shapes
•  Entropy rate = distinguishing factor
• Using only the entropy rate, a correct classification rate is 92.06%
• Favorable performance without training data

3. Terminology

• Entropy rate: accurate criterion of classification

4. Details

• Entropy
• Each point in a stroke is assigned a symbol based on the angle (corresponding angle in the Table 1)

In this figure, text has various symbol compared to rectangle.

• This symbol is the random variable on the basis of which we can calculate entropy.

• Use a zero-order entropy
• each symbol's probability of occurrence is determined independent of the previous symbols.
• Define an entropy model 'alphabet'
• Implementation
• Stroke Grouping
• A spatial and temporal threshold
• The successful rate: 99.78%
• After groping
• Resample 
• Transform each stroke into a string of symbols
• Calculate the percentage of the occurrence of symbols
• Classification
• Confidence Measure
• in order to integrate a classifier into other sketch recognition 
• Data collecting and Testing

5. Evaluation

Paper Review #13: SketchREAD

1. Paper Bibliography

• Title: SketchREAD: A Multi-Domain Sketch Recognition Engine

• Authors: Alvarado, Christine, and Randall Davis.

• Publication: Proceedings of the 17th annual ACM symposium on User interface software and technology. ACM, 2004.

2. Summary

• Provide structure description of the shapes in a certain domain (No training data or programming is necessary.)
• Context
• Guide the search for possible interpretations
• Reclassify low-level shapes
• Effect:
• Reduce recognition errors 
• Robustness to ambiguity and uncertainty inherent in complex, freely-drawn sketches
• Bayesian network
• Use a novel form of dynamically constructed Bayesian networks to evaluate these interpretation
• Effect:
• Recover from low-level recognition level
• Target domains: family trees and circuit diagram

3. Terminology

• Interpretation
• Hypothesis

4. Details

• The description of a shape

• Recognition
• Problem
• Real-time system -> Noise -> low-level misinterpretation -> higher-level interpretation fail
• Guarantee all interpretation -> exponential cases
• Solution
• Bottom-up recognition
• Generate most likely interpretation first
• Top-down
• Seek out missing interpretations
• Bayesian Network
• Evaluate partial interpretation hypotheses 
• Expand the hypothesis space by exploring the most likely interpretation first
• Hypothesis Evaluation
• A directed acyclic graph
• Which factors influence each other
• A set of conditional probability distributions
• How these factors influence one another
• Hypothesis Generation
• Top-down, Bottom-up, Pruning
• Selecting an Interpretation

5. Evaluation

• Circuit diagram is longer than family tree.

Paper Review #12: HMM-Based Efficient Sketch Recognition

1. Paper Bibliography

• Title: HMM-Based Efficient Sketch Recognition

• Authors: Sezgin, Tevfik Metin, and Randall Davis.

• Publication: Proceedings of the 10th international conference on Intelligent user interfaces. ACM, 2005.

2. Summary

• How viewing sketching as an interactive process
• User study: People have preferred ways of drawing in certain domain.
• Contribution
• Polynomial time algorithm for sketch recognition and segmentation
• Efficient sketch recognition, segmentation and classification

3. Terminology

• Segmentation: Grouping strokes which constitutes the same object
• Classification: Determining which object each group of strokes represent
• Labeling: Assigning labels to components of a recognized object

4. Details

• Capture an individual's preferred stroke ordering 
• Vertical, Horizontal, Positive slope and Negative slope
• sketching = incremental & interactive process
• Viterbi: Compute the best sequence of HMM state transition for generating O
• Baum-Welch algorithm: Estimate HMM parameter (probabilities of transition, observation and start)
• Encoding
• convert strokes into geometric primitives
• Modeling with fixed input length HMMs
• Modeling using HMMs with variable length training data

5. Evaluation

• Evaluation of the HMM-based recognition with real data
• Fixed length & Variable length (slightly better)
• Running time comparison to a baseline method
• Baseline: feature-based recognizer

Paper Review #11: A Tutorial on Hidden Markov Models and Selected Application in Speech Recognition

1. Paper Bibliography

• Title: iscrete Markov Processes A Tutorial on Hidden Markov Models and Selected Application in Speech Recognition

• Authors: Rabiner, Lawrence

• Publication: Proceedings of the IEEE 77.2 (1989): 257-286.

2. Summary

• Statistical methods of Markov source / Hidden Markov modeling
• rich in mathematical structure; the theoretical basis for use in a wide range of applications
• work well in practice (applied properly)
• Review paper
• Review paper

3. Details

• Discrete Markov Processes
• Extension to Hidden Markov Models
• Elements of an HMM
• The Three Basic Problems for HMMs
• Solutions to the Three Basic Problems of HMMs
• Solution to Problem 1
• Solution to Problem 2
• Solution to Problem 3
• Types of HMMs
• Continuous Observation Densities in HMMs
• Autoregressive HMMs
• Variants on HMM Structures - Null Transitions and Tied States
• Inclusion of Explicit State Duration Density in HMMs
• Optimization Criterion
• Comparison of HMMs
• Implementation Issues for HMMs
• Scaling
• Multiple Observation Sequences
• Initial Estimates of HMM Parameters
• Effects of Insufficient Training Data
• Choice of Model
• Implementation of Speech Recognizers Using HMMs
• Overall Recognition System
• Isolated Word Recognition
• LPC Feature Analysis
• Vector Quantization
• Choice of Model Parameters
• Segmental k-Means Segmentation into States
• Incorporation of State Duration into the HMM
• HMM Performance on Isolated Word Recognition
• Connected Word Recognition Using HMMs
• Connected Digit Recognition from Word HMMs Using Level Building
• Level Building on HMMs
• Training the Word Models
• Duration Modeling for Connected Digits
• Performance of the Connected Digit HMM Recognizer
• HMMs for Large Vocabulary Speech Recognition
• Limitations of HMMs

With HMM, an advanced process
Foward chaining + Backward chaining = Viterbi
1. Evaluation problem: calculating probability (F + B)
2. Decoding Problem: given a sequence observation what is most likely hidden data
3. Training Problem: Baum Welch

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.