Symbol and character recognition: application to engineering drawings

In this paper, we consider the general problem of technical document interpretation, as applied to the documents of the French Telephonic Operator, France Télécom. More precisely, we focus the content of this paper on the computation of a new set of features allowing the classification of multioriented and multiscaled patterns. This set of invariants is based on the Fourier–Mellin Transform. The interests of this computation rely on the excellent classification rate obtained with this method and also on using this Fourier–Mellin transform within a “filtering mode”, with which we can solve the well known difficult problem of connected character recognition.     

Transforming paper documents into XML format with WISDOM++

The transformation of scanned paper documents to a form suitable for an Internet browser is a complex process that requires solutions to several problems. The application of an OCR to some parts of the document image is only one of the problems. In fact, the generation of documents in HTML format is easier when the layout structure of a page has been extracted by means of a document analysis process. The adoption of an XML format is even better, since it can facilitate the retrieval of documents in the Web. Nevertheless, an effective transformation of paper documents into this format requires further processing steps, namely document image classification and understanding. WISDOM++ is a document processing system that operates in five steps: document analysis, document classification, document understanding, text recognition with an OCR, and transformation into HTML/XML format. The innovative aspects described in the paper are: the preprocessing algorithm, the adaptive page segmentation, the acquisition of block classification rules using techniques from machine learning, the layout analysis based on general layout principles, and a method that uses document layout information for conversion to HTML/XML formats. A benchmarking of the system components implementing these innovative aspects is reported. Received June 15, 2000 / Revised November 7, 2000     

Automatic document classification and indexing in high-volume applications

In this paper a system for analysis and automatic indexing of imaged documents for high-volume applications is described. This system, named STRETCH (STorage and RETrieval by Content of imaged documents), is based on an Archiving and Retrieval Engine, which overcomes the bottleneck of document profiling bypassing some limitations of existing pre-defined indexing schemes. The engine exploits a structured document representation and can activate appropriate methods to characterise and automatically index heterogeneous documents with variable layout. The originality of STRETCH lies principally in the possibility for unskilled users to define the indexes relevant to the document domains of their interest by simply presenting visual examples and applying reliable automatic information extraction methods (document classification, flexible reading strategies) to index the documents automatically, thus creating archives as desired. STRETCH offers ease of use and application programming and the ability to dynamically adapt to new types of documents. The system has been tested in two applications in particular, one concerning passive invoices and the other bank documents. In these applications, several classes of documents are involved. The indexing strategy first automatically classifies the document, thus avoiding pre-sorting, then locates and reads the information pertaining to the specific document class. Experimental results are encouraging overall; in particular, document classification results fulfill the requirements of high-volume application. Integration into production lines is under execution. Received March 30, 2000 / Revised June 26, 2001     

Classification of document pages using structure-based features

Searching for documents by their type or genre is a natural way to enhance the effectiveness of document retrieval. The layout of a document contains a significant amount of information that can be used to classify it by type in the absence of domain-specific models. Our approach to classification is based on “visual similarity” of layout structure and is implemented by building a supervised classifier, given examples of each class. We use image features such as percentages of text and non-text (graphics, images, tables, and rulings) content regions, column structures, relative point sizes of fonts, density of content area, and statistics of features of connected components which can be derived without class knowledge. In order to obtain class labels for training samples, we conducted a study where subjects ranked document pages with respect to their resemblance to representative page images. Class labels can also be assigned based on known document types, or can be defined by the user. We implemented our classification scheme using decision tree classifiers and self-organizing maps. Received June 15, 2000 / Revised November 15, 2000     

Rule-based document structure understanding with a fuzzy combination of layout and textual features

Document image processing is a crucial process in office automation and begins at the ‘OCR’ phase with difficulties in document ‘analysis’ and ‘understanding’. This paper presents a hybrid and comprehensive approach to document structure analysis. Hybrid in the sense that it makes use of layout (geometrical) as well as textual features of a given document. These features are the base for potential conditions which in turn are used to express fuzzy matched rules of an underlying rule base. Rules can be formulated based on features which might be observed within one specific layout object. However, rules can also express dependencies between different layout objects. In addition to its rule driven analysis, which allows an easy adaptation to specific domains with their specific logical objects, the system contains domain-independent markup algorithms for common objects (e.g., lists). Received June 19, 2000 / Revised November 8, 2000     

User Environments and Individuals: Experience with Adaptive Interface Agents

