This paper presents a modified disparity measurement to recover the depth and a robust method to estimate motion parameters. First, this paper considers phase correspondence for the computation of disparity. It has less computation for disparity than previous methods that use the disparity from correspondence and from correlation. This modified disparity measurement uses the Gabor filter to analyze the local phase property and the exponential filter to analyze the global phase property. These two phases are added to make quasi-linear phases of the stereo image channels which are used for the stereo disparity finding and the structure recovery of scene. Then, we use feature-based correspondence to find the corresponding feature points in temporal image pair. Finally, we combine the depth map and use disparity motion stereo to estimate 3-D motion parameters.

In general, message passing multiprocessors suffer from communication overhead and shared memory multiprocessors suffer from memory contention. Also, data I/O overhead limits performance. In particular, computer vision tasks that require massive computation are strongly affected by these disadvantages. This paper proposes new parallel architectures for computer vision, a Flexibly (Tightly/Loosely) Coupled Multiprocessor (FCM) and a Flexibly Coupled Hypercube Multiprocessor (FCHM) to alleviate these problems. FCM and FCHM have a variable address space memory in which a set of neighboring memory modules can be merged into a shared memory by a dynamically partitionable topology. FCM and FCHM are based on two different topologies: reconfigurable bus and hypercube. The proposed architectures are quantitatively analyzed using computational models and parallel vision algorithms are simulated on FCM and FCHM using the Intel's Personal SuperComputer (iPSC), a hypercube multiprocessor, showing significant performance improvements over that of iPSC.

A particle trajectory estimation method from far electromagnetic fields are discussed in this paper. Authors have already presented a trajectory estimation method for single particle system and good agreements between a source particle trajectory and an estimated one have been obtained. For this, this paper discusses twin particles system as an examples of multi-particles systems for simplicity. First of all, it is pointed out that far electromagnetic fields from the twin particles system show quite different aspect from the single particle system using an example, radiation patterns produced by two particles which carry out circular motion. This result tells us that any trajectory estimations for general multi-particles system are almost impossible. However, it is shown that when the distance between the particles is small, the estimation method for the single particle system can be applied to the twin particles system, and that twin particles effects appear as disturbance of estimated trajectory.

In this paper, we propose the architecture of BALANCE (Better Adaptive Load-balancing through Acquiring kNowledge of Characteristic of an Environment) in which users can submit their jobs without acquiring either a status of an environment or characteristics of jobs and servers even in a widely connected heterogeneous network. The architecture of BALANCE includes three types of information bases and two types of daemons. Information bases, namely job, resource, and environment information base, manage the knowledge of job characteristics, available resources for CPUs, and status of the environment, respectively, as a proxy for users. The dispatching daemon selects an adequate server for each job using knowledge stored in the information bases. A service daemon executes each job. On completing each job, a service daemon gets a statistic of the job and returns it to the dispatching daemon where the job came from so that the statistic will be available at the next dispatching time. BALANCE enables an environment (1) to balance the load, (2) to share software functions as well as hardware facilities, and (3) to learn a user's job characteristics. We have implemented a prototype with more than 50 heterogeneous UNIX workstations connected by different networks. Two simple experiments on this prototype are presented. These experiments show a load balancing scheme that takes the characteristics of each job into account.

This paper describes a procedural detailed compaction method for the symbolic layout design of CMOS leaf cells and its algorithmic aspects. Simple symbolic representations that are loosely designed by users in advance are automatically converted into densely compacted physical patterns in two phases: symbolic–to–pattern conversion and segment–based detailed compaction. Both phases are executed using user-defined procedures and a specified set of design rules. The detailed compaction utilizes a segment–based constraint graph generated by an extended plane sweep method where various kinds of design rules can be applied. Since various kinds of basic operations can be applied to the individual segments of patterns in the procedures, the detailed procedure for processing can be described in accordance with fabrication process technologies and the corresponding sets of design rules. This combined stepwise procedure provides a highly flexible framework for the symbolic layout of CMOS leaf cells. The proposed approach was implemented in a symbolic layout system called CAMEL. To date, more than 300 kinds of symbolic representations of CMOS leaf cells have been designed and are stored in the database. Using several different sets of design rules, symbolic representations have been automatically converted into compacted patterns without design rule violations. The areas of those generated patterns were averaged at 98% of the manually designed patterns. Even in the worst case, the increases in area were less than about 10% of the manually designed ones. Furthermore, since processing times are much shorter than manual design periods, for example, 300 kinds of symbolic representations can be converted to corresponding physical patterns in only a day. It is evident, through these practical design experiences with CAMEL, that our approach is more flexible and process–tolerant than conventional ones.

