In this study, an extraction method of failure sound signal which is strongly contaminated by noise is investigated by genetic algorithm and statistical tests of the frequency domain for the failure diagnosis of machinery. In order to check the extraction accuracy of the failure signal and obtain the optimum extraction of failure signal, the "existing probability P_s (t^*_k) of failure signal" and statistical information I_qp are defined as the standard indices for evaluation of the extraction results. It has been proven by practical field data and application of the inspection and diagnosis robot that the extraction method discussed in this paper is effective for detection of a failure and distinction of it's origin in the diagnosis of machinery.

In order to ensure the reliability and safety of equipment installed in process lines, it is important that maintenance and management should make efficient use of machine diagnosis techniques. Machine diagnosis by means of acoustic signals has hitherto been beset with difficulty, but there is now a strong demand that new acoustic type diagnosis equipment (utilizing acoustic signals) be developed. In response to this demand, the authors recently conducted research on diagnosis of machine faults by means of the processing of acoustic signals. In this research they were able to develop new acoustic type machine diagnosis techniques, and, using these techniques, to develop acoustic diagnosis equipment for practical use.

Intracranial blood flow noise measuring and analyzing system were developed to detect the cerebrovascular diseases such as aneurysm, stenosis and occlusion in their early stage. To realize the effective measuring of the sound known as the 'bruit,' dedicated PVDF-film based sensor working on the closed eyelid was designed. FFT spectrums and Wigner distributions were used as analyzing methods to clarify both the precise spectrum and the time variance of the signals. Thirty normal people without any history of cerebrovascular disease were tested with the system to estimate the characteristics of the background noise. Thirteen patients, including eight stenosis, four aneurysm and one occlusion, were studied with the system. FFT spectral differences between patient and normal existed over the frequency range from 0.5kHz to 1.2kHz. In this range apparent increases of the signal components' power were observed for the patients. Numerically, this tendency was confirmed by the power difference between 750Hz and 1.5kHz, which could be the possible index of the existence diagnosis for cerebrovascular diseases. The shape of the FFT spectral pattern showed some difference between stenosis and aneurysm. In stenosis cases, it seemed that there existed the flat level from 0.4kHz to 1.2kHz, while in aneurysm cases the power decreases smoothly as frequency increases from the peak around 0.7kHz. Time variance of the bruit according to the cardiac cycle could be seen in the cases of stenosis from 30% to 50%, but not in the cases from 40% to 90%. This fact suggested the possibility to diagnose the extent of the stenosis. In most cases, recognizable spectral peak around 0.7 kHz were observed. Although the physical meanings of those peaks were not so clear, still it was the apparent characteristics and might be including important information.

A non-invasive method is proposed to estimate the location of intracranial vascular disease using several sensors placed on the forehead. The advantage of this method over earlier measurements with a single ocular sensor is the abilty to localize the region of abnormal vascular tissue. A weighted least mean square procedure is applied to estimating the time difference between the sensor outputs using the phase distribution in the cross-spectrum. It is possible to estimate time differences shorter than sampling period. Computer simulation and clinical experiments demonstrate that a distance difference of around 20 times shorter than the wavelength can be obtained.

In this paper, the discrimination of ultrasonic heart (echocardiographic) images is studied by making use of some texture features, including the angular second moment, contrast, correlation and entropy which are obtained from a gray-level cooccurrence matrix. Features of these types are used as inputs to the input layer of a neural network (NN) to classify two sets of echocardiographic images-normal heart and dilated cardiomyopathy (DCM) (18 and 13 samples, respectively). The performance of the NN classifier is also compared to that of a minimum distance (MD) classifier. Implementation of our algorithm is performed on a PC-486 personal computer. Our results show that the NN produces about 94% (the confidence level setting is 0.9) and the MD produces about 84% correct classification. We notice that the NN correctly classifies all the DCM cases, namely, all the misclassified cases are of false positive. These results indicate that the method of feature-based image analysis using the NN has potential utility for computer-aided diagnosis of the DCM and other heart diseases.

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.

