The task of writer verification is to provide a likelihood score for whether the queried and known handwritten image samples belong to the same writer or not. Such a task calls for the neural network to make it's outcome interpretable, i.e. provide a view into the network's decision making process. We implement and integrate cross-attention and soft-attention mechanisms to capture the highly correlated and salient points in feature space of 2D inputs. The attention maps serve as an explanation premise for the network's output likelihood score. The attention mechanism also allows the network to focus more on relevant areas of the input, thus improving the classification performance. Our proposed approach achieves a precision of 86% for detecting intra-writer cases in CEDAR cursive “AND” dataset. Furthermore, we generate meaningful explanations for the provided decision by extracting attention maps from multiple levels of the network.

We propose an end-to-end learning method based on statistical features extracted on set-of-samples level as a step toward solving the writer verification problem which is about deciding whether two handwriting sources are identical given handwriting samples from the two sources. The set-of-samples features are extracted on top of single sample features. Single sample features are traditionally learned using sample-to-sample comparison similarity learning. In this paper, we learn it as a sub-module of an end-to-end two-sets-of-samples comparison similarity learning. We compare human-engineered (GSC features) single sample features and automatically learned features using convolutional neural networks (CNN) and find the latter performs better with abundant training data and data augmentation. The statistical features on sets of samples capture both inner-writer variabilities and intra-writer variabilities. Experiments are conducted on frequently occurring words and digraphs such as "and" and "th" from around 1500 writers. We perform experiments on pre-training using sample-to-sample similarity learning and end-to-end fine-tuning. The results show that two-sets-of-samples comparison gives much better accuracy than sample-to-sample comparison. In addition, the end-to-end training based on parametric statistical features gives better accuracy than standard distribution comparison tests such as the K-S test based on distance space.

We propose an effective Hybrid Deep Learning (HDL) architecture for the task of determining the probability that a questioned handwritten word has been written by a known writer. HDL is an amalgamation of Auto-Learned Features (ALF) and Human-Engineered Features (HEF). To extract auto-learned features we use two methods: First, Two Channel Convolutional Neural Network (TC-CNN); Second, Two Channel Autoencoder (TC-AE). Furthermore, human-engineered features are extracted by using two methods: First, Gradient Structural Concavity (GSC); Second, Scale Invariant Feature Transform (SIFT). Experiments are performed by complementing one of the HEF methods with one ALF method on 150000 pairs of samples of the word "AND" cropped from handwritten notes written by 1500 writers. Our results indicate that HDL architecture with AE-GSC achieves 99.7% accuracy on seen writer dataset and 92.16% accuracy on shuffled writer dataset which out performs CEDAR-FOX, as for unseen writer dataset, AE-SIFT performs comparable to this sophisticated handwriting comparison tool.

Visual restoration and recognition are traditionally addressed in pipeline fashion, i.e. denoising followed by classification. Instead, observing correlations between the two tasks, for example clearer image will lead to better categorization and vice visa, we propose a joint framework for visual restoration and recognition for handwritten images, inspired by advances in deep autoencoder and multi-modality learning. Our model is a 3-pathway deep architecture with a hidden-layer representation which is shared by multi-inputs and outputs, and each branch can be composed of a multi-layer deep model. Thus, visual restoration and classification can be unified using shared representation via non-linear mapping, and model parameters can be learnt via backpropagation. Using MNIST and USPS data corrupted with structured noise, the proposed framework performs at least 20% better in classification than separate pipelines, as well as clearer recovered images.

Social dynamics is concerned primarily with interactions among individuals and the resulting group behaviors, modeling the temporal evolution of social systems via the interactions of individuals within these systems. In particular, the availability of large-scale data from social networks and sensor networks offers an unprecedented opportunity to predict state-changing events at the individual level. Examples of such events include disease transmission, opinion transition in elections, and rumor propagation. Unlike previous research focusing on the collective effects of social systems, this study makes efficient inferences at the individual level. In order to cope with dynamic interactions among a large number of individuals, we introduce the stochastic kinetic model to capture adaptive transition probabilities and propose an efficient variational inference algorithm the complexity of which grows linearly — rather than exponentially— with the number of individuals. To validate this method, we have performed epidemic-dynamics experiments on wireless sensor network data collected from more than ten thousand people over three years. The proposed algorithm was used to track disease transmission and predict the probability of infection for each individual. Our results demonstrate that this method is more efficient than sampling while nonetheless achieving high accuracy.

Restricted Boltzmann machines (RBMs) and their variants have attracted a lot of attention recently. They have been applied widely, e.g., In handwriting recognition, document categorization and object recognition. Unfortunately, an RBM requires a large parameter space since it is a fully-connected bipartite graph, especially with high dimensional input spaces. Moreover, it is still unclear how it selects discriminative features for classification problems. This necessitates the selection of effective and discriminative features for recognition. In this paper, we propose a Noisy-Or discriminative restricted Boltzmann machine (Abbr. As NDRBM or Noisy-Or RBM), which combines RBM and Noisy-Or gate function. On the one hand, it can greatly reduce the parameter space. Furthermore, this model extends the RBM into a multiple instance learning scenario-to help select discriminative features or regions. An approximate approach is proposed to make the NDRBM practical. We apply our method on handwriting style development recognition and recognition rates are observed to be better than competitive baselines on two data sets (cursive and handprint data from Grades 2-4).

The task of writer identification is based on the assumption of individuality of handwriting. While previous studies of individuality have considered different statistical extremes: representative population of the United States and a population of twins, the present study takes a third approach-an analysis of handwriting over time, specifically children's handwriting as they develop in early grades. Using extended handwriting samples of children in Grades 2-4, the commonly occurring word and written in cursive style as well as hand-print were extracted. The samples were assigned feature values by human questioned document examiners using a truthing-tool. The distribution of the characteristics were analyzed by first constructing probabilistic graphical models of the data. Information theoretic measures-entropy and relative entropy were computed using samples generated from the models. The measures are used to determine the range of variations in handwriting and the changes that take place between grades. Results from this early study indicates that handwriting develops with more conformity in grades 2 and 3, when they are first taught, and diverges as they grow older, between grades 3 and 4.

Bayesian Networks are probabilistic models of data that are useful to answer probabilistic queries. Existing algorithms use either local measures of deviation from independence or global likelihood measures. They are based on probabilistic correlation, so the directionality of the model lacks the causal meaning as we expected. We tackle this problem from a new perspective using causality, which is a more fundamental measure than correlation. Integrating both the global and local views of causal inference, the proposed computationally efficient algorithm learns a high quality Bayesian network without using any score-based searching. Given a partial directed acyclic graph, causal pairs with the highest accuracy are inferred with the fewest number of pair wise causal inferences. Specifically, with discrete data, the χ2statistical test is used to identify the most dependent and possible causal pairs. Furthermore, the learned causality is forward-propagated. Experiments on handwriting data show that, besides the ability of causal inference, our algorithm performs better than two previous algorithms, one based on branch-and-bound search, and the other a greedy algorithm using χ2tests and a log-loss function. The learned structure not only has lowest loss in representing the data, but also reveals underlying causal relationships which are useful for scientific discovery.