The propagation characteristics of dielectric waveguides with slanted grating structure are analyzed by using the combination of the improved Fourier series expansion method and the approximated multilayer method. The slanted grating region is appoximated by a structure with stratified thin modulated index layers. This method is effective to the guiding problems of the planar slanted grating, because the electromagnetic fields in each layer can be expressed by shifting the phase of the solution in the first layer. In this paper, numerical results are given for the grating with the rectangular and the sinusoidal profile for arbitrary slant angle. The radiation efficiencies for the grating with negative and positive slant angle are also discussed.

In this paper, the power dissipation issue is considered in the gate sizing procedure. In order to observe the tradeoff among area, delar and power dissipation in a circuit, gate sizing algorithms which can minimize power under delay constraints or minimize area under power and delay constraints are formulated. Experiments are performed to investigate the properties of area–power–delay tradeoff in the gate sizing procedure.

The warp model of the extended Hough transform (EHT) has been proposed to design the explicit expression of the transform function of EHT. The warp model is a skewed parameter space (R(µ,ξ), φ(µ,ξ)) of the space (µ,ξ), which is homeomorphic to the original (ρ,θ) parameter space. We note that the introduction of the skewness of the parameter space defines the angular and positional sensitivity characteristics required in the detection of lines from the pattern space. With the intent of contributing some solutions to basic computer vision problems, we present theoretically a dynamic and centralfine/peripheral-coarse camera vision architecture by means of this warp model of Hough transform. We call this camera vision architecture askant vision' from an analogy to the human askant glance. In this paper, an outline of the EHT is briefly shown by giving three functional conditions to ensure the homeomorphic relation between (µ,ξ) and (ρ,θ) parameter spaces. After an interpretation of the warp model is presented, a procedure to provide the transform function and a central-coarse/peripheralfine Hough transform function are introduced. Then in order to realize a dynamic control mechanism, it is proposed that shifting of the origin of the pattern space leads to sinusoidal modification of the Hough parameter space.

Numerical studies of reaction–diffusion systems which consist of chaotic oscillators are carried out. The Rössler oscillators are used, which are arranged two–dimensionally and coupled by diffusion. Pacemakers where the average periods of the oscillators are artificially changed are set to produce target patterns. It is found that target patterns emerge from pacemakers and grow up as if they were in a regular oscillatory medium. The wavelength of the pattern can be varied and controlled by changing the parameters (size and frequency) of the pacemaker. The behavior of the coupled system depends on the size of the system and the strength of the pacemaker. When the system size is large, the Poincar return maps show that the behavior of the coupled system is not simple and the orbit falls into a high–dimensional attractor, while for a small system the attractor is rather simple and a one–dimensional map is obtained. Moreover, for appropriate strength of pacemakers and for certain sizes of the systems the oscillations become periodic. It is also found that the largest and local Lyapunov exponents of the system are positive and these values are uniformly distributed over the pattern. The values of the exponents are smaller than that of the uncoupled Rössler oscillator; this is due to the fact that the diffusion reduces the exponents and modifies the form of the attractor. We conclude that the large scale patterns can stably exist in the chaotic medium.

In the conventional protocol synthesis, it is generally assumed that primitives in service specifications cannot be executed simultaneously at different Service Access Points (SAPs). Thus if some primitives are executed concurrently, then protocol errors of unspecified receptions occur. In this paper, we try to extend a class of service specifications from which protocol specifications are synthesized by the previous methods. We first introduce priorities into primitives in protocol specification so that it always selects exactly one primitive of the highest priority from a set of primitives that can be executed simultaneously, and executes it. Then, based on this execution ordering, we propose a new protocol synthesis method which can avoid protocol errors due to message collisions, communication competitions and so on. By applying the proposed synthesis method, we can automatically synthesize a protocol specifications from a given service specification which includes an arbitraty number of processes and allows parallel execution of primitives.

