The bulk of the documents that affect our lives are digital or born digital. Our laborious investigations of layout, script, font and graphics, are turning into mere exercises with little influence on pursuits outside the Document Analysis and Recognition (DAR) community. Recent performance improvements on such tasks, even if based on deep learning and AI , are as much the result of advances in computer hardware as of breakthroughs in document research. It is time to automate tasks beyond transcription. This Commentary addresses our mission, our approach to some technical issues, and the role of AI in DAR. Opportunities for a wider role for document analysis include more pervasive application of statistical decision theory, integrated genre analysis , summarization, interpretation and information extraction, bolder goals in content analysis, and alternative modalities, induced by the open source movement, for sharing research results . Importantly, expanding the scope of our research incurs increased responsibility for retaining human prerogatives in critical decision making and preserving essential human skills like good writing and discriminative reading.

Individuals, institutions and even cities and countries are often ranked according to some linear weighting of their attributes. Under commonly prevailing conditions, it is possible to find weights that give top rank to most arbitrarily designated entries. The number of entries may exceed the number of attributes by orders of magnitude. Necessary and sufficient conditions on the subject-attribute matrix are derived in terms of one-against-all halfplane dichotomies and convex hulls. Pairwise attribute difference vectors are more effective than attribute vectors for one-against-all classification. Comparisons of MeFirst algorithms based on neural networks and on linear programming (LP), on datasets drawn from published rankings of scientists and universities, show that on these tasks, LP is significantly faster.

Repetitively formatted historical books are tokenized and tagged according to eight token types (capitalized words, numbers, punctuation ...). To extract family information, templates of short sequences of tags are generated around frequent proper nouns and specified tokens like "born". Each template is associated with a user-assigned class (head of household, father, mother, spouse, geographic location ...) and a pointer to an overlapping or nearby fragment of text to be extracted. Matching the template against the book text yields class-labeled factoids. In an interaction cycle, new extraction templates are proposed for user approval or editing. Each edit-then-extract cycle typically yields thousands of factoids and a dozen new templates. With five approximately half-hour interactive sessions, 44,000 genealogical factoids were extracted from a 17th century Scottish register of marriages and births and from published 19th-20th century Ohio funeral parlor records. The experience indicates that this method quickly yields quality results with higher F-score than reported for hand-constructed rule templates.

Algorithmic methods are demonstrated for information extraction from table header elements, including data categories and data hierarchies. The table headers are found with the Minimum Index Point Search algorithm. The header-path alignment and header completion algorithms yield database-ready table content and configuration statistics on a random sample of 400 diverse tables with ground truth and 1120 tables without ground truth from international statistical data sites.

Automating the conversion of human-readable HTML tables into machine-readable relational tables will enable end-user query processing of the millions of data tables found on the web. Theoretically sound and experimentally successful methods for index-based segmentation, extraction of category hierarchies, and construction of a canonical table suitable for direct input to a relational database are demonstrated on 200 heterogeneous web tables. The methods are scalable: the program generates the 198 Access compatible CSV files in ~0.1s per table (two tables could not be indexed).

HTML tables represent a significant fraction of web data. The often complex headers of such tables are determined accurately using their indexing property. Isolated headers are factored to extract category hierarchies. Web tables are then transformed into a canonical form and imported into a relational database. The proposed processing allows for the formulation of arbitrary SQL queries over the collection of induced relational tables.

Correct segmentation of a web table into its component regions is the essential first step to understanding tabular data. Our algorithmic solution to the segmentation problem relies on the property that strings defining row and column header paths uniquely index each data cell in the table. We segment the table using only "logical layout analysis" without resorting to any appearance features or natural language understanding. We start with a CSV table that preserves the 2-dimensional structure and contents of the original source table (e.g., an HTML table) but not font size, font weight, and color. The indexing property of table headers implies a four-quadrant partitioning of the table about a minimum index point. The algorithm finds the index point through an efficient guided search. Experimental results on a 200-table benchmark demonstrate the generality of the algorithm in handling a variety of table styles and forms.

We propose to adapt Turing's seminal 1950 test for machine intelligence to evaluating progress in document analysis systems. Our premise is that a problem can be considered solved if automated and human solutions to the underlying task are indistinguishable to a skeptical human judge. For the domain-specific problems of concern here, we reformulate the test to keep the interaction between judges and human/machine participants to graphical user interfaces that do not require natural language processing, a notable difference from Turing's original formulation. Examples of tasks that may lend themselves to such tests include detecting or identifying specific document components such as logos, photographs, tables, as well as writer and language identification. The administration of the test would be facilitated by commercial crowd-sourcing systems such as Amazon Mechanical Turk, as well as research platforms such as the Lehigh Document Analysis Engine (DAE) that accept arbitrary documents for input, record test results, and provide for trusted execution of submitted programs.

