Segmentation and recognition of Chinese bank check amounts

This paper describes a system for the recognition of legal amounts on bank checks written in the Chinese language. It consists of subsystems that perform preprocessing, segmentation, and recognition of the legal amount. In each step of the segmentation and recognition phases, a list of possible choices are obtained. An approach is adopted whereby a large number of choices can be processed effectively and efficiently in order to achieve the best recognition result. The contribution of this paper is the proposal of a grammar checker for Chinese bank check amounts. It is found to be very effective in reducing the substitution error rate. The recognition rate of the system is 74.0%, the error rate is 10.4%, and the reliability is 87.7%. Received June 9, 2000 / Revised January 10, 2001     

Diacritical processing for unconstrained online handwriting recognition using a forward search

Out-of-order diacriticals introduce significant complexity to the design of an online handwriting recognizer, because they require some reordering of the time domain information. It is common in cursive writing to write the body of an `i' or `t' during the writing of the word, and then to return and dot or cross the letter once the word is complete. The difficulty arises because we have to look ahead, when scoring one of these letters, to find the mark occurring later in the writing stream that completes the letter. We should also remember that we have used this mark, so that we don't use it again for a different letter, and we should also penalize a word if there are some marks that look like diacriticals that are not used. One approach to this problem is to scan the writing some distance into the future to identify candidate diacriticals, remove them in a preprocessing step, and associate them with the matching letters earlier in the word. If done as a preliminary operation, this approach is error-prone: marks that are not diacriticals may be incorrectly identified and removed, and true diacriticals may be skipped. This paper describes a novel extension to a forward search algorithm that provides a natural mechanism for considering alternative treatments of potential diacriticals, to see whether it is better to treat a given mark as a diacritical or not, and directly compare the two outcomes by score. Received October 30, 1998 / Revised January 25, 1999     

Evaluating the performance of table processing algorithms

While techniques for evaluating the performance of lower-level document analysis tasks such as optical character recognition have gained acceptance in the literature, attempts to formalize the problem for higher-level algorithms, while receiving a fair amount of attention in terms of theory, have generally been less successful in practice, perhaps owing to their complexity. In this paper, we introduce intuitive, easy-to-implement evaluation schemes for the related problems of table detection and table structure recognition. We also present the results of several small experiments, demonstrating how well the methodologies work and the useful sorts of feedback they provide. We first consider the table detection problem. Here algorithms can yield various classes of errors, including non-table regions improperly labeled as tables (insertion errors), tables missed completely (deletion errors), larger tables broken into a number of smaller ones (splitting errors), and groups of smaller tables combined to form larger ones (merging errors). This leads naturally to the use of an edit distance approach for assessing the results of table detection. Next we address the problem of evaluating table structure recognition. Our model is based on a directed acyclic attribute graph, or table DAG. We describe a new paradigm, “graph probing,” for comparing the results returned by the recognition system and the representation created during ground-truthing. Probing is in fact a general concept that could be applied to other document recognition tasks as well. Received July 18, 2000 / Accepted October 4, 2001     

Quality assessment and restoration of typewritten document images

We present a useful method for assessing the quality of a typewritten document image and automatically selecting an optimal restoration method based on that assessment. We use five quality measures that assess the severity of background speckle, touching characters, and broken characters. A linear classifier uses these measures to select a restoration method. On a 139-document corpus, our methodology reduced the corpus OCR character error rate from 20.27% to 12.60%. Received November 10, 1998 / Revised October 27, 1999     

A new electronic check system with reusable refunds

This paper presents a new online check system that solves the reusability problem of refunds in existing systems using the partially blind signature. The clear part of the signature is used to encode the face value of a check. In our system, refunds can be reused in payment in the same way as withdrawn checks without any limitation. We also use a one-time secret key as the serial number of a check to increase the efficiency of payment. The new system provides multiple offline shopping sessions to minimize the number of online messages. During the offline session, we use a one-way accumulator to construct a proof of payment. The security and the atomicity of the system is also discussed. Published online: 3 September 2002     

A complete system for the intelligent interpretation of engineering drawings

Converting paper-based engineering drawings into CAD model files is a tedious process. Therefore, automating the conversion of such drawings represents tremendous time and labor savings. We present a complete system which interprets such 2D paper-based engineering drawings, and outputs 3D models that can be displayed as wireframes. The system performs the detection of dimension sets, the extraction of object lines, and the assembly of 3D objects from the extracted object lines. A knowledge-based method is used to remove dimension sets and text from ANSI engineering drawings, a graphics recognition procedure is used to extract complete object lines, and an evidential rule-based method is utilized to identify view relationships. While these methods are the subject of several of our previous papers, this paper focuses on the 3D interpretation of the object. This is accomplished using a technique based on evidential reasoning and a wide range of rules and heuristics. The system is limited to the interpretation of objects composed of planar, spherical, and cylindrical surfaces. Experimental results are presented. Received December 2, 1998 / Revised June 18, 1999     

A generic method of cleaning and enhancing handwritten data from business forms