Ultrasonic diffraction image of specimen informs its acoustic structure as X ray diffraction method for analysis of the crystal structure. This ultrasonic diffraction method has a feature that focused ultrasound beam is used and diffraction image is observed on focal plane. When the structure of specimen is perfectly periodic, its diffraction image produces symmetrical respect to origin, but the diffraction image of weak periodic structure such as living tissue has some asymmetricity. In this paper, the principle of ultrasonic diffraction method, and data processing for asymmetrical and scattered diffraction image caused by weak periodic structure are described. The results of diffraction image of plant tissue and animal tissue, and its discussion are also described. This method is expected to be useful in evaluation of acoustic structure such as living tissue and internal tissue of bone.

A continuous-wave ultrasonic Doppler system using wide field ultrasound transducers was applied to telemeter blood velocity from the carotid artery of exercising subjects. Velocity spectrogram was obtained by Hanning windowed fast Fourier transformation of the telemetered data. Distortion caused by a high-pass filter and transducers in the telemetry system was discussed in the paper. As the maximum Reynolds number in our experiment was 1478 which is smaller than the critical level of 2000, the blood flow should be laminar. Spatial velocity profiles were then reconstructed from the velocity spectrogram. In this paper, we defined a converging index Q of the velocity spectrum to measure the bluntness of the spatial velocity distribution across the blood vessel. Greater Q, the blunter the velocity profile will be. Simulation results for spatial velocity distributions of theoretical parabolic flow and Gaussian-distribution spectra with varied Q value showed that the cut-off effect by a high-pass filter of cut-off frequency f_c=200Hz in our system could be ignored when the axial velocity is larger than 0.30 m/s and Q is greater than 2.0. Our experimental results, in contrast to those obtained from phantom systems by us and by Hein and O'Brien, indicate that the distribution of blood velocity is much blunter than previously thought. The Q index exceeded 10 during systole, whereas it was 0.5 in parabolic flow. The peak of Q index lagged behind that of axial blood velocity by approximately 0.02s. The phase delay of the Q index curve might be due to the time needed for the red blood cells to form the non-homogeneous distribution.

In this paper we propose a new method for removing the characteristic of the piezoelectric transducer from the received signal in the pulse-echo method so that the time resolution in the determination of transit time of ultrasound in a thin layer is increased. The total characteristic of the pulse-echo system is described by cascade of distributed-constant systems for the ultrasonic transducer, matching layer, and acoustic medium. The input impedance is estimated by the inverse matrix of the cascade system and the voltage signal at the electrical port. From the inverse Fourier transform of input impedance, the transit time in a thin layer object is accurately determined with high time resolution. The principle of the method is confirmed by simulation experiments.

In order to evaluate quantitatively TMJ sound, TMJ sound in normal subject group, CMD patient group A with palpable sounds unknown to them, CMD patient group B with palpable sounds known to them, and CMD patient group C with audible sounds were detected by a contact microphone, and frequency analysis of the power spectra was performed. The power spectra of TMJ sound of normal subject group and patient group A showed patterns with frequency values below 100 Hz, whereas the power spectra of patient groups B and C showed distinctively different patterns with peaks of frequency component exceeding 100 Hz. As regards the cumulative frequency value, the patterns for each group clearly differed from those of other groups; in particular the 80% cumulative frequency value showed the greatest difference. From these results, it is assumed that the 80% cumulative frequency value can be used as an effective indicator for quantitative evaluation of TMJ sound.

The aliasing probability was analyzed for MISRs when the error probability for each input was different. A closed form expression was derived by applying the complete weight distributions of linear codes over a Galois field and its dual codes. The aliasing probability for MISRs characterized by non-primitive polynomials was also analyzed. The inner product for binary representation of symbols was used instead of multiplication over a Galois field. The results show the perfect expression for analyzing the aliasing probability of MISRs.

We have developed a method to automatically generate a multi-input-adder circuit for an irregular array of partial products. "FASTOOL," an FIR Filter Automatic Synthesis TOOL for an HDL design environment, is proposed for use with this method and with conventional filter coefficient design programs. Filter design from specifications to the structure of Verilog-HDL has been automated. It is possible for a system designer to quickly perform filter LSI optimization by balancing cost and performance.

