This paper investigates highly discriminating features for writer identification for off-line handwritten text lines and passages. Five categories of features are tested: slant and slant energy, skew, pixel distribution, curvature, and entropy. Four experiments are run utilizing the IAM Handwriting Database and the ICDAR 2011 Writer Identification Contest dataset: the first, on 10 writers from the IAM dataset, the second, on 50 writers from the IAM dataset, the third, on 100 writers from the IAM dataset, and the fourth, strictly following the methodology of the 2011 ICDAR Writer Identification Contest. When compared to the other methodologies tested in the ICDAR competition, ours ranked fourth out of nine. These features support high recognition rates and are competitive with other state of the art methods for writer identification.

Automatic methods for analyzing sentiment and its movement through a play's social network are investigated. From structured dialogue we can algorithmically determine who is speaking and guess at who is listening or being directly addressed. Knowing who is speaking to whom allows the flow of sentiment to be tracked between characters and, within plays with clear time-lines, permits tracking the development of emotional relationships. We hypothesize that changing polarities between characters can be modeled as edge weights in a dynamic social network- a "sentiment network"-which can be used to distinguish a document's genre (tragedies versus comedies), detect a given character's enemies and allies, and model the overall emotional development of a play. Experiments on Shakespeare's plays are presented along with discussion of improvements and further applications.

Whole-book recognition is a document image analysis strategy that operates on the complete set of a book's page images using automatic adaptation to improve accuracy. We describe an algorithm which expects to be initialized with approximate iconic and linguistic models--derived from (generally errorful) OCR results and (generally imperfect) dictionaries--and then, guided entirely by evidence internal to the test set, corrects the models which, in turn, yields higher recognition accuracy. The iconic model describes image formation and determines the behavior of a character-image classifier, and the linguistic model describes word-occurrence probabilities. Our algorithm detects "disagreements" between these two models by measuring cross entropy between 1) the posterior probability distribution of character classes (the recognition results resulting from image classification alone) and 2) the posterior probability distribution of word classes (the recognition results from image classification combined with linguistic constraints). We show how disagreements can identify candidates for model corrections at both the character and word levels. Some model corrections will reduce the error rate over the whole book, and these can be identified by comparing model disagreements, summed across the whole book, before and after the correction is applied. Experiments on passages up to 180 pages long show that when a candidate model adaptation reduces whole-book disagreement, it is also likely to correct recognition errors. Also, the longer the passage operated on by the algorithm, the more reliable this adaptation policy becomes, and the lower the error rate achieved. The best results occur when both the iconic and linguistic models mutually correct one another. We have observed recognition error rates driven down by nearly an order of magnitude fully automatically without supervision (or indeed without any user intervention or interaction). Improvement is nearly monotonic, and asymptotic accuracy is stable, even over long runs. If implemented naively, the algorithm runs in time quadratic in the length of the book, but random subsampling and caching techniques speed it up by two orders of magnitude with negligible loss of accuracy. Whole-book recognition has potential applications in digital libraries as a safe unsupervised anytime algorithm.

Can a high-performance document image recognition system be built without detailed knowledge of the application? Having benefited from the statistical machine learning revolution of the last twenty years, our architectures rely less on hand-crafted special-case rules and more on models trained on labeled-sample data sets. But urgent questions remain. When we can't collect (and label) enough real training data, does it help to complement them with data synthesized using generative models? Is it ever completely safe to rely on synthetic data? If we can't manage to train (or craft) a single complete, near-perfect, application-specific "strong" model to drive recognition, can we make progress by combining several imperfect or incomplete "weak" models? Can recognition that is carried out jointly over weak models perform optimally while still running fast? Can a recognizer automatically pick a strong model of its input? Must we always pre-train models for every kind ("style") of input expected, or can a recognizer adapt to unknown styles? Can weak models adapt autonomously, growing stronger and so driving accuracy higher, without any human intervention? Can one model "criticize" - and then proceed to correct - other models, even while it is being criticized and corrected in turn by them? After twenty-five years of research on these questions we have partial answers, many in the affirmative: in addition to promising laboratory demonstrations, we can take pride in successful applications. I'll illustrate the evolution of the state of the art with concrete examples, and point out open problems.

