Reading 24

Reading 24: SketchREADPaperAlvarado, Christine, and Randall Davis. "SketchREAD: a multi-domain sketch recognition engine." Proceedings of the 17th annual ACM symposium on User interface software and technology. ACM, 2004.Publication Link: http://dl.acm.org/citation.cfm?id=1029637

Summary:This paper aims at recognizing freely hand drawn diagram sketches. It uses a hierarchical shape description language to describe shapes in a domain. Definition of a shape has its sub-shapes and constraints. From the description of a shape and domain pattern, a Bayesian network is constructed to indicate causal relationships. While sketch recognition, an interpretation network is also generated. Hypothesis generation has 3 steps:1) Bottom up: As user draws, system parses the strokes into primitives using domain independent recognition toolkit.2) Top down: System re-interprets the strokes and attempts to find missing sub-shapes from partial interpretations3) Pruning: System removes unlikely interpretations

Discussion:It gives examples of a really complicated domain, like physics. This seems really challenging and exciting at the same time. Also the fact that it is multi-domain is really impressive. As it performs stoke parsing while user is drawing, it seems pretty effective

Reading 23

Paper

Rabiner, Lawrence R. "A tutorial on hidden Markov models and selected applications in speech recognition." Proceedings of the IEEE 77.2 (1989): 257-286.

Direct Link: http://www.robots.ox.ac.uk:5000/~vgg/rg/papers/hmm.pdf

Summary:

This paper provides detailed explanation of Hidden Markov Models. It reviews the theory of discrete Markov chains and concept of hidden states. It depicts that observation(which is a fucntion of state) can be used effectively. Example of markov chain with 5 states is discussed along with state transitions. Then the weather example with different possibilities is discussed. Models are represented as doubly embedded stochastic processes in extension to HMMs. Elements of HMM:

1) Number of states in model.

2) Number of distinct observation symbols per state

3) State transition probability distribution function

4) Observation symbol probability distribution state

5) Initial state distribution

HMMs have three issues:

1) How to compute probability of observation sequence, given the model

2) How to choose corresponding state sequence

3) How to adjust the model parameters

Discussion:

This paper looks like a very good tutorial on HMMs, hence justifying its title. But, it seems like a little bit long to analyse it completely!

Reading 22

Reading 22: HMM Recognizer
PaperSezgin, Tevfik Metin, and Randall Davis. "HMM-based efficient sketch recognition." Proceedings of the 10th international conference on Intelligent user interfaces. ACM, 2005.
Publication Link: http://dl.acm.org/citation.cfm?id=1040899

Summary:
This paper has used HMM for recognising strokes. Generally it is done in two steps:
1) Encoding: Sketches are encoded to generate observations using Sketch Processing Toolkit.
2) Segmentation and recognition: Interpretation of a complex scene involves generating hypotheses for the whole scene. For this optimization problem, dynamic programming is used and implemented in the form of shortest path problem. By computing shortest path, the sum of negative likelihoods is minimized i.e. likelihood of observation is maximised.
Discussion:
This paper is very concise and easy to understand. A little bit more information about how the probabilistic models and what an HMM model is, would have proven more helpful. Viewing and analysing sketch as intuitive process is very intuitive and necessary.

Reading 21

LADDER

Paper:

Hammond, Tracy, and Randall Davis. "LADDER, a sketching language for user interface developers." Computers & Graphics 29.4 (2005): 518-532.
Publication Link: http://www.sciencedirect.com/science/article/pii/S0097849305000865

Summary:
LADDER  is a symbolic language to describe how shapes are drawn. The definition of shape has the following parts: List of components, Geometric constraints, Set of aliases, Editing behavior, Display methods. It also creates an abstract behavior as in an abstract class, which is very easy to extend. Some primitive shapes are already defined like path, line, arc etc. Sample constraints are leftOf, horizontal, centeredBelow etc. Vectors are maintained for variable number of components in a shape. 
For primitive shape recognition, low-level recognition is performed on the stroke. If it does not provide correct interpretation, domain recognizer will never be able to recognize it. For domain shape recognition, Jess rule is defined to recognize the shape. It is then passed through a constraint solver.


Discussion:
The idea of creating a symbolic language to describe the process of drawing shape is very amazing. It presents a novel idea of creating an abstract behavior as in an abstract class, which is very easy to extend. 

Reading 20