Probabilistic models of characteristics of handwritten words are useful in forensic document examination since they can be used to answer queries such as: determine the rarity of a given style of writing of the word, find the probability of observing those characteristics in a representative database of given size, etc. The task considered here is to use a training set of samples of a word written by a representative population of individuals (with each individual's writing of the word being described by a fixed set of discrete categorical variables), to construct directed probabilistic graphical models (Bayesian networks or BNs) and then use such models to answer probabilistic queries. However, since the BN structure learning problem is NP-hard, we propose an approximate method and analyze its performance and complexity. The proposed algorithm uses a local measure of deviance from independence (chi-squared tests between pairs of variables) and a global score (log-loss). The method builds the BN structure incrementally, by adding directed edges with high deviance and choosing the edge direction to minimize log-loss. The method is evaluated with samples of the word and obtained from a representative population of the United States with descriptive characteristic sets that are different for cursive writing and for hand-printing. For several samples obtained from the BN, the probability of random correspondence (PRC) is inferred. A measure of the discriminatory power of the characteristic set (conditional PRC) is also determined. The computational complexity of determining the probability of finding a similar one to a given sample, within a tolerance, in a database of given size, is discussed.

Forensic identification is the task of determining whether or not observed evidence arose from a known source. In every forensic domain, it is useful to determine the probability that the evidence and known can be attributed to the same individual so that identification/exclusion opinions can be accompanied by a probability statement. At present, in most forensic domains outside of DNA, it is not possible to make such a statement since the necessary probability distributions cannot be computed with reasonable accuracy. It involves determining a likelihood ratio (LR) -the ratio of the joint probability of the evidence and source under the identification hypothesis (that the evidence came from the source) and under the exclusion hypothesis (that the evidence did not arise from the source). The joint probability approach is computationally and statistically infeasible when the number of variables is even moderately large, e.g., the number of parameters to be determined is exponential with the number of variables. An approximate method is to replace the joint probability by another probability: that of (dis)imilarity between evidence and object under the two hypotheses. While this distance-based approach reduces to linear complexity with the number of variables, it is an oversimplification. A third method, which decomposes the LR into a product of two factors, one based on distance and the other on rarity, has intuitive appeal-forensic examiners assign higher importance to rare attributes in the evidence. Theoretical discussions of the three approaches and empirical evaluations done with several data types (continuous features, binary features, multinomial and graph) will be described. Experiments with handwriting using binary and multinomial features show that the distance and rarity method is significantly better than the distance only method. Work was done with Yi Tang.

During the last few years the pattern analysis and machine intelligence community has developed automation tools for forensic document examination (FDE), in particular for determining whether a given handwriting specimen can be attributed to known writing. As with other expert systems, such as for medical diagnosis, current automation tools are useful only as part of a larger manually-intensive procedure. Defining a computational approach for the overall problem not only places these tools in context but also helps validate and improve existing manual procedures. We consider the standard work flow in FDE of handwritten items and annotate the steps where automation is available or possible. A well-known ransom note case is considered as an example, where there are multiple questioned documents, testing for multiple writers of the same document, determining whether the writing is disguised, known writing is formal while questioned writing is informal, etc. The findings for the particular ransom note case using the tools are given. Observations are made for developing a more fully automated approach to FDE.

Identifying unusual or unique characteristics of an observed sample in useful in forensics in general and handwriting analysis in particular. Rarity is formulated as the probability of letter formations characterized by a set of features. Modeling the distribution as a probabilistic graphical model several probabilities are inferred: the probability of random correspondence (PRC) as a measure of the discriminatory power of the characteristics, conditional PRC associated with a given sample and the probability of finding a similar one within tolerance in a database of given size. Using the most commonly occurring letter pair "th" and characteristics specified by questioned document examiners, the highest probability formation and low probability formations in a database are determined. Computational issues in scaling the methods are discussed.

The ellipse is a fundamental shape in both natural and man-made objects and hence frequently encountered in images. Existing ellipse detection algorithms, viz., randomized Hough transform (RHT) and multi-population genetic algorithm (MPGA), have disadvantages. The RHT performs poorly with multiple ellipses and MPGA has a high false positive rate for complex images. The proposed algorithm selects random points using constraints of smoothness, distance and curvature. In the process of sampling, parameters of potential ellipses are progressively learnt to improve parameter accuracy. New probabilistic fitness measures are used to verify ellipses extracted: ellipse quality based on the Ramanujan approximation and completeness. Experiments on synthetic and real images show performance better than RHT and MPGA in detecting multiple, deformed, full or partial ellipses in the presence of noise and interference.

Over the last century forensic document science has developed progressively more sophisticated pattern recognition methodologies for ascertaining the authorship of disputed documents. We present a writer verification method and an evaluation of its performance on historical documents with known and unknown writers. The questioned document is compared against handwriting samples of Herman Melville, a 19th century American author who has been hypothesized to be the writer as well as against samples crafted by several writers from the same time period. The comparison led to a high confidence result to the questioned document's writer ship, as well as gives evidence for the validity of the writer verification method in the context of historical documents. Such methodology can be applied to many such questioned historical documents, both in literary and legal fields.

One of the most challenging tasks in analyzing handwritten documents is to tackle the inherent skew that is introduced due to writer's handwriting, segment the handwritten lines and estimate the skew angle and its direction. Complexities such as variable spacing between words and lines, variable line skew, variable line width and height, overlapping words and lines etc. arises in handwritten documents unlike printed documents. This paper explores the application of Radon transform to process handwritten documents and compares its performance with Hough transform while segmenting lines and detecting skew. The computational advantage of Radon transform over Hough transform with equally good results makes it an ideal choice to process handwritten documents.

Signature verification is a common task in forensic document analysis. The goal is to make a decision whether a questioned signature belongs to a set of known signatures of an individual or not. In a typical forgery case a very limited number of known signatures may be available, with as few as four or five knows. Here we describe a fully Bayesian approach which overcomes the limitation of having too few genuine samples. The algorithm has three steps: Step 1: Learn prior distributions of parameters from a population of known signatures; Step 2: Determine the posterior distributions of parameters using the genuine samples of a particular person; Step 3: Determine probabilities of the query from both genuine and forgery classes and the Log Likelihood Ratio (LLR) of the query. Rather than give a hard decision, this method provides a probabilistic measure LLR of the decision and the performance of the Bayesian Learning is improved especially in the case of limited known samples.

Core point prediction is of critical importance to latent fingerprints individuality assessment. While tremendous effort have been made in core point detection, locating core points in latent fingerprints continues to be a difficult problem because latent prints usually contain only partial images with core points left outside the print. A novel method is proposed that predicts the locations and orientations of core points for latent fingerprints. The method is based on Gaussian processes and provides prediction in interpretations of probability rather than binary decision. The accuracy of the method is illustrated by experiments on a real-life latent fingerprint data set.

A method for computing the rarity of latent fingerprints represented by minutiae is given. It allows determining the probability of finding a match for an evidence print in a database of n known prints. The probability of random correspondence between evidence and database is determined in three procedural steps. In the registration step the latent print is aligned by finding its core point; which is done using a procedure based on a machine learning approach based on Gaussian processes. In the evidence probability evaluation step a generative model based on Bayesian networks is used to determine the probability of the evidence; it takes into account both the dependency of each minutia on nearby minutiae and the confidence of their presence in the evidence. In the specific probability of random correspondence step the evidence probability is used to determine the probability of match among n for a given tolerance; the last evaluation is similar to the birthday correspondence probability for a specific birthday. The generative model is validated using a goodness-of-fit test evaluated with a standard database of fingerprints. The probability of random correspondence for several latent fingerprints are evaluated for varying numbers of minutiae.

We present a framework of adaptive (self-training) semi-supervised learning as applied to the problem of handwriting recognition. Each problem instance itself is treated as a set of unlabeled "training'' data; a general model, trained on a set of labeled data, is adapted into an appropriate problem specific model. Learning is continued until convergence is reached, yielding better results than the generalized model alone. An implementation of the framework was tested on English and Arabic handwritten documents. The initial supervised learning model gave word recognition performance of 81% and 67% for English and Arabic respectively. The subsequent semi-supervised learning adjustments yielded 86% and 77% word recognition performance for English and Arabic respectively.

Expanding on an earlier study to objectively validate the hypothesis that handwriting is individualistic, we extend the study to include handwriting in the Arabic script. Handwriting samples from twelve native speakers of Arabic were obtained. Analyzing differences in handwriting was done by using computer algorithms for extracting features from scanned images of handwriting. Attributes characteristic of the handwriting were obtained, e.g., line separation, slant, character shapes, etc. These attributes, which are a subset of attributes used by forensic document examiners (FDEs), were used to quantitatively establish individuality by using machine learning approaches. Using global attributes of handwriting, the ability to determine the writer with a high degree of confidence was established. The work is a step towards providing scientific support for admitting handwriting evidence in court.

Impression evidence in the form of shoe-prints are commonly found in crime scenes. A critical step in automatic shoe-print identification is extraction of the shoe-print pattern. It involves isolating the shoe-print foreground (impressions made by the shoe) from the remaining elements (background and noise). The problem is formulated as one of labeling the regions of a shoeprint image as foreground/background. It is formulated as a machine learning task which is approached using a probabilistic model, i.e., conditional random fields (CRFs). Since the model exploits the inherent long range dependencies that exist in the shoe-print it is more robust than other approaches, e.g., neural networks and adaptive thresholding of grey-scale images into binary. This was demonstrated using a data set of 45 shoeprint image pairs representing latent and known shoe-print images.

Generative models of pattern individuality attempt to learn the distribution of observed quantitative features to determine the probability of two random patterns being the same. Considering fingerprint patterns, Gaussian distributions have been previously used for minutiae location and von-Mises distributions for minutiae orientation so as to determine the probability of random correspondence (PRC) between two fingerprints. Motivated by the fact that ridges have not been modeled in generative models and the benefits from ridge points in fingerprint matching, ridge information is incorporated into the generative model by using the distribution for ridge point location and orientation. The proposed model offers a more accurate fingerprint representation from which more reliable PRCs can be computed. Based on parameters estimated from fingerprint databases, PRCs using ridge information are seen to be much smaller than PRCs computed with only minutiae.

The biometric verification task is to determine whether or not an input and a template belong to the same individual. In the context of automatic fingerprint verification the task consists of three steps: feature extraction, where features (typically minutiae) are extracted from each fingerprint, scoring, where the degree of match between the two sets of features is determined, and decision, where the score is used to accept or reject the hypothesis that the input and template belong to the same individual. The paper focuses on the final decision step, which is a binary classification problem involving a single score variable. The commonly used decision method is to learn a score threshold from a labeled set of inputs and templates, by first determining the receiver operating characteristic (ROC) of the task. The ROC method works well when there is a well-registered fingerprint image. The paper shows that when there is uncertainty due to fingerprint quality, e.g. the input is a latent print or a partial print, the decision method can be improved by using the likelihood ratio of match/non match. The likelihood ratio is obtained by modeling the distributions of same finger and different finger scores using parametric distributions. The parametric forms considered are Gaussian and Gamma distributions whose parameters are learnt from labeled training samples. The performances of the likelihood and ROC methods are compared for varying numbers of minutiae points available for verification. Using either Gaussian or Gamma parametric distributions, the likelihood method has a lower error rate than the ROC method when few minutiae points are available. Likelihood and ROC methods converge to the same accuracy as more minutiae points are available.

Generative models of pattern individuality attempt to represent the distribution of observed quantitative features, e.g., by learning parameters from a database, and then use such distributions to determine the probability of two random patterns being the same. Considering fingerprint patterns, Gaussian distributions have been previously used for minutiae location and von-Mises distributions for minutiae orientation so as to determine the probability of random correspondence (PRC) between two fingerprints. Motivated by the fact that ridges have not been modeled in generative models, and using representative ridge points in fingerprint matching, ridge information is incorporated into the generative model by using a third distribution for ridge types. The joint probability of minutiae location, minutiae orientation and ridge type is modeled as a mixture distribution. The proposed model offers a more accurate fingerprint representation from which more reliable PRCs can be computed. Based on parameters estimated from fingerprint databases, PRCs using ridge types are seen to be much smaller than PRCs computed with only minutiae.

In recent years, mathematical, statistical and computer science methods have found extensive application in developing new procedures for crime investigation, prosecution and the enforcement of law. Computer-based methods have also become important tools for performing certain forensic functions. Yet, knowledge and intuition of the human expert plays a central role. This paper gives a brief overview of the potential of computational methods in forensics. The state of the art is described, some practical examples are given and a viewpoint is expressed that the methods can be extended to functions that currently rely only on expert knowledge.

Document examiners use a variety of features to analyze a given handwritten document for writer verification. The challenge in the automatic classification of a pair of documents to belong to the same or different writer, are both (i)The task of proper selection and extraction of features from the handwritten document and (ii)The use of a proper model that is capable of utilizing the true discriminatory power of these features for classification. This paper describes the use of content specific skeleton based features for characters and pairs of characters (bigrams) and ascertains their discriminatory power. A triangulation skeletonisation procedure is first used to obtain the skeleton of the character(s), and features are computed from the skeleton. Experiments and results are conducted on content specific features extracted for two most frequently occurring bigrams (th, he), and characters (d and f). A neural network based on a Bayesian formulation was used to ascertain the discriminability power of these features. To combine these features with previously existing writer verification features, an alternative Naive Bayes model is also described and evaluated. From the results obtained, we conclude that bigram th has the highest discriminatory power followed by character d, f and bigram he. Also the paper highlights the significant increase in performance of writer verification(^ 15% more) with the use of Bayesian neural networks as against the Naive Bayes model.

The paper describes a lexicon driven approach for word recognition on handwritten documents using conditional random fields (CRFs). CRFs are discriminative models and do not make any assumptions about the underlying data and hence are known to be superior to hidden Markov models (HMMs) for sequence labeling problems. For word recognition, the document is first segmented into word images using an existing neural network based algorithm. Each word image is then over segmented into a number of small segments such that the combination of segments forms character images. Segment(s) is/are labeled as characters with probability evaluated from the CRF model. The total probability of a word image representing an entry from the lexicon is computed using a dynamic programming algorithm which evaluates the optimal combination of segments.

The problem of Writer Verification is to make a decision of whether or not two handwritten documents are written by the same person. Providing a strength of evidence for any such decision is an integral part of the writer verifi- cation problem. The strength of evidence should incorpo- rate (i) The amount of information compared in each of the two documents (line/half page/full page etc.), (ii) The na- ture of content present in the document (same/different con- tent), (iii) Features used for comparison and (iv) The error rate of the model used for making the decision. This pa- per describes the statistical model used for writer verifica- tion and also introduces a mathematical formulation to in- clude the above four mentioned parameters, for calculating strength of evidence of same/different writer. The statisti- cal model uses Gamma and Gaussian densities to paramet- rically model the distance space distribution arising from comparing ensemble of pairs of documents. The strength of evidence is mapped to a 9-point qualitative scale for the decision; one that is often used by questioned document ex- aminers. Experiments and results show that with increase in information content from just a single word to a full page of document, the verification accuracy of the model increases.

An approach to off-line signature verification, one with an on-line flavor, is described. A sequence of data is obtained by tracing the exterior contour of the signature which allows the application of string-matching algorithms. The upper and lower contours of the signature are first determined by ignoring small gaps between signature components. The contours are combined into a single sequence so as to define a pseudo-writing path. To match two signatures a non-linear normalization method, viz., dynamic time warping, is applied to segment them into curves. Shape descriptors based on Zernike moments are extracted as features from each segment. A harmonic distance is used for measuring signature similarity. Performance is significantly better than that of a word-shape based signature verification method. When the two methods are combined, the overall performance is significantly better than either method alone. With a database of 1320 genuines and 1320 forgeries the combination method has an accuracy of 95% (with 20% rejection) which is comparable to that of on-line systems.

A statistical model for determining whether a pair of documents, a known and a questioned, were written by the same individual is proposed. The model has the following four components: (i) discriminating elements, e.g., global features and characters, are extracted from each document; (ii) differences between corresponding elements from each document are computed; (iii) using conditional probability estimates of each difference, the log-likelihood ratio (LLR) is computed for the hypotheses that the documents were written by the same or different writers; the conditional probability estimates themselves are determined from labeled samples using either Gaussian or gamma estimates for the differences assuming their statistical independence; and (iv) distributions of the LLRs for same and different writer LLRs are analyzed to calibrate the strength of evidence into a standard nine-point scale used by questioned document examiners. The model is illustrated with experimental results for a specific set of discriminating elements.

This paper describes a novel approach for signature verification and identification in an offline environment based on a quasi-multiresolution technique using GSC (Gradient, Structural and Concavity) features for feature extraction. These features when used at the word level, instead of the character level, yield promising results with accuracies as high as 78% and 93% for verification and identification, respectively. This method was successfully employed in our previous theory of individuality of handwriting developed at CEDAR — based on obtaining within and between writer statistical distance distributions. In this paper, exploring signature verification and identification as offline handwriting verification and identification tasks respectively, we depict a mapping from the handwriting domain to the signature domain.

Most fast k-nearest neighbor (k-NN) algorithms exploit metric properties of distance measures for reducing computation cost and a few can work effectively on both metric and nonmetric measures. We propose a cluster-based tree algorithm to accelerate k-NN classification without any presuppositions about the metric form and properties of a dissimilarity measure. A mechanism of early decision making and minimal side-operations for choosing searching paths largely contribute to the efficiency of the algorithm. The algorithm is evaluated through extensive experiments over standard NIST and MNIST databases.

Classifying an unknown input is a fundamental problem in pattern recognition. A common method is to define a distance metric between patterns and find the most similar pattern in the reference set. When patterns are in binary feature vector form, there have been two approaches to improve the performance over the equal-weighted Hamming distance metric. One is to give different weights to different features using an optimization technique, and the other is to use a similarity measure that gives full credit to features present in both patterns and the less credit to those absent from both patterns. Both approaches have been reported to perform better than the na ve Hamming distance approach. In this paper, we propose to combine these two approaches using a genetic algorithm to optimize weights. Experimental results show that this method is superior to conventional measures in an OCR application.

The analysis of handwritten documents from the viewpoint of determining their authorship has great bearing on the criminal justice system. In many cases, only a limited amount of handwriting is available and sometimes it consists of only numerals. Using a large number of handwritten numeral images extracted from about 3000 samples written by 1000 writers, a study of the individuality of numerals for identification/verification purposes was conducted. We have studied the individuality of numerals using clusterization and measured the numerals discriminability for verification purposes. The study shows that some numerals present a higher discriminatory power and that their performances for the verification/identification tasks are very different. 1.

The Dempster-Shafer Theory of Evidence is an estab-lished method for combining different sources of informa-tion. In this paper we explore ways to improve the combina-tion performance by building a better BPA for each clas-sifier using both “global ” and “local classifier informa-tion. We propose modifications to two well-known BPA-computation methods to make them better suited for com-bining Type-III classifiers. We also explore the use of compound hypotheses when a classifier cannot confidently choose between the top two returned classes. Experimental tests demonstrate the superiority of some of the approaches proposed here on the numeral recognition

... (words) is the key for obtaining the discriminating elements of handwriting. While allographs usually inhabit in words and segregation of a word into allographs is more subjective than objective, especially for cursive writing, analysis of handwritten words is a natural and better option. In this study, a handwritten word image is characterized by gradient, structural, and concavity features, and individuality of handwritten words is experimented through writership identification and verification on over 12,000 word images extracted from 3000 handwriting samples of 1000 individuals in U.S.. Experimental results show that handwritten words are very effective in differentiating handwriting and carry more individuality than most handwritten characters (allographs).

Analysis of handwritten characters (allographs) plays an important role in forensic document examination. However, so far there lacks a comprehensive and quantitative study on individuality of handwritten characters. Based on a large number of handwritten characters extracted from handwriting samples of 1000 individuals in US, the individuality of handwritten characters has been quantitatively measured through identification and verification models. Our study shows that in general alphabetic characters bear more individuality than numerals and use of a certain number of characters will significantly outperform the global features of handwriting samples in handwriting identification and verification. Moreover, the quantitative measurement of discriminative powers of characters offers a general guidance for selecting most-informative characters in examining forensic documents. 1

We present a new framework for local feature selection in text filtering. In this framework, a feature set is constructed per category by first selecting a set of terms highly indicative of membership (positive set) and another set of terms highly indicative of nonmembership (negative set), and then combining these two sets. This feature selection framework not only unifies several standard feature selection methods, but also facilitates the proposal of a new method that optimally combines the positive and negative sets. The experimental comparison between the proposed method and standard methods was conducted on six feature selection metrics: chi-square, correlation coefficient, odds ratio, GSS coefficient and two proposed variants of odds ratio and GSS coefficient: OR-square and GSS-square respectively. The results show that the proposed feature selection method improves text filtering performance.

Multi-classifier combination based on Dempster-Shafer theory of evidence has demonstrated it's superior performance. In the approach based on Dempster-Shafer theory, the basic probability assignments for evidence is usually derived from classifiers' global performance. However, our study discovered that while using classifiers' global performance as basic probability assignments doesn't necessarily improve performance under some circumstances, the alternative approach using classifiers' class-wise performance as basic probability assignments does improve the classification performance and outperforms the traditional one based on classifiers' global performances. Basic probability assignments based on classifiers' class-wise performances results in more accurate calculation of beliefs, thus boosts the combinator's performance.

The sub-category classification problem is that of discriminating a pattern to all sub-categories. Not surprisingly, sub-category classification performance estimates are useful information to mine as many researchers are interested in any trend of pattern in specific sub-category. This paper presents a datamining technique to mine a database consisting of experimental and observational unit variables. Experimental unit variables are those attributes which make sub-categories of the entity, e.g., demographic data and observational unit variables are features observed to classify the entity, e.g., test results or handwriting styles, etc. Since there are an enormously large number of subcategories based on the experimental unit variables, we apply the a priori algorithm to select only sub-categories that have enough support among all possible ones in a given database. Those selected sub-categories are then discriminated using observational unit variables as input features to the Artificial Neural Network (ANN) classifier. The importance of this paper is twofold. First, we propose an algorithm that quickly selects all sub-categories that have enough both support and classification rate. Second, we successfully applied the proposed algorithm to the field of handwriting analysis. The task is to determine similarity of handwriting style of a specific group of people. Document examiners are interested in trends in the handwriting of specific groups, e.g., (i) does a male write differently from a female? (ii) can we tell the difference in handwriting of age group between 25 and 45 from others?, etc. Subgroups of white males in the age group 15-24 and white females in the age group 45-64 show 87 % correct classification performance.

This paper describes the issues involved in the design of a system for evaluating improvements in the performance of a real-time address recognition system being used by the United States Postal Service for processing mail-piece images. Evaluation of the performance of recognition systems is normally carried out by measuring the performance of the system on a representative sample of images. Designing a comprehensive and valid testing scenario is a complex task that requires careful attention. Sampling live mail-stream to generate a deck of images representative of the general mail-stream for testing, truthing (generating reference data on a significant number of images), grading and evaluation, and designing tools to facilitate these functions are important topics that need to be addressed. This paper describes the efforts of the United States Postal Service and CEDAR towards developing an infrastructure for sampling, truthing and testing of mail-stream images.

Motivated by several rulings in United States courts concerning expert testimony in general and handwriting testimony in particular, we undertook a study to objectively validate the hypothesis that handwriting is individualistic. Handwriting samples of 1500 individuals, representative of the US population with respect to gender, age, ethnic groups, etc., were obtained. Analyzing differences in handwriting was done by using computer algorithms for extracting features from scanned images of handwriting. Attributes characteristic of the handwriting were obtained, e.g., line separation, slant, character shapes, etc. These attributes, which are a subset of attributes used by expert document examiners, were used to quantitatively establish individuality by using machine learning approaches. Using global attributes of handwriting and very few characters in the writing, the ability to determine the writer with a high degree of confidence was established. The work is a step towards providing scientific support for admitting handwriting evidence in court. The mathematical approach and the resulting software also have the promise of aiding the expert document examiner.

We undertook a study to objectively validate the hypothesis that handwriting is individualistic. Handwriting samples of one thousand five hundred individuals, representative of the US population with respect to gender age, ethnic groups, etc., were obtained. Analyzing differences in handwriting was done by using computer algorithms for extracting features from scanned images of handwriting. Attributes characteristic of the handwriting were obtained, e.g., line separation, slant, character shapes, etc. These attributes, which are a subset of attributes used by expert document examiners, were used to quantitatively establish individuality by using machine learning approaches. Using global attributes of handwriting and very few characters in the writing, the ability to determine the writer with a high degree of confidence was established. The work is a step towards providing scientific support for admitting handwriting evidence in court. The mathematical approach and the resulting software also have the promise of aiding the expert document examiner.

Foreign mail recognition (FMR) is part of the more general problem of recognizing destination addresses in a mail stream. It is defined as the problem of finding the country of destination of a mail piece sent to a foreign address. We discuss some of the differences between FMR and domestic mail recognition (DMR) and present its specific challenges. Two complementary baseline algorithms that use heuristics in combining word, character and digit recognizers are presented. Their performance is improved by reducing the search space for the address elements using address configuration distributions. Preliminary results are presented.

Classifying an unknown input is a fundamental problem in pattern recognition. One standard method is finding its nearest neighbors in a reference set. It would be very time consuming if computed feature by feature for all templates in the reference set; this naive method is O(nd) where n is the number of templates in the reference set and d is the number of features or dimension. For this reason, we present a technique for quickly eliminating most templates from consideration as possible neighbor. The remaining candidate templates are then evaluated feature by feature against the query vector. We utilize frequencies of features as a pre-processing to reduce query processing time burden. The most notable advantage of the new method over other existing techniques occurs where the number of features is large and the type of each feature is binary although it works for other type features. We improved our OCR system by at least a factor of 2 (without a threshold) or faster (with higher threshold value).

The similarity between two histograms has attracted many researchers in various fields. The type of histograms to be matched is often angular such as gradient directions in character images and hue values in color images. The distance between two angular type histograms differs from those of nominal or ordinal type histograms; however, conventional distance measures do not distinguish them. Thus we present a new algorithm to compute the newly proposed distance. We describe how to apply the distance to handwritten character similarity.

The Writer Verification is a process to compare questioned handwriting with samples of handwriting obtained from known sources for the purposes of determining authorship or non-authorship. It plays an important investigative and forensic role in many types of crime. Particularly problematic in this regard is the fact that there exists neither true standard nor universal definition of comparison. For this reason, we propose an algorithmic objective approach. Using visual information of two or more digitally scanned handwritten items, we show a method to access the authorship confidence that is the probability of errors. Instead of building a costly handwritten item database to support the confidence, questioned words are simulated from the CEDAR letter image database in order to handle any handwritten items. An Artificial Neural Network is trained to verify the authorship using the synthesized words.

A gradation of pattern discrimination problems is encountered in interpreting handwritten postal addresses. There are several multiclass discrimination problems, including handwritten numeral recognition with 10 classes, alphanumeral recognition with 36 classes, and touching-digit pair recognition with 100 classes. Word recognition with a lexicon is a problem where the number of classes varies from a few to about a thousand. Some of the discrimination techniques, particularly those with few classes, lend themselves well to neural network classification, while others are better handled by Bayesian polynomial and nearest-neighbor methods. This paper describes each of the discrimination problems and the performances of each of the subsystems in a handwritten address interpretation system developed at CEDAR.

This paper describes hierarchical OCR, a character recognition methodology that achieves high speed and accuracy by using a multiresolution and hierarchical feature space. Features at different resolutions, from coarse to fine-grained, are implemented by means of a recursive classification scheme. Typically, recognizers have to balance the use of features at many resolutions (which yields a high accuracy), with the burden on computational resources in terms of storage space and processing time. We present in this paper, a method that adaptively determines the degree of resolution necessary in order to classify an input pattern. This leads to optimal use of computational resources. The hierarchical OCR dynamically adapts to factors such as the quality of the input pattern, its intrinsic similarities and differences from patterns of other classes it is being compared against, and the processing time available. Furthermore, the finer resolution is accorded to only certain "zones" of the input pattern which are deemed important given the classes that are being discriminated. Experimental results support the methodology presented. When tested on standard NIST data sets, the hierarchical OCR proves to be 300 times faster than a traditional K-nearest-neighbor classification method, and 10 times taster than a neural network method. The comparison uses the same feature set for all methods. Recognition rate of about 96 percent is achieved by the hierarchical OCR. This is at par with the other two traditional methods.

Handwriting has continued to persist as a means of communication and recording information in day-to-day life even with the introduction of new technologies. Given its ubiquity in human transactions, machine recognition of handwriting has practical significance, as in reading handwritten notes in a PDA, in postal addresses on envelopes, in amounts in bank checks, in handwritten fields in forms, etc. This overview describes the nature of handwritten language, how it is transduced into electronic data, and the basic concepts behind written language recognition algorithms. Both the online case (which pertains to the availability of trajectory data during writing) and the off-line case (which pertains to scanned images) are considered. Algorithms for preprocessing, character and word recognition, and performance with practical systems are indicated. Other fields of application, like signature verification, writer authentification, handwriting learning tools are also considered.

This paper presents nonstationary Markovian models and their application to recognition of strings of tokens, such as ZIP codes in the US mailstream. Unlike traditional approaches where digits are simply recognized in isolation, the novelty of our approach lies in the manner in which recognitions scores along with domain specific knowledge about the frequency distribution of various combination of digits are all integrated into one unified model. The domain knowledge is derived from postal directory files. This data feeds into the models as n-grams statistics that are seamlessly integrated with recognition scores of digit images. We present the recognition accuracy (90%) achieved on a set of 20,000 ZIP codes.

Given two character images, we would like to measure their similarity or difference. Such a similarity or difference measure facilitates the solution to character recognition and handwriting analysis problems. There is, however, no universal definition for similarity measure satisfying a wide range of characteristics such as the slant, deformation or other invariant constraints. For this reason, we propose a new definition for the character similarity measure. First, the proposed method converts a two-dimensional image into a one-dimensional string. Next, it computes the edit distance by the modified approximate string matching algorithm. We describe how to extract the string information and compute the distance and then present the details of applications in handwriting analysis and both online and offline character recognition.

This paper introduces a multifont classification scheme to help with the recognition of multifont and multisize characters. It uses typographical attributes such as ascenders, descenders and serifs obtained from a word image. The attributes are used as an input to a neural network classifier to produce the multifont classification results. It can classify 7 commonly used fonts for all point sizes from 7 to 18. The approach developed in this scheme can handle a wide range of image quality even with severely touching characters. The detection of the font can improve character segmentation as well as character recognition because the identification of the font provides information on the structure and typographical design of characters. Therefore, this multifont classification algorithm can be used for maintaining good recognition rates of a machine printed OCR system regardless of fonts and sizes. Experiments have shown that font classification accuracies reach high performance levels of about 95 percent even with severely touching characters. The technique developed for the selected 7 fonts in this paper can be applied to any other fonts.

In this paper we present a solution to the general vision problem of parsing and recognizing a set of correlated entities in the presence of imperfect information. Our solution mechanism involves the generation of multiple hypotheses in the initial stages of the system, and the use of very-large vocabulary recognition, together with a database of all the valid combination of the correlated entities, to choose among the hypotheses. We have applied our ideas and techniques to the specific task of identifying the city, state and zipcode fields in handwritten addresses. Given the image of a handwritten address, our algorithm produces a ranking of the 76,121-entry database of valid (city, state, zip) triples in the U.S. and in nearly 75% of the cases, the correct entry for the input address is assigned a rank of at most 10.

An efficient system which finds the best match between an input image and a lexicon is presented. To capture writing style of spacing between words and characters prime stroke analysis based on statistical methods is introduced. A method for estimating bound on number of characters without actual recognition is also presented. For system efficiency, before actual recognition, classified groups of word segments and eligible subset of lexicons are generated as hypotheses. The hypotheses are verified and ordered by a lexicon driven word recognizor. We have tested our approach in the street name recognition/interpretation for US mail stream. Experimental results and encouraging.

This paper concerns a study of information content in postal address fields for automatic address interpretation. Information provided by a combination of address components and information interaction among components is characterized in terms of Shannon's entropy. The efficiency of assignment strategies for determining a delivery point code can be compared by the propagation of uncertainty in address components. The quantity of redundancy between components can be computed from the information provided by these components. This information is useful in developing a strategy for selecting a useful component for recovering the value of an uncertain component. The uncertainty of a component based on another known component can be measured by conditional entropy. By ranking the uncertainty quantity, the effective processing flow for determining the value of a candidate component can be constructed.

84.6% of touching digit strings have only two digits touching, 12.3% have three digits touching and 3.1% have more than three digits touching. We present a multi-expert approach to recognize touching digit pairs (TDP) and touching digit triples (TDT). We combine holistic and traditional segmentation methods. 25,686 TDP training samples and 2,778 TDP testing samples collected from USPS mail are used in our experiment. The holistic method outperforms the traditional segmentation-based methods. The multi-expert combination has the best performance: a correct recognition rate of 91.1% on TDP.

Describes the derivation of probability of correctness from scores assigned by most recognizers. Derivation of probability values puts the output of different recognizers on the same scale; this makes comparison across recognizers trivial. The authors draw on examples from handwritten word recognition to illustrate their point.

This paper presents nonstationary Markovian models and their application to recognition of strings of tokens. Domain specific knowledge is brought to bear on the application of recognizing zip codes in the US mailstream by the use of postal directory files. These files provide a wealth of information on the delivery points (mailstops) corresponding to each zip code. This data feeds into the models as n-grams, statistics that are integrated with recognition scores of digit images. An especially interesting facet of the model is its ability to excite and inhibit certain positions in the n-grams leading to the familiar area of Markov random fields. We empirically illustrate the success of Markovian modeling in postprocessing applications of string recognition. We present the recognition accuracy of the different models on a set of 20000 zip codes. The performance is superior to the present system which ignores all contextual information and simply relies on the recognition scores of the digit recognizers.

This paper describes the derivation of probability of correctness from scores assigned by most recognizers. Motivation for this research is three-fold: (i) probability values can be used to rerank the output of any recognizer by using a new set of training data; if the training data is sufficiently large and representative of the test data, the recognition rates are seen to improve significantly, (ii) derivation of probability values puts the output of different recognizers on the same scale; this makes comparison across recognizers trivial, and (iii) word recognition can be readily extended to phrase and sentence recognition because the integration of language models becomes straightforward. We have conducted an extensive set of experiments. The results show a reranking of recognition choices based on the derived probability values leading to an enhancement in performance.

A reply card processing (RCP) service was developed at CEDAR to demonstrate how the United States Postal Service could deliver business and courtesy reply cards to clients electronically instead of physically. The electronic delivery of the more than one billion cards that the USPS processes in a year was to expedite the order fulfilment cycle for participating customers, resulting in cost savings and accelerated response times. CEDAR developed the necessary subsystems which included a postal image management system. As well as providing the networking applications for ensuring the seamless transfer of card images to the postal clients, the task involved advancing the state-of-the-art in forms processing to read the card images and to deliver the information in a form ready for database integration.

This paper describes a methodology that allows fast and accurate character recognition while keeping the dimensionality of the feature space relatively small. Higher dimensionality can add to the discriminatory power of a recognizer but pays the price in an increase of computational time. We present a method that achieves high accuracy even with a low-dimensional feature space by simulating a multiresolution feature space. Our approach is supported by promising experimental results. Recognition rate of 98% is achieved on a test set of about 16,000 handwritten numerals. Recognition rates on upper and lower case handprinted characters is about 95%.

OCR is an error-prone process. It is time-consuming and expensive to manually proofread OCR results. The errors remaining in OCRed texts can cause serious problems in reading and understanding if they do not refer to the original image representation. As demonstrated in this paper, a hybrid document which combines symbolic representation and image representation may relieve the problem. If we represent a OCRed document properly in HTML, OCR errors will not have much negative effect on the human reading process in an HTML browser and can be corrected by using an HTML authoring tool. Under this approach, an experiment evaluating a Japanese OCR system developed at CEDAR is also reported in this paper.

The authors describe ongoing research on a system for rapid verification of unconstrained off-line handwritten phrases using perceptual holistic features of the handwritten phrase image. The system is used to verify handwritten street names automatically extracted from live US mail against recognition results of analytical classifiers. The system rejects errors with 98% accuracy at the 30% accept level, while consuming approximately 20 msec per image on the average on a 150 MHz SPARC 10.

Hand-written address interpretation (HWAI) technology has been recently incorporated into the processing of letter mail by the US Postal Service. The Remote Bar Coding System, which is an image management system for assigning bar codes to mail that has not been fully processed by postal OCR equipment, has been retrofitted with a Remote Computer Reader (RCR), into which the HWAI technology is integrated. A description of the HWAI technology, including its algorithms for the control structure, recognizers and databases, is provided. Its performance on more than a million hand-written mail-pieces in a field deployment of the integrated RCR-HWAI system is indicated. Future enhancements for a nationwide deployment of the system are indicated.

Binarization has been difficult for document images with poor contrast, strong noise, complex patterns, and/or variable modalities in gray-scale histograms. We developed a texture feature based thresholding algorithm to address this problem. Our algorithm consists of three steps: 1) candidate thresholds are produced through iterative use of Otsu's algorithm (1978); 2) texture features associated with each candidate threshold are extracted from the run-length histogram of the accordingly binarized image; 3) the optimal threshold is selected so that desirable document texture features are preserved. Experiments with 9,000 machine printed address blocks from an unconstrained US mail stream demonstrated that over 99.6 percent of the images were successfully binarized by the new thresholding method, appreciably better than those obtained by typical existing thresholding techniques. Also, a system run with 500 troublesome mail address blocks showed that an 8.1 percent higher character recognition rate was achieved with our algorithm as compared with Otsu's algorithm.

