Images form a rich information source, which remains underutilized in biomedical document classification. We present here work that uses both image- and text-based features in order to identify articles of interest, in this case, pertaining to cis-regulatory modules in the context of gene-networks. Extending on our new idea, which we have recently introduced, of using OCR-based features to identify DNA contents in images, we combine image and text based classifiers to categorize documents as relevant or irrelevant to cis-regulatory modules. Using a set of hundreds of articles, marked by experts as relevant or irrelevant to cis-regulatory modules, we train/test image and text based classifiers, as well as classifiers integrating both. Our results indicate that the latter show the best performance with Recall, F-measure and Utility measures all above 0.9, demonstrating the significance of incorporating image data, and specifically OCR-based features, into the document categorization process. Moreover, the use of character distribution properties to represent images is directly relevant to other biomedical images containing text (e.g. RNA, proteins). Diagrams and other images containing text are also prevalent outside the biomedical domain, hence the work stands to be applicable and beneficial in other application areas.

Bug localization is the task of determining which source code entities are relevant to a bug report. Manual bug localization is labor intensive since developers must consider thousands of source code entities. Current research builds bug localization classifiers, based on information retrieval models, to locate entities that are textually similar to the bug report. Current research, however, does not consider the effect of classifier configuration, i.e., all the parameter values that specify the behavior of a classifier. As such, the effect of each parameter or which parameter values lead to the best performance is unknown. In this paper, we empirically investigate the effectiveness of a large space of classifier configurations, 3,172 in total. Further, we introduce a framework for combining the results of multiple classifier configurations since classifier combination has shown promise in other domains. Through a detailed case study on over 8,000 bug reports from three large-scale projects, we make two main contributions. First, we show that the parameters of a classifier have a significant impact on its performance. Second, we show that combining multiple classifiers--whether those classifiers are hand-picked or randomly chosen relative to intelligently defined subspaces of classifiers--improves the performance of even the best individual classifiers.

Evaluating mathematical expression recognition involves a complex interaction of input primitives (e.g. pen/finger strokes), recognized symbols, and recognized spatial structure. Existing performance metrics simplify this problem by separating the assessment of spatial structure from the assessment of symbol segmentation and classification. These metrics do not characterize the overall accuracy of a pen-based mathematics recognition, making it difficult to compare math recognition algorithms, and preventing the use of machine learning algorithms requiring a criterion function characterizing overall system performance. To address this problem, we introduce performance metrics that bridge the gap from handwritten strokes to spatial structure. Our metrics are computed using bipartite graphs that represent classification, segmentation and spatial structure at the stroke level. Overall correctness of an expression is measured by counting the number of relabelings of nodes and edges needed to make the bipartite graph for a recognition result match the bipartite graph for ground truth. This metric may also be used with other primitive types (e.g. image pixels).

Studying the evolution of topics (collections of co-occurring words) in a software project is an emerging technique to automatically shed light on how the project is changing over time: which topics are becoming more actively devel-oped, which ones are dying down, or which topics are lately more error-prone and hence require more testing. Existing techniques for modeling the evolution of topics in software projects suffer from issues of data duplication, i.e., when the repository contains multiple copies of the same document, as is the case in source code histories. To address this is-sue, we propose the Diff model, which applies a topic model only to the changes of the documents in each version instead of to the whole document at each version. A comparative study with a state-of-the-art topic evolution model shows that the Diff model can detect more distinct topics as well as more sensitive and accurate topic evolutions, which are both useful for analyzing source code histories.

Topics are collections of words that co-occur frequently in a text corpus. Topics have been found to be effective tools for describing the major themes spanning a corpus. Using such topics to describe the evolution of a software system's source code promises to be extremely useful for development tasks such as maintenance and re-engineering. However, no one has yet examined whether these automatically discovered topics accurately describe the evolution of source code, and thus it is not clear whether topic models are a suitable tool for this task. In this paper, we take a first step towards deter-mining the suitability of topic models in the analysis of software evolution by performing a qualitative case study on 12 releases of JHotDraw, a well studied and documented system. We define and compute various metrics on the identified topics and manually investigate how the metrics evolve over time. We find that topic evolutions are characterizable through spikes and drops in their metric values, and that the large majority of these spikes and drops are indeed caused by actual change activity in the source code. We are thus encouraged by the use of topic models as a tool for analyzing the evolution of software.

