The ringing occurred in the step response causes an undesirable stripe pattern in TV signals. A simultaneous approximation with both the frequency and the step response is required in the designing filter which is used in the image signal processing in order to prevent the ringing. The wellknown Remez algorithm for designing FIR filters approximates the response only in the frequency domain. As the result, the filters designed by this algorithm causes the large ringing in the step response. In this paper, we propose the method of design for FIR filters with minimum amplitude in the stopband, under the condition that the step response has no ringing and the prescribed rise characteristics. For this end, we use the constrained successive projections method.

The uncertainty involved in the gradient constraint for optical flow detection is often modeled as constant Gaussian noise added to the time-derivative of the image intensity. In this paper, we examine this modeling closely and investigate the error behavior by experiments. Our result indicates that the error depends on both the spatial derivatives and the image motion. We propose alternative uncertainty models based on our experiments. It is shown that the optical flow computation algorithms based on them can detect more accurate optical flow than the conventional least-squares method.

Pitchmatching algorithms are widely used in layout environments where no grid constraints are imposed. However, realistic layouts include multiple grid constraints which facilitate the applications of automatic routing. Hence, pitchmatching algorithms should be extended to those realistic layouts. This paper formulates a pitchmatching problem with multiple grid constraints. An algorithm for solving this problem is constructed as an extension of conventional pitchmatching algorithms. The computational complexity is also discussed in comparison with a conventional naive algorithm. Finally, examples and application results to realistic layouts are presented.

This paper describes COCE (COordinative Character Extractor), a method for extracting printed Japanese characters and their character strings from all sorts of document images. COCE is based on a multi-agent system where each agent tries to find a character string and extracts the characters in it. For the adaptability, the agents are allowed to look after arbitrary parts of documents and extract the characters using only the knowledge independent of the layouts. Moreover, the agents check and correct their results sometimes with the help of the other agents. From experimental results, we have verified the effectiveness of our approach.

In order to estimate elasticity distribution of living soft tissue by ultrasonic pulse-echo method, we developed an algorithm by which we estimate 2-D displacement vector field from two successive rf echo data frames. The algorithm estimates a displacement vector iteratively by matching the phase characteristics of the local regions of two data frames. The estimation process is composed of coarse one and the fine one. In the coarse estimation process, the displacement is estimated by detecting the peak of the 2-D cross-correlation function. In the fine process, the displacement is estimated iteratively by shifting the 2nd frame data so that the phase characteristics matches with that of the 1st frame data. In each iterative step of both processes, the estimated displacement vector field is spatially smoothed. This proposed algorithm exhibits excellent performance in obtaining accurate and smooth distribution of displacement vector which is required to obtain strain distribution and finally shear modulus distribution. We conducted an experiment on an agar phantom which has inhomogeneous shear modulus distribution. Using the proposed method, we obtained 2-D displacement field with reasonable accuracy. We reconstructed a relative shear modulus map using axial strain assuming 1-D stress condition. The reconstructed map using the calculated axial strain through 2-D displacement estimation algorithm was satisfactory, and was clearly superior to the one through 1-D displacement estimation algorithm. The proposed 2-D displacement field estimation algorithm seems to be a versatile and powerful tool to measure strain distribution for the purpose of tissue elasticity estimation under various deformation conditions.

In this work, a statistical analysis is performed for a simple constrained high-order Yule-Walker (YW) tone frequency estimator obtained from the first equation of the constrained high-order YW equations. Explicit expressions for its estimation bias and variance are efficiently derived by virtue of a Taylor series expansion technique. Especially, being explicit in terms of frequency, data length and Signal-to-Noise Ratio (SNR) value, the resulting bias expression can not be obtained by using the asymptotic analyses used for the parameter estimation methods. The obtained expressions are compared with their counterparts of the Pisarenko tone frequency estimator. Simulations are performed to support the theoretical results.

