This paper describes a new algorithm for finding the contours of a moving object in an image sequence. A distinctive feature of this algorithm is its complete bottom-up strategy from image data to a consistent contour description. In our algorithm, an input image sequence is immediately converted to a complete set of quasi logical spatio-temporal measures on each pixel, which provide constraints on varying brightness. Then, candidate regions in which to localize the contour are bounded based on consistent grouping among neighboring measures. This reduces drastically the ambiguity of contour location. Finally, Some mid-level constraints on spatial and temporal smoothness of moving boundaries are invoked, and they are combined with these low-level measures in the candidate regions. This is performed efficiently by the regularization over the restricted trajectory of the moving boundary in the candidate regions. Since any quantity is dimensionless, the results are not affected by varying conditions of camera and objects. We examine the efficiency of this algorithm through several experiments on real NTSC motion pictures with dynamic background and natulal textures.

This paper proposes a scheme that offers robust extraction of target images in standard view from input facial images, in order to realize accurate and automatic identification of human faces. A standard view for target images is defined using internal facial features, i.e., the two eyes and the mouth, as steady reference points of the human face. Because reliable detection of such facial features is not an easy task in practice, the proposed scheme is characterized by a combination of two steps: first, all possible regions of facial features are extracted using a color image segmentation algorithm, then the target image is selected from among the candidates defined by tentative combination of the three reference points, through applying the classification framework using the sub-space method. Preliminary experiments on the scheme's flexibility based on subjective assessment indicate a stability of nearly 100% in consistent extraction of target images in the standard view, not only for familiar faces but also for unfamiliar faces, when the input face image roughly matches the front view. By combining this scheme for normalizing images into the standard view with an image matching technique for identification, an experimental system for identifying faces among a limited number of subjects was implemented on a commercial engineering workstation. High success rates achieved in the identification of front view face images obtained under uncontrolled conditions have objectively confirmed the potential of the scheme for accurate extraction of target images.

To derive blood flow dynamics from cineangiograms (CAG), we have developed an image processing algorithm to estimate a two-dimensional blood fiow velocity map projected on CAG. Each image area of CAG is diveded into blocks, and it is assumed that the movement of the contrast medium between two serial frames is restricted only to adjacent blocks. By this assumption, a fundamental equation" and the maximum flow constraints" are derived. The equation and constraints state the relationship between the volume of contrast medium in each block and the flow components" that are the volumes of contrast medium flowing from/to its adjacent blocks. The initial guess" that is a set of approximately obtained flow components is corrected using these relationships. The corrected flow components are then transformed into blood flow velocities, which are illustrated in the form of a needle diagram. In numerical experiments, the estimation error between the real flow velocity generated artificially and the flow velocity estimated with our algorithm was evaluated under one of the worst conditions. Although the maximum error was fairly large, the estimated flow velocity map was still acceptable for visual inspection of flow velocity pattern. We then applied our algorithm to an abdominal CAG (clinical data). The results showed flow stagnation and reverse flow in the abdominal aneurysm, which are consistent with the presence of a thrombus in the aneurysm. This algorithm may be a useful diagnostic tool in the assessment of vascular disease.

This article discusses on PDM (Petri net based Development Methodology) which integrates approaches, modeling methods, design methods and analysis methods in a coherent manner. Although various development techniques based on Petri nets have demonstrated advantages over conventional techniques, those techniques are rather ad hoc and lack an overall picture on entire development process. PDM anticipates to provide a refernce process model to develop distributed systems with various Petri net based development methods. Behavioral properties of distrbuted systems can be an appropriate application domain of PDM.

A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.

This paper describes a noise resistant algorithm for recovering the three-dimensional motion of a rigid object from optical flow. First, it is shown that in the absence of noise three-demensional motion can be obtained exactly by a linear algorithm except in the special case in which the surface of the object is on a general quadratic surface passing through the viewpoint, and the normal vector of the surface at the viewpoint is perpendicular to the translation velocity vector. In the presence of noise, an evaluation function is introduced based on the least squares method. It is shown, however, that the solution which minimizes the evaluation function is not always optimal due to statistical bias. To deal with this problem, a method to eliminate the statistical bias in the evaluation function is proposed for zero mean white noise. Once the statistical bias is eliminated, the solution of the linear algorithm coincides with the correct solution by means of expectation. In this linear algorithm, only the eigenvector corresponding to the zero eigenvalue of a 33 matrix is necessary to find the translational velocity. Once the translational velocity is obtained, the rotational velocity can be computed directly. This method is also shown to be noise resistant by computer simulation.

