Analogical retrieval of symbols from a symbol database

Problem

For computers to understand diagrams as we do, they must be able to identify individual symbols as they are drawn. In our prior research, we've explored two very different techniques that handle this problem. For this mini-project, we'll ask you to explore a third technique -- symbol identification via analogical retrieval.

Background

Our previous work [1,2,3] on identifying symbols in military diagrams used the following techniques: 1) a rule-based domain theory that determined the symbol type using characteristic low-level visual features, and 2)  a multi-modal interface that allowed the user to name or  characterize a glyph as it was drawn.  Both of these techniques have their uses. However, neither is particularly adept at identifying symbols that are ambiguous or incomplete. A third technique that addresses this issue is to use a similarity metric to retrieve candidate interpretations for a symbol.  Given a drawn symbol, we can compare that symbol to a library of symbols that are used in that domain. We then use the closest fit (perhaps with tweaking or verification if the fit is not strong).

Deliverables

• Create a database of visual symbols using the XFig or JFig drawing tools.  A symbol set will be provided by the sponsor.
• Use the GeoRep system [4] to create a set of predicate calculus descriptions for these symbols. This will involve tweaking an existing ruleset.
• Finally, use the MAC/FAC analogical retrieval engine [5], find the closest-fitting symbols for a test set of symbols.

A research notebook covering the three-week project will be turned in to the sponsor.  The notebook should include notes on the papers read, research directions considered, and results obtained.

References (Available from sponsor)

      [1]   Forbus, K. D., Ferguson, R. W., & Usher, J. M. (2000). Boundary-based multimodal input for geographic planning sketches. In P. Healy (Ed.), Proceedings of the First International Workshop on Interactive Graphical Communication . London: Queen Mary College, University of London.

      [2]   Ferguson, R. W., Rasch, R. A. J., Turmel, W., & Forbus, K. D. (2000). Qualitative spatial interpretation of Course-of-Action diagrams, Proceedings of the 14th International Workshop on Qualitative Reasoning . Morelia, Mexico.

      [3]   Forbus, K. D., Ferguson, R. W., & Usher, J. M. (2000). Towards a computational model of sketching, Proceedings of the International Conference on Intelligent User Interfaces . Sante Fe, New Mexico.

      [4]   Ferguson, R. W., & Forbus, K. D. (2000). GeoRep: A flexible tool for spatial representation of line drawings, Proceedings of the 18th National Conference on Artificial Intelligence. Austin, Texas: AAAI Press.

      [5]   Forbus, K. D., D. Gentner, et al. (1995). MAC/FAC: A model of similarity-based retrieval. Cognitive Science, 19(2): 144-206.