This paper proposes a new method to design an optimal pipelined instruction set processor using formal HW/SW codesign methodology. A HW/SW partitioning algorithm for selecting an optimal pipelined architecture is introduced. The codesign task addressed in this paper is to find a set of hardware implemented operations to achieve the highest performance of an ASIP with pipelined architecture under given gate count and power consumption constraints. The problem formalization as well as the proposed algorithm can be considered as an extension of our previous work toward a pipelined architecture. The experimental results show that the proposed method is quite effective and efficient.

In this paper we describe a method for resynthesizing the controller of a design for a fixed datapath with the objective of increasing the design's throughput by minimizing its total execution time. This work has tremendous potential in two important areas: one, design reuse for retargetting datapaths to new libraries, new technologies and different bit-widths; and two, back-annotation of physical design information during High-Level Synthesis (HLS), and subsequent adjustment of the design's schedule to account for realistic physical design information with minimal changes to the datapath. We present our approach using various formulations, prove optimality of our algorithm and demonstrate the effectiveness of our technique on several HLS benchmarks. We have observed improvements of up to 34% in execution time after straightforward application of our controller resynthesis technique to the outputs of HLS.

This paper presents Ternary Decision Diagrams which represent sets of products. This paper also presents manipulating methods for sum-of-products forms and ringsum-of-products forms using Ternary Decision Diagrams, and gives comparison results between Ternary Decision Diagrams and Binary Decision Diagrams.

Ordered binary decision diagrams (OBDDs) have been widely used in many CAD applications as efficient data structures for representing and manipulating Boolean functions. For the efficient use of the OBDD, it is essential to find a good variable order, because the size of the OBDD heavily depends on its variable order. Dynamic variable reordering is a promising solution to the variable ordering problem of the OBDD. Dynamic variable reordering with the sifting algorithm is especially effective in minimizing the size of the OBDD and reduces the need to find a good initial variable order. However, it is very time-consuming for practical use. In this paper, we propose two new implementation techniques for fast dynamic variable reordering. One of the proposed techniques reduces the number of variable swaps by using the lower bound of the OBDD size, and the other accelerates the variable swap itself by recording the node states before the swap and the pivot nodes of the swap. By using these new techniques, we have achieved the speed-up ranging from 2.5 to 9.8 for benchmark circuits. These techniques have reduced the disadvantage of dynamic variable reordering and have made it more attractive for users.

Though tree covering is an efficient algorithm for technology mapping, phase assignments on tree boundaries are not taken into consideration. Several inverter minimization algorithms have been proposed so far, but they do phase optimization before or after technology mapping, and their cost function is not to minimize the total area but to minimize the number of inverters. This paper describes a new formulation of phase optimization problem aiming to minimize the total area during the technology mapping. Cost function representing area according to each phase assignment is introduced, and tree covering algorithm is modified to handle that cost function. Edge-Valued Binary Decision Diagram is used to represent the function implicitly. Experimental results show that proposed method reduces about 10% area on average compared with a state-of-the-art logic synthesis system sis.

This paper presents testing methods for a logic synthesis system which supports the standard HDL UDL/I, focusing on conformance test to the language specification. Conformance test, to prove that the system completely satisfies the language specification, is very important to provide a unified design environment for users of CAD tools which support the language. The basic idea of our testing methods is using a logic simulator, due to a limited schedule for the test execution. We classified the test into two: unit test and integration test. Unit test is a test of each individual functionality of the system, and integration test is a test to prove that the whole system works correctly and satisfies the language specification. And we prepared and used various kinds of test data. One of them is the UDL/I Test Suite and it was also utilized to observe progress of language coverage by the system during the test execution.

UDL/I test suites and UDL/I Simulation/Synthesis Environment had been developed separately in parallel. Both were designed from syntax and semantics definition of UDL/I Language Reference Manual. Through test of the UDL/I Simulation/Synthesis Environment using the UDL/I test suites, quality of the test suites and the environment had been improved. Finally all the testing result matched with expected one. It was validated that both the test suites and the environment followed UDL/I language specification.