A modern architect can not design high performance computer architecture without thinking all factors of performance from hardware level (logic/layout design) to system level (application programs, operating systems, and compilers). For computer architecture design, there are few practical CAD tools, which support design activities of the architect. In this paper, we propose a CAD tool, called COACH, for computer architecture design. COACH supports architecture design from hardware level to system level. To make a high-performance general purpose computer system, the architect evaluates system performance as well as hardware level performance. To evaluate hardware level performance accurately, logic/layout synthesis tools and simulator are used for evaluation. Logic/layout synthesis tools translate the architecture design into logic circuits and layout pattern and simulator is used to get accurate information on hardware level performance which consists of clock frequency, the number of transistors, power consumption, and so on. To evaluate system level performance, a compiler generator is introducd. The compiler generator generates a compiler of a programming language from the desripition of architecture design. The designed architecture is simulated in the behavior level with programs compiled by the compiler, and the architect can get information on system level performance which consists of program execution steps, etc. From both hardware level performance and system level performance, the architect can evaluate and revise his/her architecture, considering the architecture from hardware level to system level. In this paper, we propose a new design methodology which uses () logic/layout synthesis tools and simulators as tools for architecture design and () a compiler generator for system level evaluation. COACH, a CAD system based on the methodology, is discussed and a prototype of COACH is implemented. Using the design methodology, two processors are designed. The result of the designs shows that the proposed design methodology are effective in architecture design.

For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.

This letter presents an algorithm named SPM which generates test patterns for single stuck-at faults in synchronous sequential circuits based on a product machine traversal method. The new idea presented in this letter is partitioned image computation combined with a mixed breadth-first/depth-first search. Image computation is carried out in partitioned manner by substituting constant logical values to some input variables. This brings about significant reduction in storage requirement during image computation. A test generator based on SPM achieved 100% fault efficiency for the ISCAS'89 benchmark circuits with not more than 32 flip-flops.

There have been several studies related to a reduction of the amount of computational resources used by Turing machines. As consequences, linear speed-up theorem" tape compression theorem", and reversal reduction theorem" have been obtained. In this paper, we consider reversal- and leaf-bounded alternating Turing machines, and then show that the number of leaves can be reduced by a constant factor without increasing the number of reversals. Thus our results say that a constant factor on the leaf complexity does not affect the power of reversal- and leaf-bounded alternating Turing machines

We introduce automatic procedures for generating and verifying sufficient correctness properties of synchronous processors. The targeted circuits are synchronous array processors designed from localized, highly regular data dependency graphs (DDGs). The specification, in the form of a DDG, is viewed as a maximally parallel circuit. The implementation, on the other hand, is a (partially) serialized circuit. Since these circuits are not equivalent from an automata-theoretic viewpoint, we define the correctness of the implementation against the specification to mean that a certain relation (called the β-relation) holds between the two. We use a compositional approach to decouple the verification of the control circuitry from that of the data path, thereby gaining efficiency. An array processor in isolation may not have a definite flow of control, because control may reside in the data stream. Therefore, for the purpose of verification, we construct an auxiliary machine, which keeps a timing reference and generates control signals abstracted from a typical data stream. Sufficient correctness conditions are expressed as past-tense computation tree logic (CTL) formulae and verified by CTL model-checking procedures. Experimental results of the verification of a matrix multiplication array and a Gaussian elimination array are presented.

Test pattern generation is getting much harder as the circuit size becomes larger. One problem is that it tends to take much time and another one is that it is difficult to detect redundant faults. Aiming to cope with these problem, an enhanced unique sensitization technique is proposed in this paper. This powerful global implication reduces the number of backtracks with reasonable computational time. And a fast test pattern generator featuring this unique sensitization demonstrates its performance using large benchmark circuits with over ten thousands of gates. It takes only a minute to detect all testable faults and to identify all redundant faults of 20,000 gates circuit on a workstation.