Whole-book recognition is a document image analysis strategy that operates on the complete set of a book's page images, attempting to improve accuracy by automatic unsupervised adaptation. Our algorithm expects to be given initial iconic and linguistic models---derived from (generally errorful) OCR results and (generally incomplete) dictionaries---and then, guided entirely by evidence internal to the test set, the algorithm corrects the models yielding improved accuracy. We have found that successful corrections are often closely associated with "disagreements" between the models which can be detected within the test set by measuring cross entropy between (a) the posterior probability distribution of character classes (the recognition results from image classification alone), and (b) the posterior probability distribution of word classes (the recognition results from image classification combined with linguistic constraints). We report experiments on long passages (up to 180 pages) revealing that: (1) disagreements and error rates are strongly correlated; (2) our algorithm can drive down recognition error rates by nearly an order of magnitude; and (3) the longer the passage, the lower the error rate achievable. We also propose formal models for a book's text, for iconic and linguistic constraints, and for our whole-book recognition algorithm---and, using these, we rigorously prove sufficient conditions for the whole-book recognition strategy to succeed in the ways illustrated in the experiments.

Highly versatile classifiers for document analysis systems demand representative training sets which can be dauntingly large, often challenging conventional trainable classifier technologies. We propose to select a small subset of training data, matched to each particular test set, in hopes of improved speed without loss of accuracy. Since selection must occur on line, we cannot use classifiers that require off-line training. Fortunately, Nearest Neighbors classifiers support on-line training; we use a fast approximate kNN technology using hashed k-D trees. The distribution of samples in k-D bins can be used to measure similarity between any two document images: we select the three most similar training images for any given test image. In experiments on a document image content extraction system, our algorithm was able to prune 118 training images to three, for a speedup of a factor of 17 with no loss of accuracy. Other experiments with an oracle and manual selection suggest that it may be possible to improve accuracy as well.

We compare methodologies for trainable document image content extraction, using a variety of ground-truth policies: loose, tight, and pixel-accurate. The goal is to achieve pixel-accurate segmentation of document images. Which ground-truth policy is the best has been debated. ``Loose'' truth is obtained by sweeping rectangles to enclose entire text blocks etc, and can be an efficient manual task. ``Tight'' truth requires more care, and more time, to enclose individual text lines. Pixel-accurate truth, in which only foreground pixels are labeled, can be obtained by applying the PARC PixLabeler tool; in our experience this tool was as quick to use as loose truthing. We have compared the accuracy of all three truthing policies, and report that tight truth supports higher accuracy than loose truth, and pixel-accurate truth yields the highest accuracy. We have also experimented on morphological expansions on pixel-accurate truth, by expanding sets of foreground pixels morphologically, and report that expanded pixel-accurate truth supports higher accuracy than pixel-accurate truth.

We report performance evaluation of our automatic feature discovery method on the publicly available Gisette dataset: a set of 29 features discovered by our method ranks 129 among all 411 current entries on the validation set. Our approach is a greedy forward selection algorithm guided by error clusters. The algorithm finds error clusters in the current feature space, then projects one tight cluster into the null space of the feature mapping, where a new feature that helps to classify these errors can be discovered. This method assumes a ``data-rich'' problem domain and works well when large amount of labeled data is available. The result on the Gisette dataset shows that our method is competitive to many of the current feature selection algorithms. We also provide analytical results showing that our method is guaranteed to lower the error rate on Gaussian distributions and that our approach may outperform the standard Linear Discriminant Analysis (LDA) method in some cases.

Whole-book recognition is a document image analysis strategy that operates on the complete set of a book's page images using automatic adaptation to improve accuracy. Our algorithm expects to be given approximate iconic and linguistic models-derived from (generally errorful) OCR results and (generally incomplete) dictionaries-and then, guided entirely by evidence internal to the test set, corrects the models yielding improved accuracy. The iconic model describes image formation and determines the behavior of a character-image classifier. The linguistic model describes word-occurrence probabilities. In previous work, we reported that adapting the iconic model alone (with a perfect linguistic model) was able to automatically reduce word error rate on a 180-page book by a large factor. In this paper, we propose an algorithm that adapts both the iconic model and the linguistic model alternately to improve both models on the fly. The linguistic model adaptation method, which we report here, identifies new words and adds them to the dictionary. With 64.6% words missing in the initial dictionary, our previous algorithm reduced word error rate from 40.2% to 23.2%. The new algorithm drives word error rate down further from 23.2% to 16.0%.

