In this paper, symbols and numerals in topographic maps are recognized by the multi-angled parallelism (MAP) matching method, and small dots and lines are extracted by the MAP operation method. These results are then combined to determine the value, position, and attributes of elevation marks. Also, we reconstruct three dimensional surfaces described by contours, which is difficult even for humans since the elevation symbols are sparse. In reconstruction of the surface, we define an energy function that enfores three constraints: smoothness, fit, and contour. This energy function is minimized by solving a large linear system of simultaneous equations. We describe experiments on 25,000:1 scale topographic maps of the Tsukuba area.

This paper discusses the role of knowledge in document image understanding from the viewpoints of representation, utilization and acquisition. For the representation of knowledge, we propose two models, a layout model and a content model, which represent knowledge about the layout structure and content of a document, respectively. For the utilization of knowledge, we implement layout analysis and content analysis which utilize a layout model and a content model, respectively. The strategy of hypothesis generation and verification is introduced in order to integrate these two kinds of analysis. For the acquisition of knowledge, we propose a method of incremental acquisition of a layout model from a stream of example documents. From the experimental results of document image understanding and knowledge acquisition using 50 samples of visiting cards, we verified the effectiveness of the proposed method.

We apply neural networks to implement a line shape recognition/classification system. The purpose of employing neural networks is to eliminate target-specific algorithms from the system and to simplify the system. The system needs only to be trained by samples. The shapes are captured by the following operations. Lines to be processed are segmented at inflection points. Each segment is extended from both ends of it in a certain percentage. The shape of each extended segment is captured as an approximate curvature. Curvature sequence is normalized by size in order to get a scale-invariant measure. Feeding this normalized curvature date to a neural network leads to position-, rotation-, and scale-invariant line shape recognition. According to our experiments, almost 100% recognition rates are achieved against 5% random modification and 50%-200% scaling. The experimental results show that our method is effective. In addition, since this method captures shape locally, partial lines (caused by overlapping etc.) can also be recognized.

In this letter, we compare the three compound methods of the Multiple-scale technique to improve the quality of the scale values estimated by the method of fuzzy categories. The results show that the maximum compound method brings higher ability to estimate the scale values than the other methods despite categories used in the scale.

The issue about document structure recognition and document understanding is today one of interesting subjects from a viewpoint of practical applications. The research objective is to extract the meaningful data from document images interpretatively and also classify them as the predefined item data automatically. In comparison with the traditional image-processing-based approaches, the knowledge-based approaches, which make use of various knowledge in order to interpret structural/constructive features of documents, have been currently investigated as more flexible and applicable methods. In this paper, we propose a totally integrated paradigm for understanding table-form documents from a viewpoint of the architectural framework.

A system for segmentation of document image and ordering text areas is described, and applied to complex printed page layouts of both Japanese and English. There is no need to make any assumptions about the shape of blocks, hence the segmentation technique can handle not only skewed images without skew-correction but also documents where columns are not rectangular. In this technique, based on the bottom-up strategy, the connected components are extracted from the reduced image, and classiferd according to their local information. The connected components calssified as characters are then merged into lines, and the lines are merged into areas. Extracted text areas are classified as body, caption, header or footer. A tree graph of the layout of the body texts is made, and the texts ordered by preorder traversal on the graph. We introduce the concept of an influence range of each node, a procedure for handling titles, thus obtaining good results on various documents. The total system is fast and compact.

This paper presents an overview of the SDC-I (Super Database Computer I) developed at the University of Tokyo, Japan. The purpose of the project was to build a high performance SQL server which emphasizes query processing over transaction processing. Recently relational database systems tend to be used for heavy decision support queries, which include many join, aggregation, and order-by operations. At present high-end mainframes are used for these applications requiring several hours in some cases. While the system architecture for high traffic transaction processing systems is well established, that for adhoc query processing has not yet adequately understood. SDC-I proved that a parallel machine could attain significant performance improvements over a coventional sequential machine through the exploitation of the high degree of parallelism present in relational query processing. A unique bucket spreading parallel hash join algorithm is employed in SDC, which makes the system very robust in the presense of data skew and allows SDC to attain almost linear performance scalability. SDC adopts a hybrid parallel architecture, where globally it is a shared nothing architecture, that is, modules are connected through the multistage network, but each module itself is a symmetric multiprocessor system. Although most of the hardware elements use commodity microprocessors for improved performance to cost, only the interconnection network incorporates the special function to support our parallel relational algorithm. Data movement over the memory and the network, rather than computation, is heavy for I/O intensive database processing. A dedicated software system was carefully designed for efficient data movement. The implemented prototype consists of two modules. Its hardware and software organization is described. The performance monitoring tool was developed to visualize the system activities, which showed that SDC-I works very efficiently.