Multi Stroke primitives

Paper

Hammond, Tracy, and Brandon Paulson. "Recognizing sketched multistroke primitives." ACM Transactions on Interactive Intelligent Systems (TiiS) 1.1 (2011): 4.

Publication Link: http://dl.acm.org/citation.cfm?id=2030369

Summary

This paper uses 5 steps in its implementation:

1) Graph Building: This step constructs the graph of spatially close strokes. Also, it adds the edges in graph which were originally connected in stroke. It checks for Euclidean distance divided by stroke length < 0.1 and Euclidean distance divided by average width of bounding box < 0.15 as thresholds.

2) Graph Searching: It checks for Strongly Connected components in graph. It uses Tarjan's algorithm which is a DFS algorithm running in linear time. 

3) Stroke Merging: It generates a ranking of graphs based on number of nodes present. Then it greedily iterates through list of possible merges. There can two issues: The order in which stroke is drawn and the connection of end points of two different strokes.

4) False Positive Removal: It follows 5 principles: Avoid complexity, Shapes should maintain constant linearity, Minimal effect of touch-up strokes, Continuation should maintain consistency and complexity, Impose confidence constraints on shapes.

5) Arrow Detection: It loops through the polylines formed and checks if endpoints of stroke is any way near to it. 

Discussion

The idea of even primitive strokes being drawn as multistroke was quite shocking. Some of the user results are very surprising, like some very simple primitive shapes being drawn as multi stroke whilst complex shapes being drawn as single stroke. In this case, this kind of user data has a huge impact I believe. 

Reading 19

PaperLi, Wenzhe, and Tracy Anne Hammond. "Recognizing text through sound alone." Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.
Direct Link: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/download/3791/4119

Summary

 This paper presents a sound based algorithm for recognizing sketch. It is able to recognize 26 English alphabets. The main steps are

1) Noise Reduction : It performs two types of Endpoint noise removal. First by taking signal energy f first 150 ms and it represents noise. Each 45 ms frame is then calculated for mean energy. Other one calculates Gaussian probability function for the first 200 ms and then obtain parameters. If at least half of all the segments within the frame are valid, it is marked as valid else marked as silence. 

2) Normalization : Mean amplitude 

3) Feature extraction: Mean amplitudde, each frame is taken at 45 ms and size as 30 ms, along with overlapping. MFCC convert the fourier transform to logs of powers and then again back to signal.

3) Template matching: It uses dynamic time warping to calculate distance between query and template.

Discussion

This paper presents a very unique and innovative idea of using sound as a medium for recognizing sketches. This method if combined with other recognizers can be used for getting some good results. A little more explanation on what the feature set is, would have been better for understanding.

Reading 18

Geometry Review:

Citation:

Paper copy only

Summary:

This book chapter provides a summary of all the useful mathematical formulas we have learnt so far in the course. It talks about cosine formula and parallelograms. It also talks about determinant, cofactor and adjoint matrices. It touches on relationship between polygons and matrices also.

Discussion:

The chapter is a good way to brush up all the formulae. It has been formulated in a way which is very easy to understand. 

Reading 17

Citation:

Paulson, Brandon, and Tracy Hammond. "PaleoSketch: accurate primitive sketch recognition and beautification." Proceedings of the 13th international conference on Intelligent user interfaces. ACM, 2008.Publication Link:http://dl.acm.org/citation.cfm?id=1378775

Summary:

This paper aims to recognize low level primitves and then hierarchically construct higher level shapes. As part of pre-recognition this paper has introduced two features: NDDE and DCR. NDDE is calculated as (stroke length between highest and lowest direction points/Total stroke length). DCR is calculated as (maximum change in direction/Average change in direction). NDDE is higher for curves and lower for polylines. This is vice versa for DCR. 

The algorithm determines whether stroke is overtraced or not by computing total number of revolutions the stroke makes diving by 2π. It performs recognition for following shapes:

1) Line

2) Polyline

3) Ellipse

4) Circle

5) Arc

6)Spiral

7) Helix

8) Complex shape

It also assigns hierarchy for all these shapes where it assigns rank for the primitive shapes. Rank of line is 1, arc is 3 and all others have rank of 5. Algorithm suggests the shape with lowest rank.

Discussion:

This paper introduces a lot of threshold values without providing any insight on how they have been derived. The number of threshold values should have been either less, or explained more about. Correct shapes were determined 99.89% of times, which is pretty impressive. Integration with LADDER could have been given more explanation.

Reading 16

Citation:

Wolin, Aaron, Martin Field, and Tracy Hammond. "Combining corners from multiple segmenters." Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 2011.

Publication Link: http://dl.acm.org/citation.cfm?id=2021185

Summary:

This paper combines polyline corner results from different segmenters by using a variation of feature subset selection. It overcomes the drawbacks that individual segmentation algorithms have. It has two steps in corner subset selection: Segmenters used and subset selection. It uses a cmbination of 5 segmenation algorithms. 

In subset selection, tt starts with all the vertices found from all five algorithms. Then at each step, it removes one corner which affects the mean squared error the least . It is done by the Floating backwards selection technique. It also does bookeeping and thus checks for previously removed corners also. Terminates when only two corners are left and the elbow point is the optimal number of vertices. We have a threshold set for the elbow point. Then training and testing are performed on the median values instead of the mean values. This is done because mean values for gaussian were having large fluctuations.

Why not start with all points? All points initally have MSE to be 0.0 aand then after removing each corner, it gives large spikes in the data. Thus, no appropriate threshold could be found.

Discussion:

This paper gives promising result as All-or-nothing accuracy is concerned. I do not understand the need of going till the two points, as if elbow point occurs before we can just stop there. This is because there is only one elbow point in the MSE curve. What will happen if we start from zero corners and then add corners from each segmenter is also a way to explore.

Reading 15

CITATION

Xiong, Yiyan, and Joseph J. LaViola Jr.

Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 2009.

Publication Link: http://dl.acm.org/citation.cfm?id=1572759

SUMMARY:

This paper first presents a summary and shortcomings of Shortstraw implementation. It lists 6 limitations in shortstraw and fixes them:

1) First three and last three points do not have straw values in shortstraw. The first two and last two are defined here.

2) Lack of timing and speed information in shortstraw. Istraw takes timing data and resamples the whole stroke.

3) Unreliable triplet collinear check. It reduces the chances of missed correct corner in Istraw. It does so by having two passes.

4) Fix threshold. The threshold is dynamic and is dependent on stroke length.

5) Noise: It avoids noise due to sharp angles.

6) No curve detection. It introduces curve detection by taking the difference between two different resampled points. 14-33 angle difference is taken as corner.

After all these improvements, the time complexity is still the same which is O(M+N^2+C).

DISCUSSION:

The results are very impressive and the results are surely very much more improved than the shortstraw implementation. Overall I just feel that threshold and the angle values, if varied rather than kept constant can create bigger impacts.

Reading 14

Citation:

Wolin, Aaron, Brian Eoff, and Tracy Hammond Proceeding SBM'08 Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling

Link:http://dl.acm.org/citation.cfm?id=2386301.2386308&coll=DL&dl=GUIDE&CFID=550427120&CFTOKEN=14778671

Summary:

This algorithm is a very efficient algorithm for corner finding. The very first step is to re-sample the points. The re-sampling distance is calculated from the length of the bounding box diagonal divided by 40. The next steps involve two approaches- bottom up and top down. It also defines concept of straw which seems very intuitive.

The bottom up approach uses straws to calculate the distance between points pi-w and pi+w where w is a constant window defined. It is taken as 3 here. The median of all straw lengths is taken. A threshold value on straw distances is defined for classifying corners. It is empirically chosen to be as median*0.95.

Next step is Top down approach. It removes false positives and missing corners. A line test is performed to find missing corners. If the ratio of chord distance and total path distance lies below a threshold, then there exists a missed corner between them. If two vertices do not pass a line test, a new vertex is declared at the point where the mid point of two end points is. Also, a collinear test  is performed between every three points. If the test passes, the center point is removed.

Discussion:

The best thing about this paper is its simplicity and the intuitive idea of using straws. I believe this idea comes straight from geometry and hence very easy to follow. The fixed window size if varied, I think can produce better results in case of corner finding as the space between the straws will increase when we move away from a corner much faster than when we move away from a line.

Reading 13

CITATION

Bo Yu, Shijie Cai

GRAPHITE '03 Proceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia

Publication Link: http://dl.acm.org/citation.cfm?id=604499

Summary:

This paper allows the users to draw in a very natural way. The process is divided into two steps: imprecise stroke approximation and post-process. In imprecise stroke approximation, it divides the work in four steps: Vertex detection, Line segment approximation, curve approximation and self-Intersection strokes. The feature area here can be calculated here to a line, to a point or to an arc. The vertex detection and primitive shape approximation is divided into an incremental procedure. Feature area verification is done while identifying line segment, Curves are identified with help of their direction graph and the value of slope. It follows two heuristic rules: simpler is better and specific is better.

Post process involves simple relation retrieval, cleanup and basic object recognition. It eliminates false noisy elements. It specifies the rules for identifying whether or not to remove  or shorten or merge a line/arc,

Discussion:

The method provides good accuracy for polylines and primitive shapes, but the accuracy drops very much while dealing with hybrid shapes. I like the fact that the system and metrices used are easy to follow and use.

Reading 12

Sketch based interfaces: early processing for sketch understanding

Paper

Sezgin, Tevfik Metin, Thomas Stahovich, and Randall Davis. "Sketch based interfaces: early processing for sketch understanding." ACM SIGGRAPH 2006 Courses. ACM, 2006.

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

Summary:

In this paper, the authors are using following three phases: approximation, beautification and basic recognition. In Stroke approximation phase, vertex detection is performed first. Vertices can be detected by either speed minima or maxima of curvature. Using only one of them does not provide accurate results and thus we use average based filtering. Extremas in those portions are looked for threshold values(mean in curvature and 90% of mean in speed data). We generate a hybrid fir based on the data. 

Noise and variety in angle changes, both pose a problem on the credibility of a single data. Using only speed, vertices might be missed and just using curvature data, extra vertices may be counted. Hybrid fit is generated by intersection of both points and then point from each is added to see which point leads to lesser OSDQ error value. For curves, ratio of Euclidean distance and arc length is used. The curve is recursively subdivided in the middle. Next steps are beautification and Basic object recognition.

Discussion:

The paper could have discussed more about how the values of threshold are calculated and why the 90% is chosen in case of speed data. The idea of using minimal feature set i.e only two (speed and curvature) is very promising

Reading 11

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

Citation:

Paulson, Brandon, et al. "What!?! no Rubine features?: using geometric-based features to produce normalized confidence values for sketch recognition." HCC Workshop: Sketch Tools for Diagramming. 2008.

Link: https://www.cs.auckland.ac.nz/research/conferences/skekchws/proceedings/vlhcc_stws_p57.pdf

Summary:

This paper proposes a hybrid approach combining two aspects of sketch recognition: Gesture based and Geometric based recognition. It also uses a statistical classifier which is quadratic classifier and combines feature set from both the recognition methods. It initially had 44 features: 33 from geometric based and 11 Rubine features. The classifiers were trained offline and the dataset contained 1800 sketches. Subsets were selected based on greedy sequential forward selection. The results show that optimal features show highest accuracy. These happen to be 14 optimal features from geometric based and only one Rubine feature.

Discussion:

It came as a surprise that only one Rubine feature could perform close to 14 geometric features. I think if this is the ratio of efficiency in recognition, there should be more experiments done for geometric features. Also, the surprising part is that some of the important seeming Rubine features like stroke length, sine cosine did not even make it to the top 15. I think there should be some evidences for extending the experiments to some more classes.

Reading 10

Visual Similarity of Pen Gestures

Citation:

Long Jr, A. Chris, et al. "Visual similarity of pen gestures." Proceedings of the SIGCHI conference on Human Factors in Computing Systems. ACM, 2000.

Publication Link: http://dl.acm.org/citation.cfm?id=332458

Summary:

Multidimensional scaling is used for reducing the dimensionality so that the matrices can visualized better for similarity. Regression analysis is done to find out which dimension represents what. 22 features were used to identify gestures, 11 of which were inherited from Rubine. 

This paper suggests that aspect is much more powerful than length and width of bounding box diagonal. The impact it creates is much higher. Also, the length and arc of shape have much lower impact. The log of aspect creates more sense than log because the values are normalized and easy to visualize for differences. 

Density metric is used for differentiating between coloring and scribbling. The curviness is measured with a threshold angle of 19 degree, which is got by summing small difference in angles.

Discussion:

I found the observation that log creates a better perception very intuitive. It certainly eases the comparison between two similar looking figures. Also, the selection of 19 degrees for the value f curviness could be explained a little bit more.