CAMs (Content Addressable Memories) are functional memories which have functions such as word-parallel equivalence search, bilateral 1-bit data shifting between consecutive words, and word-parallel writing. Since CAMs can be integrated because of their regular structure, massively parallel CAM functions can be executed. Taking advantage of CAMs, Ishiura and Yajima have proposed a parallel fault simulation algorithm using a CAM. This algorithm, however, requires a large amount of CAM storage to simulate large-scale circuits. In this paper, we propose a new massively parallel fault simulation algorithm requiring less CAM storage, and compare it with Ishiura and Yajima's algorithm. Experimental results of the algorithm on CHARGE --the CAM-based hardware engine developed in our laboratory--are also reported.

In circuit partitioning for FPGAs, partitioned signal nets are connected using I/O blocks, through which signals are coming from or going to external pins. However, the number of I/O blocks per chip is relatively small compared with the number of logic-blocks, which realize logic functions, accommodated in the FPGA chip. Because of the I/O block limitation, the size of a circuit implemented on each FPGA chip is usually small, which leads to a serious decrease of logic-block utilization. It is required to utilize unused logic-blocks in terms of reducing the number of I/O blocks and realize circuits on given FPGA chips. In this paper, we propose an algorithm which partitions an initial circuit into multi-FPGA chips. The algorithm is based on recursive bi-partitioning of a circuit. In each bi-partitioning, it searches a partitioning position of a circuit such that each of partitioned subcircuits is accommodated in each FPGA chip with making the number of signal nets between chips as small as possible. Such bi-partitioning is achieved by computing a minimum cut repeatedly applying a network flow technique, and replicating logic-blocks appropriately. Since a set of logic-blocks assigned to each chip is computed separately, logic-blocks to be replicated are naturally determined. This means that the algorithm makes good use of unused logic-blocks from the viewpoint of reducing the number of signal nets between chips, i.e. the number of required I/O blocks. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it decreases the maximum number of I/O blocks per chip by a maximum of 49% compared with conventional algorithms.

In VLSI or PCB layout, one often encounters a region that is either of rectilinear shape or can be approximated by a rectilinear region. Although many placement methods have been proposed, most of them are applicable only to rectangular regions. For these algorithms to be applied to a rectilinear region, two processing steps, region partitioning and rectangular region cell placement are necessary. Hence, the placement results are so far dependent on the locations of the regions partitioned and frequently become trapped in local minima. Recently, neural networks have been suggested as a new way to resolve the cell placement problem. This paper proposed a unified modeling method that uses a neural net model with additional calibration nodes to model rectilinear region cell placement. In this method, the ideal distance between cells is preserved to simultaneously minimize both the total wire length and the module overlap. Unlike traditional approaches, the proposed algorithm requires only a single processing step. Experiments have been conducted to verify the performance of the proposed algorithm. The total wire length obtained by our method is shorter than those generated by previous methods.

This paper presents a new approach of data pipelining for mincut partitioning acceleration using a parallel computer. When using a parallel computer, it is important to have many processors always active, also the quality of the partitioning must not be sacrificed. Out approach covers both speed and quality. We choose the hardware CAD accelerator TP5000 to implement our approach, which consists of dedicated Very Long Instruction Word (VLIW) processors with high-speed interconnections. The TP5000 allows its connections to be reconfigured to optimize the data pipelines. We estimate that the speed of our approach using 10 processors on the TP5000 is 30 times faster than a SPARCStation-10.

Three primary wiring capacitance components for multi-layer interconnect structure in sub-micron LSI were analyzed by using 2D/3D simulators, and an influence of neighboring wiring was investigated as a three-body problem. The investigated neighboring wiring are three kinds, and they are same-layer, upper-layer and under-layer wiring. An analytical model of each capacitance component was proposed for LPE (Layout Parameter Extraction) system, and its accuracy and application limit were discussed. This new model can estimate each capacitance component of complicated interconnect structure within 20% error.

This paper presents an accurate and semi-physical MOSFET substrate current model suitable for analog circuit simulations. The proposed model is valid over a wide range of the electric field present in MOSFET devices and is continuous from cut off region to saturation region. The developed model was implemented into the circuit simulator, SPICE3. Benchmark of the developed model was achieved by making comparisons between the measured data and the simulated data for MOSFET devices, push-pull CMOS inverters, a regulated cascode CMOS operational amplifier. The experimental results showed that the developed model was more accurate and computationally efficient than the conventional models.