Performance evaluation of document recognition systems is a difficult and practically important problem. Issues arise in defining requirements, in characterizing the systempsilas range of inputs and outputs, in interpreting published performance evaluation results, in reproducing performance evaluation experiments, in choosing training and test data, and in selecting performance metrics. We discuss these issues in the context of evaluating systems for recognition of mathematical expressions. Excellent progress has been made in the theory and practice of performance evaluation, but many open problems remain.

The sounds generated by a writing instrument provide a rich and under-utilized source of information for pattern recognition. We examine the feasibility of recognition of handwritten cursive text, exclusively through an analysis of acoustic emissions. Our recognizer uses a template matching approach, with templates and similarity measures derived variously from: raw power signal with fixed resolution, discrete sequence of magnitudes obtained from peaks in the power signal, and ordered tree obtained from a scale space signal representation. Test results are presented for isolated lowercase cursive characters and for whole words. Recognition rates of over 70% (alphabet) and 90% (26 words) are achieved, based solely on acoustic emissions, with samples provided by a single writer. We also present qualitative results for recognizing gestures such as circling, scratch-out, check-marks, and hatching. These preliminary results demonstrate that acoustic emissions are a rich source of information, usable - on their own or in conjunction with image-based featuresi - to solve pattern recognition problems. In future work, this approach can be used in applications such as writer identification, handwriting and gesture-based computer input technology, emotion recognition, and temporal analysis of sketches.

Document recognition involves many kinds of hypotheses: segmentation hypotheses, classification hypotheses, spatial relationship hypotheses, and so on. Many recognition strategies generate valid hypotheses, which are eventually rejected, but current evaluation methods consider only accepted hypotheses. As a result, we have no way to measure errors associated with rejecting valid hypotheses. We propose describing hypothesis generation in more detail, by collecting the complete set of generated hypotheses and computing the recall and precision of this set: we call these the 'historical recall' and 'historical precision.' Using table cell detection examples, we demonstrate how historical recall and precision along with the complete set of generated hypotheses assist in the evaluation, debugging, and design of recognition strategies.

The table recognition literature contains many strategies specified informally as a sequence of operations, obscuring both models of table structure and the effects of individual decisions. Decision making is more transparent in formal model based approaches (e.g. grammar based) but these approaches are less flexible than informal ones. We propose an intermediate level of formalization, defining strategies as a sequence of basic graph transformations that correspond to recognition operations (e.g. classification, segmentation). Transformations are parameterized by logical types and decision functions, which together define structure models and executable strategies for interpreting input graphs. We provide an overview of our first attempt at this intermediate level of formalization, the Recognition Strategy Language (RSL). As a proof of concept, we reimplement two informally specified table recognition strategies from the literature in RSL. The RSL implementations capture descriptions of the formerly implicit table structure models, and automatically capture all decision making.

Handwritten mathematical notation contains ambiguities of various kinds. Here we focus on ambiguity in spatial relationships; in particular, we use fuzzy logic to treat ambiguity in subscript-or-inline and inline-or-superscript spatial relationships. We extend an existing system for recognizing handwritten mathematical notation, adding the capability of producing a ranked list of interpretations rather than a single top-choice interpretation. Fuzzy membership values are assigned to each spatial relationship; a given pair of symbols can have non-zero membership in fuzzy sets subscript and inline, or in fuzzy sets inline and superscript. These fuzzy membership values are combined to produce an overall confidence value for the entire interpretation. We have modified the user interface of our system so that a user can quickly view and select from the ranked interpretations when the highest confidence interpretation is incorrect.

We describe a robust and efficient system for recognizing typeset and handwritten mathematical notation. From a list of symbols with bounding boxes the system analyzes an expression in three successive passes. The Layout Pass constructs a Baseline Structure Tree (BST) describing the two-dimensional arrangement of input symbols. Reading order and operator dominance are used to allow efficient recognition of symbol layout even when symbols deviate greatly from their ideal positions. Next, the Lexical Pass produces a Lexed BST from the initial BST by grouping tokens comprised of multiple input symbols; these include decimal numbers, function names, and symbols comprised of nonoverlapping primitives such as "=". The Lexical Pass also labels vertical structures such as fractions and accents. The Lexed BST is translated into L/sup A/T/sub E/X. Additional processing, necessary for producing output for symbolic algebra systems, is carried out in the Expression Analysis Pass. The Lexed BST is translated into an Operator Tree, which describes the order and scope of operations in the input expression. The tree manipulations used in each pass are represented compactly using tree transformations. The compiler-like architecture of the system allows robust handling of unexpected input, increases the scalability of the system, and provides the groundwork for handling dialects of mathematical notation.

