ShortStraw: A Simple and Effective Corner Finder for Polylines

ShortStraw: A Simple and Effective Corner Finder for

Polylines

A. Wolin, B. Eoff, and T. Hammond

Texas A&M University

Department of Computer Science

College Station, TX 77843-3112

Howdy!

             In this blog post, I will give a brief summary of the algorithm presented in the above mentioned paper and state my opinion on it.

             The authors propose a novel method to find corners in a poly- line. Their method is very simple, easy to implement and highly accurate. For different sets of stroke points, the Euclidean distance (straw) between the start and end points is calculated and the shortest straws indicate a corner. Following is a description of the algorithm:

The stroke points are resampled using a specific algorithm. The distance between two points is calculated as the length of the diagonal of the bounding box divided by 40, 40 being an empirical constant. If this constant is increased, it causes noise while if the constant is decreased, it causes over- smoothing of the stroke. Using the following algorithm, the corners are determined:

The main algorithm terminates when i > |points|. To remove false positives, pairs of consecutive corners are tested for a line test (ratio of Euclidean distance between start and end points and path distance between start and end points is greater than 0.95 and close to 1), If they fail the line test, there must be a corner in between themn and that corner is approximated to be the mid- point. Then triplets of consecutive corners are tested to see if they form a line. If they do form a line, the middle corner is a false positive and is removed. 

The algorithm performed really well in the evaluation phase. It outperformed most of the existing algorithms. They use two accuracy measures. The first measure is the number of correctly found corners divided by the number of correct corners a human would perceive. But this doesn't account for false positives. So they use an all- or- nothing measure which means that only the minimum number of corners required to segment the stroke are found.

I like the approach that the authors use. It is simple, fast and easy to implement. Also, the accuracy is very high and so the algorithm can be used by people who don't have a background in advanced math too.

I used the following sources for this blog post:

[1] Proceeding. SBM'08 Proceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling. Pages 33-40. Eurographics Association Aire-la-Ville, Switzerland, Switzerland ©2008

Thanks for reading my blog! Have a great and blessed day!

Gig'em!!!

A Domain-Independent System for Sketch Recognition

A Domain-Independent System for Sketch Recognition

Bo Yu, Shijie Cai

State Key Laboratory of Software Novel Technology, Nanjing University, China

mikeyucn@hotmail.com

Howdy!

             In this blog post, I would like to briefly summarize the above paper and provide my view on it.

             Freehand sketching is one of the most effective way to communicate and in this paper, the authors develop a system that can recognize gestures independent of the domain and give the user freedom from using non- intuitive ways like menus and toolbars. It also allows the user to draw shapes using multiple strokes.

             The system creates a direction and a curvature graph for the input gesture and users various ways to identify the gesture and re- construct it. 

Figure 1

They use various ways to recognize a line, a circle, an arc, an ellipse and other shapes. One of the methods they use is feature area. The system calculates feature area to a line, feature area to a point and feature area to an arc as follows:

Figure 2

The vertices are detected by looking at the sharpest corners of the direction graph. The authors use various methods to eliminate false positives. Once the entire diagram has been identified, the system does post- processing which basically consists of Simple Relation Retrieval, Cleanup and Basic Object Recognition which identifies objects that are independent of the domain. The Cleanup phase (removing useless elements at the beginning and the end of the stroke) has 3 rules:

1.) If a line segment (arc) with at least one extreme point open, i.e. not connected to other elements, is very short compared with the mean length of all the elements in its original stroke, then remove this line segment (arc)

2.) Given one line segment (arc) with each extreme point connected to some other element, ifit is very short compared with its neighbor elements’ length and these two ones are neither symmetrical nor parallel, then shorten this line segment(arc)to its midpoint.

3.) If two line segments (arcs) with similar angles (centers and radii) are connected or overlapped, then merge them into a new one.

The user can select objects by doing a circle gesture around them. There are other commands that the user can provide using gestures:

Figure 3