A fast matching algorithm using dynamic programming for handwritten word recognition is presented. The variable duration for each character is defined based on the character segmentation statistics obtained during the training phase. The variable duration represents the possible ways in which a character image can be split into segments. Experimental results prove that our approach using the variable duration outperforms the method using fixed duration in terms of both accuracy and speed. The processing time for the matching process increases at the rate of log(N) as the lexicon size N increases. A speed of 200 msec, including image handling procedures, on a single Sparc 10 platform and a recognition accuracy of 96.7% are achieved for a lexicon size of 10.

A segmentation and recognition method for handwritten phrases, such as street names, is presented in this paper. Some of the challenges posed by the problem are: (1) identifying correct word gaps from character gaps and (2) minimization of computational complexity during the recognition of potential words. A trainable word segmentation scheme using a neural network is introduced. The network learns the type of spacing (including size) that one should expect between different pairs of characters in handwritten text. The concept of variable duration, which is obtained during the training phase of a word recognition engine we have developed, is expanded to reduce the computational complexity which has been a serious concern in this type of application.

The reading of names and addresses is one of the most complex tasks in automated forms processing. This paper describes an integrated real-time system to read names and addresses on tax forms of the U.S. Internal Revenue Service. The Name and Address Block Reader (NABR) system accepts both machine-printed and hand-printed address block images as input. The application software has two major steps: document analysis (connected component analysis, address block extraction, label detection, hand-print/machine-print discrimination) and document recognition. Document recognition has two nonidentical streams for machine-print and hand-print: the key steps are address parsing, character recognition, word recognition, and postal database lookup. (ZIP+4 and City-State-ZIP files.) System output is a packet containing the results of recognition together with database access status file. Real-time throughput (8500 forms/h) is achieved by employing a loosely coupled multiprocessing architecture where successive input images are distributed to available address recognition processors. The functional architecture, software design, system architecture, and the hardware implementation are described. Performance evaluation on machine-printed and handwritten addresses are presented.