We propose algorithms for ameliorating difficulties in fast approximate k Nearest Neighbors (kNN) classifiers that arise from imbalances among classes in numbers of samples, and from concentrations of samples in small regions of feature space. These problems can occur with a wide range of binning kNN algorithms such as k-D trees and our variant, hashed k-D trees. The principal method we discuss automatically rebalances training data and estimates concentration in each K-d hash bin separately, which then controls how many samples should be kept in each bin. We report an experiment on 86.7M training samples which shows a 7-times speedup and higher minimum per-class recall, compared to previously reported methods. The context of these experiments is the need for image classifiers able to handle an unbounded variety of inputs: in our case, highly versatile document classifiers which require training sets as large as a billion training samples.

We report an automatic feature discovery method that achieves results comparable to a manually chosen, larger feature set on a document image content extraction problem: the location and segmentation of regions containing handwriting and machine-printed text in documents images. This approach is a greedy forward selection algorithm that iteratively constructs one linear feature at a time. The algorithm finds error clusters in the current feature space, then projects one tight cluster into the null space of the feature mapping, where a new feature that helps to classify these errors can be discovered. We conducted experiments on 87 diverse test images. Four manually chosen linear features with an error rate of 16.2% were given to the algorithm; the algorithm then found an additional ten features; the composite 14 features achieve an error rate of 13.8%. This outperforms a feature set of size 14 chosen by principal component analysis (PCA) with an error rate of 15.4%. It also nearly matches the error rate of 13.6% achieved by twice as many manually chosen features. Thus our algorithm appears to compete with both the widely used PCA method and tedious and expensive trial-and-error manual exploration.

We describe the results of large-scale experiments with algorithms for unsupervised improvement of recognition of book-images using fully automatic mutual-entropy-based model adaptation. Each experiment is initialized with an imperfect iconic model derived from errorful OCR results, and a more or less perfect linguistic model, after which our fully automatic adaptation algorithm corrects the iconic model to achieve improved accuracy, guided only by evidence within the test set. Mutual-entropy scores measure disagreements between the two models and identify candidates for iconic model correction. Previously published experiments have shown that word error rates fall monotonically with passage length. Here we show similar results for character error rates extending over far longer passages up to fifty pages in length: we observed error rates were driven from 25% down to 1.9%. We present new experimental results to support the motivating principle of our strategy: that error rates and mutual-entropy scores are strongly correlated. Also, we discuss theoretical, algorithmic, and methodological challenges that we have encountered as we scale up experiments towards complete books.

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.

