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.

We present a memory efficient method for transposing a run-length encoded bi-level image. Image transposing is a commonly used operation for affine transformations such as document image deskewing. The best existing method for transposing a run-length image is the pxy table based method. For images of typical engineering drawings, which are large, crowded and noisy, this method requires an exorbitant amount of memory. The method proposed uses a very compact representation of run-length encoded images. Also, it bypasses certain steps from the pxy table based method. Consequently, the saving in memory use is proportional to the number of horizontal runs and the number of vertical (transposed) runs. The computation time for both the methods is almost identical.

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.

We have developed an efficient method to extract straight lines at any orientation from a line drawing. The method works by extracting the horizontal and vertical lines using the FAST method, detecting the angles of the other lines and applying the FAST method again while the image is rotated to each corresponding angle. The method is efficient because it is based on very efficient line finding, transposition, and rotation operations which work over the run-length representation of the line drawing.

The paper describes a method for interpretation of lines in distributing frame drawings of a telephone company. The lines are composed of hierarchical components: intersections, segments and line links. First, intersections are located. Segments of lines are then detected. Adjacent segments are finally linked into a line. A post processing step refines the lines. The line extraction and classification are insensitive to touching characters and broken lines. A number of experimental results using real drawings demonstrate good performance of the algorithms.

This paper describes a methodology to interpret the information from telephone company DSX assignment table drawings. Horizontal lines are found using an efficient algorithm that works over the run-length encoded representation of the image. For vertical lines, the image is transposed using an efficient method we developed, and the algorithm for horizontal lines is applied again. Using the information about the lines, the tabular structures are extracted by finding biconnected components on the graph formed by the lines and their intersections. A methodology has also been developed for the representation of end access to the entries inside the tables.

We present efficient techniques for the interpretation and representation of tabular documents. Our goal is to achieve processing times that are fast enough for an interactive table conversion system. The techniques are based on the run-length encoded representation of scanned documents. We use DSX assignment tables, a predominant type of engineering drawing in telephone company central offices, as sample images in this paper. However, the techniques presented can be applied directly to tabular documents in any application.

In this paper we present the idea of using customizable tools to develop systems to interpret telephone company drawings. These drawings are composed primarily of horizontal and vertical lines. By selecting the intersections as primitives, routines are developed to establish spatial relations of the primitives which are used to describe the structures. Another aspect that as presented is the benefit of using run length encoding to reduce the amount of memory and the processing time needed to process the large files resulting from scanning the forementioned drawings. Examples of the interpretation of telephone company distributing frame and front equipment drawings are presented.

A system for the interpretation of telephone company drawings is described. Two different types of drawings are interpreted: manhole and table drawings. Each drawing is interpreted by using a different approach to suit its characteristics. Manhole drawings represent the interconnection of telephone lines in the field. The approach used is the vectorization of the line segments to extract continuous lines. The table drawings contain information related to the cables in the manhole. The approach is to locate lines and their intersections to extract the information for entries. An Intelligent Character Recognition (ICR) system is used to interpret text information by using grammars.>

Iterative methods, such as the conjugate gradient method, have long been used for the computation of optical flow along contours. For a contour with N points, the conjugate gradient method requires O(N) iterations (i.e., O(N/sup 2/) operations) to converge to a solution. We propose direct analytical methods for computing optical flow along both open contours and closed contours. These methods use O(N) operations, are numerically stable, and can be easily implemented on parallel hardware.>

This paper describes a methodology to interpret central office drawings using basic features in order to increase the efficiency of the interpretation. To interpret these drawings, the intersections between vertical and horizontal lines are located and related to obtain the position of boxes. Once the graphical information is interpreted, a grammar driven intelligent character recognition (ICR) system is used to extract text information in order to complete the interpretation of the drawing.

We describe a prototype generic form reader (GFR) system for reading hand-filled forms. The system can read run-on or touching handprinted characters. A one-time form specification is required for each type of form that the system is expected to read. The form specification includes geometric location of registration marks and fields of interest, field grammars, and system parameters. The GFR begins by detecting registration marks, computing image skew, extracting deskewed fields, and computing connected components in the field images. Next, the connected components are split into segments using heuristics about good splitting points. The system is liberal in splitting, i.e., a split segment could be a part of a character or a complete character, and hopefully no more than a character. Next, the segments are adaptively regrouped into 'seg-groups' with the aid of a dynamic programming algorithm that matches the character answers for the seg-groups with the field grammar specification. The single character recognizer (SCR) uses high order combinations of raw geometric features derived from segments and seg-groups. The high order combining rules are derived by statistical discriminant analysis of raw features. The GFR system provides some generic tools that can be applied to other document image analysis problems besides forms reading.>