This paper shows that coherent optimization strategies for multilevel systhesis should rely on a good link between the factorization, the technology mapping and the netlist optimization. Factorization options are shown to play a key role. The technology mapping should optimize both area and critical path and only netlist structure preserving" optimization techniques (buffer insertion, gate replication) should be applied first to preserve the factorization decision. Only in a last step resynthesis of critical areas based on a local view is applied. The approach has been experimented on a set of large combinational benchmarks.

Reducing communication complexity is a viable approach to multilevel logic synthesis. A communication complexity based approach was proposed previously. In the previous works, only disjoint input decomposition was considered. However, for certain types of circuits, the circuit size can be reduced by using overlapped decomposition. In this paper, we consider overlapped decompositions. Some design issues for overlapped decompositions such as detecting globals" and deriving subfunctions are addressed. Moreover, the Decomposition Don't Cares (DDC) is considered for improving the decomposed results. By using these techniques together, the area and delay of circuits can be further minimized.

Since the time required for testing logic circuits is proportional to the number of test vectors, the size of test sets as well as test generation time is one of the most important factors to be considered in test generation. The size of test sets becomes an essential issue, especially for scan designed circuits, because of the need to shift a test vector serially into the scan path. In this paper, we propose new methods of generating compact test sets to detect al the irredundant single stuck-at faults in combinational circuits. The proposed algorithms calculate a test function for each fault which corresponds to the set of all test vectors for the fault and generate a compact test set by analyzing the test functions. The analysis is based on finding a test vector which detects the largest number of remaining faults. Since our methods select a test vector among all the test vectors, represented by a test function, for a target fault, smaller test sets can be generated, in general, than that by conventional test set compaction methods. The experimental results show that the size of test sets generated by our method is about one-third as large as that without compaction.

This paper describes the hierarchical behavioral description language celled SFL and its processing system. This integrated CAD system called PARTHENON is used for designs of the leading ASICs in the NTT Systems Labs. This paper shows, therefore, the effectiveness of PARTHENON as a practical high-lelel synthesis system through real design experience. SFL was developed to aid in the design of the hardware functions and behaviors of ASICs composed solely of clocksynchronized circuits. The main features of SFL are as follows: (1) It is not mixed with connection description, but employs only behavioral description (like procedual description in program language), and it provides hierarchical expression of behavioral description. (2) It permits the description of parallel processing operations by adopting a new hardware task concept. And, (3) it is linked with the behavioral simulator, logic synthesizer, and other components of the processing system. After describing SFL in some detail, a brief explanation of its synthesizer and other processing components is provided, along with its application results in the real design of some leading ASICs at the NTT Systems Laboratories.

This paper characterizes a class of optimal fixed-to-fixed length data compression codes for memoryless Gaussian sources that achieve asymptotically the rate-distortion bound under squared-error criterion. Any source output of blocklength n is encoded by two steps, i.e., 1) to quantize in gain by scholar quantizers and 2) to quantize in shape by pointsets on n-dimensional hyperspheres. To show the asymptotic optimality of the proposed codes, rate-distortion properties of the codes are analyzed in detail by using a random coding argument on the n-dimensional unit hypersphere. It is shown that asymptotic behaviors of the proposed codes are mainly determined by the choice of scalar quantizer of the gain. As a results, deep insights into not only the class of asymptotically optimal codes but also the rate-distortion bound itself are obtained.

A new arithmetic multiple-valued algebra with functional completeness is introduced. The algebra is called Neuro-Algebra for it has very similar formula and architecture to neural networks. Two canonical forms of multiple-valued functions of this Neuro-Algebra are presented. Since the arithmetic operations of the Neuro-Aglebra are basically a weighted-sum and a piecewise linear operations, their implementations are very simple and straightforward. Furthermore, the multiple-valued networks based on the Neuro-Algebra can be trained by the traditional back-propagation learning algorithm directly.

This paper considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. By the way, a graph is called an almost tree if E(B)V(B)+ K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K0 if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem.

This paper proposes new design methods for single b-bit (b2) byte error correcting and double bit error detecting code, called SbEC-DED code, suitable for high-speed memory systems using byte organized RAM chips. This new type of byte error control code is practical from the viewpoint of having less redundancy and stronger error control capability than the existing ones. A code design method using elements from a coset of subfield under addition gives the practical SbEC-DED code with 64 information bits and 4-bit byte length which has the same check-bit length, 12 bits, as that of the Hamming single byte error correcting code. This also has very high error detection capabilities of random double byte errors and of random triple bit errors.