We report an improved methodology for training a sequence of classifiers for document image content extraction, that is, the location and segmentation of regions containing handwriting, machine-printed text, photographs, blank space, etc. The resulting segmentation is pixel-accurate, and so accommodates a wide range of zone shapes (not merely rectangles). We have systematically explored the best scale (spatial extent) of features. We have found that the methodology is sensitive to ground-truthing policy, and especially to precision of ground-truth boundaries. Experiments on a diverse test set of 83 document images show that tighter ground-truth reduces per-pixel classification errors by 45% (from 38.9% to 21.4%). Strong evidence, from both experiments and simulation, suggests that iterated classification converges region boundaries to the ground-truth (i.e. they don't drift). Experiments show that four-stage iterated classifiers reduce the error rates by 24%. We also present an analysis of special cases suggesting reasons why boundaries converge to the ground-truth.

We discuss problems in developing policies for ground truthing document images for pixel-accurate segmentation. First, we describe ground truthing policies that apply to four different scales: (1) paragraph, (2) text line, (3) character, and (4) pixel. We then analyze difficult and/or ambiguous cases that will challenge any policy, e.g. blank space, overlapping content, etc. Experiments have shown the benefit of using "tighter'' zones that capture more detail (e.g., at the text line level, instead of paragraph). We show that tighter ground truth does significantly improve classification results, by 45% in recent experiments. It is important to face the fact that a pixel-accurate segmentation can be better than manually obtained ground truth. In practice, perfectly accurate pixel-level ground truth may not be achievable of course, but we believe it is important to explore methods to semi-automatically improve existing ground truth.

We describe experimental results for unsupervised recognition of the textual contents of book-images using fully automatic mutual-entropy-based model adaptation. Each experiment starts with approximate iconic and linguistic models---derived from (generally errorful) OCR results and (generally incomplete) dictionaries---and then runs a fully automatic adaptation algorithm which, guided entirely by evidence internal to the test set, attempts to correct the models for improved accuracy. The iconic model describes image formation and determines the behavior of a character-image classifier. The linguistic model describes word-occurrence probabilities. Our adaptation algorithm detects disagreements between the models by analyzing mutual entropy between (1) the a posteriori probability distribution of character classes (the recognition results from image classification alone), and (2) the a posteriori probability distribution of word classes (the recognition results from image classification combined with linguistic constraints). Disagreements identify candidates for automatic model corrections. We report experiments on 40 textlines in which word error rates fall monotonicaly with passage lengths. We also report experiments on an enhanced algorithm which can cope with character-segmentation errors (a single split, or a single merge, per word). In order to scale up experiments, soon, to whole book images, we have revised data structures and implemented speed enhancements. For this algorithm, we report results on three increasingly long passage lengths: (a) one full page, (b) five pages, and (b) ten pages. We observe that error rates on long words fall monotonically with passage lengths.

We propose a feature selection method that constructs each new feature by analysis of tight error clusters. This is a greedy, time-efficient forward selection algorithm that iteratively constructs one feature at a time, until a desired error rate is reached. The algorithm finds error clusters in the current feature space, then projects one tight cluster into the null space of the feature mapping, where a new feature that helps to classify these errors can be discovered. Tight error clusters indicate that the current features are unable to discriminate these samples. The approach is strongly data-driven and restricted to linear features, but otherwise general. Large scale experiments show that it can achieve a monotonically decreasing error rate within the feature discovery set, and a generally decreasing error rate on a distinct test set.

We report an improved methodology for training classifiers for document image content extraction, that is, the location and segmentation of regions containing handwriting, machine-printed text, photographs, blank space, etc. Our previous methods classified each individual pixel separately (rather than regions): this avoids the arbitrariness and restrictiveness that result from constraining region shapes (to, e.g., rectangles). However, this policy also allows content classes to vary frequently within small regions, often yielding areas where several content classes are mixed together. This does not reflect the way that real content is organized: typically almost all small local regions are of uniform class. This observation suggested a post-classification methodology which enforces local uniformity without imposing a restricted class of region shapes. We choose features extracted from small local regions (e.g. 4-5 pixels radius) with which we train classifiers that operate on the output of previous classifiers, guided by ground truth. This provides a sequence of post-classifiers, each trained separately on the results of the previous classifier. Experiments on a highly diverse test set of 83 document images show that this method reduces per-pixel classification errors by 23%, and it dramatically increases the occurrence of large contiguous regions of uniform class, thus providing highly usable near-solid 'masks' with which to segment the images into distinct classes. It continues to allow a wide range of complex, non-rectilinear region shapes.

We give an analysis of relationships between expected retrieval performance and classification recognition accuracy in the context of document image content extraction and inventory. By content extraction we mean location and measurement of regions containing handwriting, machine- printed text, photographs, blank space, etc, in documents represented as bilevel, grey-level, or color images. Recent experiments have shown that even modest per-pixel content classification accuracies can support usefully high recall and precision rates (of, e.g., 80-90%) for retrieval queries within document collections seeking pages that contain a given minimum fraction of a certain type of content. In an effort to elucidate this interesting empirical result, we have analyzed the interdependency of classification and retrieval under a variety of assumptions about the distribution of content types in document image collections. We show that under general conditions we cannot derive precision and recall measures from per-pixel classification measures alone, but we can estimate the expected values of these measures. If however the distribution of content and error rates are uniform across the entire collection, our results suggest, it is possible to predict precision and recall measures from classification accuracy and vice versa.

The ScatterType CAPTCHA (completely automated public Turing tests to tell computers and humans apart), designed to resist character-segmentation attacks and shown to be highly legible to human readers, is analyzed for vulnerabilities and is offered for experiments in automatic attack. As introduced in Baird and Riopka (2005), 'ScatterType' challenges are images of machine-print text whose characters are cut into pieces which then drift apart, in an attempt to frustrate segment-then-recognize computer vision attacks. Analysis of experimental human legibility data has shown that better than 95% correct legibility can be achieved through judicious choice of the pseudorandom generating parameters (Baird et al., 2005). That analysis is summarized and discussed here as motivation for a discussion of potential vulnerabilities. An invitation to attack ScatterType is offered.

A trainable method for distinguishing between mathematics notation and natural language (here, English) in images of textlines, using computational geometry methods only with no assistance from symbol recognition, is described. The input to our method is a "neighbor graph" extracted from a bilevel image of an isolated textline by the method of Kise et al. (1998): this is a pruned form of Delaunay triangulation of the set of locations of black connected components. Our method first attempts to classify each vertex and, separately, each edge of the neighbor graph as belonging to math or English; then these results are combined to yield a classification of the entire textline. All three classifiers are automatically trainable. Features for the vertex and edge classifiers were selected semi-manually from a large number in a process driven by training data: this stage is potentially fully automatable. In experiments on images scanned from books and images generated synthetically, this methodology converged in three iterations to a textline classifier with an error rate of less than one percent.

The rapid growth of digital libraries (DLs) worldwide poses many new challenges for document image analysis (DIA) research and development. DLs promise to offer more people access to larger document collections, and at far greater speed, than physical libraries can. But DLs also tend, for many reasons, to serve poorly, or even to omit entirely, many types of non-digital human-legible media, such as originally printed and handwritten documents. These media, in their original physical (undigitized) form, are readily - if not always quickly - legible, searchable, and browseable, whereas in the form of document images accessed through DLs they often lose many of their original advantages while of course lacking many advantages of symbolically encoded information. The author explores these issues and illustrates them with brief case studies arising from his experience as a DIA researcher in collaboration with several DL projects in the US. Difficult open DIA technical problems in DL applications are identified in the contrasting advantages of paper and digital displays, at every stage of capture, early processing, recognition, analysis, presentation, retrieval, and in personal and interactive applications. These support the conclusion that the international DIA R & D community is urgently needed (because uniquely qualified) to provide new technology to help rescue from neglect - even, in many cases, eventual oblivion - the world's vast culturally irreplaceable legacy paper document collections.

We show that document image decoding (DID) supervised training algorithms, as a result of recent refinements, achieve high accuracy with low manual effort even under conditions of severe image degradation in both training and test data. We describe improvements in DID training of character template, set-width, and channel (noise) models. Large-scale experimental trials, using synthetically degraded images of text, have established two new and practically important advantages of DID algorithms: 1) high accuracy (> 99% characters correct) in decoding using models trained on even severely degraded images from the same distribution; and 2) greatly improved accuracy (< 1/10 the error rate) across a wide range of image degradations compared to untrained (idealized) models. This ability to train reliably on low-quality images that suffer from massive fragmentation and merging of characters, without the need for manual segmentation and labeling of character images, significantly reduces the manual effort of DID training.