Open problems are defined differently in document image analysis than in the physical sciences, theoretical computer science, or mathematics. Instead of a formal definition, problems in DIA are stated in terms of automation of an application area (e.g., postal address reading) or a scientific sub field (e.g., image compression). The notion of a successful solution may be based on (1) the relative accuracy of automated vs. expert solutions (given specific data and degree of manual tuning), (2) the distinguish ability of automated output from human output (a Turing Test), (3) the degree of current community interest (via conferences and journals), and/or (4) economic considerations. Because of the lack of formal definition for DIA problems, heuristics predominate over provably correct algorithms, and full disclosure of implementation details as well as populations and samples is essential. Results on available test sets are often only tangentially related to motivating applications. In addition, interest in automating certain tasks has been evolving rapidly as a result of advances in technology. Further community discussion of these issues may accelerate progress and symbiosis with allied disciplines.

We present a method based on header paths for efficient and complete extraction of labeled data from tables meant for humans. Although many table configurations yield to the proposed syntactic analysis, some require access to semantic knowledge. Clicking on one or two critical cells per table, through a simple interface, is sufficient to resolve most of these problem tables. Header paths, a purely syntactic representation of visual tables, can be transformed ("factored") into existing representations of structured data such as category trees, relational tables, and RDF triples. From a random sample of 200 web tables from ten large statistical web sites, we generated 376 relational tables and 34,110 subject-predicate-object RDF triples.

Calligraphic data entry is accelerated by generating, with a feature-based character classifier, an ordered list of reference candidate labels for each character image. The improvement of labeling throughput depends on the top-N accuracy of the classifier, which in turn is a function of the available already-labeled patterns. Experiments on a database of 13,351 ancient calligraphic characters indicate that clicking on reference labels is more than twice as fast as Pinyin keyboard entry.

Resources are presented for fostering paper-based election technology. They comprise a diverse collection of real and simulated ballot and survey images, and software tools for ballot synthesis, registration, segmentation, and ground truthing. The grids underlying the designated location of voter marks are extracted from 13,315 degraded ballot images. The actual skew angles of sample ballots, recorded as part of complete ballot descriptions compiled with the interactive ground-truthing tool, are compared with their automatically extracted parameters. The average error is 0.1 degrees. These results provide a baseline for the application of digital image analysis to the scrutiny of electoral ballots.

Optical scan voting is considered by many to be the most trustworthy option for conducting elections because it provides an independently verifiable record of each voter’s intent. While op-scan technology has been in use for decades, attempts to improve the machine reading of ballots raises a range of interesting issues in document image analysis. Work thus far has been hindered by a lack of real-world data, since ballots associated with actual elections are kept secure from the public and normally destroyed after a period time. Fortunately, as a result of a recent challenged election in the State of Minnesota, a large collection of op-scan ballot images was made available for public inspection on the World Wide Web. In this paper, we present this unique resource to the document analysis community. We also describe our efforts to annotate the collection, including the latest version of a graphical tool we have developed for collecting ground-truth interpretations, along with the protocol now being employed. The collection, consisting of ballot images, file formats, and associated truth data, is being made openly available to facilitate research in this important area.

We describe a component of a document analysis system for constructing ontologies for domain-specific web tables imported into Excel. This component automates extraction of the Wang Notation for the column header of a table. Using column-header specific rules for XY cutting we convert the geometric structure of the column header to a linear string denoting cell attributes and directions of cuts. The string representation is parsed by a context-free grammar and the parse tree is further processed to produce an abstract data-type representation (the Wang notation tree) of each column category. Experiments were carried out to evaluate this scheme on the original and edited column headers of Excel tables drawn from a collection of 200 used in our earlier work. The transformed headers were obtained by editing the original column headers to conform to the format targeted by our grammar. Forty-four original headers and their reformatted versions were submitted as input to our software system. Our grammar was able to parse and the extract Wang notation tree for all the edited headers, but for only four of the original headers. We suggest extensions to our table grammar that would enable processing a larger fraction of headers without manual editing.

Portable ballot counters using camera technology and manual paper feed are potentially more reliable and less expensive than scanner based systems. We show that the spatial sampling rate, geometric linearity, point spread function, and photometric transfer function of off-the-shelf consumer cameras are acceptable for ballot imaging. However, scanner illumination is much more uniform than can be economically accomplished for variable size ballots. Therefore flat-field compensation must be designed into the image processing software. We illustrate the mechanical design of a prototype camera based ballot reader based on our comparative observations.