In identification of a finite impulse response (FIR) model using noise-corrupted input and output data, the least squares type of estimation schemes such as the ordinary least squares (LS), the corrected least squares (CLS) and the total least squares (TLS) method become often numerically unstable, when the true input signal to the system is strongly correlated. To overcome this ill-conditioned problem, we propose a regularized CLS estimation method by introducing multiple regularization parameters to minimize the mean squares error (MSE) of the regularized CLS estimate of the FIR model. The asymptotic MSE can be evaluated by considering the third and fourth order cross moments of the input and output measurement noises, and an analytical expression of the optimal regularization parameters minimizing the MSE is also clarified. Furthermore, an effective regularization algorithm is given by using the only accessible input-output data without using any true unknown parameters. The effectiveness of the proposed data-based regularization algorithm is demonstrated and compared with the ordinary LS, CLS and TLS estimates through numerical examples.

In this paper we study the bifurcations of the periodic solutions induced by the symmetrical properties of a system of hybridly coupled oscillators of the Rayleigh type. By analogy with the results concerning with the equilibria, we classify the periodic solutions according to their spatial and temporal symmetries. We discuss the possible bifurcations of each type of periodic solution. Finally we analyze the phase portraits of the system when the parameters vary.

In this paper we study the properties induced by the symmetrical properties of a system of hybridly coupled oscillators of the Rayleigh type on the bifurcations of its equilibria. We first discuss the symmetrical properties of the system. Then we classify the equilibria according to their symmetrical properties. Demonstrating the structural degeneracy of the system, we give the complete stability analysis of the equilibria.

The family P_k of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for P_k, all the minimal forbidden minors are known only for P₁. This paper lists 36 minimal forbidden minors for P₂, and shows that there exist no other minimal forbidden minors for P₂.

This paper presents some tighter bounds on universal noiseless coding, in particular, the lowerbound tighter than Davisson et al.'s for finite sequence and the upperbound for some typical universal data compression. We find that Davisson et al.'s bound satisfies some optimization in the case of using the Jeffreys prior and also that the derived upperbound in this paper is within O(1/n) from the Clarke and Barron asymptotics in the case of some restricted typical universal data compression defined in the paper.

Petri nets are useful in modeling and analyzing various types of discrete-event systems such as parallel processing systems, distributed systems, and sequential control systems, because Petri nets can easily be used to represent such properties of these systems as concurrency, nondecidability, and causality. Various behavioral analytic problems on Petri nets are reduced to reachability and liveness on them. It is also known that the decidability of liveness is equivalent to that of reachability which is solvable. However, useful necessary and sufficient structural liveness conditions have been given only for extended free-choice (EFC) nets and their subclasses. Moreover recently, a necessary and sufficient structural liveness condition for a useful subclass N_KT=(S_KT, T_KT, F_KT, M_oKT) (i.e., a Petri net in which each minimal structural deadlock (MSDL) contains at least one real or virtual kindling trap, each locally structural-live MSDL N_D=(S_D, T_D, F_D, M_oD) is never globally dead even if all key transitions for local liveness of each MSDL are controlled by the net of S_KTS_D s.t. S_KTS_D, and there exists no singular MSDL of type (α)) has also been given. In this paper, in order to give one of the bases for a necessary and sufficient "structural" or "initial-marking-based" liveness condition for a general Petri net N, we will, first, directly present a necessary and sufficient local liveness condition for each MSDL with a real deadlock-trap structure in a subclass Ñ (N) using the net structure and initial token distribution and extending basic concepts used in N_KT, where Ñ is a general Petri net without live behavioral traps, local liveness means a useful necessary condition for the above final goal, and real deadlock-trap structure means that each MSDL in Ñ contains at least one minimal structural trap. Secondly, a new subclass is shown in which, if the above locally structural liveness condition for each MSDL holds, then the whole-net liveness is also guaranteed. It is also argued that the obtained results are applicable to describing new live behavioral traps and deriving a necessary and sufficient structural liveness condition, which is the final goal in this work, for a general Petri net N.

