This paper describes a fast and flexible method for extracting text regions from a document page containing text, graphics, and pictures. Such regions can be given as an input to an OCR system. The user fixes two parameters, the minimum width w of the text to be detected, and the precision /spl epsiv/ needed (both expressed as a percentage of the image width), according to the implementation needs. The method works by subdividing the page into overlapping columns whose width and inter-shift depend on w and /spl epsiv/, and by performing text lines extraction on each column separately. Successively, a statistical analysis of the text line elements found in each column is performed, and they are connected to form complete text lines. Finally, related pieces of text are merged into blocks so that a sensible reading order is provided for the OCR system. The algorithm is very fast, is able to work on low-resolution document pages and is robust against skew. The algorithm as also very flexible: no assumptions are made on the layout of the document, the shape of the text regions, and the font size and style; the main assumption is that the background is uniform and the text approximately horizontal. Despite the statistical nature of the method, a single line of text of a certain font size is generally sufficient to warrant detection. Experimental results are shown which demonstrate the effectiveness of the method on several different kinds of documents.

An efficient, novel technique for segmenting document pages of mixed content into text and non-text regions is presented. The aim of the technique is to provide a pre-processing for an OCR system, so that large amounts of documents of unknown layout can be examined and the written content of such documents can be put into digital format without human intervention. The user fixes two parameters, the minimum width w of the text to be detected, and the precision /spl epsiv/ needed (both expressed as a percentage of the image width), according to the implementation needs (default values that yield good results for widely varying kinds of documents are /spl epsiv/=2%, w=4/spl epsiv/). The method works by detecting pieces of text lines in small overlapping columns of width w-2/spl epsiv/, shifted with respect to each other by /spl epsiv/ and by merging such pieces in a bottom-up fashion to form complete text lines and blocks of text lines. The algorithm is very fast and flexible and is able to work on low-resolution document pages. Experimental results are given which demonstrate the effectiveness of the method on several different kinds of documents.

This paper investigates the quantitative reconstruction of the 3D structure of a scene from a line drawing, by using the geometrical constraints provided by the location of vanishing points. The additional information on vanishing points allows the design of an algorithm which has several advantages with respect to the usual approach based on a reduction to linear programming (Sugihara, 1982). These advantages range from a lower computational complexity to error tolerance and exact reconstruction of the 3D-geometry of the objects. These features make the algorithm a useful tool for the quantitative analysis of real-world images, which is useful for several tasks from scene understanding to automatic vehicle guidance.

The authors investigate the computational time complexity of the labeling problem for line drawings of polyhedral scenes. It is found that line drawings can be labeled in time proportional to the number of segments once the vanishing points associated to the possible directions for the edges are known. The vanishing points can be given a priori, otherwise they can in many cases be detected by standard techniques from the line drawing itself. The NP-completeness of the labeling problem for line drawings of trihedral scenes (Kirousis and Papadimitriou, 1988) is then due to the lack of knowledge about the vanishing points, which is equivalent to the knowledge of the possible directions for the edges. These results help draw a more accurate boundary between the problems in the interpretation of line drawings that are polynomially solvable and those that are NP-complete.>