It is quite common in document analysis and symbol recognition to rely on a priori knowledge about the nature of the document in order to locate candidate symbols. It is desirable, but less common, for a segmentation procedure to rely on "a posteriori" feedback from a non-human-guided process to adjust for segmentation errors. For this method to succeed, the feedback must come from a reliable classifier (one that is able to reject negative symbols including miss-segmented symbols). This paper examines the use of positive and negative training data on a nearest-neighbour classifier for hand-drawn geometric shapes. We explore the issues involved in the development of a reliable classifier using this method, and we discuss the trade-off between reliability and correctness.

Unified Modeling Language (UML) diagrams are widely used by software engineers to describe the structure of software systems. Early in the software design cycle, software engineers informally sketch initial UML diagrams on paper or whiteboards. The information provided by these UML diagrams needs to be made available to computer assisted software engineering (CASE) tools. In order to smooth this transition from paper to electronic form, we have developed an online recognition system for UML diagrams. The system accepts input from an electronic whiteboard, a data tablet or a mouse. Efforts have been made to separate the domain-independent and domain-specific parts of the recognition system. The kernel of the system is retargetable, providing a general front end for online recognition of any glyph-based diagram notation. The kernel is extended with UML-specific routines for segmentation, recognition of glyphs, and recognition of glyph relationships.

The structure of mathematics notation is particularly difficult to recognize in handwritten notation because irregular symbol placements are common. We present an efficient and robust method of parsing handwritten and typeset mathematics notation without backtracking. The system is designed to be easily adaptable to various dialects of mathematics notation. The following strategies are used: (1) separate the analysis of layout, syntax, and semantics, (2) recursively apply search functions and image partitioning to recognize dominant and nested baselines, and (3) use tree transformations to express computations in a compact, efficiently executable form.

Diagrams are widely used in society to transmit information such as circuit designs, music, mathematical formulae, architectural plans, and molecular structure. Computers must process diagrams both as images (marks on paper) and as information. A diagram recognizer translates from image to information and a diagram generator translates from information to image. Current technology for diagram generation is ahead of the technology for diagram recognition. Diagram generators have extensive knowledge of notational conventions which relate to readability and aesthetics, whereas current diagram recognizers focus on the hard constraints of the notation. To create a recognizer capable of exploiting layout information, it is expedient to reuse the expertise in existing diagram generators. In particular, we discuss the use of Lime (our editor and generator for music notation) to proofread and correct the raw output of MIDIScan (a third-party commercial recognizer for music notation). Over the past several years, this combination of software has been distributed to thousands of users.

Many software applications require the construction and manipulation of graphs. In standard programming languages, this is accomplished using low-level mechanisms such as pointer manipulation or array indexing. In contrast, graph productions are a convenient high-level visual notation for coding graph modifications. A graph production replaces one subgraph by another subgraph. Graph productions can define a graph grammar and graph language, or can directly transform an input graph into an output graph. Graph transformation has been applied in many areas, including the definition of visual languages and their tools, the construction of software development environments, the definition of constraint programming algorithms, the modeling of distributed systems, and the construction of neural networks. One application is presented in detail: the interpretation of mathematical notation in scanned document images. The graph models the set of mathematical symbols, and their spatial and logical relationships. This graph is transformed by productions written in the PROGRES language. Copyright © 1999 John Wiley & Sons, Ltd.