The traditional style of working with computers generally revolves around the computer being used as a tool, with individual users directly initiating operations and waiting for the results of them. A more recent paradigm of human-computer interaction, based on the indirect management of computing resources, is agent-based interaction. The idea of delegation plays a key part in this approach to computer-based work, which allows individuals to relinquish the routine, mechanistic parts of their everyday tasks, having them performed automatically instead. Adaptive interfaces combine elements of both these approaches, where the goal is to have the interface adapt to its users rather than the reverse. This paper addresses some of the issues arising from a practical software development process which aimed to support individuals using this style of interaction. This paper documents the development of a set of classes which implement an architecture for adaptive interfaces. These classes are intended to be used as part of larger user interface systems which are to exhibit adaptive behaviour. One approach to the implementation of an adaptive interface is to use a set of software “agents”– simple processes which effectively run “in the background”– to decompose the task of implementing the interface. These agents form part of a larger adaptive interface architecture, which in turn forms a component of the adaptive system.     

Specifications in Context: Stakeholders, Systems and Modelling of Conflict

This paper looks from an ethnographic viewpoint at the case of two information systems in a multinational engineering consultancy. It proposes using the rich findings from ethnographic analysis during requirements discovery. The paper shows how context – organisational and social – can be taken into account during an information system development process. Socio-technical approaches are holistic in nature and provide opportunities to produce information systems utilising social science insights, computer science technical competence and psychological approaches. These approaches provide fact-finding methods that are appropriate to system participants’ and organisational stakeholders’ needs.  The paper recommends a method of modelling that results in a computerised information system data model that reflects the conflicting and competing data and multiple perspectives of participants and stakeholders, and that improves interactivity and conflict management.     

Efficiently publishing relational data as XML documents

XML is rapidly emerging as a standard for exchanging business data on the World Wide Web. For the foreseeable future, however, most business data will continue to be stored in relational database systems. Consequently, if XML is to fulfill its potential, some mechanism is needed to publish relational data as XML documents. Towards that goal, one of the major challenges is finding a way to efficiently structure and tag data from one or more tables as a hierarchical XML document. Different alternatives are possible depending on when this processing takes place and how much of it is done inside the relational engine. In this paper, we characterize and study the performance of these alternatives. Among other things, we explore the use of new scalar and aggregate functions in SQL for constructing complex XML documents directly in the relational engine. We also explore different execution plans for generating the content of an XML document. The results of an experimental study show that constructing XML documents inside the relational engine can have a significant performance benefit. Our results also show the superiority of having the relational engine use what we call an “outer union plan” to generate the content of an XML document. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001     

The “Authoring on the Fly” system for automated recording and replay of (tele)presentations

We discuss the problem of capturing media streams which occur during a live lecture in class or during a telepresentation. Instead of presenting yet another method or system for capturing the classroom experience, we introduce some informal guidelines and show their importance for such a system. We derive from these guidelines a formal framework for sets of data streams and an application model to handle these sets so that a real-time replay becomes possible. The Authoring on the Fly system is a possible realization of a framework which follows these guidelines. It allows the capture and real-time replay of data streams captured during a (tele)presentation, including audio, video, and whiteboard action streams. This article gives an overview of the different AoF system components for the various phases of the teaching and learning cycle. It comprises an integrated text and graphics editor for the preparation of pages to be loaded by the whiteboard during the presentation phase. The recording component of the system captures various data streams of the live presentation. They are postprocessed by the system so that they become instances of the class of media for whose replay the general application model was developed. From a global point of view, the Authoring on the Fly system allows one to merge three apparently distinct tasks – teaching in class, telepresentation, and multimedia authoring – into one single activity. The system has been used routinely for recording telepresentations over the MBone net and has already led to a large number of multimedia documents which have been integrated automatically into Web-based teaching and learning environments.     

The Region of Aachen as a ‘Learning Region’: A Case Study

All economic processes are increasingly being networked across the globe. This economic globalisation has become possible through the globalisation of information and communication technology networks. In view of such growing globalisation of economic processes, the region and its enterprises can only sustain competitiveness on the basis of continuous innovation processes, i.e., through continuous learning. The question, however, is which kind of economic framework – established by regional or transregional politics – is needed to support such innovation and learning processes in the region. In this paper, some aspects of this framework and its structural change processes are described, leading to the strategy to implement the concept of a Learning Region. The Learning Region is characterised in that it recognises its own needs for change and to accept these challenges, leading to its own learning processes within its cooperative networks.     

WIRES: A Methodology for Developing Workflow Applications

