For reduction of computational complexity in the IA algorithm, the thinned-out IA algorithm in which only one step size is updated every iteration is proposed and is complementarily switched with the HA algorithm according to the convergence. The switching is determined by using the gradient of the error signal power. These are investigated through the computer simulations.

A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. The subject of the paper is to find a minimal siphon containing a given set of specified places of a general Petri net.

Research in very low-bit rate coding has made significant advancements in the past few years. Most recently, the introduction of the MPEG-4 proposal has motivated a wide variety of a approaches aimed at achieving a new level of video compression. In this paper we review progress in VLBV categorized into 3 main areas. (1) Waveform coding, (2) 2D Content-based coding, and (3) Model-based coding. Where appropriate we also described proposals to the MPEG-4 committee in each of these areas.

Hybrid image coding method is one of the most promising methods for efficient coding of moving images. The method makes use of jointly motion-compensated prediction and orthogonal transform like DCT. This type of coding scheme was adopted in several world standards such as H.261 and MPEG in ITU-T and ISO as a basic framework [1], [2]. Most of the work done in motion-compensated prediction has been based on a block matching method. However, when input moving images include complicated motion like rotation or enlargement, it often causes block distortion in decoded images, especially in the case of very low bit-rate image coding. Recently, as one way of solving this problem, some motion-compensated prediction methods based on an affine transform or bilinear transform were developed [3]-[8]. These methods, however, cannot always express the appearance of the motion in the image plane, which is projected plane form 3-D space to a 2-D plane, since the perspective transform is usually assumed. Also, a motion-compensation method using a perspective transform was discussed in Ref, [6]. Since the motion detection method is defined as an extension of the block matching method, it can not always detect motion parameters accurately when compared to gradient-based motion detection. In this paper, we propose a new motion-compensated prediction method for coding of moving images, especially for very low bit-rate image coding such as less than 64 kbit/s. The proposed method is based on a perspective transform and the constraint principle for the temporal and spatial gradients of pixel value, and complicated motion in the image plane including rotation and enlargement based on camera zooming can also be detected theoretically in addition to translational motion. A computer simulation was performed using moving test images, and the resulting predicted images were compared with conventional methods such as the block matching method using the criteria of SNR and entropy. The results showed that SNR and entropy of the proposed method are better than those of conventional methods. Also, the proposed method was applied to very low bit-rate image coding at 16 kbit/s, and was compared with a conventional method, H.261. The resulting SNR and decoded images in the proposed method were better than those of H.261. We conclude that the proposed method is effective as a motion-compensated prediction method.

Gray scale images are represented by recurrent neural subnetworks which together with a competition layer create an associative memory. The single recurrent subnetwork Ni implements a stochastic nonlinear fractal operator Fi, constructed for the given image fi. We show that under realstic assumptions F has a unique attractor which is located in the vicinity of the original image. Therefore one subnetwork represents one original image. The associative recall is implemented in two stages. Firstly, the competition layer finds the most invariant subnetwork for the given input noisy image g. Next, the selected recurrent subnetwork in few (5-10) global iterations produces high quality approximation of the original image. The degree of invariance for the subnetwork Ni on the inprt g is measured by a norm ||g-Fi(g)||. We have experimentally verified that associative recall for images of natural scenes with pixel values in [0, 255] is successful even when Gaussian noise has the standard deviation σ as large as 500. Moreover, the norm, computed only on 10% of pixels chosen randomly from images still successfuly recalls a close approximation of original image. Comparing to Amari-Hopfield associative memory, our solution has no spurious states, is less sensitive to noise, and its network complexity is significantly lower. However, for each new stored image a new subnetwork must be added.

