We first describe an automatic table ground truth generation system which can efficiently generate a large amount of accurate table ground truth suitable for the development of table detection algorithms. Then a novel background analysis-based, coarse-to-fine table identification algorithm and an X-Y cut table decomposition algorithm are described. We discuss an experimental protocol to evaluate the table detection algorithms. For a total of 1,125 document pages having 518 table entities and a total of 10,941 cell entities, our table detection algorithm takes line, word segmentation results as input and obtains around 90% cell correct detection rates.

We present an improved zone content classification method and its performance evaluation. We added two new features to the feature vector from one previously published method (Sivaramakrishnan et al., 1995). We assumed different independence relationships in two zone sets. We used an optimized binary decision tree to estimate the maximum zone content class probability in one set while using the Viterbi algorithm to find the optimal solution for a zone sequence in the other set. The training, pruning and testing data set for the algorithm include 1,600 images drawn from the UWCDROM III document image database. The classifier is able to classify each given scientific and technical document zone into one of the nine classes, 2 text classes (of font size 4 - 18pt and font size 19 - 32 pt), math, table, halftone, map/drawing, ruling, logo, and others. Compared with our previous work (Wang et al., 2000), it raised the accuracy rate to 98.52% from 97.53% and reduced the mean false alarm rate to 0.53% from 1.26%.

In this paper, we give a formal definition of a document image structure representation, and formulate document image structure extraction as a partitioning problem: finding an optimal solution partitioning the set of glyphs of an input document image into a hierarchical tree structure where entities within the hierarchy at each level have similar physical properties and compatible semantic labels. We present a unified methodology that is applicable to construction of document structures at different hierarchical levels. An iterative, relaxation-like method is used to find a partitioning solution that maximizes the probability of the extracted structure. All the probabilities used in the partitioning process are estimated from an extensive training set of various kinds of measurements among the entities within the hierarchy. The offline probabilities estimated in the training then drive all decisions in the online document structure extraction. We have implemented a text line extraction algorithm using this framework.

Presents the results of the third international graphics recognition contest. We evaluated the performance of four different vectorization systems on scanned images of CAD drawings. The EditCost Index was used for comparative evaluation of the systems. The performance curves of the systems on the test images are presented in this paper.

Presents a special symbol recognition system that incorporates the result of OCR to recognize the special symbols those nor handled by the current commercial OCR systems. Given a document image and the OCR output, we first refine the character coordinates produced by the OCR. Then, the special symbols are distinguished from the normal characters. Finally, we compute the features from the special symbol sub-images and a supervised classifier is used to assign the sub-images to one of the predefined special symbol categories. The system was tested on 5516 images from the National Library of Medicine. The evaluation results are reported in the paper.

This paper presents a text word extraction algorithm that takes a set of bounding boxes of glyphs and their associated text lines of a given document and partitions the glyphs into a set of text words, using only the geometric information of the input glyphs. The algorithm is probability based. An iterative, relaxation-like method is used to find the partitioning solution that maximizes the joint probability. To evaluate the performance of our test word extraction algorithm, we used a 3-fold validation method and developed a quantitative performance measure. The algorithm was evaluated on the UW-III database of some 1600 scanned document image pages. An area-overlap measure was used to find the correspondence between the detected entities and the ground-truth. For a total of 827, 433 ground truth words, the algorithm identified and segmented 800, 149 words correctly, an accuracy of 97.43%.

This paper describes a text-line identification and segmentation technique that is probability based, where all probabilities are estimated from an extensive training set of various kind of measurements of distances between the terminal and non-terminal entities with which the algorithm works. The off-line probabilities estimated in the training then drive all decisions in the on-line segmentation algorithm. On the UW-III database of some 1600 scanned document image pages, having some 105020 text lines, the algorithm identifies and segments 104773 correctly, an accuracy of 99.76%.

This paper introduces a methodology for bootstrapping and creating large number of groundtruthed "real-life" degraded images from an existing data set with a fraction of the original cost and time. The real-life degradations include geometric distortions, coffee stains, water or ink marks, and folds and creases. The methodology includes an automatic procedure to generate unlimited "real-life" degraded images (with coffee and ink marks and soil spots) without any cost. A small experiment was conducted to illustrate the effectiveness of our methodology. In the experiment, 22 real-life degraded images and the two original images were tested on a commercial OCR system. The accuracy rates of the OCR for the two original pages are 98.46% and 99.34% while the accuracy rates for the degraded pages are ranging from 57.17% to 98.45%, depending on the severity and the type of degradation applied to the pages.

Presents a methodology for evaluating graphics recognition systems operating on images that contain straight lines, circles, circular arcs, and text blocks. It enables an empirical comparison of vectorization software packages and uses practical performance evaluation methods that can be applied to complete vectorization systems. The methodology includes a set of matching criteria for pairs of graphical entities, a set of performance evaluation metrics, and a benchmark for the evaluation of graphics recognition systems. The benchmark was tested on three systems. The results are reported and analyzed in the paper.

A document image analysis toolbox including a collection of data structures and algorithms to support a variety of applications, is described in this paper. An experimental environment is built to allow developers to develop, test and optimize their algorithms and systems. Appropriate and quantitative performance metrics for each kind of information a document analysis technique infers have been developed. The performance of each algorithm has been evaluated based on these metrics and the UW-III document image database which contains a total of 1600 English document images randomly selected from scientific and technical journals.