The automation of business form processing is attracting intensive research interests due to its wide application and its reduction of the heavy workload due to manual processing. Preparing clean and clear images for the recognition engines is often taken for granted as a trivial task that requires little attention. In reality, handwritten data usually touch or cross the preprinted form frames and texts, creating tremendous problems for the recognition engines. In this paper, we contribute answers to two questions: “Why do we need cleaning and enhancement procedures in form processing systems?” and “How can we clean and enhance the hand-filled items with easy implementation and high processing speed?” Here, we propose a generic system including only cleaning and enhancing phases. In the cleaning phase, the system registers a template to the input form by aligning corresponding landmarks. A unified morphological scheme is proposed to remove the form frames and restore the broken handwriting from gray or binary images. When the handwriting is found touching or crossing preprinted texts, morphological operations based on statistical features are used to clean it. In applications where a black-and-white scanning mode is adopted, handwriting may contain broken or hollow strokes due to improper thresholding parameters. Therefore, we have designed a module to enhance the image quality based on morphological operations. Subjective and objective evaluations have been studied to show the effectiveness of the proposed procedures. Received January 19, 2000 / Revised March 20, 2001     

MAGELLAN: Map Acquisition of GEographic Labels by Legend ANalysis

A system named MAGELLAN (denoting Map Acquisition of GEographic Labels by Legend ANalysis) is described that utilizes the symbolic knowledge found in the legend of the map to drive geographic symbol (or label) recognition. MAGELLAN first scans the geographic symbol layer(s) of the map. The legend of the map is located and segmented. The geographic symbols (i.e., labels) are identified, and their semantic meaning is attached. An initial training set library is constructed based on this information. The training set library is subsequently used to classify geographic symbols in input maps using statistical pattern recognition. User interaction is required at first to assist in constructing the training set library to account for variability in the symbols. The training set library is built dynamically by entering only instances that add information to it. MAGELLAN then proceeds to identify the geographic symbols in the input maps automatically. MAGELLAN can be fine-tuned by the user to suit specific needs. Recognition rates of over 93% were achieved in an experimental study on a large amount of data. Received January 5, 1998 / Revised March 18, 1998     

Identifying facsimile duplicates using radial pixel densities

A method for detecting full layout facsimile duplicates based on radial pixel densities is proposed. It caters for facsimiles, including text and/or graphics. Pages may be positioned upright or inverted on the scanner bed. The method is not dependent on the computation of text skew or text orientation. Using a database of original documents, 92% of non-duplicates and upright duplicates as well as 89% of inverted duplicates could be correctly identified. The method is vulnerable to double scanning. This occurs when documents are copied using a photocopier and the copies are subsequently transmitted using a facsimile machine. Received September 29, 2000 / Revised: August 23, 2001     

ObjectGlobe: Ubiquitous query processing on the Internet

We present the design of ObjectGlobe, a distributed and open query processor for Internet data sources. Today, data is published on the Internet via Web servers which have, if at all, very localized query processing capabilities. The goal of the ObjectGlobe project is to establish an open marketplace in which data and query processing capabilities can be distributed and used by any kind of Internet application. Furthermore, ObjectGlobe integrates cycle providers (i.e., machines) which carry out query processing operators. The overall picture is to make it possible to execute a query with – in principle – unrelated query operators, cycle providers, and data sources. Such an infrastructure can serve as enabling technology for scalable e-commerce applications, e.g., B2B and B2C market places, to be able to integrate data and data processing operations of a large number of participants. One of the main challenges in the design of such an open system is to ensure privacy and security. We discuss the ObjectGlobe security requirements, show how basic components such as the optimizer and runtime system need to be extended, and present the results of performance experiments that assess the additional cost for secure distributed query processing. Another challenge is quality of service management so that users can constrain the costs and running times of their queries. Received: 30 October 2000 / Accepted: 14 March 2001 Published online: 7 June 2001     

An architecture for handwritten text recognition systems

This paper presents an end-to-end system for reading handwritten page images. Five functional modules included in the system are introduced in this paper: (i) pre-processing, which concerns introducing an image representation for easy manipulation of large page images and image handling procedures using the image representation; (ii) line separation, concerning text line detection and extracting images of lines of text from a page image; (iii) word segmentation, which concerns locating word gaps and isolating words from a line of text image obtained efficiently and in an intelligent manner; (iv) word recognition, concerning handwritten word recognition algorithms; and (v) linguistic post-pro- cessing, which concerns the use of linguistic constraints to intelligently parse and recognize text. Key ideas employed in each functional module, which have been developed for dealing with the diversity of handwriting in its various aspects with a goal of system reliability and robustness, are described in this paper. Preliminary experiments show promising results in terms of speed and accuracy. Received October 30, 1998 / Revised January 15, 1999     

An empirical measure of the performance of a document image segmentation algorithm

