Table-form document structure analysis is an important problem in the document processing domain. This paper presents a new method called Box-Driven Reasoning (BDR) to robustly analyze the structure of table-form documents that include touching characters and broken lines. Real documents are copied repeatedly and overlaid with printed data, resulting in characters that touch cells and lines that are broken. Most previous methods employ a line-oriented approach, but touching characters and broken lines make the procedure fail at an early stage. BDR deals with regions directly in contrast with other previous methods and a reduced resolution image is introduced to supplement information deteriorated by noise. Experimental tests show that BDR reliably recognizes cells and strings in document images with touching characters and broken lines.
Akira WATANABE Yuuji KOUI Shoichiro SENO Tetsuo IDEGUCHI
We propose an architecture of a high-speed internetworking device using central control method. Co-operations of hardware and software is required to realize high relay performance. For the hardware, we have designed an original bus arbitration control method to achieve a high throughput of a data bus. For the software, we have devided a normal relay processing from other processing and built it as a basic function of the monitor. By this method, relay perfomance improves dramatically, because of a multiple effect of the reduction of software overheads and the improvement of cache hit ratio. We have developed the prototype device and confirmed the effects of the proposed method.
Hiromi BABA Tsukasa NOMA Naoyuki OKADA
This paper discusses visualization of temporal and spatial information in natural language descriptions (NLDs), focusing on the translation process of intermediate representations of NLDs to proper scenarios" and environments" for animations. First, the intermediate representations are shown according to the idea of actors. Actors and non-actors are represented as primitives of objects, whereas actions as those of events. Temporal and spatial constraints by a given NLD text are imposed upon the primitives. Then, the representations containing unknown temporal or spatial parameters --time and coordinates-- are translated into evaluation functions, where the unlikelihood of the deviations from the predicted temporal or spatial relations are estimated. Particularly, the functions concerning actor's movements contain both temporal and spatial parameters. Next, the sum of all the evaluation functions is minimized by a nonlinear optimization method. Thus, the most proper actors' time-table, or scenario, and non-actors' location-table, or environment, for visualization are obtained. Implementation and experiments show that both temporal and spatial information in NLDs are well connected through actors' movements for visualization.
Shunji MORI Yu NAKAJIMA Hirobumi NISHIDA
There are many instances in which character shape of a class changes smoothly to that of another class. Although there are many ways of the change, the most delicate change is curvature feature. The paper treat this problem systematically in both theoretically and experimentally. Specifically some confusing pairs were constructed which are well known in the field of OCR, such as 2 Z and 4 9. A series of samples generated using each model which change subtly were provided to conduct a psychological experiment. The results exhibit a monotone change of recognition rates from nearly 100% to 0% as the shape changes continuously. To imitate the humans' performance, feature of curvature was extracted based on continuous function representation based on Bezier's spline curve. Specifically two methods were tried from theoretical and engineering points of view and very successful results were obtained.
The mean field theory has been recognized as offering an efficient computational framework in solving discrete optimization problems by neural networks. This paper gives a formulation based on the information geometry to the mean field theory, and makes clear from the information-theoretic point of view the meaning of the mean field theory as a method of approximating a given probability distribution. The geometrical interpretation of the phase transition observed in the mean field annealing is shown on the basis of this formulation. The discussion of the standard mean field theory is extended to introduce a more general computational framework, which we call the generalized mean field theory.
Toshiyuki YOSHIDA Todor COOKLEV Akinori NISHIHARA Nobuo FUJII
This paper proposes a design technique for 3-D non-separable QMF banks with Face-Centered Cubic Sampling (FCCS) and Body-Centered Cubic Sampling (BCCS). In the proposed technique, 2-D McClellan transformation is applied to a suitably designed 2-D prototype QMF to obtain 3-D QMFs. The design examples given in this paper demonstrate advantages of the proposed method.
Kari H. A. KARKKAINEN Pentti A. LEPPANEN
It is demonstrated with the Berlekamp-Massey shift-register synthesis algorithm that the linear complexity value of binary complementary sequences is at least 3/4 of the sequence length. For some sequence pairs the linear complexity value can be even 0.98 times the sequence length. In the light of these results strongly non-linear complementary sequences are considered suitable for information security applications employing the spread-spectrum (SS) technique.
Yoshimichi WATANABE Takehiro TOKUDA
We present two efficient attribute evaluator construction methods for a wide subclass of L-attributed grammars by enumeration of attributed items during one-pass bottom-up parsing. We have already proposed a construction method of a parser/evaluator for the subclass of L-attributed grammar. However the evaluator produced by our previous method uses a great number of attributed items to evaluate all attributes of a given input string. In this paper we propose two generalized methods to reduce the number of attributed itmes used in attribute evaluation. Our methods allow us to evaluate all attributes taking advantage of the use of available lookahead information.
Masaki KUMANOYA Toshiyuki OGAWA Yasuhiro KONISHI Katsumi DOSAKA Kazuhiro SHIMOTORI
Various kinds of new architectures have been proposed to enhance operating performance of the DRAM. This paper reviews these architectures including EDO, SDRAM, RDRAM, EDRAM, and CDRAM. The EDO slightly modifies the output control of the conventional DRAM architecture. Other innovative architectures try to enhance the performance by taking advantage of DRAM's internal multiple bits architecture with internal pipeline, parallel-serial conversion, or static buffers/on-chip cache. A quantitative analysis based on an assumption of wait cycles was made to compare PC system performance with some architectures. The calculation indicated the effectiveness of external or on-chip cache. Future trends cover high-speed I/O interface, unified memory architecture, and system integrated memory. The interface includes limited I/O swing such as HSTL and SSTL to realize more than 100MHz operation. Also, Ramlink and SyncLink are briefly reviewed as candidates for next generation interface. Unified memory architecture attempts to save total memory capacity by combining graphics and main memory. Advanced device technology enables system integration which combine system logic and memory. It suggests one potential direction towards system on a chip in the future.
Hiroshi KONDO Shuji TUTUMI Satoshi MIKURIYA
A simple and convenient approach for a radial symmetrical point detection is proposed. In this paper the real part-only synthesis is utilized in order to make an origin symmetric pattern of the original image and to perform automatically the calculation of its autocorrelation for the detection of the symmetry center of the image.
Jonghyun LEE Inhwan JUNG Songchun MOON
Recently, a number of concurrency control algorithms have been proposed for multidatabase system (MDBS) concurrency control methods (CCMs) and the most challenging issue of them has been a concern about how to ensure global serializability (GSR). In this paper, we examine two concurrency control algorithms of MDBS through simulation approach: optimistic ticket method (OTM) and global ticket method (GTM). In historical note, OTM is known to be the first practical solution, since this approach ensures GSR by way of automatically resolving indirect conflicts among global transactions without making any restrictions on local CCMs. However, OTM is expected to yield poor performance since it enforces all global transactions to take a local ticket which causes direct conflicts between them. In GTM, the global transaction manager in an MDBS assigns a global ticket to global transactions rather than accessing a local ticket as in OTM. Our experimental results showed that GTM outperforms OTM in cases that short timeout values are given. However, in case that the timeout value relatively becomes long, our results demonstrated that OTM outperforms GTM.
Masamitsu TOKUDA Ryoichi OKAYASU Yoshiharu AKIYAMA Kusuo TAKAGI Fujio AMEMIYA
Based on the test method proposed by Sub-Committee G of the International Special Committee on Radio Interference, most telephone receivers in Japan have insufficient immunity to acoustic noise caused by radio-frequency fields. This is because the modulation depth of the RF signal used is too high to accurately simulate the audio-frequency components of TV video signals. Reducing the modulation depth from 80% to 5% produces a more realistic simulation.
Arata KOIKE Hideo KITAZUME Hiroshi SAITO Mika ISHIZUKA
This paper investigates Available Bit Rate (ABR) traffic control based on the Explicit Forward Congestion Indication (EFCI). A flow control mechanism is specified for ABR service to control the source rate. Resource Management (RM) cells are used to convey feedback. A source sends a forward RM cell for at least every N cells sent. At the destination, a forward RM cell turns around as a backward RM cell and returns to the source. A data cell has EFCI-bit in its header field. A network element sets EFCI-bit if it is congested. A destination indicates congestion status of networks by using RM cells based on the value of the EFCI-bit of the data cells. A one-bit feedback scheme is used by the ATM Forum. However, indication schemes have also been proposed which use explicit indication of source rate based both on values of the EFCI-bit of data cells and on other information contained in a forward RM cell. We evaluated explicit indication schemes as well as a one-bit scheme by simulation. Simulation study showed explicit cell rate indication gives superior performance than one-bit indication especially for long round trip distances. In this paper, we report the results with brief discussion.
Yukihiro HAMADA Feng BAO Aohan MEI Yoshihide IGARASHI
A directed graph G = (V,E) is called the n-rotator graph if V = {a1a2
This paper proposes a tool to analyze complicated phenomena from a simple hysteresis network. The simple hysteresis network is described by a piecewise liner ordinal differential equation and has only two parameters: self feedback and DC team. Then this simple system exhibits various kinds of attractors: stable equilibria, periodic orbits, tori and chaos. In order to perform the numerical analysis, we derive return map and propose a fast calculation algorithm for the return map and its Lyapunov exponents based on the exact solutions. Using this algorithm, we have clarified chaos generation and related bifurcation phenomena. Also, we give theoretical formula that give fundamental bifurcation set.
Yukiko ITO Hajime OGAWA Hiromichi TANI
A new cost model CPO (Cost of Process Ownership) has been proposed. We have already the well known cost model CEO (Cost of Equipment Ownership) [1] which is a cost index assigned independently to individual equipment. However, CPO is basically a cost index assigned to process step in processing flow chart of actual product in a Fab line. Therefore, it is essentially more effective to evaluate the Fab performance such as cost analysis of process steps, estimation of the whole wafer processing cost for specific product, identification of the bottle neck process step or equipment in a Fab line. Further, in designing a high cost-performance factory or in modifying existing factory, it affords important guide such as optimal scales for both factory and equipments with their investment efficiency.
Hisao OIKAWA Takao YAMAZAKI Hidetoshi KIMURA
Estimating the macroscopic demand for telephones is essential to long-term planning construction of telecommunication networks facilities. Although there are several useful forecast equations, they need some types and/or vast amounts of data that are sometimes unavailable, especially in developing countries. This paper presents a sophisticated telephone demand estimation technique that is based on the demands of residential and business users. It uses several parameters to estimate the increase in telephone demand. A simplified equation is also presented that is a function of only one parameter: normalized gross domestic product (GDP) per capita. This simplified equation is shown to be useful by using data for more than ten countries.
Nguyen Ngoc BINH Masaharu IMAI Akichika SHIOMI Nobuyuki HIKICHI
This paper proposes a new method to design an optimal pipelined instructions set processor for ASIP development using a formal HW/SW codesign methodology. First, a HW/SW partioning algorithm for selecting an optimal pipelined architecture is outlined. Then, an adaptive detabase approach is presented that enables to enhance the optimality of the design through very accurate estimation of the performance of a pipelined ASIP in the HW/SW partitioning process. The experimental results show that the proposed method is effective and efficient.
Yasuyuki SHIRAI Masaki NARAZAKI Tadahiro OHMI
We have developed a complete chromium oxide (Cr2O3) passivated gas tubing system by introducing ferritic stainless steel instead of conventional austenitic stainless steel (SUS316L). 100% Cr2O3 passivation film can be formed on electropolished ferritic stainless steel surface because the diffusion coefficient of Cr in ferritic stainless steel is 104 times larger than in austenitic stainless steel. In ferritic stainless steel, moreover, welded bead surface is covered by 100% Cr2O3 pas-sivated film by an introduction of advanced welding technology.
Nozomu TOGAWA Masao SATO Tatsuo OHTSUKI
In this paper, we propose a new FPGA design algorithm, Maple-opt, in which technology mapping, placement, and global routing are executed so that the delay of each critical signal path in an input circuit is within a specified upper bound imposed on it. The basic algorithm of Maple-opt is top-down hi-erarchical bi-partitioning of regions. Technology mapping onto logic-blocks of FPGAs, their placement, and global routing are determined simulatenously in each hierarchical process. This simultaneity leads to less congested layout for routing. In addition to that, Maple-opt computes a lower bound of delay for each path with a constraint value and determines critical paths based on the difference between the lower bound and the constraint value dynamically in each hierarchical process. Two delay reduction processes are executed for the critical paths; one is routing delay reduction and the other is logic-block delay reduction. Routing delay reduction is realized such that, when bi-partitioning a region, each constrained path is assigned to one subregion. Logic-block delay reduction is realized such that each constrained path is mapped onto fewer logic-blocks. Experimental results for some benchmark circuits show its efficiency and effectiveness.