The paper presents an efficient technique for document page layout structure extraction and classification by analyzing the spatial configuration of the bounding boxes of different entities on the given image. The algorithm segments an image into a list of homogeneous zones. The classification algorithm labels each zone as test, table, line-drawing, halftone, ruling, or noise. The text lines and words are extracted within text zones and neighboring text lines are merged to form text blocks. The tabular structure is further decomposed into row and column items. Finally, the document layout hierarchy is produced from these extracted entities.

This paper describes a word segmentation algorithm which is based on the recursive morphological closing transform. The algorithm is trainable for any given document image population and is capable of detecting words on a document image simultaneously. We describe an experimental protocol to train and evaluate our word segmentation algorithm based on a set of layout ground-truthed document images. We also discussed a method to compare two sets of word bounding boxes-one from the ground truth and the other from the output of the word segmentation algorithm, and compute the numbers of miss, false, correct splitting, merging and spurious detections. The experimental results demonstrate that under the optimal algorithm parameter settings, the correct word detection percentage is about 95% on both the training and testing image populations. If this includes the splitting and merging detections, the detection percentage is about 99.4%.

This paper describes an algorithm to estimate the text skew angle in a document image. The algorithm utilizes the recursive morphological transforms and yields accurate estimates of text skew angles on a large document image data set. The algorithm computes the optimal parameter settings on the fly without any human interaction. In this automatic mode, experimental results indicate that the algorithm generates estimated text skew angles within 0.5/spl deg/ of the true text skew angles with a probability of 99%. To process a 300 dpi document image, the algorithm takes 10 seconds on SUN Sparc 10 machines.

A top-down page segmentation technique known as the recursive X-Y cut decomposes a document image recursively into a set of rectangular blocks. This paper proposes that the recursive X-Y cut be implemented using bounding boxes of connected components of black pixels instead of using image pixels. The advantage is that great improvement can be achieved in computation. In fact, once bounding boxes of connected components are obtained, the recursive X-Y cut is completed within an order of a second on Sparc-10 workstations for letter-sized document images scanned at 900 dpi resolution.

This paper describes a method for extracting words, textlines and text blocks by analyzing the spatial configuration of bounding boxes of connected component on a given document image. The basic idea is that connected components of black pixels can be used as computational units in document image analysis. In this paper, the problem of extracting words, textlines and text blocks is viewed as a clustering problem in the 2-dimensional discrete domain. Our main strategy is that profiling analysis is utilized to measure horizontal or vertical gaps of (groups of) components during the process of image segmentation. For this purpose, we compute the smallest rectangular box, called the bounding box, which circumscribes a connected component. Those boxes are projected horizontally and/or vertically, and local and global projection profiles are analyzed for word, textline and text-block segmentation. In the last step of segmentation, the document decomposition hierarchy is produced from these segmented objects.

A document can be divided into zones on the basis of its content. For example, a zone can be either text or non-text. This paper describes an algorithm to classify each given document zone into one of nine different classes. Features for each zone such as run length mean and variance, spatial mean and variance, fraction of the total number of black pixels in the zone, and the zone width ratio for each zone are extracted. Run length related features are computed along four different canonical directions. A decision tree classifier is used to assign a zone class on the basis of its feature vector. The performance on an independent test set was 97%.

A corner is modelled as the intersection of two lines. A corner point is that point on an input digital arc whose a posteriori probability of being a corner is the maximum among all the points on the arc. The performance of the corner detector is characterized by its false alarm rate, misdetection rate, and the corner location error all as a function of the noise variance, the included corner angle, and the arc length. Theoretical expressions for the quantities compare well with experimental results.>

Two sources of document degradation are modeled: i) perspective distortion that occurs while photocopying or scanning thick, bound documents, and ii) degradation due to perturbations in the optical scanning and digitization process: speckle, blurr, jitter, thresholding. Perspective distortion is modeled by studying the underlying perspective geometry of the optical system of photocopiers and scanners. An illumination model is described to account for the nonlinear intensity change occuring across a page in a perspective-distorted document. The optical distortion process is modeled morphologically. First, a distance transform on the foreground is performed, followed by a random inversion of binary pixels where the probability of flip is a function of the distance of the pixel to the boundary of the foreground. Correlating the flipped pixels is modeled by a morphological closing operation.>

The design of a comprehensive standard document database for machine-printed documents is presented. The effort to produce a series of carefully ground-truthed document databases to be issued on CD-ROMs is described in detail. The databases can be utilized by the OCR and document understanding community as a common platform to develop, test, and evaluate their algorithms.>

Producing a database of scanned document images for development or evaluation of OCR and document image understanding algorithms is neither easy nor inexpensive. The authors first briefly describe the makeup of a database of scanned document images of scientific and technical documents written in English which are being produced in a CD-ROM format. Then, the authors concentrate on the implementation methodology used to prepare the database. The methodology gives the protocols for each step of the database preparation, and the error model used for the estimation of the ground-truth errors that may exist in the database is discussed.>

The Proteus architecture is a highly parallel MIMD, multiple instruction, multiple-data machine, optimized for large granularity tasks such as machine vision and image processing. The system can achieve 20 Giga-flops (80 Giga-flops peak). It accepts data via multiple serial links at a rate of up to 640 megabytes/second. The system employs a hierarchical reconfigurable interconnection network with the highest level being a circuit switched Enhanced Hypercube serial interconnection network for internal data transfers. The system is designed to use 256 to 1024 RISC processors. The processors use one megabyte external Read/Write Allocating Caches for reduced multiprocessor contention. The system detects, locates, and replaces faulty subsystems using redundant hardware to facilitate fault tolerance.>