Up to now, the only useful and well-known structural or initial-marking-based necessary and sufficient liveness conditions of Petri nets have only been those of an extended free-choice (EFC) net and its subclasses such as a free-choice (FC) net, a forward conflict free (FCF) net, a marked graph (MG), and a state machine (SM). All the above subclasses are activated only by deadlock-trap properties (i.e., real d-t properties in this paper), which mean that every minimal structural deadlock (MSDL N_D=(S_D, T_D, F_D, M_oD)) in a net contains at least one live minimal structural trap (MSTR N_T=(S_T, T_T, F_T, M_oT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), and the net with kindling traps N_KT have recently been determined, in which each MSDL without real d-t properties was also activated by a new type of trap of trap, i.e., behavioral traps (BTRs), which are defined by introducing a virtual MSTR, a virtual maximal structural trap (virtual STR), a virtual MSDL, and a virtual maximal structural deadlock (virtual SDL) into a target MSDL. In this paper, a structural or initial-marking-based necessary and sufficient condition for local liveness (i.e., virtual deadlock-trap properties) of each MSDL N_D s.t. S_DS_T, S_DS_T, S_DS_T (but N_D s.t. S_DS_T is dead owing to real deadlock-trap properties) in a general Petri net N is presented by extending that in N_KT. Specifically, live minimal behavioral traps (MBTRs) as well as live maximal behavioral traps (BTRs), i.e., virtual deadlock-trap properties, in a general Petri net N are characterized using the real d-t properties of each MSDL N_D s.t. S_DS_T for a general Petri net N, which were also obtained by extending the concept of return paths in N_KT in connection with an MSDL which contains at least one MSTR and by using the concepts of T-cornucopias and absolute T-cornucopias in a subclass Ñ of N. In other words, BTRs are defined by introducing a virtual MSTR, a virtual STR, a virtual MSDL, and a virtual SDL into a target MSDL without real d-t properties. Additionally, a structural or initial-marking-based necessary and sufficient condition for liveness of a new subclass N_n of a general Petri net N (i.e., a general Petri net without time) is derived, and the usefulness of the obtained results is also discussed.

If a general Petri net N = (S, T, F, M_o) is transition-live under M_o, it is evident that each maximal structural deadlock SDL(_D) in N as well as each minimal structural deadlock MSDL (N_D) in each _D is also transition-live under M_o. However, since the converse of the latter of the above is not always true, it is important to obtain the conditions for this converse to be true if we want to have a useful necessary and sufficient "initial-marking-based" or "structural" liveness condition for N. Up to now, usefull and well-known structural or initial-marking-based necessary and sufficient liveness conditions of Petri nets have only been those of an asymmetric choice (AC) net and its subclasses such as an EFC net, an FC net, an FCF net, MG, and SM. However, all the above subclasses are activated only by real or virtual deadlock-trap properties which are local liveness for each minimal deadlocks; in other words, the above topics of this paper are unconditionally satisfied in those subclasses because of their special structure of nets. In this paper, a necessary and sufficient structural liveness condition for a general Petri net N with globally structural live minimal structural deadlocks is presented as follows: The next () or () is satisfied. () N has no SDL _D. () If N has at least one SDL _D, () or () is satisfied under the condition that each MSDL N_D in N is transition-live under M_o. () N has no singular MSDL (α) (i.e., (α-) and (α-)). () If N has at least one singular MSDL (α-)((α-), resp.), every semi-MDSL ()((), resp.) N_DS = (S_DS, T_DS, F_DS, M_oDS with respect to each singular MSDL (α-)((α-), resp.), is transition-live under the M_oDS under the condition of "the condition (**)", where the locally structural liveness for this N_DS means (1) or (2)((3), resp.) of Lemma 4-4 and "the condition (**)" is defined in Lemma 4-7 of this paper. The relationship between the above results and the liveness problem for N is also shown.

A new motion field segmentation algorithm under the 8-parameters motion model is presented which uses a multipass iterative region-refining techinique. The iterative region-refining module consists of a seed block detection and subsequent region-refining iterations. An initial estimate of an object motion is provided in the seed block detection process. This initial estimate is iteratively updated and approaches to a reliable mapping parameter set in region-refining process. A multipass composition of the module makes it possible to detect multiple motions in a scene. Our simulation results confirm that the proposed method successfully partitions an image into independently moving objects with allowable computation time.