We exploit the gap in ability between human and machine vision systems to craft a family of automatic challenges that tell human and machine users apart via graphical interfaces including Internet browsers. Turing proposed (1950) a method whereby human judges might validate "artificial intelligence" by failing to distinguish between human and machine interlocutors. Stimulated by the "chat room problem", and influenced by the CAPTCHA project of Blum et al. (2000), we propose a variant of the Turing test using pessimal print: that is, low-quality images of machine-printed text synthesized pseudo-randomly over certain ranges of words, typefaces, and image degradations. We show experimentally that judicious choice of these ranges can ensure that the images are legible to human readers but illegible to several of the best present-day optical character recognition (OCR) machines. Our approach is motivated by a decade of research on performance evaluation of OCR machines and on quantitative stochastic models of document image quality. The slow pace of evolution of OCR and other species of machine vision over many decades suggests that pessimal print will defy automated attack for many years. Applications include 'bot' barriers and database rationing.

Printing, photocopying, and scanning processes degrade the image quality of a document. Statistical models of these degradation processes are crucial for document image understanding research. In this paper, we present a statistical methodology that can be used to validate local degradation models. This method is based on a nonparametric, two-sample permutation test. Another standard statistical device, the power function, is then used to choose between algorithm variables such as distance functions. Since the validation and the power function procedures are independent of the model, they can be used to validate any other degradation model. A method for comparing any two models is also described. It uses p-values associated with the estimated models to select the model that is closer to the real world.

We estimate, using synthetically generated images, the smallest changes in document image quality that can be distinguished reliably and fully automatically by T. Kanungo's (1996) bootstrapping test. Six parameters of a physics based document image degradation model (H.S. Baird, 1992), are varied, one at time: for each, over a range of parameter value differences, two sets of synthetic images are generated pseudorandomly and the two sets tested for statistical equivalence using Kanungo's method. The rate at which Kanungo's method rejects the hypothesis that the two sets are drawn from the same distribution is analyzed as a function of parameter difference (a specialized "power function"). The finest discriminations afforded by the method are given by the width of the power function at a low fixed reject threshold. The data show that remarkably fine discriminations are possible-often subtler than are evident to visual inspection-for all six parameters. As few as 25 reference images are sufficient. These results suggest that Kanungo's method is sufficiently sensitive to a wide range of physics based image degradations to serve as an engineering foundation for many image quality estimation and OCR engineering purposes.