The nearest neighbor (NN) approach is a powerful nonparametric technique for pattern classification tasks. In this paper, algorithms for prototype reduction, hierarchical prototype organization and fast NN search are described. To remove redundant category prototypes and to avoid redundant comparisons, the algorithms explain geometrical information of a given prototype set which is represented approximately by computing k-nearest/farthest neighbors of each prototype. The performance of a NN classifier using those algorithms for Japanese character recognition is reported.

The paper examines the general classifier combination problem under strict separation of the classifier and combinator design. Several desirable combinator properties are identified: omnitype mixed type and correlated classifier combination, redundant classifier elimination, model complexity control, and dynamic selection combination. By adapting some of the theories and algorithms developed for neural network learning. They present a combination model which provides a solution to these problems. Experimental results on handwritten digits verify these findings.

A document analysis system which understands the incoming fax cover pages can serve as a mail routing system. This paper reports our research as part of an effort to realize such a system and focuses on locating the recipient's name and address on fax cover sheets. The name and address regions will later be extracted from the image and sent to an address interpretation unit for further processing. Fax cover pages are one type of documents which have changeable layout, contain many objects of different nature, and possess compact contents. Previous page segmentation techniques which mainly used geometric features are found not suitable for the current task. Our method uses a scheme which strongly couples text recognition and block segmentation. The system attempts to locate and recognize words which are data field indicators so as to figure out the positions of such keywords as "TO" and "COMPANY". The information regarding the positions of "TO" and "COMPANY" indicators is used as reference in block segmentation to segment out their associated data regions. Our system has proved to work reasonably well on a sample set composed of 12 machined-printed images and 115 handwritten images.

