Kenichi KANATANI Sachio TAKEDA
This paper presents a theoretically best algorithm within the framework of our image noise model for reconstructing 3-D from two views when all the feature points are on a planar surface. Pointing out that statistical bias is introduced if the least-squares scheme is used in the presence of image noise, we propose a scheme called renormalization, which automatically removes statistical bias. We also present an optimal correction scheme for canceling the effect of image noise in individual feature points. Finally, we show numerical simulation and confirm the effectiveness of our method.
Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.
In the actual sound environmental systems, it seems to be essentially difficult to exactly evaluate a whole probability distribution form of its response fluctuation, owing to various types of natural, social and human factors. We have reported a unified probability density expression in the standard expansion form of Hermite type orthonormal series taking a well-known Gaussian probability density function (abbr. p.d.f.) as the basis for generally evaluating non-Gaussian, non-linear correlation and/or non-stationary properties of the fluctuation phenomenon. However, in the real sound environment, there still remain many actual problems on the necessity of improving the above standard type probability expression for practical use. First, a central point in this paper is focused on how to find a new probabilistic theory of practically evaluating the variety and complexity of the actual random fluctuations, especially through newly introducing an equvivalence transformation toward the standard type probability expression mentioned above in the expansion form of Hermite type orthonormal series. Then, the effectiveness of the proposed theory has been confirmed experimentally too by applying it to the actual problems on the response probability evaluation of various sound insulation systems in an acoustic room.
Hidetoshi OGIHARA Masaki YOSHIMARU Shunji TAKASE Hiroki KUROGI Hiroyuki TAMURA Akio KITA Hiroshi ONODA Madayoshi INO
The Double-Sided Rugged poly Si (DSR) technology has been developed for high density DRAMs. The DSR technology was achieved using transformation of rugged poly Si caused by ion implantation. The DSR can increase the surface area of the storage electrode, because it has rugged surfaces on both upper and lower sides. The 2-FINs STC (STacked Capacitor cell) with DSR was fabricated in the cell size of 0.72 µm2, and it is confirmed that the DSR can increase the surface area 1.8 times larger than that of smooth poly Si. It is expected that 25 fF/bit is obtained with a 300 nm-thick storage electrode. These effects show that sufficient capacitance for 256 Mb DRAMs is obtained with a low storage electrode. It is confirmed that there is no degradation in C-V and I-V characteristics. Moreover, the DSR needs neither complicated process steps nor special technologies. Therefore, the DSR technology is one of the most suitable methods for 256 Mb DRAMs and beyond.
Vijaya Gopal BANDI Hideki ASAI
A new algorithm, which is incorporated into the waveform relaxation analysis, for efficiently simulating the transient response of single lossy transmission lines or lossy coupled multiconductor transmission lines, terminated with arbitrary networks will be presented. This method exploits the inherent delay present in a transmission line for achieving simulation efficiency equivalent to obtaining converged waveforms with a single iteration by the conventional iterative waveform relaxation approach. To this end we propose 'line delay window partitioning' algorithm in which the simulation interval is divided into sequential windows of duration equal to the transmission line delay. This window scheme enables the computation of the reflected voltage waveforms accurately, ahead of simulation, in each window. It should be noted that the present window partitioning scheme is different from the existing window techniques which are aimed at exploiting the non–uniform convergence in different windows. In contrast, the present window technique is equivalent to achieving uniform convergence in all the windows with a single iteration. In addition our method eliminates the need to simulate the transmission line delay by the application of Branin's classical method of characteristics. Further, we describe a simple and efficient method to compute the attenuated waveforms using a particular form of lumped element model of attenuation function. Simulation examples of both single and coupled lines terminated with linear and nonlinear elements will be presented. Comparison indicates that the present method is several times faster than the previous waveform relaxation method and its accuracy is verified by the circuit simulator PSpice.
Katsumi HARASHIMA Miki YOSHIDA Hironori KOMI Kunio FUKUNAGA
We propose an optimal throughput problem using graph transformations to maximize throughput of a pipelined data path with some loops. The upper bound of the throughput, equals to the lower bound of the iteration interval between the start of two successive iterations, is limited by the length of a critical loop. Therefore we can maximize the throughput by minimizing the length of the critical loop. The proposed method first schedules an initial Data Flow Graph (DFG) under the initial iteration interval as few as it can use resources, then it transforms the DFG into the flow graph with the minimal length of the critical loop by rescheduling the given initial scheduling result. If there are any control steps which violate the resource constraints owing to the transformations, then these operations are adjusted so as to satisfy given resource consrtraints. Finally by rescheduling the transformed DFG, it gives a schedule with maximum throughput. Experiments show the efficiency of our proposed approach.
Toyofumi SAITO Jun-ichiro TORIWAKI
In this paper, we present new algorithms to calculate the reverse distance transformation and to extract the skeleton based upon the Euclidean metric for an arbitrary binary picture. The presented algorithms are applicable to an arbitrary picture in all of n-dimensional spaces (n2) and a digitized picture sampled with the different sampling interval in each coordinate axis. The reconstruction algorithm presented in this paper is resolved to serial one-dimensional operations and efficiently executed by general purpose computer. The memory requirement is very small including only one picture array and single one-dimensional work space array for n-dimensional pictures. We introduce two different definitions of skeletons, both of them allow us to reconstruct the original binary picture exactly, and present algorithms to extract those skeltons from the result of the squared Euclidean distance transformation.
Jong-Il PARK Nobuyuki YAGI Kazumasa ENAMI
This paper describes an image synthesis method based on an estimation of camera parameters. In order to acquire high quality images using image synthesis, we take some constraints into account, which include angle of view, synchronization of change of scale and change of viewing direction. The proposed method is based on an investigation that any camera operation containing a change of scale and a pure 3D rotation can be represented by a 2D geometric transformation. The transformation can explain all the synthesis procedure consisting of locating, synchronizing, and operating images. The procedure is described based on a virtual camera which is constituted of a virtual viewing point and a virtual image plain. The method can be efficiently implemented in such a way that each image to be synthesized undergoes the transformation only one time. The parameters in the image transformation are estimated from image sequence. The estimation scheme consists of first establishing correspondence and then estimating the parameters by fitting the correspondence data to the transformation model. We present experimental results and show the validity of the proposed method.
Shanjun ZHANG Toshio KAWASIMA Yoshinao AOKI
A two-cascaded image processing approach to enhance the subtle differences in X-ray CT image is proposed. In the method, an asymmetrical non-linear subfilter is introduced to reduce the noise inherent in the image while preserving local edges and directional structural information. Then, a subfilter is used to compress the global dynamic range of the image and emphasize the details in the homogeneous regions by performing a modular transformation on local image den-sities. The modular transformation is based on a dynamically defined contrast fator and the histogram distributions of the image. The local contrast factor is described in accordance with Weber's fraction by a two-layer neighborhood system where the relative variances of the medians for eight directions are computed. This method is suitable for low contrast images with wide dynamic ranges. Experiments on X-ray CT images of the head show the validity of the method.
Junichi NAKAYAMA Hiroya MOTOYAMA
This paper gives a systematic approach to generate a Markov chain by a discrete-valued auto-regressive equation, which is a a nonlinear auto-regressive equation having a discrete-valued solution. The power spectrum, the correlation function and the transition probability are explicitly obtained in terms of the discrete-valued auto-regressive equation. Some computer results are illustrated in figures.
Toshiyuki YOSHIDA Akinori NISHIHARA Nobuo FUJII
In multidimensional signal sampling, the orthogonal sampling scheme is the simplest one and is employed in various applications, while a non-orthogonal sampling scheme is its alternative candidate. The latter sampling scheme is used mainly in application where the reduction of the sampling rate is important. In three-dimensional (3-D) signal processing, there are two typical sampling schemes which belong to the non-orthogonal samplings; one is face-centered cubic sampling (FCCS) and the other is body-centered cubic sampling (BCCS). This paper proposes a new design method for 3-D band-limiting FIR filters required for such non-orthogonal sampling schemes. The proposed method employs the McClellan transformation technique. Unlike the usual 3-D McClellan transformation, however, the proposed design method uses 2-D prototype filters and 2-D transformation filters to obtain 3-D FIR filters. First, 3-D general sampling theory is discussed and the two types of typical non-orthogonal sampling schemes, FCCS and BCCS, are explained. Then, the proposed design method of 3-D bandlimiting filters for these sampling schemes is explained and an effective implementation of the designed filters is discussed briefly. Finally, design examples are given and the proposed method is compared with other method to show the effectiveness of our methos.
This paper proposes a second order auto-regressive equation with discrete-valued random coefficients. The auto-regressive equation transforms an independent stochastic sequence into a binary sequence, which is a special case of a stationary Markov chain. The power spectrum, correlation function and the transition probability are explicitly obtained in terms of the random coefficients. Some computer results are illustrated in figures.
Junichi NAKAYAMA Kenichi NAKAMURA Yasuo YOSHIDA
A systematic method is proposed to generate a random image with a known correlation function and the modified Laplace distribution; the modified Laplace distribution includes the one-side exponential distribution and the Laplace distribution as a special case. Several random images with an isotropic correlation and the modified Laplace distribution are generated and displayed in figures.
Mohamed FAKIR Chuichi SODEYAMA
A method for the recognition of Arabic printed scripts entered from an image scanner is presented. The method uses the Hough transformation (HT) to extract features, Dynamic programming (DP) matching technique, and a topological classifier to recognize the characters. A process of characters recognition is further divided into four parts: preprocessing, segmentation of a word into characters, features extraction, and characters identification. The preprocessing consists of the following steps: smoothing to remove noise, baseline drift correction by using HT, and lines separation by making an horizontal projection profile. After preprocessing, Arabic printed words are segmented into characters by analysing the vertical and the horizontal projection profiles using a threshold. The character or stroke obtained from the segmentation process is normalized in size, then thinned to provide it skeleton from which features are extracted. As in the procedure of straight lines detection, a threshold is applied to every cell and those cells whose count is greater than the threshold are selected. The coordinates (R, θ) of the selected cells are the extracted features. Next, characters are classified in two steps: In the first one, the character main body is classified using DP matching technique, and features selected in the HT space. In the second one, simple topological features extracted from the geometry of the stress marks are used by the topological classifier to completely recognize the characters. The topological features used to classify each type of the stress mark are the width, the height, and the number of black pixels of the stress marks. Knowing both the main group of the character body and the type of the stress mark (if any), the character is completely identified.
The embedded Markov processes associated with Markovian queueing systems are closely related, and their relationships are important for establishing an analytical basis for performance evaluation techniques. As a first step, we analyze the embedded processes associated with a general M/M/1 queueing system. Linear transformations between the infinitesimal generators and the transition probability matrices of embedded processes at arrival and departure times are explicitly derived. Based upon these linear transformations, the equilibrium distributions of the system states at arrival and departure times are obtained and expressed in terms of the equilibrium distribution at arbitrary times. The approach presented here uncovers an underlying algebraic structure of M/M/1 queueing systems, and establishes an algebraic methodology for analyzing the equilibrium probabilities of the system states at arrival and departure times for more general Markovian queueing systems.
This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.
This paper first discusses the software reusability-based development process in a lifecycle and reusable objects modification process called differentiation. Next, the supporting environment is described. Both the method and the environment allow developers to carry out requirement definitions, specification and implementation in a reusable way. Some quantitative evaluations are given about how productivity and quality have been improved by using this method and environment, based on a number of case studies made on development projects. Reusability has been largely improved by differential specification, and adjustment method and a direct transformation capability.
Norihiro YOSHIDA Suthichai NOPPANAKEEPONG Osamu HIROTA Shigeo TSUJII
In this letter, it is clarified that the quantum noise properties of the linear amplification and locking amplification in the injection locked laser process are different. The noise property of the locking amplification is newly given.
Kiyoshi NISHIKAWA Russell M. MERSEREAU
We present a successful method for designing 2-D circularly symmetric R lowpass filters with constant group delay. The procedure is based on a transformation of a 1-D prototype R filter with constant group delay, whose magnitude response is the 2-D cross-sectional response. The 2-D filter transfer function has a separable denominator and a numerator which is obtained from the prototype numerator by means of a series of McClellan transformations whose free parameters can be optimized by successive procedure. The method is illustrated by an example.
WANG Guo-Hua Kenzo WATANABE Yutaka FUKUI
A dual transformation incorporating the frequency-dependent scaling factor with the impedance dimension is proposed to synthesize the current-mode counterpart of a voltage-mode original. A general class of current-mode active-RC biquadratic filters and a switched-capacitor low-pass biquad are derived to demonstrate the synthesis procedure. Their simulation and test results show that the current transfer functions are the same as the voltage transfer functions of the originals, and thus confirm the validity of the procedure. The dual trasformation described herein is general in that with the scaling factor chosen appropriately it can meet a wide variety of circuit transformation, and thus useful also for circuit classification and identification.