We describe the architecture of a system for reading machine-printed documents in known predefined tabular-data layout styles. In these tables, textual data are presented in record lines made up of fixed-width fields. Tables often do not rely on line-art (ruled lines) to delimit fields, and in this way differ crucially from fixed forms. Our system performs these steps: copes with multiple tables per page; identifies records within tables; segments records into fields; and recognizes characters within fields, constrained by field-specific contextual knowledge. Obstacles to good performance on tables include small print, tight line-spacing, poor-quality text (such as photocopies), and line-art or background patterns that touch the text. Precise skew-correction and pitch-estimation, and high-performance OCR using neural nets proved crucial in overcoming these obstacles. The most significant technical advances in this work appear to be algorithms for identifying and segmenting records with known layout, and integration of these algorithms with a graphical user interface (GUI) for defining new layouts. This GUI has been ergonomically designed to make efficient and intuitive use of exemplary images, so that the skill and manual effort required to retarget the system to new table layouts are held to a minimum. The system has been applied in this way to more than 400 distinct tabular layouts. During the last three years the system has read over fifty million records with high accuracy.

This paper discusses some technical aspects of multimedia messaging systems. By 'messages', we mean non-real-time communications containing various media (text, speech, FAXed document images, video, electronic ink, etc.), passing between users over enterprise-wide telephony and data networks, and collecting in 'multimedia mailboxes'. Messaging, like 'digital libraries', is an application domain for indexing, retrieval, searching, etc.-but it offers some significantly different challenges and opportunities. We discuss some technical implications of the expected contents of messages, waiting time in mailboxes, and the particular needs of messaging users.

Many obstacles to progress in image pattern recognition result from the fact that per-class distributions are often too irregular to be well-approximated by simple analytical functions. Simulation studies offer one way to circumvent these obstacles. We present three closely related studies of machine-printed character recognition that rely on synthetic data generated pseudo-randomly in accordance with an explicit stochastic model of document image degradations. The unusually large scale of experiments - involving several million samples that makes this methodology possible have allowed us to compute sharp estimates of the intrinsic difficulty (Bayes risk) of concrete image recognition problems, as well as the asymptotic accuracy and domain of competency of classifiers.

this report, combine decisions (or statistics) from all the text lines on the page to support a final decision at the page level. The order of execution is as follows. Within a page, we visit each text line (in arbitrary order), extracting features and computing statistics for each (details of these will be given below). Each text line is immediately classified as Asian or Latin (or rejected), in a way that requires no prior knowledge of the orientation. Feature statistics which support other decisions are accumulated and, at the end of the page, the remaining decisions are made in the following order. First, we distinguish between Asian and Latin scripts, determined by a majority vote of the text-line classifications already decided. If the page's script is Asian, we then decide the page's language using feature statistics accumulated from all text lines (again, at any orientation); then, using knowledge of the Asian-script page's language, we detect the page's orientation. If the page's script is Latin, we detect the page's orientation first and then decide the page's language. An overview of this process is shown in Figure 1. Details of the methods used for each of these decisions, along with test results, are discussed in the sections that follow. But first, we briefly summarize the training and test data used. 3 Training and Testing Data

Two document degradation models that model the perturbations introduced during the document printing and scanning process were proposed recently. Although degradation models are very useful, it is very important that we validate these models by comparing the synthetically generated images against real images. In recent past, two different validation procedures have also been proposed to validate such document degradation models. These validation procedures are functions of sample size and various distance functions. In this paper we outline a statistical methodology to compare the various validation schemes that result by using different distance functions. This methodology is general enough to compare any two validation schemes.

We have demonstrated a high degree of automation in the engineering of complex machine vision systems, by building ten printed-text page readers, each specialized to a European language, at the pace of one language per week. The page readers provide these functions: page layout analysis, polyfont symbol recognition, typographical morphology, lexicon-driven contextual analysis, and Unicode output encoding. The accuracy and speed of the resulting readers are usably high, and can be easily improved if required by comparatively routine enhancements of subsystems. This exercise illustrates the advantages of a research strategy that emphasizes versatility before, but not at the expense of, accuracy and speed.