Commercial forms-reading systems for extraction of data from forms do not meet acceptable accuracy requirements on forms filled out by hand. In December 1993, NIST called industry and research organizations working in the area of handwriting recognition to participate in a test to determine the state of the art in the area. A database of form images containing actual responses received by the US Census Bureau was provided. The handwritten responses are very loosely constrained in terms of writing style, format of response and choice of text. The sizes of the lexicons provided are very large (about 50000 entries) and yet the coverage is incomplete (about 70%). In this paper we discuss the approach taken by CEDAR to automate the task of reading the census forms. The subtasks of field extraction and phrase recognition are described.

The analysis of a document image to derive a symbolic description of its structure and contents involves using spatial domain knowledge to classify the different printed blocks (e.g., text paragraphs), group them into logical units (e.g., newspaper stories), and determine the reading order of the text blocks within each unit. These steps describe the conversion of the physical structure of a document into its logical structure. We have developed a computational model for document logical structure derivation, in which a rule-based control strategy utilizes the data obtained from analyzing a digitized document image, and makes inferences using a multi-level knowledge base of document layout rules. The knowledge-based document logical structure derivation system (DeLoS) based on this model consists of a hierarchical rule-based control system to guide the block classification, grouping and read-ordering operations; a global data structure to store the document image data and incremental inferences; and a domain knowledge base to encode the rules governing document layout.