A method for extracting and recognizing character strings from unformed document images, which have inclined character strings and have no structure at all, is described. To process such kinds of unformed documents, previous schemes, which are intended only to deal with documents containing nothing but horizontal or vertical strings of characters, do not work well. Our method is based on the idea that the processes of recognition and extraction of character patterns should operate together, and on the characteristic that the character patterns are located close to each other when they belong to the same string. The method has been implemented and applied to several images. The experimental results show the robustness of our method.

This paper proposes a request-grant-type multiple access control called bandwidth-request labeled-slot multiple access (BLMA) for wireless LANs. BLMA employs slotted ALOHA in the request stage and has an algorithm to avoid unfair access due to the capture effect in this stage. In BLMA, terminals transmit data using fixed length slots called fragment slots in the transmission stage. The base station assigns the fragment slots one by one to terminals for peer-to-peer communication in which terminals communicate directly. It also controls the retransmission based on the stop and wait automatic repeat request scheme. The base station retransmits data for the source terminal as much as it can. BLMA provides simple and fair access control, efficient link utilization, and easy implementation. It also allows modes to be easily changed automatically from peer-to-peer communication to store-and-forward communication in which terminals communicate via the base station. Design concepts of a wireless MAC discussed and details of BLMA are described. The evaluation results of the BLMA are also shown.

In digital control, it is essential to make the delay time for a large number of multiply-additions small because of sensor feedback. To meet the requirement, an architecture of the reconfigurable parallel processor using field-programmable gate arrays (FPGAs) is proposed. Although the performance is drastically increased in the full custom VLSI implementation, even the reconfigurable parallel processor using FPGAs becomes useful for many practical digital control applications. The performance evaluation shows that the delay time for the resolved acceleration cotrol computation of a twelve-degrees-of-freedom (DOF) redundant manipulator becomes about 70 µs which is about seventeen times faster than that of a parallel processor approach using conventional digital signal processors (DSPs).

This paper presents an algorithm for string searching in a character lattice. A character lattice, which is obtained through a character recognition process, is a general and flexible data structure that represents many hypothesized strings in a document image. In this paper, the authors propose a simple and efficient algorithm; it consists of a single loop of some set-operations and scans the character lattice only once. The authors also describe two actual implementations of the algorithm; one uses Bit-Arrays and the other a Trie. Owing to its bir parallelism, the Bit-Array approach is able to search for a single pattern faster than the Trie approach, and is easily extended to complex matchings such as an approximate one. It is suited for document retrieval systems that need to search for a keyword as fast as possible. A hashed compact version of the character lattice is also useful to increase the speed of the search for a single pattern. In contrast, the Trie approach is able to search for a large number of patterns simultaneously, and is suited for document understanding systems that need to extract words from the character lattice. The experimental results have shown that both approaches achieve high performance.

The present study describes using the state transition type of drawing understanding framework to construct a multi-purpose drawing understanding system. This new system employs an understanding process that complies with the understanding rules, which are easily obtained by the user. The same set of user-provided rules must be used for the same type of target drawings, but for slightly different ones, fine tuning is required to obtain understanding rules. To overcome this inherent drawback in constructing drawing understanding systems, we extended the system using a newly constructed understanding rule generating support system. The resultant integrated system is based on a man-machine cooperation type interface, and can automatically generate rules from user-provided simple interactions using a graphical user interace (GUI). To obtain efficient rule generation, the system employs an inductive inference method as a learning algorithm. Map-drawing experiments were successfully carried out, and an evaluation based on a rule leaning error criterion subsequently revealed an efficient rule generation process.

It is demonstrated that the enhancement in the functional capability of an elemental transistor is quite essential in developing human-like intelligent electronic systems. For this purpose we have introduced the concept of four-terminal devices. Four-terminal devices have an additional dimension in the degree of freedom in controlling currents as compared to the three-terminal devices like bipolar and MOS transistors. The importance of the four-terminal device concept is demonstrated taking the neuron MOS transistor (abbreviated as neuMOS or νMOS) and its circuit applications as examples. We have found that any Boolean functin can be realized by a two-stage configuratin of νMOS inverters. In addition, the variable threshold nature of the device allows us to build real-time reconfigurable logic circuits (no floating gate charging effect is involved in varying the threshold). Based on the principle, we have developed Soft-Hardware Logic Circuits and Real-Time Rule-Variable Data Matching Circuits. A winner-take-all circuit which finds the largest signal by hardware parallel processing has been also developed. The circuit is applied to building an associative memory which is different from Hopfield network in both principle and operation. The hardware algorithm in which binary, multivalue, and analog operations are merged at a very device level is quite essential to establish intelligent information processing systems based on highly flexible, real-time programmable hardwares realized by four-terminal devices.