Describes an experiment in estimating the Bayes error of an image classification problem: a difficult, practically important, two-class character recognition problem. The Bayes error gives the "intrinsic difficulty" of the problem since it is the minimum error achievable by any classification method. Since for many realistically complex problems, deriving this analytically appears to be hopeless, the authors approach the task empirically. The authors proceed first by expressing the problem precisely in terms of ideal prototype images and an image defect model, and then by carrying out the estimation on pseudorandomly simulated data. Arriving at sharp estimates seems inevitably to require both large sample sizes-in the authors' trial, over a million images-and careful statistical extrapolation. The study of the data reveals many interesting statistics, which allow the prediction of the worst-case time/space requirements for any given classifier performance, expressed as a combination of error and reject rates.

A method for analyzing the structure of the white background in document images is described, along with applications to the problem of isolating blocks of machine-printed text. The approach is based on computational-geometry algorithms for off-line enumeration of maximal white rectangles and on-line rectangle unification. These support a fast, simple, and general heuristic for geometric layout segmentation, in which white space is covered greedily by rectangles until all text blocks are isolated. Design of the heuristic can be substantially automated by an analysis of the empirical statistical distribution of properties of covering rectangles: for example, the stopping rule can be chosen by Rosenblatt’s perceptron training algorithm. Experimental trials show good behavior on the large and useful class of textual Manhattan layouts. On complex layouts from English-language technical journals of many publishers, the method finds good segmentations in a uniform and nearly parameter-free manner. On a variety of non-Latin texts, some with vertical text lines, the method finds good segmentations without prior knowledge of page and text-line orientation.

The accuracy of today's document recognition algorithms falls abruptly when image quality degrades even slightly. In an effort to surmount this barrier, researchers have in recent years intensified their study of explicit, quantitative, parameterized models of the image defects that occur during printing and scanning. The author reviews the recent literature and discusses the form these models might take. A preview of a large public-domain database of character images, labeled with ground-truth including all defect model parameters, is given. The use of massive pseudo-randomly generated training sets for the construction of high-performance decision trees for preclassification is described. In a more theoretical vein, the author reports preliminary results in the estimation of the intrinsic error of precisely-specified text recognition problems. Finally, the author calls attention to some open problems.>

The authors describe an experiment in the construction of perfect metrics for minimum-distance classification of character images. A perfect metric is one that, with high probability, is zero for correct classifications and non-zero for incorrect classifications. They promise excellent reject behavior in addition to good rank ordering. The approach is to infer from the training data faithful but concise representations of the empirical class-conditional distributions. In doing this, the authors have abandoned many visual simplifying assumptions about the distributions, e.g., that they are simply-connected, unimodal, convex, or parametric (e.g., Gaussian). The method requires unusually large and representative training sets, which we provide through pseudorandom generation of training samples using a realistic model of printing and imaging distortions. The authors illustrate the method on a challenging recognition problem: 3755 character classes of machine-print Chinese, in four typefaces, over a range of text sizes. In a test on over three million images, the perfect-metric classifier achieved better than 99% top-choice accuracy. In addition, it is shown that it is superior to a conventional parametric classifier.>

A system for isolating blocks, lines, words, and symbols within images of machine-printed textual documents that is, to a large existent, independent of language and writing system is described. This is achieved by exploiting a small number of nearly universal typesetting and layout conventions. The system does not require prior knowledge of page orientation (module 90/spl deg/), and copes well with nonzero skew and shear angles (within 10/spl deg/). Also it locates blocks of text without reliance on detailed a priori layout models, and in spite of unknown or mixed horizontal and vertical text-line orientations. Within blocks, it infers text-line orientation and isolates lines, without knowledge of the language, symbol set, text sizes, or the number of text lines. Segmentation into words and symbols, and determination of reading order, normally require some knowledge of the language: this is held to minimum by relying on shape-driven algorithms. The underlying algorithms are based on Fourier theory, digital signal processing, computational geometry, and statistical decision theory. Most of the computation occurs within algorithms that possess unambiguous semantics (that is, heuristics are kept to a minimum). The effectiveness of the method on English, Japanese, Hebrew, Thai, and Korean documents is discussed.>