The push toward voting via hand marked paper ballots has focused attention on the limitations of current optical scan systems. Discrepancies between human and machine interpretations of ballot markings can lead to a loss of trust in the election process. In this paper, a style-based approach to ballot recognition is proposed in which marks are recognized collectively rather than in isolation. The consistency of a voter's style is leveraged to improve the overall accuracy of the system. We compare style-based recognition to various kinds of singlet classifiers and show that it outperforms them by a substantial margin.

A persistent flaw in the evaluation of page segmentation algorithms is examined.

As a result of well-publicized security concerns with direct recording electronic (DRE) voting, there is a growing call for systems that employ some form of paper artifact to provide a verifiable physical record of a voter's choices. In this paper, we present a system we are developing to support a multi-institution, cross-disciplinary research project examining issues that arise when paper ballots are used in elections. We survey the motivating factors behind our work, discuss the special constraints raised in processing ballots as opposed to more general document images, and describe the current status of our system.

The Wang Notation Tool (WNT) is a semi-automatic, interactive tool that converts tables to Wang notation - a layout independent representation of tables where all relationships between cells are recorded without relying on the physical structure of tables. WNT requires minimal interaction to select categories from which it deduces relationships. However, if WNT is incorrect, user correction is available to generate correct Wang notation.

Querying any information system requires the knowledge of some formal language, making it inaccessible to computer-naive potential users. We propose a new intuitive querying mechanism where the query is a (well-formed) table. We extract the underlying logical structure of the table to retrieve values from a database. Query tables are interpreted to perform simple SELECT & JOIN operations. We demonstrate that query tables with different layouts but with the same underlying logical structure yield correct answers. This approach can be extended to form complicated conditional queries and queries involving aggregates.

Optical mark sensing, i.e., detecting whether a “bubble” has been filled in, may seem straightforward. However, on US election ballots the shape, intensity, size and position of the marks, while specified, are highly variable due to a diverse electorate. The ballots may be produced and scanned by poorly maintained equipment. Yet near-perfect results are required. To improve the current technology, which has been subject to criticism, components of a process for identifying marks on an optical sense ballot are evaluated. When marked synthetic ballots are compared to an unmarked ballot, the absolute difference of adaptive thresholded images gives best detection rates for all darknesses of marks, but at a false alarm rate increase. Simple absolute differencing can give good detection results with lower false alarm rates.

We formalize the notion of style context, which accounts for the increased accuracy of the field classifiers reported in this journal recently. We argue that style context forms the basis of all order-independent field classification schemes. We distinguish between intraclass style, which underlies most adaptive classifiers, and interclass style, which is a manifestation of interpattern dependence between the features of the patterns of a field. We show how style-constrained classifiers can be optimized either for field error (useful for short fields like zip codes) or for singlet error (for long fields, like business letters). We derive bounds on the reduction of error rate with field length and show that the error rate of the optimal style-constrained field classifier converges asymptotically to the error rate of a style-aware Bayesian singlet classifier.

In contrast to holistic methods, local matching methods extract facial features from different levels of locality and quantify them precisely. To determine how they can be best used for face recognition, we conducted a comprehensive comparative study at each step of the local matching process. The conclusions from our experiments include: (1) additional evidence that Gabor features are effective local feature representations and are robust to illumination changes; (2) discrimination based only on a small portion of the face area is surprisingly good; (3) the configuration of facial components does contain rich discriminating information and comparing corresponding local regions utilizes shape features more effectively than comparing corresponding facial components; (4) spatial multiresolution analysis leads to better classification performance; (5) combining local regions with Borda count classifier combination method alleviates the curse of dimensionality. We implemented a complete face recognition system by integrating the best option of each step. Without training, illumination compensation and without any parameter tuning, it achieves superior performance on every category of the FERET test: near perfect classification accuracy (99.5%) on pictures taken on the same day regardless of indoor illumination variations, and significantly better than any other reported performance on pictures taken several days to more than a year apart. The most significant experiments were repeated on the AR database, with similar results.

Recent papers have claimed that the result of K-means clustering for time series subsequences (STS clustering) is independent of the time series that created it. Our paper revisits this claim. In particular, we consider the following question: Given several time series sequences and a set of STS cluster centroids from one of them (generated by the K-means algorithm), is it possible to reliably determine which of the sequences produced these cluster centroids? While recent results suggest that the answer should be NO, we answer this question in the affirmative.We present cluster shape distance, an alternate distance measure for time series subsequence clusters, based on cluster shapes. Given a set of clusters, its shape is the sorted list of the pairwise Euclidean distances between their centroids. We then present two algorithms based on this distance measure, which match a set of STS cluster centroids with the time series that produced it. While the first algorithm creates DQG reuse this term more smaller "fingerprints" for the sequences, the second is more accurate. In our experiments with a dataset of 10 sequences, it produced a correct match 100% of the time.Furthermore, we offer an analysis that explains why our cluster shape distance provides a reliable way to match STS clusters to the original sequences, whereas cluster set distance fails to do so. Our work establishes for the first time a strong relation between the result of K-means STS clustering and the time series sequence that created it, despite earlier predictions that this is not possible.

