Parsing adjacency grammars for calligraphic interfaces
Joaquim Armando Jorge · 1996
Integration of pen input into interactive environments holds the promise of gains in user-friendliness and more natural interaction styles than present direct manipulation tools can provide, since handwritten gestures and pen strokes offer more expressive power than the keyboard or mouse. However, pen-based applications have yet to enjoy widespread acceptance, because pen data are difficult to analyze due to noise, user variations and imprecise meaning. Calligraphic interfaces is a term we have coined to designate a class of pen-based user interfaces in which hand-sketching or drawing serves as the main organizational metaphor, as opposed to the point-and-click desktop metaphor commonly employed in current graphical user interfaces (even those which support some pen-based interaction). Our study of calligraphic interfaces extends previous research in formal visual languages, syntactic pattern recognition, and user interface design. We define relational adjacency grammars, which make it possible to develop efficient off-line parsing algorithms for a large family of visual languages for depicting diagrams. Our adjacency-driven parsing approach improves on previous research, by using adjacency-constraining relations to prune the search space during intermediate analysis steps, thereby yielding gains in asymptotic complexity. Fuzzy relational adjacency grammars are then considered as a means to add the expressive power of fuzzy logic, so as to deal with imprecise and uncertain data in the calligraphic interface. We develop novel incremental parsing algorithms which can handle partial sentences and erroneous or unrecognized items. Fuzzy template matching is the core technique of our stroke recognizer, which classifies atomic gestures and symbols. Finally, this recognizer is coupled to a parser-generator, to provide an environment for developing calligraphic interfaces.