8 Mart 2009 Pazar

Symbol Recognintion with Kernel Density Matching

Wan Zhang,Liu Wenyin and Kun Zhang

This paper proposes a new statistical method for symbol recognition. The proposition is similarity measurement of two symbols to satisfy various requests in symbol recognition such as scaling-invariance, etc. A symbol is represented by a 2D joint density estimated from a set of points sampled from the skeleton of the symbol. Matching two symbols is then equivalent to determining whether the two symbols have similar portability distributions. Similarity of two symbols are determined by the Kullback-Leibler (KL) divergence distance. However, this matching is not orientation invariant. So they propose two other methods for determining orientation of the symbol: Angle searching algorithm and independent component analysis (ICA) technique.

For extracting probability distributions Kernel Density Estimator is used (aka Parzen Window Method). And for preprocessing they applied adaptive noise reduction, vectorization of points and uniform length sample points. They also centralized the symbol for zero-mean and applied principal component analysis (PCA) in order to make the symbol representations more robust.

To solve the rotation problem they tried two methods searching and ICA. Searching algorithm was searching the orientation which resulted with least KL divergence which was very time consuming. So they proposed a second ICA method which works faster. ICA's property is that outputs don not change even if some components of the original data are multiplied by a nonzero constant, or data are rotated.

Experiments conducted of proposed method were on GREC 2003 and 2005 datasets. These datasets include rotated and noise added symbols. The results on GREC dataset are impressive and successful. This method might the be the best method for this dataset so far.


Proposed technique is designed to be noise invariant and become successful. However, as my focus is on sketch recognition definition of noise in this paper doesn't relates to the different drawings in sketch recognition as it is not just some random samples and points. For sketch recognition a flexible technique is required rather than noise independent.

2 Mart 2009 Pazartesi

Interaction techniques for ambiguity resolution in recognition-based interfaces

Jennifer MAnkoff, Scott E. Hudson, Gregory D. Abowd [Georgia Institute of Technology Carnegie Mellon University]

Paper briefly presents a survey of existing error correction techniques in the user interface. These 'mediation' techniques most commonly fall in to one of the two strategies, repetition and choice. Paper calls them 'mediators' because they are mediate between the user and computer to specify the correct interpretation of the user's input. Mediation techniques then serve to resolve ambiguity of possible interpretations of user input, helping to determine which of those potential interpretations is the one user intended.
Paper lists programs that resolve ambiguity and says that they do not go ahead of choice or repetition techniques. So the purpose of this paper is to introduce four new mediation techniques other than choice and repetition.
1. Adding alternatives to choice mediators: Extending the basic n-best list choice mediator, by enabling users to control filtering and specify individual characters (ex: selecting only some part of an suggested word from the list), allow users to specify length (ex: user can feed mediator to indicate that users intended word is longer) and allow users to escapce (in case of totally wrong start)
2. Occlusion in choice mediators: Problem is that mediator interactions and user inputs can overlap. What paper suggest is: The mediator repositions all interactors that intersect with its suggestions so as to remove any occlusion.
3. Target Ambiguity: Target ambiguity arises when the target of the user's input is uncertain. For example selecting word by circling and it can be addressed by treating the mouse an area instead of a point. The magnified area is interactive and users can click on interactors inside it just as an unmagnified portion of the screen.
4. Errors of Omission: This error occurs when some or all of the user's inpout is not interpreted at all by the recognizer. Paper address this with guieded re-recognition. The user can re initiate re-recognition by specifiying a segment that should have been recognized. By doing so, the user is giving system an important new information.

Paper address problems of common recognition systems and makes a good separation of mediators from recognizers. Also each proposed mediator offer and address a problem in mediating techniques. As all recognizers are error prone, the methods described are useful while designing a recognition system. However, first method (adding alternatives) makes a more important point than others because other techniques seem to be specific for some domains, especially in Occlusion and Target Ambiguity.

Auto-completion for Diagram Editors Basedn on Graph Grammers

Steffen Mazanek,Sonja Maier, Mark Minas Universitat der Bundeswehr, Germany

The syntax or a particular visual language can be defined by means of a graph grammar. In an usual way of diagram editors,a diagram template is chosen and then empty texts are filled accordingly. However, the purpose of this paper is not selecting pre-defined template from editor but to enable editor to auto-complete diagram according to diagrams grammar.

For a given graph H and Hyper-Edge Replacement Grammar (HRG) G, H is first parsed into hyper-edges and nodes. A completion of H with respect to G is graph H' that again belongs to language G. To form H' there could be 2 types of modifications:
1.Inserting a new edge into H,
2. Connecting nodes of H.

Auto-completion of graphs are done as follows:
1. A spatial relationship hyper-graph(SRHG) is formed by neighbourhood relations within graph.
2. Sending this information to parser. Parser connects edges and forms a new graph.
3. If user asks for assistance and indicates desired size of completion.
4. It computes all possible graph completions up to the used defined size.
5. Selected graph is send to step 1.

The graph parser used in this paper is uses dynamic-programming techniques similar to Coke, Youngger and Kasami algorithm. In order to layout the graphs an constraint satisfactory problem technique is used.


Although paper accomplishes its target to complete graph, their proposition is not a very smart way of doing it. While taking assistance, offering all possible graphs is not very intelligent. Also, in order to add another node to the graph, user has to specify nodes to add. I don't think that this paper is relevant to topic of auto-completion because of these reasons.