In many applications of pattern recognition, patterns appear together in groups (fields) that have a common origin. For example, a printed word is usually a field of character patterns printed in the same font. A common origin induces consistency of style in features measured on patterns. The features of patterns co-occurring in a field are statistically dependent because they share the same, albeit unknown, style. Style constrained classifiers achieve higher classification accuracy by modeling such dependence among patterns in a field. Effects of style consistency on the distributions of field-features (concatenation of pattern features) can be modeled by hierarchical mixtures. Each field derives from a mixture of styles, while, within a field, a pattern derives from a class-style conditional mixture of Gaussians. Based on this model, an optimal style constrained classifier processes entire fields of patterns rendered in a consistent but unknown style. In a laboratory experiment, style constrained classification reduced errors on fields of printed digits by nearly 25 percent over singlet classifiers. Longer fields favor our classification method because they furnish more information about the underlying style.

Patterns often occur as homogeneous groups or fields generated by the same source. In multisource recognition problems, such isogeny induces statistical dependencies between patterns (termed style context). We model these dependencies by second-order statistics and formulate the optimal classifier for normally distributed styles. We show that model parameters estimated only from pairs of classes suffice to train classifiers for any test field length. Although computationally expensive, the style-conscious classifier reduces the field error rate by up to 20 percent on quadruples of handwritten digits from standard NIST data sets.

We propose further improvement of a handwriting recognition method that avoids segmentation while able to recognize words that were never seen before in handwritten form. This method is based on the fact that few pairs of English words share exactly the same set of letter bigrams and even fewer share longer n-grams. The lexical n-gram matches between every word in a lexicon and a set of reference words can be precomputed. A position-based match function then detects the matches between the handwritten signal of a query word and each reference word. We show that with a reasonable set of reference words, the recognition of lexicon words exceeds 90%.

In style-constrained classification often there are only a few samples of each style and class, and the correspondences between styles in the training set and the test set are unknown. To avoid gross misestimates of the classifier parameters it is therefore important to model the pattern distributions accurately. We offer empirical evidence for intuitively appealing assumptions, in feature spaces appropriate for symbolic patterns, for (1) tetrahedral configurations of class means that suggests linear style-adaptive classification, (2) improved estimates of classification boundaries by taking into account the asymmetric configuration of the patterns with respect to the directions toward other classes, and (3) pattern-correlated style variability.

We often need to access and reorganize information available in multiple tables in diverse Web pages. To understand tables, we rely on acquired expertise, background information, and practice. Current computerized tools seldom consider the structure and content in the context of other tables with related information. This paper addresses the table processing issue by developing a new framework to table understanding that applies an ontology-based conceptual modeling extraction approach to: (i) understand a table's structure and conceptual content to the extent possible; (ii) discover the constraints that hold between concepts extracted from the table; (iii) match the recognized concepts with ones from a more general specification of related concepts; and (iv) merge the resulting structure with other similar knowledge representations for use in future situations. The result is a formalized method of processing the format and content of tables while incrementally building a relevant reusable conceptual ontology.

Algorithms are presented for fully automatic three-dimensional (3-D) tracing of neurons that are imaged by fluorescence confocal microscopy. Unlike previous voxel-based skeletonization methods, the present approach works by recursively following the neuronal topology, using a set of 4 x N2 directional kernels (e.g., N = 32), guided by a generalized 3-D cylinder model. This method extends our prior work on exploratory tracing of retinal vasculature to 3-D space. Since the centerlines are of primary interest, the 3-D extension can be accomplished by four rather than six sets of kernels. Additional modifications, such as dynamic adaptation of the correlation kernels, and adaptive step size estimation, were introduced for achieving robustness to photon noise, varying contrast, and apparent discontinuity and/or hollowness of structures. The end product is a labeling of all somas present, graph-theoretic representations of all dendritic/axonal structures, and image statistics such as soma volume and centroid, soma interconnectivity, the longest branch, and lengths of all graph branches originating from a soma. This method is able to work directly with unprocessed confocal images, without expensive deconvolution or other preprocessing. It is much faster that skeletonization, typically consuming less than a minute to trace a 70-MB image on a 500-MHz computer. These properties make it attractive for large-scale automated tissue studies that require rapid on-line image analysis, such as high-throughput neurobiology/angiogenesis assays, and initiatives such as the Human Brain Project.