The reading of names and addresses is one of the most complex tasks in automated forms processing. The paper describes an integrated real time system to read names and addresses on tax forms of the Internal Revenue Service of the United States. The Name and Address Block Reader (NABR) system accepts both machine printed and hand printed address block images as input. The application software has two major steps: document analysis (connected component analysis, address block extraction, label detection, hand print/machine print discrimination); and document recognition. Document recognition has two non identical streams for machine print and hand print; key steps are: address parsing, character recognition, word recognition and postal database lookup (ZIP+4 and City-State-ZIP files). Real time throughput (8,500 forms per hour) is achieved by employing a loosely coupled multiprocessing architecture. The functional architecture, software design, system architecture and hardware implementation are described. Performance evaluation on machine printed and handwritten addresses are presented.

An algorithm for recognition of machine-printed word images of multiple font types and varying qualities is presented. The information provided by both the entire shape of the word and its component letters was utilized in recognition. The algorithm uses the general shape of a word as the primary cue in recognition, with a few letters, which are highly identifiable when compared with the others, as the supplementary cues. In determining word shape, an ideal word pattern approach was applied to deal with the difficulty introduced by large variety of font types and image qualities. The size of given lexicon was reduced by recognizing the first and last characters. Experimental results with over two thousands test images, which are printed in a wide range of font styles and qualities, are presented to demonstrate the proposed approach.