From a GF(q) sequence {ai}i0 with period qn - 1 we can obtain new periodic sequences {ai}i0 with period qn by inserting one symbol b GF(q) at the end of each period. Let b0 = Σqn-2 i=0 ai. It Is first shown that the linear complexity of {ai}i0, denoted as LC({ai}) satisfies LC({ai}) = qn if b -b0 and LC({ai}) qn - 1 if b = -b0 Most of known sequences are shown to satisfy the zero sum property, i.e., b0 = 0. For such sequences satisfying b0 = 0 it is shown that qn - LC({ai}) LC({ai}) qn - 1 if b = 0.

This paper presents an overview of research activities in Japan in the field of very low bit-rate video coding. Related research based on the concept of "intelligent image coding" started in the mid-1980's. Although this concept originated from the consideration of a new type of image coding, it can also be applied to other interesting applications such as human interface and psychology. On the other hand, since the beginning of the 1990's, research on the improvement of waveform coding has been actively performed to realize very low bit-rate video coding. Key techniques employed here are improvement of motion compensation and adoption of region segmentation. In addition to the above, we propose new concepts of image coding, which have the potential to open up new aspects of image coding, e.g., ideas of interactive image coding, integrated 3-D visual communication and coding of multimedia information considering mutual relationship amongst various media.

Entire systems on a chip (SOCs) embodying a processor, memory, and system-specific peripheral hardware are now an everyday reality. The current generation of SOC designers are driven more than ever by the need to lower chip cost, while at the same time being faced with demands to get designs to market more quickly. It was to support this new community of designers that we developed Satsuki-an integrated processor synthesis and compiler generation system. By allowing the designer to tune the processor design to the bitwidth and performance required by the application, minimum cost designs are achieved. Using synthesis to implement the processor in the same technology as the rest of the chip, allows for global chip optimization from the perspective of the system as a whole and assures design portability. The integral compiler generator, driven by the same parameters used for processor synthesis, promotes high-level expression of application algorithms while at the same time isolating the application software from the processor implementation. Synthesis experiments incorporating a 0.8 micron CMOS gate array have produced designs ranging from a 45 MHz, 1,500 gate, 8-bit processor with a 4-word register file to a 31 MHz, 9,800 gate, 32-bit processor with a 16-word register file.

3D model-based coding methods that need 3D reconstruction techniques are proposed for next-generation image coding methods. A method is presented that reconstructs 3D shapes of dynamic objects from image sequences captured using two cameras, thus avoiding the stereo correspondence problem. A coaxial camera system consisting of one moving and one static camera was developed. The optical axes of both cameras are precisely adjusted and have the same orientation using an optical system with true and half mirrors. The moving camera is moved along a straight horizontal line. This method can reconstruct 3D shapes of static objects as well as dynamic objects using motion vectors calculated from the moving camera images and revised using the static camera image. The method was tested successfully on real images by reconstructing a moving human shape.

Many numerical simulation problems of natural phenomena are formulated by large tridiagonal and block tridiagonal linear systems. In this paper, an efficient parallel algorithm to solve a tridiagonal linear system is proposed. The algorithm named bi-recurrence algorithm has an inherent parallelism which is suitable for parallel processing. Its time complexity is 8N - 4 for a tridiagonal linear system of order N. The complexity is little more than the Gaussian elimination algorithm. For parallel implementation with two processors, the time complexity is 4N - 1. Based on the bi-recurrence algorithm, a VLSI oriented tridiagonal solver is designed, which has an architecture of 1-D linear systolic array with three processing cells. The systolic tridiagonal solver completes finding the solution of a tridiagonal linear system in 3N + 6 units of time. A highly parallel systolic tridiagonal solver is also presented. The solver is characterized by highly parallel computability which originates in the divide-and-conquer strategy and high cost performance which originates in the systolic architecture. This solver completes finding the solution in 10(N/p) + 6p + 23 time units, where p is the number of partitions of the system.