Very few pairs of English words share exactly the same letter bigrams. This linguistic property can be exploited to bring lexical context into the classification stage of a word recognition system. The lexical n-gram matches between every word in a lexicon and a subset of reference words can be precomputed. If a match function can detect matching segments of at least n-gram length from the feature representation of words, then an unknown word can be recognized by determining the subset of reference words having an n-gram match at the feature level with the unknown word. We show that with a reasonable number of reference words, bigrams represent the best compromise between the recall ability of single letters and the precision of trigrams. Our simulations indicate that using a longer reference list can compensate errors in feature extraction. The algorithm is fast enough, even with a slow processor, for human-computer interaction.

We present strategies and results for identifying the symbol type (lower-case, upper-case, digit, and punctuation or special symbols) of every character in a text document by using various kinds of information from neighboring characters. In the expectation of reasonable word and character segmentation for shape clustering, we designed several type recognition methods that depend on cluster n-grams, shape codes, and within word context. On an ASCII test corpus of 925 articles that simulates perfect image-level processing, these methods achieve a substantial improvement over default assignment of all characters to lower case.

The principle that for every document analysis task there exists a mechanism for creating well-defined ground-truth is a widely held tenet. Past experience with standard datasets providing ground-truth for character recognition and page segmentation tasks supports this belief. In the process of attempting to evaluate several table recognition algorithms we have been developing, however, we have uncovered a number of serious hurdles connected with the ground-truthing of tables. This problem may, in fact, be much more difficult than it appears. We present a detailed analysis of why table ground-truthing is so hard, including the notions that there may exist more than one acceptable "truth" and/or incomplete or partial "truths".

In many applications of pattern recognition, patterns appear in groups (fields) that have a common origin. For example, a printed word is afield of character patterns printed in the same font. A common origin induces consistency of style among features measured on patterns. In the presence of multiple styles, the features of co-occurring patterns are statistically dependent through the underlying style. Modeling such dependence among constituent patterns of afield increases the classification accuracy. Effects of style consistency on the distributions of field features (concatenation of pattern features) are modeled by hierarchical mixtures. Each field derives from a mixture of styles, while, within a field, a pattern derives from a class-style conditional mixture of Gaussians. An optimal (least-error) style-conscious classifier processes entire fields of patterns rendered in a consistent but unknown style, based on the model. In a laboratory experiment, style-conscious classification reduced errors on fields of printed digits by nearly 25% over singlet classifiers. Longer fields favor our classification method, because they furnish more information about the underlying style.

We present a document-specific OCR system and apply it to a corpus of fixed business letters. Unsupervised classification of the segmented character bitmaps on each page, using a "clump" metric, typically yields several hundred clusters with highly skewed populations. Letter identities are assigned to each cluster by maximizing matches with a lexicon of English words. We found that for 2/3 of the pages, we can identify almost 80% of the words included in the lexicon, without any shape training. Residual errors are caused by mis-segmentation including missed lines and punctuation. This research differs from earlier attempts to apply cipher decoding to OCR in: (1) using real data; (2) a more appropriate clustering algorithm; and (3) decoding a many-to-many instead of a one-to-one mapping between clusters and letters.

In some classification tasks, all patterns in a field, such as digits in a ZIP-code image, originate from the same, but unknown, source (writer/print style). The class-conditional feature distributions depend on the source of the patterns. Several sources may share the same distribution, or style. The style-conditional distributions are estimated from the training set. The optimal field-classifier computes the class-conditional field-feature-probabilities as the sum of class-and-style-conditional field-feature-probabilities, weighted by the prior probabilities of the styles. We compare the decision regions and error rates of style-weighted classification with both conventional singlet and top-style classification in a minimal family of examples, and discuss some related practical considerations.

The contributions to document image analysis of 99 papers published in the IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) are clustered, summarized, interpolated, interpreted, and evaluated.

The black layer is digitized from a USGS topographic map digitized at 1000 dpi. The connected components of this layer are analyzed and separated into line art, text, and icons in two passes. The paired street casings are converted to polylines by vectorization and associated with street labels from the character recognition phase. The accuracy of character recognition is shown to improve by taking account of the frequently occurring overlap of line art with street labels. The experiments show that complete vectorization of the black line-layer bitmap is the major remaining problem.