Concerning the complexity of tree drawing, the following result of Supowit and Reingold is known: the problem of minimum drawing binary trees under several constraints is NP-complete. There remain, however, many open problems. For example, is it still NP-complete if we eliminate some constraints from the above set? In this paper, we treat tree-structured diagrams. A tree-structured diagrm is a tree with variably sized rectangular nodes. We consider the layout problem of tree-structured diagrams on Z2 (the integral lattice). Our problems are different from that of Supowit and Reingold, even if our problems are limited to binary trees. In fact, our set of constraints and that of Supowit and Reingold are incomparable. We show that a problem is NP-complete under a certain set of constraints. Furthermore, we also show that another problem is still NP-complete, even if we delete a constraint concerning with the symmetry from the previous set of constraints. This constraint corresponds to one of the constraints of Supowit and Reingold, if the problem is limited to binary trees.

The selection of an appropriate key search algorithm for a specific application field is an important issue in application systems development. This is because data retrieval is the most time-consuming part of many application programs. An automatic selection method for key search algorithms is presented in this paper. The methodology has been implemented in a system called KESE2 (KEy-SEarch ALgorithm SElection). Key search algorithms are selected according to the user's requirements through interaction with KESE2 which bases its inferences on an evaluation table. This evaluation table contains values rating the performance of each key search algorithm for the different searching properties, or characteristics. The selection algorithm presented is based on step by step reduction of unsuitable key search algorithms and searching properties. The paper also proposes assistance facilities that consist of both a support function and a program synthesis function. Experimental results show that the appropriate key search algorithms are effectively selected, and that the necessary number of questions asked, to select the appropriate algorithm, is reduced to less than half of the total number of possible questions. The support function is useful for the user during the selection process and the program synthesis function fully translates a selected key search algorithm into high level language in an average of less than 1 hour.

In this paper, we present a method for extracting the Japanese printed characters from unformatted document images. This research takes into account the multiple general features specific to the Japanese printed characters. In our method, these features are thought of as the constraints for the regions to be extracted within the constraint satisfaction approach. This is achieved by minimizing a constraint function estimating quantitative satisfaction of the features. Our method is applicable to all kinds of the Japanese documents because it is no need of a priori knowledge about the document layout. We have favorable experimental results for the effectiveness of this method.

In this paper, we describe a worst-case design optimization approach for statistical design of integrated circuits with a circuit performance model scheme. After formulating worst-case optimization to an unconstrained multi-objective function minimization problem, a new objective function is proposed to find an optimal point. Then, based on an interpolation model scheme of approximating circuit performance, realistic worst-case analysis can be easily done by Monte Carlo based method without increasing much the computational load. The effectiveness of the presented approach is demonstrated by a standard test function and a practical circuit design example.

This paper presents a heuristic floorplanning method that improves the method proposed by Vijayan and Tsay. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method can reduce the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results for MCNC benchmarks showed that the quality of solutions of the proposed method is better than [7],[8] by about 15% on average, and even for the large number of blocks, the proposed method keeps the high quality of solutions.

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.

For medical imaging, non-rigid motion analysis of the heart deformability is a nontrivial problem. This paper introduces a new method to analyze the gated SPECT (Single Photon Emission Computed Tomography) imges for 3-D motion information of left ventricular. Our motion estimation method is based on a new concept called normal direction constraint" in that the normal of a surface patch of some deforming objects at certain time instant is constant. This paper consists of the following processes: contour extraction, slices interpolation, normal vector field generation, expanding process, motion estimation for producing a 2-D motion vector field, and deprojection for a 3-D motion vector field. In the experiments, we will demonstrate the accuracy of our method in analyzing the 3-D motion field of deforming object.

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.

We can understand and recover a scene even from a picture or a line drawing. A number of methods have been developed for solving this problem. They have scarcely aimed to deal with scenes of multiple objects although they have ability to recognize three-dimensional shapes of every object. In this paper, challenging to solve this problem, we describe a method for deciding configurations of multiple objects. This method employs the assumption of coplanarity and the constraint of occlusion. The assumption of coplanarity generates the candidates of configurations of multiple objects and the constraint of occlusion prunes impossible configurations. By combining this method with a method of shape recovery for individual objects, we have implemented a system acquirig a three-dimensional information of scene including multiple objects from a monocular image.

