Research
Seminars
Department Series
[an error occurred while processing this directive]
When Did You Decide That? Making Recognition Decisions Explicit Using RSL. |
|
Richard Zanibbi Department of Computer Science Queen's University |
|
The Recognition Strategy Language (RSL) is designed to address three methodological problems in the structural pattern recognition literature: informal algorithm definitions, excessive implementation effort, and inadequate techniques for performance evaluation. All three of these problems are addressed by explicit representation of intermediate recognition decisions and results. RSL is a functional language that defines a recognition algorithm as a sequence of decisions that segment, classify, and relate entities. Each decision has an associated type and function. The type defines a space of alternatives (e.g. defining possible segment compositions), while the function makes the decision (e.g. selecting from the possible segment compositions). On execution, an RSL program automatically records each decision made and updates recognition results appropriately. In this way, book-keeping for recognition results is handled by the language, and not the programmer.
RSL was used to re-implement two published algorithms (those of Handley [1999] and Hu [2001]) that recognize the structure of tables from the spatial arrangement of words and ruling lines located in a document. Among other benefits, the RSL syntax captures formerly implicit properties of the table structure models used by these two algorithms. Also, RSL captures when and how decisions create, reject, and reinstate hypotheses (e.g. for table cells). The effect of individual decisions is unambiguous, which simplifies debugging, permits evaluation of individual decisions and intermediate states, and allows us to observe two new metrics. The first metric is historical recall, the percentage of correct hypotheses generated by an algorithm. The second metric is historical precision, the percentage of correct hypotheses generated. Historical recall and precision take rejected hypotheses into account; in this way, they complement conventional recall and precision, which characterize accepted hypotheses. Through comparing the table cells detected by the RSL re-implementations of the Handley and Hu algorithms, we demonstrate how RSL's book-keeping and historical recall and precision allow evaluation to be both finer grained (e.g. at the level of individual decisions), and more complete.
Richard Zanibbi holds a Ph.D. in Computer Science from Queen's University (Canada). His research interests include pattern recognition, machine learning, and applying software engineering and HCI techniques to improving recognition system design and evaluation. Previously he has worked for the Diagram Recognition and Medical Computing labs at Queen's University, as well as for Legasys and Xerox corporations. Richard is currently a postdoctoral fellow (NSERC) at the Centre for Pattern Recognition and Machine Intelligence (Concordia University, Canada).
[an error occurred while processing this directive]