We present a method of classifying a pattern using information furnished by a ranked list of templates, rather than just the best matching template. We propose a parsimonious model to compute the class-conditional likelihood of a list of templates ranked on the basis of their match scores. We discuss the estimation of parameters used in the model. The results of maximum likelihood classification on isolated digit patterns consistently show a 10-20% relative gain in recognition accuracy when we use more than one top-template.

To maintain OCR accuracy with decreasing quality of page image composition, production, and digitization, it is essential to tune the system to each document. We propose a prototype extraction method for document-specific OCR systems. The method automatically generates training samples from unsegmented text images and the corresponding transcripts. It is tolerant of transcription errors, so a transcript produced automatically by an imperfect omnifont OCR system can be used. The method is based on new algorithms for estimating character widths, character locations in a word, and match/nonmatch probabilities from unsegmented text. An experimental word recognition system is designed and developed to combine prototype extraction algorithms and segmentation-free word recognition. The system can adapt itself to different page images and achieve high recognition accuracy on heavily degraded print.

This is a review, from an intuitive rather than a mathematical perspective, of the statistical foundations of adaptive recognition. Key considerations are priors, sample size and sampling strategy, labels, statistical dependencies, and dimensionality. The small-sample bias and variance of maximum likelihood, MAP and Bayes estimators are compared in a small concrete case. Iterative expectation maximization for estimating the sufficient statistics of mixtures is illustrated in a simple setting. It is shown that correlation among features is sometimes unjustly maligned. A counterintuitive increase in the error rate after adding a second feature is traced to the curse of dimensionality. Adaptive classification is presented in the context of both parametric and nonparametric (nearest neighbors and neural nets) estimation. Some recent theoretical results and older experimental observations on hybrid classification are summarized.

The bitmap obtained by scanning a printed pattern depends on the exact location of the scanning grid relative to the pattern. We consider ideal sampling with a regular lattice of delta functions. The displacement of the lattice relative to the pattern is random and obeys a uniform probability density function defined over a unit cell of the lattice. Random-phase sampling affects the edge-pixels of sampled patterns. The resulting number of distinct bitmaps and their relative frequencies can be predicted from a mapping of the original pattern boundary to the unit cell (called a module-grid diagram). The theory is supported by both simulated and experimental results. The module-grid diagram may be useful in helping to understand the effects of edge-pixel variation on optical character recognition.

A Bayesian method of isolating character bitmaps from paragraph-length samples of heavily degraded text images is demonstrated. The method requires a transcript of the text, but it is sufficiently robust to tolerate errors in transcripts obtained from multifont commercial OCR software. The resulting prototypes (labeled character images) are used to recognize additional text an the same document.

N-tuple features for optical character recognition have received only scattered attention since the 1960s. Our main purpose is to show that advances in computer technology and computer science compel renewed interest. N-tuple features are useful for printed character classification because they indicate the presence or absence of a given rigid configuration of n black and white pixels in a pattern. Desirable n-tuples fit each pattern of a specified (positive) training set of characters in at least p different shift positions, and fail to fit each pattern of a specified (negative) training set by at least n-q pixels in each shift position. We prove that the problem of finding a distinguishing n-tuple is NP-complete, by examining a natural subproblem with binary strings called the missing configuration problem. The NP-completeness result notwithstanding, distinguishing n-tuples are found automatically in a few seconds on contemporary workstations. We exhibit a practical search algorithm for generating, from a small training set, a collection of n-tuples with low class-conditional correlation and with specified design parameters n, p, and q. The generator, which is available on the Internet, is empirically shown to be effective through a comparison with a benchmark generator. We show experimentally that the design parameters provide a useful tradeoff between distinguishing power and generation time, and also between the conditional probabilities for the positive and negative classes. We explore the feature probabilities obtainable for various dichotomies, and show that the design parameters control the feature probabilities.

Considers the problem of evaluating character image generators that model distortions encountered in optical character recognition (OCR). While a number of such defect models have been proposed, the contention that they produce the desired result is typically argued in an ad hoc and informal way. The authors introduce a rigorous and more pragmatic definition of when a model is accurate: they say a defect model is validated if the OCR errors induced by the model are indistinguishable from the errors encountered when using real scanned documents. The authors describe four measures to quantify this similarity, and compare and contrast them using over ten million scanned and synthesized characters in three fonts. The measures differentiate effectively between different fonts and different scans of the same font regardless of the underlying text.

Shift-invariant, custom designed n-tuple features are combined with a probabilistic decision tree to classify isolated printed characters. The feature probabilities are estimated using a novel compound Bayesian procedure in order to delay the fall-off in classification accuracy with tree size due to a small sample set. On a ten-class confusion set of eight-point characters, the method yields error rates under 1% with only 3 training samples per class.