Given a sorted set S of n points in the plane, the prefix convex hulls problem of S is to compute the convex hull for every prefix set of S. We present a parallel algorithm for this problem. Our algorithm runs in O(logn) time using n/logn processors in the CREW PRAM computational model. The algorithm is shown to be time and cost optimal. One of the techniques we adopt to achieve these optimal bounds is the use of a new parallel data structure Array-Tree.

In a distributed system, the protocol entities must exchange some data values and synchronization messages in order to ensure the temporal ordering of the events described in a service specification for the distributed system. It is desirable that a correct protocol specification can be derived automatically from a given service specification. In this paper, we propose an algorithm which synthesizes automatically a correct protocol specification from a service specification described as a Marked Graph with Registers (MGR) model and resources (registers and gates) allocation information. This model has a finite control modeled as a marked graph. Therefore, parallel events can be described. In our method, to minimize the number of the exchanged messages, we use a procedure to calculate an optimum solution for 0-1 integer linear programming problems. The number of the steps which each protocol entity needs to simulate one transition in the service specification is also minimized. Ways to avoiding conflict of registers are also described. Our approach has the following advantages. First, parallel events can be described in a service specification. Secondly, many practical systems can be described in the MGR model. Finally, at the protocol specification level, we can understand what events can be executed in parallel.

Creating a bandwidth abundant B-ISDN requires the further development of path technologies. Optical path cross-connect nodes (OXCs) will be required that offer very high levels of expandability. The present limited traffic demands must be efficiently supported while permitting easy step-wise expansion in capacity. This paper proposes two OXC architectures that offer high modularity with regard to incoming/outgoing links or the number of multiplexed wavelengths in each link. This paper briefly reviews, for optical path realization, the wavelength path (WP) and the virtual wavelength path (VWP) techniques. The proposed OXC architectures provide flexibility and minimum investment to encourage introduction but support incremental network growth and investment to match traffic demand. The architectures make it easy to upgrade a WP network to a VWP network, simply by replacing some optical components. It is also shown that the proposed OXC architectures ensure effective optical signal detection after a long-haul optical fiber transmission because they minimizes signal power losses within the OXC. Therefore, the proposed OXC architecture can be applied to global area networks. The proposed OXC architectures will play a key role in realizing the optical path infrastructure for the future bandwidth abundant B-ISDN.

A W-graph is a partially known graph which contains wild-components. A wild-component is an incompletely defined connected subgraph having p vertices and p-1 unspecified edges. The informations we know on a wild-component are which has a vertex set and between any two vertices there is one and only one path. In this paper, we discuss the properties of circuits in a W-graph (called W-circuits). Although a W-graph has unspecified edges, we can obtain some important properties of W-circuits. We show that the W-ring sum of W-circuits is also a W-circuit in the same W-graph. The following (1) and (2) are proved: (1) A W-circuit Ci of a W-graph can be transformed into either a circuit or an edge disjoint union of circuits, denoted by Ci*, of a graph derived from the W-graph, (2) if W-circuits C1, C2, , Cn are linearly independent, then C1*, C2*, , Cn* obtained in (1) are also linearly independent.

This paper describes a preconstrained compaction method and its application to the direct design-rule conversion of CMOS layouts. This approach can convert already designed physical patterns into compacted layouts that satisfy user-specified design rules. Furthermore, preconstrained compaction can eliminate unnecessarily extended diffusion areas and polysilicon wires which tend to be created with conventional longest path based compactions. Preconstrained compaction can be constructed by combining a longest path algorithm with forward and backward slack processes and a preconstraint generation process. This contrasts with previously proposed approaches based on longest path algorithms followed by iterative improvement processes, which include applications of linear programming. The layout styles in those approaches are usually limited to a model where fixed-shaped rectilinear blocks are moved so as to minimize the total length of rectilinear interconnections among the blocks. However, preconstrained compaction can be applied to reshaping polygonal patterns such as diffusion and channel areas. Thus, this compaction method makes it possible to reuse CMOS leaf and macro cell layouts even if design rules change. The proposed preconstrained compaction approach has been applied to direct design-rule conversion from 0.8-µm to 0.5-µm rules of CMOS layouts containing from several to 10,195 transistors. Experimental results demonstrate that a 10.6% reduction in diffusion areas can be achieved without unnecessary extensions of polysilicon wires with a 39% increase in processing times compared with conventional approaches.