An experimental printed-page reader that is easy to adapt to various languages is described. Changing the target language may involve simultaneous changes in symbol sets, typefaces, sizes of text, page layouts, linguistic contexts, and imaging defects. The strategy has been to isolate the effects of these sources of variation within separate, independent engineering subsystems. In this way, it has been possible to construct, with a minimum of manual effort, classifiers for arbitrary combinations of symbols, typefaces, sizes, and imaging defects. An attempt has been made to rid the algorithms of all language-specific rules, relying instead on automatic learning from examples and generalized table-driven methods. For some tasks it has been feasible to avoid language dependency altogether. Linguistic context can be exploited through data-directed filtering algorithms in a uniform and modular manner, so that preexisting tools developed by computational linguistics can readily be applied. These principles are illustrated by trials on English, Swedish, Tibetan, and special technical texts.>

A technique for image segmentation using shape-directed covers is described and applied to the fully automatic analysis of complex printed-page layouts. The structure of the background (white space) is analyzed, assisted by an enumeration of all maximal white rectangles. For this enumeration, the most computationally expensive step, an algorithm has been developed that, aside from a sort, achieves an expected runtime linear in the number of black connected components. The crucial engineering decision is the specification of a partial order on white rectangles to express domain-specific knowledge of preferred shapes and sizes. This order determines a sequence of partial covers of the background, and thus, a sequence of nested page segmentations. In experimental trials on Manhattan layouts, good segmentations often occur early in this sequence, using a simple and uniform shape-direction rule. This is a global-to-local strategy, which for some tasks is superior to strategies currently emphasized in the literature, including bottom-up and top-down.>

An application of back-propagation networks to handwritten zip code recognition is presented. Minimal preprocessing of the data is required, but the architecture of the network is highly constrained and specifically designed for the task. The input of the network consists of size-normalized images of isolated digits. The performance on zip code digits provided by the US Postal Service is 92% recognition, 1% substitution, and 7% rejects. Structured neural networks can be viewed as statistical methods with structure which bridge the gap between purely statistical and purely structural methods.>

By applying semantic analysis to images of extended passages of text, several volumes of a chess encyclopedia have been read with high accuracy. Although carefully proofread, the books were poorly printed and posed a severe challenge to conventional page-layout analysis and character-recognition methods. An experimental page-reader system performed strictly top-down layout analysis for identification of columns, lines, words, and characters. This proceeded rapidly and reliably thanks to a recently developed skew-estimation technique. Resegmentation of broken, touching, and dirty characters was handled in an efficient and integrated manner by a heuristic search operating on isolated words. By analyzing the syntax of game descriptions and applying the rules of chess, the error rate was reduced by a factor of 30 from what was achievable through shape analysis alone. Several computer vision systems integration issues suggested by this experience are discussed.>

We describe the current state of a system that recognizes printed text of various fonts and sizes for the Roman alphabet. The system combines several techniques in order to improve the overall recognition rate. Thinning and shape extraction are performed directly on a graph of the run-length encoding of a binary image. The resulting strokes and other shapes are mapped, using a shape-clustering approach, into binary features which are then fed into a statistical Bayesian classifier. Large-scale trials have shown better than 97 percent top choice correct performance on mixtures of six dissimilar fonts, and over 99 percent on most single fonts, over a range of point sizes. Certain remaining confusion classes are disambiguated through contour analysis, and characters suspected of being merged are broken and reclassified. Finally, layout and linguistic context are applied. The results are illustrated by sample pages.

The task of coordinating manipulators, vision and force sensors, and simpler devices within a robotic workcell is often impeded by a proliferation of nonstandard command interfaces and the rigidity of available control languages. However, many robotic devices provide a set of ASCII commands via an RS-232C port. To support fast prototyping in an adaptive robotics laboratory, we have chosen to extend the general-purpose language Pascal so that the full command repertoire of such devices can be invoked in a uniform way. A succinct syntax has been designed, using semantic overloading, that mirrors the dialogue between workcell controller and device. For example, the acts of issuing a command and receiving its reply can be combined or separated syntactically, permitting a variety of synchronizing strategies. Asynchronous device activity can be overlapped, since each device's dialogue is handled by a dedicated task within a multi-tasking operating system. For further conciseness, formatting of commands and parsing of replies are device- and datatype-sensitive. Many idiosyncrasies of the devices are effectively hidden from the programmer, including awkward formats designed for interactive human use. Errors arising in communication links or devices are automatically trapped and optionally referred to the operator. The implementation supports the Unimation Puma 560 Mark II and Control Automation CAR-1000 manipulators, and the Automatix AV-II and SRI vision systems.