Document Image Analysis

The following sections are included:

• CONTENTS

Interest in the automatic processing and analysis of document images has been rapidly increasing during the past few years. New conferences were established, existing ones received a growing number of submissions, and many related publications appeared. The increasing interest in this field is motivated by several factors. First, document image analysis has a history of over thirty years and many fundamental ideas have been known for a long time. But it was only recently that powerful and cheap hardware became available to put these ideas into practice. Secondly, the first low-cost OCR devices, i.e. scanners with OCR-software running on personal computers, were very successful and there are many other practical problems for which the development of similar solutions seems possible in the near future. Moreover, there are close links between document image analysis and some other currently popular research topics in computer science, like multi- or hypermedia systems, and a new generation of man-machine interfaces…

A perfectly parallel thinning algorithm (PPTA) is proposed. It can generate perfect skeletons, which consist of end points, break points, and hole points only. Experimental results show that the proposed PPTA can also preserve image connectivity, produce thinner skeletons, and is faster than many existing thinning algorithms. For example, it is twice as fast as one of the fastest parallel thinning algorithm by Holt, Stewart, Clint and Perrorte.

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

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.

Check forms are used by many people in daily life for money remittances. Surprisingly, the processing of these forms at banks and post offices is only partly automated. In this paper, we consider a particular kind of form, viz., the GIRO check forms used in Switzerland. We will describe a fully automatic system which is able to recognise the financial institution, the name and address of the receiver, and the account number on a GIRO check. The system comprises procedures for binarization, segmentation, model matching, and optical character recognition (OCR). Experiments on a sample set of 48 checks have shown promising results in terms of both computation time and recognition accuracy.

Knowing the structure of a document is the key to successful processing of a document. There exist a variety of definitions of document structures. This paper is a survey of methods describing document structures. Several novel concepts and theoretical analyses are also presented.

A document not only has a concrete two-dimensional image but also a conceptual structure which corresponds to human's thinking. The process of publishing or writing corresponds to encoding the conceptual structure into a concrete structure. Conversely, the concrete structure of the document is decoded into its conceptual one in document processing. In this paper, conceptual and concrete structures are introduced.

A complete system for treating both of the conceptual and concrete structures is probably still decades away. As the first stage, this study puts some emphasis on concrete structures, for which, geometric, logical, textual, information, textural, and other structures are described.

An automatic system that reads an image of a logic diagram, digitized by a document scanner, and generates a description of the diagram in terms of logic symbols and their interconnections is proposed. The digitized image is converted into a set of line segments by way of a sequence of picture processing operations. Then symbols and connections are recognized by identifying loops and rectilinear polylines. Graphical description of a set of symbol models is provided as prior knowledge about input diagrams.

Experiments show that the system can recognize more than 96% of logic symbols and connections and that an A4 size diagram (210 × 297 mm) of average complexity can be processed within 10 seconds on a workstation.

We present a syntactic approach to technical drawing dimensions analysis. A specific grammar is used to describe dimensions of drawings. This grammar can be graphically designed by combining different graphic primitives. The algorithm used for analysis can start at different points of the grammar. The analysis proceeds bottom-up and top-down according to previously obtained results.

We have proposed the MAP (Multi-Angled Parallel) operation method which extracts geometric features from a topographic map using erosion-dilation operations on a directional feature field. We have also proposed the MAP matching method which recognizes fixed-shaped symbols in the topographic map by using parallel operations on the same directional feature field. We have shown that all kinds of feature extraction and recognition can be effectively performed within the framework of parallel operation.

In this paper, we show that elevation values in a topographic map can be recognized by a combination of MAP operation with the MAP matching. Numerals and symbols are recognized by the MAP matching method, while small dots and lines are extracted by the MAP operation method. These results are used together to determine the value, position and attribute of elevations in topographic maps.

This paper describes a new method for character recognition of typewritten text. The proposed approach is based on the approximation of character signatures by rational functions. Specifically, after the preprocessing operation, a separation procedure is applied to each character and its one-dimensional signatures are derived. These signatures are then approximated by rational functions via a linear programming technique and according to the minimax criterion. The values of the approximation errors for each signature are specified as character features. Through this technique only six powerful features are derived for each character. The classification technique employed is simple, adapted to the features selected and is based on features' similarities in combination with the minimum Euclidean distance classifier.

The topology and the capacity of a traditional multilayer neural system, as measured by the number of connections in the network, has surprisingly little impact on its generalization ability. This paper presents a new adaptive modular network that offers superior generalization capability. The new network provides significant fault tolerance, quick adaption to novel inputs, and high recognition accuracy. We demonstrate this paradigm on recognition of unconstrained handwritten characters.

Recognition of handwritten character strings is a challenging problem, because we need to cope with variations of shapes and touching/breaking of characters at the same time. A natural approach to recognizing such complex objects is as follows: The object is decomposed into segments, and meaningful partial shapes (shapes which are recognized as some characters) are constructed by merging segments locally. Then, a globally consistent interpretation of the object is determined from the combination of partial shapes. This approach can be referred to as a model-based split-and-merge method. Based on this idea, we present an algorithm for recognition and segmentation of character strings. We give systematic performance statistics by experiments using handwritten numerals. This algorithm can be applied to character strings composed of any number of characters and any type of touching or breaking, whether the number of constituent characters is known or unknown.

The stroke analysis method is an effective approach for handwritten Chinese character recognition. But as we know, it is very difficult to accurately extract the strokes. In this paper, a robust stroke extraction method is proposed. First, smoothing and thinning processes are applied to smooth the shape and to obtain the skeleton of the observed character. Then the end point, internal point and fork point are detected by calculating their own crossing numbers while the corner points are determined by a knowledge-based iterative method. Virtual-end-points are introduced for separating a stroke into a certain number of line segments without losing the connection relations among them. By representing each line segment as a vertex and the connection relation of two segments as an edge, the observed character can be represented by an attributed graph. Finally, a stroke extraction procedure is proposed to extract the strokes from the global structures of the character. After each stroke of a character is extracted, the cross points can also be determined. Experimental results have shown that the proposed method is more effective than the other methods.^3,5–6

A simplified Bayes rule is used to classify 5401 categories of handwritten Chinese characters. The main feature for the Bayes rule deals with the probability distribution of black pixels of a thinned character. Our idea is that each Chinese character indicated by the black pixels represents a probability distribution in a two-dimensional plane. Therefore, an unknown pattern is classified into one of 5401 different distributions by the Bayes rule. Since the handwritten character has an irregular shape variation, the whole character is normalized and then thinned. Finally, a transformation is used to spread the black pixels uniformly over the whole square plane, but it still keeps the relative positions of the original black pixels. The main feature gives an 88.65% recognition rate. In order to raise the recognition rate, 4 more subsidiary features are elaborately selected such that they are not affected much by the irregularly shaped variation. The 4 features raise the recognition rate to 93.43%. A 99.30% recognition rate is achieved if the top 10 categories of HCC are selected by our recognition method and 99.61% if the top 20 are selected.

When optical character recognition (OCR) devices process the same page image, they generate similar text strings. Differences are due to recognition errors. A page of text rarely contains long repeated substrings; therefore, N strings generated by OCR devices can be quickly matched by detecting long common substrings. An algorithm for matching an arbitrary number of strings based on this principle is presented. Although its worst-case performance is O(Nn²), its performance in practice has been observed to be O(Nn log n), where n is the length of a string. This algorithm has been successfully used to study OCR errors, to determine the accuracy of OCR devices, and to implement a voting algorithm.

The following sections are included:

• INDEX