Parallel processing in speech recognition is described, which is carried out at each frame on time axis. We have already proposed a parallel processing algorithm for HMM (Hidden Markov Model)-based speech recognition using Markov Random Fields (MRF). The parallel processing is realized by modeling the hidden state sequence by an MRF and using the Iterated Conditional Modes (ICM) algorithm to estimate the optimal state sequence given an observation sequence and model parameters. However this parallel processing with the ICM algorithm is applicable only to the standard HMM but not to the improved HMM like the linear predictive HMM which takes into account the correlations between nearby observation vectors. In this paper we propose a parallel processing algorithm applicable to the correlation-considered HMM, where a new deterministic relaxation algorithm called the Generalized ICM (GICM) algorithm is used instead of the ICM algorithm for estimation of the optimal state sequence. Speaker independent isolated word recognition experiments show the effectiveness of the proposed parallel processing using the GICM algorithm.

The new algorithm for VP bandwidth control described and analyzed in this paper is a revised version of the Successive Modification Method. Its operation is based only on call-level performance (call blocking probabilities) measured in real time, without explicitly taking the cell-level performance into account. This algorithm does not need to predict future traffic demand and to perform network-wide optimization according to the predicted traffic. These features are well suited for a B-ISDN environment, with the variety of ATM bearer services and the uncertainty of their traffic demand and other characteristics. This paper describes the relationship between the proposed control and other traffic controls in ATM networks, such as CAC and VP shaping/policing. It also offers a solution to the problem of the competition that arises when several VPs in the same transmission path need increased bandwidth. Evaluation of the transient behavior of the VP bandwidth occupied by VCs shows that there is a lower limit in the control cycle and that this limit can be estimated as the longest average holding time of VCs among all services. Numerical results obtained using a call-by-call simulator show that proposed control is effective in preventing the performance degradation caused by a large traffic imbalance in communications networks. Comparison of the proposed control with a dynamical alternate routing for VC reveals that the VP bandwidth control is effective in relieving only the areas showing serious performance degradation, but that it is not so effective in improving the overall network performance.

Lexical-functional grammars (lfg's) were introduced to define the syntax of natural languages. In lfg's, a finite set of attribute-value pairs called an f-structure is associated with each internal node in a derivation tree. For efficient parsing, some subclasses of lfg's were proposed. However, these subclasses have been shown to generate at least one -complete language. In this paper, we introduce a subclass of lfg's called pd-lfg's. In pd-lfg's, an f-structure forms a pushdown stack. For a node v in a derivation tree and at most one specified child vi of v, the f-structure of vi is obtained by performing a specified pushdown stack operation on the f-structure of v. We prove the equivalence of the generative capacity of modified head grammars (mhg's) and that of pd-lfg's. Since the languages generated by mhg's are known to be recognizable in O(n6) time, the languages generated by pd-lfg's can be recognized in O(n6) time.

A new method for the accurate extraction of glottal source parameters is proposed. This method, called Heuristic Analysis-by-Synthesis (HAbS), has been developed specifically to overcome the weaknesses of other methods of glottal source parameter extraction. The specific features of this method are the use of the AbS method for extraction of glottal source and vocal tract parameters, the use of a parametric glottal source model during vocal tract analysis, the use of alternating glottal source and vocal tract analyses, and simultaneous, time-domain analysis of the glottal source parameters and the first formant. This method has been implemented in such a way that user interaction is not required. The performance of the HAbS method is evaluated using both synthetic-speech and natural-speech data. Error is measured in both the time domain and the spectral domain, and the standard deviation of extracted parameter values is computed. In addition, the error in analysis of each glottal-source parameter is computed using synthetic-speech data. In order to assess the accuracy of the HAbS method as compared to other methods, three other methods (LPC, AIF, and AbS) are evaluated using the same data methods of error measurement. From these evaluations, it is clear that the HAbS method yields results that are more accurate than these other methods.

A globally and quadratically convergent algorithm is presented for solving nonlinear resistive networks containing transistors modeled by the Gummel-Poon model or the Shichman-Hodges model. This algorithm is based on the Katzenelson algorithm that is globally convergent for a broad class of piecewise-linear resistive networks. An effective restart technique is introduced, by which the algorithm converges to the solutions of the nonlinear resistive networks quadratically. The quadratic convergence is proved and also verified by numerical examples.