In this paper we examine the effects of random-phase spatial sampling on the optical character recognition process. We start by presenting a detailed analysis in the case of 1-dimensional patterns. Empirical data demonstrate that our model is accurate. We then give experimental results for more complex, 2-dimensional patterns (i.e. printed, scanned characters). Spatial sampling seems to account for a significant amount of the variability seen in practice.

Many current optical character recognition (OCR) systems attempt to decompose printed pages into a set of zones, each containing a single column of text, before converting the characters into coded form. The authors present a methodology for automatically assessing the accuracy of such decompositions, and demonstrate its use in evaluating six OCR systems.>

Requirements for the objective evaluation of automated data-entry systems are presented. Because the cost of correcting errors dominates the document conversion process, the most important characteristic of an OCR device is accuracy. However, different measures of accuracy (error metrics) are appropriate for different applications, and at the character, word, text-line, text-block, and document levels. For wholly objective assessment, OCR devices must be tested under programmed, rather than interactive, control.>

Independent decisions by two high performance nearest-neighbor hand-printed digit classifiers are combined in a principled manner. Three combination methods are investigated: Bayesian combination, Dempster-Shafer evidential reasoning, and dynamic classifier selection. On a test set of 60,000 hand-printed digits, dynamic classifier selection performs slightly better than Bayesian or Dempster-Shafer evidential reasoning, but the lowest error rate is obtained by K-nearest-neighbor combination. Single-parameter classifier combination is used to generate error-reject curves. Essential error-free classification is obtained at the cost of 4% rejects. The zero-reject error rate decreases from 1.18% for the best single classifier system to 0.67% for the combined classifier.>

A method for extracting alternating horizontal and vertical projection profiles are from nested sub-blocks of scanned page images of technical documents is discussed. The thresholded profile strings are parsed using the compiler utilities Lex and Yacc. The significant document components are demarcated and identified by the recursive application of block grammars. Backtracking for error recovery and branch and bound for maximum-area labeling are implemented with Unix Shell programs. Results of the segmentation and labeling process are stored in a labeled x-y tree. It is shown that families of technical documents that share the same layout conventions can be readily analyzed. Results from experiments in which more than 20 types of document entities were identified in sample pages from two journals are presented.>

Current OCR devices generate too many errors due to missegmentation and multifont confusion. Some of these errors can be avoided or corrected though greater use of linguistic context and local shape consistency in printed matter. To teach machines to read, OCR designers should allow their devices to modify their internal parameters according to information gained through a family of internal feedback loops.>

It is argued that it is time for a major change of approach to optical character recognition (OCR) research. The traditional approach, focusing on the correct classification of isolated characters, has been exhausted. The demonstration of the superiority of a new classification method under operational conditions requires large experimental facilities and databases beyond the resources of most researchers. In any case, even perfect classification of individual characters is insufficient for the conversion of complex archival documents to a useful computer-readable form. Many practical OCR tasks require integrated treatment of entire documents and well-organized typographic and domain-specific knowledge. New OCR systems should take advantage of the typographic uniformity of paragraphs or other layout components. They should also exploit the unavoidable interaction with human operators to improve themselves without explicit 'training'.>

The emergence of neural networks as a significant subdiscipline with corresponding attempts at application to engineering problems is traced back to the 1960s, when Frank Rosenblatt, a Cornell University psychologist, showed by mathematical analysis, digital computer simulation, and experiments with special-purpose parallel analog systems that neural networks with variable-weight connections could be trained to classify spatial patterns into prespecified categories. In his attempts to provide biologically plausible explanations of the function of the central nervous system, he investigated relatively simple networks that were amenable to analysis and more complex networks whose behavior could be predicted only in terms of gross characteristics. He assembled a sizable group involving theoreticians, experimentalists, technologists, and, later, biologists. His work caught the imagination of the press and led to the wave of febrile activity that subsided at the end of that decade.

The authors briefly recapitulate the face-to-face composition (FFC) model for the representation and manipulation of topological and geometric entities. They then summarize L.S. Homem de Mello's and A. Sanderson's (1988) proposal for assembly planning. It is shown that the assembly AND/OR graph proposed by L.S. Homem de Mello and A. Sanderson for task planning is an efficient data structure showing all possible assembly sequences. It can be obtained directly from the FFC model by a sequence of component-merging operations.>

The face-to-face composition (FFC) graph is the formal representation of a family of models of solid objects for advanced engineering applications. It is a multirooted hierarchical structure based on boundary representation and is capable of accommodating different conceptual views of the same object or assembly. A node of the FFC graph describes a volumetric object component consisting of a single shell, while its arcs correspond to connection faces between pairs of single components. Operators are available both for modifying the object and for changing the representation. Node groups define a correct order of evaluation of the FFC graph which produces a valid solid object at each step. The model also includes a formal definition of the notion 'feature-of' as an open subgraph corresponding to constructs not necessarily realizable on their own, such as rivet holes with pads.>