This paper addresses the problem of estimating 3-D motion of a rigid object from a sequence of monocular 2-D images. The surface of object is assumed to be modeled with several patches, each of which is expressed by an implicit equation. The proposed method estimates the pose (i.e., the location and orientation) of object that corresponds to each image in the sequence: The sequence of the estimated poses gives the motion of the object. The estimation is done by solving a system of equations, each of which is typically an algebraic equation of low degree, that is derived from the expressions of the surface patches and image contours data: so the method does not require establishing the correspondence between successive two frames in the image sequence or computing optic flow. Allowing several-patch models for objects enables the proposed approach to deal with a great variety of objects. The paper includes a numerical example, where our aproach has been applied to a polyhedral object modeled with several patches.

C1 class smooth interpolation by a fuzzy reasoning for a small data set is proposed. The drafting technique of a human expert is implemented by using a set of fuzzy rules. The effectiveness of the present method is verified by computer simulations and by applications to the practical interpolation problem in a power system.

A new application of the factorization method is reported for 3-D shape reconstruction from endoscope image sequences. The feasibility of the method is verified with some theoretical considerations and results of extensive experiments. This method was developed by Tomasi and Kanade, and improved by Poelman and Kanade, with the aim of achieving accurate shape reconstruction by using a large number of points and images, and robustly applying well-understood matrix computations. However, the latter stage of the method, called normalization, is not as easily understandable as the use of singular value decomposition in the first stage. In fact, as shown in this report, many choices are possible for this normalization and a variety of results have been obtained depending on the choice. This method is easy to understand, easy to implement, and provides sufficient accuracy when the approximation used for the optical system is reasonable. However, the details of the theoretical basis require further study.

The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree3 in a network, is bound to some constant K0.

For the dependent protocols to perform the server-aided RSA secret computation, the damage caused by the active attacks is greater than that by the passive attacks. Though there are two dependent proposed protocols against active attacks, the cost of the two protocols is still high. In this paper, we propose two efficient dependent protocols. Even considering the low cost of these two protocols, they can also guard against the proposed active attacks.

M-ary orthogonal keying (MOK) systems under carrier frequency offset (CFO) are investigated. It is shown that spurious signals are introduced by the offset frequency components of spectrum after multiplication in correlation detection process, and some conditions on robust orthogonal signal sets are derived. Walsh function sets are found to be very weak against CFO, since they produce large spurious signals. As robust orthogonal signal sets against CFO, the rows of circulant Hadamard matrices are proposed and their error performanses are evaluated. The results show that they are good M-ary orthogonal signal sets in the presence of CFO.

Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.

In this paper, we define the distortion at a certain complexity level, which is the dual quantity of the distortion-complexity. We prove a theorem dual to the theorem which we have given of the asymptotic property of the distortion-complexity. We also give a universal data-base for fixed-rate data compression with distortion and prove its asymptotic optimality.

There are many kinds of transmission lines such as uniform, nonuniform and nonlinear ones terminated by linear and/or nonlinear subnetworks. The nonuniform transmission lines are crucial in integrated circuits and printed circuit boards, because these circuits have complex geometries and layout between the multi layers, and most of the transmission lines possess nonuniform characteristics. On the other hand, the nonlinear transmission line have been focused in the fields of communication and instrumentation. Here, we present a new numerical method for analyzing nonuniform and nonlinear transmission lines with linear and/or nonlinear terminations. The waveforms at any points along the lines are described by the Fourier expansions. The partial differential equations representing the circuit are transformed into a set of ordinary differential equations at each frequency component, where for nonlinear transmission line, the perturbation technique is applied. The method is efficiently applied to weakly nonlinear transmission line. The nonuniform transmission lines terminated by a nonlinear subnetwork are analyzed by hybrid frequency-domain method. The stability for stiff circuit is improved by introducing compensation element. The efficiency of our method is illustrated by some examples.

We study Lempel-Ziv-Yokoo algorithm [1, Algorithm 4] for universal data compression. In this paper, we give a simpler implementation of Lempel-Ziv-Yokoo algorithm than the original one [1, Algorithm 4] and show its asymptotic optimality for a stationary ergodic source.