In image analysis, recognition of the primitives plays an important role. Subsequent analysis is used to interpret the arrangement of primitives. This subsequent analysis must make allowance for errors or ambiguities in the recognition of primitives. In this paper, we assume that the primitive recognizer produces a set of possible interpretations for each primitive. To reduce this primitive-recognition ambiguity, we use contextual information in the image, and apply constraints from the image domain. This process is variously termed constraint satisfaction, labeling or discrete relaxation. Existing methods for discrete relaxation are limited in that they assume a priori knowledge of the neighborhood model: before relaxation begins, the system is told (or can determine) which sets of primitives are related by constraints. These methods do not apply to image domains in which complex analysis is necessary to determine which primitives are related by constraints. For example, in music notation, we must recognize which notes belong to one measure, before it is possible to apply the constraint that the number of beats in the measure should match the time signature. Such constraints can be handled by our graph-rewriting paradigm for discrete relaxation: here neighborhood-construction is interleaved with constraint-application. In applying this approach to the recognition of simple music notation, we use approximately 180 graph-rewriting rules to express notational constraints and semantic-interpretation rules for music notation. The graph rewriting rules express both binary and higher-order notational constraints. As image-interpretation proceeds, increasingly abstract levels of interpretation are assigned to (groups of) primitives. This allows application of higher-level constraints, which can be formulated only after partial interpretation of the image.

N-grams are a well-structured knowledge representation that has proven useful in the recognition of textual documents. In this paper, we propose that n-grams can be extended to the domain of graphical documents as well. This has the advantage of providing a regular, easily-maintainable knowledge representation for local constraints, specifically symbol-interaction knowledge, in the graphical domain. To extend the definition of an n-gram from the textual to the graphical domain, we must resolve how to handle directional considerations, how to treat the variety of relations that can occur between image primitives, and how to treat multiple neighbours. We have implemented a prototype system for the application of n-gram knowledge to the recognition of sketch maps. Early results are encouraging. We look forward to further refining this system. N-grams appear to be a promising tool for representing spatial constraints in a form that is useful to the recognition of graphical documents.

This paper investigates graph rewriting as a tool for high-level recognition of two-dimensional mathematical notation. "High-level recognition" is the process of determining the meaning of a diagram from the output of a symbol recognizer. Characteristic problems of high-level mathematics recognition include: determining the groupings of symbols into recursive subexpressions and resolving ambiguities that depend upon global context. Our graph-rewriting approach uses knowledge of the notational conventions of mathematics, such as operator precedence and operator range, more effectively than syntactic or previous structural methods. Graph rewriting offers a flexible formalism with a strong theoretical foundation for manipulating two-dimensional patterns. It has been shown to be a useful technique for high-level recognition of circuit diagrams and musical scores. By demonstrating a graph-rewriting strategy for mathematics recognition, this paper provides further evidence for graph rewriting as a general tool for diagram recognition, and identifies some of the issues that must be considered as this potential is explored.

Abstract Lime is a music editor, oriented to the production of printed music. A user manipulates the information content of the music notation, while viewing the physical appearance of the notation. To implement this, Lime must perform a complex translation from an abstract musical source representation to a graphical product. Techniques are discussed for providing automation without loss of customizability, for implementing WYSIWYG editing, for supporting multiple products (e.g. orchestral score and parts), and for providing good response time despite a slow translator. Similar design issues are encountered by editors for other types of diagrams, such as schematics, chemical formulas, and maps.

Graph grammars provide a useful formalism for describing structural manipulations of multidimensional data. The authors review briefly theoretical aspects of graph grammars, particularly of the embedding problem, and then summarize graph-grammar applications. Currently graph grammars are used most successfully in application areas other than pattern recognition. Widespread application of graph grammars to picture processing tasks will require research into problems of large-scale grammars, readability of grammars, and grammatical processing of uncertain data.>

A system that recognizes common rhythmic patterns through template matching is described. The use of template matching gives the user the unusual ability to modify the set of templates used for analysis. This modification effects a tradeoff between the temporal accuracy required of the input and the complexity of the recognizable rhythm patterns that happen to be common in a particular piece of music. The evolving implementation of this algorithm has received heavy use over a six-year period and has proven itself as a practical and reliable input method for fast music transcription. It is concluded that templates demonstrably provide the necessary temporal context for accurate rhythm recognition.>

A method is presented for identifying texture elements while simultaneously recovering the orientation of textured surfaces. A multiscale region detector, based on measurements in a Del /sup 2/G (Laplacian-of-Gaussian) scale space, is used to construct a set of candidate texture elements. True elements are selected from the set of candidate elements by finding the planar surface that best predicts the observed areas of the latter. Results are shown for a variety of natural textures, including waves, flowers, rocks, clouds, and dirt clods.>