Simchony, Chellappa, and Shao (1990) proposed a semi-direct method for computing area based optical flow. Their method is based on the iterative application of a direct Poisson solver. This method is restricted to Dirichlet boundary conditions, i.e., it is applicable only when velocity vectors at the boundary of the domain are known a priori. The authors show, both experimentally and through analysis, that the semi-direct method converges only for very large smoothness. At such levels of smoothness, the solution is obtained merely by filling in the known boundary values; the data from the image is almost totally ignored. Next, the authors consider the Concus and Golub method (1973), another semi-direct method, for computing optical flow. This method always converges, but the convergence is too slow to be of any practical value. The authors conclude that semi-direct methods are not suited for the computation of area based optical flow.>

The authors present efficient methodologies for interpreting manhole drawings of a telephone company for information extraction. They have developed a skew correction algorithm for deskewing scanned images, a new rule-based text/graphics separation algorithm for separating annotations in the drawings, and a graphics interpretation system which includes model-based arrow head detection, splice detection, and recognition of interconnections of cables and stubs. The final result from the interpretation system is a table which includes an ordered list of all cables and their interconnections which are contained in a manhole. Experimental results are used throughout to describe the algorithms.>

An intelligent character recognition (ICR) system for offline recognition of isolated handprinted characters is presented. The system comprises a feature extraction stage and a classifier (a feedforward network) that is trained using error backpropagation. The feature extraction stage consists of two steps. Given a bilevel image of a character, the system first extracts a set of experimentally optimized raw geometric features. These features are then combined to obtain higher order features which have higher discriminating ability according to the Fisher discriminant measure. The specific combinations of raw features that are chosen in particular application are determined by statistical analysis of the training data. The nonlinearity introduced by the feature combination is found to be much more powerful than the traditional sigmoid nonlinearity of backpropagation neural network classifiers. It is shown that by using the high-order features, one can drastically reduce the number of hidden nodes required in the classifier while retraining the same level of classification accuracy.>

T. Simchony et al. (1990) proposed a semidirect method for computing area-based optical flow, based on the iterative application of a direct Poisson solver. This method is restricted to Dirichlet boundary conditions, i.e. it is applicable only when velocity vectors at the boundary of the domain are known a priori. It is shown, both experimentally and through analysis, that the semidirect method converges only for a very high degree of smoothness. At such levels of smoothness, the solution is obtained merely by filling in the known boundary values; the data from the image is almost totally ignored. It is concluded that the semidirect method is not suited for the computation of area-based optical flow.>

E. Hildreth's (1984) method of computing optical flow along contours cannot resolve the aperture problem for a rigidly translating straight line contour. The authors propose an additional constraint, which they call the minimum norm constraint, as a means of resolving the ambiguity for such a contour. The minimum norm constraint tends to drive the velocity estimate towards the direction normal to the contour everywhere along the contour, i.e., it counters the effect of the smoothness constraint. This is in accord with recent psychophysical studies of K. Nakayama and G. Silverman (1988) which have revealed the presence of such a tendency in the human visual system. The authors propose an analog network for computing contour based optical flow in real-time. They illustrate the minimum norm constraint through experiments.>

Several analog networks have been proposed for solving the variational problems of early vision. The networks can be implemented in hardware using analog VLSI: thus, they can be used in real-time environments. The underlying mathematical formulations do not necessarily lead to a unique solution. The authors show how the nonuniqueness carries over to the analog networks. In particular, they study networks for contour-based optical flow, area-based optical flow, membrane surface reconstruction, and thin-plate surface reconstruction. An additional constraint, the minimum norm constraint, is proposed in the variational formulations of these problems. The minimum norm constraint ensures a unique solution. In analog networks, the constraint can be imposed simply by shunting each node to ground through an appropriate positive resistor. The minimum norm constraint also tends to force the solution to conform more with local measurements. This is in accord with a psychophysical study which has revealed the presence of such a tendency in the human visual system