The evaluation of the system suggests that the users liked the system. I think it's a great idea as it provides good recognition independent of the domain and can be tweaked to suit certain requirements and be made domain- specific.

I used the following sources for this blog post:

[1] Proceeding GRAPHITE '03 Proceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia. Pages 141-146 . ACM New York, NY, USA ©2003

Thanks for reading my blog! Have a great and blessed day!

Gig'em!!!

Sketch Recognition Algorithms for Comparing Complex and Unpredictable Shapes

Sketch Recognition Algorithms for

Comparing Complex and Unpredictable Shapes

Howdy!

             I would like to talk a little bit about the above paper and state my opinion on it.

             The paper talks about a sketch- recognition system Mechanix which can be used to teach statics problems. The system recognized the gesture drawn as a truss or a free body diagram and then recognizes the mechanics behind it. It allows students to draw diagrams as if they are drawing it with pen and paper and then gives them feedback by comparing the student's drawing with the correct one. This helps professors and  TAs teaching classes with a lot of students.

The system uses 3 metrics to compare the user's response with the instructor's stored correct answer: Hausdorff distance, modified Hausdorff distance and Tanimoto co- efficient. Hausdorff distance between two shapes A and B is:

where Pa is the set of points of A and Pb is the set of points of B. Similarly, Db is calculated and the Hausdorff Distance is:

The modified Hausdorff distance is:

From the Hausdorff distance, the probability of the two shaped being similar is calculated as follows:

The constant 20 is chosen as half of the side- length of the bounding box. If P is less than zero, it means that the shapes are really dissimilar and hence it can be treated as a zero probability.

The Tanimoto coefficient is calculated as follows:

nAB is the number of points common to A and B and nA and nB are the number of points in A and B respectively. 

The paper discusses about the methods that they use for truss identification and free body identification. Identifying those two shapes is very important as they form the main component in any such diagram.

Their experiments and results suggest that students like the Mechanix system and they find it helpful. I personally think that this is a very cool design as the instructors can leverage it to compensate for the lack of individual attention to students in huge classes. 

I used the following sources for this blog post:

[1] Proceeding IJCAI'11 Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume Three. Pages 2436-2441. AAAI Press ©2011

Thanks for reading my blog! Have a great and blessed day!

Gig'em!!!

The Word-Gesture Keyboard: Reimagining Keyboard Interaction

The Word-Gesture Keyboard: 

Reimagining Keyboard 

Interaction

Shumin Zhai and per ola Kristensson

Howdy!

             I am going to present a short summary of the above mentioned article and give my opinion on it.

             In the article, the authors talk about a new text- input system that they developed. The name of the system is ShapeWriter. It is a gesture- based text- input system. Instead of entering the text through the conventional keyboard style, the authors present a novel method which relies on word gestures.

Figure 1

             To type in a word, the user needs to make a single- stroke gesture that goes over all the letters in the word. It is demonstrated in the above picture. The stroke features are compared with the word gesture features and the word that has the highest match is returned. The system also returns the k next best matches in case the recognition is not correct. Following equation is used to calculate the probabilities:

where P(G|W) is the probability of gesture G given word W, P(W) is the probability of the word W and P(G) is the probability of the gesture G.

Using Fitts' Law, Index Difficulty (ID) is calculates in bits using the following equations:

where t is the time to go from letter k to letter k+1, D is the distance between letters k and k+1, S is the size of the (k+1)th key and a and b are constants. 

The total time to write a word is:

where N is the number of letters in the word.

It is also possible to input commands by pressing the command key followed by the command shortcut as follows:

Figure 2

The authors have tested the program with many users and the general consensus about the product has been positive. 

I think that the idea of specifying words by gestures is truly amazing and can be very helpful in increasing the text- input speed and accuracy as there is error correction too. There is a big room for making advances in this area. 

I used the following sources for this blog post:

[1] Magazine. Communications of the ACM CACM Homepage archive. Volume 55 Issue 9, September 2012. Pages 91-101. ACM New York, NY, USA

Thanks for reading my blog! Have a great and blessed day!

Gig'em!!!