Determining the readability of documents is an important task. Human readability pertains to the scenario when a document image is ultimately presented to a human to read. Machine readability pertains to the scenario when the document is subjected to an OCR process. In either case, poor image quality might render a document unreadable. A document image which is human readable is often not machine readable. It is often advisable to filter out documents of poor image quality before sending them to either machine or human for reading. This paper is about the design of such a filter. We describe various factors which affect document image quality and the accuracy of predicting the extent of human and machine readability possible using metrics based on document image quality.

The trade-off between the granularity of the data representation and the recognition accuracy is examined in this paper. We show that unless a particular criterion is satisfied, there is no guarantee of achieving a prescribed recognition accuracy. This criterion of interest, is the mutual information content between the measurements and the class identities. A novel method for the objective evaluation of intrinsic error in recognition as sampling rate varies, is described. This approach is general enough to permit the evaluation of error even when the parameter under study takes a different form. To demonstrate this we present results in feature subset selection and multiple classifier combination. In the case of feature selection, the measurements are the features. In the case of multiple classifier combination it is the "quality" of the individual classifiers, evalulated based on the mutual information between the classifier parameters and class identities.>

An address paragraph consists of several lines (sentences) of text. Each sentence consists of numbers, words and phrases that identify a meaningful geographical region. Addresses are typically present in documents such as postal envelopes, business cards, facsimile cover pages-where there exist other text and graphics. The problem considered is that of segmenting the subimage corresponding to the address paragraph from the entire document image. Previous approaches to locating address paragraphs, primarily for postal envelopes, have avoided use of character and word information and focused on global features. The authors present a new method based on using character recognition and address syntax. In this approach, the core problem is formulated as a consistent labeling problem based on syntactic features. The proposed method has been implemented for locating the destination address block on machine-printed letter mail. Experimental results with 2000 images of letter mail are indicated.

Automatic analysis of images of forms is a problem of both practical and theoretical interest; due to its importance in office automation, and due to the conceptual challenges posed for document image analysis, respectively. We describe an approach to the extraction of text, both typed and handwritten, from scanned and digitized images of filled-out forms. In decomposing a filled-out form into three basic components of boxes, line segments and the remainder (handwritten and typed characters, words, and logos), the method does not use a priori knowledge of form structure. The input binary image is first segmented into small and large connected components. Complex boxes are decomposed into elementary regions using an approach based on key-point analysis. Handwritten and machine-printed text that touches or overlaps guide lines and boxes are separated by removing lines. Characters broken by line removal are rejoined using a character patching method. Experimental results with filled-out forms, from several different domains (insurance, banking, tax, retail and postal) are given.

Describes the control structure for an intelligent handwritten address interpretation system. The system takes a grey-level address image, segments the address into lines and words, parses the address into meaningful syntactic categories, recognizes words using dynamically generated lexicons, and determines the destination code with the aid of postal directories.>

A multiple classifier system is a powerful solution to difficult pattern recognition problems involving large class sets and noisy input because it allows simultaneous use of arbitrary feature descriptors and classification procedures. Decisions by the classifiers can be represented as rankings of classifiers and different instances of a problem. The rankings can be combined by methods that either reduce or rerank a given set of classes. An intersection method and union method are proposed for class set reduction. Three methods based on the highest rank, the Borda count, and logistic regression are proposed for class set reranking. These methods have been tested in applications of degraded machine-printed characters and works from large lexicons, resulting in substantial improvement in overall correctness.>

A major step in model-based fault diagnosis is the generation of candidate components which might be responsible for the observed symptom of a malfunction. After the candidates are determined, each component can then be examined in turn. It is useful to be able to choose the most likely candidate to focus on first so that the faulty parts can be located sooner. This paper presents some topological heuristics for ordering candidates according to their relationships with violations and corroborations. Candidates are also reordered or eliminated when new information is acquired during diagnosis. These ordering and reordering techniques are shown to be effective for model-based diagnosis. For single fault cases, the average length of diagnosis is log n, where n is the number of components. In general, the average length of diagnosis is k log n when there rare k faults in the device initially.>

A complete system for the recognition of unconstrained handwritten words using a continuous density variable duration hidden Markov model (CDVDHMM) is described. A new segmentation algorithm based on mathematical morphology is used to translate the 2-D image into a 1-D sequence of sub-character symbols. This sequence of symbols is modeled by the CDVDHMM. Generally, there are two information sources associated with the written text. While the shape information of each character symbol is modeled as a mixture Gaussian distribution, the linguistic knowledge, i.e., constraint, is modeled as a Markov chain. In this context, the variable duration state is used to take care of the segmentation ambiguity among the consecutive characters. Some experimental results are described to demonstrate the success of the proposed scheme.>

Forms are used extensively in today's offices. The task of an automated form reader is to locate data filled on a form and to encode the content into appropriate symbolic descriptions. The challenges in form reading are due to high volume and large variety. A robust form reader with high adaptability and trainability. The form reader consists of two modules: field registration and data recognition module. The field registration module acquires knowledge about the forms of interest and the data recognition module recognizes text data on filled forms using the acquired knowledge. The capability of the reader increases progressively through supervised learning. The form reader has been training to read a large variety of forms with machine-printed data. The adaptability and trainability of the system have been demonstrated through the experiments.>

The authors shown many advantages of using postal syntactic features in address block location. Performing character recognition at low resolution (100 PPI) is desirable for a real-time system. An efficient word matching algorithm is designed to match words against a dictionary of about 500 keywords and assign a syntactic tag to each word in a text block. The critical information and the street syntax are extracted by parsing the syntactic tags. The usage of the postal syntactic features has been introduced in many aspects such as recovering lost information, selecting a more likely destination address block, and improving destination address block segmentation. With character recognition available in the system, the utilization of other syntax and context information on the mail pieces becomes feasible. The initial testing results of the incorporation of the syntactic processing in address block location were positive and encouraging.>

Document image binarization is not a completely solved problem for unconstrained document images. Binarization algorithms, whether global or local, can easily fail on images with noisy or complex background, or poor contrast. The authors report preliminary results on a new approach to document image binarization, an algorithm based on gray scale histogram and run-length histogram analysis. Experimental results on unconstrained machine printed address blocks from the US letter mail stream show that over 99% of such address blocks can be correctly binarized.>

Several hierarchical levels in modeling text are discussed. At each level, the model is typically based on elements at the next lower level, e.g., characters in terms of features, words in terms of characters, phrases/sentences in terms of words, and paragraphs in terms of sentences. Such models are referred to as analytic, since they are based on step-by-step analysis. Although such models are usually sufficient, in order to achieve system robustness it is necessary to use models that skip a level, e.g., words in terms of features/pixels and sentences in terms of characters. Such models are holistic in that decisions about entities are made in the context of decisions about other entities. Holistic methods are slower than analytic methods and do not necessarily perform better. However, when analytic and holistic methods are combined, overall system performance is higher than either alone. Recognition algorithms based on different models can be combined to achieve robustness.>

Determining the delivery location for mail pieces based on handwritten addresses is a problem that trained humans can normally solve. As a problem in machine reading and interpretation, it presents many challenges. A method for determining the delivery point codes (DPCs) for handwritten addresses by computer is described. Solution to the task requires locating and recognizing address components (e.g., ZIP Code, street number, P.O. box number) and using multiple information sources to assign the DPC to an address. The methodology uses diverse pattern recognition techniques, image processing algorithms (thresholding, underline removal, separation of lines, location and recognition of address components), and access to United States Postal Service (USPS) databases to determine the DPC.>

The goal of diagnostic reasoning is to identify malfunction (disease) that best accounts for the observed discrepancies (symptoms) in system behavior. Model-based diagnosis emerges as an alternative to both the empirical symptom-based and traditional fault-model-based approaches. Within the model-based paradigm, there is an important approach which bases its reasoning on conflicts for diagnosing multiple failures. We refer to such an approach as conflict-based diagnosis in this work. Previous conflict-based diagnostic systems resort to some objective notion of parsimony, e.g. nonredundancy, to reduce the exponential search space of hypotheses. Instead of using subjective measures, a probabilistic model is developed which provides an objective measure for ranking hypotheses. Based on the probabilistic model, an algorithm which generates plausible diagnostic hypotheses in decreasing order of their probabilities is presented. Some possible uses of the algorithm are discussed.

The human face is an object that is easily located in complex scenes by humans and adults alike. Yet the development of an automated system to perform this task is extremely challenging. This paper is about developing computational procedures to locate human faces in newspaper photographs where scenes are often cluttered making object location non-trivial. On the other hand, the task is made feasible by constraints which follow naturally from rules in photo-journalism. Faces identified by the caption are clearly depicted without occlusion and contrast against the background and sizes of faces fall within a fixed range depending on the dimensions of the photograph and the number of people featuring in it.>