In this paper, the Pisarenko and the Constrained Yule-Walker (CYW) estimators of a tone frequency are first newly derived from the viewpoint of using directly the autocorrelation coefficients. Then, simulation of these two estimators is carried out in some detail. The simulation results show that compared with the Pisarenko estimator the CYW estimator, which has not been adequately studied, works poorly for low and moderate Signal-to-Noise Ratio (SNR) values. However, in case of high SNR value, it yields very small bias and comparable estimation variance, and thus produces more accurate tone frequency estimates.

In this paper, we present a new technique for the semantic analysis of sentences, including an ambiguity-packing method that generates a packed representation of individual syntactic and semantic structures. This representation is based on a dependency structure with constraints that must be satisfied in the syntax-semantics mapping phase. Complete syntax-semantics mapping is not performed until all ambiguities have been resolved, thus avoiding the combinatorial explosions that sometimes occur when unpacking locally packed ambiguities. A constraint satisfaction technique makes it possible to resolve ambiguities efficiently without unpacking. Disambiguation is the process of applying syntactic and semantic constraints to the possible candidate solutions (such as modifiees, cases, and wordsenses) and removing unsatisfactory condidates. Since several candidates often remain after applying constraints, another kind of knowledge to enable selection of the most plausible candidate solution is required. We call this new knowledge a preference. Both constraints and preferences must be applied to coordination for disambiguation. Either of them alone is insufficient for the purpose, and the interactions between them are important. We also present an algorithm for controlling the interaction between the constraints and the preferences in the disambiguation process. By allowing the preferences to control the application of the constraints, ambiguities can be efficiently resolved, thus avoiding combinatorial explosions.

High variability of object features and bad class separation of objects are the main causes for the difficulties encountered during the interpretation of ground-level natural scenes. For coping with these two problems we propose a method which extracts those regions that can be segmented and immediately recognized with sufficient reliability (core regions) in the first stage, and later try to extend these core regions up to their real object boundaries. The extraction of reliable core regions is generally difficult to achieve. Instead of using fixed sets of features and fixed parameter settings, our method employs multiple local features (including textural features) and multiple parameter settings. Not all available features may yield useful core regions, but those core regions that are extracted from these multiple features make a cntributio to the reliability of the objects they represent. The extraction mechanism computes multiple segmentations of the same object from these multiple features and parameter settings, because it is not possible to extract such regions uniquely. Then those regions are extracted which satisfy the constraints given by knowledge about the objects (shape, location, orientation, spatial relationships). Several spatially overlapping regions are combined. Combined regions obtained for several features are integrated to form core regions for the given object calss.

Behavior modeling of objects is critical in object-oriented design. In particular, it is essential to preserve integrity constraints on object behavior in application environments where objects of various classes dynamically interact with each other. In order to provide a stable design technique, a behavior model using the notion of the life cycle schema of a class is proposed. To model the aspect of behavioral abstraction of objects, the notion of schema refinement together with a diagrammatic representation technique is also defined. In this framework, a formalization of behavior constraints on objects which interact with each other is proposed together with its graphical representation. Verification rules of consistency of behavior constraints are also discussed. In order to perform certain functions, several partner objects of the same or different classes should collaborate establishing client-server relationships. The contract of a class is defined as a collection of responsibilities of a server class to a client class where each responsibility is specified in the form of the script. To achieve a high degree of systems integrity, a procedure to derive scripts from behavior constraints on collaborating partners is developed. It is also critical to evenly distribute responsibilities to partner objects. A delegation is placing a whole or a part of responsibilities of an object in charge of other objects. Based on the design principle delegation along the aggregation hierarchy,' a unified design approach to delegation that enables to reorganize scripts in constraints preserving way is proposed.

Algorithms for computing channel capacity have been proposed by many researchers. Recently, one of the authors proposed an efficient algorithm using Newton's method. Since this algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy. In this letter, it is shown that this algorithm can be extended to the algorithm for computing the constrained capacity, i.e., the capacity of discrete memoryless channels with linear constraints. The global convergence of the extended algorithm is proved, and its effectiveness is verified by numerical examples.