Document image segmentation is the first step in document image analysis and understanding. One major problem centres on the performance analysis of the evolving segmentation algorithms. The use of a standard document database maintained at the Universities/Research Laboratories helps to solve the problem of getting authentic data sources and other information, but some methodologies have to be used for performance analysis of the segmentation. We describe a new document model in terms of a bounding box representation of its constituent parts and suggest an empirical measure of performance of a segmentation algorithm based on this new graph-like model of the document. Besides the global error measures, the proposed method also produces segment-wise details of common segmentation problems such as horizontal and vertical split and merge as well as invalid and mismatched regions. Received July 14, 2000 / Revised June 12, 2001[-1mm]     

The IAM-database: an English sentence database for offline handwriting recognition

In this paper we describe a database that consists of handwritten English sentences. It is based on the Lancaster-Oslo/Bergen (LOB) corpus. This corpus is a collection of texts that comprise about one million word instances. The database includes 1,066 forms produced by approximately 400 different writers. A total of 82,227 word instances out of a vocabulary of 10,841 words occur in the collection. The database consists of full English sentences. It can serve as a basis for a variety of handwriting recognition tasks. However, it is expected that the database would be particularly useful for recognition tasks where linguistic knowledge beyond the lexicon level is used, because this knowledge can be automatically derived from the underlying corpus. The database also includes a few image-processing procedures for extracting the handwritten text from the forms and the segmentation of the text into lines and words. Received September 28, 2001 / Revised October 10, 2001     

Document skew estimation without angle range restriction

The existing skew estimation techniques usually assume that the input image is of high resolution and that the detectable angle range is limited. We present a more generic solution for this task that overcomes these restrictions. Our method is based on determination of the first eigenvector of the data covariance matrix. The solution comprises image resolution reduction, connected component analysis, component classification using a fuzzy approach, and skew estimation. Experiments on a large set of various document images and performance comparison with two Hough transform-based methods show a good accuracy and robustness for our method. Received October 10, 1998 / Revised version September 9, 1999     

Intelligent forms processing system

This paper describes an intelligent forms processing system (IFPS) which provides capabilities for automatically indexing form documents for storage/retrieval to/from a document library and for capturing information from scanned form images using intelligent character recognition (ICR). The system also provides capabilities for efficiently storing form images. IFPS consists of five major processing components: (1) An interactive document analysis stage that analyzes a blank form in order to define a model of each type of form to be accepted by the system; the parameters of each model are stored in a form library. (2) A form recognition module that collects features of an input form in order to match it against one represented in the form library; the primary features used in this step are the pattern of lines defining data areas on the form. (3) A data extraction component that registers the selected model to the input form, locates data added to the form in fields of interest, and removes the data image to a separate image area. A simple mask defining the center of the data region suffices to initiate the extraction process; search routines are invoked to track data that extends beyond the masks. Other special processing is called on to detect lines that intersect the data image and to delete the lines with minimum distortion to the rest of the image. (4) An ICR unit that converts the extracted image data to symbol code for input to data base or other conventional processing systems. Three types of ICR logic have been implemented in order to accommodate monospace typing, proportionally spaced machine text, and handprinted alphanumerics. (5) A forms dropout module that removes the fixed part of a form and retains only the data filled in for storage. The stored data can be later combined with the fixed form to reconstruct the original form. This provides for extremely efficient storage of form images, thus making possible the storage of very large number of forms in the system. IFPS is implemented as part of a larger image management system called Image and Records Management system (IRM). It is being applied in forms data management in several state government applications.     

Efficient extraction of primitives from line drawings composed of horizontal and vertical lines

The performance of the algorithms for the extraction of primitives for the interpretation of line drawings is usually affected by the degradation of the information contained in the document due to factors such as low print contrast, defocusing, skew, etc. In this paper, we are proposing two algorithms for the extraction of primitives with good performance under degradation. The application of the algorithms is restricted to line drawings composed of horizontal and vertical lines. The performance of the algorithms has been evaluated by using a protocol described in the literature. Received: 6 August 1996 / Accepted: 16 July 1997     

Using citing information to understand the logical structure of document images

The most noticeable characteristic of a construction tender document is that its hierarchical architecture is not obviously expressed but is implied in the citing information. Currently available methods cannot deal with such documents. In this paper, the intra-page and inter-page relationships are analyzed in detail. The creation of citing relationships is essential to extracting the logical structure of tender documents. The hierarchy of tender documents naturally leads to extracting and displaying the logical structure as tree structure. This method is successfully implemented in VHTender, and is the key to the efficiency and flexibility of the whole system. Received February 28, 2000 / Revised October 20, 2000     

A criterion based on Fourier transform for segmentation of connected digits

Abstract. Segmentation is the most difficult problem in handwritten character recognition systems and often causes major errors in performance. To reach a balance between speed and accuracy, a filter distinguishing connected images from isolated images for multiple stage segmentation is required. The Fourier spectrum is a promising approach to this problem, although it suffers from the heavy influence of stroke width. Therefore, we introduce SFS (SFS) to eliminate the stroke-width effect. Based on the SFS, a set of features and a fine-tuned criterion are presented to classify connected/isolated images. Theoretical analysis demonstrates their soundness, while experimental results demonstrate that this criterion is better than other methods. Received February 18, 2000 / Revised June 3, 2000