Difficult pattern recognition problems involving large class sets and noisy input can be solved by a multiple classifier system, which allows simultaneous use of arbitrary feature descriptors and classification procedures. Independent decisions by each classifier can be combined by methods of the highest rank, Borda count, and logistic regression, resulting in substantial improvement in overall correctness.>

A top-down approach to word recognition is proposed. Discussions are presented on dynamically selecting the most effective feature combinations, which are applied to discriminate between a limited set of word hypotheses.>

The architecture of a reading machine designed to achieve a high rate of correct interpretation of text as well as high speed in performing the interpretation is described. The refinement of the architecture for a specialized reading machine, to find and interpret addresses on a stream of postal letters, is also described. The addresses can be either machine-printed or handwritten. The primary subtasks correspond to finding the block of text corresponding to the destination address, recognizing characters and words within the address, and interpreting the text using postal directories. The need for multiple algorithms and multiple scales for recognition (holistic and analytic) and for methods for combining results of multiple algorithms, the efficacy of artificial neural nets and fuzzy matching, and the feasibility of reading unconstrained handwritten words when there exist accompanying numeric fields that limit word choices are shown.>

Understanding a block of handwritten text means mapping it into a semantic representation. We describe an approach to reading a block of handwritten text when there are certain loose constraints placed on the spatial layout and syntax of the text. Early recognition of primitives guides the location of syntactic components. A system to read handwritten postal addresses is described as an instance. The semantic representation in this case is a digit string (ZIP Code). Methods for segmenting a string of digits into components and for recognizing digits using a multiplicity of recognizers are given.

The authors adopted a model-based approach, where the shape of the object is defined in terms of several mini-templates. The mini-templates are abstract descriptions of simple geometric features like arcs and corners. Relationships between mini-templates are not rigid. Rather, they are represented by springs that allow deformation of a template in terms of its size and orientation. Cost functionals are determined empirically. The authors expect their system to generate candidate regions in a given photograph associated with a rank of its goodness.>

The authors describe a method for segmenting a newspaper page image into labeled macro components (blocks) and recognizing the content. Connected component analysis is used to segment a newspaper image into several rectangular blocks and to filter connected components into character and noncharacter components. Textural analysis is then used to classify the remaining noncharacter components into graphics and photographs. Experimental results indicate that these techniques work very well.>

A computational approach to locating human faces in newspaper photographs is described. While the computational recognition of a well-framed face as one of a known set of faces has received some attention, the computational location of faces in varying contexts is relatively unexplored. Candidates for the locations of faces are hypothesized by extracting features in the edge-image of the photograph and matching with a model of a face profile. A face is defined by a parametric representation of each of the component parts. Knowledge contained in the caption is represented using semantic networks and is used to reason about the locations of faces of individuals in the photograph.>

The use of spatial knowledge is necessary in a variety of artificial intelligence and expert systems applications. The need is not only in tasks with spatial goals such as image interpretation and robot motion, but also in tasks not involving spatial goals, e.g. diagnosis and language understanding. The paper discusses methods of representing spatial knowledge, with particular focus on the broad categories known as analogical and propositional representations. The problem of neurological localization is considered in some detail as an example of intelligent problem-solving that requires the use of spatial knowledge. Several solutions for the problem are presented: the first uses an analogical representation only, the second uses a propositional representation and the third uses an integrated representation. Conclusions about the different representations for building intelligent systems are drawn.

Cursive script word recognition is the problem of transforming a word from the iconic form of cursive writing to its symbolic form. Several component processes of a recognition system for isolated offline cursive script words are described. A word image is transformed through a hierarchy of representation levels: points, contours, features, letters, and words. A unique feature representation is generated bottom-up from the image using statistical dependences between letters and features. Ratings for partially formed words are computed using a stack algorithm and a lexicon represented as a trie. Several novel techniques for low- and intermediate-level processing for cursive script are described, including heuristics for reference line finding, letter segmentation based on detecting local minima along the lower contour and areas with low vertical profiles, simultaneous encoding of contours and their topological relationships, extracting features, and finding shape-oriented events. Experiments demonstrating the performance of the system are also described.>

A methodology for recognizing ZIP codes (US postal codes) in handwritten addresses is presented that uses many diverse pattern recognition and image processing algorithms. Given a high-resolution image of a handwritten address block, the solution invokes routines capable of hypothesizing the location of the ZIP code, segmenting and recognizing ZIP code digits, locating and recognizing city and state names, and looking up the results in a dictionary. The control structure is not strictly sequential, but rather in the form of a blackboard architecture that opportunistically invokes routines as needed. An implementation of the methodology is described as well as results with a database of grey-level images of handwritten addresses (taken from live mail in a US Postal Service mail processing facility). Future extensions of the approach are discussed.>

A method of recognizing an object of interest in a complex visual environment is described. Motivated by the problem of finding the destination address block on a piece of mail, a general framework for coordinating a collection of specialized image analysis tools is described. The resulting system can deal with a wide range of environments: from those having a high degree of global spatial structure (e.g. mail envelopes which conform to specifications) to those with no structure (e.g. magazines with randomly pasted address labels). The problem-solving architecture accounts for uncertainty in the imaging environment by using the blackboard model. The system consists of several specialized tools and a control structure so that the tools are opportunistically invoked and coordinated. Its performance on an image database of difficult cases is described.>

An encoding/decoding technique and a computer architecture for progressive refinement of 3-D images is suggested. The method is based on a binary tree representation of grey-level images. A scheme to transform an N × N × N image array into a sequence of at most N × N × N elements is given. As more elements of the sequence are scanned finer resolution representations of the image are obtained. The proposed architecture, which is suitable for VLSI implementation, performs the transformations between the image and its encoding using O(log N) processors and in time and space proportional to the image size.

The use of diverse knowledge sources in text recognition and in correction of letter substitution errors in words of text is considered. Three knowledge sources are defined: channel characteristics as probabilities that observed letters are corruptions of other letters, bottom-up context as letter conditional probabilities (when the previous letters of the word are known), and top-down context as a lexicon. Two algorithms, one based on integrating the knowledge sources in a single step and the other based on sequentially cascading bottom-up and top-down processes, are compared in terms of computational/storage requirements and results of experimentation.

A new algorithm for text recognition that corrects character substitution errors in words of text is presented.The search for a correct word effectively integrates three knowledge sources: channel characteristics, bottom-up context, and top-down context.Channel characteristics are used in the form of probabilities that observed letters are corruptions of other letters; bottom-up context is in the form of the probability of a letter when the previous letters of the word are known; and top-down context is in the form of a lexicon.A one-pass algorithm is obtained by merging a previously known dynamic programming algorithm to compute the maximum a posteriori probability string (known as the Viterbi algorithm) with searching a lexical trie.Analysis of the computational compexity of the algorithm and results of experimentation with a PASCAL implementation are presented.

This paper deals with a method of estimating a correct string X from its noisy version Y produced by a cursive script recognition system. An accurate channel model that allows for splitting, merging, and substitution of symbols is introduced. The best estimate X is obtained by using a dynamic programming search which combines a known search strategy (stack decoding) with a trie structure representation of a dictionary. The computational complexity of the algorithm is derived and compared with that of a method based on the generalized Levenshtein metric. Experimental results with the algorithm on English text based on a dictionary of the 1027 most commonly occurring words are described.

The binary n-gram and Viterbi algorithms have been suggested as alternative approaches to contextual postprocessing for text produced by a noisy channel such as an optical character recognizer. This correspondence describes the underlying theory of each approach in unified terminology, and presents new implementation algorithms for each approach. In particular, a storage efficient data structure is proposed for the binary n-gram algorithm and a recursive formulation is given for the Viterbi algorithm. Results of extensive experiments with each algorithm are described.

The development of image processing algorithms for time-varying imagery and computerized tomography data calls for generalization of the concepts of adjacency, connectivity, boundary, etc., to three and four-dimensional discrete spaces. This paper defines these basic concepts in unified terminology and presents algorithms for a boundary detection task in multidimensional space. The performance of these algorithms is discussed with respect to theoretical maximum complexity, and is illustrated with simulated computerized tomography data.

The two-step approach to nonparametric discrimination is that of estimating class-conditional densities and deriving the Bayes decision rule as if the estimates were true. Direct implementation of such a decision rule ecounters two computational problems. Complexity increases with sample size, and finite precision limits the decision rule domain. Here a recursive algorithm to reduce the expected number of operations and word-length limitations below that of the direct approach is developed. A special case of the formulation reduces to the weighted k-nearest-neighbor rule.

An efficient algorithm for determining the sequency vector S̄nof a 2n× 2nHadamard matrix is developed. The method requires fewer computation steps than a previously known method.