A substitution cipher consists of a block of natural language text where each letter of the alphabet has been replaced by a distinct symbol. As a problem in cryptography, the substitution cipher is of limited interest, but it has an important application in optical character recognition. Recent advances render it quite feasible to scan documents with a fairly complex layout and to classify (cluster) the printed characters into distinct groups according to their shape. However, given the immense variety of type styles and forms in current use, it is not possible to assign alphabetical identities to characters of arbitrary size and typeface. This gap can be bridged by solving the equivalent of a substitution cipher problem, thereby opening up the possibility of automatic translation of a scanned document into a standard character code, such as ASCII. Earlier methods relying on letter n-gram frequencies require a substantial amount of ciphertext for accurate n-gram estimates. A dictionary-based approach solves the problem using relatively small ciphertext samples and a dictionary of fewer than 500 words. Our heuristic backtrack algorithm typically visits only a few hundred among the 26! possible nodes on sample texts ranging from 100 to 600 words.

A sequential optical character recognition algorithm, ideally suited for implementation by means of microprocessors with limited storage capabilities, is formulated in terms of a binary decision tree. Upper bounds On the recognition performance are derived in terms of the stability of the digitized picture elements. The design process is described in detail. The algorithm is tested on single-font typewritten characters and the experimental and theoretical results are compared.

This correspondence calls attention to several frequently used assumptions and techniques culled from the pattern recognition literature.

For some time now we have also been interested in studying human factors aspects of computer text editors. We have surveyed the literature [9], and we have conducted several investigations of our own [10] ranging from an application of file-comparison algorithms in editor research [1], through prediction of editing performance [7], to the design and implementation of SIMPLE, our own editing system for beginners [8, 11].Currently we are concentrating our efforts on gathering data to determine how much time users spend performing various editing activities. We intend to extend the work begun in previous studies, to investigate suboptimal editor performance including errors and nonoptimal means of achieving goals, and to study the broder aspects of editing such as file manipulation and job control that have largely been ignored.

A lectureless mode of instruction for programming courses is described. The observations collected in a pilot experiment teaching FORTRAN to about one hundred business students are recorded and analyzed. Advantages and disadvantages of the method, and implications for other languages and other clienteles are discussed.

A method of video compaction based on transmitting only the first instance of each class of digitized patterns is shown to yield a compaction ratio of 16: 1 on a short passage of text from the IEEE SPECTRUM. Refinements to extend the bandwidth reduction to 40: 1 by relatively simple means are proposed but not demonstrated.

A system intended to provide input of printed text to computers is applied to published patents, annotated law reports, and technical journals.

Abstract—An unconventional approach to character recognition is developed. The resulting system is based solely on the statistical properties of the language, therefore it can read printed text with no previous training or a priori information about the structure of the characters. The known letter-pair frequencies of the language are used to identify the printed symbols in the following manner.

The problem of recognizing a large alphabet (1000 different characters) is approached using a two stage process. In the first stage of design, the data is partitioned into groups of similar characters by means of heuristic and iterative algorithms. In the second stage, peephole templates are generated for each character in such a way as to guarantee discrimination against other characters in the same similarity class. Recognition is preceded by establishing an order of search through the groups with a relatively small number of ``group masks.'' The character is then identified by means of the ``individual masks.'' through a threshold criterion. The effects on the error and reject rates of varying the several parameters in the design and test procedure are described on the basis of computer simulation experiments on a 20 000 character data set. An error rate of 1 percent with 7 percent rejects, is obtained on new data.

The output of a simple statistical categorizer is used to improve recognition performance on a homogeneous data set. An array of initial weights contains a coarse description of the various classes; as the system cycles through a set of characters from the same source (a typewritten or printed page), the weights are modified to correspond more closely with the observed distributions. The true identifies of the characters remain inaccessible throughout the training cycle. This experimental study of the effect of the various parameters in the algorithm is based on\sim 30 000characters from fourteen different font styles. A fivefold average decrease over the initial rates is obtained in both errors and rejects.

Widespread and persistent interest in the implementation of multilevel logic, conditional probability computers, learning machines, and brain models has created a need for an inexpensive analog or quasi-digital storage element. A number of possible approaches to this problem, ranging from the slow and reliable electromechanical systems to the many forms of charge and flux integration, are reviewed, and the suitability of each device for various fields of application is briefly discussed.