Workflow management systems are becoming a relevant support for a large class of business applications, and many workflow models as well as commercial products are currently available. While the large availability of tools facilitates the development and the fulfilment of customer requirements, workflow application development still requires methodological guidelines that drive the developers in the complex task of rapidly producing effective applications. In fact, it is necessary to identify and model the business processes, to design the interfaces towards existing cooperating systems, and to manage implementation aspects in an integrated way. This paper presents the WIRES methodology for developing workflow applications under a uniform modelling paradigm – UML modelling tools with some extensions – that covers all the life cycle of these applications: from conceptual analysis to implementation. High-level analysis is performed under different perspectives, including a business and an organisational perspective. Distribution, interoperability and cooperation with external information systems are considered in this early stage. A set of “workflowability” criteria is provided in order to identify which candidate processes are suited to be implemented as workflows. Non-functional requirements receive particular emphasis in that they are among the most important criteria for deciding whether workflow technology can be actually useful for implementing the business process at hand. The design phase tackles aspects of concurrency and cooperation, distributed transactions and exception handling. Reuse of component workflows, available in a repository as workflow fragments, is a distinguishing feature of the method. Implementation aspects are presented in terms of rules that guide in the selection of a commercial workflow management system suitable for supporting the designed processes, coupled with guidelines for mapping the designed workflows onto the model offered by the selected system.     

ScholOnto: an ontology-based digital library server for research documents and discourse

The internet is rapidly becoming the first place for researchers to publish documents, but at present they receive little support in searching, tracking, analysing or debating concepts in a literature from scholarly perspectives. This paper describes the design rationale and implementation of ScholOnto, an ontology-based digital library server to support scholarly interpretation and discourse. It enables researchers to describe and debate via a semantic network the contributions a document makes, and its relationship to the literature. The paper discusses the computational services that an ontology-based server supports, alternative user interfaces to support interaction with a large semantic network, usability issues associated with knowledge formalisation, new work practices that could emerge, and related work. Published online: 22 September 2000     

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     

Interactive authoring of multimedia documents in a constraint-based authoring system

As multimedia applications spread widely, it is crucial for programming and design support systems to handle “time” in multimedia documents effectively and flexibly. This paper presents a set of interactive system support tools for designing and maintaining the temporal behavior of multimedia documents. The tool set provides mechanisms for anomaly detection, temporal query processing, and interactive scheduling. It is based on a fast incremental constraint solver we have developed, which can be adapted by any constraint-based system. The incremental constraint solver provides immediate feedback to the user, supporting a highly interactive design process. Combined with existing optimal layout generation mechanisms proposed in the literature, our tools effectively utilize the flexibility provided by constraint-based systems.     

Recognition of table of contents for electronic library consulting

A labelling approach for the automatic recognition of tables of contents (ToC) is described in this paper. A prototype is used for the electronic consulting of scientific papers in a digital library system named Calliope. This method operates on a roughly structured ASCII file, produced by OCR. The recognition approach operates by text labelling without using any a priori model. Labelling is based on part-of-speech tagging (PoS) which is initiated by a primary labelling of text components using some specific dictionaries. Significant tags are first grouped into homogeneous classes according to their grammar categories and then reduced in canonical forms corresponding to article fields: “title” and “authors”. Non-labelled tokens are integrated in one or another field by either applying PoS correction rules or using a structure model generated from well-detected articles. The designed prototype operates very well on different ToC layouts and character recognition qualities. Without manual intervention, a 96.3% rate of correct segmentation was obtained on 38 journals, including 2,020 articles, accompanied by a 93.0% rate of correct field extraction. Received April 5, 2000 / Revised February 19, 2001     

Long lived adaptive splitter and applications

Summary. Long-lived and adaptive implementations of mutual exclusion and renaming in the read/write shared memory model are presented. An implementation of a task is adaptive if the step complexity of any operation in the implementation is a function of the number of processes that take steps concurrently with the operation. The renaming algorithm assigns a new unique id in the range to any process whose initial unique name is taken from a set of size N, for an arbitrary N and where k is the number of processes that actually take steps or hold a name while the new name is being acquired. The step complexity of acquiring a new name is , while the step complexity of releasing a name is 1. The space complexity of the algorithm is where n is an upper bound on the number of processes that may be active at the same time (acquiring or holding new names), which could be N in the worst case. Both the system response time and the worst case number of operations per process in the presented mutual-exclusion algorithm are adaptive. Both algorithms rely on the basic building block of a long-lived and adaptive splitter. While the adaptive-splitter satisfies a slightly different set of properties than the Moir-Anderson splitter [MA95], it is adaptive and long-lived. In addition, the new splitter properties enable the construction of a non-blocking long-lived (2k-1)-renaming algorithm (which is optimal in the size of the new name space). We believe that the mechanisms introduced in our splitter implementation are interesting on their own, and might be used in other adaptive and long-lived constructions. Received: March 2000 / Accepted July 2001     

Failure detection and consensus in the crash-recovery model

Summary. We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice – those with no failures or failure detector mistakes. In such runs, consensus is achieved within time and with 4 n messages, where is the maximum message delay and n is the number of processes in the system. Received: May 1998 / Accepted: November 1999     

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