In direct connection with the signal information processing, a practical method of identification and probabilistic prediction for sound insulation systems is theoretically proposed in the object-oriented expression forms by introducing a few functional system parameters. Concretely, a trial of identification of the above functional system parameters and the output probabilistic prediction for a panel thickness change of double-wall type sound insulation system, especially, under the existence of a strong background noise inside of the reception room, is newly proposed based on one of wide sense digital filters and SEA (Statistical Energy Analysis) method. Finally, by using the actual music sound of an arbitrary distribution type, the effectiveness of the proposad method is confirmed experimentally by applying it to some problems of predicting the cumulative probability distribution of the transmitted sound level fluctuation.

An adaptive LMS filtering system is proposed for computing the Discrete Walsh Transform (DWT). The signal to be transformed serves as the 'desired signal' for the adaptive filter, while a set of periodic Walsh sequences serve as the input signal vector for the adaptive filter. The weights of the adaptive filter provide the DWT. The given approach is more efficient in terms of the required computations and memory locations compared with the direct approach. In contract with existing Fast DWT algorithm, the proposed solution provides more flexibility as far as the signal block length is concerned. In other words, the proposed approach is not restricted to a block length N to be of power 2.

A fast Newton/LMS algorithm is proposed which uses an efficient inversion technique of input autocorrelation matrix when the periodic pseudo random sequence is used as the reference signal. The number of operations is greatly reduced and the computational results show fast convergence rate and low misadjustment error. And the application of the algorithm to the case of nonperiodic reference signal is described.

In intelligent integrated systems such as robotics for autonomous work, it is essential to respond to the change of the environment very quickly. Therefore, the development of special-purpose VLSI processors for intelligent integrated systems with small latency becomes an very important subject. In this paper, we present a scheduling algorithm for high-level synthesis. The input to the scheduler is a behavioral description which is viewed as a data flow graph (DFG). The scheduler minimizes the latency, which is the delay of the critical path in the DFG, and minimizes the number of functional units and buses by improving the utilization rates. By using an integer linear programming, the scheduler optimally assigns nodes and arcs in the DFG into steps.

This paper presents a discrete Fourier analyzer using analog VLSI technology. An analog current-mode technique is employed for implementing it by a regular array structure based on the straight-forward discrete Fourier transform (DFT) algorithm. The basic components are 1-dimensional (1-D) analog current-mode multiplier array for fixed coefficient multiplication, two-dimensional (2-D) analog switch array and wired summations. The proposed scheme can process speedily N-point DFT in a time proportional to N. Possibility of the realization of the analog DFT VLSI based on 1 µm technology is discussed from the viewpoints of precision, speed, area, and power dissipation. In the case of 1024-point DFT, the standard deviation of the total error is estimated to be about 2%, the latency, or processing time is about 110 µs, and the signal sample rate based on a pipeline manner is about 4.7 MHz. A prototype MOS integrated circuit of the 16-point multiplier array has been implemented and a typical operation using the multiplier array has been confirmed.

A feedback pattern recognition method using an inverse recall neural network model is proposed. The feedback method can adjust processing parameter values adaptively to individual patterns so as to produce reliable recognition results. In order to apply an adaptive control technique to such pattern recognition processings, the evaluation value for recognition uncertainty is determined to be a function with regard to an input pattern and processing parameters. In its feedback phase, the input pattern is fixed and processing parameters are adjusted to decrease the recognition uncertainty. The proposed neural network model implements two functions in this feedback recognition method. One is a discrimination as a kind of multi-layer feedforward model. The other is to generate an input modification so as to decrease the recognition uncertainty. The modification values indicate parts which are important for more certain recognition but are missed in the original input to the nerwork. The proposed feedback method can adjust prcessing parameter values in order to detect the important parts shown by the inverse recall network model. As explained in this paper, feature extraction parameter values are adaptively adjusted by this feedback method. After the inverse recall model and the feedback function are implemented, features are extracted again by using the modified feature extraction parameter values. The feature is classified by the feedforward function of the network model. The feedforward and feedback processings are repeated until a certain recognition result is obtained. This method was examined for hadwritten alpha-numerics with rotation distortion. The feedback method was found to decrease the rejection ratio at the same substitution error ratio with high efficiency.

This paper proposes a group demodulator that employs multi-symbol chirp Fourier transform to demodulate pulse shaped and time asynchronous signals without degradation; this is not possible with conventional group demodulators based on chirp Fourier transform. Computer simulation results show that the bit error rate degradation of the proposed group demodulator at BER=10-3 is less than 0.3dB even when a root Nyquist (α=0.5) filter is used as the transmission pulse shaping filter and the symbol timing offset between the desired channel and the chirp sweep is half the symbol period.